📊 statistics

Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions

This paper analyzes repeated first-price auctions where shilling manipulates feedback rather than allocation, proposing a hybrid algorithm that achieves optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret by combining robust interval elimination with optimistic debiasing, while demonstrating that such feedback-only manipulation significantly increases the statistical difficulty of learning to bid.

Original authors: Luigi Foscari, Matilde Tullii, Vianney Perchet

Published 2026-05-22

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Luigi Foscari, Matilde Tullii, Vianney Perchet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to buy a rare collectible at an online auction. You don't know how much other people are willing to pay, so you have to learn by watching what happens when you place your bids.

Usually, if you lose an auction, the platform tells you the highest bid that beat you. This helps you learn: "Oh, I need to bid a little higher next time."

But in this paper, the authors imagine a scenario where the auctioneer is a bit tricky. They call this "shilling."

The Trick: The "Fake Competitor"

Imagine the auctioneer has a secret friend who places fake bids just to make the competition look fiercer than it really is.

If you win: Great! You get the item, and the fake friend doesn't matter.
If you lose: The auctioneer tells you the highest bid including the fake one.

So, if the real highest bid was \ $50, but the fake friend bid \$ 80, the auctioneer tells you, "You lost to $80!"

The Problem: You might think, "Wow, everyone is bidding \ $80! I better bid \$ 85 next time!" But the real competition was only $50. You are being tricked into overpaying.
The Twist: Sometimes, the fake friend bids very low (say, \ $10). If the real bid was \$ 50, the auctioneer still tells you the max, which is $50. In this case, you get the real information.

The paper asks: How can a smart bidder learn the true prices when the auctioneer is lying about the losing bids, but only sometimes?

The Two-Pronged Strategy

The authors designed a "learning algorithm" (a set of rules for a computer) that acts like a cautious detective. It uses two different approaches at the same time, like having a safety net and a high-speed car.

1. The Safety Net (The "Robust" Branch)

This part of the algorithm says, "I don't trust the losing bid reports at all. I'm going to ignore the fake numbers."

It only looks at whether it won or lost.
It treats the auction like a simple "price tag" game (like buying a coffee where you just see if you can afford it).
Result: This is slow and safe. It guarantees you won't lose too much money, but you won't learn super fast. It's like walking carefully in the dark.

2. The Optimist (The "Optimistic" Branch)

This part says, "Let's try to use the fake numbers, but let's be smart about it."

It knows the pattern of the fake bids (e.g., "The fake friend usually bids between \ $10 and \$ 20").
When it sees a losing bid, it does some math to "subtract" the fake part and guess what the real bid might have been.
The Catch: This only works well if the fake bids are low enough to let the real bid peek through.
Result: When the fake bids are low and helpful, this method learns much faster than the safety net. It's like driving fast on a clear road.

3. The "Racing" Mechanism

The algorithm doesn't know in advance which method will work better. So, it runs both at the same time in a "race."

It constantly checks: "Is the Optimist making sense? Is the data reliable?"
If the fake bids are too high and the Optimist is getting confused, the algorithm switches back to the Safety Net.
If the data looks clean, it leans into the Optimist to learn faster.

The Big Discovery

The paper proves that even though the auctioneer is manipulating the information, the learner can still do surprisingly well.

If the fake bids are always high: The learner is stuck with the slow "Safety Net" speed.
If the fake bids are sometimes low: The learner can use the "Optimist" to speed up, learning much faster than if they were just guessing.

The authors also proved a mathematical limit: you can't learn infinitely fast. There is a "speed limit" based on how often the fake bids accidentally reveal the truth. If the fake bids are very rare (low probability), you are forced to go slow. If they happen often, you can go fast.

In a Nutshell

This paper is about learning to bid in a rigged game where the referee lies about the scores. The authors built a strategy that ignores the lies when necessary but cleverly uses the truth hidden inside the lies when possible. They showed that even with a lying referee, you can still learn the market prices efficiently, provided you have a way to tell when the referee is being helpful versus when they are just messing with you.

Technical Summary: Learning to Bid in Feedback-Manipulated Auctions

Problem Setting
The paper investigates repeated first-price auctions where the auctioneer (or seller) engages in "shilling"—the use of artificial bids to manipulate the feedback received by a learning bidder. Unlike traditional models where manipulation might alter the allocation rule or payment, this work focuses on feedback-manipulated auctions. Specifically, the learner competes against a real highest competing bid, $b_t$ , and wins if their bid $p_t \geq b_t$ . However, upon losing, the learner does not observe the true $b_t$ . Instead, they observe a shilled report $o_t = \max\{b_t, s_t\}$ , where $s_t$ is an independent shill bid drawn from a known distribution $S$ .

This setup creates a unique learning challenge: the allocation remains truthful (the learner wins or loses based on reality), but the information channel is distorted. High shill bids mask the true competition, while low shill bids reveal "suffix information" (information about bids larger than the one played). The goal is to minimize regret against the best fixed bid for the realized value, $v_t$ , in the presence of this masked feedback.

Methodology
The authors propose an algorithm that operates in epochs over a discretized grid of prices and values. The core innovation is a dual-branch approach combined with a validation and racing procedure:

Robust Branch (Interval Elimination): This branch ignores the shilled reports entirely, relying only on the binary win/loss outcome. It treats the problem as a dynamic pricing task with censored feedback. This branch guarantees a regret rate of $\tilde{O}(T^{2/3})$ , serving as a safety net when shilling is severe or the shill distribution is not informative.
Optimistic Branch (Debiased Suffix Learning): This branch attempts to exploit the shilled reports. Since the shill distribution $F_S$ $F_{S}$ is known, the algorithm constructs an unbiased estimator for the true competing bid distribution $F_B$ $F_{B}$ using the observation $o_t$ $o_{t}$ .
- It utilizes suffix observations: When $o_t \leq q$ , it implies $b_t \leq q$ (if the shill was low enough).
- It employs a weighted least-squares framework to combine direct win/loss measurements with these suffix-difference measurements.
- Crucially, it introduces a geometric uncertainty analysis. The algorithm does not just estimate pointwise values but constructs confidence bounds over intervals of active bids, leveraging the fact that a single low-shill event reveals information about a whole range of higher bids.
Dyadic Validation: The algorithm does not assume the scale of the shill distribution (specifically the probability $\gamma$ of a "low-shill" event that reveals information) is known. It validates optimistic updates against a set of dyadic candidates for the shill scale. If an optimistic candidate fails validation (e.g., the shill distribution is too irregular or the scale is too small), the algorithm reverts to the robust branch.

Key Contributions

Robustness with Safety Nets: The paper provides a robust interval-elimination procedure that achieves the $\tilde{O}(T^{2/3})$ dynamic pricing rate even when shilling renders the feedback useless.
Optimistic Debiasing: It develops an optimistic procedure that extracts structured information from the "noisy path-like" signals of shilled reports. By converting suffix observations into measurements of adjacent utility differences, the algorithm achieves faster rates when the active bid regions are regular and well-covered.
Adaptivity: The algorithm adapts to the unknown effective shill level through a dyadic validation scheme, removing the need for prior knowledge of the shill scale or feedback geometry.
Tight Lower Bounds: The authors prove a matching lower bound for the single-active-region case. They construct a "hidden cell" instance where a small utility bump exists in an unknown interval. The proof demonstrates that the regret is fundamentally limited by the trade-off between local search (dynamic pricing regime) and cross-learning via losing-side reports.

Results
The paper establishes the following regret bounds (up to logarithmic factors):

Upper Bound: The algorithm achieves a regret of $\tilde{O}\left(\min\left\{T^{2/3}, \rho^{1/4}\sqrt{T}\gamma^{-1/4}\right\}\right)$ $\tilde{O} (min {T^{2/3}, ρ^{1/4} T γ^{- 1/4}})$ , where $\rho$ $ρ$ is the number of active bid regions and $\gamma$ $γ$ is the probability of informative low-shill events.
- In the single-active-region case ( $\rho=1$ ), the bound is $\tilde{O}\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ .
- This rate interpolates between the $T^{2/3}$ rate of dynamic pricing (when shilling is heavy, $\gamma \to 0$ ) and the $\sqrt{T}$ rate of standard first-price auctions (when shilling is light, $\gamma$ is large).
Lower Bound: For the single-active-region case, the paper proves a lower bound of $\Omega\left(\min\left\{T^{2/3}, \sqrt{T}\gamma^{-1/4}\right\}\right)$ . This confirms that the algorithm is minimax-optimal up to logarithmic factors. The lower bound construction highlights that even with knowledge of the shill distribution, the learner cannot fully recover the $\sqrt{T}$ rate if informative shill events are rare, as the "hidden cell" remains difficult to identify quickly.

Significance and Claims
The paper claims that even feedback-only shilling (where the allocation rule is untouched) can sharply alter the statistical difficulty of repeated bidding. The manipulation acts through the information channel, biasing the learner toward higher bids and partially destroying the cross-learning structure that typically allows for $\sqrt{T}$ regret in first-price auctions.

The authors position this work as a first step toward a theory of feedback manipulation in auctions. They explicitly state that extending these results to unknown shill distributions, richer shilling models (e.g., dependent on the learner's bid), and more general active-region geometries remains an open question. The significance lies in demonstrating that carefully exploiting the structure of manipulated feedback can recover much more than a purely robust approach, provided the manipulation follows specific structural constraints (like max-shilling with known distribution).