The power of verification for greedy mechanism design

Fotakis, D, Krysta, P and Ventre, C (2015) The power of verification for greedy mechanism design. In: 14th International conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2015), 2015-5-4 - 2015-5-8, Istanbul, Turkey.

Text CAPayments.pdf - Author Accepted Manuscript Download (326kB)

Abstract

Greedy algorithms are known to provide near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders, ignoring incentive compatibility. Borodin and Lucier [5] however proved 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 subsets 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 for the greedy algorithm of [20], which is 2-approximate for submodular CAs, to become truthful with money in finite bidding domains. Our proof is based on an interesting structural analysis of the strongly connected components of the declaration graph.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	21 Jun 2016 08:51
Last Modified:	19 Jan 2023 07:36
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001459