- •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.11. Игры на квадрате
В таких играх каждый игрок имеет континуум чистых стратегий,
обычно представляемых точками интервала [0,1]. Тогда чистая стратегия
каждого игрока – число из этого интервала, а функция выигрыша A(x, y)
определена на единичном квадрате.
Смешанная стратегия представляет собой вероятностное распреде-
ление на множестве чистых стратегий. Оно может быть представлено
функцией распределения:
F (0)
0, F (1) 1,
F (x)
F (x ), если x
x ,
F (x)
F (x 0), если x
0.
Если игрок 1 использует чистую стратегию x , а игрок 2 – смешан-
ную стратегию G( y) , то ожидаемый выигрыш равен интегралу Стильтье-
са:
1
E( x, G)
A( x, y)dG( y).
(1)
0
Если же игрок 2 использует чистую стратегию y , а игрок 1 смешан-
ную стратегию F , то ожидаемый выигрыш
1
E(F , y)
A( x, y)dF ( x).
(2)
0
Наконец, если игрок 1 использует F , а игрок 2 использует G , то
имеем
42
1 1
E(F , G)
A( x, y)dF ( x)dG( y).
(3)
0 0
В каждом случае считаем, что интегралы существуют. Разумеется
тогда
1
1
E(F , G)
0
E(F , y)dG( y)
0
E( x, G)dF ( x).
(4)
Если можно определить два числа
и
то возникают два вопроса:
1
2
supinf E(F , y)
y
inf sup E(x,G) ,
G
(5)
(6)
1) Будет ли выполняться равенство v1
v2 ?
2) Можно ли sup inf и inf sup заменить на max min и min max со-
ответственно?
Если ответ на оба эти вопроса положителен, то оптимальные сме-
шанные стратегии существуют. Если эти стратегии можно найти, то игра
определена столь же хорошо, как и конечные игры.
Если утвердительно можно ответить только на 1-й вопрос, то игра
имеет общее значение v1 и v2 , но не имеет оптимальных стратегий. Тем не
менее, она будет иметь -оптимальные стратегии: т.е. для любого
0
существуют такие смешанные стратегии F и G игроков 1 и 2 соответст-
венно, что
E(F, y)
E(x, G)
v
v
;
для любого x и y из [0,1].
Таким образом, хотя бесконечная игра определена не столь хорошо,
как конечные игры, она обладает известной устойчивостью.
2.12. Игры с непрерывным ядром
Для игр с непрерывным ядром оптимальные стратегии существуют.
Теорема 1. Если ядро A(x, y) – непрерывная функция, то sup inf и
inf sup могут быть заменены на max min и min max соответственно.
Доказательство. Известно, что функция A(x, y) непрерывна. Поэтому для
любой F функция
1
E(F , y)
0
A( x, y)dF ( x)
43
F
x
непрерывна по y . Так как интервал [0,1] компактен, E(F , y) в некоторой
его точке будет достигать минимума. Таким образом, sup inf E(F , y) мож-
y
но заменить на sup min E(F , y) .
y
По определению v1 для любого n существует такое распределение
Fn , что
min E(Fn , y) v1
y
1
n
.
Заметим теперь, что из любой последовательности функций распре-
деления ( F1 , F2 , …) на [0,1] можно извлечь некоторую поточечно сходя-
щуюся подпоследовательность. Пусть F0 – предел этой подпоследователь-
ности. Ясно, что F0 удовлетворяет условиям:
F0 (0)
0, F0 (1) 1,
F0 ( x)
F0 ( x ), если x
x ,
так как им удовлетворяет каждая из функций Fn . С другой стороны, функ-
ция F0 не обязательно удовлетворяет условию F0 ( x)
F0 ( x 0), если
x 0, потому что это свойство не сохраняется при предельном переходе.
Определим функцию F0 следующим образом:
0, если x
0;
F0 ( x)
F0 (x 0), если 0
x 1;
(1)
1, если x 1.
Легко видеть, что F0 является стратегией (т. е. функцией распреде-
ления.). Функции F0 и F0 отличаются только в точках разрывов. Но так
как эти функции монотонны, точки их разрывов образуют счѐтное множе-
ство и поэтому для любого y
1
0
A( x, y)d F0 ( x)
1
0
A( x, y)dF0 ( x) .
Функция A(x, y) непрерывна и, следовательно, равномерно непре-
рывна. Ввиду того, что F0 является пределом подпоследовательности из
Fn , мы имеем
1
0
A( x, y)dF0 ( x)
1
lim A( x, y)dFn ( x) .
n
0
Но последний предел не меньше v1 для каждого значения y . Таким обра-
зом:
min E(F0 , y)
y
v1
44
F
F
и на F0 достигается требуемый максимум.
Аналогично можно показать, что inf sup можно заменить на
min max .
Теорема 2. Если ядро A(x, y) непрерывно, то v1 = v2 .
Доказательство. Для любого целого числа n рассмотрим матрицу
An
{aijn} размерности (n 1) (n 1) , где aijn
A(
ni
,
nj
) ;
i,
j
0, n.
Игра с матрицей выигрыша An имеет значение wn и оптимальные
стратегии rn
(r0n ,..., rnn ) и sn
(s0n ,..., snn ) игроков 1 и 2 соответственно.
Функция A(x, y) непрерывна. Так как квадрат компактен, то A(x, y)
равномерно непрерывна. Таким образом, для заданного
0 можно найти
такое
0 , что если
( x x ) 2
( y
y ) 2
,
то
A( x, y) A( x , y )
Возьмѐм n столь большим, чтобы 1n
равенством
[ nx]
.
. Определим стратегию Fn ( x)
Fn ( x)
где [ nx ] – целая часть числа nx .
i 0
ri n ,
Для любого y положим j
[ny]. Ясно, что
n
и так как
j
n n
i 0
aijnrin
wn ,
y
j
n
,
имеем
A( x, y)
A( x, nj )
1
1
1
0
A( x, y)dFn ( x)
0
j
n
0
dFn ( x)
,
то есть
E(Fn , y) E(Fn , nj )
Следовательно, для любого y
.
E(Fn , y)
wn
и поэтому v1 wn
.
Аналогично можно показать, что v 2 wn
.
45
E(F , )
A( x, )dFn ( x)
Из 2-х последних неравенств получаем, что v1 v 2
2 . Но из того,
что v1 v 2 и произвольности , следует, что v1 v 2 .
Из доказательств этой теоремы следует, что, во-первых,
V
lim wn .
n
И, во-вторых, что стратегии Fn аппроксимируют оптимальную стра-
тегию сколь угодно точно. В этом смысле матричные игры аппроксими-
руют непрерывную игру A(x, y) . Если ядро очень гладкое, то может ока-
заться, что уже при очень небольшом n аппроксимация будет достаточно
хорошей.
С другой стороны, если ядро слишком нерегулярно, то для хорошей
аппроксимации требуются большие значения n.
