Как найти вектор шепли - Исправление недочетов и поиск решений вместе с Examum.ru

Вектор Шепли

В этом параграфе мы отдельно рассмотрим еще один подход к поиску оптимальных решений кооперативных игр, предложенный Л. Шепли и ставший на сегодняшний день наиболее распространенным на практике. Этот подход основан на принципе «справедливого дележа» исходя из вклада каждого игрока в выигрыш коалиции.

Вкладом /-го игрока называется величина v(K,) — v где v — характеристическая функция кооперативной игры. То есть вклад игро- [1]

ка — это приращение выигрыша коалиции при его участии по сравнению с выигрышем коалиции без этого игрока.

Вектор Шепли, или значение Шепли (Shapley value) Ф(г) =(Фь Ф„), представляет собой распределение, в котором выигрыш каждого игрока Ф, равен его среднему вкладу в соответствующие коалиции К. В форме, практически реализуемой для расчетов, значение Шепли для каждого игрока имеет вид

где п — число игроков;

к — число участников коалиции К.

Вектор Шепли удовлетворяет следующим свойствам (аксиомы Шепли).

1. Линейность (аксиома агрегации). Ф(г) представляет собой линейный оператор, т.е. для любых двух игр с характеристическими функциями и и со:

для любой игры с характеристической функцией v и для любого а

Это свойство показывает, что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.

2. Симметричность (аксиома симметрии). Получаемый игроком выигрыш не зависит от его номера. Это означает, что если игра со получена из игры v перестановкой игроков, то ее вектор Шепли Ф(со) есть вектор Ф(и) с соответствующим образом переставленными элементами. То есть игроки, одинаково входящие в игру, должны получать одинаковые выигрыши.

3. Аксиома эффективности. При распределении общего выигрыша не должно выделяться ничего «бесполезному игроку», не вносящему вклада ни в какую коалицию. В теории кооперативных игр такой игрок называется болваном, т.е. для такого игрока i для любой коалиции К, содержащей /, выполняется v(K) — v( К/i) = 0 и соответственно Ф,=0. Благодаря этому свойству вектор Шепли позволяет полностью распределить имеющийся в распоряжении тотальной коалиции выигрыш, т.е. сумма компонент вектора Ф(и) равна v(N). Иными словами, при разделении общего выигрыша коалиции ничего не выделяется на долю «посторонних» игроков, не принадлежащих этой коалиции, но и ничего не взимается с них.

Приведем пример игры с «болваном». В игре трех лиц характеристические функции определяются следующим образом: г(1) = 0;

г(2)=г>(3) = 1;г>(12)=г(13) = 1; г(23) = 3; ь'(123) = 3. Вэтой игре игрок 1 — «болван».

Доказано (теорема Шепли), что для любой кооперативной игры существует единственное распределение выигрыша, удовлетворяющее аксиомам 1—3, и это распределение — вектор Шепли. Если вектор Шепли принадлежит с-ядру, то этот дележ одновременно справедлив и устойчив, но вектор Шепли может и не принадлежать непустому с-ядру.

Пример 4.2. Четыре акционера имеют следующее количество акций: 10, 20, 30 и 40 соответственно. Любое решение утверждается акционерами, имеющими в сумме большинство акций (> 50). Это решение считается выигрышем, равным 1. Поэтому данная ситуация может рассматриваться как простая игра четырех игроков, в которой выигрывающими коалициями являются следующие: <2; 4>, <3; 4>, <1; 2; 3>, <1; 2; 4>, <2; 3; 4>, <1; 3; 4>, <1; 2; 3; 4>. Необходимо найти оптимальный дележ выигрыша между акционерами.

Найдем вектор Шепли для этой игры. Вначале рассмотрим все коалиции, выигрывающие с игроком 1, но не выигрывающие без него. Имеется только одна такая коалиция: <1; 2; 3>, поэтому вектор Шепли для этого игрока содержит всего одно слагаемое. В данной коалиции три игрока, и вектор Шепли для игрока 1 определяется как

Далее определяем все выигрывающие коалиции, но не выигрывающие без игрока 2: <2; 4>, <1; 2; 3>, <2; 3; 4>. Поэтому

В результате получаем вектор Шепли

Отметим, что если считать распределение выигрыша среди акционеров традиционно, т.е. пропорционально количеству имеющихся у них акций, то получим следующее распределение: , отличающееся от вектора Шепли, в котором выигрыши игроков 2 и 3 равны, хотя игрок 3 имеет больше акций. Это получается из-за того, что возможности образования коалиций у игроков 2 и 3 одинаковы. Для игроков 1 и 2 выигрыши соответствуют их различию в количестве имеющихся акций.

Как всем пережениться (одно-, дву- и трёхполые браки) с точки зрения математики и почему мужики всегда в выигрыше

В 2012 году Нобелевскую премия по экономике выдали Ллойду Шепли и Элвину Роту. «За теорию стабильного распределения и практики устройства рынков». Алексей Савватеев в 2012 году попытался просто и понятно рассказать в чем суть заслуг математиков. Предлагаю вашему вниманию конспект видеолекции.

Сегодня будет теоретическая лекция. Про эксперименты Эла Рота, в частности с донорством, я не буду рассказывать.

Когда объявили, что Ллойд Шепли (1923-2016) получил нобелевку, был стандартный вопрос: «Как!? Он ещё жив. » Самый знаменитый его результат был получен в 1953 году.

Формально, премию дали за другое. За работу 1962 года за «теорему об устойчивом бракосочетании»: «Приём в колледжи и стабильность брака» (College Admission and the Stability of Marriage).

Об устойчивом бракосочетании

Matching (мэтчинг) — задача о нахождении соответствия.

Есть некая изолированная деревня. Там «m» молодых людей и «w» девушек. Нужно их друг на друге переженить. (Не обязательно одинаковое количество, может в итоге кто-то останется один.)

Какие нужно сделать предпосылки в модели? Что не просто наугад переженить. Делается некий шаг в сторону свободного выбора. Допустим есть мудрый аксакал, который хочет так переженить, чтоб после его смерти не начались разводы. (Развод, это ситуация, когда муж хочет в жены стороннюю женщину больше, чем жену.)

Эта теорема в духе современной экономики. Она исключительно бесчеловечна. Экономика традиционно бесчеловечна. В экономике человек заменен на машину по максимизации прибыли. То что я буду рассказывать — совершенно безумные вещи с точки зрения морали. Не принимайте близко к сердцу.

Экономисты смотрят на брак так.
m₁, m₂,… m_k — мужчины.
w₁, w₂,… w_L — женщины.

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

Всё происходит в обе стороны, у девушек то же самое.

Начальные данные произвольные. Единственное предположение/ограничение — мы не меняем своих предпочтений.

Теорема: Независимо от распределения и уровня нуля, всегда существует способ установить взаимно однозначное соответствие между частью мужчин и частью женщин, так, что оно будет устойчиво по отношению к любым видам расколов (не только разводов).

Какие могут быть угрозы?

Есть пара (m,w), которая не находится в браке. Но для w текущий муж хуже чем m, а для m текущая жена хуже, чем w. Это неустойчивая ситуация.

Есть еще вариант, что кого-то женили на том, кто «ниже нуля», в этой ситуации тоже брак распадется.

Если женщина в браке, но ей больше нравится неженатый, для которого она выше нуля.

Если два человека, оба не в браке, и оба друг для друга «выше нуля».

Утверждается, что для любых начальных данных такая система браков существует, устойчивая ко всем видам угроз. Во-вторых, алгоритм нахождения такого равновесия очень прост. Соизмерим с M*N.

Эту модель обобщили и расширили до «многоженства» и применили во многих областях.

Процедура Гейла-Шепли

Если все мужчины и все женщины будут выполнять «предписания», то результирующая система бракосочетания окажется устойчивой.

Предписания.
Берем несколько дней, сколько понадобится. Каждый день разбиваем на две части (утро и вечер).

В первое утро каждый мужчина отправляется к своей самой лучшей женщине и стучится в окошко, предлагая ей выйти за него замуж.

Вечером того же дня ход переходит к женщинам.Что может обнаружить женщина? Что под окном у неё толпа, либо один, либо ни одного мужчины. Те, у кого никого не оказалось сегодня, пропускают ход, ждут. Остальные, у кого есть хотя бы один, проверяют пришедших мужчин на то, что они «выше уровня нуля». Чтобы был хотя бы один. Если совсем не повезло и все ниже нуля, тогда всех надо послать. Женщина выбирает максимального из пришедших, говорит ему подождать, а остальных посылает.

Перед вторым днем ситуация такая — у некоторых женщин сидит один мужчина, у некоторых ни одного.

Во второй день всем «свободным» (посланным) мужчинам нужно идти ко второй по приоритету женщине. Если такой нет, то мужчина объявляется холостым. Тем мужчинам, которые уже сидят у женщин, пока ничего не делают.

Вечером женщины смотрят на ситуацию. Если к тому кто уже сидел присоединился более приоритетный, то менее приоритетного отправляют прочь. Если пришедшие ниже, чем уже имеющийся — все отсылаются. Женщины каждый раз выбирают максимальный элемент.

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

Можно ли прогнать весь этот процесс, но чтоб женщины бегали к мужчинам? Процедура симметричная, но решение может быть другим. Но вот вопрос, кому от этого лучше?

Теорема. Рассмотрим не только эти два симметричных решения, но множество всех устойчивых систем бракосочетания. Исходный предложенный механизм (мужчины бегают, а женщины соглашаются/отказываются) приводит к системе бракосочетаний, которая лучше для любого мужчины, чем любая другая и хуже, чем любая другая для любой женщины.

Однополые браки

Рассмотрим ситуацию с «однополыми браками». Рассмотрим математический результат, который ставит под сомнение необходимость их легализовать. Идеологически некорректный пример.

Рассмотрим четырёх гомосексуалистов a, b, c, d.

приоритеты для a: bcd
приоритеты для b: cad
приоритеты для c: abd
для d не имеет значение как он ранжирует оставшихся трёх.

Утверждение: в этой системе нет устойчивой системы бракосочетаний.

Сколько есть систем для четырёх людей? Три. ab cd, ac bd, ad bc. Пары будут разваливаться и процесс зациклится.

«Трёхполые» системы.
Это важнейший вопрос, который открывает целую область математики. Этим занимался мой коллега в Москве — Владимир Иванович Данилов. «Брак» он рассматривал как распитие водки и роли были такие: «разливающий», «говорящий тост» и «тот, кто нарезает колбасу». В ситуации, когда представителя каждой роли 4 и больше — невозможно решить перебором. Вопрос об устойчивой системе — открытый.

Вектор Шепли

В коттеджном поселке решили заасфальтировать дорогу. Нужно скинуться. Как?

Шепли в 1953 году предложил решение этой задачи. Предположим ситуацию конфликта с группой лиц N=<1,2. n>. Нужно разделить издержки/выигрыши. Допустим люди сообща сделали что-то полезное, продадут и как разделить прибыль?

Шепли предложил при дележе руководствоваться тем, сколько могли бы получить те или иные подмножества этих людей. Сколько денег смогли бы заработать все 2 N непустых подмножества. И на основе этой информации Шепли написал универсальную формулу.

Пример. Солист, гитарист и барабанщик играют в подземном переходе в Москве. Втроем они зарабатывают 1000 рублей в час. Как её делить? Можно поровну.
V(1,2,3)=1000

Предположим, что
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100

Справедливый дележ невозможно определить до тех пор, пока мы не знаем, какие выигрыши ждут ту или иную компанию, если она отсоединится и будет действовать самостоятельно. А когда мы определили числа (задали кооперативную игру в характеристической форме).

Супераддитивность — это когда вместе зарабатывают больше, чем по отдельности, когда выгоднее объединиться, но непонятно как разделить выигрыш. По этому поводу сломано много копий.

Есть игра. Три бизнесмена одновременно нашли месторождение на 1 млн долларов. Если они втроем договорятся, то миллион их. Любая пара может замочить (отстранить от дела) и весь миллион получить себе. А в одиночку никто ничего не может. Эта страшная кооперативная игра, в которой нет решения. Всегда найдутся такие двое, что они смогут устранить третьего… Кооперативная теория игр начинается с примера, который не имеет решения.

Мы же хотим такое решение, что никакая коалиция не захочет блокировать общее решение. Множество всех дележей, которые нельзя блокировать — это ядро. Бывает что ядро — пустое. Но даже если не пустое, как же делить?

Шепли предлагает делить так. Киньте монету с n! гранями. В этом порядке выписываем всех игроков. Допустим, первый барабанщик. Он заходит и берет свои 100. Дальше заходит «второй», допустим, солист. (Вместе с барабанщиком они могут заработать 450, барабанщик уже взял 100) Солист берет 350. Входит гитарист (вместе 1000, -450), берет 550. Последний вошедший довольно часто бывает в выигрыше. (Супермодулярность)

Если мы для всех порядков выпишем:
ГСБ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
СГБ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
СБГ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
БСГ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
БГС — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
ГБС — (выигрыш С) — (выигрыш Г) — (выигрыш Б)

И по каждому столбцу сложим и поделим на 6 — усреднение по всем порядкам — это вектор Шепли.

Шепли доказал теорему (примерно): Есть такой класс игр (супермодулярные), в которых следующий вошедший в большую команду — он привнёс в неё больший выигрыш. Ядро всегда не пусто и является выпуклой комбинацией точек (в нашем случае 6 точек). Вектор Шепли лежит в самом центре ядра. Его всегда можно предложить в качестве решения, никто не будет против.

В 1973 году было доказано, что задача с коттеджами — супермодулярна.

Дорогу до первого коттеджа делят все n человек. До второго — n-1 человек. И тд.

В аэропорту есть взлетная полоса. Разным компаниям нужна разная длина. Возникает та же самая задача.

Думаю что те кто выдавал Нобелевскую премию имели ввиду и эту заслугу, а не только задачу марьяжа.

Кооперативные игры

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N =<1, 2, . n>, а через S – любое его подмножество. Пусть игроки из S договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r , то есть , а число всевозможных коалиций равно

= 2n – 1.

Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от числа всех игроков в данной игре. Для исследования этих игр необходимо учитывать все возможные коалиции, и поэтому трудности исследований возрастают с ростом n. Образовав коалицию, множество игроков S действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков.

Функция u, ставящая в соответствие каждой коалиции S наибольший, уверенно получаемый его выигрыш u(S), называется характеристической функцией игры. Так, например, для бескоалиционной игры n игроков u(S) может получиться, когда игроки из множества S оптимально действуют как один игрок против остальных NS игроков, образующих другую коалицию (второй игрок).

Характеристическая функция u называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция u простая, то коалиции S, для которых u(S)=1, называются выигрывающими, а коалиции S, для которых u(S) = 0, – проигрывающими.

Если в простой характеристической функции u выигрывающими являются те и только те коалиции, которые содержат фиксированную непустую коалицию R, то характеристическая функция u, обозначаемая в этом случае через uR, называется простейшей.

Содержательно простые характеристические функции возникают, например, в условиях голосования, когда коалиция является выигрывающей, если она собирает более половины голосов (простое большинство) или не менее двух третей голосов (квалифицированное большинство).

Более сложным является пример оценки результатов голосования в Совете безопасности ООН, где выигрывающими коалициями являются все коалиции, состоящие из всех пяти постоянных членов Совета плюс ещё хотя бы один непостоянный член, и только они.

Простейшая характеристическая функция появляется, когда в голосующем коллективе имеется некоторое “ядро”, голосующее с соблюдением правила “вето”, а голоса остальных участников оказываются несущественными.

Пусть коалиции как-то образованы. Тогда возникает вопрос: как делить общий выигрыш с учетом веса каждой коалиции между ее членами?

Естественно положить в основу анализа кооперативной игры принцип оптимального распределения максимального выигрыша u(S) между сторонами .

Реализация этого принципа приводит к рассмотрению С-ядра − множество недоминируемых «вполне устойчивых» дележей кооперативной игры.

Вектор x = (x1, . xn), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции u.

Распределение выигрышей (делёж) игроков должно удовлетворять следующим естественным условиям: если обозначить через xi выигрыш i—го игрока, то, во-первых, должно удовлетворяться условие индивидуальной рациональности

т. е. любой игрок должен получить выигрыш в коалиции не меньше, чем он получил бы, не участвуя в ней (в противном случае он не будет участвовать в коалиции); во-вторых, должно удовлетворяться условие коллективной рациональности

= u(N) (2)

т. е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем u(N), то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше, чем u(N), то это значит, что игроки должны делить между собой сумму большую, чем у них есть).

Система <N, u>, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.

Делёж x доминирует y, если существует такая коалиция S, для которой делёж x доминирует y. Это доминирование обозначается так: x > y.

Наличие доминирования x > y означает, что в множестве игроков N найдётся коалиция, для которой x предпочтительнее y. Соотношение доминирования возможно не для всякой коалиции. Так невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков.

Любой дележ из С-ядра устойчив, в том смысле, что ни одна из коалиций не имеет ни желания, ни возможности изменить исход игры.

Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией u, необходимо и достаточно, чтобы для любой коалиции S выполнялось неравенство .

С-ядро может оказаться пустым, например, когда есть слишком сильные коалиции. Если С-ядро пусто, то требования всех коалиций одновременно не могут быть удовлетворены.

Пример. Найти С-ядро в кооперативной игре 3-х сторон, если максимальные гарантированные выигрыши всевозможных в данном случае семи коалиций () следующие:

u(1, 2, 3)=9, u(2, 3)=7, u(1, 3)=4, u(1, 2)=4, u(1) =u(2) =u(3) =0.

Воспользуемся утверждением, раскрывающим метод построения С-ядра как множества недоминируемых дележей, т. е. для того, чтобы дележ x(S) принадлежал С-ядру необходимо и достаточно выполнения неравенств:

, S N,

где xi − доля i-ой стороны;

i Î S, такая, что должно выполняться требование xi ³ u(i), i=1, 2, 3.

Составим соотношения (4 уравнения для 3 неизвестных):

Для нахождения x1, x2, x3 получаем следующие системы из 3-х неизвестных:

источники:

http://habr.com/ru/post/463391/

http://pandia.ru/text/77/23/55198.php

Источник

12.1. Вектор и аксиомы Шепли

Носителем
игры называется такая коалицияS,
чтодля любой коалиции(любой игрок, не принадлежащий носителю,
является «болваном» и не может ничего
внести ни в одну коалицию).

Обозначим
((N,u))
игруnигроков с
характеристической функциейu,P—произвольную
перестановку множества игроковN={1,2,…,n},
аπ—соответствующую ей подстановку,
в которой дляi=1,2,…,n
()
значениепредставляет собой элемент множестваN, в который переходит
элемент iв
перестановкеP. Тогда
обозначим ((N,πu))
такую игруnигроков
((N,w)),
что для любой коалиции,S={i₁,i₂,…,i_s}

(12.1.1)

Игра
((N,πu))
отличается от игры ((N,u))
только тем, что в ней игроки поменялись
ролями в соответствии с перестановкойP.

Поставим
в соответствие каждой кооперативной
игре ((N,u))nигроков вектор
(вектор значений или вектор Шепли
игры)φ(u)=[φ₁(u),φ₂(u),…,
φ_n(u)]^T,
компоненты которого будем
интерпретировать как выигрыши, полученные
игроками в результате соглашения или
решения арбитра. При этом рассматриваемое
соответствие удовлетворяет следующимаксиомам Шепли:

1. Если коалицияS—любой носитель игры
((N,u)),
то

(12.1.2)

2. Для любой
подстановки π справедливо

(12.1.3)

3. Если ((N,u))
и ((N,w))—две
любые кооперативные игры, то

(12.1.4)

Можно
доказать, что этих аксиом достаточно,
чтобы определить вектор единственным
образом.

Рассмотрим
простую игруn
игроков ((N,^Su))
с характеристической функцией, которая
для любой коалицииsигрокови заданной коалицииопределяется следующим образом

(12.1.5)

Тогда аксиомы
1, 2 однозначно определяют для этой игры
вектор Шепли

(12.1.6)

Действительно,
SиT—носители
игры. Тогда по аксиоме 1, если,
то

(12.1.7)

Отсюда следует,
что
При этом в соответствии с аксиомой 2Наконец, поскольку в коалицииS
именно sигроков,
то в соответствии с аксиомой 1 сумма
компонент вектораШеплиравна 1.

Можно
показать, что любая игра может быть
единственным образом представлена в
виде линейной комбинации простых игр
((N,^Su)),
поэтому характеристическая функция и
вектор Шепли (оптимальный дележ) любой
игры выражаются в виде линейных комбинаций
соответствующих простейших
характеристических функций и векторов.

Если
((N,u))—любая
играnигроков, то
можно найти 2ⁿ–1
вещественных чисел^Sc,
таких, что

(12.1.8)

где суммирование
идет по всем подмножествам Sмножества Nкроме
пустого множества. При этом, считая, что
число элементов (игроков) в подмножествеTравно t,
можно определить

(12.1.9)(12.1.10)

Лекция 13 вектор шепли (продолжение)

13.1. Пример расчета вектора Шепли

В
примере 11.1 («джаз-оркестр») N={1,2,3},u(1,2,3)=10 000,
u(1,2)=8 000,
u(2,3)=6 500,
u(2)=3 000,
u(1,3)=5 000,
u(1)=2 000,
u(3)=0. Определим
вектор Шепли игры
(оптимальный дележ)φ=[φ₁,φ₂,φ₃]^T.

Обозначим
S₁={1},
S₂={2},
S₃={3},
S₁₂={1,2},
S₁₃={1,3},
S₂₃={2,3},
S₁₂₃={1,2,3}.

13.2. Понятие о дифференциальных играх

Рассмотрим
два объекта управления (игроки 1и2), которые описываются двумя
системами обыкновенных дифференциальных
уравнений

(13.2.1)

(13.2.2)

Игрок
1(2) начинает движение из
состояния¹x(t₀)
(²x(t₀))
и перемещается вn–мерном
пространстве состояний, выбирая в каждый
момент времени значение¹m(²m)–мерного
вектора управления¹u(t)
[²u(t)]
в соответствии со своими целями и
информацией, которая ему доступна в
этот момент времени.

Цели
игроков в дифференциальной игре
определяются с помощью функций выигрыша
(проигрыша), которые зависят от траекторий
движения игроков ¹x(t)
и²x(t).
Если, например, антагонистическая
дифференциальная игра описывает процесс
преследования игроком2игрока1, то расстояние между игрокамипредставляет собой выигрыш игрока1
и проигрыш игрока2. При
этом игроки в каждый момент времени
могут иметь полную, точную или искаженную
информацию о своем состоянии и состоянии
противника. Если, например, один из
игроков в каждый момент времени имеет
информацию также и об управлении, которое
выбирает противник, то такая игра
называется игройс дискриминацией
противника.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Напечатано::	Гость
Дата:	воскресенье, 28 мая 2023, 11:34

Описание

Основные понятия и определения.

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

Рассмотрим биматричную игру с побочными платежами. Если участники по условию игры в состоянии договориться с друг другом, то решение — то есть выигрыши игроков, не будет зависеть от выбираемых ими стратегий, а только лишь от способа дележа общего дохода. При этом для них важно еще и то, насколько выгодно им вступать в такое соглашение или коалицию.

Коалицией в кооперативное игре называется всякое (любое) подмножество множества игроков.

Пример. Пусть I = {1,2,…i…n} — некоторое множество игроков. Коалициями будут: k₁= {1,2,5,i};

k₂= {i} = i;

k₃= { } = Æ ;

k₄= { 1,2,…n} = I.

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

Характеристической функцией v(k) называется наибольший выигрыш, уверенно получаемый коалицией k.

Пример. Допустим, существует небольшая бригада состоящая из двух рабочих и мастера. Дневное задание может выполняться всей бригадой или мастером с одним из рабочих. Выполнение дневного задания гарантирует бригаде заработок в С единиц (выигрыш).

Задать характеристическую функцию этой игры.

I = { M, p₁, p₂} — множество игроков игры. Тогда

v(Æ) = v(p₁, p₂) = v (p₁) = v (p₂)= v (M) = 0,

v (M, p₁, p₂) = v( M,p₁) = v( M, p₂) = C.

Из заданной характеристической функции видно в какие коалиции выгодно вступать игрокам, так как выигрыш существенно зависит от состава коалиций. Таким образом, характеристическая функция задается на множестве всех подмножеств множества игроков I игры Г и принимает вещественные значеня.

Свойства характеристической функции:

1. Персональность v_Г(Æ) = 0;

2. Супераддитивность v_Г(КÈL) ³ v_Г(К) + v_Г(L), где K,LÎI, KÇL = Æ;

3. Дополнительность v_Г(К) + v_Г(IK) = v_Г(I) = C,

где С — постоянная сумма выигрыша.

2. Дележи в кооперативных играх.

Как только игроки вкоалиции получили свой максимально гарантированный выигрыш, возникае задача о том, как его разделить между участниками.

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

Пусть задана характеристическая функция v над множеством игроков I. Какие векторы дележей в этом случае допустимы?

Прежде всего, каждый игрок вступает в коалицию только в том случае, если это, по крайней мере, не уменьшает его выигрыш, то есть если

x_i ³ v(i) Эгалитарный подход

å x_i = v (I) Утилитарный подход

Приведенные условия носят названия индивидуальной и коллективной рациональности, так как позволяют получить максимальную выгоду и использовать возможности системы полностью.

Дележом в условиях характеристической функции v называется вектор х = ( х₁, х₂, … х_n), удовлетворяющий условиям индивидуальной и коллективной рациональности.

Классической кооперативной игрой называется система < I, v >, включающая множество игроков I и характеристическую функцию v над этим множеством, а так же множество Х дележей в условиях этой характеристической функции.

Теорема. Для того, чтобы вектор х = ( х₁, х₂, … х_n) был дележом в кооперативной игре < I, v >, необходимо и достаточно, чтобы

х_i = v (i) + a_i, a_i ³ 0, i Î I;

å a_i = v(I) — å v(i)

Нетрудно видеть, что компоненты вектора х удовлетворяют условию индивидуальной рациональности. Условие кооперативной рациональности

åx_i = å v (i) + v(I) — å v(i) = v(I) также выполняется.

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

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

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

Существующая классификация делит все кооперативные игры, прежде всего, на существенные и несущественные.

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

v (КÈL) = v(К) + v(L), где K,LÎI, KÇL = Æ;

Существенными называются остальные игры.

Любая кооперативная игра с аддитивной (а не супераддитивной) характеристической функцией является несущественной, ее участники не заинтересованы в образовании коалиций, так как это не увеличивает их выигрыш (долю).

Признак аддитивности характеристической функции задается теоремой:

Теорема. Для того, чтобы характеристическая функция была аддитивной, необходимо и достаточно, чтобы выполнялось равенство å v(i) = v(I).

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

Теорема. В несущественной игре существуе только один дележ

( v(1), v(2),… v(n) ).

Во всякой существенной игре множество дележей бесконечно.

Это обьясняется тем, что в существенной игре обязательно существует

D = v(I) — å v(i) > 0,

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

Игроки так же делятся на существенных и несущественных (болванов), а множества игроков — на носителей игры и множества болванов.

Существенным называется игрок i, если существует такая коалиция К, что

v(K) + v(i) < v(KÈi).

Болваном называется игрок i, если для любой коалиции KÌI cправедливо

v(K) + v(i) = v( KÈi).

Допустим, L — множество болванов (несущественных игроков) и LÌK, тогда

v(K) = v(K L) + å v(i), а если K = L, то v(K) = å v(i).

Существенные игроки образуют множество носителей игры, NÌI. Признаком этого для коалиции К является:

v(K) = v(KÇN) + å v(i)_iÎ_KN.

3. Аффинно-эквивалентные игры.

Существенные и несущественные игры тоже делятся на классы.

Кооперативная игра с множеством игроков I и характеристической функцией v называется аффинно-эквивалентной игре с тем же множеством игроков и характеристической функцией v’, если найдутся такое положительное число k и произвольные вещественные c_i ( i Î I ), что для любой коалиции KÌ L имеет место равенство:

v’(K) = k v(K) + å c_i, iÎK.

При афинной эквивалентности v ~ v’ дележ x соответствует дележу х’ так, что: x_i ’ = k x_i + c_i.

Иногда вместо аффинной эквивалентности самих кооперативных игр удобно говорить об аффинной эквивалентности их характеристических функций.

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

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

Рассмотрим с позиций стратегической эквивалентности несущественные игры.

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

Теорема. Всякая существенная игра аффинно эквивалентна нулевой игре.

Следствие. Все несущественные игры с одним и тем же множеством игроков аффинно эквивалентны друг другу.

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

Для изучения существенных игр наиболее удобна a-b редуцированная форма, то есть такая, в которой v(i) = a, v(I) = b. Обычно используются варианты a=0, b=1 и a=1, b=0.

Теорема. Всякая существенная игра аффинно эквивалентна одно и только одной игре в 0-1 редуцированной форме.

То есть любую существенную кооперативную игру можно свести к редуцированной форме и в этом виде производить ее исследование и изучение. От существенной кооперативной игры к ее редуцированной форме можно перейти следующим образом. Для произвольной коалиции К:

v’(K) = ( v(K) — å_i_Î_K v(i))/ ( v(I) — å_i_Î_I v(i)) (3.1.)

Нетрудно видеть, что 0-1 редуцированная форма существенной кооперативной игры позволяет по характеристической функции сразу же судить об эффективности обьединения в коалицию (см.знаменатель), то есть в чистом виде рассматривать свойство супераддитивности.

Все дележи в 0-1 редуцированной форме должны отвечать условиям: x_i ³0, так как v(i) = 0, но есть еще D, так как игра существенная å x_i = v(I) = 1.

Пример. Дана кооперативная игра, I = {1,2,3,4}. Задана характеристическая функция: v(1) = -1; v(2) = v(3) = -2; v(1,2,4) = v(1,3,4) = 2; v(2,3,4) =1;

v(4)= v(1,2)= v(1,3) = v(1,4) = v(2,3)= v(2,4) = v(3,4) = v(1,2,3) = v(1,2,3,4) = 0;

Найти характеристическую функцию 0-1 редуцированной формы.

Воспользуемся формулой 3.1. В знаменателе выражения стоит постоянная величина v(I) — å_i_Î_I v(i) = 0 — (-1-2-2) = 5. Остальные вычисления занесем в таблицу:

К	1	2	3	4	12	13	14	23	24	34	123	124	134	234	1234
v’	0	0	0	0	0,6	0,6	0,2	0,8	0,4	0,4	1	1	1	1	1

4. Доминирование дележей.

Рассмотрим кооперативную игру Г = < I, v > и два дележа в этой игре: х = ( х₁, х₂, … х_n) и y = ( y₁, y₂, … y_n). Допустим, K Ì I — некоторая коалиция в игре.

Дележ х доминирует дележ у по коалиции К, если выполняются неравенства å_i_Î_K х_i £ v(К) и х_i > y_i, iÎ К. Доминирование дележа по коалиции К обозначается хñ_Ку, х dom_К y, или x R_кy.

Первое неравенство определения утверждает, что коалиция К способна обеспечить такой дележ, так как сумма выигрышей, получаемых членами коалиции не превышает ее максимального гарантированного выигрыша V(K). Второе означает, что каждый член коалиции К получает по дележу х больше, чем по дележу у ( именно в этом смысл доминирования). Иногда, определяя отношение доминирования, не указывают конкретно коалицию, а просто говорят, что дележ х доминирует дележ у (хñу). Однако, при этом подразумевается, что существует коалиция К, по которой это доминирование имеет место, то есть справедливо хñ_Ку.

Для коалиции К доминирующий дележ полезнее, чем доминируемый. Эта коалиция будет его отстаивать. Иной случай, когда с этим дележом не согласятся остальные игроки (входящие в множество IK). Но коалиция К может сама обеспечить себе такой дележ, так как å_i_Î_K х_i £ v(К).

Следует отметить, что доминирование возможно по любой коалиции, кроме коалиции из одного игрока и из всех игроков. В первом случае К = {i} из определения следует, что х_i £ v(i), что противоречит свойству индивидуальной рациональности дележа х ( х ³ v(i)).

В случае К = I из х_i > y_iследует , что åх_i > åy_i= v(I), то есть дележ х должен давать в сумме больше, чем гарантированный выигрыш для всех игроков.

Важно, что отношение доминирования дележей выполняется для аффинно эквивалентных кооперативных игр, то есть доминирование инвариантно относительно аффинной эквивалентности.

Теорема. Если v и v’ — аффинно-эквивалентные характеристические функции, причем дележам х и у в v соответствуют дележи x’ и y’ в v’, то из х ñ_Ку следует х’ ñ_Ку’.

Отношение доминирования выполняется для всех кооперативных аффинно эквивалентных игр и является свойством не одной игры, а всего класса эквивалентных игр. Поскольку, например, в несущественной игре всего один дележ, то для них понятие доминирования не имеет смысла. Существенные игры исследовать на доминирование можно используя 0-1 редуцированную форму.

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

В достаточно общей модели принятия решения трудно сказать принимающему решение, какую альтернативу он должен выбрать или какая его стратегия является оптимальной. Главным в такой модели является прогноз действий партнеров, так как если он имеется, то остальное — сравнительно простая задача максимизации выгоды участника в условиях риска. Поэтому оптимальность в теории игр и понимается как ожидаемое, возможное. Оптимальными исходами называются исходы, возможные в условиях допустимых действий игроков и коалиций, совершаемых согласно их интересам.

Например,в игровой модели Шепли-Шубик, 1969 года (кооперация производства с обменом продуктами) или просто модели обменов, вопрос о том, как кооперировать, может быть заменен вопросом: какое понятие оптимальности следует применять для дележа прибыли?

Ответить на этот вопрос по заданной характеристической функции невозможно, поскольку ответ существенно зависит от дополнительных свойств модели. Например, правила дележа будут различными в зависимости от того, является ли правило обьектом переговоров между участниками кооперации или оно издается правительством в качестве закона и поэтому должно соблюдаться в принудительном порядке. В каждом из этих двух случаев существенными могут оказаться и другие условия. Может потребоваться такое правило, при котором партнеры по кооперации будут незаинтересованы скрывать друг от друга свои ресурсы ( делать их дефицитными для модели) или отказываться от запланированных поставок. Иногда приходится не забывать об элементарном требовании, чтобы никто не получал доли прибыли без соответствующего вклада в общий выпуск, и т.д.

В общем, принцип оптимальности с точки зрения приложений есть такое правило, какое нужно для решения рассматриваемой проблемы.

Рассмотрим в качестве принципов оптимизации устойчивость коалиционной структуры и принцип справедливости.

Эксцессом дележа х для коалиции К в условиях характеристической функции v называется разность

e_v(x,K) = v(K) — å_i_Î_K х_i , колторая показывает, насколько может коалиция К увеличить свой выигрыш по сравнению с суммой, предлагаемой по дележу. Если эксцесс положителен, то соответственный дележ реализуем для данной коалиции, в этом случае дележ называется эффективным.

Если дележ не эффективен, то это значит, что сумма платежей превышает выигрыш коалиции. Коалиция увеличить его не может, поэтому неэффективный дележ оптимален по принципу устойчивости.

Дележ называется абсолютно неэффективным, если он не эффективен ни для какой коалиции.

Для игры с постоянной суммой эксцесс положителен и всегда эффективен.

Пример. Рассмотрим существенную игру трех лиц с постоянной суммой. С позиций доминирования в этой игре можно рассматривать только коалиции {1,2}, {1,3}, {2,3}. Пусть х = ( х₁, х₂, … х_n) и y = ( y₁, y₂, … y_n) — дележи и х dom_1,2 y . Из определения доминирования следует, что должно выполняться

х₁+ х₂= 1 — х₃ £ v(1,2) и х₁ > у₁ , х₂> у₂ .

Поскольку по свойству дополнительности для 0-1 редуцированной формы v(1,2) = v (1,2,3) — v(3) = 1 — 0 = 1, то неравенство x₁+ x₂ = 1 — x₃£ 1 всегда выполняется. Вторая группа неравенств из определения доминирования дележей и х₁ > у₁ , х₂> у₂ и условие ее выполнения лучше всего иллюстрируются графически.

Так как рассматривается 0-1 редуцированная форма, то

х₁+ х₂+ х₃ = y₁+ y₂+ y₃= 1 и любой дележ в такой задаче можно представить как точку симплекса, задаваемую барицентрическими координатами.

Симплекс — простейший выпуклый многогранник данного числа измерений n. При n = 3 cимплекс — произвольный, в том числе неправильный тетраэдр. При n = 2 симплекс — произвольный треугольник, при n = 1 — отрезок, при n = 0 — одна точка, таким образом, n-мерный симплекс имеет n+1 вершину.

Если в пространстве R^mдана система декартовых координат х₁, х₂, … х_mв которой вершина е_i ( i=0: n) имеет координаты х₁(i), х₂(i), … х_m(i), то симплекс с вершинами е₀, е₁, е₂,…е_nсостоит из всех точек пространства, координаты которых имеют вид:

х_k= a₀х_k(0) + a₁х_k(1) + …+ a_nх_k(n), k = 1: m, a ³ 0 — произвольные, å a_i= 1.

Барицентрические координаты точки М на плоскости по отношению к трем базисным (не лежащим на одной плоскости) точкам А₁, А₂, А₃ этой плоскости — такие три числа m₁, m₂, m₃ (å m_i= 1), что точка М представляет собой центр тяжести системы из трех материальных точек с массами m₁, m₂, m₃ , расположенными в точках А₁, А₂, А₃ ( или вершинах симплекса).

В нашем примере роль масс играют полезности, которые получают игроки по рассматриваемым дележам. Если х₁ > у₁, то точка х должна быть расположена ближе к вершине 1, чем точка у. Все точки, соответствующие стороне симплекса 32 имеют нулевую барицентрическую координату х₁, а все точки линии, параллельной ребру 32 — одинаковую барицентричекую координату х₁ . Поэтому “расстоянием” между любой точкой симплекса и какой-либо его вершиной является длина перпендикуляра, опущенного из этой вершины на прямую, проходящую через рассматриваемую точку параллельно стороне, противоположной вершине.

Для определения всех точек симплекса, соответствующих дележам, доминируемым дележом х по коалиции {1,2}, необходимо провести через х прямые, параллельные сторонам симплекса 2,3 и 1,3. Заштрихованная область и дает множество доминируемых дележей. Пунктир означает, что внутренние границы области в нее не входят. Точно так же можно построить все области доминирования дележом х по коалициям {1,2}, {2,3} и {1,3}. Незаштрихованные области — соответствуют дележам у₁, доминирующим дележ х₁.

Для того, чтобы дележи не доминировали друг друга, соответствующие им точки должны лежать на прямой, параллельной одной из сторон треугольника (ab, cd и ef на рисунке для дележа х).

Для игры с непостоянной суммой могут иметь место и неэфективные дележи, поэтому неравенство х_i + x_j£ v(i,j) , х_i+ х_j+ х_l = 1, может быть нарушено. Так как это равносильно 1- х_l£ v(i,j) , то условия доминирования принимают вид:

х_i > у_i , х_j > у_j , х_l ³ 1 — v(i,j).

5. С — ядро (core).

Наличие доминирующих и доминируемых дележей в кооперативной игре приводит к появлению коалиций, заинтересованных в тех или иных дележах. Следовательно, если найдется дележ, не доминируемый никаким другим дележом, то он, скорее всего, не вызовет возражений у игроков и не приведет к образованию коалиций с «собственными интересами».

Множество дележей в кооперативной игре, каждый из которых не доминируется какими — либо другими дележами, называется С-ядром этой игры.

Теорема. Для того, чтобы дележ х принадлежал С-ядру кооперативной игры с характеристической функцией v , необходимо и достаточно, чтобы для любой коалиции К выполнялось неравенство :

å_i_Î_K х_i³ v(K), ( т.е. все дележи в С-ядре абсолютно неэффективны ).

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

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

Теорема. Во всякой существенной игре с постоянной суммой С-ядро пусто.

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

Пример. Рассмотрим общую кооперативную игру трех лиц в 0-1 редуцированной форме. Имеем: v(Æ ) = v(1) = v(2) = v (3) = 0; v (1,2,3) = 1; v(1,2) = C₃; v (2,3) = C₁; V (1,3) = C₂; 0 £ C_i £ 1, i = 1:3.

Из определения свойств дележей, принадлежащих С-ядру, имеем:

x₁+ x₂ ³ C₃; x₁+ x₂ ³ C₃; x₁+ x₂ ³ C₃; а поскольку для любого дележа справедливо правило групповой рациональности, x₁+ x₂ + x₃ = 1, то условие принадлежности дележа к С-ядру имеет окончательный вид в форме:

1 — x₃ ³ C₃; 1 — x₂ ³ C₂; 1— x₁ ³ C₁; или x₃£ 1- C₃ ; x₂£ 1- C₂ ; x₁£ 1- C₁.

Сложим почленно все неравенства: x₁+ x₂ + x₃£ 3 — (C₁ + C₂ + C₃). Имеем: C₁ + C₂ + C₃£ 2. Это условие является необходимым для существования непустого С-ядра.

6. Решение по Нейману — Моргенштерну.

Дележи, входящие в С-ядро, не доминируются другими дележами, но сами доминировать другие не могут, поэтому выбор дележа из С-ядра — решение трудно оспоримое, но далеко не самое лучшее.

Разумеется, идеальным было бы указание такого дележа, который не только не доминировался какими-либо другими дележами, но и сам бы доминировал любой другой дележ. Приемлемые результаты можно получить путем некоторого расширения класса дележей подобно введению смешанных стратегий для решения антагонистических игр.

Такое расширение было произведено Дж. фон Нейманом и О.Моргенштерном путем использования понятий внутренней и внешней устойчивости.

Под внутренней устойчивостью множества дележей, образующих решение, понимается не доминирование дележей внутри решения. Под внешней устойчивостью понимается свойство доминирования хотя-бы одним из дележей, входящих в решение, любого дележа не входящего в решение.

Решением по Нейману-Моргенштерну ( Н-М решением ) кооперативной игры называется такое множество R дележей, что:

1. Никакие два дележа из R не доминируют друг друга (внутренняя устойчивость);

2. Каким бы ни был дележ S R найдется дележ r R такой, что r dom s (внешняя устойчивость).

Теорема связи между С-ядром и Н-М решением: Если в кооперативной игре существует С-ядро и Н-М решение R, то С Ì R.

Теорема. Если некоторое Н-М решение кооперативной игры <I,v> состоит из единственного дележа х, то характеристическая функция v является несущественной. (Н-М решение существенной кооперативной игры не может состоять только из одного дележа).

Недостатки Н-М решения:

1. Известны примеры кооперативных игр, которые не имеют Н-М решения. Более того, в настоящее время не известны какие-либо критерии, позволяющие судить о наличии у игры Н-М решения. Тем самым заложенный в Н-М решении принцип оптимальности не является универсально реализуемым и область его реализуемости пока остается неопределенной.

2. Кооперативные игры, если имеют Н-М решение, то, как правило, более одного. Поэтому принцип оптимальности, приводящий к Н-М решению не является полным: он не в состоянии указать игрокам единственной системы норм распределения выигрыша.

3. Решения существенных кооперативных игр состоят из более чем из одного дележа. Таким образом даже выбор какого-либо конкретного Н-М решения еще не определяет выигрыша каждого из игроков.

Эти недостатки не «пороки», которые следовало бы исправлять, а недостатки, которые хотелось бы восполнить. Это отражает положение дел в действительности: большинство экономических и социальных проблем допускает множественные решения, и эти решения не всегда поддаются непосредственному сравнению по их предпочтительности.

7. Вектор Шепли.

До сих пор были рассмотрены решения игр, отвечающие принципам оптимальности в смысле выгодности и устойчивости ( maxmin в чистых или смешанных стратегиях ) или только устойчивости ( C-ядро и Н-М решение в кооперативных играх ). Рассмотрим решения, оптимальные в смысле справедливости.

Задача состоит в том, чтобы найти вектор распределения общего выигрыша между участниками игры: Ф(v) = ( Ф₁(v), Ф₂(v),… Ф_n(v))

При этом необходимо, чтобы Ф(v) был дележом в условиях кооперативной игры, то есть отвечал бы требованиям игдивидуальной и групповой рациональности.

Предлагаемое решение носит аксиоматический характер, то есть выводится формальным образом из некоторой полной и непротиворечивой системы аксиом. Эта система включает в себя: аксиому эффективности, аксиому симметрии и аксиому агрегации.

Аксиома эффективности: распределение выигрыша носителя игры ( N ) происходит только между игроками, входящими в носитель. Иными словами, все приращение выигрыша, достигаемое только за счет обьединения в коалицию (эффект супераддитивности), распределяется только между теми, кто его обеспечил. С другой стороны, все болваны получают только то, что они выиграли бы в одиночку или в составе коалиции.

Формально эти условия выражаеюся в том, что å Ф_i(v) = v (N), iÎN, и Ф_j(v) = v(j), jÎ IN.

Аксиома симметрии: игроки, входящие в игру симметрично, должны получать одинаковый доход. Здесь симметричность понимается как одинаковое влияние на характеристическую функцию. Это утверждение равносильно тому, что доход игрока не зависит от его номера или «имени».

Формально Ф_j(v) = Ф_p_j(v), где p — целое положительное число.

Аксиома агрегации: если игрок принимает участие в двух играх с характеристическими функциями v’ и v”, то причитающаяся ему доля:

Ф(v’ + v”) = Ф(v’) + Ф(v”), если множества игроков в обоих играх совпадают.

Совокупность аксиом является непротиворечивой и полной: для всякой характеристической функции v вектор Ф(v) существует и является единственным (вектор Шепли). Непротиворечивость обеспечивает существование, а полнота его единственность.

Теорема. Для любой характеристической функции v над I={1,2,…n} компоненты вектора Шепли определяются по формуле

Пример. Для кооперативной игры трех лиц в 0-1 редуцированной форме эта формула имеет вид: Ф_i(v) = 1/6 (2 — 2C_i + C_j + C_f).

Следовательно, координаты вектора Шепли:

Ф₁(v) = 1/6 (2 — 2C₁ + C₂ + C₃), где C₁ = v(2,3);

Ф₂(v) = 1/6 (2 — 2C₂ + C₁ + C₃), где C₂ = v(1,3);

Ф₃(v) = 1/6 (2 — 2C₃ + C₁ + C₂), где C₃ = v(1,2).

Для того, чтобы вектор Шепли принадлежал к С-ядру необходимо и достаточно, чтобы выполнялось неравенство: 4C_i + C_j + C_f £ 4 для всех i, j,f.

8. Примеры классических кооперативных игр.

Задача «Джаз-оркестр».

Условие. Владелец клуба в Париже обещает 1000 $ певцу (S), пианисту (P) и ударнику (D) за совместную игру в клубе. Выступление дуэта певца и пианиста он расценивает в 800 $, ударника и пианиста — в 650 $, а одного пианиста в 300 $. Другие дуэты и солисты не рассматриваются , а присутствие пианиста владелец считает обязательным.

Дуэт певец — ударник зарабатывает 500 $ за вечер в одной удобно расположеной станции метро, певец зарабатывает в среднем 200 $ за вечер в открытом кафе. Ударник один ничего не может заработать.

Стоит ли музыкантам соглашаться на приглашение владельца клуба и как поделить общий заработок ?

Решение. Обозначим S, P,D — 1 игрок, 2 игрок и 3 игрок соответственно.

Найдем 0-1 редуцированную форму исходной игры:

Коалиция

123

SPD

1000

800

500

650

200

300

v(0-1)

0,6

0,7

Условие эффективности дележей	Условие неэффективности (принадлежности к С-ядру)
Для редуцированной формы
x₁³ 1 — v(2,3) = 0,3	x₁£ 0,3
x₂³ 1 — v(1,3) = 0,4	x₂£ 0,4
x₃³ 1 — v(1,2) = 0,4	x₃£ 0,4
Для нередуцированной формы
x_S + x_P£ 800 , x_D³ 200	x_S + x_P³ 800, x_D£ 200
x_S + x_D£ 500 , x_P³ 500	x_S + x_D³ 500, x_P£ 500
x_D + x_P£ 650 , x_S³ 350	x_D + x_P³ 650, x_S£ 350

Найдем вектор Шепли для этой игры. В нередуцированной форме n=3, коалиции могут быть из одного, двух и трех игроков.

Ф_S = (3-3)!2! (1000 -650)/ 3! + 1!1![(800 — 300) + (500 — 0)] / 3! + 2!0! 200 / 3! = 350;

Ф_P= 475;

Ф_D= 175.

Нетрудно видеть, что, Ф_S + Ф_P + Ф_D = 1000, то есть условие коллективной рациональности выполняется. С другой стороны:

Ф_S = 350 > v(S) = 200;

Ф_P = 475 > v(P) = 300;

Ф_D = 175 > v(D) = 0, то есть условия индивидуальной рациональности так же выполняются. Таким образом, в данном случае вектор Шепли является дележом, кроме того, он входит в С-ядро :

x_D = Ф_D=175 < 200, x_P = Ф_P=475 < 500, x_S = Ф_S=350 = 350 (выплата певцу оказалась максимальной).

Для 0-1 редуцированной формы:

Ф₁(v) = 1/6 (2 — 2C₁ + C₂ + C₃) = (2 — 1,4 + 1,2)/ 6 = 0,3;

Ф₂(v) = 1/6 (2 — 2C₂ + C₁ + C₃) = (2 — 1,2 + 1,3)/ 6 = 0,35;

Ф₃(v) = 1/6 (2 — 2C₃ + C₁ + C₂) = (2 — 1,2 + 1,3)/ 6 = 0,35.

Вектор Шепли Ф(v) = ( 0,3; 0,35; 0,35) входит в С-ядро игры:

4C_i + C_j + C_f = 2,8 + 0,6 + 0,6 = 4 ( £ 4), то есть условие соблюдается на границе для первого игрока. Для других двух игроков:

4C_i + C_j + C_f = 2,4 + 0,7 + 0,6 = 3,7 < 4, то есть условие вхождения в С-ядро тоже соблюдается.

Ответ. Музыкантам выгодно предложение владельца клуба, так как они заработают за этот вечер не менее, чем обычно. Общий заработок в 1000 $ они должны поделить следующим образом: певцу 350 $, пианисту 435 $, ударнику 175 $.

1. Нестратегические игры

Основные понятия и определения.

Коалицией в кооперативное игре называется всякое (любое) подмножество множества игроков.

Пример. Пусть I = {1,2,…i…n} — некоторое множество игроков. Коалициями будут: k₁= {1,2,5,i};

k₂= {i} = i;

k₃= { } = Æ ;

k₄= { 1,2,…n} = I.

Характеристической функцией v(k) называется наибольший выигрыш, уверенно получаемый коалицией k.

Задать характеристическую функцию этой игры.

I = { M, p₁, p₂} — множество игроков игры. Тогда

v(Æ) = v(p₁, p₂) = v (p₁) = v (p₂)= v (M) = 0,

v (M, p₁, p₂) = v( M,p₁) = v( M, p₂) = C.

Свойства характеристической функции:

1. Персональность v_Г(Æ) = 0;

2. Супераддитивность v_Г(КÈL) ³ v_Г(К) + v_Г(L), где K,LÎI, KÇL = Æ;

3. Дополнительность v_Г(К) + v_Г(IK) = v_Г(I) = C,

где С — постоянная сумма выигрыша.

2. Дележи в кооперативных играх.

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

x_i ³ v(i) Эгалитарный подход

å x_i = v (I) Утилитарный подход

х_i = v (i) + a_i, a_i ³ 0, i Î I;

å a_i = v(I) — å v(i)

åx_i = å v (i) + v(I) — å v(i) = v(I) также выполняется.

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

Существующая классификация делит все кооперативные игры, прежде всего, на существенные и несущественные.

v (КÈL) = v(К) + v(L), где K,LÎI, KÇL = Æ;

Существенными называются остальные игры.

Признак аддитивности характеристической функции задается теоремой:

Теорема. В несущественной игре существуе только один дележ

( v(1), v(2),… v(n) ).

Во всякой существенной игре множество дележей бесконечно.

Это обьясняется тем, что в существенной игре обязательно существует

D = v(I) — å v(i) > 0,

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

Существенным называется игрок i, если существует такая коалиция К, что

v(K) + v(i) < v(KÈi).

Болваном называется игрок i, если для любой коалиции KÌI cправедливо

v(K) + v(i) = v( KÈi).

Допустим, L — множество болванов (несущественных игроков) и LÌK, тогда

v(K) = v(K L) + å v(i), а если K = L, то v(K) = å v(i).

Существенные игроки образуют множество носителей игры, NÌI. Признаком этого для коалиции К является:

v(K) = v(KÇN) + å v(i)_iÎ_KN.

3. Аффинно-эквивалентные игры.

Существенные и несущественные игры тоже делятся на классы.

v’(K) = k v(K) + å c_i, iÎK.

При афинной эквивалентности v ~ v’ дележ x соответствует дележу х’ так, что: x_i ’ = k x_i + c_i.

Рассмотрим с позиций стратегической эквивалентности несущественные игры.

Теорема. Всякая существенная игра аффинно эквивалентна нулевой игре.

Следствие. Все несущественные игры с одним и тем же множеством игроков аффинно эквивалентны друг другу.

v’(K) = ( v(K) — å_i_Î_K v(i))/ ( v(I) — å_i_Î_I v(i)) (3.1.)

v(4)= v(1,2)= v(1,3) = v(1,4) = v(2,3)= v(2,4) = v(3,4) = v(1,2,3) = v(1,2,3,4) = 0;

Найти характеристическую функцию 0-1 редуцированной формы.

К	1	2	3	4	12	13	14	23	24	34	123	124	134	234	1234
v’	0	0	0	0	0,6	0,6	0,2	0,8	0,4	0,4	1	1	1	1	1

4. Доминирование дележей.

Рассмотрим в качестве принципов оптимизации устойчивость коалиционной структуры и принцип справедливости.

Эксцессом дележа х для коалиции К в условиях характеристической функции v называется разность

Дележ называется абсолютно неэффективным, если он не эффективен ни для какой коалиции.

Для игры с постоянной суммой эксцесс положителен и всегда эффективен.

х₁+ х₂= 1 — х₃ £ v(1,2) и х₁ > у₁ , х₂> у₂ .

Так как рассматривается 0-1 редуцированная форма, то

х_k= a₀х_k(0) + a₁х_k(1) + …+ a_nх_k(n), k = 1: m, a ³ 0 — произвольные, å a_i= 1.

х_i > у_i , х_j > у_j , х_l ³ 1 — v(i,j).

5. С — ядро (core).

å_i_Î_K х_i³ v(K), ( т.е. все дележи в С-ядре абсолютно неэффективны ).

Теорема. Во всякой существенной игре с постоянной суммой С-ядро пусто.

Из определения свойств дележей, принадлежащих С-ядру, имеем:

1 — x₃ ³ C₃; 1 — x₂ ³ C₂; 1— x₁ ³ C₁; или x₃£ 1- C₃ ; x₂£ 1- C₂ ; x₁£ 1- C₁.

6. Решение по Нейману — Моргенштерну.

1. Никакие два дележа из R не доминируют друг друга (внутренняя устойчивость);

2. Каким бы ни был дележ S R найдется дележ r R такой, что r dom s (внешняя устойчивость).

Недостатки Н-М решения:

7. Вектор Шепли.

Формально эти условия выражаеюся в том, что å Ф_i(v) = v (N), iÎN, и Ф_j(v) = v(j), jÎ IN.

Формально Ф_j(v) = Ф_p_j(v), где p — целое положительное число.

Ф(v’ + v”) = Ф(v’) + Ф(v”), если множества игроков в обоих играх совпадают.

Следовательно, координаты вектора Шепли:

Ф₁(v) = 1/6 (2 — 2C₁ + C₂ + C₃), где C₁ = v(2,3);

Ф₂(v) = 1/6 (2 — 2C₂ + C₁ + C₃), где C₂ = v(1,3);

Ф₃(v) = 1/6 (2 — 2C₃ + C₁ + C₂), где C₃ = v(1,2).

8. Примеры классических кооперативных игр.

Задача «Джаз-оркестр».

Стоит ли музыкантам соглашаться на приглашение владельца клуба и как поделить общий заработок ?

Решение. Обозначим S, P,D — 1 игрок, 2 игрок и 3 игрок соответственно.

Найдем 0-1 редуцированную форму исходной игры:

Коалиция

123

SPD

1000

800

500

650

200

300

v(0-1)

0,6

0,7

Условие эффективности дележей	Условие неэффективности (принадлежности к С-ядру)
Для редуцированной формы
x₁³ 1 — v(2,3) = 0,3	x₁£ 0,3
x₂³ 1 — v(1,3) = 0,4	x₂£ 0,4
x₃³ 1 — v(1,2) = 0,4	x₃£ 0,4
Для нередуцированной формы
x_S + x_P£ 800 , x_D³ 200	x_S + x_P³ 800, x_D£ 200
x_S + x_D£ 500 , x_P³ 500	x_S + x_D³ 500, x_P£ 500
x_D + x_P£ 650 , x_S³ 350	x_D + x_P³ 650, x_S£ 350

Ф_S = (3-3)!2! (1000 -650)/ 3! + 1!1![(800 — 300) + (500 — 0)] / 3! + 2!0! 200 / 3! = 350;

Ф_P= 475;

Ф_D= 175.

Ф_S = 350 > v(S) = 200;

Ф_P = 475 > v(P) = 300;

x_D = Ф_D=175 < 200, x_P = Ф_P=475 < 500, x_S = Ф_S=350 = 350 (выплата певцу оказалась максимальной).

Для 0-1 редуцированной формы:

Ф₁(v) = 1/6 (2 — 2C₁ + C₂ + C₃) = (2 — 1,4 + 1,2)/ 6 = 0,3;

Ф₂(v) = 1/6 (2 — 2C₂ + C₁ + C₃) = (2 — 1,2 + 1,3)/ 6 = 0,35;

Ф₃(v) = 1/6 (2 — 2C₃ + C₁ + C₂) = (2 — 1,2 + 1,3)/ 6 = 0,35.

Вектор Шепли Ф(v) = ( 0,3; 0,35; 0,35) входит в С-ядро игры:

4C_i + C_j + C_f = 2,4 + 0,7 + 0,6 = 3,7 < 4, то есть условие вхождения в С-ядро тоже соблюдается.

Источник

Лекция 2 в pdf и видео (скоро будет)

Мы ответим на несколько вопросов:

Когда ядро не пусто?
Почему вектор Шепли — это хорошо?
Когда вектор Шепли лежит в ядре?

Поехали!

1. Когда ядро не пусто?

Разрешим каждому игроку трудиться в нескольких коалициях сразу. Каждый игрок будет распределять свое время (усилия) между несколькими коалициями. Предположим, что игроки распределяют свои усилия между коалициями в одинаковой пропорции. К пример, в коалиции ${S_{1}}$ все трудятся 20% своего времени, в коалиции ${S_{2}}$ — 30% своего времени и т.д.

С помощью ${lambda_{S}}$ обозначим долю своего времени (своих сил), которые игрок тратит трудясь на коалицию {S} . Конечно же, для любой коалиции {S} величина ${lambda_{S}in [0;1]}$ и ${sum_{S} lambda_{S}=1}$ (все свои усилия игрок куда-то тратит).

Для простоты введем:

Definition 1 Набор весов ${lambda_{S}}$ называется сбалансированным, если ${lambda_{S}in[0;1]}$ и ${sum_{S} lambda_{S}=1}$ .

Критерий непустоты ядра довольно прост:

Большая коалиция должна зарабатывать достаточно много, чтобы суметь пообещать каждой коалиции столько, чтобы у той не было желания отсоединиться. А именно:

Ядро не пусто, если и только если при любом распределении усилий игроков между коалициями их заработок не превосходит заработка большой коалиции.

Theorem 2 Бондарева. Ядро игры в характеристической форме непусто, если и только если для любого сбалансированного набора ${lambda_{S}}$ :

$displaystyle sum_{S} lambda_{S}v(S)leq v(N) (1)$

Proof: Если ядро непусто, то существует вектор {x} , такой что: ${sum_{iin S} x_{i}geq v(S)}$ для любой коалиции {S} .

Следовательно,

$displaystyle sum_{S} lambda_{S}v(S) leq sum_{S} lambda_{S} sum_{iin S} x_{i} leq sum_{S} lambda_{S} sum_{iin N} x_{i} = sum_{iin N} x_{i} sum_{S} lambda_{S} = sum_{iin N} x_{i} cdot 1 = v(N) (2)$

Доказательство в обратную сторону перенесено в приложение Box

2. Почему вектор Шепли — это хорошо?

Когда мы говорили о ядре, мы ввели два хороших свойства (эффективность и отсутствие сепаратистских тенденций), его определяющих. А из этих хороших свойств немедленно следует способ нахождения (решение системы неравенств).

Когда же мы говорили о векторе Шепли, мы ввели способ его подсчета (как матожидание). Потом мы доказали, что он также эффективен. А какими еще хорошими свойствами он обладает?

Давайте поговорим о справедливости! Справедливость для нас будет предcтавлена двумя требованиями: одинаковые игроки должны получать одинаковый выигрыш и бесполезные игроки должны получать ноль.

Definition 3 Назовем игрока «болваном» (dummy player), если он не добавляет ценность ни одной коалции. Игрок болван, если : . В частности, .

У Osborne dummy player определен как игрок, который в каждую коалицию приносит ровно свою стоимость {v(i)} и ни капли больше. Этому игроку логично выдать {v(i)} и исключить его из дальнейшего участия в дележе. На меньшее такой игрок не согласен сам, а больше ни одна коалиция не захочет ему плататить.

В соответствии с библейским принципом «Кто не работает, тот да не ест!» болваны должны получать ноль.

Definition 4 Платеж удовлетворяет условию «Болваны получают ноль», если (хм, неожиданно) болваны получают ноль.

Например, если в игру «Носки» добавить Васю без носков, то было бы справедливо, чтобы ему ничего не доставалось при дележе выигрыша. При подсчете вектора Шепли для игрока болвана {i} оказывается, что для любого порядка {pi} и, следовательно, .

Definition 5 Платеж удовлетворяет требованию симметричности, если одинаковые игроки получают одинаковый выигрыш.

Если два игрока вносят одинаковый вклад во все коалиции, то хочется, чтобы они получали одинаково. Например, в игре «Ботинки» у Лени и у Левы по одному левому ботинку. В векторе Шепли они получают одинаковый выигрыш. Для одинаковых игроков {i} и {j} величины их вкладов во все коалиции равны, поэтому случайные величины и имеют одинаковое распределение. Поэтому и их математические ожидания равны. (может тут поподробнее)

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

Definition 6 Правило , которое сопоставляет каждой игре некий дележ , называется линейным, если выполнены два условия:

1.

2. ${d(v_{1}+v_{2})=d(v_{1})+d(v_{2})}$

Что это означает?

Первое требование довольно логично. Пусть есть две игры. Одна задана характеристической функцией {v} . А во второй — выигрыши любой коалиции в {c} раз больше, чем в первой, т.е. выигрыши задаются функцией . Если мы придумали какой-то «справедливый» дележ для первой игры, {d(v)} , то «справедливый» дележ для второй игры должен быть .

Второе требование более запутанное. Пусть у нас снова есть две игры, ${v_{1}}$ и ${v_{2}}$ . Мы придумали «справедливый» дележ в каждой из игр, ${d(v_{1})}$ и ${d(v_{2})}$ . А теперь предложим нашим игрокам сыграть в третью игру, ${v=v_{1}+v_{2}}$ . В этой игре заработок коалиции {S} равен сумме заработков этой коалиции в изначальных двух играх, ${v(S)=v_{1}(S)+v_{2}(S)}$ . Согласно второму требованию «справедливый» дележ в игре {v} должен равняться сумме «справедливых» дележей в играх ${v_{1}}$ и ${v_{2}}$ . Насколько это согласуется с человеческими представлениями о справедливости? Хорошего ответа на этот вопрос я не знаю.

Theorem 7 Единственным дележом удовлетворяющим требованиям эффективности, линейности, «болваны получают ноль» и симметричности (одинаковые игроки получают одинаковый выигрыш) является вектор Шепли.

Сначала докажем, что вектор Шепли удовлетворяет всем этим свойствам: Мы уже фактически доказали, что вектор Шепли удовлетворяет требованиям эффективности, симметричности и требованию «болваны получают ноль». Проверяем только линейность.

Пусть теперь какое-нибудь правило дележа удовлетворяет четырем требованиям. Докажем, что это может быть только вектор Шепли. Для начала докажем это для простых игр.

Definition 8 Игра в характеристической форме называется простой, если игра супераддитивна и стоимость любой коалции всегда равна либо нулю, либо единице. Другими словами существует особая коалиция , такая что без ее участия в полном составе нельзя получить ничего, а с ее участием в полном составе можно получить единицу:

$displaystyle v_{S}(K)= begin{cases} 1, Ssubset K \ 0, Snot subset K \ end{cases} (3)$

Поскольку в простой игре все игроки не входящие в {S} — болваны, то они получают 0 (условие «болваны получают ноль»). А игроки входящие в {S} неразличимы между собой, и поэтому обязаны делить общий заработок {v(S)} поровну (условие эффективности плюс условие симметричности), т.е. получать ${frac{v(N)}{|S|}}$ . Значит, для простых игр условия «болваны получают ноль», симметричность и эффективность однозначно определяют дележ. А вектор Шепли им всегда удовлетворяет.

Рассмотрим произвольную игру в характеристической форме. Она полностью определяется функцией {v} . Функцию {v} можно записать в виде ${v=sum_{S}mu(S)v_{S}}$ . Это не что иное, как разложение вектора с помощью базиса. Для наглядности приведем пример:

Разложение игры «Носки» на простые игры. ${v=60v_{a}+120v_{b}+60v_{a,b}}$ .

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

3. Когда вектор Шепли лежит в ядре?

Есть такой красивое словосочетание «эффект снежного кома». Каков его смысл? Если катить маленький снежок, то он медленно растет, а если катить большой ком снега, то он быстро растет. Эта идея иногда верна и в кооперативных играх. К примеру, Вовочка подбивает Петю бойкотировать контрольную, которую устравивает Марь Иванна. Если бойкотировать контрольную пока согласен только сам Вовочка, то Петя мало что добавит к выигрышу Вовочки. А если бойкотировать уже согласны все в классе кроме Пети, то присоединение Пети к бойкотирующим резко увеличивает их выигрыш.

Возникает следующее определение.

Definition 9 Игра в характеристической форме проявляет «эффект снежного кома» (snowball effect), если для любого игрока и для любых коалиций не содержащих игрока выполнено условие:

Левая часть неравенства — это выигрыш маленькой коалции {K} от присоединения Пети, а правая часть — выигрыш крупной коалиции {L} от присоединения Пети.

Это определение эквивалентно более общепринятому, но менее наглядному определению супермодулярности:

Definition 10 Игра в характеристической форме называется супермодулярной (supermodular или convex), если для любых коалиций и :

Слово convex оказывается слишком перегруженным (есть convex set, convex function и пр.), поэтому чтобы избежать путаницы лучше использовать supermodular.

Докажем эквивалентность определений: Proof: Пусть игра {v} — супермодулярна. Пусть , . Рассмотрим коалиции и {T=L} . Применяем супермодулярность:

Игрок {i} не лежит ни в {K} , ни в {L} , поэтому:

Что дает определение игры с эффектом снежного кома.

Пусть игра {v} обладает эффектом снежного кома. Пусть {S} и {T} — две произвольные коалиции.

Шаг 1. Рассмотрим коалиции и {L=T} . По определению . Рассмотрим произвольного игрока, . В силу эффекта снежного кома:

Шаг 2. Добавим в коалиции {K} и {L} игрока {i} , при этом конечно, . Рассмотрим нового произвольного игрока, , . Применяем эффект снежного кома к :

Заметьте, что если сложить эти два неравенства, то получится:

Это легко интерпретируется: если два игрока {i} и {j} вступают в более крупную коалицию , то они приносят больший доход.

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

Вспомнив, что , а {L=T} , получаем:

что является определением супермодулярности. Box

Игры с «эффектом снежного кома» хороши тем, что:

Theorem 11 Ядро супермодулярной игры непусто

Proof:

Зафиксируем произвольный порядок формирования большой коалиции {pi} . Оказывается, что вектор лежит в ядре. Действительно:

Для того, чтобы не перегружать доказательство индексами поступим так. Во-первых, поскольку нумерация игроков произвольна, будем считать, что игроки входят в порядке: 1,2,3…, {n} . Если они входят в другом порядке, то перенумеруем их. Во-вторых, введем обозначение ${K_{i}}$ — это игроки первые {i} игроков, ${K_{i}={1,2,3,...,i}}$ . До игрока {i} , естественно успели войти игроки из ${K_{i-1}}$ .

Шаг 1. Рассмотрим произвольную коалицию из одного игрока {i} .

В силу супермодулярности:

$displaystyle v(K_{i-1}cap i)+v(K_{i-1}cup i)geq v(K_{i-1})+v(i) (13)$

Что равносильно:

$displaystyle v(i)leq v(K_{i-1}cup i)-v(K_{i-1}) (14)$

Значит, . Итак, ни один игрок не выиграет, если откажется от предлагаемого дележа и возьмет {v(i)} .

Индукция. Допустим мы доказали, что ни одной коалиции из {k-1} игрока не выгодно отсоединятся. Рассмотрим произвольную коалицию {K} из {k} игроков. В этой коалиции есть игрок с наибольшим номером {m} . Значит ${Ksubset K_{m}}$ , но ${Knot subset K_{m-1}}$ .

В силу супермодулярности:

$displaystyle v(K_{m-1}cap K)+v(K_{m-1}cup K)geq v(K_{m-1})+v(K) (15)$

Заметив, что ${K_{m-1}cup K=K_{m}}$ получаем:

$displaystyle v(K_{m-1}cap K)+v(K_{m})-v(K_{m-1})geq +v(K) (16)$

Разница ${v(K_{m})-v(K_{m-1})}$ — это то, что вектор Шепли отдает {m} -му игроку, т.е. ${v(K_{m})-v(K_{m-1})=Add(m,pi)}$ .

В коалиции ${K_{m-1}cap K}$ меньше участников, чем в {K} , значит по предположению индукции ей не выгодно отсоединяться, т.е.

$displaystyle sum_{iin K_{m-1}cap K}Add(i,pi)geq v(K_{m-1}cap K) (17)$

Получаем, что:

$displaystyle sum_{iin K_{m-1}cap K}Add(i,pi) + Add(m,pi)geq v(K) (18)$

Но в левой части стоит ровно та сумма денег, которая предлагается коалиции {K} , а значит и ей не выгодно отсоединятся. Box

Поскольку векторы — это то, что усредняет вектор Шепли мы немедленно получаем:

Theorem 12 Если игра — супермодулярная, то вектор Шепли лежит в ядре

Proof: Ядро задается системой линейных неравенств, значит оно является выпуклым множеством.

Поскольку для любого фиксированного порядка формирования большой коалиции {pi} вектор

лежит в ядре, то и все что находится «между» этими векторами лежит в ядре. Значит и вектор Шепли, как среднее арифметическое этих векторов, также лежит в ядре. Box

Более того, в супермодулярных играх верен и более точный результат:

Theorem 13 Ядро супермодулярной игры — это многогранник с вершинами в , где — это всемозвожные порядки формирования большой коалиции.

Оставим это утверждение без доказательства, но проиллюстрируем:

includegraphics{coop_gt.3}

4. Окончание доказательства т. Бондаревой, критерия непустоты ядра

Напомним формулировку:

Theorem 14 Бондарева. Ядро игры в характеристической форме непусто, если и только если для любого сбалансированного набора ${lambda_{S}}$ :

Proof:

Обратно. Пусть неравенство 20 выполнено.

Может есть какое-то более геометрическое доказательство?
У Данилова через т. Какутани. Приведенное доказательство взято из Osborne, Rubinstein

Для доказательства в обратную сторону нам понадобится технических факт:

Theorem 15 Два выпуклых множества в ${R^{n}}$ можно разделить гиперплоскостью.

Этот факт мы примем без доказательства как хорошо согласующийся с геометрическими представлениями.

Введем обозначение ${1_{S}}$ — это вектор из {n} чисел, каждое из которых равно нулю или единице, в зависимости от того, входит ли соответствующий участник в коалицию {S} . В частности, ${1_{N}}$ — это вектор из {n} единичек, а ${1_{emptyset}}$ — это вектор из {n} нулей. Например, если и коалиция , то ${1_{S}=(1,0,0,1)}$ .

Вектор ${1_{S}}$ лежит в {n} -мерном пространстве.

Допишем к вектору ${1_{S}}$ стоимость соответствующей коалиции, получим вектор ${(1_{S},v(S))}$ , лежащий в {(N+1)} -мерном пространстве.

Рассмотрим два множества (в ${R^{n+1}}$ ):

${A={(1_{N},v(N)+varepsilon)| varepsilon>0}}$ . Это множество выпуклое, т.к. это полупрямая с выколотым началом.

${B={sum_{S} lambda_{S} (1_{S},v(S)) | forall S lambda_{S}in [0;1] }}$ . Это множество также выпуклое, т.к. является линейной комбинацией конечного числа векторов с произвольными неотрицательными весами.

Эти множества не имеют общих точек, в силу неравенства 20. Оба множества выпуклы, значит существует гиперплоскость разделяющая множества {A} и {B} .

Как существование такой гиперплоскости записать математически?

Это означает, что существует такой ненулевой вектор ${vec{alpha}=(alpha_{1},alpha_{2},...,alpha_{n+1})}$ , что:

, для любых {ain A} и {bin B} .

Сначала мы докажем, что ${alpha_{n+1}<0}$ , а затем построим из ${(alpha_{1},alpha_{2},...,alpha_{n})}$ элемент ядра.

Заметим, что ${alpha_{n+1}}$ не может быть положительным: если бы оно было положительным можно было бы взять вектор {a} с большим и добиться положительности .

Уточним, что ${alpha_{n+1}}$ не может быть равен нулю. Для этого рассмотрим вектор ${v=(1_{N},v(N))}$ , начало полупрямой {A} . Он лежит в множестве {B} — достаточно взять ${lambda_{N}=1}$ , а остальные ${lambda_{S}=0}$ . Поскольку вектор {v} попадает на границу {A} для него неравенство выглядит так: .

Заметим, что ${vec{alpha}cdot v=sum_{i=1}^{N}alpha_{i}+alpha_{n+1}v(N)}$ .

При ${alpha_{n+1}}$ равном нулю мы получали бы, что ${sum_{i=1}^{n}alpha_{i}=0}$ . Но это невозможно, т.к. в этом случае равнялось бы нулю.

Маленький итог: ${alpha_{n+1}<0}$ . Значит неравенство 21 можно разделить на ${(-alpha_{n+1})}$ . При этом знаки неравенства не поменяются, а последняя компонента вектора превратится в минус единицу. Обозначим: ${x_{i}=-alpha_{i}/alpha_{n+1}}$ .

Что это нам дает?

Левая часть неравенства говорит: для любого {b} : ${(x_{1},x_{2},...,x_{n},-1)cdot b geq 0}$ .

Возьмем ${b=(1_{S},v(S))}$ . Получаем, ${sum_{iin S}x_{i}geq v(S)}$ .

Правая часть неравенства говорит: для любого {a} : ${(x_{1},x_{2},...,x_{n},-1)cdot a <0}$ .

Возьмем ${v=(1_{N},v(N))}$ . Этот вектор в {A} не входит, но лежит на границе {A} , поэтому неравенство будет нестрогим: ${sum_{iin N}x_{i}leq v(N)}$ .

Что это значит? Это означает, что есть такой вектор {x} , который большая коалиция может выплатить (может у нее даже что-то останется). При этом ни одна коалиция {S} не может получить больше, чем достается ей при дележе {x} . Следовательно, ядро не пусто.

Box

Источник