Learning to Bid in Discriminatory Auctions with Budget Constraints

How can a budget-constrained bidder learn to bid optimally in repeated multi-unit pay-as-bid (PAB) auctions when competing bids are adversarial, valuations vary over time, and the action space is exponentially large?

The authors model the bidder's utility as value minus a cost-of-capital-adjusted payment. They observe that the bidder's utility decomposes across units, allowing them to map the problem of finding an optimal no-overbidding (NOB) strategy to finding a shortest path in a directed acyclic graph (DAG). To handle budget constraints, they design a coupled primal-dual algorithm where the DAG-based procedure handles primal utility maximization, while online gradient descent updates a dual variable (a pacing multiplier) to ensure budget feasibility.

The paper establishes that the optimal offline bidding strategy can be computed in polynomial time using shortest-path algorithms on a DAG. In the online setting, the authors provide algorithms that achieve sublinear regret under both full-information and bandit feedback. Notably, they demonstrate that the bidder's utility under a realized context reveals information about counterfactual utilities, enabling complete cross-learning that makes regret bounds independent of the number of contexts. Finally, they provide an efficient implementation where per-round time and space complexity scale only with the number of edges in the DAG, making the approach scalable to massive context spaces.

This work provides a robust framework for automated bidding in complex, multi-unit auction environments like treasury auctions or electricity markets. By moving beyond simple single-item models and addressing the computational challenges of large action spaces, the authors offer a practical path for bidders to manage budgets effectively in real-world, non-truthful auction formats.