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
- Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
We consider a problem where an auctioneer sells an indivisible good to two 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) - Value Variance Minimization for Learning Approximate Equilibrium in
Aggregation Systems [8.140037969280716]
We consider the problem of learning approximate equilibrium solutions (win-win) in aggregation systems.
In this paper, we consider the problem of learning approximate equilibrium solutions (win-win) in aggregation systems so that individuals have an incentive to remain in the aggregation system.
arXiv Detail & Related papers (2020-03-16T10:02:42Z) - 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.