Bilateral trade: a regret minimization perspective

Nicolo Cesa-Bianchi, Cesari Tommaso, Roberto Colomboni, Federico Fusco and Stefano Leonardi
Additional contact information
Nicolo Cesa-Bianchi: UNIMI - Università degli Studi di Milano = University of Milan
Cesari Tommaso: TSE-R - Toulouse School of Economics - UT Capitole - Université Toulouse Capitole - UT - Université de Toulouse - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement
Roberto Colomboni: UNIMI - Università degli Studi di Milano = University of Milan, IIT - Italian Institute of Technology = Istituto Italiano di Tecnologia
Federico Fusco: UNIROMA - Università degli Studi di Roma "La Sapienza" = Sapienza University [Rome]
Stefano Leonardi: UNIROMA - Università degli Studi di Roma "La Sapienza" = Sapienza University [Rome]

Post-Print from HAL

Abstract: Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. In this paper, we cast the bilateral trade problem in a regret minimization framework over T rounds of seller/buyer interactions, with no prior knowledge on their private valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different feedback models and private valuations, using as a benchmark the best fixed price in hindsight. More precisely, we prove the following tight bounds on the regret: Θ(T−−√) for full-feedback (i.e., direct revelation mechanisms). Θ(T2/3) for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities. Θ(T) for realistic feedback and seller/buyer valuations with bounded densities. Θ(T) for realistic feedback and independent seller/buyer valuations. Θ(T) for the adversarial setting.

Keywords: Two-sided markets; Online learning; Posted-price mechanisms; Partial monitoring (search for similar items in EconPapers)
Date: 2024-02-17
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Published in Mathematics of Operations Research, 2024, 49 (1), pp.171-203. ⟨10.1287/moor.2023.1351⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-04475574

DOI: 10.1287/moor.2023.1351

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().