Stable matchings beyond stable marriage: models, algorithms, complexity
Creators: name: Heeger, Klaus
Publisher: name: Technische Universität Berlin
Year: 2023
Subjects: subject: 000 Informatik, Informationswissenschaft, allgemeine Werke
subject: matching under preferences
subject: parameterized complexity
subject: popular matching
subject: hospital residents problem
subject: stable roommates

description: In this thesis, we consider different computational problems in the context of stable matchings. In these problems, a set of agents is given, and each agent has preferences over the other agents. A matching assigns the agents into groups of two agents. A matching is stable if there are no two agents preferring each other to the partners assigned to them. We now sketch the main results of this thesis. First, we consider the case that there are two different types of agents, and a matching must match agents of one type to agents of the other type (this variant is usually called Stable Marriage in the literature). In this setting, we show that for different kinds of "manipulations" it is NP-hard to manipulate (using at most some given number of manipulations) the set of agents and their preferences such that a specific pair of two agents is contained in a stable matching. However, for the manipulative action of deleting an agent from the instance, we show that one can modify in linear time the instance to contain a given agent pair using as few deletions as possible. Afterwards, we consider the problem of finding a popular matching. We assume that each agent of one type has weight w &gt; 3 while all agents of the other type have weight 1. A matching M is then called popular if there is no other matching M' such that the weight of the agents preferring M' to M exceeds the weight of the agents preferring M to M'. We describe a linear-time algorithm finding a popular matching if one exists. Next, we drop the assumption that there are two different types of agents (this variant of stable matching problems is called Stable Roommates) and allow the agents to contain ties in their preferences. The agents and their preferences naturally induce a graph, called the acceptability graph, which has one vertex for each agent and connecting two agents if and only if they appear in each other's preferences. Parameterizing by the structural graph parameter tree-cut width of the acceptability graph, we show that computing a stable matching is fixed-parameter tractable. Afterwards, we turn to stable matching problems allowing multiple agents to be matched together. We consider a generalization of stable matchings with two kinds of agents, namely hospitals and residents, and a hospital may be matched to multiple residents. The number of residents a hospital is matched to shall be either zero or between a given lower and upper quota. We show that a stable matching can be computed in polynomial time (if a stable matching exists) when each lower quota is at most two. Finally, we consider an extension of stable matchings where the agents shall not be matched in groups of size two, but in groups of size d. We consider two different parameters measuring the similarity of the preferences to being compatible with a strict ranking of the agents and show fixed-parameter tractability for one parameter and W{1]-hardness for the other.
description: In dieser Arbeit wird die Komplexität verschiedener Probleme im Kontext stabiler Matchings betrachtet. In solchen Problemen ist eine Menge von Agenten gegeben, wobei jeder Agent Präferenzen über die anderen Agenten hat. Ein Matching weist die Agenten einander in Zweiergruppen zu. Stabile Matchings sind Matchings, für die es keine zwei Agenten gibt, die sich gegenseitig gegenüber dem durch das Matching zugewiesenen Partner bevorzugen. Wir skizzieren nun die Hauptresultate dieser Arbeit. Zuerst betrachten wir den Fall, dass es zwei verschiedene Typen von Agenten gibt und ein Matching jeweils Agenten von einem Typ zu einem Agenten des anderen Typs zuweist (diese Variante wird in der Literatur üblicherweise Stable Marriage genannt). Für diesen Fall zeigen wir für verschiedene Arten von "Manipulationen", dass es NP-schwer ist, die Menge der Agenten und deren Präferenzen mit einer bestimmten Anzahl an Manipulationen so zu manipulieren, dass ein bestimmtes Agentenpaar in einem stabilen Matching enthalten ist. Für die Manipulation "Löschen von Agenten" jedoch zeigen wir, dass man in linearer Zeit eine Instanz durch das Löschen von möglichst wenigen Agenten so manipulieren kann, dass ein gegebenes Agentenpaar in einem stabilen Matching enthalten ist. Danach betrachten wir das Problem, ein populäres Matching zu finden. Wir nehmen dabei an, dass jeder Agent des einen Typs Gewicht w &gt; 3 und jeder Agent des anderen Typs Gewicht 1 hat. Ein Matching M ist populär, wenn es kein Matching M' gibt, sodass das Gewicht der Agenten, die M' gegenüber M bevorzugen, größer ist als das Gewicht der Agenten, die M gegenüber M' bevorzugen. Wir beschreiben einen Linearzeitalgorithmus, der ein populäres Matching findet sofern eines existiert. Als Nächstes lassen wir die Annahme, dass die Agenten in zwei Typen unterteilt sind, fallen (das resultierende Stabiles-Matching-Problem wird Stable Roommates genannt) und erlauben den Agenten, indifferent zwischen mehreren Agenten zu sein. Die Agenten und ihre Präferenzen induzieren auf natürliche Weise einen Graphen, genannt Akzeptanzgraph, der für jeden Agenten einen Knoten enthält und zwei Knoten mit einer Kante verbindet falls sie gegenseitig in ihren Präferenzen auftauchen. Wir zeigen, dass ein stabiles Matching zu berechenen "fixed-parameter tractable" parametrisiert mit dem strukturellen Graphparameter "Tree-Cut Width" des Akzeptanzgraphs ist. Anschließend wenden wir uns Problemen zu, in denen stabile Matchings mehrere Agenten einander zuweisen können. Wir betrachten eine Verallgemeinerung von stabilen Matchings, bei der es zwei Typen von Agenten gibt, Krankenhäuser und Ärzte, und mehrere Ärzte einem Krankenhaus zugewiesen werden können. Jedem Krankenhaus sollen dabei entweder zwischen einer unteren und einer oberen Schranke viele Ärzte oder gar keine Ärzte zugewiesen werden. Wir zeigen, dass ein stabiles Matching in polynomieller Zeit berechnet werden kann (sofern ein stabiles Matching existiert) wenn die untere Schranke jedes Krankenhauses maximal zwei ist. Zum Schluss betrachten wir eine Erweiterung von stabilen Matchings, bei der die Agenten in Gruppen der Größe $d$ statt Größe zwei zugewiesen werden sollen. Wir betrachten zwei verschiedene Parameter, die die Ähnlichkeit der Präferenzen zu Präferenzen, die kompatibel mit einer strikten Ordnung der Agenten sind, messen. Für den einen Parameter zeigen wir \glqq fixed-parameter tractability\grqq, während wir für den anderen Parameter W[1]-Härte zeigen.