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

DOI10.1287/moor.2020.1058zbMath1466.91071arXiv1511.09208OpenAlexW3093095863MaRDI QIDQ4991678

Paul Dütting, Thomas Kesselheim, Éva Tardos

Publication date: 3 June 2021

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.09208

zbMATH Keywords

randomized rounding price of anarchy algorithmic mechanism design oblivious rounding nontruthful mechanisms smoothness framework

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Algorithmic game theory and complexity (91A68) Mechanism design theory (91B03)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Uniform price auctions: equilibria and efficiency
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
Probabilistic construction of deterministic algorithms: approximating packing integer programs
Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Bounding the inefficiency of outcomes in generalized second price auctions
Combinatorial auctions with decreasing marginal utilities
Computationally Manageable Combinational Auctions
Truthful Mechanisms with Implicit Payment Computation
Inefficiency of Standard Multi-unit Auctions
Valuation Compressions in VCG-Based Combinatorial Auctions
Online Mechanism Design (Randomized Rounding on the Fly)
Intrinsic Robustness of the Price of Anarchy
Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding
Approximation Techniques for Utilitarian Mechanism Design
Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
On k-Column Sparse Packing Programs
Optimal Flows in Networks with Multiple Sources and Sinks, with Applications to Oil and Gas Lease Investment Programs
Incentives in Teams
An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
Randomized metarounding
On Maximizing Welfare When Utility Functions Are Subadditive
On the Complexity of Computing an Equilibrium in Combinatorial Auctions
Truthful and Near-Optimal Mechanism Design via Linear Programming
On the limits of black-box reductions in mechanism design
Black-Box Randomized Reductions in Algorithmic Mechanism Design
Composable and efficient mechanisms
Equilibria of Greedy Combinatorial Auctions
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
Bayesian Combinatorial Auctions
Algorithm for optimal winner determination in combinatorial auctions

This page was built for publication: Algorithms as Mechanisms: The Price of Anarchy of Relax and Round