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

Paul Dütting (), Thomas Kesselheim () and Éva Tardos ()
Additional contact information
Paul Dütting: Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom
Thomas Kesselheim: Institute of Computer Science, University of Bonn, 53115 Bonn, Germany
Éva Tardos: Department of Computer Science, Cornell University, Ithaca, New York 14853

Mathematics of Operations Research, 2021, vol. 46, issue 1, 317-335

Abstract: Many algorithms that are originally designed without explicitly considering incentive properties are later combined with simple pricing rules and used as mechanisms. A key question is therefore to understand which algorithms, or, more generally, which algorithm design principles, when combined with simple payment rules such as pay your bid, yield mechanisms with a small price of anarchy. Our main result concerns mechanisms that are based on the relax-and-round paradigm. It shows that oblivious rounding schemes approximately preserve price of anarchy guarantees provable via smoothness. By virtue of our smoothness proofs, our price of anarchy bounds extend to Bayes–Nash equilibria and learning outcomes. In fact, they even apply out of equilibrium, requiring only that agents have no regret for deviations to half their value. We demonstrate the broad applicability of our main result by instantiating it for a wide range of optimization problems ranging from sparse packing integer programs, over single-source unsplittable flow problems and combinatorial auctions with fractionally subadditive valuations, to a maximization variant of the traveling salesman problem.

Keywords: algorithmic mechanism design; nontruthful mechanisms; price of anarchy; smoothness framework; randomized rounding; oblivious rounding (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2020.1058 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:1:p:317-335

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().