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.

Approximately Efficient Two-Sided Combinatorial Auctions / Colini-Baldeschi, Riccardo; Goldberg, Paul W.; de Keijzer, Bart; Leonardi, Stefano; Roughgarden, Tim; Turchetta, Stefano. - (2017), pp. 591-608. (Intervento presentato al convegno 18th ACM Conference on Economics and Computation, EC 2017 tenutosi a Cambridge; United States) [10.1145/3033274.3085128].

Approximately Efficient Two-Sided Combinatorial Auctions

Colini-Baldeschi, Riccardo;de Keijzer, Bart;Leonardi, Stefano
;
Turchetta, Stefano
2017

Abstract

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.
2017
18th ACM Conference on Economics and Computation, EC 2017
Combinatorial Auctions; Mechanism Design; Two-sided Markets
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Approximately Efficient Two-Sided Combinatorial Auctions / Colini-Baldeschi, Riccardo; Goldberg, Paul W.; de Keijzer, Bart; Leonardi, Stefano; Roughgarden, Tim; Turchetta, Stefano. - (2017), pp. 591-608. (Intervento presentato al convegno 18th ACM Conference on Economics and Computation, EC 2017 tenutosi a Cambridge; United States) [10.1145/3033274.3085128].
File allegati a questo prodotto
File Dimensione Formato  
Colini-Baldeschi_Postprint_Approximately_2017.pdf

accesso aperto

Note: https://dl.acm.org/citation.cfm?doid=3033274.3085128
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 720.3 kB
Formato Adobe PDF
720.3 kB Adobe PDF
Colini-Baldeschi_Frontespizio-indice_Approximately_2017.pdf

accesso aperto

Tipologia: Altro materiale allegato
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.52 MB
Formato Adobe PDF
1.52 MB Adobe PDF
Colini-Baldeschi_Approximately_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.47 MB
Formato Adobe PDF
1.47 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1073149
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 19
social impact