Profit Maximization in Bilateral Trade against a Smooth Adversary

Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn · 2026

Read Profit Maximization in Bilateral Trade against a Smooth Adversary by Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12664.txt.

Introduction

Di Gregorio and three colleagues study profit maximisation for a broker in bilateral trade. A broker intermediates between a strategic seller and buyer who wish to trade a good. Valuations come from a smooth adversary in an online learning setting. They devise an algorithm with regret growing like the square root of the horizon, up to logarithmic factors. That rate is tight in the horizon and matches the stochastic independent-case minimax rate, while standing apart from fully adversarial settings where sublinear regret is impossible.

Catalog record

CREATORSimone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70956
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.12664

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Profit Maximization in Bilateral Trade against a Smooth Adversary Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn Abstract Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents’ valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a O ~ ​ ( T ) \tilde{O}(\sqrt{T}) regret bound, which is tight in the time horizon T T up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker’s action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight O ~ ​ ( T ) \tilde{O}(\sqrt{T}) regret bound for a related mechanism design model: the joint ads problem. 1 Introduction In bilateral trade, a broker intermediates between two agents—a seller and a buyer—who are interested in trading a good ( 46 ; 34 ) . Both agents are characterized by a private valuation for the item, and their goal is to maximize their own utility. The broker, on the other hand, aims at maximizing some economic metric, while ensuring that (i) agents report truthfully their valuations ( dominant-strategy incentive compatibility ) and (ii) the utility for participating in the mechanism of each agent is non-negative ( individual rationality ). In this paper, we focus on profit-maximization , a canonical objective in economics which naturally arises in the applications (e.g., all e-commerce platforms that connect sellers to buyers). In particular, we investigate profit maximization in bilateral trade through the lens of online learning, with the goal of designing an algorithm that minimizes the regret with respect to the best mechanism in hindsight. For this problem, 21 provides two surprising results: while the best mechanism can be learned very quickly in the stochastic setting where the agents valuations are drawn i.i.d. from an unknown but fixed distribution, no algorithm can achieve sublinear regret in the standard adversarial setting. This leaves open the natural question of whether it is possible to perform learning beyond the stationary i.i.d. setting. Following a consolidated approach rooted in beyond-worst-case-analysis ( 41 ) , we investigate the learnability of the problem against the \sigma -smooth adversary. Such an adversary can choose different distributions over valuations at different time steps, but is constrained to distributions that are “not too peaked” (see Definition 2 ). A characterizing feature of our learning task is the complexity of the broker action space. A mechanism for bilateral trade is specified by two functions—an allocation and a payment rule—mapping bids to allocation and payments. Standard mechanism design arguments (see Appendix B.1 ) allow for a simple geometric characterization of the generic M\in\mathcal{M} . Its allocation rule corresponds to a subdivision of the bids space into two regions: one in which the trade happens and one where this is not the case. This partition has to be closed in the “up-left” direction, so that increasing the buyer’s bid or decreasing the seller’s does not decrease the likelihood of observing a trade. The payments are then given by suitable projection of the valuation pair on the boundary of the allocation region, à la 35 . While this characterization collapses the learning problem to tracking the best allocation region, the mechanism space is still non-parametric! This separates us from the majority of the online learning literature on mechanism design, where the learning objective is intrinsically parametric, e.g., the best price(s) ( 30 ; 16 ; 17 ) , the best reserve price(s) ( 20 ; 40 ) , or the best bid ( 24 ; 18 ) . 1.1 Our Result Our first contribution is the design of the learning algorithm Hier-Mech , which enjoys a regret rate of O(\nicefrac{{1}}{{\sigma}}\cdot\sqrt{T}\log T) for profit maximization in bilateral trade against a \sigma -smooth adversary ( Theorem 1 ). This is, up to lower order terms, the same bound achievable in the i.i.d. setting, while no sublinear algorithm can exist in the (non-smooth) adversarial setting ( 21 ) . We then formally prove a reduction from the joint ads problem to profit-maximization in bilateral trade ( Theorem 2 ). Joint ads is a mechanism design setting where two agents collaborate to purchase a non-excludable good, and has been studied in the online learning setting in 1 . The reduction implies a lower bound of \Omega(\sqrt{T}) on the regret for bilateral trade ( Corollary 1 ), matching the performance of Hier-Mech . Therefore, we characterize the time-horizon dependence of the minimax regret rate against the \sigma -smooth adversary, up to poly-log terms. This settles an open question in 21 . Finally, the reduction allows us to adapt Hier-Mech to the joint ads setting, maintaining the same (tight) regret rate. This improves on the previous regret upper bound of O(\nicefrac{{1}}{{\sigma}}\cdot T^{\nicefrac{{2}}{{3}}}) , settling an open question in 1 (see Corollary 2 ). In combination, our results thus show that, from an information-theoretic perspective, the \sigma -smooth adversary is “as easy as” the i.i.d. setting. Interestingly, the \sqrt{T} rate algorithms for these two data-generation models are obtained with very different techniques and arguments (see Section 1.2 for more details). The strong statistical learning guarantees for the smooth adversarial setting reinforce the effectiveness of smoothness as a meaningful way of overcoming adversarial impossibility results in economic problems ( 16 ; 17 ; 18 ; 22 ) . A remaining discrepancy is that the running time of Hier-Mech scales as \exp(\sqrt{T}) , while the i.i.d. setting admits a poly-time algorithm. Closing this computational gap and tightening the regret dependency on the smoothness parameter \sigma remain the primary open questions in this space. 1.2 Technical Challenges The main challenge of profit-maximization in bilateral trade is the non-parametric nature of the action space, and the special “projection-like” nature of the payments, which induce the profit function. The Adversary is Non-Stationary. In the stochastic i.i.d. setting, 21 address the learning problem by proposing a modified version of follow-the-leader, arguing via probabilistic chaining ( 43 ) that (i) a data and distribution dependent finite family \mathcal{M}^{\prime} of mechanisms has its profit estimated very quickly and (ii) all mechanisms outside \mathcal{M}^{\prime} can be ruled out quickly as candidate optimum. Such approach, however, is doomed to fail in any non-stationary setting, like the one we are studying. Indeed, for any mechanism M , past profits can be completely uncorrelated with future ones, so that one can never “rule out” mechanisms which are suboptimal up to that point. Exploiting Lipschitzness. Smoothness makes the expected-profit function Lipschitz in the choice of the mechanism (for a proper distance). Following the standard approach in the Lipschitz bandits

Read the complete text