Truth revelation in approximately efficient combinatorial auctions

By Daniel J. Lehmann, Liadan O'Callaghan, Yoav Shoham. JACM, 2002

800 citations recorded by the source corpus.

Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms---in particular, their truth revelation properties---assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.

Subfields: Economics and Econometrics, Management Science and Operations Research, Marketing

View Paper: https://www.semanticscholar.org/paper/4d450f968ade898eeb96708b81b21a76de553584

How researchers see this paper

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

In Economics and Econometrics

In Management Science and Operations Research

In Marketing

Citations in the corpus

Computationally feasible VCG mechanisms (2000, methodology): “This characterization precludes the possibility of obtaining truthfulness by applying VCG rules to many of the proposed heuristics for combinatorial auctions (e.g., the greedy algorithms of Lehmann et al., 2002 and Nisan, 2000).”
Computational-Mechanism Design: A Call to Arms (2003, background): “The literature shows a handful of positive results— for instance, for the case of single-minded bidders that desire at most one bundle 20 and for the case of multiunit allocation problems for a slightly relaxed solution concept.”
Revenue generation for truthful spectrum auction in dynamic spectrum access (2009, methodology): “Complexity issues of VCG auction are studied in [14,16] which target social welfare.”
Revenue maximization with a single sample (2010, background): “This factor is essentially optimal for polynomial-time approximation, under appropriate computational complexity assumptions (Lehmann et al., 2002).”