Матричные игры. Теория матричных игр. Основные определения и теоремы теории матричных игр. Запись матричной игры в виде платежной матрицы

Нижняя цена игры всегда не превосходит верхнюю цену игры.

Игра с седловой точкой есть игра, для которой .

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

стратегии.

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

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

7.2. Запись матричной игры в виде платежной матрицы

Рассмотрим конечную игру, в которой первый игрок А имеет m стратегий, а второй игрок B имеет n стратегий. Такая игра называется игрой m×n. Обозначим стратегии A₁, А₂, ..., А_m и В₁, В₂, ..., В_n. Предположим, что каждая сторона выбрала определенную стратегию A_i или B_j. Если игра состоит только из личных ходов, то выбор стратегий однозначно определяет исход игры – выигрыш одной из сторон a_ij. Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A_i и B есть случайная величина, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша будет математическое ожидание случайного выигрыша, которое тоже обозначается как a_ij.

Предположим, что известны значения a_ij при каждой паре стратегий. Эти значения можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют стратегиям A_i, столбцы – стратегиям B_j. Тогда в общем виде матричную игру можно записать следующей платежной матрицей:

где A_i – названия стратегий игрока 1, B_j – названия стратегий игрока 2, a_ij – значения выигрышей игрока 1 при выборе им i-й стратегии, а игроком 2 – j-й стратегии. Поскольку игра есть игра с нулевой суммой, значение выигрыша для игрока 2 является величиной, противоположенной по знаку значению выигрыша игрока 1.

7.3. Понятие о нижней и верхней цене игры. Решение игры в чистых стратегиях

Каждый из игроков стремится максимизировать свой выигрыш с учетом поведения противодействующего игрока. Поэтому для игрока 1 необходимо определить минимальные значения выигрышей в каждой из стратегий, а затем найти максимум из этих значений, то есть определить величину V_н = max_i min_j a_ij или найти минимальные значения по каждой из строк платежной матрицы, а затем определить максимальное из этих значений. Величина V_н называется максимином матрицы или нижней ценой игры. Стратегия игрока, которая соответствует максимину V_н, называется максиминной стратегией.

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

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

V_в = min_j max_i a_ij или найти максимальные значения по каждому из столбцов платежной матрицы, а затем определить минимальное из этих значений. Величина V_в называется

минимаксом матрицы – верхней ценой игры или минимаксным выигрышем.

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

В случае, когда значения V_н и V_в не совпадают, при сохранении правил