In digital advertising and programmatic marketplaces, the rules governing how items are bought and sold have undergone a massive paradigm shift. For years, the industry relied predominantly on second-price auctions. In a second-price auction, the highest bidder wins but pays the price of the second-highest bid. This format possesses a elegant mathematical property: bidding your true, private valuation of an item is a dominant strategy. You have no incentive to cheat or guess what others are doing; honesty is utility-maximizing.
Today, almost every major ad exchange has pivoted to first-price auctions, where the winner pays exactly what they bid. This structural shift completely breaks the incentive for truthful bidding. If your true valuation of an ad impression is \$10, and you bid \$10, winning the auction means you pay \$10. Your net profit (or advertiser surplus) is exactly zero.
To capture any value at all, participants must transition to a strategy known as bid shading—the practice of strategically lowering a bid below its true valuation while still maintaining a high probability of winning.
The Fundamental Trade-off
To understand why bid shading is a challenging optimization problem, we can look at the expected utility of a single auction. Let $v$ represent a bidder's true private valuation of an impression, and let $b$ represent the actual bid submitted to the first-price auction ($b \le v$).
The bidder's utility if they win is the surplus $v - b$. If they lose, their utility is $0$. The probability of winning depends on whether the submitted bid clears the highest competing bid in the market, which we can treat as a random variable $m$. Therefore, the expected utility $U(b)$ can be written as:
$$U(b) = (v - b) \cdot \mathbb{P}(b > m)$$
This equation reveals a sharp mathematical tension:
- Maximize Margin: To maximize the profit margin per win $(v - b)$, the bidder wants to make $b$ as small as possible.
- Maximize Win Rate: To maximize the probability of winning $\mathbb{P}(b > m)$, the bidder wants to make $b$ as large as possible.
As noted by Xiaotie Deng et al. in Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions, this trade-off eliminates any simple dominant strategy. Instead, finding the optimal bid requires accurately modeling or learning the behavior of the competitive landscape.
Modeling the Competitive Landscape
Because the optimal bid depends entirely on the distribution of the maximum competing bid $m$, modern bidding systems leverage machine learning to predict this hidden market threshold.
Asymmetric Loss Functions
Standard machine learning models typically minimize symmetric errors, like Mean Squared Error (MSE), where overestimating and underestimating a target are penalized equally. In bid shading, however, errors are fundamentally asymmetric. If you bid slightly too high, you still win the auction but suffer a minor reduction in profit margin. If you bid slightly too low, you fail to clear the competitive threshold, lose the auction entirely, and receive a utility of zero.
To address this, Djordje Gligorijevic et al. introduced a machine learning framework using Factorization Machines optimized with a custom asymmetric loss function in Bid Shading in The Brave New World of First-Price Auctions. By penalizing under-bidding more severely than over-bidding, the model learns to shade bids conservatively, safeguarding the advertiser's win rate while capturing significant surplus.
Deep Distribution Modeling
Rather than predicting a single point estimate for the optimal bid, a more robust approach is to predict the entire probability distribution of the winning market price. Tian Zhou et al. proposed an end-to-end deep learning architecture in An Efficient Deep Distribution Network for Bid Shading in First-Price Auctions that models the market price as a continuous distribution conditioned on auction features. Once the full distribution $\mathbb{P}(m)$ is known, the expected utility curve can be explicitly mapped out, allowing the system to analytically solve for the precise bid $b$ that maximizes expected utility.
Leveraging Predictive Hints
Sometimes, the auction platform itself provides partial information to help buyers navigate the market. Aaron Flores et al. explored this in Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions, demonstrating how bidders can utilize machine learning "hints" (rough predictions of competitor bids). Crucially, the authors proved that knowing the confidence or variance of a prediction is often more valuable than the prediction itself, as it allows the shading algorithm to dynamically widen or narrow its safety margins based on market certainty.
Learning to Shade Under Real-World Constraints
In practice, advertisers do not participate in isolated auctions; they run long-term campaigns across millions of sequential auctions under strict operational constraints, such as fixed daily budgets or target Return-on-Investment (ROI) thresholds. This transforms bid shading from a static prediction problem into an online stochastic control problem, as highlighted by Nicolas Grislain et al. in Recurrent Neural Networks for Stochastic Control in Real-Time Bidding.
No-Regret Learning
When competing in repeated auctions where the underlying distribution of competitor bids is unknown and potentially changing, algorithms aim to minimize regret—the difference between the total utility achieved by the algorithm and the utility that could have been achieved by the single best fixed bidding strategy in hindsight.
This challenge is compounded by censored feedback: if your shaded bid loses, you typically do not get to see what the winning bid actually was. To handle this, Rui Ai et al. developed a framework combining dynamic programming with survival analysis in No-regret Learning in Repeated First-Price Auctions with Budget Constraints, proving that near-optimal regret bounds are achievable even under strict budget limits and limited feedback.
When both budget and ROI constraints are active simultaneously, the optimization landscape becomes highly non-linear. Yilin LI et al. in No-Regret Online Autobidding Algorithms in First-price Auctions and Gagan Aggarwal et al. in No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints designed online autobidding algorithms that compete against sophisticated randomized or Lipschitz-continuous bidding benchmarks, establishing theoretical guarantees for multi-constraint optimization in non-truthful environments.
Accelerating Convergence
While standard online learning algorithms guarantee a regret bound that grows at a rate of $O(\sqrt{T})$, this can be too slow for fast-paced advertising markets. If the environment is relatively stable and stochastic rather than adversarial, Juliette Achddou et al. demonstrated in Fast Rate Learning in Stochastic First Price Bidding that it is possible to achieve "fast rate" learning, slashing expected regret down to $O(\log^2 T)$. This means an agent can converge to the mathematically optimal shading strategy exponentially faster, minimizing wasted capital during the exploration phase.
Market Dynamics and Equilibrium
When every participant in an auction ecosystem adopts machine learning to shade their bids, the market becomes a dynamic, co-evolving system. One agent's optimal shading strategy alters the winning thresholds for everyone else.
The Complexity of Stability
This strategic interdependence complicates the search for a stable market state, or Nash Equilibrium. Johannes Brustle et al. analyzed this in Price Manipulability in First-Price Auctions, showing that the necessity of bid shading introduces structural price manipulability and potential instability into markets.
In fact, from a computational complexity standpoint, Xi Chen et al. proved in Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules that finding an approximate equilibrium in a first-price auction under arbitrary tie-breaking rules is PPAD-complete—meaning it is fundamentally hard for algorithms to compute. However, the authors also provided a silver lining: under standard uniform tie-breaking rules, polynomial-time approximation schemes can efficiently locate stable states.
The Seller's Counter-Strategy
Bid shading also fundamentally alters the problem from the seller's perspective. Because buyers are intentionally hiding their true valuations behind shaded bids, the seller (the publisher) cannot easily observe the true market demand for their inventory.
To protect their revenue, sellers must optimize their reserve prices (the minimum price floor required to win). As explored by Zhe Feng et al. in Reserve Price Optimization for First Price Auctions in Display Advertising, sellers must explicitly model the fact that buyers are strategic shaders. By setting optimal, dynamic reserve prices, sellers can force buyers to bid closer to their true valuations, effectively counteracting the effects of bid shading.
Holistic Platform Optimization
Finally, large intermediaries like Demand-Side Platforms (DSPs) must manage this complexity across multiple layers. A DSP often runs an internal auction to choose which advertiser's creative to submit to an external first-price ad exchange.
Historically, DSPs treated these as two independent steps: first pick the best internal ad, then apply a bid shading algorithm to the winner. However, Yadong Xu et al. showed in Simultaneous Optimization of Bid Shading and Internal Auction for Demand-Side Platforms that this separation is sub-optimal. By using partially monotone neural networks to jointly optimize internal candidate selection and external bid shading simultaneously, platforms can achieve significantly higher total advertiser surplus and platform profit, proving that bid shading is not just an isolated prediction trick, but a core component of modern mechanism design.
Key Foundational Work
Bid Shading in The Brave New World of First-Price Auctions (2020) — contributed 1 concept elements to this direction.
Recurrent Neural Networks for Stochastic Control in Real-Time Bidding (2019) — contributed 1 concept elements to this direction.