** 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:

along with symmetric constraints for the Q_j and V. This demonstrates that

** 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:

[Postscript] [Compressed Postscript] [PDF]

[Postscript] [Compressed Postscript] [PDF]

[Postscript] [Compressed Postscript] [PDF]

** 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.

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 first lecture this week, Ralph Ahn will introduce us
to general equilibria theory. Related material:

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 15: Nikhil Dinesh will examine these two papers:

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.
**