Bayesian Optimization-based Combinatorial Assignment
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.
Code (1)
Tasks
Bayesian OptimizationSimilar Papers 제목 키워드 기반
Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel
In this work we propose a batch Bayesian optimization method for combinatorial problems on permutations, which is well suited for expensive-to-evaluate objectives. We first introduce LAW, an efficient batch acquisition m…
Bayesian OptimizationPoint ProcessesSchedulingCombinatorial Bayesian Optimization using the Graph Cartesian Product
This paper focuses on Bayesian Optimization (BO) for objectives on combinatorial search spaces, including ordinal and categorical variables. Despite the abundance of potential applications of Combinatorial BO, including …
Bayesian OptimizationNeural Architecture SearchVariable SelectionMALBO: Optimizing LLM-Based Multi-Agent Teams via Multi-Objective Bayesian Optimization
The optimal assignment of Large Language Models (LLMs) to specialized roles in multi-agent systems is a significant challenge, defined by a vast combinatorial search space, expensive black-box evaluations, and an inheren…
Combinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytopes
Bayesian optimization is a popular method for solving the problem of global optimization of an expensive-to-evaluate black-box function. It relies on a probabilistic surrogate model of the objective function, upon which …
Bayesian Optimizationglobal-optimizationBayesian Variational Optimization for Combinatorial Spaces
This paper focuses on Bayesian Optimization in combinatorial spaces. In many applications in the natural science. Broad applications include the study of molecules, proteins, DNA, device structures and quantum circuit de…
Bayesian OptimizationGaussian Processes