2012 жылы экономика бойынша Нобель сыйлығы Ллойд Шепли мен Элвин Ротқа берілді. «Тұрақты бөлу теориясы және нарықтарды ұйымдастыру тәжірибесі үшін». Алексей Савватеев 2012 жылы математиктердің еңбегінің мәнін қарапайым және анық түсіндіруге тырысты. Мен сіздердің назарларыңызға түйіндемені ұсынамын .
Бүгін теориялық лекция өтеді. Тәжірибелер туралы , атап айтқанда донорлық, мен айтпаймын.
Бұл туралы жарияланған кезде Нобель сыйлығын алған кезде стандартты сұрақ туындады: «Қалай!? Ол әлі тірі ме!?!?» Оның ең танымал нәтижесі 1953 жылы алынды.
Ресми түрде бонус басқа нәрсе үшін берілді. 1962 жылы «Неке тұрақтылығы теоремасы» туралы мақаласы үшін: «Колледжге түсу және неке тұрақтылығы».
Тұрақты неке туралы
қолайлы (сәйкестендіру) – сәйкестікті табу тапсырмасы.
Белгілі бір оқшауланған ауыл бар. «M» жас жігіттер мен «w» қыздар бар. Біз оларды бір-бірімізге үйлендіруіміз керек. (Міндетті түрде бірдей сан емес, мүмкін соңында біреу жалғыз қалуы мүмкін.)
Модельде қандай жорамалдар жасалуы керек? Кездейсоқ қайта үйлену оңай емес. Еркін таңдауға белгілі бір қадам жасалуда. Қайтыс болған соң ажырасулар басталып кетпеуі үшін қайта үйленгісі келетін дана ақсақал бар делік. (Ажырасу - күйеуінің әйелінен гөрі үшінші жақтың әйелін әйелі ретінде алғысы келетін жағдай.)
Бұл теорема қазіргі экономиканың рухында. Ол ерекше адамгершілікке жатпайды. Экономика әдетте адамгершілікке жатпайды. Экономикада адам пайданы көбейту үшін машинамен ауыстырылады. Менің сізге айтатыным моральдық тұрғыдан алғанда мүлдем ақылсыз нәрселер. Оны жүрекке жақын қабылдамаңыз.
Экономистер некеге осылай қарайды.
м1, м2,… мк - ерлер.
w1, w2,... wL - әйелдер.
Ер адам қыздарға қалай «тапсырыс беретінін» анықтайды. Сондай-ақ «нөлдік деңгей» бар, одан төмен әйелдерге тіпті басқалар болмаса да, әйел ретінде ұсынылмайды.
Барлығы екі бағытта болады, қыздарда бірдей.
Бастапқы деректер ерікті. Жалғыз болжам/шектеу - біз өз қалауларымызды өзгертпейміз.
Теорема: Бөлу мен нөлдік деңгейге қарамастан, кейбір ерлер мен кейбір әйелдердің арасында жеке-жеке хат алмасуды орнатудың жолы әрқашан бар, осылайша ол бөлінудің барлық түрлеріне (тек ажырасуға ғана емес) төзімді.
Қандай қауіптер болуы мүмкін?
Үйленбеген жұп (м,ж) бар. Бірақ w үшін қазіргі күйеуі m-ден нашар, ал m үшін қазіргі әйел w-дан нашар. Бұл тұрақсыз жағдай.
Сондай-ақ, біреу «нөлден төмен» адамға үйленді деген нұсқа бар; бұл жағдайда неке де бұзылады.
Егер әйел үйленген болса, бірақ ол нөлден жоғары тұратын үйленбеген ер адамды жақсы көрсе.
Егер екі адам екеуі де үйленбеген болса және екеуі де бір-біріне «нөлден жоғары» болса.
Кез келген бастапқы деректер үшін қауіп-қатердің барлық түрлеріне төзімді мұндай неке жүйесі бар деп айтылады. Екіншіден, мұндай тепе-теңдікті табу алгоритмі өте қарапайым. M*N-мен салыстырайық.
Бұл модель жалпыланып, «көп әйел алуға» дейін кеңейтілді және көптеген салаларда қолданылды.
Гейл-Шепли процедурасы
Егер барлық ерлер мен барлық әйелдер «рецепттерді» орындаса, нәтижесінде неке жүйесі тұрақты болады.
Рецепттер.
Қажет болса, бірнеше күн аламыз. Біз әр күнді екі бөлікке бөлеміз (таңертең және кешке).
Бірінші таңертең әрбір ер адам өзінің ең жақсы әйеліне барып, оған үйленуді сұрап, терезені қағады.
Сол күні кешке кезек әйелдерге беріледі Әйел нені аша алады? Оның терезесінің астында бір адам немесе ер адам жоқ. Бүгін ешкімі жоқтар кезегін өткізіп, күтеді. Қалғандары, кем дегенде біреуі бар, олар «нөлден жоғары» екенін көру үшін келген ерлерді тексереді. Кем дегенде біреуі болуы үшін. Егер сіз мүлдем бақытсыз болсаңыз және бәрі нөлден төмен болса, онда барлығын жіберу керек. Әйел келгендердің ең үлкенін таңдап, күтуін айтып, қалғандарын жібереді.
Екінші күнге дейін жағдай мынадай: кейбір әйелдерде бір еркек бар, кейбіреулерде жоқ.
Екінші күні барлық «бос» (жіберілген) ер адамдар екінші кезектегі әйелге бару керек. Егер мұндай адам болмаса, онда ер адам бойдақ деп жарияланады. Әйелдермен отырған еркектер әлі ештеңе істеп жатқан жоқ.
Кешке әйелдер жағдайға қарайды. Егер бұрын отырған біреу жоғарырақ басымдыққа қосылса, төменгі басымдық жіберіледі. Егер келгендер бардан төмен болса, барлығын шығарып салады. Әйелдер әр уақытта максималды элементті таңдайды.
Қайталаймыз.
Нәтижесінде әрбір ер адам өз әйелдерінің барлық тізімін қарап шықты және жалғыз қалды немесе әлдебір әйелмен айналысады. Сосын бәрін үйлендіреміз.
Бүкіл осы процесті жүргізу мүмкін бе, бірақ әйелдер ерлерге жүгіре ме? Процедура симметриялы, бірақ шешім әртүрлі болуы мүмкін. Бірақ сұрақ: бұдан кім жақсы?
Теорема. Осы екі симметриялық шешімді ғана емес, барлық тұрақты неке жүйелерінің жиынтығын қарастырайық. Ұсынылған бастапқы механизм (ерлер жүгіреді және әйелдер қабылдайды/бас тартады) кез келген еркек үшін кез келген басқалардан жақсырақ және кез келген әйел үшін кез келген басқасынан нашар болатын неке жүйесіне әкеледі.
Бірдей жыныстық некелер
«Бір жынысты некеге» қатысты жағдайды қарастырайық. Оларды заңдастыру қажеттілігіне күмән тудыратын математикалық нәтижені қарастырайық. Идеологиялық тұрғыдан дұрыс емес мысал.
Төрт гомосексуалды қарастырайық a, b, c, d.
үшін басымдықтар: bcd
b:cad үшін басымдықтар
c үшін басымдықтар: abd
d үшін оның қалған үш орынды қалай қойғаны маңызды емес.
Бекіту: Бұл жүйеде тұрақты неке жүйесі жоқ.
Төрт адамға неше жүйе бар? Үш. ab cd, ac bd, ad bc. Ерлі-зайыптылар ажырасып, процесс циклдармен жүреді.
«Үш жынысты» жүйелер.
Бұл математиканың бүкіл саласын ашатын ең маңызды сұрақ. Мұны менің Мәскеудегі әріптесім Владимир Иванович Данилов жасады. Ол «үйленуді» арақ ішу деп есептеді және рөлдер: «құйғыш», «тост сөйлейтін», «шұжық кесетін». Әр рөлдің 4 немесе одан да көп өкілі болған жағдайда оны дөрекі күшпен шешу мүмкін емес. Тұрақты жүйе мәселесі ашық.
Шепли векторы
Саяжай ауылында олар жолды асфальттауды шешті. Кіру керек. Қалай?
Шепли бұл мәселенің шешімін 1953 жылы ұсынды. N={1,2…n} адамдар тобымен қақтығыс жағдайын алайық. Шығындар/пайдалар ортақ болуы керек. Адамдар бірге пайдалы нәрсе жасады делік, оны сатыңыз және пайданы қалай бөлуге болады?
Шепли бөлу кезінде біз осы адамдардың белгілі бір жиынтықтары қаншалықты ала алатынын басшылыққа алуды ұсынды. Барлық 2N бос емес жиындар қанша ақша таба алады? Және осы мәліметтерге сүйене отырып, Шепли әмбебап формула жазды.
Мысал. Мәскеудегі жерасты өткелінде солист, гитарист және барабаншы ойнайды. Үшеуі сағатына 1000 рубль алады. Оны қалай бөлуге болады? Мүмкін бірдей.
V(1,2,3)=1000
Енді солай етейік
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100
Егер компания бөлініп, өз бетімен әрекет етсе, оны қандай табыстар күтіп тұрғанын білмейінше, әділ бөлімді анықтау мүмкін емес. Ал біз сандарды анықтаған кезде (сипаттамалық формада кооперативтік ойынды орнатыңыз).
Супераддитивтілік - бұл олардың бөлектен гөрі көп табыс табуы, біріктіру тиімдірек болған кезде, бірақ ұтысты қалай бөлу керектігі белгісіз. Бұл туралы көптеген көшірмелер бұзылған.
Ойын бар. Үш кәсіпкер бір уақытта құны 1 миллион доллар болатын депозит тапты. Үшеуі келіссе, миллионы бар. Кез келген ерлі-зайыптылар өлтіріп (істен алып тастай алады) және бүкіл миллионды өздеріне ала алады. Және ешкім жалғыз ештеңе істей алмайды. Бұл шешімі жоқ қорқынышты бірлескен ойын. Үшіншісін жоя алатын екі адам әрқашан болады... Бірлескен ойын теориясы шешімі жоқ мысалдан басталады.
Ешбір коалиция ортақ шешімге тосқауыл қоюды қаламайтындай шешімді қалаймыз. Бұғаттауға болмайтын барлық бөлімдердің жиынтығы ядро болып табылады. Өзегі бос болып қалады. Бірақ бос болмаса да, қалай бөлуге болады?
Шепли осылай бөлуді ұсынады. n белгісімен тиын лақтырыңыз! жиектер. Біз барлық ойыншыларды осы ретпен жазамыз. Бірінші барабаншы делік. Ол кіреді және өзінің 100-ін алады. Содан кейін «екінші» келеді, солист делік. (Барабаншымен бірге олар 450 таба алады, барабаншы 100 алды) Солист 350 алады. Гитарист кіреді (бірге 1000, -450), 550 алады. Соңғысы жиі жеңеді. (Супермодулярлық)
Барлық тапсырыстар бойынша жазатын болсақ:
GSB - (С жеңісі) - (D жеңісі) - (В жеңісі)
SGB - (С жеңісі) - (D жеңісі) - (В жеңісі)
SBG - (С жеңісі) - (D жеңісі) - (В жеңісі)
BSG - (С жеңісі) - (D жеңісі) - (В жеңісі)
BGS - (C өсімі) - (D өсімі) - (В өсімі)
GBS - (C жеңісі) - (D жеңісі) - (В жеңісі)
Әр баған үшін біз 6-ға қосамыз және бөлеміз - барлық тапсырыстар бойынша орташа - бұл Шепли векторы.
Шепли теореманы дәлелдеді (шамамен): Ойындар класы бар (супермодульдік), онда үлкен командаға келесі адам қосылатын оған үлкен жеңіс әкеледі. Ядро әрқашан бос емес және нүктелердің дөңес комбинациясы (біздің жағдайда 6 ұпай). Шепли векторы ядроның дәл ортасында жатыр. Оны әрқашан шешім ретінде ұсынуға болады, оған ешкім қарсы болмайды.
1973 жылы коттедждер мәселесі супермодульдік екендігі дәлелденді.
Барлық n адам бірінші коттеджге баратын жолды бөліседі. Екіншіге дейін – n-1 адам. Және т.б.
Әуежайда ұшу-қону жолағы бар. Әртүрлі компанияларға әртүрлі ұзындықтар қажет. Дәл осындай мәселе туындайды.
Менің ойымша, Нобель сыйлығын алғандар тек маржа міндетін емес, осы еңбегін ескерген.
рахмет!
Көбірек көрсету
- «Математика - қарапайым» арнасы:
- «Савватеев шекарасыз» арнасы: edusex.ru, brainsex.ru, studfuck.ru
- Жалпыға ортақ «Математика қарапайым»:
- Көпшіліктің «Математиктер қалжыңы»:
- Сайт, онда барлық дәрістер +100 сабақ және одан да көп: savvateev.xyz
Ақпарат көзі: www.habr.com