logo
ЛОИИ методичка 2015

Представление игры в матричной форме

П

Рисунок 1 – Матрица игры

усть имеется игра, в которой у игрока А существуетm стратегий, а у игрока В – п стратегий. Обозначим эти стратегии соответственно Аь А2,…, Ат и Вь В2,…, Вп. Такая игра называется игрой (т * п). Обозначим а^ выигрыш игрока А при использовании им стратегии Ai? А игроком В – стратегий Bj. Если для каждой пары стратегий Aj,Bj выигрыш а^ известен, то можно построить матрицу игры (платежную матрицу), изображенную на рисунке 1. В этом случае говорят, что игра представлена в матричной форме.

Рассмотрим антагонистическую игру двух сторон (m.n), представленную в матричной форме. Поиск оптимальных стратегий игроков осуществляется, используя так называемый «принцип минимакса». По этому принципу для игрока А оптимальной является максиминная стратегия, т.е. стратегия, максимизирующая минимальный выигрыш игрока А. Этот гарантированный выигрыш называется нижней ценой игры. Обозначим его а.

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

Можно показать, что в общем случае а <= р. Если а = р = V, то имеем игру с седловой точкой, а выигрыш V называется ценой игры. Стратегии А*, В* дающие выигрыш V называются оптимальными, чистыми стратегиями, а их совокупность называется решением игры. При наличии седловой точки в игре говорят, что игра решается в чистых стратегиях.

Рисунок 2 – Матрица игры с седловой точкой

Седловых точек может быть несколько, в этом случае имеется несколько оптимальных стратегий. При этом во всех седловых точках платежи одинаковы и равны цене игры V . На рисунке 2 приведена матрица игры (3x4) с седловой точкой.

    1. Yandex.RTB R-A-252273-3
      Yandex.RTB R-A-252273-4