Итак, что же делать, если ядро пусто? Решение-то нужно иметь в любом случае, независимо то того, пусто оказалось ядро или не пусто. У нас есть игра, есть некий конфликт, конфликт надо как-то решить. Ну вот, есть такой метод, за который в 2012 году Ллойд Шепли получил Нобелевскую премию. За него и еще за одно изобретение, о котором речь пойдет в другой раз. Шепли. Метод называется «вектор Шепли», хотя 2012 год это Нобелевская премия, а изобретение датируется, наверное, 1963 год, то есть это один из чемпионов по количеству лет, которые прошли до получения Нобелевской премии. Я бы назвал это «дележ Шепли», а не «вектор Шепли». Ну, «вектор» в смысле, что любой дележ является вектором. Итак, пусть у нас есть совершенно произвольная игра. Что предложил Шепли? Он предложил взять игроков, упорядочить их произвольным образом и впускать, так сказать, в аудиторию по одному. Или в подземный переход, как этих музыкантов наших. Впускают первого. Он начинает там, например, петь. Впускают второго. Они вместе начинают что-то делать и тем самым второй добавляет какой-то дополнительный выигрыш первому. Затем запускают третьего и они уже выступают все втроем, и этот третий получает тоже дополнительный выигрыш, который он привнес в компанию предыдущих двух. Вот. Значит, если такой вектор предложить, то встанет вопрос о том, что такой дележ зависит, естественно, от порядка. Поэтому Шепли предложил усреднить на множестве всех порядков, всех упорядочений игроков. То есть, вектор Шепли – это 1 / n! * сумму дележей, построенных таким образом. Для каждого порядка построен свой собственный вектор дележа. Их суммируют и делят на n!. В случае, когда у нас три игрока, n! = 6. Поэтому речь идет о соответствующем усреднении шести разных векторов дележа, в зависимости от того, в каком порядке они входят. Давайте посмотрим, что будет, например, в этом случае, в котором у нас ядро оказалось пустым. Значит, нужно перечислить все порядки. ABC BAC ACB BCA CAB и CBA. Давайте аккуратно распишем [БЕЗ СЛОВ] какой дележ, какой вектор получится в каждой строчке. После чего просуммируем и поделим на 6. На самом деле, цифры, которые здесь выписаны, исходно подбирались так, чтобы они все делились на 6. Поэтому имеет смысл делить на 6 сразу же и потом просто просуммировать. Ну, например, берем A. Входит A и поет. Это 18. Делим на 6, получаем 3. Затем входит B. Они вместе с A исполняют вот такую вот партию «A поет, B играет» и это 114. Делим на 6, получается 19. 19 – это вместе. После чего мы вычитаем из 19 – 3 и получаем, что C прибавил 16 к их команде. Потом заходит последний и добавляет еще 1. То есть он добавляет 6, но мы сразу поделили на 6. Проверяем: 3 + 16 + 1 = 20. Все правильно – это 1/6 от 120. Сейчас будет 6 векторов-дележей, каждый из которых суммируется к 20. Их сумма она как раз и задает вектор Шепли. Ну давайте ее выясним. Теперь B заходит. 12. Итого 2. После этого заходит A. Надо, кстати, быть очень аккуратным, потому что часто студенты путаются и вначале сюда вносят... вот B заходит, пишут прибавку не B, а A. То, что B заходит первый, но он, естественно, вносит себе, а не A. A заходит второй и привносит остаток до 19, то есть 17. Потом заходит C и привносит 1. Потом, значит, опять первым заходит A, вторым заходит уже C, и они вместе 108 / 6 = 18. Значит C добавляет 15 очков. И зашедший последним B добавляет 2. Теперь зашел B. Мы уже знаем, что когда первым заходит B, это 2. Но теперь нужно вычесть из BC. BC это 30 / 6 = 5. Значит C ему добавляет 3. Остальные 15 получает A, заходя последним. Теперь C заходит, получает 1. Вслед за ним заходит A, получает 17. И заходит B, получает 2. Ну и наконец, заходит C, получает 1. Заходит B, получает 4. Заходит A, получает 15. Это надо просуммировать и получить вектор Шепли, который в данном случае окажется равен 70, 28 и 22. Проверяем: сумма равна 120. Все правильно. Ну вот пожалуйста, вот вам решение. Решение будет оспорено. Решение Шепли будет оспорено, естественно, потому что ядро пусто, значит любое решение оспаривается. В частности это решение кем будет оспорено? Ну, например, группой A и B. Они здесь в сумме 98 получают, но они же могут получить 114. Поэтому решение это будет оспорено. Но мы знаем, что если мы будем настаивать на том, чтобы решение не было оспорено, то мы далеко не придем. Вот. Теперь давайте рассмотрим несколько других ситуаций, интересных довольно. Во-первых, какой вектор Шепли получится у нас в нашей исходной задаче про музыкантов вот с такими цифрами? Ответ: если мы проделаем все то же самое, вектор Шепли получится 86, 56, 38. 86, 56, 38. Я предлагаю всем слушателям самостоятельно это проделать. Давайте посмотрим, где он лежит? 86, 56, 38. Значит, всего 180, а мы отсчитываем 86 – это чуть меньше половины, да? То есть с точки зрения A это где-то вот тут. Теперь B – 56, это чуть-чуть меньше 1/3. Вот. Ну и получается, что тем самым по C должно получиться, ой, по B, неправильно, вот 56 меньше 1/3, и по C должно получиться 38. Ну, в общем, если внимательно на это посмотреть, окажется, что он лежит в ядре. Ну так, где-то не в самом центре ядра он где-то лежит, значит, здесь вот в ядре. Ну, а что такое центр ядра? Что означает вообще слово «центр», если есть некоторый многогранник? В дальнейшем мы увидим, что значению слова «центр» для некоторого класса игр можно придать смысл. И для этого класса игр, в котором есть смысл понятия «центр», вот эта вот игра, которую мы здесь выписали, она будет принадлежать к этому классу игр и в этом смысле вектор Шепли будет лежать в центре. Но пока просто отметим, что он попал в ядро, а потом мы к этому вопросу вернемся. Ну хорошо, итог: ядро может быть пустым. Тогда мы переходим, например, к вектору Шепли как к естественной концепции. И не смущаемся тем, что некоторые коалиции блокируют такой дележ. Ну, ничего страшного, нужно как-то попробовать их убедить, чтобы они его не блокировали. Ядро может быть не пустым, вектор Шепли может в нем лежать. Вопрос: а может ли быть так, что ядро не пусто, а вектор Шепли в нем не лежит? Ответ: к сожалению, может. В качестве упражнения предлагаю проверить, что если вот здесь заменить 120 на 132, то ядро в этой игре окажется не пустым. Но так как на любой платеж в ядре накладывается ограничение Xa ≤ 102, ≥ 18, когда мы начнем вычислять вектор Шепли, проверьте, что в нем значение у A = 105, то есть оно выпадает за пределы допустимых. Поэтому у этой игры не пустое ядро, есть естественный вектор Шепли, как и у любой игры, но вектор Шепли в ядре не лежит. Кстати, на всякий случай, ну вот, типичный элемент в ядре у этой игры новой будет такой: 100, 20 и 12. Можете проверить, что здесь никаких нарушений нет, ни одна коалиция не хочет блокировать этот дележ. И вот тогда действительно неизвестно, что делать. Потому что посмотрите какая ситуация: ядро не пусто и есть такие дележи, которые никем не блокируются. А вектор Шепли при этом дает элемент не в ядре, то есть вектор Шепли блокируется. Мы его вычисляем, но он блокируется некоторой коалицией. И тогда совершенно непонятно, брать ли его в качестве решения или какой-нибудь элемент ядра. И более того, ответ на этот вопрос полностью открыт – тут ничего нельзя сказать, наука здесь сказать ничего не может. Она может сказать: «ну вот хотите – берите вектор Шепли, который не лежит в ядре, хотите – берите что-нибудь из ядра». Здесь интересным ответом был бы такой ответ: что игра эта плохая, она не относится к некоторому специальному хорошему классу игр. Ну вот об этом хорошем классе игр мы и поговорим в следующем сюжете.
