— Найдавнішими є товарні ринки, де відбувається обмін між продавцями і покупцями. Коли в однієї людини був у надлишку один товар, а у іншої — другий, вони могли обмінятися. Згодом для спрощення цього процесу з'явилися гроші. Продавець може виставити ціну, а покупці вирішуватимуть, купувати чи ні. Коли на ринку декілька людей починають продавати однаковий товар, то ціна на нього падає, якщо продавців мало — ціна зростає. Так ринок реагує на перевищення та зниження пропозиції.

Іноді виникають ситуації, коли гроші «не працюють». Недостатньо заплатити і вибрати товар, потрібно, щоб вас також вибрали. Наприклад, вступна кампанія у ВНЗ. Абітурієнти отримують бюджетні місця безкоштовно, але потрібно, щоб і університет прийняв студента з його балами.

Розглянемо ринок роботи програмістів. Припустимо, що він працює, як товарний. Компанія розмістила вакансію і запропонувала певну зарплату. На цю пропозицію відгукнулось 10 кандидатів. Компанія починає відсіювати зайвих кандидатів, знижуючи запропоновану заробітну плату, аж поки не залишиться один програміст. В реальності відбувається інакше: без співбесіди та відбору Гугл не візьме програміста, навіть якщо той згодиться працювати за половину зарплатні. Такі ринки називаються matching markets — ринками з паруванням, і вони мають свої особливості.

Щоб ринок з паруваннями був успішним, необхідно, аби виконувались три властивості. Розглянемо на прикладі ринку сервісу з бронювання житла Airbnb. Гості обирають житло, яке хочуть орендувати, а його господар обирає із усіх пропозицій одного гостя, якому дозволить оселитись в своєму помешканні на деякий час.

Також на ринок з паруваннями впливають так звані огидні (repugnant) транзакції. Огидна транзакція — це не та, яка просто викликає огиду, а та, яку частина людей забороняє робити іншим. Щоб сконструювати працюючий ринок, потрібно врахувати цей фактор. «Огидний» не завжди тотожно незаконному. Огида залежить від категорії людей або країни, тобто те, що вважається огидним для одних, для інших — цілком нормально. Наприклад,в США не можна в ресторані замовити страву з конини. В 1998 році в Каліфорнії пройшов референдум, на якому люди проголосували за заборону страв із конини. При цьому вбивати коней, годувати кониною собак — цілком законно. У той же час для Європи страви з конини досить звичні.

В середньовічній Європі погано відносились до позик під відсотки. У деяких країнах це було заборонено законом, але рабство за борги вважалось цілком нормальним. Багато людей продавали себе в рабство на декілька років, щоб оплатити переїзд до Америки. Менше ніж за 300 років ситуація змінилась: рабство стало огидним, а позика під відсотки — вітається. Хоча у мусульманських країнах огидне ставлення до відсотків збереглося досі.

Інколи сама дія не викликає огиду, але коли за це отримують гроші, то ставлення до неї змінюється. Наприклад, проституція: секс — незаборонений, але ставлення до сексу за гроші погане. У США, як і в більшості країн світу не можна платити за донорські органи. По закону їх можна отримати лише в дарунок.

Ринок створює певні правила. Якщо вони не будуть «хорошими», учасники шукатимуть способи обійти їх, а це може призвести до руйнування ринку.

До 1900 року в США молоді лікарі після закінчення інституту могли відразу практикувати. Але ввели нову реформу, і правила змінились: щоб стати самостійним практикуючим лікарем, випускнику потрібно простажуватися декілька років під наглядом досвідчених спеціалістів. Інтернатура була першою сходинкою в кар'єрі молодих лікарів, їм було важливо потрапити в хороші лікарні, які також хотіли собі найкращих інтернів. Спочатку клініки пропонували інтернатуру студентам після випуску, але щоб обійти конкурентів і отримати кращих, деякі лікарні робили пропозиції на декілька тижнів раніше. Коли всі лікарні це зрозуміли, виник такий ефект як «ранність». Студентів почали наймати все раніше, і через деякий час пропозиції приходили за три роки до закінчення університету. За такий час було важко визначити, чи стане цей студент успішним лікарем. Та й майбутні інтерни тягнули час, щоб почекати пропозиції від кращої клініки або погоджувались, а потім розривали контракт.

В 1946 році втрутилась третя сторона — медичні школи, вони встановили дату, до якої не надавали лікарням жодної інформації про студентів. Це вирішило проблему з ранністю, але виник другий ефект — «вибухові пропозиції». Лікарні робили пропозиції, на які потрібно відповісти відразу. Студент не мав часу почекати іншого запрошення і не міг відмовитись від того, що надійшло — адже, можливо, кращого вже не буде.

Тоді вирішили зробити центр, куди студенти та роботодавці подавали результати співбесід. При цьому студенти вказували свій пріоритет по лікарнях, а роботодавці визначали пріоритет по студентам. Цей центр мав зробити парування для всіх студентів і лікарень так, щоб задовольнити інтереси двох сторін. Єдиний вихід — зробити алгоритм, який буде захищеним від наступних проблем.

Ці проблеми розв'язав алгоритм Гейла-Шеплі, який виник у 1950-х роках.

1962 року вийшла стаття американських економістів та математиків Девіда Гейла та Ллойда Шеплі з інтригуючою назвою «Подача документів у коледж та стабільність шлюбу», в якій автори описали свій алгоритм парування.

Розглянемо його на прикладі нескладної задачі про шлюб. Ми маємо трьох жінок (А, В, С) і трьох чоловіків (а,b,c) з певними уподобаннями, які вказані на схемах. Тобто жінка А вважає, що найкращою парою для неї був би чоловік b, на другому місці — а, на третьому — с. Потрібно за скінченну кількість кроків запропонувати парування, яке було б стабільним.

Для прикладу перевіримо пари Аа,Вb, Сс. Це парування не буде стабільним, оскільки жінка B і чоловік с можуть утворити кращі пари. Парування Аа,Вс, Сb також нестабільне, тому що b може запропонувати А кращу пару. А от парування Аb, Ва, Сс є стабільним, оскільки всі жінки отримали свої перші місця, і жоден чоловік не може запропонувати їм кращу пару.

Доведено, що стабільне парування завжди існує, і навіть не завжди єдине. Якщо у нас n чоловіків і n жінок, то алгоритм Гейла-Шеплі знайде його не більше, ніж за n кроків. Розглянемо, як він працює на попередньому прикладі.

Кожен чоловік робить пропозицію своєму першому номеру в списку уподобань. Жінка, яка отримала декілька пропозицій, вибирає найкращу, ставить її в список очікування, а іншим відмовляє. Ті, кому відмовили роблять пропозицію своєму наступному уподобанню і так далі.

В нашому випадку чоловіки а, b, c роблять пропозиції жінкам A, B, B відповідно.

Жінка А ставить чоловіка а в список очікування (адже він в неї на другому місці і можливо їй запропонують кращий варіант). Жінка B відмовляє чоловіку b (він для неї на третьому місці) і ставить в список очікування с (він на другому місці).

Чоловік b, отримавши відмову, робить пропозицію жінці А (вона в нього на другому місці). У жінки А чоловік b на першому місці в списку, тому вона погоджується, а чоловікові а відмовляє.

Цей чоловік звертається до жінки B, яка погоджується, оскільки він в неї на першому місці, і відмовляє чоловіку с.

с робить пропозицію С і вона погоджується. Ми отримали такий же результат Аb, Ва, Сс, що є стабільним.

Якщо хочете опробувати алгоритм самостійно, то ось нескладна задача. Чотири студенти А, В, С, D поселяються в гуртожитки. Є дві двомісні кімнати, але кожен студент з кимось хоче жити разом, а з кимось — ні (на схемі показані уподобання). Потрібно розселити студентів в кімнати таким чином, щоб всі залишились задоволеними (утворити стійкі парування). Спробуйте використати алгоритм Гейла-Шеплі.

Цей алгоритм працює і для більш складних задач. Розглянемо, як розвивався ринок вступу до ВНЗ в Україні. В часи, коли я вступав до університету, дозволялося подавати лише оригінали документів. Податися в декілька вузів могли лише ті, хто мав золоту медаль чи нагороди за олімпіади — це була як суперздатність. Оскільки більшість абітурієнтів мали можливість подати документи лише в один університет, і гарантії точного вступу не було, з'явилася ранність. Виникли різні підготовчі курси, які давали право раннього вступу, вузівські олімпіади. Часто вони були платними.

Минулого року з'явилися нові правила. Я їх подививися та зрозумів, що тепер відбір проходитиме за алгоритмом Гейла-Шеплі. Є центральне сховище, де відбувається розподіл абітурієнтів по вузам, кожен студент може вибрати до семи різних ВНЗ, вказавши на заявках пріоритет вступу. Зі сторони вузів пріоритет — це бал ЗНО, або ще творчий конкурс для деяких університетів. Після того формуються три черги — пільги першої категорії, пільги другої і загальна.

Потім відбувається парування.

Абітурієнтам приходять повідомлення про те, куди вони можуть подавати оригінали.

Ринки неуспішні, коли порушується одна з трьох основ: щільність, швидкість та безпечність. Симптоми неуспішного ринку — ранність, неефективність, черги. Припустимо, що ми хочемо розвалити ринок реєстрації автомобілів. Потрібно зробити так, щоб послуга розвивалась лише в декількох місцях — двох-трьох центрах, а іншим компаніям, що надають подібні послуги, заборонено виходити на цей ринок. Тепер потрібно його перевантажити — ускладнити доступ до послуги, утворити черги. Щоб порушити безпечність, потрібна відсутність гарантій на послуги, тобто компанія не несе відповідальність, коли у користувачів якісь проблеми. Далі можна створити сірий або чорний ринок, де за додаткові гроші надавати людям ці послуги швидше.

Алгоритм Гейла-Шеплі гарно працював для медичних шкіл в 1950-1970-х роках, але потім він почав давати збій через шлюби. У 1980-х в медичних школа стало навчатися більше жінок, серед випускників з'явилось багато сімейних пар, а алгоритм не розрахований на це. Одному із подружжя він міг дати роботу в Орландо, а іншому — в Сан-Франциско. Пари почали відмовлятися від участі в розподілі і шукати роботу самостійно. Американський економіст Алвін Рот написав статтю, в якій довів, що неможливо створити алгоритм, який видав би стабільне парування для випадку з подружніми парами. Роту запропонували покращити існуючий алгоритм, щоб враховувати інтереси сімейних студентів. Вчений зумів модифікувати алгоритм, але він працює за умови, що пар не дуже багато. Ним користуються досі.

Після цього Роту запропонували робити інші алгоритми. Найвідоміший — алгоритм парування для ринку донорства нирок.

Є два типи донорства — звичайне (від людини, що загинула) і від живої людини. Продавати та купувати нирку за гроші легально не можна, а безкоштовно надати орган може лише близька людина. Щоб операція була успішною, донору та хворому потрібно пройти тест на сумісність крові та тканин. Проблема в том, що у родичів рівень відмови нової нирки підвищується. Отже, є люди, які потребують нирку особливого типу, і люди, які готові їм віддати свою, але їхні типи не співпадають. Можна спробувати знайти іншу пару, що знаходиться в подібній ситуації, але потрібно, щоб тип співпав у двох пар донорів і хворих, а це малоймовірно. Алгоритм Рота дозволив утворювати цілі ланцюжки донорів і хворих. Донори віддавали свою нирку хворому, якому вона підійде, а хворі отримували органи потрібного типу. 2003 року в США було всього 19 операцій від живих донорів, в 2017 їх стало 5300.

В 2012 році Алвін Рот та Ллойд Шеплі отримали Нобелівську премію по економіці за розробку теорії стійких парувань та застосування її до створення ринків.