Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms

• URL: http://arxiv.org/abs/1705.00243v6
• Date: Sat, 6 May 2023 23:00:00 GMT
• Title: Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms
• Authors: Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
• Abstract summary: 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.
• Score: 86.81403511861788
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study multi-item profit maximization when there is an underlying distribution over buyers' values. In practice, a full description of the distribution is typically unavailable, so we study the setting where the mechanism designer only has samples from the distribution. If the designer uses the samples to optimize over a complex mechanism class -- such as the set of all multi-item, multi-buyer mechanisms -- a mechanism may have high average profit over the samples but low expected profit. This raises the central question of this paper: how many samples are sufficient to ensure that a mechanism's average profit is close to its expected profit? To answer this question, we uncover structure shared by many pricing, auction, and lottery mechanisms: for any set of buyers' values, profit is piecewise linear in the mechanism's parameters. Using this structure, we prove new bounds for mechanism classes not yet studied in the sample-based mechanism design literature and match or improve over the best-known guarantees for many classes.

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)
• Optimal Automated Market Makers: Differentiable Economics and Strong Duality [22.943723387429678]
  Optimal market making in the presence of multiple goods is not well understood. We show that finding an optimal market maker is dual to an optimal transport problem. We present conjectures of optimal mechanisms in settings which show further complex behavior.
  arXiv  Detail & Related papers  (2024-02-14T12:27:54Z)
• 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)
• 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)
• Automated Mechanism Design for Classification with Partial Verification [64.69418921224529]
  We study the problem of automated mechanism design with partial verification. We focus on truthful mechanisms in the setting where all types share the same preference over outcomes.
  arXiv  Detail & Related papers  (2021-04-12T03:29:31Z)
• 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.