2.4 Recapitulação

Por exemplo, suponha que X tenha três vagas, todas preenchidas pelos associados B > A > C. Suponha, também, que X é um agente seletor, que recebe propostas. Ele somente aceitará uma proposta de D caso D > C; depois da substituição, a listagem temporária será ordenada novamente segundo as preferências de X, podendo ser B > D > A, por exemplo, e deixando A em situação de potencial substituição. Por outro lado, na situação de ser X quem faz propostas, ele somente proporá a algum agente quando A, B ou C abandonarem-no em prol de outra oferta mais interessante e, em caso de aceitação, preencherá a vaga aberta.

No caso de um número arbitrário de vagas abrindo-se, portanto, tomamos em conjunto os "associados" e as novas propostas, selecionamos os candidatos mais preferidos, dentre todos, e rejeitamos os demais que excederem o número de vagas disponíveis.

Novamente, o processo termina quando cada agente proponente estiver alocado ou houver sido rejeitado por cada agente seletor.

O resultado final será o mesmo que obtivemos com o procedimento exemplificado. Trataremos assim um pequeno

exemplo na Seção 5.1.

2.4 Recapitulação

Buscamos explicar e exemplificar o algoritmo Gale-Shapley para obter emparelhamentos estáveis de casais e indicar sua adaptabilidade mesmo a situações com falta de preferência, números desiguais de indivíduos a serem pareados, listas incompletas e uniões de um único agente com vários outros.

Isso foi possível contando com algumas estratégias comuns em raciocínio lógico, como a utilização de curingas e repetição de listas, permitindo aplicar novamente o mesmo procedimento, realizando a redução desses problemas mais complexos à primeira versão mais simples que estudamos.

Importante: Reflita e constate que essa solução também pode ser aplicada em situações ainda mais complexas, em que ocorram todos os problemas supracitados simultaneamente.

Adotamos a figura do casamento para explicar os exemplos tradicionais, mas, nos próximos capítulos, veremos que o algoritmo é considerado tanto na academia como no mundo real cotidiano, nas questões de admissão de alunos nas universidades e escolas e de emparelhamento de colegas de quarto.