Bibliografia comentada

Na literatura acadêmica e científica, existe um padrão rigoroso de citação dos trabalhos consultados para a elaboração de um texto ou que o fundamentam, não bastando sua listagem em uma bibliografia, mas também ao longo do texto e junto às informações utilizadas.

Nossa exposição evitou um excesso dessas referências formais para preservar o fluxo de leitura de nosso público, com o entendimento de que as técnicas utilizadas são parte da tradição matemática. Contudo, cumpre-nos identificar e apresentar nossas diversas fontes:

BROWN, J.; SHERBERT, D. Introductory linear algebra with applications. PWS, 1984.

Apresenta a álgebra linear, um campo da matemática universitária extremamente útil para outras teorias e para as ciências e engenharias. Os problemas de otimização linear e o método Simplex são exemplificados com boa abrangência.

GALE, D.; SHAPLEY, L. College admissions and the stability of marriage. The American Mathematical Monthly, v. 69, n. 1, p. 9-15, 1962.

É o artigo que originou toda a teoria que apresentamos. Além do próprio algoritmo, ele já contém diversas informações importantes, como: os conceitos de estabilidade e otimalidade aplicados a emparelhamentos (p. 10); a generalização para números distintos de homens e mulheres (p. 13); o exemplo insolúvel de colegas de quarto (p. 12); o tratamento de universidades com múltiplas vagas usando turmas provisórias (p. 13); e o princípio de que a otimalidade deve ser almejada para o grupo de estudantes, porque "as universidades existem para os estudantes, não o contrário" (p. 10). Convém citar a homenagem de Roth; Sotomayor (1990, p. 170), feita em vista do fato notável de que uma metodologia parecida já fora desenvolvida pelo NIMP vários anos antes: também Colombo não foi o primeiro a descobrir as Américas, mas seu mérito maior é de ter sido o último; assim, depois dele, a descoberta não precisou ser refeita mais uma vez, ao contrário, possibilitou outras realizações.

GUBITOSO, A.; LOPES, V. Proposta para alocação dos discentes nas turmas de graduação da UFABC: versão 1. Technical report – CMCC – UFABC. Santo André: CMCC-UFABC, 2015. Disponível em:

<http://cmcc.ufabc.edu.br/images/Pesquisa/TechnicalReports/TR001

.pdf>. Data de depósito: 21/10/2015.

Um "relatório técnico" é uma apresentação prévia de uma técnica ou resultado – neste caso, de nossa proposta para o problema das matrículas na UFABC, como discutimos no último capítulo – antes de sua formulação definitiva ou finalizada.

GUSFIELD, D.; IRVING, R. The stable marriage problem: structure and algorithms. The MIT Press, 1989.

É mais voltado a questões de ciência da computação, como: (a) a especificação de algoritmos para resolver diversos problemas e a determinação de sua eficiência, isto é, quantos passos os procedimentos realizam até chegar a uma solução, em função do tamanho do problema (como, por exemplo, número de agentes envolvidos), e (b) à estrutura subjacente aos problemas de emparelhamento e seu uso nesses algoritmos.

Por estrutura, entendem-se conceitos como o de rotação (que

introduzimos em nosso Capítulo 6) ou padrões reconhecidos entre emparelhamentos ou dentro de um emparelhamento, que permitem uma melhor descrição do problema, dos métodos e das soluções.

Por exemplo, considerando somente os problemas de casamento

mais simples de nosso Capítulo 1, pode não ser possível comparar duas soluções para um mesmo conjunto de listas de preferência, se um homem melhora enquanto outro piora de situação, mas ambas compartilham um emparelhamento melhor (cada homem recebe a esposa que julga melhor dentre as das duas soluções) e outro pior (cada homem recebe a pior esposa dentre as duas), formando um diagrama de emparelhamentos estáveis chamado reticulado. Esse reticulado pode ser usado para vários problemas de determinação e contagem de soluções com propriedades específicas.

KNUTH, D. Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms. American Mathematical Society, 1997.

O autor serviu-se do problema de emparelhamento e do algoritmo Gale-Shapley como excelente motivação para ministrar uma série de aulas sobre a ciência da computação, seus assuntos, métodos e questões em aberto. É boa leitura para o estudante que deseja seguir carreira na área, bastando-lhe os conhecimentos universitários iniciais.

Logo em sua pág. 5, Knuth acaba por oferecer um pequeno exemplo de uma regra inestimável: é preciso cuidado com definições semelhantes, mas não equivalentes, utilizadas para um mesmo termo por autores variados e com objetivos específicos. De fato, Knuth afirma que emparelhamentos estáveis nem sempre existem quando as listas de preferência são incompletas, dando este conjunto (com outros rótulos) como exemplo:

A: X X: C > A > B B: Z > X > Y Y: B > A > C C: Z > X Z: A > B > C

Por um lado, seguindo nossas convenções para listas incompletas e o algoritmo de Gale-Shapley, obtemos o emparelhamento B – Z, C – X, restando A, Y solteiros, que é estável. Por outro, Knuth requer uma bijeção total entre os conjuntos {A, B, C} e {X, Y, Z} e nota só haver um único tal emparelhamento, consistindo de A – X, B – Y e C – Z, que não é estável porque é bloqueado pelo par (B,Z).

LINS, M.; CALÔBA, G. Programação linear: com aplicações em teoria dos jogos e avaliação de desempenho (data envelopment analysis). Interciência, 2006.

É uma referência lusófona e detalhada para a programação linear e o método Simplex.

ROTH, A. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, v. 92, n. 6, p. 991-1016, 1984.

______. The college admissions problem is not equivalent to the marriage problem. Journal of Economic Theory, v. 36, p. 277-288, 1985.

ROTH, A.; PERANSON, E. The redesign of the matching market for american physicians: some engineering aspects of economic design. The American Economic Review, v. 89, n. 4, p. 748-780, 1999.

ROTH, A.; SOTOMAYOR, M. The college admissions problem revisited. Econometrica, v. 57, n. 3, p. 559-570, 1989.

Esses quatro artigos, assim como Gale; Shapley (1962), são publicações acadêmicas, isto é, textos de apresentação formal de pesquisa científica enviados a periódicos especializados que os submeteram a uma revisão por outro especialista, isto é, os trabalhos foram conferidos quanto a seu rigor e veracidade.

______. Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, 1990.

Este livro organiza e aglutina os resultados anteriores dos autores, assim como de Gale e Shapley e outros colegas, publicados em diversos artigos científicos, a fim de prover uma exposição unificada. Tornou-se, portanto, uma referência para conhecimento e estudo na área de alocações. Além dos problemas de casamento e de admissão em universidades, o livro incorpora estudos sobre o conceito de "núcleo", mercados com precificação e leilões, alocações de firmas e trabalhadores e de compradores e vendedores.

ROYAL SWEDISH ACADEMY OF SCIENCES. The prize in economic sciences 2012: information for the public: stable matching: theory, evidence, and practical design. 2012a. Disponível em:

<http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/

popular-economicsciences2012.pdf>. Acesso em: 08/04/2014.

Certamente, todo ano, quando anunciados os agraciados com os prêmios Nobel, há grande interesse do público mundial em saber de suas carreiras e contribuições. A Academia Sueca, responsável pela outorga dos prêmios, prepara essa divulgação para satisfazer nossa curiosidade.

A apresentação explica também que o prêmio de 2012 a Shapley e Roth reconhece todo o trabalho de suas carreiras, não apenas a pesquisa a respeito de emparelhamentos. Por exemplo, Shapley e colegas também desenvolveram um algoritmo para permitir trocas entre agentes de unidades indivisíveis de um recurso, com um procedimento distinto do de Gale-Shapley, mas com a mesma noção de estabilidade. Esse procedimento depois foi visto como adequado para transplantes de rins, em que a "preferência" de um paciente por um rim é expressa por sua compatibilidade.

ROYAL SWEDISH ACADEMY OF SCIENCES. Scientific background on the Sveriges Riksbank Prize in economic sciences in memory of Alfred Nobel 2012: stable allocations and the practice of market design: compiled by the economic sciences prize committee of the Royal Swedish Academy of Sciences. 2012b. Disponível em:

<http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/

advanced-economicsciences2012.pdf>. Acesso em: 08/04/2014.

A Academia Sueca também prepara uma apresentação científica da outorga, como um retrato das contribuições feitas e seus desdobramentos. Assim como indicamos Knuth (1997) para o estudante que ingressa na ciência da computação, este survey é leitura importante para aquele que se inicia nas ciências econômicas enquanto alude a diversos temas importantes. Contém resultados recentes e uma bibliografia técnica representativa.