**Note:** The info below show be enough to easily find most of the
papers on the Web. If you can't find one of the papers below after 5
minutes of searching, contact the instructor for a copy.

- Bounding the Price of Anarchy of Selfish Routing
- Status:
- 1-person version (the paper below): available

- Jose Correa, Andreas Schulz, and Nicolas Stier Moses, "Selfish Routing in Capacitated Networks", Mathematics of Operations Research 2004.

- Status:
- Bounding the Price of Anarchy with Asymmetric Costs
- Status:
- 1-person version (both papers below): taken by Andrew Aymeloglu

- Chau/Sim, "The Price of Anarchy for Non-Atomic Congestion Games with Symmetric Cost Maps and Elastic Demands", Operations Research Letters 2003.
- Georgia Perakis, "The Price of Anarchy under Nonlinear and Asymmetric Costs", 2004 (available from instructor).

- Status:
- The Worst-Case Severity of Braess's Paradox
- Status:
- 1-person version (the paper below): taken by NeilFred Picciotto

- Tim Roughgarden, "On the Severity of Braess's Paradox: Designing Networks for Selfish Users Is Hard", to appear in Journal of Computer and System Sciences.

- Status:
- Price of Anarchy/Stability in Network Design
- Status:
- 1-person version (2 of 3 papers below): taken by Jorge Vittes
- 2-person version (all papers below): available

- Elliot Anshelevich et al, "Near-Optimal Network Design with Selfish Agents", FOCS 2003.
- Elliot Anshelevich et al, "Price of Stability for Network Design...", FOCS 2004.
- Alex Fabrikant et al, "On a Network Creation Game", PODC 2003.

- Status:
- Congestion and Potential Games
- Status:
- 1-person version (both papers below): taken by Mike Munie

- Robert Rosenthal, "A Class of Games Possessing Pure-Strategy Nash Equilibria", International Journal of Game Theory 1973. (Available from instructor.)
- Dov Monderer and Lloyd Shapley, "Potential Games", Games and Economic Behavior 1996.

- Status:
- Price of Anarchy of Bandwidth Allocation
- Status:
- 1-person version (1st paper below): taken by Jason Chuang
- 2-person version (both papers below): taken by Rajat Bhattacharje

- Ramesh Johari and John Tsitsiklis, "Efficiency loss in a network resource allocation game", Mathematics of Operations Research 2004.
- Johari/Mannor/Tsitsiklis, "Efficiency loss in a network resource allocation game: the case of elastic supply", 2004.

- Status:
- Price of Anarchy in Facility Location Games
- Status:
- 1-person version (1st paper below): taken by Kim Diana Ly
- 2-person version (both papers below): available

- Vetta FOCS 2002 paper (see main course Web page).
- Nikhil Devanur et al, "Price of Anarchy, Locality Gap, and a Network Service Provider Game", 2004.

- Status:
- Bounding Inefficiency Out of Equilibrium in Facility Location Games
- Status:
- 1-person version (the paper below): taken by Thuc Vu

- Mirrokni/Vetta APPROX 2004 paper (see main course Web page).

- Status:
- The KP Model
- Status:
- 1-person version (both papers below): taken by Nikola Milosavljevic

- Koutsoupias/Papadimitriou, "Worst-case Equilibria", STACS 1999.
- Czumaj/Voecking, "A Tight Bound on Worst-case Equilibria", SODA 2002.

- Status:
- Frugality in Shortest-Path Auctions and Other Mechanisms
- Status:
- 1-person version (first 2 papers below): taken by Ari Greenberg
- 2-person version (all papers below): available

- Archer/Tardos, "Frugal Path Mechanisms", SODA 2002.
- Elkind/Sahai/Steiglitz, "Frugality in Path Auctions", SODA 2004.
- Archer/Tardos, "Truthful Mechanisms for Single-Parameter Agents", FOCS 2001.

- Status:
- Auctions for Digital Goods
- Status:
- 1-person version (1st paper below): taken by Kanishka Shrivastava
- 2-person version (both papers below): available

- Goldberg/Hartline/Karlin/Wright, "Competititve Auctions", submitted.
- Goldberg/Hartline, "Competitiveness via Consensus", SODA 2003.

- Status:
- Multicast Cost Sharing
- Status:
- 1-person version (first 2 papers below): taken by Hamsa Balakrishnan
- 2-person version (all 3 papers below): available

- Feigenbaum/Papadimitriou/Shenker STOC 2000 paper.
- Feigenbaum et al PODC 2002 paper.
- Archer et al, "Approximation and Collusion in Multicast Cost Sharing", Games and Economic Behavior 2004.

- Status:
- Steiner Tree Cost Sharing
- Status:
- 1-person version (both papers below): taken by Yuanli Zhou

- Jain/Vazirani STOC 2001 + STOC 2002 papers.

- Status:
- Bad Examples for the Lemke-Howson Algorithm for Computing Nash Equilibria
- Status:
- 1-person version (the paper below): taken by Lawrence Wisne

- Savani/von Stengel, "Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game", FOCS 2004.

- Status:
- Complexity of Computing Correlated Equilibria in Compactly
Represented Games
- Status:
- 1-person version (the paper below): taken by Jon Hill

- Papadimitriou/Roughgarden, "Computing Equilibria in Multi-Player Games", to appear in SODA 2005.

- Status:
- Complexity of Computing Market Equilibria
- Status:
- 1-person version (1st paper below): taken by Varun Malhotra
- 2-person version (both papers below): available

- Devanur et al, "Market Equilibrium via a Primal-Dual-Type Algorithm", journal version of FOCS 2002 paper.
- Kamal Jain, "A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities", FOCS 2004.

- Status:
- Pricing Selfish Routing Networks
- Status:
- 2-person version (both papers below): available

- Cole/Dodis/Roughgarden STOC 2003 paper.
- Fleischer/Jain/Mahdian FOCS 2004 paper.

- Status:
- Incompatibility of VCG with Approximation Algorithms
- Status:
- 1-person version (the paper below): taken by Itamar Rosenn

- Nisan/Ronen, "Computationally Feasable VCG Mechanisms", EC 2000.

- Status:
- Fast Computation of VCG Payments for Shortest-Path Auctions
- Status:
- 1-person version (the paper below): taken by Stephen Guo

- Hershberger/Suri, " Vickrey Prices and Shortest Paths: What is an edge worth?", FOCS 2001 + erratum in FOCS 2002.

- Status:
- Combinatorial Auctions
- Status:
- 1-person version (2 of the papers below): taken by Soni Mukherjee
- 2-person version (4 of the papers below): taken by Mihaela Enachescu and Manuel Zamfir

- Noam Nisan, "Bidding and Allocation in Combinatorial Auctions", EC 2000.
- Zurel/Nisan EC 2001 paper.
- Lehmann/Lehmann/Nisan EC 2001 paper.
- Archer/Papadimitriou/Talwar/Tardos SODA 2003 paper.
- Lehmann/O'Callaghan/Shoham, "Truth Revelation in Approximately Efficient Combinatorial Auctions", JACM 2002.

- Status:
- Optimal Auctions
- Status:
- 1-person version (both papers below): taken by Pierre-Alexandre Pont

- Amir Ronen, " On approximating optimal auctions", EC 2001.
- Ronen/Saberi FOCS 2002 paper.

- Status: