Algorithms for selfish agents

This page is http://ec.tcfs.it

Staff: Vincenzo Auletta, Paolo Penna, Giuseppe Persiano.

Objectives: This class intends to discuss some of the issues that are on the border between Theoretical Computer Science (more specifically, Complexity Theory and Design and Analysis of Algorithms) and Microeconomics (more specifically, Game Theory and Incentive Theory).

Next class: Wednesday June 18, 15:00 C/49.

A set of lecture notes for the class is available here.

Topics:

  1. Modeling selfish behaviour.
    Games in strategic form, Nash equilibrium, Prisoner's dilemma, Football Match or Shopping, Matching Pennies.
    Lecture notes available here.
    The book A course in game theory, by M. J. Osborne and A. Rubinstein is an excellent reference for Game Theory.
    The book An introduction to game theory by M. J. Osborne is instead a kinder introduction. Some chapters are availbale from Osborne's home page and can be found at the links below: The seminal paper by John F. Nash Non-cooperative games is available here.

  2. Selfish routing: the flow model.
    Braess's paradox, coordination ratio, upper bound for linear latency.
    Lecture notes available here.
    Most of the material is from the paper How Bad is Selfish Routing? by E. Tardos and T. Roughgarden, FOCS 2000, available here. The paper (and other related papers) can be found at http://www.cs.cornell.edu/timr.

  3. Selfish routing: the discrete model.
    Bounds on the coordination ratio when jobs have discrete sizes.
    Lecture notes available here.
    The material is based on Worst-case equilibria by E. Koutsoupias, C. H. Papadimitriou available here (original site here).

  4. Selfish routing: Stackelberg games
    Bound on the coordinaiton ration when the system manager controls a fraction of the jobs.
    The material is based on Stackelberg Scheduling Strategies by T. Roughgarden.
    The paper is available here or from http://www.cs.cornell.edu/timr.

  5. Introduction to Mechanism Design: VCG mechanisms
    A simple routing problem involving selfish links. The shortest path problem on graphs with edges owned by selfish agents. Definition of dominant strategy and of truthful mechanism. Truthful VCG mechanisms for utilitarian problems.
    Lecture notes available here.
    The material is partially based on Algorithms For Rational Agents by A. Ronen, available here or from http://iew3.technion.ac.il/~amirr/
    The seminal paper by W. Vickrey Counterspeculation, Auctions, and Competitive Sealed Tenders is available here.

  6. Applications of VCG mechanisms
    The problem of sharing the cost of a multicast transmission on a given tree: maximizing the net worth; the problem as a utilitarian problem; an exact algorithm and the VCG payments; other constraints and distributed implementations. The problem of scheduling jobs on unrelated machines: the Min-Work mechanism and its truthfulness; approximation analysis and the lower bound for deterministic truthful mechanisms on two machines.
    The material is partially based on
    1. Sharing the Cost of Multicast Transmissions by J. Feigenbaum, C.H. Papadimitriou and S. Shenker, available from http://cs-www.cs.yale.edu/homes/jf/home.html#papers
    2. Algorithmic mechanism design by N. Nisan and A. Ronen, available here or from http://iew3.technion.ac.il/~amirr/

  7. Combinatorial Auctions
    Definition of the problem and its relations to mechanism design. Integer Programming formulation and discussion of its computational complexity and approximability. Restriction of the problem to single-minded agents and infeasibility of VCG mechanisms. Sufficient conditions to have a truthful auction for single-minded agents. A square root approximation truthful mechanism for single-minded agents. A near-optimal approximation truthful mechanism for known single minded agents.
    Lecture notes available here.
    The material is partially based on
    1. Truth Revelation in Approximately Efficient Combinatorial Auctions by D. Lehmann, L. O'Callaghan and Y. Shoham, available here or from http://www.cs.huji.ac.il/~lehmann/papers/mechanisms/LCS.ps.
    2. Truthful Approximation Mechanisms for Restricted CombinatorialAuctions by Ahuva Mu'alem and Noam Nisan. available from here or from http://www.cs.huji.ac.il/~noam/mkts.html.
    3. Combinatorial Auctions: A survey by S. de Vries and R. Vohra.

  8. Competitive Auctions
    Definition of the problem and competitive framework. Deterministic and randomized auctions. Optimal omniescent single-price and multi-price auctions and their competitiveneness. Non competitiveness of deterministic auctions with respect to omniescent auctions. A randomized 4-competitive auction.
    The material is partially based on
    1. Competitive Auctions by A. Goldberg, H. Hartline, A. Karlin, A. Wright. available from here or from http://www.avglab.com/andrew/.

  9. Scheduling on related machines
    Approximating algorithm for scheudling jobs on related machines owned by selfish agents.
    Lecture notes available here.
    The material in partially based on
    1. Truthful Mechanisms for One-Parameter Agents by A. Archer and E. Tardos. from FOCS 2001 available here or from http://www.orie.cornell.edu/~aarcher/Research/.

    Suggested papers for student presentations

    The following list includes interesting papers that were not presented in class or were presented only partially. The interested students should contact the teaching staff in order to be assigned a paper.

    1. Selfish traffic allocation for server farms by A. Czumaj, P. Krysta, and B. Vocking.

    2. Tight bounds for worst-case equilibria by A. Czumaj and B. Vocking.

    3. Stackelberg Scheduling Strategies by T. Roughgarden.

    4. Algorithmic mechanism design by N. Nisan and A. Ronen

    5. An approximate truthful mechanism for combinatorial auctions with single parameter agents by A. Archer, C. Papadimitriou, K. Talwar and E. Tardos

    6. Applications of Approximation Algorithms to Cooperative Games by K. Jain and V. Vazirani

    Related courses

    Following is a list of classes and links on related topics.