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

В игре двух лиц с нулевой суммой (такую игру называют также антагонистической) принимают участие два игрока: игрок 1 и иг­рок 2. В распоряжении каждого из них имеется множество стра­тегий. Под стратегией понимают совокупность правил (принци­пов), определяющих выбор варианта действий при каждом ходе игро­ка в зависимости от сложившейся ситуации. Пусть А = { а ₁, а ₂ ,... } — множество стратегий игрока 1, В = { b ₁, b ₂ ,... } — множество стра­тегий игрока 2. Элементы множества А — возможные стратегии (действия) игрока 1, элементы множества В — стратегии игрока 2. Условия игры представлены так называемой функцией выигрыша игрока 1: H (a_i, b_j), где а_i Î А — i -я стратегия игрока 1, b_j Î В — j -я стратегия игрока 2. В игре с нулевой суммой выигрыш игрока 2 равносилен проигрышу игрока 1 и равен поэтому — H (a_i, b_j). Пред­полагается, что функция выигрыша обоим игрокам известна. По­скольку игроков всего двое и игра антагонистическая, коалиции невозможны.

Игра, в которой множества А и В стратегий игроков конечны, т.е. | А | < ¥, | В |< ¥, называется матричной. В этом случае функ­ция выигрышей игрока 1 имеет вид матрицы, называемой матри­цей игры (матрицей выигрышей, платежной матрицей) Н = { а_ij } _m,n, i = 1,..., т; j = 1,..., п. Строки этой матрицы соответствуют стра­тегиям a ₁, а ₂ ,..., а_m игрока 1, столбцы — стратегиям b ₁, b ₂ ,..., b_n игрока 2. Элемент матрицы a_ij = H (a_i, b_j) — выигрыш игрока 1 в случае, когда он применит стратегию а_i, а его противник — стра­тегию b_j, i = 1,..., т; j = 1,..., п.

Элементы матрицы могут быть положительными, отрицатель­ными или равными нулю. Случай, когда данный элемент матри­цы положителен, означает, что игрок 2 в определенной ситуа­ции должен уплатить игроку 1 сумму, равную значению этого эле­мента. Если данный элемент отрицателен, игрок 1 уплачивает игроку 2 сумму, равную абсолютному значению этого элемента. И наконец, если этот элемент равен нулю, никакой выплаты не производится. Таким образом, в игре двух лиц с нулевой суммой один игрок выигрывает столько же, сколько проигрывает другой (все выплаты производятся из «карманов» противников). Это и объясняет название — игра с нулевой суммой.

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

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

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

Если игрок 1 не знает, как поступит его противник, то, дей­ствуя наиболее целесообразно, не желая рисковать и считая, что противник также будет действовать целесообразно, он выберет такую стратегию, которая гарантирует ему наибольший из наи­меньших выигрышей при любой стратегии противника. Принято говорить, что при таком образе действий игрок 1 руководству­ется принципом максиминного выигрыша. Этот выигрыш определя­ется формулой a = a_ij. Величина a называется нижней ценой игры, максиминным выигрышем, или сокращенно — максимином.

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

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

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

Здесь р ₁, р ₂ ,..., р_m — вероятности использования игроком 1 в смешанной стратегии своих чистых стратегий a ₁, a ₂,..., a_m; q ₁, q ₂ ,..., q_n — вероятности использования игроком 2 в смешан­ной стратегии своих чистых стратегий b ₁, b ₂ ,..., b_n.

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

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

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

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

Сведение игры двух лиц с нулевой суммой к задаче линейного программирования. Если седловая точка отсутствует, то общим методом решения игры любой (конечной) размерности является сведение игры двух лиц с нулевой суммой к задаче линейного профаммирования. Из основного положения теории стратегичес­ких игр следует, что при использовании смешанных стратегий существует по меньшей мере одно оптимальное решение с ценой игры v, причем a £ v £ b, т.е. цена игры находится между ниж­ним и верхним значениями игры. Величина v неизвестна, но мож­но предположить, что v > 0. Это условие выполняется, поскольку путем преобразования матрицы всегда можно сделать все ее эле­менты положительными. Таким образом, если в исходной платеж­ной матрице имеется хотя бы один неположительный элемент, то первым шагом в процедуре сведения игры к задаче линейного программирования должно быть ее преобразование в матрицу, все элементы которой строго положительны. Для этого достаточ­но увеличить все элементы исходной матрицы на одно и то же число d > | a_ij |, где а_ij £0. При таком преобразовании мат­рицы оптимальные стратегии игроков не изменяются.

Допустим, что смешанная стратегия игрока 1 складывается из стратегий a ₁, a ₂,..., a_m с вероятностями соответственно p ₁, p _2, ..., p_{m (} , ). Оптимальная смешанная стратегия игрока 2 скла­дывается из стратегий b ₁, b _2, ..., b_n с вероятностями q ₁, q _2, ..., q_n (, ). Условия игры определяются платежной матрицей , , i = 1,..., m; j = 1,..., n.

Если игрок 1 применяет оптимальную смешанную стратегию, а игрок 2 — чистую стратегию b_j, то средний выигрыш игрока 1 (математическое ожидание выигрыша) составит р ₁ a _{1 j} + р ₂ a _{2 j} + ... + р_ma_mj, j = 1,..., n.

Игрок 1 стремится к тому, чтобы при любой стратегии игрока 2 его выигрыш был не менее чем цена игры v и сама цена игры была максимальной. Такое поведение игрока 1 описывается следующей моделью линейного программирования:

v ® max (игрок 1 стремится максимизировать свой выигрыш),

или, обозначив х_i = р_i /v, имеем

Причем

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

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

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