Truthful Mechanisms via Greedy Iterative Packing

DOI10.1007/978-3-642-03685-9_5MaRDI QIDQ3638869zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(8)

• Approximate truthful mechanism design for two-dimensional orthogonal knapsack problem
• Approximate composable truthful mechanism design
• Truthful mechanism design for bin packing with applications on cloud computing
• Mathematical Foundations of Computer Science 2005
• Truthful Unification Framework for Packing Integer Programs with Choices
• Equilibria of greedy combinatorial auctions
• Online knapsack revisited
• Optimal interval scheduling with a resource constraint

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)