2.3 Permitindo poligamia

2) Aplique o algoritmo às listas de preferência seguintes, em que há duas mulheres a menos, tanto da perspectiva dos homens propondo, como quando as mulheres propõem:

Victor: C Ana: Z > Y > X > V Wilson: A > B > C Beatriz: Y > X > W > V Xavier: A > C > B Carolina: X > V > Y Yuri: C > A > B

Zé: B > C > A

Resposta: Quando os homens propõem, formam-se os casais

X – C, Y – A e Z – B. Quando as mulheres propõem, formam-se

os casais A – Z, B – Y e C – X. Em ambas as situações, Victor

e Wilson permanecem solteiros.

 

2.3 Permitindo poligamia

O algoritmo, além de conseguir tratar de situações com indiferença e com números desiguais de homens e mulheres, também pode ser adaptado para uma análise das situações em que ocorre pareamento de um indivíduo com mais de um único elemento do outro grupo. Ou seja, iremos discutir agora a situação em que, por exemplo, um homem deseja ter mais de uma companheira.

Faremos isso criando "vagas" ou "slots" para múltiplas mulheres na "carteira" de cada homem.

Procedimento: Para denotar que X escolhe ter 3 parceiras, utilizaremos índices numéricos da seguinte forma: X , X , X , 1 2 3 que significa dizer que cada X corresponde a uma das "vagas" i para parceira de X.

Para ilustrar essa ocorrência, o universo foi determinado de forma aleatória como de 2 homens e 7 mulheres, sendo eles: Xavier (X); Yuri (Y); Ana (A); Beatriz (B); Carolina (C); Débora (D); Érica (E); Flávia (F); Glória (G). Acrescentamos que Xavier deseja ter três parceiras e Yuri procura por duas parceiras. Em consequência disso, Xavier tem três "vagas" para companheira, enquanto que Yuri tem duas "vagas", com um total de cinco vagas, e duas mulheres ficarão solteiras. Débora e Glória, porém, aceitam somente um homem cada. Os agentes têm as seguintes preferências:

Xavier: D > F > C > B > A > G > E Ana: Y > X Yuri: C > D > B > G > E > A > F Beatriz: X > Y

Carolina: X > Y Débora: Y Érica: X > Y Flávia: Y > X Glória: X

Dessa forma, o processo de listagem das preferências que cada uma dessas pessoas faz em relação aos membros do outro grupo é o mesmo. Porém, agora, cada homem tem uma lista para cada "vaga". Para a execução do algoritmo, as vagas são consideradas como "pessoas diferentes". Por outro lado, todas as listas de preferência das vagas de um mesmo homem devem ser as mesmas e idênticas às preferências desse homem. Finalmente, tais vagas são equivalentes nas listas das mulheres, porque correspondem ao mesmo homem:

X : D > F > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X3

X : D > F > C > B > A > G > B: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 E Y2

X : D > F > C > B > A > G > C: X ≡ X ≡ X > Y ≡ 3 1 2 3 1 E Y2

Y : C > D > B > G > E > A > D: Y ≡ Y 1 12 F

Y : C > D > B > G > E > A > E: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 F Y2

F: Y ≡ Y > X ≡ X ≡ 1 2 1 2 X3

G: X ≡ X ≡ X 1 23

À medida que as rodadas se desenvolvem, os homens fazem propostas às mulheres de que mais gostam, escolhendo a primeira mulher em sua lista de preferência com cada uma de suas "vagas". Desse modo, suas vagas, por serem consideradas como pessoas distintas, irão todas propor à mesma mulher, a qual escolhe sempre a primeira opção como uma possível escolha artificial (já discutida no problema de indiferenças) dentre as que são equivalentes.

 

1ª Rodada – propostas e escolhas

Olhando as preferências dos homens em suas listas e a consequente escolha das mulheres quanto às propostas que recebem, temos que X , X e X propõem a Débora, que não os 1 2 3 aceita; Y e Y propõem a Carolina, que seleciona Y e rejeita Y , 1 2 1 2 escolhendo, das duas vagas equivalentes, apenas uma. Assim, a execução desse processo nada difere das anteriores.

X : > F > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X3

X : > F > C > B > A > G > B: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 E Y2

X : > F > C > B > A > G > C: X ≡ X ≡ X > ≡ 3 1 2 3 E Y2

Y : > D > B > G > E > A > D: Y ≡ Y 1 12 F

Y : > D > B > G > E > A > E: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 F Y2

F: Y ≡ Y > X ≡ X ≡ 1 2 1 2 X3

G: X ≡ X ≡ X 1 23

Como os homens têm algumas de suas "vagas" rejeitadas, novas propostas são feitas de modo que se modifique as tabelas:

 

2ª Rodada – propostas e escolhas

 

Y D ∴ D: Y 22

X , X , X F ∴ F: X 1 2 31

Y C ∴ C: Y 11

Com as novas propostas, obtemos:

X : > > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X3

X : > > C > B > A > G > B: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 E Y2

X : > > C > B > A > G > C: X ≡ X ≡ X > ≡ 3 1 2 3 E Y2

Y : > D > B > G > E > A > D: Y ≡ 1 1 F

Y : > > B > G > E > A > E: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 F Y2

F: Y ≡ Y > ≡ X ≡ 1 2 2 X3

G: X ≡ X ≡ X 1 23

Como ainda há rejeições, no caso de X e X , ocorre uma terceira 2 3 rodada:

 

3ª Rodada – propostas e escolhas

X : > > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X3

X : > > > B > A > G > B: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 E Y2

X : > > > B > A > G > C: X ≡ ≡ X > ≡ 3 1 3 E Y2

Y : > D > B > G > E > A > D: Y ≡ 1 1 F

Y : > > B > G > E > A > E: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 F Y2

F: Y ≡ Y > ≡ X ≡ 1 2 2 X3

G: X ≡ X ≡ X 1 23

É importante destacar que, como as listas de preferência de cada "vaga" de um mesmo homem têm a mesma ordenação das mulheres, as propostas a uma mesma mulher serão frequentes. Quando a vaga faz uma proposta, a mulher escolhida já pode estar alocada com outra vaga do mesmo homem, o que resulta na permanência da vaga original, segundo nosso critério de não trocar equivalentes. Exemplo disso é que Débora rejeitará Y porque já 1 está alocada com Y : 2

 

4ª Rodada – propostas e escolhas

X : > > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X3

X : > > > B > A > G > B: X ≡ X ≡ > Y ≡ 2 1 2 1 E Y2

X : > > > > A > G > C: X ≡ ≡ X > Y ≡ 3 1 3 1 E Y2

Y : > > B > G > E > A > D: Y ≡ 1 1 F

Y : > > B > G > E > A > E: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 F Y2

F: Y ≡ Y > ≡ X ≡ 1 2 2

X3

G: X ≡ X ≡ X 1 23

 

5ª Rodada – propostas e escolhas

X : > > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X3

X : > > > B > A > G > B: X ≡ X ≡ > Y ≡ 2 1 2 1 E Y2

X : > > > > A > G > C: X ≡ ≡ X > Y ≡ 3 1 3 1 E Y2

Y : > > > G > E > A > D: Y ≡ 1 1 F

Y : > > B > G > E > A > E: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 F Y2

F: Y ≡ Y > ≡ X ≡ 1 2 2

X3

G: X ≡ X ≡ X 1 23

 

6ª Rodada – propostas e escolhas

X : > > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X3

X : > > > B > A > G > B: X ≡ X ≡ > Y ≡ 2 1 2 1 E Y2

X : > > > > A > G > C: X ≡ ≡ X > Y ≡ 3 1 3 1 E Y2

Y : > > > > E > A > D: Y ≡ 1 1 F

Y : > > B > G > E > A > E: X ≡ X ≡ X > Y ≡ 2 1 2 3 1 F Y2

F: Y ≡ Y > ≡ X ≡ 1 2 2

X3

G: X ≡ X ≡ X 1 23

 

7ª Rodada – propostas e escolhas

X : > > C > B > A > G > A: Y ≡ Y > X ≡ X ≡ 1 1 2 1 2 E X 3

X : > > > B > A > G > B: X ≡ X ≡ > Y ≡ 2 1 2 1 E Y 2

X : > > > > A > G > C: X ≡ ≡ X > Y ≡ 3 1 3 1 E Y 2

Y : > > > > > A D: Y ≡ 1 1 > F

Y : > > B > G > E > A > E: X ≡ X ≡ X > ≡ 2 1 2 3 F Y 2

F: Y ≡ Y > ≡ X ≡ 1 2 2 X 3

G: X ≡ X ≡ X 1 23

Segundo a tabela, Xavier consegue então se unir a Beatriz, Carolina e Flávia, enquanto Yuri se estabelece com Débora e Érica. Consequentemente, por não haver mais "vagas" disponíveis, Ana é forçada a ficar solteira, ao passo que Glória fica solteira por escolha própria, por preferir isso a ser pareada com Yuri.

A partir desses resultados, percebemos que não há nenhuma ocorrência de instabilidade, mesmo quando expandimos esse algoritmo a situações em que o emparelhamento ocorre entre mais do que um indivíduo com um outro. Isso porque, ao repetirmos as listas de preferências, ao invés de modificarmos o algoritmo, transformamos os polígamos Xavier e Yuri em X , X , X , Y e Y , 1 2 3 1 2 de modo que utilizamos nessa resolução tanto a repetição da lista dos polígamos como o algoritmo Gale-Shapley.

Note que outros conjuntos de listas de preferência podem resultar em agentes polígamos sem preencher todas as suas "vagas".

 

Exercícios

1) Aplique o algoritmo, agora do ponto de vista da proposta feita pelas mulheres, às mesmas listas de preferência, reproduzidas a seguir:

Ana: Y > X Xavier (3 vagas): D > F > C > B > A > G

> E

Beatriz: X > Y Yuri (2 vagas): C > D > B > G > E > A >

F

Carolina: X >

Y

Débora: Y

Érica: X > Y

Flávia: Y > X

Glória: X

Resposta: Novamente obtemos X – {B, C, F} e Y – {D, E},

enquanto Ana é forçada a ficar solteira e Glória o faz por opção

(Yuri a preferiria a Érica).

2) Aplique o algoritmo, uma vez para propostas feitas pelos homens, outra pelas mulheres, às listas de preferência abaixo, verificando quais mulheres ficam solteiras e se de forma forçada (rejeitadas por todos os homens) ou não:

R (3 vagas): D > A > F > G > C > E > B > A: T > S > H R S (1 vaga): G > B > C > A > F > D > E > B: S > R > H T T (2 vagas): G > E > A > F > C > D > B > C: R > T > H S

D: T > S

E: R > S >

T

F: S > T >

R

G: T > R

H: R

Resultado: Com os homens propondo, obtemos R – {A, C, F},

S – B e T – {E, G}, enquanto D fica solteira por opção e H

porque ninguém lhe propõe. Com as mulheres propondo, a

situação das solteiras é a mesma, porém, R – {C, E, F}, S – B e

T – {A, G}.

 

Solução sem multiplicações

O procedimento descrito acima para tratar a poligamia é muito ineficiente, ao fazer várias vagas atuarem como pessoas e proporem repetidamente a um mesmo indivíduo, mesmo quando este já rejeitou uma vaga semelhante ou está alocado a outra vaga semelhante.

Podemos, tanto nestes exemplos pequenos como na prática computacional, trabalhar com as listas originais e manter, também, registros dos totais de vagas para cada agente e as respectivas quantidades de vagas ainda disponíveis ou não preenchidas. Com esse formato, mantemos, para cada "carteira", uma listagem temporária de "associados" e, quando completa, substituímos os associados menos preferidos por aqueles que estão ingressando.