2012 gouf den Nobelpräis an der Economie un de Lloyd Shapley an den Alvin Roth ausgezeechent. "Fir d'Theorie vun der stabiler Verdeelung an der Praxis vun der Organisatioun Mäert." Aleksey Savvateev 2012 probéiert einfach a kloer d'Essenz vun de Merite vun Mathematiker ze erklären. Ech presentéieren Iech e Resumé .
Haut gëtt et en theoretesch Virtrag. Iwwer Experimenter , besonnesch mat Spenden, wäert ech net soen.
Wéi et ugekënnegt gouf, datt den Nobelpräis krut, gouf et eng Standardfro: "Wéi!? Ass hien nach lieweg!?!?" Säi bekanntste Resultat gouf 1953 kritt.
Formell gouf de Bonus fir eppes anescht ginn. Fir säi Pabeier 1962 iwwer den "Bestietnesstabilitéitstheorem": "College Admission and the Stability of Marriage."
Iwwer nohalteg Bestietnes
bruecht (passend) - d'Aufgab fir eng Korrespondenz ze fannen.
Et gëtt eng gewëssen isoléiert Duerf. Et gi "m" jonk Männer a "w" Meedercher. Mir mussen se matenee bestueden. (Net onbedéngt déiselwecht Zuel, vläicht gëtt um Enn iergendeen eleng gelooss.)
Wéi eng Viraussetzunge mussen am Modell gemaach ginn? Datt et net einfach ass zoufälleg erëm ze bestueden. E gewësse Schrëtt gëtt a Richtung fräie Choix gemaach. Loosst eis soen datt et e weise Aksakal ass, dee wëll erëm bestueden, sou datt no sengem Doud Scheedungen net ufänken. (Scheedung ass eng Situatioun wann e Mann eng Drëtt Partei Fra wéi seng Fra méi wéi seng Fra wëll.)
Dësen Theorem ass am Geescht vun der moderner Economie. Si ass aussergewéinlech onmënschlech. D'Wirtschaft war traditionell onmënschlech. An der Economie gëtt de Mënsch duerch eng Maschinn ersat fir de Gewënn ze maximéieren. Wat ech Iech soen ass absolut verréckt Saachen aus enger moralescher Siicht. Huelt et net zu Häerz.
Economisten kucken op d'Bestietnes dës Manéier.
m1, m2,... mk - Männer.
w1, w2,... wL - Fraen.
E Mann gëtt identifizéiert mat wéi hien Meedercher "bestallt". Et gëtt och e "Nullniveau", ënnert deem Fraen iwwerhaapt net als Fra ugebuede kënne ginn, och wa keng aner sinn.
Alles geschitt a béid Richtungen, d'selwecht fir Meedercher.
Déi initial Donnéeën sinn arbiträr. Déi eenzeg Viraussetzung / Limitatioun ass datt mir eis Virléiften net änneren.
Theorem: Onofhängeg vun der Verdeelung an dem Niveau vun Null, et gëtt ëmmer e Wee fir eng een-zu-een Korrespondenz tëscht e puer Männer a e puer Fraen ze etabléieren, sou datt et robust ass fir all Zorte vu Spaltungen (net nëmme Scheedungen).
Wéi eng Gefore kënnen et sinn?
Et gëtt eng Koppel (m,w) déi net bestuet ass. Awer fir w ass den aktuelle Mann méi schlëmm wéi m, a fir m ass déi aktuell Fra méi schlëmm wéi w. Dëst ass eng onhaltbar Situatioun.
Et gëtt och d'Optioun datt een mat engem bestuet war deen "ënner Null" ass; an dëser Situatioun wäert d'Bestietnes och auserneen falen.
Wann eng Fra bestuet ass, awer si léiwer en onbestuete Mann, fir deen si iwwer Null ass.
Wann zwee Leit sinn allebéid bestuet, a béid sinn "iwwer Null" fir all aner.
Et gëtt argumentéiert datt fir all initial Donnéeën esou e Bestietnes System existéiert, resistent géint all Zorte vu Bedrohungen. Zweetens, den Algorithmus fir sou e Gläichgewiicht ze fannen ass ganz einfach. Loosst eis mat M*N vergläichen.
Dëse Modell gouf generaliséiert an op "Polygamie" ausgebaut an a ville Beräicher applizéiert.
Gale-Shapley Prozedur
Wann all Männer an all Fraen d"Virschrëfte verfollegen,"Déi doraus resultéierend Bestietnes System wäert nohalteg ginn.
Rezepter.
Mir huelen e puer Deeg wéi néideg. Mir trennen all Dag an zwee Deeler (moies an owes).
Um éischte Moien geet all Mann bei seng bescht Fra an klappt op d'Fënster, a freet hatt mat him ze bestueden.
Am selwechten Dag owes geet den Tour un d'Fraen.Wat kann eng Fra entdecken? Datt et eng Mass ënnert hirer Fënster war, entweder een oder keng Männer. Déi, déi haut keen hunn, sprangen hiren Tour a waarden. De Rescht, déi op d'mannst een hunn, kontrolléiert d'Männer déi kommen ze gesinn datt se "iwwer dem Niveau Null" sinn. Op d'mannst een ze hunn. Wann Dir komplett Pech hutt an alles ënner Null ass, da soll jiddereen geschéckt ginn. D'Fra wielt de gréisste vun deenen, déi komm sinn, seet him ze waarden, a schéckt de Rescht.
Virum zweeten Dag ass d'Situatioun esou: Verschidde Fraen hunn ee Mann, anerer hunn keen.
Um zweeten Dag, all "gratis" (geschéckt) Männer mussen op déi zweet Prioritéit Fra goen. Wann et keng sou Persoun ass, da gëtt de Mann als eenzeg deklaréiert. Déi Männer, déi scho mat Fraen sëtzen, maachen nach näischt.
Owes kucken d'Fraen d'Situatioun. Wann een, dee scho souz, eng méi héich Prioritéit ugeschloss huet, da gëtt déi ënnescht Prioritéit fortgeschéckt. Wann déi, déi kommen, méi niddereg si wéi dat, wat scho verfügbar ass, gëtt jidderee fortgeschéckt. Fraen wielen déi maximal Element all Kéier.
Mir widderhuelen.
Als Resultat ass all Mann duerch d'ganz Lëscht vu senge Fraen gaang a gouf entweder eleng gelooss oder mat enger Fra engagéiert. Da wäerte mir jidderee bestueden.
Ass et méiglech dëse ganze Prozess ze lafen, awer fir Fraen fir Männer ze lafen? D'Prozedur ass symmetresch, awer d'Léisung kann anescht sinn. Awer d'Fro ass, wien ass besser vun dësem?
Theorem. Loosst eis net nëmmen dës zwou symmetresch Léisungen betruechten, awer de Set vun all stabile Bestietnessystemer. D'Original proposéiert Mechanismus (Männer lafen a Fraen akzeptéieren / refuséieren) Resultater an engem Bestietnes System dass besser ass fir all Mann wéi all aner a méi schlëmm wéi all aner fir all Fra.
Selwecht Geschlecht Bestietnes
Betruecht d'Situatioun mam "selwecht Geschlecht Bestietnes." Loosst eis e mathematescht Resultat betruechten dat Zweifel op d'Noutwennegkeet stellt se ze legaliséieren. En ideologesch falscht Beispill.
Betruecht véier homosexuell a, b, c, d.
Prioritéit fir eng: bcd
Prioritéite fir b:cad
Prioritéit fir c: abd
fir d et egal wéi hien déi aner dräi klasséiert.
Erklärung: Et gëtt keen nohaltege Bestietnes System an dësem System.
Wéi vill Systemer ginn et fir véier Leit? Dräi. ab cd, ac bd, ad bc. D'Koppelen falen auserneen an de Prozess wäert an Zyklen goen.
"Dräi-Geschlecht" Systemer.
Dëst ass déi wichtegst Fro, déi e ganzt Gebitt vun der Mathematik opmaacht. Dëst gouf vu mengem Kolleg zu Moskau gemaach, Vladimir Ivanovich Danilov. Hien huet "Bestietnes" als Wodka gedronk an d'Rolle waren wéi follegt: "deen deen schëtt", "deen deen den Toast schwätzt", an "deen deen d'Wurst schneit." An enger Situatioun wou et 4 oder méi Vertrieder vun all Roll sinn, ass et onméiglech duerch brute Kraaft ze léisen. D'Fro vun engem nohaltege System ass eng oppe.
Shapley Vektor
Am Gîte rural hu si decidéiert d'Strooss ze asphaltéieren. Muss chip an. Wéi?
De Shapley huet 1953 eng Léisung fir dëse Problem proposéiert. Loosst eis eng Situatioun vu Konflikt mat enger Grupp vu Leit unhuelen N={1,2…n}. Käschten / Virdeeler musse gedeelt ginn. Ugeholl datt d'Leit zesummen eppes nëtzlech gemaach hunn, et verkafen a wéi de Gewënn ze deelen?
De Shapley huet virgeschloen datt wa mir deelen, mir sollte guidéiert ginn duerch wéi vill verschidde Subsets vun dëse Leit kéinte kréien. Wéi vill Sue kéinten all 2N net eidel Subsets verdéngen? A baséiert op dës Informatioun huet Shapley eng universell Formel geschriwwen.
E Beispill. E Solist, Gittarist an Batteur spillen an engem ënnerierdesche Passage zu Moskau. Déi dräi vun hinnen verdéngen 1000 Rubelen pro Stonn. Wéi et ze deelen? Eventuell gläich.
V(1,2,3)=1000
Loosst eis dat maachen
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Eng fair Divisioun kann net festgeluecht ginn, bis mir wëssen, wat Gewënn op eng bestëmmte Firma waarden, wann se ofbriechen an eleng handelt. A wann mir d'Zuelen bestëmmt (setze d'Kooperativ Spill an charakteristesch Form).
Superadditivitéit ass wann se zesummen méi verdéngen wéi getrennt, wann et méi rentabel ass ze vereenegen, awer et ass net kloer wéi de Gewënn opgedeelt gëtt. Vill Exemplare sinn iwwer dëst gebrach ginn.
Et gëtt e Spill. Dräi Geschäftsleit hunn gläichzäiteg en Depot am Wäert vun $ 1 Millioun fonnt. Wann déi dräi averstane sinn, da sinn et eng Millioun vun hinnen. All Koppel kann ëmbréngen (aus dem Fall ewechhuelen) an déi ganz Millioun fir sech selwer kréien. A keen kann eppes eleng maachen. Dëst ass e grujeleg Co-op Spill ouni Léisung. Et wäerten ëmmer zwee Leit sinn, déi déi drëtt eliminéiere kënnen ... Kooperativ Spilltheorie fänkt mat engem Beispill un dat keng Léisung huet.
Mir wëllen esou eng Léisung, datt keng Koalitioun déi gemeinsam Léisung wëll blockéieren. De Set vun all Divisiounen déi net blockéiert kënne ginn ass de Kernel. Et geschitt, datt de Kär eidel ass. Awer och wann et net eidel ass, wéi deelen?
Shapley proposéiert dës Manéier opzedeelen. Gitt eng Mënz mat n! Kanten. Mir schreiwen all d'Spiller an dëser Reiefolleg. Loosst eis den éischten Drummer soen. Hie kënnt eran an hëlt seng 100. Da kënnt de "zweet", loosst eis soen de Solist. (Zesumme mam Batteur kënne si 450 verdéngen, de Batteur huet der schonn 100 geholl) De Solist hëlt 350. De Gittarist geet eran (zesummen 1000, -450), hëlt 550. Dee leschten an zimlech oft gewënnt. (Supermodularitéit)
Wa mir fir all Bestellung schreiwen:
GSB - (win C) - (win D) - (win B)
SGB - (win C) - (win D) - (win B)
SBG - (win C) - (win D) - (win B)
BSG - (win C) - (win D) - (win B)
BGS - (gewinn C) - (gewinn D) - (gewinn B)
GBS - (win C) - (win D) - (win B)
A fir all Kolonn addéiere mer a deelen mat 6 - Duerchschnëtt iwwer all Bestellungen - Dëst ass e Shapley Vektor.
De Shapley huet den Theorem bewisen (ongeféier): Et gëtt eng Klass vu Spiller (supermodular), an där déi nächst Persoun, déi mat enger grousser Equipe bäitrieden, e méi grousse Gewënn bréngt. De Kär ass ëmmer net eidel an ass eng konvex Kombinatioun vu Punkten (an eisem Fall, 6 Punkten). De Shapley-Vektor läit am Zentrum vum Kär. Et kann ëmmer als Léisung ugebuede ginn, keen wäert dergéint sinn.
1973 gouf bewisen datt de Problem mat Hütten supermodulär ass.
All n Leit deelen der Strooss op déi éischt Gîte rural. Bis zu der zweeter - n-1 Leit. etc.
De Fluchhafen huet eng Piste. Verschidde Firme brauche verschidde Längt. Dee selwechte Problem entsteet.
Ech mengen, datt déi, déi den Nobelpräis ausgezeechent hunn, dëse Verdéngscht am Kapp haten, an net nëmmen d'Aufgab vum Margin.
Merci!
Awer
- Kanal "Math - Simple":
- Kanal "Savvateev ouni Grenzen": edusex.ru, brainsex.ru, studfuck.ru
- Ëffentlech "Mathematik ass einfach":
- Ëffentlech "Mathematiker Witz":
- Websäit, all Virliesungen do +100 Lektioune a méi: savvateev.xyz
Source: will.com