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 (or are unclear about which paper is being referred to) after 5 minutes of searching, contact the instructor. Unless otherwise noted, when you pick one of these project topics, you are expected to read, think about, and summarize all of the papers listed for that topic.

Note: Teams of 2 are possible with consent of the instructor (obviously, the project should be correspondingly more ambitious).

Deadlines:

• by Tuesday 10/31/06: email your project topic to the instructor (available on a first-come, first-serve basis).
• by 5PM Friday 11/17/06: email a 1-3 page outline to the instructor.
• Final report details TBA.

Possible topics:

Algorithmic Mechanism Design

1. Profit-maximizing random sampling auctions.
   Summary: The same problem that Jason discussed in lecture. Focus on the second paper and the parts of the first paper that study the RSOP auction.
   • Status:
     • Taken by Daniel Chen.
   • Goldberg/Hartline/Karlin/Saks/Wright, "Competitive Auctions", Games and Economic Behavior, 2006.
   • Feige, Flaxman, Hartline, Kleinberg, "On the competitive ratio of the random sampling auction", WINE 2005.

2. Collusion-Resistant Auctions for Digital Goods.
   • Summary: For digital goods, there are near optimal auctions that resist collusion.
   • Status:
     • Taken by Subie Patel
   • Goldberg, Hartline, "Collusion-Resistant Mechanism for Single Parameter Agents", SODA 2005.

3. Envy-free pricing
   • Summary: the optimization problem of envy-free pricing plays a central role in the design of near optimal mechanisms. Envy-free pricing is hard in general. Perhaps there are interesting special cases that are polynomial time solvable.
   • Status:
     • Taken by Aneesh Sharma.
   • Gurusuami, Hartline, Karlin, Kempe, Kenyon, McSherry, "On Profit-Maximizing Envy-Free Pricing", SODA 2005.

4. Optimal Auctions.
   • Summary: studies the design of profit-maximizing auctions assuming independent prior distributions on the valuations of the bidders. (A classic paper, a little technical in parts.)
   • Status:
     • Available.
   • Roger Myerson, "Optimal auction design", Mathematics of Operations Research, 1981.

5. Polynomial-Time Optimal Auctions
   • Summary: studies the design of approximately profit-maximizing auction assuming a prior (possibly correlated) joint distribution on the valuations of the bidders.
   • Status:
     • Available.
   • Amir Ronen, " On approximating optimal auctions", EC 2001.
   • Ronen/Saberi FOCS 2002 paper.

6. Online Auctions with Limited Supply
   • Summary: Variants of the problem studied in Problem 3 of HW#1.
   • Status:
     • Taken by Greg Nelson.
   • Hajiaghayi/Kleinberg/Parkes, Adaptive Limited-Supply Online Auctions, EC 2004.
   • Kleinberg, A Multiple-Choice Secretary Problem with Applications to Online Auctions, SODA 2005.

7. Profit-Maximization in the Presence of Costs
   • Summary: recall that digital goods auctions have no costs of productions. Adding costs seem to significantly complicate the problem.
   • Status:
     • Taken by Aleksandra Korolova.
   • Fiat/Goldberg/Hartline/Karlin STOC 2002.
   • Optional: try to use the techniques in Roughgarden/Sundararajan STOC 2006 (discussed at length in class) to design profit-maximizing mechanisms with costs.

8. Sponsored search auctions (equilibrium analysis)
   • Summary: Studies the equilibria of the Google and Yahoo! ad auctions.
   • Status: taken by Aravindakshan Babu.
   • Read the Edelman/Ostrovsky/Schwarz and Varian papers listed as references for the 10/5 lecture.

9. Sponsored search auctions (online)
   • Summary: Online algorithms for a problem motivated by sponsored search auctions.
     • Status: taken by Dominic DiPalantino.
   • Mehta, Saberi, Vazirani, Vazirani, "AdWords and Generalized Online Matching", FOCS 2005.

10. Limited supply auctions with bidders who have budgets
    • Summary: Offline auctions for bidders with budgets (motivated by sponsored search auctions).
    • Status:
      • Taken by Sean Yeh-en Ting.
    • Borgs, Immorlica, Mahdian, Saberi, "Multi-unit auctions with budget-constrained bidders", EC 2005.
    • Abrams SODA 2006.

11. Known Single-Minded Bidders
    • Summary: recall that in the LOS paper bidders were single-minded and allowed to lie about both their set and their value for the set. It turns out that somewhat better mechanisms are possible if the sets are known to the mechanism (and players can only lie about their values).
    • Status:
      • Available.
    • Mu'alem/Nisan, AAAI 2002.
    • Archer/Papadimitriou/Talwar/Tardos, SODA 2003 (also Internet Mathematics volume 1).

12. Approximate Winner Determination with Submodular Valuations
    • Summary: This is same topic as Problem 4 of HW#1. Focus on the results in the second paper, referring to the first paper for background.
    • Status:
      • Taken by Ying Wang.
    • Lehmann/Lehmann/Nisan, EC 2001 (for background).
    • Dobzinski/Schapira, An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders, SODA 2006.

13. Approximate Winner Determination with Subadditive Valuations
    • Summary: As above, but with more general subadditive valuations. Focus on the second paper, referring to the first paper for background.
    • Status:
      • Taken by Jack Stahl.
    • Dobzinski/Nisan/Schapira, STOC 2005.
    • Uriel Feige, On Maximizing Welfare when Utility Functions are Subadditive, STOC 2006.

14. Truthful (in expectation) combinatorial auctions via linear programming.
    • Summary: Gives a randomized, polynomial-time, truthful in expectation combinatorial auction that achieves a O(\sqrt{m})-approximation of surplus for general valuations. The key technical lemma (decomposing a scaled-down fractional allocation as a weighted average of integral allocations) is based on an earlier paper of Carr/Vempala, which you should also read and discuss.
    • Status:
      • Taken by Peter Hawkins.
    • Lavi/Swamy, FOCS 2005.
    • Carr/Vempala, STOC 2000 (also Random Structures and Algorithms 2002).

15. iBundle.
    • Summary: this is an iterative combinatorial auction, unlike the auctions discussed in class.
    • Status:
      • Taken by Adam Sadovsky.
    • Pick a representative subset of papers by David Parkes; see also his PhD thesis and his chapter in the new Combinatorial Auctions book.

16. Communication complexity of CAs.
    • Summary: what approximation factor is possible with polynomial communication for general valuations?
    • Status:
      • Available.
    • Nisan/Segal (short version) and Nisan, see references for 10/17 lecture.

17. Frugality in Shortest-Path Auctions and Other Mechanisms
    • Summary: studies what magnitudes or payments are necessary to implement the VCG mechanism in a natural shortest-path application.
    • Status:
      • Available.
    • Archer/Tardos, "Frugal Path Mechanisms", SODA 2002.
    • Elkind/Sahai/Steiglitz, "Frugality in Path Auctions", SODA 2004.

18. Distributed Algorithmic Mechanism Design
    • Summary: Studies when mechanisms like the VCG mechanism can be implemented efficiently in a distributed way.
    • Status:
      • Taken by Nathan Marz.
    • Feigenbaum/Papadimitriou/Shenker STOC 2000 paper.
    • Feigenbaum et al PODC 2002 paper.

19. From Primal-Dual Algorithm to Cross-Monotonic Cost-Sharing Methods.
    • Summary: For problems more complicated than fixed-tree multicast, designing an approximately budget-balanced and cross-monotonic cost-sharing method is a non-trivial problem. Primal-dual approximation algorithms have proved very useful for this.
    • Status:
      • Taken by Donghyun Daniel Kim.
    • Jain/Vazirani STOC 2001 paper.
    • Pal/Tardos FOCS 2003 paper (focus on the facility location application, don't worry about the rent-or-buy network design part).

20. Impossibility Results for Budget-Balanced, Cross-Monotonic Cost-Sharing Methods.
    • Summary: Some natural problems do not admit a cross-monotonic cost-sharing method with reasonable budget balance.
    • Status:
      • Available.
    • Immorlica/Mahdian/Mirrokni, SODA 2005.

21. Approximation in Non-Utilitarian Mechanism Design: the Single Parameter case.
    • Summary: For objectives different than surplus (e.g., more "fair" objectives) there is no analogue of the VCG mechanism, and all truthful mechanisms are suboptimal. A natural question is to understand the best approximation possible by a truthful mechanism. This paper obtains numerous upper and lower bounds when agents have simple (depending on only one number) valuations.
    • Status:
      • Taken by Jorge Ortiz.
    • Archer/Tardos, FOCS 2001.

22. Approximation in Non-Utilitarian Mechanism Design: the Multi-Parameter case.
    • Summary: For more complex valuations, we have little understanding on what kinds of approximation guarantees are possible with truthful mechanisms. The papers below show the (limited) state of the art.
    • Status:
      • Available.
    • Nisan/Ronen, STOC 1999 (focus on the results about minimizing the makespan on unrelated machines).
    • Christodoulou/Koutsoupias/Vidali, A Lower Bound for Scheduling Mechanisms, to appear in SODA 2007.

Inefficiency of Equilibria

1. Bounding the Price of Anarchy with Asymmetric Costs
   • Summary: Derives bounds on the price of anarchy of selfish routing when the cost of an edge can depend on the entire traffic pattern, rather than just on the congestion on that edge.
   • Status:
     • Taken by Seungbeom Kim.
   • Georgia Perakis, "The Price of Anarchy under Nonlinear and Asymmetric Costs", IPCO 2005.

2. Atomic Selfish Routing
   • Summary: Derives bounds on the price of anarchy for special cases of atomic selfish routing.
   • Status:
     • Taken by Doug Johnston.
   • Suri/Toth/Zhou SPAA '04.
   • I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli. Tight bounds for selfish and greedy load balancing. ICALP 2006. (Focus on Sections 2 and 3.)

3. The Worst-Case Severity of Braess's Paradox
   • Summary: In-depth study of Braess's Paradox: its worst-case severity and the computational complexity of detecting it.
   • Status:
     • Taken by Belinda Gu.
   • Roughgarden, "On the Severity of Braess's Paradox: Designing Networks for Selfish Users Is Hard", Journal of Computer and System Sciences 2006.

4. Price of Stability in Undirected Shapley Cost-Sharing Networks
   • Summary: what is the price of stability in undirected Shapley network design games? (Recall it is ln k in directed networks.) This paper makes progress on a special case.
   • Status:
     • Available.
   • Fiat/Kaplan/Levy/Olonetsky/Shabo, On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations, ICALP 2006.

5. Price of Anarchy in Local Network Formation Games
   • Summary: studies the POA in a different model of network formation, where players are nodes who build incident edges, rather than terminal pairs who build entire end-to-end paths.
   • Status:
     • Taken by Tai-Jin Lee.
   • Fabrikant et al, PODC 03.
   • Albers et al, SODA 06 (focus on Section 3, improved bounds on the POA).

6. Price of Anarchy of Bandwidth Allocation
   • Summary: Studies efficiency loss in a natural protocol for allocating bandwidth. A nice blend of mechanism design and the price of anarchy.
   • Status:
     • Taken by Bob Hough.
   • Ramesh Johari and John Tsitsiklis, "Efficiency loss in a network resource allocation game", Mathematics of Operations Research 2004.

7. Designing Bandwidth Allocation Protocols to Minimize Efficiency Loss
   • Summary: Studies how to design bandwidth-sharing protocols to minimize the efficiency loss. Among a natural class, the proportional sharing protocol in the paper above minimizes this efficiency loss.
   • Status:
     • Available.
   • Ramesh Johari and John Tsitsiklis, "Characterization theorems for smooth market-clearing mechanisms", 2005.

8. Strong Price of Anarchy
   • Summary: In several applications, better bounds are possible for "strong" Nash equilibria (where no coalition can profitably deviate) than for regular Nash equilibria.
   • Status:
     • Taken by Chris Breaux.
   • Andelman/Feldman/Mansour, Strong Price of Anarchy, to appear in SODA 2007.

9. Sink Equilibria
   • Summary: what can you say about the price of anarchy when pure-strategy Nash equilibria do not exist? This paper proposed a relaxed solution concept and proves bounds on the inefficiency of selfish behavior in atomic selfish routing games with weighted players.
   • Status:
     • Taken by Justin Driemeyer.
   • Goemans/Mirrokni/Vetta, FOCS 2005.

10. The KP Model
    • Summary: Bounds on the price of anarchy in scheduling games (in fact, this model is where the POA was first studied).
    • Status:
      • Available.
    • Koutsoupias/Papadimitriou, "Worst-case Equilibria", STACS 1999.
    • Czumaj/Voecking, "A Tight Bound on Worst-case Equilibria", SODA 2002.

Algorithms for and Complexity of Equilibria

1. Bad Examples for the Lemke-Howson Algorithm for Computing Nash Equilibria
   • Summary: The Lemke-Howson algorithm is a simplex-like algorithm for computing a Nash equilibrium of a two-player game. The paper below shows that it has exponential worst-case running time, and uses some nice polytope theory to do it.
   • Status:
     • Available.
   • Savani/von Stengel, "Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game", FOCS 2004.

2. PPAD-completeness of computing a Nash equilibrium in a bimatrix game.
   • Status:
     • Taken by Christian Romming.
   • Chen/Deng, FOCS 2006.
   • Also discuss the relevant background concepts in the Papadimitriou JCSS 1994 paper.

3. 0-1 Games are Universal Two-Player Games (from the perspective of computing a Nash equilibrium).
   • Summary: Computing a Nash equilibrium in arbitrary two-player games reduces to computing one in 0-1 two-player games.
   • Status:
     • Taken by Peter Ciccolo.
   • Abbott/Kane/Valiant, FOCS 2005.

4. Complexity of Computing Correlated Equilibria in Compactly Represented Games
   • Summary: Correlated equilibria remain tractable even in a wide class of compactly represented multi-player games.
   • Status:
     • Available.
   • Papadimitriou/Roughgarden, "Computing Equilibria in Multi-Player Games", SODA 2005.

5. Complexity of Computing Market Equilibria (Combinatorial Approaches)
   • Summary: market equilibria refers to a setting of prices to goods in a market so that supply equals demand. The papers below give combinatorial algorithms for computing such equilibria.
   • Status:
     • Taken by Simla Ceyhan.
   • Devanur et al, "Market Equilibrium via a Primal-Dual-Type Algorithm", journal version of FOCS 2002 paper.
   • Garg/Kapoor, STOC 2004.

6. Complexity of Computing Market Equilibria (Mathematical Programming Approaches)
   • Summary: market equilibria refers to a setting of prices to goods in a market so that supply equals demand. The paper below gives mathematical programming formulations and algorithms for this problem.
   • Status:
     • Taken by Dongdong Ge.
   • Jain, "Arrow-Debreu Market Equilibrium for Linear Utilities", FOCS 2004.

7. Computing Pure-Strategy Nash Equilibria and PLS-completeness.
   • Summary: How hard is it to compute pure-strategy Nash equilibria in games where they are guaranteed to exist? As this paper shows, it could be easy or hard, and the answer depends on the underlying game structure in an clean way.
   • Status:
     • Available.
   • Ackermann/Roeglin/Voecking, FOCS 2006.

8. Computing Approximate Pure-Strategy Nash Equilibria
   • Summary: Shows that natural dynamics (players iteratively updating their strategies) converges quickly to an approximate Nash equilibrium in a class of congestion games.
   • Status:
     • Taken by Paul Tarjan.
   • Chien/Sinclair, SODA 2007.

9. Algorithms for Equilibria in Graphical Games
   • Summary: Graphical games are a natural subclass of games where there is a notion of "locality" between players. Is it easier to compute Nash equilibria in graphical games than in arbitrary ones?
   • Status:
     • Taken by Ben Newman.
   • Kearns/Littman/Singh, UAI 2001.
   • Elkind/Goldberg/Goldberg, EC 2006.