New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs

• URL: http://arxiv.org/abs/2302.11700v3
• Date: Mon, 15 Jul 2024 21:29:02 GMT
• Title: New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs
• Authors: Maria-Florina Balcan, Hedyeh Beyhaghi,
• Abstract summary: We study the learnability of two classes of mechanisms prominent in economics, namely menus of lotteries and two-part tariffs. We provide the first online learning algorithms for menus of lotteries and two-part tariffs with strong regret-bound guarantees.
• Score: 19.34580414545524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We advance a recently flourishing line of work at the intersection of learning theory and computational economics by studying the learnability of two classes of mechanisms prominent in economics, namely menus of lotteries and two-part tariffs. The former is a family of randomized mechanisms designed for selling multiple items, known to achieve revenue beyond deterministic mechanisms, while the latter is designed for selling multiple units (copies) of a single item with applications in real-world scenarios such as car or bike-sharing services. We focus on learning high-revenue mechanisms of this form from buyer valuation data in both distributional settings, where we have access to buyers' valuation samples up-front, and the more challenging and less-studied online settings, where buyers arrive one-at-a-time and no distributional assumption is made about their values. We provide a suite of results with regard to these two families of mechanisms. We provide the first online learning algorithms for menus of lotteries and two-part tariffs with strong regret-bound guarantees. Since the space of parameters is infinite and the revenue functions have discontinuities, the known techniques do not readily apply. However, we are able to provide a reduction to online learning over a finite number of experts, in our case, a finite number of parameters. Furthermore, in the limited buyers type case, we show a reduction to online linear optimization, which allows us to obtain no-regret guarantees by presenting buyers with menus that correspond to a barycentric spanner. In addition, we provide algorithms with improved running times over prior work for the distributional settings. Finally, we demonstrate how techniques from the recent literature in data-driven algorithm design are insufficient for our studied problems.

Related papers

• Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
  Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and a brand) This problem captures, for example, situations where a merchant and a brand bid cooperatively in an auction to advertise a product, and both benefit from the ad being shown. A mechanism collects bids from the two and decides whether to allocate and which payments the two parties should make.
  arXiv  Detail & Related papers  (2024-09-12T07:59:10Z)
• A Primal-Dual Online Learning Approach for Dynamic Pricing of Sequentially Displayed Complementary Items under Sale Constraints [54.46126953873298]
  We address the problem of dynamically pricing complementary items that are sequentially displayed to customers. Coherent pricing policies for complementary items are essential because optimizing the pricing of each item individually is ineffective. We empirically evaluate our approach using synthetic settings randomly generated from real-world data, and compare its performance in terms of constraints violation and regret.
  arXiv  Detail & Related papers  (2024-07-08T09:55:31Z)
• Learning-augmented Online Algorithm for Two-level Ski-rental Problem [8.381344684943212]
  We study the two-level ski-rental problem,where a user needs to fulfill a sequence of demands for multiple items by choosing one of three payment options. We develop a learning-augmented algorithm (LADTSR) by integrating Machine Learning predictions into the robust online algorithm.
  arXiv  Detail & Related papers  (2024-02-09T16:10: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)
• 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)
• Faithful Edge Federated Learning: Scalability and Privacy [4.8534377897519105]
  Federated learning enables machine learning algorithms to be trained over a network of decentralized edge devices without requiring the exchange of local datasets. We analyze how the key feature of federated learning, unbalanced and non-i.i.d. data, affects agents' incentives to voluntarily participate. We design two faithful federated learning mechanisms which satisfy economic properties, scalability, and privacy.
  arXiv  Detail & Related papers  (2021-06-30T08:46:40Z)
• 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)
• Certifying Strategyproof Auction Networks [53.37051312298459]
  We focus on the RegretNet architecture, which can represent auctions with arbitrary numbers of items and participants. We propose ways to explicitly verify strategyproofness under a particular valuation profile using techniques from the neural network verification literature.
  arXiv  Detail & Related papers  (2020-06-15T20:22:48Z)
• 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.