Core-selecting payment rules for combinatorial auctions with uncertain availability of goods

Moor, Dmitry; Seuken, Sven; Grubenmann, Tobias; Bernstein, Abraham

Abstract

In some auction domains, there is uncertainty regarding the final availability of the goods being auctioned off. For example, a government may auction off spectrum from its public safety network, but it may need this spectrum back in times of emergency. In such a domain, standard combinatorial auctions perform poorly because they lead to violations of individual rationality (IR), even in expectation, and to very low efficiency. In this paper, we study the design of core-selecting payment rules for such domains. Surprisingly, we show that in this new domain, there does not exist a payment rule with is guaranteed to be ex-post core-selecting. However, we show that by designing rules that are “execution-contingent,” i.e., by charging payments that are conditioned on the realization of the availability of the goods, we can reduce IR violations. We design two core-selecting rules that always satisfy IR in expectation. To study the performance of our rules we perform a computational Bayes-Nash equilibrium analysis. We show that, in equilibrium, our new rules have better incentives, higher efficiency, and a lower rate of ex-post IR violations than standard core-selecting rules.

Citation

Moor, D., Seuken, S., Grubenmann, T., & Bernstein, A. (2016, July). Core-selecting payment rules for combinatorial auctions with uncertain availability of goods. Presented at Twenty-Fifth International Joint Conference on Artificial Intelligence, New York

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Twenty-Fifth International Joint Conference on Artificial Intelligence
• Start Date: Jul 9, 2016
• End Date: Jul 15, 2016
• Publication Date: 2016
• Deposit Date: Jun 3, 2023
• Pages: 424-432
• Book Title: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)
• ISBN: 978-1-57735-770-4
• Public URL: http://researchrepository.napier.ac.uk/Output/3116058
• Publisher URL: https://www.ijcai.org/Proceedings/16