1 Некоторые понятия теории игр
Описание структуры конкретной игры обычно содержит три блока: 1) допустимые множества ходов или стратегий участников; 2)цели; 3)тип поведения участников, зависящий от их информированности и др., описываемый "концепцией решения" игры.
По этим трем заданным параметрам ситуации желательно уметь определять множество возможных исходов, то есть "решение".допустимые множества
цели тип поведения
исход (решение) игры (1)
Для формального анализа игру обычно записывают в одной из форм: развернутой (детальное описание возможных ходов), характеристической (описываются значения выигрышей каждой коалиции, для анализа кооперативных игр) или стратегической (нормальной). Последний вариант, изучаемый далее, означает, что игра есть
G := {/, (Х^, (щ)!), где / := {l,...,m} — множество участников г, X := (Хі)І := ПіХі — допустимое множество стратегий участников,
и := (ui)i = (ui)i?i — набор целевых функций участников (каждая целевая функция Ui\ Хі І—» ]R зависит, вообще говоря, от всех (xj)jсмешанную стратегию улучшить матожидание своего выигрыша, при неизменных стратегиях партнеров; то есть
ДІ Є argmax ^ щ(х)(ілі(хі) • М^) •... • Дп(ж„)).
Для случая когда (осторожные) игроки не обладают информацией о целях партнеров и о том, какие стратегии выбирают другие, подходит следующая концепция.
Определение 1.0.6 Множество осторожных или максиминных решений есть
ММ := {х Є Х\ иг(хг,х.г) = sup ( inf иг(уг^.г) ) (г Є /)}.4 (2)
Уі&Хі z—іЄХ—і
Поясним: в осторожном решении (равновесием его называть не совсем точно) игроки ожидают от партнеров самого худшего для себя. Это кажется правдоподобным поведением при неизвестности целей партнеров и однократном розыгрыше; а также и в ситуации антагонистической игры.
Определение 1.0.7 Множество седловых точек есть Sad := ММЕ П NE.
Это те Нэшевские (осторожные) равновесия, где худшие предположения сбываются.Определение 1.0.8 Антагонистической называют игру с нулевой (или, что то же, постоянной) суммой выигрышей, т.е. такую, что ЕІЄ/ИІ(Ж) = ®^х є Х. Для антагонистической игры двух лиц цена игры /л0 есть полезность первого игрока в седловой точке Sad, то есть
P.Q := Slip inf Ui(xi,X2) = inf SUp
3Обычно имеют в виду повторяющуюся игру.
Есть виды равновесий в которых подразумевается, что игроки более дальновидны и информированы. В том числе в "сложном равновесии" считается, что они знают цели друг друга, последовательно отбрасывают доминируемые стратегии и ожидают того же от других.
Определение 1.0.9 Определим последовательность игр С1,С2,...,С*,..., задавая каждый раз множество всех стратегий новой игры как прошлое множество недоминируемых стратегий: Xt+l := Vі (t = 1,2,...) (предполагается что все игроки отбрасывают доминируемые стратегии одновременно). Множество слабых сложных равновесий игры GI есть стационарное множество этой последовательности: WSE •= Vі = Vl~l (Bt > 1). Сложное равновесие 5 х є SE есть такое х є WSE, где каждый игрок имеет только эквивалентные стратегии в финальной игре Gf.
В равновесии по Штакельбергу (Stackelberg) первый игрок (лидер) ориентируется на индивидуально оптимальные ответы партнеров зная их предпочтения, а остальные (ведомые) играют, как в NE, близоруко.
Определение 1.0.10 Считая 1го игрока лидером, обозначим множество Нэшевскирациональных откликов его партнеров на его стратегию х\ через
NRI(XI) := {жІ Є ХІ\ Ui(x) = maxXieXiUi(xi,xi), (і ^ I)}, тогда: Осторожное (пессимистическое) равновесие по Штакельбергу с лидером N 1 есть такой набор х є StEPi, что
XTL Є argmaxxiex1mmxie7V^1(xl)Ui(xi,xi),
si Є argmiQIiejVJZ1(Sl)Ui(3ei,xi).
(Оптимистическое) равновесие по Штакельбергу х є StEOi есть XTL Є argmaxxiex1maxxie7v^1(xl)Ui(xi,xi), si Є
Равновесие Штакельберга может возникать, например, когда один из игроков (лидер) делает свой выбор раньше других ("ведомых") и знает их цели.
Концепция StEO\ предполагает доброжелательность партнеров к лидеру при выборе из эквивалентных для себя вариантов (из NR), a StEPi — недоброжелательность; если же выбор "ведомых" однозначен, то разницы между StEO и StEP нет.В последующем мы используем также понятия некоторых кооперативных решений.
Определение 1.0.11 Назовем (сильным) множеством Парето /Паретооптимумом, или "сильной Паретограницей") множество неулучшаемых по Парето точек (исходов), то есть6
Т := {х fix Є X : и(х) > и(х)},
(иначе: это множество исходов неблокируемых большой коалицией I при сильном блокировании); слабая Паретограница есть
WP := {х\ ДхЄХ : и(х) » и(ж)}.
Рассматривают также сложные равновесия с неодновременным отбрасыванием худших стратегий, а с заданной последовательностью ходов (Мулен, стр.40). Они подобны вводимым ниже равновесиям Штакельберга StE (наши определения StEOi, StEPi не традиционны).
6Для пар векторов > далее означает >^, а > — покомпонентно больше.
6
То есть Паретооптимум — это такое состояние, в котором никто из участников не может увеличить свою целевую функцию без уменьшения целевой функции по крайней мере одного другого участника.
Определение 1.0.12 Ядром С (обычным, слабым ядром) называется множество состояний неблокируемых никакой коалицией Тс/, при обычном (слабом) определении блокирования: Т блокирует вариант х є X если существует альтернатива Хі Є Хі (і є Т) такая, что все участники из Т выигрывают по сравнению с х, т.е. UT(XT,XT} ^ UT(X] — при любых действиях XT не входящих в коалицию Т игроков.7
Перейдем к утверждениям. Из данных определений непосредственно следует
Утверждение 1.0.1 Ядро принадлежит слабой Паретогранице, а сильное ядро — сильной (обычной) Паретогранице:
Cs с Р, С с WP.
Некооперативные решения игр чаще всего оказываются не оптимальными по Парето, как станет ясно из примеров.
Без доказательства (см. Мулен) отметим условия существования и вложений определенных выше множеств.
Теорема 1 (Нэш, 1951) Пусть для всех (і є /) все Хі компактны и выпуклы, все Ui(.) непрерывны и вогнуты по xir тогда множество NE •=? 0, компактно.
Следствие 1.1 Если все Хі конечны, то множество NEm •=? 0, компактно.
Доказательство теоремы опирается на теорему о неподвижной точке применяемую к отображению отклика Т определяемому ниже в (3).
Связь матричных игр с линейным программированием и нахождение NEm.
Доказательство Сл. 1.1 для антагонистических (матричных) игр двух лиц можно проводить и независимо от теоремы Нэша, через линейное программирование, что дает также способ поиска NEm для этих игр. Для этого задачу 1го игрока записывают в форме максимизации (неизвестной ему заранее) цены игры /л0 по переменным //о,//, при ограничениях ц > О, Е^ІІА^ = 1, nak > JJ.Q (k = 1,...,п2), где ak Є Rni — столбцы матрицы платежей (akj] := (ui(x{,x1^}}. Здесь ограничения типа > выражают гипотезу 1го о неблагоприятном поведении противника (максимин). Легко проверить, что задача противника есть двойственная к описанной задаче. Таким образом симплекс методом можно найти седловую пару в игре Gm, она является и Нэшевской парой. Для случая биматричной игры 2x2 также легко найти NEm графически, строя функции (или отображения) NRi(xi) отклика игроков на действия партнеров.Утверждение 1.0.2 8 1) Если все Хі конечны, то WSE ^ 0. 2) В антагонистической игре двух лиц где все Хі конечны SE с Sad, и если SE ^ 0, то у игры есть цена.
7Силыным ядром Cs называется множество состояний, неблокируемых никакой коалицией при сильном блокировании (что означает UT(XT,XT) > UT(X) вместо UT(XT,XT) ^ UT(X) в определении блокирования).
8Более важная теорема Куна на эту тему касается игр в развернутой форме: из нее, в частности, следует, что в шахматах есть SE (оно пока неизвестно).
Утверждение 1.0.3 Пусть все Xi компактны a Ui непрерывны, тогда 1) Т>Г\ММЕ ^ Ф,Р ^ 0; 2) множества JDE,MME,NE компактны, NE с NEm; 3) если ЮЕ ф 0, то
ММЕ D ЮЕ = V = Sad = SE С NE,
Доказательство утверждения (3) элементарно: поскольку доминирующие стратегии заведомо лучше остальных стратегий, то соответствуют и другим некооперативным решениям