El problema de los matrimonios estables con información incompleta.
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 analyti...
| Published in: | Revista Cubana de Física Vol. 23; no. 2; pp. 80 - 86 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Published: |
Universidad de La Habana
2006
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| Summary: | 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 of having at least one stable state where every player is married in the incomplete information game G(c). The range of connectivities (…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 . Se presenta el Problema de los Matrimonios junto a algunos resultados y algoritmos. Se define el problema con información incompleta G(c) y se demuestran algunos teoremas que lo hacen equivalente a un problema con P( c ) e s información incompleta G'(c=1). Basados en eso calculamos la probabilidad de encontrar al menos un estado estable en el que todos los jugadores estén casados en G(c). Se calcula la conectividad critica que define el rango …1] de conectividades en las que es posible asignar matrimonios de forma estable a todos los jugadores. |
|---|