Multi-agent Reinforcement Learning for Decentralized Stable Matching
- URL: http://arxiv.org/abs/2005.01117v3
- Date: Sat, 4 Dec 2021 00:43:42 GMT
- Title: Multi-agent Reinforcement Learning for Decentralized Stable Matching
- Authors: Kshitija Taywade, Judy Goldsmith, Brent Harrison
- Abstract summary: In the real world, people/entities usually find matches independently and autonomously, such as finding jobs, partners, roommates, etc.
It is possible that this search for matches starts with no initial knowledge of the environment.
We propose the use of a multi-agent reinforcement learning paradigm for a spatially formulated decentralized two-sided matching market.
- Score: 13.563394785448192
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the real world, people/entities usually find matches independently and
autonomously, such as finding jobs, partners, roommates, etc. It is possible
that this search for matches starts with no initial knowledge of the
environment. We propose the use of a multi-agent reinforcement learning (MARL)
paradigm for a spatially formulated decentralized two-sided matching market
with independent and autonomous agents. Having autonomous agents acting
independently makes our environment very dynamic and uncertain. Moreover,
agents lack the knowledge of preferences of other agents and have to explore
the environment and interact with other agents to discover their own
preferences through noisy rewards. We think such a setting better approximates
the real world and we study the usefulness of our MARL approach for it. Along
with conventional stable matching case where agents have strictly ordered
preferences, we check the applicability of our approach for stable matching
with incomplete lists and ties. We investigate our results for stability, level
of instability (for unstable results), and fairness. Our MARL approach mostly
yields stable and fair outcomes.
Related papers
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
Two-sided matching markets describe a class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences.
We exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions.
arXiv Detail & Related papers (2024-10-06T06:47:53Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward.
We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy.
We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
arXiv Detail & Related papers (2023-08-29T18:18:21Z) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees.
We study this question in a general framework for interactive decision making with multiple agents.
We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
arXiv Detail & Related papers (2023-05-01T06:46:22Z) - Efficient Model-based Multi-agent Reinforcement Learning via Optimistic
Equilibrium Computation [93.52573037053449]
H-MARL (Hallucinated Multi-Agent Reinforcement Learning) learns successful equilibrium policies after a few interactions with the environment.
We demonstrate our approach experimentally on an autonomous driving simulation benchmark.
arXiv Detail & Related papers (2022-03-14T17:24:03Z) - The Dichotomous Affiliate Stable Matching Problem: Approval-Based
Matching with Applicant-Employer Relations [27.388757379210034]
We introduce the Dichotomous Affiliate Stable Matching (DASM) Problem, where agents' preferences indicate dichotomous acceptance or rejection of another agent in the marketplace.
Our results are threefold: (1) we use a human study to show that real-world matching rankings follow our assumed valuation function; (2) we prove that there always exists a stable solution by providing an efficient, easily-implementable algorithm that finds such a solution; and (3) we experimentally validate the efficiency of our algorithm versus a linear-programming-based approach.
arXiv Detail & Related papers (2022-02-22T18:56:21Z) - Convergence Rates of Average-Reward Multi-agent Reinforcement Learning
via Randomized Linear Programming [41.30044824711509]
We focus on the case that the global reward is a sum of local rewards, the joint policy factorizes into agents' marginals, and full state observability.
We develop multi-agent extensions, whereby agents solve their local saddle point problems and then perform local weighted averaging.
We establish that the sample complexity to obtain near-globally optimal solutions matches tight dependencies on the cardinality of the state and action spaces.
arXiv Detail & Related papers (2021-10-22T03:48:41Z) - 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) - 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) - Learning to Incentivize Other Learning Agents [73.03133692589532]
We show how to equip RL agents with the ability to give rewards directly to other agents, using a learned incentive function.
Such agents significantly outperform standard RL and opponent-shaping agents in challenging general-sum Markov games.
Our work points toward more opportunities and challenges along the path to ensure the common good in a multi-agent future.
arXiv Detail & Related papers (2020-06-10T20:12:38Z) - Individual specialization in multi-task environments with multiagent
reinforcement learners [0.0]
There is a growing interest in Multi-Agent Reinforcement Learning (MARL) as the first steps towards building general intelligent agents.
Previous results point us towards increased conditions for coordination, efficiency/fairness, and common-pool resource sharing.
We further study coordination in multi-task environments where several rewarding tasks can be performed and thus agents don't necessarily need to perform well in all tasks, but under certain conditions may specialize.
arXiv Detail & Related papers (2019-12-29T15:20:24Z)
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.