Multi-agent Reinforcement Learning for Decentralized Stable Matching

Kshitija Taywade, Judy Goldsmith, Brent Harrison

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

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.

Original languageEnglish
Title of host publicationAlgorithmic Decision Theory - 7th International Conference, ADT 2021, Proceedings
EditorsDimitris Fotakis, David Ríos Insua
Pages375-389
Number of pages15
DOIs
StatePublished - 2021
Event7th International Conference on Algorithmic Decision Theory, ADT 2021 - Toulouse, France
Duration: Nov 3 2021Nov 5 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13023 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on Algorithmic Decision Theory, ADT 2021
Country/TerritoryFrance
CityToulouse
Period11/3/2111/5/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

  • Decentralized system
  • Multi-agent reinforcement learning
  • Stable matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Multi-agent Reinforcement Learning for Decentralized Stable Matching'. Together they form a unique fingerprint.

Cite this