Stable Marriage Problem with Incomplete Information

  • Alejandro Lage Depto. Física Teórica, Facultad de Física, Universidad de la Habana
  • Roberto Mulet Cátedra de Sistemas Complejos Henri Poincaré, San Lázaro y L, Ciudad de la Habana, Cuba


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 Pes(c) of having at least one stable state where every player is married in the incomplete information game G(c). The range of connectivities ( Cc …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 Cc.

Dec 1, 2006
How to Cite
LAGE, Alejandro; MULET, Roberto. Stable Marriage Problem with Incomplete Information. Revista Cubana de Física, [S.l.], v. 23, n. 2, p. 80-85, dec. 2006. ISSN 2224-7939. Available at: <>. Date accessed: 04 oct. 2023.
Original Articles