Академия. Теория игр. Неделя 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 голосами имеет большее влияние на результаты голосования, он вето-игрок, а у остальных хотя количество голосов различно, но сила влияния на исход голосования одинакова.
ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА
Я узнал, что существуют коалиционные игры, вернее, что известные мне ситуации из реальной жизни описываются коалиционной теорией игр. Более подробно мною были рассмотрены две из множества концепций решения этих типов игр: ядро и вектор Шепли. Я понял, что одна из самых распространённых областей применения теории - политика, и, в частности, механизм голосования или влияния на принятия того или иного коалиционного решения. А ведущие игроки (вето-игроки) решают, практически, всё.