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 переменные

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


 

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

72191. Захист інформації та інформаційна безпека: посібник 998.5 KB
  Інформація, будучи продуктом діяльності, виступає як власність держави, підприємств, установ, організацій, громадян, і, як об’єкт власності, вимагає захищеності. Проте проблема захисту інформації не зводиться тільки до захисту прав її власників, але і містить в собі такий важливий аспект...
72192. БАЗЫ ДАННЫХ: УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС 7.9 MB
  Методические указания к выполнению лабораторных работ являются составной частью раздела «Информационные ресурсы дисциплины» учебно-методического комплекса и содержат описание лабораторных работ, порядок их выполнения и требования к оформлению отчета.
72193. Безопасность жизнедеятельности: Учебно-методический комплекс 503.5 KB
  Безопасность жизнедеятельности БЖД –- наука о сохранении здоровья и безопасности человека в процессе жизнедеятельности; об опасностях среды обитания в том числе производственной среды; о выявлении и анализе опасностей и защите от них.
72194. Высокотехнологичное оборудование предприятий общественного питания: Учебное пособие 2.76 MB
  К механическому высокотехнологичному оборудованию для предприятий общественного питания относятся: ленточные пилы; мясорубки с системой охлаждения в процессе измельчения продукта; иньекторы; вакуумные массажеры-маринаторы; вакуумные упаковочные машины.
72195. Схемотехника аналоговых электронных устройств: Учебное пособие 3.54 MB
  В учебном пособии рассмотрены теоретические основы и принципы действия аналоговых устройств на биполярных и полевых транзисторах. Анализируются основные схемы , используемые в аналоговых трактах типовой радиоэлектронной аппаратуры, приводятся расчетные формулы, позволяющие определить элементы...
72196. Спектроскопические методы. Атомно-эмиссионный спектральный анализ. Фотометрические методы анализа 1.35 MB
  Спектроскопические методы анализа основаны на взаимодействии электромагнитного излучения с веществом. Это взаимодействие сопровождается явлениями из которых наиболее важны испускание поглощение и рассеяние излучения. К оптическим спектральным методам анализа относятся методы...
72197. Синтаксис и семантика языка Паскаль 42.5 KB
  Элементарные конструкции языка Паскаль включают в себя имена, числа и строки. Имена (идентификаторы) называют элементы языка - константы, метки, типы, переменные, процедуры, функции, модули, объекты. Идентификатор в Турбо Паскале может включать в себя: буквы латинского алфавита, цифры символ подчеркивания.
72198. Россия во второй половине 19 века 52 KB
  Важным рубежом в истории России стал крах николаевской системы. В феврале 1855 г. внезапно скончался Николай I. В 1856 г. полной катастрофой для России закончилась Крымская война. За годы войны дефицит государственного бюджета вырос с 14,5 млн. руб. до 307,5; в 1856 г.
72199. Россия в 1917 г. Альтернативы общественного развития 40 KB
  Февральская революция 1917 г. стала эпохальным событием в истории России. Династия Романовых, правившая 304 года, рухнула за неполных 8 дней. До сих пор ученые колеблются в оценке событий 1917 г. Февральская революция была вызвана целым комплексом причин: Первая мировая война.