Approximately-strategyproof and tractable multi-unit auctions

Abstract

We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multi-unit allocation problem. The bidding language in our auctions allows marginal-decreasing piecewise constant curves. First, we develop a fully polynomial-time approximation scheme for the multi-unit allocation problem, which computes a (1+ε)≈ in worst-case time T = O(n3/ε), given n bids each with a constant number of pieces. Second, we embed this approximation scheme within a Vickrey-Clarke-Groves (VCG) mechanism and compute payments to n agents for an asymptotic cost of O(T log n). The maximal possible gain from manipulation to a bidder in the combined scheme is bounded by ε/(1+ε) V, where V is the total surplus in the efficient outcome.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 99 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.