A universally-truthful approximation scheme for multi-unit auctions

• 成果类型: Article
• 署名作者: Voecking, Berthold
• 署名单位: RWTH Aachen University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.12.007
• 发表日期: 2019
• 页码: 4-16
• 关键词: Mechanism design; Multi-unit auctions; Universal truthfulness

摘要

We present a randomized incentive-compatible polynomial-time approximation scheme for multi-unit auctions. For every fixed is an element of > 0, the approximation scheme provides a polynomial-time algorithm approximating the optimal social welfare within a factor of 1 - is an element of. 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. (C) 2014 Elsevier Inc. All rights reserved.