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

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

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

Напоминание. Пусть Е – некоторое множество вещественных чисел. Если существует число 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) – игра двух игроков, с ненулевой суммой, в которой игрок 1 выбирает число х из множества Х, игрок 2 выбирает число y из множества Y, и после этого игроки 1 и 2 получают соответственно выигрыши M1(x, y) и M2(x, y). Пусть, далее, G (X,Y,M) – игра двух игроков с нулевой суммой, в которой игрок 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, то он определяет

Бесконечные антагонистические игры(2x2 - 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 (существования). Всякая антагонистическая бесконечная игра двух игроков 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, х),

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

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

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

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

Напомним, что выпуклой функцией 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)

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

Бесконечные антагонистические игры

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

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

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

V = Бесконечные антагонистические игрыБесконечные антагонистические игрыM(x, y),           Бесконечные антагонистические игры

значение yo определяется как решение следующего уравнения

Бесконечные антагонистические игры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 [Бесконечные антагонистические игры;Бесконечные антагонистические игры] = Бесконечные антагонистические игры.

При этом значение х получается равным хo = Бесконечные антагонистические игры. Это же значение получается из решения уравнения

Бесконечные антагонистические игрыБесконечные антагонистические игры = Бесконечные антагонистические игры,

т.к. минимум достигается при 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 найдётся такая, которая является смесью двух существенных стратегий х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 рассмотрим третий случай.

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

М(х, yo) = V,

то есть

(х -Бесконечные антагонистические игры)2 = Бесконечные антагонистические игры.

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

aБесконечные антагонистические игры(0,Бесконечные антагонистические игры) + (1 - a)Бесконечные антагонистические игры(1,Бесконечные антагонистические игры) = 0.

Нетрудно найти

Бесконечные антагонистические игрыБесконечные антагонистические игры

Тогда уравнение для a примет вид :

a - (1 - a) = 0,

откуда a =Бесконечные антагонистические игры. Следовательно, стратегия игрока 1

F(х) = Бесконечные антагонистические игрыJo(х) + Бесконечные антагонистические игрыJ1(х),

а игрока 2

Q(y) = Бесконечные антагонистические игры(y).

Здесь через Бесконечные антагонистические игры(x) обозначена ступенчатая функция

Бесконечные антагонистические игры(x) = Бесконечные антагонистические игры .