| Lec. No. |
Date |
Topic |
Readings
(From Shoham and Leyton-Brown text) |
Additional Materials
(Optional) |
HW |
| 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 this | Algorithmic 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 Sets | HW2 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) |
