Di sala 2012 de, Xelata Nobelê ya Aboriyê ji Lloyd Shapley û Alvin Roth re hat dayîn. "Ji bo teoriya belavkirina stabîl û pratîka rêxistinkirina bazaran." Aleksey Savvateev di sala 2012-an de hewl da ku bi hêsanî û bi zelalî cewhera hêjayiyên matematîkzan rave bike. Ez kurtejiyanekê pêşkêşî we dikim .
Îro wê derseke teorîk bê dayîn. Der barê ceribandinên , bi taybetî bi bexşînê, ez ê nebêjim.
Dema ku hat ragihandin ku Xelata Nobelê wergirtibû, pirsek standard hebû: “Çawa!? Ma ew hîn sax e!?” Encama wî ya herî navdar di sala 1953 de hate bidestxistin.
Bi fermî, bonus ji bo tiştek din hate dayîn. Ji bo gotara wî ya sala 1962-an li ser "teorema aramiya zewacê": "Qedexekirina zanîngehê û aramiya zewacê."
Di derbarê zewaca domdar de
Lihevhatin (lihevkirin) - peywira dîtina pêwendiyek.
Gundekî veqetandî heye. Xortên “m” û keçên “w” hene. Divê em wan bi hev re bizewicînin. (Ne hewce ye ku heman hejmar, dibe ku di dawiyê de kesek tenê bimîne.)
Divê di modelê de çi texmîn bêne kirin? Ku ew ne hêsan e ku ji nû ve zewicî bi rasthatinî. Ji bo hilbijartina azad gavek diyar tê avêtin. Em bibêjin aksakalekî jîr heye ku dixwaze ji nû ve bizewice da ku piştî mirina wî hevberdan dest pê nekin. (Destberdan rewşek e ku mêr ji jina xwe bêtir jina xwe ya sêyemîn dixwaze.)
Ev teorem di ruhê aboriya modern de ye. Ew bi taybetî nemirovî ye. Aborî bi kevneşopî nemirovî bûye. Di aboriyê de, mirov bi makîneyek ji bo zêdekirina qezencê tê guhertin. Tiştê ku ez ê ji we re bibêjim ji hêla exlaqî ve bi tevahî tiştên dîn in. Bi dilê xwe negirin.
Aborînas bi vî awayî li zewacê dinêrin.
m1, m2,… mk - mêr.
w1, w2,... wL - jin.
Zilamek bi awayê ku ew "emrê" keçan dike tê nasîn. Di heman demê de "asta sifir" jî heye, ku di binê wê de jin bi ti awayî nayên pêşkêş kirin, tevî ku yên din tune bin.
Her tişt di herdu aliyan de diqewime, ji bo keçan heman.
Daneyên destpêkê keyfî ne. Tenê texmîn/sînor ev e ku em tercîhên xwe naguherînin.
Teorem: Bêyî dabeşbûn û asta sifirê, her gav rêyek heye ku meriv pêwendiyek yek-bi-yek di navbera hin mêr û hin jinan de saz bike da ku ew ji her cûre perçebûnê re (ne tenê ji hevberdanê) bihêz be.
Dibe ku çi tehdîd hebin?
Cotek (m,w) heye ku ne zewicî ye. Lê ji bo w mêrê niha ji m xerabtir e û ji bo m jina niha ji w xerabtir e. Ev rewşeke bê domdar e.
Di heman demê de vebijarkek heye ku kesek bi kesekî ku "di bin sifirê" de ye re zewicî bû; di vê rewşê de, zewac jî dê hilweşe.
Ger jinek zewicî be, lê ew zilamek nezewicî tercîh dike, ji bo ku ew ji sifirê re ye.
Ger du kes herdu jî nezewicî bin, û her du jî ji bo hev "ji sifirê" bin.
Tê îdiakirin ku ji bo her daneyên destpêkê sîstemek zewacê ya bi vî rengî heye, li hember her cûre gefan berxwedêr e. Ya duyemîn, algorîtmaya dîtina hevsengiyek wusa pir hêsan e. Ka em bi M*N re bidin ber hev.
Ev modêl hate giştîkirin û berbelavbûna “pirzamî” û di gelek waran de hat sepandin.
Pêvajoya Gale-Shapley
Ger hemî mêr û hemî jin "reçeteyan" bişopînin, pergala zewacê ya encam dê domdar be.
Reçeteyên.
Li gorî hewcedariyê em çend rojan digirin. Em her roj dikin du beş (sibe û êvar).
Sibeha ewil her zilam diçe cem jina xwe ya herî baş û li pencerê dixe û jê re dixwaze bizewice.
Êvara heman rojê dor li jinan dibe, jin dikare çi kifş bike? Ku di bin pencereya wê de qelebalixek hebû, yan yek yan jî tu mêr. Yên ku îro tu kes nînin, dora xwe diavêjin û li bendê ne. Yên mayî, yên ku bi kêmanî yek heye, zilamên ku têne kontrol bikin ku ew "ji asta sifirê" ne. Bi kêmanî yek hebe. Ger hûn bi tevahî bêbext in û her tişt di binê sifirê de ye, wê hingê divê her kes were şandin. Jinik ji yên ku hatine yê herî mezin hildibijêre, jê re dibêje bila bisekine û yên mayî jî dişîne.
Beriya roja duduyan, rewş ev e: hinek jinan yek mêr in, hinekan jî tune.
Di roja duyemîn de, hemî zilamên "azad" (şandin) hewce ne ku biçin cem jina pêşîn a duyemîn. Ger kesek wisa tune be, wê demê mêr bi tenê tê ragihandin. Ew zilamên ku berê bi jinan re rûdiniştin, hê tiştekî nakin.
Êvarê jin li rewşê dinêrin. Ger yekî ku berê rûniştibû bi pêşanîyek bilindtir tev lê bû, wê hingê pêşîniya jêrîn tê şandin. Eger yên tên ji yên heyî kêmtir bin, her kes tê şandin. Jin her car hêmana herî zêde hildibijêrin.
Em dubare dikin.
Di encamê de, her zilamek di tevahiya lîsteya jinên xwe de derbas bû û an bi tenê ma an jî bi hin jinan re mijûl bû. Paşê em ê her kesî bizewicin.
Ma gengaz e ku meriv vê pêvajoyê tev bimeşîne, lê jin bi mêran re bimeşin? Pêvajoyek sîmetrîk e, lê çareserî dikare cûda be. Lê pirs ev e, kî ji vê çêtir e?
Teorem. Ka em ne tenê van her du çareseriyên sîmetrîk, lê komek hemî pergalên zewacê yên domdar bifikirin. Mekanîzmaya pêşniyarkirî ya orîjînal (zilam direvin û jin qebûl dikin / red dikin) di encamê de pergalek zewacê peyda dike ku ji bo her zilamî ji yên din çêtir û ji her yekê ji bo her jinê xirabtir e.
Zewaca heman zayendî
Rewşa "zewaca hevzayendan" bifikire. Ka em encamek matematîkî ya ku gumanê li ser hewcedariya qanûnîkirina wan dixe berçavan. Mînaka îdeolojîk a nerast.
Li çar homoseksuelên a, b, c, d binêrin.
pêşanî ji bo a: bcd
pêşanî ji bo b: cad
pêşanî ji bo c: abd
ji bo d ferq nake ew sisê mayî çawa rêz dike.
Îfade: Di vê pergalê de pergala zewacê ya domdar nîne.
Ji bo çar kesan çend sîstem hene? Sê. ab cd, ac bd, ad bc. Dê zewac ji hev veqetin û pêvajo dê di çerçoveyê de bimeşe.
Sîstemên "sê zayendî".
Ev pirsa herî girîng e ku qada matematîkê ya tevahî vedike. Ev ji aliyê hevkarê min li Moskowê, Vladîmîr Îvanovîç Danîlov hat kirin. Wî "zewac" wek vexwarina araqê dinirxand û rol jî wiha bûn: "Yê ku dirijîne", "Yê ku tostê dipeyive" û "Yê ku sosîsê dibire." Di rewşek ku ji her rolê 4 an zêdetir nûnerên wan hene, ne mimkûn e ku bi hêzek hov were çareser kirin. Pirsa sîstemeke domdar pirseke vekirî ye.
Vektora Shapley
Li gundê kotê biryar dan ku rê asfalt bikin. Pêwîstî bi çîpkirinê heye. Çawa?
Shapley di sala 1953 de ji bo vê pirsgirêkê çareseriyek pêşniyar kir. Ka em rewşek pevçûnê bi komek mirovan re bikin N={1,2…n}. Pêdivî ye ku lêçûn / berjewendî bêne parve kirin. Bifikirin ku mirovan bi hev re tiştek kêrhatî kir, bifroşin û meriv çawa qezencê dabeş bike?
Shapley pêşnîyar kir ku dema dabeşkirinê, divê em bi rê ve bibin ka çend beşên van kesan çiqas dikarin bistînin. Hemî 2N binkomên ne vala dikarin çiqas pere qezenc bikin? Û li ser vê agahdariyê, Shapley formula gerdûnî nivîsand.
Nimûne. Solîstek, gîtarîst û tembûrvanek li Moskowê li pasajeke binerdê dilîzin. Her sê ji wan di saetekê de 1000 ruble qezenc dikin. Meriv çawa wê dabeş bike? Dibe ku wekhev.
V(1,2,3)=1000
Werin em wisa bikin
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Dabeşkirinek adil nayê destnîşankirin heya ku em zanibin ka çi destkeftî li benda pargîdaniyek diyarkirî ye ger ew ji hev veqete û bi serê xwe tevbigere. Û gava ku me hejmaran diyar kir (lîstika hevkariyê di forma taybetmendiyê de bicîh bikin).
Superadditivity ew e dema ku ew bi hev re ji hev cûda bêtir qezenc dikin, dema ku yekbûnek bikêrtir e, lê ne diyar e ka meriv çawa qezencan dabeş dike. Li ser vê yekê gelek nusxe hatine şikandin.
Lîstikek heye. Sê karsaz di heman demê de depoyek bi qasî 1 mîlyon dolar dîtin. Ger her sê ji wan razî bin, wê demê mîlyonek ji wan hene. Her cotek dikare bikuje (ji dozê derxe) û tevahiya mîlyonê ji xwe re bigire. Û kes bi tena serê xwe nikare tiştekî bike. Ev lîstikek hevkariyek tirsnak e ku bê çare ye. Dê her dem du kes hebin ku dikarin ya sêyemîn tasfiye bikin... Teoriya lîstika hevkar bi mînakek ku çare nîne dest pê dike.
Em çareseriyeke wisa dixwazin ku ti koalîsyon naxwaze çareseriya hevpar asteng bike. Komek hemî dabeşên ku nayên asteng kirin kernel e. Diqewime ku core vala ye. Lê heke vala nebe jî, çawa dabeş dibe?
Shapley dabeşkirina vî rengî pêşniyar dike. Bi n re zîvekî biavêje! qeraxên. Em hemî lîstikvanan bi vê rêzê dinivîsin. Em bibêjin tembûrê yekem. Ew tê hundur û 100-a xwe digire. Paşê "duyemîn" tê hundur, em bibêjin solîst. (Bi tembûrê re ew dikarin 450 qezenc bikin, tembûrê jixwe 100 standiye) Solîst 350 distîne. Guitarist dikeve hundir (bi hev re 1000, -450), 550 distîne. Yê dawî pir caran bi ser dikeve. (Supermodularity)
Ger em ji bo hemî fermanan binivîsin:
GSB - (serkeftin C) - (serkeftin D) - (serkeftina B)
SGB - (serkeftin C) - (serkeftin D) - (serkeftina B)
SBG - (serkeftin C) - (serkeftin D) - (serkeftin B)
BSG - (serkeftin C) - (serkeftin D) - (serkeftina B)
BGS - (qezenc C) - (qezenc D) - (qezenc B)
GBS - (serkeftin C) - (serkeftin D) - (serkeftina B)
Û ji bo her stûnê em lê zêde dikin û dabeş dikin 6 - li ser hemî fermanan - ev vektorek Shapley ye.
Shapley teorema îsbat kir (teqrîben): Çînek lîstikan (supermodular) heye, ku tê de kesê din ku beşdarî tîmek mezin dibe serkeftinek mezintir jê re tîne. Kernel her gav ne vala ye û ji xalan berhevokek binavkirî ye (di rewşa me de, 6 xal). Vektora Shapley li navenda navokê ye. Her tim weke çareserî dikare were pêşkêşkirin, tu kes li dijî wê dernakeve.
Di sala 1973-an de hate îsbat kirin ku pirsgirêka xaniyan supermodular e.
Hemî n kes riya kozika yekem parve dikin. Heya duyemîn - n-1 kes. hwd.
Di balafirgehê de pistegehek heye. Pargîdaniyên cûda hewceyê dirêjiyên cûda ne. Heman pirsgirêk derdikeve holê.
Ez wisa difikirim ku yên ku xelata Nobelê dane, ev merîfet di hişê xwe de hebû, ne tenê wezîfeya marjînal.
Spas!
Hîn
- Kanala "Math - Simple":
- Kanala "Savvateev bê sînor": edusex.ru, brainsex.ru, studfuck.ru
- Giştî "Matematîk hêsan e":
- Gel "Pêkaniya Matematîkê":
- Malper, hemî dersên li wir +100 ders û bêtir: savvateev.xyz
Source: www.habr.com