Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning

• URL: http://arxiv.org/abs/2402.19420v2
• Date: Tue, 23 Jul 2024 19:15:44 GMT
• Title: Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning
• Authors: Greg d'Eon, Neil Newman, Kevin Leyton-Brown,
• Abstract summary: We investigate whether multi-agent reinforcement learning algorithms can be used to understand iterative auctions. We find that MARL can indeed benefit auction analysis, but that deploying it effectively is nontrivial. We illustrate the promise of our resulting approach by using it to evaluate a specific rule change to a clock auction.
• Score: 10.41350502488723
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Iterative combinatorial auctions are widely used in high stakes settings such as spectrum auctions. Such auctions can be hard to analyze, making it difficult for bidders to determine how to behave and for designers to optimize auction rules to ensure desirable outcomes such as high revenue or welfare. In this paper, we investigate whether multi-agent reinforcement learning (MARL) algorithms can be used to understand iterative combinatorial auctions, given that these algorithms have recently shown empirical success in several other domains. We find that MARL can indeed benefit auction analysis, but that deploying it effectively is nontrivial. We begin by describing modelling decisions that keep the resulting game tractable without sacrificing important features such as imperfect information or asymmetry between bidders. We also discuss how to navigate pitfalls of various MARL algorithms, how to overcome challenges in verifying convergence, and how to generate and interpret multiple equilibria. We illustrate the promise of our resulting approach by using it to evaluate a specific rule change to a clock auction, finding substantially different auction outcomes due to complex changes in bidders' behavior.

Related papers

• Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
  We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. Our goal is to design computationally efficient auctions that maximize the difference between the quality of the acquired services and the total cost of the sellers.
  arXiv  Detail & Related papers  (2024-11-20T18:06:55Z)
• Approximating Auction Equilibria with Reinforcement Learning [0.0]
  This paper introduces a self-play based reinforcement learning approach that employs advanced algorithms to approximate Bayes-Nash equilibria. Through self-play, these algorithms can learn robust and near-optimal bidding strategies in auctions with known equilibria.
  arXiv  Detail & Related papers  (2024-10-17T18:34:57Z)
• Deep Reinforcement Learning for Sequential Combinatorial Auctions [40.89021064082742]
  Revenue-optimal auction design is a challenging problem with significant theoretical and practical implications. We propose a new reinforcement learning framework tailored for sequential auctions that leverages first-order gradients. Our approach achieves significant improvement in revenue over both analytical baselines and standard reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2024-07-10T20:00:22Z)
• Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
  We study the problem of bidding strategies in pay-as-bid (PAB) auctions from the perspective of single bidder. We show that a utility trick enables a time algorithm to solve the offline problem where competing bids are known in advance. We also present additional findings on the characterization of PAB equilibria.
  arXiv  Detail & Related papers  (2023-07-27T20:49:28Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  We study a game between autobidding algorithms that compete in an online advertising platform. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret.
  arXiv  Detail & Related papers  (2023-01-30T21:59:30Z)
• A Context-Integrated Transformer-Based Neural Network for Auction Design [25.763612577196124]
  One of the central problems in auction design is developing an incentive-compatible mechanism that maximizes the auctioneer's expected revenue. We propose $mathttCITransNet$, a context-integrated transformer-based neural network for optimal auction design. We show by extensive experiments that $mathttCITransNet$ can recover the known optimal solutions in single-item settings, outperform strong baselines in multi-item auctions, and generalize well to cases other than those in training.
  arXiv  Detail & Related papers  (2022-01-29T03:47:00Z)
• MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning [65.52675802289775]
  We show that an uncertainty aware classifier can solve challenging reinforcement learning problems. We propose a novel method for computing the normalized maximum likelihood (NML) distribution. We show that the resulting algorithm has a number of intriguing connections to both count-based exploration methods and prior algorithms for learning reward functions.
  arXiv  Detail & Related papers  (2021-07-15T08:19:57Z)
• Learning Revenue-Maximizing Auctions With Differentiable Matching [50.62088223117716]
  We propose a new architecture to approximately learn incentive compatible, revenue-maximizing auctions from sampled valuations. Our architecture uses the Sinkhorn algorithm to perform a differentiable bipartite matching which allows the network to learn strategyproof revenue-maximizing mechanisms.
  arXiv  Detail & Related papers  (2021-06-15T04:37:57Z)
• Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising [42.7415188090209]
  We develop deep models to efficiently extract contexts from auctions, providing rich features for auction design. DNAs have been successfully deployed in the e-commerce advertising system at Taobao.
  arXiv  Detail & Related papers  (2021-06-07T13:20:40Z)
• ProportionNet: Balancing Fairness and Revenue for Auction Design with Deep Learning [55.76903822619047]
  We study the design of revenue-maximizing auctions with strong incentive guarantees. We extend techniques for approximating auctions using deep learning to address concerns of fairness while maintaining high revenue and strong incentive guarantees.
  arXiv  Detail & Related papers  (2020-10-13T13:54:21Z)
• Learning to Infer User Hidden States for Online Sequential Advertising [52.169666997331724]
  We propose our Deep Intents Sequential Advertising (DISA) method to address these issues. The key part of interpretability is to understand a consumer's purchase intent which is, however, unobservable (called hidden states)
  arXiv  Detail & Related papers  (2020-09-03T05:12:26Z)

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.