Në vitin 2012, Çmimi Nobel në Ekonomi iu dha Lloyd Shapley dhe Alvin Roth. “Për teorinë e shpërndarjes së qëndrueshme dhe praktikën e organizimit të tregjeve”. Aleksey Savvateev në 2012 u përpoq të shpjegonte thjesht dhe qartë thelbin e meritave të matematikanëve. Unë paraqes në vëmendjen tuaj një përmbledhje .
Sot do të ketë një leksion teorik. Rreth eksperimenteve , në veçanti me donacion, nuk do ta tregoj.
Kur u njoftua se mori çmimin Nobel, kishte një pyetje standarde: “Si!? A është akoma gjallë?!?!” Rezultati i tij më i famshëm u mor në 1953.
Formalisht, bonusi u dha për diçka tjetër. Për letrën e tij të vitit 1962 mbi "teoremën e stabilitetit të martesës": "Pranimi në kolegj dhe stabiliteti i martesës".
Rreth martesës së qëndrueshme
Matching (përputhja) - detyra për të gjetur një korrespondencë.
Ka një fshat të caktuar të izoluar. Ka “m” të rinj dhe “w” vajza. Duhet t'i martojmë me njëri-tjetrin. (Jo domosdoshmërisht i njëjti numër, ndoshta në fund dikush do të mbetet vetëm.)
Cilat supozime duhet të bëhen në model? Se nuk është e lehtë të rimartohesh rastësisht. Një hap i caktuar po bëhet drejt zgjedhjes së lirë. Le të themi se ekziston një aksakal i mençur që dëshiron të rimartohet në mënyrë që pas vdekjes së tij të mos fillojnë divorcet. (Divorci është një situatë kur një burrë dëshiron një grua të palës së tretë si gruan e tij më shumë se gruan e tij.)
Kjo teoremë është në frymën e ekonomisë moderne. Ajo është jashtëzakonisht çnjerëzore. Ekonomia ka qenë tradicionalisht çnjerëzore. Në ekonomi, njeriu zëvendësohet nga një makinë për të maksimizuar fitimet. Ajo që do t'ju them janë absolutisht gjëra të çmendura nga pikëpamja morale. Mos e merrni për zemër.
Ekonomistët e shohin martesën në këtë mënyrë.
m1, m2,… mk - burra.
w1, w2,... wL - gra.
Një burrë identifikohet me mënyrën se si ai "urdhëron" vajzat. Ekziston edhe një “nivel zero”, nën të cilin gratë nuk mund të ofrohen fare për bashkëshorte, edhe nëse nuk ka të tjera.
Gjithçka ndodh në të dy drejtimet, e njëjta gjë për vajzat.
Të dhënat fillestare janë arbitrare. I vetmi supozim/kufizim është se ne nuk i ndryshojmë preferencat tona.
Teorema: Pavarësisht nga shpërndarja dhe niveli i zeros, ekziston gjithmonë një mënyrë për të krijuar një korrespondencë një-për-një midis disa burrave dhe disa grave, në mënyrë që të jetë e qëndrueshme për të gjitha llojet e ndarjeve (jo vetëm divorcet).
Çfarë kërcënimesh mund të ketë?
Ka një çift (m,w) që nuk është i martuar. Por për w burri aktual është më i keq se m, dhe për m gruaja aktuale është më e keqe se w. Kjo është një situatë e paqëndrueshme.
Ekziston edhe opsioni që dikush të jetë martuar me dikë që është "nën zero"; në këtë situatë, martesa gjithashtu do të shpërbëhet.
Nëse një grua është e martuar, por preferon një burrë të pamartuar, për të cilin është mbi zero.
Nëse dy persona janë të dy të pamartuar, dhe të dy janë "mbi zero" për njëri-tjetrin.
Argumentohet se për çdo të dhënë fillestare ekziston një sistem i tillë martese, rezistent ndaj të gjitha llojeve të kërcënimeve. Së dyti, algoritmi për gjetjen e një ekuilibri të tillë është shumë i thjeshtë. Le të krahasojmë me M*N.
Ky model u përgjithësua dhe u zgjerua në "poligami" dhe u aplikua në shumë fusha.
Procedura Gale-Shapley
Nëse të gjithë burrat dhe të gjitha gratë ndjekin "recetat", sistemi i martesës që rezulton do të jetë i qëndrueshëm.
Recetat.
Ne marrim disa ditë sipas nevojës. Ne e ndajmë çdo ditë në dy pjesë (mëngjes dhe mbrëmje).
Në mëngjesin e parë, çdo burrë shkon te gruaja e tij më e mirë dhe troket në dritare, duke i kërkuar asaj të martohet me të.
Në mbrëmjen e së njëjtës ditë radha u kthehet grave.Çfarë mund të zbulojë një grua? Se kishte një turmë nën dritaren e saj, ose një ose asnjë burrë. Ata që nuk kanë askënd sot e kalojnë radhën dhe presin. Pjesa tjetër, të cilët kanë të paktën një, kontrollojnë burrat që vijnë për të parë se ata janë "mbi nivelin zero". Të ketë të paktën një. Nëse jeni plotësisht i pafat dhe gjithçka është nën zero, atëherë të gjithë duhet të dërgohen. Gruaja zgjedh personin më të madh nga ata që erdhën, i thotë të presë dhe të tjerët i dërgon.
Para ditës së dytë, situata është kjo: disa gra kanë një burrë, disa nuk kanë asnjë.
Në ditën e dytë, të gjithë burrat "të lirë" (të dërguar) duhet të shkojnë te gruaja e prioritetit të dytë. Nëse nuk ka një person të tillë, atëherë burri shpallet beqar. Ata burra që tashmë janë ulur me gratë nuk po bëjnë asgjë ende.
Në mbrëmje, gratë shikojnë situatën. Nëse dikujt që ishte ulur tashmë i është bashkuar një prioritet më i lartë, atëherë prioriteti më i ulët largohet. Nëse ata që vijnë janë më të ulët se sa është në dispozicion, të gjithë largohen. Femrat zgjedhin çdo herë elementin maksimal.
E përsërisim.
Si rezultat, secili burrë kaloi në të gjithë listën e grave të tij dhe ose mbeti vetëm ose u fejua me ndonjë grua. Atëherë do të martohemi të gjithë.
A është e mundur të drejtohet i gjithë ky proces, por gratë të vrapojnë te burrat? Procedura është simetrike, por zgjidhja mund të jetë e ndryshme. Por pyetja është, kush është më mirë nga kjo?
Teorema. Le të shqyrtojmë jo vetëm këto dy zgjidhje simetrike, por grupin e të gjitha sistemeve të qëndrueshme të martesës. Mekanizmi i propozuar origjinal (burrat vrapojnë dhe gratë pranojnë/refuzojnë) rezulton në një sistem martese që është më i mirë për çdo burrë se çdo tjetër dhe më i keq se çdo tjetër për çdo grua.
Martesat e të njëjtit seks
Merrni parasysh situatën me "martesat e të njëjtit seks". Le të shqyrtojmë një rezultat matematikor që vë në dyshim nevojën e legalizimit të tyre. Një shembull ideologjikisht i pasaktë.
Konsideroni katër homoseksualë a, b, c, d.
prioritetet për një: bcd
prioritetet për b:cad
prioritetet për c: abd
për d nuk ka rëndësi se si i rendit tre të mbeturit.
Deklarata: Nuk ka një sistem të qëndrueshëm martese në këtë sistem.
Sa sisteme ka për katër persona? Tre. ab cd, ac bd, ad bc. Çiftet do ndahen dhe procesi do ecë me cikle.
Sistemet "tre gjinore".
Kjo është pyetja më e rëndësishme që hap një fushë të tërë të matematikës. Këtë e bëri kolegu im në Moskë, Vladimir Ivanovich Danilov. Ai e shihte "martesën" si të pirë vodka dhe rolet ishin si më poshtë: "ai që derdh", "ai që flet dolli" dhe "ai që pret sallamin". Në një situatë ku ka 4 ose më shumë përfaqësues të secilit rol, është e pamundur të zgjidhet me forcë brutale. Çështja e një sistemi të qëndrueshëm është një çështje e hapur.
vektor Shapley
Në fshatin vilë vendosën të asfaltonin rrugën. Duhet të futet. Si?
Shapley propozoi një zgjidhje për këtë problem në 1953. Le të supozojmë një situatë konflikti me një grup njerëzish N={1,2…n}. Kostot/përfitimet duhet të ndahen. Supozoni se njerëzit së bashku bënë diçka të dobishme, e shesin dhe si ta ndajnë fitimin?
Shapley sugjeroi që gjatë ndarjes, ne duhet të udhëhiqemi nga sa nëngrupe të caktuara të këtyre njerëzve mund të merrnin. Sa para mund të fitojnë të gjitha 2N nëngrupet jo boshe? Dhe bazuar në këtë informacion, Shapley shkroi një formulë universale.
Shembull. Një solist, kitarist dhe baterist luajnë në një pasazh nëntokësor në Moskë. Të tre fitojnë 1000 rubla në orë. Si ta ndajmë atë? Mundësisht në mënyrë të barabartë.
V(1,2,3)=1000
Le të pretendojmë se
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Një ndarje e drejtë nuk mund të përcaktohet derisa të dimë se çfarë përfitimesh e presin një kompani të caktuar nëse shkëputet dhe vepron vetë. Dhe kur përcaktuam numrat (vendosim lojën bashkëpunuese në formë karakteristike).
Superaditiviteti është kur së bashku fitojnë më shumë se veçmas, kur është më fitimprurëse të bashkohen, por nuk është e qartë se si të ndahen fitimet. Shumë kopje janë thyer për këtë.
Ka një lojë. Tre biznesmenë gjetën njëkohësisht një depozitë me vlerë 1 milion dollarë. Nëse të tre janë dakord, atëherë janë një milion prej tyre. Çdo çift mund të vrasë (të heqë nga çështja) dhe të marrë të gjithë milionin për vete. Dhe askush nuk mund të bëjë asgjë vetëm. Kjo është një lojë e frikshme bashkëpunimi pa zgjidhje. Gjithmonë do të jenë dy persona që mund të eliminojnë të tretin... Teoria e lojës bashkëpunuese fillon me një shembull që nuk ka zgjidhje.
Ne duam një zgjidhje të tillë që asnjë koalicion nuk do të dojë të bllokojë zgjidhjen e përbashkët. Grupi i të gjitha ndarjeve që nuk mund të bllokohen është kerneli. Ndodh që thelbi është bosh. Por edhe nëse nuk është bosh, si të ndahet?
Shapley sugjeron ndarjen në këtë mënyrë. Hidhe një monedhë me n! skajet. Ne i shkruajmë të gjithë lojtarët në këtë renditje. Le të themi bateristi i parë. Ai hyn dhe merr 100. Pastaj hyn “i dyti”, le të themi solisti. (Së bashku me bateristin mund të fitojnë 450, bateristi ka marrë tashmë 100) Solisti merr 350. Kitaristi hyn (së bashku 1000, -450), merr 550. I fundit në shumë shpesh fiton. (Supermodulariteti)
Nëse shkruajmë për të gjitha porositë:
GSB - (fitore C) - (fitore D) - (fitore B)
SGB - (fitore C) - (fitore D) - (fitore B)
SBG - (fitore C) - (fitore D) - (fitore B)
BSG - (fitore C) - (fitore D) - (fitore B)
BGS - (fitimi C) - (fitimi D) - (fitimi B)
GBS - (fitore C) - (fitore D) - (fitore B)
Dhe për secilën kolonë ne shtojmë dhe pjesëtojmë me 6 - mesatarisht mbi të gjitha porositë - ky është një vektor Shapley.
Shapley vërtetoi teoremën (afërsisht): Ekziston një klasë lojërash (supermodulare), në të cilat personi tjetër që do t'i bashkohet një ekipi të madh i sjell një fitore më të madhe. Bërthama është gjithmonë jo bosh dhe është një kombinim konveks pikash (në rastin tonë, 6 pikë). Vektori Shapley shtrihet në qendër të bërthamës. Mund të ofrohet gjithmonë si zgjidhje, askush nuk do të jetë kundër.
Në vitin 1973, u vërtetua se problemi me vilat është supermodular.
Të gjithë njerëzit ndajnë rrugën për në vilë të parë. Deri në të dytin - n-1 persona. etj.
Aeroporti ka një pistë. Kompani të ndryshme kanë nevojë për gjatësi të ndryshme. I njëjti problem lind.
Mendoj se ata që dhanë çmimin Nobel e kishin parasysh këtë meritë dhe jo vetëm detyrën e diferencës.
Ju faleminderit!
Akoma
- Kanali "Matematika - E thjeshtë":
- Kanali "Savvateev pa kufij": eduex.ru, brainsex.ru, studfuck.ru
- Publik "Matematika është e thjeshtë":
- Publik "Shaka e Matematikanëve":
- Faqja e internetit, të gjitha leksionet atje +100 mësime dhe më shumë: savvateev.xyz
Burimi: www.habr.com