Академия. Теория игр. Неделя 10.

Медленно, но неумолимо я приближаюсь к финалу курса "Теории игр"  проекта Академия от @ontofractal и, если оглянуться назад, то можно увидеть колючие заросли определений, через которые мне пришлось продираться, штабеля матриц и дремучие леса деревьев Игры. 

Иногда я ощущаю себя одним из героев Германа Гессе )))

ВВЕДЕНИЕ В КОАЛИЦИОННУЮ ТЕОРИЮ ИГР

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

Игра "Сороконожка". В некотором царстве-государстве правительство вдруг решает выделить деньги на развитие одного из двух ведущих университетов. Сюжет достаточно сказочный, но идея в принципе распределения этой спонсорской помощи. Ректору первого университета предлагается сумма в $1. Если он согласится, то получит эту сумму, и игра закончится. Если не согласится, то ректору второго университета предложат уже $10 и т.д. Последняя сумма в $100 000 000 (если игроки до неё доберутся) будет предложена ректору первого университета и в случае его согласия перейдёт в собственность учебного заведения. В противном случае игра заканчивается, и ни один из университетов ничего не получает. Дерево игры похоже на сороконожку:

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

Время определений пришло:

Например, есть три игрока: Боря, Витя и Галя. Они могут образовать 8 коалиций: пустую, три по одному человеку, 3 по два человека и одну большую. Пусть значения характеристической функции будут следующие: у большой коалиции выигрыш равен 5, у коалиций по два человека - 2 и во всех остальных случаях - 0. Обозначать всё это я буду так:

На характеристические функции часто накладывается свойство супераддитивности:

В коалиционных играх, которые я буду рассматривать, игроки стремятся к объединению в группы и решать будут только одно - как поделить между собой выигрыш. Это распределение будет представлено в виде "вектора выигрышей":

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

КОНЦЕПЦИЯ РЕШЕНИЯ КОАЛИЦИОННЫХ ИГР: ЯДРО

Итак, некоторые игроки объединились в коалицию. Я хочу, чтобы вектор выигрышей обладал следующими свойствами:

1) он должен быть эффективным - всё должно быть распределено между всеми;

2) он должен быть коалиционно рационален - не должно найтись такой меньшей коалиции, которой было бы выгодно отколоться от данной.

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

Витя с Борей продают на улице блины. Витя может их печь, а Боре очень хорошо удаётся начинка. Блины с начинкой принесут им платёж в $300. Если бы Витя работал один, то пустые блины принесли бы ему $200, а одна начинка вообще бы ничего не принесла Боре. Как должны распределиться между ними платежи, чтобы они вступили в коалицию? 

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

Витя должен получить не меньше $200, Боря вообще будет рад любой денежке, а в сумме у них должно быть $300. Тогда ядро будет выглядеть следующим образом:

Теперь другая ситуация. У Бори, Вити и Гали есть пицца, которую они должны поделить. Коалиция из большего количества игроков может силой забрать всю пиццу себе. В этом случае ядро уже будет выглядеть иначе:

Но если сложить неравенства 2, 3 и 4, то сумма платежей всех игроков будет равна 1,5, что противоречит неравенству 5. Значит, в этой игре ядро пусто. То есть большая коалиция не стабильна, всегда найдутся желающие отколоться от неё.

Получается, что у концепции "ядро" есть два недостатка: 

1) оно может состоять из слишком большого числа различных векторов платежей;

2) оно может быть пустым.

Ядро можно применить не для всякой коалиционной игры.

КОНЦЕПЦИЯ РЕШЕНИЯ КОАЛИЦИОННЫХ ИГР: ВЕКТОР ШЕПЛИ

Пусть формируется большая коалиция. Я хочу, чтобы вектор платежей обладал следующими свойствами:

1) эффективность - сумма выигрышей всех игроков равна выигрышу большой коалиции;

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

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

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

Существует единственный вектор платежей, обладающий всеми четырьмя свойствами - вектор Шепли. И его можно даже вычислить по вот такой простенькой формуле:

Она показывает выигрыш i-го игрока.

Пусть коалиция формируется из трёх игроков случайным образом:

Тогда большую коалицию можно сформировать 3! способами или в общем случае - n! 

Вернусь к страшной формуле. Пусть i-й игрок присоединяется к уже существующей коалиции. Каким будет его вклад? В формуле он выделен красным цветом:

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

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

Компонента для Вити будет другой:

Те же результаты можно получить и из следующей таблицы:

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

ПРОСТЫЕ ИГРЫ

Ну, наконец-то, хоть что-то простое начинается ))) Хотя, игровые теоретики - весёлые ребята, могли и что-то суперсложное назвать простым. 

Итак, 

Пока, вроде бы, ничего сложного. Коалиция К, называется выигрывающей, если v(K)=1 и проигрывающей, если v(K)=0. 

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

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

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

А ядро описывается системой:

Её можно упростить:

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

1) в простой игре с вето-игроками последние делят весь выигрыш большой коалиции между собой;

2) ядро простой игры не пусто тогда и только тогда, когда в ней есть хотя бы один вето-игрок.

в 1954 году вектор Шепли стал использоваться для анализа голосований и применительно к простым играм его стали называть индексом влияния Шепли-Шубика.

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

Среди игр с голосованием есть отдельная группа, называемая голосование с квотой.

Рассмотрю следующую игру на голосование с квотой. Пусть у одного игрока 4 голоса, у второго - 2, у третьего и четвёртого - по 1. Квота равна 5, то есть для принятия решения хватит 5 голосов. В этом случае выигрыш коалиции равен 1, в противном случае - 0. Составлю таблицу, где слева выпишу все выигрывающие коалиции, а сверху - всех игроков. На пересечении строк и столбцов буду ставить 1, если игрок вверху является ключевым для коалиции слева:

Первый игрок является ключевым для трех коалиций размера 2, для трех коалиций размера 3 и для одной коалиции размера 4, и его компонента индекса Шепли-Шубика будет равна 3/4:

Аналогично можно вычислить компоненты индекса для остальных игроков. У них она одинакова и равна по 1/12. То есть, игрок с 4 голосами имеет большее влияние на результаты голосования, он вето-игрок, а у остальных хотя количество голосов различно, но сила влияния на исход голосования одинакова.

 

ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА 

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

“Конспект подготовлен для Академии Голоса @academy”