A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets that maximizes social welfare must run a deficit, resulting in a necessity to relax welfare efficiency and the use of approximation mechanisms. Such mechanisms in general make extensive use of the Bayesian priors. In this work, we investigate a question of increasing theoretical and practical importance: how much prior information is required to design mechanisms with near-optimal approximations? Our first contribution is a more general impossibility result stating that no meaningful approximation is possible without any prior information, expanding the famous impossibility result of Myerson and Satterthwaite. Our second contribution is that one single sample (one number per item), arguably a minimum-possible amount of prior information, from each seller distribution is sufficient for a large class of two-sided markets. We prove matching upper and lower bounds on the best approximation that can be obtained with one single sample for subadditive buyers and additive sellers, regardless of computational considerations. Our third contribution is the design of computationally efficient blackbox reductions that turn any one-sided mechanism into a two-sided mechanism with a small loss in the approximation, while using only one single sample from each seller. On the way, our blackbox-type mechanisms deliver several interesting positive results in their own right, often beating even the state of the art that uses full prior information.

Efficient two-sided markets with limited information / Dütting, Paul; Fusco, Federico; Lazos, Filippos; Leonardi, Stefano; Reiffenhäuser, Rebecca. - (2021), pp. 1452-1465. (Intervento presentato al convegno ACM Symposium on Theory of Computing tenutosi a Rome; Italy (virtual event)) [10.1145/3406325.3451076].

Efficient two-sided markets with limited information

Fusco, Federico
;
Lazos, Filippos;Leonardi, Stefano;Reiffenhäuser, Rebecca
2021

Abstract

A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets that maximizes social welfare must run a deficit, resulting in a necessity to relax welfare efficiency and the use of approximation mechanisms. Such mechanisms in general make extensive use of the Bayesian priors. In this work, we investigate a question of increasing theoretical and practical importance: how much prior information is required to design mechanisms with near-optimal approximations? Our first contribution is a more general impossibility result stating that no meaningful approximation is possible without any prior information, expanding the famous impossibility result of Myerson and Satterthwaite. Our second contribution is that one single sample (one number per item), arguably a minimum-possible amount of prior information, from each seller distribution is sufficient for a large class of two-sided markets. We prove matching upper and lower bounds on the best approximation that can be obtained with one single sample for subadditive buyers and additive sellers, regardless of computational considerations. Our third contribution is the design of computationally efficient blackbox reductions that turn any one-sided mechanism into a two-sided mechanism with a small loss in the approximation, while using only one single sample from each seller. On the way, our blackbox-type mechanisms deliver several interesting positive results in their own right, often beating even the state of the art that uses full prior information.
2021
ACM Symposium on Theory of Computing
Two sided markets; single sample; combinatorial auctions
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Efficient two-sided markets with limited information / Dütting, Paul; Fusco, Federico; Lazos, Filippos; Leonardi, Stefano; Reiffenhäuser, Rebecca. - (2021), pp. 1452-1465. (Intervento presentato al convegno ACM Symposium on Theory of Computing tenutosi a Rome; Italy (virtual event)) [10.1145/3406325.3451076].
File allegati a questo prodotto
File Dimensione Formato  
Dütting_Efficient_2021.pdf

accesso aperto

Note: https://doi.org/10.1145/3406325.3451076
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 913.45 kB
Formato Adobe PDF
913.45 kB Adobe PDF

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/1556941
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 8
social impact