Deep Learning for Two-Sided Matching
- URL: http://arxiv.org/abs/2107.03427v2
- Date: Wed, 15 Nov 2023 00:01:54 GMT
- Title: Deep Learning for Two-Sided Matching
- Authors: Sai Srivatsa Ravindranath, Zhe Feng, Shira Li, Jonathan Ma, Scott D.
Kominers, David C. Parkes
- Abstract summary: 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.
- Score: 14.571017168011725
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We initiate the study of deep learning for the automated design of two-sided
matching mechanisms. What is of most interest is to use machine learning to
understand the possibility of new tradeoffs between strategy-proofness and
stability. These properties cannot be achieved simultaneously, but the
efficient frontier is not understood. We introduce novel differentiable
surrogates for quantifying ordinal strategy-proofness and stability and use
them to train differentiable matching mechanisms that map discrete preferences
to valid randomized matchings. We demonstrate that the efficient frontier
characterized by these learned mechanisms is substantially better than that
achievable through a convex combination of baselines of deferred acceptance
(stable and strategy-proof for only one side of the market), top trading cycles
(strategy-proof for one side, but not stable), and randomized serial
dictatorship (strategy-proof for both sides, but not stable). This gives a new
target for economic theory and opens up new possibilities for machine learning
pipelines in matching market design.
Related papers
- Learning Neural Strategy-Proof Matching Mechanism from Examples [24.15688619889342]
We develop a novel attention-based neural network called NeuralSD, which can learn a strategy-proof mechanism from a human-crafted dataset.
We conducted experiments to learn a strategy-proof matching from matching examples with different numbers of agents.
arXiv Detail & Related papers (2024-10-25T08:34:25Z) - Deviations from the Nash equilibrium and emergence of tacit collusion in a two-player optimal execution game with reinforcement learning [0.9208007322096533]
We study a scenario in which two autonomous agents learn to liquidate the same asset optimally in the presence of market impact.
Our results show that the strategies learned by the agents deviate significantly from the Nash equilibrium of the corresponding market impact game.
We explore how different levels of market volatility influence the agents' performance and the equilibria they discover.
arXiv Detail & Related papers (2024-08-21T16:54:53Z) - Learning to Maximize Gains From Trade in Small Markets [6.204762177970342]
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.
arXiv Detail & Related papers (2024-01-21T20:57:12Z) - Exploiting hidden structures in non-convex games for convergence to Nash
equilibrium [62.88214569402201]
A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria.
We provide explicit convergence guarantees for both deterministic and deterministic environments.
arXiv Detail & Related papers (2023-12-27T15:21:25Z) - Practical Approaches for Fair Learning with Multitype and Multivariate
Sensitive Attributes [70.6326967720747]
It is important to guarantee that machine learning algorithms deployed in the real world do not result in unfairness or unintended social consequences.
We introduce FairCOCCO, a fairness measure built on cross-covariance operators on reproducing kernel Hilbert Spaces.
We empirically demonstrate consistent improvements against state-of-the-art techniques in balancing predictive power and fairness on real-world datasets.
arXiv Detail & Related papers (2022-11-11T11:28:46Z) - Decorrelative Network Architecture for Robust Electrocardiogram
Classification [4.808817930937323]
It is not possible to train networks that are accurate in all scenarios.
Deep learning methods sample the model parameter space to estimate uncertainty.
These parameters are often subject to the same vulnerabilities, which can be exploited by adversarial attacks.
We propose a novel ensemble approach based on feature decorrelation and Fourier partitioning for teaching networks diverse complementary features.
arXiv Detail & Related papers (2022-07-19T02:36:36Z) - 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) - 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 from History for Byzantine Robust Optimization [52.68913869776858]
Byzantine robustness has received significant attention recently given its importance for distributed learning.
We show that most existing robust aggregation rules may not converge even in the absence of any Byzantine attackers.
arXiv Detail & Related papers (2020-12-18T16:22:32Z) - Hidden Cost of Randomized Smoothing [72.93630656906599]
In this paper, we point out the side effects of current randomized smoothing.
Specifically, we articulate and prove two major points: 1) the decision boundaries of smoothed classifiers will shrink, resulting in disparity in class-wise accuracy; 2) applying noise augmentation in the training process does not necessarily resolve the shrinking issue due to the inconsistent learning objectives.
arXiv Detail & Related papers (2020-03-02T23:37:42Z)
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.