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

Пусть — игра, а — ее смешанное расширение.

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

Обозначим гарантированное значение выигрыша первого игрока при стратегии p через A(p):

.

Далее первого игрока будет интересовать выбор из всех возможных стратегий такой, при которой его гарантированный выигрыш будет максимальным:

.

Стратегия называется максиминной стратегией первого игрока в смешанном расширении игры.

Для второго игрока рассуждения аналогичные. Применяя свою смешанную стратегию , его максимальный проигрыш будет равен:

.

Далее второго игрока будет интересовать выбор из всех возможных стратегий такой, при которой его гарантированный проигрыш будет минимальным:

.

Стратегия является минимаксной стратегией второго игрока в смешанном расширении игры.

Таким образом, называется нижней ценой игры в смешанном расширении, а называется верхней ценой игры в смешанном расширении.

Теорема. Если имеется игра , а — ее смешанное расширение, то

a) ;

b) ;

c) ;

d) ;

e) .

Условие «а» говорит о том, что при выборе первым игроком любой смешанной стратегии значение его гарантированного выигрыша равно значению гарантированного выигрыша при использовании вторым игроком только чистых стратегий. Согласно условию «b» нижняя цена игры при смешанных стратегиях первого игрока не меньше нижней цены игры при чистых стратегиях, т.е. что существует смешанная стратегия, которая во всяком случае не хуже оптимальной чистой стратегии. Пункты «c»и «d» содержат аналогичные утверждения в отношении второго игрока. Пункт «e» означает, что нижняя цена игры при использовании смешанных стратегий не превосходит верхней цены игры , т.е. при использовании наилучших смешанных стратегий гарантированный выигрыш первого игрока не превзойдет обеспеченного проигрыша второго игрока.

Доказательство – Коршунов Ю.М. Математические основы кибернетики.

Следствие. .

Из этого следует, что если игра Г имеет цену, т.е. (это имеет место для игр с седловой точкой), то , т.е. игра G также имеет цену. Поэтому оптимальная стратегия в игре Г является оптимальной и в игре G. В этом случае игру G можно не рассматривать, а оптимальные стратегии игроков находить методом, описанным для игр с седловой точкой.

Но игра G была введена для анализа таких игр, у которых . Применение смешанных стратегий позволяет найти цену игры и оптимальные стратегии игроков в этом случае.

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

 

Основная теорема антагонистических игр.

S-игра

 

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

Можно рассмотреть множество векторов:

….. .

Игра, заданная множеством точек , получила название S-игры.

Правила S-игры следующие: второй игрок выбирает одну из точек , а первый игрок выбирает i-ую координату этой точки . При этом выигрыш первого игрока, соответственно проигрыш второго, будет равен значению i-ой координаты точки , т.е. :

.

Нетрудно видеть, что S-игра эквивалентна обычной игре в нормальной форме , т.к. выбор точки из множества эквивалентен выбору стратегии , а выбор координаты этой точки эквивалентен выбору стратегии .

Если число стратегий первого игрока равно двум, то S-игра имеет наглядное геометрическое интерпретацию, т.к. точки множества будут в этом случае точками плоскости (платежная матрица имеeт вид:

, в которой столбцы определяют точки с координатами ).

 

Пример:

Рассмотрим игру . Эквивалентная S - игра содержит 5 точек: , , , , . Геометрическое изображение этой игры приведено на рисунке.

 

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

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

Доказательство. Рассмотрим смешанные стратеги игроков и . При использовании этих смешанных стратегий проигрыш второго игрока

, где .

Обозначим через S точку в m-мерном пространстве с координатами :

;

………………………….

.

Учитывая, что , это выражение можно записать в виде векторного соотношения

.

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

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

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

Следствие. Поскольку смешанная стратегия первого игрока остается в S-игре той же самой, что и в обычной игре, из доказанной теоремы следует, что S – игра полностью эквивалентна обычной игре, т.е. любая игра может быть представлена в виде эквивалентной S-игры.