価格、入札、価値：すべての問題を解決する ML 駆動型組合せ入札のすべて

arXiv:2411.09355v3 Announce Type: replace-cross 要旨: 本稿では、反復組合せ入札 (ICAs) の設計について研究します。この分野の主要な課題は、アイテムの数が増えるにつれて束の空間が指数関数的に増大することにあります。これを解決するために、最近の研究では、効率を最大化するために入札者から最も重要な情報のみを集めることを目指す、機械学習 (ML) に基づく偏好提起アルゴリズムが提案されています。しかしながら、現在の SOTA の ML に基づくアルゴリズムは価値クエリを用いて入札者の偏好を提起するのに対し、実際応用に用いられる ICAs は情報提起において extbf{要求クエリ} を用います。本稿では、価値クエリと要求クエリからの両方の完全な情報を活用することを証明する新しい ML アルゴリズムを導入し、実験を通じて両方のクエリタイプを組み合わせることで実際において学習性能が劇的に向上することを示します。これらの洞察に基づき、本稿では価値クエリと要求クエリを用いる新しい ML 駆動型入札 MLHCA を提示します。MLHCA は以前の SOTA を大幅に凌駕し、効率の損失を最大 10 倍に削減し、最大 58 extbackslash 回もクエリ数を削減します。つまり、MLHCA は大きな効率改善を実現すると同時に入札者の知覚負荷を低減させ、実現可能性と効率に関する新しい基準を確立しました。当社のコードは https://github.com/marketdesignresearch/MLHCA に利用可能です。

arXiv:2411.09355v3 Announce Type: replace-cross Abstract: We study the design of iterative combinatorial auctions (ICAs). The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, recent work has proposed machine learning (ML)-based preference elicitation algorithms that aim to elicit only the most critical information from bidders to maximize efficiency. However, while the SOTA ML-based algorithms elicit bidders' preferences via value queries, ICAs that are used in practice elicit information via \emph{demand queries}. In this paper, we introduce a novel ML algorithm that provably makes use of the full information from both value and demand queries, and we show via experiments that combining both query types results in significantly better learning performance in practice. Building on these insights, we present MLHCA, a new ML-powered auction that uses value and demand queries. MLHCA significantly outperforms the previous SOTA, reducing efficiency loss by up to a factor 10, with up to 58\% fewer queries. Thus, MLHCA achieves large efficiency improvements while also reducing bidders' cognitive load, establishing a new benchmark for both practicability and efficiency. Our code is available at https://github.com/marketdesignresearch/MLHCA.