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):
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:
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
The following two survey papers are good general references:
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:
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:
WEEK 4 (Feb 3):
Graphical Games --- Conclusion
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.
Other readings on large-population models:
WEEK 6 (Feb 17): Correlated Equilbira,
Graphical Games, and Probabilistic Inference
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:
WEEK 8 (Mar 3): Learning and Repeated Games,
Continued
Here are Prof. Littman's lecture materials:
WEEK 9 (Mar 10): SPRING BREAK
WEEK 10 (Mar 17): Learning and Repeated Games,
Continued
March 20: Ian Ross will lead us through a presentation of
the following trio of papers on repeated games and learning:
WEEK 11 (Mar 24): Alternative Equilibria ---
Evolutionary Game Theory
WEEK 12 (Mar 31):
Macroeconomic and Market Models
In the second lecture, Yuan Ding will discuss the following paper:
WEEK 13 (Apr 7):
Algorithmic Mechanism Design
Some interesting auction links:
Sangkyum Kim will start our study of auctions and mechanism
design by covering:
WEEK 14 (Apr 14): Auctions, Continued;
Game Theory and the Internet
April 17: Michael Johns will survey these two papers:
WEEK 15 (Apr 21):
Game Theory and the Internet,
Continued
April 22: Vasileios Kandylas will cover these two papers:
April 24: Hong Zhang and Wonhong Nam will cover the following pair
of papers:
IMPORTANT: Course project write-ups will be due to Prof. Kearns
via email on FRIDAY, MAY 9. This is a hard deadline.
In the first lecture this week, Ralph Ahn will introduce us
to general equilibria theory. Related material:
April 15: Nikhil Dinesh will examine these two papers: