How to Bid

October 6, 2026

Every production bidding system in the research literature factorizes the bid the same way, and it’s worth writing down why before any math:

bid(x) = multiplier · value(x),      value(x) = pCTR(x) · pCVR(x) · V

The value half is machine learning — calibrated probabilities learned from your own logs, covered in a companion entry. This entry is about the multiplier half: given a budget, a CPA target, an auction format, and a competitive landscape, what is the optimal function that turns value into a bid? The remarkable thing, after a decade of papers, is how settled the answer is. The optimal shape is derivable; the constrained variants all reduce to one structural theorem with more dual variables; and every production system is some approximation of an online solver for one number (λ) per constrained resource. I’ll build the result up, then show where it’s still an open problem.

Linear bidding is only the unconstrained special case

The heuristic that ran production for years (Zhang et al. 2016, eq. 1):

b(t) = b₀ · θₜ/θ̄

— bid proportional to the instance pCTR over the segment average; linear in value, one tuned constant. And the default theory says: bid your value (truthful), and you cannot be exploited. The central result of the bidding literature is that both are optimal only when nothing binds. With a budget or a CPA constraint, the value→bid map becomes nonlinear and the nonlinearity is computable; and in a repeated auction with budgets, bidding your true value isn’t even dominant — Balseiro, Besbes & Weintraub (Management Science, 2015) show optimal play there looks like uniform multiplicative pacing: bid a fixed fraction α ≤ 1 of value, forever, so long as the budget binds and never binds slack. Every DSP’s throttling heuristic had been reconstructing that equilibrium empirically since 2006. Constraints force nonlinearity; the job is computing it.

ORB: the derivation that settled the shape

Zhang, Yuan & Wang, “Optimal Real-Time Bidding for Display Advertising” (KDD 2014), full derivation (their eqs. 5–16):

Primal. Maximize expected value (clicks) over a bidding function b(θ) — not a bid, a function from KPI estimate θ to bid — subject to expected spend ≤ B/N per auction opportunity arriving with density pθ(θ), where the win-rate w(b) is the bid-landscape CDF:

max_b   ∫ θ·w(b(θ))·pθ(θ) dθ     s.t.   ∫ b(θ)·w(b(θ))·pθ(θ) dθ ≤ B/N

KKT. Lagrangian with multiplier λ, Euler–Lagrange derivative w.r.t. b(θ), and the objective collapses to one identity:

λ·w(b) = (θ − λ·b)·w′(b)

Read it English-first: the marginal value of the budget (λ) equals the marginal win-rate per cent, net of what you’d overpay by. And note the silence: pθ(θ) cancels out. The optimal bidding function depends only on the win-rate curve and λ; the value distribution enters only by moving λ. This is why the landscape is the load-bearing object, and why λ is a pacing quantity (its own entry). Two parametric win-rate curves, two closed forms:

Both are concave in θ: optimally you bid more than proportionally on cheap traffic and less than proportionally on expensive — “buy many cheap impressions, not few expensive ones” — because win-rate rises steepest at low bids, so the marginal auction per dollar is cheapest there. (General form w(b)=b^α/(c^α+b^α): no analytic bid for α > 2, and the shape intuition holds.) Finally λ itself is fixed by the budget-feasibility condition — expected spend must equal B/N — which has no closed form, no problem, bisection on a monotone function. Three subsystems in one equation: the value distribution from ML sets λ’s level, the landscape sets the shape, the budget sets λ through the spend equation. The CPA-constrained variant adds a second multiplier and the bid becomes a ratio of linear-fractional terms — the shape argument is identical.

USCB: every constrained problem is one formula

He et al. (Alibaba), “A Unified Solution to Constrained Bidding” (KDD 2021), takes the natural generalization — an LP with impression-selection variables, M side constraints (budget; CPA/ROI/CPC targets; deep-conversion ratios), relaxed and dualized — and its Theorem 2.1 gives the optimal bid as:

bᵢ* = w₀*·vᵢ − Σⱼ wⱼ*·( qᵢⱼ(1 − 1_CRⱼ) − kⱼ·pᵢⱼ )        w₀* = 1/(α* + Σⱼ βⱼ*·1_CRⱼ)

English: linear value scaling, minus per-constraint correction terms. The lovely corollary is what a CPA (cost-related) constraint contributes: the additive correction vanishes (its indicator zeroes the sum) and only the denominator inflates — a CPA constraint is a tax on the multiplier, not a filter on impressions. Non-cost constraints (say, a ratio of conversions to clicks) subtract value-dependent terms per impression. All the bookkeeping reduces to K+1 dual numbers — solved offline with a real LP solver on forecast supply, or online by dual ascent. When the paper’s own ablations compare against per-constraint heuristics, the wins are exactly where constraints interact: a budget-tight campaign near its CPA ceiling needs different value→bid curvature than either loop alone prescribes, and no heuristic-family spans that interaction.

The online solvers: feedback control of λ

λ must be solved while the auctions run — supply arrives online and competitors drift. The map λ→spend has unknown, drifting gain (competition moves under you), dead time (conversion delay), and multiplicative response (steepening win-rate curves make spend move roughly exponentially w.r.t. log-bid — pooled price distributions look log-normal, per-segment ones fail the test). Predicted supply makes it a root-find; no forecast makes it a control problem. Two published production answers:

Feedback loops. Zhang et al. (WSDM 2016, deployed on the BigTree mobile DSP, offline-studied on iPinYou logs) ship bid adjustment b'(t) = b(t)·exp(φ(t)) — an exponential actuator keeping bids positive — with φ from PID or waterlevel (integrator-only; φ(t+1) = φ(t) + γ·(r − x(t))) control on the eCPC error. Their elegant §3.4 result: set each channel’s controller reference from the equalization condition — at the optimal dual α, marginal clicks per yuan must be equal across exchanges/geos, (1/α) = cᵢ/cᵢ′ + ξᵢ for all channels i — and a bank of ignorant PID loops becomes the LP solution with automatic cross-channel budget reallocation. Model-free optimization by setting references, not solving programs. LinkedIn’s 2014 pacer is the same family from the budget side: a period LP computes the pacing rate, online correction tracks it against realized spend — and its published failure lessons (overrun at day boundaries; throttling as the reliable emergency brake because bid changes have unpredictable spend response) are the reason throttling never died.

Dual descent, the modern canonical form. Balseiro, Lu & Mirrokni, “The Best of Many Worlds” (Oper. Res. 2023): keep the dual, act greedily against reduced value ṽᵢ = vᵢ − λ·cᵢ, and update by online mirror descent — the multiplicative rule λ ← λ·exp(η·(cᵢ − B/T))/Z and the subgradient rule are instances of one scheme with different reference functions. Guarantees: Õ(√T) regret under stochastic arrivals (optimal order), constant competitive ratio adversarially, and provably no early depletion — λ rises before the budget exhausts, the property every pacing engineer actually cares about (Prop. 2). The survey literature (Aggarwal et al. 2024, which I’ve read as the map of this whole area) states the consensus: Lagrangian dual methods are “the work-horse algorithms of budget pacing” and they subsume PID: the integral law in log-λ space is mirror descent with a linear reference. Per-request O(1) — fits the bidder hot path exactly.

The equilibrium those loops converge to, jointly. When every bidder runs a pacing multiplier, there’s a fixed point: first-price pacing equilibrium (Conitzer, Kroer, Sodomka & Stier-Moses; EC 2019 → Management Science 2022): bids αᵢ·vᵢⱼ with αᵢ ∈ [0,1], and the FPPE is characterized as the componentwise-maximal budget-feasible multiplier vector — feasible vectors closed under max implies uniqueness and Pareto-dominance, and it’s seller-revenue-maximizing too. Convergence: the waterlevel law λ ← λ·e^{η·err} provably finds the period-optimal bid in sublinear campaign time even under hidden, drifting cost functions (Hajiaghayi & Springer 2022), and dual-descent dynamics converge to it in repeated models (Balseiro, Kim, Mahdian, Mirrokni, OR 2021). The cold bath at the end: computing the pacing equilibrium in general is PPAD-hard (Chen, Kroer & Kumar, Math. OR 2023) — which is precisely why nobody solves the fixed point and everybody runs feedback, which is precisely why the control literature exists. State of the art now studies regret and efficiency without assuming convergence at all (Gaitonde et al., ITCS 2023): the loop need not settle to be good.

Where RL actually sits

Cai et al. (WSDM 2017) formulated the day as an MDP — state = (time, remaining budget, request features), action = bid, reward = click/conversion — and solved it with deep Q-learning over coarsely-discretized budget states, reporting double-digit lifts over landscape-only baselines on iPinYou/YOYI; multi-advertiser extensions followed (Jin et al. CIKM 2018). The useful positioning comes from the comparison view: ORB/USCB solve the open-loop problem (optimal function under an estimated landscape and known λ mechanics), while RL solves the closed-loop one — the environment is partly you, your own pacing perturbs the landscape, and offline logs are selection-biased by your past policy (you observe only the auctions you won, at the prices you paid). The bandit-theory framing closes the loop formally: budgeted bidding is bandits-with-knapsacks, and Balseiro & Gur (Management Science 2019) give regret-optimal learning procedures in repeated budgeted auctions — the correspondence between learning well and equilibrium behavior is now theorem-grade. The honest read of five or six years of RL-bidding papers: where the state and reward are definable, RL wins modestly and expensively; where they aren’t (sparse conversions, nonstationary markets, a policy that changes the data it trains on), the LP dual decomposition + online dual updates is simpler, provable, and production-hardened. The winning published production systems are characterized by simple policy classes with many dual weights and robust online solvers — the bid map should be derivable, not just learned.

First-price markets: the multiplier survives, the shade goes inside

Under first price, payment = bid, and the whole machinery re-expresses: per-auction, maximize (v − b)·W(b), whose first-order condition, v − b* = W(b*)/w(b*), sets the shade as the inverse hazard rate of market price (the shading entry takes this apart; the empirical WWW’24 studies show market-wide play is mostly uniform shading, i.e., FPPE’s prediction holds approximately in production and deviations concentrate in thin and thick auctions). And the structural news from USCB’s generalization: the bid = min(λ_budget, λ_ROS) · shade(x) · v composition shows the dual structure survives the format change — pacing and shading are two multipliers on the same channel, which is the trap its entry describes.

The bidder’s design checklist, as this thread composes into a system

  1. One bid function: bid = f(v̂(x), λ, duals, shade(x)); derive it, don’t learn it, then tune it.
  2. Constrained resources each get one dual: budget, CPA, ROS, frequency caps, min-delivery floors. Parallel loops, min-compose the multipliers — serial cascading double-penalizes and violates constraints by Ω(T) (Balseiro et al., KDD 2023’s field guide proves the separation; the paper calls the architecture the whole difference between guarantee and disaster).
  3. Landscape models (w(b|x), p(z|x)) are offline artifacts feeding both the bid shape and the shade; calibration is a first-class output, not a final-stage polish.
  4. λ updated by multiplicative dual descent with anti-windup, gain scheduling from dS/dφ estimates (the landscape gives them for free), and never zeroed on staleness — last-known-good with conservative bias, or you turn off a line-item by an outage of a cache miss.
  5. Explore deliberately (budgeted bandits), because your censoring means unexplored segments are un-estimable, and the map is driftier than your priors.
  6. Instrument the derived quantities: realized CPA vs target per channel, marginal clicks/yuan equalization residuals, λ trajectories per campaign. Revenue tells you last week; these tell you today.

The satisfaction of this thread, for me, is architectural: what began as “guess a bid” is one convex story — a value model learned from logs, a landscape learned from censoring, a dual price solved by feedback — with proofs attached at the interesting corners. It is rare for a market to be this legible from the buyer’s seat, and that legibility is itself the reason the moat (from the economy entry) moved from algorithms to data.

References

  1. Zhang, W., Yuan, S. & Wang, J. (2014). “Optimal Real-Time Bidding for Display Advertising.” KDD. doi:10.1145/2623330.2623633
  2. He, Y., Chen, X., Wu, D., Pan, J., Tan, Q., Yu, C., Xu, J. & Zhu, X. (2021). “A Unified Solution to Constrained Bidding in Online Display Advertising.” KDD. doi:10.1145/3447548.3467199
  3. Balseiro, S., Besbes, O. & Weintraub, G. (2015). “Repeated Auctions with Budgets in Ad Exchanges.” Management Science 61(4):864–884. doi:10.1287/mnsc.2014.2022
  4. Zhang, W., Rong, Y., Wang, J., Zhu, T. & Wang, X. (2016). “Feedback Control of Real-Time Display Advertising.” WSDM. doi:10.1145/2835776.2835843, arXiv:1603.01055
  5. Agarwal, A. et al. (2014). “Budget Pacing for Targeted Online Advertisements at LinkedIn.” KDD. doi:10.1145/2623330.2623366
  6. Balseiro, S., Lu, H. & Mirrokni, V. (2023). “The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems.” Operations Research 71(1):101–119. doi:10.1287/opre.2021.2242, arXiv:2011.10124
  7. Balseiro, S., Bhawalkar, K., Feng, Z., Lu, H., Mirrokni, V., Sivan, B. & Wang, S. (2023). “A Field Guide for Pacing Budget and ROS Constraints.” KDD. arXiv:2302.08530
  8. Conitzer, V., Kroer, C., Sodomka, E. & Stier-Moses, N. (2019/2022). “Pacing Equilibrium in First-Price Auction Markets.” EC 2019, doi:10.1145/3328526.3329600; journal: “Multiplicative Pacing Equilibria in Auction Markets,” Management Science 70(2). doi:10.1287/mnsc.2022.4310, arXiv:1811.07166
  9. Balseiro, S., Kim, B., Mahdian, M. & Mirrokni, V. (2021). “Budget-Management Strategies in Repeated Auctions.” Operations Research 69(3):859–876. doi:10.1287/opre.2020.2073 (+ WWW 2018, doi:10.1145/3038912.3052682)
  10. Hajiaghayi, M. & Springer, R. (2022). “Analysis of a Learning Based Algorithm for Budget Pacing.” arXiv:2205.13330
  11. Chen, X., Kroer, C. & Kumar, R. (2021). “The Complexity of Pacing for Second-Price Auctions.” Mathematics of Operations Research. arXiv:2103.13969
  12. Cai, H., Ren, K., Zhang, W. & Wang, K. (2017). “Real-Time Bidding by Reinforcement Learning in Display Advertising.” WSDM. doi:10.1145/3018661.3018702, arXiv:1701.02490
  13. Jin, J. et al. (2018). “Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertising.” CIKM. doi:10.1145/3269206.3272021
  14. Balseiro, S. & Gur, Y. (2019). “Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium.” Management Science 65(9). doi:10.1287/mnsc.2018.3174
  15. Aggarwal, G., Badanidiyuru, A. & Mehta, A. (2019). “Autobidding with Constraints.” WINE. doi:10.1007/978-3-030-35389-6_2
  16. Aggarwal, G. et al. (2024). “Autobidding and Auctions in Online Advertising: A Survey.” arXiv:2408.07685
  17. Chen, Y. (2025). “A Practical Guide to Budget Pacing Algorithms in Digital Advertising.” arXiv:2503.06942
  18. Deng, Y., Mao, J., Mirrokni, V., Zhang, H. & Zuo, S. (2022/2024). “Efficiency of the First-Price Auction in the Autobidding World.” arXiv:2208.10650; NeurIPS 2024, doi:10.52202/079017-4420