ПРИКЛАДНАЯ МАТЕМАТИКА И МЕХАНИКА
Том 68. Вып. 4, 2004
УДК 62-50
© 2004 г. Л. В. Грауэр, Л. А. Петросян МНОГОШАГОВЫЕ ИГРЫ
Рассматриваются бесконечношаговая и конечношаговая игры на древовидном графе, каждой вершине которого соответствует некоторая одновременная игра. Дается определение сильного трансферабельного равновесия по Нэшу. Для бесконечношаговых игр вводится процедура регуляризации, которая позволяет построить сильное трансферабельное равновесие. Для конкретного случая повторяющейся бесконечношаговой игры "Дилемма заключенного" п лиц найдено сильное трансферабельное равновесие в явном виде. Для конечношаговых игр определен новый класс равновесий по Нэшу, основанный на использовании стратегий наказания. Получены явные аналитические формулы числа шагов, необходимых для наказания. Показано, что выигрыши в данном равновесии превосходят выигрыши в классическом абсолютном равновесии.
В литературе по теории многошаговых и повторяющихся игр известны теоремы [1-3], из которых следует возможность построения Парето оптимальных равновесий по Нэшу с использованием стратегий наказания; поскольку авторство этих теорем не определено, они получили название народных теорем. Однако в указанных работах народные теоремы доказаны для бесконечношаговых игр. Перенесение же результатов на случай конечношаговых игр сталкивалось с невозможностью реализации наказывающих стратегий на последних шагах игры. Был разработан новый подход [4], использующий как стратегии наказания, так и обычное равновесие по Нэшу, для повторяющихся биматричных игр. В данной работе полностью решена проблема построения соответствующих равновесий по Нэшу для конечношаговых игр п лиц.
В теории игр важен вопрос построения сильных равновесий, т.е. равновесий, устойчивых относительно отклонений коалиций игроков. Для классического статического случая оно не имеет особого смысла, так как такие равновесия, как правило, не существуют. Именно поэтому в классической теории игр рассматривались равновесия, устойчивые относительно отклонений отдельных игроков [5, 6]. Наиболее подробно этот вопрос освещен в [7]. В данной работе с использованием идеологии народных теорем удается при достаточно широких предположениях конструктивно построить сильное равновесие и получить условия его существования для бесконечношаговых игр. В качестве базового иллюстративного примера выбрана многошаговая игра, на каждом шаге которой играется игра "дилемма заключенного'' п лиц [8].
1. Бесконечношаговая игра. Рассмотрим бесконечный древовидный граф О = (Ъ, Ь), где Ъ - множество вершин и Ь : Ъ ^ 2Ъ, Ь(г) = Ь1 с Ъ, г 6 Ъ. Ь1 - множество вершин, следующих за г. Будем полагать, что множества Ь , г 6 Ъ, конечны. Каждой вершине г 6 Ъ соответствует одновременная игра п лиц
Г( г) = < N; Х\,..., ХП; К\, Ю
где N = {1, ..., п} - множество игроков, одинаковое для всех г 6 Ъ, Хг - множество стратегий игрока г 6 N (множества Хг, г 6 Ъ, конечны), Кг (х\, ..., хгп) - функция выигрыша игрока г (г 6 N, хг 6 Хг). Игра Г(г) называется одношаговой игрой.
Для каждой г 6 Ъ определена функция перехода Т( г; хгп) = Т (г; хг )б Ьг (Т (г; хг )Ф0& Ь1 ¿0)
Функция Т определяет для каждой вершины г и ситуации X в игре Г(г) вершину г' и соответственно игру Г(г') (г' = Т(г; хг) 6 Ьг), которые будут на следующем шаге.
На дереве О = (Ъ; Ь) с помощью одновременных игр Г(г) и функции перехода Т определим многошаговую игру О (г0) следующим образом. На первом шаге в начальной вершине г0 6 Ъ происходит одновременная игра Г(г0). Если в этой игре реализовалась
ситуация хг°, тогда на следующем шаге будет происходить игра Г^), где г! = Т(г0; хг°). Если на шаге к происходила одновременная игра Г(гк _ 1) и в Г(гк _ 1) реализовалась ситуация хг 1, то на следующем шаге будет происходить игра Г(гк) (гк = Т(гк - 1; хг 1)). Многошаговая игра О (г0) заканчивается, если на некотором шаге I имеем Ь= 0 (в
этом случае Т(г{; хг) = 0). Реализовавшуюся последовательность ситуаций хг°, хг1, ...
гк
..., х , ... назовем траекторией, а соответствующую последовательность вершин г0, г1, ...,гк, ... - путем в графе.
Чистая стратегия поведения л,(у), у 6 Ъ, игрока I 6 N в многошаговой игре О -функция, ставящая каждой вершине у 6 Ъ в соответствие чистую стратегию игрока I в одношаговой игре Г(у) : щ(у) = ху 6 Ху. Смешанная стратегия поведения q (у), у 6 Ъ,
игрока I 6 N в игре О определяется как отображение, ставящее в соответствие каждой вершине у 6 Ъ смешанную стратегию игрока I в одношаговой игре Г(у).
Определим функцию выигрыша в игре О (г0) как дисконтированную сумму выигрышей в одношаговых играх вдоль реализовавшегося пути. Она будет включать дисконтирующий множитель 5, 5 6 (0; 1), так как в игре О (г0) могут появиться бесконечные пути г0, г1, ..., гт, ... Таким образом, выигрыш равен
К; = £ Кгт(хгт)5т, 16 N (1.1)
т = 0
Для того чтобы гарантировать существование суммы (1.1), будем полагать, что все выигрыши в одношаговых играх равномерно ограничены (Кг (хг) < К, г 6 Ъ).
В игре О (г0) игроки обладают полной информацией в том смысле, что в каждой вершине г 6 Ъ они знают одновременную игру Г(г), в которую играют, и каждый игрок помнит все стратегии, выбранные в предыдущих вершинах всеми игроками.
Для каждой вершины у 6 Ъ рассмотрим подыгры О (у) игры О (г0), начинающиеся из у и играемые на подграфе О(у) = (Ъу, Ь). Здесь ^ - множество вершин подграфа О(у). Функция выигрыша игрока I в игре О (у) определена как тК\1 (х1 )51 - т.
-р. _г0 -г1 -гт - -
Рассмотрим траекторию х , х , ..., х , ... с соответствующим путем г0 = г0, г1, г2, . где гк = Т(гк _ 1; хЧ -1), на которой сумма выигрышей всех игроков максимальна, т.е.
£ £ К1т(хгт)5т _ тах £ £ К^т(хгт)5т _ У(г0; Ю (1.2)
; 6 Ют = 0 хг°.....х'т,...1 6 Ют = 0
Такую траекторию будем называть кооперативной (предполагается, что максимум достигается).
Для каждой подыгры О (г), г 6 Ъ, рассмотрим соответствующую игру О (г) = У(г, 8)) в форме характеристической функции. Характеристическая функция (ХФ) У(г; 8), 8 с N определена как значение антагонистической игры т 8 (г), построенной по структуре игры О (г), между коалицией 8, выступающей в роли максимизирующего игрока, и коалицией N \ 8, выступающей в роли минимизирующего игрока. Выигрыш игрока 1 (коалиции 8) определен как сумма выигрышей ее членов. Дополнительно предполагается, что эти значения У(г; 8) существуют для каждых г 6 Ъ и 8 с N. Обозначим через
(Цг8 (), ()) пару оптимальных стратегий поведения в игре ^ (г). Здесь
Й(•) = {чг(■); г 6 8}, ^■) = {■); г 6 мя} (1.3)
Таким образом, пара стратегий ((), ()) в игре ^ (г) образует некоторую
ситуацию в игре О (г) : Цг (■) = ((■), Цп (■)).
Рассмотрим последовательность подыгр О(гт) вдоль г0, г!, ..., гт, ... Для ХФ У( гт, N выполняется уравнение Беллмана, и
V(zm; N) = maxi £ (x1") + 5V(T(zm, x"); N)l
x*m L i e N j
V(Zm; N) = £ KZm(xZm) + 5V(Zm + i; N)
В каждой подыгре G (zm) рассмотрим С-ядро С(zm) и предположим, что С(zm) Ф 0. Для каждой подыгры G (zm) построим новую ХФ V (zm ; S) следующим образом:
t>(zm; S) = maxi £ kz"(xzm||) + 5 V(T(zm; xzm||xs); S) |, = {x, j e S} (1.4)
xs L i e S j
Тогда
Г V(zm; S)> V(zm; S), S с N У(zm; N) = V(zm; N), l Л (1.5)
Lv(zm; s:)> y(zm; s2), s2 с sx
ХФ V может не быть супераддитивной. В игре G (zm) = (N, V (zm; S)) построим С-ядро С (zm) с помощью новой ХФ.
Из соотношений (1.5) следует, что С (zm) с С(zm) (m = 0, 1, ...). 2. Регуляризация игры G(z0). Предположим, что С(zm) Ф 0 (m = 0, 1, ...). Пусть дележ а = (а1, ..., ап) e С (z0). Последовательность векторов ß = ß1, ..., ß;, ... (ß; =
= фи, ..., Рп1)) называется процедурой распределения дележа во времени (ПРД), если выполняются следующие условия:
а _ £ Р./5'. ат _ £ М1-т. ; 6 _ а ). «т _ (аТ>•••> «т) 6 С(гт) (2.1)
/ = 0 I_ т
ПРД в существует для каждого дележа а 6 С (г0), для произвольной последовательности дележей а = а0, а1, ..., ат, ... (ат 6 С (гт)) ее можно определить следующим образом: ргт = ат - 5ат +1, г 6 N (т = 0, 1, ...).
Рассмотрим многошаговую игру Ор (г0), которая отличается от игры 0(г0) лишь значениями функций выигрыша вдоль кооперативной траектории. Предположим, что в игре Ор (г0) в каждой одношаговой игре Г(гт) (т = 0, 1, ...) выигрыш в ситуа-
/ —гт —гт\ —гт
ции (х1 , ..., хп ) = х определен как
К(х\т, ..., хП) = р,-т, I 6 N, т = 0, 1, ... вместо Кг™ (хт) (выигрыш в игре Г(гт)). Для всех других ситуаций (х\т, ..., х™) вы-
ТЯ / гт гт \ Ту?-гт / гт гт \ тт~ / \
игрыш остается неизменным: Кг (х1 , ..., хп ) = К1 (х1 , ..., хп ). Как и выше, дг ( ), I 6 N, - стратегия поведения в игре Ор (г0), а - множество стратегий поведения.
Ситуация в стратегиях поведения #*(•) = (д* (■), ..., д* (■)) называется сильным трансферабелъным равновесием по Нэшу в игре Ор (г0), если
£ К;(д* (■ ))>£ К(д* (■ )\\д3( ■)), УБ с N, д3( ■ )6 П (2.2)
г е 5 г е 5 ] 6 б
Теорема 1. В игре О р (г0) существует сильное трансферабельное равновесие по Нэшу (2.2) в стратегиях поведения.
Доказательство. Рассмотрим следующую ситуацию д (■) = ((■), ..., (Цп (■)) в игре
О р (г0):
(■) = хгт для г = гт; (■) = дг?(г) при г 6 Ъг?; (2.3)
компонента дг () произвольна в других случаях где Г( гр) - первая одношаговая игра из последовательности игр Г( г0), ..., Г( гт), ..., в которых существует коалиция Б с N, такая, что г г Б, а игроки ] 6 Б отклоняются
от х р; д1' (г) - ¿-я компонента стратегии (') в игре ОБ, N\Б (гр).
Докажем, что ситуация д ( ) = (( ), ..., с[п ( )) является сильным трансферабельным равновесием по Нэшу. Из определения стратегий дг () (г = 1, 2, ..., п) (2.3) следует, что
Кб(д(■)) = £ К;(д(■)) = £ £ р^ = £ а; = £ а0
г 6 б г 6Бт = 0 г 6 б г 6 б
Теперь рассмотрим ситуации ([ Б с Д, и выигрыши в этих ситуациях. Ес-
ли [Б(-) совпадает с [& (■) вдоль 20, ..., 2т , • • •, тогда ясно, что
[( ■)) = [( ■ )|| ■))
Предположим, что стратегия [■(•) предписывает поведение в одной из одношаговых игр Г( 2т) (т = 0, 1, ...), отличное от поведения, предписываемого стратегией [Б( ).
Обозначим через 2р первую вершину пути 20, ..., 2т , ..., в которой [(2т) Ф х- ,- € Б.
В этом случае в ситуации ([ ()|
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.