40107

Теорема о необходимых и достаточных условиях оптимальности смешанных стратегий

Доклад

Менеджмент, консалтинг и предпринимательство

Пусть игра определена матрицей и ценой игры V. оптимальная стратегия 1 игрока х является первой координатой некоторой седловой точки фции выигрыша Мх у. СЛЕДСТВИЕ: Если для смешанных стратегий и числа V одновременно выполняются 1 и 2 то будут оптимальными стратегиями игроков а V цена игры. Докво: умножим 1 на y и просуммируем: умножим 2 на x и просуммируем: Получаем Тогда по следствию Т о седловой точке точка седловая и ...

Русский

2013-10-15

167.5 KB

35 чел.

22. Теорема о необходимых и достаточных условиях оптимальности смешанных стратегий.

Метод сведения решения игр к решению задачи линейного программирования.

Т. [о необходимых и достаточных условиях оптимальности смешанных стратегий]

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

,    (1)

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

    (2). 

Док-во: Рассмотрим с точки зрения 2-го игрока.  

 – оптимальная стратегия 1 игрока  х* является первой координатой некоторой седловой точки  ф-ции выигрыша М(х, у). Тогда по определению седловой точки:

, .

.    

Так как это неравенство выполняется для , то оно выполняется и для   k = 1..n.

Остается    к=1,n. ЧТД.

Вып-ся (1):

,  .

Выделим  смешанную стратегию . Умножим каждое j неравенство на уj и просуммируем. Эти у – неотр.     

.

эта функция имеет седловую точку, выберем  седловую точку (). Для нее вып-ся: . Следовательно

 

В таком случае (по следствию Т о седловой точке) для  х, у   ,     седловая точка  х* – оптимальная стратегия для 1 игр. ЧТД.

СЛЕДСТВИЕ: Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то () будут оптимальными стратегиями игроков, а V– цена игры.

Док-во: умножим (1) на y и просуммируем:

умножим (2) на x и просуммируем:

Получаем

 

Тогда по следствию Т о седловой точке точка () – седловая и  – цена игры.

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

ЧТД.

Метод сведения решения игр к решению задачи линейного программирования. (I метод)

Пусть игра определена матрицей   и ценой игры V. По следствию теоремы

Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то

– оптимальные стратегии игроков   (*)

Требуется, чтобы V > 0. Если все aij > 0, то V > 0. Если  aij < 0, то ко всем aij прибавляем |min aij|, тогда получим эквивалентные игры, то есть новое V = V +|min aij|, а стратегии те же.

1) Рассмотрим левую часть:

V > 0 необходимо здесь, чтобы не менялся знак, так как делим на V.

Обозначим , тогда

решение систем равенств и неравенств – задача оптимизации с целевой функцией, составленной с помощью одного равенства/неравенства и систем ограничений в виде других равенств/неравенств:

(1)

На max, потому что стратегия 2-го игрока  

2) Рассмотрим правую часть (аналогично):

  разделим на V > 0:   (2)

Задачи (1) и (2) – двойственные, т.е. решение одной можно найти из решения другой (в последней симплекс-таблице в строке оценок). Значения линейных форм совпадут:

Обозначим некоторое число  (3)

И в качестве  возьмем  (4)

Покажем, что  – компоненты оптимальных смешанных стратегий игроков, а число V – цена игры с матрицей A.

     – смешанные стратегии. Покажем оптимальность:

Умножив неравенства задач (1) и (2) на V получим (*) при полученных нами  – оптимальное решение, а V – цена игры.

Алгоритм:

  1.  по матрице А составить (1) и (2)
  2.  найти решения
  3.  по (3) найти цену игры, по (4) оптимальные стратегии.


 

А также другие работы, которые могут Вас заинтересовать

69163. Внешние нагрузки на крыло самолета и их распределение 1.13 MB
  На крыло самолета действуют следующие нагрузки: распределенные аэродинамические силы qаэр; распределенные массовые силы конструкции крыла qкр; сосредоточенные силы от грузов агрегатов находящиеся внутри или вне крыла gгр.
69164. Построение эпюр поперечных сил Q, изгибающих М и крутящих моментов Мz в сечениях крыла 696.5 KB
  Построение эпюр поперечных сил Q изгибающих М И крутящих моментов Мz В СЕЧЕНИЯХ КРЫЛА 8. Уравновешиваются эти нагрузки опорными реакциями rф крыла на фюзеляже рис. Площадь каждой iой трапеции численно равна приращению поперечной силы...
69166. Механизмы инвестирования и реинвестирования. Оценка бизнеса 97 KB
  По формам собственности инвестиции подразделяются: частные средства граждан предприятий негосударственной формы собственности неправительственных организаций; государственные финансируемые за счет бюджетных средств различных уровней государственными предприятиями...
69167. Системы налогообложения 114.5 KB
  Налоги оплата услуг государства за обеспечение гражданских прав и свобод граждан страны. Объект налогообложения событие вещь явление существование которых предполагает уплату соответствующего налога например наличие квартиры или наличие прав на земельный...
69168. Прогнозирование в проектах 181 KB
  Прогноз вполне понятно это продукт прогнозирования. объективная необходимость прогнозирования в условиях рыночной экономики обусловлена: Общественным характером производства; Усложнением межотраслевых и региональных связей...
69169. Механизмы управления рисками 145.5 KB
  Понятием риска характеризуется неопределенность связанная с возможностью возникновения в ходе реализации проекта неблагоприятных ситуаций и последствий. Таким образом четко заметна тесная связь риска вероятности и неопределенности.
69170. Механизмы ценообразования 118.5 KB
  Цены мощный рычаг управления экономикой хотя их реальные возможности воздействия на экономику вообще и на уровень жизни в частности намного меньше надежд возлагаемых на цены на ценовой механизм людьми. Это с одной стороны сами цены их виды структура величина динамика изменения...
69171. Проектное финансирование 128 KB
  На практике вклад акционеров в проект чаще осуществляется в виде внутренних займов, чем в виде вклада в уставный капитал. Распространено также реинвестирование прибыли, причем в последнее время в основном с помощью паевых инвестиционных фондов,...