40107

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

Доклад

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

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

Русский

2013-10-15

167.5 KB

34 чел.

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) оптимальные стратегии.


 

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

82828. Індійська філософія 194.13 KB
  Аспект часу в історії філософської думки Індії завжди відігравав лише підпорядковану роль. Тому немає історії індійської філософії, а будь-яка історична періодизація розглядалася як умовність. Але філософія залишається невід’ємною частиною життя індійця - завжди сучасною і завжди життєво...
82829. Гироскопы и их применение 269.5 KB
  В данном случае он представляет собой тяжелое дискообразное тело, способное вращаться с малым трением вокруг закрепленного центра масс. Оправа состоит из двух колец: внутреннего и наружного. Ось вращения гироскопа проходит через его центр масс и закреплена в подшипниках, расположенных во внутреннем кольце.
82830. Взаимосвязь здоровья и работоспособности студентов 41.8 KB
  Цель работы - изучить взаимосвязь здоровья и работоспособности студентов. Уровень здоровья определяется способностью организма адаптироваться к ним. В результате каждая из популяций приобретает свою характерную структуру здоровья определяемую степенью её адаптации к условиям среды.
82831. Право и мораль 48 KB
  Мораль — принятые в обществе представления о хорошем и плохом, правильном и неправильном, добре и зле, а также совокупность норм поведения, вытекающих из этих представлении. Мораль регулирует взаимоотношения между людьми во всех сферах общественной жизни. Она имеет «вездесущий, всепроникающий характер».
82832. Парова машина 555.5 KB
  Першим механічним двигуном що знайшов практичне застосування була парова машина. Спочатку вона призначалася для використання в заводському виробництві але пізніше паровий двигун стали встановлювати на самохідних машинах паровозах пароплавах автомобілях і тракторах.
82833. Перші українські політичні партії 36.72 KB
  Програмовий документ партії проголошував боротьбу проти самодержавства, встановлення парламентського ладу, демократичних свобод та автономії територій, заселених українцями, введення української мови в школах, адміністративних установах.
82834. Особенности проведения ГИС в горизонтальных скважинах 59 KB
  Основные причины различия показаний методов ГИС в вертикальных и сильноискревленных стволах: Влияние пространственного взаиморасположения пласта и скважины Анизотропия свойств. В горизонтальных скважинах проникновения происходит в отдельных проницаемых пропластках непосредственно...
82835. Безработица. Причины образования, последствия 244 KB
  Актуальность темы заключается в том что проблема занятости и безработицы в наши дни становится неотъемлемым элементом жизни России оказывающим существенное влияние не только на социально-экономическую но и на политическую ситуацию в стране.
82836. Генная инженерия 65.36 KB
  Цели создания ГМО продовольственная и сельскохозяйственная организация ООН FO рассматривает использование методов генетической инженерии для создания трансгенных сортов растений либо других организмов как неотъемлемую часть сельскохозяйственной биотехнологии.