остается навек одиноким.
Каждая девушка, пока ещё кто-то куда-то приходит и кто-то кого-то посылает, всякий раз решает задачу выбора «лучшего из доступных»: если хоть один раз ей подвернулся приемлемый вариант, она уже свою удачу не упустит и будет рядом держать кого-то — либо этого, либо даже более подходящего. Если же все время не везло и никто из мало-мальски приемлемых женихов так и не появился, девушка остаётся незамужней навсегда.
В конце концов наступит момент (это можно строго математически доказать!), когда хождения прекратятся. Кто-то остался навек холостым или незамужней, а кто-то сидит под дверями и ждёт. В этот момент все сидящие приглашаются внутрь соответствующих домов, и разом играются все такие свадьбы. На этом шаге алгоритм, описанный выше и носящий имя Гейла и Шепли, останавливается и заканчивает свою работу.
Можно доказать (это сделали Ллойд Шепли, вместе с уже ушедшим от нас в 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 рублей в час!
Так же легко можно решить и задачу про квартирную сделку, поняв, какие издержки понесла бы каждая из сторон, если бы была
