  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.
