cs.GTNov 6, 2026

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

Authors: Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo

Organizations: Computer Science Department, New York University, NYC, United States. · Department of Computer, Control, and Management Engineering, Sapienza University, Rome, Italy. · Google Research, NYC, United States. · EPFL, Lausanne, Switzerland.

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

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

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

    Nov 5, 2026Johannes Brüstle, Simone Di Gregorio, Federico Fusco +1Bilateral TradeRegret Minimization

  2. Contextual Procurement Auctions with Bandit Learning

    Jul 7, 2026Yiling Chen, Shi Feng, Sadie ZhaoMechanism DesignRegret Minimization