Определение бесконечной антагонистической игры
Естественным обобщением матричных игр являются бесконечные антагонистические игры (БАИ), в которых хотя бы один из игроков имеет бесконечное количество возможных стратегий. Мы будем рассматривать игры двух игроков, делающих по одному ходу, и после этого происходит распределение выигрышей. При формализации реальной ситуации с бесконечным числом выборов можно каждую стратегию сопоставить определённому числу из единичного интервала, т.к. всегда можно простым преобразованием любой интервал перевести в единичный и наоборот.
Напоминание. Пусть Е – некоторое множество вещественных чисел. Если существует число y, такое, что x£y при всех хÎЕ (при этом y не обязательно принадлежит Е), то множество Е называется ограниченным сверху, а число y называется верхней границей множества Е. Аналогично определяется ограниченность снизу и нижняя граница множества Е. Обозначаются верхняя и нижняя границы соответственно через sup Е и inf Е соответственно.
Пример. Пусть множество Е состоит из всех чисел вида , n = 1,2, ... Тогда множество Е ограничено, его верхняя грань равна 1, а нижняя 0, причём 0ÏЕ , а 1ÎЕ.
Для дальнейшего изложения теории игр этого класса введём определения и обозначения : [0; 1] – единичный промежуток, из которого игрок может сделать выбор; х – число (стратегия), выбираемое игроком 1; y– число (стратегия), выбираемое игроком 2; Мi
(x,y) – выигрыш i-го игрока; G (X,Y,M1
,M2
) – игра двух игроков, с ненулевой суммой, в которой игрок 1 выбирает число х из множества Х, игрок 2 выбирает число y из множества Y, и после этого игроки 1 и 2 получают соответственно выигрыши M1
(x, y) и M2
(x, y). Пусть, далее, G (X,Y,M) – игра двух игроков с нулевой суммой, в которой игрок 1 выбирает число х, игрок 2 – число y, после чего игрок 1 получает выигрыш М(x, y) за счёт второго игрока.
Большое значение в теории БАИ имеет вид функции выигрышей M(x, y). Так, в отличии от матричных игр, не для всякой функции M(x, y) существует решение. Будем считать, что выбор определённого числа игроком означает применение его чистой стратегии, соответствующей этому числу. По аналогии с матричными играми назовём чистой нижней ценой игры величину
V1
= M(x, y) или V1
= M(x, y),
а чистой верхней ценой игры величину
V2
= M(x, y) или V2
= M(x, y),
Для матричных игр величины V1
и V2
всегда существуют, а в бесконечных играх они могут не существовать.
Естественно считать, что, если для какой-либо бесконечной игры величины V1
и V2
существуют и равны между собой (V1
= V2
= V), то такая игра имеет решение в чистых стратегиях, т.е. оптимальной стратегией игрока 1 есть выбор числа xo
ÎX и игрока 2 – числа yo
ÎY, при которых M(xo
, yo
) = V, в этом случае V называется ценой игры, а (xo
, yo
) – седловой точкой в чистых стратегиях.
Пример 1. Игрок 1 выбирает число х из множества Х = [0; 1], игрок 2 выбирает число y из множества Y = [0; 1]. После этого игрок 2 платит игроку 1 сумму
M(x, y) = 2х2
- y2
.
Поскольку игрок 2 хочет минимизировать выигрыш игрока 1, то он определяет
(2x2
-y2
) = 2х2
- 1,
т.е. при этом y = 1. Игрок 1 желает максимизировать свой выигрыш, и поэтому определяет
(M(x, y)) = (2х2
- 1) = 2-1 = 1,
который достигается при х = 1.
Итак, нижняя цена игры равна V1
= 1. Верхняя цена игры
V2
= ((2х2
-y2
)) = (2 - y2
) = 2-1 = 1,
т.е. в этой игре V1
= V2
= 1. Поэтому цена игры V = 1, а седловая точка (1;1).
Пример 2. Игрок 1 выбирает хÎX = (0; 1), игрок 2 выбирает yÎY = (0; 1). После этого игрок 1 получает сумму
M(x, y) = x + y
за счёт игрока 2. Поскольку Х и Y- открытые интервалы, то на них V1
и V2
не существуют. Если бы Х и Y были замкнутые интервалы, то, очевидно, было бы следующее :
V1
= V2
= 1 при xo
= 1, yo
= 0.
С другой стороны, ясно, что, выбирая х достаточно близкое к 1, игрок 1 будет уверен, что он получит выигрыш не меньше, чем число, близкое к цене игры V = 1; выбирая y близкое к нулю, игрок 2 не допустит, чтобы выигрыш игрока 1 значительно отличался от цены игры V = 1.
Степень близости к цене игры может характеризоваться числом e > 0. Поэтому в описываемой игре можно говорить об оптимальности чистых стратегий хo
= 1, yo
= 0 соответственно игроков 1 и 2 с точностью до произвольного числа e > 0. В связи с этим введём следующие определения.
Точка (,), где ÎX, ÎY, в антагонистической непрерывной игре G называется точкой e-равновесия , если для любых стратегий xÎX игрока 1, yÎY игрока 2 имеет место неравенство
М(х,) -e£M(,) £ М(, y) + e.
Точка e-равновесия (,) называется также e-седловой точкой функции М(x, y), а стратегии и называются e-оптимальными стратегиями. Эти стратегии являются оптимальными с точностью до e в том смысле, что, если отклонение от оптимальной стратегии никакой пользы игроку принести не может, то его отклонение от e-оптимальной стратегии может увеличить его выигрыш не более, чем на e.
Можно доказать, что для того, чтобы функция М имела e-седловые точки для любого e>0 необходимо и достаточно чтобы
M(x, y) = M(x, y).
Если игра G не имеет седловой точки (e-седловой точки) в чистых стратегиях, то оптимальные стратегии можно искать среди смешанных стратегий. Однако, в качестве вероятностной меры здесь вводятся функции распределения вероятностей применения игроками чистых стратегий.
Пусть F(х) – функция распределения вероятностей применения чистых стратегий игроком 1. Если число x- чистая стратегия игрока 1, то
F(х) = P(x£ х),
где P(x£ х) означает вероятность того, что случайно выбранная чистая стратегия x не будет превосходить числа х. Аналогично рассматривается функция распределения вероятностей применения чистых стратегий h игроком 2
Q(y) = P(h£ y).
Функции F(х) и Q(y) называются смешанными стратегиями соответственно игроков 1 и 2. Если F(х) и Q(y) дифференцируемы, то существуют их производные, обозначаемые соответственно через f(x) и q(y) (функции плотности распределения).
В общем случае дифференциал функции распределения dF(х) выражает вероятность того, что стратегия x находится в промежутке
х £x£ х + dх.
Аналогично для игрока 2: dQ(y) означает вероятность того, что его стратегия h находится в интервале
y £h£ y + dy.
Тогда выигрыш игрока 1 составит
М(х, y) dF(х),
а выигрыш игрока 2 равен
М(х, y) dQ(y).
Средний выигрыш игрока 1 при условии, что игрок 2 применяет свою чистую стратегию y, получим, если проинтегрируем выигрыш по всем возможным значениям х, т.е.
E(F, y) =
Напомним, что множество Y для y является замкнутым промежутком [0; 1].
Если игрок 1 применяет свою чистую стратегию х, а игрок 2 - y, то выигрыш игрока 1 составит
М(х, y) dP(х) dQ(y).
Средний выигрыш игрока 1 при условии, что оба игрока применяют свои смешанные стратегии F(х) и Q(y), будет равен
E(F,Q) = .
По аналогии с матричными играми определяются оптимальные смешанные стратегии игроков и цена игры: в антагонистической непрерывной игре G(Х,Y,М) пара смешанных стратегий F*(х) и Q*(y) соответственно для игроков 1 и 2 образует седловую точку в смешанных стратегиях, если для любых смешанных стратегий F(х) и Q(y) справедливы соотношения
Е(F,Q*) £ Е(F*,Q*) £ Е (F*,Q).
Из левой части последнего неравенства следует, что если игрок 1 отступает от своей стратегии F*(х), то его средний выигрыш не может увеличиться, но может уменьшиться за счёт лучших действий игрока 2, поэтому F*(х) называется оптимальной смешанной стратегией игрока 1.
Из правой части последнего неравенства следует, что если игрок 2 отступит от своей смешанной стратегии Q*(y), то средний выигрыш игрока 1 может увеличиться, а не уменьшиться, за счёт более разумных действий игрока 1, поэтому Q*(y) называется оптимальной смешанной стратегией игрока 2. Средний выигрыш Е(F*,Q*), получаемый игроком 1 при применении игроками оптимальных смешанных стратегий, называется ценой игры.
По аналогии с матричными играми рассматривается нижняя цена непрерывной игры в смешанных стратегиях
V1
= E(F,Q)
и верхняя цена игры
V2
= E(F,Q).
Если существуют такие смешанные стратегии F*(х) и Q*(y) соответственно для игроков 1 и 2, при которых нижняя и верхняя цены непрерывной игры совпадают, то F*(х) и Q*(y) естественно назвать оптимальными смешанными стратегиями соответствующих игроков, а V1
= V2
= V – ценой игры.
Можно доказать, что существование седловой точки в смешанных стратегиях игры G(Х,Y,М) равносильно существованию верхней V2
и нижней V1
цен игры в смешанных стратегиях и их равенству V1
= V2
= V.
Таким образом, решить игру G(Х,Y,М) – означает найти седловую точку или такие смешанные стратегии, при которых нижняя и верхняя цены игры совпадают.
Теорема 1 (существования). Всякая антагонистическая бесконечная игра двух игроков
Теорема 2. Пусть – бесконечная антагонистическая игра с непрерывной функцией выигрышей М(х, y) на единичном квадрате и ценой игры V. Тогда, если Q(y) – оптимальная стратегия игрока 2 и для некоторого xo
,
то xo
не может входить в точки спектра оптимальной стратегии игрока 1; если F(х) – оптимальная стратегия игрока 1и для некоторого yo
,
то yo
не может быть точкой спектра оптимальной стратегии игрока 2.
Из теоремы 2 следует, что если один из игроков применяет оптимальную стратегию, а другой – чистую, притом что средний выигрыш игрока 1 отличается от цены игры, то эта чистая стратегия не может войти в его оптимальную стратегию (или она входит в неё с вероятностью нуль).
Теорема 3. Пусть в бесконечной антагонистической игре функция выигрышей М(х,y) непрерывная для хÎ[0; 1], yÎ[0; 1] и
М(х, y) = -М(y, х),
тогда цена игры равна нулю и любая оптимальная стратегия одного игрока будет также оптимальной стратегией другого игрока.
Сформулированные свойства оптимальных смешанных стратегий и цены игры помогают находить или проверять решения, но они ещё не дают в общем виде приемлемых методов решения игры. Более того, не существует общих методов для точного нахождения решения БАИ, и в том числе непрерывных игр на единичном квадрате. Поэтому рассматриваются частные виды антагонистических бесконечных игр.
Игры с выпуклыми функциями выигрышей.
Игры с выпуклыми непрерывными функциями выигрышей, называемые часто ядром, называются выпуклыми.
Напомним, что выпуклой функцией f действительной переменной х на интервале (а,b) называется такая функция, для которой выполняется неравенство
f(a1
х1
+ a2
х2
) £a1
f(х1
) + a2
f(х2
),
где х1
и х2
– любые две точки из интервала (а,b); a1
, a2
³ 0, причём a1
+ a2
= 1.
Если для a1
¹ 0, a2
¹ 0 всегда имеет место строгое неравенство
f(a1
х1
+ a2
х2
) < a1
f(х1
) + a2
f(х2
),
то функция f называется строго выпуклой на (а;b). Геометрически выпуклая функция изображает дугу, график которой расположен ниже стягивающей её хорды (см. рис.)
Напомним, также, что непрерывная и строго выпуклая функция f на замкнутом интервале принимает минимальное значение только в одной точке интервала.
Для нахождения решения выпуклой игры можно воспользоваться следующей теоремой.
Теорема 4. Пусть М(х, y) – непрерывная функция выигрышей игрока 1, на единичном квадрате и строго выпуклая по y для любого х. Тогда имеется единственная оптимальная чистая стратегия y = yo
Î[0;1] для игрока 2, цена игры определяется по формуле
V = M(x, y),
значение yo
определяется как решение следующего уравнения
M(x, yo
) = V.
Замечание. Если в теореме 4 не предполагать строгую выпуклость функции М(х, y) по y, а просто выпуклость, то теорема остаётся в силе с тем отличием, что у игрока 2 оптимальная чистая стратегия не будет единственной.
Замечание. Выпуклые игры называют часто выпукло-вогнутыми, т.к. игра в них имеет седлообразное ядро, а так как ядро седлообразное, то игра имеет седловую точку в чистых стратегиях.
Таким образом, если М(х, y) непрерывна и выпукла по y, то цена игры определяется по формуле (1), и игрок 2 имеет оптимальную чистую стратегию, определяемую из уравнения (2).
Аналогично и для игрока 1: если функция выигрышей М(х, y) непрерывна по обоим аргументам и строго вогнута по х при любом y, то в этом случае игрок 1 имеет единственную оптимальную стратегию.
Цена игры определяется по формуле
V = M(x,y),
а чистая оптимальная стратегия хo
игрока 1 определяется из уравнения
M(xo
, y) = V.
Пример. Пусть на квадрате [0;1] задана функция
М(х, y) = .
Так как
для xÎ[0; 1], yÎ(0;1),
то М(х, y) строго вогнута по х для любого yÎ(0;1). Следовательно, цена игры находится по формуле (3)
V = .
Отметим, что при 0 £ х £ справедливо равенство
=
а при 0,5 < х £ 1
=
Поэтому
V = max [; ] =
= max [; ] =
= max [;] = .
При этом значение х получается равным хo
= . Это же значение получается из решения уравнения
= ,
т.к. минимум достигается при y = 0, и это уравнение превращается в следующее
= ,
откуда следует, что х = .
Заметим, что если в функции выигрышей (5) поменять местами х и y, то она не изменится, а следовательно, эта функция выпукла и по y при всех х Î[0;1]. Поэтому к ней применима та же теория, т.е. у игрока 2 существует оптимальная чистая стратегия yo
, определяемая из уравнения (4)
=
Очевидно, максимум по х достигается при х = , и последнее уравнение примет вид
= .
Решением последнего уравнения будет yo
= 0. Следовательно, игрок 2 имеет оптимальную чистую стратегию yo
= 0.
Замечание. В приведённом выше примере мы могли определить оптимальную стратегию игрока 1, а игрока 2 - только случайно, в силу “удачного” вида М(х, y).
Рассмотрим теперь метод определения оптимальных стратегий того игрока, для которого функция выигрышей не обязательно выпукла. Пусть непрерывная функция М(х, y), заданная на единичном квадрате, выпукла по y. Нас будет интересовать вопрос нахождения оптимальных стратегий 1 игрока. Предположим также, что для х Î[0; 1], y Î[0; 1] существует частная производная функции М(х, y) по y, причём в точках y = 0 и y = 1 (х, y) = понимается как правая и левая производная соответственно. Обозначим через yo
одну из оптимальных чистых стратегий игрока 2 (эта стратегия существует в соответствии с теоремой 4).
Согласно теореме 2 чистые стратегии х игрока 1 могут входить в его оптимальную стратегию с положительной вероятностью, если для них выполняется равенство
М(х, yo
) = V.
Такие чистые стратегии х называются существенными.
Теорема 5. Пусть дана бесконечная антагонистическая игра с непрерывной и дифференцируемой по y на единичном квадрате при любом х функцией выигрышей М(х, y), с оптимальной чистой стратегией yo
игрока 2 и ценой игры V, тогда :
1) если yo
= 1, то среди оптимальных стратегий игрока 1 имеется существенная чистая стратегия х1
, для которой
(х1
, 1) £ 1;
2) если yo
= 0, то среди оптимальных стратегий игрока 1 имеется существенная чистая стратегия х2
, для которой
(х2
, 0) ³ 0;
3) если 0 £ yo
£ 1, то среди оптимальных стратегий игрока 1 найдётся такая, которая является смесью двух существенных стратегий х1
и х2
. Для этих стратегий
(х1
, yo
) £ 0, (х2
, yo
) ³ 0,
стратегия х1
употребляется с вероятностью a, стратегия х2
– с вероятностью (1 -a), где a находится из уравнения
a(х1
, yo
) + (1 -a)(х2
, yo
) = 0.
Пример. Пусть функция выигрышей в бесконечной антагонистической игре задана на единичном квадрате и равна
М(х, y) = (х -y)2
= х2
- 2хy + y2
.
Эта функция непрерывна по х и y, и поэтому эта игра имеет решение. Кроме того
= 2 > 0.
Следовательно, М(х, y) выпукла по y, и поэтому согласно теореме 4 цена игры определяется по формуле (1), игрок 2 имеет чистую оптимальную стратегию yo
, определяемую из уравнения (2). Таким образом, имеем
V = (x-y)2
;
Для определения (x2
- 2xy + y2
) последовательно найдём
= 2x - 2y := 0 Þ x = y
= 2 > 0 Þ при x = y функция M имеет минимум для любого y.
Þ максимум достигается в одной из крайних точек x = 0 и (или) x = 1
M(0; y) = y2
M(1; y) = 1 - 2y + y2
= (y - 1)2
V= max {y2
; (1 - y)2
}
Данный max {...} достигается в том случае, если y2
= (1 -y)2
, т.е. y = .
Следовательно V = при yo
= .
Определим теперь оптимальные стратегии для игрока 1. Поскольку yo
= , то 0 < yo
< 1. Согласно теореме 5 рассмотрим третий случай.
Определим х из уравнения
М(х, yo
) = V,
то есть
(х -)2
= .
Решая последнее уравнение, получим х1
= 0, х2
= 1. Теперь необходимо определить величину a– вероятность применения чистой стратегии х1
= 0. С этой целью используем уравнение (*).
a(0,) +(1 -a)(1,) = 0.
Нетрудно найти
Тогда уравнение для a примет вид :
a- (1 -a) = 0,
откуда a =. Следовательно, стратегия игрока 1
F(х) = Jo
(х) + J1
(х),
а игрока 2
Q(y) = (y).
Здесь через (x) обозначена ступенчатая функция
(x) = .