2004/11/01 by Kimmo Eriksson, Eriksson, Kimmo, Jonas Sjöstrand +4
Computer Science · Economics, Econometrics and Finance · Mathematics · #91A06 #91B68 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Game Theory and Voting Systems #math.CO #msc:91A06 #msc:91B68
paper · pdf · doi:10.48550/arxiv.math/0411028
14 pages
arxiv created 2004/11/01 · openalex publication_date 2004/11/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider stable three-dimensional matchings of three categories of agents, such as women, men and dogs. This was suggested long ago by Knuth (1976), but very little seems to have been published on this problem. Based on computer experiments, we present a couple of conjectures as well as a few counter-examples to other natural but discarded conjectures. In particular, a circular 3D matching is one where women only care about the man, men only care about the dog, and dogs only care about the woman they are matched with. We conjecture that a stable outcome always exists for any circular 3D matching market, and we prove it for markets with at most four agents of each category.