Suggested project topics for CS364B (Topics in 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.

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

Deadlines:

• by Friday 10/28/05: pick a project topic (available on a first-come, first-serve basis).
• by 5PM Friday 11/18/05: 10-15 page report due (summary/synthesis of papers + proposed open question to work on). The instructions are essentially the same as those for the final report in last year's 364A class.
• by 5PM Friday 12/9/05: final revision of initial report due (accounting for instructor comments on the earlier version and including progress on open question). Final suggested length: 15-25 pages.

Possible topics:

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

• Approximate Winner Determination with Submodular Valuations
  • Summary: We covered this very briefly in lectures #6 and 7. You should give a more fleshed out discussion of the LLN paper and also understand a recent improvement to the approximation ratio (second paper below). Obvious open question: can one turn an O(1)-approximately efficienct approximation algorithm into a truthful mechanism?
  • Status:
    • Taken by Christian Romming.
  • Lehmann/Lehmann/Nisan, EC 2001.
  • Dobzinski/Schapira, An Improved Approximation Algorithm for Combinatorial Auctions with Submodular Bidders, 2005.

• Approximate Winner Determination with Subadditive Valuations
  • Summary: As above, but with more general subadditive valuations.
  • Status:
    • Taken by Arik Motskin.
  • Dobzinski/Nisan/Schapira, STOC 2005.
  • Uriel Feige, On Maximizing Welfare when Utility Functions are Subadditive, 2005.

• Truthful (in expectation) mechanisms via linear programming.
  • Summary: We saw a taste of this paper in lecture #8. 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 Donghyun Daniel Kim.
  • Lavi/Swamy, FOCS 2005.
  • Carr/Vempala, STOC 2000 (also Random Structures and Algorithms 2002).

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

• Communication complexity of CAs.
  • Summary: in class we discussed what efficiency is possible with polynomial communication for general valuations. This question is also interesting for special classes of valuations.
  • Status:
    • Taken by Alan Johnson.
  • Segal chapter in the new Combinatorial Auctions book (this was handed out in class).

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

• Redicibility Among Equilibrium Problems
  • "The Nash hierarchy collapses to the 4-player case". I.e., computing a Nash eq in a 4-player game can be done in poly-time if and only if it can be done in any game with a constant number of players. Obvious open question: should it collapse down to 3-player games?
  • Status:
    • Taken by Andrew Morrison.
  • Goldberg/Papadimitriou, Reducibility Among Equilibrium Problems.

• PPAD-completeness of computing a Nash equilibrium with 4 or more players. Again: why not with 3 or more players?
  • Status:
    • Available.
  • Daskalakis/Goldberg/Papadimitriou, The Complexity of Computing a Nash Equilibrium.
  • Also discuss the relevant background concepts in the Papadimitriou JCSS 1994 paper.

• 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. Obvious open questions: what about approximate Nash equilibria? What about games with more than 2 players?
  • Status:
    • Taken by Adam Guetz.
  • Abbott/Kane/Valiant, FOCS 2005.

• Sponsored search auctions (batched)
  • Summary: Can knapsack auctions be designed to take into account budgets?
  • Status:
    • Taken by Wael Salloum.
  • Borgs, Immorlica, Mahdian, Saberi, "Multi-unit auctions with budget-constrained bidders", EC 2005.
  • Aggarwal, Hartline, "Knapsack Auctions" SODA 2006.
  • Optional Reference: Balcan, Blum, Hartline, Mansour, "Mechanism Design via Machine Learning", FOCS 2005.
  • Optional Reference: Abrams, "Revenue Maximization When Bidders Have Budgets" SODA 2006.

• Sponsored search auctions (online)
  • Summary: online auctions solve a trivial online matching problem with incentive compatibility constraints. The AdWords paper solves a more general online matching problems with applications to auctions for selling advertisements on web search engines. Obvious open question: can these approaches be combined to give good online auctions for AdWords?
  • Status:
    • Taken by Andrew Schwartz.
  • Mehta, Saberi, Vazirani, Vazirani, "AdWords and Generalized Online Matching", FOCS 2005.
  • Hajiaghayi, Kleinberg, Parkes, "Adaptive Limited-Supply Online Auctions", EC 2004.
  • Optional Reference: Awerbuch, Azar, Meyerson, "Reducing truth-telling online mechanisms to online optimization", STOC 2003.
  • Optional Reference: Blum, Hartline, "Near-Optimal Online Auctions" EC 2005.

• Collusion and Bidders with Budgets.
  • Summary: For digital goods, there are near optimal auctions that resist collusion. There also near optimal auctions for bidders with budgets. Obvious Question: Can these be combined to give near optimal auctions for bidders with budgets who may collude.
  • Status:
    • Available
  • Borgs, Immorlica, Mahdian, Saberi, "Multi-unit auctions with budget-constrained bidders", EC 2005.
  • Goldberg, Hartline, "Collusion-Resistant Mechanism for Single Parameter Agents", SODA 2005.
  • Optional Reference: Abrams, "Revenue Maximization When Bidders Have Budgets" SODA 2006.

• Random sampling, double auctions, and worst case competitive ratio
  Summary: For unlimited supply auctions, random sampling is constant competitive in worst case. For double auctions, random sampling is good in the limit. Obvious Open Question: Prove or dis-prove that random sampling for double auctions is constant competitive in worst case (i.e., for the auction defined in Baliga and Vohra).
  • Status:
    • Available
  • Baliga and Vohra, "Market Research and Market Design", Advances in Theoretical Economics 2003.
  • Feige, Flaxman, Hartline, Kleinberg, "On the competitive ratio of the random sampling auction", WINE 2005.

• Online limited supply auctions with budgets
  • Summary: Borgs et al. give an offline auction for bidders with budgets. Obvious open question: Can the same be done online?
  • Status:
    • Available
  • Borgs, Immorlica, Mahdian, Saberi, "Multi-unit auctions with budget-constrained bidders", EC 2005.
  • Hajiaghayi, Kleinberg, Parkes, "Adaptive Limited-Supply Online Auctions", EC 2004.
  • Optional Reference: Abrams, "Revenue Maximization When Bidders Have Budgets" SODA 2006.

• 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:
    • Available
  • Gurusuami, Hartline, Karlin, Kempe, Kenyon, McSherry, "On Profit-Maximizing Envy-Free Pricing", SODA 2005.
  • Briest, Krysta. "Single-Minded Unlimited Supply Pricing on Sparse Instances", SODA 2006.
  • Demaine, Feige, Hajiaghayi, Salavatipour "Combination Can Be Hard: Approximability of the Unique Coverage Problem", SODA 2006

• Envy-free procurement
  • Summary: There is an interesting relationship between envy-free pricing and the cell phone power problem considered in Bahl et al.
  • Status:
    • Available
  • Bahl, Hajiaghayi, Jain, Mirrokni, Qui, Saberi, "Efficient Power Assignment in Wireless LAN using LP duality", unpublished.
  • Gul, Stacchetti, "Walrasian Equilibrium with Gross Substitutes", Economic Theory 1999.
  • Optional Reference: Gurusuami, Hartline, Karlin, Kempe, Kenyon, McSherry, "On Profit-Maximizing Envy-Free Pricing", SODA 2005.

• Optimal mechanisms for agents with costly valuation computations
  • Summary: Larson and Sandholm study mechanism design for agents who do not know their own valuations, but instead must compute them at some cost. This significantly affects incentives. Question: Can optimal mechanisms (given Bayesian priors) be designed for this setting?
  • Status:
    • Taken by Neetin Gulati.
  • Larson and Sandholm, "Costly Valuation Computation in Auctions" TARK 2001.
  • Myerson, "Optimal Mechanism Design", Mathematics of Operations Research 1981.
  • Optional Reference: Larson, "Mechanism Design for Computational Limited Agents", Ph.D. Thesis.