En 2012, la Nobelpremio pri Ekonomiko estis aljuĝita al Lloyd Shapley kaj Alvin Roth. "Por la teorio de stabila distribuo kaj la praktiko de organizado de merkatoj." Aleksey Savvateev en 2012 provis simple kaj klare klarigi la esencon de la meritoj de matematikistoj. Mi prezentas al via atento resumon .
Hodiaŭ okazos teoria prelego. Pri eksperimentoj , precipe kun donaco, mi ne rakontos.
Kiam oni anoncis tion ricevis la Nobel-premion, estis norma demando: “Kiel!? Ĉu li ankoraŭ vivas!?!?” Lia plej fama rezulto estis akirita en 1953.
Formale, la bonuso estis donita por io alia. Por lia 1962 artikolo pri la "geedzeca stabilecteoremo": "Kolegia Akcepto kaj la Stabileco de Geedziĝo."
Pri daŭrigebla geedziĝo
Egaleco (korespondado) - la tasko trovi korespondadon.
Estas certa izolita vilaĝo. Estas "m" junaj viroj kaj "w" knabinoj. Ni devas edzigi ilin unu al la alia. (Ne nepre la sama nombro, eble finfine iu restos sola.)
Kiajn supozojn oni devas fari en la modelo? Ke ne estas facile reedziĝi hazarde. Certa paŝo estas farita al libera elekto. Ni diru, ke ekzistas saĝa aksakal, kiu volas reedziĝi, por ke post sia morto eksedziĝoj ne komenciĝu. (Ezedziĝo estas situacio, kiam edzo volas trian virinon kiel edzinon pli ol sian edzinon.)
Ĉi tiu teoremo estas en la spirito de moderna ekonomiko. Ŝi estas escepte malhoma. Ekonomio estis tradicie malhoma. En ekonomiko, homo estas anstataŭigita per maŝino por maksimumigi profitojn. Kion mi diros al vi estas absolute frenezaj aferoj el morala vidpunkto. Ne prenu ĝin al koro.
Ekonomiistoj rigardas geedzecon tiel.
m1, m2,... mk - viroj.
w1, w2,... wL - virinoj.
Viro estas identigita kun kiel li "ordigas" knabinojn. Ekzistas ankaŭ "nulnivelo", sub kiu virinoj tute ne povas esti ofertitaj kiel edzinoj, eĉ se ne ekzistas aliaj.
Ĉio okazas ambaŭdirekte, same por knabinoj.
La komencaj datumoj estas arbitraj. La nura supozo/limigo estas, ke ni ne ŝanĝas niajn preferojn.
Teoremo: Sendepende de la distribuo kaj la nivelo de nulo, ĉiam ekzistas maniero establi unu-al-unu korespondadon inter iuj viroj kaj kelkaj virinoj tiel ke ĝi estu fortika al ĉiuj specoj de disiĝoj (ne nur eksedziĝoj).
Kiuj minacoj povus esti?
Estas paro (m,w) kiu ne estas edziĝinta. Sed por w la nuna edzo estas pli malbona ol m, kaj por m la nuna edzino estas pli malbona ol w. Ĉi tio estas nedaŭrigebla situacio.
Ankaŭ ekzistas la eblo, ke iu estis edziĝinta al iu, kiu estas "sub nulo"; en ĉi tiu situacio, la geedziĝo ankaŭ disfalos.
Se virino estas edziĝinta, sed ŝi preferas fraŭlon, por kiu ŝi estas super nulo.
Se du homoj estas ambaŭ fraŭlaj, kaj ambaŭ estas "super nulo" unu por la alia.
Oni argumentas, ke por iuj komencaj datumoj tia edzeca sistemo ekzistas, imuna al ĉiuj specoj de minacoj. Due, la algoritmo por trovi tian ekvilibron estas tre simpla. Ni komparu kun M*N.
Tiu modelo estis ĝeneraligita kaj vastigita al "poligamio" kaj aplikita en multaj lokoj.
Gale-Shapley proceduro
Se ĉiuj viroj kaj ĉiuj virinoj sekvas la "preskribojn", la rezulta geedziĝsistemo estos daŭrigebla.
Preskriboj.
Ni prenas kelkajn tagojn laŭbezone. Ni dividas ĉiun tagon en du partojn (mateno kaj vespero).
En la unua mateno, ĉiu viro iras al sia plej bona virino kaj frapas sur la fenestro, petante al ŝi geedziĝi kun li.
Vespere de la sama tago, la vico turnas sin al la virinoj.Kion povas malkovri virino? Ke sub ŝia fenestro estis homamaso, aŭ unu aŭ neniu viroj. Tiuj, kiuj hodiaŭ ne havas iun ajn, preterlasas sian vicon kaj atendu. La ceteraj, kiuj havas almenaŭ unu, kontrolas la virojn, kiuj venas por vidi, ke ili estas "super la nulnivelo". Havi almenaŭ unu. Se vi estas tute malbonŝanca kaj ĉio estas sub nulo, tiam ĉiuj estu senditaj. La virino elektas la plej grandan el tiuj kiuj venis, rakontas al li atendi, kaj sendas la ceterajn.
Antaŭ la dua tago, la situacio estas jena: iuj virinoj havas unu viron, iuj havas neniun.
En la dua tago, ĉiuj "senpagaj" (senditaj) viroj devas iri al la dua prioritata virino. Se ne ekzistas tia persono, tiam la viro estas deklarita fraŭla. Tiuj viroj, kiuj jam sidas kun virinoj, ankoraŭ nenion faras.
Vespere, la virinoj rigardas la situacion. Se al iu, kiu jam sidis, aliĝis pli alta prioritato, tiam la pli malalta prioritato estas forsendita. Se tiuj, kiuj venas, estas pli malaltaj ol tio, kio jam disponeblas, ĉiuj estas forsenditaj. Virinoj elektas la maksimuman elementon ĉiufoje.
Ni ripetas.
Kiel rezulto, ĉiu viro ekzamenis la tutan liston de siaj virinoj kaj estis aŭ lasita sola aŭ engaĝita kun iu virino. Tiam ni edzinigos ĉiujn.
Ĉu eblas fari ĉi tiun tutan procezon, sed virinoj kuri al viroj? La proceduro estas simetria, sed la solvo povas esti malsama. Sed la demando estas, kiu estas pli bona de ĉi tio?
Teoremo. Ni konsideru ne nur ĉi tiujn du simetriajn solvojn, sed la aron de ĉiuj stabilaj geedzecaj sistemoj. La originala proponita mekanismo (viroj kuras kaj virinoj akceptas/rifuzas) rezultigas geedziĝsistemon kiu estas pli bona por iu viro ol iu alia kaj pli malbona ol iu alia por iu virino.
Samseksaj geedzecoj
Konsideru la situacion kun "samseksa edz(in)eco". Ni konsideru matematikan rezulton, kiu dubas pri la neceso leĝigi ilin. Ekzemplo ideologie malĝusta.
Konsideru kvar samseksemulojn a, b, c, d.
prioritatoj por a: bcd
prioritatoj por b:cad
prioritatoj por c: abd
ĉar d ne gravas kiel li vicigas la ceterajn tri.
Deklaro: Ne ekzistas daŭrigebla geedziĝa sistemo en ĉi tiu sistemo.
Kiom da sistemoj estas por kvar homoj? Tri. ab cd, ac bd, ad bc. La paroj disfalos kaj la procezo iros en cikloj.
"Tri-genraj" sistemoj.
Ĉi tiu estas la plej grava demando, kiu malfermas tutan kampon de matematiko. Tion faris mia kolego en Moskvo, Vladimir Ivanoviĉ Danilov. Li rigardis "geedziĝon" kiel trinki vodkon kaj la roloj estis jenaj: "tiu, kiu verŝas", "tiu, kiu parolas la rostpanon", kaj "tiu, kiu tranĉas la kolbason." En situacio kie estas 4 aŭ pli da reprezentantoj de ĉiu rolo, estas neeble solvi per kruda forto. La demando pri daŭrigebla sistemo estas malfermita.
Shapley-vektoro
En la dometa vilaĝo oni decidis asfalti la vojon. Necesas enigi. Kiel?
Shapley proponis solvon al tiu problemo en 1953. Ni supozu situacion de konflikto kun grupo de homoj N={1,2...n}. Kostoj/profitoj devas esti dividitaj. Supozu ke homoj kune faris ion utilan, vendis ĝin kaj kiel dividi la profiton?
Shapley sugestis ke dum dividado, ni devus esti gviditaj de kiom certaj subaroj de ĉi tiuj homoj povus ricevi. Kiom da mono povus gajni ĉiuj 2N ne-malplenaj subaroj? Kaj surbaze de ĉi tiu informo, Shapley skribis universalan formulon.
Ekzemplo. Solisto, gitaristo kaj tamburisto ludas en subtera pasejo en Moskvo. La tri el ili gajnas 1000 rublojn hore. Kiel dividi ĝin? Eble egale.
V(1,2,3)=1000
Ni ŝajnigu tion
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Justa divido ne povas esti determinita ĝis ni scias, kiaj gajnoj atendas difinitan kompanion, se ĝi rompas kaj agas memstare. Kaj kiam ni determinis la nombrojn (metu la kooperan ludon en karakteriza formo).
Superadditiveco estas kiam kune ili gajnas pli ol aparte, kiam estas pli profite kuniĝi, sed ne estas klare kiel dividi la gajnojn. Multaj kopioj estis rompitaj pri tio.
Estas ludo. Tri komercistoj samtempe trovis deponejon kun valoro de 1 miliono USD. Se ili tri konsentas, tiam estas miliono da ili. Ĉiu paro povas mortigi (forigi el la kazo) kaj akiri la tutan milionon por si. Kaj neniu povas fari ion ajn sola. Ĉi tio estas timiga kunlabora ludo sen solvo. Ĉiam estos du homoj, kiuj povas forigi la trian... Koopera ludoteorio komenciĝas per ekzemplo, kiu ne havas solvon.
Ni volas tian solvon, ke neniu koalicio volos bari la komunan solvon. La aro de ĉiuj dividoj, kiuj ne povas esti blokitaj, estas la kerno. Okazas, ke la kerno estas malplena. Sed eĉ se ĝi ne estas malplena, kiel dividi?
Shapley sugestas dividi ĉi tiun manieron. Ĵetu moneron per n! randoj. Ni skribas ĉiujn ludantojn en ĉi tiu ordo. Ni diru la unua tamburisto. Li eniras kaj prenas sian 100. Tiam la "dua" envenas, ni diru la solisto. (Kune kun la tamburisto ili povas gajni 450, la tamburisto jam prenis 100) La solisto prenas 350. La gitaristo eniras (kune 1000, -450), prenas 550. La lasta en sufiĉe ofte venkas. (Supermoduleco)
Se ni skribu por ĉiuj mendoj:
GSB - (venko C) - (venko D) - (venko B)
SGB - (venko C) - (venko D) - (venko B)
SBG - (venko C) - (venko D) - (venko B)
BSG - (venko C) - (venko D) - (venko B)
BGS - (gajno C) - (gajno D) - (gajno B)
GBS - (venko C) - (venko D) - (venko B)
Kaj por ĉiu kolumno ni aldonas kaj dividas per 6 - averaĝe super ĉiuj ordoj - ĉi tio estas Shapley-vektoro.
Shapley pruvis la teoremon (proksimume): Estas klaso de ludoj (supermodulaj), en kiuj la venonta persono aliĝi al granda teamo alportas pli grandan venkon al ĝi. La kerno estas ĉiam ne-malplena kaj estas konveksa kombinaĵo de punktoj (en nia kazo, 6 poentoj). La Shapley-vektoro situas en la centro mem de la nukleo. Ĝi ĉiam povas esti proponita kiel solvo, neniu estos kontraŭ ĝi.
En 1973, estis pruvite, ke la problemo kun dometoj estas supermodula.
Ĉiuj n homoj dividas la vojon al la unua dometo. Ĝis la dua - n-1 homoj. Ktp.
La flughaveno havas startlenon. Malsamaj kompanioj bezonas malsamajn longojn. La sama problemo ekestas.
Mi pensas, ke tiuj, kiuj aljuĝis la Nobel-premion, havis en menso ĉi tiun meriton, kaj ne nur la taskon de marĝeno.
Dankon!
Tamen
- Kanalo "Matematiko - Simpla":
- Kanalo "Savveteev sen limoj": edusex.ru, brainsex.ru, studfuck.ru
- Publika "Matematiko estas simpla":
- Publika "Matematikistoj ŝercas":
- Retejo, ĉiuj prelegoj tie +100 lecionoj kaj pli: savvateev.xyz
fonto: www.habr.com