Учебная работа. Реферат: Бесконечные антагонистические игры

(4 оценок, среднее: 4,75 из 5)

Загрузка...

Учебная работа. Реферат: Бесконечные антагонистические игры

Определение нескончаемой антагонистической игры

Естественным обобщением матричных игр являются нескончаемые антагонистические игры (БАИ), в каких хотя бы один из игроков имеет нескончаемое количество вероятных стратегий. Мы будем разглядывать игры 2-ух игроков, делающих по одному ходу, и опосля этого происходит распределение выигрышей. При формализации настоящей ситуации с нескончаемым числом выборов можно каждую стратегию сравнить определённому числу из единичного интервала, т.к. постоянно можно обычным преобразованием хоть какой интервал перевести в единичный и напротив.

Напоминание. Пусть Е – некое огромное количество вещественных чисел. Если существует число y, такое, что x£y при всех хÎЕ (при всем этом y не непременно принадлежит Е), то огромное количество Е именуется ограниченным сверху, а число y именуется верхней границей огромного количества Е. Аналогично определяется ограниченность снизу и нижняя граница огромного количества Е. Обозначаются верхняя и нижняя границы соответственно через sup Е и inf Е соответственно.

Пример. Пусть огромное количество Е состоит из всех чисел вида , n = 1,2, … Тогда огромное количество Е ограничено, его верхняя грань равна 1, а нижняя 0, причём 0ÏЕ , а 1ÎЕ.

Для предстоящего изложения теории игр этого класса введём определения и обозначения : [0; 1] – единичный просвет, из которого игрок в состоянии сделать выбор; х – число (стратегия), выбираемое игроком 1; y– число (стратегия), выбираемое игроком 2; Мi
(x,y) – выигрыш i-го игрока; G (X,Y,M1
,M2
) – игра 2-ух игроков, с ненулевой суммой, в какой игрок 1 выбирает число х из огромного количества Х, игрок 2 выбирает число y из огромного количества Y, и опосля этого игроки 1 и 2 получают соответственно выигрыши M1
(x, y) и M2
(x, y). Пусть, дальше, G (X,Y,M) – игра 2-ух игроков с нулевой суммой, в какой игрок 1 выбирает число х, игрок 2 – число y, опосля что игрок 1 получает выигрыш М(x, y) за счёт второго игрока.

Огромное значение в теории БАИ имеет вид функции выигрышей M(x, y). Так, в отличии от матричных игр, не для всякой функции M(x, y) существует решение. Будем считать, что выбор определённого числа игроком значит применение его незапятанной стратегии, соответственной этому числу. По аналогии с матричными играми назовём незапятанной нижней ценой игры величину

V1
= M(x, y) либо V1
= M(x, y),

а незапятанной верхней ценой игры величину

V2
= M(x, y) либо V2
= M(x, y),

Для матричных игр величины V1
и V2
постоянно есть, а в безграничных играх они могут не существовать.

естественно считать, что, если для какой-нибудь нескончаемой игры величины V1
и V2
есть и равны меж собой (V1
= V2
= V), то таковая игра имеет решение в незапятнанных стратегиях, т.е. хорошей стратегией игрока 1 есть выбор числа xo
ÎX и игрока 2 – числа yo
ÎY, при которых M(xo
, yo
) = V, в этом случае V именуется ценой игры, а (xo
, yo
) – седловой точкой в незапятнанных стратегиях.

Пример 1. Игрок 1 выбирает число х из огромного количества Х = [0; 1], игрок 2 выбирает число y из огромного количества Y = [0; 1]. Опосля этого игрок 2 платит игроку 1 сумму

M(x, y) = 2х2
— y2
.

Так как игрок 2 желает минимизировать выигрыш игрока 1, то он описывает

(2×2
-y2
) = 2х2
— 1,

т.е. при всем этом y = 1. Игрок 1 хочет максимизировать собственный выигрыш, и потому описывает

(M(x, y)) = (2х2
— 1) = 2-1 = 1,

который достигается при х = 1.

Итак, нижняя стоимость игры равна V1
= 1. Верхняя стоимость игры

V2
= ((2х2
-y2
)) = (2 — y2
) = 2-1 = 1,

т.е. в данной для нас игре V1
= V2
= 1. Потому стоимость игры V = 1, а седловая точка (1;1).

Пример 2. Игрок 1 выбирает хÎX = (0; 1), игрок 2 выбирает yÎY = (0; 1). Опосля этого игрок 1 получает сумму

M(x, y) = x + y

за счёт игрока 2. Так как Х и Y- открытые интервалы, то на их V1
и V2
не есть. Если б Х и Y были замкнутые интервалы, то, разумеется, было бы последующее :

V1
= V2
= 1 при xo
= 1, yo
= 0.

С иной стороны, ясно, что, выбирая х довольно близкое к 1, игрок 1 будет уверен, что он получит выигрыш не меньше, чем число, близкое к стоимости игры V = 1; выбирая y близкое к нулю, игрок 2 не допустит, чтоб выигрыш игрока 1 существенно различался от цены игры V = 1.

Степень близости к стоимости игры может характеризоваться числом e > 0. Потому в описываемой игре можно гласить о оптимальности незапятнанных стратегий хo
= 1, yo
= 0 соответственно игроков 1 и 2 с точностью до случайного числа e > 0. В связи с сиим введём последующие определения.

Точка (,), где ÎX, ÎY, в антагонистической непрерывной игре G именуется точкой e-равновесия , если для всех стратегий xÎX игрока 1, yÎY игрока 2 имеет пространство неравенство

М(х,) -e£M(,) £ М(, y) + e.

Точка e-равновесия (,) именуется также e-седловой точкой функции М(x, y), а стратегии и именуются e-оптимальными стратегиями. Эти стратегии являются хорошими с точностью до e в том смысле, что, если отклонение от хорошей стратегии никакой полезности игроку принести не может, то его отклонение от e-оптимальной стратегии может прирастить его выигрыш не наиболее, чем на e.

Можно обосновать, что для того, чтоб функция М имела e-седловые точки для хоть какого e>0 нужно и довольно чтоб

M(x, y) = M(x, y).

Если игра G не имеет седловой точки (e-седловой точки) в незапятнанных стратегиях, то рациональные стратегии можно находить посреди смешанных стратегий. Но, в качестве вероятностной меры тут вводятся функции распределения вероятностей внедрения игроками незапятнанных стратегий.

Пусть F(х) – функция распределения вероятностей внедрения незапятнанных стратегий игроком 1. Если число x- незапятнанная стратегия игрока 1, то

F(х) = P(x£ х),

где P(x£ х) значит возможность того, что случаем избранная незапятнанная стратегия x не будет превосходить числа х. Аналогично рассматривается функция распределения вероятностей внедрения незапятнанных стратегий h игроком 2

Q(y) = P(h£ y).

Функции F(х) и Q(y) именуются смешанными стратегиями соответственно игроков 1 и 2. Если F(х) и Q(y) дифференцируемы, то есть их производные, обозначаемые соответственно через f(x) и q(y) (функции плотности распределения).

В общем случае дифференциал функции распределения dF(х) выражает возможность того, что стратегия x находится в промежутке

х £x£ х + dх.

Аналогично для игрока 2: dQ(y) значит возможность того, что его стратегия h находится в интервале

y £h£ y + dy.

Тогда выигрыш игрока 1 составит

М(х, y) dF(х),

а выигрыш игрока 2 равен

М(х, y) dQ(y).

Средний выигрыш игрока 1 при условии, что игрок 2 применяет свою чистую стратегию y, получим, если проинтегрируем выигрыш по всем вероятным значениям х, т.е.

E(F, y) =

Напомним, что огромное количество Y для y является замкнутым промежутком [0; 1].

Если игрок 1 применяет свою чистую стратегию х, а игрок 2 — y, то выигрыш игрока 1 составит

М(х, y) dP(х) dQ(y).

Средний выигрыш игрока 1 при условии, что оба игрока используют свои смешанные стратегии F(х) и Q(y), будет равен

E(F,Q) = .

По аналогии с матричными играми определяются рациональные смешанные стратегии игроков и стоимость игры: в антагонистической непрерывной игре G(Х,Y,М) пара смешанных стратегий F*(х) и Q*(y) соответственно для игроков 1 и 2 образует седловую точку в смешанных стратегиях, если для всех смешанных стратегий F(х) и Q(y) справедливы соотношения

Е(F,Q*) £ Е(F*,Q*) £ Е (F*,Q).

Из левой части крайнего неравенства следует, что если игрок 1 отступает от собственной стратегии F*(х), то его средний выигрыш не может возрости, но может уменьшиться за счёт наилучших действий игрока 2, потому F*(х) именуется хорошей смешанной стратегией игрока 1.

Из правой части крайнего неравенства следует, что если игрок 2 отступит от собственной смешанной стратегии Q*(y), то средний выигрыш игрока 1 может возрости, а не уменьшиться, за счёт наиболее разумных действий игрока 1, потому Q*(y) именуется хорошей смешанной стратегией игрока 2. Средний выигрыш Е(F*,Q*), получаемый игроком 1 при применении игроками хороших смешанных стратегий, именуется ценой игры.

По аналогии с матричными играми рассматривается нижняя стоимость непрерывной игры в смешанных стратегиях

V1
= E(F,Q)

и верхняя стоимость игры

V2
= E(F,Q).

Если есть такие смешанные стратегии F*(х) и Q*(y) соответственно для игроков 1 и 2, при которых нижняя и верхняя цены непрерывной игры совпадают, то F*(х) и Q*(y) естественно именовать хорошими смешанными стратегиями соответственных игроков, а V1
= V2
= V – ценой игры.

Можно обосновать, что существование седловой точки в смешанных стратегиях игры G(Х,Y,М) равносильно существованию верхней V2
и нижней V1
цен игры в смешанных стратегиях и их равенству V1
= V2
= V.

Таковым образом, решить игру G(Х,Y,М) – значит отыскать седловую точку либо такие смешанные стратегии, при которых нижняя и верхняя цены игры совпадают.

Аксиома 1 (существования). Всякая антагонистическая нескончаемая игра 2-ух игроков G с непрерывной функцией выигрышей М(х,y) на единичном квадрате имеет решение (игроки имеют рациональные смешанные стратегии).

Аксиома 2. Пусть – нескончаемая антагонистическая игра с непрерывной функцией выигрышей М(х, y) на единичном квадрате и ценой игры V. Тогда, если Q(y) – лучшая стратегия игрока 2 и для некого xo

то xo
не может заходить в точки диапазона хорошей стратегии игрока 1; если F(х) – лучшая стратегия игрока 1и для некого yo

то yo
не быть может точкой диапазона хорошей стратегии игрока 2.

Из аксиомы 2 следует, что если один из игроков применяет лучшую стратегию, а иной – чистую, притом что средний выигрыш игрока 1 различается от цены игры, то эта незапятнанная стратегия не может войти в его лучшую стратегию (либо она заходит в неё с вероятностью нуль).

Аксиома 3. Пусть в нескончаемой антагонистической игре функция выигрышей М(х,y) непрерывная для хÎ[0; 1], yÎ[0; 1] и

М(х, y) = -М(y, х),

тогда стоимость игры равна нулю и неважно какая лучшая стратегия 1-го игрока будет также хорошей стратегией другого игрока.

Сформулированные характеристики хороших смешанных стратегий и цены игры помогают отыскивать либо инспектировать решения, но они ещё не дают в общем виде применимых способов решения игры. Наиболее того, не существует общих способов для четкого нахождения решения БАИ, и в том числе непрерывных игр на единичном квадрате. Потому рассматриваются личные виды антагонистических безграничных игр.

Игры с выпуклыми функциями выигрышей.

Игры с выпуклыми непрерывными функциями выигрышей, именуемые нередко ядром, именуются выпуклыми.

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

f(a1
х1
+ a2
х2
) £a1
f(х1
) + a2
f(х2
),

где х1
и х2
– любые две точки из интервала (а,b); a1
, a2
³ 0, причём a1
+ a2
= 1.

Если для a1
¹ 0, a2
¹ 0 постоянно имеет пространство серьезное неравенство

f(a1
х1
+ a2
х2
) < a1
f(х1
) + a2
f(х2
),

то функция f именуется строго выпуклой на (а;b). Геометрически выпуклая функция изображает дугу, график которой размещен ниже стягивающей её хорды (см. рис.)

Напомним, также, что непрерывная и строго выпуклая функция f на замкнутом интервале воспринимает малое

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

Аксиома 4. Пусть М(х, y) – непрерывная функция выигрышей игрока 1, на единичном квадрате и строго выпуклая по y для хоть какого х. Тогда имеется единственная лучшая незапятнанная стратегия y = yo
Î[0;1] для игрока 2, стоимость игры определяется по формуле

V = M(x, y),

M(x, yo
) = V.

Замечание. Если в аксиоме 4 не полагать строгую неровность функции М(х, y) по y, а просто неровность, то аксиома остаётся в силе с тем различием, что у игрока 2 лучшая незапятнанная стратегия не будет единственной.

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

Таковым образом, если М(х, y) непрерывна и выпукла по y, то стоимость игры определяется по формуле (1), и игрок 2 имеет лучшую чистую стратегию, определяемую из уравнения (2).

Аналогично и для игрока 1: если функция выигрышей М(х, y) непрерывна по обоим аргументам и строго вогнута по х при любом y, то в этом случае игрок 1 имеет единственную лучшую стратегию.

Стоимость игры определяется по формуле

V = M(x,y),

а незапятнанная лучшая стратегия хo
игрока 1 определяется из уравнения

M(xo
, y) = V.

Пример. Пусть на квадрате [0;1] задана функция

М(х, y) = .

Потому что

для xÎ[0; 1], yÎ(0;1),

то М(х, y) строго вогнута по х для хоть какого yÎ(0;1). Как следует, стоимость игры находится по формуле (3)

V = .

Отметим, что при 0 £ х £ справедливо равенство

а при 0,5 < х £ 1

Потому

V = max [; ] =

= max [; ] =

= max [;] = .

При всем этом . Это

= ,

т.к. минимум достигается при y = 0, и это уравнение преобразуется в последующее

= ,

откуда следует, что х = .

Заметим, что если в функции выигрышей (5) поменять местами х и y, то она не поменяется, а как следует, эта функция выпукла и по y при всех х Î[0;1]. Потому к ней применима та же теория, т.е. у игрока 2 существует лучшая незапятнанная стратегия yo
, определяемая из уравнения (4)

Разумеется, максимум по х достигается при х = , и крайнее уравнение воспримет вид

= .

Решением крайнего уравнения будет yo
= 0. Как следует, игрок 2 имеет лучшую чистую стратегию yo
= 0.

Замечание. В приведённом выше примере мы могли найти лучшую стратегию игрока 1, а игрока 2 — лишь случаем, в силу “успешного” вида М(х, y).

Разглядим сейчас способ определения хороших стратегий того игрока, для которого функция выигрышей не непременно выпукла. Пусть непрерывная функция М(х, y), данная на единичном квадрате, выпукла по y. Нас будет заинтересовывать вопросец нахождения хороших стратегий 1 игрока. Представим также, что для х Î[0; 1], y Î[0; 1] существует личная производная функции М(х, y) по y, причём в точках y = 0 и y = 1 (х, y) = понимается как правая и левая производная соответственно. Обозначим через yo
одну из хороших незапятнанных стратегий игрока 2 (эта стратегия существует в согласовании с аксиомой 4).

Согласно аксиоме 2 незапятнанные стратегии х игрока 1 могут заходить в его лучшую стратегию с положительной вероятностью, если для их производится равенство

М(х, yo
) = V.

Такие незапятнанные стратегии х именуются существенными.

Аксиома 5. Пусть дана нескончаемая антагонистическая игра с непрерывной и дифференцируемой по y на единичном квадрате при любом х функцией выигрышей М(х, y), с хорошей незапятанной стратегией yo
игрока 2 и ценой игры V, тогда :

1) если yo
= 1, то посреди хороших стратегий игрока 1 имеется значимая незапятнанная стратегия х1
, для которой

(х1
, 1) £ 1;

2) если yo
= 0, то посреди хороших стратегий игрока 1 имеется значимая незапятнанная стратегия х2
, для которой

(х2
, 0) ³ 0;

3) если 0 £ yo
£ 1, то посреди хороших стратегий игрока 1 найдётся таковая, которая является консистенцией 2-ух существенных стратегий х1
и х2
. Для этих стратегий

(х1
, yo
) £ 0, (х2
, yo
) ³ 0,

стратегия х1
употребляется с вероятностью a, стратегия х2
– с вероятностью (1 -a), где a находится из уравнения

a(х1
, yo
) + (1 -a)(х2
, yo
) = 0.

Пример. Пусть функция выигрышей в нескончаемой антагонистической игре задана на единичном квадрате и равна

М(х, y) = (х -y)2
= х2
— 2хy + y2
.

Эта функция непрерывна по х и y, и потому эта игра имеет решение. Не считая того

= 2 > 0.

Как следует, М(х, y) выпукла по y, и потому согласно аксиоме 4 стоимость игры определяется по формуле (1), игрок 2 имеет чистую лучшую стратегию yo
, определяемую из уравнения (2). Таковым образом, имеем

V = (x-y)2
;

Для определения (x2
— 2xy + y2
) поочередно найдём

= 2x — 2y := 0 Þ x = y

= 2 > 0 Þ при x = y функция M имеет минимум для хоть какого y.

Þ максимум достигается в одной из последних точек x = 0 и (либо) x = 1

M(0; y) = y2

M(1; y) = 1 — 2y + y2
= (y — 1)2

V= max {y2
; (1 — y)2
}

Данный max {…} достигается в том случае, если y2
= (1 -y)2
, т.е. y = .

Как следует V = при yo
= .

Определим сейчас рациональные стратегии для игрока 1. Так как yo
= , то 0 < yo
< 1. Согласно аксиоме 5 разглядим 3-ий вариант.

Определим х из уравнения

М(х, yo
) = V,

другими словами

(х —)2
= .

Решая крайнее уравнение, получим х1
= 0, х2
= 1. сейчас нужно найти величину a– возможность внедрения незапятанной стратегии х1
= 0. С данной для нас целью используем уравнение

a(0,) +(1 -a)(1,) = 0.

Несложно отыскать