ЭКОНОМЕТРИКА и математическая экономика / Васин А.А., Морозов В.В. Введение в теорию игр с приложениями к экономике. 2003

7. Исследование игровых моделей

Заметим, что v > 0 . Поэтому v > max[A − µnB, 0] = v.

в) Покажем, что в игре существует решение в смешанных стратегиях вида (ϕ0, y0, v), ãäå y0 − чистая минимаксная стратегия обороны, а

оптимальная смешанная стратегия для нападения имеет вид

n	n	µk	−	, i = 1, ..., n.
ϕ0 = i=1	pi0Ix(i) , pi0 = µi k=1
X	X	1		1

Поскольку функция F (x, y) выпукла по y, достаточно проверить условие ( ) для смешанной стратегии ϕ0 :

F (ϕ0, y) ≥

y Y.

v

Имеем

n

F (ϕ0, y) = Z

F (x, y)dϕ0(x) = i=1 pi0F (x(i), y) =

X

X

n

n

X

Xi

=

pi0 max[A − µiyi, 0] =

max[pi0A − µipi0yi, 0] ≥

i=1

=1

n

n

n

1

≥ max[ i=1

(pi0A − µipi0yi), 0] = max[A − i=1 yi

k=1

−

1

µk

, 0] =

X

n

X

X

1

= max[A − B k=1

µk −

, 0] = v.

X

Здесь мы воспользовались элементарным неравенством

n

n

n

X

Xi

X

max[ai, bi] ≥ max[

ai,

bi],

i=1

=1

i=1

справедливом для любых вещественных чисел ai, bi, i = 1, ..., n.

Модель дуэли.

Âдуэли принимают участие два дуэлянта ( первый и второй игроки).

Âначальный момент времени дуэлянты находятся на расстоянии d0 è

по команде начинают сближаться. В распоряжении каждого дуэлянта имеется один выстрел, который он может произвести в противника с любого расстояния (конечно, при условии, что дуэлянт жив), он даже может подойти к противнику вплотную.

71

p1(d) =

ГЛАВА I. АНТАГОНИСТИЧЕСКИЕ ИГРЫ

Пусть pk(d) − функция меткости k-ãî дуэлянта, равная вероятности поражения противника, если выстрел был произведен с расстояния d. Предположим, что функции pk(d) непрерывны и убывают на отрезке [0, d0] и без потери общности pk(0) = 1, pk(d0) = 0, k = 1, 2.

Определим антагонистическую игру. Пусть x X = [0, d0] − расстояние, с которого первый игрок намечает произвести свой выстрел. Аналогично, y Y = [0, d0] − расстояние, с которого намечает свой выстрел

второй игрок. Определим функцию выигрыша F (x, y) первого игрока.

Рассмотрим сначала шумную дуэль, когда противники слышат выстрелы друг друга. Тогда

(1 p2	(y), 0	≤ x < y d0.
F (x, y) = p1(x),	0	≤	y ≤ x ≤ d0	,
−			≤

По смыслу F (x, y) есть вероятность поражения первым игроком второго. Если x < y и второй игрок промахнется, то первый, услышав выстрел противника, стреляет в него с расстояния 0 вместо x. Отметим, что F (x, y) является осреднением функции, принимающей значение 1 или 0

âзависимости от того, убит второй дуэлянт или нет. Итак, шумная дуэль

.

определена как игра в нормальной форме = X, Y, F (x, y)

Покажем, что шумная дуэль имеет решение в чистых стратегиях (d , d , v = p1(d )), ãäå d − единственный корень уравнения

1 − p2(d). Проверим неравенства из определения седловой точки

F (x, d ) ≤ p1(d ) = F (d , d ) ≤ F (d , y) x X, y Y.

Имеем			(1 p2(d ) = p1(d ), 0 x < d ,
F (x, d ) = p1					(x)		≤ p1(d ),	d ≤ x ≤ d0		,
				−				≤
(1 p2(y) 1 p2(d ) = p1								(d ), d < y d0.
F (d , y) = p1		(d ),				≥	−		0 ≤ y	≤ d ,
	−										≤

Если функции меткости игроков одинаковы, то из уравнения

p1(d) = 1 − p1(d) находим, что значение игры равно 1/2, а d является

корнем уравнения p1(d) = 1/2.

 бесшумной дуэли игроки не слышат выстрелы друг друга и

(p1	(x)(1		p2	(y)), 0	≤ x < y		d0.
F (x, y) = p1	(x),	−		0	y ≤ x ≤ d0			,
					≤	≤

72

7. Исследование игровых моделей

Покажем, что бесшумная дуэль не имеет решения в чистых стратегиях.

Найдем величину v = sup inf F (x, y). Стратегия x = d0 не может

0≤x≤d0 0≤y≤d0

быть максиминной, поскольку F (d0, y) = p1(d0) = 0 ïðè âñåõ y Y. Пусть 0 ≤ x < d0. Тогда

inf	F (x, y) = min[ inf F (x, y),	inf F (x, y)] =
0≤y≤d0	0≤y≤x	x<y≤d0

= min[p1(x), p1(x)(1 − p2(x))] = p1(x)(1 − p2(x)).

Отсюда v = max p1(x)(1 − p2(x)).

0≤x≤d0

Упражнение 7.1. Докажите, что

v = inf sup F (x, y) = p1(d ).

0≤y≤d0 0≤x≤d0

Таким образом, v = max p1(x)(1 − p2(x)) <

0≤x≤d0

< max min[p1(x), 1 − p2(x)] = p1(d ) = v.

0≤x≤d0

Решение бесшумных дуэлей обычно сводится к интегрированию обыкновенных дифференциальных уравнений. Мы ограничимся исследованием конкретного примера.

Пример 7.1. Рассмотрим бесшумную дуэль с одинаковыми функциями меткости игроков p1(d) = p2(d) = 1 − d, 0 ≤ d ≤ d0 = 1. Тогда

(

1 − x, 0 ≤ y ≤ x ≤ 1,

F (x, y) =

(1 − x)y, 0 ≤ x < y ≤ 1.

Предположим, что оптимальные смешанные стратегии игроков ϕ0(x) è ψ0(y) имеют совпадающие спектры Sp(ϕ0) = Sp(ψ0) = [0, a], ãäå a ≤ 1 − параметр, подлежащий определению. Пусть на отрезке [0, a] функции

распределения ϕ0(x) è ψ0(y) непрерывны и имеют производные (плотности распределения) f(x) è g(y).

По свойству дополняющей нежесткости (теорема 4.3)

F (ϕ0, y) = v y [0, a] èëè

a	y	a
Z0	F (x, y)f(x)dx = Z0	(1 − x)yf(x)dx + Zy	(1 − x)f(x)dx = v.	(7.2)

73

ГЛАВА I. АНТАГОНИСТИЧЕСКИЕ ИГРЫ

Дифференцируя дважды по y интегральное уравнение (7.2), получим дифференциальное уравнение 3f(y) = (1 − y)f0(y), имеющее (после за-

ìåíû y íà x ) общее решение вида f(x) = c(1

−

x)−3. По определению

1

(

)

a

плотности R0

f

x

dx = 1

(условие нормировки). Отсюда

c

1

dx =

"

1

− 1# = 1.

(7.3)

(1

x)3

2

(1

a)2

Z0

−

−

c

Найденная плотность f(x) должна также удовлетворять исходному интегральному уравнению (7.2), т.е.

"	1		#
c	1 − a		− 1 − y = v.	(7.4)
Поскольку уравнение (7.4) не является тождеством по				y, смешанная

стратегия ϕ0(x) указанного вида не существует. Поэтому предположим, что функция распределения ϕ0(x) имеет скачок величины σ в нуле. Тогда уравнения (7.2)−(7.4) изменятся:

y	a
σy + Z0	(1 − x)yf(x)dx + Zy	(1 − x)f(x)dx = v,	(7.2)0

"#

c1

σ + 2 (1 − a)2 − 1 = 1,

"	1	#
σy + c	1 − a	− 1 − y = v.

(7.3)0

(7.4)0

Для того чтобы уравнение (7.4)0 выполнялось как тождество, необходимо положить σ = c. Из уравнений (7.3)0, (7.4)0 получаем

"#

c		1	+ 1 = 1,	ca		= v.	(7.5)
2		(1 − a)2		1 − a

Из свойства дополняющей нежесткости также следует, что

F (x, ψ0) = v x [0, a] èëè

a	x	a
Z0	F (x, y)g(y)dy = Z0	(1 − x)g(y)dy + Zx	(1 − x)yg(y)dy = v.	(7.6)

74

8. Многошаговые антагонистические игры

Отсюда, как и выше, получим g(y) = c1(1 − y)−3. Подставляя g(y) в уравнение (7.6), находим

c1

(1 − x)" x

1

dy +

a

y

dy#

= v

(1

y)3

(1

y)3

Z0

−

Zx

−

1

a

или, используя условие нормировки R0

g(y)dy = c1

R0

(1 − y)−3dy = 1,

(1 − x)"1 −

c1

+

c1

# = v.

1 a

1 x

−

−

Для того чтобы последнее равенство выполнялось тождественно, необходимо, чтобы c1 = v = 1 − a. Отсюда и из (7.5) находим

√

a = 2 − √2, c1 = v = √2 − 1, c = σ = 2 − 2. 2

Окончательно

ϕ0(x) =

2 −4√2

(x

1 1)2 + 1!, 0 ≤ x ≤ 2 − √2,

−

√2 < x

1,

1,

2

−

≤

√22− 1

1 1)2 − 1!, 0 ≤ y ≤ 2 − √2,

ψ0(y) =

(y

−

1,

−

√

< y

2

2

1.

0 состоит в том, что

≤

Особенность

ϕ

оптимальной смешанноé стратегии

√

первый игрок с вероятностью σ = 2− 2

√

бесшумной

противником. Отметим также, что значение игры

2 ждет до полноãо сближения с

v = 2 − 1

дуэли меньше значения игры v = 1/2 шумной дуэли, что объясняется уменьшением информированности первого игрока.

8. Многошаговые антагонистические игры

Определим многошаговую антагонистическую игру с полной информацией. Игра происходит в течение T шагов с номерами t = 1, ..., T. Íà

75

ГЛАВА I. АНТАГОНИСТИЧЕСКИЕ ИГРЫ

каждом шаге t игроки выбирают по очереди альтернативы − значения

переменных xt, yt.

Øàã 1. Сначала первый игрок выбирает альтернативу x1 U1, затем второй игрок, зная выбор первого, выбирает альтернативу y1 V1(x1) =

V1(·).

Пусть игроки в течение t − 1 шагов выбрали альтернативы

x1, ..., xt−1, y1, ..., yt−1. Положим xt = (x1, ..., xt), yt = (y1, ..., yt).

Øàã t. Сначала первый игрок, зная предысторию xt−1, yt−1, выбирает альтернативу xt Ut(xt−1, yt−1) = Ut(·). Затем второй игрок выбирает альтернативу yt Vt(xt, yt−1) = Vt(·), зная предысторию xt, yt−1, включая выбор xt первого игрока на данном шаге.

После завершения шага T возникает пара (xT , yT ), называемая партией игры. По смыслу партия игры − это запись всех альтернатив, вы-

бранных игроками. Для любой партии (xT , yT ) задается выигрыш F (xT , yT ) первого игрока.

Определим теперь игру в нормальной форме. На шаге t первый игрок может выбрать альтернативу xt как значение функции x˜t : xt = x˜t(xt−1, yt−1), которая должна быть определена при всевозможных зна- чениях аргументов xt−1, yt−1. Обозначим множество всех таких функций

˜

x˜t через Ut. Заметим, что x˜1 = x1, поскольку на первом шаге первый

игрок никакой информацией не располагает.

Стратегия первого игрока представляет собой набор функций

	T
˜	Yt
	˜
x˜ = (˜xt, t = 1, ..., T ) X =	Ut.
	=1

Аналогично, на шаге t второй игрок может выбирать альтернативу yt êàê значение функции y˜t : yt = y˜t(xt, yt−1), которая должна быть определена при всевозможных значениях аргументов xt, yt−1. Обозначим множество

˜

всех таких функций y˜t через Vt. Стратегия второго игрока представляет собой набор функций

	T
˜	Yt
	˜
y˜ = (˜yt, t = 1, ..., T ) Y =	Vt.
	=1

Игроки могут выбрать стратегии x,˜ y˜ независимо друг от друга до игры, а во время игры − применять их "автоматически."Любой паре стратегий (˜x, y˜) однозначно соответствует партия игры:

76

8. Многошаговые антагонистические игры

x1 = x˜1, y1 = y˜1(x1), x2 = x˜2(x1, y1) è ò.ä.

def

Далее F (˜x, y˜) = F (xT , yT ), ãäå (xT , yT ) − партия, соответствующая стратегиям x˜ è y˜. Итак, многошаговая игра с полной информацией опре-

˜ ˜

делена в нормальной форме = X, Y , F (˜x, y˜) .

В дальнейшем будем рассматривать два класса игр: игра 0, в которой все множества Ut(·), Vt(·) конечны;

èãðà 00, в которой все множества Ut(·) ≡ Ut, Vt(·) ≡ Vt не зависят от предысторèи и являются компактами метрических пространств, а функция F (xT , yT ) непрерывна на произведении

U1 × · · · × UT × V1 × · · · × VT .

Определим пару стратегий

x˜0 = (˜x0t , t = 1, ..., T ), y˜0 = (˜yt0, 1, ..., T ),

используя метод динамического программиðования. Äîîïðеделим функ-

öèþ F на всех отрезках партии вида (xt, yt−1) èëè (xt, yt) и назовем

åå функцией Беллмана. Компоненты стратегий x˜0t , y˜t0 будем задавать в порядке, обратном выборам игроков.

Определим сначала y˜T0 . Для этого зафиксируем произвольное значе- ние аргументов (xT , yT −1) и зададим значение функции

def

y˜T0 (xT , yT −1) = yT0 :

, y0 ) =

def

F (

x

T ,

y

T −1

min

F (

x

T ,

y

T −1

, yT ) = F (

x

T ,

y

T −1

).

T

yT VT (·)

Определим функцию x˜T0

. Зафиксируем произвольное значение аргумен-

òîâ (

T −1,

T −1) и зададим значение функции

x

y

def

x˜T0 (

T −1,

T −1) = xT0 :

x

y

, x0 ,

def

F (

x

T −1

y

T −1

) = max F (

x

T −1

, x

T

,

y

T −1

) = F (

x

T −1

,

y

T −1

).

T

xT UT (·)

Пусть определены компоненты стратегий и значения функции Беллмана

y˜T0 , x˜0T , ..., y˜t0+1, x˜0t+1, F (xT , yT −1), ..., F (xt, yt).

Тогда y˜t0, x˜0t , F (xt, yt−1), F (xt−1, yt−1) задаются по приведенным выше формулам с заменой T íà t.

Покажем, что стратегии x˜0, y˜0 определены корректно для игр 0 è 00. Действительно, в игре 0 все множества Ut(·), Vt(·) конечны и поэтому

77

ГЛАВА I. АНТАГОНИСТИЧЕСКИЕ ИГРЫ

максимумы и минимумы, фигурирующие в определениях x˜0, y˜0, достига- ются. Аналогичное утверждение справедливо и для игры 00, поскольку

по теореме 2.2 функция Беллмана непрерывна на соответствующих компактах.

Определим величину

def F (x1)			min	F (x1, y1) = ...
v˜ = max F (x1)	=	max
x1 U1		x1 U1 y1 V1(·)
= max min ...		max	min	F (		T ,		T ).
					x		y
x1 U1 y1 V1(·)		xT UT (·) yT VT (·)

Справедлива следующая

Теорема 8.1 (Цермело). Всякая многошаговая антагонистическая игра с полной информацией 0 (èëè 00) имеет решение (˜x0, y˜0, v˜).

Доказательство. Докажем, что функция F (˜x, y˜) имеет седловую точ-

0

0

˜

˜

êó (˜x

, y˜ )0íà X

× Y . Для этого достаточно доказать, что

1) F (˜x , y˜)

≥

v˜

y˜

˜

Y ;

0

˜

2) F (˜x, y˜ )

≤ v˜ x˜ X.

Докажем неравенство 1). Имеем

F (˜x0, y˜)

min F (˜x0, y˜ , ..., y˜

−1

, y

T

) = F (˜x0, y˜ , ..., y˜

) =

≥ yT

VT

(

)

1

T

1

T −1

·

def x˜0

max

F (˜x0

, ..., x˜0

, x

, y˜ , ..., y˜

) =

= T

xT UT (·)

1

T −1

T

1

T −1

= F (˜x0, ..., x˜0

, y˜ , ..., y˜

)

≥

...

≥

F (˜x0

, y˜ )

max F (x

) = v˜.

1

T −1

1

T −1

1

1

≥ x1

U1

1

Неравенство 2) доказывается аналогично.

Пример 8.1. Покажем, что игра "шахматы"имеет решение. Существует такое целое число T, что в соответствии с правилами игры любая

шахматная партия заканчивается не позднее хода T. Поэтому без потери общности можно считать, все партии продолжаются T ходов1. Шахматы являются игрой вида 0. Ut(xt−1, yt−1) есть множество разрешенных правилами альтернативных выборов хода белыми (первым игроком) на t-м ходу в позиции, определяемой предыдущими ходами игроков (xt−1, yt−1).

1Если партия заканчивается раньше, то игроки делают необходимое число фиктивных ходов, не влияющих на исход игры.

78

8. Многошаговые антагонистические игры

Аналогично интерпретируется множество Vt(xt, yt−1) выборов хода черными на t-м ходу. Выигрыш белых определяется по правилу

				1,	если выиграли белые,
F (	x	T ,	y	T ) = 0,	если выиграли черные,
				1/2,	если сыграли вничью.

По теореме Цермело игра "шахматы"имеет решение. Практическое значение этот результат имеет для позиций эндшпиля, где обычно ищут форсированный выигрыш, либо ничью.

Пример 8.2. Рассмотрим матрицу

A =	2		7	2	0 .
		5	3	1	4
	4		0	2	5
		3	2	3

Разобьем множество ее строк на подмножества M1 = {1, 2} è M2 = {3, 4}, а множество столбцов − на подмножества N1 = {1, 2} è N2 = {3, 4}. Определим двухшаговую игру с полной информацией.

Øàã 1. Сначала первый игрок выбирает номер α {1, 2} множества

Mα, из которого он будет на втором шаге делать выбор строки матрицы

A. Затем второй игрок, зная α, выбирает номер β {1, 2} множества Nβ, из которого он будет на втором шаге выбирать номер столбца матрицы

A.

Шаг 2. Первый игрок выбирает номер строки i Mα, зная α, β, затем второй игрок выбирает номер столбца j Nβ, çíàÿ α, β, i.

Выигрыш первого игрока равен aij.

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

79

ГЛАВА I. АНТАГОНИСТИЧЕСКИЕ ИГРЫ

P

1

1 2k PPP2PP

P

@

2

@

1 k@ 2

k

k

1 k @ 2

3

@

@

@

1

2

3

Bk

Bk

1

0

2

0

Bk

J

Bk

1

J

k2

J

J

3 k4

J

J

1 J2

Bk

3 J4

Bk

3

2

J

J

3

2

B

B

Bk

Bk

B

B

1 B 2 1 B 2

B

B

B

B

3 B 4 3 B4

B

B 3 B4

3 B 4 1 B2

1 B2

B

B

5

3 2

7

B

B

B

B

3 3 2 5

1

4

2

0 3

2

4

0

Ðèñ. 8.1

Начальная (корневая) вершина дерева 1

соответствует первому хо-

ду первого игрока (выбор альтернативы

α), в вершинах второго уров-

ня альтернативу β выбирает второй игрок и т.д. В финальных вершинах, отвечающих различным партиям игры, указаны выигрыши пер- вого игрока F (α, β, i, j) = aij. В вершинах четвертого уровня указаны

значения функции Беллмана F (α, β, i) = min F (α, β, i, j), в вершинах

j Nβ

третьего уровня − F (α, β) = max F (α, β, i), в вершинах второго уров-

	−						i Mα	−
íÿ		F	(	α	)	=	min F (α, β), а в начальной вершине		значение игры
							β=1,2

v˜ = max F (α) = 2.

α=1,2

Укажем оптимальные стратегии игроков

x˜

0

0

˜0

0

˜0

˜0

(α, β, i)) :

= (α

, i

(α, β)), y˜ = (β

(α), j

α

0

= 2,

˜0

(2, 1) = 3,

˜0

(2, 2) = 3,

˜0

(1) = 2,

˜0

(2) = 1,

i

i

β

β

˜0

˜0

˜0

˜0

(2, 1, 4) = 2.

j

(1, 2, 1) = 3, , j

(1, 2, 2) = 4, j

(2, 1, 3) = j

Отметим, что сначала мы подсчитали функцию Беллмана, а затем построили в естественном порядке компоненты оптимальных стратегий. В результате была достигнута некоторая экономия вычислений, поскольку эти компоненты необязательно следует определять при всех значениях

1Дерево изображено в перевернутом виде, поскольку так его удобнее рисовать.

80