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

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


 

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

80373. Галузеві особливості виробництва і функціонування капіталу. Форми прибутку, процент і рента 110 KB
  Галузеві особливості виробництва і функціонування капіталу. Форми прибутку процент і рента Вступ до теми Метою заняття є визначити сутність понять господарський комплекс галузь сектори економіки господарська одиниця також національне господарство; охарактеризувати особливості функціонування капіталу у виробничій сфері торгівлі та сфері послуг; означити поняття прибуток та рентабельність; зясувати стан розвитку кредитних відносин в Україні. Особливості функціонування капіталу у виробничій сфері торгівлі та сфері послуг. На самостійне...
80374. Суспільне відтворення. Суспільний продукт і його основні форми 154.5 KB
  Будьякий процес виробництва має бути безперервним тобто повинен періодично проходити одні й ті самі стадії. Відтворення постійне відновлення та повторення процесу виробництва. Вищим інтересом підприємства є максимізація прибутку а суспільного виробництва максимізація добробуту населення Підприємство орієнтується на ринковий попит а суспільне виробництво на сукупний попит і т. Суспільне економічне відтворення основане на органічній єдності всіх частин що його утворюють: виробництва розподілу обміну споживання; домогосподарств...
80375. Економічний розвиток. Зайнятість, відтворення робочої сили та їх регулювання державою 185.5 KB
  Зайнятість відтворення робочої сили та їх регулювання державою Вступ до теми Метою сьогоднішнього заняття План 1. Проблеми зайнятості та відтворення робочої сили в Україні. Фактори та показники розширеного відтворення робочої сили. Якщо економіка має недостатньо робочих місць для бажаючих працювати то формується неповна зайнятість: певна кількість робочої сили вимушено залишається без роботи.
80376. Господарський механізм у системі регулювання суспільного відтворення. Держава та її економічні функції 253 KB
  Господарський механізм у системі регулювання суспільного відтворення. Ринковий і державний механізми регулювання економіки. На самостійне опрацювання Форми і методи державного регулювання економіки. Основні теорії державного регулювання.
80377. Сучасні економічні системи. Особливості розвитку перехідних економік 258 KB
  Особливості розвитку перехідних економік Вступ до теми Мета заняття: охарактеризувати економічну систему капіталізму вільної конкуренції зясувати сутність монополістичного капіталізму; означити сутність та моделі змішаної економіки; охарактеризувати економічну систему сучасного капіталізму визначити механізм її функціонування розглянути еволюцію та перспективи розвитку сучасного капіталізму. Моделі змішаної економіки. Механізм функціонування соціалістичної економіки. Особливості ринкової трансформації української економіки.
80378. Економічні аспекти глобальних проблем та їх вплив на економічний розвиток України 121 KB
  Глобальні проблеми — це всезагальні проблеми, що відзначаються загальнопланетарним за своїми масштабами і значенням характером, повязані з життєвими інтересами народів усіх країн, становлять загрозу життю для всього людства і можуть бути вирішенні спільними діями всіх країн світу.
80379. ПРЕДМЕТ І МЕТОД ПОЛІТИЧНОЇ ЕКОНОМІЇ 136 KB
  Метою сьогоднішнього заняття є дослідити основні етапи розвитку та визначити предмет обєкт функції методи політекономії зясувати суть економічних категорій та законів а також визначити місце політичної економії в системі економічних наук. Політична економія як теоретикометодологічна база інших економічних наук. Oikonomi буквально мистецтво ведення домашнього господарства нині застосовують у чотирьох значеннях: народне господарство певної країни групи країн або всього світу; сфера господарської діяльності людини у якій...
80380. Виробництво матеріальних благ і послуг. Продукт і характер праці 138 KB
  Галузі виробництва. Основні фактори суспільного виробництва та їхній взаємозвязок. Соціальна і економічна ефективність виробництва. Метою сьогоднішнього заняття є дослідити процес суспільного виробництва фактори які впливають на процес виробництва; межу виробничих можливостей; продуктивні сили суспільства.
80381. ЕКОНОМІЧНІ ПОТРЕБИ ТА ЕКОНОМІЧНІ ІНТЕРЕСИ 157 KB
  Метою заняття є розкриття суті економічних потреб їх безмежності розгляд закону зростання потреб охарактеризувати корисність блага і суть економічних інтересів. План Економічні потреби суспільства їх сутність і класифікація. Безмежність потреб.