04-07

Mechanism Design for Computationally Limited Agents

The frameworks of game theory and mechanism design have exerted significant influence on formal models of multiagent systems and electronic markets by providing tools for designing and analyzing systems in order to guarantee certain desirable outcomes. However, many game-theoretic models assume idealized rational decision makers interacting in prescribed ways. In particular, the models often ignore the fact that in many systems the agents are not fully rational, but instead have constraints on their computational capabilities which inhibit them from acting as fully rational agents would. This creates a potentially hazardous gap in game theory and automated negotiation as agents may not be motivated to behave in the expected way, leading to potentially undesirable outcomes.

In this talk I will present work aimed at bridging this gap. By explicitly incorporating the deliberation (computational and information gathering) actions of agents into their strategies, we are able to provide a theory of interaction for self-interested computationally-bounded agents. I will describe a new game-theoretic solution concept, the deliberation equilibrium and use this concept to analyze several classic and commonly used auctions. In particular, I will illustrate the complex strategic behavior which arises when agents have deliberation limitations, which has been overlooked by traditional analysis. I will conclude by discussing mechanism design principles for multiagent systems and electronic markets with resource-bounded agents.