Godine 2012. Nobelovu nagradu za ekonomiju dobili su Lloyd Shapley i Alvin Roth. "Za teoriju stabilne distribucije i praksu organiziranja tržišta." Aleksey Savvateev 2012. pokušao je jednostavno i jasno objasniti bit zasluga matematičara. Predstavljam vam sažetak .
Danas će biti teoretsko predavanje. O eksperimentima , posebno s donacijom, neću reći.
Kad je to objavljeno dobio Nobelovu nagradu, bilo je standardno pitanje: “Kako!? Je li još živ!?!?” Njegov najpoznatiji rezultat postignut je 1953.
Formalno, bonus je dat za nešto drugo. Za njegov rad iz 1962. o “teoremu o stabilnosti braka”: “Upis na fakultet i stabilnost braka.”
O održivom braku
Odgovarajući (podudaranje) - zadatak pronalaženja korespondencije.
Postoji izvjesno izolirano selo. Ima “m” mladića i “w” djevojaka. Moramo ih vjenčati jedno s drugim. (Ne nužno isti broj, možda na kraju netko ostane sam.)
Koje pretpostavke treba napraviti u modelu? Da nije lako ponovno se nasumično udati. Čini se određeni korak prema slobodnom izboru. Recimo, postoji mudar aksakal koji se želi ponovno oženiti da nakon njegove smrti ne počnu razvodi. (Razvod je situacija kada muž više želi treću ženu za ženu nego svoju ženu.)
Ovaj je teorem u duhu moderne ekonomije. Ona je izuzetno neljudska. Ekonomija je tradicionalno nehumana. U ekonomiji, čovjeka zamjenjuje stroj kako bi se maksimizirao profit. Ono što ću vam reći su apsolutno lude stvari s moralne točke gledišta. Ne uzimaj to k srcu.
Ekonomisti na brak gledaju na ovaj način.
m1, m2,… mk - muškarci.
w1, w2,... wL - žene.
Muškarac se poistovjećuje s tim kako "naređuje" djevojkama. Postoji i “nulta razina”, ispod koje žene uopće ne mogu biti ponuđene za supruge, čak i ako nema drugih.
Sve se odvija u oba smjera, kod djevojaka isto.
Početni podaci su proizvoljni. Jedina pretpostavka/ograničenje je da ne mijenjamo svoje preferencije.
Teorema: Bez obzira na distribuciju i razinu 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 razvoda (ne samo na razvode).
Kakve prijetnje mogu biti?
Postoji par (m,ž) koji nije u braku. Ali za w sadašnji muž je gori od m, a za m trenutna žena je gora od w. Ovo je neodrživa situacija.
Postoji i opcija da je netko bio u braku s nekim tko je “ispod nule”, u toj situaciji će se i brak raspasti.
Ako je žena udana, ali preferira neoženjenog muškarca, za kojeg je iznad nule.
Ako su dvoje ljudi oboje nevjenčani, i oboje su jedno za drugo "iznad nule".
Tvrdi se da za sve početne podatke postoji takav bračni sustav, otporan na sve vrste prijetnji. Drugo, algoritam za pronalaženje takve ravnoteže je vrlo jednostavan. Usporedimo s M*N.
Ovaj model je generaliziran i proširen na "poligamiju" i primijenjen u mnogim područjima.
Gale-Shapleyjev postupak
Ako svi muškarci i sve žene slijede "recepte", rezultirajući bračni sustav bit će održiv.
Recepti.
Po potrebi uzimamo nekoliko dana. Svaki dan dijelimo na dva dijela (jutro i večer).
Prvog jutra svaki muškarac ide svojoj kumi i kuca na prozor tražeći da se uda za njega.
Navečer istoga dana red dolazi na žene.Što žena može otkriti? Da je pod njenim prozorom gužva, ili jedan ili nijedan muškarac. Oni koji danas nemaju nikoga preskoče svoj red i čekaju. Ostali, koji imaju barem jednog, provjeravaju muškarce koji dolaze da vide da su “iznad nulte razine”. Imati barem jednu. Ako ste totalni peh i sve je ispod nule, onda treba poslati svakoga. Žena izabere najvećeg od onih koji su došli, kaže mu da čeka, a ostatak pošalje.
Prije drugog dana situacija je ovakva: neke žene imaju jednog muškarca, neke nemaju nijednog.
Drugi dan, svi “slobodni” (poslani) muškarci trebaju ići kod žene drugog prioriteta. Ako takve osobe nema, tada se muškarac proglašava samcem. Ti muškarci koji već sjede sa ženama još ništa ne rade.
Navečer žene gledaju situaciju. Ako se nekome tko je već sjedio pridružio viši prioritet, tada se niži prioritet šalje. Ako su oni koji dolaze niži od onoga što je već dostupno, svi su otjerani. Žene svaki put biraju maksimalan element.
ponavljamo.
Kao rezultat toga, svaki je muškarac prošao kroz cijeli popis svojih žena i ostao sam ili zaručen s nekom ženom. Onda ćemo sve vjenčati.
Je li moguće voditi cijeli ovaj proces, a da žene trče muškarcima? Postupak je simetričan, ali rješenje može biti drugačije. Ali pitanje je kome je od ovoga bolje?
Teorema. Razmotrimo ne samo ova dva simetrična rješenja, već skup svih stabilnih bračnih sustava. Izvorni predloženi mehanizam (muškarci trče, a žene prihvaćaju/odbijaju) rezultira bračnim sustavom koji je bolji za bilo kojeg muškarca od bilo kojeg drugog, a gori od bilo kojeg drugog za bilo koju ženu.
Istospolni brak
Razmotrite situaciju s "istospolnim brakom". Razmotrimo matematički rezultat koji baca sumnju na potrebu njihove legalizacije. Ideološki nekorektan primjer.
Razmotrimo četiri homoseksualca a, b, c, d.
prioriteti za a: bcd
prioriteti za b:cad
prioriteti za c: abd
za d nije važno kako će poredati preostala tri.
Izjava: U ovom sustavu nema održivog bračnog sustava.
Koliko ima sustava za četiri osobe? Tri. ab cd, ac bd, ad bc. Parovi će se raspasti i proces će ići u ciklusima.
"Trorodni" sustavi.
Ovo je najvažnije pitanje koje otvara cijelo jedno polje matematike. To je učinio 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 reže kobasicu”. U situaciji kada postoje 4 ili više predstavnika svake uloge, to je nemoguće riješiti brutalnom silom. Pitanje održivog sustava je otvoreno.
Shapleyev vektor
U vikend naselju odlučili su asfaltirati cestu. Treba uplatiti. Kako?
Shapley je 1953. predložio rješenje za ovaj problem. Pretpostavimo situaciju sukoba s grupom ljudi N={1,2…n}. Troškove/koristi treba podijeliti. Pretpostavimo da su ljudi zajedno napravili nešto korisno, prodali to i kako podijeliti dobit?
Shapley je predložio da se pri dijeljenju trebamo voditi time koliko određene podskupine tih ljudi mogu primiti. Koliko bi novca mogli zaraditi svi 2N nepraznih podskupova? I na temelju tih podataka Shapley je napisao univerzalnu formulu.
Primjer. Solist, gitarist i bubnjar sviraju u podzemnom prolazu u Moskvi. Njih troje zarađuju 1000 rubalja po satu. Kako to podijeliti? Moguće podjednako.
V(1,2,3)=1000
Pretvarajmo se to
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Pravedna podjela ne može se utvrditi dok ne znamo koji dobici čekaju datu tvrtku ako se odvoji i djeluje samostalno. I kada smo odredili brojeve (postavili kooperativnu igru u karakterističnom obliku).
Superaditivnost je kada zajedno zarađuju više nego odvojeno, kada je isplativije udružiti se, ali nije jasno kako podijeliti dobitak. Mnogo je kopija polomljeno oko ovoga.
Postoji igra. Tri poduzetnika istovremeno su pronašla depozit vrijedan milijun dolara. Ako se njih troje slažu, onda ih je milijun. Svaki par može ubiti (ukloniti iz slučaja) i dobiti cijeli milijun za sebe. I nitko ne može ništa sam. Ovo je zastrašujuća co-op igra bez rješenja. Uvijek će biti dvoje ljudi koji mogu eliminirati trećeg... Teorija kooperativne igre počinje s primjerom koji nema rješenja.
Želimo takvo rješenje da niti jedna koalicija neće htjeti blokirati zajedničko rješenje. Skup svih odjeljaka koji se ne mogu blokirati je kernel. Događa se da je jezgra prazna. Ali ako i nije prazna, kako podijeliti?
Shapley predlaže podjelu na ovaj način. Bacite novčić s n! rubovi. Ispisujemo sve igrače ovim redom. Recimo prvi bubnjar. On ulazi i uzima svojih 100. Onda ulazi “drugi”, recimo solist. (Zajedno s bubnjarom mogu zaraditi 450, bubnjar je već uzeo 100) Solist uzme 350. Uđe gitarist (zajedno 1000, -450), uzme 550. Zadnji u dosta često pobjeđuje. (Supermodularnost)
Ako ispisujemo za sve narudžbe:
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)
GBS - (pobjeda C) - (pobjeda D) - (pobjeda B)
A za svaki stupac zbrajamo i dijelimo sa 6 - prosjek svih narudžbi - ovo je Shapleyev vektor.
Shapley je dokazao teorem (približno): Postoji klasa igara (supermodularnih), u kojima sljedeća osoba koja se pridruži velikom timu donosi veću pobjedu. Jezgra je uvijek neprazna i konveksna je kombinacija točaka (u našem slučaju 6 točaka). Shapleyev vektor nalazi se u samom središtu jezgre. Uvijek se može ponuditi kao rješenje, nitko neće biti protiv.
Godine 1973. dokazano je da je problem s vikendicama supermodularan.
Svih n ljudi dijeli put do prve kućice. Do drugog - n-1 ljudi. itd.
Zračna luka ima pistu. Različite tvrtke trebaju različite duljine. Pojavljuje se isti problem.
Mislim da su oni koji su dodijelili Nobelovu nagradu imali na umu tu zaslugu, a ne samo zadatak margine.
Hvala vam!
Još
- Kanal “Matematika - Jednostavno”:
- Kanal “Savvateev bez granica”: edusex.ru, brainsex.ru, studfuck.ru
- Javna “Matematika je jednostavna”:
- Javna “Šala matematičara”:
- Web stranica, sva predavanja tamo +100 lekcija i više: savvateev.xyz
Izvor: www.habr.com