Papers for Presentation

For each section, there is a partial order on how the papers should be presented.

Mechanism Design and Auctions with Scheduling Applications

Partial order (1  2, 3  4)

  1. Aaron Archer and Éva Tardos, "Truthful mechanisms for one-parameter agents", FOCS 2001.
  2. Seminal paper that follows up the Algorithmic Mechanism Design paper that I have covered in lecture. Focuses on minimizing makespan in the related machine model.
  3. V. Auletta, R. De Prisco, P. Penna, G. Persiano, “Deterministic Truthful Mechanisms for Scheduling on Selfish Machines”, STACS 2004.
  4. Follows up the Archer Tardos paper with a deterministic truthful mechanism for variants of the problem of minimizing makespan on related machines.
  5. A. Fiat, A. Goldberg, J. Hartline and A. Karlin,"Competitive Generalized Auctions,"STOC 2002: 72-81.
  6. Focuses on auctioning a resource with unlimited numbers of copies such as digital music.
  7. A. V. Goldberg and J. D. Hartline,“Envy-Free Auctions for Digital Goods” (EC '03).
  8. A followup study of auctions for a commodity in unlimited supply, e.g., a digital good. In particular they consider three desirable properties for auctions: being competitive, truthful, and envy-free.
  9. A. V. Goldberg and J. D. Hartline(MSR-TR-2004-40), “Collusion-Resistant Mechanisms for Single-Parameter Agents” . (SODA 2005).
  10. They consider the problem of designing mechanisms with the incentive property that no coalition of agents can engage in a collusive strategy that results in an increase in the combined utility of the coalition.
  11. John Hershberger and Subhash Suri. Vickrey Prices and Shortest Paths: What is an edge worth?, FOCS 2001
  12. They show that the shortest path mechanism given in the Algorithmic Mechanism design paper covered in class can be made more efficient.

Price of Anarchy

Partial order: (1  all, 2  3)

1)E. Koutsoupias, C. H. Papadimitriou "Worst-case equilibria", STACS 99.

  • Seminal paper that introduces “price of anarchy” concept. Examines simple model.

2)T. Roughgarden and É. Tardos. How Badis Selfish Routing?. In FOCS 2000 and JACM 2002.

  • This paper, which I touched on very briefly in class, analyzes how total latency can increase when users route themselves selfishly as opposed to in a coordinated fashion.

3)T. Roughgarden. The Price of Anarchy is Independent of the Network Topology. In JCSS 2003.

  • This paper shows that essentially the worst case happens for minimizing total latency on very simple networks. Thus, network topology is not the problem.

4)A. Czumaj and B. Vöcking: Tight Bounds for Worst-Case Equilibria, in SODA 2002.

  • Provides tight bounds for the model introduced by Koutsoupias and Papadimitriou.

5)Adrian Vetta, Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions. FOCS, 2002.

  • Studies conditions under which price of anarchy will not be too bad. Applications to the routing problem considered before as well as facility location and other related problems.