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

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


 

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

54738. Суд над Р.Раскольниковым по роману Ф.М.Достоевского «Преступление и наказание» 62 KB
  Действующие лица деловой игры: Судья Присяжные 3 человека Родион Раскольников Следователь Порфирий Петрович Адвокат Прокурор Разумихин Соня Мармеладова Доктор Зосимов Хозяйка квартиры Раскольникова Ход урока. Спустя 5 месяцев после совершенного Раскольниковым преступления состоялся суд над главным героем. Сегодняшний урок будет проходить в форме деловой игры в форме суда над Раскольниковым. Заседание посвящено расследованию причин убийства Алены Ивановны и ее сестры Лизаветы господином Раскольниковым.
54739. Конспект урока Железы внутренней секреции 86.5 KB
  Образовательная цель: активизация учебного процесса в направлении повышения его эффективности придания уроку современных динамичных форм раскрыть основные свойства гормонов. Железы внутренней секреции. Я хочу послушать ваше мнение как вы прокомментируете увиденное Ученик: профессор Преображенский занимался проблемами омоложения и с этой целью желая приостановить старение организма пытался пересаживать половые железы. Но почему он пересадил гипофиз Учитель: вопрос очень хороший поскольку...
54740. Текстовый редактор “Word” 37.5 KB
  Цели урока: Образовательные обеспечить повторение понятия ТР форматирование редактирования правила набора текста работа с выделенным фрагментом текста; продолжить формировать навыки и умения работы в ТР; 3 восполнить следующие пробелы: правила набор текста работа с выделенным объектом. Этапы урока. Организация начала урока.
54741. Открытие явления электромагнитной индукции 36 KB
  Проблема: А может ли магнитное поле породить ток Осуществим ли лозунг который ставили перед собой ученые 19 века Слайд №2: Превратить магнетизм в электричество Выдвижение цели урока осуществляется совместно с учениками: Выяснить экспериментальным путем возможности или невозможности создания тока магнитным полем. ЭТАП 3 Анализ результатов: создание слайда №6 способы получения тока с помощью магнитного поля. Примерные рассуждения учащихся: слайд3 слайд4 слайд5 Гальванометр...
54742. Понятие средних издержек. Предельные издержки 33.75 KB
  Средние издержки – это валовые издержки (валовые издержки – это сумма постоянных и переменных издержек. Они представляют собой денежные расходы фирмы на производство продукции), приходящиеся на единицу продукции.
54743. Совокупный, средний, предельный доход предприятия 23.99 KB
  Доход – денежная оценка результатов деятельности фирмы (или отдельного физического лица) в форме денежной суммы, поступающей в ее непосредственное распоряжение, т.е. это выручка от реализованной продукции (услуги) в течение какого-либо периода
54744. Определение оптимального объема производства 17.2 KB
  Предприятие, как правило, стремится получить максимальную прибыль. При прочих равных условиях наибольшее влияние на максимизацию прибыли оказывают объем производства (реализации) продукции и цена выпускаемого товара.
54745. Прямоугольная система координат. Векторы в пространстве. Координаты вектора 377.5 KB
  Задачи урока: Научить находить координаты вектора. Координаты вектора Прямые x y z называются координатными осями или осями координат точка их пересечения O началом координат а плоскости xOy xOz и yOz координатными плоскостям. Аналогично можно определить координаты y и z точки .
54746. Россия в период социального многообразия (14 декабря 2011г) 1.78 MB
  Большинство людей в нашем открытом и взаимозависимом обществе всё чаще встречается с теми, кто явно отличается от них. Раньше, несколько столетий назад, вообще контакты с людьми других национальностей были эпизодическими, они были в диковинку. Теперь эти контакты постоянны и в реальном мире, и в виртуальной среде. Они отличаются и привычками, и внешним видом, и политическими убеждениями.