Approximately Efficient Two-Sided Combinatorial Auctions
ACM Transactions on Economics and Computation · 29.02.2020 · 8 (1) · 1-29
DOI: 10.1145/3381523 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 11.03.2020. Verfasst von Riccardo Colini-Baldeschi und 5 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 34 Literaturangaben. Gefördert von: MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets”, NSF, ERC.
Abstract (Originalsprache)
We develop and extend a line of recent work on the design of mechanisms for two-sided markets. The markets we consider consist of buyers and sellers of a number of items, and the aim of a mechanism is to improve the social welfare by arranging purchases and sales of the items. A mechanism is given prior distributions on the agents’ valuations of the items, but not the actual valuations; thus, the aim is to maximise the expected social welfare over these distributions. As in previous work, we are interested in the worst-case ratio between the social welfare achieved by a truthful mechanism and the best social welfare possible. Our main result is an incentive compatible and budget balanced constant-factor approximation mechanism in a setting where buyers have XOS valuations and sellers’ valuations are additive. This is the first such approximation mechanism for a two-sided market setting where the agents have combinatorial valuation functions. To achieve this result, we introduce a more general kind of demand query that seems to be needed in this situation. In the simpler case that sellers have unit supply (each having just one item to sell), we give a new mechanism whose welfare guarantee improves on a recent one in the literature. We also introduce a more demanding version of the strong budget balance (SBB) criterion, aimed at ruling out certain “unnatural” transactions satisfied by SBB. We show that the stronger version is satisfied by our mechanisms.
Förderung
- MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets”
- NSF
- ERC
- Google Focused Award on “Algorithms for Large-scale Data Analysis”
Zitieren
APA
Colini-Baldeschi, R., Goldberg, P. W., Keijzer, B. D., Leonardi, S., Roughgarden, T., & Turchetta, S. (2020). Approximately Efficient Two-Sided Combinatorial Auctions. ACM Transactions on Economics and Computation, 8(1), 1-29. https://doi.org/10.1145/3381523
Vancouver
Colini-Baldeschi R, Goldberg PW, Keijzer BD, Leonardi S, Roughgarden T, Turchetta S. Approximately Efficient Two-Sided Combinatorial Auctions. ACM Transactions on Economics and Computation. 2020;8(1):1-29. doi:10.1145/3381523
BibTeX
@article{ColiniBaldeschi2020,
author = {Colini-Baldeschi, Riccardo and Goldberg, Paul W. and Keijzer, Bart de and Leonardi, Stefano and Roughgarden, Tim and Turchetta, Stefano},
title = {Approximately Efficient Two-Sided Combinatorial Auctions},
journal = {ACM Transactions on Economics and Computation},
year = {2020},
volume = {8},
number = {1},
pages = {1--29},
doi = {10.1145/3381523}
}
EUVIMED