У 2012 році Нобелівську премію з економіки видали Ллойду Шеплі та Елвіну Роту. «За теорію стабільного розподілу та практики влаштування ринків». Олексій Саватєєв у 2012 році спробував просто і зрозуміло розповісти у чому суть заслуг математиків. Пропоную вашій увазі конспект .
Сьогодні буде теоретична лекція. Про експерименти , зокрема з донорством, я не розповідатиму.
Коли оголосили, що отримав нобелівку, було стандартне запитання: «Як!? Він ще живий!?!?» Найвідоміший його результат було отримано 1953 року.
Формально премію дали за інше. За роботу 1962 року за «теорему про стійке одруження»: «Прийом у коледжі та стабільність шлюбу» (College Admission and the Stability of Marriage).
Про стійке одруження
Узгодження (Метчінг) - Завдання про знаходження відповідності.
Є якесь ізольоване село. Там "m" молодих людей та "w" дівчат. Потрібно їх передружити один на одному. (Не обов'язково однакова кількість, може, в результаті хтось залишиться один.)
Які необхідно зробити причини в моделі? Що не просто навмання переженити. Робиться крок у бік вільного вибору. Припустимо, є мудрий аксакал, який хоче так переженити, щоб після його смерті не почалися розлучення. (Розлучення, це ситуація, коли чоловік хоче за дружину сторонню жінку більше, ніж дружину.)
Ця теорема на кшталт сучасної економіки. Вона винятково нелюдська. Економіка традиційно нелюдська. В економіці людина замінена на машину з максимізації прибутку. Те, що я розповідатиму — абсолютно шалені речі з погляду моралі. Не приймайте близько до серця.
Економісти дивляться на шлюб так.
m1, m2, ... mk - Чоловіки.
w1, w2, ... wL - жінки.
Чоловік ототожнюється з тим, як він упорядковує дівчат. Є ще й «нульовий рівень», перебуваючи нижче за який, жінкам взагалі не можна пропонуватися за дружину, навіть якщо інших немає.
Все відбувається в обидві сторони, у дівчат те саме.
Початкові дані довільні. Єдине припущення/обмеження — ми не змінюємо своїх переваг.
Теорема: Незалежно від розподілу та рівня нуля, завжди існує спосіб встановити взаємно однозначну відповідність між частиною чоловіків і частиною жінок, так що він буде стійким по відношенню до будь-яких видів розколів (не тільки розлучень).
Які можуть бути небезпеки?
Є пара (m,w), яка не одружена. Але для w поточний чоловік гірший ніж m, а для m поточна дружина гірша, ніж w. Це нестійка ситуація.
Є ще варіант, що когось одружили з тим, хто «нижчий за нуль», у цій ситуації теж шлюб розпадеться.
Якщо жінка в шлюбі, але їй більше подобається неодружений, для якого вона вища за нуль.
Якщо дві людини, обидва не одружені, і обидва один для одного «вище нуля».
Стверджується, що з будь-яких початкових даних така система шлюбів існує, стійке всім видам загроз. По-друге, алгоритм знаходження такої рівноваги дуже простий. Порівняємо з M*N.
Цю модель узагальнили і розширили до «багатоженства» та застосували у багатьох областях.
Процедура Гейла-Шеплі
Якщо всі чоловіки і всі жінки виконуватимуть «розпорядження», то результуюча система одруження виявиться стійкою.
Розпорядження.
Беремо кілька днів, скільки знадобиться. Щодня розбиваємо на дві частини (ранок та вечір).
Першого ранку кожен чоловік вирушає до своєї найкращої жінки і стукає у віконце, пропонуючи їй вийти за нього заміж.
Увечері того ж дня хід переходить до жінок. Що може виявити жінка? Що під вікном у неї натовп, або один або жодного чоловіка. Ті, у кого нікого не було сьогодні, пропускають хід, чекають. Решта, у кого є хоча б один, перевіряють чоловіків, що прийшли на те, що вони «вищі за рівень нуля». Щоб був бодай один. Якщо зовсім не пощастило і все нижче за нуль, тоді всіх треба послати. Жінка вибирає максимального з тих, хто прийшов, каже йому почекати, а решту посилає.
Перед другим днем ситуація така – у деяких жінок сидить один чоловік, у деяких – жодного.
На другий день всім «вільним» (посланим) чоловікам потрібно йти до другої за пріоритетом жінки. Якщо такої немає, то чоловік оголошується неодруженим. Тим чоловікам, які вже сидять у жінок, поки що нічого не роблять.
Увечері жінки дивляться на ситуацію. Якщо до того хто вже сидів приєднався пріоритетніший, то менш пріоритетного відправляють геть. Якщо ті, хто прийшов нижче, ніж вже наявний, всі відсилаються. Жінки щоразу вибирають максимальний елемент.
Повторюємо.
У результаті кожен чоловік перебрав весь список своїх жінок і або залишився один, або заангажований у якоїсь жінки. Тоді ми всіх одружуємо.
Чи можна прогнати весь цей процес, але щоби жінки бігали до чоловіків? Процедура симетрична, але рішення може бути іншим. Але питання, кому від цього краще?
Теорема. Розглянемо не тільки ці два симетричні рішення, але й безліч усіх стійких систем одруження. Вихідний запропонований механізм (чоловіки бігають, а жінки погоджуються/відмовляються) призводить до системи одружень, яка краще для будь-якого чоловіка, ніж будь-яка інша та гірша, ніж будь-яка інша для будь-якої жінки.
Одностатеві шлюби
Розглянемо ситуацію із «одностатевими шлюбами». Розглянемо математичний результат, який ставить під сумнів необхідність легалізувати їх. Ідеологічно некоректний приклад.
Розглянемо чотирьох гомосексуалістів a, b, c, d.
пріоритети для a: 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. Останній, хто увійшов, досить часто буває у виграші. (Супермодулярність)
Якщо ми для всіх порядків випишемо:
ГСБ - (виграш С) - (виграш Г) - (виграш Б)
СГБ - (виграш С) - (виграш Г) - (виграш Б)
СБГ - (виграш С) - (виграш Г) - (виграш Б)
БСГ - (виграш С) - (виграш Г) - (виграш Б)
БГС - (виграш С) - (виграш Г) - (виграш Б)
ГБС - (виграш С) - (виграш Г) - (виграш Б)
І по кожному стовпцю складемо і поділимо на 6 - усереднення за всіма порядками - це вектор Шеплі.
Шеплі довів теорему (приблизно): Є такий клас ігор (супермодулярні), у яких наступний у велику команду - він приніс до неї більший виграш. Ядро завжди не порожнє і є опуклою комбінацією крапок (у нашому випадку 6 крапок). Вектор Шеплі лежить у центрі ядра. Його завжди можна запропонувати як рішення, ніхто не буде проти.
1973 року було доведено, що завдання з котеджами — супермодулярне.
Дорогу до першого котеджу ділять усі n чоловік. До другого – n-1 людина. І т.д.
В аеропорту є злітна смуга. Різним компаніям потрібна різна довжина. Виникає те саме завдання.
Думаю, що ті, хто видавав Нобелівську премію, мали на увазі і цю заслугу, а не тільки завдання мар'яжу.
Спасибо!
Ще
- Канал «Математика – просто»:
- Канал «Саватеїв без кордонів»: edusex.ru, brainsex.ru, studfuck.ru
- Паблік «Математика – просто»:
- Паблік «Математики жартують»:
- Сайт, усі лекції там +100 уроків та інше: savvateev.xyz
Джерело: habr.com