Algoritmos de Gale-Shapley

É um grafo tripartido. Repare-se que existe uma partição em $3$ conjuntos (azuis, verdes e vermelhos), e em cada conjunto não há vértices adjacentes.

Neste exemplo vamos trabalhar com o Relacionamento entre Rapazes e Raparigas, onde temos $4$ Raparigas e $4$ Rapazes.

A seguinte tabela é um exemplo de Lista de Preferências

Exemplo de Lista de Relacionamentos Estável:

• $\{(1,4),(2,1),(3,2),(4,3)\}$

Exemplos de Listas de Relacionamentos Instáveis:

• $\{(1,1),(2,3),(3,2),(4,4)\}$
  Esta lista tem um Bloqueio $(1,4)$. Repare-se que o Rapaz $1$ prefere a Rapariga $4$ à Rapariga $1$ (o seu par na lista) e a Rapariga $4$ prefere o Rapaz $1$ ao Rapaz $4$ (o seu par na lista).

• $\{(1,1),(2,2),(3,4),(4,3)\}$
  Esta lista tem $6$ Bloqueios: $(1,2),(1,4),(2,1),(2,4),(3,2),(4,4)$

1. Provar que cada Rapaz está associado a uma Rapariga

Como cada Rapariga aceita sempre uma proposta se estiver livre, se um Rapaz pedir namoro à última rapariga da sua Lista de Preferências, significa que as outras Raparigas têm par (namorado), a última só o rejeitará se também tiver namorado.
Isso é impossível, pois só se confirmaria se o número de Rapazes fosse maior que o número de Raparigas, o que nunca se verifica.

Se um Rapaz chegar à última Rapariga ela aceita-o sempre.

2. Provar que o algoritmo termina.

Como nenhum rapaz se pode propor $2$ vezes à mesma Rapariga, o número máximo de propostas que poderá haver são $r^2$, onde $r = \#Rapazes = \#Raparigas$. Como é um número finito, o Algoritmo tem fim.

3. Provar que no final a Lista é Estável

Se o Rapaz acabou por não ficar relacionado com uma rapariga $m$, que preferia em relação à com quem ficou $\operatorname{L}(h)$, então é porque $m$ o rejeitou.
Se $m$ o rejeitou foi porque tinha recebido uma proposta de um pretendente que preferia, não havendo assim Bloqueio.

Deste modo, será impossível encontrar Bloqueios na Lista final que resulta de aplicar o Algoritmo.

QED

Resolução:

1. Rapaz $1$ propõe-se à Rapariga $3$; ela aceita
2. Rapaz $2$ propõe-se à Rapariga $3$; ela rejeita
3. Rapaz $3$ propõe-se à Rapariga $3$; ela aceita e rejeita o Rapaz $1$
4. Rapaz $4$ propõe-se à Rapariga $3$; ela aceita e rejeita o Rapaz $3$
5. Rapaz $1$ propõe-se à Rapariga $2$; ela aceita
6. Rapaz $2$ propõe-se à Rapariga $2$; ela aceita e rejeita o Rapaz $1$
7. Rapaz $1$ propõe-se à Rapariga $1$; ela aceita
8. Rapaz $3$ propõe-se à Rapariga $4$; ela aceita

A Lista de Relacionamentos obtida é $\{(1,1),(2,2),(3,4),(4,3)\}$ que é estável.

Resolução:

Sendo um parceiro estável de $h_0/m_0$, um $m_1/h_1$ par com $h_0/m_0$ numa dada Lista Estável.

Supondo que uma certa execução $E$ do Algoritmo de Gale-Shapley produz um Relacionamento estável $R_0$ que inclui o par $(h,m)$.
Imaginemos que $R_0$ não é o Relacionamento estável que mais beneficia $h$, porque existe outro Relacionamento estável $R_1 \neq R_0$, onde $h$ está relacionado com $m'$, que prefere a $m$.
Pelo Algoritmo, conclui-se que, numa dada iteração de $E$, $m'$ teve de rejeitar $h$ (Relembrar que os Rapazes vão se propondo às Raparigas segundo a sua preferência).
Supondo que essa rejeição (de $m'$ face a $h$), foi a primeira vez em que uma rapariga rejeito um parceiro estável, pois $m'$ preferia outro Rapaz $h'$ a $h$.

Se nenhuma rapariga rejeitara um parceiro estável antes, então $h'$ não tem nenhuma parceira estável que prefira a $m'$.
Então, como em $R_1$ temos o par $(h,m')$ e $h'$ está relacionado com uma Rapariga que não prefere, em relação a $m'$, é óbvio que o par $(m',h')$ é um bloqueio de $R_1$. Assim, este Relacionamento não é estável.

Conclui-se que, qualquer Relacionamento, onde um Rapaz $h$ fica com uma Rapariga $m'$ que prefere em relação ao seu par $m$ que resultou da Aplicação do Algoritmo de Gale-Shapley, é Instável.

QED

Tentando provar por absurdo.

Vamos supor que o Teorema é Falso e que, sendo $R_0$ o relacionamento estável otimal para os Rapazes, que resulta do Algoritmo de Gale-Shapley, existe outro relacionamento estável $R_1$, onde uma dada Rapariga $m$ fica com um rapaz $h_1$, que prefere menos em relação ao rapaz $h_0$ com que ficou em $R_0$.

Como $R_0$ é otimal para os Rapazes , em $R_1$ $h_0$ ficará com uma rapariga que prefere menos, em relação a $m$. Para além disso, $m$ também ficou com um Rapaz $h_1$ que prefere menos em relação ao $h_0$.
Conclui-se que $(m,h_0)$ é um Bloqueio de $R_1$, logo $R_1$ não é estável.

QED