CS Paper Radar

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.GT cs.DScs.LG ·submitted 2026-11-05 15:30 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Regret for Profit Maximization in Bilateral Trade

cs.GT cs.LG ·2026-11-06 ·Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
theory similarity 0.87
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 $\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.

0.13

Optimal Regret for Online Market Making with Limit Order Book

cs.GT cs.LG ·2026-10-07 ·Maria Elena Vischi, Francesco Emanuele Stradi, Alberto Marchesi
hot direction similarity 0.74
Abstract

We study online learning in market making, where, at each round, a market maker posts bid and ask prices before observing the market price and the private valuation of an incoming trader. In this setting, Maran et al. 2026 introduce a feedback model motivated by limit order books, in which the trader's valuation is revealed only if no transaction occurs. Assuming that trader valuations are drawn i.i.d. from an unknown distribution while market prices are chosen adversarially, they establish an expected regret bound of $\widetilde{\mathcal{O}}(T^{2/3})$. In this work, we improve upon this guarantee by establishing a high-probability regret bound of $\widetilde{\mathcal{O}}(\sqrt{T})$. As a warm-up, we first consider the full-feedback setting. We introduce a discretization of the bid-ask space based on two coupled grids and combine it with Hedge to achieve the desired regret rate. Building on these ideas, we then address the substantially weaker feedback induced by a limit order book and develop an algorithm that achieves the same guarantee. Finally, we investigate the limits of learnability in fully adversarial environments, where the valuations may vary arbitrarily as well. Perhaps surprisingly, we show that when both market prices and trader valuations are chosen adversarially, sublinear regret is impossible even under full feedback, thereby motivating our stochastic assumption on the valuations.

0.28

Support-Dependent Regret Rates for Profit Maximization in Multilateral Trade

cs.GT ·2026-10-06 ·Francesco Bacchiocchi, Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
similarity 0.73
Abstract

We study online profit maximization in multilateral trade, a setting that generalizes both dynamic pricing and bilateral trade. At each round, an intermediary posts prices to buyers and offers payments to sellers; trade occurs only if every agent accepts. We consider valuations drawn from an unknown joint distribution, allowing arbitrary correlation across agents, under the assumption that each agent's marginal valuation distribution has unknown support of size at most $K$. For constant dimension $d$, we design an algorithm with regret $\widetilde O(\sqrt{K^dT})$. This extends optimal support-dependent guarantees for one-dimensional dynamic pricing to the multidimensional setting of multilateral trade. At the core of our approach is a normalized zooming procedure that adapts to the local probability of trade, avoiding the excessive refinement of nearly flat regions that can arise with standard zooming.

0.14

Contextual Search and Bilateral Trade with a Trace-Square-Root Potential

cs.GT cs.LG ·2026-11-06 ·Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme +1 more
similarity 0.71
Abstract

We present a unified potential method for contextual search and bilateral trade with one-bit feedback and obtain order-tight algorithms for both problems. Our framework starts from a Bayesian perspective in which the unknown target (for contextual search) and the unknown pair of valuations (for bilateral trade) are sampled from a known prior distribution. In that model, the decision maker bases its prediction on the posterior distribution, obtained by conditioning on feedback received in previous rounds. For Bayesian contextual search, we present an algorithm with a total loss bounded by $O(\mathrm{Tr} \sqrt Σ)$, where $Σ$ is the covariance matrix of the target's prior; and for contextual bilateral trade, our algorithm's regret is bounded by $O(\mathrm{Tr} \sqrt{Σ_S}+\mathrm{Tr} \sqrt{Σ_B})$, where $Σ_S$ and $Σ_B$ are the covariance matrices of the seller's and buyer's valuations. We then use ideas from this Bayesian setting and adapt a ``dual'' of this trace-square-root potential to the classical worst-case setting, where the target and valuations are chosen adversarially from the unit Euclidean ball. For both contextual search and bilateral trade, we obtain tight $O(\sqrt d)$-regret algorithms. These results match the existing lower bounds up to a constant factor and improve on the previous guarantees of $O(d\log d)$ for contextual search and of $O(d6^d)$ for bilateral trade.

0.11

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

cs.LG stat.ML ·2026-09-11 ·Mengxiao Zhang
similarity 0.68
Abstract

We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$.

0.17

Regret, equilibrium, and learning in games: A guided tour

cs.GT cs.LGmath.OC ·2026-08-10 ·Panayotis Mertikopoulos
publishedtheory similarity 0.68
Abstract · 44 pages, 3 figures; to appear as a chapter in "Equilibria in Games: Existence, Selection, and Dynamics", edited by Sylvain Sorin and Bernha…

This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

0.25

Optimal Online Learning in Bilateral Trade Through Interest

cs.GT ·2026-11-01 ·Mengfan Ma, Haoyu Song, Yiran Tong
similarity 0.68
Abstract · 52 pages, 5 figures

We consider online learning in bilateral trade on platforms such as Uber, Airbnb, and eBay. In each round, a platform posts a payment to a seller and a price to a buyer, both with private valuations, and observes only whether trade occurs. Its objective is to maximize cumulative gains-from-trade, the sum of the differences between buyers' and sellers' valuations across completed trades. We measure the platform's performance by its regret against the best fixed common price. Financial self-sufficiency motivates global budget balance (Bernasconi et al., 2024), which allows profits from some trades to subsidize others, provided that the final balance is nonnegative. Such financial planning should also account for the time value of money: profits earned earlier can accumulate interest, providing additional funds for future subsidies. Motivated by this observation, we introduce global budget balance with interest, under which a platform starting with no funds can use both trading profits and accrued interest to finance subsidies. For a horizon of $T$ rounds and a fixed exponent $θ\ge0$, we consider the per-round interest rate $r_T = T^{-θ}$. We study two classic valuation models, adversarial and correlated i.i.d., and obtain tight bounds on regret against the best fixed common price in both. As the interest rate grows, optimal regret in each model drops from $\tildeΘ(T^{3/4})$ to $\tildeΘ(T^{5/7})$. The intermediate rates differ: $\tildeΘ(T^{3θ/4})$ for adversarial valuations when $20/21 < θ< 1$, and $\tildeΘ(T^{(2θ+3)/7})$ for correlated i.i.d. valuations when $1 < θ< 9/8$. Finally, as an extension, we study $α$-regret, with approximation factor $α\ge1$, for adversarial valuations against the best feasible distribution over price pairs, and show that the optimal competitive ratio rises from 2 to 3 as interest strengthens.

0.36

Learning to Price with Persuasion

cs.GT cs.LGecon.TH ·2026-08-17 ·Maria-Florina Balcan, Tejas Pagare, Karan Singh
similarity 0.67
Abstract · 29 Pages, 1 Table

Motivated by modern marketplaces, where the platform or the seller routinely gathers detailed user profiles, we study a novel learning theoretic model that simultaneously involves information and mechanism design. Specifically, we consider the economic setting recently introduced by Bergemann et al. (2022), where in addition to the menu of quality-price pairs, the seller offers information on the value of the match between product quality and buyer's taste via a signaling scheme. We relax the assumption that the seller knows the buyers' belief about the distribution of tastes and study the sample requirements of designing a revenue maximizing scheme. We consider both the batch setting where we have access to data from a set of i.i.d. buyers and an online demand query model where we observe the buyers' behaviors to seller's schemes. Despite the apparent non-convexity of the problem, we also give the first FPTAS to compute a scheme that maximizes the revenue within an arbitrarily small additive loss, which was left open by Bergemann et al. (2022). Overall, this brings a new learning perspective in asymmetric economic settings where buyers and sellers know different types of information.

0.17