Computer Science, Algorithms and Economics
Here is a preliminary list of papers which we will read and present
in class.
- Sept 6 and 11, 2006.
Algorithmic Mechanism Design
by N. Nisan and A. Ronen. Expanded version of the paper that appeared in STOC 1999.ps
-
Sept 13, 2006.
Algorithms for Selfish Agents -- Mechanism Design for Distributed Computation
by N. Nisan. STACS 1999.ps
-
Sept 13, 2006.
A. Archer and 'E. Tardos: Frugal Path mechanisms, in the Proceedings of the 2002 Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 991-999.ps
-
Sept 18, 2006.
T. Roughgarden and E. Tardos: How Bad is Selfish Routing? JACM, 2002. Preliminary version has appeared in the Proceedings of the 41st Annual IEEE Symposium on the Foundations of Computer Science, 2000. ps
-
Sept 20 and 25, 2006.
Truth Revelation in Approximately Efficient Combinatorial Auctions, Lehmann et al., JACM 49(5) Sept. 2002 pp. 577-602pdf
-
Sept 27, 2006.
On profit-maximizing envy-free pricing.
V. Guruswami, J. Hartline, Anna Karlin, D. Kempe, C. Kenyon and F. McSherry. pdf
-
Oct 2, 2006.
Competitive auctions. A. Goldberg, J. Hartline, A. Karlin, M. Saks and A. Wright.pdf
-
Oct 4 and 11, 2006.
Game theory and
von Neumann minimax theorem: statement, proof, application
to randomized lower bounds, relation with strong LP duality theorem,
application of minimax theorem to Max-flow-min-cut.
-
Oct 16, 2006.
Non-cooperative multicast and facility location games, by
Chekuri Chuzhoy Lewin-Eytan Naor and Orda.
-
Oct 18 Itay Neeman. Sequential auction problems on eBay. EC 2006.
-
Oct 23, 2006.
Worst case equilibria, Koutsoupias and Papadimitriou, STACS 1998.
ps
-
Oct 25 Aparna Das. An analysis of alternative slot auction designs for sponsored search. S. Lahaie.
-
Oct 30, 2006.
Alexander Vasserman. Convergence to approximate Nash equilibria in congestion games.
-
Nov 1 Aurojit Panda. Equilibria in online games.
-
Nov 6
The complexity of computing a Nash equilibrium.
-
Nov 8 Jacob Baskin. Strong price of anarchy.
-
Nov 13 Jadrian Miles. Settling the complexity of a 2-player Nash
equilibrium.
-
Nov 15 class cancelled.
-
Nov 20, 2006. Existence of general Nash equilibria.pdf
-
Nov 22 no class (Thanksgiving weekend).
-
Nov 27, 2006. Warren Schudy. Market equilibrium via a primal-dual type algorithm.
-
Nov 29 Ha Tran. Adwords and generalized online matching.
-
Dec 4, 2006. Class from 3 to 5:30pm.
Tingjian Ge. Random Popular Matchings, by Mohammad Mahdian.
Yaris Sabzposh "Convergence and Approximation in Potential Games" by Christodoulou, et al.
-
Dec 6, 2006. Class from 3 to 5:30pm. Bernard Gordon. New trade-offs in cost-sharing mechanisms.
Areeb Sabzposh.
Routing Without Regret: On Convergence to Nash Equilibria of Regret
Minimizing Algorithms in Routing Games
-
Dec 11, 2006. Will Cooper. Playing games in many possible worlds