Игры с выпуклыми функциями выигрышей.

Игры с выпуклыми непрерывными функциями выигрышей, называемые часто ядром, называются выпуклыми.

Напомним, что выпуклой функцией f действительной переменной х на интервале (а,b) называется такая функция, для которой выполняется неравенство

f(a₁ х₁ + a₂ х₂) £ a₁ f(х₁) + a₂ f(х₂),

где х₁ и х₂  любые две точки из интервала (а,b); a₁, a₂ ³ 0, причём a₁ + a₂ = 1.

Если для a₁ ¹ 0, a₂ ¹ 0 всегда имеет место строгое неравенство

f(a₁ х₁ + a₂ х₂) < a₁ f(х₁) + a₂ f(х₂),

то функция f называется строго выпуклой на (а;b). Геометрически выпуклая функция изображает дугу, график которой расположен ниже стягивающей её хорды (см. рис.)

Напомним, также, что непрерывная и строго выпуклая функция f на замкнутом интервале принимает минимальное значение только в одной точке интервала.

Для нахождения решения выпуклой игры можно воспользоваться следующей теоремой.

Теорема 4. Пусть М(х, y)  непрерывная функция выигрышей игрока 1, на единичном квадрате и строго выпуклая по y для любого х. Тогда имеется единственная оптимальная чистая стратегия y = y_o Î[0;1] для игрока 2, цена игры определяется по формуле

V = M(x, y),

значение y_o определяется как решение следующего уравнения

M(x, y_o) = V.

Замечание. Если в теореме 4 не предполагать строгую выпуклость функции М(х, y) по y, а просто выпуклость, то теорема остаётся в силе с тем отличием, что у игрока 2 оптимальная чистая стратегия не будет единственной.

Замечание. Выпуклые игры называют часто выпукло-вогнутыми, т.к. игра в них имеет седлообразное ядро, а так как ядро седлообразное, то игра имеет седловую точку в чистых стратегиях.

Таким образом, если М(х, y) непрерывна и выпукла по y, то цена игры определяется по формуле (1), и игрок 2 имеет оптимальную чистую стратегию, определяемую из уравнения (2).

Аналогично и для игрока 1: если функция выигрышей М(х, y) непрерывна по обоим аргументам и строго вогнута по х при любом y, то в этом случае игрок 1 имеет единственную оптимальную стратегию.

Цена игры определяется по формуле

V = M(x,y),

а чистая оптимальная стратегия х_o игрока 1 определяется из уравнения

M(x_o, 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 существует оптимальная чистая стратегия y_o, определяемая из уравнения (4)

=

Очевидно, максимум по х достигается при х = , и последнее уравнение примет вид

= .

Решением последнего уравнения будет y_o = 0. Следовательно, игрок 2 имеет оптимальную чистую стратегию y_o = 0.

Замечание. В приведённом выше примере мы могли определить оптимальную стратегию игрока 1, а игрока 2 - только случайно, в силу удачного вида М(х, y).

Рассмотрим теперь метод определения оптимальных стратегий того игрока, для которого функция выигрышей не обязательно выпукла. Пусть непрерывная функция М(х, y), заданная на единичном квадрате, выпукла по y. Нас будет интересовать вопрос нахождения оптимальных стратегий 1 игрока. Предположим также, что для х Î[0; 1], y Î[0; 1] существует частная производная функции М(х, y) по y, причём в точках y = 0 и y = 1 (х, y) = понимается как правая и левая производная соответственно. Обозначим через y_o одну из оптимальных чистых стратегий игрока 2 (эта стратегия существует в соответствии с теоремой 4).

Согласно теореме 2 чистые стратегии х игрока 1 могут входить в его оптимальную стратегию с положительной вероятностью, если для них выполняется равенство

М(х, y_o) = V.

Такие чистые стратегии х называются существенными.

Теорема 5. Пусть дана бесконечная антагонистическая игра с непрерывной и дифференцируемой по y на единичном квадрате при любом х функцией выигрышей М(х, y), с оптимальной чистой стратегией y_o игрока 2 и ценой игры V, тогда :

1) если y_o = 1, то среди оптимальных стратегий игрока 1 имеется существенная чистая стратегия х₁, для которой

(х₁, 1) £ 1;

2) если y_o = 0, то среди оптимальных стратегий игрока 1 имеется существенная чистая стратегия х₂, для которой

(х₂, 0) ³ 0;

3) если 0 £ y_o £ 1, то среди оптимальных стратегий игрока 1 найдётся такая, которая является смесью двух существенных стратегий х₁ и х₂. Для этих стратегий

(х₁, y_o) £ 0, (х₂, y_o) ³ 0,

стратегия х₁ употребляется с вероятностью a, стратегия х₂  с вероятностью (1 - a), где a находится из уравнения

a (х₁, y_o) + (1 - a) (х₂, y_o) = 0.

Пример. Пусть функция выигрышей в бесконечной антагонистической игре задана на единичном квадрате и равна

М(х, y) = (х - y)² = х² - 2хy + y².

Эта функция непрерывна по х и y, и поэтому эта игра имеет решение. Кроме того

= 2 > 0.

Следовательно, М(х, y) выпукла по y, и поэтому согласно теореме 4 цена игры определяется по формуле (1), игрок 2 имеет чистую оптимальную стратегию y_o, определяемую из уравнения (2). Таким образом, имеем

V = (x - y)²;

Для определения (x² - 2xy + y²) последовательно найдём

= 2x - 2y := 0 Þ x = y

= 2 > 0 Þ при x = y функция M имеет минимум для любого y.

Þ максимум достигается в одной из крайних точек x = 0 и (или) x = 1

M(0; y) = y²

M(1; y) = 1 - 2y + y² = (y - 1)²

Þ V= max {y²; (1 - y)²}

Данный max {...} достигается в том случае, если y² = (1 - y)², т.е. y = .

Следовательно V = при y_o = .

Определим теперь оптимальные стратегии для игрока 1. Поскольку y_o = , то 0 < y_o < 1. Согласно теореме 5 рассмотрим третий случай.

Определим х из уравнения

М(х, y_o) = V,

то есть

(х - )² = .

Решая последнее уравнение, получим х₁ = 0, х₂ = 1. Теперь необходимо определить величину a  вероятность применения чистой стратегии х₁ = 0. С этой целью используем уравнение (*).

a (0, ) + (1 - a) (1, ) = 0.

Нетрудно найти

Тогда уравнение для a примет вид :

a - (1 - a) = 0,

откуда a = . Следовательно, стратегия игрока 1

F(х) = J_o(х) + J₁(х),

а игрока 2

Q(y) = (y).

Здесь через (x) обозначена ступенчатая функция

(x) = .