Alguns Problemas Matemáticos Interessantes

Pessoal, algumas novidades do mundo econômico têm aparecido aí no fim de ano, algumas animadoras, outras nem tanto. Todos devem ter acompanhado a ascenção do Brasil para 6ª Economia mundial e visto os destaques da inflação, superávit primário e outros tópicos. Bom, como microeconomista que sou, não vou me concentrar nesses assuntos por hoje. Sobre a questão do 6º lugar, digo que é uma notícia boa e interessante, mas há bem pouco tempo, ainda no "Brasil-novo" pós 2003, estavamos em 11º. Enfim, se colocação de tamanho de PIB fosse indicativo de qualidade de vida para seus concidadãos a China já estava bem a muito tempo. A notícia é interessante para reforçar o tamanho de nossa economia.

Mas me concentro aqui em temas mais microeconômicos e matemáticos e alguns assuntos que aguardam um pouco para entrarem aqui no Blog. Um deles é um comparativo usando densidade relativa para saber qual é o melhor disco dos Beatles. Qual é o seu preferido?! Outro assunto nesse tema, e por vir aqui, é uma aplicação estatística ao problema de detecção de comportamentos diferentes: "o problema do chefe". Outro é um joguinho de Sodoku que fiz para o R, ainda não está pronto, pois meu algoritmo tenta achar um jogo válido entre os zilhões de jogos possíveis! A idéia do meu algoritimo é achar primeiro uma solução e depois cobrir os números de acordo com a facilidade que o jogador desejar. O fácil deve cobrir poucos números, o médio um pouco mais e assim por diante. Li em algum lugar que o Sudoku super profissional conta com apenas 16 números no grid inicial.  Os interessados já podem encontrar o jogo em um pacote "Sudoku" já disponível no R. Pelo menos a janelinha do meu sudoku (a da foto acima) é mais bacana. Quem não tem costume de usar o R e mesmo assim quer jogar um Sudoku e gerar jogos veja aqui nesse site.

Mas o propósito desse post no momento é convidá-los a conhecer o Problema do Casamento Estável (um joguinho muito interessante e didático), também conhecido como problema da dança de salão, desenvolvido pelo professor David Gale (1922-2008), da foto aí do lado, mais particularmente o algoritmo Gale-Shapley proposto em artigo de 1962. O problema consiste em alocar as pessoas de acordo com suas preferências da melhor maneira possível para os proponentes e que não dê empate. Imagine um salão de dança com o mesmo número de homens e mulheres. Esse problema envolve a escolha de um parceiro para a dança de acordo com as preferências. Suponhamos que os homens convidem primeiro as mulheres para dançar, então os homens propõem primeiro à mulher preferida. Mas e se mais de um homem convidar a mesma mulher para dançar? Então a mulher terá opção de escolha de acordo com as suas preferências. O problema pode ser invertido, com as mulheres propondo primeiro. O interessante é que nem sempre as soluções serão idênticas, o grupo que propõe primeiro tem maior chance de estar melhor, no mínimo estará igual a situação em que o outro grupo propõe. Um dos principais nomes nessa área é a profa. Marilda Sotomayor da faculdade de economia da USP que desenvolveu essa área, um dos seus artigos mais importantes é com o prof. Gale. Além disso é co-autora com Alvin Roth, outro nome importante da área, do livro "Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis".

Há poucos dias meu orientador, o prof. Eduardo Rios-Neto, me propôs lidar com esse problema para vermos uma questão de como são alocados os alunos de escolas públicas, uma aplicação importante que procura responder: "Será que podemos melhorar nosso ensino alocando melhor os estudantes?". E me debrucei a tentar o algoritmo na linguagem R, que tenho mais familiaridade. Hoje postei o resultado disso no R-Nabble, comunidade para usuários e desenvolvedores do R-project. Convido a todos que tiverem interesse, e lidam com o R, a me ajudarem e melhorar o algoritmo. É importante testá-lo para novos desenvolvimentos da aplicação de alocação de alunos entre escolas.

Um exemplo interessante de aplicação é a dissertação de Felipe Bardella mestrado da USP. Em que ele estudou a relação de preferências que os alunos candidatos da ANPEC faziam para o exame e os resultados da seleção. Suas conclusões levam que o mercado da ANPEC passou por um tempo de aprendizado e que se trata de um mercado descentralizado com solução próxima a do algoritimo NRMP. Os centros mais bem rankeados tem maior facilidade em fazer valer sua ordenação de preferências sobre os candidatos, os demais centros tem mais dificuldades o que insere maior instabilidade do processo para eles. Uma sugestão da dissertação de Bardella não foi ainda adotada pela ANPEC. Adoção de uma listagem maior do que 6 centros que é atualmente feita.