Bilateral trade is a fundamental economic scenario comprising a strategically acting buyer and seller (holding an item), each holding valuations for the item, drawn from publicly known distributions. It was recently shown that the only mechanisms that are simultaneously dominant strategy incentive compatible, strongly budget balanced, and ex-post individually rational, are fixed price mechanisms, i.e., mechanisms that are parametrised by a price p, and trade occurs if and only if the valuation of the buyer is at least p and the valuation of the seller is at most p. The gain from trade (GFT) is the increase in welfare that results from applying a mechanism. We study the GFT achievable by fixed price mechanisms. We explore this question for both the bilateral trade setting and a double auction setting where there are multiple i.i.d. unit demand buyers and sellers. We first identify a fixed price mechanism that achieves a GFT of at least 2 / r times the optimum, where r is the probability that the seller’s valuation does not exceed that of the buyer’s valuation. This extends a previous result by McAfee. Subsequently, we improve this approximation factor in an asymptotic sense, by showing that a more sophisticated rule for setting the fixed price results in a GFT within a factor (log(1/)) of the optimum. This is asymptotically the best approximation factor possible. For the double auction setting, we present a fixed price mechanism that achieves for all >0 a gain from trade of at least (1−) times the optimum with probability 1−2/#2/2 , where # is the expected number of trades of the mechanism. This can be interpreted as a “large market” result: Full efficiency is achieved in the limit, as the market gets thicker.

Fixed price approximability of the optimal gain from trade / Colini-Baldeschi, Riccardo; Goldberg, Paul; de Keijzer, Bart; Leonardi, Stefano; Turchetta, Stefano. - 10660:(2017), pp. 146-160. (Intervento presentato al convegno 13th International Conference on Web and Internet Economics, WINE 2017 tenutosi a Bangalore; India nel 2017) [10.1007/978-3-319-71924-5_11].

Fixed price approximability of the optimal gain from trade

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

Abstract

Bilateral trade is a fundamental economic scenario comprising a strategically acting buyer and seller (holding an item), each holding valuations for the item, drawn from publicly known distributions. It was recently shown that the only mechanisms that are simultaneously dominant strategy incentive compatible, strongly budget balanced, and ex-post individually rational, are fixed price mechanisms, i.e., mechanisms that are parametrised by a price p, and trade occurs if and only if the valuation of the buyer is at least p and the valuation of the seller is at most p. The gain from trade (GFT) is the increase in welfare that results from applying a mechanism. We study the GFT achievable by fixed price mechanisms. We explore this question for both the bilateral trade setting and a double auction setting where there are multiple i.i.d. unit demand buyers and sellers. We first identify a fixed price mechanism that achieves a GFT of at least 2 / r times the optimum, where r is the probability that the seller’s valuation does not exceed that of the buyer’s valuation. This extends a previous result by McAfee. Subsequently, we improve this approximation factor in an asymptotic sense, by showing that a more sophisticated rule for setting the fixed price results in a GFT within a factor (log(1/)) of the optimum. This is asymptotically the best approximation factor possible. For the double auction setting, we present a fixed price mechanism that achieves for all >0 a gain from trade of at least (1−) times the optimum with probability 1−2/#2/2 , where # is the expected number of trades of the mechanism. This can be interpreted as a “large market” result: Full efficiency is achieved in the limit, as the market gets thicker.
2017
13th International Conference on Web and Internet Economics, WINE 2017
Theoretical Computer Science; Computer Science (all)
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Fixed price approximability of the optimal gain from trade / Colini-Baldeschi, Riccardo; Goldberg, Paul; de Keijzer, Bart; Leonardi, Stefano; Turchetta, Stefano. - 10660:(2017), pp. 146-160. (Intervento presentato al convegno 13th International Conference on Web and Internet Economics, WINE 2017 tenutosi a Bangalore; India nel 2017) [10.1007/978-3-319-71924-5_11].
File allegati a questo prodotto
File Dimensione Formato  
Colini-Baldeschi_Postprint_Fixed-Price-Approximability_2017.pdf

accesso aperto

Note: https://link.springer.com/chapter/10.1007/978-3-319-71924-5_11
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 331.97 kB
Formato Adobe PDF
331.97 kB Adobe PDF
Colini-Baldeschi_Fixed-Price-Approximability_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 226.44 kB
Formato Adobe PDF
226.44 kB 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/1073143
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? ND
social impact