Stable Marriage Problem with Incomplete Information

Abstract

After a brief introduction to the Stable Marriage Problem (SMP) and to some known algorithms and results, we define the SMP with incomplete information G(c). We show that it can be turned into an equivalent problem G’(c=1) with complete information. This equivalence will be used to derive an analytic expression for the probability P_es(c) of having at least one stable state where every player is married in the incomplete information game G(c). The range of connectivities ( C_c …1] defines the games with incomplete information where it is reasonable to look for a stable state where every player is married. An analytic expression is given for C_c.