Machine Learning-Powered Combinatorial Clock Auction

• URL: http://arxiv.org/abs/2308.10226v2
• Date: Thu, 28 Mar 2024 15:53:48 GMT
• Title: Machine Learning-Powered Combinatorial Clock Auction
• Authors: Ermis Soumalias, Jakob Weissteiner, Jakob Heiss, Sven Seuken,
• Abstract summary: We study the design of iterative auctions (ICAs) We present a novel method for training an ML model on demand queries. We experimentally evaluate our ML-based demand mechanism in several spectrum auction domains.
• Score: 13.724491757145385
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, several papers have recently proposed machine learning (ML)-based preference elicitation algorithms that aim to elicit only the most important information from bidders. However, from a practical point of view, the main shortcoming of this prior work is that those designs elicit bidders' preferences via value queries (i.e., ``What is your value for the bundle $\{A,B\}$?''). In most real-world ICA domains, value queries are considered impractical, since they impose an unrealistically high cognitive burden on bidders, which is why they are not used in practice. In this paper, we address this shortcoming by designing an ML-powered combinatorial clock auction that elicits information from the bidders only via demand queries (i.e., ``At prices $p$, what is your most preferred bundle of items?''). We make two key technical contributions: First, we present a novel method for training an ML model on demand queries. Second, based on those trained ML models, we introduce an efficient method for determining the demand query with the highest clearing potential, for which we also provide a theoretical foundation. We experimentally evaluate our ML-based demand query mechanism in several spectrum auction domains and compare it against the most established real-world ICA: the combinatorial clock auction (CCA). Our mechanism significantly outperforms the CCA in terms of efficiency in all domains, it achieves higher efficiency in a significantly reduced number of rounds, and, using linear prices, it exhibits vastly higher clearing potential. Thus, with this paper we bridge the gap between research and practice and propose the first practical ML-powered ICA.

Related papers

• Automated Deterministic Auction Design with Objective Decomposition [31.918952529696885]
  This paper introduces OD-VVCA, an objective decomposition approach for automated designing Virtual Valuations Combinatorial Auctions (VVCAs) We utilize a parallelizable dynamic programming algorithm to compute the allocation and revenue outcomes of a VVCA efficiently. We then decompose the revenue objective function into continuous and piecewise constant discontinuous components, optimizing each using distinct methods.
  arXiv  Detail & Related papers  (2024-02-19T07:45:04Z)
• Reinforcement Learning from Human Feedback with Active Queries [67.27150911254155]
  Current reinforcement learning approaches often require a large amount of human-labelled preference data. We propose query-efficient RLHF methods, inspired by the success of active learning. Our experiments show that ADPO, while only making about half of queries for human preference, matches the performance of the state-of-the-art DPO method.
  arXiv  Detail & Related papers  (2024-02-14T18:58:40Z)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
  arXiv  Detail & Related papers  (2023-10-11T20:34:17Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Bayesian Optimization-based Combinatorial Assignment [10.73407470973258]
  We study the assignment domain, which includes auctions and course allocation. The main challenge in this domain is that the bundle space grows exponentially in the number of items.
  arXiv  Detail & Related papers  (2022-08-31T08:47:02Z)
• Should All Proposals be Treated Equally in Object Detection? [110.27485090952385]
  The complexity-precision trade-off of an object detector is a critical problem for resource constrained vision tasks. It is hypothesized that improved detection efficiency requires a paradigm shift, towards the unequal processing of proposals. This results in better utilization of available computational budget, enabling higher accuracy for the same FLOPS.
  arXiv  Detail & Related papers  (2022-07-07T18:26:32Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. We show how to achieve significantly lower regret when the opponents' maximal bid distribution is known. Our algorithms converge much faster than alternatives proposed in the literature for various bid distributions.
  arXiv  Detail & Related papers  (2021-07-05T07:48:52Z)
• Online Learning of Competitive Equilibria in Exchange Economies [94.24357018178867]
  In economics, the sharing of scarce resources among multiple rational agents is a classical problem. We propose an online learning mechanism to learn agent preferences. We demonstrate the effectiveness of this mechanism through numerical simulations.
  arXiv  Detail & Related papers  (2021-06-11T21:32:17Z)
• A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling [19.453243313852557]
  Empirical Revenue Maximization (ERM) is one of the most important price learning algorithms in auction design. We generalize the definition of an incentive-awareness measure proposed by Lavi et al to quantify the reduction of ERM's outputted price due to a change of $mge 1$ out of $N$ input samples. We construct an efficient, approximately incentive-compatible, and revenue-optimal learning algorithm using ERM in repeated auctions against non-myopic bidders, and show approximate group incentive-compatibility in uniform-price auctions.
  arXiv  Detail & Related papers  (2020-10-12T08:20:35Z)
• Auction learning as a two-player game [19.706363403596196]
  Auction Design is a two-player game with stationary utility functions. Design an incentive that maximizes expected revenue is a central problem in Auction Design.
  arXiv  Detail & Related papers  (2020-06-10T06:45:20Z)
• Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms [86.81403511861788]
  We study multi-item profit when there is an underlying distribution over buyers' values. For any set of buyers' values, profit is piecewise linear in the mechanism's parameters. We prove new bounds for mechanism classes not yet in the sample-based mechanism design literature.
  arXiv  Detail & Related papers  (2017-04-29T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.