ВЫЧИСЛЕНИЕ РАВНОВЕСИЙ ПО НЭШУ В СМЕШАННЫХ СТРАТЕГИЯХ
На самом деле мы обнаружили нечто большее: если игрок / использует стратегию ц+, то игроку і безразлично, какую выбрать стратегию. Следовательно, равновесная стратегия игрока і создает как раз такой уровень неопределенности, что все ходы игрока / неразличимы для него по выигрышу.
Это свойство рассмотренной игры не является редким. В разд. 2 мы покажем, что это необходимое свойство всех вполне смешанных NE-исходов, т. е. таких исходов, в которых вероятность того, что данный игрок выберет любую данную стратегию, не равна нулю.
Вполне смешанные равновесия не только легко интерпретируются, но и легко вычисляются (см. лемму 3, разд. 2).
Заметим пока, что в отличие от двух WjE-исходов в чистых стратегиях (вполне) смешанный МЕ-исход доминируем по Парето (соответствующий ему вектор выигрышей ^ 1 *
12^ё) вектором выигрышей (1, 1)). Однако
ситуация (р*, р*) симметрична (р* = р*) и равноправна (и* = ?), поэтому она может быть рекомендована с нормативной точки зрения.
На самом деле в симметричных играх всегда существует симметричное равновесие по Нэшу в смешанных стратегиях.
Упражнение 2.
Пусть (Х{, щ\ i?N)симметричная игра:
Xt = X/ для всех (, j € N,
Ui (х{, xN\{L,}, xj) = uf{Xj, xNK[U /}, xt) для всех i, j?N, x?XN.
Докажите, что смешанное расширение имеет по крайней мере один симметричный МЕ-исход у:
Иі ру для всех / ? N.
Указание. Следуйте доказательству теоремы 2 гл. II, положив
Ф(р, ?) = ы1(рІ, ?/)Mj(v) для всех р, \?MN.
Упражнение 3, в котором равновесная по Нэшу стратегия не является осторожной
Мы уже знаем (примеры 2 и 3 гл. Ill), что /??-стратегия может не быть осторожной.
Здесь мы покажем, что то же самое может случиться и в играх со смешанными стратегиями. Рассмотрим игру G 2x2:
Докажите, что в смешанном расширении игры G каждый игрок имеет единственную осторожную стратегию ррг и существует единственный М?-исход (р^, рг).
Проверьте следующие соотношения:
"і Р?) р) = (Р?, р?) = і (Рі. РЙ-
Дайте интерпретацию.
Упражнение 4. Пример блефа
Имеются две картыстаршая и младшая. Игрок 1 с равной вероятностью вытаскивает одну из них, причем делает это в тайне от игрока 2. Затем он решает: либо дать доллар второму игроку, либо играть дальше.
В последнем случае игрок 2 принимает решение: либо спасовать, и тогда он дает доллар игроку 1, либо играть дальше. В последнем случае карта игрока 1 открывается и игрок 2 платит 4 доллара игроку 1, если это оказалась старшая карта, в противном случае игрок 1 платит 5 долларов игроку 2.
Смоделируйте эту игру двух лиц с нулевой суммой в нормальной форме и вычислите оптимальные смешанные стратегии обоих игроков и цену игры в смешанных стратегиях.
Упражнение 5. Игра двух лиц с нулевой суммой и линейное программирование
Для игры G = (Xt, Х2, их) докажите, что решение задачи линейного программированияшаха
щ€Л1і. а их (р1( для всех *2€Х2 (6)
относительно переменных (а, рх) дает цену игры в смешанных стратегиях и оптимальную смешанную стратегию игрока 1. Что можно сказать о задаче, двойственной к (6)?
Задача I. Смешанные стратегии в игре двух лиц с нулевой суммой выгодны обоим игрокам
Пусть (Хь Х2, і)игра двух лиц с нулевой суммой без цены:
sup inf ut ах a2 == inf sup uv
Xi Xt Xg X,
1) Предположим, что для любой фиксированной чистой стратегии xt С Xt отображение xf + их взаимно однозначно на Ху ({і, /} = {1, 2}). Докажите, что цена vm(ut) принадлежит открытому интервалу \dt, a2).
2) Приведите пример (с нарушением предположения о взаимной однозначности), в котором
sup inf щ = ?т (Иі) inf sup uv
*1 *i * X,
Задача 2.
1) В предположении, что игра двух лиц G (Xt, Х2, щ) имеет цену, докажите, что любая выпуклая комбинация оптимальных стратегий в игре G является оптимальной стратегией в игре Gm. Приведите пример, показывающий, что обратное утверждение не верно.
2) Пусть теперь G = (X,., щ\ i?N)игра в нормальной фор
ме. ГІокажите на примере, что недоминируемая чистая стратегия хг игрока і в игре G {xt ? (,- )) может быть доминируе
мой в игре Gm.
3) Докажите, что если xtдоминируемая стратегия игрока ? в игре G (Х{ ? S{ (/)), то в игре Gm найдется по крайней мере один NE-исход ц, в котором игрок і не использует стратегию xt:
4) Докажите, что если игрок і имеет доминирующую стратегию р,- в игре Grn (р(- ? Di (М;)), тогда все чистые стратегии xh такие, что р,- (лг() 0, эквивалентны и на самом деле являются доминирующими в игре G (x,?Df (и,)).
Задача 3. Взаимозаменяемость смешанных NE-исходов в играх двух лиц (Партхасаратхи, Рагхаван [1971])
В смешанном расширении йт (Мх, М2, ии и2) игры двух лиц AfjE-исходы, вообще говоря, не являются взаимозаменяемыми:
из р, p'€N?(GjHe следует (pf, р^,), (р[, р2) € W?(GJ.
Такая ситуация имеет место, например, в смешанном расширении игры перекресток (см. пример 2 выше).
1) Докажите, что N Дисходы игры Gm взаимозаменяемы тогда и только тогда, когда множество NE(Gm) является выпуклым подмножеством RXixR*2 (множества Х{ предполагаются конечными).
2) В предположении, что NE(Gm) выпуклое (и, следовательно, в силу 1) прямоугольное) подмножество множества MjXA12, докажите существование по крайней мере одного смешанного NE-исхода р*, который либо доминирует по Парето любой другой смешанный (VjE-исход, либо имеет такой же вектор выигрышей:
Vp $NE(Gm) иДрХиДр*) (=1,2.
2. ВЫЧИСЛЕНИЕ РАВНОВЕСИЙ ПО НЭШУ В СМЕШАННЫХ СТРАТЕГИЯХ
Определение 2. Пусть Xt конечное множество стратегий игрока (, ( € N. Для произвольной смешанной стратегии pf € М{ обозначим через [р,-] носитель р,, т. е. множество чистых стратегий игрока (, которые входят в р, с положительной вероятностью:(хг) 0}.
Скажем, что смешанная стратегия р; является вполне смешанной, если ее носитель есть все множество (чистых) стратегий, т. е. Ы = Xf. Назовем исход р в игре Gm вполне смешанным, если р{вполне смешанная стратегия при всех i?N.
Теорема 2. Предположим, что исходная игра G = (Xit up, i?N) имеет конечные множества стратегий. Пусть р g ? NE (Gm)равновесие по Нэшу в смешанных стратегиях. Тогда справедлива следующая система равенств:
(7)
?і ? N, ?х; € [р,] щ (ЬХ{, р,) = щ (р).
Доказательство. Фиксируем i?N. Тогда по определению ситуации равновесия по Нэшу имеем
и,-(6*., р,-)м;(р) для всех *,€'[р/]. (8)
Предположим, что хотя бы одно из этих неравенств строгое; иі (б*? I*/) иі О4)-
Умножая все неравенства из (8) на р; (xt) и учитывая, что Р/ (х[) 0, получаем
Щ(р) = иі( 2 рЛ= 2 рЛ
і 2 Р,- (xt) I щ (p) = и, (p).
6 ["Л /
Полученное противоречие доказывает, что все неравенства в (8) на самом деле обращаются в равенства. Щ
Согласно теореме 2, равновесие по Нэшу в смешанных стратегиях р обладает следующим свойством: любая смешанная стратегия pj с тем же носителем, что и р,-, является наилучшим ответом игрока і на р;. В частности, если р есть вполне смешанное равновесие, то любая стратегия игрока і является наилучшим ответом на набор рг равновесных стратегий остальных игроков.
Следовательно, в игре двух лиц в состоянии вполне смешанного равновесия игрок і выбирает стратегию, которая уравнивает выигрыши игрока /' при всех его (смешанных) стратегиях. Эта стратегия не зависит от функции выигрыша игрока і. Этот факт проиллюстрирован на разобранном выше примере 2 и в лемме 3 (она будет приведена ниже).
В то же время в игре с тремя по крайней мере игроками стратегии вполне смешанного равновесия должны определяться совместно, причем Иі зависит от платежной функции щ в силу системы (7).
Теорема 2 является основным инструментом, позволяющим вычислять исходы равновесий по Нэшу в смешанных стратегиях. В самом деле, предположим, что мы ищем исход ?NE(Gm), считая носители всех стратегий р,- заданными, т. е,
(9)
Тогда система (7) переписывается в следующем виде;
?( € N ?л:,., у{ ? Y{ ut (6*., pf) = u( (Ьу., p?). (10)
Система (10) дает 2(І^гІ 1) независимых одномерных урав-
І6 N
нений. В силу (9) каждая стратегия pf состоит из ( Yt 1) независимых переменных ^принимая во внимание условие
2 р,- (*,- ) = 1Y Эти простые рассуждения могут быть сущеет-х‘ 6Y‘ /
венно развиты. Они приводят к следующему утверждению.
Фиксируем Хг, i g N; тогда существует открытое всюду плотное подмножество Q из (КЛгл,)Л/ такое, что для всех наборов (и,.); е Л/ из Q и всех прямоугольных подмножеств YN = = X у, из XN система (9), (10) относительно неизвестных pf М;,
f е Л/
і € М, имеет не более одного решения.
Поскольку XN имеет конечное число прямоугольных подмножеств, то отсюда следует, что если (ы,-)гел/ принадлежит Q, то соответствующая игра Gm имеет конечное число ME-исходов: NE(Gm) в общем положении конечно (при (Де д/ из Q), Когда множества стратегий Х{, і ? N, содержат (очень) малое число элементов, то следующий алгоритм позволяет полностью определить NE (Gm). Фиксируем прямоугольное подмножество Yл/ из XN. Решаем систему (9), (10) относительно переменных р, g М{ для всех i g N Для каждого решения р нужно проверить остальные неравенства
V/ € М Vxi?Xi\Yi ы,-(б*., p/)Mf(p„ pf). Биматричные игры
Для игр двух лиц описанные выше вычисления становятся более наглядными при использовании матричного представления, которое мы уже описывали для простых примеров. Выигрыши игрока і теперь заданы матрицей
Ui~ [ні (xt *)]**і*
х% €
где Хгмножество строк, а Х2множество столбцов. Смешанная стратегия р, ? М, есть вектор-строка
Рі= [Рі (Л'і)]^і е х,,
а смешанная стратегия р2 € Mt есть вектор-столбец
Рг = f Рг (^а)1*і е Xs-
Выигрыш игрока і есть обычное матричное произведение Щ (Рі Ра) " Рі^іРг-
Предположим, что (pt, р2)вполне смешанный NE-тхом,. Тогда система (10) принимает вид
(И)
^ 1р2 "
\hUs = vjLx„
где С/,-р2 есть /??-выигрыш игрока t, а fx, (соответст
венно і*,) вектор-столбец (вектор-строка), все компоненты которого равны 1.
Лемма 2. Пусть Хх = Х, и Uv U2две невырожденные XtxXz матрицы. Тогда если игра G = (Xx, Х2, Ult Ut) имеет вполне смешанный NE-ucxod (рх, р2), то он единствен и задается так:
где V; -1, 2.x,Ui х,
Обратно, если векторы р1( р2 удовлетворяют (12) и все их компоненты неотрицательны, то пара (рх, р2) является смешанным NE-исходом в игре G.
Доказательство. Умножая первое уравнение в (11) на 1/р1, получаем р2 = Умножая последнее равенство на і*,,
имеем 1 = іхг-Н'2==уДх!Уі"1:1;с1, следовательно, число ?г отлично от нуля и равно l/i^l^ix,. Обратное утверждение доказывается также легко: из (12) выводим (11), поэтому
I Pit^psj для всех
I = для всех р4€М2-
Заметим, что (р2, р2) вполне смешанный AfjE-исход только при условии, что все его компоненты положительны. Система (12) этого не гарантирует. Для вычислительных целей лучше представлять равновесные выигрыши в (12) следующим образом:
(13)
, det (Up
2 VCi(*u
Х\ € Хі АГд б Xj
где Uc(xu х2) обозначает алгебраическое дополнение элемента (х? х2) в матрице U.
Часто приходится довольствоваться утверждениями для случая общего положения, т. е. верными для почти всех игр.
Определение 3. Пусть множества стратегий игроков Xt и Х2 конечны. Скажем, что некоторое свойство Р выполнено почти для всех игр, определенных на Х1хХ2, если множество
{(и "2)€Кх,хХ*хКх‘х;Чдля игры (Хх, Х2, ии ы2) не выполнено Р)
имеет меру Лебега, равную нулю, и содержится в некотором замкнутом подмножестве без внутренних точек пространства ц?Х,хх2 [rx,xx„ (снабженного обычной топологией) ),
Теорема 3. Пусть Хх и Хгзаданные конечные множества. Почти для всех игр, определенных на X, х Х2, выполнено следующееі
множество равновесий по Нэшу в смешанных стратегиях конечно%) и для любого равновесного по Нэшу исхода игры в смешанных стратегиях (р1) р3) ? N Е (Gm) множества [[хг] и [р3] состоят из одинакового числа элементов.
Доказательство. Напомним, что система из k векторов \еи ек\ пространства R называется аффинно независимой, если система из k 1 векторов (ejек, ..., ек_х ек) линейно независима в IR.
Будем говорить, что игра регулярна, если выполнено следующее условие:
для любых /,сХj и /3сХ3
1) система из /J векторов и[^ (хх) (их (хи х2))Хг6І!(х1^І1) имеет максимальный аффинный ранг в R/z, (14)
2) система из /а векторов и^ (хг) = (и2(хи x2))XiSi,(xs^I2) имее-т максимальный аффинный ранг в IR{.
Ясно, что почти все игры, определенные на XtxX, являются регулярными в смысле условия (14),
Пусть игра (Xj, Х3, и? ы3) регулярна и (р,і( р3) € НЕ (Gm) равновесие по Нэшу в смешанных стратегиях. В силу свойства (7) теоремы 2 для любого фиксированного элемента хі € [р2] выполнено _
?х2 ^ [Ргі ^2 СМ'х ^2г2) ~ П3 (Рі, бд.о ),
ИЛИ /
?Х2 € LmJ 2 4,2{хх, х2) [Aj (Xj) = 2 U2 0^11 Xz) Мт t^l)-
АГ,6[ц,]
Итак, I [p3] I векторов (x3) (x2 € [p3]) лежат в одной и той же гиперплоскости пространства Если бы в [pj содержалось
меньше элементов, чем в [р3], то это противоречило бы регулярности в смысле (14).
Таким образом, [р3] г^[Рх]. Аналогичным образом из теоремы 2 вытекает, что [Р'1]Іг^ІІЛ]- Следовательно, [Рх] = [РаЦ.
Осталось доказать, что множество NE(Gm) конечно. Если бы оно было бесконечно, то нашлись бы две пары по Нэшу смешанных стратегий (ри р2) и (р^, р4), такие, что
[Рі] = [РіІ! [Ра] ~ ІИв]* (Мі M's) (М! И-з)-
Пусть, например, pt Ф р^. Выберем произвольный элемент € [р2]. В силу свойства (7) теоремы 2 имеем
^2 (і^ІІ ^2 (Пі ®л)*2^. б*,)=й2(рь бхо).
(15)
€ [р2]
Однако [р2] векторов и[^ (х2), л;2€[р2] имеют по предположению максимальный аффинный ранг в IRCm.i1, другими словами,
( Ln-a] I !) вектрв {ul/i] (x2) u[ill] (4)), х2 g Ги2] \ хі имеют максимальный линейный ранг, равный) [р2] 1 (напомним, что ІЫЫЫІ)- Между тем рх, м-і€и р,х#рь поэтому векторы pf и р^ линейно независимы.
Итак, в силу условия (15) получаем, что ранг системы векторов {(ы^і] (*2)ы[т3 (4))},2б[(1г] ч х$ не больше ([р2] 2. Полученное противоречие доказывает теорему.
Теорема 4. Пусть Хг и Х2 фиксированные конечные множества. Почти для всех игр, определенных на Xt х Х2, справедливо следующее утверждение:
Равновесные по Нэшу исходы в смешанных стратегиях, которые не являются равновесными в исходной игре, не являются оптимальными по Парето в смешанном расширении игры.
Доказательство. Пусть (рх, р2) (Е НЕ (Gm). Покажем, что исход (р1( р2) не является оптимумом Парето в игре Gm == = (Мг, М2, иь ы2). Пусть игра (Хи Х-2, uit и2) регулярна (т. е. выполнено свойство (14)).
Из доказательства теоремы 3 имеем I [м-і] I = I [м-г] I- Обозначим через И1 и И2 квадратные матрицы порядка I [рх] IXI [р2] , полученные ограничением функций щ и ы2 на [Рі]х[р2]. Обозначим также через р, вектор-строку (pj (я,),
-^і € [м-і]) а чеРез равектор-столбец (р2(л;2), х,€[р2]). Пусть іі (іг) обозначает вектор-строку (столбец) пространства с компонентами, равными единице. Из свойства (7) теоремы 2 получаем
(M-i М-а) * = (М-і М-а)' tfl-i- (16)
Предположим, что матрицы Ut и U 2 не вырождены (напомним, что они квадратные) и удовлетворяют следующему свойству:
I ^€R ±1U^Ui = alii,
\ У2Уг1і. = аа-і2.
В силу (16) имеем
р^ = Ы2 (pj, р2) - H-i ¦ ?72 *; Pg Mj (pj, p2)?/11-H,
Поскольку матрицы Ui и U 2 невырождены, то (^(рх, ц2)ф0 и и, (рх, р2) Ф 0. Итак, свойство (17) эквивалентно следующему:
(18)
(19)
\ 1-7 2 Ш ' -^-2*
Условие (18) можно переписать так:
3?й* = 0 и fc1C/2M-2 0, 362еі?М і3-62 = 0 и ^t/AX).
(Для доказательства эквивалентности (18) и (19) нужно использовать лемму Фаркаша.)
В силу (16) для всех Х0 и Ьи Ь2, удовлетворяющих (19), получаемА + Mi) U і (р* + р1У1р2 =
= * (biU^ + frUA + MJJM = X W^-ЩиА). (20)
Аналогично?Х, 0 (pj + Xfrj) U2 (р2+ М*) = ^ А^гРг 4 Х^И ,2) 4 9l^2P2
Следовательно, в силу (19) для достаточно малой X 0 имеем
Pj?/jP2 (pi 4* Xfx) U j (р2 4 Xf3)i (21)
Рх^гРг (14 4 ^x) (Рг "1" ^г)
Отметим, что по построению рх (хг) 0 при хг ? [р,] и р3 (х2) 0 при х2 ^ [р3]- Следовательно, в силу (19) для достаточно малых X 0 получаем
?*х € [pi] (Pi + Щхг 0 2 (Рх 4 Щ)хг = 1.
(22)*1 е [ц,] ^
? *2 € [р2] (9а 4 Щ)х, . 2 (Рг + ^г)*, = 1 -
*2€[Hs!
Иначе говоря, соответствующие векторам (pi+Xbj) и (р3+лЬ3) смешанные стратегии pJ^Afi с носителем [рх] и р? € М2 с носителем [р3] в силу (21) удовлетворяют условию
/ ui (Рі 9а) иі (91 (^а)' ^23)
\ Ы3 (рх, ра) М3 (рх, рг).
Итак, исход (рі, р3) не является оптимумом Парето в игре (Мл, М2, и2, и2). Чтобы прийти к этому заключению, нам пришлось предположить, что исходная игра регулярна и что ограничения Mj и и2 на [pj х [р2] не вырождены (если их отождествить с квадратными матрицами) и, кроме того, удовлетворяют свойству (17).
Заметим, что свойство (17) заведомо не выполнено, если Ux и U2матрицы 1 х 1, или, другими словами, (М'і. (^а) пара чистых стратегий. Напротив, если Ut и U2 квадратные матрицы с хотя бы двумя строками, почти все пары (Uv U2) состоят из обратимых пар, удовлетворяющих условию (17). (Доказательство оставляем читателю.)
Пусть ймножество регулярных игр, таких, что при /jdXj и /jcXj (I /t (= I /21 1) ограничения их и и2 на /1Х/2 являются невырожденными матрицами, удовлетворяющими условию (17). Тогда множество й открыто и всюду плотно (как конечное пересечение конечных всюду плотных множеств) и его дополнение имеет меру Лебега, равную нулю (поскольку оно является конечным объединением многообразий коразмерности 1). Это доказывает утверждение теоремы 4.
Пример 3, Биматричные игры 2x2 (у каждого игрока по две стратегии: Т, В и L, R, которым на рисунке соответствуют стратегии Верх, Низ и Слева, Справа).
Рассмотрим следующее семейство биматричных игр
Игрок 1
Предположим, что а{, bh c;, d{ четыре различных действительных числа (і=1, 2). Этого достаточно для исключения вырожденных случаев: множество NE (Gm) всегда будет конечно.
Имеется три класса игр.
Случай 1. В исходной игре G по крайней мере один игрок, скажем игрок 1, имеет доминирующую стратегию, скажем Т Тогда игра С и ее смешанное расширение Gm имеют единственную ситуацию равновесия по Нэшу:
{(Г, L)} при йі Cj, {(Т, R)} при аг с2.
NE{G) = NE{Ga)~
В самом деле, неравенства ах bu сх dx приводят к тому, что в игре Gm чистая стратегия Т строго доминирует все остальные смешанные стратегии.
Случай 2. Игра G не имеет равновесия по Нэшу Это может быть следствием выполнения одной из систем неравенств
{Рі ^1 @2 ^2 ^2 ^2}
ИЛИ
{^х С ^1 Сх, С2 ^2 ^2 ^2}
Тогда смешанное расширение Gffl игры G имеет единственный Л/?-исход, а именно вполне смешанное равновесие:
? _ / d2ft2_ а2С2_
(24)
^ \ a2 + d2b2 с2 ’ a2 + d2ft2с2
_ ( rfi~ci сцbj
^ V ai + ^i biCi ’ a1 + d1b1c1
Соответствующие равновесные выигрыши определяются так:
aidjfcxCx ax+dfbiex *
а2Л2b2c2 a2 -\-d2b2c2
(25)
Эти формулы являются непосредственным следствием леммы 3 и уравнения (13): в силу предположений случая 2 либо Ut невырожденная матрица, либо мы можем добавлением константы с к матрице U{ сделать матрицу U(-j-c невырожденной. Эта операция не изменяет множество І?^-исходов и добавляет ту же константу с к І?^-выигрышам.
Случай 3. Игра G имеет два равновесия по Нэшу
Это получается при выполнении одной из систем неравенств
{^х С аи Сх; ^1 ^2 С ^2* ^2 ^2}
или
{af Ь1г dt с2, a2 с2, d2 b2}.
Тогда в игре Gm возникает еще один і?^-исход, а именно вполне смешанное равновесие (p,f, p,f), определяемое из (24):
NE{Gm) = NE{G)U {(м-*. р?)}-
В качестве упражнения оставляем читателю проверить, что случаи 1, 2, 3 есть в точности разбиение семейства биматрич-ных игр 2x2, удовлетворяющих условию о взаимной однозначности.
Упражнение 6
Приведите пример биматричной игры G 2x2, в которой ни у одного игрока нет эквивалентных чистых стратегий, а множество НЕ (GJ бесконечно.
Упражнение 7. Игры 2x2 с нулевой суммой Рассмотрите семейство игр 2x2 с нулевой суммой:
Случай 1. Пересечение [а, d]C\[b, с] не пусто.
Тогда игра G имеет цену. При рассмотрении ее смешанного расширения ничего нового не получается.
Случай 2. Пересечение [a, d] П [b, с] пусто.
Тогда игра G не имеет цены, а в игре Gm существует единственная седловая пара, причем она вполне смешанная. Цена игры Gm определяется так:
ad be a+dbc’vm(G)
Упражнение 8
Дайте геометрический метод вычисления цены игры в смешанных стратегиях и оптимальных смешанных стратегий для любой игры двух лиц с нулевой суммой, в которой хотя бы у одного игрока имеется только две чистые стратегии). Примените этот метод к игре
ГО 3 2 5 3/21[6 2 1 0 2 J-
Упражнение 9
Пусть (Xt, Х5, ?/j) игра двух лиц с нулевой суммой, в смешанном расширении которой нет вполне смешанной седловой пары.
Для всех (лг1( х2) g Xj X Xj обозначим через ?г (х1} х2) цену игры
(Х1\{х1}) Х5\{хг}, иг)
в смешанных стратегиях. Платежная матрица этой игры получается из исходной матрицы U1 зачеркиванием строки х, и столбца х2.
Докажите, что игра (Xlf Xj, ?^) имеет седловую пару в чистых стратегиях и ее цена равна цене игры Gm.
Задача 4. Игра таможенный досмотръ Имеются два игрока таможенник (игрок I) и коммерсант (игрок 2). Коммерсант появляется на таможне несколько раз. Каждый раз он решает взять с собой контрабандный товар
или нет (ему нужно пронести этот товар ровно одни раз). Таможенник при каждом появлении коммерсанта может произвести досмотр. В игре Gn коммерсант появляется на таможне не более п раз.
Игра кончается, если была попытка пронести контрабандный товар независимо от того, удачная она или нет.
Если на шаге п игрок 1 проверяет игрока 2, а у того нет ничего предосудительного, то игрок 1 платит игроку 2 единицу И начинается игра G„_x. Если игрок 1 отказывается от проверки, а игрок 2 проносит контрабанду, то игрок 2 получает с(с1) и игра кончается.
Если игрок 1 обнаруживает контрабандный товар, то он получает награду /(/с) и игра заканчивается. Если проверка не произведена, и контрабанда не пронесена, то никаких платежей не делается и начинается игра G„_j.
1) Предполагая известной цену y„_j игры G„_t в смешанных стратегиях, найдите цену ?п игры Gn в смешанных стратегиях.
2) Вычислите ?п и оптимальные смешанные стратегии обоих игроков.
Задача 5
Зафиксируем конечные множества Xlt Х2 и для любой матрицы Ut обозначим через ?т{і!х) цену игры (с нулевой суммой) (Хи Х2, их) в смешанных стратегиях.
1) Докажите, что ^((/^ непрерывная функция Ux.
2) Докажите, что существует открытое всюду плотное множество Q из R*iX-**, такое, что для любого ?х из Q смешанное расширение игры (Хх, Х2, Ux) имеет единственную седловую пару.
Задача 6. Выгодные потери выигрыша при вполне смешанном равновесии по Нэшу (Мулен [1975])
Пусть G (Xlt Х2, U 1( U2) биматричная игра, в которой множества Хх и Х2 имеют одинаковую мощность, а 1/, и У, невырожденные ХххХ2 матрицы. На протяжении данной задачи предположим, что Gm имеет (обязательно единственное) вполне смешанное равновесие (ц1( р,2), определяемое по лемме 2.
Положим ?1=о1-Их,(/Г1- Таким образом, ?г вектор (строка) из R**. Компоненты этого вектора могут иметь произвольный знак.
Отметим, однако, что Vj-4x, = l и, следовательно, некоторые компоненты ?, неотрицательны.
1) Докажите, что ?х есть смешанная стратегия игрока 1 тогда и только тогда, когда вполне смешанный /V?-выигрыш Oj (заданный в (12)) является ценой игры с нулевой суммой (Х2, Х2, Uj) в смешанных стратегиях:
