Suggested project topics for COMS 6998-3 (Algorithmic Game Theory)

Note: The information below should 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 instructors. 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.


Possible topics:

    Selfish Routing

  1. Braess paradox

  2. Incentivizing selfish users

  3. Atomic users (not infinitely splittable flows)

    More Price of Anarchy

  4. Price of anarchy in scheduling games

  5. Strong price of anarchy

    Sealed-Bid Combinatorial Auctions

  6. Known single-minded bidders

  7. Approximate winner determination with subadditive valuations

  8. Frugality in shortest-path auctions and other mechanisms

  9. Distributed implementations of the VCG mechanism

    Iterative Combinatorial Auctions

  10. Iterative auctions based on subgradient algorithms

  11. Iterative auction for elements of a matroid

  12. Iterative auctions and VCG payments

    Communication Complexity in Auctions

  13. Winner determination with polynomial communication

  14. Communication complexity of the VCG mechanism

  15. Communication complexity of thruthfulness

    Optimal Auctions

  16. Optimal mechanism design

  17. Optimal online auctions

  18. Online auctions with limited supply


  19. Envy-free pricing

    Algorithms for Market Equilibrium

  20. Exact algorithms for computing market equilibria

  21. Market equilibrium via mathematical programming

    Complexity of Nash Equilibria

  22. Complexity of computing Nash equilibria

  23. Complexity of computing approximate Nash equilibria

    Sponsored Search Auctions

  24. Revenue in sponsored search auctions

  25. Online algorithms for sponsored search

  26. Equilibria of sponsored search auctions

    Special Topics

  27. Colonel Blotto games and optimal election spending

  28. Incentive design in peer-to-peer networks

  29. Cost sharing and group strategyproofness

  30. Unsharing mechanisms

  31. Online primal-dual algorithms for sponsored search