Теорема о минимаксе

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

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

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

: , ,

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

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

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

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

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

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

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

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

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

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

Для доказательства этого неравенства достаточно найти такую смешанную стратегию первого игрока, при которой для всех имеет место

. (1)

Действительно, если (1) имеет место, то

. Таким образом, доказательство теоремы будет сводиться к доказательству неравенства (1).

Доказательство. Рассмотрим множество T, состоящее из точек таких, что . На рисунке показана область T для двумерного пространства, которая в данном случае имеет вид прямоугольного клина с вершиной, лежащей на прямой, проведенной из начала координат под углом к оси абсцисс. Рассмотрим некоторые свойства множества T.

Множество T является выпуклым. Рассмотрим произвольные точки и этого множества. Уравнение отрезка, соединяющего эти две точки, будет иметь вид:

, , .

Проектируя это уравнение на i-ую ось и учитывая теорему об максимальном элементе выпуклого множества, получаем

(2). Следовательно, любая точка рассматриваемого отрезка принадлежит T и множество T выпуклое.

Множество T не пересекается с множеством . Это следует из того, что любая точка множества имеет по крайней мере одну координату, большую или равную (следствие 1 из теоремы «Если S — произвольная точка m-мерного пространства и — многомерная переменная, то имеет место соотношение .»), а значит T и не имеют общих точек.

Поскольку T и — выпуклые непересекающиеся области, то существует разделяющая их гиперплоскость такая, что множество T и окажутся в разных полупространствах, определяемых этой гиперплоскостью. Следовательно, существует такое и число c, что уравнение (3) будет уравнением разделяющей гиперплоскости, причем

для ; для . (4)

Покажем, что . Пусть — точка, у которой i-ая координата равна 1, а остальные равны малой величине . Рассмотрим точку . Так как ее максимальная координата равна (следствие 2 из теоремы «Если S — произвольная точка m-мерного пространства и — многомерная переменная, то имеет место соотношение »), то точка . Следовательно,