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

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

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

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

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

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

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

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

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

, (3.4)

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

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

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

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