4 - Manipulação e trapaças

Um problema de sistemas de seleção e alocação é, na realização prática, a preocupação dos candidatos em entender o processo a que serão submetidos e atuar de modo a obter o melhor resultado possível.

No modelo de alocação que consideramos, com propostas e escolhas, perceberemos a possibilidade de um candidato rejeitar uma proposta que prefira e escolher uma outra que considere pior, a fim de alcançar um resultado melhor no final do processo. Dessa forma, o agente apresentaria erroneamente suas preferências com o propósito de obter resultados diferentes, realmente preferíveis.

Assim, ao discutirmos a aplicação do algoritmo Gale-Shapley e dos programas desenvolvidos para situações do cotidiano, é necessário examinar a questão da manipulação dos dados, principalmente a partir da apresentação falsa das preferências. O ponto de partida para essa análise é o questionamento: é do interesse de todos os agentes envolvidos indicar suas verdadeiras preferências?

Verifica-se que a resposta é negativa, porque o interesse mútuo de todos os agentes em falar a verdade não ocorre em nenhum procedimento que produza soluções estáveis. (ROTH;

SOTOMAYOR, 1990, p. 87) Como observamos na Seção 1.3, será necessário considerar qualquer possível procedimento, não apenas Gale-Shapley, e demonstrações formais no caso deste, não apenas nossa intuição com a movimentação das "molduras".

4.1 Como ocorre a trapaça

Como um exemplo, adaptado com modificações de Roth; Sotomayor (1990, p. 81), tomamos o seguinte conjunto de preferências:

Victor (V): A > B > C > Ana (A): W > X > V > Y > Z D

Wilson (W): D > B > A > Beatriz (B): X > V > W > Y > C Z Xavier (X): D > C > B > Carolina (C): Z > Y > V > W A > X Yuri (Y): A > D > C > B Débora (D): V > W > Y > Z >

X

Zé (Z): A > B > D > C

A partir dessas preferências, obtemos as seguintes alocações quando os homens propõem: V – A, W – D, X – B, Y solteiro, Z – C.

Entretanto, se Ana muda sua lista de preferências, de modo a apresentar uma ordenação falsa em que diz preferir Yuri e Zé a Victor, isto é:

Ana (A): W > X > Y > Z > V,

obtemos outra formação de casais: V – D, W – A, X – B, Y solteiro, Z – C.

com preferências com preferências verdadeiras falsas

A: W > X > > Y > Z A: > X > Y > Z > V

B: > V > W > Y > Z B: > V > W > Y > Z

C: > Y > V > W > X C: > Y > V > W > X

D: V > > Y > Z > X D: > W > Y > Z > X

Assim, ao apresentar erroneamente suas preferências, Ana melhora sua situação, pois se aloca ao homem que prefere verdadeiramente, enquanto que, antes, estava alocada ao seu terceiro homem mais preferível.

Além disso, Débora também é beneficiada indiretamente pela trapaça de Ana, dado que foi promovida de seu segundo homem mais preferível para o primeiro.

Logo, para Ana, é um comportamento estratégico apresentar falsas preferências a fim de manter-se junto a um homem menos preferível dentre as propostas que recebe, para que, em alguma etapa posterior do processo, receba a proposta de um homem mais preferível que, se não fosse pela trapaça, não chegaria a lhe propor.

Exercício

1) Aplique o algoritmo Gale-Shapley aos dois conjuntos de preferên cias e confira o exemplo.

Porém, para que a manipulação ocorra e seja bem-sucedida, Ana teria que saber as preferências das demais pessoas a fim de realizar simulações do processo e descobrir como suas preferências falsas poderiam impor novas escolhas. As propostas inéditas a ela por seus candidatos mais preferíveis ocorrem quando as mulheres a quem eles propuseram, antes, rejeitaram-nos em favor de novas opções de parceiros e estes, por sua vez, fazem tais propostas devido às rejeições de Ana.

Assim, para trapacear e ser favorecida, ou Ana tem de ter acesso às listas de preferências das demais pessoas ou as propostas têm de ser rodadas mais de uma vez, de forma que, a partir da observação das propostas e escolhas, Ana tenha, pelo menos, um esboço das preferências.

Definição: Estratégia é uma decisão sobre o conjunto de ações a realizar, como uma postura ou raciocínio para apresentação de informações e decisões, qualquer que seja. Cada manipulação das preferências, condicionada ou não às preferências alheias, é uma estratégia, mas ser honesto quanto a suas preferências também é uma estratégia. Definição: A estratégia dominante de um agente é a estratégia que melhor responde às possíveis estratégias que possam ser adotadas pelos demais agentes. As razões para tal estratégia, que deverá ser seguida pelo agente, acabam por esclarecer que não há nenhum incentivo a ele para que atue de forma diferente.

Assim, em uma situação-problema em geral, é importante determinar qual é a estratégia dominante de cada agente.

Viabilidade da manipulação

Para verificarmos quando a trapaça é possível, destacamos alguns resultados e informações de Roth; Sotomayor (1990, p. 87-90), referentes a um "mercado", ou conjunto de agentes, no qual as preferências são estritas e existe mais de uma alocação estável.

Ao analisar a escolha de cada agente por sua estratégia dominante, Roth constatou que não existe nenhum mecanismo de alocação estável em que indicar as preferências verdadeiras seja a estratégia dominante para todos os agentes. Essa observação ficou então conhecida como o Teorema da Impossibilidade de Roth. Depois, por consequência, concluiu-se que não existe nenhum mecanismo de alocação estável em que indicar as preferências verdadeiras seja a melhor estratégia para todos os agentes quando todos os outros agentes indicam suas verdadeiras preferências, ou seja, pelo menos um agente pode se beneficiar ao apresentar erroneamente suas preferências, assumindo que os outros contaram a verdade.

Adaptamos, aqui, o exemplo da demonstração dada por Roth e Sotomayor:

Xavier (X): A > B Ana (A): Y > X Yuri (Y): B > A Beatriz (B): X > Y

Só há dois emparelhamentos possíveis e ambos são estáveis: (1º) X – A, Y – B, ótimo para os homens, e (2º) X – B, Y – A, ótimo para as mulheres. Se Ana mudar sua lista para Y > ■, então somente o segundo pode ser obtido, qualquer que seja o mecanismo, garantindo sua melhor escolha. Analogamente, qualquer agente (Xavier, Yuri ou Beatriz) pode impôr que somente um emparelhamento seja possível e, então, obtido pelo mecanismo, contanto que os demais três mantenham suas listas originais.

Exercício

1) Verifique a estabilidade dos dois emparelhamentos e o sucesso das estratégias dos quatro agentes.

Gale e Sotomayor mostraram como, em uma dada situação, ao menos um agente pode trapacear: se há ao menos dois emparelhamentos estáveis, o mecanismo produz – um que é distinto ou do ótimo dos homens ou do ótimo das mulheres; um desses agentes, portanto, não atinge seu ótimo possível e beneficia-se ao remover de sua lista todos os indivíduos que considera piores que esse ótimo.

Entretanto, note que os agentes que apresentam preferências falsas são aqueles que recebem as propostas, enquanto que os agentes que propõem têm como melhor estratégia, ou estratégia dominante, indicar suas verdadeiras preferências, dado que o resultado é sempre o melhor possível para eles.

Por exemplo, considerando as seguintes listas de preferência para o uso de Gale-Shapley:

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

Com o desenrolar do processo, terminamos, na última rodada, com:

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

Como vimos no Capítulo 1, percebe-se, pelo próprio movimento das molduras, que o homem sempre propõe primeiro à melhor opção possível disponível e, se modificar sua lista de preferências, será, então, pareado à primeira mulher preferível que o aceitar, da mesma forma que ocorre quando se falar a verdade.

Exercício

1) Aplique o algoritmo de Gale-Shapley e confira esse exemplo.

Se, nesta situação, tanto Xavier como Zé, os homens que não estiveram com sua primeira opção, inverterem suas listas de qualquer forma, vão continuar com Carolina e Beatriz como suas melhores opções possíveis, respectivamente, dado que a primeira opção de Xavier está bloqueada pelo par Ana e Yuri, que se preferem mutuamente, e, por conseguinte, a primeira opção de Zé está bloqueada pelo par Xavier e Carolina. Zé e Beatriz, mesmo cada um não sendo a primeira opção do outro, preferem-se mutuamente, pois seus parceiros "ideais" (Ana e Yuri, respectivamente) já formam um par de bloqueio, que não pode ser desfeito para que o resultado continue a ser estável. Logo, não há incentivos para eles falsearem sua lista de preferência para serem alocados a uma outra parceira.

Isso em razão de que, sendo os homens que propõem, a situação de cada um apenas pode "piorar" em termos de sua lista de preferência. Quando o processo termina, o homem conseguiu sua parceira mais preferível possível sem manipular o mecanismo, porque, se escolher alguém menos preferível numa rodada, não haverá como, posteriormente, escolher uma parceira mais preferível.

Logo, a manipulação de um homem em sua lista de preferência, quando são eles que propõem, não pode ser bem-sucedida, porque o resultado será para ele tão bom quanto o resultado original de suas preferências verdadeiras.

Por isso, Dubins e Freedman, assim como Roth, concluíram que o mecanismo que resulta na melhor alocação estável para os homens (nos termos de preferências indicadas) faz com que a estratégia dominante para cada homem seja indicar suas verdadeiras preferências. Ademais, é importante ressaltar que, quando são as mulheres que propõem, por simetria, ser verdadeira também é a estratégia dominante de todas elas. Portanto, de forma geral, para o grupo que faz as propostas, a melhor estratégia é sempre ser verdadeiro.