Медленно, но неумолимо я приближаюсь к финалу курса "Теории игр" проекта Академия от @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 голосами имеет большее влияние на результаты голосования, он вето-игрок, а у остальных хотя количество голосов различно, но сила влияния на исход голосования одинакова.
ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА
Я узнал, что существуют коалиционные игры, вернее, что известные мне ситуации из реальной жизни описываются коалиционной теорией игр. Более подробно мною были рассмотрены две из множества концепций решения этих типов игр: ядро и вектор Шепли. Я понял, что одна из самых распространённых областей применения теории - политика, и, в частности, механизм голосования или влияния на принятия того или иного коалиционного решения. А ведущие игроки (вето-игроки) решают, практически, всё.
Ваш пост поддержали следующие Инвесторы Сообщества "Добрый кит":
litrbooh, neo, mir, lira, orezaku, yuriks2000, newodin, vika-teplo, borisss, kondratij, anatolich, felicita, dim447, nikitosuna, sansey, evgeniy1989
Поэтому я тоже проголосовал за него!
Узнать подробности о сообществе можно тут:
Разрешите представиться - Кит Добрый
Правила
Инструкция по внесению Инвестиционного взноса
Вы тоже можете стать Инвестором и поддержать проект!!!
Если Вы хотите отказаться от поддержки Доброго Кита, то ответьте на этот комментарий командой "!нехочу"
dobryj.kit теперь стал Делегатом! Ваш голос важен для всего сообщества!!!
Поддержите нас на странице https://golos.io/~witnesses, вот так: