A Regret Analysis of Bilateral Trade
This work addresses the challenge of designing mechanisms for bilateral trade under no prior knowledge, providing foundational regret bounds that could impact algorithmic economics and mechanism design.
The paper tackles the bilateral trade problem by analyzing it in a regret minimization framework over multiple rounds without prior knowledge of private valuations, proving regret bounds for fixed-price mechanisms under different feedback models and valuation assumptions, such as ϕ(√T) for full-feedback and ϕ(T^{2/3}) for realistic feedback with independent bounded densities.
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. Despite the simplicity of this problem, a classical result by Myerson and Satterthwaite (1983) affirms the impossibility of designing a mechanism which is simultaneously efficient, incentive compatible, individually rational, and budget balanced. This impossibility result fostered an intense investigation of meaningful trade-offs between these desired properties. Much work has focused on approximately efficient fixed-price mechanisms, i.e., Blumrosen and Dobzinski (2014; 2016), Colini-Baldeschi et al. (2016), which have been shown to fully characterize strong budget balanced and ex-post individually rational direct revelation mechanisms. All these results, however, either assume some knowledge on the priors of the seller/buyer valuations, or a black box access to some samples of the distributions, as in D{ü}tting et al. (2021). In this paper, we cast for the first time the bilateral trade problem in a regret minimization framework over rounds of seller/buyer interactions, with no prior knowledge on the private seller/buyer valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different models of feedback and private valuations, using as benchmark the best fixed price in hindsight. More precisely, we prove the following bounds on the regret: $\bullet$ $\widetildeΘ(\sqrt{T})$ for full-feedback (i.e., direct revelation mechanisms); $\bullet$ $\widetildeΘ(T^{2/3})$ for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities; $\bullet$ $Θ(T)$ for realistic feedback and seller/buyer valuations with bounded densities; $\bullet$ $Θ(T)$ for realistic feedback and independent seller/buyer valuations; $\bullet$ $Θ(T)$ for the adversarial setting.