1danilovtseva_e_r_farafonov_i_g_d_yakova_g_n_teoriya_igr_osno

Справедливы три свойства стратегической эквивалентности – рефлексивность, симметрия и транзитивность.

1. Рефлексивность. Каждая игра Г стратегически эквивалентна самой себе: Г ~ Г .

Д о к а з а т е л ь с т в о. Положим k = 1 и Ci = 0, для всех i в любой ситуации s имеем Hi (s) = 1 Hi (s)+ 0, что и требовалось доказать.

2. Симметрия. Если Г~ Г′ , то Г′~ Г.

Д о к а з а т е л ь с т в о. Пусть Г~ Г′ , тогда эти игры имеют одни и те же множества игроков и их стратегий, а функции выигрыша связаны следующим образом:

Hi (s) = k Hi′(s) + ci , k > 0, ci R
H ′(s) = 1/ k H		(s) − c / k,				1	> 0, c / k R
i	i		i			k		i
Г′~ Г,
что и требовалось доказать.
3. Транзитивность. Если	Г ~ Г ′		и	Г′~ Г′′, то Г~ Г′′.
Д о к а з а т е л ь с т в о. Пусть			Г ~		Г ′ и Г′~ Г′′ , тогда Г, Г′, Г′′

имеют одни и те же множества игроков и их стратегий, а функции выигрыша связаны следующим образом:

Hi (s) =	k Hi′(s) + ci ,
Hi′(s) =	p Hi′′(s) + bi , k > 0, p > 0, ci R, bi R.

Тогда Hi и Hi′′	связаны соотношением
Hi (s) =	kpHi′′(s) + (kbi + ci ), kp > 0, (kbi + ci ) R,

что по определению 6 означает эквивалентность Г~ Г′′.

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

Различие между двумя стратегически эквивалентными играми по сути состоит лишь в различии начальных капиталов игроков ci и единиц измерения выигрышей, определяемых коэффициентом k.

11

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

Теорема 1. Стратегически эквивалентные игры имеют одни и те же ситуации равновесия.

Д о к а з а т е л ь с т в о. Пусть Г~ Г′, а s* – ситуация равновесия в игре Г. Докажем, что s* – ситуация равновесия в игре Г′ . Из определения ситуации равновесия s* в игре Г следует, что для всех i I и si Si верно следующее:

Hi (s *

si ) ≤ Hi (s*).

(6.1)

А стратегическая эквивалентность Г и Г′ означает

Hi (s*) = kHi′(s*) + ci ,

(6.2)

Hi (s *

si ) = kHi′(s *

si ) + ci ;

(6.3)

из (6.1), (6.2), (6.3) получаем

kH	′	(s*		s ) + c ≤ kH		i	′(s*) + c ,
	i			i	i		i
откуда (с учетом k > 0) получаем

Hi′(s * si ) ≤ Hi′(s*) i I и si Si , что и означает равновесность стратегии s* в игре Г′.

Определение 7. Бескоалиционная игра Г = < I, {Si }i I , {Hi }i I > такая, что в любой ситуации s S суммарный выигрыш игроков равен нулю, называется игрой с нулевой суммой.

Теорема 2. Всякая бескоалиционная игра с постоянной суммой стратегически эквивалентна некоторой игре с нулевой суммой.

Доказательство. Пусть Г = {I, {Si}i I , {Hi}i I } –играспостоянной

суммой, т. е. для всех ситуаций s S верно ∑Hi (s)				= c,	c = const.
		iI	∑ci
Выберем произвольные ci (i I ), , для которых				= c, и рассмот-
			i I
рим	игру	Г′ = {I,{Si}i I , {Hi′}i I } с функциями			выигрышей
Нi′(s) = Hi (s) − ci . Видно, что, с одной стороны,			Г и Г′		эквивалент-
ны, а, с другой стороны, Г′ – является игрой с нулевой суммой, так как
∑Hi′(s) = ∑Hi (s) − ∑ci = c − c = 0 s S.
iI	iI	iI

12

7. Антагонистические игры

Антагонистическая игра является частным случаем бескоалиционной игры.

Определение 8. Игра Г = < I,{Si}i I ,{Hi}i I > называется антагонистической, если число игроков в ней равно двум, а значения функций выигрыша этих игроков в каждой ситуации равны по величине и

противоположны по знаку, т. е. H1(s) = −H2 (s), s S.

(7.1)

Из определения следует, что в любой ситуации антагонистической игры H1(s) + H2 (s) = 0 . Иначе говоря, антагонистическая игра – это игра двух лиц с нулевой суммой.

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

Поэтому под антагонистической игрой обычно понимают тройку: Г = < A, B, H >, где А и В – множества стратегий игроков 1 и 2, а Н –

функция выигрыша игрока 1, заданная на S = {(a, b): a A, b B}. Из теоремы 2 следует, что бескоалиционная игра двух лиц с постоянной

суммой стратегически эквивалентна некоторой антагонистической игре.

8. Седловые точки

Пусть Г = < A, B, H > – антагонистическая игра. Для ситуации равновесия (a, b) должно быть верно

	H1(a,	b) ≥ H1(a′,	b), a′ A;	(8.1)
	H2 (a,	b) ≥ H2 (a,	b′), b′ B.	(8.2)
Учитывая, что H2 (a,	b) = −H1(a, b), запишем выражение (8.2) как
−H1(a, b) ≥ −H1(a, b′),	b′ B	или H1(a, b) ≤ H1(a, b′), b′ B.

Вместе с (8.1) запишем это в виде двойного неравенства (переходя от обозначения H1 к обозначению Н для функции выигрыша 1-го игрока)

H (a′, b) ≤ H (a, b) ≤ H (a, b′), a′ A, b′ B.

Это неравенство выражает следующее свойство функции Н в точке (a, b): при любом изменении переменной a значение Н может только уменьшиться, а при изменении значения переменной b – только увеличиться, т. е. по переменной a функция Н невозрастающая, а по переменной b – неубывающая. Таким образом, на поверхности, описывае-

13

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

Замечание. Следует иметь в виду, что понятие седловой точки в теории игр отличается от аналогичного понятия в геометрии.

Первое отличие состоит в том, что в теории игр для седлообразной точки необходимо, чтобы в ней достигался максимум именно по первой переменной, а минимум – по второй. В геометрии же от порядка переменных седлообразность точки не зависит.

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

9. Отступление в теорию функций

Определение 9. Пусть f – функция, заданная на множестве D. Ее супремумом на этом множестве называется наименьшее из всех чисел p таких, что f (x) ≤ p при любом x D.

Обозначение супремума: sup f (x) или sup f (x), если есть ясность

x D

относительно области задания f(x).

Определение 10. Инфимумом функции f на D называется наибольшее из чисел p таких, что p ≤ f (x), x D.

Обозначение: inf f (x) или inf f (x).

x D

Определение 11. Если супремум функции f на D достигается, т. е. если существует x D, такое что f (x) = sup f (x), то он называется максимумом.

Обозначение: max f (x).

Определение 12. Если инфимум функции f на D достигается, т. е. если существует x D такое что f (x*) = inf f (x), то он называется минимумом.

Обозначение: min f (x).

Утверждение 1. Если существует некоторая постоянная c такая, что

f (x) ≤ c, x D, то и sup f (x) ≤ c;

x D

14

если некоторая постоянная d такова, что f (x) ≥ d, x D, то и

inf f (x) ≥ d.

x D

Данное утверждение следует непосредственно из определений 9 и 10. Утверждение 2. Если f (x) и g (x) заданы на D и при любом x D

верно f (x) ≤ g (x), то верно и sup f (x) ≤ sup g (x), inf f (x) ≤ inf g (x).

Д о к а з а т е л ь с т в о. Из условия и определение супремума имеем f (x) ≤ g (x) ≤ sup g (x) = const с учетом утверждения 1 sup f (x) ≤

≤ sup g (x).

Аналогично доказывается неравенство для инфимумов.

Теорема 3. Если x изменяется в области D , y изменяется в облас-
ти E , f (x, y) определена на D × E , то
supinf		f (x, y) ≤ inf sup f (x, y).		(9.1)
x	y	y	x

Д о к а з а т е л ь с т в о. Имеем при любом x и y f (x, y) ≤ sup f (x, y).

		x
Учитываяутверждение2,получим: inf	f (x, y) ≤ inf sup f (x, y) = const.
y	y	x

Справа здесь стоит постоянная. Поэтому в соответствии с утвержде-

нием 1 имеем: supinf		f (x, y) ≤ inf sup f (x, y).
x	y	y	x

Следствие (Утверждение 3): Если в выражении (9.1) экстремумы достигаются, то

max inf f (x, y) ≤	minsup f (x, y).		(9.2)
x y	y	x

Если, кроме того, достигаются и все внутренние экстремумы, т. е.

если x	min f (x, y) и y	max f (x, y), то
	y		x
	max min f (x, y) ≤ min max f (x, y).			(9.3)
	x	y	y x

Неравенства (9.1), (9.2), (9.3) называют иногда неравенствами минимаксов. Они имеют большое значение в теории игр.

15

10. Равенство минимаксов и седловые точки

Теорема 4. Для того чтобы функция f (x, y) , заданная на множестве D × E , имела седловые точки, необходимо и достаточно, чтобы существовали (т. е. достигались) минимаксы

max inf f (x, y),		minsup f (x, y)		(10.1)
x	y	y	x
и выполнялось равенство
max inf f (x, y) = minsup f (x, y).				(10.2)
x y		y	x
Замечание. Подразумевается седлообразность точки в смысле тео-
рии игр.
Д о к а з а т е л ь с т в о.	1. Необходимость. Пусть f(x, y) имеет
седловые точки и (x*, y*) – одна из них. Это означает, что
f (x, y* )≤ f (x*, y* )≤			f (x*, y).	(10.3)

Применяя к левой части выражения (10.3) утверждение 1 п. 9, получим

sup f (x, y* )≤ f (x*, y* ).	(10.4)
x

Далее, используя определение инфимума применительно к функции g (y) = sup f (x, y), получаем

		x	g (y* )= sup f (x, y* )≤ f (x*, y* ). (10.5)
inf sup f (x, y) = inf g (y) ≤
y	x	y	x

Аналогично, применяя к правой части выражения (10.3) утверждение 1 п. 9 и используя определение супремума применительно к функ-

ции z (x) = inf f (x, y), получим

y

supinf f (x, y) = sup z (x) ≥ z (x* )= inf f (x*, y)≥ f (x*, y* ). 10.6)

x	y	x	y

Объединяя выражения (10.5) и (10.6), имеем:

inf sup f (x, y) ≤ sup f (x, y* )≤ f (x*, y* )≤ inf f (x*, y)≤ supinf f (x, y) (10.7)

y	x	x	y	x	y

inf	sup f (x, y) ≤ supinf f (x, y).
y	x	x	y

16

Но, согласно теореме 3, справедливо и противоположное неравенство supinf f (x, y) ≤ inf sup f (x, y).

x	y	y	x

Поэтому

inf sup f (x, y) = supinf f (x, y).				(10.8)
y	x	x	y

Значит, в выражении (10.7) крайние части равны. Следовательно, равны друг другу все части этого неравенства. В частности, inf sup f (x, y) = sup f (x, y*).

y	x	x

Таким образом в выражении inf sup f (x, y) инфимум достигается

y x

(именно при y = y*) и оно может быть записано как minsup f (x, y).

y x

Точно так же из равенства всех частей в выражении (10.7) вытекает,

что inf f (x*, y) = supinf f (x, y), т. е. супремум достигается в точке x*

y	x	y

и поэтому вместо sup inf			f (x, y) мы можем писать max inf f (x, y).
	x	y	x y
В итоге равенство (10.8) может быть переписано следующим обра-
зом max inf f (x, y) = min sup f (x, y), что и требовалось доказать.
x	y	y	x

2. Достаточность. Предположим теперь, что минимаксы (10.1) существуют и равны, а внешние экстремумы на них достигаются соответственно в точках x* и y*

Это значит, что max inf	f (x, y) = inf	f (x*, y).
x y	y
Но, кроме того, по определению инфимума inf f (x*, y) ≤				f (x*, y),
			y
так что max inf f (x, y) = inf f (x*, y) ≤ f (x*, y*).				(10.9)
x y	y
Аналогично рассуждая, получаем
f (x*, y*) ≤ sup f (x, y*) = min sup f (x, y).				(10.10)
	x	y	x

По предположению минимаксы (10.1) равны, а значит равны друг другу и все сравниваемые в неравенствах (10.9) и (10.10) выражения. В

частности, sup f (x, y*) = f (x*, y*).

x

17

f (x, y*) ≤ f (x*, y*) ≤ f (x*, y),

Учитывая, что f (x, y*) ≤ sup f (x, y*) x,	получим
x
f (x, y*) ≤ f (x*, y*),	x.	(10.11)

Точно так же из равенства частей выражения (10.9) имеем inf f (x*, y) = f (x*, y*).

y

С учетом inf f (x*, y) ≤ f (x*, y) y получаем

y
f (x*, y* )≤ f (x*, y) y.	(10.12)

Выражения (10.1) и (10.2) вместе дают

т. е. (x*, y*) – седловая точка функции f(x, y).

Замечание 1. В ходе доказательства этой теоремы (достаточности) было установлено, что в качестве компонент седловой точки могут быть независимо друг от друга взяты любые x и y, на которых достигаются внешние экстремумы в минимаксах (10.1). Поэтому, если (a, b) и (c, d) – седловые точки функции f(x, y), то точки (a, d) и (c, b) так же будут седловыми для этой функции. Это свойство множества всех седловых точек функции называется обычно прямоугольностью множества.

Замечание 2. Из выражения (10.9), (10.10), (10.2) вытекает, что значение функции в седловой точке равно общему значению минимаксов (10.1), являющемуся некой константой.

Следовательно, значения функции во всех ее седловых точках равны друг другу.

11. Матричные игры

Определение 13. Антагонистические игры, в которых каждый игрок имеет конечное множество стратегий, называются матричными играми.

Такая игра полностью определяется некоторой матрицей, в которой строки соответствуют стратегиям первого игрока, столбцы – стратегиям второго игрока, а на их пересечении стоит выигрыш первого игрока

в соответствующей ситуации H (i, j) = aij . Эта матрица называется

матрицей игры, или матрицей выигрышей. Приняты следующие обозначения.

Пусть – матрица некоторой игры.

A

18

	a	a	...	a
	11	12	...	1n
	a21	a22		a2n
A =		...	...	...	.
	...
	am1	am2	...	amn

Такая игра называется m × n –игрой.

Стратегии первого игрока – номера соответствующих строк, стратегии второго игрока – номера соответствующих столбцов.

Ai.
	– i-я строка матрицы A .
A. j
	– j-й столбец матрицы A .
(i, j) – ситуация, где i – номер строки, j – номер столбца.

Ситуация (i, j) в матричной игре является равновесной, если aij* ≤ ai* j* ≤ ai* j i = 1,...,m, j = 1, ..., n.

В соответствии с теоремой 4 для существования в матричной игре седловых точек (ситуаций равновесия) необходимо и достаточно, что-

бы были равны минимаксы: max min aij = min max aij .
i j	j i

Существование этих минимаксов очевидно, так как множества стратегий каждого игрока конечны, а значит экстремумы на них достигаются.

Схема нахождения седловых точек матрицы :

A

a		a	...	a		→ min a1 j
	11	12		1n		j
a21		a22	...	a2n		→ min a2 j
		...	...	...		j	→ max min aij
						→ ...
...								i j
am1		am2	...	amn		→ min a
						j	mj
	↓	↓	↓	↓
max ai1		max ai2 ...		max ain
	i	i		i
		min max aij
		j i
Определение 14. Стратегии i				и	j , на которых достигаются
max min aij	и min max aij ; называются соответственно максиминной и
i j	j	i

минимаксной.

19

Если максимин и минимакс равны друг другу, то их общее значение

называется значением матричной игры с матрицей выигрышей A и обо-

значается V (A).

П р и м е р 1. Пусть задана матрица выигрышей

1

−3

−2

→

min a

= −3

j

1 j

0

5

4

→

min a

=

0

→ max min a = 2

A =

2 j

j

i j

ij

=

2

3

2

→

min a

2

j

ij

↓

↓

↓

max ai1

max ai2

max ai3

i

i

i

= 2

= 5

= 4

min max aij = 2

j

i

Седловой точкой является

Максимин и минимакс равны и V (A)= 2.

ситуация (3, 1), образованная 3-й стратегией первого игрока и 1-й стратегией второго игрока.

Замечание. Хотя выигрыш в ситуации (3,3) тоже равен 2, но эта точка не является седловой, так как для второго игрока данная ситуация приемлема (проигрыш минимален среди проигрышей третьей строки), а вот для первого игрока – не приемлема (выигрыш не является максимальным среди выигрышей третьего столбца).

П р и м е р 2. Пусть задана матрица выигрышей

		10	30	→ 10	→ max min aij = 20.
A =
	40		20	→ 20	i j

↓↓

40 30

min max aij = 30

j i

Максимин равен 20 и достигается при i = 2, а минимакс равен 30 и достигается при j = 2. Значит игра не имеет ситуации равновесия в чистых стратегиях.

20