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).
Deadlines:
 by Tuesday 10/31/06: email your project topic to the instructor
(available on a firstcome, firstserve basis).
 by 5PM Friday 11/17/06: email a 13 page outline to the instructor.
 Final report details TBA.
Possible topics:
Algorithmic Mechanism Design
 Profitmaximizing random sampling auctions.
Summary: The same problem that Jason discussed in lecture.
Focus on the second paper and the parts of the first paper that
study the RSOP auction.
 Status:
 Goldberg/Hartline/Karlin/Saks/Wright, "Competitive Auctions",
Games and Economic Behavior, 2006.
 Feige, Flaxman, Hartline, Kleinberg, "On the competitive ratio of
the random sampling auction", WINE 2005.
 CollusionResistant Auctions for Digital Goods.
 Summary: For digital goods, there are near optimal auctions that
resist collusion.
 Status:
 Goldberg, Hartline, "CollusionResistant Mechanism for Single Parameter Agents", SODA 2005.

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.
 Optimal Auctions.
 Summary: studies the design of profitmaximizing
auctions assuming independent prior distributions on
the valuations of the bidders. (A classic paper, a little
technical in parts.)
 Status:
 Roger Myerson, "Optimal auction design", Mathematics of Operations
Research, 1981.
 PolynomialTime Optimal Auctions
 Summary: studies the design of approximately profitmaximizing
auction assuming a prior (possibly correlated) joint distribution on
the valuations of the bidders.
 Status:
 Amir Ronen, " On approximating optimal auctions", EC 2001.
 Ronen/Saberi FOCS 2002 paper.
 Online Auctions with Limited Supply
 Summary: Variants of the problem studied in Problem 3 of HW#1.
 Status:
 Hajiaghayi/Kleinberg/Parkes, Adaptive LimitedSupply Online Auctions, EC 2004.
 Kleinberg, A MultipleChoice Secretary Problem with Applications
to Online Auctions, SODA 2005.
 ProfitMaximization in the Presence of Costs
 Summary: recall that digital goods auctions have no costs
of productions. Adding costs seem to significantly complicate
the problem.
 Status:
 Taken by Aleksandra Korolova.
 Fiat/Goldberg/Hartline/Karlin STOC 2002.
 Optional: try to use the techniques in Roughgarden/Sundararajan
STOC 2006 (discussed at length in class) to design profitmaximizing
mechanisms with costs.
 Sponsored search auctions (equilibrium analysis)
 Summary: Studies the equilibria of the Google and Yahoo! ad auctions.
 Status: taken by Aravindakshan Babu.
 Read the Edelman/Ostrovsky/Schwarz and Varian papers listed as
references for the 10/5 lecture.
 Sponsored search auctions (online)
 Summary: Online algorithms for a problem motivated
by sponsored search auctions.
 Status: taken by Dominic DiPalantino.
 Mehta, Saberi, Vazirani, Vazirani, "AdWords and Generalized Online Matching", FOCS 2005.
 Limited supply auctions with bidders who have budgets
 Summary: Offline auctions for bidders with budgets (motivated
by sponsored search auctions).
 Status:
 Taken by Sean Yehen Ting.
 Borgs, Immorlica, Mahdian, Saberi, "Multiunit auctions with budgetconstrained bidders", EC 2005.
 Abrams SODA 2006.
 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 mechanism (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: This is same topic as Problem 4 of HW#1.
Focus on the results in the second paper, referring to the
first paper for background.
 Status:
 Lehmann/Lehmann/Nisan, EC 2001 (for background).
 Dobzinski/Schapira, An Improved Approximation Algorithm for
Combinatorial Auctions with Submodular Bidders, SODA 2006.
 Approximate Winner Determination with Subadditive Valuations
 Summary: As above, but with more general subadditive valuations.
Focus on the second paper, referring to the first paper for
background.
 Status:
 Dobzinski/Nisan/Schapira, STOC 2005.
 Uriel Feige, On Maximizing Welfare when Utility Functions
are Subadditive, STOC 2006.
 Truthful (in expectation) combinatorial auctions via linear programming.
 Summary: Gives a randomized, polynomialtime, truthful in
expectation combinatorial auction that achieves a
O(\sqrt{m})approximation of surplus for general valuations. 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:
 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: what approximation factor is possible
with polynomial communication for general valuations?
 Status:
 Nisan/Segal (short version) and Nisan, see references for 10/17
lecture.
 Frugality in ShortestPath Auctions and Other Mechanisms
 Summary: studies what magnitudes or payments are necessary
to implement the VCG mechanism in a natural shortestpath
application.
 Status:
 Archer/Tardos, "Frugal Path Mechanisms", SODA 2002.
 Elkind/Sahai/Steiglitz, "Frugality in Path Auctions", SODA 2004.
 Distributed Algorithmic Mechanism Design
 Summary: Studies when mechanisms like the VCG mechanism
can be implemented efficiently in a distributed way.
 Status:
 Feigenbaum/Papadimitriou/Shenker STOC 2000 paper.
 Feigenbaum et al PODC 2002 paper.
 From PrimalDual Algorithm to CrossMonotonic CostSharing Methods.
 Summary: For problems more complicated than fixedtree multicast, designing
an approximately budgetbalanced and crossmonotonic costsharing
method is a nontrivial problem. Primaldual approximation algorithms
have proved very useful for this.
 Status:
 Taken by Donghyun Daniel Kim.
 Jain/Vazirani STOC 2001 paper.
 Pal/Tardos FOCS 2003 paper (focus on the facility location
application, don't worry about the rentorbuy network design part).
 Impossibility Results for BudgetBalanced, CrossMonotonic
CostSharing Methods.
 Summary: Some natural problems do not admit a crossmonotonic costsharing
method with reasonable budget balance.
 Status:
 Immorlica/Mahdian/Mirrokni, SODA 2005.
 Approximation in NonUtilitarian Mechanism Design: the Single
Parameter case.
 Summary: For objectives different than surplus (e.g., more "fair"
objectives) there is no analogue of the VCG mechanism, and all
truthful mechanisms are suboptimal. A natural question is to
understand the best approximation possible by a truthful mechanism.
This paper obtains numerous upper and lower bounds when agents
have simple (depending on only one number) valuations.
 Status:
 Archer/Tardos, FOCS 2001.
 Approximation in NonUtilitarian Mechanism Design: the
MultiParameter case.
 Summary: For more complex valuations, we have little understanding
on what kinds of approximation guarantees are possible with
truthful mechanisms. The papers below show the (limited)
state of the art.
 Status:
 Nisan/Ronen, STOC 1999 (focus on the results about minimizing
the makespan on unrelated machines).
 Christodoulou/Koutsoupias/Vidali, A Lower Bound for Scheduling
Mechanisms, to appear in SODA 2007.
Inefficiency of Equilibria
 Bounding the Price of Anarchy with Asymmetric Costs
 Summary: Derives bounds on the price of anarchy of selfish routing when
the cost of an edge can depend on the entire traffic pattern, rather
than just on the congestion on that edge.
 Status:
 Georgia Perakis, "The Price of Anarchy under Nonlinear and
Asymmetric Costs", IPCO 2005.
 Atomic Selfish Routing
 Summary: Derives bounds on the price of anarchy for special cases of atomic
selfish routing.
 Status:
 Suri/Toth/Zhou SPAA '04.
 I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and
L. Moscardelli. Tight bounds for selfish and greedy load balancing.
ICALP 2006. (Focus on Sections 2 and 3.)
 The WorstCase Severity of Braess's Paradox
 Summary: Indepth study of Braess's Paradox: its worstcase severity and
the computational complexity of detecting it.
 Status:
 Roughgarden,
"On the
Severity of Braess's Paradox: Designing Networks for Selfish Users Is
Hard", Journal of Computer and System Sciences 2006.
 Price of Stability in Undirected Shapley CostSharing Networks
 Summary: what is the price of stability in undirected
Shapley network design games? (Recall it is ln k in directed
networks.) This paper makes progress on a special case.
 Status:
 Fiat/Kaplan/Levy/Olonetsky/Shabo, On the Price of Stability for
Designing Undirected Networks with Fair Cost Allocations, ICALP 2006.
 Price of Anarchy in Local Network Formation Games
 Summary: studies the POA in a different model of network
formation, where players are nodes who build incident edges, rather
than terminal pairs who build entire endtoend paths.
 Status:
 Fabrikant et al, PODC 03.
 Albers et al, SODA 06 (focus on Section 3, improved bounds on the POA).
 Price of Anarchy of Bandwidth Allocation
 Summary: Studies efficiency loss in a natural protocol for
allocating bandwidth. A nice blend of mechanism design and the price
of anarchy.
 Status:
 Ramesh Johari and John Tsitsiklis, "Efficiency loss in a network
resource allocation game", Mathematics of Operations Research 2004.
 Designing Bandwidth Allocation Protocols to Minimize Efficiency Loss
 Summary: Studies how to design bandwidthsharing protocols to
minimize the efficiency loss. Among a natural class, the proportional
sharing protocol in the paper above minimizes this efficiency loss.
 Status:
 Ramesh Johari and John Tsitsiklis, "Characterization theorems for
smooth marketclearing mechanisms", 2005.
 Strong Price of Anarchy
 Summary: In several applications, better bounds are possible for "strong" Nash
equilibria (where no coalition can profitably deviate) than for
regular Nash equilibria.
 Status:
 Andelman/Feldman/Mansour, Strong Price of Anarchy, to appear
in SODA 2007.
 Sink Equilibria
 Summary: what can you say about the price of anarchy
when purestrategy Nash equilibria do not exist? This paper
proposed a relaxed solution concept and proves bounds on the
inefficiency of selfish behavior in atomic selfish routing games with
weighted players.
 Status:
 Taken by Justin Driemeyer.
 Goemans/Mirrokni/Vetta, FOCS 2005.
 The KP Model
 Summary: Bounds on the price of anarchy in scheduling games (in fact, this
model is where the POA was first studied).
 Status:
 Koutsoupias/Papadimitriou, "Worstcase Equilibria", STACS 1999.
 Czumaj/Voecking, "A Tight Bound on Worstcase Equilibria", SODA
2002.
Algorithms for and Complexity of Equilibria
 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.
 PPADcompleteness of computing a Nash equilibrium
in a bimatrix game.
 Status:
 Taken by Christian Romming.
 Chen/Deng, FOCS 2006.
 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.
 Status:
 Abbott/Kane/Valiant, FOCS 2005.
 Complexity of Computing Correlated Equilibria in Compactly
Represented Games
 Summary: Correlated equilibria remain tractable even
in a wide class of compactly represented multiplayer games.
 Status:
 Papadimitriou/Roughgarden, "Computing Equilibria in MultiPlayer
Games", SODA 2005.
 Complexity of Computing Market Equilibria (Combinatorial Approaches)
 Summary: market equilibria refers to a setting of prices to goods
in a market so that supply equals demand. The papers below
give combinatorial algorithms for computing such equilibria.
 Status:
 Devanur et al, "Market Equilibrium via a PrimalDualType
Algorithm", journal version of FOCS 2002 paper.
 Garg/Kapoor, STOC 2004.
 Complexity of Computing Market Equilibria (Mathematical
Programming Approaches)
 Summary: market equilibria refers to a setting of prices to goods
in a market so that supply equals demand. The paper below
gives mathematical programming formulations and algorithms for this
problem.
 Status:
 Jain, "ArrowDebreu Market Equilibrium for Linear Utilities", FOCS 2004.
 Computing PureStrategy Nash Equilibria and PLScompleteness.
 Summary: How hard is it to compute purestrategy Nash equilibria
in games where they are guaranteed to exist? As this paper shows, it
could be easy or hard, and the answer depends on the underlying game
structure in an clean way.
 Status:
 Ackermann/Roeglin/Voecking, FOCS 2006.
 Computing Approximate PureStrategy Nash Equilibria
 Summary: Shows that natural dynamics (players iteratively updating
their strategies) converges quickly to an approximate Nash equilibrium
in a class of congestion games.
 Status:
 Chien/Sinclair, SODA 2007.
 Algorithms for Equilibria in Graphical Games
 Summary: Graphical games are a natural subclass of games
where there is a notion of "locality" between players.
Is it easier to compute Nash equilibria in graphical games
than in arbitrary ones?
 Status:
 Kearns/Littman/Singh, UAI 2001.
 Elkind/Goldberg/Goldberg, EC 2006.