Bilateral Trade: A Regret Minimization Perspective
This work addresses a fundamental problem in economics for designing mechanisms in bilateral trade, offering theoretical guarantees that are incremental in extending regret analysis to this domain.
The paper tackles the bilateral trade problem by framing it in a regret minimization framework over multiple rounds, with no prior knowledge of private valuations, and provides tight regret bounds for various feedback models and valuation assumptions, such as Θ(√T) for full-feedback and Θ(T^{2/3}) for realistic feedback with independent valuations.
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: - $Θ(\sqrt{T})$ for full-feedback (i.e., direct revelation mechanisms). - $Θ(T^{2/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.