Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/ium/postscript/s04/games7.ps Дата изменения: Thu May 6 17:09:39 2004 Дата индексирования: Sat Dec 22 12:50:12 2007 Кодировка: koi8-r Поисковые слова: http astrokuban.info astrokuban

Игры в развёрнутой форме: определения и аксиома Куна
Теперь мы переходим к анализу класса игр, в которых информация вскрывается
по ходу игры совершенно произвольным образом. Формализация этого класса игр
является делом непростым, но зато практические все жизненные ситуации, которые
требуют строгого анализа и прогноза действий участников, могут быть успешно фор-
мализованы и изучены в рамках этого подхода. Игры в нормальной форме, а также
детские игры | все они могут быть представлены в виде игры в развёрнутой форме.
В этом проявляется определённая универсальность предлагаемого подхода в теории не-
кооперативных игр.
Начинается задание игры в развёрнутой форме, конечно, с указания множества N
игроков. Условимся, во избежание ненужных осложнений, считать множество N конеч-
ным.
Далее, задаётся так называемое дерево игры | это конечное дерево с отмечен-
ной вершиной (следовательно, можно считать его ориентированным). Обозначим за
A множество вершин дерева (оно конечное), за a 0 2 A | отмеченную вершину, и за
M  AA | множество его рёбер. Ориентировку множества рёбер введём очевидным
образом: если a 1 и a 2 соединены ребром, то (a 1 ; a 2 ) 2 M $ (единственный) путь из
вершины a 0 в вершину a 2 пролегает через вершину a 1 , а не наоборот.
Введём порядок на множестве A вершин дерева, считая, что a выше b, если (един-
ственный) путь из вершины a 0 в вершину b проходит через вершину a. (В частности,
для любого ребра (a 1 ; a 2 ) 2 M имеем, что a 1 выше a 2 .)
Множество самых низких вершин дерева (относительно введённого порядка) назы-
вается множеством терминальных вершин, и обозначается за T . Все остальные вер-
шины разбиваются на непересекающиеся классы:
A n T = A 0 t ft i2N A i g; (1)
и интерпретируется это так: i-й игрок делает ход в вершинах a 2 A i (или Ђконтроли-
руетЃэти вершины). В вершинах множества A 0 ЂходитЃ природа; чуть позже это станет
ясно. Вовсе не обязательно, что отмеченная вершина контролируется природой, хотя
на практике такое бывает достаточно часто ( в 50 процентах случаев).
Что значит Ђделает ходЃ? Это означает, что игрок i, оказавшись в вершине a 2 A i ,
выбирает одну из стрелочек (т.е. направленных рёбер), исходящих из этой вершины:
(a; b) 2 M , и передаёт ход игроку, который контролирует вершину b. Природа тоже
ЂвыбираетЃ одну из стрелочек, исходящих из вершины a 2 A 0 , однако в случае хода
природы изначально заданы вероятности различных ходов (т.е. вероятностное рас-
пределение на множестве стрелок, исходящих из такой вершины). Множество стрелок,
исходящих из данной верщины a 2 A, обозначается за M a = f(a; b)g 2 M . Фактически,
это образ многозначного отображения M в точке a.
Что касается множества T терминальных вершин, то для каждой из них указаны
выигрыши игроков, то есть, в задание игры в развёрнутой форме входит отображение
u : T ! R N : (2)
Если бы на этом дело кончалось, то теория игр в развёрнутой форме была бы вся
целиком лёгким упражнением, а многие жизненно важные сценарии оказались бы за
1

бортом. Потому что в том виде, как игра до сих пор сформулирована, нет места
неопределённости, скрытой информации, которая в сущности и наполняет смыслом весь
теоретико-игровой анализ решений. Поэтому придётся продолжить (уточнить) наше
описание игры.
А именно, учёт неопределённости состоит в том, что некоторые вершины дерева
неразличимы с точки зрения контролирующего их игрока. Таким образом, сразу же
введём для каждого из игроков разбиение A i = A i1 t : : : A il i
множества контролируемых
им вершин на непересекающиеся ниформационные множества, внутри каждого из ко-
торых игрок i не может установить, где же конкретно он в данный момент находится и
принимает решение. Разумеется, это разбиение должно удовлетворять некоторым до-
полнительным требованиям, чтобы исключить ситуацию, когда игрок | идиот (если
из разных вершин одного и того же инфо-множества исходит неодинаковое число стре-
лочек), или когда он пьян (игра в Ђпьяного шофёраЃ) либо страдает дефектом памяти,
забывая, ходил ли он вообще, или как именно он ходил, или просто информацию по ходу
игры, которую он когда-либо узнал.
Чтобы формализовать высказанные требования, будем следовать подходу великого
математика Куна (который в паре с Такером устанавливал разные свойства экстре-
мальных задач). А именно, введём следующие два условия, которые завершат наше
описание игры в развёрнутой форме:
Условие 1: для каждого инфо-множества A ij задано множество ходов в нём, M ij ,
вместе с фиксированными биекциями M ij , M a для любого a 2 A ij ; иными словами,
с точки зрения игрока i, ситуация во всех вершинах информационного множества вы-
глядит идентичной.
Условие 2 (собственно, аксиома Куна): для любого инфо-множества A ij любого
игрока i, и для любых двух точек a; b 2 A ij , и любой вершины x того же игрока i, пред-
шествующей вершине a, должна существовать вершина y игрока i, находящаяся вместе
с x в одном и том же инфо-множестве (возможно, просто-напросто с x-ом совпадаю-
щая), которая посредством того же самого хода предшествует вершине b. Запутано,
но зато универсально: ниже будет продемонстрировано, что это условие адекватно
формализует игры с Ђсовершенной памятьюЃ.
Чтобы пояснить это, подумаем, что надо называть стратегией игрока. Явно, стра-
тегическим множеством надо назвать S i = [ l j
j=1 M ij . То есть, стратегия представляет
собой Ђплан действийЃ, на все возможные случаи жизни. Но тогда вопрос: что же такое
смешанная стратегия? Видимо, элемент симплекса ф(S i ), как обычно. Но это множество
великовато! Посмотрите хотя бы на его размерность. Да и маловероятно это, чтобы
вероятностью снабжался каждый конкретный план действий. (Интерпретация Дани-
лова с библиотеками.) Скорее, смешанной стратегией следовало бы считать результат
смеси ходов в каждом из инфо-множеств, т.е. множество смешанных стратегий должно
быть [ l j
j=1 ф(M ij ), имеющая куда меньшую размерность, нежели ф(S I ) = ф([ l j
j=1 M ij ).
Чтобы внести ясность,заметим, что любой из двух разных видов смешения, даже
если виды смешения у разных игроков различны, приведёт к однозначному исходу игры,
после фиксации того или иного типа смешанных стратегий у игроков. Назовём же две
стратегии (независимо от их типа) эквивалентными, если при любых выборах стра-
2

тегий остальными игроками платежи всем игрокам без исключения будут одинаковы.
Назовём теперь поведенческой стратегией смешанную стратегию в более экономном
смысле слова. Тогда:
Теорема Куна. Если аксиома Куна выполнена, то для любой смешанной стратегии
любого игрока существует поведенческая стратегия, эквивалентная ей.
Можно и непосредственно установить соответствие, реализующее эту эквивалент-
ность (упражнение). Впоследствии мы будем работать только с поведенчемкими стра-
тегиями.
3