A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling

• URL: http://arxiv.org/abs/2010.05519v1
• Date: Mon, 12 Oct 2020 08:20:35 GMT
• Title: A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling
• Authors: Xiaotie Deng, Ron Lavi, Tao Lin, Qi Qi, Wenwei Wang, Xiang Yan
• Abstract summary: 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.
• Score: 19.453243313852557
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Empirical Revenue Maximization (ERM) is one of the most important price learning algorithms in auction design: as the literature shows it can learn approximately optimal reserve prices for revenue-maximizing auctioneers in both repeated auctions and uniform-price auctions. However, in these applications the agents who provide inputs to ERM have incentives to manipulate the inputs to lower the outputted price. We generalize the definition of an incentive-awareness measure proposed by Lavi et al (2019), to quantify the reduction of ERM's outputted price due to a change of $m\ge 1$ out of $N$ input samples, and provide specific convergence rates of this measure to zero as $N$ goes to infinity for different types of input distributions. By adopting this measure, 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.

Related papers

• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
  arXiv  Detail & Related papers  (2024-05-31T19:26:05Z)
• Conformal Online Auction Design [6.265829744417118]
  COAD incorporates both the bidder and item features to provide an incentive-compatible mechanism for online auctions. It employs a distribution-free, prediction interval-based approach using conformal prediction techniques. COAD admits the use of a broad array of modern machine-learning methods, including random forests, kernel methods, and deep neural nets.
  arXiv  Detail & Related papers  (2024-05-11T15:28:25Z)
• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. We propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP) We show that LOOP achieves a sublinear $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret, where $d$ and $beta$ correspond to AGEC and log-covering number of the hypothesis class respectively
  arXiv  Detail & Related papers  (2024-04-19T06:24:22Z)
• Machine Learning-Powered Combinatorial Clock Auction [13.724491757145385]
  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.
  arXiv  Detail & Related papers  (2023-08-20T10:43:50Z)
• Robust multi-item auction design using statistical learning: Overcoming uncertainty in bidders' types distributions [6.5920927560926295]
  Our proposed approach utilizes nonparametric density estimation to accurately estimate bidders' types from historical bids. To further enhance efficiency of our mechanism, we introduce two novel strategies for query reduction. Simulation experiments conducted on both small-scale and large-scale data demonstrate that our mechanism consistently outperforms existing methods in terms of revenue design and query reduction.
  arXiv  Detail & Related papers  (2023-02-02T08:32:55Z)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  An auction mechanism that maximizes the auctioneer's revenue while minimizes bidders' ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks.
  arXiv  Detail & Related papers  (2022-10-11T16:13:25Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. We propose new algorithms that can learn a mechanism whose revenue is nearly optimal simultaneously for all true distributions'' that are $alpha$-close to the original distribution in Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2021-07-13T17:37:21Z)
• 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)
• Reserve Price Optimization for First Price Auctions [14.18752189817994]
  We propose a gradient-based algorithm to adaptively update and optimize reserve prices based on estimates of bidders' responsiveness to experimental shocks in reserves. We show that revenue in a first-price auction can be usefully decomposed into a emphdemand component and a emphbidding component, and introduce techniques to reduce the variance of each component.
  arXiv  Detail & Related papers  (2020-06-11T15:35:19Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

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.