Abstract: We study the bidding problem in repeated uniform price multi-unit auctions from the perspective of a single *value-maximizing* buyer who aims to maximize their cumulative value over $T$ rounds while adhering to return-on-investment (RoI) constraints in each round. Buyers adopt $m$-*uniform bidding* format, where they submit $m$ bid-quantity pairs $(b_i, q_i)$ to demand $q_i$ units at bid $b_i$. We introduce *safe* bidding strategies as those that satisfy RoI constraints in every auction, regardless of competing bids. We show that these strategies depend only on the bidder’s valuation curve, and the bidder can focus on a finite subset of this class without loss of generality. While the number of strategies in this subset is exponential in $m$, we develop a polynomial-time algorithm to learn the optimal safe strategy that achieves sublinear regret in the online setting, where regret is measured against a clairvoyant benchmark that knows the competing bids *a priori* and selects a fixed hindsight optimal safe strategy. We then evaluate the performance of safe strategies against a clairvoyant that selects the optimal strategy from a richer class of strategies in the online setting. In this scenario, we compute the *richness ratio*, $\alpha\in(0, 1]$ for the class of strategies chosen by the clairvoyant and show that our algorithm, designed to learn safe strategies, achieves $\alpha$-approximate sublinear regret against these stronger benchmarks. Experiments on semi-synthetic data from real-world auctions show that safe strategies substantially outperform the derived theoretical bounds, making them quite appealing in practice.

Lay Summary:

What’s the problem?In many real-world auctions—like those for emissions permits, government bonds, or electricity—multiple identical items are sold at the same price. Buyers participate in these auctions repeatedly and want to get as much value as possible from what they buy, while ensuring that each purchase gives a good return on investment (RoI). This work looks at how a single such buyer should bid over time.What does the research do?The authors define a class of safe bidding strategies that guarantee the buyer meets their RoI constraint in every auction, regardless of what other bidders do. These strategies are based entirely on how much the buyer values each unit. While there are exponentially many possible strategies, the paper develops an efficient algorithm to learn the best one over time. This algorithm performs nearly as well as an ideal bidder who knows all future competition in advance.Why does this matter for decision-makers?Safe bidding strategies are easy to understand, computationally efficient, and robust—even when compared to more flexible or “ideal” strategies. Experiments using data inspired by real-world auctions show that these strategies perform significantly better than conservative theoretical predictions. Because of this, these strategies offer a powerful, robust approach for bidders in high-stakes markets.