Mechanism Design for Computationally Bounded Agents
The frameworks of game theory and mechanism design have exerted significant influence on formal models of multiagent systems 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 multiagent systems, the agents are not fully rational. Instead they are computational agents who have time and cost constraints that hinder them from optimally determining their utilities from the game and which strategies are best to follow. Because of this, the game theoretic equilibrium for rational agents does not generally remain the same for agents with bounds on their computational capabilities. This creates a potentially hazardous gap in game theory and automated negotiation since computationally bounded agents are not motivated to behave in the desired way. My thesis statement is that it is possible to bridge this gap. By incorporating computational actions into the strategies of agents, I plan to provide a theory of interaction for self-interested computationally-bounded agents. I will present a fully normative model of computation control which allows agents to make online decisions based on results of their computation and the restrictions placed on their computational capabilities. Using this model, I propose a new game theoretic solution concept, the deliberation equilibrium. This solution concept will allow me to investigate the impact computational restrictions have on agents' strategies in different mechanisms and will provide a foundation for developing mechanism design tools for computationally bounded agents. I finally propose to show experimentally that the model of computation control is feasible and general, and that it is possible to design robust multiagent systems for computationally bounded agents.