Extensão ao problema do casamento estável?

11

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?

IgorCarron
fonte
1
Parece uma pergunta divertida, especialmente se você mora em Utah!
Dave Clarke
1
A questão é um pouco aberta. Naturalmente, você pode garantir que exista uma solução para o problema de companheiros de quarto estáveis se alterar a definição de um par de bloqueio e / ou restringir a estrutura das preferências correspondentes. Como um exemplo trivial, você pode criar uma formulação de problema na qual qualquer correspondência máxima é "estável" e, em seguida, existe um algoritmo ganancioso simples para encontrar essa correspondência. Mas acho que não é isso que você gostaria de ouvir; você poderia elaborar um pouco mais?
Jukka Suomela
1
Dois livros excelentes sobre o problema do casamento estável e seus parentes são: Correspondência de dois lados de Alvin Roth e Marilda Sotomayor e O problema do casamento estável de Dan Gusfield e Robert W. Irving.
Joseph Malkevitch 30/09/10
1
"O casamento estável e sua relação com outros problemas combinatórios" de Knuth também é recomendado. Você pode encontrar a versão digitalizada da edição em francês no site: www-cs-faculty.stanford.edu/~uno/ms.html
Dai Le

Respostas:

11

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:

  • N
  • Um artigo que mostra várias aplicações para o lema crucial de Scarf e cita várias outras: (Em particular, uma versão fracionada do teorema de Gale-Shapley para hipergráficos de Aharoni e Holzman é descrita): R. Aharoni e T. Fleiner, Em um lema de Scarf, J. Combin. Teoria Ser. B 87 (2003), 72--80.
  • Uma solução do problema homens-mulheres-cães, quando existem no máximo 4 de cada gênero, aparece em um artigo de Eriksson et al (Math Soc Sci 2006).
Gil Kalai
fonte
@Prof. Kalai: Você poderia me indicar uma boa referência sobre a condição essencial não vazia de Scarf para o caso de casamento estável?
Dai Le
Experimente o artigo original de Scarf que eu adicionei à resposta.
Gil Kalai
10

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 :

Em matemática, especialmente nos campos da teoria dos jogos e da combinatória, o problema estável de companheiros de quarto (SRP) é o problema de encontrar uma correspondência estável - uma correspondência na qual não há par de elementos, cada um de um conjunto correspondente, em que cada membro do par prefere o outro à partida. Isso é diferente do problema do casamento estável, pois o problema dos companheiros de quarto estáveis ​​não exige que um conjunto seja dividido em subconjuntos de homens e mulheres. Qualquer pessoa pode preferir alguém no mesmo conjunto.

É geralmente indicado como:

Em uma determinada instância do problema de companheiros de quarto estáveis ​​(SRP), cada um dos 2n participantes classifica os outros em estrita ordem de preferência. Uma correspondência é um conjunto de n pares de participantes não ordenados (não ordenados). Um M correspondente em uma instância de SRP é estável se não houver dois participantes x e y, cada um dos quais prefere o outro ao seu parceiro em M. Diz-se que um par bloqueia M ou que é um par bloqueador em relação a M.

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:

  1. Pelo menos uma certa fração das pessoas fica satisfeita com os colegas de quarto. Aqui, a satisfação pode ser interpretada de maneira diferente. Por exemplo:
    • Diz-se que um par (x, y) está satisfeito se y é a primeira escolha de x e vice-versa.
    • Diz-se que um par (x, y) é satisfeito se um de x ou y é a primeira escolha de outro.
    • Diz-se que um par (x, y) está insatisfeito se existir um par (z, w) tal que x goste de z mais que y e z goste de x mais que w.
    • ...
  2. No máximo, uma certa fração das pessoas fica insatisfeita com os colegas de quarto. (Esse requisito pode ser diferente do descrito acima, dependendo da interpretação da satisfação .)
MS Dousti
fonte
Acho que o OP já sabe tudo isso, e a questão era como mudar as regras do jogo para garantir a existência de uma correspondência estável.
Jukka Suomela
Além disso, o contra-exemplo mais simples envolve 4 vértices em que a primeira e a segunda preferências de 3 deles definem um ciclo de 3.
Por Vognsen
2
Acho que as pessoas costumam usar o termo "correspondência estável" para se referir a qualquer variante do problema e "casamento estável" versus "companheiros de quarto estáveis" se desejam enfatizar que estudam a versão bipartida versus não bipartida do problema . Mas, como sempre, é melhor para definir os seus termos e não assumir que estes são padronizados ...
Jukka Suomela
Hesito em aprovar esta resposta por causa do primeiro parágrafo, o que aparentemente ofende algumas pessoas.
Tsuyoshi Ito
@ Tsuyoshi Ito: Eu não quis ofender ninguém. Pensando bem, removi o primeiro parágrafo completamente.
MS Dousti 30/09/10
7

nm

mhum
fonte
Mas isso é novamente uma correspondência bipartida: você tem dois tipos diferentes de entidades, "pessoas" versus "casas" (assim como você tem "homens" versus "mulheres" no problema tradicional do casamento estável). A pergunta parecia ser especificamente sobre correspondência não bipartida.
Jukka Suomela
Você pode ter razão. Eu estava pensando que esse problema poderia abordar "uma sociedade em que um determinado subconjunto da população segue um conjunto de regras diferente do conjunto maior".
mhum 30/09/10
Entendo, pensei que se referisse a uma sociedade em que temos uma subpopulação homossexual. Vamos ver se obtemos esclarecimentos para a pergunta.
Jukka Suomela
Sim, eu quis dizer uma sociedade em que temos um subconjunto dessa população que se comporta com um conjunto diferente de regras.
IgorCarron 01/10/10