# Bayesian Optimization-based Combinatorial Assignment

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 31 Aug 2022.

## Builds on (most cited first, 16 of 16)

- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Weight Uncertainty in Neural Networks](https://mlsanity.com/paper/1505.05424/) (2015)
- [Accurate Uncertainties for Deep Learning Using Calibrated Regression](https://mlsanity.com/paper/1807.00263/) (2018)
- [Probabilistic Backpropagation for Scalable Learning of Bayesian Neural Networks](https://mlsanity.com/paper/1502.05336/) (2015)
- [Hyperparameter Ensembles for Robustness and Uncertainty Quantification](https://mlsanity.com/paper/2006.13570/) (2020)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation](https://mlsanity.com/paper/1911.12809/) (2019)
- [Benchmarking the Neural Linear Model for Regression](https://mlsanity.com/paper/1912.08416/) (2019)
- [NOMU: Neural Optimization-based Model Uncertainty](https://mlsanity.com/paper/2102.13640/) (2021)
- [Constrained Discrete Black-Box Optimization using Mixed-Integer Programming](https://mlsanity.com/paper/2110.09569/) (2021)
- [Deep Learning-powered Iterative Combinatorial Auctions](https://mlsanity.com/paper/1907.05771/) (2019)
- [Machine Learning-powered Iterative Combinatorial Auctions](https://mlsanity.com/paper/1911.08042/) (2019)
- [Monotone-Value Neural Networks: Exploiting Preference Monotonicity in Combinatorial Assignment](https://mlsanity.com/paper/2109.15117/) (2021)
- [Fourier Analysis-based Iterative Combinatorial Auctions](https://mlsanity.com/paper/2009.10749/) (2020)

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

- [Accelerated Preference Elicitation with LLM-Based Proxies](https://mlsanity.com/paper/2501.14625/) (2025)
- [LLM-Powered Preference Elicitation in Combinatorial Assignment](https://mlsanity.com/paper/2502.10308/) (2025)
- [Machine Learning-Powered Combinatorial Clock Auction](https://mlsanity.com/paper/2308.10226/) (2023)
- [Machine Learning-Powered Course Allocation](https://mlsanity.com/paper/2210.00954/) (2022)
- [How (Implicit) Regularization of ReLU Neural Networks Characterizes the Learned Function -- Part II: the Multi-D Case of Two Layers with Random First Layer](https://mlsanity.com/paper/2303.11454/) (2023)
- [Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All](https://mlsanity.com/paper/2411.09355/) (2024)
- [Deep Sensitivity Analysis for Objective-Oriented Combinatorial Optimization](https://mlsanity.com/paper/2403.00016/) (2024)
- [Towards Interpreting Multi-Objective Feature Associations](https://mlsanity.com/paper/2403.00017/) (2024)
- [Grey-box Bayesian Optimization for Sensor Placement in Assisted Living Environments](https://mlsanity.com/paper/2309.05784/) (2023)

## Abstract (arXiv)

We study the combinatorial assignment domain, which includes combinatorial auctions and course allocation. The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, several papers have recently proposed machine learning-based preference elicitation algorithms that aim to elicit only the most important information from agents. However, the main shortcoming of this prior work is that it does not model a mechanism's uncertainty over values for not yet elicited bundles. In this paper, we address this shortcoming by presenting a Bayesian optimization-based combinatorial assignment (BOCA) mechanism. Our key technical contribution is to integrate a method for capturing model uncertainty into an iterative combinatorial auction mechanism. Concretely, we design a new method for estimating an upper uncertainty bound that can be used to define an acquisition function to determine the next query to the agents. This enables the mechanism to properly explore (and not just exploit) the bundle space during its preference elicitation phase. We run computational experiments in several spectrum auction domains to evaluate BOCA's performance. Our results show that BOCA achieves higher allocative efficiency than state-of-the-art approaches.