WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 5 |

оптимальной такую ситуацию, от т которой ни одному (x1, x2 ) X1 X из игроков невыгодно отклоняться. Такая ситуация называется (x1, x2 ) 2.2. Принцип максмина и минимакса равновесной, а принцип оптимальности, основанный на построении равновесной ситуации, – принципом равновесия. Ниже будет показано, Установим связь между принципом равновесия и принципами мичто для антагонистических игр принцип равновесия эквивалентен нимакса и максмина в антагонистической игре. Пусть дана МИ с матпринципам минимакса и максмина. Разумеется, для этого необходимо рицей существование равновесия, т. е. чтобы принцип оптимальности был 11 … 1n реализуем.

A = … … …, Перепишем определение равновесия по Нэшу для антагонистичес- … mn кой игры:

mK1(x1, x2) = i, j ; K2(x1, x2) = i, j = -i, j ;

которая полностью определяет выигрыши игроков.

K1(x1, x2) = i, j ; K2(x1, x2) = i, j = -i, j.

Первый выбирает строку i, второй – столбец j. Выигрыш первого о Откуда следует, что игрока стоит на пересечении i-й строки и j -го столбца. Эта же величина есть проигрыш или выигрыш с обратным знаком второго игрока.

K1(x1, x2) = i, j K1(x1, x2) = i, j i X1;

Итак, первый игрок произвольно выбрал стратегию i. В каком K2(x1, x2) = -i, j K2(x1, x2) = -i, j j X ;

выигрыше он может быть уверен В минимальном, естественно, т. е.

i, j i, j i, j i, j X.

min минимальное значение выигрыша ij при выбранной стратегии i j Определение 2.4. В антагонистической игре ситуация GA (i, j) ему обеспечено. Естественно выбрать такую стратегию i, при которой называется ситуацией равновесия или седловой точкой, если этот минимум максимален, т. е. естественно выбрать i0, при которой i, j i, j i, j i, j X.

достигается 12 min max ij = v j i maxmin ij = min i0 j = v, i j j max i1 max i2 … max in i i i где v – нижнее значение игры (нижняя цена игры).

j 11 12 … 1n min j Определение 2.7. Стратегия i0 называется максминной страте 22 … 2n min 2 max j j гией первого игрока.

min ij = v i j … … … … … Пусть теперь второй игрок выбрал j -й столбец и уверен, что он min m2 … mn mj mпроиграет не больше, чем max ij. Естественно выбрать такую стратегию j i Рис. 2.1. Схема нахождения максмина и минимакса для игры GA j, при которой этот максимальный проигрыш минимален, т. е. выбрать такой столбец j0, который минимизирует его проигрыш:

Лемма 2.1. В антагонистической игре.

GA v v Теорема 2.1. Для того чтобы в ла (m n)-МИ существовала GA v = minmax ij = max ij0, j i i ситуация равновесия, необходимо и достаточно, чтобы, при этом м v = v максминная и минимаксная стратегия (i0, j0) образует ситуацию где v – верхнее значение игры (верхняя цена игры).

равновесия.

Определение 2.8. Стратегия j0 называется минимаксной стратеОпределение 2.9. Игры, в которых существуют ситуации равновегией второго игрока.

сия, называются вполне определенными.

Таким образом, минимакс и максмин для игры могут быть GA Поэтому данная теорема устанавливает критерий вполне опреденайдены по схеме, представленной на рис. 2.1.

ленной игры и может быть переформулирована следующим образом.

Пример 2.3. Так, в игре с матрицей из примера 2.2 нижнее значение Теорема 2.2. Для того чтобы игра была вполне определена, (максмин) и максминная стратегия i0 первого игрока, i0 = 2, а v v = 3 необходимо и достаточно, чтобы существовали минимакс и максмин а верхнее значение (минимакс) и минимаксная стратегия j0 второго и выполнялось равенство.

о v v = v игрока – v = 3, j0 = 2. А в игре с матрицей Замечание 2.1. Заметим, что в (m n)-МИ экстремумы, т. е.

GA минимакс и максмин достигаются всегда, а вот ситуация, в которой 7 (4) 6 / / / максимальный элемент по столбцу и минимальный элемент по строке / -1 0 -1 5 равны, очень редка. См. пример 2.3, где есть максминная и минимаксная стратегии, а ситуации равновесия нет и, соответственно, значения игры /-1 0 -1 -тоже нет.

(0) 4 6 Пример 2.4. Так, в игре с матрицей максминная стратегия первого игрока – i0 = 3, нижнее значение игры – (2) 4 ; минимаксная стратегия второго игрока – j0 = 2, верхнее значение v = 1 1 4 игры v = 4.

(2)(2) 3 - 2 0 - 2 14 * ситуация является равновесной. При этом max min ij = X1 ={i i X1, j X2, (i, j) Z(GA)}, (2, 1) i j * = min max ij = 2.

X2 ={j j X2, i X1, (i, j) Z(GA)}.

j i Тогда множество можно представить в виде Z(GA) 1 * * Z(GA) = X1 X.

С другой стороны, игра с матрицей не имеет ситуации 0 * X2 тся Определение 2.10. Множества и в игре называются X1 * Z(GA) равновесия в чистых стратегиях (седловых точек), так как множествами оптимальных стратегий, а их элементы – оптимальными min max ij = 1 > max min ij = 0.

j i i j стратегиями первого и второго игрока соответственно.

Множество ситуации равновесия в антагонистической игре облаGA Самостоятельная работа № дает свойствами, которые позволяют говорить об оптимальности ситуации равновесия и входящих в нее стратегий. Обозначим множество всех Найти все максминные и минимаксные стратегии игроков, нижнее ситуаций равновесия через Z(GA) X1 X2.

и верхнее значения игры; указать все ситуации равновесия и значение Теорема 2.3. Пусть, – две произвольные ситуации (i1, j1) (i2, j2) игры, если они есть.

равновесия в антагонистической игре. Тогда GA 1) i1, j1 = i2, j2 ; i1, j2 = i2, j1 ;

ЗАНЯТИЕ № 2) (i1, j2) Z(GA); (i2, j1) Z(GA).

Из теоремы следует, что любая пара оптимальных стратегий обра- 3.1. Смешанные стратегии матричных игр (МИ) зует ситуацию равновесия, а функция выигрыша в ней принимает одно и то же значение, равное значению игры. В МИ с полной информацией игроки не делают тайны из своих Пример 2.5. В игре с матрицей равновесных стратегий, которые гарантируют всем игрокам одновременно оптимальный максминный «выигрыш» независимо от поведения проj1 jтивника. Однако в отсутствие седловой точки игроки не довольствуются 6 (3) 8 (3) своим максминным «выигрышем»: кто из нас ограничится малым, если 0 1 0 4 есть надежда на большее Рассмотрим МИ i1 (3)5 (3) 8 (3) i2 (3)6 (3) 4 (3) 1 2 1 0, v = 0, v = 1.

ситуации 1 2 (i1, j1) = (2,2); (i2, j1) = (3, 2); (i2, j2) = (3, 4); (i1, j2) = (2, 4) являются равновесными. При этом Будем рассуждать так. Если играть 5 млн раз, то возможный выиг.

v = K(i1, j1) = K (i2, j1)= K (i2, j2)= K (i1, j2) = рыш первого игрока при выборе 1-й стратегии будет 1/2. Аналогично Из второй части теоремы следует:

может действовать второй игрок, выбирая какой-либо столбец. Первый * * игрок гарантирует, что он выиграет 1/2, а второй гарантирует, что он X2 а Утверждение 2.1. Пусть X1 и – проекции множества на Z(GA) проиграет не более 1/2, т. е. игроки выбирают своими стратегиями X1 и X2 соответственно, т. е.

.

(1 2,1 2) 16 Таким образом, каждый игрок, манипулируя непредсказуемо для Определение 3.5. Случайная величина, значениями которой противника (например, по правилам, известным только ему, или случай- являются стратегии игрока, называется его смешанной стратегией.

но) чистыми стратегиями, убеждается, что при многократном повторе- Учитывая введенное определение смешанных стратегий, нии игры может улучшить свой максминный «выигрыш».

прежние стратегии будем называть «чистыми». Так как случайная величина характеризуется своим распределением, то будем Рассмотрим МИ с матрицей Amn, где {i i = 1,m} – стратегии отождествлять в дальнейшем смешанную стратегию с веропервого игрока; – стратегии второго игрока. Ситуация игры – {j j = 1,n} ятностным распределением на множестве чистых стратегий. Таким образом, вектор x может быть интерпретирован следующим образом.

пара стратегий.

(i, j) Это набор вероятностей, с которыми первый игрок выбирает Определение 3.1. Стратегию, полученную в многократно повторясоответствующие строки матрицы. – вероятность выбора первой емой игре при случайном механизме реализации чистых стратегий игрока, называют рандомизированной (смешанной) стратегией игрока. стратегии, i – вероятность выбора i -й стратегии, m – m -й страте ратеОпределение 3.2. Под смешанной стратегией первого игрока гии, сумма этих вероятностей равна 1.

y Аналогично, – это набор вероятностей, в соответствии с которыми будем понимать m-мерный смешанный вектор x = (1,...,i,..., m ) Rm, второй игрок выбирает столбцы матрицы: первый – выбор первого m столбца, j – j -го столбца, – -го столбца, сумма их равна 1.

n n = 1, i 0, i = 1,m i, Определение 3.6. Чистая стратегия является частным случаем i=смешанной стратегии. Она заключается в выборе -й строки и имеет i где – число строк матрицы выигрышей Amn.

m вид xi = (0,..., 1i,...,0), т. е. -я строка выбирается с вероятностью 1.

i Таких векторов x бесконечно много. Множество всех стратегий m Соответственно, чистая стратегия для второго игрока первого игрока x обозначим I0.

Определение 3.3. Аналогично смешанная стратегия второго игрока y = (0,...,0,1j,0,...,0). Таким образом, чистые стратегии – выбор номеров j y = (1,...,,...,n) определяется как n-мерный вектор, т. е.

n j строк или столбцов. У первого игрока – чистых стратегий, у второго – m n чистых стратегий.

n =1, 0, j = 1, n j j, Определение 3.7. Если игроки выбрали свои смешанные стратегии, j=то пара смешанных стратегий игроков в матричной игре (x, y) GA где – число столбцов матрицы выигрышей Amn.

n называется ситуацией в смешанных стратегиях.

В ситуации в смешанных стратегиях пара чистых стратегий При этом i 0 и j 0 – соответственно вероятности выбора (x, y) о реализуется с вероятностью ij. Если такая пара появляется, то чистых стратегий и при использовании игроками (i, j) i X1 j Xсмешанных стратегий х и у. Множество всех стратегий второго игрока выигрыш первого игрока есть ij, отсюда следует, что вероятность y обозначим.

II выигрыша ij является ij, следовательно, выигрыш ij является ся Определение 3.4. Напомним, что вещественная функция, значения случайной величиной. Поэтому выигрыш первого игрока в ситуации которой имеют определенную вероятность, называется случайной в смешанных стратегиях для (x, y) (m n)-МИ можно определить GA величиной.

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

ми стратегиями.

m n Заметим, что выигрыши, при применении первым E(i, y) E(x, j) E(x, y) = ij = xA, y = x, Ay ij, i =1 j =или вторым игроком чистой стратегии i или j соответственно, а другим – смешанной стратегии (у или х) имеют вид где, – скалярное произведение.

n При этом функция является непрерывной по E(x, y) x I E(xi, y) = E(i, y) = = i y; i =1, m;

ij j и.

y II j=Если играть 10 млн раз при выборе первым игроком i -й стратегии, m j а вторым – j-й, то средний выигрыш за эти 10 млн раз повторений игры E(x, yi ) = E(x, j) = i = x, j = 1, n, ij будет для первого игрока млн, выигрыш второго игрока i=а E(x, y)j составит - E(x, y)10 где i, – i-я строка и j-й столбец соответственно млн.

(m n)-матрицы А.

Определим смешанное расширение МИ.

m n Пусть. Тогда если вместо использовать ть E(x, y) = i x Определение 3.8. Антагонистическая игра называется G A ij j i=1 j=смешанным расширением игры, если задается следующим образом:

GA чистую стратегию, то.

= {I; II; E(x, y)} m n m Игроки 1 и 2 выбирают стратегии, для первого о x I, y II E(x, y) = = E(i, y).

i ij j i игрока реализуется выигрыш, для второго – –E(x, y). Игра E(x, y) GA i=1 j =1 i= является подыгрой для, т. е.

G GA G.

A A y о Аналогично, если вместо использовать чистую стратегию, то n m n 3.2. Ситуация равновесия в смешанных стратегиях E(x, y) = i = E(x, j).

j ij j i=1 j=1 j= Определение 3.9. Ситуация в игре образует ситуацию (x, y) G A Следовательно, равновесия, а число является значением игры, если v = E(x, y) G A m n m n (3.1) E(x, y) E(x, y) E(x, y) x I, y II.

E(x, y) = E(i, y) = E(x, j) = i.

i j ij j i=1 j=1 i=1 j=В ситуации за 10 млн раз игры, если отклонение от ситуации (x, y) Пусть – ситуация в смешанных стратегиях в игре будет происходить достаточно часто, то выигрыш для первого игрока (x, y) I II может уменьшиться, а для второго потери увеличатся.

. Оказывается, что для проверки ситуации на равновесность GA (x, y) Теорема 3.1. В любой МИ существует ситуация равновесия в неравенства (3.1) достаточно проверять не для всех и, x I y II смешанных стратегиях.

а лишь для и, поскольку справедливо следующее i X1 j XЭквивалентная формулировка. В любом смешанном расширении МИ существует ситуация равновесия. утверждение.

20 Теорема 3.2. Необходимое и достаточное условие существования то вероятность выбора -й стратегии первым игроком в ситуации i равновесия. равновесия обязательно должна быть Для того чтобы ситуация и число были, соответ(x, y) v = E(x, y) i = 0. (3.4) ственно, ситуацией равновесия в смешанных стратегиях и значением Согласно теореме 3.2, условие равновесия E(i, y) E(x, y) E игры, необходимо и достаточно, чтобы имели место следующие нераy да. Пусть и оптимальны. Тогда. Если для E(x, j) i, j венства: x E(x, y) = v какого-либо i неравенство слева выполняется строго, то первый игрок,. (3.2) E(i, y) v E(x, j) i X1, j X отклонившись на чистую стратегию i, свой выигрыш уменьшит, следоЛемма 3.1. Если в игре существует ситуация равновесия в чистых вательно, вероятность выбора первым игроком в ситуации равновесия стратегиях, то она является ситуацией равновесия в смешанных стратечистой стратегии i должна быть равной нулю.

гиях, и значение игры в чистых стратегиях равно значению игры в смеТеорема 3.4. Пусть y = (1,...,n) о – оптимальная стратегия второго шанных стратегиях.

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

а.

v x Эквивалентная формулировка. Пусть – ситуация (x, y) Тогда, если равновесия в игре. Тогда ситуация равновесна и в игре G.

GA (x, y) A, (3.5) E(x, j) > v Пример 3.1. «Орел или решка» моделируется игрой то вероятность выбора j -й стратегии обязательно должна быть o p j = 0. (3.6) o (1,-1) (-1,1).

p(-1,1) (1,-1) Теоремы 3.3 и 3.4 обосновывают процедуру выбора стратегии, которая обеспечивает успешный поиск.

Легко видеть, что в этой игре нет ситуации равновесия в чистых y о Теорема 3.5. Пусть и – оптимальные стратегии 1-го и 2-го x стратегиях, так как в любой ситуации одному из игроков выгодно игроков, – значение игры. Тогда v отклониться от выбранной стратегии при условии, что другой игрок min E(x, j) = v в этой ситуации придерживается своей стратегии. Однако, как мы (3.7) j=1,n увидим, пара смешанных стратегий, где, (x, y) x = (1 2,1 2), y = (1 2,1 2) и в которых каждый из игроков играет свои чистые стратегии с равными вероятностями, образует ситуацию равновесия в смешанных стратегиях. max E(i, y) = v. (3.8) i=1,m 3.3. Свойства оптимальных смешанных стратегий Теорема 3.6. Пусть – GA (m n)-МИ. Для того чтобы ситуация в смешаных стратегиях была равновесной в игре, необходимо (x, y) G A Рассмотрим свойства оптимальных стратегий, которые в ряде и достаточно выполнение равенства случаев помогают находить значение игры и ситуацию равновесия.

max E(i, y) = min E(x, j). (3.9) Теорема 3.3. Пусть x = (1,...,m) – оптимальная смешанная 1im 1 jn y стратегия первого игрока, – значение игры и – оптимальная v смешанная стратегия второго игрока. Тогда, если Теорема 3.7. Для МИ G справедливы следующие соотношения:

A, (3.3) E(i, y) < v max min E(x, j) = v = min max E(i, y), (3.10) x j y i 22 y причем экстремумы по смешанным стратегиям и в (3.10) достигаx 31 - 22 < v; (1) - 2 + 23 = v; (4) ются на оптимальных стратегиях игроков.

- 1 + 42 = v; (2) 42 + 23 = v; (5) Пример 3.2. Возьмем матрицу 21 + 22 = v; (3) 22 + 63 > v. (6) - 2 Вычтем (4) из (5)., 3 =1 v = -1 4 2. 2 = 0 1 = 2 2 2. Следовательно, оптимальная стратегия 2 = v 2 - 1 = 3 и.

x = (0, 0, 1) y = (2 5, 3 5,0) Здесь – по строкам, v = 3 – по столбцам. Следовательно, в чистых v = стратегиях ситуации равновесия не существует. Будем искать ситуацию 3.4. Равновесие по Нэшу в смешанных стратегиях в биматричной равновесия в смешанных стратегиях.

игре Составим систему из 14 неравенств:

N Обобщим понятие ситуации равновесия на игру из игроков.

E(i, y) v E(x, j) i, j;

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

– множество игроков;

N = {1, n} 0, n = 1;

j j j=1 = i – множество ситуаций в смешанных стратегиях;

m i=1,n 0, = 1.

i i i = {i} – множество смешанных стратегий i i-го игрока, а, i=;

i N Решение может не получиться, так как могут быть отрицательные ki – число чистых стратегий i-го игрока;

Pages:     | 1 || 3 | 4 |   ...   | 5 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.