dd-dimensional stable matching with cyclic preferences

•Every marriage problem admits a stable matching (Gale and Shapley, 1962).•We consider an extension with dd different genders and cyclic preferences.•If there are at most d+1d+1 agents per gender, we show that a stable matching exists.•This stable matching can be found in polynomial time.

Gale and Shapley (1962) have shown that in marriage markets, where men and women have preferences over potential partners of the other gender, a stable matching always exists. In this paper, we study a more general framework with dd different genders due to Knuth (1976). The genders are ordered in a directed cycle and agents only have preferences over agents of the subsequent gender. Agents are then matched into families, which contain exactly one agent of each gender. We show that there always exists a stable matching if there are at most d+1d+1 agents per gender, thereby generalizing and extending previous results. The proof is constructive and computationally efficient.