CPS 296.2 - Computational Game Theory and Mechanism Design

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. There is also increasing interest in the systems community.

2. The course will also be open to interested students outside of computer science, for example students in economics or mathematics. Such students should talk to Vince before the start of the course to discuss background issues and what you hope to get out of the course. Requirements may be individualized for such students to take background disadvantages (and advantages) into account.

Prerequisites
Basic knowledge of probability, algorithms, and (very basic) computational complexity. Undergraduates are welcome provided they have the required background. Interested students without computer science backgrounds (e.g. students in economics or mathematics) should talk to Vince first.

Grading
Participation: 5%
Assignments: 15%
Midterm: 15%
Quizzes: 15%
Project: 50%

A few surprise quizzes will be given during the course. Such a quiz will take place at the end of a class. So make sure that you are following what is happening - ask questions! Also, you should read the slides and other materials before class. If you do so, the quizzes should be easy. If you miss a quiz (hopefully for a good reason), you will be asked to do something more difficult to make up for it.

You may discuss assignments with at most one other person. Each person must do her or his own writeup. Moreover, you may not simply write down a solution and give it to the other person. You may present things to each other on (say) a whiteboard, but the other person should not simply be copying things over. You should acknowledge everyone you worked with, as well as all other sources, on the writeup. Assignments are always due immediately at the beginning of class.

Auditing the course
Auditing is discouraged for undergraduate and junior graduate students in computer science. Arrangements for students outside of computer science can be made on an individual basis. Anyone wishing to audit the course should talk to Vince before the start of the course.

Book
We will use parts of a new book by Shoham and Leyton-Brown (SLB), an early draft of which can be found in a subdirectory of this directory called book/ under the name SLB.pdf. (Just append book/SLB.pdf to the URL in your browser -- I do not want to make a link to the draft. Access from within Duke only.) The draft appears to be very good, but let me know if you find anything that does not seem to be accurate. Also let me know if you need references, which are still missing from this draft. Please do not distribute the draft.

There will be additional readings for individual classes. The slides for the course should also be considered part of the reading.

Some additional books that you could use as references (very much optional):

Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Algorithmic Game Theory.

General microeconomic theory:
Andreu Mas-Colell, Michael D. Whinston, Jerry R. Green, Microeconomic Theory. (Especially Part 2: Game Theory, and Part 5: Welfare Economics and Incentives (which studies mechanism design).)

Game theory:
Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory.
Drew Fudenberg and Jean Tirole, Game Theory.

Combinatorial auctions:
Peter Cramton, Yoav Shoham, Richard Steinberg, Combinatorial Auctions. (Some of the chapters of this book can be found online.)

Many of the topics in the course are also covered in Vince's thesis, which you may find is another useful resource.

Schedule

Date	Topic	Materials
8/29	Course at a glance. What problems are we trying to solve? Example applications: game playing, trading agents, preference aggregation, elections, electronic marketplaces, resource allocation, routing.	Slides.
8/31	Risk neutrality and risk aversion. Expected utility theory. Games in normal form. Dominance and iterated dominance. Computing dominated strategies.	Slides. Homework 1 out. SLB Appendices B and D (if you need them); Sections 3.1, 3.2, Subsection 3.3.3, Section 4.7. Paper on computing dominated strategies. (You can skip the part on Bayesian games.)
9/5	Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. Correlated equilibrium. Computing correlated equilibria.	Slides. SLB 3.3.1, 3.3.2, 3.3.5, 3.3.6, 4.1, 4.2.1, 4.2.4, 4.4, 4.5, 4.6, 4.8. Paper on computing Nash equilibria. (You only need to read the part concerning 2-player games.)
9/7	Games in extensive form. Backwards induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements.	Slides. SLB Chapter 5; you can skip alpha-beta, 5.2.3, and 5.2.4.
9/11, 1-2pm, LSRC D344	Special lecture: Computing Kemeny and Slater rankings. (Vince is giving this talk on voting in the algorithms seminar and it lines up nicely with the course, so please try to attend it. The lecture on these topics that was planned for later in the course will probably be skipped.)	Slides. Kemeny paper, Slater paper. (Will not be covered in the midterm.)
9/12	Preference aggregation/social choice. Voting rules. Desirable properties of voting rules. Arrow's impossibility theorem. Muller-Satterthwaite impossibility theorem. Manipulation. Gibbard-Satterthwaite impossibility theorem. Single-peaked preferences.	Slides. Quiz 1 bonus questions slides. SLB Chapter 7. Section on voting with some more voting rules.
9/14	Bayesian games. Mechanism design. Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Groves mechanisms.	Homework 1 due. Homework 2 out. Slides. SLB 6.3, Chapter 8 (up to and including 8.7). Alternative resources with roughly the same content: Chapter on mechanism design + chapter on revelation principle. Parkes chapter on mechanism design.
9/19	Mechanism design continued.
9/21	Auctions. English, Japanese, Dutch, first-price sealed-bid, second-price sealed-bid (Vickrey). Revenue equivalence. Redistribution. Myerson's "optimal" auction. Reverse auctions. Exchanges. Myerson-Satterthwaite impossibility theorem.	Slides. SLB 9.1, 9.2. Paper on redistribution.
9/22, 1:30-2:30pm, LSRC D344	Special lecture: Common voting rules as maximum likelihood estimators. (Vince is giving this talk on voting in the DRIV seminar; it lines up nicely with the course and there may be some project ideas there, so please try to attend it.)	Slides. Paper. (Will not be covered in the midterm.)
9/26	Combinatorial auctions. Bidding languages. Winner determination. Generalized Vickrey auction. Combinatorial reverse auctions and exchanges.	Slides. SLB 9.3.1, 9.3.2, 9.3.3. Optional: Lehmann et al. chapter on winner determination. Sandholm chapter on optimal winner determination.
9/28	Preference elicitation in voting and auctions. Iterative combinatorial auctions. Communication complexity. Restricted classes of valuations.	Slides. Optional: Parkes chapter on iterative CAs. Sandholm-Boutilier chapter on preference elicitation in CAs.
10/3	Preference elicitation continued. Review for midterm (bring questions!).	Project proposal (1+ pages) due.
10/5	MIDTERM. Covers all material covered in class so far.	Copy of midterm.
10/10	Fall break. No class.
10/12	Midterm solutions. Concise representations of games. Congestion games. Potential games. Graphical games. Action-graph games. MAIDs.	Homework 2 due. Slides. SLB 6.4, 6.5. Optional: Paper on action-graph games.
10/17	Repeated games. Folk theorem. Stochastic games.	Slides. SLB 6.1, 6.2. Optional: Paper on computing a Nash equilibrium in repeated games. Paper on stochastic games and learning.
10/19	Repeated and stochastic games continued.
10/24	Learning in games. Iterated best response. Fictitious play. No-regret algorithms. Targeted learning. Evolutionary game theory.	Slides. SLB 14.1, 14.2, 14.5, 14.6, 14.7.1, 14.7.2.
10/26	Cooperative/coalitional game theory. Core. Nucleolus. Shapley value. Computing solutions.	Slides. SLB Chapter 11.
10/31	No class.
11/2	Collusion. Use of false names over the Internet.	Project progress report (~2 pages) due. Homework 3 out. Slides. Optional: Paper on collusion in combinatorial auctions and exchanges. Paper on false-name bidding. Another paper on false-name bidding. Paper on collusion/false names in coalitional game theory.
11/7	No class.
11/9	Automated mechanism design.	Slides. Chapter on automated mechanism design, read up to and including 6.6. Optional: Remainder of the chapter. Paper on automatically creating multistage mechanisms.
11/14	Algorithmic mechanism design. Approximately efficient truthful combinatorial auctions. Shortest paths. Minimizing make-span. Characterizing allocation rules that can be made incentive compatible.	Slides. Optional: Paper on algorithmic mechanism design. Paper on computing Clarke payments for shortest paths. Paper on approximately efficient, incentive compatible combinatorial auctions. Paper on characterizing which allocation rules can be made incentive compatible.
11/16	Computational hardness as a barrier against manipulation. Limitations.	Slides. Optional: Paper on STV being hard to manipulate. Paper on using a preround to increase hardness. Papers 1 and 2 on hardness with few alternatives. Papers 1 and 2 on voting rules usually being easy to manipulate.
11/20, 11:45am-12:45pm, LSRC D106	Special lecture: Nicole Immorlica (Department Colloquium). Derandomizing auctions that are approximately optimal in the worst case.	Paper.
11/21	Wrapping up. Student project presentations: Mason: Selectively Processing Surveillance Video Using Game-Theoretic Reasoning Mingyu: A Family of Strategy-proof Redistribution Mechanisms for VCG Payments	Homework 3 due. Optional: Paper on redistribution (again).
11/23	Thanksgiving break. No class.
11/28	Student project presentations: Susanna: Manipulating with Incomplete Information Neeti: Applying Scoring Rules to Integrated Classifiers Joe: Partially Solving Games with Bounds on Utilities
11/30	Student project presentations: Rolando: Automated Mechanism Design with Collusion Handling Zheng: Voting as MLE with Gaussian Noise Model Mac: Can you trust eBay? The Computational Complexity of Auction Control	Final project writeup due.

Projects
A final project will be a major component of this course. The expectation is that students will attempt to do some original work on topics related to the course. Students may work on the project alone or in pairs (with pairs expected to do larger projects). If there is a good reason to have even more people on one team, this may be considered. The project may be theoretical or experimental; creativity is encouraged. The final product is a writeup (in the form of a research paper) and a class presentation (all team members must participate in the presentation). Some projects may well lead to publishable papers (perhaps with some additional work).

In order to produce a strong project, it is important to start thinking about the project early. An initial proposal is due early in the course. This proposal should explain the topic of your project, what types of results you hope to obtain, and what some of the technical issues are that you will need to address. If necessary, Vince can help with finding topics. Some general suggestions for finding topics:

1. Look ahead in the course for topics that sound interesting to you. If materials on that topic are not yet available, talk to Vince for pointers (perhaps he can even make the slides for that topic a little early for you).

2. Consider your own research and its relationship to the course. Do you work on techniques that can be applied to any of the course's problems? Can techniques in the course help your work?

3. Take some result in the course that you like, and change the setting. Do things become easier (harder) if we look at a more restricted (more general) version of the problem? Do analogous results hold in similar settings?

More specific topics can be found here (access from within Duke only).

An intermediate project progress report is also required. This report should explain what results you have obtained already, what (if any) difficulties you encountered, and what you plan to do to complete your project. Ideally, at this point, you should already have some good results, so that you can spend the rest of your time on answering questions generated by your results, as well as preparing your writeup and presentation.

Your project grade will depend on the proposal and progress report as well as the final writeup and presentation.

Project presentation guidelines: Each presentation will last 75 minutes / 3 = 25 minutes, you should probably talk for 20 minutes so that there will be some time for questions and discussion at the end as well. I imagine that you will want to make some slides; if you prefer to give the talk on the whiteboard, that is OK, but I still expect it to be a well-prepared talk, so you should know exactly what you will write on the board. (I would think that doing a good whiteboard talk would be more difficult.) You should clearly explain the context of what you are doing (prior research), so that your classmates can follow your presentation. You can assume that your audience knows what we have covered in class, though it is probably good to briefly remind them of the relevant parts of the course. Then, you should make clear what you have done, what you still plan to do, and what would be nice to do in future research but you will not do for this course.

List of optional references
The below list of references is intended to help students learn more about topics that they are especially interested in, by giving them a place to start reading. Many of the papers should be easy to find online (e.g. authors' web pages). These are not all required readings. Please refer to the schedule for the required readings.

Normal-form games and computing Nash equilibria/other solutions
Simple Search Methods for Finding a Nash Equilibrium. Porter, Nudelman, Shoham. Games and Economic Behavior (to appear). Early version in AAAI-04.
Algorithms for Rationalizability and CURB Sets. Benisch, Davis, Sandholm. AAAI-06.
Computing the Optimal Strategy to Commit to. Conitzer, Sandholm. EC-06.
A Technique for Reducing Normal-Form Games to Compute a Nash Equilibrium. Conitzer, Sandholm. AAMAS-06.
Hard-to-Solve Bimatrix Games. Savani, von Stengel. Econometrica, 2006.
Complexity of (Iterated) Dominance. Conitzer, Sandholm. EC-06.
Settling the Complexity of 2-Player Nash Equilibrium. Chen, Deng. ECCC, 2005.
Mixed-Integer Programming Methods for Finding Nash Equilibria. Sandholm, Gilpin, Conitzer. AAAI-05.
A Generalized Strategy Eliminability Criterion and Computational Methods for Applying It. Conitzer, Sandholm. AAAI-05.
Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms. Nudelman, Wortman, Shoham, Leyton-Brown. AAMAS-04.
Complexity Results about Nash Equilibria. Conitzer, Sandholm. IJCAI-03.
Computing Equilibria for Two-Person Games. von Stengel. Handbook of Game Theory, Chapter 45.
Nash and Correlated Equilibria: Some Complexity Considerations. Gilboa, Zemel. Games and Economic Behavior, 1989.
The Complexity of Eliminating Dominated Strategies. Gilboa, Kalai, Zemel. Mathematics of Operations Research, 1993.
A Program for Finding Nash Equilibria. Dickhaut, Kaplan. Mathematica Journal, 1991.

Coalitional/cooperative games and computing solutions
Multi-Attribute Coalitional Games. Ieong, Shoham. EC-06.
Complexity of Constructing Solutions in the Core Based on Synergies Among Coalitions. Conitzer, Sandholm. AIJ-06. Early version in IJCAI-03.
Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games. Ieong, Shoham. EC-05.
Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in Multi-Issue Domains. Conitzer, Sandholm. AAAI-04.
On the Complexity of Cooperative Game Solution Concepts. Deng, Papadimitriou. Mathematics of Operations Research, 1994.