Kate Larson

Mechanism Design for Computationally-Limited Agents Degree Type: Ph.D. in Computer Science
Advisor(s): Tuomas Sandholm
Graduated: August 2004

Abstract:

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 both optimally determining their utilities from the game and determining 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 provide a theory of interaction for self-interested computationally bounded agents. This allows one to formally study the impact that bounded rationality has on agents' strategic behavior. It also provides a foundation for game-theory and mechanism design for computationally limited agents.

First, this thesis introduces a model of bounded rationality where agents must compute in order to determine their preferences. The computing resources of the agents are restricted so that the agents must carefully decide how to best use their computation. I present a fully normative model of deliberation control, the performance profile tree. Not only does this structure provide full normativity in theory, but I also show that in real-world applications it improves deliberation control compared to other methods.

This thesis proposes explicitly incorporating the deliberation actions of agents into a game-theoretic framework. I introduce a new game-theoretic solution concept, the deliberation equilibrium. This provides one with an approach for understanding and analyzing the strategic use of computation. Using this approach I analyze different negotiation protocols for computationally limited agents. I study two different bargaining settings where agents try to reach an agreement on whether to coordinate their actions or act independently. I provide algorithms that agents can use to determine their optimal strategies (including computing actions). I also study the impact that computing limitations have on bidding agents in auctions, where agents must compute or gather information in order to determine their valuations for the items being auctioned. I show that commonly used auction mechanisms all suffer from agents having incentive to strategically deliberate, that is use computing resources in order to (partially) determine their competitors' valuations. This means that mechanisms which had dominant strategy equilibria for rational agents are no longer strategy-proof for computationally limited agents.

Finally, this thesis studies the problem of designing mechanisms specifically for computationally-limited agents. My goal is to build mechanisms which have good deliberative properties as well as good economic properties. I propose a set of properties that I believe that mechanisms should exhibit, but then show that it is impossible to design interesting mechanisms which satisfy all the properties. While this result is negative, in that it is an impossibility result, it does provide direction for future research.

Thesis Committee:
Tuomas Sandholm (Chair)
Avrim Blum
Andrew Moore
Craig Boutilier (University of Toronto)
Mark Satterthwaite (Northwestern University)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Artificial intelligence, multiagent systems, game theory, mechanism design, bounded rationality, resource bounded reasoning