Клуб избранных союзов: рецепт стабильности по фон Нейману ✛
Восемьсот участников — фирмы и работники — выходят на рынок. Каждый держит в уме жёсткий список предпочтений. Задача: разбиться на пары так, чтобы никому не захотелось всё переиграть. В математике это называют кооперативной игрой с запретом на повторные союзы, а её корни уходят к работам Джона фон Неймана и Оскара Моргенштерна. Они описали стабильные множества — своего рода клуб избранных союзов, куда принимают только особые распределения партнёров. Но что именно входит в этот клуб, долго оставалось загадкой.
Войти в клуб непросто. Нужны два качества: внутренняя стабильность (члены клуба не свергают друг друга) и внешняя (любой аутсайдер проигрывает кому-то из клуба). На языке теории это стабильное множество фон Неймана–Моргенштерна. Исследователи задались вопросом: можно ли описать этот клуб, не перебирая бесчисленные комбинации? Ответ оказался изящным: нужно просто вычеркнуть из списка предпочтений все бесперспективные пары. Первая процедура, оптимизационная по сути, опирается на решёточную структуру ядра — множества распределений без улучшающих коалиций. Последовательно удаляя несовместимые варианты, она сохраняет лишь те отношения, что не рушат доминантную картину. Вторая процедура, эффективностно-ориентированная, отсеивает «пары-прерыватели», мешающие Парето-улучшениям. Объединение двух чисток даёт редуцированный профиль P* — коллективное зеркало доминантных связей.
Главный результат: стабильное множество единственно и в точности совпадает с ядром профиля P*. Иными словами, клуб избранных — это в точности все недоминируемые исходы в урезанной игре. Система доминантных связей устроена так, что любой исход вне клуба побеждается одним из его членов — и путь туда занимает не более трёх шагов. Экономия: чтобы найти стабильные пары, не нужно перебирать подмножества — достаточно применить две простые процедуры и взять ядро.
Открытие стирает границу между кооперативным и структурным взглядами на стабильность. Доминантные отношения теперь связаны с решёточной геометрией. Помимо теории, появляется практический алгоритм для распределения донорских органов, школьного выбора и сетевых рынков. А в перспективе — перенос метода на рынки «многие-к-одному» и изучение динамических систем, где агенты с децентрализованным принятием решений самостоятельно дрейфуют к стабильности. Оценка в три шага подсказывает: такой процесс сходится быстро. Так что восемьсот участников могут быть спокойны — их клуб предсказуем.
Лемму о декомпозиции — обычно инструмент только для ядра — здесь впервые распространили на любые внутренне устойчивые множества. Именно это обобщение позволило «нарезать» рынок на независимые IS-циклы и построить урезанный профиль.