Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationarity

Abstract:We study budget pacing in repeated first-price auctions when an advertiser's private-value distributions change over time and the stationary competing-bid distribution is unknown. We ask how a feasible expenditure plan should enter online bid shading, learning, and hard budget control. We establish a plan-to-performance decomposition for a plan-driven projected-dual policy. The policy uses any feasible expenditure plan as a soft target, learns an unknown stationary competing-bid CDF from thresholds revealed after each auction, and enforces the campaign budget on every sample path. Against a distribution-informed expected-budget fluid benchmark, the uniform-plan reward gap is $O(\sqrt T)+O(\mathcal W_T)$, where $\mathcal W_T$ measures heterogeneity in private-value distributions. With a supplied feasible plan, the global gap decomposes into a one-sided $O(\sqrt{T})$ fixed-plan execution term and a plan-mismatch term bounded by $(b/2a)PlanError$. The same analysis provides guarantees for strict and relaxed period-cap comparators, exact recovery of the global benchmark under a specific allowance vector, and separate lower bounds establishing the necessity of the temporal-heterogeneity and Plan Error terms. An upstream planner can translate forecasts or managerial priorities into a feasible spending trajectory, while the online controller adapts bids using realized thresholds and expenditures. The guarantee is modular: it evaluates the final normalized or projected plan through $PlanError$. A specific forecasting model can be linked to the guarantee by establishing how its primitive estimation errors propagate to this plan-quality metric.

Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

arXiv:2505.02796 [cs.GT]

(or arXiv:2505.02796v3 [cs.GT] for this version)

https://doi.org/10.48550/arXiv.2505.02796 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.