Algoritmos de Gale-Shapley

Defini√ß√Ķes

Grafo k-partido

Um grafo diz-se kk-partido (k‚ąąN2)(k \in \N_2) se existe uma parti√ß√£o do conjunto dos seus v√©rtices em kk conjuntos, nenhum deles contendo v√©rtices adjacentes.
Se k=2k=2 pode-se chamar bipartido, se k=3k=3 tripartido e para k>3k> 3 multipartido.

Exemplo

Grafo Tripartido

√Č um grafo tripartido. Repare-se que existe uma parti√ß√£o em 33 conjuntos (azuis, verdes e vermelhos), e em cada conjunto n√£o h√° v√©rtices adjacentes.

Algoritmo da Estabilidade

Relacionamento

Sejam HH e MM dois conjuntos finitos equipolentes (com o mesmo tamanho), que representam o conjunto de Rapazes e Raparigas, respetivamente. Seja L‚Ā°:H‚ÜíM\operatorname{L}: H \rightarrow M uma bije√ß√£o, representa um relacionamento entre rapazes e raparigas que consiste numa lista de pares (h,m)(h,m), designada Lista de Relacionamentos.
Como √© uma bije√ß√£o, tamb√©m podemos ter a rela√ß√£o inversa W‚Ā°:M‚ÜíH\operatorname{W}: M \rightarrow H.

Bloqueio

Usando o exemplo do Relacionamento entre Rapazes e Raparigas, diz-se que o par (h,m)(h,m), h‚ąąM,m‚ąąMh \in M, m \in M, √© um Bloqueio na lista de relacionamentos, se n√£o pertence √† lista de relacionamentos, mas hh preferia estar com mm do que com L‚Ā°(h)\operatorname{L}(h) e mm preferia estar com hh do que com W‚Ā°(m)\operatorname{W}(m).

Uma Lista de Relacionamentos diz-se Est√°vel se n√£o existirem pares de bloqueio em L‚Ā°\operatorname{L}.

Lista de Preferências

Usando mais uma vez o exemplo do Relacionamento entre Rapazes e Raparigas, cada Rapaz e cada Rapariga poderá ter uma Lista de Preferências onde apresenta os membros do conjunto oposto que prefere por ordem.

Exemplo

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

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

Rapazes12>4>1>323>1>4>232>3>1>444>1>3>2Raparigas12>1>4>324>3>1>231>4>3>242>1>4>3\begin{array}{|} \text{Rapazes} & & & & & & & &\\ 1&\quad &2 &> &4 &> &1 &> &3\\ 2&\quad &3 &> &1 &> &4 &> &2\\ 3&\quad &2 &> &3 &> &1 &> &4\\ 4&\quad &4 &> &1 &> &3 &> &2\\ \hline \text{Raparigas} & & & & & & & &\\ 1&\quad &2 &> &1 &> &4 &> &3\\ 2&\quad &4 &> &3 &> &1 &> &2\\ 3&\quad &1 &> &4 &> &3 &> &2\\ 4&\quad &2 &> &1 &> &4 &> &3\\ \end{array}

Exemplo de Lista de Relacionamentos Est√°vel:

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

Exemplos de Listas de Relacionamentos Inst√°veis:

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

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

Algoritmo da Estabilidade

Serve para verificar se uma Lista de Relacionamentos é estável ou instável.

O Algoritmo é descrito pelo seguinte pseudo-código.

Estabilidade Pseudo

Algoritmo de Gale-Shapley

Descrição Do Algoritmo

Informal

  1. Cada Rapaz e Rapariga ou est√£o comprometidos ou livres
  2. Cada Rapariga, assim que fica comprometida, continuará nesse estado durante o resto da execução do algoritmo. Poderá, eventualmente, trocar de par
  3. Todo o Rapaz que pede em namoro mais do que uma vez, fica com namoradas cada vez menos desej√°veis
  4. As Raparigas ficam tanto mais favorecidas quanto maior for o n√ļmero de trocas de namorado
  5. Quando um Rapariga livre recebe uma proposta, aceita e fica comprometida
  6. Quando uma Rapariga comprometida recebe nova proposta, compara o novo pretende com o namorado e escolhe ficar com o que lhe favorece mais
  7. Cada Rapaz pede namora às Raparigas seguindo a sua ordem de preferência
  8. Assim que um Rapaz √© rejeitado, prop√Ķe-se imediatamente √† Rapariga seguinte na sua Lista de Prefer√™ncias.

Pseudo-Código

Gale-Shapley Pseudo

NOTA

N√£o importa qual a ordem das propostas dos Rapazes, o Algoritmo acabar√° sempre na mesma Lista


Correção Do Algoritmo de Gale-Shapley

Para toda a inst√Ęncia do problema do relacionamento est√°vel, o algoritmo Gale-Shapley termina com uma lista de relacionamentos est√°veis.

Demonstração
  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.

  1. Provar que o algoritmo termina.

Como nenhum rapaz se pode propor 22 vezes √† mesma Rapariga, o n√ļmero m√°ximo de propostas que poder√° haver s√£o r2r^2, onde r=#Rapazes=#Raparigasr = \#Rapazes = \#Raparigas. Como √© um n√ļmero finito, o Algoritmo tem fim.

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

Se o Rapaz acabou por n√£o ficar relacionado com uma rapariga mm, que preferia em rela√ß√£o √† com quem ficou L‚Ā°(h)\operatorname{L}(h), ent√£o √© porque mm o rejeitou.
Se mm 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

Exemplos da Emulação do Algoritmo

No teste só poderemos usar 22 Maneiras, ambas exemplificadas abaixo.

Maneira 1
Rapazes13>2>1>423>2>4>133>4>1>243>2>1>4Raparigas11>4>3>222>3>1>434>3>1>242>3>4>1\begin{array}{|} \text{Rapazes} & & & & & & & &\\ 1&\quad &3 &> &2 &> &1 &> &4\\ 2&\quad &3 &> &2 &> &4 &> &1\\ 3&\quad &3 &> &4 &> &1 &> &2\\ 4&\quad &3 &> &2 &> &1 &> &4\\ \hline \text{Raparigas} & & & & & & & &\\ 1&\quad &1 &> &4 &> &3 &> &2\\ 2&\quad &2 &> &3 &> &1 &> &4\\ 3&\quad &4 &> &3 &> &1 &> &2\\ 4&\quad &2 &> &3 &> &4 &> &1\\ \end{array}

Resolução:

  1. Rapaz 11 prop√Ķe-se √† Rapariga 33; ela aceita
  2. Rapaz 22 prop√Ķe-se √† Rapariga 33; ela rejeita
  3. Rapaz 33 prop√Ķe-se √† Rapariga 33; ela aceita e rejeita o Rapaz 11
  4. Rapaz 44 prop√Ķe-se √† Rapariga 33; ela aceita e rejeita o Rapaz 33
  5. Rapaz 11 prop√Ķe-se √† Rapariga 22; ela aceita
  6. Rapaz 22 prop√Ķe-se √† Rapariga 22; ela aceita e rejeita o Rapaz 11
  7. Rapaz 11 prop√Ķe-se √† Rapariga 11; ela aceita
  8. Rapaz 33 prop√Ķe-se √† Rapariga 44; ela aceita

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

Maneira 2
Rapazes13>2>1>423>2>4>133>4>1>243>2>1>4Raparigas11>4>3>222>3>1>434>3>1>242>3>4>1\begin{array}{|} \text{Rapazes} & & & & & & & &\\ 1&\quad &3 &> &2 &> &1 &> &4\\ 2&\quad &3 &> &2 &> &4 &> &1\\ 3&\quad &3 &> &4 &> &1 &> &2\\ 4&\quad &3 &> &2 &> &1 &> &4\\ \hline \text{Raparigas} & & & & & & & &\\ 1&\quad &1 &> &4 &> &3 &> &2\\ 2&\quad &2 &> &3 &> &1 &> &4\\ 3&\quad &4 &> &3 &> &1 &> &2\\ 4&\quad &2 &> &3 &> &4 &> &1\\ \end{array}

Resolução:

(1,3)(2,)(3,)(4,)(1,3)(2,3)(3,)(4,)(1,3)(2,3)(3,3)(4,)(1,3)(2,3)(3,3)(4,3)(1,2)(2,3)(3,3)(4,3)(1,2)(2,2)(3,3)(4,3)(1,1)(2,2)(3,3)(4,3)(1,1)(2,2)(3,4)(4,3)\begin{array}{c} (1,3)&(2,)&(3,)&(4,)\\ (1,3)&(2,\cancel{3})&(3,)&(4,)\\ (1,\cancel{3})&(2,\cancel{3})&(3,3)&(4,)\\ (1,\cancel{3})&(2,\cancel{3})&(3,\cancel{3})&(4,3)\\ (1,2)&(2,\cancel{3})&(3,\cancel{3})&(4,3)\\ (1,\cancel{2})&(2,2)&(3,\cancel{3})&(4,3)\\ (1,1)&(2,2)&(3,\cancel{3})&(4,3)\\ (1,1)&(2,2)&(3,4)&(4,3) \end{array}

Consequências

Teorema 1

Todas as poss√≠veis execu√ß√Ķes do algoritmo de Gale-Shapley (tendo os rapazes como proponentes *) produzem o mesmo relacionamento est√°vel, e, neste relacionamento est√°vel, cada rapaz obt√©m a melhor das parceiras que pode ter em qualquer relacionamento est√°vel.

* s√£o os Rapazes que se prop√Ķem √†s raparigas, como descrito inicialmente no Algoritmo. Se fossem as Raparigas as proponentes, os papeis invertiam-se.

Demonstração

Sendo um parceiro est√°vel de h0/m0h_0/m_0, um m1/h1m_1/h_1 par com h0/m0h_0/m_0 numa dada Lista Est√°vel.

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

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

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

QED

Teorema 2

No relacionamento estável optimal para os rapazes, cada rapariga obtém o pior parceiro que pode obter em qualquer relacionamento estável.

NOTA

Relacionamento Est√°vel Otimal para Rapazes/Raparigas:
Relacionamento Estável, onde os Rapazes/Raparigas obtêm o melhor parceiro possível.

Demonstração

Tentando provar por absurdo.

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

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

QED