Матричная игра двух лиц с нулевой суммой

Лабораторная работа №3

Стратегические игры

Игра — это математическая модель конфликтной ситуации, которая предполагает наличие следующих компонент:

а) заинтересованных сторон;

б) возможных действий каждой стороны;
в) интересов сторон.

В игре заинтересованные стороны называются игроками, каждый из которых может предпринимать не менее двух действий (если игрок имеет в своем распоряжении только одно действие, то он фактически не участвует в игре, поскольку заранее известно, что он предпримет). Само слово «игра» применяется для обозначения некоторого набора правил и соглашений, составляющих данный вид игры, например: футбол, карточная игра, шахматы.

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

Для игр характерна неопределенность результата (исхода). Причины или источники неопределенности относятся к трем группам:
• комбинаторные источники (шахматы);
• влияние случайных факторов (игра в орлянку, кости, карточные игры, где расклад является случайным);
• стратегическое происхождение неопределенности: игрок не знает, какого образа действий придерживается его противник; здесь неопределенность исходит от другого лица; соответствующие игры называются стратегическими.
Таким образом, в стратегической игре действия предпринимают две или более стороны, в отличие от нестратегической игры, в которой действия предпринимает одна сторона, а остальные являются заинтересованными сторонами.

Классификации стратегических игр

Игры различают по:
1) числу игроков (игра 2-х лиц, игра п лиц (п> 2));
2) количеству игроков и их стратегиям (конечные, бесконечные);
3) количеству информации, имеющейся у игроков относительно прошлых ходов (игры с полной, игры с неполной информацией); шахматы — пример игры с полной информацией;
4) принципу деления выигрыша (коалиционные, бескоалиционные).

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

Матричная игра двух лиц с нулевой суммой

Вигре двух лиц с нулевой суммой (такую игру называют также антагонистической) принимают участие два игрока: игрок 1 и игрок 2.

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

Пусть и множества стратегий игрока 1 и 2, соответственно. Элементы множества А – возможные стратегии (действия) игрока 1, элементы множества В – стратегии игрока 2. Множество А содержит т элементов, множество В п элементов.

Условия игры представлены так называемой функцией выигрыша игрока 1:

Н(аi, bj), где aiÎ А — стратегия i игрока 1, bjÎ В — стратегия j игрока 2.

В игре с нулевой суммой выигрыш игрока 2 равносилен проигрышу игрока 1 и равен —Н(аi, bj).

Предполагается, что функция выигрыша обоим игрокам известна. Поскольку игроков двое и игра антагонистическая, коалиции невозможны. Игра, в которой множества стратегий игроков конечны, называется матричной. В этом случае функция выигрышей игрока 1 имеет вид матрицы, называемой матрицей игры (матрица выигрышей, платежная матрица)

.

Строки этой матрицы соответствуют стратегиям игрока 1, столбцы — стратегиям игрока 2.

Элемент матрицы это выигрыш игрока 1 в случае, когда он применит стратегию аi, а его противник — стратегию bj.

Элементы матрицы могут быть положительными, отрицательными или равными нулю. Случай, когда элемент матрицы положителен, означает, что игрок 2 в определенной ситуации должен уплатить игроку 1 сумму, равную значению этого элемента. Если элемент отрицателен, игрок 1 уплачивает игроку 2 сумму, равную абсолютному значению этого элемента. И, наконец, если этот элемент равен нулю, выплаты не производится. Таким образом, в игре двух лиц с нулевой суммой один игрок выигрывает столько же, сколько проигрывает другой (все выплаты производятся из «карманов» противников). Это и объясняет название — игра с нулевой суммой.

Игрок 1 стремится к максимальному выигрышу, игрок 2 — к минимальному проигрышу. Решить игру — значит найти оптимальные стратегии игроков и их выигрыши.

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

Допустим, что согласно правилам игры, игрок 1 может выбрать произвольную строку матрицы и, следовательно, может выбрать одно из чисел 1, ..., т.

Аналогично, игрок 2 имеет возможность выбора произвольного столбца матрицы выигрышей и, следовательно, одно из чисел 1, ..., п.

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

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

Рассмотрим процесс принятия решений обеими сторонами, предполагая, что игроки действуют рационально.

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

Принято говорить, что при таком образе действий игрок 1 руководствуется принципом максиминного выигрыша.

Этот выигрыш определяется формулой . Величина a называется нижней ценой игры, максиминным выигрышем, или сокращенно максимином.

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

Принято говорить, игрок 2 руководствуется принципом минимаксного проигрыша.

Этот проигрыш определяется выражением . Величина b называется верхней ценой игры или минимаксом.

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

Для любой игры с нулевой суммой a ≤ b чем и объясняются названия «нижняя цена» и «верхняя цена».

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

Ситуация, в которой нижняя и верхняя цены игры совпадают, называется седловой точкой.

Пример 1Пусть матрица некоторой игры имеет вид:

A\B	b1	b2	b3	b4	минимальный выигрыш игрока 1
a1
а2
а3
Максимальный проигрыш игрока 2

В этой игре партнер 1 имеет три возможные стратегии: а1, а2, а3,

а партнер 2 — четыре возможные стратегии b1, b2, b3, b4.

Рассмотрим процесс принятия игроками решения (предполагается, что они принимают в данной ситуации рациональные решения).

Взглянув на матрицу игры, можно заметить, что если игрок 1 не знает, как поступит его противник, то действуя наиболее целесообразно и, считая, что противник будет действовать подобным же образом, он выберет стратегию а₂, которая гарантирует ему наибольший из трех возможных наименьших выигрышей: 9, 13, 8. Другими словами, игрок 1 руководствуется принципом максиминного выигрыша. Этот выигрыш есть нижняя цена игры. Для нашего примера он равен 13.
Игрок 2 рассуждает аналогично: если он выберет стратегию b3 то потеряет самое большее 23, если стратегию b2, то — 40 и т.д. В результате он выберет стратегию b3, которая гарантирует ему наименьший из четырех возможных проигрышей:
23, 40, 13, 25.

Принято говорить, что игрок 2 руководствуется принципом минимаксного проигрыша. Этот проигрыш . Для нашей матрицы b = 13.

Ситуация (а2, b3) есть седловая точка, и а = 13 есть цена игры.
При наличии седловой точки ни одному из участников игры невыгодно отклоняться от своей минимаксной стратегии: он будет наказан противником, тем, что получит меньший выигрыш.

ПРИМЕР1. Где строить?
Две конкурирующие крупные торговые фирмы Ф1 и Ф2, планируют построить в одном из четырех небольших городов Г1, Г2, Г3, и Г4, лежащих вдоль автомагистрали, по одному универсаму. Взаимное расположение городов, расстояние между ними и численность населения показаны на следующей схеме.

30 тыс. человек Г1	50 тыс. человек Г2	40 тыс, человек Г3	30 тыс. человек Г4
40км	ЗОкм	5Окм

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

Условия	Распределение оборота между фирмами, %
Ф1	Ф2
Универсам фирмы Ф1 расположен к городу ближе универсама фирмы Ф2
Универсамы обеих фирм расположены на одинаковом расстоянии от города
Универсам фирмы Ф1 расположен от города дальше универсама фирмы Ф2

Например, если универсам фирмы Ф1 расположен к городу ближе универсама фирмы Ф2, то оборот фирм от покупок, сделанных жителями данного города, распределится следующим образом: 75% получит Ф1, остальное — Ф2.

Представьте описанную ситуацию, как игру двух лиц и определите, в каких городах целесообразно фирмам построить свои универсамы.