Fotakis, D and Krysta, P and Ventre, C (2018) The Power of Verification for Greedy Mechanism Design. The Journal of Artificial Intelligence Research, 62. pp. 459-488. DOI https://doi.org/10.1613/jair.1.11215
Fotakis, D and Krysta, P and Ventre, C (2018) The Power of Verification for Greedy Mechanism Design. The Journal of Artificial Intelligence Research, 62. pp. 459-488. DOI https://doi.org/10.1613/jair.1.11215
Fotakis, D and Krysta, P and Ventre, C (2018) The Power of Verification for Greedy Mechanism Design. The Journal of Artificial Intelligence Research, 62. pp. 459-488. DOI https://doi.org/10.1613/jair.1.11215
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 |
---|---|
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 23 Jul 2018 10:27 |
Last Modified: | 16 May 2024 19:26 |
URI: | http://repository.essex.ac.uk/id/eprint/22023 |
Available files
Filename: document.pdf