Computer Science Department
School of Computer Science, Carnegie Mellon University
Mechanism Design for Computationally Limited Agents
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.