Approximately-strategyproof and tractable multiunit auctions

Approximately-strategyproof and tractable multiunit auctions

0.00 Avg rating0 Votes
Article ID: iaor20051916
Country: Netherlands
Volume: 39
Issue: 1
Start Page Number: 105
End Page Number: 121
Publication Date: Mar 2005
Journal: Decision Support Systems
Authors: , ,
Keywords: bidding, combinatorial analysis
Abstract:

We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multiunit allocation problem. The bidding language allows marginal-decreasing piecewise-constant curves and quantity-based side constraints. We develop a fully polynomial-time approximation scheme for the multiunit allocation problem, which computes a (1+e) approximation in worst-case time T=O(n3/e), given n bids each with a constant number of pieces. We integrate this approximation scheme within a Vickrey–Clarke–Groves mechanism and compute payments for an asymptotic cost of O(Tlogn). The maximal possible gain from manipulation to a bidder in the combined scheme is bounded by eV/(1+e), where V is the total surplus in the efficient outcome.

Reviews

Required fields are marked *. Your email address will not be published.