Regret in adversarial contextual bilateral trade

A broker posts one price to a seller and a buyer. Each round supplies a context, and each party’s private valuation is a linear function of that context. The broker learns only whether both parties accept. How much gain from trade can the broker lose compared with knowing both valuations in every round?

Why it matters and what counts as progress

Why it matters: A single accept-or-reject bit hides which party set the binding constraint. The regret bound measures the cost of learning from that limited feedback.

What counts as progress: Find a strategy with a smaller worst-case regret bound or prove that no strategy can do better. Keep the valuation model, feedback and comparator fixed when comparing rates.

How the problem developed

  1. February 2026 · Initial bounds [2]

    Romain Cosson and colleagues Established the contextual model and gave a horizon-independent upper bound on gain-from-trade regret.

  2. 6 Nov 2026 · Sharp regret order [1]

    Romain Cosson and colleagues with GPT-6 Astra Proved that expected regret of order the square root of dimension is achievable with one-bit feedback.

AI contribution

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

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

For fixed buyer and seller parameter vectors in the unit Euclidean ball and adaptively chosen contexts of norm at most 1, the paper gives a randomised one-price algorithm whose expected cumulative gain-from-trade regret is O(d)O(\sqrt d) in dimension d. It uses only the trade bit and needs no prior or time horizon.

AI involvementAI-centered
ImportanceNotable
Technical verificationReported
Human understandingExplained
Paper date:

Sources

  1. Cosson and colleagues’ trace-square-root potential
  2. Cosson and colleagues, Contextual Online Bilateral Trade
Publication history