Emparelhamento Estável

Exercícios do Livro Algorithm Design de Kleinberg e Tardos

Preâmbulo

Primeiramente, é importante destacar que esse material é escrito e enquadrado da maneira que funciona para mim. Portanto, obviamente, ele contém vieses de aprendizado, cada experiência de aprendizado é única e individual e o que é pra mim pode não ser pra vocÊ. Então, antes de criticar, lembre disso.

Segundamente, Análise e Projetos de Algorítimo (APA) é uma disciplina específica de ciência da computação e muitos alunos, principalmente os com projetos interdisciplinares, vão questionar a utilidade e importância dela no longo prazo. Contudo, é importante que essa não seja a mentalidade porque quanto mais pensar assim menos você vai absorver o conteúdo. Tente pensar que você está aprendendo um novo jeito de resolver problemas.

Sempre que você aprende um novo jeito de aprender problemas, você ganha mais uma ferramenta e uma perspectiva para olhar o mundo a sua volta. Então, pense dessa maneira, APA é um nova ferramenta e perspectiva para você olhar o mundo. Um livro muito recomendado sobre essa perspectiva é o Algoritmos para viver

Agora, indo ao que interessa.

Introdução

O que é um algoritmo? (clique para expandir)

Algoritmo é um passo a passo de uma ação para chegar a um objetivo. Dada determinada entrada e um objetivo, nós temos que pensar qual a sequência lógica que precisamos “falar” para o computador para que consigamos o objetivo desejado.

Nesse contexto, a disciplina de APA tem como objetivo demonstrar que a) como o seu algoritmo é desenhado; b) o quão rápido ele é; c) e quanta memória ele consome IMPORTAM MUITO. Como será visto, ao desenhar um algoritmo - ou seja uma sequência lógica para atingir um objetivo - você pode levar pouco tempo, OU MUITO TEMPO.

PORTANTO, quando falamos de algoritmo devemos nós preocupar com duas coisas:

1. Velocidade;
2. Memória.

Antes de aprofundar nas métricas para medir essa performance (running time), vamos ao primeiro problema trazido por Kleinberg e Tardos¹: o emparelhamento estável.

¹ J. Kleinberg e E. Tardos. Algorithm Design. Addison Wesley, 2005.

1º Problema: Emparelhamento Estável

Em 1962, David Gale e Lloyd Shapley, dois economistas matemáticos, se perguntaram o seguinte É possível idealizar um processo de admissão em um colégio, ou de recrutamento de emprego em uma empresa, que seja estável? OU SEJA, uma solução preferível.

Entendendo o problema:

Para quaisquer listas de preferências, é possível determinar um emparelhamento estável? Ou seja, dadas as listas de preferências de A e B, é possível determinar um emparelhamento estável onde há uma situação de estabilidade, onde cada um está a escolher a sua melhor resposta, dada a escolha dos outros.

Einstein uma vez disse: “se tivesse uma hora para resolver um problema e minha vida dependesse dessa solução, eu passaria 55 minutos definindo a pergunta certa a se fazer. Porque se eu soubesse a pergunta correta, poderia resolver o problema em menos de cinco minutos”.

Por exemplo:

1. Cada um dos n candidatos se inscreve em cada uma das n empresas, e cada empresa quer aceitar apenas um candidato mas elas tem sua lista de preferência entre os candidatos;
2. Cada um nos n homens está interessado em cada uma das n mulheres, e cada mulher só pode aceitar apenas um homem e elas tem sua lista de preferência entre os homens;
3. Dado um conjunto de preferências entre hospitais e estudantes de medicina, é possível chegar a um emparelhamento estável?

A professora já falou sobre o exemplo de homem e mulher em sala de aula, então nesse material eu vou focar no exemplo que os autores do livro usam aqui.

O objetivo é criar um processo de admissão entre hospitais e estudantes de medicina que seja auto-reforçador, ou seja, que se mantenha estável por si só. Para isso, deve-se evitar pares instáveis, nos quais um hospital e um estudante preferem um ao outro em vez das suas atribuições atuais. Uma atribuição estável garante que não há incentivos para mudar, pois ninguém sairia ganhando ao trocar de parceiro — o que torna o sistema “justo” e resistente a manipulações.

No que tange aos dados de entrada, cada hospital e cada estudante tem uma lista de preferências. O desafio é encontrar uma correspondência entre eles de forma que nenhum outro par hospital-estudante prefira estar junto em vez de manter sua atual designação — ou seja, encontrar um emparelhamento estável.

O que está acontecendo é bem simples. Os matchs M é um conjunto de pares ordenados h-s, certo? Sendo que h está no conjunto H e s está no conjunto S. O MATCH PERFEITO (\(|M| = |H| = |S| = n\)) onde o número de pares é igual ao número de hospitais que é igual ao número de estudantes que é igual a n. Isso garante que cada hospital está pareado com um estudante e vice-versa, sem sobras — ou seja, um casamento perfeito. Beleza, MAS COMO CHEGAMOS A ESSE RESULTADO?

Exemplo passo a passo bem devagar

O exemplo vem do material oficial do livro disponível aqui

Temos duas tabelas. Uma com a preferência dos hospitais (cima) e a preferência dos estudantes (embaixo). Primeiramente, Atlanta convida Wayne (sua 1ª opção), como Wayne não tem nenhum par ele aceita e eles formam o primeiro par. Feito isso vamos para o próximo hospital.

Boston convida Yolanda (sua 1ª opção), Yolanda aceita porque ela está sem par mesmo então o que vier é lucro já que ela precisa muito trabalhar.

O próximo da lista Chicago convida Wayne. Como Wayne prefere Chicago a Atlanta, Wayne rejeita Atlanta e pareia com Chicago agora. Atlanta agora está sem par.

Como Atlanta ficou sem par, o algoritmo volta para Atlanta. Atlanta convida Val (sua segunda preferência) e Val aceita porque ela está sem par.

Detroit agora propõe para para Val, mas ela rejeita porque prefere estar com Atlanta

Detroit ainda está sem par, então ela vai pra sua segunda preferência que é Yolanda. Como Detroit está na frente de Boston nas preferências de Yolanda, Yolanda rejeita Boston e pareia com Detroit. Fazendo com que Boston fique sem par.

A partir daqui eu sugiro o leitor tentar fazer sozinho. O Resultado final está abaixo.

Depois de muitas idas e vindas, temos o emparelhamento estável. Conseguiu chegar nessa solução?

Exercícios do Livro

Questão 1

Considere uma cidade com \(n\) homens e \(n\) mulheres procurando se casar entre si. Cada homem possui uma lista de preferências que ordena todas as mulheres, e cada mulher possui uma lista de preferências que ordena todos os homens.

O conjunto das \(2n\) pessoas é dividido em duas categorias: pessoas boas e pessoas más. Suponha que, para algum número k, com \(1 \leq k \leq n - 1\), existam \(k\) homens bons e \(k\) mulheres boas; assim, há \(n - k\) homens maus e \(n - k\) mulheres más.

Todos preferem se casar com qualquer pessoa boa do que com qualquer pessoa má. Formalmente, cada lista de preferência tem a propriedade de que classifica cada pessoa boa do gênero oposto acima de cada pessoa má do gênero oposto: suas primeiras \(k\) posições são ocupadas pelas pessoas (do gênero oposto), em alguma ordem, e as pessoas próximas \(n - k\) posições sõa ocupadas pelas pessoas más (do gênero oposto), também em alguma ordem.

Mostre que, em todo o emparelhamento estável, todo homem bom está casado com uma mulher boa.

Resposta da questão 1 (Clique para expandir)

Para resolver essa questão, vc tem que fazer fazer por contradição. É possível haver um emparelhamento estável onde o homem \(m\) está casado com uma mulher má \(w\)? Não. Porque \(m\) prefere qualquer mulher boa a qualquer mulher má. E \(m'\) (mulher boa) prefere qualquer homem bom a qualquer homem mau. Ou seja, a contradição não é possível pq TODO O \(m\) vai sempre preferir a \(m'\) e toda a \(m'\) vai preferir o \(m\).

Questão 2

Podemos pensar em uma generalização do Problema do Emparelhamento Estável em que certos pares homem-mulher são explicitamente proibidos. No caso de empregadores e candidatos, podemos imaginar que certos candidatos simplesmente não possuem as qualificações ou certificações necessárias, e portanto não podem ser empregados por certas empresas, por mais desejáveis que pareçam.

Usando a analogia do casamento entre homens e mulheres, temos um conjunto \(M\) de \(n\) homens, um conjunto \(W\) de \(n\) mulheres, e um conjunto \(F \subseteq M \times W\) de pares que simplesmente não têm permissão para se casar. Cada homem \(m\) classifica todas as mulheres \(w\) para as quais \((m, w) \notin F\), e cada mulher \(w\) classifica todos os homens \(m\) para os quais \((m, w) \notin F\).

Neste cenário mais geral, dizemos que uma correspondência (matching) \(S\) é estável se ela não apresentar nenhum dos seguintes tipos de instabilidade:

1. Existem dois pares \((m, w)\) e \((m', w')\) em \(S\) com a propriedade de que \((m, w') \notin F\), \(m\) prefere \(w'\) a \(w\), e \(w'\) prefere \(m\) a \(m'\). (Esse é o tipo usual de instabilidade.)

2. Existe um par \((m, w) \in S\), e um homem \(m'\) tal que \(m'\) não faz parte de nenhum par na correspondência, \((m', w) \notin F\), e \(w\) prefere \(m'\) a \(m\). (Um homem solteiro é mais desejável e não é proibido.)

3. Existe um par \((m, w) \in S\), e uma mulher \(w'\) tal que \(w'\) não faz parte de nenhum par na correspondência, \((m, w') \notin F\), e \(m\) prefere \(w'\) a \(w\). (Uma mulher solteira é mais desejável e não é proibida.)

4. Existe um homem \(m\) e uma mulher \(w\), nenhum dos quais faz parte de qualquer par na correspondência, tal que \((m, w) \notin F\). (Há duas pessoas solteiras que não têm impedimentos para se casar uma com a outra.)

Note que, sob essas definições mais gerais, uma correspondência estável não precisa ser uma correspondência perfeita.

Agora podemos perguntar: para todo conjunto de listas de preferência e todo conjunto de pares proibidos, existe sempre uma correspondência estável?

Resolva essa questão fazendo uma das duas coisas:

1. Apresente um algoritmo que, para qualquer conjunto de listas de preferência e pares proibidos, produza uma correspondência estável; ou

2. Dê um exemplo de listas de preferência e pares proibidos para os quais não existe uma correspondência estável.

Resposta questão 2 (Clique para expandir)

A solução para A perpassa o algoritmo Gale-Shapley (Algoritmo GS). Obviamente, uma versão adaptada dele para poder incluir os pares proibidos. Ou seja, não queremos que \(m\) proponha para \(w\) se esse par é proibido. A diferença será no loop.

OBS: O nome do código abaixo é pseudocódigo, serve só para ilustrar.
“while” é a função para repetir o código
“If” é a condição
“else” é o que é pra fazer se a condição não for atendida.
“endif” e “endwhile” são para encerrar os blocos de condições e repetições respectivamente.

#condição incial
Initially all m ∈ M and w ∈ W are free 
#nosso loop: se m livre e não propos a todas as mulheres que não pertecem ao subconjuntos de pares proibidos, repete
While there is a man m who is free and hasn’t proposed to every woman w for which (m, w) ∉ F
#o resto segue o algoritmo GS padrão
Choose such a man m
Let w be the highest-ranked woman in m’s preference list
to which m has not yet proposed
If w is free then
(m, w) become engaged
Else w is currently engaged to m
If w prefers m to m then
m remains free
Else w prefers m to m
(m, w) become engaged
m becomes free
Endif
Endif
Endwhile
Return the set S of engaged pairs

A segunda solução (b), perpassa esmiuçar as condições da questão:

Primeiro, suponha que exista uma instabilidade do tipo (i), que consiste nos pares \((m, w)\) e \((m', w')\) em \(S\), com as seguintes propriedades:

\((m, w') \notin F\)

\(m\) prefere \(w'\) a \(w\)

\(w'\) prefere \(m\) a \(m'\)

Neste caso, \(m\) deve ter proposto para \(w'\). Como ela acabou com \(m'\), isso significa que \(w'\) rejeitou \(m\), então ela prefere seu parceiro final \(m'\) a \(m\) — o que contradiz nossa suposição. ✅

Segundo, suponha que exista uma instabilidade do tipo (ii), que consiste no par \((m, w) \in S\) e em um homem \(m'\) que:

Não está em nenhum par da correspondência

\((m', w) \notin F\)

\(w\) prefere \(m'\) a \(m\)

Neste cenário, \(m'\) deve ter proposto a \(w\) e foi rejeitado. Portanto, \(w\) prefere seu parceiro final \(m\) a \(m'\) — novamente uma contradição. ✅

Terceiro, suponha que exista uma instabilidade do tipo (iii), que consiste no par \((m, w) \in S\) e em uma mulher \(w'\) tal que:

\(w'\) não faz parte de nenhum par da correspondência

\((m, w') \notin F\)

\(m\) prefere \(w'\) a \(w\)

Mas se \(w'\) está solteira, então nenhum homem propôs a ela, em particular, \(m\) nunca propôs a \(w'\), o que contradiz a afirmação de que ele prefere \(w'\) a \(w\), pois teria proposto a ela antes. ✅

Por fim, suponha que exista uma instabilidade do tipo (iv), envolvendo um homem \(m\) e uma mulher \(w\), ambos solteiros, tal que:

\((m, w) \notin F\)

Mas para que \(m\) esteja solteiro, ele deve ter proposto a todas as mulheres não proibidas. Em particular, ele deve ter proposto a \(w\). Logo, \(w\) não estaria solteira — mais uma contradição. ✅

Conclusão: Nenhum dos quatro tipos de instabilidade pode ocorrer. Portanto, a correspondência gerada pelo algoritmo é estável, mesmo considerando os pares proibidos \(F\).

Vou atualizando colocando as outras questões aqui.