Computationally feasible VCG mechanisms

By Noam Nisan, Amir Ronen. ACM Conference on Economics and Computation, 2000

583 citations recorded by the source corpus.

A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers. The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithm’s output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.

Subfields: Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/a61bd10b57b54a7a9fbec6d4e2b313eb6e1ebafa

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

Citations in the corpus

Sharing the Cost of Multicast Transmissions (2001, background): “In one of the rst works to merge these two concerns, Nisan and Ronen [23, 24, 25 ] pose noncooperative allocation problems such as routing and load balancing and analyze the computational complexity of the relevant strategyproof mechanisms.”
A Survey on Big Data Market: Pricing, Trading and Protection (2018, background): “Seal-bid Auctions have been well explored, and typical examples include the k th-price auction [125], [126], VCG auction [127], [128], and McAfee auction [113].”
Truthful approximation mechanisms for restricted combinatorial auctions (2008, background): “Much work has recently been done on these topics, see e.g., (Vohra & de Vries 2000; Sandholm et al. 2001; Nisan 2000; Lehmann, O’Callaghan, & Shoham 1999) and many references therein.”
Distributed algorithmic mechanism design: recent results and future directions (2002, background): “Nisan and Ronen [52] initiated the study of AMD by adding computational tractability to the set of concerns that must be addressed in the design of incentive-compatible mechanisms.”
Choosing Samples to Compute Heuristic-Strategy Nash Equilibrium (2003, background): “Second, the result can be a mechanism that is not practical to deploy, either for reasons of communication complexity (e.g. [12]) or for reasons of computational complexity (e.g. [10]).”
Iterative combinatorial auctions: achieving economic and computational efficiency (2001, background): “Introduce bidding programs; allow the auctioneer to compute the value of a particular bundle " on-the-fly " (Nisan & Ronen 00) – helps if formulation easier than solution – but, shifts computation to the center and introduces issues of trust and privacy.”
Truth revelation in approximately efficient combinatorial auctions (2002, background): “1999a, 1999b] and the publication of this final version, a number of both impossibility and possibility results [Nisan and Ronen 2000; Archer and Tardos 2001; Lehmann et al. 2001; Bartal et al. 2002; Mu’alem and Nisan 2002] on the topic of feasible approximations and truthful mechanisms for differen”
Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation (2006, background): “Several papers investigate computationally feasible (but inefficient) auctions in private-values settings (see Nisan and Ronen (2000), Lehman et al. (1999), and Holzman and Monderer (2004)).”