Многошаговые (позиционные) игры с полной информацией

Математические модели конфликтов с учетом динамики исследуются в теории позиционных игр. Наиболее простым классом позиционных игр является класс конечношаговых игр с полной информацией.

При решении таких игр используется теория графов.

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

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

Формально игрок имеет полную память, если для двух его любых информационных множеств U и V можно из одного, расположенного «ниже» на дереве игры (скажем V), попасть в множество U по единственной альтернативе.

Значение игр с полной памятью определяется тем, что каждый игрок может обойтись так называемыми стратегиями поведения, задание и реализация которых значительно проще, чем смешанных стратегий. Определение стратегии поведения дано в начале этой главы. Различие между смешанной стратегией и стратегией поведения пояснена Г.У. Куном [13] следующим образом: можно представить себе каждую чистую стратегию как книжку инструкций, в которой каждая страница относится лишь к одному информационному множеству и точно устанавливает, что нужно делать игроку в этом информационном множестве. Множество чистых стратегий соответствует библиотеке таких книг. Смешанная стратегия выбирает одну книгу посредством случайного механизма с распределением вероятностей, совпадающим с распределением вероятностей смешанной стратегии. Стратегия поведения представляет одну книгу, но особого рода: каждая страница этой книги, соответствующая тому или иному информационному множеству, задает распределение вероятностей на множестве альтернатив данного множества.

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

Стратегии поведения f* и g* первого и второго игроков являются оптимальными, если выполняется двойное неравенство

, (3.4)

где f, g – любые стратегии соответственно первого и второго игроков, а – функция выигрыша первого игрока.

Оказывается, в конечных позиционных играх с полной памятью игроки имеют оптимальные стратегии поведения. Для нахождения оптимальных стратегий поведения игры с полной памятью достаточно решить некоторую матричную игру с ограничениями, которая сводится к задаче линейного программирования [13] .

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

Наиболее простыми играми с полной памятью, не считая игр с полной информацией, являются так называемые одновременные многошаговые игры. Содержательно одновременно многошаговая игра представляет собой антагонистическую многошаговую игру, в которой на каждом шаге игроки 1 и 2 выбирают свои действия одновременно, т. е. не имея информации о выборе противником позиции в этот момент. После того как выбор сделан, они становятся известными обоим игрокам, и игроки вновь совершают одновременный выбор и т. д. Условно такую игру можно изобразить с помощью графа.

Игра с выжиданием

Рассмотрим теперь положение дел, как бы объединяющее черты игры с полной информацией и игры без информации.

Представим себе, что в момент принятия решения о выпуске того или иного вида продукции «Сокол» может наряду с двумя имеющимися в его распоряжении возможностями – выпускать СПО первого или второго вида – осуществить еще третью возможность: выждать, пока не станут ясными производственные планы предприятия «Чайка», и уже после этого принимать окончательное решение. Очевидно, что подобное выжидание обойдется предприятию недешево. Опоздание при выходе на рынок и, как следствие, уменьшение объема сбыта продукции. Допустим, что до выхода на рынок опоздавшего предприятия «Сокол» «Чайка» успеет внедрить 200 систем. Поведение же предприятия «Чайка» пусть остается таким же, как и в предыдущих примерах: принимать решение о выпуске БПО₁ или БПО₂ в начальный момент времени, не имея какой-либо информации о намерениях предприятия «Сокол».

Такую игру удобно описать в виде «древовидного графа» (см. рис. 3.1). Вершины этого графа (позиции) соответствуют тем «физическим» состояниям, в которых могут находиться игроки. Идущие от позиций вверх дуги графа (альтернативы) соответствуют решениям, которые выбирают игроки в позициях. Позиции, не имеющие альтернатив, (окончательные) соответствуют исходам игры. В окончательных позициях игроки получают выигрыши.

Игрок, принимающий решение, не в состоянии точно указать, в какой именно позиции он находится, т. е. каково его истинное физическое состояние. Множество позиций, составляющих одно информационное состояние игрока – это его информационное множество.

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

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

Рис. 3.1

В нашем примере «Сокол» имеет три информационных множества, состоящих из одной позиции каждая. Это значит, что «Сокол» действует все время в условиях полной информации об обстановке. В позиции 0 знает, что вообще еще ничего не произошло, а в позициях 4 и 5 знает, во-первых, об ожидании в течение некоторого времени, и, во-вторых, о том, какую продукцию выпускает «Чайка».

Напротив, «Чайка» имеет одно информационное множество, состоящее из трех позиций (1, 2 и 3-я). Это значит, что «Чайка» действует в условиях отсутствия информации, не зная в момент принятия решения, выжидает «Сокол» или нет, и если нет, то на какой продукции предприятие остановилось. Стратегией игрока является принятие в каждом информационном состоянии некоторого решения или, употребляя только что введенную терминологию, выбор в каждом информационном множестве некоторой альтернативы (очевидно, из всех позиций, принадлежащих одному информационному множеству, должны выходить одни и те же альтернативы). В этом смысле стратегию игрока следует понимать как функцию, заданную на семействе всех его информационных множеств, значением которой на каждом информационном множестве является некоторая альтернатива, принадлежащая этому информационному множеству.

Рассмотрим теперь информационные множества предприятия «Чайка». У предприятия «Чайка» одно информационное множество с двумя альтернативами, поэтому данное предприятие имеет лишь две стратегии: БПО₁ и БПО₂.

Предприятие «Сокол», напротив, имеет три информационных множества, и их альтернативы могут сочетаться друг с другом произвольным образом. Следовательно, «Сокол» имеет стратегий. Некоторые из них, впрочем, не представляют интереса. Так, стратегия, состоящая в выборе в позиции 0 альтернативы СПО₁, а в позиции 4 альтернативы СПО₂, все равно полностью реализоваться не может, ибо после выбора предприятием «Сокол» в позиции 0 альтернативы СПО₁ игра вообще не может попасть в позицию 4 (равно как и в позицию 5). В связи с этим «реально возможных» стратегий у предприятия «Сокол», как это легко подсчитать, может быть лишь 6, и всего в игре может реализоваться различных ситуаций.

Каждая ситуация ведет к некоторой окончательной позиции. Так, принятие предприятием «Сокол» стратегии, состоящей в выборе им в позиции 0 альтернативы выжидания, а в каждой из позиций 4 и 5 альтернативы СПО₁, при принятии предприятием «Чайка» стратегии БПО₁ приводит к окончательной позиции 6. Полное описание соответствия окончательных позиций Ситуациям игры можно свести в табл. 3.1.

Таблица 3.1

Подсчитаем выигрыши (игрока 1, т. е. предприятия «Чайка»), соответствующие окончательным позициям игры. Например, в позициях 6–9 «Чайка» сбывает, во-первых, 20 % своей продукции, а затем оставшиеся 80 % спроса покрываются совместно с предприятием «Сокол» согласно данным табл. 1.2. Таким образом, общий сбыт игрока 1 в позиции 6 будет составлять 20 % плюс 40 % от оставшихся 80 %, т. е. всего 52 %. Аналогичный подсчет выигрышей игрока 1 для остальных окончательных позиций сведен в табл.

Таблица 3.2

№ окончательной позиции
Выигрыш «Чайки», в %

 

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

Игра с матрицей выигрышей является той игрой в нормальной форме, которая соответствует исходной позиционной игре.

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

Ввиду различия в матрице выигрышей максимина и минимакса (как легко подсчитать, первый из них равен 40, а второй – 52) можно предположить, что игрокам, в частности предприятию «Чайка», при этом придется пользоваться смешанными стратегиями. Предположим, что «Чайка» выбирает смешанную стратегию, в которой вероятность выбора первой чистой стратегии (т. е. БПО₁) равна р (такое предположение завести нас в тупик никак не может, ибо если в действительности искомая стратегия окажется чистой, то это просто будет означать, что или ). Если игрок 2 выберет свою первую чистую стратегию, то ожидаемый выигрыш игрока 1 будет равен , или . Результаты аналогичных подсчетов для каждой из чистых стратегий игрока 2 сведены в табл. 3.3.

Таблица 3.3

Чистая стратегия игрока 2		2 А			5 Б
Ожидаемый выигрыш игрока 1

 

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

Используя график (рис. 3.2) можно рассчитать, что при р от 0 до 16/54 минимальным из всех ожидаемых выигрышей будет соответствующий последнему (шестому) столбцу матрицы, при р от 16/54 до 34/46 ‑ второму столбцу и, наконец, при р от 34/46 до 1 – пятому.

 

Максимальный из этих минимумов будет достигаться при р = 34/46 и будет равен 48. Сравнение с игрой из предыдущего раздела показывает, что использование предприятием «Сокол» выжидающей тактики позволит увеличить его ожидаемый выигрыш на 7 единиц (напомним, что этими единицами являются в нашем случае проценты реализованной продукции). При этом предприятие «Чайка» должно будет выбирать выпуск БПО₁ не с половинной, а с существенно большей вероятностью, а именно с вероятностью 34/46 (примерно равно 0,7).

 

Рис. 3.2

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

Вычислим вероятности, с которыми игрок 2 смешивает свои стратегии А и Б. Обозначим через р вероятность, с которой игрок 2 выбирает стратегию А (тогда будет вероятностью, с которой он выбирает стратегию Б). «Ожидание ожидаемого выигрыша» игрока 1 при этом будет равно

,

т. е. .

Минимакс этого последнего выражения равен 52 % и достигается при q = 3/46. Таким образом, предприятие «Сокол» должно выжидать с вероятностью, приблизительно равной 2/3, после чего действовать сообразно обстоятельствам. Подчеркнем, что найденная вероятность получилась в результате учета 20 %-ных потерь сбыта от задержки выпуска продукции. Очевидно, что если бы эти потери по сделанному нами в условиях задачи предположению оказались бы большими, то оптимальная вероятность задержки оказалась бы меньшей, и наоборот.