1 Search Results for "Juhos, Attila"


Document
Pairwise Preferences in the Stable Marriage Problem

Authors: Ágnes Cseh and Attila Juhos

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability - weak, strong and super-stability - under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.

Cite as

Ágnes Cseh and Attila Juhos. Pairwise Preferences in the Stable Marriage Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{cseh_et_al:LIPIcs.STACS.2019.21,
  author =	{Cseh, \'{A}gnes and Juhos, Attila},
  title =	{{Pairwise Preferences in the Stable Marriage Problem}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.21},
  URN =		{urn:nbn:de:0030-drops-102603},
  doi =		{10.4230/LIPIcs.STACS.2019.21},
  annote =	{Keywords: stable marriage, intransitivity, acyclic preferences, poset, weakly stable matching, strongly stable matching, super stable matching}
}
  • Refine by Author
  • 1 Cseh, Ágnes
  • 1 Juhos, Attila

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 acyclic preferences
  • 1 intransitivity
  • 1 poset
  • 1 stable marriage
  • 1 strongly stable matching
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail