Godine 2012. Nobelovu nagradu za ekonomiju dobili su Lloyd Shapley i Alvin Roth. "Za teoriju stabilne distribucije i praksu organizovanja tržišta." Aleksey Savvateev je 2012. godine pokušao jednostavno i jasno objasniti suštinu zasluga matematičara. Predstavljam Vašoj pažnji sažetak .
Danas će biti održano teorijsko predavanje. O eksperimentima , posebno sa donacijom, neću reći.
Когда объявили, что получил нобелевку, был стандартный вопрос: «Как!? Он ещё жив!?!?» Самый знаменитый его результат был получен в 1953 году.
Formalno, bonus je davan za nešto drugo. Za njegov rad iz 1962. o “teoremi stabilnosti braka”: “Prijem na fakultet i stabilnost braka”.
Об устойчивом бракосочетании
odgovarajući (podudaranje) - zadatak pronalaženja korespondencije.
Postoji jedno izolovano selo. Ima “m” mladića i “w” djevojaka. Moramo ih udati jedno za drugo. (Ne nužno isti broj, možda će na kraju neko ostati sam.)
Koje pretpostavke treba napraviti u modelu? Da nije lako nasumično se ponovo oženiti. Pravi se određeni korak ka slobodnom izboru. Recimo da postoji mudri aksakal koji želi da se ponovo oženi da nakon njegove smrti ne počnu razvodi. (Razvod je situacija kada muž želi ženu treće strane za ženu više nego svoju ženu.)
Ova teorema je u duhu moderne ekonomije. Ona je izuzetno neljudska. Ekonomija je tradicionalno bila nehumana. U ekonomiji čovjeka zamjenjuje mašina kako bi se maksimizirao profit. Ono što ću vam reći su apsolutno lude stvari sa moralne tačke gledišta. Ne uzimaj to k srcu.
Ekonomisti na ovaj način gledaju na brak.
m1, m2,… mk - muškarci.
w1, w2,… wL — женщины.
Muškarac se identifikuje sa načinom na koji „naređuje“ devojke. Postoji i „nulti nivo“, ispod kojeg se žene uopšte ne mogu nuditi za žene, čak i ako nema drugih.
Sve se dešava u oba smera, isto za devojke.
Početni podaci su proizvoljni. Jedina pretpostavka/ograničenje je da ne mijenjamo svoje preferencije.
Teorema: Bez obzira na distribuciju i nivo nule, uvijek postoji način da se uspostavi korespondencija jedan-na-jedan između nekih muškaraca i nekih žena tako da bude otporna na sve vrste podjela (ne samo na razvode).
Kakve pretnje mogu postojati?
Есть пара (m,w), которая не находится в браке. Но для w текущий муж хуже чем m, а для m текущая жена хуже, чем w. Это неустойчивая ситуация.
Postoji i opcija da je neko bio u braku sa nekim ko je „ispod nule“ i u ovoj situaciji brak će se raspasti.
Ako je žena udata, ali više voli neoženjenog muškarca, za kojeg je iznad nule.
Ako su dvije osobe obje nevjenčane, a oboje su jedno za drugo "iznad nule".
Tvrdi se da za sve početne podatke postoji takav sistem braka, otporan na sve vrste prijetnji. Drugo, algoritam za pronalaženje takve ravnoteže je vrlo jednostavan. Hajde da uporedimo sa M*N.
Ovaj model je generalizovan i proširen na "poligamiju" i primenjen u mnogim oblastima.
Gale-Shapleyeva procedura
Ako svi muškarci i sve žene slijede “recepte”, rezultirajući bračni sistem će biti održiv.
Recepti.
Uzimamo nekoliko dana po potrebi. Svaki dan dijelimo na dva dijela (jutro i veče).
Prvog jutra svaki muškarac odlazi svojoj kumi i kuca na prozor tražeći od nje da se uda za njega.
Uveče istog dana, red dolazi na žene. Šta žena može otkriti? Da je pod njenim prozorom bila gomila, bilo jedan ili nijedan muškarac. Oni koji danas nemaju nikoga, preskaču svoj red i čekaju. Ostali, koji imaju barem jednog, provjeravaju muškarce koji dođu da vide da su “iznad nulte razine”. Da imam barem jednu. Ako ste potpuno nesretni i sve je ispod nule, onda sve treba poslati. Žena bira najvećeg od onih koji su došli, kaže mu da čeka, a ostale šalje.
Pre drugog dana situacija je sledeća: neke žene imaju jednog muškarca, neke nemaju.
Drugog dana, svi “slobodni” (poslani) muškarci treba da odu kod žene drugog prioriteta. Ako takva osoba ne postoji, onda se muškarac proglašava samcem. Oni muškarci koji već sjede sa ženama još ništa ne rade.
Uveče žene sagledavaju situaciju. Ako se nekome ko je već sjedio pridružio veći prioritet, onda se odbacuje niži prioritet. Ako su oni koji dolaze manji od onoga što je već dostupno, svi se šalju. Žene svaki put biraju maksimalan element.
Ponavljamo.
Kao rezultat toga, svaki muškarac je prošao kroz čitav spisak svojih žena i bio je ili ostavljen sam ili zaručen sa nekom ženom. Onda ćemo sve oženiti.
Da li je moguće voditi cijeli ovaj proces, ali da žene trče muškarcima? Postupak je simetričan, ali rješenje može biti drugačije. Ali pitanje je, kome je bolje od ovoga?
Teorema. Razmotrimo ne samo ova dva simetrična rješenja, već skup svih stabilnih bračnih sistema. Originalni predloženi mehanizam (muškarci trče, a žene prihvataju/odbijaju) rezultira bračnim sistemom koji je bolji za svakog muškarca od bilo kojeg drugog i gori od bilo kojeg drugog za bilo koju ženu.
Istopolni brakovi
Razmotrite situaciju sa “istospolnim brakovima”. Razmotrimo matematički rezultat koji dovodi u sumnju potrebu da se oni legaliziraju. Ideološki netačan primjer.
Razmotrimo četiri homoseksualca a, b, c, d.
prioriteti za: bcd
prioriteti za b:cad
prioriteti za c: abd
для d не имеет значение как он ранжирует оставшихся трёх.
Izjava: U ovom sistemu ne postoji sistem održivog braka.
Koliko sistema postoji za četiri osobe? Tri. ab cd, ac bd, ad bc. Parovi će se raspasti i proces će ići u ciklusima.
«Трёхполые» системы.
Ovo je najvažnije pitanje koje otvara čitavo polje matematike. To je uradio moj kolega u Moskvi Vladimir Ivanovič Danilov. Na „brak“ je gledao kao na ispijanje votke, a uloge su bile sljedeće: „onaj koji toči“, „onaj koji govori tost“ i „onaj koji seče kobasicu“. U situaciji kada ima 4 ili više predstavnika svake uloge, to je nemoguće riješiti grubom silom. Pitanje održivog sistema je otvoreno.
Shapley vektor
U vikend naselju su odlučili asfaltirati cestu. Treba ubaciti. Kako?
Shapley je predložio rješenje za ovaj problem 1953. godine. Pretpostavimo situaciju sukoba sa grupom ljudi N={1,2…n}. Trebate podijeliti troškove/koristi. Pretpostavimo da su ljudi zajedno uradili nešto korisno, prodali to i kako podijeliti zaradu?
Shapley je sugerirao da se prilikom podjele trebamo voditi time koliko bi određeni podskupovi ovih ljudi mogli primiti. Koliko novca mogu zaraditi svi 2N nepraznih podskupova? I na osnovu ovih informacija, Shapley je napisao univerzalnu formulu.
Primjer. Солист, гитарист и барабанщик играют в подземном переходе в Москве. Втроем они зарабатывают 1000 рублей в час. Как её делить? Можно поровну.
V(1,2,3)=1000
Pretvarajmo se
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Pravedna podjela se ne može utvrditi dok ne znamo koji dobici čekaju datu kompaniju ako se odvoji i djeluje samostalno. I kada smo odredili brojeve (postavili kooperativnu igru u karakterističan oblik).
Супераддитивность — это когда вместе зарабатывают больше, чем по отдельности, когда выгоднее объединиться, но непонятно как разделить выигрыш. По этому поводу сломано много копий.
Postoji igra. Tri biznismena su istovremeno pronašla depozit u vrednosti od milion dolara. Ako se njih troje slože, onda ih je milion. Svaki par može ubiti (ukloniti iz slučaja) i dobiti cijeli milion za sebe. I niko ništa ne može sam. Ovo je zastrašujuća zajednička igra bez rješenja. Uvijek će biti dvoje ljudi koji mogu eliminirati trećeg... Kooperativna teorija igara počinje primjerom koji nema rješenje.
Želimo takvo rješenje da nijedna koalicija neće htjeti blokirati zajedničko rješenje. Skup svih podjela koji se ne mogu blokirati je kernel. Dešava se da je jezgro prazno. Ali čak i ako nije prazan, kako podijeliti?
Shapley predlaže podjelu na ovaj način. Baci novčić sa n! ivice. Ovim redom ispisujemo sve igrače. Recimo prvi bubnjar. Uđe i uzme svojih 100. Onda dolazi "drugi", recimo solista. (Zajedno sa bubnjarom mogu zaraditi 450, bubnjar je već uzeo 100) Solista uzima 350. Gitarista ulazi (zajedno 1000, -450), uzima 550. Poslednji često pobjeđuje. (supermodularnost)
Если мы для всех порядков выпишем:
GSB - (pobjeda C) - (pobjeda D) - (pobjeda B)
SGB - (pobjeda C) - (pobjeda D) - (pobjeda B)
SBG - (pobjeda C) - (pobjeda D) - (pobjeda B)
BSG - (pobjeda C) - (pobjeda D) - (pobjeda B)
BGS - (pojačanje C) - (pojačanje D) - (pojačanje B)
ГБС — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
I za svaku kolonu dodajemo i dijelimo sa 6 - u prosjeku za sve narudžbe - ovo je Shapleyjev vektor.
Shapley je dokazao teoremu (približno): Postoji klasa igara (supermodularna), u kojoj sljedeća osoba koja se pridruži velikom timu donosi veću pobjedu. Kernel je uvijek neprazan i predstavlja konveksnu kombinaciju tačaka (u našem slučaju 6 tačaka). Šeplijev vektor leži u samom centru jezgra. Uvek se može ponuditi kao rešenje, niko neće biti protiv.
1973. godine dokazano je da je problem sa vikendicama supermodularan.
Дорогу до первого коттеджа делят все n человек. До второго — n-1 человек. И тд.
Aerodrom ima pistu. Različite kompanije trebaju različite dužine. Isti problem se javlja.
Mislim da su oni koji su dodijelili Nobelovu nagradu imali na umu ovu zaslugu, a ne samo zadatak margine.
Hvala vam!
Ipak
- Kanal “Matematika - Jednostavno”:
- Канал «Савватеев без границ»: edusex.ru, brainsex.ru, studfuck.ru
- Javno “Matematika je jednostavna”:
- Паблик «Математики шутят»:
- Сайт, все лекции там +100 уроков и прочее: savvateev.xyz
izvor: www.habr.com