- •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.14. Игры с выбором момента времени
Как показано ранее, непрерывные игры всегда имеют оптимальные
стратегии. Но общих аналитических методов их вычисления нет.
Если игра с разрывным ядром, то мы не можем быть уверены, что
она имеет оптимальные стратегии. Но в некоторых случаях именно раз-
рывность позволяет находить оптимальные стратегии (если они существу-
ют) аналитическими методами.
Рассмотрим один тип игр на квадрате, называемый играми с выбором
момента времени. Прототипом такой игры является игра, в которой каж-
дый игрок может сделать только одно действие в течение данного интер-
вала времени. Порядок, в котором игроки действуют, чрезвычайно важен.
Этот факт является причиной разрыва ядра вдоль диагонали x
та.
Рассмотрим игру с ядром A(x, y) вида
y квадра-
K ( x, y),
x
y,
A(x, y)
( x),
L( x, y),
x
x
y,
y,
(1)
где функция K (x, y) определена и непрерывна на множестве 0
x
y 1,
а функция L(x, y) на множестве 0
y
x 1, а функция (x) непрерывна
на [0, 1].
Нельзя быть уверенным, что оптимальные стратегии в этой игре су-
ществуют. Тем не менее, мы можем определить некоторые свойства опти-
мальных стратегий в предположении, что они существуют.
Пусть F – смешанная стратегия игрока 1. Для y
[0,1] мы имеем
y
1
E(F , y)
K (x, y)dF (x)
( y)[F ( y) F ( y 0)]
L(x, y)dF (x) .
(2)
0
y
48
Если F – непрерывная функция, то можем опустить среднее выра-
жение и получим
y
1
E(F , y)
0
K (x, y)dF (x)
y
L(x, y)dF (x) .
(3)
Предположим, что F и G – оптимальные стратегии игроков 1 и 2 и
что обе они являются непрерывными функциями распределения.
Известно, что если F и G оптимальны, а y0 − точка (чистая страте-
гия против смешанной F ), в которой
то
G ( y0 )
E(F , y0 )
0 ,
v ,
(4)
(5)
где v − значение игры.
Теперь, если G положительна в точке y0 , то она положительна и в
некоторой окрестности y0 . Поэтому для любого y , достаточно близкого к
y0 , мы будем иметь E(F , y)
Но это значит, что
v .
E(F , y)
y
На основании правила Лейбница
V ( )
V ( )
0 .
(6)
d
d
f (x, )dx
d
f (x, )dx
d
d
U ( )
U ( )
уравнение (6) можно переписать в виде
y
1
[L( y, y) K ( y, y)]F ( y)
0
K y (x, y)F (x)dx
y
Ly (x, y)F (x)dx .
(7)
Выражение (7) представляет собой интегральное уравнение относительно
F , которое иногда довольно легко решать.
Предположим теперь, что нам дана игра с ядром вида (1). Мы не мо-
жем гарантировать существование оптимальных стратегий. Мы даже не
знаем, будут ли они непрерывными, дискретными или частично непрерыв-
ными и частично дискретными распределениями. Однако довольно естест-
венно считать, что оптимальные стратегии F и G являются непрерывны-
ми распределениями, а их производные F и G положительны на интер-
валах
(a, b) и (c, d) соответственно и равны нулю вне этих интервалов.
Теперь имеем несколько соотношений, связывающих функции F и G и
числа a, b, c, d и v :
E(F , y)
E(F , y)
E(x, G)
v для y (c, d ) ;
v для любого с;
v для x (a, b) ;
(8)
(9)
(10)
E(x, G) v для любого x ;
(11)
49
f (V ( ), ) dV
f (U ( ), ) dU
y
1
[L( y, y) K ( y, y)]F ( y)
для y
(c, d ) ;
[K ( x, x) L( x, x)]G ( x)
для x
(a, b) .
x
0
K y (x, y)F (x)dx
0
K x ( x, y)G ( y)dy
1
x
Ly (x, y)F (x)dx , (12)
y
Lx ( x, y)G ( y)dy , (13)
Здесь 0
a
b
1, 0
c
d
1 и, кроме того, F и G должны быть
стратегиями. Если вся система имеет решение, то это решение даст нам
оптимальные стратегии, а также значение игры. Если решения нет, то игра
либо не имеет оптимальных стратегий, либо, если она их имеет, то они не
такого типа, как предполагалось выше (непрерывные).
Иногда ядро кососимметрично, т.е.
L(x, y)
(x)
K ( y, x) ,
0 .
(14)
(15)
Если это так, то значение игры, если оно существует, должно рав-
няться нулю, а оптимальные стратегии, если они существуют, должны
быть одинаковы для обоих игроков. Таким образом, будем иметь:
F G , a c , b d , v
и соотношения (8 – 13) примут вид
0 ,
E(F , y) 0 для y (a, b) ;
E(F , y) 0 для любого y ;
(16)
(17)
y
b
[L( y, y) K ( y, y)]F ( y)
для y
(a, b) .
a
K y (x, y)F (x)dx
y
Ly (x, y)F (x)dx , (18)
Эта система вместе с обычными ограничениями даст решение игры,
если такое решение существует.
Пример 2.9. Рассмотрим следующую дуэль. Два дуэлянта (игрока) в мо-
мент t
0 начинают идти навстречу друг другу. Они встретятся (если
ничто не помешает) в момент t 1. Каждый имеет пистолет только с од-
ной пулей и может выстрелить в любой момент, когда пожелает. Если ему
удалось поразить противника, а сам он невредим, то дуэль немедленно
прекращается, и тот, кто выстрелил успешно, является победителем. Если
оба дуэлянта промахнулись, то дуэль оканчивается вничью. Если оба стре-
ляли одновременно, и каждый поразил другого, то дуэль также считается
окончившейся вничью.
Сделаем два предположения. 1) Меткость выстрела при сближении
игроков возрастает таким образом, что если какой-либо игрок выстрелил в
момент t, то вероятность поражения противника равна t. 2) Дуэль является
бесшумной, т.е. игрок не знает, что его противник выстрелил (если конеч-
но тот промахнулся).
50
Найдем ядро этой игры. Если игрок 1 выбирает момент x , а игрок 2
– момент y
x , то игрок 1 с вероятностью x попадет в противника (в этом
случае его выигрыш равен +1). Если он промахнулся (с вероятностью 1 x
), то он будет поражен с вероятностью y (получит выигрыш –1).
Таким образом, мы имеем
K (x, y)
x 1 (1 x) y ( 1)
x
y
xy .
(19)
Очевидно, что эта игра симметрична, поэтому
L(x, y)
( y x
yx)
x
y
xy
(20)
и
Далее, мы имеем также
(x)
K y (x, y)
0 .
1 x , (21)
и
Ly (x, y)
1 x
(22)
L( y, y) K ( y, y)
2 y 2
(23)
Предположим теперь, что оптимальная стратегия является непре-
рывной функцией распределения F с положительной производной в ин-
тервале (a, b) . Тогда по формуле (18)
y
b
2
a
( 1 x)F (x)dx
y
( 1 x)F (x)dx .
(24)
Это интегральное уравнение (относительно F ) может быть преоб-
разовано в дифференциальное уравнение дифференцированием обоих час-
тей, что даст:
4 yF
2 y 2 F
( y 1)F
( y 1)F
2 yF ,
или, упростив,
yF
Решение этого уравнения имеет вид
F ( y)
3F . (25)
ky 3 . (26)
Теперь нужно найти a, b и k. Предположим, что b < 1. Мы знаем, что
для всех y
(a, b)
E(F , y)
0 .
Но функция E(F , y) непрерывна по y , откуда следует, что
Следовательно,
E(F , b)
0 .
b
b
E(F , b)
a
K ( x, b)dF ( x)
a
( x b bx)dF ( x)
0 .
Но если b <1, то
51
2 y F ( y)
b
( x 1 x)dF ( x) 0 ,
a
и поэтому E(F,1)
0 , что противоречит условию (17). Таким образом
b 1.
(27)
Так как b 1, то E(F,1)
0 . Ввиду этого
1
k (2x 1) x 3dx 0 ,
a
1
k (2x
a
2
x 3 )dx k ( 2x
1
1
2
x 2 ) 1a
k (
3
2
2
a
1
2a 2
)
k
2a
2
( 3a 2
4a 1) .
Откуда следует
3a 2
4a 1 0 .
Это уравнение имеет два решения: a 1 и a
a 1 невозможно, следовательно,
1
3
. Ясно, что значение
Так как F – стратегия, то
a
1
3
.
(28)
1
1
3
F (x)dx
1
1
3
kx 3dx 1,
поэтому
1
k .
4
Это дает нам оптимальную стратегию для каждого из двух игроков.
Она является непрерывной функцией распределения, определенной сле-
дующим образом из
F ( x)
1
,
3
1 1
4 3
,
что даст оптимальную стратегию 2-х игроков в виде:
0,
если
x
1
3
.
F (x)
1 9
4 2
1
2x 2
, если x
1
3
.
52
0, если x
x 3 , если x
