Truthful and near-optimal mechanism design via linear programming

By Ron Lavi, Chaitanya Swamy. IEEE Annual Symposium on Foundations of Computer Science, 2005

320 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Budget Feasible Mechanisms (2010, methodology): “one can avoid randomization by using a sophisticated technique that uses relaxation of a nonlinear program. The following method can be applied to Coverage problems. Our method is inspired by [5] and [21] who display the powerful use of LP relaxations for designing truthful mechanisms. First, we par”
On maximizing welfare when utility functions are subadditive (2006, methodology): “Extending an approach of [9], we show how this can be done when players wish to maximize their expected benefit (namely, expected utility minus”
Approximate Mechanism Design without Money (2013, background): “The social cost of a facility location y ∈ R n with respect to the proﬁle x ∈ R n is sc( y, x ) = i ∈ N cost( y, x i ); the social cost of a distribution P with respect to x is sc( P, x ) = E y ∼ P [sc( y, x )].”