2012-ben a közgazdasági Nobel-díjat Lloyd Shapley és Alvin Roth kapta. "A stabil elosztás elméletéhez és a piacszervezés gyakorlatához." Aleksey Savvateev 2012-ben megpróbálta egyszerűen és egyértelműen elmagyarázni a matematikusok érdemeinek lényegét. Egy összefoglalót ajánlok figyelmükbe .
Ma elméleti előadás lesz. A kísérletekről , főleg adományozással, nem árulom el.
Amikor bejelentették, hogy megkapta a Nobel-díjat, volt egy standard kérdés: „Hogyan!? Él még!?!?" Leghíresebb eredményét 1953-ban érte el.
Formálisan másért adták a bónuszt. A „házasság stabilitási tételéről” szóló 1962-es tanulmányához: „Főiskolai felvétel és a házasság stabilitása”.
A fenntartható házasságról
Hozzáillő (illesztés) - a megfelelés megtalálásának feladata.
Van egy elszigetelt falu. Vannak „m” fiatal férfiak és „w” lányok. Össze kell házasítanunk őket. (Nem feltétlenül ugyanaz a szám, talán a végén valaki egyedül marad.)
Milyen feltételezéseket kell tenni a modellben? Hogy nem könnyű véletlenül újraházasodni. Egy bizonyos lépést tesznek a szabad választás felé. Tegyük fel, hogy van egy bölcs aksakal, aki újra meg akar házasodni, hogy a halála után ne kezdődjenek el a válások. (A válás olyan helyzet, amikor a férj jobban akar egy harmadik féltől származó nőt feleségének, mint a feleségét.)
Ez a tétel a modern közgazdaságtan szellemében van. Kivételesen embertelen. A közgazdaságtan hagyományosan embertelen. A közgazdaságtanban az embert egy gép váltja fel a profit maximalizálása érdekében. Amit elmondok, erkölcsi szempontból teljesen őrült dolgok. Ne vedd a szívedre.
A közgazdászok így néznek a házasságra.
m1, m2,… mk - férfiak.
w1, w2,... wL - nők.
A férfit azzal azonosítják, hogyan „rendeli” a lányokat. Létezik egy „nulla szint” is, amely alatt nőket egyáltalán nem lehet feleségül ajánlani, még ha nincs is más.
Minden mindkét irányban történik, lányoknál ugyanaz.
A kezdeti adatok tetszőlegesek. Az egyetlen feltevés/korlátozás az, hogy nem változtatunk a preferenciáinkon.
Tétel: Az eloszlástól és a nulla szinttől függetlenül mindig van mód egy-egy kapcsolat létrehozására néhány férfi és néhány nő között, hogy az minden típusú szakításra (nem csak a válásra) ellenálljon.
Milyen fenyegetések lehetnek?
Van egy pár (m,w), aki nem házas. De w esetében a jelenlegi férj rosszabb, mint m, és m esetében a jelenlegi feleség rosszabb, mint w. Ez egy tarthatatlan helyzet.
Arra is van lehetőség, hogy valaki „nulla alatti” emberrel kötött házasságot, ebben a helyzetben a házasság is szétesik.
Ha egy nő nős, de inkább egy hajadon férfit szeret, akinek nulla felett van.
Ha két ember mindketten nem házasok, és mindkettő „nulla felett” van egymásnak.
Azt állítják, hogy minden kezdeti adat esetében létezik egy ilyen házassági rendszer, amely ellenáll mindenféle fenyegetésnek. Másodszor, az ilyen egyensúly megtalálásának algoritmusa nagyon egyszerű. Hasonlítsuk össze M*N-nel.
Ezt a modellt általánosították és kiterjesztették „poligámiára”, és számos területen alkalmazták.
Gale-Shapley eljárás
Ha minden férfi és minden nő betartja az „előírásokat”, a létrejövő házassági rendszer fenntartható lesz.
Előírások.
Igény szerint néhány napot veszünk igénybe. Minden napot két részre osztunk (reggel és este).
Az első reggel minden férfi elmegy a legjobb nőjéhez, és bekopogtat az ablakon, kérve, hogy vegye feleségül.
Még aznap este a nők felé fordul a fordulat Mit fedezhet fel egy nő? Hogy tömeg volt az ablaka alatt, vagy egy ember, vagy nem. Azok, akiknek ma nincs senkijük, kihagyják a sorukat és várnak. A többiek, akiknek van legalább egy, ellenőrizzék az odaérkező férfiakat, hogy „nulla szint felett” vannak-e. Hogy legyen legalább egy. Ha teljesen peches vagy és minden nulla alatt van, akkor mindenkit el kell küldeni. A nő kiválasztja a legnagyobbat az érkezők közül, azt mondja neki, hogy várjon, a többit elküldi.
A második nap előtt a helyzet a következő: van akinek egy férfija van, van akinek nincs.
A második napon minden „szabad” (elküldött) férfinak a második prioritású nőhöz kell mennie. Ha nincs ilyen személy, akkor a férfit egyedülállónak nyilvánítják. Azok a férfiak, akik már nőkkel ülnek, még nem csinálnak semmit.
Este a nők megnézik a helyzetet. Ha valakihez, aki már ült, magasabb prioritású csatlakozott, akkor az alacsonyabb prioritású elküldésre kerül. Ha az érkezők alacsonyabbak a már elérhetőnél, mindenkit elküldenek. A nők minden alkalommal a maximális elemet választják.
Ismételjük.
Ennek eredményeként minden férfi végignézte a női listáját, és vagy egyedül maradt, vagy eljegyeztek egy nőt. Akkor mindenkit összeházasítunk.
Lehetséges ezt az egész folyamatot lefuttatni, de a nők a férfiakhoz futnak? Az eljárás szimmetrikus, de a megoldás eltérő lehet. De a kérdés az, hogy ki jár jobban ettől?
Tétel. Tekintsük nemcsak ezt a két szimmetrikus megoldást, hanem az összes stabil házassági rendszer összességét. Az eredeti javasolt mechanizmus (a férfiak futnak, a nők pedig elfogadják/elutasítják) egy olyan házassági rendszert eredményez, amely minden férfinak jobb, és minden nőnek rosszabb, mint bármelyik másik.
Az azonos neműek házasságai
Fontolja meg az „azonos neműek házasságának” helyzetét. Tekintsünk egy matematikai eredményt, amely kétségbe vonja ezek legalizálásának szükségességét. Ideológiailag helytelen példa.
Nézzünk négy homoszexuálist a, b, c, d.
prioritások a: bcd
prioritások a b:cad számára
prioritások c: abd
mert d nem mindegy, hogyan rangsorolja a maradék hármat.
Nyilatkozat: Ebben a rendszerben nincs fenntartható házassági rendszer.
Hány rendszer van négy személyre? Három. ab cd, ac bd, ad bc. A párok széthullanak, és a folyamat ciklusokban megy végbe.
"Három nemű" rendszerek.
Ez a legfontosabb kérdés, amely a matematika egész területét nyitja meg. Ezt moszkvai kollégám, Vlagyimir Ivanovics Danilov tette. A „házasságot” vodkaivásnak tekintette, és a szerepek a következők voltak: „aki tölt”, „aki pirítóst mond” és „aki felvágja a kolbászt”. Olyan helyzetben, amikor minden szerepnek 4 vagy több képviselője van, lehetetlen nyers erővel megoldani. A fenntartható rendszer kérdése nyitott.
Shapley vektor
A nyaralófaluban úgy döntöttek, hogy aszfaltozzák az utat. Be kell jelentkezni. Hogyan?
Shapley megoldást javasolt erre a problémára 1953-ban. Tételezzünk fel egy konfliktushelyzetet egy N={1,2…n} embercsoporttal. A költségeket/haszonokat meg kell osztani. Tegyük fel, hogy az emberek közösen csináltak valami hasznosat, eladták, és hogyan osztják fel a nyereséget?
Shapley azt javasolta, hogy az osztás során azt kell figyelembe venni, hogy ezeknek az embereknek bizonyos részhalmazai mennyit kaphatnak. Mennyi pénzt kereshet mind a 2N nem üres részhalmaz? És ezen információk alapján Shapley univerzális képletet írt.
Példa. Egy szólista, gitáros és dobos játszik egy moszkvai földalatti járatban. Ők hárman 1000 rubelt keresnek óránként. Hogyan kell felosztani? Esetleg egyformán.
V(1,2,3)=1000
Tegyünk úgy, mintha
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
A tisztességes felosztást addig nem lehet meghatározni, amíg nem tudjuk, milyen haszon vár egy adott vállalatra, ha az elszakad és önállóan cselekszik. És amikor meghatároztuk a számokat (beállítjuk a kooperatív játékot jellemző formába).
Szuperadditivitás az, amikor együtt többet keresnek, mint külön-külön, amikor jövedelmezőbb az egyesülés, de nem világos, hogyan kell felosztani a nyereményt. Erről sok példány tört.
Van egy játék. Három üzletember egyszerre talált egy 1 millió dollár értékű betétet. Ha hárman egyetértenek, akkor egymillióan lesznek. Bármelyik pár ölhet (eltávolíthatja az ügyből), és megszerezheti magának az egész milliót. És senki nem tud semmit egyedül csinálni. Ez egy ijesztő kooperatív játék, megoldás nélkül. Mindig lesz két ember, aki ki tudja küszöbölni a harmadikat... A kooperatív játékelmélet egy példával kezdődik, aminek nincs megoldása.
Olyan megoldást akarunk, hogy egyetlen koalíció sem akarja akadályozni a közös megoldást. Az összes nem blokkolható részhalmaz a kernel. Előfordul, hogy a mag üres. De ha nem is üres, hogyan kell felosztani?
Shapley ezt a felosztást javasolja. Dobj fel egy érmét n-nel! élek. Ebben a sorrendben írjuk ki az összes játékost. Mondjuk az első dobos. Bejön és elveszi a 100-at. Aztán bejön a „második”, mondjuk a szólista. (A dobossal együtt 450-et kereshetnek, a dobos már 100-at vett el) A szólista 350-et vesz el. A gitáros belép (együtt 1000, -450), 550-et vesz el. Gyakran az utolsó nyer. (Szupermodularitás)
Ha minden rendelésnél kiírjuk:
GSB - (C győzelem) - (D győzelem) - (B győzelem)
SGB - (C győzelem) - (D győzelem) - (B győzelem)
SBG - (C győzelem) - (D győzelem) - (B győzelem)
BSG - (C győzelem) - (D győzelem) - (B győzelem)
BGS - (C erősítés) - (D erősítés) - (B erősítés)
GBS - (C győzelem) - (D győzelem) - (B győzelem)
És minden oszlophoz hozzáadjuk és elosztjuk 6-tal - az összes rendelés átlagát - ez egy Shapley vektor.
Shapley bebizonyította a tételt (hozzávetőlegesen): A játékoknak van egy osztálya (szupermoduláris), amelyben a következő személy, aki csatlakozik egy nagy csapathoz, nagyobb nyereményt hoz annak. A kernel mindig nem üres, és pontok konvex kombinációja (esetünkben 6 pont). A Shapley-vektor a mag közepén található. Mindig fel lehet ajánlani megoldásként, senki nem lesz ellene.
1973-ban bebizonyosodott, hogy a nyaralók problémája szupermoduláris.
Mind a n ember osztozik az első házikóhoz vezető úton. A másodikig - n-1 ember. Stb.
A repülőtéren van kifutópálya. A különböző cégeknek eltérő hosszúságra van szükségük. Ugyanez a probléma merül fel.
Úgy gondolom, hogy a Nobel-díjat odaítélők ezt az érdemet tartották szem előtt, nem csak a margó feladatát.
Köszönöm!
Még
- „Matek – Egyszerű” csatorna:
- Csatorna „Savvateev határok nélkül”: edusex.ru, brainsex.ru, studfuck.ru
- Nyilvános „A matematika egyszerű”:
- Nyilvános „matematikus vicc”:
- Weboldal, ott minden előadás +100 óra és még sok más: savvateev.xyz
Forrás: will.com