Mechanisms for multi-unit auctions

DOI10.1613/JAIR.2950MaRDI QIDQ5190267zbMATH OpenOpenAlexFDO

Authors Shahar Dobzinski, Noam Nisan

Publication date 15 March 2010

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: We present an incentive-compatible polynomial-time approximation scheme for multi-unit auctions with general k-minded player valuations. The mechanism fully optimizes over an appropriately chosen sub-range of possible allocations and then uses VCG payments over this sub-range. We show that obtaining a fully polynomial-time incentive-compatible approximation scheme, at least using VCG payments, is NP-hard. For the case of valuations given by black boxes, we give a polynomial-time incentive-compatible 2-approximation mechanism and show that no better is possible, at least using VCG payments.

Recommendations

• A universally-truthful approximation scheme for multi-unit auctions
• scientific article; zbMATH DE number 7053320
• Incentive compatible mulit-unit combinatorial auctions: a primal dual approach
• Mechanisms for multi-unit combinatorial auctions with a few distinct goods
• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents

Cited in

(25)

• Multidimensional mechanism design for auctions with externalities
• Setting lower bounds on truthfulness
• A universally-truthful approximation scheme for multi-unit auctions
• Network pollution games
• On fair price discrimination in multi-unit markets
• Multi-unit auctions: beyond Roberts
• On social envy-freeness in multi-unit markets
• Incentive compatible mulit-unit combinatorial auctions: a primal dual approach
• Limitations of VCG-based mechanisms
• On the choice of obtaining and disclosing the common value in auctions
• Truthful approximation mechanisms for restricted combinatorial auctions
• New results for network pollution games
• Mechanism design with approximate valuations
• Prompt Mechanism for Online Auctions with Multi-unit Demands
• scientific article; zbMATH DE number 5845905 (Why is no real title available?)
• MECHANISM DESIGN FOR OPTIMAL AUCTION OF DIVISIBLE GOODS
• Welfare and revenue guarantees for competitive bundling equilibrium
• scientific article; zbMATH DE number 7204414 (Why is no real title available?)
• Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems
• scientific article; zbMATH DE number 7053320 (Why is no real title available?)
• Advances in Computing Science – ASIAN 2003. Progamming Languages and Distributed Computation Programming Languages and Distributed Computation
• Walrasian pricing in multi-unit auctions
• Fairness and incentive compatibility via percentage fees
• Multidimensional auctions
• Uniform price auctions: equilibria and efficiency

This page was built for publication: Mechanisms for multi-unit auctions

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