The Power of Verification for Greedy Mechanism Design



Fotakis, Dimitris, Krysta, Piotr and Ventre, Carmine
(2018) The Power of Verification for Greedy Mechanism Design. Journal of Artificial Intelligence Research, 62. pp. 459-488.

[img] Text
cmon24-Elements.pdf - Author Accepted Manuscript

Download (394kB)

Abstract

Greedy algorithms are known to provide, in polynomial time, near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders. It is known that truthful greedy-like mechanisms for CAs with multi-minded bidders do not achieve good approximation guarantees. In this work, we seek a deeper understanding of greedy mechanism design and investigate under which general assumptions, we can have efficient and truthful greedy mechanisms for CAs. Towards this goal, we use the framework of priority algorithms and weak and strong verification, where the bidders are not allowed to overbid on their winning set or on any subset of this set, respectively. We provide a complete characterization of the power of weak verification showing that it is sufficient and necessary for any greedy fixed priority algorithm to become truthful with the use of money or not, depending on the ordering of the bids. Moreover, we show that strong verification is sufficient and necessary to obtain a 2-approximate truthful mechanism with money, based on a known greedy algorithm, for the problem of submodular CAs in finite bidding domains. Our proof is based on an interesting structural analysis of the strongly connected components of the declaration graph.

Item Type: Article
Depositing User: Symplectic Admin
Date Deposited: 17 May 2018 11:37
Last Modified: 19 Jan 2023 06:33
DOI: 10.1613/jair.1.11215
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3021400