Projeto e Análise de Algoritmos I

Aula 02 - Emparelhamento Estável

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica

Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado, André Grahl Pereira, Lucas Nunes Alegre, Marcus Ritt e Luciana Buriol.

Emparelhamento Estável

Emparelhamento entre Hospitais e Médicos

Objetivo: Dado um conjunto de preferências entre hospitais e estudantes de medicina, definir um processo de admissão autoimposto.

Par Instável: estudante e e hospital h são instáveis se:

e prefere h ao seu hospital atribuído; e
h prefere e a um dos seus estudantes aprovados.

Emparelhamento Estável:

Interesse próprio força a atribuição e previne acordos unilaterais.

Exemplo: Empresas e estudantes.

Problema de Emparelhamento Estável

Objetivo: Dado um conjunto de n hospitais e um conjunto de n estudantes, encontrar uma atribuição adequada.

Participantes ranqueiam membros do grupo oposto.
Cada hospital lista estudantes em ordem de preferência da melhor para a pior.
Cada estudante lista hospitais em ordem de preferência do melhor para o pior.

Exemplo de Instância (3 hospitais, 3 estudantes):

Preferências dos Hospitais:

h_1 \colon e_1 \succ e_2 \succ e_3
h_2 \colon e_2 \succ e_1 \succ e_3
h_3 \colon e_1 \succ e_2 \succ e_3

Preferências dos Estudantes:

e_1 \colon h_2 \succ h_1 \succ h_3
e_2 \colon h_1 \succ h_2 \succ h_3
e_3 \colon h_1 \succ h_2 \succ h_3

Emparelhamento Perfeito

Def. Um emparelhamento S é um conjunto ordenado de pares h-e com h \in H e e \in E tal que cada hospital h \in H e cada estudante e \in E aparece no máximo em um par de S.

Def. Um emparelhamento S é perfeito se |S|=|H|=|E|=n.

Exemplo de Emparelhamento Perfeito:

H = \{h_1, h_2, h_3\} e E = \{e_1, e_2, e_3\}
S = \{(h_1, e_2), (h_2, e_1), (h_3, e_3)\}

Par Instável

Def. Dado um emparelhamento perfeito S, um hospital h e uma estudante e são um par instável se:

h prefere e a seu parceiro atual; e

e prefere h a seu parceiro atual.

Obs. Um par instável (h, e) pode melhorar seus parceiros com uma ação conjunta.

Exemplo:

Preferências:

h_1 \colon e_1 \succ e_2
h_2 \colon e_1 \succ e_2
e_1 \colon h_1 \succ h_2
e_2 \colon h_1 \succ h_2

Emparelhamentos:

\{(h_1, e_1), (h_2, e_2)\} é estável
\{(h_1, e_2), (h_2, e_1)\} é instável
(pois h_1 e e_1 formam um par instável)

Problema de Emparelhamento Estável

Def. Um emparelhamento estável é um emparelhamento perfeito sem pares instáveis.

Problema: Dadas listas de preferências de n hospitais e n estudantes, encontrar um emparelhamento estável (se existir).

Natural, desejável, condição autoimposta.
Interesse próprio previne qualquer hospital-estudante trocar de pares.

Problema de Emparelhamento Estável

P: Emparelhamentos estáveis sempre existem?

Problema: Colega de Quarto Estável.

2n pessoas.
Cada pessoa ranqueia outras pessoas de 1 até 2n-1.
Atribuir pares de colegas de quarto sem pares instáveis.
Emparelhamentos estáveis nem sempre existem.
Note que nesse caso não há a separação em dois grupos isolados.

Problema de Emparelhamento Estável

P: Emparelhamentos estáveis sempre existem?

	1ª	2ª	3ª
A	B	C	D
B	C	A	D
C	A	B	D
D	A	B	C

Observações sobre instabilidades:

A–B, C–D \Rightarrow B–C instável
A–C, B–D \Rightarrow A–B instável
A–D, B–C \Rightarrow A–C instável

Conclusão: Não existe emparelhamento perfeito que seja estável neste exemplo.

P: Como encontrar um emparelhamento estável?

Algoritmo Gale-Shapley

Algoritmo intuitivo que garante encontrar um emparelhamento estável.

\begin{algorithmic} \Procedure{Gale-Shapley}{$H, E$} \State Inicialize $S \gets \emptyset$, e todos os hospitais e estudantes como livres \While{existe um hospital livre $h$ que ainda não propôs a todo estudante} \State Escolha um tal hospital $h$ \State Seja $e$ o estudante de maior preferência de $h$ ao qual $h$ ainda não propôs \If{$e$ está livre} \State $S \gets S \cup \{(h, e)\}$ \Else \State $e$ está atualmente emparelhado com $h'$ \If{$e$ prefere $h'$ a $h$} \State $h$ continua livre \Else \State $S \gets S \setminus \{(h', e)\}$ \State $S \gets S \cup \{(h, e)\}$ \State $h'$ fica livre \EndIf \EndIf \EndWhile \State \Return $S$ \EndProcedure \end{algorithmic}

Análise de Gale-Shapley

Algoritmo Gale-Shapley

O que mostrar?

Item 1: Emparelhamento perfeito.

Item 2: Sem pares instáveis.

Item 3: Algoritmo G-S termina.

Item 4: Justiça.

Prova de Corretude: Emparelhamento Perfeito

Afirmação. No Algoritmo G-S, todos os hospitais e estudantes são emparelhados.

Prova. Prova por contradição.

Suponha para o efeito de contradição que o hospital h não está pareado quando o algoritmo termina.
h foi rejeitado por todos os estudantes na sua lista.
Então todos os estudantes têm um par ao fim do algoritmo que elas preferem a h.
Mas o número de hospitais e estudantes é o mesmo. Então, todo hospital possui um par, inclusive h, o que gera uma contradição. \blacksquare

Algoritmo Gale-Shapley

O que mostrar?

Item 1: ~~Emparelhamento perfeito.~~

Item 2: Sem pares instáveis.

Item 3: Algoritmo G-S termina.

Item 4: Justiça.

Prova de Corretude: Emparelhamento Estável

Afirmação. No Algoritmo G-S, não existem pares instáveis.

Prova. S é perfeito. Suponha para o efeito de contradição que o par (h, e) \in S é instável.

Caso 1: h nunca propôs a e.
- h prefere seu par atual a e.
- (h, e) é estável.

Caso 2: h propôs a e.
- e rejeitou h (imediatamente ou depois).
- e prefere seu par atual a h.
- (h, e) é estável.
Em ambos os casos, o par (h, e) é estável. \blacksquare

Algoritmo Gale-Shapley

O que mostrar?

Item 1: ~~Emparelhamento perfeito.~~

Item 2: ~~Sem pares instáveis.~~

Item 3: Algoritmo G-S termina.

Item 4: Justiça.

Prova de Corretude: Terminação

Obs. Hospitais propõem para estudantes em ordem decrescente de preferência (apenas piora).

Obs. Assim que uma estudante é proposta, ela nunca fica sozinha, ela apenas troca a proposta atual por uma proposta melhor (apenas melhora).

P: Como provar que o algoritmo termina?

P: Como medir progresso? . . . Número de indivíduos livres? . . . Número de pares? . . . Número de propostas realizadas?

Prova de Corretude: Terminação

Afirmação. O algoritmo termina no máximo após n^2 iterações do loop.

Prova. A cada iteração do loop um hospital propõe para uma nova estudante. Existem apenas n^2 possíveis propostas. \blacksquare

Hospitais

	1ª	2ª	3ª	4ª	5ª
V	A	B	C	D	E
W	B	C	D	A	E
X	C	D	A	B	E
Y	D	A	B	C	E
Z	A	B	C	D	E

Estudantes

	1ª	2ª	3ª	4ª	5ª
A	W	X	Y	Z	V
B	X	Y	Z	V	W
C	Y	Z	V	W	X
D	Z	V	W	X	Y
E	V	W	X	Y	Z

Exemplo: Pior caso.

Pior Caso

Afirmação. O algoritmo realiza no máximo n(n-1)+1 propostas.

Prova.

Uma estudante, ao receber uma proposta, nunca mais volta a ficar livre.
O algoritmo termina no exato momento em que o último estudante livre é comprometida.
No pior caso, antes dessa última proposta, os outros (n-1) estudantes já receberam propostas de todos os n hospitais.
Isso totaliza n(n-1) propostas feitas a essas estudantes.
A proposta seguinte é feita à estudante restante e encerra o algoritmo.
Portanto, o número máximo de propostas é \underbrace{n}_{\text{hospitais}} \underbrace{(n-1)}_{\text{rejeições}} + \underbrace{1}_{\text{final sem rejeição}} = n^2 - n + 1. \blacksquare

Resumo

Teorema. [Gale-Shapley 1962] O algoritmo Gale-Shapley garante encontrar um emparelhamento estável para qualquer instância do Problema de Emparelhamento Estável.

P: Se existem múltiplos emparelhamentos estáveis, qual o algoritmo G-S irá retornar? A ordem das propostas importa?

Algoritmo Gale-Shapley

O que mostrar?

Item 1: ~~Emparelhamento perfeito.~~

Item 2: ~~Sem pares instáveis.~~

Item 3: ~~Algoritmo G-S termina.~~

Item 4: Justiça.

Justiça

Entendendo a Solução

P. A ordem em que os hospitais são selecionados para propor muda o resultado do algoritmo?

Def. Uma estudante e é uma parceiro viável para um hospital h se existe algum emparelhamento estável com o par (h, e).

Exemplo:

h - e, e'.
h' - e, e'.
e - h, h'.
e' - h, h'.
Apenas e é viável para h.

Entendendo a Solução

Def. Uma estudante e é uma parceiro viável para um hospital h se existe algum emparelhamento estável com o par (h, e).

Atribuição Hospital-Ótima: Todo hospital recebe o melhor parceiro viável.

É um emparelhamento perfeito?
É um emparelhamento estável?

Afirmação. Toda execução do algoritmo G-S retorna uma atribuição hospital-ótima.

Corolário. Uma atribuição hospital-ótima é um emparelhamento estável.

Otimalidade para Hospitais

Afirmação. O algoritmo G-S é hospital-ótimo: cada hospital recebe sua melhor parceiro viável.

Prova. Por contradição.

[Hipótese] Suponha que algum hospital não termina com suo melhor parceiro viável.

Como os hospitais propõem em ordem decrescente de preferência, algum hospital foi rejeitado por um parceiro viável.
Seja h o primeiro hospital rejeitado por um parceiro viável, e e = \text{best}(h) esso parceiro.
- (Até esse momento, nenhum outro hospital foi rejeitado por uma viável.)
Quando e rejeita h, ela se compromete com outro pretendente h' — logo e prefere h' a h.

Otimalidade para Hospitais — Estrutura da Contradição

[Construção] e é viável para h, logo por definição existe emparelhamento estável S' com (h, e).

Seja e' o parceiro de h' em S' (com e' \neq e).
Em E: quando h' propôs a e, ainda não havia sido rejeitado por nenhuma viável — pois h foi o primeiro!
e' é viável para h' (estão em S'). Se h' tivesse proposto a e' antes e e' o rejeitasse → h' seria o primeiro rejeitado, não h — contradição!
Logo h' ainda não propôs a e' ⟹ h' prefere e a e'.
Temos: h' prefere e a e' e e prefere h' a h ⟹ (h', e) bloqueia S'. \blacksquare

Execução E do G-S

↛

→

h′

e rejeita h e prefere h′

Emparelhamento estável S′

↔

h′

↔

e′

h′ prefere e a e′

e prefere h′ a h

⟹ (h′, e) bloqueia S′ — contradição!

Conclusão: Todo hospital termina com suo melhor parceiro viável no algoritmo G–S.

Entendendo a Solução

P: O que acontece com os estudantes?

Pessimalidade para Estudantes: Cada estudante recebe o pior parceiro viável.

Pessimalidade para Estudantes

Afirmação. O algoritmo G-S é estudante-péssimo.

Prova. Por contradição. Suponha que o hospital h é atribuído a e em S^*, mas h não é o pior parceiro viável de e.

Então existe um emparelhamento estável S' em que e é pareado com um hospital h', de quem e gosta menos do que h.
\Rightarrow e prefere h a h'.
Seja e' \neq e o parceiro de h em S'. Por otimalidade para hospitais, e é o melhor parceiro viável para h (foram pareados em S^*).
\Rightarrow h prefere e a e'.
Então, (h, e) é um par instável em S', uma contradição. \blacksquare

Emparelhamento de Empresas e Alunos

Exemplo: Hospitais \approx Empresas, Estudantes \approx Alunos.

Variação 1: Alguns participantes declaram outros como inaceitáveis.

Variação 2: Números diferentes de hospitais e estudantes.

Variação 3: Poligamia limitada.

Def. Um emparelhamento S é instável se há uma empresa e e um aluno a tal que:

e e a são aceitáveis mutuamente; e

a não está emparelhado, ou a prefere e a sua empresa atual; e

e não preencheu todas as suas vagas, ou e prefere a a um dos seus atuais estagiários.

Contexto Histórico

Nomeado em homenagem a David Gale e Lloyd Shapley, que o publicaram em 1962.
Já era utilizado desde o início da década de 1950 no National Resident Matching Program (NRMP), para alocação de médicos residentes nos EUA.

Contexto Histórico

National Resident Matching Program.

Processo de decisão centralizada.
38.000 estudantes e 28.000 posições.

Nobel de Economia em 2012

Lloyd Shapley: Teoria de emparelhamento estável e algoritmo G-S.

Alvin Roth: Aplicação do algoritmo G-S no problema de hospitais e estudantes, e doadores de órgãos com pacientes.

Uma Aplicação Moderna

Content delivery networks (CDNs). Distribute much of world’s content on web.

User. Preferences based on latency and packet loss.
Web server. Preferences based on costs of bandwidth and co-location.
Goal. Assign billions of users to servers, every 10 seconds.

Akamai

Implementação em Python

Github