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:
- 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.
- 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.
- 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).
- 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.
- 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.
- 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
- 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
- Algorithmic mechanism design by N. Nisan and A. Ronen, available
here or from http://iew3.technion.ac.il/~amirr/
- 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
- 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.
- 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.
- Combinatorial Auctions: A survey by S. de Vries and R. Vohra.
- 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
- Competitive Auctions by A. Goldberg, H. Hartline, A. Karlin, A.
Wright. available from here or from http://www.avglab.com/andrew/.
- 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
- 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.
- Selfish traffic allocation
for server farms by A. Czumaj, P. Krysta, and B. Vocking.
- Tight bounds for
worst-case equilibria by A. Czumaj and B. Vocking.
- Stackelberg Scheduling
Strategies by T. Roughgarden.
- Algorithmic mechanism
design by N. Nisan and A. Ronen
- An approximate truthful
mechanism for combinatorial auctions with single parameter agents by
A. Archer, C. Papadimitriou, K. Talwar and E. Tardos
- 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.