Combinatorial auctions with verification are tractable

Krysta, Piotr and Ventre, Carmine (2015) Combinatorial auctions with verification are tractable. THEORETICAL COMPUTER SCIENCE, 571 (C). pp. 21-35.

Text cawithverfull4.pdf - Unspecified Download (328kB)

Abstract

We study mechanism design for social welfare maximization in combinatorial auctions with general bidders given by demand oracles. It is a major open problem in this setting to design a deterministic truthful auction which would provide the best possible approximation guarantee in polynomial time, even if bidders are double-minded (i.e., they assign positive value to only two sets in their demand collection). On the other hand, there are known such randomized truthful auctions in this setting. In the general model of verification (i.e., some kind of overbidding can be detected) we provide the first deterministic truthful auctions which indeed provide essentially the best possible approximation guarantees achievable by any polynomial-time algorithm even if the complete input data is known. This shows that deterministic truthful auctions have the same power as randomized ones if the bidders withdraw from unrealistic lies. Our truthful auctions are based on greedy algorithms and our approximation guarantee analyses employ linear programming duality based techniques. Finally, our truthfulness analyses are based on applications of the cycle-monotonicity technique which we show to surprisingly couple with the greedy approach.

Item Type:	Article
Uncontrolled Keywords:	Mechanism design, Foundation of incentive-compatibility, Combinatorial auctions, Mechanisms with verification
Depositing User:	Symplectic Admin
Date Deposited:	03 Dec 2015 11:19
Last Modified:	16 Dec 2022 12:11
DOI:	10.1016/j.tcs.2015.01.001
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2040779

Available Versions of this Item

• Combinatorial auctions with verification are tractable. (deposited 03 Dec 2015 11:19) [Currently Displayed]