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

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


 

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

47223. Розробка технології виконання зачіски, стрижки, фарбування 725.12 KB
  Так сукня з декольте всетаки вимагає високої зачіски хоча можна поекспериментувати і зі стилем ретро для розпущених волоссяхвилясті локони укладені чітко по лінії особи ідеальні для декольте. Збираємо волосся назад як для хвоста гарненько перекручуємо проти годинникової стрілки і обертаємо вздовж потилиці і навколо пальця в джгут тепер ховаємо кінці волосся в шов і закріплюємо мушлю шпильками. Деякі дівчата чомусь упевнені що вечірні зачіски на випускнийможливі...
47224. Недвижимость как объект гражданских прав 1.07 MB
  Ульянова юридический факультет кафедра гражданского права и процесса Допущена к защите: зав. Недвижимое имущество как объект гражданского права РФ. Особенности элементноструктурных отношений в недвижимом имущественном комплексе Заключение Библиографический список ВВЕДЕНИЕ Актуальность выбранной темы выпускной квалификационной работы определяется тем что на данный момент вопросы правового положения недвижимого имущества как объекта гражданского права приобрели особую востребованность.Возникновение и развитие недвижимости как объекта...
47226. Оформлення дипломних (курсових) робіт. Вимоги і коментарі 432.5 KB
  Галузь застосування Оформлення дипломних курсових робіт: Вимоги і коментарі мають силу стандарту організації та поширюються на дипломні і курсові роботи які пишуть та захищають в Гуманітарному університеті...
47227. Система автоматичного регулювання та контролю температури в жилому приміщенні 582 KB
  Для визначення ефективності роботи підприємства визначимо кількісний склад витрат які формують собівартість одиниці продукції. Сума амортизаційних нарахувань розраховується за формулою...
47228. Экологизация школьного курса географии в аспекте загрязнения гидросферы 115.5 KB
  Загрязнение воды в настоящее время является проблемой угрожающей всему человечеству. Обеззараживание питьевой воды проводится для уничтожения в загрязненной воде используемой человеком возбудителей заболеваний передающихся водным путем и для предупреждения передачи кишечных инфекций через воду. С питьевой водой в организм человека могут попасть всевозможные микробы возбудители многих инфекционных и паразитарных заболеваний: холера брюшной тиф дракункулез лямблиоз вирусный гепатит полиомиелит дизентерия сальмонеллезы шистосомозы и...
47229. Цифровые лаборатории как средство современного школьного химического образования 362.97 KB
  Компьютерные модели в обучении химии. Компьютерные модели макромира. Компьютерные модели в обучении химии Среди различных типов педагогических программных средств многие авторы особо выделяют те в которых используются компьютерные модели.
47230. Экологизация в учебно-воспитательной работе 70 KB
  Ход мероприятия: 1 Действие На сцене – край леса. А есть еще природы храм – С лесами тянущими руки Навстречу солнцу и ветрам. Ты же видишь мы свои Ученик 3: Привет тебе мой край родной С твоими темными лесами...
47231. РЕКОМЕНДАЦИИ ПО ПОВЫШЕНИЮ РЕЗУЛЬТАТОВ ФИНАНСОВОЙ ДЕЯТЕЛЬНОСТИ СИБИРСКОГО БАНКА СБЕРБАНК РОССИИ 386.12 KB
  Многообразие факторов, оказывающих влияние на результаты деятельности коммерческих банков, определяет необходимость рассмотрения этих результатов в процессе их исследования как многофункциональной и многоцелевой экономической системы.