2.2 Trabalhando com números diferentes de indivíduos

Otávio (O): N > M > I > J ≡ Isabella (I): O > P ≡ S > T L > R Pedro (P): N ≡ J > I > M > Joana (J): O ≡ T ≡ S > R > L P Roberto (R): L > I ≡ N > J Laura (L): R > S ≡ T ≡ O ≡ > M P Sérgio (S): I > M > N ≡ L ≡ Marina (M): O ≡ P ≡ R > T J > S Thiago (T): L > J ≡ I > M > Natália (N): S ≡ O ≡ R > T N ≡ P

Resposta: Com a proposta dos homens às mulheres, obtemos

os seguintes resultados: O – N; P – M; R – L; S – I e T – J.

Neste caso, a regra de indiferença é utilizada quando I não

troca S por P. Com as mulheres sendo quem propõe, os pares

formados são: I – P; J – T; L – R; M – O e N – S.

4) Verifique que, com as listas do exercício anterior e substituindo imediatamente o símbolo "≡" pelo símbolo ">", obtemos casais diferentes quando o emparelhamento é realizado segundo as propostas dos homens: O – N; P – I; R – L; S – M e T – J.

 

2.2 Trabalhando com números

diferentes de indivíduos

O algoritmo também pode ser utilizado para tratar de situações de alocações com números desiguais de, por exemplo, homens e mulheres. Veremos como acomodar essa diferença em três momentos: com a adição de novos agentes "curingas" nas listas de preferência; sem o uso de curingas, reformulando as condições de conclusão do algoritmo (isto é, quando sabemos que o procedimento chegou ao final); com a consideração de listas incompletas de preferência, que é o tratamento mais geral e do qual nos serviremos no restante do livro.

Solução com curingas

Acrescentar um "curinga" ou um novo objeto à estrutura existente é um artifício ubíquo em raciocínios matemáticos. O curinga será considerado um novo agente, terá uma lista de preferência própria e deverá ser incluído nas listas de preferência dos agentes originais.

Para realizar isso, se o indivíduo não informa nada a não ser a listagem de uma ordem de preferência pelas pessoas do outro grupo, o curinga é colocado no final de sua lista de preferência. Por outro lado, se essa pessoa informar (ou o sistema acomodar essa informação), o curinga pode ir em qualquer lugar na ordem de preferência desse indivíduo, separando quem essa pessoa gostaria de casar de quem ela não aceitaria. Esse curinga pode, inclusive, ir no começo de uma lista de preferência ao ser também utilizado como uma preferência pelas pessoas que escolhem ficar sozinhas a parear-se com quaisquer pessoas do outro grupo. Porém, se um indivíduo for alocado a um curinga sem que esta fosse sua preferência, significa que todas as pessoas do grupo oposto rejeitaram sua proposta, de modo que, ao ser alocado a um curinga, esta pessoa fica solteira.

Em razão dessa possibilidade, finalmente iremos tratar de ocorrências em que um agente acredita que determinada alocação é pior do que continuar sem combinação, no caso, continuar solteiro; porém, descobriremos uma imperfeição nesse procedimento, relacionada à assimetria entre quem propõe e quem apenas seleciona propostas.

Notação: Para denotar o curinga, utilizaremos o símbolo ■.

Para ilustrar essa problemática, o universo foi montado como de 5 homens e 4 mulheres, sendo eles: Victor (V); Wilson (W); Xavier (X); Yuri (Y); Zé (Z); Beatriz (B); Carolina (C); Débora (D); Érica (E) .

Deste modo, mais uma vez é iniciado o processo com a listagem que cada uma dessas pessoas faz dos membros do outro grupo de acordo com uma ordem de preferência para a escolha de seu parceiro de casamento; com a diferença, entretanto, de que, agora, eles podem incluir o curinga em sua lista de preferência quando e se preferirem ficar solteiros a escolher alguma das opções que ainda não listaram.

Incluímos uma lista de indiferença para o curinga, de modo a contemplá-lo no algoritmo.

Victor: C > D > ■ > E > B Beatriz: Y > X > Z > V > W Wilson: B > E > C > D > ■ Carolina: W > X > Y > V > Z Xavier: B > C > E > D > ■ Débora: X > Z > Y > V > W Yuri: C > B > D > E > ■ Érica: W > Z > X > Y > V Zé: D > B > C > E > ■ ■: V ≡ W ≡ X ≡ Y ≡ Z

A partir da listagem dessas preferências, de acordo com o processo já explicado anteriormente, começam as rodadas de propostas dos homens às mulheres que acreditam ser as mais preferíveis e subsequentes escolhas de cada mulher pelo melhor homem dentre os que lhe propõe.

 

1ª Rodada – propostas

 

Victor: C> D > ■ > E > B V C

 

Wilson: B> E > C > D > ■ W B

 

Xavier: B> C > E > D > ■ X B

 

Yuri: C> B > D > E > ■ Y C

 

Zé: D> B > C > E > ■ Z D

 

1ª Rodada – escolhas

W, X B B: Y > X > Z > V > W ∴ B : X

V, Y C C: W > X > Y > V > Z ∴ C : Y Z D D: X > Z > Y > V > W ∴ D : Z ∅ E E: W > Z > X > Y > V

■: V ≡ W ≡ X ≡ Y ≡ Z

Conforme as decisões desses indivíduos, na rodada seguinte temos:

 

2ª Rodada – propostas e escolhas

Victor: Ĉ > D > ■ > E > B Beatriz: Y > X > Z > V > W Wilson: B > E > C > D > Carolina: W > X > Y > V >Z ■

Xavier: B > C > E > D > ■ Débora: X > Z > Y > V > W Yuri: C> B > D > E > ■ Érica: W > Z > X > Y > V Zé: D> B > C > E > ■ ■: V ≡ W ≡ X ≡ Y ≡ Z

Na terceira rodada, Victor, como o único homem rejeitado, faz uma nova proposta:

 

3ª Rodada – propostas e escolhas

 

Victor: > > > E > B Beatriz Y > > Z > V > W

Wilson: > > C > D > ■ Carolina: W > X > > V

>Z

Xavier: > C > E > D > Débora: X > > Y > V > ■ W

Yuri: > B > D > E > ■ Érica: > Z > X > Y > V

Zé: > B > C > E > ■ ■: ≡ W ≡ X ≡ Y ≡ Z

Logo, o processo termina aqui, quando todos os agentes estão ou pareados com alguém do grupo oposto ou solteiros.

Esse exemplo é particular, no sentido de que o número de mulheres é exatamente um a menos que o de homens, de modo que algum homem ficaria solteiro (não haveria mulheres o suficiente para todos os homens). Entretanto, nenhum homem foi alocado a um curinga por ter suas propostas rejeitadas por todas as mulheres, devido ao fato de que Victor, de livre e espontânea vontade (ou seja, segundo sua lista de preferências), escolheu ficar sozinho. Isso porque, para ele, se ele não casasse com Carolina ou Débora, não haveria nenhuma outra mulher com quem ele aceitaria se casar; assim, ao ser sua terceira opção continuar solteiro, Victor esclarece que, para ele, qualquer casamento com as demais mulheres (Érica ou Beatriz) seria inaceitável, isto é, seria pior do que continuar solteiro.

Contudo, se Victor tivesse uma lista de preferência diferente, em que preferisse Érica e Beatriz à opção de ficar solteiro (ou seja, ficar solteiro seria sua última opção), ele ainda seria o homem solteiro da alocação (agora forçado), uma vez que, com a continuação do processo, suas propostas a Érica e Beatriz seriam ambas rejeitadas.

Outras listas de preferência, é claro, podem levar a situações distintas.

Em geral, podemos usar mais curingas, de modo que sua quantidade corresponda à diferença exata entre os totais dos grupos, sendo que, em cada lista de preferência, eles devem estar contíguos e ser equivalentes (por motivos de lógica). Por exemplo, se forem 5 homens e 3 mulheres, teremos dois curingas em sequência na lista de preferências fornecida por cada homem.

 

Exercício

1) Aplique o algoritmo do ponto de vista da proposta feita pelas mulheres, a partir das mesmas listas de preferências acima, verificando qual dos homens ficaria solteiro e se seria de forma forçada (rejeitado por todas as mulheres) ou por opção (propondo ao curinga antes de alguma mulher). Repetimos as listas abaixo:

Beatriz: Y > X > Z > V > W Victor: C > D > ■ > E > B Carolina: W > X > Y > V > Z Wilson: B > E > C > D > ■ Débora: X > Z > Y > V > W Xavier: B > C > E > D > ■ Érica: W > Z > X > Y > V Yuri: C > B > D > E > ■ ■: V ≡ W ≡ X ≡ Y ≡ Z Zé: D > B > C > E > ■

Resposta: Ao verificarmos que os pares formados são B – Y, C

– X, D – Z, E – W, percebemos que Victor continua a ser o

homem que fica solteiro, de forma forçada, uma vez que

nenhuma mulher lhe propõe. Note que, neste caso, há menos

agentes proponentes que receptores.

Observação: Nossa conclusão sobre curingas servirem para separar opções "aceitáveis" e "inaceitáveis" é natural e válida para os agentes proponentes (homens), devido ao fato de suas molduras deslocarem-se sempre da opção mais preferida para a menos preferida durante a execução de Gale-Shapley. Porém, o deslocamento contrário para os agentes seletores (mulheres) inviabiliza essa manobra.

Tentar resolver esse problema só gera confusão: por exemplo, se pusermos as opções inaceitáveis antes do curinga e as aceitáveis depois, contrariamente ao próprio espírito de ordenação das listas de preferência, nem assim obteremos uma solução.

Não devemos pensar nisso como um defeito do artifício de usar curingas, que tem o mérito de destacar essa confusão assim que se pensa no caso, mas como um reflexo do exagero no seu uso.

Para o problema inicial de números diferentes de indivíduos, os curingas podem ser utilizados sem problemas, sempre ao final das listas de preferência originais; no entanto, procuraremos, também, uma solução diferente.

Depois retomaremos a questão das opções inaceitáveis (na literatura, o curinga pode aparecer, em uma lista de preferência, usado para tão somente delimitar as opções aceitáveis e as inaceitáveis).

 

Solução sem curingas

Como visto acima, a utilização do curinga é um facilitador para a resolução de problemas com diferentes números de indivíduos. Entretanto, existe uma outra forma de tornar esta situação-problema resolvível através da modificação das condições de encerramento do algoritmo.

Note que, nas explicações e exemplos até aqui, definimos que o algoritmo chegava ao fim quando todos os agentes que faziam as propostas estavam pareados a agentes do outro conjunto. Então, acordamos que o processo continua enquanto algum proponente ainda tiver, em sua lista de preferência, alguns candidatos seletores a quem propor. Ou seja, o processo termina quando, após uma rodada completa de propostas e escolhas, cada proponente ou está pareado a algum seletor ou foi rejeitado por todos, terminando solteiro.

 

Exercício

1) Quais alterações são necessárias no programa de computador descrito na Seção 1.4 para acomodar essa nova condição de parada e os números diferentes de homens e mulheres?

No caso específico de o número de agentes proponentes ser menor que o de seletores, digamos h homens e m mulheres com h ≤

m, o encerramento do processo pode ser descrito de outro modo: é

quando h mulheres diferentes estão pareadas. Porém, essa descrição não será válida no caso de listas incompletas, que adotaremos a seguir.

 

Listas incompletas de preferência

Uma solução que comporta a manifestação de opções aceitáveis ou inaceitáveis é, simplesmente, não listar as opções inaceitáveis nas listas de preferência, isto é, cada homem listará somente as mulheres com as quais aceita se casar e cada mulher listará somente os homens que considera aceitáveis. Naturalmente, as listas podem ter números variados de integrantes e deverão ser tratadas com a formulação do algoritmo que trata números diferentes de indivíduos. O novo procedimento sempre encontrará uma solução estável, em um número finito de etapas, mas poderá acontecer que agentes (possivelmente todos) resultem solteiros.

Por exemplo, A: X > Y significa que A prefere X e depois Y, mas se não for emparelhado com nenhum dos dois, A prefere não admitir nenhum outro agente. Analogamente, a lista X: A significa que X prefere o agente A mas se não conseguir tal resultado, então prefere não ter nenhum outro. (Alguns autores exprimem que tal agente será "alocado a si mesmo".)

Nessa situação, os agentes rejeitam automaticamente as propostas vindas de quem não está em suas listas, de modo que, para acelerar o procedimento, podemos previamente remover A da lista de X se X não está na lista de A (porque A não aceitaria X), no caso de X propor e A selecionar. Também, após a montagem das listas de preferência, podemos retirar do procedimento quem já não aceita ninguém como parceiro.

É com esta formulação em mente que trabalharemos a partir de agora, ao expressar as listas de preferência dos nossos exemplos.

 

Exercícios

1) 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: A Ana: Z > W > V > Y > X Wilson: A > C > B Beatriz: V > X > Y > Z > W Xavier: B > C > A Carolina: Z > W > V > X > Y Yuri: A > B

Zé: C > A > B

Resposta: Em ambas as situações, Victor e Yuri permanecem

solteiros, enquanto se formam os casais W – A, X – B e Z – C.