Кооперативные игры
Санкт-Петербургский
государственный университет сервиса и экономики
Старорусский
филиал
Реферат
"Кооперативные
игры"
Выполнила
студентка группы № 26
Яшина Александра
Старая Русса
Содержание
Введение <l >
. Кооперативные игры
<l >
. Решение
кооперативной игры при помощи вектора Шепли <l >
Заключение <l >
Список использованной
литературы <l >
Введение
Зачастую встречаются конфликтные ситуации с числом игроков больше двух,
где есть возможность объединения двух или более игроков для получения
совместной выгоды. Классический пример это объединение всех продавцов с целью
завышения цен. Для описания таких ситуаций служат кооперативные игры. Они
отвечают на вопрос кому и с кем выгодно объединятся, и стоит ли это делать
вообще.
В данной работе рассматриваются коалиционные (кооперативные) игры. Так же
приведено решение задачи при помощи аксиом Шепли.
1. Кооперативные игры
В России при построении математической модели конфликта делают различия
между коалицией действия и коалицией интересов. Коалицией действия называются
те или иные коллективы, участвующие в игре и принимающие решения. Коалицией
интересов называются коллективы, участвующие в игре и отстаивающие некоторые
общие интересы. Кроме того, вводится понятие ситуации - результат выбора всеми
коалициями действия своих стратегий.
Игра называется кооперативной, или коалиционной, если игроки могут
объединяться в группы, беря на себя некоторые обязательства перед другими
игроками и координируя свои действия. Этим она отличается от некооперативных
игр, в которых каждый обязан играть за себя. Развлекательные игры редко
являются кооперативными, однако такие механизмы нередки в повседневной жизни.
Из двух типов игр, некооперативные описывают ситуации в мельчайших
деталях и выдают более точные результаты. Кооперативные рассматривают процесс
игры в целом. Попытки объединить два подхода дали немалые результаты. Так
называемая программа Нэша уже нашла решения некоторых кооперативных игр как
ситуации равновесия некооперативных игр.
Гибридные игры включают в себя элементы кооперативных и некооперативных
игр. Например, игроки могут образовывать группы, но игра будет вестись в
некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы
своей группы, вместе с тем стараясь достичь личной выгоды.
Кооперативные игры получаются в тех случаях, когда, в игре n игроков
разрешается образовывать определённые коалиции. Обозначим через N множество
всех игроков, N ={1, 2,..., n}, а через K - любое его подмножество. Пусть
игроки из K договариваются между собой о совместных действиях и, таким образом,
образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r
игроков, равно числу сочетаний из n по r, то есть , а число всевозможных коалиций равно
конфликтный коалиционный кооперативный шепли
= 2n - 1.
Из этой формулы видно, что число всевозможных коалиций значительно растёт
в зависимости от числа всех игроков в данной игре. Для исследования этих игр
необходимо учитывать все возможные коалиции, и поэтому трудности исследований
возрастают с ростом n. Образовав коалицию, множество игроков K действует как
один игрок против остальных игроков, и выигрыш этой коалиции зависит от
применяемых стратегий каждым из n игроков.
Функция , ставящая в соответствие каждой коалиции K наибольший,
уверенно получаемый его выигрыш (K), называется характеристической
функцией игры. Так, например, для бескоалиционной игры n игроков (K)
может получиться, когда игроки из множества K оптимально действуют как один
игрок против остальных N\K игроков, образующих другую коалицию (второй игрок).
Характеристическая функция называется простой, если она
принимает только два значения: 0 и 1. Если характеристическая функция
простая, то коалиции K, для которых (K) =1, называются выигрывающими,
а коалиции K, для которых (K) = 0, - проигрывающими.
Если в простой характеристической функции выигрывающими являются
те и только те коалиции, которые содержат фиксированную непустую коалицию R, то
характеристическая функция , обозначаемая в этом случае через R,
называется простейшей.
Содержательно простые характеристические функции возникают, например, в
условиях голосования, когда коалиция является выигрывающей, если она собирает
более половины голосов (простое большинство) или не менее двух третей голосов
(квалифицированное большинство).
Более сложным является пример оценки результатов голосования в Совете
безопасности ООН, где выигрывающими коалициями являются все коалиции, состоящие
из всех пяти постоянных членов Совета плюс ещё хотя бы один непостоянный член,
и только они.
Простейшая характеристическая функция появляется, когда в голосующем
коллективе имеется некоторое "ядро", голосующее с соблюдением правила
"вето", а голоса остальных участников оказываются несущественными.
Обозначим через uG
характеристическую функцию бескоалиционной игры. Эта функция обладает
следующими свойствами:
Персональность: uG (Æ) = 0,т.е. коалиция, не содержащая ни одного игрока, ничего не
выигрывает;
Супераддитивность:
uG (KÈL) ³ uG (K) + uG
(L), если K, L Ì N,
KÇL ¹ Æ,
т.е. общий выигрыш коалиции не меньше суммарного выигрыша всех участников
коалиции;
Дополнительность:
uG (K) + u (N) = u (N)
т.е. для бескоалиционной игры с постоянной суммой сумма выигрышей
коалиции и остальных игроков должна равняться общей сумме выигрышей всех
игроков. Распределение выигрышей (делёж) игроков должно удовлетворять следующим
естественным условиям: если обозначить через xi выигрыш i-го игрока,
то, во-первых, должно удовлетворяться условие индивидуальной рациональности
т.е. любой игрок должен получить выигрыш в коалиции не меньше, чем он
получил бы, не участвуя в ней (в противном случае он не будет участвовать в
коалиции); во-вторых, должно удовлетворяться условие коллективной рациональности
= u
(N)
т.е. сумма выигрышей игроков должна соответствовать возможностям (если
сумма выигрышей всех игроков меньше, чем (N), то игрокам незачем
вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше,
чем (N), то это значит, что игроки должны делить между собой сумму
большую, чем у них есть). Таким образом, вектор x = (x1,..., xn),
удовлетворяющий условиям индивидуальной и коллективной рациональности, называется
дележём в условиях характеристической функции . Система {N, },
состоящая из множества игроков, характеристической функции над этим множеством
и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях
характеристической функции, называется классической кооперативной игрой.
Кооперативная игра с множеством игроков N и характеристической функцией
называется стратегически эквивалентной игрой с тем же множеством игроков и
характеристической функцией 1, если найдутся такие к
0 и произвольные вещественные Ci (iN), что для любой
коалиции К N имеет место равенство:
u1 (K) = k u (K) +
Смысл определения стратегической эквивалентности кооперативных игр (с. э.
к. и) состоит в том, что характеристические функции с. э. к. и. отличаются
только масштабом измерения выигрышей k и начальным капиталом Ci. Стратегическая
эквивалентность кооперативных игр с характеристическими функциями u и u1 обозначается так u~u1. Часто вместо стратегической эквивалентности кооперативных
игр говорят о стратегической эквивалентности их характеристических функций.
Справедливы следующие свойства для стратегических эквивалентных игр:
. Рефлексивность, т.е. каждая характеристическая функция эквивалентна
себе u~u.
. Симметрия, т.е. если u~u1,
то u1~u.
. Транзитивность, т.е. если u~u1 и u1~u2, то u~u2.
Одними из наиболее интересных способов решения коалиционных игр являются
решения с применением аксиом Шелли.
2. Решение
кооперативной игры при помощи вектора Шепли
Аксиомы Шепли:
. Аксиома эффективности. Если S - любой носитель игры с
характеристической функцией u, то
= u
(S)
Иными словами, "справедливость требует", что при разделении
общего выигрыша носителя игры ничего не выделять на долю посторонних, не
принадлежащих этому носителю, равно как и ничего не взимать с них.
. Аксиома симметрии. Для любой перестановки p и iÎN должно выполняться (pu) = ji (u), т.е. игроки, одинаково входящие в
игру, должны "по справедливости" получать одинаковые выигрыши.
. Аксиома агрегации. Если есть две игры с характеристическими функциями u¢ и u¢¢, то
j i (u¢ + u¢¢) = j i (u¢)
+ j i (u¢¢),
т.е. ради "справедливости" необходимо считать, что при участии
игроков в двух играх их выигрыши в отдельных играх должны складываться.
Определение. Вектором цен (вектором Шепли) игры с характеристической
функцией u называется
n-мерный вектор
j (u) = (j1 (u), j2
(u),..., jn (u)),
удовлетворяющий аксиомам Шепли.
Теорема. Существует единственная функция j, определённая для всех игр и удовлетворяющая аксиомам
Шепли.
Определение. Характеристическая функция wS (T), определённая для любой коалиции S, называется
простейшей, если
wS (T) =
Содержательно простейшая характеристическая функция описывает такое
положение дел, при котором множество игроков S выигрывает единицу тогда и
только тогда, когда оно содержит некоторую основную минимальную выигрывающую
коалицию S. Вектор Шепли содержательно можно интерпретировать следующим
образом: предельная величина, которую вносит i-й игрок в коалицию T, выражается
как u
(T) - u (T \{i}) и
считается выигрышем i-го игрока; gi (T) - это вероятность того, что i-й игрок вступит в коалицию T \{i}; ji (u) - средний выигрыш i-го игрока в
такой схеме интерпретации. В том случае, когда u - простейшая,
Следовательно
,
где суммирование по T распространяется на все такие выигрывающие коалиции
T, что коалиция T \{i}не является выигрывающей.
Пример. Рассматривается корпорация из четырёх акционеров, имеющих акции
соответственно в следующих размерах
1
= 10, a2 = 20, a3 = 30, a4 = 40.
Любое решение утверждается акционерами, имеющими в сумме большинство
акций. Это решение считается выигрышем, равным 1. Поэтому данная ситуация может
рассматриваться как простая игра четырёх игроков, в которой выигрывающими
коалициями являются следующие:
{2; 4}, {3; 4},
{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},
{1; 2; 3; 4}.
Найдём вектор Шепли для этой игры. При нахождении j1 необходимо учитывать, что имеется только одна
коалиция T = {1; 2; 3}, которая выигрывает, а коалиция T \{1} = {2; 3} не
выигрывает. В коалиции T имеется t = 3 игрока, поэтому
.
Далее, определяем все выигрывающие коалиции, но не выигрывающие без 2-го
игрока: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому
.
Аналогично получаем, что , . В результате получаем, что вектор Шепли равен . При этом, если считать, что вес
голоса акционера пропорционален количеству имеющихся у него акций, то получим
следующий вектор голосования , который, очевидно, отличается от вектора Шепли. Анализ игры
показывает, что компоненты 2-го и 3-го игроков равны, хотя третий игрок имеет
больше акций. Это получается вследствие того, что возможности образования коалиций
у 2-го и 3-го игрока одинаковые. Для 1-го и 4-го игрока ситуация естественная,
отвечающая силе их капитала.
Заключение
Кооперативная
теория игр, раздел теории <http://bse.sci-lib.com/article050432.html>
игр, в котором игры рассматриваются без учёта стратегических возможностей
игроков (тем самым кооперативная теория игр изучает некоторый класс моделей
общих игр). В частности, в кооперативной теории игр входит исследование
нестратегических (кооперативных) игр, лишённых с самого начала стратегического
аспекта. В кооперативной игре задаются возможности и предпочтения различных
групп игроков (коалиций) и из них выводятся оптимальные (устойчивые,
справедливые) для игроков ситуации, в том числе распределения между ними
суммарных выигрышей: устанавливаются сами принципы оптимальности, доказывается
их реализуемость в различных классах игр, и находятся конкретные реализации. В
терминах кооперативных игр поддаются описанию многие экономические и
социологические явления.
1. Большая советская энциклопедия, 1978 г.
2. Теория игр
<http://ecsocman.edu.ru/db/msg/54933.html> - статья Миркина Б.Г. на
портале "Экономика. Социология. Менеджмент".