Isso pode parecer mais uma questão de ciências sociais do que uma questão do TCS, mas não é. Ao ler " Algoritmos aleatórios ", que descrevem o problema do casamento estável, pode-se ler o seguinte (p54)
"Pode-se demonstrar que, para todas as listas de preferências, existe pelo menos um casamento estável. (Curiosamente, esse não é o caso de uma sociedade monogâmica homossexual com número par de habitantes) ..."
Existem extensões muito simples do Problema do Casamento Estável que permitem algum tipo de estado estacionário que inclua uma sociedade monogâmica homossexual ou uma sociedade em que um determinado subconjunto da população siga um conjunto de regras diferente do conjunto maior?
Afirmativamente, existem algoritmos que realizam essa correspondência?
fonte
Respostas:
Existe uma conjectura aberta sobre três tipos de pessoas. Suponha que você tenha homens, mulheres e cães, para que os homens tenham listas de preferências em mulheres, as mulheres tenham listas de preferências em cães e os cães tenham listas de preferências em homens. Sempre existe um casamento estável?
(Para outras estruturas de preferência na sociedade de três tipos, as respostas são conhecidas por serem negativas).
Outro comentário é que o casamento estável representa um núcleo não vazio e existe uma condição bem conhecida por Scarf que implica a existência de um núcleo não vazio. Sabe-se que as condições do lenço são satisfeitas para o problema original do casamento estável e para o problema de alocação da casa. (Mas falhou no problema de homens / mulheres / cães).
Algumas referências:
fonte
O que você está perguntando não é mais chamado de "Problema estável no casamento". Por outro lado, é chamado de "Problema com colegas de quarto estáveis". De acordo com a Wikipedia :
A Wikipedia discute a resposta para sua pergunta. Ele diz que o caso estável nem sempre pode ser encontrado, mas existe um algoritmo eficiente, devido a Irving (1985), que encontrará essa correspondência se houver um.
Editar:
Vários relaxamentos naturais são concebíveis para o SRP: Em vez de exigir que "não haja dois participantes xey, cada um dos quais prefere o outro ao seu parceiro em M", pode-se exigir que:
fonte
fonte