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

Johannes Brüstle; Simone Di Gregorio; Federico Fusco; Stefano Leonardi

cs.GTNov 5, 2026

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

Authors: Johannes Brüstle, Simone Di Gregorio, Federico Fusco, Stefano Leonardi

Organizations: Department of Computer, Control, & Management Engineering, Sapienza University of Rome, Rome, Italy.

Abstract

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 $\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 $\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 $\tilde Θ(T^{\frac 35})$ . This last result contrasts with the $\tilde{O}(\sqrt{T})$ regret bound that can be obtained for one-sided pricing with regular distributions.

Figures & tables

Setting	Distribution assumptions	Minimax regret
Adversarial	—	$\widetilde{O}(T^{\nicefrac{{2}}{{3}}})$ – Thm. 4.1
Stochastic Setting	Generic
	Independent	$\Omega(T^{\nicefrac{{2}}{{3}}})$ – [ 30 ]
	Independent & Regular	$\widetilde{\Theta}(T^{\nicefrac{{3}}{{5}}})$ – Thms. 6.1 & 7.1
	Independent & MHR	$\widetilde{\Theta}(\sqrt{T})$ – Thms. 5.1 & [ 34 ]

Table 1: Minimax regret rates for profit maximization with posted prices in bilateral trade. Entries with the same color share the same minimax rate. The adversarial positive result applies to all other settings, while the lower bound for i.i.d. distributions with independent marginals also applies to the generic stochastic setting and the adversarial one.

Panel of Figure 1 — Figure 1: A possible sequence of seller and buyer blocks involved in the estimation of the probability function of trade for two specific targets in $\mathscr{A}$ , according to Equation 2 .

Panel of Figure 2 — Figure 2: Visualization of Sierpinski sampling. Left: sampled pairs for $K=16$ ; color and shape identify the first sampling node in the interval tree (middle), and gray pairs are sampled later. Right: the first split separating $i$ and $j$ supplies three sampled pairs that determine $P(\nicefrac{{i}}{{K}},\nicefrac{{j}}{{K}})$ by independence. Here $(i,j)=(3,13)$ and the splitting midpoint is $\ell=8$ .

Panel of Figure 3 — Figure 3: Expected profit $h^{j}(q)$ at prices $(q/2,q)$ for the lower-bound construction. The baseline $h^{0}$ has a plateau of maximizers. Two alternatives, $h^{1}$ and $h^{3}$ (here $K=4$ ), coincide with $h^{0}$ outside $I_{1}$ and $I_{3}$ , respectively.

Panel of Figure 4 — Figure 4: The decomposition considered in Step 2 of the proof of Lemma 4.8 : the area filled with squares is the region of the space when no trade happens under any of the four posted prices; each area where some trade happens and thus considered in the decomposition is filled with a distinct pattern.

\widehat{P}(i/K,j/K)=\frac{\overline{P}_{ik}\overline{P}_{kj}}{\max\{\overline{P}_{ik},\overline{P}_{kj},\overline{P}_{kk}\}},\hskip 18.49988pt0/0=0,

(48)

Algorithm 7 Initialize regular

Panel of Figure 5 — Figure 5: One cycle for candidate $i$ . With $z_{i},\rho_{i}$ fixed, refinement optimizes $1/r_{\rho_{i}\lambda_{z_{i}}}$ and returns the selected run’s average query $y_{i}$ and estimate $\widehat{r}_{i}$ . If $i$ survives comparison with the other candidates, $y_{i}$ becomes its reference for the next phase. The region, root, and intended parameter remain fixed.

Regret Minimization

Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.

See all 122 papers

Profit Maximization in Bilateral Trade against a Smooth Adversary
May 12, 2026Simone Di Gregorio, Paul Dütting, Federico Fusco +1Mechanism Design Minimax Regret
Department of Computer, Control and Management Engineering Sapienza University of Rome · Google Research · Department of Computer Science Aarhus University
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
Mar 6, 2026Hangyi ZhaoMinimax Regret Regret Minimization
Regret Minimization in Bilateral Trade With Perturbed Markets
May 11, 2026Anna Lunghi, Matteo Castiglioni, Alberto MarchesiMechanism Design Automated Negotiation
Politecnico di Milano

May 12, 2026J/K move · Enter open · S save

Profit Maximization in Bilateral Trade against a Smooth Adversary

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

Department of Computer, Control and Management Engineering Sapienza University of Rome · Google Research · Department of Computer Science Aarhus University

Mechanism Design Minimax Regret Regret Minimization

Open paper AskPDF arXiv

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

\tilde{O}(\sqrt{T})

regret bound, which is tight in the time horizon

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

\tilde{O}(\sqrt{T})

regret bound for a related mechanism design model: the joint ads problem.

Abstract

Regret Minimization

Explore similar work

Profit Maximization in Bilateral Trade against a Smooth Adversary

Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound

Regret Minimization in Bilateral Trade With Perturbed Markets