Truthful approximation mechanisms for restricted combinatorial auctions

By Ahuva Mu'alem, Noam Nisan. Games Econ. Behav., 2008

352 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.

Towards Sharp Inapproximability For Any 2-CSP (2007, neutral): “As shown by Mu’alem and Nisan [31], an algorithm that takes the MAX of one or more monotone algorithms is not necessarily monotone, and thus not truthful.”
Revenue generation for truthful spectrum auction in dynamic spectrum access (2009, background): “Complexity issues of VCG auction are studied in [14,16] which target social welfare.”
Computer-Aided Verification for Mechanism Design (2015, background): “We especially thank Ran Shorrer for pointing out empirical evidence that agents may manipulate their reports even when the mechanism is truthful.”
Mechanism Design via Differential Privacy (2007, neutral): “For the combinatorial auction problem, the work of Lavi, Mu'alem, and Nisan [27] shows that under fairly natural assumptions, no truthful and computationaly efficient mechanism can give a good approximation to the social welfare.”
Higher-Order Approximate Relational Refinement Types for Mechanism Design and Differential Privacy (2014, background): “A key component of the language is a type analysis to determine if an algorithm is monotone ; if bidders have a single real number as their value ( single-parameter domains ), then truthfulness is equivalent to a monotonicity property (e.g., see Mu’Alem and Nisan [40]).”
Budget Feasible Mechanisms (2010, background): “often reduces to designing monotone allocation rules, since payments can be computed via binary search [21].”