Harvard Logo

Class schedule

Lec. No. Date Topic Readings
(From Shoham and Leyton-Brown text)
Additional Materials
1 Thur 9/2 Introduction
(Handouts: [1] and [2])
no assignment
2 Tue 9/7 Cooperative Agents: Distributed Constraint Satisfaction Chapter 1 Kearns, Montfort, and Suri, An experimental study of the Coloring Problem on Human Subject Networks, Hogg and Huberman, Better Than the Best: The Power of Cooperation, Yokoo and Hirayama, Algorithsms for Distributed Constraint Satisfaction: A Review
3 Thur 9/9 Cooperative Agents: Distributed Optimization Chapter 2 Mailer and Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Petcu and Faltings, DPOP: A Scalable Method for Multiagent Constraint Optimization, Modi, Shen, Tambe and Yokoo, ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees, Maheswaran et al., Taking DCOP to the RealWorld: Efficient Complete Solutions for Distributed Multi-Event Scheduling, Excerpts from Russel and Norvig's AI textbook on refutation completeness (the meat is in pages 350-353) 1 and 2
4 Tue 9/14 Non-Cooperative Game Theory Chapter 3 (not 3.3.4, 3.4.5 and 3.4.7) Osborne and Rubinstein, A course in game theory, Iterated Regret Minimization: A New Solution Concept by Halpern and Pass, 2009.
5 Thur 9/16 Nash's theorem Section 3.3.4 John F. Nash, Jr., Non-cooperative games, Annals of Mathematics, 54 (1951) 286-295.
Tue 9/21 (Guest lecture by Ian Kash) Correlated Equilibrium Sections 3.4.5 and 3.4.7, and also thisAlgorithmic Game Theory by Nisan, Roughgarden, Tardos and Vazirani
6 Thur 9/23 Computation for Normal-Form Games Chapter 4 (not 4.2.2) Constantinos Daskalakis, Paul W. Goldberg and Christos Papadimitriou, The Complexity of Computing a Nash Equilibrium, Andrew Gilpin, Tuomas Sandholm, and Troels Bjerre Sensen, A heads-up no-limit Texas Hold'em poker player: Discretized betting models and automatically generated equilibrium-finding programs, Cheng et al.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 and Wilson, A Global Newton Method to Compute Nash Equilibria
7 Tue 9/28 Lemke-Howson algorithm Section 4.2.2 von Stengel, Equilibrium computation for games in strategic and extensive form HW 1 out
8 Thur 9/30 Games with Sequential Actions Chapter 5 Osborne and Rubinstein, A course in game theory
9 Tue 10/5 Repeated Games, Stochastic Games and Bayesian Games
Sections 6.1-6.3 Rubinstein, Chapter 8 Modeling Bounded Rationality MIT Press, 1998, Halpern and Pass, Game Theory with Costly Computation, Fortnow and Santhanam Bounding Rationality by Discounting Time
10 Thur 10/7 Congestion games, Potential games and Price of Anarchy Section 6.4 Roughgarden, Computing equilibria: A computational complexity perspective, Roughgarden and Tardos, Bounding the inefficiency of equilibria in nonatomic congestion games HW1 due
11 Tue 10/12 Computationally motivated graphical representations
Section 6.5 Jiang, Leyron-Brown and Bhat, Action-Graph Games, Papadimitriou and Roughgarden, Computing Correlated Equilibria in Multi-Player Games, Daskalakis, Fabrikant and Papadimitriou, The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games, Elkind, Goldberg and Goldberg, Nash Equilibria in Graphical Games on Trees Revisited, Koller and Milch, Multi-Agent Influence Diagrams for Representing and Solving Games, Kearns, Littman and Singh, Graphical Models for Game Theory, Pfeffer and Gal, On the reasoning patterns of agents in games, Pfeffer and Gal, Networks of Influence Diagrams: A Formalism for Representing Agents' Beliefs and Decision-Making Processes, Stein et al. Exchangeable equilibria contradicting exactness of the Papadimitriou-Roughgarden algorithm
12 Thur 10/14
(Led by Antos)
Learning and Teaching
Section 7.1, 7.2, 7.3 and 7.7
Shoham, Powers and Grenager, On the Agenda(s) of Research on Multi-Agent Learning
Augmann, Rationality and Bounded Rationality, Hart and Mansour, How Long to Equilibrium? The Communication Complexity of Uncoupled Equilibrium Procedures, Fudenberg and Kreps, Learning Mixed Equilibria, Kalai and Lehrer, Rational Learning Leads to Nash Equilibrium, Knox and Stone, Combining Manual Feedback with Subsequent MDP Reward Signals for Reinforcement Learning
13 Tue 10/19 Learning: Algorithmic Approaches
Section 7.4, 7.5 and 7.6 Powers and ShohamLearning against opponents with bounded memory, Greenwald and Hall, Correlated-Q Learning, Hu and Wellman, Nash Q-Learning for General-Sum Stochastic Games
14 Thur 10/21 Class Discussion No assignment
(Submit discussion points) Readings: Bolton, Greiner and Ockenfels, Engineering Trust: Reciprocity in the Production of Reputation Information, Pickard et al. Title: Time Critical Social Mobilization: The DARPA Network Challenge Winning Strategy
15 Tue 10/26 Aggregating Preferences: Social Choice Chapter 9 Altman and Tennenholtz, Ranking systems: The PageRank Axioms,Dwork, Kumar, Naor and Sivakumar, Rank aggregation methods for the web Tideman, Independence of clones as a criterion for voting rules, S. Barbera, An introduction to strategy-proof social choice functions HW 2 out
17 Thu 10/28 Protocols for Strategic Agents I Sections 10.1-10.4 Rothkopf, Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical, Ausubel and Milgrom, The Lovely but Lonely Vickrey Auction, Varian Mechanism Design for Computerized Agents, Nisan Introduction to mechainsm design (a brief introduction), Jackson Mechanism Theory
18 Tue 11/2 Protocols for Strategic Agents II Sections 10.5, 10.6 and 10.7 McGrew and Shoham, Using Contracts to Influence the Outcome of a Game, Feigenbaum, Shenker and Papadimitriou, Sharing the Cost of Multicast Trasmissions, Lehmann, Shoham and O'Callaghan, Truth Revelation in Approximately Efficient Combinatorial Auctions, Nisan and Ronen, Computationally Feasible VCG Mechanisms
19 Thur 11/4 Protocols for Strategic Agents III
Sections 11.1-11.4 Cramton and Schwartz, Collusive Bidding: Lessons from the FCC spectrum auctions, Nisan, Bidding and Allocation in Combinatorial Auctions, de Vries and Vohra, Combinatorial Auctions: A survey, Sandholm, Expressive Commerce and its Applications to Sourcing: How we conducted $35B of Generalized Combinatorial Auctions, Nisan and Blumrosen Combinatorial auctions, Pennock and Sami, Computational aspects of prediction markets, Hartline, Lectures on Optimal Mechainsm Design, Edelman, Ostrovsky and Schwartz, Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords
16 Tue 11/9 (guest lecturer Ariel Procacia) Computational Social Choice Bartholdi, Tovey and Trick The computational difficulty of manipulating an election, Faliszewski and Procaccia, AI's war on manipulation: Are we winning?, Conitzer and Sandholm, Common Voting Rules as Maximum Likelihood Estimators Multi-issue voting. False name proof. Complexity. Bartholdi and Orlin, Single Transferable Vote Resists Strategic Voting, Conitzer, Sandholm and Lang, When are elections with few candidates hard to manipulate?, Bartholdi, Tovey and Trick, Voting schemes for which it can be difficult to tell who won the election, Xia and Conitzer, Stackelberg Voting Games: Computational Aspects and Paradoxes, Zuckerman, Procaccia and Rosenschein, Algorithms for the Coalitional Manipulation Problem, Brandt, Fischer, and Harrenstein The Computational Complexity of Choice SetsHW2 due 11/10!
Thur 11/11 Holiday!
20 Tue 11/16 Stability and Power of Agent Coalitions
Chapter 12 Conitzer and Sandholm, Complexity of constructing solutions in the core based on synergies among coalitions, Pickard et al., Time Critical Social Mobilization: The DARPA Network Challenge Winning Strategy, E. Markakis and A. Saberi, On the Core of the Multicommodity Flow Game, Ieong and Shoham, Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games, Goldberg, Goldberg and Wooldridge, Computational Complexity of Weighted Threshold Games HW3 out
21 Thur 11/18 Reputation, Scrip and Currency Systems

Please bring 1-page proposal for exp. paper!
Friedman, Resnick and Sami Manipulation-Resistant Reputation Systems, Reeves, Soule and Kasturi, Yootopia!, Kash, Friedman and Halpern, Optimizing Scrip Systems: Efficiency, Crashes, Hoarders, and Altruists Piatek et al., One hop reputations for peer to peer file sharing workloads, Seuken, Tang and Parkes, Accounting Mechanisms for Distributed Work Systems, Altman and Tennenholtz, Incentive Compatible Ranking Systems, Cheng and Friedman, Sybilproof Reputation Mechanisms, Cheng and Friedman, Manipulability of PageRank under Sybil Strategies, Alon, Fischer, Procaccia and Tennenholtz, Sum of us: strategyproof selection from the selectors, Dandekar et al., Liquidity in Credit Networks: A Little Trust Goes a Long Way
22 Tue 11/23 Logics of Knowledge and Belief Chapter 13 Brafman, Halpern and Shoham, On the Knowledge requirement of tasks Moore, A formal theory of knowledge and action, Halpern and Moses Knowledge and common knowledge in a distributed environment
Thur 11/25 Thanksgiving (No class)
23 Tue 11/30
(Led by Antos)
Probability, Dynamics and Intention Chapter 14 Fagin and Halpern, Reasoning about knowledge and probability, Gardenfors Belief Revision: An Introduction, Cohen and Levesque Intention is Choice with Commitment, van der Hoek and Pauly, Modal logic for games and information, Maynard-Zhang and Lehmann Representing and aggregating conflicting beliefs, Rao and Georgeff Modeling rational agents within a BDI-architecture, Grosz, Hunsberger and Kraus, Planning and acting together HW3 due (23:59)
24 Thur 12/2 Class Discussion No assignment
Fri 12/10 Final paper due
(at 2pm to MD 133)