Suggested project topics for CS364A (Algorithmic Game Theory)

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.

• 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).

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

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

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

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

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

• 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).

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

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

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

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

• Steiner Tree Cost Sharing
  • Status:
    • 1-person version (both papers below): taken by Yuanli Zhou
  • Jain/Vazirani STOC 2001 + STOC 2002 papers.

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

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

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

• Pricing Selfish Routing Networks
  • Status:
    • 2-person version (both papers below): available
  • Cole/Dodis/Roughgarden STOC 2003 paper.
  • Fleischer/Jain/Mahdian FOCS 2004 paper.

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

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

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

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