Instructor: Christos H. Papadimitriou
Soda 389, mailto:%20christos@cs.berkeley.edu,
(510) 642-1559
Office Hours: Wednesdays 2-3, and by appointment
Meets: Tuesdays 3:30-5:30pm, in Soda 306
Course Format: Lectures by the instructor, occasionally by guests.
Course Requirements:
There have been many instances in the recent literature in which algorithmic thinking is combined with game-theoretic, or, more generally, economic concepts to address problems arising in the context of the Internet. The purpose of this course is to seize this moment and promote this interaction. The emphasis will be on mathematically sophisticated techniques in the interface between algorithms and game theory, as well as their applications to the Internet. Topics will include some of the following (the list will crystallize gradually,with references and/or links to documents):
Lectures and Notes
Friday January 19: Introduction A talk at SODA 2001 (powerpoint presentation)
Tuesday January 23: Existence of equilibria
Tuesday January 30: Variants of the concepts of "game" and "rational play"
Tuesday February 6: Social choice theory
Tuesday February 13: Mechanism design
Tuesday February 20: Algorithmic mechanism design (see papers by Nisan; also, notes)
Tuesday February 27: Scott Shenker will lecture
on Learning
and Implementation on the Internet
(see also
two related papers and his slides from the
lecture)
Tuesday March 6: Cost sharing in multicasts (see paper by Feigenbaum et al. and other papers below)
Tuesday March 13: Combinatorial auctions (papers below, and notes)
Tuesday March 20: First half: Combinatorial auctions (continued) Second half: Talk by Anna Karlin on spectral methods in information retrieval (first paper in her web page).
Tuesday March 27: Spring Break
Tuesday April 3: (No lecture on Thursday either....)
Tuesday April 10: Coalitional games and solution concepts
Tuesday April 17: Coalitional games and solution concepts (cont.)
Tuesday April 24: Multi-objective optimization
Tuesday May 1: Powerlaws in the
Internet, the Web, and the Economy
(see lecture notes,
the papers below, and this course at UMass )
Tuesday May 8: Continued,
probably
Problem Sets
First problem
set, due February 20 IMPORTANT ADDITION: Please include in your problem set solutions a
paragraph with your thoughts about the project.
Readings
Two books I recommend:
Osborne and Rubinstein, A Course in Game Theory
David Kreps, A Course in Microeconomic Theory
The following papers will either be covered in the lectures, or
are suggested readings for the project part of the course.
Papers on algorithmic mechanism design:
Algorithms
for Selfish Agents by Nisan
Algorithmic
Mechanism Design by Nisan and Ronen
A
solution to Vickrey shortest paths by Suri and Hershberger
Papers on internet congestion and game theory/economics:
Resource
Pricing and the Evolution of Congestion Control by Gibbens and Kelly
A Modest
Proposal for Preventing Internet Congestion by Odlyzko
Optimization
Problems in Congestion Control by Karp, Koutsoupias, Papadimitriou, Shenker
Differential
QoS and Pricing in Networks by Key and McAuley
Pricing
Congestible Resources, Chapter 4 by Varian
Stackelberg
Scheduling by Roughgarden
Papers on the price of anarchy:
Worst-case Equilibria by
Koutsoupias and Papadimitriou
How Bad
is Selfish Routing? by Roughgarden and Tardos
Papers on combinatorial auctions:
A
survey
Bidding
and Allocation in Combinatorial Auctions by Nisan
Iterative
Combinatorial Auctions: Theory and Practice by Parkes and Ungar
Optimal
Auction Design by Parkes
Graph-theoretic
auctions by Akcoglu, Aspnes, et al.
Papers on multicast auctions:
Incentive-compatible
On-line Auctions by Lavi and Nisan
"Cost Sharing of a Homogeneous Good:
Average versus Serial Methods," by Moulin and
Shenker
Sharing the Cost of
Multicast Transmissions by Feigenbaum, Papadimitriou, Shenker
Strategyproofness
via LP Duality by Vijay Vazirani and Jain
Auctions
of Digital Goods by Goldberg, Hartline, and Wright
Papers on repeated games:
Bounded
Rationality and Computational Complexity by Papadimitriou and Yannakakis
Rational
Learning and Nash Equilibrium by Kalai and Lehrer
Papers on multi-objective optimization:
The Approximability of
Trade-offs by Papadimitriou and Yannakakis
An application of social choice to document ranking
Rank
Aggregation, Spam Resistance, and Social Choice by Dwork Kumar Moni Naor and
Sivakumar
Papers on power laws:
Stochastic
models of the web graph by Kumar et al.
Powerlaws
in the internet topology by Faloutsos3
Highly
optimized tolerance by Carlson and Doyle ( plus another
paper by them )
Sally Floyd's web page on
self-similarity in the Internet
Papers on game theory:
My STOC 2001
paper (most topics in the class reviewed).
Strategic
Information Transmission by Crawford and Sobel
A survey paper: Games,
Computers, and OR by Kalai
A dynamics that, in some sense and cases,
converges to the Nash equilibrium:
Nash
Convergence of Gradient Dynamics in General-Sum Games, by Singh Kearns and
Mansour
A representation of games, with an algorithm for computing Nash
equibria in some
special cases Graphical
models in game theory Kearns Littman and Singh