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


Possible topics:

Algorithmic Mechanism Design

  1. Profit-maximizing random sampling auctions.

  2. Collusion-Resistant Auctions for Digital Goods.

  3. Envy-free pricing

  4. Optimal Auctions.

  5. Polynomial-Time Optimal Auctions

  6. Online Auctions with Limited Supply

  7. Profit-Maximization in the Presence of Costs

  8. Sponsored search auctions (equilibrium analysis)

  9. Sponsored search auctions (online)

  10. Limited supply auctions with bidders who have budgets

  11. Known Single-Minded Bidders

  12. Approximate Winner Determination with Submodular Valuations

  13. Approximate Winner Determination with Subadditive Valuations

  14. Truthful (in expectation) combinatorial auctions via linear programming.

  15. iBundle.

  16. Communication complexity of CAs.

  17. Frugality in Shortest-Path Auctions and Other Mechanisms

  18. Distributed Algorithmic Mechanism Design

  19. From Primal-Dual Algorithm to Cross-Monotonic Cost-Sharing Methods.

  20. Impossibility Results for Budget-Balanced, Cross-Monotonic Cost-Sharing Methods.

  21. Approximation in Non-Utilitarian Mechanism Design: the Single Parameter case.

  22. Approximation in Non-Utilitarian Mechanism Design: the Multi-Parameter case.

Inefficiency of Equilibria

  1. Bounding the Price of Anarchy with Asymmetric Costs

  2. Atomic Selfish Routing

  3. The Worst-Case Severity of Braess's Paradox

  4. Price of Stability in Undirected Shapley Cost-Sharing Networks

  5. Price of Anarchy in Local Network Formation Games

  6. Price of Anarchy of Bandwidth Allocation

  7. Designing Bandwidth Allocation Protocols to Minimize Efficiency Loss

  8. Strong Price of Anarchy

  9. Sink Equilibria

  10. The KP Model

Algorithms for and Complexity of Equilibria

  1. Bad Examples for the Lemke-Howson Algorithm for Computing Nash Equilibria

  2. PPAD-completeness of computing a Nash equilibrium in a bimatrix game.

  3. 0-1 Games are Universal Two-Player Games (from the perspective of computing a Nash equilibrium).

  4. Complexity of Computing Correlated Equilibria in Compactly Represented Games

  5. Complexity of Computing Market Equilibria (Combinatorial Approaches)

  6. Complexity of Computing Market Equilibria (Mathematical Programming Approaches)

  7. Computing Pure-Strategy Nash Equilibria and PLS-completeness.

  8. Computing Approximate Pure-Strategy Nash Equilibria

  9. Algorithms for Equilibria in Graphical Games