DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2024.30

Fast, Fair and Truthful Distributed Stable Matching for Common Preferences

Authors: Juho Hirvonen and Sara Ranjbaran

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract

Stable matching is a fundamental problem studied both in economics and computer science. The task is to find a matching between two sides of agents that have preferences over who they want to be matched with. A matching is stable if no pair of agents prefer each other over their current matches. The deferred acceptance algorithm of Gale and Shapley solves this problem in polynomial time. Further, it is a mechanism: the proposing side in the algorithm is always incentivised to report their preferences truthfully. The deferred acceptance algorithm has a natural interpretation as a distributed algorithm (and thus a distributed mechanism). However, the algorithm is slow in the worst case and it is known that the stable matching problem cannot be solved efficiently in the distributed setting. In this work we study a natural special case of the stable matching problem where all agents on one of the two sides share common preferences. We show that in this case the deferred acceptance algorithm does yield a fast and truthful distributed mechanism for finding a stable matching. We show how algorithms for sampling random colorings can be used to break ties fairly and extend the results to fractional stable matching.

Cite as

Juho Hirvonen and Sara Ranjbaran. Fast, Fair and Truthful Distributed Stable Matching for Common Preferences. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hirvonen_et_al:LIPIcs.OPODIS.2024.30,
  author =	{Hirvonen, Juho and Ranjbaran, Sara},
  title =	{{Fast, Fair and Truthful Distributed Stable Matching for Common Preferences}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.30},
  URN =		{urn:nbn:de:0030-drops-225666},
  doi =		{10.4230/LIPIcs.OPODIS.2024.30},
  annote =	{Keywords: stable matching, deferred acceptance, local algorithm, mechanism design}
}

Search Results

Documents authored by Ranjbaran, Sara

Fast, Fair and Truthful Distributed Stable Matching for Common Preferences

Abstract

Cite as

Thanks for your feedback!

Could not send message