CS Paper Radar

Support-Dependent Regret Rates for Profit Maximization in Multilateral Trade

Francesco Bacchiocchi, Matteo Castiglioni, Anna Lunghi, Alberto Marchesi

cs.GT ·submitted 2026-10-06 16:12 UTC · v1

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.

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

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

cs.GT cs.DScs.LG ·2026-11-05 ·Johannes Brüstle, Simone Di Gregorio, Federico Fusco, Stefano Leonardi
similarity 0.73
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.

0.15

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

Approximately Efficient Multidimensional Bilateral Trade

cs.GT ·2026-09-02 ·Aviad Rubinstein, Xizhi Tan, Zixin Zhou
top venuehighly cited similarity 0.67
Abstract · To appear in the 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)

A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets. Because achieving the full GFT is generally impossible, the literature has focused on constant-factor approximations---a notoriously difficult problem even in simple settings. It was only recently that a breakthrough result by [DMSW22] achieved a constant-factor approximation for single-item bilateral trade. The same guarantee was later extended to single-dimensional matching markets with general downward-closed constraints [BRTW26]. Most existing results, however, are limited to single-dimensional agents. A notable multi-dimensional exception is [CGMZ21]. They considered a market with one constrained-additive buyer and $n$ single-dimensional sellers and provided a mechanism that achieves a $\log^2(n)$ approximation to the second-best GFT, i.e., the maximum expected GFT theoretically achievable by any mechanism satisfying Bayesian Incentive Compatibility (BIC), Interim Individual Rationality (IIR), and ex-ante Weak Budget Balance (WBB). In this paper, we study multi-dimensional bilateral trade problem where both sides of the market are multi-dimensional. We start with one buyer with XOS valuation and one seller with an additive cost function. We then generalize to a market with $n$ XOS buyers and one additive seller. Assuming independent items' values and costs, in both settings we propose simple mechanisms that are BIC, IIR, and ex-ante WBB, while achieving a constant fraction of the optimal (first-best) expected GFT.

0.47

Welfare Approximation in Multilateral Trade

cs.GT ·2026-08-11 ·Tomer Ezra, Aadityan Ganesh, Aviad Rubinstein
theory similarity 0.65
Abstract

We introduce the study of \emph{multilateral trade}: a mechanism-design problem in which a single potential trade involves $k$ agents and can be executed only if all $k$ agents agree to participate. The classical case $k=2$ is the well-studied bilateral trade problem, where a seller and a buyer with private values must decide whether to trade an item initially held by the seller. Existing extensions of bilateral trade have largely focused on markets with many buyers and many sellers, but where each realized transaction is still bilateral, requiring agreement only between the matched buyer and seller. Our formulation captures settings in which the trade itself requires joint participation, coupling the agents' incentives and creating new challenges. We study welfare approximation in this setting under incentive compatibility, individual rationality, and budget balance. We give a DSIC mechanism with approximation ratio $O(k^2)$, and a BIC mechanism with approximation ratio $\widetilde O(k^{3/2})$. We prove matching lower bounds up to polylogarithmic factors. Finally, we extend the model to an $\ell$-out-of-$k$ partial-agreement setting, where the trade may occur once at least $\ell$ agents participate. In this relaxed model, the welfare guarantees improve smoothly as $k-\ell$, the number of agents whose participation is not required, grows, and we obtain matching upper and lower bounds up to polylogarithmic factors.

0.04

Second-Best Trade Is Half Efficient in Multidimensional Markets

cs.GT ·2026-11-10 ·Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu
theory similarity 0.64
Abstract

We prove that at least half of the first-best gains from trade can always be achieved in multidimensional two-sided markets with additive values and costs and arbitrary downward-closed feasibility constraints. The guarantee is achieved by a mechanism satisfying Bayesian incentive compatibility, interim individual rationality, and strong budget balance, and is tight already in single-item bilateral trade. Types are independent across agents, while the coordinates of each agent's type may be arbitrarily correlated. Feasibility constraints may couple trades across items and agents. This extends the known tight one-half guarantee for single-item bilateral trade. Our proof develops a new application of the Cai--Devanur--Weinberg duality framework. We show that the objective of every feasible dual is at least half of the first best. Strong duality then yields the guarantee without characterizing an optimal mechanism or dual. The key observation is that every feasible dual induces continuous-time Markov chains that, when stopped by exponential clocks, recover true types as expectations of virtual types. The dual constraints control the rate at which these chains change the prior distributions. We establish our bound by combining this control with a coupling of the agents' clocks.

0.05

From Bilateral Trade to Matching Markets: Sharp Gains from Trade

cs.GT ·2026-09-25 ·Zhengyang Liu, Ying Qin, Zihe Wang
similarity 0.63
Abstract

We study gains from trade in matching markets with independent private values and costs, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. A second-best guarantee for finite bilateral trade extends without loss to matching markets with independent Borel priors, arbitrary downward-closed feasibility, and finite expected first-best gains. For bounded buyers with monotone hazard rates and arbitrary bounded sellers, we determine the exact worst-case ratio of second-best to first-best gains, approximately $0.72490721$. For binary buyers and sellers with at most $m$ types, we determine the exact ratio for every $m$, including $8/9$ when $m=2$ and a limit of $4/5$ as $m$ grows. Both families of bounds are tight already in bilateral trade.

0.40

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