Three-dimensional stable matching with cyclic preferences
- PDF / 281,447 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 267 Views
Three-dimensional stable matching with cyclic preferences Kanstantsin Pashkovich1 · Laurent Poirrier2 Received: 28 May 2019 / Accepted: 14 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
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. Keywords Stable matching · Three-dimensional · Matching · Stable
1 Introduction The stable matching problem is one of the most important problems in algorithmic game theory. In the stable matching problem, we are given two disjoint sets of agents, where each agent in one set has a preference order over agents in the other set. We are interested in finding a matching of agents, i.e. we are interested in pairing some agents from the first set with some agent from another set. Moreover, we want the resulting matching to be stable, i.e. there should exist no two agents which prefer each other to their assigned partners. In their seminal paper, Gale and Shapley [8] show that a stable
L. Poirrier was supported by NSERC Discovery Grant RGPIN-2018-04335.
B
Laurent Poirrier [email protected] Kanstantsin Pashkovich [email protected]
1
School of Computer Science and Electrical Engineering, University of Ottawa, 800 King Edward Avenue, Ottawa, ON K1N 6N5, Canada
2
Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada
123
K. Pashkovich, L. Poirrier
matching always exists and they provide an algorithm for finding a stable matching in polynomial running time. The situations changes when we have three disjoint groups of agents, where the agents in the first, second and third groups have a preference order over the agents in the second, third and first groups, respectively. In an instance of the three-dimensional stable matching problem with cyclic preferences (c3DSM), we have three disjoint sets of agents A, B and C such that |A| = |B| = |C| = n. Each agent a in the set A has a total order of the agents in B according to the preference of a. Thus, given a ∈ A and b, b ∈ B we can compare the agents b and b according to the preference of a. For the sake of exposition, we use the notation b >a b to say that a prefers b to b . Similarly, each agent b in the set B has a total order of the agents in C; and each agent c in the set C has a total order of the agents in A. A (perfect) matching M is a set of n disjoint triples of the form (a, b, c), a ∈ A, b ∈ B and c ∈ C. Given a matching M, for all a ∈ A we denote by M(a) the agent b ∈ B such that M
Data Loading...
