Computational Game Theory and Mechanism Design (CPS 296.2), Fall 2006
You may also be interested in: Topics in Computational Economics (CPS 296.3), Spring 2007


Details
Tu-Th 11:40-12:55, 306 North Building.
Instructor: Vincent Conitzer. (Please call me Vince.)

Office hour: Tu 3-4, LSRC D207.
Description
Computer scientists are increasingly confronted with settings where multiple self-interested parties interact. Two prominent examples are electronic marketplaces and networked computer systems.

To act optimally in such settings, each party (or "agent") must take into account how the other agents are likely to act. Game theory studies how this should be done, and it provides various solution concepts which prescribe how agents should act when the actions of other agents affect their utilities. For example, agents are said to play in Nash equilibrium if no single agent can benefit by deviating. In this course, we will review these concepts, as well as operationalize them by providing algorithms to compute the solutions. This will allow us to write software that performs well in multiagent settings (as well as to create good computer players for game-theoretically nontrivial games, such as poker).

Playing the game is only half the story. As computer scientists, we often get to design the game (the rules of the electronic marketplace, the system protocols, etc.). While we cannot directly control the behavior of (self-interested) users, we can give them incentives to behave in a desirable way. Mechanism design studies how to design the game (or "mechanism") so that self-interested behavior will lead to good outcomes. In this course, we will review basic results in mechanism design, including standard mechanisms as well as impossibility results. We will also study computational aspects of mechanism design, including efficiently eliciting information from the agents, computing the outcomes of mechanisms in various settings, and even optimizing the mechanism itself.

Throughout the course, we will consider applications such as (combinatorial) auctions, exchanges, and voting.
Recommended for:
1. Anyone in computer science who is interested. The amount of research on these topics in both the AI and theory communities has surged in recent years.