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

Пусть в игре участвует два игрока 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.Тогда.И наоборот,если,то существует седловая точка,причем.

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