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
- 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 consider the problem of learning how to bid in repeated multi-unit pay-as-bid auctions.
The problem of learning how to bid in pay-as-bid auctions is challenging according to the nature of the action space.
We show that the optimal solution to the offline problem can be obtained using a time dynamic programming scheme.
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) - Softmax with Regularization: Better Value Estimation in Multi-Agent
Reinforcement Learning [72.28520951105207]
Overestimation in $Q$-learning is an important problem that has been extensively studied in single-agent reinforcement learning.
We propose a novel regularization-based update scheme that penalizes large joint action-values deviating from a baseline.
We show that our method provides a consistent performance improvement on a set of challenging StarCraft II micromanagement tasks.
arXiv Detail & Related papers (2021-03-22T14:18:39Z) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
We develop efficient sequential bidding strategies for repeated auctions.
We provide the first parametric lower bound for this problem.
We propose more explainable strategies which are reminiscent of the Explore Then Commit bandit algorithm.
arXiv Detail & Related papers (2020-11-10T12:45:02Z) - 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.