Algorithms as Mechanisms: The Price of Anarchy of Relax and Round

Add to your list(s) Download to your calendar using vCal

• Paul Dütting (LSE)
• Tuesday 18 November 2014, 14:00-15:00
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Felix Fischer.

Many algorithms, that are originally designed without explicitly considering incentive properties, are later combined with simple pricing rules and used as mechanisms. The resulting mechanisms are often natural and simple to understand. But how good are these algorithms as mechanisms? Truthful reporting of valuations is typically not a dominant strategy (certainly not with a pay-your-bid, first-price rule, but it is likely not a good strategy even with a critical value, or second-price style rule either). Our goal is to show that a wide class of approximation algorithms yields this way mechanisms with low Price of Anarchy.

The seminal result of Lucier and Borodin [SODA’10] shows that combining a greedy algorithm that is an alpha-approximation algorithm with a pay-your-bid payment rule yields a mechanism whose Price of Anarchy is O(alpha). In this paper we significantly extend the class of algorithms for which such a result is available by showing that this close connection between approximation ratio on the one hand and Price of Anarchy on the other also holds for the design principle of relaxation and rounding provided that the relaxation is smooth and the rounding is oblivious.

We demonstrate the far-reaching consequences of our result by showing its implications for sparse packing integer programs, such as multi-unit auctions and generalized matching, for the maximum traveling salesman problem, for combinatorial auctions, and for single source unsplittable flow problems. In all these problems our approach leads to novel simple, near-optimal mechanisms whose Price of Anarchy either matches or beats the performance guarantees of known mechanisms.

Joint work with Thomas Kesselheim and Eva Tardos

This talk is part of the Optimization and Incentives Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Economics and Computer Science Talks
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• Optimization and Incentives Seminar
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.