Problem of stable rommates

Question

Descrição do problema:

Discuta e Implemente uma solução inteligente para o problema conhecido como problem of roommates, que é um problema relacionado, mas mais difícil que o problema discutido nessa aula. Um número par de garotos precisam ser divididos em pares para dividir quartos em uma república. Um conjunto de pares é chamado estável se não existe nenhum par de garotos que prefere um ao outro que seus atuais pares. Dê um exemplo desse problema que não possui uma solução estável.

Answer 1

Vamos começar pelo exemplo do problema que não tem solução estável. Suponha que existam quatro garotos: A, B, C e D. Cada um deles com as preferências:

A = (B>C>D)
B = (C>A>D)
C = (A>B>D)
D = (A>B>C)

Provaremos que todos os pareamentos possíveis são instáveis.

Vamos começar com o pareamento inicial AB, CD. A prefere B, então está satisfeito. B, no entanto, prefere C. Como C também prefere B a D, os pareamentos não são estáveis.

Testando o segundo pareamento possível, AC, BD. A prefere B a C, e C prefere A a D, então o pareamento não é estável.

Testando o terceiro pareamento possível, AD, BC. A prefere C a D, e C prefere A a D, então o pareamento não é estável.

Assim, nenhum dos pareamentos é estável, o que gera circularidade.

Dessa forma, a solução não existe quando um dos garotos é a última escolha de todos os outros, o que chamaremos de stinky roomate condition. Assim, qualquer tentativa de ordenamento deve primeiro testar se essa condição não ocorre.

Em primeiro lugar, é necessário importar as bibliotecas que utilizaremos no exercício:

import pandas as pd
import numpy as np
import random
import math
from joblib import Parallel,delayed

Em seguida, vamos criar um gerador de preferências aleatórias dependente do número de garotos e gerar notas para os garotos dependendo de sua posição na preferência dos demais garotos. Minha ideia aqui é que se os garotos melhor posicionados proporem primeiro, a chance de serem os preferidosé maior, então gera menos iterações. Além disso, a nota permite identificar o caso do stiny roomate, que terá sempre nota zero.

Agora, vamos fazer a primeira rodada de pareamento: o garoto com maior nota (garotoX) propõe dividir quarto com o primeiro da lista de preferências dele (garotoY).

Se o garoto que recebeu a proposta não tem roommate, ele aceita a proposta. Se o garotoY já tem um roommate, ele verifica se o garotoX está melhor colocado em sua lista de preferências. Se estiver, ele troca de roommate. Se não estiver, ele nega, e o garotoX propõe para o próximo garoto de sua lista.

Toda vez que há um pareamento novo, ou seja, uma proposta é aceita, é necessário alocar os garotos como roommates um do outro, descartar os roommates antigos e sinalizar que houve uma mudança, dado que o código termina se passar por todas as preferências e ninguém quiser trocar, indicando que os pareamentos são estáveis.

Além disso, é necessário indicar quem recebeu a proposta de quem. A ideia aqui é que quem recebeu a proposta descarta das suas preferências todos os garotos com avaliação pior, dado que ele não vai trocar um garoto melhor por um pior. Se no processo de descarte algum garoto ficar com preferência vazia, isso é um sinal de que não há equilíbrio possível. Após o descarte das preferências, roda-se o algoritmo novamente, tentando parear os garotos.

Assim, o algoritmo tem três saídas: stinky roomate, pareamentos estáveis, e circularidade por preferência vazia.

Vou colocar todo esse processo em uma função que depende apenas do número de garotos:

#Vamos criar uma função que depende apenas do número de garotos
def roomate_pairing(numero_garotos):
lista_garotos = range(0,numero_garotos)
print(lista_garotos)

class erro1(Exception):
    """Erro: número de garotos deve ser par"""
    pass

# Vamos estabelecer uma função que atribua, a cada garoto,
# uma lista de preferência para os demais garotos, isto é, 
# a lista de prefeência deve ser aleatória e incluir todos 
# os garotos menos ele mesmo.

def generate_preference(lista_garotos,garoto):
    if (len(lista_garotos) % 2) == 0:
        pass
    else:
        raise erro1('numero impar de garotos')
    new_list = []
    new_list = lista_garotos[:]
    del new_list[garoto]
    random.shuffle(new_list)
    return new_list

# Teste para o garoto número 1 da lista:

a = generate_preference(lista_garotos,1)
print a

# Neste caso, o primeiro da lista é o mais preferido e assim sucessivamente.

#Agora vamos criar um dicionário que associa a cada garoto 
#a sua lista de preferências.

preferencias_temp = {}
for garoto in lista_garotos:
    preferencias_temp.update({garoto:generate_preference(lista_garotos,garoto)})


#vamos criar uma matriz em que cada garoto é uma coluna, com suas preferências.

preferencias_df = pd.DataFrame(preferencias_temp)
#nomeando as colunas
preferencias_df.columns = 'garoto_'  + preferencias_df.columns.astype(str) 

#vamos criar uma função que já crie essa matriz a partir do número de garotos

def create_preferences_df(numero_garotos):
    lista_garotos = range(0,numero_garotos)
    preferencias_temp = {}
    for i in lista_garotos:
        preferencias_temp.update({i:generate_preference(lista_garotos,i)})
    preferencias_df = pd.DataFrame(preferencias_temp)
    preferencias_df.columns = 'garoto_'  + preferencias_df.columns.astype(str) 
    preferencias_df = 'garoto_' + preferencias_df.astype(str)
    return preferencias_df

preferences_df = create_preferences_df(numero_garotos)

#vamos agora criar um dicionário para as notas

total_grades = {}
for garoto in preferences_df.columns:
    total_grades.update({garoto:0})

total_grades

#vamos definir a nota máxima como o numero de linhas menos um. 
#Para cada garoto X nas colunas, vamos acessar a lista de preferências.
#Em seguida, vamos somar as notas dos demais garotos à nota conferida pelo garoto X

max_score = preferences_df.shape[0] - 1
for garoto in preferences_df.columns:
    preference_series = preferences_df.loc[:,garoto]
    for rank in preference_series.index:
        total_grades[preference_series[rank]] = total_grades[preference_series[rank]] + max_score - rank


#Vamos criar um dicionario conjugado
temp_dict = {'garoto':total_grades.keys(),'notas':total_grades.values(),'roommate':numero_garotos*[''],'proposed_by':numero_garotos*['']}
temp_dict

#vamos criar um data frame de pareamento_df
pareamento_df_original = pd.DataFrame(temp_dict)
pareamento_df_original = pareamento_df_original[['garoto','notas','roommate','proposed_by']]

#vamos verificar a lista de alunos por grau de desejabilidade
pareamento_df_original = pareamento_df_original.sort_values(by='notas', ascending=False).set_index('garoto')
pareamento_df_original

#vamos fazer um processo iterativo de pareamento, 
#em que o garoto que faz a proposta é o que possui 
#a maior nota entre os que náo tem roomates
pareamento_df_final=pareamento_df_original.copy()
#sinalizador se esta estavel
mudou = False
#Vamos excluir o caso em que haja algum aluno com nota zero, ou seja, o caso do stinky roomate
if (pareamento_df_original.notas==0).sum()>0:
    return ('problema não tem solução pelo caso do stinky roomate')
#enquanto houver algum garoto sem roomate
while ((pareamento_df_final.loc[:,'roommate']=='').any() | mudou==True):
    mudou=False
    for garotoX in pareamento_df_final.index:
        #criar um vetor de preferências desse garoto
        preferences_garotoX=preferences_df.loc[:,garotoX]
        if pareamento_df_final.loc[garotoX,'roommate']=='':
            for garotoY in preferences_garotoX:
                if garotoY != '':
                    #se o garotoY não tiver ninguém
                    if pareamento_df_final.loc[garotoY,'roommate']=='':
                        #ele aceita o garotoX e eles viram roomates um do outro
                        pareamento_df_final.loc[garotoY,'roommate']=garotoX
                        pareamento_df_final.loc[garotoX,'roommate']=garotoY
                        #todos os que tinham proposta do garotoX perdem a proposta
                        pareamento_df_final.loc[pareamento_df_final.loc[:,'proposed_by']==garotoX,'proposed_by']=''
                        #garotoY fica com a proposta do garotoX
                        pareamento_df_final.loc[garotoY,'proposed_by']=garotoX
                        #garotoX perde qualquer proposta que tinha
                        pareamento_df_final.loc[garotoX,'proposed_by']=''
                        #sinaliza que nesta rodada houve mudança
                        mudou=True
                        break    
                    else:
                        #determinar qual o roommate atual nesta iteração
                        current_roommate_Y=pareamento_df_final.loc[garotoY,'roommate']
                        current_roommate_X=pareamento_df_final.loc[garotoX,'roommate']
                       # print('current_roommate_X =',current_roommate_X)
                        #criar um vetor de preferência do garoto Y
                        preferences_garotoY=preferences_df.loc[:,garotoY]
                        #verifica se o que está propondo é melhor que o atual, se sim, troca
                        if preferences_garotoY[preferences_garotoY==garotoX].index<preferences_garotoY[preferences_garotoY==current_roommate_Y].index:
                            #o roomate antigo do Y fica vazio, porque ele trocou
                            pareamento_df_final.loc[current_roommate_Y,'roommate']=''
                            #se o current roomate tiver sido proposto pelo garoto Y, ele também perde a proposta
                            pareamento_df_final.loc[current_roommate_Y,'proposed_by']=''
                            #garotoX e garotoY viram roomates
                            pareamento_df_final.loc[garotoY,'roommate']=garotoX
                            pareamento_df_final.loc[garotoX,'roommate']=garotoY
                            #todos os que tinham proposta do garotoX perdem a proposta
                            pareamento_df_final.loc[pareamento_df_final.loc[:,'proposed_by']==garotoX,'proposed_by']=''
                            #garotoY fica com a proposta do garotoX
                            pareamento_df_final.loc[garotoY,'proposed_by']=garotoX
                            #garotoX perde qualquer proposta que tinha
                            pareamento_df_final.loc[garotoX,'proposed_by']=''
                            #sinaliza que nesta rodada houve mudança
                            mudou=True
                            break
    #Se o código rodou por todos os garotos e ninguem trocou, os pareamentos são estáveis
    if mudou==False:
        return('PAREAMENTOS SAO ESTAVEIS')
    #Se o código rodou e alguém trocou, verificar se alguma preferência está vazia. Preferência vazia é sinal de que ão há convergência possível
    else:
        for garotoX in preferences_df:
            if (preferences_df.loc[:,garotoX] == '').all():
                return('nao ha equilibrio possivel')

    # Os caras que receberam a proposta deletam de sua preferência todos os menos preferidos e os que são deletados deletam esse cara também
    for garotoX in pareamento_df_final.index:
        if pareamento_df_final.loc[garotoX,'proposed_by']=='':
            pass
        else:
            #print(garotoX,'\n\n\n\n\n\n')
            garoto_que_propos = pareamento_df_final.loc[garotoX,'proposed_by']
            #criar um vetor de preferências desse garoto
            preferences_garotoX=preferences_df.loc[:,garotoX].copy()
            #deletar todos os que forem pior avaliados que o que propôs
            #primeiro vamos identificar o índice do garoto que propôs nas preferências do garotoX
            indice_da_proposta=preferences_garotoX[preferences_garotoX == garoto_que_propos].index.values[0]
            #Verificar se o garoto que propôs não é o último na preferência do garoto X
            if indice_da_proposta != preferences_df.index[-1]:
                #Se ele não for o último, deletar todos os que são pior avaliados
                preferences_df.loc[indice_da_proposta+1:,garotoX] = ''
                #identificar quais garotos foram eliminados na etapa anterior
                garotos_eliminados = preferences_garotoX[indice_da_proposta+1:]
                #deletar o garotoX da preferência de todos os eliminados
                for garoto_eliminado in garotos_eliminados:
                    #primeiro verificar se o garoto j'a não foi eliminado antes
                    if garoto_eliminado != '':
                        #atribuir valor zero aos garotos que foram deletados da preferência do garotoX
                        preferences_df.loc[preferences_df.loc[:,garoto_eliminado] == garotoX,garoto_eliminado] = ''

E, por último, vamos fazer rodar mil vezes para uma quantidade numero_garotos de garotos
e reportar qual o percentual das três soluções possíveis nas mil simulações

results = Parallel(n_jobs = 8, verbose = 10)(delayed(roomate_pairing)(numero_garotos) for numero_garotos in 1000*[8])
resulting_series = pd.Series(results)
resulting_series.value_counts()/resulting_series.shape[0]

Resultados de mil simulações para quatro garotos:
PAREAMENTOS SAO ESTAVEIS 0.855
problema não tem solução pelo caso do stinky roomate 0.145

Resultado de mil simulações para seis garotos:
PAREAMENTOS SAO ESTAVEIS 0.996
problema não tem solução pelo caso do stinky roomate 0.004

Resultado de mil simulações para dez garotos:
PAREAMENTOS SAO ESTAVEIS 0.99
nao ha equilibrio possivel 0.01

Resultado de mil simulações para 30 garotos:
PAREAMENTOS SAO ESTAVEIS 0.962
nao ha equilibrio possivel 0.038

Comments

Maria Carolina, gostei bastante do seu post. Me incentivou a pesquisar mais sobre o assunto ("matching"), além de me fazer perceber como um algoritmo nos ajuda a entender o problema e sua solução, principalmente nos detalhes que parecem desnecessários ou sem sentido. Entretanto, tenho uma dúvida e algumas observações que espero ser úteis.

Não entendi porque a existência de "stinky roommate condition" implica em não-existência de uma solução. Pelo que extraí da sua explicação e do código, essa condição ocorre quando algum dos garotos é a última opção para todos os demais garotos. No exemplo que você deu, com quatro garotos, se trocássemos a ordem de preferência do garoto B para (A>C>D), ainda teríamos o garoto D como o "stinky roommate". Porém, os pares AB e CD seriam estáveis, não? Os garotos A e B não teriam incentivo para trocar de companheiro de quarto, pois ambos estão no topo da lista de preferências do outro. Por outro lado, embora os garotos C e D tenham incentivos para trocar, ninguém aceitaria trocar com eles.

Me parece que seu algoritmo replica a fase 1 do algoritmo de Irving (artigo em http://www.dcs.gla.ac.uk/~pat/jchoco/roommates/papers/Comp_sdarticle.pdf, ou um resumo no wikipedia em https://en.wikipedia.org/wiki/Stable_roommates_problem), com o acréscimo da "stinky roommate condition". A estratégia é realizar rodadas em que os garotos escolhem seus parceiros preferidos, até não restar qualquer garoto sem parceiro, e reduzir o conjunto de preferências de acordo com os pares formados. O ponto de parada ocorre quando, ou i) não há mais "blocking pair", que no algoritmo significa que não houve trocas de parceiros na última rodada, ou ii) alguma lista de preferência está vazia.

Entretanto, não consegui enxergar a fase 2 do algoritmo de Irving, em que as listas reduzidas de preferências passam por novas rodadas de reduções, com reconhecimento de sequência cíclica ("all-or-nothing cycle") e rejeição por parte das primeiras opções dos garotos dessa sequência. Acho que a fase 2 seria desnecessária somente se, ao final da fase 1, alguma lista reduzida de preferências fosse vazia (implicando que não há "matching" estável) ou se todas fossem compostas exatamente por 1 elemento (implicando em um "matching" estável).

Uma observação final, em relação à sua implementação do código, é que, a cada rodada, há um loop para formar/testar todos os pares e, depois, outro loop para reduzir as preferências. Imagino se não seria mais eficiente reduzir as preferências a cada formação/troca de par. Seria apenas um loop a cada rodada.