# Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming

arXiv: https://arxiv.org/abs/2002.08841 · HTML: https://mlsanity.com/paper/2002.08841/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2020.

## Built on by (most cited first, 6 of 6)

- [Modeling the AC Power Flow Equations with Optimally Compact Neural Networks: Application to Unit Commitment](https://mlsanity.com/paper/2110.11269/) (2021)
- [Closing the Loop: A Framework for Trustworthy Machine Learning in Power Systems](https://mlsanity.com/paper/2203.07505/) (2022)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Loss Functions for Discrete Contextual Pricing with Observational Data](https://mlsanity.com/paper/2111.09933/) (2021)
- [Tackling Provably Hard Representative Selection via Graph Neural Networks](https://mlsanity.com/paper/2205.10403/) (2022)
- [Convex Surrogate Loss Functions for Contextual Pricing with Transaction Data](https://mlsanity.com/paper/2202.10944/) (2022)

## Abstract (arXiv)

We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. First, we show that it is not possible to solve this problem in polynomial time unless the Exponential Time Hypothesis fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. Moreover, we show that this MIP formulation is ideal (i.e. the strongest possible formulation) for the revenue function of a single impression. Since it can be computationally expensive to exactly solve the MIP formulation in practice, we also study the performance of its linear programming (LP) relaxation. Though it may work well in practice, we show that, unfortunately, in the worst case the optimal objective of the LP relaxation can be O(number of samples) times larger than the optimal objective of the true problem. Finally, we present computational results, showcasing that the MIP formulation, along with its LP relaxation, are able to achieve superior in- and out-of-sample performance, as compared to state-of-the-art algorithms on both real and synthetic datasets. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems.