Latest papers

9 papers3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Nov 6, 2026

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

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(TrΣ)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(TrΣS+TrΣB)O(\mathrm{Tr} \sqrt{Σ_S}+\mathrm{Tr} \sqrt{Σ_B}), where ΣSΣ_S and ΣBΣ_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(d)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(dlog⁡d)O(d\log d) for contextual search and of O(d6d)O(d6^d) for bilateral trade.
Nov 6, 2026

Optimal Regret for Profit Maximization in Bilateral Trade

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.
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.
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.
Jun 13, 2026

Repeated Bilateral Trade: The Quest for Fairness

We study repeated bilateral trade from a fairness perspective. At each round, a fresh seller-buyer pair arrives, and the platform posts a price before observing the traders' valuations. Trade occurs only if both agents accept the price. Rather than maximizing only the gain from trade, we consider platforms that seek balanced divisions of the generated surplus. We show that natural fairness desiderata lead to a one-parameter Rawls-to-Nash family of fair-gain objectives, obtained by aggregating the seller's and buyer's net gains through nonpositive Hölder means. Unlike the standard gain-from-trade objective and the Rawlsian fair-gain objective studied in prior work, our proposed objectives induce a new statistical structure in which expected rewards are recovered from threshold feedback through a two-dimensional singular-kernel integral identity. This leads to a nonstandard pure-exploration problem whose natural estimators are rectangular double sums with row-column dependence and singular weights. Assuming independent i.i.d. seller and buyer valuation sequences with arbitrary unknown marginals, we characterize the optimal learning rates for the whole Rawls-to-Nash family of fair-gain objectives, giving matching fixed-confidence sample-complexity and regret bounds up to polylogarithmic factors.
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.
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 CC. We design an algorithm that adaptively scales with the level of corruption, achieving an O~(T3/4)+O(Clog⁡(T))\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 O~(T3/4)\tilde{\mathcal{O}}(T^{3/4}) regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.
Mar 9, 2026

A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search

The celebrated Myerson--Satterthwaite theorem shows that in bilateral trade, no mechanism can be simultaneously fully efficient, Bayesian incentive compatible (BIC), and budget balanced (BB). This naturally raises the question of how closely the gains from trade (GFT) achievable by a BIC and BB mechanism can approximate the first-best (fully efficient) benchmark. The optimal BIC and BB mechanism is typically complex and highly distribution-dependent, making it difficult to characterize directly. Consequently, much of the literature analyzes simpler mechanisms such as the Random-Offerer (RO) mechanism and establishes constant-factor guarantees relative to the first-best GFT. An important open question concerns the worst-case performance of the RO mechanism relative to first-best (FB) efficiency. While it was originally hypothesized that the approximation ratio GFTFBGFTRO\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}} is bounded by 22, recent work provided counterexamples to this conjecture: Cai et al. proved that the ratio can be strictly larger than 22, and Babaioff et al. exhibited an explicit example with ratio approximately 2.022.02. In this work, we employ AlphaEvolve, an AI-guided evolutionary search framework, to explore the space of value distributions. We identify a new worst-case instance that yields an improved lower bound of GFTFBGFTRO≥2.0749\frac{\text{GFT}_{\text{FB}}}{\text{GFT}_{\text{RO}}} \ge \textbf{2.0749}. This establishes a new lower bound on the worst-case performance of the Random-Offerer mechanism, demonstrating a wider efficiency gap than previously known.
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 TT-exponents up to logarithmic factors, with no knowledge of the moment order p∈(1,2)p \in (1,2) or its scale σpσ_p, and -- in the nonparametric case -- none of the effective Hölder smoothness β∈(0,1]β\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 pp-th moments for some p∈(1,2)p \in (1,2), with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret O~(T(2−p)/p)\widetilde{O}(T^{(2-p)/p}) in the parametric model and O~(T1−2β(p−1)/(βp+d(p−1)))\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 TT up to logarithmic factors over the effective smoothness range β∈(0,1]β\in (0,1], interpolating between the classical nonparametric rate at p=2p{=}2 and the trivial linear rate as p→1+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 E[g(m,V,W)−g(π,V,W)]≤L∣m−π∣2\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2 -- no second moment is needed.