40108

Функция выигрыша в матричных играх без седловой точки. Смешанные и оптимальные смешанные стратегии. Метод сведения решения матричных игр к задаче линейного программирования

Доклад

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

Функция выигрыша в матричных играх без седловой точки. Парная игра с нулевой суммой задается формально матрицей игры матрицей А = {ij} элементы которой определяют выигрыш первого игрока и проигрыш второго если первый игрок выберет iю стратегию а второй jю стратегию. Пара i0j0 называется седловой точкой матрицы решением игры если выполняются условия: mx по столбцу I игрок min по строке II игрок Значение функции выигрыша в седловой точке называется ценой игры. Тогда выигрыш первого игрока при условии что он выбирает...

Русский

2013-10-15

119.5 KB

24 чел.

23. Функция выигрыша в матричных играх без седловой точки. Смешанные и оптимальные смешанные стратегии. Метод сведения решения матричных игр к задаче линейного программирования.

Матричной называют парную игру с нулевой суммой при условии, что каждый игрок имеет конечное число чистых стратегий. Парная игра с нулевой суммой задается формально матрицей игры – матрицей А = {aij}, элементы которой определяют выигрыш первого игрока (и проигрыш второго), если первый игрок выберет i-ю стратегию, а второй - j-ю стратегию. Пара  (i0,j0) называется седловой точкой матрицы (решением игры), если выполняются условия:  (max по столбцу (I игрок), min по строке (II игрок))

Значение функции выигрыша в седловой точке называется ценой игры.

Седловая точка обеспечивает равновесие в игре, но она существует не всегда (н-р, в 2-х пальцевой игре Морра ее нет). В случае, когда нет седловой точки игрокам не выгодно пользоваться одной и той же стратегией, так как в этом случае противник будет выбирать наилучший для себя вариант. Тогда выбор стратегий должен быть вероятностным – выбор осуществляется случайным образом с определенными вероятностями.

Если обозначить через  вероятности выбора i-ой стратегии первым игроком. При этом:

Сумма равна 1, так как он обязан что-то выбрать, у него нет возможности не выбрать

А через  вероятности выбора j-ой стратегии вторым игроком:

то наборы  и  называются смешанными стратегиями первого и второго игроков соответственно. Смешанная стратегия – это набор вероятностей чистых стратегий.

Тогда выигрыш первого игрока при условии, что он выбирает i-ю стратегию, а второй – j-ю стратегию составит .

Функция выигрыша первого игрока  – мат. ожидание выигрыша первого игрока. Соответственно средний выигрыш второго игрока = –M(x, y)

Любая матричная игра имеет решение в смешанных стратегиях, т.е. существует   

Решение задачи (нахождение оптимальных смешанных стратегий) заключается в нахождении седловой точки функции M(x, y) на множестве . Оптимальность понимается в том смысле, что набор устраивает игроков, никто не хочет выбирать другие стратегии.

Тогда  и  называются оптимальными смешанными стратегиями игроков. Задачи заключается в нахождении оптимальных смешанных стратегий игроков и цены игры

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

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

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

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

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

Решение СЛАУ сводится к задаче ЛП.

(1)

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

V меняем на W, так как системы (1)-(2) независимы, поэтому они имеют разные переменные.

(2)

Допустим, решили задачи и получили:

Если в этих решениях последние координаты совпадали бы, то выполнялись бы неравенства:

 

Тогда для каких-то  выполнялось бы следствие теоремы оптимальности.

Покажем двойственность.

Необходимо получить двойственные задачи.

Обозначим

{неравенства (3)-(4) лучше написать в развернутом виде, чтобы была видна двойственность}

  (3)

ЗАМ:

Аналогично для второй задачи:

   (4)

Задачи (3) и (4) – двойственные, т.е. решение одной можно найти из решения другой (в последней симплекс-таблице в строке оценок на местах, соответствующих дополнительным переменным). Значения линейных форм в оптимальной точке совпадут. Поэтому, получив решения , получим

Алгоритм решения:

  1.  по матрице А построить задачи (3) и (4)
  2.  найти решения задач

тогда  – цена игры, оптимальные стратегии игроков:

Преимущества и недостатки метода:

+ сразу получаем решение игры, т.е. не надо переобозначать

+ можно решать игры с любой ценой игры

– больше на 2 переменные

– надо вводить дополнительные переменные, так как


 

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

75586. Вашингтон — столиця США, План-конспект уроку з англійської мови для учнів 9-х класів 74.5 KB
  Обладнання: підручник автентичний текст для читання Wshington D. Т: Tody we re going to tlk bout Wshington D. By the end of the lesson you should be ble: to review lexicl nd grmmr mteril bout the United Sttes nd its lrgest city New York; to identify min ides nd detils from the uthentic text for reding; to tlk bout Wshington D. The clp of the US is Wshington D.
75588. Театр. Вільний час, План-конспект уроку з англійської мови для учнів 9-х класів 71.5 KB
  Активізувати вживання ЛО теми «Вільний час», «Відвідування театру естради». Практикувати учнів у читанні тексту з метою отримання загального уявлення (skimming) та максимально повного й точного розуміння усієї інформації, що в ньому міститься (scanning) Підготувати до самостійного усного висловлювання про відвідування театру.
75589. Відвідування театру естради, План-конспект уроку з англійської мови для учнів 9-х класів 65.5 KB
  Активізувати в мові учнів вживання ЛО теми «Відвідування театру». Підготувати учнів до самостійного висловлювання про відвідування театру естради на основі плану. Практикувати у діалогічному мовленні: конструюванні діалогів за заданою ситуацією та з урахуванням міжрольових взаємодій комунікативних партнерів...
75590. Музичні захоплення, План-конспект уроку з англійської мови для учнів 9-х класів 90.5 KB
  Обладнання: підручник вікторина Pop Music Quiz НО1 текст для читання My fvourite singer Elvis Presley king of rock nd roll HO2 Fill in the tble HO3 Write biogrphy of your own fvourite pop strrdquo;HO4 тексти 1 2 для позакласного читання з серії Pop rt з молодіжних журналів НO5 НO6. Т: We re going to tlk bout your fvourite music musicins singers nd pop groups By the end of the lesson you should be ble: to tlk bout your fvourite music musicins singers nd pop groups; to conduct your own dilogues using the given one s n...
75591. Музичні захоплення. Мій улюблений співак 63.5 KB
  Обладнання: підручник текст і запис пісні Yesterdy групи Betles НО1 текст цієї пісні з пропускамНO2 текст для аудіювання The Betles НО3 True or Flse HO4 HO5. Предявлення тексту для аудіювання The Betles. Т: Wht do you think Do you know the fmous group The Betles Wht hits of the Betles do you like re the Betles still populr in Englnd Why 2 WhileListening ctivities. Н03: The Betles The Betles becme ntionlly fmous in Englnd in October 1962 when their first single record Love me do entered the Hit Prde t number 27.
75592. Музичні захплення, План-конспект уроку з англійської мови для учнів 9-х класів 59.5 KB
  Практикувати учнів у читанні тексту з метою отримання загального уявлення (scanning) та з метою точного й повного розуміння усієї інформації, що в ньому міститься (skimming). Навчати висловлюванню за змістом прочитаного тексту.
75593. Шекспір — видатний англійський письменник 69 KB
  Обладнання: підручник автентичний текст для читання Shkespere HO1 True or Flse H02 nswer the questions H03 Strip story H04 текст для позакласного читання про англійських або американських акторів на вибір учителя. Т: The topic of our tody\'s lesson is Shkespere the gretest English writer...
75594. Відвідування кінотеатру 71 KB
  Активізувати у мові учнів ЛО теми «Відвідування кінотеатру». Практикувати учнів у читанні тексту з метою отримання загального уявлення (skimming) та з метою максимально повного й точного розуміння всієї інформації, що міститься в тексті (scanning).