Three-dimensional Stable Matching with Cyclic Preferences
| Autor: | Kanstantsin Pashkovich, Laurent Poirrier |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Matching (statistics) 021103 operations research Control and Optimization Group (mathematics) 0211 other engineering and technologies Computational intelligence 010103 numerical & computational mathematics 02 engineering and technology Stable marriage problem 01 natural sciences MATCHING THREE-DIMENSIONAL Combinatorics STABLE Computer Science - Computer Science and Game Theory MATCHING STABLE STABLE MATCHING THREE-DIMENSIONAL 0101 mathematics STABLE MATCHING Mathematics Computer Science and Game Theory (cs.GT) |
| DOI: | 10.48550/arxiv.1807.05638 |
| Popis: | We consider the three-dimensional stable matching problem with cyclic preferences, a problem originally proposed by Knuth. Despite extensive study of the problem by experts from different areas, the question of whether every instance of this problem admits a stable matching remains unanswered. In 2004, Boros, Gurvich, Jaslar and Krasner showed that a stable matching always exists when the number of agents in each of the groups is three. In 2006, Eriksson, Sj\"ostrand and Strimling showed that a stable matching exists also when the number of agents in each group is four. In this paper, we demonstrate that a stable matching exists when each group has five agents. Furthermore, we show that there are at least two distinct stable matchings in that setting. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|