Bilateral Trade: A Regret Minimization Perspective

DOI10.1287/MOOR.2023.1351arXiv2109.12974OpenAlexW3203261540MaRDI QIDQ6189901FDOQ6189901

Authors: Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi 

Publication date: 5 March 2024

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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: - $Theta(sqrtT)$ for full-feedback (i.e., direct revelation mechanisms). - $Theta(T^{2/3})$ for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities. - $Theta(T)$ for realistic feedback and seller/buyer valuations with bounded densities. - $Theta(T)$ for realistic feedback and independent seller/buyer valuations. - $Theta(T)$ for the adversarial setting.

Full work available at URL: https://arxiv.org/abs/2109.12974

zbMATH Keywords

online learningtwo-sided marketspartial monitoringposted-price mechanisms

Mathematics Subject Classification ID

Computational learning theory (68Q32) Rationality and learning in game theory (91A26) Mechanism design theory (91B03)

Cited In (1)

• An \(\alpha \)-regret analysis of adversarial bilateral trade

This page was built for publication: Bilateral Trade: A Regret Minimization Perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6189901)