A universally-truthful approximation scheme for multi-unit auctions

Berthold Vöcking

Games and Economic Behavior, 2019, vol. 113, issue C, 4-16

Abstract: We present a randomized incentive-compatible polynomial-time approximation scheme for multi-unit auctions. For every fixed ϵ>0, the approximation scheme provides a polynomial-time algorithm approximating the optimal social welfare within a factor of 1−ϵ. Our mechanism is truthful in the universal sense, i.e., it is a distribution over deterministically truthful mechanisms. It employs VCG payments in a non-standard way as the underlying deterministic mechanisms are not maximal in range and do not belong to the class of affine maximizers. Instead, each of them is composed of a collection of affine maximizers, one for each bidder. This yields a subjective variant of VCG in which payments for different bidders are defined on the basis of possibly different affine maximizers.

Keywords: Mechanism design; Multi-unit auctions; Universal truthfulness (search for similar items in EconPapers)
JEL-codes: C61 C63 D44 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825613001735
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:113:y:2019:i:c:p:4-16

DOI: 10.1016/j.geb.2013.12.007

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().