On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences
| Autor: | C. Gregory Plaxton, Chi-Kit Lam |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
050101 languages & linguistics
Matching (graph theory) Computer science Open problem 05 social sciences Cyclic order 02 engineering and technology Stable marriage problem Type (model theory) Combinatorics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Preference (economics) |
| Zdroj: | Algorithmic Game Theory ISBN: 9783030304720 SAGT |
| Popis: | We study the three-dimensional stable matching problem with cyclic preferences. This model involves three types of agents, with an equal number of agents of each type. The types form a cyclic order such that each agent has a complete preference list over the agents of the next type. We consider the open problem of the existence of three-dimensional matchings in which no triple of agents prefer each other to their partners. Such matchings are said to be weakly stable. We show that contrary to published conjectures, weakly stable three-dimensional matchings need not exist. Furthermore, we show that it is NP-complete to determine whether a weakly stable three-dimensional matching exists. We achieve this by reducing from the variant of the problem where preference lists are allowed to be incomplete. Our results can be generalized to the k-dimensional stable matching problem with cyclic preferences for \(k \ge 3\). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|