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

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


 

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

21014. РАСЧЕТ Параметров антенн 51 KB
  ЗАДАНИЕ 1: Из трех параметров антенны известны два : сопротивление излучения R=4360 Ом КНД=310 Определить значение ненормированной характеристики направленности F . Решение D = 120 F2D;jmax RS Тогда Ответ :F=1061289 ЗАДАНИЕ 2: Определить эффективную площадь антенны по заданным частота f =8000 МГц КНД D = 4555 дБ Решение D = 4pSэфф l2 l = с f =00375 м Тогда Ответ:Sэфф =1961819 м2 ЗАДАНИЕ 3: Известны: эффективная площадь антенны Sэфф = 7200 м2 сопротивление излучения R = 4400 Ом Определить действующую длину антенны Lд...
21015. РАСЧЕТ Параметров антенн. Расчет характеристик и параметров антенн 99.5 KB
  Общие сведения Реальные антенны излучают в окружающее пространство в различных направлениях неодинаково. Зависимость напряженности поля излучаемого антенной измеренная на достаточно большом но одинаковом расстоянии от антенны от углов наблюдения D и j называется характеристикой направленности. Коэффициент направленного действия показывает во сколько раз необходимо увеличить мощность излучения при замене направленной антенны ненаправленной для сохранения прежней напряженности поля в точке приема. Эффективной или действующей площадью Sэфф...
21016. РАСЧЕТ Параметров СИММЕТРИЧНОГО И НЕСИММЕТРИЧНОГО ВИБРАТОРОВ 61 KB
  Донецк 2011 год Цель работы: расчет характеристик и параметров симметричного и несимметричного вибраторов Варианты индивидуальных заданий Задание 1.4 м диаметр симметричного вибратора 2r =6 мм Решение =140186м W=276lg  r68 Ом при l = 0. Определить волновое сопротивление если известны: частота F= 1000 кГц длина плеча l =150 м диаметр несимметричного вибратора 2r =2 мм Решение =300м W=138lg  r34 Ом при l = 0.
21017. РАЗРАБОТКА ОТЧЕТОВ В VISUAL FOXPRO 130 KB
  При разработке отчета выполняются следующие основные операции: создание отчета; настройка отчета; создание среды окружения отчета; сохранение отчета; модификация отчета; просмотр отчета; печать отчета. Кроме вышеуказанных операций при разработке отчета производится создание и настройка объектов размещаемых в отчете. Отдельно также рассмотрены просмотр и печать отчета выполняемые программным путем в ходе работы приложения. Разработка отчета Создание отчета В Visual FoxPro для создания отчетов можно использовать следующие...
21018. РАЗРАБОТКА ЭКРАННЫХ ФОРМ В VISUAL FOXPRO 297.5 KB
  Объектная организация пользовательского интерфейса Формы являются основой пользовательского интерфейса обеспечивая ввод просмотр и изменение информации выполнение служебных и вспомогательных функций. В зависимости от организации диалога формы могут запускаться автономно либо иерархически вызываться друг из друга. Использование среды окружения позволяет упростить связывание элементов формы с БД задать специфичные для формы свойства данных изменить связи между таблицами для работы в форме. Содержит объекты формы.
21019. ВЫБОРКА ДАННЫХ В VISUAL FOXPRO 114 KB
  ОПЕРАТОР ВЫБОРКИ SELECTSQL Оператор выборки SELECT предназначен для описания и исполнения запросов к БД. РАБОТА С КОНСТРУКТОРОМ ЗАПРОСОВ Конструктор Запросов предназначен для создания оператора SELECT путем автоматизированного формирования фраз оператора. Открытие Конструктора Запросов Запуск Конструктора Запросов для создания нового запроса может быть выполнен: а нажатием кнопки New окна проекта при выбранной группе Queries. При выполнении указанных действий открывается окно Конструктора Запросов и окно выбора таблиц.
21020. РЕАЛИЗАЦИЯ БАЗЫ ДАННЫХ В VISUAL FOXPRO 149 KB
  idx предназначенными для хранения созданных для таблицы индексов. Каждый индекс указывает последовательность следования записей таблицы в соответствии с заданным для него ключевым выражением. При наличии главного индекса строки таблицы отображаются и обрабатываются в порядке определяемом данным индексом в противном случае в порядке их физического следования в таблице. Конструктор базы данных позволяет создавать и модифицировать таблицы входящие в базу данных определять для таблиц индексы и требования к данным.
21021. НАЧАЛЬНОЕ ЗНАКОМСТВО С VISUAL FOXPRO 172.5 KB
  ЗАПУСК VISUAL FOXPRO Запуск Visual FoxPro выполняется стандартными для Windows способами. Командная строка используемая при этом может быть дополнена параметрами: а Игнорируются установки записанные в Регистре Windows и имеющийся файл конфигурации C file Определяет имя и путь к файлу конфигурации который должен использоваться при запуске СУБД или приложения Visual FoxPro. D file Определяет имя и путь к файлу библиотеки RunTime DLL L file e Определяет имя и путь к файлу ресурсов R Обновляет информацию в Регистре Windows...