Learning to Bid in Discriminatory Auctions with Budget Constraints
Authors: Negin Golrezaei, Sourav Sahoo
Organizations: Sloan School of Management, Massachusetts Institute of Technology · Operations Research Center, Massachusetts Institute of Technology
Abstract
We study repeated bidding in multi-unit discriminatory (pay-as-bid) auctions for a single bidder with per-round utility equal to value minus α times payment, where α∈[0,1] is a cost-of-capital parameter. The bidder aims to maximize cumulative utility over T rounds subject to a total budget B. The problem is challenging even without budgets: the action space is exponential in M, the maximum demand of the bidder and the valuation vector (context) varies over time. Exploiting a decomposition of utility across units, we develop polynomial-time learning algorithms based on shortest paths in a directed acyclic graph, obtaining sublinear regret under both full-information and bandit feedback. In the bandit setting, the regret is independent of the number of contexts due to complete cross-learning: observing the utility of the chosen action under the realized context reveals the utility for the same action under all counterfactual contexts. With budget constraints, when the average normalized per-round budget ρ=MTB<1, we design a coupled primal-dual algorithm in which the DAG-based procedure uses dual-adjusted edge weights for primal updates, while online gradient descent updates the dual variable, yielding ρ-approximate sublinear regret. Finally, we give implementations whose per-round time and space are independent of the number of contexts, enabling scalability to large or even infinite context spaces.
Learning to bid in repeated multi-unit auctions with bandit feedback poses a fundamental challenge. Existing methods often rely on rigid explore-then-exploit schedules, assume stationary adversaries, and optimize solely for bidder utility, thereby limiting adaptability and strategic robustness. To address these limitations, we introduce the A3M framework, which integrates adaptive deep reinforcement learning (DRL), explicit adversarial reasoning, and principled multi-objective reward design for online auction strategy optimization. A3M employs an actor-critic DRL backbone to dynamically balance exploration and exploitation, an opponent model for fictitious play against non-stationary adversaries, and a composite reward function to jointly maximize utility, auctioneer revenue, and fairness. We provide the first comprehensive empirical evaluation of this integrated approach against established baselines in both discriminatory and uniform price auctions. Results show that A3M reduces final regret by 30--40% in standard settings, maintains robust performance against adversarial strategy shifts, scales favorably with the number of units K, and enables tunable multi-objective trade-offs. An extensive ablation study confirms the necessity of each core component. Our work establishes A3M as a powerful and flexible framework for learning in complex auction environments.
We study repeated contextual procurement auctions in which producers have private costs and the platform must learn context-dependent product values from bandit feedback. The objective is welfare rather than revenue or a virtual-cost surrogate: regret is the total surplus loss relative to the full-information efficient procurement rule. We first show that the natural UCB allocation rule attains O~(ngT) welfare regret under truthful bids, but its adaptive bid-dependent learning path does not by itself give a truthfulness guarantee. To obtain exact incentives, we design a bid-independent explore-then-commit mechanism with empirical critical payments; it is dominant-strategy truthful and has O~((ng)1/3T2/3) regret. We then introduce frozen-payment UCB, which estimates payments in an initial bid-independent exploration phase, freezes those payment estimates, and continues adaptive UCB allocation learning afterwards. Under a smoothed truthful-path margin condition, this mechanism gives a regret-incentive tradeoff: the near-UCB tuning attains O~(ngT) welfare regret, while the average per-round gain from any fixed deviation is at most O~(T−1/4) for fixed n,g. A matching lower bound shows that this frozen-payment frontier is unavoidable.
We study the problem of learning to bid when the bidder's value is dynamic, i.e., when the current value depends on past outcomes. Specifically, we consider a bidder participating in repeated second-price auctions whose value depends on the time elapsed since their last successful bid, with auctions arriving in continuous time and only aggregated feedback revealed at the end of the horizon. Such a bidder must (1) balance the immediate benefit of winning the current auction against its impact on future values and (2) learn unknown environmental parameters. We derive regret bounds for a class of learning methods that combine plug-in estimators with a differential-equation characterization of the optimal policy, and show that a specific confidence bound algorithm learns the optimal policy with a near optimal regret of O(logN) for piecewise linear primitives, and O(N1/3) for general, smooth primitives, achieving these regrets without explicit randomization. These theoretical results are supported by numerical experiments.