Живая математика. Нематематическая книга о вдохновении, науке, образовании и жизни

А что же девушки на второй день? Они смотрят на вновь пришедших. И те девушки, которые в первый день одного из парней «придержали», сравнивают его с лучшим из вновь появившихся (если вообще кто-то появился). Если старый лучше всех новых, то он остается ждать и дальше, а новые посылаются; если лучший из новых лучше старого, то старый посылается вместе со всеми остальными, а лучший из новых занимает место старого. За одним исключением: если лучший из вновь пришедших — самый желанный для неё, то такая пара сразу же играет свадьбу. Те из девушек, которые послали всех в предыдущий день, решают задачу с чистого листа, как если бы это был первый день.

Так продолжается день за днём, вечер за вечером. Кто из парней «ангажирован» — ждёт до талого, пока его не пошлют или до тех пор, пока всякие хождения в деревне полностью не прекратятся. Кто послан, смотрит на свой список и решает, идти ли к третьей, четвертой и так далее, пока наконец не обнаружит, что все прочие не заслуживают чести быть его женой; такой парень остается навек одиноким.

Каждая девушка, пока ещё кто-то куда-то приходит и кто-то кого-то посылает, всякий раз решает задачу выбора «лучшего из доступных»: если хоть один раз ей подвернулся приемлемый вариант, она уже свою удачу не упустит и будет рядом держать кого-то — либо этого, либо даже более подходящего. Если же все время не везло и никто из мало-мальски приемлемых женихов так и не появился, девушка остаётся незамужней навсегда.

В конце концов наступит момент (это можно строго математически доказать!), когда хождения прекратятся. Кто-то остался навек холостым или незамужней, а кто-то сидит под дверями и ждёт. В этот момент все сидящие приглашаются внутрь соответствующих домов, и разом играются все такие свадьбы. На этом шаге алгоритм, описанный выше и носящий имя Гейла и Шепли, останавливается и заканчивает свою работу.

Можно доказать (это сделали Ллойд Шепли, вместе с уже ушедшим от нас в 2008 году Дэвидом Гейлом), что система заключенных подобным образом браков устойчива. В конечном итоге никто не женат насильно, и нигде не возникнет «разводной пары», то есть пары «мужчина — женщина», в которой оба участника предпочтут брак друг с другом текущему своему положению. После этого Старейшина, познакомившийся с теорией игр не понаслышке, может спокойно умирать.

Конечно, Нобелевская премия была вручена не за красивую сказку о бракосочетаниях. Просто этот алгоритм оказался чрезвычайно удобным при распределении студентов по университетам, учеников по колледжам, работников по фирмам и даже донорских органов по людям, в них кровно нуждающимся. Тогда и оценили его экономисты, правда, спустя целых полвека.

Однако нобелевский лауреат Ллойд Шепли знаменит не только этим алгоритмом: за 10 лет до этого, в 1953 году, он изобрёл так называемый «вектор Шепли», хотя более правильно было бы назвать его изобретение «дележом по Шепли», ибо предложенный Ллойдом Шепли метод помогает разделить выигрыши и затраты в спорных (конфликтных) ситуациях. А официальное его наименование звучит так: «Принцип справедливого распределения выигрыша между игроками в задачах кооперативной теории игр».

Давайте рассмотрим более подробно, как вектор Шепли помогает при решении различных бытовых проблем. Допустим, перед нами три ситуации.

1. Трое заключают круговую сделку по квартирам. Первому надо срочно оформить все бумаги (это стоит 30 тысяч рублей за неделю ожидания), второму это дело предстаёт в средней срочности (18 тысяч рублей за две недели), в то время как третий никуда не торопится (12 тысяч рублей за месяц ожидания). Оформляют срочно. Но кто сколько должен платить, чтобы распределение платежей было справедливым?

2. Трое музыкантов играют в переходе. Солистка Оля, барабанщик Гена и гитарист Паша втроем зарабатывают 130 рублей за час. Если Оля и Гена будут играть в паре, они за час заработают 60 рублей; Оля и Паша смогут заработать 70 рублей; Паша и Гена без Оли смогут получать в час всего 30 рублей. Поодиночке ребята могут заработать: Оля 40 рублей, Паша 20 рублей, Гена 10 рублей. Кто сколько должен получать из зарабатываемых ими 130 рублей в час, чтобы делёж был справедливым?

3. К новому коттеджному поселку прокладывается асфальтовая дорога от магистральной трассы. Стоимость строительства одного метра дороги равна 1 000 рублей, расстояния от магистрали до коттеджей равны соответственно 50 метров, 100 метров, 150 метров и 200 метров. Стоимость всей дороги — 200 тысяч рублей. Кто из жильцов какую часть стоимости дороги должен оплатить, опять-таки исходя из соображений справедливости?