W 2012 roku Nagrodę Nobla w dziedzinie ekonomii otrzymali Lloyd Shapley i Alvin Roth. „Za teorię stabilnej dystrybucji i praktykę organizacji rynków”. Aleksey Savvateev w 2012 roku próbował prosto i jasno wyjaśnić istotę zasług matematyków. Zwracam uwagę na podsumowanie .
Dziś odbędzie się wykład teoretyczny. O eksperymentach , w szczególności z darowizną, nie powiem.
Kiedy to ogłoszono otrzymał Nagrodę Nobla, padło standardowe pytanie: „Jak!? Czy on nadal żyje!?!?" Jego najsłynniejszy wynik uzyskano w 1953 roku.
Formalnie premia została przyznana za coś innego. Za artykuł z 1962 r. na temat „twierdzenia o stabilności małżeństwa”: „Przyjęcie na studia i stabilność małżeństwa”.
O trwałym małżeństwie
Dopasowywanie (dopasowanie) - zadanie odnalezienia korespondencji.
Jest pewna odizolowana wioska. Jest „m” młodych mężczyzn i „w” dziewcząt. Musimy ich poślubić. (Niekoniecznie ta sama liczba, może w końcu ktoś zostanie sam.)
Jakie założenia należy przyjąć w modelu? Że nie jest łatwo ponownie wyjść za mąż przez przypadek. Czyni się pewien krok w kierunku wolnego wyboru. Załóżmy, że istnieje mądry aksakal, który chce ożenić się ponownie, aby po jego śmierci nie doszło do rozwodów. (Rozwód to sytuacja, gdy mąż bardziej pragnie za żonę obcej kobiety niż swojej żony.)
Twierdzenie to jest w duchu współczesnej ekonomii. Jest wyjątkowo nieludzka. Ekonomia tradycyjnie była nieludzka. W ekonomii człowieka zastępuje maszyna, która maksymalizuje zyski. To, co wam powiem, jest czymś absolutnie szalonym z moralnego punktu widzenia. Nie bierz tego sobie do serca.
Ekonomiści patrzą na małżeństwo w ten sposób.
m1, m2,… mk - mężczyźni.
w1, w2,... wL - kobiety.
Mężczyzna utożsamia się ze sposobem, w jaki „zamawia” dziewczyny. Istnieje także „poziom zerowy”, poniżej którego kobietom w ogóle nie można proponować za żony, nawet jeśli nie ma innych.
Wszystko dzieje się w obie strony, tak samo u dziewcząt.
Dane początkowe są dowolne. Jedynym założeniem/ograniczeniem jest to, że nie zmieniamy naszych preferencji.
Twierdzenie: Niezależnie od rozkładu i poziomu zera, zawsze istnieje sposób na ustalenie korespondencji jeden do jednego między niektórymi mężczyznami i niektórymi kobietami, tak aby była ona odporna na wszelkiego rodzaju rozłamy (nie tylko rozwody).
Jakie mogą być zagrożenia?
Jest para (m, w), która nie jest małżeństwem. Ale dla mnie obecny mąż jest gorszy od m i dla mnie obecna żona jest gorsza od w. Jest to sytuacja niezrównoważona.
Istnieje też możliwość, że ktoś był w związku małżeńskim z kimś, kto jest „poniżej zera” – w tej sytuacji małżeństwo również się rozpadnie.
Jeśli kobieta jest zamężna, ale woli niezamężnego mężczyznę, dla którego jest powyżej zera.
Jeśli dwie osoby nie są w związku małżeńskim i oboje są dla siebie „powyżej zera”.
Twierdzi się, że dla dowolnych danych wyjściowych istnieje taki system małżeński, odporny na wszelkiego rodzaju zagrożenia. Po drugie, algorytm znajdowania takiej równowagi jest bardzo prosty. Porównajmy z M*N.
Model ten został uogólniony i rozszerzony na „poligamię” i zastosowany w wielu obszarach.
Procedura Gale’a-Shapley’a
Jeśli wszyscy mężczyźni i wszystkie kobiety będą przestrzegać „przepisów”, powstały system małżeński będzie trwały.
Recepty.
W razie potrzeby bierzemy kilka dni. Każdy dzień dzielimy na dwie części (rano i wieczorem).
Pierwszego ranka każdy mężczyzna udaje się do swojej drużby i puka w okno, prosząc ją o rękę.
Wieczorem tego samego dnia kolej na kobiety.Co kobieta może odkryć? Że pod jej oknem był tłum, albo jeden, albo żaden mężczyzna. Ci, którzy dzisiaj nie mają nikogo, pomijają swoją kolej i czekają. Pozostali, którzy mają przynajmniej jednego, sprawdzają przychodzących mężczyzn, czy są „powyżej poziomu zerowego”. Mieć choć jednego. Jeśli masz całkowitego pecha i wszystko jest poniżej zera, to wszyscy powinni zostać wysłani. Kobieta wybiera największego z przybyłych, każe mu poczekać, a resztę wysyła.
Przed drugim dniem sytuacja jest taka: niektóre kobiety mają jednego mężczyznę, inne nie mają żadnego.
Drugiego dnia wszyscy „wolni” (wysłani) mężczyźni muszą udać się do kobiety drugiego priorytetu. Jeśli nie ma takiej osoby, mężczyzna zostaje uznany za kawalera. Ci mężczyźni, którzy już siedzą z kobietami, jeszcze nic nie robią.
Wieczorem kobiety przyglądają się sytuacji. Jeśli do kogoś, kto już siedział, dołączył wyższy priorytet, to niższy priorytet zostaje odesłany. Jeśli liczba tych, którzy przyjdą, będzie niższa od tej, która jest już dostępna, wszyscy zostaną odesłani. Kobiety za każdym razem wybierają element maksymalny.
My powtarzamy.
W rezultacie każdy mężczyzna przejrzał całą listę swoich kobiet i albo został sam, albo związał się z jakąś kobietą. Wtedy wszyscy się pobierzemy.
Czy można przeprowadzić cały ten proces, żeby kobiety nie uciekły do mężczyzn? Procedura jest symetryczna, ale rozwiązanie może być inne. Pytanie jednak brzmi, kto na tym wyjdzie lepiej?
Twierdzenie. Rozważmy nie tylko te dwa symetryczne rozwiązania, ale zbiór wszystkich stabilnych systemów małżeńskich. Pierwotnie proponowany mechanizm (mężczyźni uciekają, kobiety akceptują/odmawiają) skutkuje systemem małżeńskim, który jest lepszy dla każdego mężczyzny niż jakikolwiek inny i gorszy niż jakikolwiek inny dla jakiejkolwiek kobiety.
Małżeństwa osób tej samej płci
Rozważmy sytuację w przypadku „małżeństw osób tej samej płci”. Rozważmy wynik matematyczny podający w wątpliwość potrzebę ich legalizacji. Przykład niepoprawny ideologicznie.
Rozważmy czterech homoseksualistów a, b, c, d.
priorytety dla a: bcd
priorytety dla b:cad
priorytety dla c: abd
dla d nie ma znaczenia, jak uszereguje pozostałe trzy.
Oświadczenie: W tym systemie nie ma trwałego systemu małżeństwa.
Ile systemów jest dostępnych dla czterech osób? Trzy. ab cd, ac bd, ad bc. Pary się rozejdą, a proces będzie przebiegał cyklicznie.
Systemy „trzech płci”.
To najważniejsze pytanie, które otwiera całą dziedzinę matematyki. Zrobił to mój kolega w Moskwie, Władimir Iwanowicz Daniłow. Postrzegał „małżeństwo” jako picie wódki, a role były następujące: „ten, który nalewa”, „ten, który wznosi toast” i „ten, który kroi kiełbasę”. W sytuacji, gdy w każdej roli jest 4 lub więcej przedstawicieli, nie da się rozwiązać problemu metodą brutalnej siły. Kwestia zrównoważonego systemu jest kwestią otwartą.
Wektor Shapleya
W wiosce z domkami postanowiono asfaltować drogę. Trzeba się wtrącić. Jak?
Shapley zaproponował rozwiązanie tego problemu w 1953 roku. Załóżmy sytuację konfliktu z grupą osób N={1,2…n}. Należy dzielić koszty/korzyści. Załóżmy, że ludzie razem zrobili coś pożytecznego, sprzedali to i jak podzielić zysk?
Shapley zasugerował, że przy podziale powinniśmy kierować się tym, ile mogą otrzymać określone podzbiory tych osób. Ile pieniędzy mogą zarobić wszystkie 2N niepuste podzbiory? Na podstawie tych informacji Shapley napisał uniwersalną formułę.
Przykład. Solista, gitarzysta i perkusista grają w podziemnym przejściu w Moskwie. Cała trójka zarabia 1000 rubli za godzinę. Jak to podzielić? Możliwe, że jednakowo.
V(1,2,3)=1000
Udawajmy, że
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Nie można ustalić sprawiedliwego podziału, dopóki nie wiemy, jakie korzyści czeka dana firma, jeśli oderwie się i zacznie działać samodzielnie. A kiedy ustaliliśmy liczby (ustaw grę kooperacyjną w charakterystycznej formie).
Superaddytywność ma miejsce wtedy, gdy razem zarabiają więcej niż osobno, gdy bardziej opłaca się łączyć, ale nie jest jasne, jak podzielić wygraną. Wiele kopii zostało z tego powodu uszkodzonych.
Jest gra. Trzej biznesmeni jednocześnie znaleźli depozyt o wartości 1 miliona dolarów. Jeśli cała trójka się zgodzi, będzie ich milion. Każda para może zabić (usunąć ze sprawy) i zgarnąć cały milion dla siebie. I nikt nie jest w stanie nic zrobić sam. To przerażająca gra kooperacyjna, w której nie ma rozwiązania. Zawsze będą dwie osoby, które mogą wyeliminować trzecią... Teoria gier kooperacyjnych zaczyna się od przykładu, który nie ma rozwiązania.
Chcemy takiego rozwiązania, aby żadna koalicja nie chciała blokować wspólnego rozwiązania. Zbiór wszystkich podziałów, których nie można zablokować, to jądro. Zdarza się, że rdzeń jest pusty. Ale nawet jeśli nie jest pusty, jak dzielić?
Shapley sugeruje taki podział. Rzuć monetą z n! krawędzie. Wypisujemy wszystkich graczy w tej kolejności. Powiedzmy, pierwszy perkusista. Wchodzi i bierze swoje 100. Potem wchodzi „drugi”, powiedzmy solista. (Razem z perkusistą mogą zarobić 450, perkusista wziął już 100) Solista bierze 350. Gitarzysta wchodzi (razem 1000, -450), bierze 550. Ostatni w dość często wygrywa. (Supermodularność)
Jeśli dla wszystkich zamówień napiszemy:
GSB - (wygrana C) - (wygrana D) - (wygrana B)
SGB – (wygrana C) – (wygrana D) – (wygrana B)
SBG - (wygrana C) - (wygrana D) - (wygrana B)
BSG - (wygrana C) - (wygrana D) - (wygrana B)
BGS - (zysk C) - (zysk D) - (zysk B)
GBS - (wygrana C) - (wygrana D) - (wygrana B)
I dla każdej kolumny dodajemy i dzielimy przez 6 - uśredniając wszystkie zamówienia - to jest wektor Shapleya.
Shapley udowodnił twierdzenie (w przybliżeniu): Istnieje klasa gier (supermodularnych), w których kolejna osoba dołączająca do dużego zespołu przynosi większą wygraną. Jądro jest zawsze niepuste i jest wypukłą kombinacją punktów (w naszym przypadku 6 punktów). Wektor Shapleya leży w samym środku jądra. Zawsze można to zaproponować jako rozwiązanie, nikt nie będzie przeciwko temu.
W 1973 roku udowodniono, że problem domków letniskowych ma charakter supermodułowy.
Wszystkie n osób dzieli drogę do pierwszego domku. Do drugiej - n-1 osób. Itp.
Lotnisko posiada pas startowy. Różne firmy potrzebują różnych długości. Pojawia się ten sam problem.
Myślę, że przyznający Nagrodę Nobla mieli na myśli właśnie tę zasługę, a nie tylko zadanie marginesu.
Dziękuję!
Ещё
- Kanał „Matematyka – prosta”:
- Kanał „Savvateev bez granic”: edusex.ru, brainsex.ru, studfuck.ru
- Publiczne „Matematyka jest prosta”:
- Publiczny „żart matematyków”:
- Strona internetowa, wszystkie wykłady +100 lekcji i więcej: savvateev.xyz
Źródło: www.habr.com