# Fast Convex Decomposition for Truthful Social Welfare Approximation

arXiv: https://arxiv.org/abs/1408.2690 · HTML: https://mlsanity.com/paper/1408.2690/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2014.

## Built on by (most cited first, 1 of 1)

- [Optimal Auction Design for the Gradual Procurement of Strategic Service Provider Agents](https://mlsanity.com/paper/2110.12846/) (2021)

## Abstract (arXiv)

Approximating the optimal social welfare while preserving truthfulness is a well studied problem in algorithmic mechanism design. Assuming that the social welfare of a given mechanism design problem can be optimized by an integer program whose integrality gap is at most α, Lavi and Swamy~citeLavi11 propose a general approach to designing a randomized α-approximation mechanism which is truthful in expectation. Their method is based on decomposing an optimal solution for the relaxed linear program into a convex combination of integer solutions. Unfortunately, Lavi and Swamy's decomposition technique relies heavily on the ellipsoid method, which is notorious for its poor practical performance. To overcome this problem, we present an alternative decomposition technique which yields an α(1 + ε) approximation and only requires a quadratic number of calls to an integrality gap verifier.