Mostrando postagens com marcador matemática. Mostrar todas as postagens
Mostrando postagens com marcador matemática. Mostrar todas as postagens

quarta-feira, 10 de abril de 2013

Algoritmos de casamentos estáveis (sobre o Nobel de economia de 2012)

Caros leitores,

Segue uma matéria interessante do site da FEA/USP sobre a área em que estou trabalhando na minha tese de doutorado. Com previsão pra acabar AGORA!! :-) (espero em breve por convite para defesa).

Eis aqui o link e o texto:

http://www.fea.usp.br/noticias.php?i=1012


Palestra explica teoria do matching


Graduada em matemática em 1967, com décadas de experiência e seis pós-doutorados na bagagem, a professora Marilda Sotomayor foi a responsável pela apresentação "Matching vai à Estocolmo". Organizada pelo departamento de Economia e pelo CAVC, a palestra tinha como objetivo explicar o uso da teoria do matching e seu papel no trabalho de Alvin Roth e Lloyd Shapley, laureados com o prêmio Nobel em 2012.

O evento, que lotou a Sala da Congregação no dia 13 de novembro, se iniciou com uma breve explicação a respeito da teoria dos jogos, da qual o matching é um dos ramos. "Um jogo é um modelo matemático, uma representação abstrata de situações da vida real em que dois ou mais tomadores de decisão, que chamamos de jogadores, interagem de acordo com regras pré-estabelecidas e suas decisões afetam um ao outro.", explicou a professora, "A teoria dos jogos é um ramo da matemática que estuda o comportamento desses tomadores de decisão", completou. Podem ser feitas ainda duas distinções: a dos jogos cooperativos (em que os jogadores podem cooperar e formar as chamadas "coalizões") e não cooperativos (cada jogador joga apenas por si próprio).

"Informalmente, um matching é um pareamento entre os jogadores que não viola as regras do mercado. No mercado de casamentos, por exemplo, um matching é um conjunto de casamentos monogâmicos", disse a professora.

O marco inicial da pesquisa no ramo data de 1962, quando foi publicado, em uma parceria entre o próprio Shapley e o matemático David Gale, falecido em 2008, o artigo "College admissions and the stability of marriage". O artigo formula e resolve o problema da admissão de estudantes às universidades através de uma distribuição estável e satisfatória. A dupla desenvolveu um algoritmo que solucionava esse problema. Em 1975 foi descoberto por Gale que este algoritmo já estava sendo usado desde 1951 nos Estados Unidos para distribuir os médicos pelos hospitais, onde eles tinham de fazer um ano de residência. Este fato foi provado e divulgado oficialmente em 1983 num trabalho de David Gale e Marilda Sotomayor.

As evidências apontam que o trabalho mais relevante da teoria de matching foi, sem dúvida, o livro "Two-sided matching. A study in game-theoretic and analysis", de autoria de Roth e Sotomayor e publicado em 1990. Este livro compila toda a teoria existente até a sua publicação e um de seus maiores feitos foi atrair a atenção dos economistas para a área de matching. "Até então, matching era considerado coisa de matemático e para matemáticos", informa a professora. Segundo o Mathematical Reviews, dentre todas as publicações de Roth, o livro é, de longe, a que mais citações tem. A segunda publicação mais citada de Roth tem um terço das citações do livro. Os autores foram laureados com o Lanchester Prize de 1990 e foram homenageados em 2010 com o congresso "Roth and Sotomayor: Twenty years after", para celebrar os vinte anos da publicação do livro.

Alguns anos após a publicação do livro, enquanto Marilda Sotomayor continuava a liderar a teoria, Alvin Roth passou a liderar as aplicações de matching à Economia: Desenho de Mercados e transplante de órgãos. "Atuou na organização dos mercados de escolha de escolas públicas de primeiro grau em Boston e em Nova York. Modelou o mercado de transplante de rins como um mercado de matching e então, usando um algoritmo devido a Gale, conhecido na literatura como "top-trading cycles" propôs uma reformulação no sistema de alocação de rins para pacientes", disse a professora.

"O prêmio Nobel outorgado a Roth e Shapley representa uma vitória de todos os autores que contribuíram com seus trabalhos para o desenvolvimento dessa teoria", concluiu Marilda.


Para quem quiser aprender sobre o tema, eu escrevi umas modestas palavras em dezembro de 2011 sobre um dos matemáticos envolvidos na confecção do algoritmo inicial.

Outo lugar de consulta pode ser essa video-aula que descobri recentemente sobre o assunto, está bem didática:




quinta-feira, 16 de fevereiro de 2012

The Frederick Mosteller's Subway Problem

Caros, pequeno post para informar que atualizei o algoritmo de Gale-Shapley que foi mencionado no post "problemas matemáticos interessantes", agora está funcionando perfeitamente para men proposing and women proposing (antes funcionava só até matrizes 6x6), testei até uma matriz 100x100. Está lá no R-Nabble. Também para não perder a oportunidade, segue um outro problema de metrô (uma vez considerei um problema de outra natureza aqui no blog) do livro "Fifty Challenging Problems in Probability" do Frederick Mosteller:

"Marvin sai do serviço em horários aleatórios entre 3 e 5 da tarde. Sua mãe mora no subúrbio e sua namorada no centro. Ele pega o primeiro metrô que aparece em qualquer direção e janta na companhia da pessoa que está na primeira direção do metrô que lhe aparece. Sua mãe reclama que ele nunca vai jantar com ela, mas ele diz que ela tem chance de 50-50. Ele jantou com sua mãe apenas duas vezes durante os últimos 20 dias de trabalho. Explique."

Quem estiver disposto a considerá-lo pensem aí, em breve posto a resposta. Como não podia deixar de ser esse problema lembra Titãs.

quarta-feira, 28 de dezembro de 2011

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.