- •2. Элементы теории игр
- •2.1. Введение
- •2.2. Стратегии. Нормальная форма игры
- •2.3. Ситуации равновесия
- •2.4. Антагонистические игры. Игры с нулевой суммой
- •2.5. Нормальная форма
- •2.6. Смешанные стратегии
- •2.7. Теорема о минимаксе
- •2.8. Вычисление оптимальных стратегий
- •2.9. Игры с ограничениями
- •2.10. Бесконечные игры
- •2.11. Игры на квадрате
- •2.12. Игры с непрерывным ядром
- •2.13. Вогнуто-выпуклые игры
- •2.14. Игры с выбором момента времени
2.13. Вогнуто-выпуклые игры
Определение. Говорят, что игра на квадрате вогнуто-выпукла, если еѐ яд-
ро A(x, y) вогнуто по x при каждом значении y и выпукло по y при ка-
ждом значении x .
Вогнуто-выпуклая игра должна иметь седлообразное ядро, и, по-
видимому, седловую точку в чистых стратегиях.
Теорема. Пусть вогнуто-выпуклая игра A(x, y) непрерывна. Тогда она
имеет оптимальные чистые стратегии.
Доказательство. Так как игра непрерывна, она имеет непрерывные стра-
тегии. Пусть для игроков 1 и 2 это будут соответственно F ( x) и G( x) .
Теперь положим
1
x0
y0
0
1
xdF ( x) ,
ydG( y) .
(1)
(2)
0
Так как функция A(x, y) вогнута по x , то для любой заданной y
существует такое , что функция
By (x)
A( x, y)
x
достигает своего максимального значения (при фиксированном y ) в точке
x0 . Мы имеем
1
E(F , y)
1
0
(B y ( x)
x)dF ( x) ,
1
E(F , y)
0
B y ( x)dF ( x)
0
xdF ( x) .
(3)
46
Функция By достигает максимума в x0 , следовательно, первый ин-
теграл в (3) не превосходит By ( x0 ) (т.к.
dF ( x) 1). Поэтому
E(F , y)
By (x0 )
x0
A(x0 , y) ,
(4)
откуда следует, что x0 не хуже F против любой y . Аналогично можно
показать, что y0 не хуже G против любой стратегии x . Таким образом, x0
и y0 – оптимальные чистые стратегии.
Пример 2.8. Рассмотрим игру с ядром
A(x, y)
2x 2
y 2
3xy
x 2 y .
Так как Axx
Видим, что
Полагая
найдем
4 <0, Ayy
2 >0, то игра действительно вогнуто-выпуклая.
Ax
-474x 3 y 1.
Ax
-474x 3 y 1=0,
x
3 y 1
4
.
Это значение x максимизирует A . Однако оно не всегда лежит в
единичном интервале, будучи отрицательным при y < 1/3. В последнем
случае получаем максимум, полагая x
0 . Следовательно,
( y)
0, если y
3 y 1
4
1
3
y
;
1
3
.
Аналогично находим
Ay
2 y 3x 2 ,
откуда находим, приравняв ее 0, с учетом того, что величина
всегда лежит на единичном интервале
2 3 x
2
не
( x)
2 3 x
2
0, если
x
x
2
3
2
3
.
;
Теперь легко найти оптимальные стратегии и значение игры.
x
4
17
, y
11
17
,
13
17
.
47
, если
, если
