Матричные игры

Рассмотрим игру, в которой участвуют два игрока, причем каждый из них имеет конечное число стратегий. Обозначим для удобства одного из игроков через A, а другого – через B.

Предположим, что игрок A имеет m стратегий, а игрок – n стратегий. Пусть игрок A выбрал стратегию A_i, а игрок B – стратегию B_j. Будем считать, что выбор игроками стратегий и однозначно определяет исход игры – выигрыш игрока A a_ij и выигрыш игрока B - b_ij, причем эти выигрыши связаны равенством

a_ij = - b_ij

(отрицательный выигрыш на бытовом языке обычно называют проигрышем).

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

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

Полученная матрица имеет размеры n×m и называется матрицей игры или платежной матрицей (отсюда и название игры – матричная). Заметим, что если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой - от игрока требуется сделать только один ход: выбрать стратегию

Рассматриваемую игру часто называют игрой n×m или n×m-игрой.

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

Рассмотрим пример игры G (4×5) в матричной форме. В нашем распоряжении (на выбор) четыре стратегии, у противника — пять стратегий. Матрица игры дана в таблице 1.

Таблица 1

Какой стратегией нам (игроку А) воспользоваться? В таблице 1 есть соблазнительный выигрыш 10, соответствующий стратегии A₃. Но если противник выберет стратегию В₃, и мы получим выигрыш 1. Очевидно, выбор стратегии необходимо осуществлять исходя из принципа осторожности (а он — основной принцип теории игр), т.е. надо выбрать ту стратегию, при которой наш минимальный выигрыш максимален. Это — так называемый «принцип минимакса»: поступай так, чтобы при наихудшем для тебя поведении противника получить максимальный вы­игрыш.

Перепишем таблицу 1 и в правом добавочном столбце запишем минимальное значение выигрыша в каждой строке (минимум строки); обозначим его для i-й строки a_i (см. таблицу 2).

Таблица 2

Из всех значений α_i (правый столбец) выделено наибольшее (3). Ему соответствует стратегия А₄. Вы­брав эту стратегию, мы во всяком случае можем быть уверены, что при любом поведении противника выиг­раем не меньше, чем 3. Эта величина — наш гарантированный выигрыш; ведя себя осторожно, меньше этого мы получить не можем. Этот выигрыш называется ниж­ней ценой игры (или «максимином» - максималь­ный из минимальных выигрышей). Будем обозначать его α. В нашем случае α = 3.

Теперь станем на точку зрения противника и по­рассуждаем за него. Выбирая стратегию, он хотел бы от­дать поменьше, но должен рассчитывать на наше, наи­худшее для него, поведение. Для этого при­пишем к таблице 2 добавочную нижнюю строку и в ней запишем максимумы столбцов β_j. Очевидно, осто­рожный противник должен выбрать ту стратегию, при которой эта величина минимальна (соответствующее значение 5 выделено в таблице 2). Эта величина β — то значение выигрыша, больше которого заведомо не отдаст нам разумный противник. Она называется верхней ценой игры (или «минимаксом» — минимальный из максимальных выигры­шей). В нашем примере β = 5 и достигается при стра­тегии противника В₃.

Итак, исходя из принципа осторожности (перестра­ховочного правила «всегда рассчитывай на худшее!»), мы должны выбрать стратегию А₄, а противник — стратегию В₃. Такие стратегии называются «мини­максными» (вытекающими из принципа минимакса). До тех пор, пока обе стороны в нашем примере будут придерживаться своих минимаксных стратегий, выиг­рыш будет равен а₄₃ = 3.

Однако минимаксные стратегии неустойчивы по отношению к информа­ции о поведении другой стороны; эти стратегии не об­ладают свойством равновесия.

Всегда ли это так? Нет, не всегда. Рассмотрим при­мер с матрицей, данной в таблице 2.

Таблица 3

В этом примере нижняя цена игры равна верхней: α = β = 6. Что из этого вытекает? Минимаксные стра­тегии игроков А и В будут устойчивыми. Пока оба игрока их придерживаются, выигрыш равен 6. Потому что любое отступление от стратегии А₂ может только ухудшить наше положение. Равным образом, информация, полученная противником, не заставит его отступить от своей стратегии В₂. Пара стратегий А₂ и В₂ обладает свойством равновесия (уравновешенная па­ра стратегий), а выигрыш (в нашем случае 6), дости­гаемый при этой паре стратегии, называется «седловой точкой матрицы». Признак наличия седловой точки и уравновешенной пары стратегий - это равенство нижней и верхней цены игры; общее значение α и β называется ценой игры. Мы будем обозначать его v.

Стратегии (в данном случае А₂, В₂), при ко­торых этот выигрыш достигается, называются опти­мальными чистыми стратегиями, а их со­вокупность — решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях. Обеим сторонам А и В можно указать их оптимальные стратегии, при которых их положе­ние — наилучшее из возможных.

Наличие седловой точки в игре — это далеко не правило, скорее — исключение. Большинство игр не имеет седловой точки. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это — так называемые «игры с полной информацией». Игрой с полной информацией называется такая игра, в которой каждый игрок при каждом личном ходе знает всю предысторию ее развития, т. е. результаты всех преды­дущих ходов, как личных, так и случайных. Примера­ми игр с полной информацией могут служить: шашки, шахматы, «крестики и нолики» и т. п.

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

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

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

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

Будем обозначать смешанные стратегии игроков А и В соответственно S_A = (p₁, р₂, …, р_т), S_B = (q₁, q₂,..., q_n), где p₁, р₂, …, р_т – полная группа событий, образующих в сумме единицу - вероятности применения игроком А стратегий А₁, A₂, ..., А_т; q₁, q₂, ..., q_n - аналогичные вероятности применения игро­ком В стратегий В₁, В₂, ..., В_п. В частном случае, ко­гда все вероятности, кроме одной, равны нулю, а эта одна — единице, смешанная стратегия превращается в чистую.

Существует основная теорема теории игр: любая конечная игра двух лиц с нулевой суммой име­ет по крайней мере одно решение — пару оптимальных стратегий, в общем случае смешанных (S*_А, S*_B), и соответствующую цену v.

Пара оптимальных стратегий (S*_А, S*_B), образующих решение игры, обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отсту­пать от своей. Эта пара стратегий образует в игре не­кое положение равновесия: один игрок хочет обратить выигрыш в максимум, другой — в минимум, каждый тянет в свою сторону и, при разумном поведении обо­их, устанавливается равновесие и устойчивый выиг­рыш v. Если v > 0, то игра выгодна для А, если v < 0 — для противника; при v = 0 игра «справедли­вая», одинаково выгодная для обоих участников.

Рассмотрим пример игры без седловой точки и при­ведем (без доказательства) ее решение. Игра состоит в следующем: два игрока А и В одновременно и не сговариваясь показывают один, два или три пальца. Выигрыш решает общее количество пальцев: если оно четное, выигрывает А и получает у В сумму, равную этому числу; если нечетное, то, наоборот, А платит В сумму, равную этому числу. Как поступать игрокам?

Составим матрицу игры. В одной партии у каждого игрока три стратегии: показать один, два или три пальца. Матрица 3×3 дана в таблице 4; в дополни­тельном правом столбце приведены минимумы строк, а в дополнительной нижней строке - максимумы столбцов.

Нижняя цена игры α = -3 и соответствует страте­гии А₁. Это значит, что при разумном, осторожном поведении мы гарантируем, что не проиграем больше, чем 3. Слабое утешение, но все же лучше, чем, ска­жем, выигрыш -5, встречающийся в некоторых клет­ках матрицы. Однако положение противника, кажется, еще хуже: нижняя цена игры β = 4, т. е. при разумном поведении он от­даст нам минимум 4.

Таблица 4

В общем, положение не слишком хорошее — ни для той, ни для другой стороны. Но по­смотрим: нельзя ли его улучшить? Оказывается, мож­но. Если каждая сторона будет применять не одну какую-то чистую стратегию, а смешанную, в которую первая и третья входят с вероятностями 1/4, а вто­рая — с вероятностью 1/2, т. е.

S^*_А = (1/4, 1/2, 1/4), S*_B = (1/4, 1/2, 1/4),

то средний выигрыш будет устойчиво равен нулю (зна­чит, игра «справедлива» и одинаково выгодна той и другой стороне). Стратегии S_A, S_B образуют решение игры, а ее цена v = 0.