|
|
CS 324 Computer Science and Game
Theory |
This schedule is tentative: it probably will be changed during the quarter as the course develops. There is no textbook for this course; instead, the readings will be the original papers we cover. There will be occasional readings from the Multiagent Systems book (Shoham) and from Modelling Bounded Rationality (Rubinstein), but students don’t need to purchase either textbooks, as handouts of all readings will be given in class. Links to papers are provided below if available. These papers are not required reading before class, nor will students necessarily be required to learn the entirety of each paper. The list is provided for reference.
Date |
Topic |
Out |
Due
|
Reading Materials |
|
3/30 |
Normal Form Complexity I |
|
|
I. “The Complexity of Eliminating Dominated Strategies” by Gilboa, Kalai, and Zemel (1989) [handout only] II. Multiagent Systems, chapter 4, p. 124-129 |
|
4/1 |
Normal Form Complexity II |
|
|
I.
“A Note on Total Functions, Existence
Theorems, and Computational Complexity” by Nimrod II.
"Nash and Correlated Equilibria: Some
Complexity Considerations ", by Gilboa and
III. “Playing Large Games Using Simple Strategies” by Lipton, Markakis, and Mehta (2003) [PS] IV.
“Complexity Results about Nash Equilibria”
by Conitzer and Sandholm
(2003) [PDF] |
|
4/6 |
Normal Form Algorithms I |
PS 1 |
|
I. The original paper on the Lemke-Howson algorithm (1964) can be found here. II. The graphical interpretation of the Lemke-Howson method can be found in "Computing Equilibria in Two-Player Games" by von Stengel [PS] III. The original paper on that interpretation is “A Note on the Lemke-Howson Algorithm” by Lloyd Shapley (1974). [handout only] IV. A good survey for both Lemke-Howson and simplicial subdivision (next class) is "Computation of Equilibria in Finite Games" by McKelvey and McLennan [PS] |
|
4/8 |
Normal Form Algorithms II |
|
|
I. Search methods are covered in “Simple Search Methods for Finding a Nash Equilibrium” by Porter, Nudelman, and Shoham (2004). [PDF] |
|
4/13 |
Normal Form Algorithms III |
|
|
I. The simplicial subdivision method is covered in “The Approximation of Fixed Points of a Continuous Mapping” by Herbert Scarf (1967) [PDF] II. The first paper on continuation methods is “A Global Newton Method To Compute Nash Equilibria” by Govindan and Wilson (2001). [PDF] |
|
4/15 |
Extensive
Form I |
PS2 |
PS1 |
I.
“Fast
Algorithms for Finding Randomized Strategies in Game Trees” by Koller, II.
“The
Complexity of Two-Person Zero-Sum Games in Extensive Form” by Koller and |
|
4/20 |
Extensive Form II |
|
|
I. “Generating and Solving Imperfect Information Games” by Koller and Pfeffer (1995) [PS] II. An extended version of the other paper (with more background) is “Representations and Solutions for Game Theoretic Problems” by Koller and Pfeffer (1997) [PS] |
|
4/22 |
Compact Forms I |
|
|
I. The original paper on congestion games is “A Class of Games Possessing Pure-Strategy Equilibria” by Rosenthal (1973) [handout only] II. A paper generalizing the notion of congestion games is “Potential Games” by Monderer and Shapley (1996) [PDF] III. “Local Effect Games” by Leyton-Brown and Tennenholtz (2003) [PDF] III.
“Efficient
Nash Computation in Large Population Games with Bounded Influence”
by IV. “The Complexity of Pure Nash Equilibria” by Fabrikant, Papadimitriou, and Talwar (2004). [PS] |
|
4/27 |
Compact Forms II |
|
|
I.
“Graphical
Models for Game Theory” by II.
“Nash
Propagation for Loopy Graphical Games” by Ortiz and III.
“Correlated
Equilibria in Graphical Games” by
Kakade, |
|
4/29 |
Compact Forms III |
PS3 |
PS2 |
I. “Pure Nash Equilibria: Hard and Easy Games” by Gottlob, Greco, and Scarcello (2003) [PDF] II. “Equilibria in Symmetric Games” by Christos Papadimitriou and Tim Roughgarden. (2003) [PS] |
|
5/4 |
Compact Forms IV |
|
|
I. “Multiagent Influence Diagrams for Representing and Solving Games” by Koller and Milch (2001) [PDF] II.
“On the
NP-Completeness of Finding an Optimal Strategy in Games with Common-Payoffs”
by |
|
5/6 |
Repeated Game Best Response |
|
|
I. “Non-Computable Strategies and Discounted Repeated Games” by Nachbar and Zame (1995). [handout only] II. “The Complexity of Computing Best Response Automata in Repeated Games” by Gilboa (1988) [handout only] III. “The Complexity of Computing Best Response Automata in Repeated Games with Mixed Strategies” by Ben-Porath (1990) [handout only] IV. “On Players with a Bounded Number of States” by Papadimitriou (1989). [handout only] V. “Value Lattices for Anytime Optimal Policy Computation in Games”, Pivazyan and Shoham (2004). |
|
5/11 |
Repeated Game Complexity |
|
|
TBA |
|
5/13 |
Bounded Rationality |
PS4 |
PS3 |
I. “Finitely Repeated Games with Finite Automata” by Neyman (1998) [handout only] II. “On Bounded Rationality and Computational Complexity” by Papadimitriou and Yannakakis (1994). [handout only] |
|
5/18 |
TBA |
|
|
|
|
5/20 |
Cooperative Game
Complexity |
|
|
I. The paper on Papadimitriou games is “On the Complexity of Cooperative Solution Concepts” by Deng and Papadimitriou (1994) [handout only] II. “Complexity of Non-Emptiness of the Core” by Conitzer and Sandholm (2002) [PDF] III. “Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in Multi-issue Domains” by Conitzer and Sandholm (2004) [PDF] |
|
5/25 |
Combinatorial Auctions I |
|
|
TBA |
|
5/27
|
Combinatorial Auctions II |
|
PS4 |
TBA |
|
6/1 |
Recitation |
|
|
|
|
6/8 |
Final, |
|
|
|
|
Comments to Bob McGrew |
|
|
|
|
|