ALGORITHMIC GAME THEORY

---

Presenations.

Here are a few possible papers that can be used for your presentation. Feel free to make other suggestions
if you want to study something with less of an algorithms and complexity bias.

Correlated Equilibria.

C. Papadimitriou, Computing correlated equilibria in multiplayer games, STOC, 2005.
(Taken: Amin Mannani and Mustapha Benjillali.)

Combinatorial Auctions.

S. Dobzinski, N. Nisan and M. Schapira, Approximation algorithms for combinatorial auctions with complement-Free bidders, STOC, 2005.
(Taken: Natalie Stoianov and Zhentao Li)

Multi-Armed Bandit Problem.

P. Auer, N. Cesa-Bianchi, Y. Freund and R. Schapire, Gambling in a rigged casino: the adversarial multi-armed bandit problem, FOCS, 1995.

Online Auctions.

A. Blum and J. Hartline, Near-optimal online auctions, SODA, 2005.
(Taken: Daniel Simeone and Patrick Donovan.)

Hardness of finding Nash Equilibria.

K. Daskalakis, P. Goldberg, C. Papadimitriou, The complexity of computing a Nash equilibrium, preprint, 2005.

X. Chen and X. Deng, Settling the complexity of 2-Player Nash-equilibrium, preprint, 2005.

Communication Complexity.

N. Nisan, The communication complexity of approximate set packing and covering, ICALP, 2002.
(Taken: Anil Ada and Laszlo Egri.)

Bandwidth Sharing.

R. Johari, and J. Tsitsiklis, Efficiency loss in a network resource allocation game, Mathematics of Operations Research, 2004.

Market Equilibria.

N. Devanur et al., Market Equilibrium via a Primal-Dual-Type Algorithm, FOCS, 2002.
(Taken: Philipp Keller and Michel Langlois.)

Power Laws on the Internet.

R. Broder et al., Graph structure in the web, World Wide Web Conference, 2000.

J. Kleinberg and S. Lawrence, The structure of the web, Science, 2001.

M. Faloutsos, P. Faloutsos and C. Faloutsos, On power-law relationships of the Internet topology, SIGCOMM, 1999.

Evolutionary Game Theory.
(Taken: Punit Agrawal and Nicolas Sonnerat)

Graphical Games.
(Taken: Matt Drescher and Hasan Mirza)