|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.
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.)||
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.
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.||
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.
SLB 6.4, 6.5.
Paper on action-graph games.
|10/17||Repeated games. Folk theorem. Stochastic games.||Slides.
SLB 6.1, 6.2.
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.
|11/2||Collusion. Use of false names over the Internet.||Project progress report (~2 pages)
Homework 3 out.
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/9||Automated mechanism design.||Slides.
Chapter on automated mechanism design, read up to and including 6.6.
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.||
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.||
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.|
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.
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.|