Truthful Mechanisms via Greedy Iterative Packing

DOI10.1007/978-3-642-03685-9_5zbMATH Open1254.68354arXiv0906.2466OpenAlexW2067557609MaRDI QIDQ3638869FDOQ3638869

Authors: Chandra Chekuri, Iftah Gamzu 

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Abstract: An important research thread in algorithmic game theory studies the design of efficient truthful mechanisms that approximate the optimal social welfare. A fundamental question is whether an alpha-approximation algorithm translates into an alpha-approximate truthful mechanism. It is well-known that plugging an alpha-approximation algorithm into the VCG technique may not yield a truthful mechanism. Thus, it is natural to investigate properties of approximation algorithms that enable their use in truthful mechanisms. The main contribution of this paper is to identify a useful and natural property of approximation algorithms, which we call loser-independence; this property is applicable in the single-minded and single-parameter settings. Intuitively, a loser-independent algorithm does not change its outcome when the bid of a losing agent increases, unless that agent becomes a winner. We demonstrate that loser-independent algorithms can be employed as sub-procedures in a greedy iterative packing approach while preserving monotonicity. A greedy iterative approach provides a good approximation in the context of maximizing a non-decreasing submodular function subject to independence constraints. Our framework gives rise to truthful approximation mechanisms for various problems. Notably, some problems arise in online mechanism design.

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

Recommendations

• Approximation techniques for utilitarian mechanism design
• Approximation techniques for utilitarian mechanism design
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• scientific article; zbMATH DE number 2079341

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Applications of game theory (91A80) Approximation algorithms (68W25) Welfare economics (91B15)

Cited In (8)

• Online knapsack revisited
• Equilibria of Greedy Combinatorial Auctions
• Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem
• Truthful Unification Framework for Packing Integer Programs with Choices
• Optimal interval scheduling with a resource constraint
• Approximate composable truthful mechanism design
• Truthful mechanism design for bin packing with applications on cloud computing
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Truthful Mechanisms via Greedy Iterative Packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638869)