КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Верхние и нижние цены в S-игреS-игра Основная теорема антагонистических игр.
Играм, в которых у первого игрока конечное число стратегий, можно дать полезную геометрическую интерпретацию. Пусть задана игра с матрицей платежей . Можно рассмотреть множество векторов: ….. , координаты которых являются столбцами матрицы H.
Игра, заданная множеством точек в m- мерном пространстие, получила название S- игры. Правила S-игры следующие: второй игрок выбирает одну из точек , а первый игрок выбирает i-ую координату этой точки . При этом выигрыш первого игрока, соответственно проигрыш второго, будет равен значению i-ой координаты точки , т.е. :. . Нетрудно видеть, что S-игра эквивалентна обычной игре в нормальной форме , т.к. выбор точки из множества эквивалентен выбору стратегии , а выбор координаты этой точки эквивалентен выбору стратегии . Если число стратегий первого игрока равно двум, то S-игра имеет наглядную геометрическую интерпретацию, Точки множества будут в этом случае точками плоскости (платежная матрица будет иметь вид: , в которой столбцы задают точки с координатами ).
Пример: Рассмотрим игру . Эквивалентная S - игра содержит 5 точек: , , , , . Геометрическое изображение этой игры приведено на рисунке.
Обозначим через выпуклую оболочку конечного множества точек . S-игра эквивалентна обычной игре в чистых стратегиях. Доказывается, что эта эквивалентность сохраняется и для смешанных стратегий. Теорема. Любая смешанная стратегия второго игрока может быть представлена точкой, принадлежащей выпуклой оболочке , и наоборот, любая точка может рассматриваться как некоторая смешанная стратегия второго игрока. Доказательство. Рассмотрим смешанные стратеги игроков и . При использовании этих смешанных стратегий проигрыш второго игрока , где . Обозначим через S точку в m-мерном пространстве с координатами : ; …………………………. . Учитывая, что , это выражение можно записать в виде векторного соотношения . Видим, что S есть не что иное, как средневзвешенное точек с весами , и, следовательно, S есть некоторая точка, принадлежащая выпуклой оболочке . Таким образом, каждой стратегии второго игрока будет соответствовать некоторая точка, принадлежащая выпуклой оболочке , и задание этой точки равносильно заданию смешанной стратегии второго игрока. Справедливо и обратное. Так как любая точка S, принадлежащая выпуклой оболочке , может быть представлена как средневзвешенное точек , определяющих выпуклую оболочку , то для каждой точки найдутся такие веса , задание которых определит смешанную стратегию второго игрока. Теорема доказана. Следствие. Поскольку смешанная стратегия первого игрока остается в S-игре той же самой, что и в обычной игре, из доказанной теоремы следует, что S – игра полностью эквивалентна обычной игре, т.е. любая игра может быть представлена в виде эквивалентной 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.
Дата добавления: 2014-01-06; Просмотров: 325; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |