40107

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

Доклад

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

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

Русский

2013-10-15

167.5 KB

28 чел.

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


 

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

68258. ОБЛІКОВО-АНАЛІТИЧНЕ ЗАБЕЗПЕЧЕННЯ УПРАВЛІННЯ БІОЛОГІЧНИМИ АКТИВАМИ САДІВНИЦТВА 229 KB
  Серед Європейських держав Україна за своїм грунтово-кліматичним потенціалом має значні переваги для розвитку інтенсивного садівництва та створення його експортного потенціалу. Такі негативні тенденції створюють передумови втрати країною потенціалу садівництва і ставлять внутрішній ринок плодів і ягід у повну залежність від їх імпорту.
68259. РЕЧОВІ ПРАВА НА ЧУЖЕ ЖИТЛО 185 KB
  Чинне цивільне законодавство України передбачає речові права на чуже майно, об’єктом яких може бути житло. Основним серед таких прав є право членів сім’ї власника житла на користування цим житлом, що закріплене в ст. 405 Цивільного кодексу України, і являє собою різновид особистого сервітуту.
68260. ПРОБЛЕМА РОЗВИТКУ ТВОРЧИХ ЗДІБНОСТЕЙ МОЛОДШИХ ШКОЛЯРІВ У ХУДОЖНІЙ СПАДЩИНІ УКРАЇНСЬКИХ ПЕДАГОГІВ (др. пол. ХІХ - ХХ ст.) 180.5 KB
  Поліспектральність і багатовекторність процесу відродження національної освіти особливо її початкової ланки висуває специфічні вимоги до всебічного розвитку особистості молодшого школяра на засадах орієнтації на унікальність і неповторність кожної дитини.
68261. ЗАСТОСУВАННЯ ФОТОТЕРМОАКУСТИЧНОГО ПЕРЕТВОРЕННЯ ДЛЯ ЗАДАЧ ДЕФЕКТОСКОПІЇ 2.47 MB
  Мета і задачі дослідження: Розробити теоретичні основи ФТА дефектоскопії шляхом створення математичної моделі яка описує процеси перетворення оптичної енергії в механічну для тришарового пружного пакету до якого прикріплено четвертий пєзопружний шар в стаціонарному режимі...
68262. ІНТЕГРОВАНА СИСТЕМА КОНТРОЛЮ ЕФЕКТИВНОСТІ ВИКОРИСТАННЯ ЕЛЕКТРИЧНОЇ ЕНЕРГІЇ У ВИРОБНИЦТВІ 466 KB
  Метою дисертаційного дослідження є створення методичних основ побудови інтегрованих систем контролю ефективності використання електричної енергії в суспільному виробництві які ґрунтуються на поєднанні удосконалених методик нормування питомих витрат електроенергії та удосконалених систем...
68263. ОСОБЛИВОСТІ НЕОДНОРІДНИХ СТРУКТУР У ФЕРИТ-ГРАНАТОВИХ ПЛІВКАХ 417 KB
  Спінпереорієнтаційний фазовий перехід першого роду від осьової фази до кутової фази відбувається шляхом зародкоутворення нової фази у доменній межі початкової фази. Особливості СПФП пояснено уявленням про зародок нової фази як про статичний солітон розміри якого зростають зі зміною співвідношення між константами анізотропії.
68264. ПРОБЛЕМА ШКІЛЬНОГО ПІДРУЧНИКА У ПЕРІОДИЧНИХ ФАХОВИХ ВІТЧИЗНЯНИХ ВИДАННЯХ (50-ті рр. ХХ ст. – поч. ХХІ століття) 218 KB
  Зміст освіти знаходить своє відображення в шкільних підручниках через що вони теж відповідно змінюються. Однією з багатьох проблем які необхідно розвязати педагогічній науці на сучасному етапі є створення якісного шкільного підручника нового типу за змістом функціями принципами структурування змісту тощо.
68265. Алопластика післяопераційних ускладнених вентральних гриж великих розмірів 262.5 KB
  Однією з найбільш дискутабельних і актуальних проблем планової та ургентної хірургії на сьогоднішній день є лікування й реабілітація хворих на післяопераційні вентральні грижі. Зростання захворюваності на післяопераційні вентральні грижі у першу чергу пов’язано із застосуванням традиційних...
68266. АДМІНІСТРАТИВНЕ СУДОЧИНСТВО У СПРАВАХ, ПОВ’ЯЗАНИХ ІЗ ВИБОРЧИМ ПРОЦЕСОМ 154 KB
  Захист виборчих прав свобод і законних інтересів забезпечується наявністю регламентованої адміністративної та судової процесуальної форми. Судовий порядок вирішення виборчих спорів забезпечує незалежність та неупередженість прийняття рішень гарантує їх обєктивність.