Algorithmic Game Theory
Computer Science 684
Fall 2005
- 5153 Upson
- 255-0984
- eva at cs.cornell.edu
Time: MWF 1:25-2:15
Place: Olin 245
Office Hours:
Tuesday 1-2 and Fridays
2-3. You may also send me
email to make an appointment.
Overview
Algorithmic Game Theory combines algorithmic thinking with
game-theoretic, or, more generally, economic concepts. The course will focus on
problems arising from, and motivated by, the Internet and other decentralized
computer networks. The most defining characteristic of the Internet is that it
was not designed by a single central entity, but emerged from the complex
interaction of many economic agents, such as network operators, service
providers, designers, users, etc., in varying degrees of collaboration and
competition. The course will focus on some of the many questions at the
interface between algorithms and game theory that arise from this point of
view.
Topics
Topics include some of the following (subject to
change):
- Introduction to Algorithms and Games
- Price of Anarchy in Nash Games
- selfish routing in network: Nash and Wardrop equilibria
- Routing Games and other congestion games
- Randomized load balancing games
- Network design with selfish agents
- Bandwidth sharing Games
- Facility Location Games
- Algorithmic Aspects of Equilibria
- existence and complexity of equilibria
- correlated equilibrium
- games with many players
- Learning in Games
- Does natural game play converge?
- Correlated equilibria are learnable
- Can we learn to do better than equilibria?
- Mechanism Design and Auctions
- algorithmic mechanism design
- auctions for digital goods
- combinatorial auctions: path auctions in networks and VCG and BGP
- frugality and alternate auction mechanisms
We may also consider a subset of the following topics depending on time
available and the interest of participants.
- Cooperative games (cost-sharing, core, Shapley value, and
applications, e.g. multicast pricing and bandwidth sharing)
- market equilibria
- Approximately optimal auctions in polynomial time
Pre-requisites
The course pre-requisites is background in algorithms and
graphs at the level of CS 482. No prior knowledge of game theory or economics
will be assumed.
Problem Sets
- Problem set 1 was due on Monday, September 26th.
- Problem set 2 was due on Wednesday, October 19th.
- Problem Set 3 is due on
Friday, November 19th.
- Short proposals for the final project are due on
Wednesday, October 26th. Here is a description of what
the final project is and what to include in a proposal.
- The final projects is due at the end of the semester:
Monday, December 12th.
- Here is a list of some papers you may consider,
if you would like a suggestion.
Topics week by week, lecture notes, references, etc.
- Notes for Friday August 26: introduction, games,
matrix, Braess paradox
-
- Notes for Monday August 29: the discrete load balancing game: Nash equilibria can be
bad
- Notes for Wednesday, August 31: non-atomic load-balancing game. Nash minimizes
maximum response time.
- Notes for Friday, Sept 2: Nash exists for load balancing and can be found by
repeatedly minimizing the maximum load.
-
- Notes for Monday, Sept 5: Nash's are local minima of a potential function Phi.
- Notes for Wednesday, Sept 7: Potential functions for nonatomic routing games, and
average delay
- Notes for Friday, Sept 9: Bi-criteria bound for average delay
-
- Notes for Monday, Sept 12: What information do players need to route: to what extent
does routing model car traffic? Internet traffic?
- Notes for Wednesday, Sept 14: Optimality conditions and the existence of Nash, and
tolls that can induce optimum.
- Notes for Friday, Sept 16: Price of Anarchy is independent of network topology
-
- Notes for Monday, Sept 19: Price of Anarchy for some functions, e.g.,
delays linear,
degree bounded polynomial, etc. Corollary about limits of Braess paradox.
- Notes for Wednesday, Sept 21: Price of Stability, and deriving simple bound on the
price of anarchy or stability using the potential function.
- Notes for Friday, Sept 23: Network design with discrete potential games:
-
- Notes for Monday, Sept 26: Worst case Price of Anarchy in discrete routing and load
balancing:
- Notes for Wednesday, Sept 28 (guest lecture by Tom
Wexler).: Facility locations games, and the prince of anarchy
- Notes for Friday, Sept 30: Extension of facility locations games to "competitive
societies".
-
- Notes for Monday, Oct 3: On Kelly's Bandwidth sharing game.
European Transactions on Telecommunications,
vol. 8, pp. 33–37, 1997.
Notes for Wednesday, Oct 5: The bandwidth allocation
as a game.
Notes for Friday, Oct 7: The bandwidth allocation
as a game finished. Bandwidth allocation on a network.
Monday, Oct 10 FALL BREAK
Notes for Wednesday, Oct 12: The bandwidth allocation
game without assumptions on a single link.
Notes for Friday, Oct 14: On the complexity of finding pure equilibria
Notes for Monday, Oct 17: Price of Anarchy without convergence.
Notes for Wednesday, Oct 19: Randomized Nash equilibria, and its existence
Notes for Friday, Oct 21: Nash Price of Anarchy for randomized Nash equilibria
Monday, Oct 24. CLASS CANCELLED
Notes for Wednesday, Oct 26: Existence of Randomized Nash equilibria
Notes for Friday, Oct 28: (guest lecture by
Ara Hayrapetyan) on a technique
for finding equilibria
Notes for Monday Oct 31: (guest lecture by
Ara Hayrapetyan) on the quality
of Nash in a pricing game
Notes for Wednesday, Nov 2: Nash in 2-player games, and 0-sum games
Notes for Friday, Nov 4: Connection of Nash and leaning
Notes for Monday, Nov 7: Adaptive Game playing: weighted majority
Notes for Wednesday, Nov 9: Adaptive Game Playing and 0-sum games and Routing
Notes for Friday, Nov 11 Correlated games, definition and examples
Notes for Monday, Nov 14: Correlated Nash properties and complexity of finding one.
Notes for Wednesday Nov 16: Correlated Nash and internal regret
Friday November 18: CLASS
Deferred to Monday, Dec 5
Monday November 21: connections between regrets
Wednesday Nov 23 and Friday Nov 25: Thanksgiving
holiday
Notes for Monday, Nov 28: Mechanism Design and the VCG mechanism
Notes for Wednesday, Nov 30: Combinatirial Auctions
Notes for Friday Dec 2: Auctions for Digital Goods
Notes for Monday, Dec 5th, (Optional extra class to replace Nov 18th) Nash games
and Truthful mechanisms
Course work
There will be 3 homework sets during
the semester, and a final project reading and evaluating papers. In
addition, students will take turns writing class notes.
Class notes are due within a week after the class at which you took notes.
Here is a sample file for scribes, if you
want to use Latex for you notes, but any other format that can be converted to
pdf and posted on the Web is fine.
For the class project students are expected to read and
evaluate 1-3 papers that were not covered in class, in an area related to the
course. The first step in
the project will be a short (1 page) "proposal", suggesting the papers you want
to read, and an outline of your plans. The final project should contain a
summary of the problem and model considered in the papers, your critical
evaluation of the problem, summary of the result, and intuitive explanation and
proof of why some of the results are true. You need to understand the proof well
enough to be able to explain it well. The expected length of a full project is
about 8-10 pages.
You may discuss the homework problems with other members of the
class, but you must write up the assignment separately and list the names of the
people with whom you discussed the assignment.
Book
There is no textbook for the course, as it covers recent research. The
following book is a very nice introduction to game theory. (But it is not
required for the course.)
- Osbourne and Rubinstein, A Course in Game Theory, MIT Press, 1994.
For the topics of selfish routing too also:
- Tim Roughgarden, Selfish Routing and the
Price of Anarchy, MIT Press, 2005.
Similar Courses
There are many similar course offered at other schools too:
Game
Theory . net offers a wide range of game theory courses. The
previous version of
this course was offered in the spring of 2004.