cs.GTNov 6, 2026

Optimal Regret for Profit Maximization in Bilateral Trade

Authors: Matteo Castiglioni, Anna Lunghi, Alberto Marchesi

Organizations: Politecnico di Milano

Abstract

Learning to profit from trade requires learning both sides of a market: what a seller is willing to accept and what a buyer is willing to pay. We study repeated bilateral trade, where an intermediary posts a purchase price to a seller and a sale price to a buyer whose valuations are drawn from an unknown joint distribution. Trade occurs only if both parties accept their respective prices, in which case the intermediary earns the difference between the two prices. The intermediary observes only whether trade occurs, without observing either valuation. We show that learning both sides of the market is no harder, in terms of regret, than learning just one. Specifically, we design an algorithm achieving regret O~(T2/3)\widetilde{\mathcal{O}}(T^{2/3}) against the best fixed pair of prices, matching, up to logarithmic factors, the classical lower bound for one-dimensional dynamic pricing. Our result shows that the classical one-dimensional regret rate survives the transition to two dimensions, raising the question of whether this absence of a curse of dimensionality extends to arbitrarily high dimensions.

Figures & tables

Explore similar work

Nov 5, 2026

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a profit-maximizing broker in a regret minimization framework. At each time step, a new seller and buyer arrive and the broker proposes a trading price to each agent. The trade happens if both agents accept, and the profit of the broker is the difference between the price received from the buyer and the one paid to the seller. At the end of each interaction, the learner only observes whether the trade occurred, and its goal is to achieve sublinear regret relative to the best fixed pair of prices in hindsight. We start by investigating the adversarial version of the problem, where buyer and seller valuations are generated by an adversary. In this setting, we construct a polynomial-time learning algorithm with a O~(T23)\tilde O(T^{\frac 23}) regret rate, which is nearly tight even if the valuations are drawn i.i.d. from independent distributions, thus matching the rate for one-sided pricing. Our adversarial algorithm combines a localized estimation procedure with an information-based minimax construction. We then consider valuations drawn i.i.d. from independent distributions satisfying the monotone-hazard-rate (MHR) property and provide a learning algorithm with nearly tight O~(T)\tilde{O}(\sqrt{T}) regret. The algorithm combines localized estimation with a stochastic convex bandit routine applied to the negative logarithm of expected profit. Finally, we complement this result by showing a separation between MHR and regular distributions, proving that the minimax regret rate in the latter setting is Θ~(T35)\tilde Θ(T^{\frac 35}). This last result contrasts with the O~(T)\tilde{O}(\sqrt{T}) regret bound that can be obtained for one-sided pricing with regular distributions.
May 12, 2026

Profit Maximization in Bilateral Trade against a Smooth Adversary

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 TT 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.
Jul 22, 2026

Breaking the T3/4T^{3/4} Barrier for Regret Minimization With Bi-Dimensional CDFs

We study regret minimization for learning CDF-related objectives of the form g(x)⋅PX∼D(X≤x),g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x), over [0,1]2[0,1]^2, where gg is a known Lipschitz function and D\mathcal{D} is an unknown distribution. At each round tt, the learner selects a point xtx_t and observes the binary feedback I(Xt≤xt)\mathbb{I}(X_t\le x_t), where Xt∼DX_t\sim\mathcal{D}. We design an algorithm achieving regret O~(T7/10)\widetilde{\mathcal{O}}(T^{7/10}), improving over the previous best-known bound of O~(T3/4)\widetilde{\mathcal{O}}(T^{3/4}) and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the Ω(T2/3)Ω(T^{2/3}) lower bound. As an application, our techniques yield the same O~(T7/10)\widetilde{\mathcal{O}}(T^{7/10}) regret bound for profit maximization in repeated bilateral trade with fixed prices.