2 - Três extensões do problema

 

Nossa apresentação do algoritmo de Gale-Shapley, no capítulo anterior, concentrou-se em um caso particular: mesmo número de homens (agentes proponentes) e mulheres (agentes seletores), com listas de preferência estritamente ordenadas e cada homem ou mulher sendo emparelhado a um único parceiro.

Agora, relaxaremos cada uma dessas condições, trabalhando, também, com situações de indiferença, números diferentes de homens e mulheres e casos de poligamia. Veremos que algumas dessas situações podem ser resolvidas por métodos novos, ainda que inspirados no original.

Porém, destacaremos que as três situações podem ser reduzidas ao cenário já estudado e resolvidas com o mesmo algoritmo. Uma redução de um problema B a um problema A é simplesmente uma transcrição da situação de B na linguagem e no contexto de A. Desse modo, resolvendo o problema assim transcrito com o método de A, obtemos uma solução de B invertendo a transcrição feita.

Nós veremos mais reduções nos capítulos seguintes, especialmente a de emparelhamento ao problema geral de otimização linear.

Também introduziremos a operação com listas incompletas de preferência, que adotaremos no restante do livro.

 

2.1 Trabalhando com indiferenças

Na situação-problema descrita e utilizada no capítulo anterior, tanto os homens como as mulheres, ao listarem uma ordem de preferência pelos indivíduos do grupo oposto segundo seus gostos, sempre esclareceram quais eram estas preferências. Entretanto, nem sempre uma determinada pessoa tem preferência sobre outras: assim, é necessário discutir situações em que há indiferença.

Definição: Utilizamos o conceito de indiferença para denotar situações em que dois ou mais elementos não são um mais preferido que o outro por alguém, em uma lista de preferência.

Dessa forma, mais uma vez, a título de exemplo para essa nova situação-problema, o universo foi determinado de forma aleatória como de homens e mulheres, sendo eles: Victor (V); Wilson (W); Xavier (X); Yuri (Y); Zé (Z); Ana (A); Beatriz (B); Carolina (C); Débora (D); Érica (E).

Como no exemplo anterior, cada uma dessas pessoas deve listar os membros do outro grupo de acordo com uma ordem de preferência para a escolha de seu parceiro de casamento, porém com a ressalva de que, agora, pode exprimir a equivalência entre alguns indivíduos, se houver.

Notação: Para denotar que A é indiferente, isto é, não tem preferência por X ou Y, utilizaremos o símbolo "≡", de modo que X ≡ Y significa: para A, o indivíduo X não é mais ou menos A

preferível a Y, ou seja, ambos são equivalentes.

Assim, o primeiro passo é que as pessoas de ambos os grupos listem as pessoas do grupo oposto segundo uma ordem de preferência ou indiferença:

Vitor: A ≡ C > D > E > Ana: Z > V ≡ W > Y > X

B Beatriz: V > X ≡ Y ≡ Z >

Wilson: A > D > E > B W

≡ C Carolina: Z > W ≡ V > X

Xavier: C ≡ D > B > E ≡ > Y

A Débora: V > W ≡ Y ≡ X ≡

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

Uma vez esclarecidas as preferências e indiferenças de cada pessoa, começam as propostas dos homens às mulheres de que mais gostam, seja cada uma determinada (se há somente uma preferida), seja escolhida aleatoriamente (dentre as equivalentes).

Precisamos explicitar uma nova regra: se uma pessoa recebe uma nova proposta e, para ela, são equivalentes o novo candidato e quem ela havia escolhido na rodada anterior, então ela não trocará de parceiro, pois não haveria um ganho ao trocar o que "já tem" por algo que é "igual".

Observação: Substituindo o símbolo "≡" pelo símbolo ">", obtemos listas estritamente ordenadas com as quais já sabemos trabalhar. Suponha que conhecemos um emparelhamento estável de acordo com essas novas listas: então, não há um homem e uma mulher que se prefiram aos seus respectivos pares, ou seja, se temos os casais I – P e J – Q então P > Q ou J > I. Desse modo, 1 Q segundo as listas originais, P > Q ou P ≡ Q ou J > I ou J≡ I. 1 1 Q Q Como supomos que um agente não troca parceiros equivalentes, mesmo que haja ganho estrito para outro agente, o emparelhamento obtido é estável também segundo as listas originais.

Essa observação nos mostra que o caso de indiferença pode ser prontamente reduzido ao caso de preferências estritas.

Contudo, faremos uma execução do algoritmo considerando diretamente as listas com indiferença e a hipótese de não substituição de equivalentes.

Também é importante esclarecer que, nessa situação, quando estudada em trabalhos práticos como em simulações computacionais, a indiferença entre parceiros pode ser removida artificialmente, após a formação das listas de preferência, por uma escolha aleatória pelo agente no momento de criar sua lista ou pelo computador ao identificar o primeiro indivíduo (ou um outro) entre os equivalentes. Dessa forma, durante a execução deste exemplo, utilizaremos a escolha aleatória sempre pelo indivíduo que aparecer primeiro na lista de preferência de um agente indiferente. Contudo, existe a possibilidade de formar outros arranjos pela escolha de outro indivíduo dentre os equivalentes, por exemplo, sempre a última pessoa ou uma sorteada. Portanto, a tomada de decisão dependerá de quais regras serão estabelecidas para orientar o processo artificial de escolha aleatória. Tal como na vida real, quando um indivíduo é obrigado a escolher, mesmo que por itens em indiferença, alguma característica influenciará sua decisão. Para denotar a escolha aleatória de um agente por um dentre os indivíduos equivalentes, ainda utilizaremos a moldura ⎕.

Em resumo, quando um agente faz uma proposta ou seleciona dentre propostas sem ter uma anterior, escolherá aquela que ocupa a melhor posição na lista; quando seleciona dentre propostas equivalentes, inclusive uma anterior, manterá esta oferta mais antiga.

De acordo com as listas de preferência, as propostas da primeira rodada começam com:

 

1ª Rodada – propostas

 

Victor: ≡ C > D > E > B V A

 

Wilson: > D > E > B ≡C W A

 

Xavier: ≡D > B > E ≡A X C

 

Yuri: > D ≡ B > E > C Y A

 

Zé: ≡ C > A ≡B ≡E Z D

 

Como Victor é indiferente quanto à sua primeira escolha ser Ana ou Carolina, uma possível alocação, escolhida de forma artificial e aleatória para o exemplo, é a proposta dele a Ana. Porém, Wilson e Yuri também propõem a Ana, por ser ela sua primeira opção determinada. Semelhantemente, Xavier, que também se encontra em uma situação de indiferença, faz uma proposta a Carolina e Zé faz uma proposta a Débora.

Como o passo seguinte é a análise que cada mulher faz das propostas que recebeu (se recebeu alguma) para, assim, escolher a que acredita ser a mais atrativa ou escolher aleatoriamente entre dois homens que não são um mais preferível que o outro, temos:

 

1ª Rodada – escolhas

 

V,W,Y A Ana: Z > ≡W > Y > X ∴ A:V ∅ B Beatriz: V > X ≡ Y ≡ Z > W

X C Carolina: Z > W ≡ V > > Y ∴ C:X

Z D Débora: V > W ≡ Y ≡ X ≡ ∴ D:Z ∅ E Érica: W > Z > X > Y ≡ V

Ana, ao ter de escolher entre Victor, Wilson e Yuri, sendo indiferente a Victor ou Wilson segundo sua lista de preferências, escolhe Victor segundo nossa convenção e rejeita Wilson (equivalente a Victor, mas listado depois dele) e Yuri (cuja proposta é inferior). As outras mulheres recebem uma ou nenhuma proposta e seguem o procedimento usual.

Na segunda rodada de escolhas, a partir das escolhas da tabela anterior, são feitas novas propostas:

 

2ª Rodada – propostas e escolhas

 

V A ∴ A : V

 

X C ∴ C : X

 

W,Y,Z D ∴ D : Z

 

Neste momento, Débora recebeu as novas propostas de Wilson e Yuri para comparar com a de Zé, que ela já tinha. Contudo, as três opções lhe são equivalentes, de modo que ela prefere continuar com Zé, mesmo Wilson sendo o primeiro listado entre eles. Foi importante, aqui, Zé ter "chegado antes" a Débora.

Dessa forma, obtemos as seguintes tabelas:

Victor: ≡ C > D > E > B Ana: Z > ≡ W > Y > X Wilson: Â > > E > B ≡ Beatriz: V > X ≡ Y ≡ Z > W C

Xavier: ≡ D > B > E ≡ Carolina: Z > W ≡ V > > Y A

Yuri: Â > ≡ B > E > C Débora: V > W ≡ Y ≡ X ≡

Zé: ≡ C > A ≡ B ≡ E Érica: W > Z > X > Y ≡ V

Na continuação do processo, a terceira rodada inicia-se com:

 

3ª Rodada – propostas e escolhas

V A; W E; X C; Y B; Z D.

Com isso, temos:

Victor: ≡ C > D > E > Ana: Z > ≡ W > Y > X B

Wilson: Â > > > B ≡ Beatriz: V > X ≡ ≡ Z > W C

Xavier: ≡ D > B > E ≡ Carolina: Z > W ≡ V > > A Y

Yuri: Â > ≡ > E > C Débora: V > W ≡ Y ≡ X ≡

Zé: ≡ C > A ≡ B ≡ E Érica: > Z > X > Y ≡ V

Isso conclui o processo de emparelhamento.

Logo, todos os homens e mulheres estão agora pareados de maneira estável, isto é, não há nenhuma mulher que preferisse estar com algum homem que também preferisse estar com ela, ao invés de sua parceira. Note que Wilson preferiria estar com Débora, mas, para ela, seu atual parceiro Zé é equivalente a Wilson e, portanto, a substituição não valeria a pena.

Portanto, emparelhamentos estáveis são possíveis inclusive quando ocorrem casos de indiferença, que pressupõem a escolha aleatória entre escolhas equivalentes, visto que, nessa situação, mesmo quando um dos indivíduos é indiferente a uma escolha, ele ainda tem de fazê-la (ainda que seja aleatória e artificialmente). Desse modo, a indiferença, na verdade, é eliminada, tornando a lista com indiferença uma lista sem indiferença (dentre várias possíveis), uma vez que continuam a serem feitas escolhas entre os indivíduos. Modificando essas escolhas quando há equivalência, porém, obtemos resultados diferentes, todos constituindo emparelhamentos estáveis para as listas de equivalência deste exemplo, como veremos no primeiro exercício a seguir.

Porém, podem não existir mais emparelhamentos que sejam ótimos para os homens ou para as mulheres, conforme destacam Roth; Sotomayor (1990, ex. 2.15).

Observação: Para os agentes proponentes, essa convenção de usar o primeiro da lista corresponde à substituição do símbolo "≡" pelo símbolo ">", como observamos no início. Então, se I tem a lista de preferências

I: P > Q ≡ R ≡ S > T,

na verdade, nós trabalhamos com a lista

I: P > Q > R > S > T.

Para os agentes seletores, não temos como fazer essa conversão de antemão, porque precisamos saber quem faz cada proposta. Porém, obtemos tal informação durante a execução do algoritmo. Suponha, então, que P tem a lista de preferências

P: I > J ≡ K ≡ L > M

e que, dentre J, K e J (um grupo de equivalentes entre si), P receba primeiro a proposta de K, rejeitando depois as de J e L se houver. Nesse caso, o comportamento de P é como se K > J, L e obtemos uma lista estrita para P escolhendo uma relação arbitrária entre J e L, assim:

P: I > K > J > L > M.

Essa lista é a utilizada por P na execução do algoritmo, para todos os efeitos.

Ter montado listas estritas para todos os agentes, de modo que a execução do algoritmo corresponda ao preceito de não substituição de equivalentes, mostra que também essa formulação produz emparelhamentos estáveis.

 

Exercícios

1) Mostre que as listas de preferência do exemplo acima podem ser tornadas iguais às listas de preferência estrita que utilizamos como exemplo no primeiro capítulo, com uma ordenação adequada das opções equivalentes. Confira, por outro lado, que o emparelhamento que obtivemos aqui difere daquele resultado.

2) Aplique o algoritmo, a partir das mesmas listas de preferência acima, agora do ponto de vista da proposta feita pelas mulheres, utilizando as regras de proposta à primeira opção e escolha (dentre equivalentes) pela opção anterior, se houver, ou então pela primeira opção. Repetimos as listas a seguir:

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

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

Resposta: O emparelhamento obtido é bem diferente, somente

tendo o casal Victor e Ana em comum: A – V; B – X; C – Z; D –

W e E – Y.

3) A partir das listas de preferência abaixo, aplique novamente o algoritmo com as regras apresentadas em ambas as situações: homens proponentes e mulheres proponentes.