Em 2012, o Prêmio Nobel de Economia foi concedido a Lloyd Shapley e Alvin Roth. "Para a teoria da distribuição estável e prática de mercado." Alexey Savvateev, em 2012, tentou explicar de maneira simples e clara qual é a essência dos méritos dos matemáticos. Trago à sua atenção as notas da palestra em vídeo .Hoje será uma aula teórica. Sobre os experimentos de
Al Roth , em particular com doações, não falarei.
Quando foi anunciado que
Lloyd Shapley (1923-2016) recebeu o Prêmio Nobel, havia uma pergunta padrão: “Como! Ele ainda está vivo!?!? ” Seu resultado mais famoso foi obtido em 1953.
Formalmente, o prêmio foi concedido a outro. Pelo trabalho de 1962 para o "teorema do casamento sustentável": "Admissão na faculdade e estabilidade do casamento".
Sobre o casamento sustentável
Correspondência é a tarefa de encontrar uma correspondência.
Há uma certa vila isolada. Existem "m" jovens e "w" meninas. É necessário casar-se um com o outro. (Não necessariamente a mesma quantidade, talvez no final alguém seja deixado em paz.)
Quais pré-requisitos você precisa fazer no modelo? O que não é apenas aleatório. Está sendo dado um passo em direção à livre escolha. Suponha que exista um sábio aksakal que queira se casar para que, após sua morte, o divórcio não comece. (O divórcio é uma situação em que o marido deseja que uma mulher de terceiros se case mais do que uma esposa.)
Este teorema está no espírito da economia moderna. Ela é extremamente desumana. A economia é tradicionalmente desumana. Em economia, uma pessoa é substituída por um carro para maximizar os lucros. O que vou contar são coisas completamente loucas em termos de moralidade. Não leve a sério.
Os economistas olham para o casamento assim.
m
1 , m
2 , ... m
k são homens.
w
1 , w
2 , ... w
L - mulheres.
Um homem é identificado como ele "ordena" as meninas. Há também um "nível zero", abaixo do qual as mulheres não devem ser oferecidas para se casar, mesmo que não existam outras.
Tudo acontece nas duas direções, as meninas têm a mesma coisa.
Os dados iniciais são arbitrários. A única sugestão / limitação é que não alteramos nossas preferências.
Teorema: Independentemente da distribuição e do nível zero, sempre há uma maneira de estabelecer uma correspondência individual entre uma parte dos homens e uma parte das mulheres, para que seja estável em relação a qualquer tipo de divisão (não apenas divórcios).
Que ameaças podem ser?
Há um casal (m, w) que não é casado. Mas para w, o marido atual é pior que m, e para m, a esposa atual é pior que w. Esta é uma situação instável.
Existe outra opção, que alguém se case com alguém "abaixo de zero"; nessa situação, o casamento também terminará.
Se uma mulher é casada, mas ela prefere uma mulher solteira, com quem está acima de zero.
Se duas pessoas, ambas solteiras, e ambas estão "acima de zero" uma para a outra.
Argumenta-se que, para qualquer dado inicial, existe um sistema de casamento resistente a todos os tipos de ameaças. Em segundo lugar, o algoritmo para encontrar esse equilíbrio é muito simples. Proporcional a M * N.
Este modelo foi generalizado e ampliado para "poligamia" e aplicado em muitas áreas.
Procedimento Gale-Shapley
Se todos os homens e mulheres cumprirem os “preceitos”, o sistema de casamento resultante será estável.
Prescrições.Demoramos alguns dias, conforme necessário. Todos os dias dividimos em duas partes (manhã e noite).
Na primeira manhã, todo homem vai até a sua melhor mulher e bate na janela, convidando-a a casar com ele.
Na noite do mesmo dia, a mudança vai para as mulheres.O que uma mulher pode descobrir? Que debaixo da janela ela tem uma multidão, um ou não um homem. Aqueles que hoje não tinham ninguém perdem o curso, esperem. O resto, que tem pelo menos um, verifica os homens que chegaram "acima de zero". Ter pelo menos um. Se você for completamente azarado e tudo estiver abaixo de zero, todos deverão ser enviados. A mulher escolhe o máximo de quem vem, manda que ele espere e manda o resto.
Antes do segundo dia, a situação é a seguinte: algumas mulheres têm um homem, outras não.
No segundo dia, todos os homens "livres" (enviados) precisam ir à mulher de segunda prioridade. Se não houver, o homem será declarado solteiro. Aqueles homens que já estão sentados com mulheres ainda não estão fazendo nada.
À noite, as mulheres olham para a situação. Se quem já estava sentado ingressou na prioridade mais alta, a prioridade mais baixa será enviada. Se os visitantes forem inferiores ao existente, todos serão enviados. As mulheres sempre escolhem o elemento máximo.
Nós repetimos.
Como resultado, cada homem examinou toda a lista de suas mulheres e ficou sozinho ou foi influenciado por alguma mulher. Então nos casaremos com todo mundo.
É possível afastar todo esse processo, mas para que as mulheres corram para os homens? O procedimento é simétrico, mas a solução pode ser diferente. Mas a questão é: quem está melhor com isso?
Teorema Considere não apenas essas duas soluções simétricas, mas o conjunto de todos os sistemas de casamento estáveis. O mecanismo proposto inicialmente (homens correm e mulheres concordam / recusam) leva a um sistema de casamento que é melhor para qualquer homem que qualquer outro e pior que qualquer outro para qualquer mulher.
Casamentos entre pessoas do mesmo sexo
Considere a situação com o casamento entre pessoas do mesmo sexo. Considere um resultado matemático que põe em dúvida a necessidade de legalizá-los. Um exemplo ideologicamente incorreto.
Considere os quatro homossexuais a, b, c, d.
prioridades para a: bcd
prioridades para b: cad
prioridades para c: abd
para d, não importa como classifica os três restantes.
Declaração: não existe um sistema de casamento sustentável neste sistema.
Quantos sistemas existem para quatro pessoas? Três ab cd, ac bd, ad bc. Os pares se desfazem e o processo se repetirá.
Sistemas "tressexuais".Essa é uma pergunta crucial que abre todo um campo da matemática. Isso foi feito pelo meu colega em Moscou, Vladimir Ivanovich Danilov. “Casamento” ele via beber vodka e os papéis eram: “servir”, “brindar” e “quem corta a linguiça”. Em uma situação em que há 4 ou mais representantes de cada função, é impossível resolver com força bruta. A questão de um sistema sustentável está aberta.
Vetor Shapley
Na aldeia dos chalés, eles decidiram pavimentar a estrada. Precisa entrar. Como
Shapley, em 1953, propôs uma solução para esse problema. Suponha uma situação de conflito com um grupo de pessoas N = {1,2 ... n}. Precisa compartilhar os custos / benefícios. Suponha que as pessoas tenham feito algo útil em conjunto; elas venderão e como compartilhar o lucro?
Shapley sugeriu compartilhar quando orientado pelo quanto um ou outro subconjunto dessas pessoas poderia obter. Quanto dinheiro todos os subconjuntos não-vazios 2
N poderiam ganhar. E com base nessas informações, Shapley escreveu uma fórmula universal.
Um exemplo Solista, guitarrista e baterista tocam na passagem subterrânea em Moscou. Os três ganham 1000 rublos por hora. Como compartilhar? Você pode igualmente.
V (1,2,3) = 1000
Suponha que
V (1,2) = 600
V (1,3) = 450
V (2,3) = 400
V (1) = 300
V (2) = 200
V (3) = 100
É impossível determinar uma divisão justa até que saibamos que tipo de lucro espera esta ou aquela empresa se ela se desconectar e agir de forma independente. E quando determinamos os números (pedimos um jogo cooperativo de forma característica).
Superradditividade é quando juntos eles ganham mais do que individualmente, quando é mais lucrativo se unir, mas não está claro como dividir o ganho. Muitas cópias foram quebradas sobre isso.
Há um jogo. Três empresários encontraram simultaneamente um depósito de US $ 1 milhão. Se os três concordarem, então um milhão deles. Qualquer casal pode se afastar (remover do negócio) e obter o milhão inteiro. E ninguém sozinho pode fazer qualquer coisa. Este é um jogo cooperativo assustador, no qual não há solução. Sempre haverá dois que podem eliminar o terceiro ... A teoria dos jogos cooperativos começa com um exemplo que não tem solução.
Mas queremos uma solução que nenhuma coalizão queira bloquear uma solução comum. O conjunto de todos os compartilhamentos que não podem ser bloqueados é o núcleo. Acontece que o núcleo está vazio. Mas mesmo que não esteja vazio, como compartilhar?
Shapley sugere compartilhar assim. Jogue uma moeda com n! facetas. Nesta ordem, escrevemos todos os jogadores. Digamos o primeiro baterista. Ele entra e pega 100. Depois vem o "segundo", digamos, um solista. (Juntamente com o baterista, eles podem ganhar 450, o baterista já venceu 100). O solista leva 350. O guitarrista entra (juntos 1000, -450), leva 550. A última pessoa que entra muitas vezes ganha. (Supermodularidade)
Se escrevermos para todos os pedidos:
GSB - (vitória C) - (vitória G) - (vitória B)
GBS - (vitória C) - (vitória G) - (vitória B)
SBG - (vitória C) - (vitória G) - (vitória B)
BSG - (vitória C) - (vitória G) - (vitória B)
BGS - (vitória C) - (vitória G) - (vitória B)
GBS - (vitória C) - (vitória G) - (vitória B)
E para cada coluna, adicionamos e dividimos por 6 - a média de todos os pedidos é
um vetor Shapley .
Shapley provou o teorema (aproximadamente): Há uma classe de jogos (supermodular) na qual a próxima pessoa a se juntar ao grande time - ele conseguiu uma vitória maior. O kernel nem sempre está vazio e é uma combinação convexa de pontos (no nosso caso, 6 pontos). O vetor Shapley fica no centro do núcleo. Sempre pode ser oferecido como uma solução, ninguém se importará.
Em 1973, ficou provado que o problema com os chalés é supermodular.
O caminho para a primeira casa de campo é compartilhado por todas as n pessoas. Até o segundo - n-1 pessoas. E assim por diante
O aeroporto tem uma pista. Empresas diferentes precisam de comprimentos diferentes. O mesmo problema surge.
Penso que aqueles que emitiram o Prêmio Nobel tinham em mente esse mérito, e não apenas a tarefa do casamento.
Obrigada