Multi-unit auctions: beyond Roberts

DOI10.1016/J.JET.2014.04.006MaRDI QIDQ2253831zbMATH OpenOpenAlexFDO

Authors Shahar Dobzinski, Noam Nisan

Publication date 13 February 2015

Published in Journal of Economic Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.1449

zbMATH Keywords

incentive compatibilityincentive compatible mechanism

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We exhibit incentive compatible multi-unit auctions that are not affine maximizers (i.e., are not of the VCG family) and yet approximate the social welfare to within a factor of $1+epsilon$. For the case of two-item two-bidder auctions we show that these auctions, termed Triage auctions, are the only scalable ones that give an approximation factor better than 2. "Scalable" means that the allocation does not depend on the units in which the valuations are measured. We deduce from this that any scalable computationally-efficient incentive-compatible auction for $m$ items and $nge2$ bidders cannot approximate the social welfare to within a factor better than 2. This is in contrast to arbitrarily good approximations that can be reached under computational constraints alone, and in contrast to the fact that the optimal social welfare can be obtained under incentive constraints alone.

Recommendations

• Efficient multiunit auctions for normal goods
• A universally-truthful approximation scheme for multi-unit auctions
• Mechanisms for multi-unit auctions
• scientific article; zbMATH DE number 7053320
• Multi-unit auctions with budget limits

Cites work

• scientific article; zbMATH DE number 5343724 (Why is no real title available?)
• scientific article; zbMATH DE number 3670138 (Why is no real title available?)
• Algorithmic mechanism design
• Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods
• Ex-post implementation and preference aggregation via potentials
• Groves' Scheme on Restricted Domains
• Monotonicity and implementability
• Roberts' theorem with neutrality: a social welfare ordering approach
• The communication requirements of efficient allocations and supporting prices
• Truthful germs are contagious: a local-to-global characterization of truthfulness
• Truthful implementation and preference aggregation in restricted domains
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation

Cited in

(19)

• Characterizing incentive compatible, Pareto optimal and sufficiently anonymous constrained combinatorial mechanisms -- two players case
• Multidimensional auctions
• A universally-truthful approximation scheme for multi-unit auctions
• Roberts' theorem with neutrality: a social welfare ordering approach
• Introduction to computer science and economic theory
• scientific article; zbMATH DE number 7204414 (Why is no real title available?)
• The case for multi-unit single-run descending-price auctions
• Separability and decomposition in mechanism design with transfers
• Dictatorial mechanisms in constrained combinatorial auctions
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• Walrasian pricing in multi-unit auctions
• Towards characterizing the deterministic combinatorial constrained efficient space
• Mechanism design with two alternatives in quasi-linear environments
• On fair price discrimination in multi-unit markets
• No truthful mechanism can be better than n approximate for two natural problems
• On social envy-freeness in multi-unit markets
• Bribeproof Mechanisms for Two-Values Domains
• Large multi-unit auctions with a large bidder
• Monotonicity and revenue equivalence domains by monotonic transformations in differences

This page was built for publication: Multi-unit auctions: beyond Roberts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2253831)