Class schedule
Class will follow the schedule below:
| Lec. No. | Date | Topic | Readings | Additional Materials |
|---|---|---|---|---|
| 1 | Tue 2/3 | Introduction | no assignment | |
| 2 | Thur 2/5 | Cooperation: Distributed Constraint Satisfaction | Chapter 1 | |
| 3 | Tue 2/10 | Cooperation: Distributed Optimization | Chapter 2 | |
| 4 | Thur 2/12 | Non-Cooperative Game Theory | Chapter 3 (not 3.3.4) | |
| 5 | Tue 2/17 | Nash's theorem | Section 3.3.4 | |
| 6 | Thur 2/19 | Computation for Normal-Form Games
(additional material: "Algorithmic Game Theory" by Nisan, Roughgarden, Tardos, Vazirani, chapter 2: part 1 and part 2, Cheng, Reeves, Vorobeychik, Wellman, "Notes on Equilibria in Symmetric Games", Nudelman, Wortman, Shoham, Leyton-Brown, "Understanding Game-Theoretic Algorithms: The Game Matters", Blum, Shelton, Koller, "A Continuation Method of Nash Equilibria in Structured Games", Scarf, "The Computation of Equilibrium Prices: An Exposition", Govindan, Wilson, "A Global Newton Method to Compute Nash Equilibria") |
Chapter 4 (not 4.2.2) | |
| 7 | Tue 2/24 | Lemke-Howson algorithm (also read chapter 3 from "Algorithmic Game Theory" by Nisan, Roughgarden, Tardos and Vazirani here) |
Section 4.2.2 | |
| 8 | Thur 2/26 | Games with Sequential Actions | Chapter 5 | |
| 9 | Tue 3/3 | Repeated Games, Stochastic Games and Bayesian Games (also read chapter 8 from Ariel Rubinstein, Modeling Bounded Rationality, MIT Press, 1998) |
Sections 6.1-6.3 | |
| 10 | Thur 3/5 | Congestion games, Potential games and Price of Anarchy (also see Roughgarden, T. Computing equilibria: A computational complexity perspective. Economic Theory, 2008 and Roughgarden, Tardos, Bounding the inefficiency of equilibria in nonatomic congestion games, Games and Economic Behavior, 47:2, May 2004, pp. 389-403) |
Section 6.4 | |
| 11 | Tue 3/10 | Computationally motivated graphical representations
(also read Action-Graph Games by Albert Xin Jiang, Kevin Leyton-Brown and Navin A.R. Bhat, Computing Correlated Equilibria in Multi-Player Games, by Papadimitriou and Roughgarden, The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games, by Daskalakis, Fabrikant, Papadimitriou, Nash Equilibria in Graphical Games on Trees Revisited, by Elkind, Goldberd and Goldberg, Multi-Agent Influence Diagrams for Representing and Solving Games, by Koller and Milch, Graphical Models for Game Theory by Kearns, Littman, Singh, On the reasoning patterns of agents in games, by Avi Pfeffer and Ya'akov Gal, Networks of Influence Diagrams: A Formalism for Representing Agents' Beliefs and Decision-Making Processes, by Avi Pfeffer and Ya'akov Gal ) |
Section 6.5 | |
| 12 | Thur 3/12 | Learning and Teaching (also read Rationality and Bounded Rationality, by Robert J. Aumann, Games and Economic Behavior 21, 2-14 (1997), How Long to Equilibrium? The Communication Complexity of Uncoupled Equilibrium Procedures, by Sergiu Hart and Yishay Mansour, STOC 2007, 345-353, Learning Mixed Equilibria, by Fudenberg and Kreps, Games and Economic Behavior 5, 320-367 (1993), Rational Learning Leads to Nash Equilibrium, by Ehud Kalai and Ehud Lehrer, Econometrica, 61:5, 1019-1046, Sep 1993, On the Agenda(s) of Research on Multi-Agent Learning, by Yoav Shoham, Rob Powers and Trond Grenager, In Proc. of Artificial Multiagent Learning: Papers from the 2004 AAAI Fall Symposium ) |
Section 7.1, 7.2, 7.3 and 7.7 | |
| 13 | Tue 3/17 | Learning: Algorithmic Approaches (also read Learning against opponents with bounded memory by Powers and Shoham, Correlated-Q Learning by Greenwald and Hall, Nash Q-Learning for General-Sum Stochastic Games by Hu and Wellman) |
Section 7.4, 7.5 and 7.6 | |
| 14 | Thur 3/19 | Class Discussion | no assignment | |
| 15 | Tue 3/31 | Aggregating Preferences: Social Choice | Chapter 9 | |
| 16 | Thur 4/2 | Protocols for Strategic Agents I | Sections 10.1, 10.2, 10.3, 10.41 | |
| 17 | Tue 4/7 | Protocols for Strategic Agents II (also see Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical by Michael H. Rothkopf, Operations Research Vol. 55, No. 2, March-April 2007, pp. 191-197, The Lovely but Lonely Vickrey Auction by Lawrence M. Ausubel and Paul Milgrom, Notes from CS 700, Fall 2008, Selling Billions of Dollars Worth of Keywords... by David Parkes ) |
Sections 10.42-10.47 | |
| 18 | Thur 4/9 | Protocols for Strategic Agents III (see also Using Contracts to Influence the Outcome of a Game by Robert McGrew and Yoav Shoham, AAAI-04, Sharing the Cost of Multicast Trasmissions by Joam Feigenbaum, Scott Shenker and Christos H. Papadimitriou, ACM Theory of Computing 2000, Truth Revelation in Approximately Efficient Combinatorial Auctions by Daniel Lehman, Yoav Shoham and Liadan Ita O'Callaghan, Computationally Feasible VCG Mechanisms by Noam Nisan and Amir Ronen ) |
Sections 10.5, 10.6 and 10.7 | |
| 19 | Tue 4/14 | Protocols for Multiagent Resource Allocation I (also see Notes on Myerson Optimal Auction by David Parkes) |
Sections 11.1 and 11.2 | |
| 20 | Thur 4/16 | Protocols for Multiagent Resource Allocation II (also see Collusive Bidding: Lessons from the FCC spectrum auctions by Carmton and Schwartz, Bidding and Allocation in Combinatorial Auctions by Nisan, Combinatorial Auctions: A survey by de Vries and Vohra, Expressive Commerce and its Applications to Sourcing: How we conducted $35B of Generalized Combinatorial Auctions by Sandholm, Algorithmic Game Theory, chapter 11, Algorithmic Game Theory, chapter 26) |
Sections 11.3 and 11.4 | |
| 21 | Tue 4/21 | Teams of Selfish Agents (also see Core Selecting Package Auctions by Day and Milgrom, Package Auctions & Exchanges by Milgrom, Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in Multi-Issue Domains by Conitzer and Sandholm, and An Anytime Approximation Method for the Inverse Shapley Value Problem by Fatima, Wooldridge and Jennings) |
Chapter 12 | |
| 22 | Thur 4/23 | Logics of Knowledge and Belief | Chapter 13 | |
| 23 | Tue 4/28 | Probability, Dynamics and Intention | Chapter 14 | |
| 24 | Thur 4/30 | Class Discussion | no assignment |