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

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

\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.

Simone Di Gregorio, Paul Dütting, Federico Fusco +1

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

Ask PDF

Mar 6, 2026

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

In contextual bilateral trade under full feedback, the posted price does not affect which valuations are observed. We show that in this model such action-independent feedback removes the polynomial adaptation penalty familiar from heavy-tailed bandits: fully parameter-free algorithms attain the oracle minimax

T

-exponents up to logarithmic factors, with no knowledge of the moment order

p \in (1,2)

or its scale

σ_p

, and -- in the nonparametric case -- none of the effective Hölder smoothness

β\in (0,1]

. The statistic that makes model selection possible is a paired squared-loss difference, whose noise-square term cancels exactly, leaving noise damped by the candidate gap. The resulting bilateral-trade regret rates are new. Trader valuations have bounded conditional densities and heavy tails -- finite

p

-th moments for some

p \in (1,2)

, with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret

\widetilde{O}(T^{(2-p)/p})

in the parametric model and

\widetilde{O}(T^{1-2β(p-1)/(βp + d(p-1))})

when the market value function is

β

-Hölder, with matching

Ω(\cdot)

lower bounds -- under a mild nondegeneracy condition -- via Assouad's method and a fixed-support mixture construction -- characterizing the minimax rate in

T

up to logarithmic factors over the effective smoothness range

β\in (0,1]

, interpolating between the classical nonparametric rate at

p{=}2

and the trivial linear rate as

p \to 1^+

. The enabling structural step extends the self-bounding property of Bachoc et al. (ICML 2025) from bounded to real-valued valuations: within our conditionally independent, conditionally centered noise model, bounded conditional densities and finite first moments suffice for the expected regret of any price

π

to satisfy

\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2

-- no second moment is needed.

Hangyi Zhao

Minimax Regret Regret Minimization Contextual Bandits

Ask PDF

May 11, 2026

Regret Minimization in Bilateral Trade With Perturbed Markets

We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in purely adversarial and stochastic settings, these environments exhibit a sharp dichotomy: adversarial environments allow for no-regret learning against the best fixed-price mechanism, whereas stochastic environments allow for no-regret learning against the best distribution over prices that is budget balanced in expectation. This gap is significant, as policies balanced in expectation can increase the GFT by a multiplicative factor of two. In this work, we bridge these extremes by studying perturbed markets, where an underlying stochastic distribution is subject to an adversarial corruption

C

. We design an algorithm that adaptively scales with the level of corruption, achieving an

\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))

regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case

\tilde{\mathcal{O}}(T^{3/4})

regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.

Anna Lunghi, Matteo Castiglioni, Alberto Marchesi

Politecnico di Milano

Mechanism Design Automated Negotiation Regret Minimization

Ask PDF

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