Применение алгоритмов теории игр в экономических системах (стр. 3 из 8)
Игры с нулевой суммой - общий капитал всех игроков не меняется, а перераспределяется между игроками. В игре с нулевой суммой и двумя участниками выигрыш одного из них равен проигрышу другого. Таким образом, в играх с нулевой суммой существует конфликт между игроками, и поэтому их называют также антагонистическими играми. Они отражают суть принципа: «мой проигрыш - ваш выигрыш мой выигрыш - ваш проигрыш» и представляют собой ситуации чистого конфликта без всяких элементов сотрудничества. Примерами таких игр может служить покер, где один выигрывает все ставки других; либо банальное воровство.
Игры с постоянной разностью, в которых игроки и выигрывают, и проигрывают одновременно, так что им выгодно действовать сообща. Игрой с отличной от нуля суммой является торговля, где каждый участник извлекает выгоду. Сюда также относятся го, шашки и шахматы; в двух последних игрок может превратить свою рядовую фигуру в более сильную, получив преимущество. Во всех этих случаях сумма игры увеличивается. Широко известным примером, где она уменьшается, является война.
По виду функций выигрыша игры делятся на: матричные, биматричные.
Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путём сведения игры к задаче линейного программирования.
Биматричная игра – это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец – стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице – выигрыш игрока 2.) [12].
Также существуют следующие типы игр:
· Симметричные и несимметричные
Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков — симметричные. В частности, таковой является: «Дилемма заключённого». В качестве несимметричных игр можно привести «Ультиматум».
· Параллельные и последовательные
В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. В последовательных, или динамических, играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. Эта информация может быть даже не совсем полной, например, игрок может узнать, что его противник из десяти своих стратегий точно не выбрал пятую, ничего не узнав о других.
· С полной или неполной информацией
Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников. Большинство изучаемых в математике игр — с неполной информацией. Например, вся «соль» «Дилеммы заключённого» или «Сравнения монеток» заключается в их неполноте.
В то же время есть интересные примеры игр с полной информацией: «Ультиматум», «Многоножка». Сюда же относятся шахматы, шашки и другие.
Часто понятие полной информации путают с похожим — совершенной информации. Для последнего достаточно лишь знание всех доступных противникам стратегий, знание всех их ходов необязательно [13].
1.4 Представление игр
Представить игру можно двумя следующими способами:
Первый способ предполагает следующее:
1) перечисление ходов, которые могут делать игроки;
2) определение информации, которой располагают игроки в процессе игры;
3) определение возможных вариантов действий игроков;
Игра «Ультиматум» в экстенсивной форме.
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.
На рисунке 1. 1 — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
Рисунок 1.1 - Представление игр в экстенсивной форме
4) указание предельных размеров платежей в конце игры.
Игру, описанную подобным образом, называют игрой в развернутой, или экстенсивной форме, а само описание, как правило, составляют в виде дерева игры, аналогичного дереву решений. Игры в развернутой форме называют также позиционными играми.
Игру в развернутой форме называют игрой с полной информацией,если в ней нельзя делать одновременно несколько ходов и если участникам известны выборы, сделанные при предшествующих ходах, включая и случайные ходы. Примером игры с полной информацией являются шахматы. Покер представляет собой игру с неполной информацией, так как игрокам неизвестно, какие карты находятся на руках у противника [12].
Второй способ описания игры состоит в том, что рассматриваются все возможные стратегии каждого игрока и определяются платежи, соответствующие любой возможной комбинации стратегий всех игроков. Описанная таким образом игра называется игрой в нормальной форме.
Нормальная форма игры двух участников состоит из платежной матрицы, показывающей, какую сумму получает каждый из игроков при любой из возможных стратегий (см. рисунок 1.2).
Элементами этой матрицы являются пары чисел, первое из которых определяет величину выигрыша игрока 1, а второе — игрока 2.
Рисунок 1.2 - Платежная матрица для игры двух участников
Игрок 1 выбирает одну из m стратегий A1, A2,…,Am. Игрок 2 выбирает одну из n стратегий B1, B2,…,Bn. Пара чисел на пересечении строки и столбца, которые соответствуют стратегиям, избранным игроками, показывает величину выигрыша каждого из них. Если игрок 1 выбирает Ai, а игрок 2 -Bj, то выигрыши игроков 1 и 2 равны соответственно aij и bij (i=1,..,m; j=1,..,n).
Платежная матрица имеет размерность m×n, где m — (конечное) число возможных стратегий игрока 1, а n — (конечное) число возможных стратегий игрока 2. Предполагается, что каждому из игроков известны все элементы платежной матрицы [14].
1.5 Матричные игры. Игры с нулевой суммой. Решение матричных игр в чистых стратегиях
Матричные игры — игры, в которых участвуют два игрока (1 и 2) с противоположными интересами, причём каждый игрок имеет конечное число чистых стратегий.
Игра называется игрой с нулевой суммой, если одна сторона выигрывает то, что проигрывает другая, т. е. сумма выигрышей 1 и 2 равна нулю. В жизни часто встречаются конфликты, в которых это условие не выполняется. Например, в военном столкновении вполне возможно, что проигрывают обе стороны. Однако во многих случаях можно, не слишком искажая сущность явления, рассматривать парные конфликты как игры с нулевой суммой.
Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок имеет m стратегий i = 1,2,...,m , второй имеет n стратегий j = 1,2,...,n . Каждой паре стратегий (i ,j) поставлено в соответствие число аij , выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i -ю стратегию, а 2 – свою j -ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i -ю стратегию
, 2 – свою j -ю стратегию 
, после чего игрок 1 получает выигрыш аijза счёт игрока 2 (если аij < 0, то это значит, что игрок 1 платит второму сумму | аij| ). На этом игра заканчивается.Каждая стратегия игрока i =
; j = 
часто называется чистой стратегией.Если рассмотреть матрицу
,то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j -го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij .