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.

Deadlines:

• by Tuesday 11/11/08: email your project topic to the instructors (available on a first-come, first-serve basis).
• by 5PM Tuesday 11/18/08: email a 1-2 page outline to the instructors.
• Final reports due Monday 12/8/08 in class.

Possible topics:

Selfish Routing

1. Braess paradox
   • Summary: How hard is it to find examples of Braess' paradox in networks?
   • "On the Severity of Braess's Paradox: Designing Networks for Selfish Users is Hard" by Roughgarden.
     • Status : taken by Rajat Dixit.

2. Incentivizing selfish users
   • Summary: How can taxes move a selfish flow to optimal?
   • "How Much can Taxes Help Selfish Routing?" by Cole, Dodis, and Roughgarden.
     • Status: taken by Matthieu Plumettaz.

3. Atomic users (not infinitely splittable flows)
   • Summary: What happens in atomic selfish routing?
   • "Tight Bounds for Selfish and Greedy Load Balancing" by Caragiannis, Flammini, Kaklamanis, Kanellopoulos, and Moscardelli.
     • Status: taken by Anureet Dhillon.

   More Price of Anarchy

4. Price of anarchy in scheduling games
   • Summary: This is the first time "price of anarchy" was defined.
   • "Worst-case Equilibria" by Koutsoupias and Papadimitriou.
   • "A Tight Bound on Worst-case Equilibria" by Czumaj and Voecking.
     • Status: taken by Kyung Hwan Kim.

5. Strong price of anarchy
   • Summary: What happens when even a coalition of players can't deviate?
   • "Strong Price of Anarchy" by Andelman, Feldman, and Mansour.
     • Status: taken by Dave Smith.

   Sealed-Bid Combinatorial Auctions

6. Known single-minded bidders
   • Summary: Sealed-bid auctions for the case of single-minded bidders where the auctioneer knowns the relevant bundles, but not the agents' values.
   • "Truthful Approximation Mechanisms for Restricted Combinatorial Auctions" by Mu'alem and Nisan (AAAI 2002).
   • "An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents" by Archer, Papadimitriou, Talwar, and Tardos (SODA 2003).
     • Status: taken by Green Zhang.

7. Approximate winner determination with subadditive valuations
   • Summary: What approximation factor is possible for the efficient allocation problem when agents have subadditive valuations?
   • "On Maximizing Welfare when Utility Functions are Subadditive" by Feige (STOC 2006).
   • "Approximation Algorithms for Combinatorial Auctions with Complement Free Bidders" by Dobzinski, Nisan, and Schapira (STOC 2005, for background).
     • Status: Available.

8. Frugality in shortest-path auctions and other mechanisms
   • Summary: Studies what magnitudes of payments are necessary to implement the VCG mechanism in a natural shortest-path application.
   • "Frugal Path Mechanisms" by Archer and Tardos (SODA 2002).
   • "Frugality in Path Auctions" by Elkind, Sahai, and Steiglitz (SODA 2004).
     • Status: Available.

9. Distributed implementations of the VCG mechanism
   • Summary: Studies when mechanisms like the VCG mechanism can be implemented efficiently in a distributed way.
   • "Sharing the Cost of Multicast Transmissions" by Feigenbaum, Papadimitriou, and Shenker (STOC 2000).
   • "A BGP-based Mechanism for Lowest-Cost Routing" by Feigenbaum, Papadimitriou, Sami, and Shenker (PODC 2002).
     • Status: taken by Igor Boshoer.

   Iterative Combinatorial Auctions

10. Iterative auctions based on subgradient algorithms
    • Summary: The iBundle auction is an iterative auction based on a "subgradient" approach, rather than primal-dual.
    • "iBundle: An Efficient Ascending Price Bundle Auction" by Parkes (EC 1999).
    • "Iterative Combinatorial Auctions: Theory and Practice" by Parkes and Ungar (AAAI 2000).
      • Status: Available.

11. Iterative auction for elements of a matroid
    • Summary: A matroid generalizes many interesting structures that one might want to auction off (e.g., finite set of identical goods, spanning trees). This paper develops an iterative auction for this setting using the primal-dual approach.
    • "Ascending auctions for integral (poly)matroids with concave nondecreasing separable values" by Bikhchandani, de Vries, Schummer, and Vohra (SODA 2008).
      • Status: Available.

12. Iterative auctions and VCG payments
    • Summary: An ascending-price auction that reaches a competitive equilibrium, then discounts prices to charge VCG payments.
    • "Ascending Price Vickrey Auctions for General Valuations" by Mishra and Parkes (Journal of Economic Theory 2007).
      • Status: taken by R.S. Wolfe.

    Communication Complexity in Auctions

13. Winner determination with polynomial communication
    • Summary: What approximation factor is possible with polynomial communication for general valuations?
    • "The Communication Complexity of Approximate Set Packing and Covering" by Nisan (ICALP 2002).
    • "The Communication Requirements of Efficient Allocations and Supporting Lindahl Prices" by Nisan and Segal (short version, for background).
      • Status: Available.

14. Communication complexity of the VCG mechanism
    • Summary: How much communication is required for the VCG mechanism?
    • "On the Communication Requirements of Verifying the VCG Outcome" by Lahaie and Parkes (EC 2007).
    • "The Communication Requirements of Efficient Allocations and Supporting Lindahl Prices" by Nisan and Segal (short version, for background).
      • Status: Available.

15. Communication complexity of thruthfulness
    • Summary: How much communication is required to compute an efficient allocation and payments that incentivize the agents to truthfully reveal their valuations?
    • "Informational Overhead of Incentive Compatibility" by Babaioff, Blumrosen, Naor, and Schapira (EC 2007).
      • Status: taken by Rajesh Venkataraman.

    Optimal Auctions

16. Optimal mechanism design
    • Summary: Approximately optimizing the revenue in truthful auctions.
    • "A Lower Bound on the Competitive Ratio of Truthful Auctions" by Blum and Hartline.
    • "From Optimal Limited to Unlimited Supply Auctions" by Hartline and McGrew.
      • Status: Available.

17. Optimal online auctions
    • Summary: Auctions that seek to maximize revenue when items arrive in an online fashion.
    • "Near-Optimal Online Auctions" by Blum and Hartline.
      • Status: Available.

18. Online auctions with limited supply
    • Summary: Auctions for a finite number of items that arrive in an online fashion.
    • "Adaptive Limited Supply Online Auctions" by Hajiaghayi, Kleinberg and Parkes.
    • "A Multiple Choice Secretary Problem with Applications to Online Auctions" by Kleinberg.
      • Status: Available.

    Pricing

19. Envy-free pricing
    • Summary: Pricing items so that buyers don't have an incentive to switch.
    • "On Profit-Maximizing Envy-Free Pricing" by Guruswami, Hartline, Karlin, Kempe, Kenyon, and McSherry.
      • Status: taken by Olivia Gillham.

    Algorithms for Market Equilibrium

20. Exact algorithms for computing market equilibria
    • Summary: An combinatorial, polynomial-time algorithm for computing an exact market equilibrium.
    • "Market Equilibrium via a Primal-Dual-Type Algorithm" by Devanur, Papadimitriou, Saberi, and Vazirani (FOCS 2002, journal version).
      • Status: taken by Chia-Hsin Wu.

21. Market equilibrium via mathematical programming
    • Summary: Studies mathematical programming formulations (linear and convex programs) and algorithms for computing market equilibria.
    • "A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities" by Jain (FOCS 2004).
      • Status: taken by Song Hee Kim.

    Complexity of Nash Equilibria

22. Complexity of computing Nash equilibria
    • Summary: Defining PPAD, and determining the computational complexity of computing Nash equilibria.
    • "Settling the Complexity of 2-Player Nash Equilibrium" by Chen and Deng.
      • Status: taken by Rodrigo Carrasco.

23. Complexity of computing approximate Nash equilibria
    • Summary: The computational complexity of computing approximate Nash equilibria.
    • "Computing Nash Equilibria: Approximation and Smoothed Complexity" by Chen, Deng, and Teng.
      • Status: taken by Gaurav Gaonkar.

    Sponsored Search Auctions

24. Revenue in sponsored search auctions
    • Summary: Techniques to increase revenue in Google and Yahoo ad auctions.
    • "Revenue Analysis of a Family of Ranking Rules for Keyword Auctions" by Lahaie and Pennock (EC 2006).
    • "Optimal Auction Design in a Multi-unit Environment: The Case of Sponsored Search Auctions" by Edelman and Schwarz (Working paper, 2008).
      • Status: taken by Peter Lu.

25. Online algorithms for sponsored search
    • Summary: An online algorithm to match bidders with budgets to slots to maximize revenue in sponsored search.
    • "AdWords and Generalized On-line Matching" by Mehta, Saberi, Vazirani, and Vazirani (Journal of the ACM 2007).
      • Status: taken by Brian Falk.

26. Equilibria of sponsored search auctions
    • Summary: Studies the equilibria of sponsored search auction and their properties (e.g., efficiency).
    • "Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords" by Edelman, Ostrovsky, and Schwarz (American Economic Review 2007).
      • Status: taken by Zhiwei Qin.

    Special Topics

27. Colonel Blotto games and optimal election spending
    • "General Blotto: Games of Allocative Strategic Mismatch" by Golman and Page (Working paper, 2006).
    • "Vote Buying" by Dekel, Jackson, and Wolinsky (Journal of Political Economy, 2008).
    • "Lotto, Blotto, or Frontrunner: The 2000 US Presidential Election and the nature of mistakes" by Merolla, Munger, and Tofias (Working paper, 2008).
      • Status: taken by Avi Hoffman.

28. Incentive design in peer-to-peer networks
    • "Robust Incentive Techniques for Peer-to-peer Networks" by Feldman, Lai, Stoica, and Chuang (EC 2004).
    • "Overcoming Free-Riding Behavior in Peer-to-Peer Systems" by Feldman and Chuang (SIGecom Exchanges 2005).
      • Status: taken by Supreeth Subramanya.

29. Cost sharing and group strategyproofness
    • "Incremental Cost Sharing: Characterization by Group Strategyproofness" by Moulin (Social Choice and Welfare 1999).
    • "Strategyproof Sharing of Submodular Costs: Budget Balance versus Efficiency" by Moulin and Shenker (Economic Theory 2001).
      • Status: taken by Chintan Sheth.

30. Unsharing mechanisms
    • "Dissolving a Partnership Efficiently" by Cramton, Gibbons, and Klemperer (Econometrica 1987).
    • "Amicable Divorce: Dissolving a Partnership with Simple Mechanisms" by McAfee (Journal of Economic Theory 1992).
      • Status: taken by Bethany Soule.

31. Online primal-dual algorithms for sponsored search
    • "Online Primal-Dual Algorithms for Maximizing Revenue in Sponsored Search" by Buchbinder, Jain, and Naor (ESA 2007).
      • Status: taken by Satyajeet Shaligram.