1. Матричная игра двух лиц с нулевой суммой

Игра, в которой множества А и В стратегий игроков конечны, т.е. |А| < ?, |В| < ?, называется матричной. В этом случае функция выигрышей игрока 1 имеет вид матрицы, называемой матрицей игры (матрицей выигрышей, платежной матрицей) Н = {ау}т>„, i = 1,..., т; j = 1,..., п. Строки этой матрицы соответствуют стратегиям аь а2, ..., ат игрока 1, столбцы — стратегиям Ъь Ъ2, ..., Ъп игрока 2. Элемент матрицы aij = H (ai, bJ) — выигрыш игрока 1 в случае, когда он применит стратегию аи а его противник — стратегию bj, i = 1, ..., т; j = 1, ..., п.

Элементы матрицы могут быть положительными, отрицательными или равными нулю. Случай, когда данный элемент матрицы положителен, означает, что игрок 2 в определенной ситуации должен уплатить игроку 1 сумму, равную значению этого элемента. Если данный элемент отрицателен, игрок 1 уплачивает игроку 2 сумму, равную абсолютному значению этого элемента. И наконец, если этот элемент равен нулю, никакой выплаты не производится.

Игрок 1 стремится к максимальному выигрышу, игрок 2 — к минимальному проигрышу. Решить игру — значит найти оптимальные стратегии игроков и их выигрыши.

В игре двух лиц с нулевой суммой, как и в любой другой стратегической игре, исход зависит от поведения обоих игроков, которое основывается на так называемых правилах игры. Допустим, что по правилам игры игрок 1 может выбрать произвольную строку матрицы и, следовательно, может выбрать одно из чисел 1, 2, ..., т. Аналогично игрок 2 имеет возможность выбора произвольного столбца матрицы выигрышей и, следовательно, одного из чисел 1, 2,..., п. Исход (результат) игры и, следовательно, сумму, которую игрок 2 должен уплатить игроку 1, определяет элемент матрицы выигрышей, находящийся на пересечении строки, выбранной игроком 1, и столбца, выбранного игроком 2. Ни один из партнеров не знает, какую стратегию применит его противник. Таким образом, имеет место ситуация полной неопределенности, при которой теория вероятностей не может помочь игрокам в выборе решения.

Рассмотрим процесс принятия решений обеими сторонами более детально, предполагая, что игроки действуют рационально.

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

max min

максиминного выигрыша. Этот выигрыш определяется формулой a = \' j aj. Величина a называется нижней ценой игры, максиминным выигрышем, или сокращенно — максимином.

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

выражением b = j \' . Величина b называется верхней ценой игры или минимаксом.

Принцип осторожности, который определяет выбор партнерами стратегий, соответствующих максиминному выигрышу или минимаксному проигрышу, часто называют принципом минимакса, а стратегии, вытекающие из этого принципа, — минимаксными стратегиями. Доказано, что всегда а 5 р, чем и объясняются названия «нижняя цена» и «верхняя цена». В случае когда нижняя цена игры равняется ее верхней цене, их общее значение называется ценой игры. При этом результат стратегической игры двух лиц с нулевой суммой можно определить, не приступая к фактической игре: вполне реален сценарий, когда партнеры, взглянув на матрицу, рассчитываются, пожимают друг другу руки и расходятся. Очевидно, что исход такой игры не изменится, если она будет повторена многократно, поскольку ни одному из игроков невыгодно отклоняться от своих минимаксных стратегий. Ситуация, в которой нижняя и верхняя цены игры совпадают, называется седловой точкой. Формальное определение: ситуация (а*, Ъ*) є Ах В называется седловой точкой, если

И {аb*) = max {Н(а,, b/); і = 1, ..., т} =

= min{#(a;, b.y,j--l, ..., п}.

/ j

В седловой точке элемент матрицы ау* = H(a*, bj*) является одновременно наименьшим в строке и наибольшим в столбце и, следовательно, соответствует цене игры. Однако существуют матрицы игры двух лиц с нулевой суммой (и таких игр большинство), для которых a Ф b, т.е. седловая точка отсутствует. Исход такой игры определить труднее, поскольку какой-либо одной так называемой чистой оптимальной стратегии ни для одного игрока не существует. В таких случаях говорят, что решение игры в чистых стратегиях отсутствует, и рассматривают так называемое смешанное расширение игры, решение которой ищут в смешанных стратегиях. Смешанная стратегия игрока — это случайная величина, значениями которой являются его чистые стратегии.

Для матричной игры т х п обозначим через Р = (ри р2,рт)

смешанную стратегию игрока 1, где рх >0, рг> 0, ..., рт > 0,

і т ^

Ер,. = 1, через Q = q2,..., qn) смешанную стратегию игрока 2,

где qx > 0, > 0, ..., qn > 0, І q} = 1.

Здесь рь р2,..., рт — вероятности использования игроком 1 в смешанной стратегии своих чистых стратегий ab a2, ..., am; qb q2, ..., qn — вероятности использования игроком 2 в смешанной стратегии своих чистых стратегий bb b2, ..., bn.

Математическое ожидание выигрыша игрока 1:

М (P,Q)=iiaijPiqj.

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

Пусть Р* — смешанная стратегия игрока 1,Q* — смешанная стратегия игрока 2. Ситуацию (P*,Q*), при которой М(Р, Q*) < М(Р*, Q*) < М(Р*, Q), называют седловой точкой смешанного расширения игры, а математическое ожидание выигрыша v = М(Р*, Q *) — ценой игры, причем всегда a < v < b.

Доминирование стратегий. Если платежная матрица такова, что каждый элемент некоторой строки i не меньше соответствующего элемента строки к и по меньшей мере один ее элемент строго больше соответствующего элемента строки k, то говорят, что стратегия а, игрока 1 доминирует его стратегию а-. Доминируемая стратегия не может быть оптимальной чистой стратегией игрока 1 и даже не может войти в его оптимальную смешанную стратегию с ненулевой вероятностью, поэтому ее можно исключить из рассмотрения, вычеркнув из матрицы строку k. Аналогично: если каждый элемент некоторого столбца j не больше соответствующего элемента столбца r и по меньшей мере один его элемент строго меньше соответствующего элемента столбца r, то говорят, что стратегия bj игрока 2 доминирует его стратегию br Поэтому столбец r матрицы можно вычеркнуть.

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

существует по меньшей мере одно оптимальное решение с ценой игры v, причем a < v < b, т.е. цена игры находится между нижним и верхним значениями игры. Величина v неизвестна, но можно предположить, что v > 0. Это условие выполняется, поскольку путем преобразования матрицы всегда можно сделать все ее элементы положительными. Таким образом, если в исходной платежной матрице имеется хотя бы один неположительный элемент, то первым шагом в процедуре сведения игры к задаче линейного программирования должно быть ее преобразование в матрицу, все элементы которой строго положительны. Для этого достаточно увеличить все элементы исходной матрицы на

max min

одно и то же число d > \' j |aj|, где аj < 0. При таком преобразовании матрицы оптимальные стратегии игроков не изменяются. Допустим, что смешанная стратегия игрока 1 складывается из стратегий a1, a2,..., am с вероятностями

т

Е Р. = 1 Р > U

соответственно p1, Р2,..., Рт (г=1 , ). Оптимальная смешанная стратегия игрока 2 скла-

т

Е qj = 1 q > и

дывается из стратегий Ъ1, Ъ2...., Ъп с вероятностями q1, q2,..., qn (j =1 , j ). Условия игры

„ {a.,} a > 0 . , определяются платежной матрицей ч}т,п, v , . = 1,..., m; j = 1,..., п.

Если игрок 1 применяет оптимальную смешанную стратегию, а игрок 2 — чистую стратегию Ъj, то

средний выигрыш игрока 1 (математическое ожидание выигрыша) составит р^у + р^у + ... + р^щ, j

= 1,..., п.

Игрок 1 стремится к тому, чтобы при любой стратегии игрока 2 его выигрыш был не менее чем цена игры v и сама цена игры была максимальной. Такое поведение игрока 1 описывается следующей моделью линейного программирования: v —> шах (игрок 1 стремится максимизировать свой выигрыш), Р\\а\\\\ +Рга21 + ••• + Ртат 1 Р\\а\\2 + Р2°22 + - + Ртат2 S V>

Р\\а\\п + Р2°2п + - + Ртатп S V\'

р{+р2 + - +Рт = і.

UD

а1пх1 + в2#Л + - + "шА * \'>

х, > 0, /= 1,..., т.

Причем

V = 1/(х, + + ... +Хт).

Поведению игрока 2 соответствует двойственная задача:

Уі + у2 + ••• + у„ -> max

(эквивалентно v min: игрок 2 стремится минимизировать свой средний проигрыш),

>(2)

а\\\\У\\ + а\\гУг + - + а\\Л ^ 1. + ЗД + ••• + а2пУп * 1>

«тЛ + + - + ОтпУп *

У;> 0, у\'= 1, ..., л,

где j>y= ^-/v.

Задача (1) всегда имеет решение. Получив ее оптимальное решение xi\'-,c2\' —>*m>, можно найти цену игры v _ 1/(^1++ •••оптимальные значения Pi>_Pi> ¦¦•> Рт и, следовательно, оптимальную стратегию игрока 1. Если исходная матрица увеличивалась на d, то для получения цены первоначальной игры v* нужно уменьшить на d.

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