Exame Anpec

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:

- Cardápio De Leitura Iii
Nada como a morte para trazer de volta a vida. A morte de que estou falando é de ninguém menos do que o matemático John F. Nash que morreu junto com sua esposa Alícia (também matemática) na madrugada deste último sábado (23/05/2015). A vida de...

- Luciano Huck Coloca Um Dilema Dos Prisioneiros Na Tv
Versões televisivas do dilema dos prisioneiros não são incomuns. Silvio Santos em 2002 decidiu implementar um jogo chamado 7 e Meio em que na final dois oponentes, depois de terem derrotado outros adversários, ficavam frente a frente no...

- Seminários Em Economia Na Puc
Esse mês fui convidado pelo colega prof. Cláudio Burian para um ciclo de seminários de graduação no curso de economia da PUC-Minas. Esse ciclo de seminários será composto por tópicos da microeconomia aplicada como Racionalidade Limitada, Economia...

- 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...

- Banco Imobiliário Em Sala De Aula
Caros alunos e amigos leitores deste famigerado blog, ontem joguei Banco Imobiliário em sala de aula com alunos da turma de Microeconomia A1 do curso de Ciências Contábeis da UFMG. Já de algum tempo jogo com meus irmãos uma versão alterada do jogo,...

Exame Anpec