1 - O algoritmo de Gale-Shapley

Em vários problemas cotidianos, os preços não podem ser um mecanismo de alocação de recursos. Por exemplo, a atribuição de órgãos humanos a pacientes para transplante, por motivos éticos, não pode ser regulada por pagamentos financeiros, dando prioridade a quem possa pagar mais.

Nós estudaremos a questão de estabilidade nas resoluções desses problemas. Exemplo de sua aplicação é a promoção, de forma abstrata, de pares perfeitos (envolvendo, assim, dois conjuntos de agentes), como de uniões entre homens e mulheres, estudada a partir do questionamento: "Como deve ser combinada uma mesma quantidade de homens e mulheres da melhor forma possível, respeitando suas preferências individuais?".

A solução encontrada por David Gale e Lloyd Shapley (1962) foi a utilização de regras pré-estabelecidas segundo um algoritmo, ou procedimento formado por passos ou etapas. Esse algoritmo baseia-se no "princípio da aceitação postergada" (em inglês deferred acceptance), isto é, as propostas de casamento somente serão definitivamente aceitas ao final do processo.

1.1 Conceitos de estabilidade e

bloqueio

Vamos considerar a situação em que, havendo dois conjuntos

de indivíduos ou agentes, estes devam ser combinados uns com os outros da melhor forma possível, formando uma bijeção (correspondência um a um) entre os dois conjuntos, chamada emparelhamento.

Definição: O emparelhamento é instável se houver um agente A pareado a um agente X, mas que preferiria estar com um agente Y, que também o preferiria. Nessa situação, há um

"ganho inexplorado", uma vez que, se A se unisse a Y, ambos estariam em uma melhor situação segundo suas preferências. Definição: O emparelhamento é estável se não for instável.

No seguinte exemplo, temos 3 homens e 3 mulheres: Xavier (X); Yuri (Y); Zé (Z); Ana (A); Beatriz (B) e Carolina (C). Cada indivíduo tem uma lista de preferências, em que ordena os indivíduos do grupo oposto (com a utilização do símbolo ">"):

Xavier: B > C > A Ana: X > Z > Y Yuri: A > C > B Beatriz: X > Y > Z Zé: B > C > A Carolina: Y > X > Z

Isso significa que Xavier prefere Beatriz, depois Carolina, e, por último, Ana.

A partir desses elementos, quais combinações entre homens e mulheres seriam possíveis? Quais desses emparelhamentos seriam adequados segundo a descrição acima de estabilidade?

Contamos três opções de esposa para o primeiro homem, sobrando duas para o segundo, e, depois, uma para o terceiro, de modo que, multiplicando esses números, há seis emparelhamentos possíveis:

(1) X – A; Y – B; Z – C

(2) X – A; Y – C; Z – B

(3) X – B; Y – A; Z – C

(4) X – B; Y – C; Z – A

(5) X – C; Y – A; Z – B

(6) X – C; Y – B; Z – A

Dentre essas seis possibilidades, podemos verificar pareamentos instáveis e estáveis, de acordo com a ideia de ganhos perdidos ou não.

As alocações que reúnem dois agentes que se preferem mutuamente são a 3 e a 4; isso porque as demais alocações não combinam Xavier e Beatriz, agentes que precisam, necessariamente, estar juntos porque se preferem mutuamente. Logo, o par (Xavier, Beatriz) bloqueia a formação de qualquer combinação de casais que não o una.