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

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

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

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

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

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

,

то x_o не может входить в точки спектра оптимальной стратегии игрока 1; если F(х) – оптимальная стратегия игрока 1и для некоторого y_o

,

то y_o не может быть точкой спектра оптимальной стратегии игрока 2.

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

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

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

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

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

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

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

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

f(a₁ х₁ + a₂ х₂ ) £a₁ f(х₁ ) + a₂ f(х₂ ),

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

Если для a₁ ¹ 0, a₂ ¹ 0 всегда имеет место строгое неравенство

f(a₁ х₁ + a₂ х₂ ) < a₁ f(х₁ ) + a₂ f(х₂ ),

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

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

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

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

V = M(x, y),

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

M(x, y_o ) = V.

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