matrimonios_estables


El problema de los matrimonios estables

Dados un cierto número de hombres y mujeres heterosexuales, organízalos por parejas de tal manera que su matrimonio sea estable. Cada persona ha ordenado a las personas del sexo opuesto según su preferencia. Los matrimonios se consideran estables si no es posible encontrar dos personas del sexo opuesto que se atraigan entre sí más que lo que les atraen sus respectivas parejas.

Este problema siempre tiene solución (¡a veces puede tener varias!) y existe un algoritmo, diseñado por David Gale and Lloyd Shapley en 1962, en el que las parejas se ordenan a sí mismas, como un sistema complejo. Mira en qué consiste el algoritmo en este vídeo:


In [ ]:
from IPython.display import HTML
HTML('<iframe src="http://youtube.com" width="700" height="400"></iframe>')

Nota: Este ejercicio sigue la nomenclatura y la estructura clásicas de este problema para que resulte intuitivo y fácil de seguir, no pretende ser un modelo real de comportamiento. Desde la organización de la PyConEs y nosotros mismos, queremos fomentar y apoyar la diversidad y la tolerancia en todas las facetas de la sociedad, y respetamos por igual todas las identidades de género y sexualidad.


In [1]:
import numpy as np
import random as random

In [2]:
class Woman (object):
    ''' Este es el elemento estático, quien recibe propuestas y elige al mejor'''
    def __init__(self, name):
        
        self.name = name
        self.preferences = {}
        self.preferences_inv = {}
        self.boyfriend = []
        self.candidates = []
        
    def engage(self, man):
            self.boyfriend = man
            man.girlfriend = self
        
    def breakup(self, man):
            self.boyfriend = []
            man.girlfriend = []
    
        
class Man (object):
    '''Este es el elemento dinámico, que busca a su mejores opciones y se propone'''
    
    def __init__(self, name):
        
        self.name = name
        self.preferences = {}
        self.preferences_inv = {}
        self.girlfriend = []
        self.number_of_proposals = 1
        
    def propose(self, woman):
        woman.candidates += [self]
        self.number_of_proposals += 1

Ahora creamos nuestra población, y la repartimos en dos listas.


In [3]:
magdalena, elena, ana, julia, marta = Woman('Magdalena'), Woman('Elena'), Woman('Ana'), Woman('Julia'), Woman('Marta')
carlos, siro, manuel, antonio, javier = Man('Carlos'), Man('Siro'), Man('Manuel'), Man('Antonio'), Man('Javier')

women = [magdalena, elena, ana, julia, marta]
men =[carlos, siro, manuel, antonio, javier]

In [4]:
for woman in women:
    #Generamos una lista de preferencias de manera aleatoria
    preferences = [ii for ii in range(1, len(men)+1)]
    random.shuffle(preferences)
    
    #Estas preferencias se almacenan como dos diccionarios
    for index in range(len(men)):
        woman.preferences[preferences[index]] = men[index]
        
    for index in range(1, len(men)+1):
        woman.preferences_inv[woman.preferences.get(index).name] = index
        
for man in men:
    preferences = [ii for ii in range(1, len(women)+1)]
    random.shuffle(preferences)
    
    for index in range(len(women)):
        man.preferences[preferences[index]] = women[index]
        
    for index in range(1, len(men)+1):
        man.preferences_inv[man.preferences.get(index).name] = index

In [5]:
def noche_de_fiesta(man, women):
    
    for woman in women:
        woman.candidates=[]
    
    for man in men:
        if man.girlfriend == []:
            man.propose(man.preferences[man.number_of_proposals])
        
    for woman in women:
    
        if woman.boyfriend == []:
            for ii in range(1, len(men)+1):
                if woman.preferences[ii] in woman.candidates:
                    woman.engage(woman.preferences[ii])
                    break
        
        elif any (woman.preferences_inv[man.name]>woman.preferences_inv[woman.boyfriend.name] for man in woman.candidates):
            woman.breakup(woman.boyfriend)
            for ii in range(1, len(men)+1):
                if woman.preferences[ii] in woman.candidates:
                    woman.engage(woman.preferences[ii])
                    break

In [ ]:
for dia in range(1, len(men)+2):
    print('Noche ' + str(dia))
    print('-------')
    noche_de_fiesta(men, women)
    for woman in women:
        print(woman.name)
        if woman.candidates != []:
            print('    Candidatos: ', [candidate.name for candidate in woman.candidates])
        if woman.boyfriend != []:
            print('    Novio: ',  woman.boyfriend.name)
    print()
    print()

Este ejercicio parece un poco extraño, ¿no?

Pero... ¿y si te dijera que es un algoritmo muy utilizado diariamente por instituciones de todo el mundo?

Te toca trabajar

Este algoritmo es muy usado para asignación de plazas en oposiciones, y se usa en varios países para repartir a los candidatos en las diferentes plazas según sus resultados y sus preferencias. Modelémoslo!

Crea unas clases nuevas llamadas 'Candidato' y 'Destino' basadas en 'Man' y 'Woman'. Simplemente con esto, ya tenemos un reparto de plazas muy adecuado, pero podemos mejorar nuestro modelo. Te sugiero que intentes los siguientes cambios:

  • Los candidatos generan una propiedad aleatoria llamada 'Nota' al ser creados, que los destinos usan para decidir sus preferencias, en vez de un orden aleatorio
  • Los destino tienen una capacidad de varios puestos, e incluso...
  • Cada destino tiene una cantidad diferente de puestos, que se define al crearlo.

Recuerda que es probable que necesites modificar las funciones anteriores (o crear otras nuevas basadas en ellas, si quieres conservar las originales sin tocar como referencia).

Para crear la población, puede que te resulte útil el método append() en el interior de un bucle.


In [ ]:


In [ ]:

Carlos Dorado, Aeropython, 20 de Noviembre de 2015


In [ ]: