Происходило это давным-давно. Высоко в горах, отрезанная от остального мира, расположилась деревня. На протяжении долгих лет управлял ею один и тот же Старейшина, мудрый и справедливый. При нем народилось много девушек и молодых парней, но все без исключения девушки были влюблены в Старейшину и не выходили из-за этого замуж. В конце концов настал ему час помирать. И вот он собрал всех жителей деревушки, и говорит: «Чтобы жизнь в деревне продолжалась, надо вам пережениться да детей нарожать. А чтобы мир да покой был, я вас сейчас так переженю, чтобы потом, когда я помру, никто не развелся и заново бы не женился».
Затем Старейшина позвонил по спутниковому телефону нобелевскому лауреату Ллойду Шепли и долго разговаривал с ним, не жалея денег.
И приказал он всем молодым людям, равно как и всем девушкам, составить список представителей противоположного пола, в порядке убывания привлекательности в качестве будущего супруга.
Неволить никого не велел, и если, скажем, для девушки Анны выйти за Сергея было горше одиночества, то так и велел в списке пометить.
Затем он велел со списками поступить следующим образом. В тот же день и час каждый парень должен был постучаться в дверь к своей самой желанной даме (кроме тех, кто пометили в своих записях, что они убежденные холостяки). Как можно догадаться, у некоторых девушек у двери возникло целое столпотворение, а у некоторых — никого, хоть шаром покати.
Кроме того, некоторые девушки, выглянув в окошко, с разочарованием обнаружили, что хоть и много мужиков собралось, но не больно-то она за кого из них замуж хочет. Что поделать, судьба бывает злой!
Дальше Старейшина приказал всем девушкам, которые в принципе хотят замуж (то есть с непустыми списками женихов), осуществить следующее:
1) выяснить, есть ли среди постучавшихся к ним самый желанный жених. Если есть, то всех прочих прогонять и свадьбу играть;
2) если нет, то проверить, есть ли среди постучавшихся хоть один вообще приемлемый жених, и если нет, то всех прогнать;
3) если приемлемые варианты есть, но самого лучшего нет, то одного наиболее приемлемого оставить, остальных прогнать — но свадьбу пока не играть!
Теперь расклад в деревне таков: все парни, кто хотел жениться, либо женились (это кому из парней так повезло, что его самая желанная невеста на первое место поставила также его), либо посланы прочь, либо ждут решения у дверей первой из их избранниц.
На следующий день ситуация повторяется, однако с небольшими изменениями: те, кто ждут у дверей, никуда не рыпаются, а ждут дальше. Те, кто счастливо женились, вообще «выходят из игры». А вот те, кто был вчера послан, смотрят на свои списки и решают, идти ли ко второй («второй сорт не брак, то есть в нашем контексте — тоже брак!») или же остаться навек холостым (в том случае, если приемлемым вариантом для брака у парня была одна-единственная самая желанная невеста).
Те, кто жениться всё же хочет, идут ко второй невесте в своём списке. И вновь женихи оказываются как-то раскиданными по порогам домов прекрасной половины деревни.
А что же девушки на второй день? Они смотрят на вновь пришедших. И те девушки, которые в первый день одного из парней «придержали», сравнивают его с лучшим из вновь появившихся (если вообще кто-то появился). Если старый лучше всех новых, то он остается ждать и дальше, а новые посылаются; если лучший из новых лучше старого, то старый посылается вместе со всеми остальными, а лучший из новых занимает место старого. За одним исключением: если лучший из вновь пришедших — самый желанный для неё, то такая пара сразу же играет свадьбу. Те из девушек, которые послали всех в предыдущий день, решают задачу с чистого листа, как если бы это был первый день.
Так продолжается день за днём, вечер за вечером. Кто из парней «ангажирован» — ждёт до талого, пока его не пошлют или до тех пор, пока всякие хождения в деревне полностью не прекратятся. Кто послан, смотрит на свой список и решает, идти ли к третьей, четвертой и так далее, пока наконец не обнаружит, что все прочие не заслуживают чести быть его женой; такой парень остается навек одиноким.
Каждая девушка, пока ещё кто-то куда-то приходит и кто-то кого-то посылает, всякий раз решает задачу выбора «лучшего из доступных»: если хоть один раз ей подвернулся приемлемый вариант, она уже свою удачу не упустит и будет рядом держать кого-то — либо этого, либо даже более подходящего. Если же все время не везло и никто из мало-мальски приемлемых женихов так и не появился, девушка остаётся незамужней навсегда.
В конце концов наступит момент (это можно строго математически доказать!), когда хождения прекратятся. Кто-то остался навек холостым или незамужней, а кто-то сидит под дверями и ждёт. В этот момент все сидящие приглашаются внутрь соответствующих домов, и разом играются все такие свадьбы. На этом шаге алгоритм, описанный выше и носящий имя Гейла и Шепли, останавливается и заканчивает свою работу.
Можно доказать (это сделали Ллойд Шепли, вместе с уже ушедшим от нас в 2008 году Дэвидом Гейлом), что система заключенных подобным образом браков устойчива. В конечном итоге никто не женат насильно, и нигде не возникнет «разводной пары», то есть пары «мужчина — женщина», в которой оба участника предпочтут брак друг с другом текущему своему положению. После этого Старейшина, познакомившийся с теорией игр не понаслышке, может спокойно умирать.
Конечно, Нобелевская премия была вручена не за красивую сказку о бракосочетаниях. Просто этот алгоритм оказался чрезвычайно удобным при распределении студентов по университетам, учеников по колледжам, работников по фирмам и даже донорских органов по людям, в них кровно нуждающимся. Тогда и оценили его экономисты, правда, спустя целых полвека.
Однако нобелевский лауреат Ллойд Шепли знаменит не только этим алгоритмом: за 10 лет до этого, в 1953 году, он изобрёл так называемый «вектор Шепли», хотя более правильно было бы назвать его изобретение «дележом по Шепли», ибо предложенный Ллойдом Шепли метод помогает разделить выигрыши и затраты в спорных (конфликтных) ситуациях. А официальное его наименование звучит так: «Принцип справедливого распределения выигрыша между игроками в задачах кооперативной теории игр».
Давайте рассмотрим более подробно, как вектор Шепли помогает при решении различных бытовых проблем. Допустим, перед нами три ситуации.
1. Трое заключают круговую сделку по квартирам. Первому надо срочно оформить все бумаги (это стоит 30 тысяч рублей за неделю ожидания), второму это дело предстаёт в средней срочности (18 тысяч рублей за две недели), в то время как третий никуда не торопится (12 тысяч рублей за месяц ожидания). Оформляют срочно. Но кто сколько должен платить, чтобы распределение платежей было справедливым?
2. Трое музыкантов играют в переходе. Солистка Оля, барабанщик Гена и гитарист Паша втроем зарабатывают 130 рублей за час. Если Оля и Гена будут играть в паре, они за час заработают 60 рублей; Оля и Паша смогут заработать 70 рублей; Паша и Гена без Оли смогут получать в час всего 30 рублей. Поодиночке ребята могут заработать: Оля 40 рублей, Паша 20 рублей, Гена 10 рублей. Кто сколько должен получать из зарабатываемых ими 130 рублей в час, чтобы делёж был справедливым?
3. К новому коттеджному поселку прокладывается асфальтовая дорога от магистральной трассы. Стоимость строительства одного метра дороги равна 1 000 рублей, расстояния от магистрали до коттеджей равны соответственно 50 метров, 100 метров, 150 метров и 200 метров. Стоимость всей дороги — 200 тысяч рублей. Кто из жильцов какую часть стоимости дороги должен оплатить, опять-таки исходя из соображений справедливости?
Общее в этих проблемах то, что «топорное» деление поровну не видится справедливым вариантом ни в одной из них. В первом случае кто торопится, тот пускай и платит больше, не правда ли? Во втором сюжете девушка Оля явно имеет перед ребятами преимущество, они без неё почти что никуда, а значит, она должна, по идее, получать больше их обоих. В третьем случае жители более далёких коттеджей накладывают большие финансовые затраты на общий проект.
В то же время, во всех трёх историях с ходу совершенно непонятно, насколько больше должны платить/получать одни по сравнению с другими.
Именно здесь нам и пригодится механизм, названный «вектором Шепли». Шепли также предложил систему из четырёх аксиом, или требований, которым должен удовлетворять механизм дележа, и доказал, что тот принцип, который мы ниже опишем, является единственным принципом дележа, удовлетворяющим этим четырем аксиомам.
Вот как работает «вектор Шепли».
Участники проблемной ситуации выстраиваются в линейку, один за другим. Например: Оля, потом Гена, потом Паша. Оля берет себе то, что может заработать в одиночку, то есть 40 рублей. Затем Гена берет себе весь дополнительный выигрыш, который он привнесёт поющей Оле, присоединившись к ней со своими барабанами: 60 рублей минус 40 рублей, то есть 20 рублей. Пришедший третьим Паша забирает оставшиеся 70 рублей (130 минус 60).
И это все? Конечно же, нет! Паша «оторвал куш» от того, что ему посчастливилось быть последним. Если бы третьей появилась Оля, то она бы получила не 40, а целых 100 рублей (130 минус 30)! Поэтому от порядка появления музыкантов зависит и результат деления заработанных 130 рублей в час.
Как же тогда поступить? Шепли предложил самый простой и понятный способ: перечислить все способы упорядочения (выстраивания в линейку) участников, для каждого способа вычислить, кому сколько досталось, и потом просто усреднить три полученных вектора дележа. Если участника три, то способов упорядочения 6 (= 3 × 2 × 1, так называемый «3-факториал»), и задача решается довольно быстро.
Решим ее для наших музыкантов.
Линейка 1:
Оля, Гена, Паша.
Оле 40, Гене 20, Паше 70.
Линейка 2:
Оля, Паша, Гена.
Оле 40, Паше 30, Гене 60.
Линейка 3:
Гена, Оля, Паша.
Гене 10, Оле 50, Паше 70.
Линейка 4:
Паша, Оля, Гена.
Паше 20, Оле 50, Гене 60.
Линейка 5:
Гена, Паша, Оля.
Гене 10, Паше 20, Оле 100.
Линейка 6:
Паша, Гена, Оля.
Паше 20, Гене 10, Оле 100.
Теперь Оля получает среднее из (40, 40, 50, 50, 100, 100), то есть (40 + 40 + 50 + 50 + 100 + 100)/6 = 380/6 — чуть больше 63 рублей (почти половину заработанных ребятами денег!), Гена — (20 + 60 + 10 + 60 + 10 + 10)/6 = 170/6 — чуть меньше 29 рублей, а Паша — 70 + 30 + 70 + 20 + 20 + 20)/6 = 230/6 — чуть меньше 39 рублей. В сумме как раз 130 рублей в час!
Так же легко можно решить и задачу про квартирную сделку, поняв, какие издержки понесла бы каждая из сторон, если бы была одна или в паре с какой-то другой. А вот задачу про коттеджи в лоб решать долго: вариантов упорядочить четырех участников — 4 × 3 × 2 × 1 = 4! (обозначение для числа «4-факториал») — целых 24 способа!
Впрочем, у задачи с коттеджами существует «обходной приём». Можно доказать, что при делении по Шепли в этой задаче нужно дорогу разделить на 4 равных участка по 50 метров. За первый из них все платят поровну (по 50/4 = 12,5 тыс. рублей каждый), за второй платят только те трое, которые по нему ездят (по 50/3, то есть примерно по 17 тыс. рублей каждый), за третий — двое последних по 25 тыс, и последний участок целиком оплатит хозяин последнего коттеджа. Таким образом, например, третий хозяин заплатит 50/4 + 50/3 + 50/2 тыс. рублей, то есть приблизительно 55 тыс, а последний — целых 105 тыс. рублей. Но и первые двое не будут кататься совсем уж бесплатно.
А задачку про квартирную сделку советую решить самостоятельно, чтобы разобраться, что к чему. Есть еще целый ряд занимательных сюжетов, связанных с вектором Шепли. Например, по этому алгоритму можно рассчитать переговорную силу пяти основных и десяти сменных участников Совета Безопасности ООН. Сила каждого из этих десяти «временщиков» равняется 1/1330, в сумме — 1/133 от общей переговорной силы, взятой за единицу.
Как говорится, здесь есть о чём призадуматься!