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 as 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.
翻译:我们研究的是组合分配域,其中包括组合拍卖和课程分配。 该领域的主要挑战是捆绑空间在项目数量上成倍增长。 为了解决这个问题,一些论文最近提议了机械学习法的优惠诱导算法,目的是只从代理商那里获取最重要的信息。 然而,先前这项工作的主要缺点是,它没有模拟一个机制对于尚未提取的捆绑的数值的不确定性。在本文件中,我们通过展示一个以巴耶西亚优化为基础的组合分配(BOCA)机制来解决这一缺陷。我们的主要技术贡献是将一种捕捉模型不确定性的方法纳入一个迭接组合拍卖机制。具体地说,我们设计了一种新的方法来估计一个上限的不确定性,可以用作获取功能来决定对代理商的下一个查询。这使得该机制能够在其优惠征求阶段适当探索(而不是仅仅利用)捆绑的空间。我们在几个频谱拍卖域进行计算实验,以评估BOCA的绩效。我们的结果显示,BOCACO取得了比州-艺术方法更高的分配效率。