Joint course CIS 620 and Wharton OPIM 952:
COMPUTATIONAL GAME THEORY
MICHAEL KEARNS
SPRING 2003

URL for this page: http://www.cis.upenn.edu/~mkearns/teaching/cgt


COURSE INSTRUCTOR
Prof. Michael Kearns
Email: mkearns@cis.upenn.edu
Office hours: by appointment

COURSE TIME AND LOCATION
Tuesdays and Thursdays 1:30-3 in G94 JMMH (new Wharton building).

COURSE FORMAT, DUTIES AND PREREQUISITES
The course will be run as a mixture of instructor lectures, guest lectures, presentations by students, and group discussions. The main duties of students taking the course for credit will be to (informally) present one or more papers from the literature to the class or lead group discussion(s) on papers, and a term paper/project. The term project can be a survey and synthesis of a few related papers, a theoretical research project, or an experimental or empirical research project.

Part of the challenge and appeal of the material to be covered is that much of it is very recent and still in formation, and the course format will reflect these facts. Special emphasis will be placed on open problems, interesting but relatively untouched topics, and avenues for further research. It should provide fertile ground for stimulating discussions and collaborations.

There are no formal prerequisites for the course, but there will be significant mathematical content and we shall proceed at a graduate pace. Some background in the basics of game theory, probability theory and statistics, algorithms and computational complexity will be helpful but are not required. I expect that the course will be appropriate for doctoral students in CIS and Wharton, and for mathematically inclined MBA students, Masters and undergraduates. Auditors are welcome.

COURSE DESCRIPTION
The last few years have seen an explosion of research activity at the boundaries of game theory, economics, computer science, artificial intelligence, biology, and a number of other disciplines. From the CS and AI side, motivations include the use of game theory as a design principle for distributed algorithms and network protocols, and as a foundation for complex autonomous agents engaged in both cooperative activity and strategic competition. From the traditional economic and game theory side, motivations include the development of richer ways of modeling complex and modern problems of strategic interaction and confrontation.

The resulting field that is emerging, known as Computational Game Theory, draws strongly on classical game theory, but differs in its focus. As the name suggests, the primary emphasis is on computational and algorithmic issues. Foremost among these are the development of succinct models for large and complex games, and algorithms that can exploit these new models in a computationally efficient manner. The new models often allow one to directly incorporate known structure into the description of a game in a flexible manner, and thus offer the promise of increased realism and applicability of game-theoretic reasoning.

The course will survey progress so far in this exciting and rapidly growing area. Special emphasis will be placed on the multidisciplinary flavor the field has thrived under, drawing on topics from artificial intelligence, computer science, mechanism design, evolution, economics, and many other disciplines.

Likely topics to be covered include (in no particular order):

  • Basics of zero-sum, general-sum game theory
  • Classical approaches for computing Nash equilibria
  • Multi-party game theory
  • Alternative equilibrium notions
  • Compact representations for multi-party games
  • Graph-theoretic models for large games
  • Computing equilibria efficiently in graphical games
  • Graphical games and Bayesian networks; connections to probabilistic inference
  • Correlated equilibria
  • Sampling arguments in game theory
  • Stochastic games and reinforcement learning
  • Game theory and machine learning
  • Regret minimization in games
  • Repeated games and bounded rationality
  • Game theory with restricted strategies
  • Game theory and distributed algorithms
  • Evolutionary game theory
  • Structured representations for macroeconmics


    COURSE SCHEDULE, LECTURE AND READING MATERIALS, AND NOTES
    What follows is an approximate schedule subject to ongoing revision and refinement. I will also link to lecture and reading materials here, so please check regularly for updates.

    WEEK 1 (Jan 13): Course Overview; Basics of Game Theory

    In the first couple of lectures, I will give a flavor of what the course will be about, and also get started on the basic notions of classical game theory. In doing so, I will probably draw on some presentation material for a recent tutorial I gave:

  • Here are postscript slides for the main body of the tutorial.
  • Here they are in PDF.
  • Here are powerpoint slides on the topic of graphical models and game theory.

    These materials of course cover only a small fraction of what we'll eventually study, but they will serve to emphasize some of the themes that will be important.

    WEEK 2 (Jan 20): Computation of Nash Equilibria --- Two Players, Many Actions

    In this week, we'll study "classical" algorithms for computing Nash equilibria for games in standard matrix or normal form. Beginning with the two-player case, we'll examine

  • Linear programming computation of Nash equilibria for the zero-sum case
  • Formulation of general-sum case as a linear complementarity problem
  • Brief overview of Lemke-Howson algorithm and Scarf's algorithm
  • A sampling-based algorithm
  • Computational complexity considerations

  • Here are some handwritten notes on the existence and computation of Nash equilibria. They (crudely) sketch the basic fixedpoint existence argument, and cover the formulation of NE computation as linear programming (zero-sum) and linear complementarity (general sum) problems.
  • Here are some handwritten notes on a subexponential algorithm for computing approximate NE. The proof method is especially interesting, relying on a sampling argument and the so-called probabilistic method. (NOTE: See the comment a little way down about computing NE given the right support sets; this can almost certainly be used to improve the rather ugly conclusion to the subexponential algorithm.)
  • The lecture notes above are hopefully obselete with the arrival of the following paper, which essentially does it right. Note also the interesting additional results on low-rank game matrices.
  • "Playing Large Games Using Simple Strategies" [PDF version] , by R. Lipton, E. Markakis, and A. Mehta. To appear, ACM Conference on Electronic Commerce, 2003.

    The following two survey papers are good general references:

  • "Computation of Equilibria in Finite Games" [PDF version] , by Richard McKelvey and Andrew McLennan.
  • "Computing Equilibria for Two-Person Games" [PDF version] , by Bernhard von Stengel.

    A comment on zero-sum, multi-player games: My colleague Michael Littman (see Mar 4 lecture below) recently made the observation that computing Nash equilibria in zero-sum, n player games (here zero-sum means that for any setting of the population joint action, the rewards all sum to zero or some other constant) is just as hard as computing Nash equilibria in general-sum games with (n-1) players. To see this, note that we can turn any game with (n-1) players into a zero-sum game with n players by simply adding a "dummy" player whose payoffs for any setting of the actions of the (n-1) are exactly equal to the negative of the sum of the other (n-1) payoffs. Note that this dummy player's payoffs are entirely determined by the actions of the others --- his own action is irrelevant, and thus a NE for the n-player zero-sum game also gives a NE for the (n-1)-player general sum game (just ignore what the dummy player does). This observation shows that the LP formulation for zero-sum games is really special to the 2-player case, and that the zero-sum constraints is not computationally helpful for more players.

    A comment on computing equilibria in 2-person, general-sum games: Suppose I tell you there is a NE for a 2-player game in which the support of the mixed stratgey for the row player is S1, and the support for the column player is S2. Then we can actually solve for a NE (P,Q) via the following system of linear constraints:

  • For every row i in S1, M1(i,Q) = U;
  • For every row i NOT in S1, M1(i,Q) <= U; (this ensures P will be a best response to Q)
  • For every row i in S1, P_i > 0, and the P_i in S1 sum to 1
    along with symmetric constraints for the Q_j and V. This demonstrates that the computational difficulty of computing NE lies in finding the right support sets. It probably also gives a much more direct solution to the sampling-argument algorithm for subexponential approximate NE computation from last lecture (though I have not yet worked through the details of the above argument in the approximate case).

    WEEK 3 (Jan 27): Models and Algorithms for Large Populations --- Graphical Games

    At this point, we have seen that Nash equilibrium computation can be done efficiently via linear programming in the very special case of 2-player, zero-sum games. We then extended this LP to formulate the general-sum case as a linear complementarity problem, which involves constraints over products of variables and thus is no longer an LP, but a more difficult problem. We then showed that if we relax to consider approximate equilbria, there is a subexponential time algorithm for the general sum case based on a small-support sampling argument.

    Overall, the news for computing equilibria in the general sum setting is grim for two players, and even worse for more players. This is about all we will about the standard matrix or normal form for games until we return to the problem of learning in games. We now turn our attention to more tractable representations.

    In this segment, we will examine recent models for games with many players, and efficient algorithms that exploit these models. We will begin with models appropriate when the number of players is large, but each player may directly interact with a relatively small group of "neighbors".

    The lectures on this topic will be given by Penn postdoctoral researcher Luis Ortiz.

    Related readings:

  • Here are Luis' handwritten lecture notes on graphical games.
  • Here are powerpoint slides on the topic of graphical models and game theory.
  • Graphical Models for Game Theory. M. Kearns, M. Littman, S. Singh. 2001. In Proceedings of UAI 2001.

  • [Postscript] [Compressed Postscript] [PDF]
  • Here are some notes, due to Luis Ortiz, giving an improved approximation bound for Lemma 4 of the KLS paper above, which in turn leads to an improved running time in Theorem 5.
  • An Efficient Exact Algorithm for Singly Connected Graphical Games. With M. Littman, S. Singh. 2001. To appear, NIPS 2001.

  • [Postscript] [Compressed Postscript] [PDF]
  • Here are Luis' handwritten lecture notes on the NashProp algorithm.
  • Nash Propagation for Loopy Graphical Games. L. Ortiz, M. Kearns. To appear, Proceedings of NIPS 2002.

  • [Postscript] [Compressed Postscript] [PDF]
  • "Multi-Agent Influence Diagrams for Representing and Solving Games", by Daphne Koller and Brian Milch.
  • "Multi-Agent Algorithms for Solving Graphical Games", by D. Vickrey and D. Koller.
  • "Game Networks", by P. La Mura.

    WEEK 4 (Feb 3): Graphical Games --- Conclusion

  • Feb 4: Luis Ortiz will finish up our study of graphical games.
  • Feb 6: NO CLASS!!!

  • Here are Luis' notes on alternative formulations of the problem of finding NE in graphical games, and Luis' notes on the connection between NashProp and constraint satisfaction problems.

    Since this is a course on computational aspects of game theory, I thought I would provide a link here to the only fairly serious software package I am aware of for manipulating games and computing equilibria, which is the GAMBIT package developed at Cal Tech. Here is the main GAMBIT page, here is the download page where you can get various Unix and PC versions of the software, and here is a link to the GAMBIT manual in PDF format. GAMBIT can handle games in standard normal (matrix) form and extensive games (games with internal state). It comes with both a GUI as well as a command language for farily general-purpose programming.

    To whet your appetite, here is little GCL program to compute the number of Nash equilibria in two-player games with a growing number of actions ; you will also need this subroutine for generating random games. You will have to modify some path names for your machine. In an upcoming lecture I will try to find a few minutes to give a demo, but feel free to try it out yourselves.

    The more empirically inclined among you might want to consider a course project that implements some of the algorithms for class in the GAMBIT environment.

    WEEK 5 (Feb 10): Other Large-Population Models

    Next we will consider large population games in which each player may interact with all others, but only in a weak or special manner.

  • Feb 11: This lecture will be given by Prof. Howard Kunreuther of Wharton School, an expert on risk management who has recently been studying game-theoretic models for problems like vaccination and airline security.
  • Powerpoint for Prof. Kunreuther's presentation
  • Related paper: "Interdependent Security" , by H. Kunreuther and G. Heal.
  • Here are some handwritten notes on large population models.
  • Related paper: "Potential Games" , by Dov Monderer and Lloyd S. Shapley.
  • Related paper: Efficient Nash Computation in Large Population Games with Bounded Influence. M. Kearns, Y. Mansour.
  • [Postscript] [Compressed Postscript] [PDF]

    Other readings on large-population models:

  • "Shopbots and Pricebots" , by A. Greenwald and J. Kephart.

    WEEK 6 (Feb 17): Correlated Equilbira, Graphical Games, and Probabilistic Inference

  • Here are some handwritten notes on correlated equilibria.
  • Tutorial material on Bayesian networks and probabilistic inference
  • Here are some extremely brief handwritten notes on Markov networks.
  • Correlated Equilibria in Graphical Games. S. Kakade, M. Kearns, J. Langford, and L. Ortiz. To appear, ACM Conference on Electronic Commerce, 2003.
  • [Postscript] [Compressed Postscript] [PDF]

    WEEK 7 (Feb 24): Learning and Repeated Games

    Students taking the course for credit should start giving thought to their course projects now. I'm happy to read and respond to emails with ideas for projects, and may post some suggested areas soon. Eventually I will arrange meetings to discuss project ideas. Your course project and in-class presentations (see Week 8 for first such opportunity) will form the basis for your grades.

    There is what should be a very interesting talk on computing market equilibria this Tuesday by Vijay Vazirani of Georgia Tech.

    In this week's lectures, we will address the fundamental issue of learning in game theory. We are fortunate to have at Penn one of the world's authorities on the topic, Prof. Dean Foster of the Stats department at Wharton. Dean will give both lectures this week, and introduce us to some powerful learning algorithms and methods of analysis, and relate them to the various notions of equilibria.

    Related readings:

  • "Adaptive Game Playing Using Multiplicative Weights", , by Y. Freund and R. Schapire.
  • "Calibrated Learning and Correlated Equilibrium", , by D. Foster and R. Vohra.
  • "Regret in the On-line Decision Problem", , by D. Foster and R. Vohra.
  • Here is some related material from the Luce and Raiffa game theory book.

    WEEK 8 (Mar 3): Learning and Repeated Games, Continued

  • March 4: Guest lecture by Prof. Michael Littman Rutgers University. Among other topics, Prof. Littman will discuss the very interesting result in the following recent paper:
  • "A Polynomial-Time Nash Equilibrium Algorithm for Repeated Games", by M. Littman and P. Stone.

    Here are Prof. Littman's lecture materials:

  • Lecture slides
  • Related Markov chain notes

  • March 6: I am in Washington DC for a meeting this day, so there will be NO LECTURE THURSDAY, MARCH 6.
  • For those of you taking the course for credit, one-page initial proposals for projects are due by email on FRIDAY, MARCH 7.

    WEEK 9 (Mar 10): SPRING BREAK

    WEEK 10 (Mar 17): Learning and Repeated Games, Continued

  • March 18: This lecture will be given by Kilian Weinberger. Kilian will discuss some traditional learning algorithms for repeated games, including ficitious play, as well as gradient-based methods, including some recent work of his own.

  • Kilian's slides
  • A related paper
  • I may intercede with a few comments about this related unpublished manuscript.

    March 20: Ian Ross will lead us through a presentation of the following trio of papers on repeated games and learning:

  • "Rational Learning Leads to Nash Equilibrium", by E. Kalai and E. Lehrer. Note: Click "Ignore all DSC" on download.
  • "On Complexity as Bounded Rationality", by C. Papadimitriou and M. Yannakakis.
  • "Optimality and Domination in Repeated Games with Bounded Players", by L. Fortnow and D. Whang.

    WEEK 11 (Mar 24): Alternative Equilibria --- Evolutionary Game Theory

  • March 25: Ian Ross will continue his discussion of repeated games; here are Ian's slides.
  • March 27: Amit Bahl will speak on evolutionary game theory. Here are Amit's slides, and some related papers follow.
  • "Effects of finite population size on evolutionary stable strategies", S. Ficici and J. Pollack.
  • "A game-theoretic investigation of selection methods used in evolutionary algorithms", S. Ficici, O. Melnick, J. Pollack.

    WEEK 12 (Mar 31): Macroeconomic and Market Models
    In the first lecture this week, Ralph Ahn will introduce us to general equilibria theory. Related material:

  • Ralph's slides
  • "Existence of an Equilibrium for a Competitive Economy", K. Arrow and G. Debreu.
  • Walras-Cassel tutorial
  • Wald System tutorial
  • On the Complexity of Equilibria , by D. Xiaotie, C. Papadimitriou, M. Safra.

    In the second lecture, Yuan Ding will discuss the following paper:

  • "Market Equilibrium via a Primal-Dual-Type Algorithm" , by N. Devanur, C. Papadimitriou, A. Saberi, V. Vazirani.

    WEEK 13 (Apr 7): Algorithmic Mechanism Design

    Some interesting auction links:

  • Trading Agent Competition
  • FCC wireless spectrum auctions

    Sangkyum Kim will start our study of auctions and mechanism design by covering:

  • ``Combinatorial Auctions: A Survey'' , S de Vries, R. Vohra.
  • Sangkyum's slides

  • NO CLASS ON THURSDAY, APRIL 10

    WEEK 14 (Apr 14): Auctions, Continued; Game Theory and the Internet
    April 15: Nikhil Dinesh will examine these two papers:

  • ``Algorithms for Selfish Agents'' , Noam Nisan.
  • ``Algorithmic Mechanism Design'' , Nisan and Ronen.
  • Here are Nikhil's slides

    April 17: Michael Johns will survey these two papers:

  • ``Competitive Auctions and Digital Goods'' , A. Goldberg, J. Hartline, A. Wright.
  • ``Optimal Auction Design for Agents with Hard Valuation Problems'' , D. Parkes.
  • Here are Michael's slides

    WEEK 15 (Apr 21): Game Theory and the Internet, Continued

    April 22: Vasileios Kandylas will cover these two papers:

  • ``A Modest Proposal for Preventing Internet Congestion'' , A. Odlyzko.
  • ``Differential QoS and Pricing in Networks: Where Flow-control Meets Game Theory'' , P. Key, D. McAuley.
  • Here are Vasileios' slides

    April 24: Hong Zhang and Wonhong Nam will cover the following pair of papers:

  • ``How Bad is Selfish Routing?'' , T. Roughgarden, E. Tardos.
  • Here are Wonghong's slides
  • ``Sharing the Cost of Multicast Transmissions'' , J. Feigenbaum, C. Papadimitriou, S. Shenker.
  • Here are Hong's slides

    IMPORTANT: Course project write-ups will be due to Prof. Kearns via email on FRIDAY, MAY 9. This is a hard deadline.