Learning to Maximize Gains From Trade in Small Markets

• URL: http://arxiv.org/abs/2401.11596v2
• Date: Wed, 19 Jun 2024 21:02:22 GMT
• Title: Learning to Maximize Gains From Trade in Small Markets
• Authors: Moshe Babaioff, Amitai Frey, Noam Nisan,
• Abstract summary: We study the problem of designing a two-sided market (double auction) under the constraints of (dominant-strategy) incentive compatibility and budget-balance. Our result is a general impossibility for the case of correlated distributions of values even between one seller and two buyers. Our second is an efficient learning algorithm for one seller and two buyers in the case of independent distributions.
• Score: 6.204762177970342
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of designing a two-sided market (double auction) to maximize the gains from trade (social welfare) under the constraints of (dominant-strategy) incentive compatibility and budget-balance. Our goal is to do so for an unknown distribution from which we are given a polynomial number of samples. Our first result is a general impossibility for the case of correlated distributions of values even between just one seller and two buyers, in contrast to the case of one seller and one buyer (bilateral trade) where this is possible. Our second result is an efficient learning algorithm for one seller and two buyers in the case of independent distributions which is based on a novel algorithm for computing optimal mechanisms for finitely supported and explicitly given independent distributions. Both results rely heavily on characterizations of (dominant-strategy) incentive compatible mechanisms that are strongly budget-balanced.

Related papers

• Competing Bandits in Decentralized Large Contextual Matching Markets [13.313881962771777]
  We study decentralized learning in two-sided matching markets where the demand side (aka players or agents) competes for a large' supply side (aka arms) Our proposed algorithms achieve instance-dependent logarithmic regret, scaling independently of the number of arms, $K$.
  arXiv  Detail & Related papers  (2024-11-18T18:08:05Z)
• 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)
• 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)
• New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem [34.51168440208439]
  We consider the sparse contextual bandit problem where arm feature affects reward through the inner product of sparse parameters. Recent studies have developed sparsity-agnostic algorithms based on the greedy arm selection policy.
  arXiv  Detail & Related papers  (2023-12-19T18:35:33Z)
• Towards Multi-Agent Reinforcement Learning driven Over-The-Counter Market Simulations [16.48389671789281]
  We study a game between liquidity provider and liquidity taker agents interacting in an over-the-counter market. By playing against each other, our deep-reinforcement-learning-driven agents learn emergent behaviors. We show convergence rates for our multi-agent policy gradient algorithm under a transitivity assumption.
  arXiv  Detail & Related papers  (2022-10-13T17:06:08Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  We develop a framework and algorithms for learning stable market outcomes under uncertainty. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.
  arXiv  Detail & Related papers  (2021-08-19T17:59:28Z)
• 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)
• Deep Learning for Two-Sided Matching [14.571017168011725]
  We use machine learning to understand the possibility of new tradeoffs between strategy-proofness and stability. We introduce novel differentiable surrogates for quantifying ordinal strategy-proofness and stability. We demonstrate that the efficient frontier characterized by these learned mechanisms is substantially better than that achievable.
  arXiv  Detail & Related papers  (2021-07-07T18:22:11Z)
• Multi-Stage Decentralized Matching Markets: Uncertain Preferences and Strategic Behaviors [91.3755431537592]
  This article develops a framework for learning optimal strategies in real-world matching markets. We show that there exists a welfare-versus-fairness trade-off that is characterized by the uncertainty level of acceptance. We prove that participants can be better off with multi-stage matching compared to single-stage matching.
  arXiv  Detail & Related papers  (2021-02-13T19:25:52Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)
• 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.