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

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


 

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

9362. Розробка принципової схеми гідро- та пневмоприводів і систем гідро пневмоавтоматики з раціональним вибором робочого середовища 208 KB
  Вступ Курсова робота з дисципліни Гідравліка, гідро- та пневмоприводи є необхідним практичним додатком до теоретичного курсу, а також підготовчим етапом до виконання курсового та дипломного проектування при розробці гідроприводу та пневмориводу мета...
9363. Разработка цифрового измерителя температуры 178.5 KB
  ТЕМА: Разработка цифрового измерителя температуры В качестве цифрового датчика температуры в схеме стенда используется цифровой датчик DS18B20 фирмы DallasSemiconductor (D1), который с помощью однопроводного интерфейса подключен к разряду 7 по...
9364. Минералы и горные породы - строительные материалы природы 101.5 KB
  Минералы и горные породы - строительные материалы природы. Минералы - природные тела, однородные по химическому составу и природным свойствам, образующиеся в глубинах и на поверхности Земли. Известно около 3000 видов минералов. Наиболее распрос...
9366. Технологический процесс ремонта, корпус пневмоцилиндра, дефектоскопия, электролитическое осаждение, механическая обработка, себестоимость, комплект технологической документации 438 KB
  Реферат Объектом разработки является технологический процесс ремонта корпуса пневмоцилиндра. Цель работы - усовершенствовать технологический процесс ремонта заданной детали, произвести необходимые расчеты, составить пояснительную записку, оформить т...
9367. Учет основных средств ООО Транс сервис 632.5 KB
  Введение Развитие различного вида предпринимательства сопровождается возрастанием роли бухгалтерской информации в управлении, контроле и анализе предпринимательской деятельности. Своевременность ее получения, соответствующее качество и достоверность...
9368. Устройство дистанционного управления 112.5 KB
  Устройство дистанционного управления Исходные данные: Микроконтроллер осуществляет прием кодовых последовательностей от пульта дистанционного управления, дешифрацию команд и управление 8-ю устройствами по принципу вкл/выкл. Обеспечить индикацию сост...
9369. Повышение уровня проходимости амфибийно-вездеходных транспортных средств путем использования нетрадиционных пневмодвижителей сверхнизкого давления 255 KB
  Повышение уровня проходимости амфибийно-вездеходных транспортных средств путем использования нетрадиционных пневмодвижителей сверхнизкого давления Общая характеристика работы. Актуальность темы диссертации определяется необходимостью разработк...