Игры двух лиц с нулевой суммой

Пусть в игре участвует два игрока A и Б, партия состоит из одного хода игрока A и ответного хода игрока Б. Ход игрока A заключается в выборе одной из n возможных стратегий . Ход игрока Б со­стоит из выбора одной из m возможных стратегий . Каждая партия игры состоит в том, что партнеры выбирают по одной своей стра­тегии, в результате чего определяются платежи игрокам. Пусть игрок A выбирает стратегию , игрок Б - стратегию . В результате осуществ­ления операции платеж игрока A игроку Б составляет , а платеж игрока Б игроку A . Такая игра является игрой с нулевой суммой, так как выигрыш игрока А равен проигрышу игрока Б.

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

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

Игра, заданная платежной матрицей, называется прямоуголь­ной или матричной игрой, приведенной к нормальной форме.

В каждой партии игрок A стремится так выбрать свою стратегию , чтобы величина его платежа была минимально возможной. В свою очередь игрок Б стремится так выбрать стратегию , чтобы максимизи­ровать выигрыш. Задача состоит в том, чтобы указать оптимальные стратегии каждой стороны, т.е. такие стратегии, которые при многократ­ном повторении игры обеспечивают Б максимально возможный средний выигрыш, а игроку А - минимально возможный средний проигрыш.

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

Рассмотрим ситуацию с позиции игрока A. На каждую выбранную стратегию игрок Б ответит такой стратегией , чтобы максимизиро­вать выигрыш

.

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

.

Определенная так величина a называется верхней ценой игры или минимаксом, а стратегия - минимаксной стратегией A. Верхняя цена игры - это тот гарантированный уровень, больше которого A не заплатит при любом поведении Б, если будет применять свою минимаксную стра­тегию .

Рассмотрим теперь ситуацию с позиции игрока Б. При каждой стратегии сторона A применит такую стратегию , чтобы проиграть как можно меньше:

.

Следовательно, наилучший из наихудших для Б вариантов отве­чает такой стратегии , что

.

Величина b, определенная таким образом, называется нижней це­ной игры или максимином. Нижняя цена игры b - гарантированный выигрыш Б при любом ответе A.

Если

,

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

В общем случае .

Равновесие пары стратегий определяется для игры двух лиц так же, как и в общем случае игры n лиц. То, что платеж описывается ска­лярной величиной, а не вектором, упрощает дело.

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

Def. Седловой точкой называется некоторый элемент матрицы платежей R такой, что при любых i, j.

Таким образом, седловая точка одновременно является наиболь­шим элементом строки k и наименьшим элементом столбца l.

Если в некоторой игре существует более одной седловой, то пред­ставляет интерес следующая теорема.

Теорема. Пусть и - седловые точки. Тогда и также являются седловыми точками и, кроме того .

Кратко данную теорему можно выразить так: седловые точки экви­валентны и взаимозаменяемы.

Следует отметить, что сформулированное свойство не распростра­няется на другие игры, т.е. не выполняется для игр с ненулевой суммой или для игр трех и более лиц.

Теорема. Пусть - седловая точка игры с матрицей R. Тогда . И наоборот, если , то существует седловая точка , причем .

Если , то матричная игра не имеет седловой точки, и мини­максные стратегии не дают решения игры, так как не являются наилуч­шими ни для одной из сторон. В этом случае говорят, что игра не имеет решения в чистых стратегиях.

Дата добавления: 2015-06-04