New algorithm learns to bid optimally despite shill manipulation in auctions

A new paper by Luigi Foscari, Matilde Tullii, and Vianney Perchet tackles a classic problem in auction theory: shilling. In repeated first-price auctions, a seller may insert fake bids (shills) to make competition appear stiffer, driving up prices. Crucially, the paper studies a subtle form where shilling only affects what the learner observes after losing (the max of the real bid and a shill), not whether the learner wins or loses. This makes learning—and bidding—much harder because the feedback is systematically distorted.

The authors propose a dual-algorithm strategy. The first branch uses robust interval elimination that ignores shill reports entirely, achieving a regret rate of O(T^{2/3})—the dynamic pricing baseline. The second branch is optimistic: it debiases losing-side reports when possible, exploiting low-shill events to achieve the faster O(√T) rate. A validation and racing procedure lets the algorithm switch between branches without knowing the correct scale or feedback geometry in advance. The paper also proves a matching lower bound, showing the approach is tight up to logarithmic factors. This work has direct implications for automated bidding systems in programmatic advertising, where shilling is a known challenge.