Algorithmic Game Theory
Computer Science 684
Fall 2005
 5153 Upson
 2550984
 eva at cs.cornell.edu
Time: MWF 1:252:15
Place: Olin 245
Office Hours:
Tuesday 12 and Fridays
23. You may also send me
email to make an appointment.
Overview
Algorithmic Game Theory combines algorithmic thinking with
gametheoretic, 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 (costsharing, core, Shapley value, and
applications, e.g. multicast pricing and bandwidth sharing)
 market equilibria
 Approximately optimal auctions in polynomial time
Prerequisites
The course prerequisites 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: nonatomic loadbalancing 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: Bicriteria 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.
 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 2player games, and 0sum 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 0sum 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 13 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 810 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.