We consider the three-dimensional stable matching problem with cyclic preferences, a problem originally proposed by Knuth. 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östrand 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.

Three-dimensional stable matching with cyclic preferences

Poirrier, Laurent
2020-01-01

Abstract

We consider the three-dimensional stable matching problem with cyclic preferences, a problem originally proposed by Knuth. 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östrand 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.
2020
Pashkovich, Kanstantsin; Poirrier, Laurent
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4053393
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact