On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences (Q2197901)

This paper explores two variations on the Gale-Shapley (henceforth referred to as G-S) assignment problem [\textit{D. Gale} and \textit{L. S. Shapley}, Am. Math. Mon. 69, 9--15 (1962; Zbl 0109.24403)]. The version of the G-S problem, whose generalizations the author restricts attention to, is the one with two sets of agents with \textit{equal number} of agents each of whom has a strict order relation defined on the set of the other agents, i.e., other than the one the agent is a member of. We will refer to these order relations as a \textit{strict preference ranking} (which is the interpretation it carried in the original paper of G-S) which is complete and strict, i.e., with no ties allowed in the ranking of the agents. Earlier papers in the literature have already investigated generalizations in which there are more than two sets of agents. Taking the specific special case of 3 sets of agents for illustrative purposes, it is assumed that the problem numbers them in a specific order, say \(A_{1},A_{2},A_{3}\), and each agent in one set holds a preference ranking over the succeeding set (next higher indexed set) of agents with the understanding that the agents in the highest numbered set of agents hold their preference ranking over the very first set of agents so that a cycle of the set of agents in a specific direction is being considered. Generalization to r agents where \(r\geq 3\) is in the straightforward way. A \textit{matching} is a triplet of bijections \(f^{i},i=1,2,3\), with each \(f^{i}:A_{i}\rightarrow A_{j}\) where \(j=i+1\) for \(i=1,2\) and \(j=1\) when \(i=3\) so it is a \textit{cyclical directed matching} of agents from \(A_{1}\) to \(A_{2}\), \(A_{2}\) to \(A_{3}\) and \(A_{3}\) to \(A_{1}\). A matching is called \textit{weakly stable} if no other matching can be found which \textit{strongly blocks} the given matching in the sense that each agent finds itself in a strictly preferred position as per his own preference ranking, i.e., each agent ends up being \textit{strictly better off} according to his own ranking compared to what he is matched with in the given matching. The concept of blocking is, of course, familiar from the literature on cooperative game theory and the concept of a stable matching is similarly familiar from the concept of a member of the Core of such a game when payoffs are not transferable, something much investigated in that literature. Earlier work already revealed that when \(r=3\) examples can be found of instances of rankings where there do not exist any weakly stable matching. This quite naturally leads to the idea of a probabilistic analysis of the problem. The author does this by taking the same approach as used by earlier writers which is to regard the space of all possible preference rankings along with a uniform density function. He is able to establish a lower bound on the expected number of weakly stable rankings (Theorem 1.1) which implies that this expected value, ``i.e., the average number of weakly stable matchings per problem instance, grows at least as fast as \((n\log n)^{r-1}\) if \(r\geq 2\)'' where \(n\) is the number of agents in each set. The author also considers a notion of blocking in a weaker sense and a corresponding stronger notion of stable matching and establishes a lower bound for that which goes to zero as \(n\rightarrow \infty\) and makes a couple of \textit{conjectures} for the asymptotic behaviour of the number of stable matchings. The paper goes on to consider a second generalization of G-S, namely, by considering \textit{partial} instead of complete rankings for each agent with the \textit{interpretation that non-comparability within a ranking be considered as a tie}. Several nested, i.e., progressively weaker notions of stable matchings were already discussed and to a certain extent analyzed in previous works. The author investigates these in the setting of an ``idealized model of random preferences with built-in partial incomparability'', establishes some bounds on the expected value of the number of such stable matchings (Theorems 1.2 and 1.3) and draws some qualitative conclusions from them; in particular, that for two of the stronger notions of stability the fraction of solvable instances of preference patterns is exponentially small. For those already interested in this area of mathematical economics and game theory this should be an useful paper to get acquainted with. Amongst other things, it provides a good overview of past research in this area as well as throws out interesting conjectures and ideas for future directions of research. It is worth noting that this line of research work appears to be preoccupied with the special version of the G-S problem where the set of agents have each the same number of agents and seemingly ignores the much more interesting case discussed there, more interesting at least from the point of view of applications and possibly also of the richness of the framework, namely of college admissions procedure where that is not the case. It is also curious that partial rankings with the specific interpretation mentioned above is used as a stand in for referring to problems where the preference ranking may have ties. While, admittedly, partial rankings have an interest in their own right, perhaps more so than just allowing for ties, it is a strange interpretation since regarding non comparability as `indifference' or `equivalence' together with usually assumed properties of order relations could lead to problems.