Гладиаторы, пираты и игры на доверии. Как нами правят теория игр, стратегия и вероятности | страница 38

В двух словах: алгоритм завершается, у каждого есть супруг, и пары стабильны.

А что, если женщины будут выбирать себе фаворитов? Наш пример с актерами даст те же самые пары: здесь у нас только одно стабильное сочетание.

Впрочем, так будет не всегда. Когда стабильных сочетаний несколько, а выбор совершают женщины, формирование пар проходит иначе.

Война полов: следующий раунд

Время вернуться к примеру, с которого началась эта глава, и напомнить себе о предпочтениях мужчин и женщин.

Предпочтения мужчин:

Рон: Нина, Джина, Йоко

Джон: Джина, Йоко, Нина

Пол: Йоко, Нина, Джина

Предпочтения женщин:

Нина: Джон, Пол, Рон

Джина: Пол, Рон, Джон

Йоко: Рон, Джон, Пол

С первого же взгляда понятно, что на этот раз потребуется только один раунд. Мужчины делают предложение фавориткам, и пары выглядят так: Рон – Нина, Джон – Джина и Пол – Йоко. Вот и все. Они определенно стабильны, ведь все мужчины нашли женщин своей мечты. Для мужчин это оптимальное решение. Впрочем, каждой женщине выпал спутник, которого она в своем списке определила в «аутсайдеры», и вряд ли можно сказать, что женщины счастливы.

Если предложение будут делать женщины, единственный раунд даст следующие пары: Йоко – Рон, Джина – Пол и Нина – Джон. Здесь каждая получает своего фаворита, а мужчинам предстоит провести всю жизнь с теми, кого они в своих списках оценили ниже всех.

Итак, можно увидеть, что игра дает преимущество тем, кто делает предложение в первом раунде.

(Кстати, здесь у нас есть еще один стабильный вариант формирования пар: Нина – Пол, Джина – Рон и Йоко – Джон. Прошу, проверьте эту стабильность – иными словами, убедитесь, что в этом случае не будет измен.)

Футболисты без моделей

Алгоритм Гейла – Шепли не сложен, но и не тривиален. Если мы оставим в стороне предпосылку о двух полах и предположим, что четверо футболистов должны провести ночь перед важным матчем в номерах для двоих, возможно, у нас не получится найти стабильное решение в выборе подходящего соседа по комнате.

Проверьте – и увидите: здесь не получится никаких стабильных пар.

И Нобелевскую премию получает…

Есть много сфер, где можно применить алгоритм Гейла – Шепли. Самая знаменитая – это назначение выпускников медицинских школ в больницы для прохождения интернатуры. Готов биться об заклад: вы уже догадались, что больницы получили право предлагать первыми (и по этому вопросу еще и сейчас ведутся судебные тяжбы). Другое важное применение «стабильного брака» – приписывание пользователей к серверам в интернете.