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 firstcome, firstserve basis).
 by 5PM Friday 11/18/05: 1015 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:
1525 pages.
Possible topics:
 Known SingleMinded Bidders
 Summary: recall that in the LOS paper bidders were singleminded
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:
 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:
 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 scaleddown 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:
 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:
 Segal chapter in the new Combinatorial Auctions book (this
was handed out in class).
 Bad Examples for the LemkeHowson Algorithm for Computing Nash Equilibria
 Summary: The LemkeHowson algorithm is a simplexlike algorithm
for computing a Nash equilibrium of a twoplayer game. The paper
below shows that it has exponential worstcase running time, and uses
some nice polytope theory to do it.
 Status:
 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 4player case".
I.e., computing a Nash eq in a 4player game can be done in
polytime 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 3player games?
 Status:
 Taken by Andrew Morrison.
 Goldberg/Papadimitriou, Reducibility Among Equilibrium Problems.
 PPADcompleteness of computing a Nash equilibrium
with 4 or more players. Again: why not with 3 or more players?
 Status:
 Daskalakis/Goldberg/Papadimitriou, The Complexity of Computing
a Nash Equilibrium.
 Also discuss the relevant background concepts in the
Papadimitriou JCSS 1994 paper.
 01 Games are Universal TwoPlayer Games (from the perspective of
computing a Nash equilibrium).
 Summary: Computing a Nash equilibrium in arbitrary twoplayer
games reduces to computing one in 01 twoplayer games. Obvious open
questions: what about approximate Nash equilibria? What
about games with more than 2 players?
 Status:
 Abbott/Kane/Valiant, FOCS 2005.
 Sponsored search auctions (batched)
 Summary: Can knapsack auctions be designed to take into account budgets?
 Status:
 Borgs, Immorlica, Mahdian, Saberi, "Multiunit auctions with budgetconstrained 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 LimitedSupply Online Auctions", EC 2004.
 Optional Reference: Awerbuch, Azar, Meyerson, "Reducing truthtelling online mechanisms to online optimization", STOC 2003.
 Optional Reference: Blum, Hartline, "NearOptimal 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:
 Borgs, Immorlica, Mahdian, Saberi, "Multiunit auctions with budgetconstrained bidders", EC 2005.
 Goldberg, Hartline, "CollusionResistant 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 disprove that random sampling for double auctions is constant competitive in worst case (i.e., for the auction defined in Baliga and Vohra).
 Status:
 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:
 Borgs, Immorlica, Mahdian, Saberi, "Multiunit auctions with budgetconstrained bidders", EC 2005.
 Hajiaghayi, Kleinberg, Parkes, "Adaptive LimitedSupply Online Auctions", EC 2004.
 Optional Reference: Abrams, "Revenue Maximization When Bidders Have Budgets" SODA 2006.

Envyfree pricing
 Summary: the optimization problem of envyfree pricing plays a central role in the design of near optimal mechanisms. Envyfree pricing is hard in general. Perhaps there are interesting special cases that are polynomial time solvable.
 Status:
 Gurusuami, Hartline, Karlin, Kempe, Kenyon, McSherry, "On ProfitMaximizing EnvyFree Pricing", SODA 2005.

Briest, Krysta. "SingleMinded Unlimited Supply Pricing on Sparse Instances", SODA 2006.

Demaine, Feige, Hajiaghayi, Salavatipour
"Combination Can Be Hard: Approximability of the Unique Coverage Problem", SODA 2006
 Envyfree procurement
 Summary: There is an interesting relationship between envyfree pricing and the cell phone power problem considered in Bahl et al.
 Status:
 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 ProfitMaximizing EnvyFree 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:
 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.