A Regret Analysis of Bilateral Trade

A Google TechTalk, presented by Federico Fusco, 2021/09/21 ABSTRACT: An Algorithms TechTalk. 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. 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 T 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. Based on a joint work with Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni and Stefano Leonardi appeared at EC 2021. arXiv: https://arxiv.org/pdf/2102.08754.pdf About the speaker: Federico is a third year PhD student at Sapienza University of Rome under the supervision of Stefano Leonardi. His main research interests are algorithmic game theory and mechanism design. His work also focuses on submodular optimization and online learning.