Em 2012, o Prémio Nobel da Economia foi atribuído a Lloyd Shapley e Alvin Roth. "Pela teoria da distribuição estável e pela prática de organização de mercados." Aleksey Savvateev em 2012 tentou explicar de forma simples e clara a essência dos méritos dos matemáticos. Apresento a sua atenção um resumo .
Hoje haverá palestra teórica. Sobre experimentos , principalmente com doação, não vou contar.
Quando foi anunciado que 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 bônus era concedido para outra coisa. Por seu artigo de 1962 sobre o “teorema da estabilidade do casamento”: “Admissão na faculdade e estabilidade do casamento”.
Sobre casamento sustentável
Correspondente (correspondência) - a tarefa de encontrar uma correspondência.
Existe uma certa aldeia isolada. Existem “m” rapazes e “w” moças. Precisamos casá-los um com o outro. (Não necessariamente o mesmo número, talvez no final alguém fique sozinho.)
Que suposições precisam ser feitas no modelo? Que não é fácil casar novamente ao acaso. Um certo passo está sendo dado em direção à livre escolha. Digamos que haja um aksakal sábio que queira se casar novamente para que, após sua morte, o divórcio não comece. (O divórcio é uma situação em que o marido deseja mais uma mulher terceirizada como esposa do que sua esposa.)
Este teorema está no espírito da economia moderna. Ela é excepcionalmente desumana. A economia tem sido tradicionalmente desumana. Na economia, o homem é substituído por uma máquina para maximizar os lucros. O que vou lhe contar são coisas absolutamente malucas do ponto de vista moral. Não leve isso a sério.
Os economistas olham para o casamento desta forma.
m1, m2,… mk - homens.
w1, w2,... wL - mulheres.
Um homem é identificado pela forma como ele “ordena” as meninas. Existe também um “nível zero”, abaixo do qual as mulheres não podem ser oferecidas como esposas, mesmo que não haja outras.
Tudo acontece nas duas direções, o mesmo para as meninas.
Os dados iniciais são arbitrários. A única suposição/limitação é que não mudamos nossas preferências.
Teorema: Independentemente da distribuição e do nível zero, há sempre uma forma de estabelecer uma correspondência um-para-um entre alguns homens e algumas mulheres, de modo que seja robusta a todos os tipos de cisões (não apenas aos divórcios).
Que ameaças podem existir?
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 insustentável.
Há também a opção de alguém ter sido casado com alguém “abaixo de zero”, nesta situação o casamento também desmoronará.
Se a mulher é casada, mas prefere um homem solteiro, para quem está acima de zero.
Se duas pessoas são solteiras e ambas estão “acima de zero” uma para a outra.
Argumenta-se que para quaisquer dados iniciais existe tal sistema de casamento, resistente a todos os tipos de ameaças. Em segundo lugar, o algoritmo para encontrar tal equilíbrio é muito simples. Vamos comparar com M*N.
Este modelo foi generalizado e expandido para a “poligamia” e aplicado em muitas áreas.
Procedimento Gale-Shapley
Se todos os homens e todas as mulheres seguirem as “prescrições”, o sistema de casamento resultante será sustentável.
Prescrições.
Levamos alguns dias conforme necessário. Dividimos cada dia em duas partes (manhã e noite).
Na primeira manhã, cada homem vai até sua padrinho e bate na janela, pedindo-a em casamento.
Na noite do mesmo dia, é a vez das mulheres: o que uma mulher pode descobrir? Que havia uma multidão debaixo da janela dela, com um ou nenhum homem. Quem não tem ninguém hoje pula a vez e espera. Os restantes, que têm pelo menos um, verificam os homens que vêm para ver se estão “acima do nível zero”. Para ter pelo menos um. Se você não tiver sorte e tudo estiver abaixo de zero, todos deverão ser enviados. A mulher escolhe o maior dos que vieram, manda ele esperar e manda os demais.
Antes do segundo dia, a situação é esta: algumas mulheres têm um homem, outras não.
No segundo dia, todos os homens “livres” (enviados) precisam ir até a mulher de segunda prioridade. Se tal pessoa não existir, o homem é declarado solteiro. Aqueles homens que já estão sentados com mulheres ainda não estão fazendo nada.
À noite, as mulheres analisam a situação. Se alguém que já estava sentado foi acompanhado por uma prioridade mais alta, a prioridade mais baixa será dispensada. Se quem chega for inferior ao que já está disponível, todos são mandados embora. 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 ficou noivo de alguma mulher. Então casaremos todos.
É possível comandar todo esse processo, mas as mulheres correrem para os homens? O procedimento é simétrico, mas a solução pode ser diferente. Mas a questão é: quem está melhor com isso?
Teorema. Consideremos não apenas estas duas soluções simétricas, mas o conjunto de todos os sistemas de casamento estáveis. O mecanismo originalmente proposto (os homens correm e as mulheres aceitam/recusam) resulta num sistema de casamento que é melhor para qualquer homem do que qualquer outro e pior do que qualquer outro para qualquer mulher.
Casamentos entre pessoas do mesmo sexo
Considere a situação do “casamento entre pessoas do mesmo sexo”. Consideremos um resultado matemático que põe em dúvida a necessidade de legalizá-los. Um exemplo ideologicamente incorreto.
Considere quatro homossexuais a, b, c, d.
prioridades para a: bcd
prioridades para b:cad
prioridades para c: abd
para d não importa como ele 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 casais se desintegrarão e o processo ocorrerá em ciclos.
Sistemas de “três gêneros”.
Esta é a questão mais importante que abre todo um campo da matemática. Isto foi feito pelo meu colega em Moscou, Vladimir Ivanovich Danilov. Ele via “casamento” como beber vodca e os papéis eram os seguintes: “aquele que serve”, “aquele que faz o brinde” e “aquele que corta a salsicha”. Numa situação em que existem 4 ou mais representantes de cada função, é impossível resolver pela força bruta. A questão de um sistema sustentável é uma questão em aberto.
Vetor Shapley
Na vila de chalés, decidiram asfaltar a estrada. Precisa contribuir. Como?
Shapley propôs uma solução para este problema em 1953. Vamos supor uma situação de conflito com um grupo de pessoas N={1,2…n}. Os custos/benefícios precisam ser compartilhados. Suponha que as pessoas juntas façam algo útil, vendam e como dividir o lucro?
Shapley sugeriu que, ao dividir, deveríamos ser guiados por quanto certos subconjuntos dessas pessoas poderiam receber. Quanto dinheiro todos os 2N subconjuntos não vazios poderiam ganhar? E com base nesta informação, Shapley escreveu uma fórmula universal.
Exemplo. Solista, guitarrista e baterista tocam em passagem subterrânea em Moscou. Os três ganham 1000 rublos por hora. Como dividir isso? Possivelmente igualmente.
V(1,2,3)=1000
Vamos fingir que
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Uma divisão justa não pode ser determinada até que saibamos que ganhos aguardam uma determinada empresa se esta se separar e agir por conta própria. E quando determinamos os números (definimos o jogo cooperativo de forma característica).
Superaditividade é quando juntos ganham mais do que separadamente, quando é mais lucrativo unir, mas não está claro como dividir os ganhos. Muitas cópias foram quebradas por causa disso.
Existe um jogo. Três empresários encontraram simultaneamente um depósito no valor de US$ 1 milhão. Se os três concordarem, então haverá um milhão deles. Qualquer casal pode matar (retirar do caso) e ficar com o milhão inteiro para si. E ninguém pode fazer nada sozinho. Este é um jogo cooperativo assustador sem solução. Sempre haverá duas pessoas que poderão eliminar a terceira... A teoria dos jogos cooperativos começa com um exemplo que não tem solução.
Queremos uma solução tal que nenhuma coligação queira bloquear a solução comum. O conjunto de todas as divisões que não podem ser bloqueadas é o kernel. Acontece que o núcleo está vazio. Mas mesmo que não esteja vazio, como dividir?
Shapley sugere dividir desta forma. Jogue uma moeda com n! arestas. Escrevemos todos os jogadores nesta ordem. Digamos o primeiro baterista. Ele entra e leva seus 100. Aí entra o “segundo”, digamos o solista. (Junto com o baterista podem ganhar 450, o baterista já levou 100) O solista leva 350. O guitarrista entra (juntos 1000, -450), leva 550. O último ganha muitas vezes. (Supermodularidade)
Se escrevermos para todos os pedidos:
GSB - (vitória C) - (vitória D) - (vitória B)
SGB - (vitória C) - (vitória D) - (vitória B)
SBG - (vitória C) - (vitória D) - (vitória B)
BSG - (vitória C) - (vitória D) - (vitória B)
BGS - (ganho C) - (ganho D) - (ganho B)
GBS - (vitória C) - (vitória D) - (vitória B)
E para cada coluna somamos e dividimos por 6 - calculando a média de todos os pedidos - este é um vetor Shapley.
Shapley provou o teorema (aproximadamente): Existe uma classe de jogos (supermodulares), em que a próxima pessoa a ingressar em um time grande traz uma vitória maior. O kernel está sempre não vazio e é uma combinação convexa de pontos (no nosso caso, 6 pontos). O vetor Shapley está bem no centro do núcleo. Sempre pode ser oferecido como solução, ninguém será contra.
Em 1973, ficou comprovado que o problema dos chalés é supermodular.
Todas as n pessoas compartilham o caminho para a primeira casa. Até o segundo - n-1 pessoas. Etc.
O aeroporto tem uma pista. Diferentes empresas precisam de comprimentos diferentes. Surge o mesmo problema.
Penso que quem atribuiu o Prémio Nobel tinha em mente esse mérito e não apenas a tarefa da margem.
Obrigado!
Ещё
- Canal “Matemática é simples”:
- Canal “Savvateev sem fronteiras”: edusex.ru, brainsex.ru, studfuck.ru
- Público “Matemática é simples”:
- “Piada dos matemáticos” pública:
- Site, todas as palestras lá +100 aulas e mais: savvateev.xyz
Fonte: habr.com