Abstract
In a sequential auction with multiple bidding agents, it is highly challenging to determine the ordering of the items to sell in order to maximize the revenue due to the fact that the autonomy and private information of the agents heavily influence the outcome of the auction. The main contribution of this paper is two-fold. First, we demonstrate how to apply machine learning techniques to solve the optimal ordering problem in sequential auctions. We learn regression models from historical auctions, which are subsequently used to predict the expected value of orderings for new auctions. Given the learned models, we propose two types of optimization methods: a black-box best-first search approach, and a novel white-box approach that maps learned models to integer linear programs (ILP) which can then be solved by any ILP-solver. Although the studied auction design problem is hard, our proposed optimization methods obtain good orderings with high revenues. Our second main contribution is the insight that the internal structure of regression models can be efficiently evaluated inside an ILP solver for optimization purposes. To this end, we provide efficient encodings of regression trees and linear regression models as ILP constraints. This new way of using learned models for optimization is promising. As the experimental results show, it significantly outperforms the black-box best-first search in nearly all settings.
Introduction
In sequential auctions, items are sold one after another to a group of bidders. A central challenge for auctioneers is determining the optimal ordering of items to maximize total revenue. Because bidders operate with limited budgets and private preferences, the sequence in which items appear significantly impacts the final outcome. For instance, selling a high-value item early might exhaust a bidder's budget, preventing them from competing for subsequent items and thus lowering overall revenue.
Traditional mathematical optimization requires a precise model of bidder behavior, which is rarely available in practice. This research addresses scenarios where the underlying rules of the system are unknown but historical data is abundant. The goal is to learn these unknown relations from data and subsequently optimize the auction sequence based on those learned patterns.
Methodology
The proposed framework consists of a two-step process: learning and optimization.
1. Learning Phase
Using historical auction data (generated via a custom simulator involving 20 agents and 40 items), the authors train regression models to predict expected revenue. Specifically, they utilize Regression Trees (CART) and LASSO (Linear Regression). These models use features such as previously sold items and accumulated revenue to predict the value of the next item in the sequence.
2. Optimization Phase
The core innovation lies in how these learned models are utilized for optimization. The authors compare two distinct strategies:
- Black-box (Best-First Search): This heuristic approach treats the machine learning model as an "oracle." It repeatedly queries the model for predictions to navigate the search space and find a high-revenue sequence.
- White-box (ILP Encoding): This novel approach translates the internal logic of the regression models—such as the decision splits in a tree or the coefficients of a linear model—directly into linear constraints. By embedding the model structure into an Integer Linear Program (ILP), standard solvers like CPLEX can mathematically navigate the model to find a global optimum.
Key Insights and Results
The White-Box Advantage
By allowing the optimization solver to "see" the internal structure of the ML model, the white-box approach can utilize advanced techniques like branch-and-bound to prune the search space. Experimental results show that this method consistently outperforms black-box search in nearly all settings, achieving higher revenues and better winning frequencies.
Complexity and Robustness
There is a notable trade-off regarding model complexity. While deeper regression trees offer higher predictive accuracy, they generate more ILP constraints, increasing computational difficulty. Interestingly, LASSO (linear) models often yielded better optimization results than complex trees. Trees have sharp decision boundaries that optimizers can sometimes "exploit" to find unrealistically high-revenue solutions (optimization overfitting). Linear models provide smoother gradients, leading to more reliable solutions.
Computational Complexity
The authors formally proved that the Optimal Ordering for Sequential Auctions (OOSA) problem is NP-hard, even when using these learned predictors. This justifies the use of sophisticated ILP solvers and heuristic search methods.
Conclusion and Future Work
While the white-box ILP approach is powerful, it faces challenges such as optimization overestimation—where the solver finds "loopholes" in the model—and scalability issues as the number of items increases. Future research will focus on Robust Optimization to account for model uncertainty and testing the framework on real-world auction data with more complex valuation functions.
Summary updated