ProHoster > Blogs > interneta ziÅas > KÄ ikviens var apprecÄties (viena, divu un trÄ«s dzimumu laulÄ«bas) no matemÄtiskÄ viedokļa un kÄpÄc vÄ«rieÅ”i vienmÄr uzvar
KÄ ikviens var apprecÄties (viena, divu un trÄ«s dzimumu laulÄ«bas) no matemÄtiskÄ viedokļa un kÄpÄc vÄ«rieÅ”i vienmÄr uzvar
2012. gadÄ Nobela prÄmija ekonomikÄ tika pieŔķirta Loidam Å eplijam un Alvinam Rotam. "Par stabilas izplatÄ«Å”anas teoriju un tirgu organizÄÅ”anas praksi." Aleksejs Savvatejevs 2012. gadÄ mÄÄ£inÄja vienkÄrÅ”i un skaidri izskaidrot matemÄtiÄ·u nopelnu bÅ«tÄ«bu. Es piedÄvÄju jÅ«su uzmanÄ«bai kopsavilkumu video lekcijas.
Å odien bÅ«s teorÄtiskÄ lekcija. Par eksperimentiem Ela Rota, jo Ä«paÅ”i ar ziedoÅ”anu, nepateikÅ”u.
Kad tika paziÅots, ka Loids Å eplijs (1923-2016) saÅÄma Nobela prÄmiju, bija standarta jautÄjums: āKÄ!? Vai viÅÅ” vÄl ir dzÄ«vs!?!?" ViÅa slavenÄkais rezultÄts tika iegÅ«ts 1953. gadÄ.
FormÄli prÄmija tika pieŔķirta par kaut ko citu. ViÅa 1962. gada darbam par ālaulÄ«bas stabilitÄtes teorÄmuā: āUzÅemÅ”ana koledÅ¾Ä un laulÄ«bas stabilitÄteā.
Par ilgtspÄjÄ«gu laulÄ«bu
Matching (atbilstība) - uzdevums atrast korespondenci.
Ir zinÄms izolÄts ciems. Ir āmā jauni vÄ«rieÅ”i un āwā meitenes. Mums viÅi ir jÄapprec viens ar otru. (Ne vienmÄr tas pats numurs, varbÅ«t beigÄs kÄds paliks viens.)
KÄdi pieÅÄmumi ir jÄizdara modelÄ«? Ka nav viegli nejauÅ”i atkÄrtoti apprecÄties. Tiek sperts zinÄms solis brÄ«vas izvÄles virzienÄ. PieÅemsim, ka ir kÄds gudrs aksakals, kurÅ” vÄlas apprecÄties vÄlreiz, lai pÄc viÅa nÄves nesÄktos ŔķirÅ”anÄs. (Å Ä·irÅ”anÄs ir situÄcija, kad vÄ«rs vairÄk par sievu vÄlas treÅ”o personu, nevis sievu.)
Å Ä« teorÄma atbilst mÅ«sdienu ekonomikas garam. ViÅa ir ÄrkÄrtÄ«gi necilvÄcÄ«ga. Ekonomika tradicionÄli ir bijusi necilvÄcÄ«ga. EkonomikÄ cilvÄku aizstÄj ar maŔīnu, lai maksimÄli palielinÄtu peļÅu. Tas, ko es jums teikÅ”u, ir pilnÄ«gi trakas lietas no morÄles viedokļa. NeÅemiet to pie sirds.
Ekonomisti uz laulÄ«bu raugÄs Å”Ädi.
m1, m2,ā¦ mk - vÄ«rieÅ”i.
w1, w2,... wL - sievietes.
VÄ«rietis tiek identificÄts ar to, kÄ viÅÅ” āpasÅ«taā meitenes. Ir arÄ« ānulles lÄ«menisā, zem kura sievietes nemaz nevar piedÄvÄt par sievÄm, pat ja citu nav.
Viss notiek abos virzienos, meitenÄm vienÄdi.
SÄkotnÄjie dati ir patvaļīgi. VienÄ«gais pieÅÄmums/ierobežojums ir tÄds, ka mÄs nemainÄm savas preferences.
TeorÄma: NeatkarÄ«gi no sadalÄ«juma un nulles lÄ«meÅa vienmÄr ir veids, kÄ izveidot savstarpÄju saraksti starp dažiem vÄ«rieÅ”iem un dažÄm sievietÄm, lai tÄ bÅ«tu izturÄ«ga pret visu veidu ŔķelÅ”anos (ne tikai laulÄ«bas ŔķirÅ”anu).
KÄdi draudi varÄtu bÅ«t?
Ir pÄris (m,w), kas nav precÄjies. Bet w paÅ”reizÄjais vÄ«rs ir sliktÄks par m, un m paÅ”reizÄjÄ sieva ir sliktÄks par w. TÄ ir neilgtspÄjÄ«ga situÄcija.
PastÄv arÄ« iespÄja, ka kÄds bija precÄjies ar kÄdu, kurÅ” ir āzem nullesā, Å”ajÄ situÄcijÄ arÄ« laulÄ«ba izjuks.
Ja sieviete ir precÄjusies, bet viÅa dod priekÅ”roku neprecÄtam vÄ«rietim, kuram viÅa ir virs nulles.
Ja divi cilvÄki abi ir neprecÄjuÅ”ies un abi viens otram ir āvirs nullesā.
Tiek apgalvots, ka attiecÄ«bÄ uz jebkuriem sÄkotnÄjiem datiem pastÄv Å”Äda laulÄ«bu sistÄma, kas ir izturÄ«ga pret visa veida draudiem. OtrkÄrt, algoritms Å”Äda lÄ«dzsvara atraÅ”anai ir ļoti vienkÄrÅ”s. SalÄ«dzinÄsim ar M*N.
Å is modelis tika vispÄrinÄts un paplaÅ”inÄts lÄ«dz "poligÄmijai" un izmantots daudzÄs jomÄs.
Geila-Šeplija procedūra
Ja visi vÄ«rieÅ”i un visas sievietes ievÄros āreceptesā, laulÄ«bas sistÄma bÅ«s ilgtspÄjÄ«ga.
Receptes.
MÄs aizÅemam dažas dienas pÄc vajadzÄ«bas. Katru dienu sadalÄm divÄs daļÄs (no rÄ«ta un vakarÄ).
PirmajÄ rÄ«tÄ katrs vÄ«rietis dodas pie savas labÄkÄs sievietes un klauvÄ pie loga, lÅ«dzot viÅu apprecÄties.
TÄs paÅ”as dienas vakarÄ kÄrta pievÄrÅ”as sievietÄm.Ko sieviete var atklÄt? Ka zem viÅas loga bija pÅ«lis, vai nu viens, vai neviens vÄ«rietis. Tie, kuriem Å”odien neviena nav, izlaiž savu kÄrtu un gaida. PÄrÄjie, kuriem ir vismaz viens, pÄrbauda vÄ«rieÅ”us, kuri ierodas, lai redzÄtu, vai viÅi ir āvirs nulles lÄ«meÅaā. Lai bÅ«tu vismaz viens. Ja galÄ«gi nepaveicas un viss ir zem nulles, tad jÄsÅ«ta visi. Sieviete izvÄlas lielÄko no atnÄkuÅ”ajiem, liek pagaidÄ«t, pÄrÄjos nosÅ«ta.
Pirms otrÄs dienas situÄcija ir Å”Äda: dažÄm sievietÄm ir viens vÄ«rietis, dažÄm nav.
OtrajÄ dienÄ visiem ābrÄ«vajiemā (nosÅ«tÄ«tajiem) vÄ«rieÅ”iem jÄdodas pie otrÄs prioritÄtes sievietes. Ja tÄdas nav, tad vÄ«rieti pasludina neprecÄtu. Tie vÄ«rieÅ”i, kas jau sÄž ar sievietÄm, vÄl neko nedara.
VakarÄ sievietes aplÅ«ko situÄciju. Ja kÄdam, kurÅ” jau sÄdÄja, pievienojÄs augstÄka prioritÄte, tad zemÄkÄ prioritÄte tiek nosÅ«tÄ«ta. Ja atnÄkuÅ”ie ir zemÄki par to, kas jau ir pieejams, visi tiek izsÅ«tÄ«ti. Sievietes katru reizi izvÄlas maksimÄlo elementu.
MÄs atkÄrtojam.
RezultÄtÄ katrs vÄ«rietis izpÄtÄ«ja visu savu sievieÅ”u sarakstu un vai nu palika viens, vai arÄ« saderinÄjÄs ar kÄdu sievieti. Tad mÄs visus apprecÄsim.
Vai ir iespÄjams palaist visu Å”o procesu, bet sievietÄm skriet pie vÄ«rieÅ”iem? ProcedÅ«ra ir simetriska, taÄu risinÄjums var bÅ«t atŔķirÄ«gs. Bet jautÄjums ir, kuram no tÄ ir labÄk?
TeorÄma. ApskatÄ«sim ne tikai Å”os divus simetriskos risinÄjumus, bet arÄ« visu stabilo laulÄ«bu sistÄmu kopumu. SÄkotnÄjais ierosinÄtais mehÄnisms (vÄ«rieÅ”i skrien un sievietes pieÅem/atsakÄs) rada laulÄ«bu sistÄmu, kas ir labÄka jebkuram vÄ«rietim un sliktÄka par jebkuru citu sievietei.
Viendzimuma laulības
Apsveriet situÄciju ar āviendzimuma laulÄ«bÄmā. ApskatÄ«sim matemÄtisko rezultÄtu, kas liek apÅ”aubÄ«t nepiecieÅ”amÄ«bu tos legalizÄt. IdeoloÄ£iski nekorekts piemÄrs.
Apsveriet Äetrus homoseksuÄļus a, b, c, d.
prioritÄtes a: bcd
prioritÄtes b:cad
prioritÄtes c: abd
jo d nav svarÄ«gi, kÄ viÅÅ” ierindo atlikuÅ”os trÄ«s.
PaziÅojums, apgalvojums: Å ajÄ sistÄmÄ nav ilgtspÄjÄ«gas laulÄ«bas sistÄmas.
Cik sistÄmu ir Äetriem cilvÄkiem? TrÄ«s. ab cd, ac bd, ad bc. PÄri izjuks un process ritÄs ciklos.
"TrÄ«s dzimumu" sistÄmas.
Å is ir vissvarÄ«gÄkais jautÄjums, kas paver visu matemÄtikas jomu. To izdarÄ«ja mans kolÄÄ£is MaskavÄ Vladimirs IvanoviÄs DaÅilovs. ViÅÅ” uzskatÄ«ja, ka ālaulÄ«baā ir degvÄ«na dzerÅ”ana, un lomas bija Å”Ädas: ātas, kas lejā, ātas, kas runÄ tostuā un ātas, kas griež desuā. SituÄcijÄ, kad katrai lomai ir 4 vai vairÄk pÄrstÄvji, to ar brutÄlu spÄku atrisinÄt nav iespÄjams. JautÄjums par ilgtspÄjÄ«gu sistÄmu ir atklÄts.
Å eiplijs ierosinÄja Ŕīs problÄmas risinÄjumu 1953. gadÄ. PieÅemsim konflikta situÄciju ar cilvÄku grupu N={1,2ā¦n}. Izmaksas/ieguvumi ir jÄsadala. PieÅemsim, ka cilvÄki kopÄ izdarÄ«ja ko lietderÄ«gu, pÄrdeva un kÄ sadalÄ«t peļÅu?
Å eplijs ierosinÄja, ka dalot mums vajadzÄtu vadÄ«ties pÄc tÄ, cik daudz Å”o cilvÄku noteiktas apakÅ”kopas varÄtu saÅemt. Cik naudas varÄtu nopelnÄ«t visas 2N netukÅ”Äs apakÅ”kopas? Un, pamatojoties uz Å”o informÄciju, Shapley uzrakstÄ«ja universÄlu formulu.
PiemÄrs. Pazemes ejÄ MaskavÄ spÄlÄ solists, Ä£itÄrists un bundzinieks. ViÅi trÄ«s nopelna 1000 rubļu stundÄ. KÄ to sadalÄ«t? IespÄjams, vienÄdi.
V(1,2,3)=1000
TaisnÄ«gu sadalÄ«jumu nevar noteikt, kamÄr mÄs nezinÄm, kÄdi ieguvumi sagaida konkrÄto uzÅÄmumu, ja tas sadalÄ«sies un rÄ«kosies pats. Un kad mÄs noteicÄm skaitļus (iestatiet sadarbÄ«bas spÄli raksturÄ«gÄ formÄ).
SuperadditivitÄte ir tad, kad kopÄ nopelna vairÄk nekÄ atseviŔķi, kad apvienoties ir izdevÄ«gÄk, bet nav skaidrs, kÄ laimestu sadalÄ«t. Par to ir salauztas daudzas kopijas.
Ir spÄle. TrÄ«s uzÅÄmÄji vienlaikus atrada depozÄ«tu 1 miljona dolÄru vÄrtÄ«bÄ. Ja viÅi trÄ«s piekrÄ«t, tad viÅu ir miljons. JebkurÅ” pÄris var nogalinÄt (noÅemt no lietas) un iegÅ«t visu miljonu sev. Un neviens neko nevar izdarÄ«t viens. Å Ä« ir biedÄjoÅ”a sadarbÄ«bas spÄle bez risinÄjuma. VienmÄr bÅ«s divi cilvÄki, kas var likvidÄt treÅ”o... KooperatÄ«vÄs spÄles teorija sÄkas ar piemÄru, kuram nav risinÄjuma.
MÄs gribam tÄdu risinÄjumu, lai neviena koalÄ«cija negribÄtu bloÄ·Ät kopÄjo risinÄjumu. Visu nodaļu kopa, ko nevar bloÄ·Ät, ir kodols. GadÄs, ka kodols ir tukÅ”s. Bet pat ja tas nav tukÅ”s, kÄ sadalÄ«t?
Å eplijs iesaka sadalÄ«t Å”ÄdÄ veidÄ. Iemet monÄtu ar n! malÄm. MÄs ierakstÄm visus spÄlÄtÄjus Å”ÄdÄ secÄ«bÄ. Teiksim, pirmais bundzinieks. ViÅÅ” ienÄk un paÅem savus 100. Tad ienÄk āotraisā, teiksim, solists. (KopÄ ar bundzinieku var nopelnÄ«t 450, bundzinieks jau paÅÄmis 100) Solists paÅem 350. IenÄk Ä£itÄrists (kopÄ 1000, -450), paÅem 550. Diezgan bieži uzvar pÄdÄjais. (SupermodularitÄte)
Ja mÄs izrakstÄm par visiem pasÅ«tÄ«jumiem:
GSB - (uzvara C) - (uzvara D) - (uzvara B)
SGB ā (uzvar C) - (uzvar D) - (uzvar B)
SBG ā (uzvara C) ā (uzvara D) ā (uzvara B)
BSG - (uzvara C) - (uzvara D) - (uzvara B)
BGS ā (pastiprinÄjums C) ā (pastiprinÄjums D) ā (pastiprinÄjums B)
GBS ā (uzvara C) ā (uzvar D) ā (uzvar B)
Un katrai kolonnai mÄs pievienojam un dalÄm ar 6 - vidÄji visiem pasÅ«tÄ«jumiem - tas ir Å eplija vektors.
Å eplijs pierÄdÄ«ja teorÄmu (aptuveni): Ir spÄļu klase (supermodulÄra), kurÄ nÄkamais, kas pievienojas lielai komandai, nes tai lielÄku uzvaru. Kodols vienmÄr nav tukÅ”s un ir izliekta punktu kombinÄcija (mÅ«su gadÄ«jumÄ 6 punkti). Å eplija vektors atrodas paÅ”Ä kodola centrÄ. To vienmÄr var piedÄvÄt kÄ risinÄjumu, neviens nebÅ«s pret to.
1973. gadÄ tika pierÄdÄ«ts, ka problÄma ar kotedžÄm ir supermodulÄra.
Visi n cilvÄki dala ceļu uz pirmo kotedžu. LÄ«dz otrajam - n-1 cilvÄki. utt.
LidostÄ ir skrejceļŔ. DažÄdiem uzÅÄmumiem ir nepiecieÅ”ami dažÄdi garumi. Rodas tÄda pati problÄma.
Es domÄju, ka tiem, kas pieŔķīra Nobela prÄmiju, bija prÄtÄ Å”is nopelns, nevis tikai rezerves uzdevums.