Антагонистические матричные игры

⇐ ПредыдущаяСтр 20 из 21Следующая ⇒

Самым простым случаем, подробно разработанным в теории игр, является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций). Рассмотрим такую игру G, в которой участвуют два игрока А и В, имеющие противоположные интересы: выигрыш одного равен проигрышу другого. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, мы можем интересоваться только выигрышем а игрока А. Естественно, А хочет максимизировать, а В — минимизировать а. Для простоты отождествим себя мысленно с одним из игроков (пусть это будет А) и будем его называть «мы», а игрока В — «противник» (разумеется, никаких реальных преимуществ для А из этого не вытекает). Пусть у нас имеется т возможных стратегий А₁, A₂, ..., А_m, а у противника — n возможных стратегий В₁, В₂, ..; В_n (такая игра называется игрой т × n). Обозначим а_ij наш выигрыш в случае, если мы пользуемся стратегией A_i, а противник—стратегией B_j.

Таблица 26.1

A_i B_j	B₁	B₂	…	B_n
A₁ A₂ … A_m	a₁₁ a₂₁ … a_m1	a₂₁ a … a_m	… … … …	a₁_n a₂_n … a_mn

Предположим, что для каждой пары стратегий Л<, В, выигрыш (или средний выигрыш) a, j нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (см. таблицу 26.1).

Если такая таблица составлена, то говорят, что игра G приведена к матричной форме (само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и практически невыполнимую, из-за необозримого множества стратегий). Заметим, что если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой — от игрока требуется сделать только один ход: выбрать стратегию. Будем кратко обозначать матрицу игры (a_ij).

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

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

Таблица 26.2

B_j A_i	B₁	B₂	B₃	B₄	B₅
A₁ A₂ A₃ A₄

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

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

Таблица 26.3

B_j A_i	B₁	B₂	B₃	B₄	B₅	α _i
A₁ A₂ A₃ A₄
β _j

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

Теперь станем на точку зрения противника и порассуждаем за него. Он ведь не пешка какая-нибудь, а тоже разумен! Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Если он выберет стратегию В₁, мы ему ответим А₃, и он отдаст 10; если выберет B₂ — мы ему ответим А₂, и он отдаст 8 и т. д. Припишем к таблице 26.3 добавочную нижнюю строку и в ней запишем максимумы столбцов β _j. Очевидно, осторожный противник должен выбрать ту стратегию, при которой эта величина минимальна (соответствующее значение 5 выделено в таблице 26.3). Эта величина β — то значение выигрыша, больше которого заведомо не отдаст нам разумный противник. Она называется верхней ценой игры (или «минимаксом» — минимальный из максимальных выигрышей). В нашем примере β = 5 и достигается при стратегии противника B₃.

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

Теперь представим себе на минуту, что мы узнали о том, что противник придерживается стратегии В₃. А ну-ка, накажем его за это и выберем стратегию А₁ — мы получим 5, а это не так уж плохо. Но ведь противник — тоже не промах; пусть он узнал, что наша стратегия А₁; он тоже поторопится выбрать В₄, сведя наш выигрыш к 2, и т. д. (партнеры «заметались по стратегиям»). Одним словом, минимаксные стратегии в нашем примере неустойчивы по отношению к информации о поведении другой стороны; эти стратегиине обладают свойством равновесия.

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

В этом примере нижняя Цена игры равна верхней: α = β = 6. Что из этого вытекает? Минимаксные стратегии игроков А и В будут устойчивыми. Пока оба игрока их придерживаются, выигрыш равен 6. Посмотрим, что будет, если мы (А) узнаем, что противник (В)

Таблица 26.4

B_j A_i	B₁	B₂	B₃	B₄	α _i
A₁ A₂ A₃
β _j

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

α = β = v

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

¹) Термин «седловая точка» взят из геометрии — так называется точка на поверхности, где одновременно достигается минимум по одной координате и максимум по другой.

У читателя может возникнуть вопрос: а почему оптимальные стратегии называются «чистыми»? Несколько забегая вперед, ответим на этот вопрос: бывают стратегии «смешанные», состоящие в том, что игрок применяет не одну какую-то стратегию, а несколько, перемежая их случайным образом. Так вот, если допустить кроме чистых еще и смешанные стратегии, всякая конечная игра имеет решение — точку равновесия. Но об атом речь еще впереди.

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

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

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

А теперь спросим себя, как быть, если игра не имеет седловой точки: α ≠ β ? Ну что же, если каждый игрок вынужден выбрать одну - единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно скоп стратегии «смешивать», чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он «передоверяет» свой выбор случайности, «бросает жребий», и берет ту стратегию, которая выпала (как организовать жребий, мы уже знаем из предыдущей главы).

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

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

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

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

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

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

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

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

Таблица 26.5

B_j A_i	B₁	B₂	B₃	α _i
A₁ A₂ A₃	-3	-3 -5	-5	-3 -5 -5
β _j

первая и третья входят с вероятностями 1/4, а вторая — с вероятностью 1/2, т. е.

то средний выигрыш будет устойчиво равен нулю (значит, игра «справедлива» и одинаково выгодна той и другой стороне). Стратегии образуют решение игры, а ее цена v = 0. Как мы это решение нашли? Это вопрос другой. В следующем параграфе мы покажем, как вообще решаются конечные игры.

Методы решения конечных игр

Перед тем, как решать игру m× n, нужно, прежде всего, попытаться ее упростить, избавившись от лишних стратегий. Это делается подобно тому, как мы когда-то отбрасывали заведомо невыгодные решения в § 6. Введем понятие «доминирования». Стратегия A_i игрока А называется доминирующей над стратегией А_k, если в строке A_i стоят выигрыши не меньшие, чем в соответствующих клетках строки A_k, и из них по крайней мере один действительно больше, чем в соответствующей клетке строки А_k. Если все выигрыши строки A_i, равны соответствующим выигрышам строки A_k, то стратегия А_i называется дублирующей стратегию A_k. Аналогично определяются доминирование и дублирование для стратегий игрока В: доминирующей называется та его стратегия, при которой везде стоят выигрыши не большие, чем в соответствующих клетках другой, и по крайней мере один из них действительно меньше; дублирование означает полное повторение одного столбца другим. Естественно, что если для какой-то стратегии есть доминирующая, то эту стратегию можно отбросить; также отбрасываются и дублирующие стратегии.

Поясним сказанное примером. Пусть игра 5× 5 задана матрицей таблицы 27.1.

Таблица 27.1

B_j A_i	B₁	B₂	B₃	B₄	B₅
A₁ A₂ A₃ A₄ A₅

Прежде всего заметим, что в ней стратегия A₅ дублирует стратегию А₂, поэтому любую из них можно отбросить. Отбрасывая A₅, замечаем, что в строке А₁ все выигрыши больше (или равны) соответствующим выигрышам строки А₄ значит А₁ доминирует над A₄. Отбросим A₄ и получим матрицу 3× 5 (таблица 27.2).

Но это еще не все! Приглядевшись к таблице 27.2, замечаем, что в ней некоторые стратегии игрока В доминируют над другими: например, B₃ над B₄, и В₅, a B₁ — над стратегией В₂ (не забудьте, что В стремится отдать поменьше! ).

Таблица 27.2

B_j A_i	B₁	B₂	B₃	B₄	B₅
A₁ A₂ A₃

Отбрасывая столбцы B₂, В₄, В₅, получаем игру 3× 2 (таблица 27.3).

Наконец, в таблице 27.3 строка А₃ дублирует А₁, поэтому ее можно отбросить. Окончательно получим игру 2× 2 (таблица 27.4).

Таблица 27.3

B_j A_i	B₁	B₃
A₁ A₂ A₃

Таблица 27.4

B_j A_i	B₁	B₃
A₁ A₂

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

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

Пусть имеется игра т× п без седловой точки с матрицей (а_ij) (см. таблицу 27.5).

Таблица 27.5

A_i B_j	B₁	B₂	…	B_n
A₁ A₂ … A_m	a₁₁ a₂₁ … a_m1	a₁₂ a₂₂ … a_m2	… … … …	a_1n a_2n … a_mn

Допустим, что все выигрыши а_ij положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решение не изменится). Если все a_ij положительны, то конечно, и цена игры, т. е. средний выигрыш при оптимальной стратегии, тоже положителен: v > 0.

Мы хотим найти решение игры, т. е. две оптимальные смешанные стратегии

(27.1)

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

Найдем сначала Мы знаем, что если один из игроков (в данном случае это А) применяет свою оптимальную стратегию, то другой (В) не может улучшить свое положение, отступая от своей. Заставим противника (В) отступать от своей оптимальной стратегии, пользуясь чистыми стратегиями В₁, B₂, ..., В_n (а мы тем временем упорно держимся стратегии ). В любом случае наш выигрыш будет не меньше, чем v:

(27.2)

Разделим неравенства (27.2) на положительную величину v и введем обозначения:

(27.3)

Тогда условия (27.2) примут вид

(27.4)

где x₁, x₂, ..., x_m — неотрицательные переменные. В силу (27.3) и того, что p₁ + р₂ +... + р_m = 1, переменные x₁, x₂,..., х_m удовлетворяют условию

х₁, + х₂, +... + x_m = . (27.5)

Но v есть не что иное, как наш гарантированный выигрыш, естественно, мы хотим сделать его максимальным, а значит, величину — минимальной.

Таким образом, задача решения игры свелась к математической задаче: найти неотрицательные значения переменных х₁, х₂, ..., x_m такие, чтобы они удовлетворяли линейным ограничениям-неравенствам (27.4) и обращали в минимум линейную функцию этих переменных:

L = х₁, + х₂, +... + x_m => min. (27.6)

«Ба! — скажет читатель, — что-то знакомое! » И точно — перед нами не что иное, как задача линейного программирования. Таким образом, задача решения игры т× п свелась к задаче линейного программирования с n ограничениями-неравенствами и т переменными. Зная x₁, x₂, ..., x_m, можно по формулам (27.3) найти p₁, р₂, ..., р_m и, значит, оптимальную стратегию и цену игры v.

Оптимальная стратегия игрока В находится совершенно аналогично, с той разницей, что В стремится минизировать, а не максимизировать выигрыш, а значит, обратить не в минимум, а в максимум величину , а в ограничениях-неравенствах вместо знаков ≥ будут стоять ≤. Пара задач линейного программирования, по которой находятся оптимальные стратегии , называется парой двойственных задач линейного программирования (доказано, что максимум линейной функции в одной из них равен минимуму линейной функции в другой, так что все в порядке — разных значений цены игры мы не получим).

Таким образом, решение игры m× п эквивалентно решению задачи линейного программирования. Нужно заметить, что и наоборот, — для любой задачи линейного программирования может быть построена эквивалентная ей задача теории игр (на том, как это делается, мы останавливаться не будем). Эта связь задач теории игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения игр, которые в некоторых случаях (при большой размерности задачи) оказываются проще, чем «классические» методы линейного программирования.

Опишем один из самых простых численных методов решения игр — так называемый метод итераций (иначе — метод Брауна — Робинсон). Идея его в следующем. Разыгрывается «мысленный эксперимент», в котором стороны А и В поочередно применяют друг против друга свои стратегии, стремясь выиграть побольше (проиграть поменьше). Эксперимент состоит из ряда «партий» игры. Начинается он с того, что один из игроков (скажем, А) выбирает произвольно одну из своих стратегий A_i. Противник (В) отвечает ему той из своих стратегий B_j которая хуже всего для А, т. е. обращает его выигрыш при стратегии 4, в минимум. Дальше снова очередь А —он отвечает В той своей стратегией А_k, которая дает максимальный выигрыш при стратегии В_j противника. Дальше — снова очередь противника. Он отвечает нам той своей стратегией, которая является наихудшей не для последней, примененной нами, стратегии А_k, а для смешанной стратегии, в которой досих пор примененные стратегии A_i, A_k встречаются с равными вероятностями. И так далее: на каждом шаге итерационного процесса каждый игрок отвечает на очередной ход другого той своей стратегией, которая является оптимальной для него относительно смешанной стратегии другого, в которую все примененные до сих пор стратегии входят пропорционально частотам их применения. Вместо того чтобы вычислять каждый раз средний выигрыш, можно пользоваться просто «накопленным» за предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный выигрыш максимален (минимален). Доказано, что такой метод сходится: при увеличении числа «партий» средний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий — к их вероятностям в оптимальных смешанных стратегиях игроков.

Впрочем, лучше всего можно понять итерационный метод на конкретном примере. Продемонстрируем его на примере игры 3× 3 предыдущего параграфа (таблица 26.5). Чтобы не иметь дела с отрицательными числами, прибавим к элементам матрицы таблицы 26.5 число 5 (см. таблицу 27.6); при этом цена игры увеличится на 5, а решение не изменится.

Начнем с произвольно выбранной стратегии игрока А, — например, со стратегии А₃. В таблице 27.7 приведены первые 15 шагов итерационного процесса по методу Брауна — Робинсон (читатель может самостоятельно продолжить расчеты).

Таблица 27.6

B_j A_i	B₁	B₂	B₃
A₁ A₂ A₃

В первом столбце дан номер партии (пары выборов) k, во втором — номер i выбранной в данной партии стратегии игрока А. В последующих трех столбцах — «накопленный выигрыш» за первые k партий при тех стратегиях, которые применяли игроки в предыдущих партиях и при стратегиях В₁, В₂, B₃ игрока В в данной партии (получается прибавлением элементов соответствующей строки к тому, что было строкой выше). Из этих накопленных

выигрышей в таблице 27.7 подчеркнут минимальный (если их несколько, подчеркиваются все). Подчеркнутое число определяет ответный выбор игрока В в данной партии — он выбирает ту стратегию, которая соответствует подчеркнутому числу (если их несколько, берется любая). Таким образом определяется номер j оптимальной (в данной партии) стратегии В (ставится в следующем столбце). В последующих

Таблица 27.7

k	i	B₁	B₂	B₃	j	A₁	A₂	A₃
									4, 5 3, 67 2, 75 4, 00 4, 84 4, 43 5, 00 4, 45 4, 90 4, 64 5, 00 4, 61 4, 93 4, 74	5, 50 6, 60 5, 50 5, 14 5, 61 5, 11 5, 30 5, 09 5, 41 5, 07 5, 21 5, 06	4, 5 6, 75 4, 84 4, 13 5, 30 5, 17 4, 79 5, 30 4, 78 5, 10 4, 87 5, 20 4, 84 5, 07 4, 90

трех столбцах дается накопленный выигрыш за k партий соответственно при стратегиях А₁, А₂, А₃ игрока А (получается прибавлением элементов столбца В_j к тому, что было строкой выше). Из этих значений в таблице 27.7 «надчеркнуто» максимальное; оно определяет выбор стратегии игрока А в следующей партии (строкой ниже). В последних трех столбцах таблицы 27.7 даны:

— нижняя оценка цены игры, равная минимальному накопленному выигрышу, деленному на числа партий k;

— верхняя оценка цены игры, равная максимальному накопленному выигрышу, деленному на k;

v* — среднее арифметическое между ними (оно служит лучше, чем нижняя и верхняя, приближенной оценкой цены игры).

Как видно, величина v* незначительно колеблется около цены игры v = 5 (цена исходной игры была 0, но мы прибавили к элементам матрицы по 5). Подсчитаем по таблице 27.7 частоты стратегий игроков. Получим:

что не так уж сильно отличается от вероятностей p₁, p₂, p₃, q₁, q₂, q₃, равных, как мы указывали раньше, для первой, второй и третьей стратегий соответственно 1/4 = 0, 25, 1/2 = 0, 50, 1/4 = 0, 25. Такие сравнительно хорошие приближения мы получили уже при 15 итерациях — это обнадеживает! К сожалению, дальше процесс приближений будет идти не так резво. Сходимость метода Брауна — Робинсон, как показывает опыт, очень медленная, Существуют способы, позволяющие как бы «подхлестнуть» еле плетущийся процесс, но мы на них останавливаться не будем.

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

* * *

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

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

Прежде всего, на практике не так уж часто встречаются строго антагонистические конфликты — разве только в настоящих «играх» (шашки, шахматы, карты и т. п.). Вне этих искусственных ситуаций, где одна сторона стремится, во что бы то ни стало обратить выигрыш в максимум, а другая — в минимум, такие конфликты почти не встречаются. Казалось бы, где, как не в области боевых действий должна была бы с успехом применяться теория игр? Ведь здесь мы встречаемся с самыми «свирепыми» антагонизмами, с самой резкой противоположностью интересов! Но оказывается, что конфликтные ситуации в этой области сравнительно редко удается свести к парным играм с нулевой суммой. Схема строгого антагонизма применима, как правило, только к операциям малого масштаба, ограниченным по значению. Например, сторона А — группа самолетов, налетающих на объект, сторона В — средства противовоздушной обороны объекта; первая стремится максимизировать вероятность уничтожения объекта, вторая — ее минимизировать. Здесь схема парной игры с нулевой суммой может найти применение. Но возьмем чуть более сложный пример: две группировки боевых единиц (типа танков, самолетов, кораблей) ведут бой. Каждая сторона стремится поразить как можно больше боевых единиц противника. В этом примере антагонизм ситуации теряет свою чистоту: она уже не сводится к парной игре с нулевой суммой. Если цели участников конфликта не прямо противоположны, а просто не совпадают, математическая модель становится много сложнее: мы уже не можем интересоваться выигрышем только одной стороны; возникает так называемая «биматричная игра», где каждый из участников стремится максимизировать свой выигрыш, а не просто минимизировать выигрыш противника. Теория таких игр гораздо сложнее, чем теория антагонистических игр, а главное, из этой теории не удается получить четких рекомендаций по оптимальному образу действий сторон [26].

Второе критическое замечание будет касаться понятия «смешанных стратегий». Если речь идет о многократно повторяемой ситуации, в которой каждая сторона может легко (без дополнительных затрат) варьировать свое поведение от случая к случаю, оптимальные смешанные стратегии в самом деле могут повысить средний выигрыш. Но бывают ситуации, когда решение надо принять одно-единственное (например, выбрать план строительства системы оборонительных сооружений). Разумно ли будет «передоверить свой выбор случаю», — грубо говоря, бросить монету, и если выпал герб, выбрать первый вариант плана, а если решка — второй? Вряд ли найдется такой руководитель, который в сложной и ответственной ситуации решится делать выбор случайным образом, хотя бы это и вытекало из принципов теории игр!

Наконец, последнее соображение: в теории игр считается, что каждому игроку известны все возможные стратегии противника, неизвестно лишь то, какой именно из них он воспользуется в данной партии игры. В реальном конфликте это обычно не так: перечень возможных стратегий противника как раз неизвестен, и наилучшим решением в конфликтной ситуации нередко будет именно выйти за пределы известных противнику стратегий, «ошарашить» его чем-то совершенно новым, непредвиденным!

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

⇐ Предыдущая 12 13 14 15 16 17 18 192021 Следующая ⇒