Нуклеолюс, устойчивые коалиции и теория паросочетаний

Когда ядро недостаточно

Ядро — привлекательная концепция, но у неё есть два недостатка: оно может быть пустым (никакое устойчивое распределение не существует) и неединственным (много устойчивых распределений). Нуклеолюс и устойчивые множества — альтернативные концепции, каждая с особой логикой.

Нуклеолюс: минимизация недовольства

Для распределения x и коалиции S определим избыток e(S, x) = v(S) − Σᵢ∈S xᵢ. Положительный избыток: коалиция S может «сделать лучше» для себя, если отколется. Отрицательный: коалиция «в проигрыше» при отколе.

Нуклеолюс — распределение x, лексикографически минимизирующее вектор избытков всех коалиций, упорядоченных по убыванию. Сначала минимизируем максимальный избыток, затем при фиксированных максимально «довольных» — следующий, и т.д.

Шмайдлер (1969): нуклеолюс существует и единственен для любой игры. Если ядро непусто — нуклеолюс в нём.

Числовой пример: N = {1,2,3}, v({1,2}) = 60, v({1,3}) = 80, v({2,3}) = 40, v(N) = 100, v({i}) = 0.

Шаг 1. Из эффективности: x₁+x₂+x₃ = 100. Условия ядра: x₁+x₂ ≥ 60, x₁+x₃ ≥ 80, x₂+x₃ ≥ 40. Из x₁+x₂ ≥ 60 и x₁+x₃ ≥ 80: добавив, 2x₁+x₂+x₃ ≥ 140, т.е. x₁ ≥ 40. И x₂+x₃ = 100−x₁ ≤ 60. Но нужно x₂+x₃ ≥ 40 ✓. Ядро: x₁ ≥ 40, x₁+x₂ ≥ 60, x₁+x₃ ≥ 80.

Нуклеолюс находим минимизацией: при x₁+x₂+x₃=100 минимизируем max(60−x₁−x₂, 80−x₁−x₃, 40−x₂−x₃). Равнивая первые два: 60−x₁−x₂ = 80−x₁−x₃ → x₃−x₂ = 20. Из x₁+x₂+x₃=100 и равенства избытков: нуклеолюс ≈ (50, 20, 30). Проверка: e({1,2},nu) = 60−70 = −10; e({1,3},nu) = 80−80 = 0; e({2,3},nu) = 40−50 = −10.

Устойчивые множества фон Неймана–Моргенштерна

Фон Нейман и Моргенштерн (1944) предложили концепцию устойчивого множества V:

• Внутренняя устойчивость: Никакое распределение x ∈ V не доминирует y ∈ V (через некоторую коалицию S: Σᵢ∈S xᵢ ≤ v(S) и xᵢ > yᵢ для всех i ∈ S)
• Внешняя устойчивость: Для каждого x ∉ V найдётся y ∈ V, доминирующее x

Устойчивое множество интерпретируется как «социальная норма»: внутри неё нет конфликта, снаружи всегда есть альтернатива из V. Проблемы: V может быть несчётным, неединственным или не существовать (пример Лукаса, 1969).

Теория паросочетаний: рынки без цен

Паросочетание (matching) — распределение агентов двух типов: работодатели–работники, студенты–университеты. Нет явной цены — только предпочтения.

Задача о стабильном браке (Гейл–Шепли, 1962): N мужчин, N женщин, строгие предпочтения. Паросочетание μ стабильно, если нет «блокирующей пары» (m, w): m предпочитает w своей партнёрше И w предпочитает m своему партнёру.

Алгоритм DA (Deferred Acceptance): 1. Мужчины делают предложения своим лучшим выборам. 2. Каждая женщина «откладывает» лучшее предложение, отклоняет остальные. 3. Отклонённые предлагают следующей в списке. 4. Повторять до стабилизации.

Теорема: DA всегда завершается стабильным паросочетанием. Результат при предложениях от мужчин — M-оптимальное (лучшее для всех мужчин среди стабильных) и W-пессимальное.

Числовой пример: 3 мужчины (m₁, m₂, m₃) и 3 женщины (w₁, w₂, w₃).

Предпочтения мужчин: m₁: w₁>w₂>w₃; m₂: w₁>w₃>w₂; m₃: w₂>w₁>w₃. Предпочтения женщин: w₁: m₂>m₁>m₃; w₂: m₁>m₂>m₃; w₃: m₁>m₂>m₃.

Раунд 1: m₁ → w₁ (принимает, держит); m₂ → w₁ (принимает, держит m₂ вместо m₁! т.к. w₁: m₂>m₁); m₁ отклонён.

Раунд 2: m₁ → w₂ (принимает, держит); m₃ → w₂ (w₂: m₁>m₃ → w₂ держит m₁, отклоняет m₃).

Раунд 3: m₃ → w₁ (w₁ держит m₂, w₁: m₂>m₃ → отклоняет m₃).

Раунд 4: m₃ → w₃ (принимает). Финал: {m₁−w₂, m₂−w₁, m₃−w₃}.

Приложение: NRMP (распределение медицинских резидентов по больницам в США с 1952 года) и школьные распределения в NYC и Бостоне — DA-алгоритм Алвина Рота (Нобель 2012). Стабильные паросочетания обеспечивают системную устойчивость: при нестабильном распределении блокирующие пары «разрывают» официальные назначения — именно это наблюдалось до внедрения DA-механизма. Устойчивость — ключевое свойство, делающее алгоритм Гейла–Шепли практически применимым в реальных рынках с двусторонними предпочтениями.

Ядро и нуклеолюс в разделе затрат и переговорах о слиянии

Концепции ядра и нуклеолюса непосредственно применяются в переговорных процессах и разделе затрат. При строительстве совместной инфраструктуры (водопровод, дорога, линия электропередачи) между несколькими пользователями ядро задаёт диапазон приемлемых распределений затрат: ни одна подгруппа пользователей не должна платить больше, чем стоило бы ей строить объект самостоятельно. Нуклеолюс минимизирует максимальное «недовольство» коалиций и даёт уникальное решение даже когда ядро пусто. В переговорах о корпоративных слияниях ядро очерчивает диапазон справедливого распределения синергий между объединяющимися сторонами: предложение вне ядра будет отклонено, поскольку одна из сторон может добиться большего без объединения. В международных торговых блоках нуклеолюс используется для установления квот и компенсационных выплат между странами-членами. Вопрос о непустоте ядра (ядро существует тогда и только тогда, когда игра сбалансирована, по теореме Бондаревой–Шепли) определяет, возможно ли стабильное сотрудничество или оно неизбежно распадётся. Симплексное программирование используется для вычисления нуклеолюса в больших играх.

Ядро и нуклеолюс вычисляются через линейное программирование: ядро — множество решений системы неравенств (по числу коалиций), нуклеолюс — минимаксный вектор избытков, находимый лексикографической минимизацией. Программный пакет gambit и библиотеки Python (nashpy, pycmptgame) реализуют эти алгоритмы и используются в академических и практических расчётах ценообразования инфраструктурных проектов.

Задание: Для игры N={1,2,3}: v({1,2})=60, v({1,3})=80, v({2,3})=40, v(N)=100. Найдите ядро и нуклеолюс. Совпадают ли они?