New algorithm achieves optimal regret in bilateral trade against smooth adversaries

A team of computer scientists has tackled a fundamental economic problem: how a profit-maximizing broker can intermediate between a seller and a buyer when valuations are generated adversarially but smoothly. The paper, published on arXiv, introduces a learning algorithm that guarantees a regret bound of Õ(√T) — matching the best possible rate in the simpler i.i.d. (independent and identically distributed) setting. This closes an important gap because sublinear regret was previously unattainable in the fully adversarial case. The researchers leverage a continuity property of smooth instances and combine it with a hierarchical net-construction of the broker's action space, analyzed via algorithmic chaining.

The result is significant not only for its theoretical tightness but also for its broad applicability. The same techniques yield a similarly tight Õ(√T) regret bound for the related joint ads problem, a mechanism design model where multiple advertisers compete. By extending strong regret guarantees from the stochastic i.i.d. case to the smooth adversary model, the work substantially expands the range of real-world scenarios where near-optimal profit can be achieved. This opens the door for more robust intermediary algorithms in online marketplaces and advertising systems.