Верхние и нижние цены в s-игре

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

.

Рассмотрим процедуру оценки верхних и нижних цен в S-игре. Если первый игрок применяет смешанную стратегию , то значение его гарантированного выигрыша

.

Обозначим через такую стратегию первого игрока, при которой достигает максимума:

(эта нижняя цена игры совпадает с ценой игры в обычной форме в силу эквивалентности S-игры с обычной игрой). Стратегию называют максиминной стратегией первого игрока.

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

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

Таким образом, максиминная стратегия первого игрока определяет нижнюю цену в S-игре:

.

Аналогично стратегия определяет верхнюю цену в S-игре:

.

Выражения для и можно представить в более удобном виде, если воспользоваться теоремой.

Теорема. Если S — произвольная точка m-мерного пространства и — многомерная переменная, то имеет место соотношение

.

Доказательство. Пусть . Рассмотрим частное значение p, соответствующее случаю

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

.

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

.

Это выражение справедливо при любом p. Сопоставляя два последних выражения приходим к соотношению:

. Теорема доказана.

Если воспользоваться доказанной теоремой, то выражение для B(S) можно переписать в виде

.

Из этого равенства вытекают два следствия:

1. , т.е. любая точка имеет по крайней мере одну координату, не меньшую, чем верхняя цена игры;

2. Если в качестве S взять , то получим:

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

Разделительная и опорная гиперплоскость двух выпуклых множеств

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

Для описания некоторых видов выпуклых множеств используется понятие крайней точки. Любая крайняя точка не может располагаться внутри отрезка, соединяющего любые две точки этого множества, а может располагаться на границе этого отрезка (или быть концевой):

: , ,

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

Выпуклым многогранником называется выпуклое множество с конечным числом крайних точек.

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

Теорема 2. Выпуклое множество S является средневзвешенным множеством из его крайних точек.

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