Принципы решения матричных антагонистических игр

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

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

Назовем v нижней ценой игры, или максимином - это гарантированный выигрыш игрока А при любой стратегии игрока В. Стратегия, соответствующая максимину, называется максиминной стратегией (их может быть несколько).

Игрок В также заинтересован в увеличении своего выигрыша, а, значит, в уменьшении выигрыша игрока А. Выбирая стратегию Вj, он учитывает максимально возможный выигрыш игрока А - βj (наибольшее число в j-м столбце матрицы Н). Среди всех чисел βj выберем наименьшее βj и назовем V верхней ценой игры, или минимаксом. Это – гарантированный проигрыш игрока В (V с обратным знаком – гарантированный выигрыш игрока В). Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

Каждая фиксированная стратегия, которую может выбрать игрок, называется его чистой стратегией.

Матричная игра имеет решение в чистых стратегиях, если игра имеет равновесную ситуацию – когда ν = V = ν*, где

Если ν = V = ν*, то решение игры в чистых стратегиях достигается в седловых точках. Любая пара (i₀, j₀) называется седловой точкой, когда существует элемент матрицы a_i0j0, обладающий свойством a_ij0 ≤ a_i0j0 ≤ a_i0j, т. е. когда элемент матрицы a_i0j0 – минимальный в своей строке и в то же время максимальный в столбце.

Если обозначить через p1, p2,..., pm вероятности (частоты), с которыми первый игрок выбирает соответственно первую, вторую,..., m-ю чистую стратегию, так что

через q1, q2,,..., qn — вероятности, с которыми второй игрок выбирает первую, вторую,..., n-ю свою чистую стратегию, причем

то наборы чисел P = (p1, p2,...,..., pm) и Q = (q1, q2,..., qn) называются смешанными стратегиями первого и второго игроков соответственно.

Каждый игрок имеет бесчисленное множество смешанных стратегий.