Apresentação

Como podemos casar homens e mulheres de modo que não surjam amantes?

A correspondência um a um entre homens e mulheres é chamada emparelhamento e, além disso, é estável quando não existirem homem e mulher que se prefiram simultaneamente aos respectivos cônjuges.

David Gale e Lloyd Shapley reconheceram essa condição em 1962 e, ao mesmo tempo, perceberam que um emparelhamento estável pode ser obtido por um procedimento passo a passo: uma versão organizada de propostas de casamento feitas pelos homens e comparadas pelas mulheres. Gale e Shapley ainda colocaram outro problema na mesma perspectiva de alocação por preferências: o da admissão em universidades.

Duas décadas depois, Alvin Roth reconheceu que o procedimento descrito já era aproximadamente utilizado na seleção de médicos residentes pelos hospitais dos Estados Unidos, investigou as condições de funcionamento do procedimento e desenvolveu diversas variantes com fins específicos. O corpo de conhecimento resultante, a "teoria do emparelhamento", também teve forte colaboração da brasileira Marilda Sotomayor e, devido à sua ampla aplicabilidade e sucesso na alocação de recursos, foi uma das inovações comemoradas em 2012 com a concessão do Nobel em economia a Shapley e Roth.

Pretendemos, neste livro, trazer o assunto ao público escolar, com uma apresentação lusófona dos primeiros conceitos e técnicas envolvidos, para que o próprio estudante possa aplicá-los em situações similares que encontre e adquira entusiasmo por alguns tópicos de ciências econômicas, ciência da computação e matemática.

Esta exposição é voltada aos jovens no ensino médio ou ingressantes no ensino superior, como uma opção de assunto para estudo paralelo ao currículo obrigatório, seja orientado ou individual. Procuramos, portanto, adotar um discurso informal e detalhado que explica também algumas técnicas simples de raciocínio matemático, como: a introdução de objetos adicionais para equiparar quantidades diferentes de elementos; a resolução de questões de indiferença com uma extensão artificial da ordem; a metodologia de elementos notacionais auxiliares; o uso de variáveis booleanas na escrita de equações. Incluímos, enfim, um ou outro exercício de prática ou reflexão, mas sem pretender a compleição de um livro didático.

Tivemos a preocupação de não apenas apresentar as "receitas" para atingir cada objetivo proposto – especialmente os algoritmos Gale-Shapley e Simplex (reduzido) –, mas, também, comentar por que funcionam e por que terminam (ou seja, obtêm seu objetivo após um número finito de passos), mesmo que de modo informal. Incluímos, também, uma apresentação pormenorizada de como montar problemas de otimização linear para resolução no programa Excel, de modo que o estudante poderá adaptá-la a qualquer situação.

Mantemos a nomenclatura tradicional de exposição, que fala em "casar grupos de homens e mulheres, com os homens fazendo propostas de casamento e as mulheres avaliando suas melhores opções". Apesar de extremamente machista, esse vocabulário é imediatamente claro para o leitor iniciante e tem, mesmo, a vantagem de usar seu aspecto machista para elucidar pontos importantes da teoria. Contudo, em momento algum fazemos apologia do machismo ou da cultura patriarcalista!

Começamos com a descrição dos conceitos relevantes e do algoritmo de Gale-Shapley, para grupos de homens e mulheres com o mesmo número de indivíduos. Depois, tratamos de três expansões: listas de preferência com possíveis indiferenças; números diferentes de homens e mulheres; poligamia. Consideramos, então, outra teoria, a programação linear, ilustrando um processo manual de resolução e o uso do Excel, para, então, verificar como o problema do casamento pode ser formulado para esse tipo de otimização. Um capítulo relata brevemente a possibilidade de qualquer procedimento de emparelhamento ser trapaceado através da prestação de falsas preferências e quais pontos de apoio existem para inibir esse mau comportamento. Outro capítulo trabalha sobre o problema de admissão em universidades, com mais detalhes do que a redução poligâmica oferece, e relata o caso concreto da residência médica americana.

Apresentamos, também, o problema dos colegas de quarto, que requer o emparelhamento de indivíduos pertencentes a um único grupo e que ordenam segundo suas preferências, portanto, todos os demais participantes. A solução utiliza o algoritmo Gale-Shapley em uma primeira etapa, mas requer passos adicionais e uma alocação estável não é mais sempre possível.

Finalmente, descrevemos, como um objeto de pesquisa, o sistema de matrícula em disciplinas na Universidade Federal do ABC, que é um problema de alocação por excelência e bastante complicado em vista da liberdade curricular característica da instituição e da necessária limitação de oferta de disciplinas e horários. Também em um formato adequado ao nosso público, propomos uma solução baseada nessas técnicas históricas.

Incluímos uma bibliografia comentada, permitindo-nos utilizar mais esse espaço para a apresentação de informações adicionais. Queremos incentivar, portanto, o leitor a estudar, ainda essas últimas páginas.

Este trabalho é produto da iniciação científica da primeira autora, sob orientação do segundo autor na UFABC, de agosto de 2014 a julho de 2015. Ambos os autores contribuíram igualmente para a redação de todos os capítulos.

Agradecemos a Rodrigo Lima e Clarissa Felippe por discutirem versões anteriores do projeto de pesquisa e a Renata Coelho por nos apresentar o sistema de matrículas em disciplinas da Graduação na UFABC. Agradecemos, também, ao CNPq, pelo apoio em forma de bolsa de iniciação científica para a primeira autora.

São Bernardo do Campo

Abril de 2016