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

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


 

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

35152. Цели и задачи администрирования 25 KB
  чтобы предоставить пользователям ИС наилучшее возможности по эффективному использованию ресурсов ИС при объективных ограничениях. 3 квалифицируемая помощь пользователям. Здесь задача состоит в том чтобы реализовать в ИС выбранную стратегию ИБ на базе 1 или нескольких политик безопасности обеспечить использование ИС только санкционированным пользователям предусмотреть резервное копирование и восстановления отдельных ресурсов или всей ИС.
35153. Сетевое администрирование. Основные понятия. Сетевые ОС 26.5 KB
  Компьютерные сети – это совокупность компьютеров связанных коммуникационной системой необходимым программным обеспечением позволяющей пользователям и приложениям получить доступ к ресурсам компьютеров сети. клиентская часть средство запроса на доступ к удаленным серверам транспортные средства сетевой ОС обеспечивающие передачу доступных между компьютерами Среди компонентов сети выделяют сетевые службы – это программные модули работающие в установленном режиме которые предоставляют доступ к конкретным ресурсам компа через сеть....
35154. Модели управления доступом к ресурсам 27 KB
  Основными компонентами ролевой модели разрешения права пользователя Разрешение – определяет тип доступа к объекту или его свойству дается пользователям или группам . разрешения применяются к защищенным объектам Рекомендуется назначать разрешения группам. Существуют группы разрешений которые являются основными или обязательными чтение разрешения смена разрешения смена владельца удаление разрешения Существует специальный вид разрешения – владения которое назначается при создании объектов. Какие бы разрешения не были установлены для...
35155. Администрирование сетей Microsoft. Средства анализа состояния сети в Windows 29 KB
  Средства анализа состояния сети в Windows. Базовые принципы: 1 необходимо иметь точную схему и документацию сети: текущая топологическая схема подробная информация обо всем его сетевом оборудовании его конфигурации и использующихся протоколах IPадресах каналах связи WU сервера и сегментах пользовательских локальных сетей. 2 перед изменениями в сети а так же после этих изменений необходимо оценивать работу в сети для того чтобы делать выводы об отрицательном или положительном влиянии внешних изменений . В Windows отдается приоритет...
35156. Службы каталогов. Пространство имен X.500 и протокол LDAP 30 KB
  Службы каталогов. Основная цель объединения компов в вычислительную сеть это обеспечение совместного использования ресурсов при администрировании вычислительной сети 1 из основных задач это реализация оптимального метода организации общих ресурсов одним из методов эффективного управления множеством ресурсов и множеством потребителей вычислительной сети является разветвленная служба каталогов Служба каталогов – это сетевая служба позволяющая получать доступ без знания точного местоположения ресурса При использовании службы каталогов вся...
35157. Active Directory. Доменная модель службы каталогов. Контроллеры домена. Возможные типы серверов в домене 33.5 KB
  Возможные типы серверов в домене. D помогает управлять как принтерами так и крупными специализированными серверами работающими одновременно в нескольких сетях С помощью D осуществляют манипулирование многими компонентами службы каталогов. В D каждый сервер содержит не менее 3 КИ: 1 КИ – это логическая структура 2 КИ – конфигурация 3 КИ – 1 или несколько пользовательских контейнеров Это поддеревья объединенные в катало объектов Доменная модель служб каталогов В D 1 из важных вещей домен – это совокупность компонентов характеризующихся...
35158. Active Directory. Схема каталога. Репликация данных. Управление службой Active Directory 34 KB
  Схема каталога. Управление службой ctive Directory Любой объект каталога принадлежит к некоторому классу объектов со своей структурой атрибутов. Определения всех классов объектов и совокупности правил позволяющих управлять структурой каталога хранится в специальной иерархической структуре – схеме каталога. Схема каталога хранится в отдельном разделе и допускает возможность расширения.
35159. Службы имен. DNS, WINS 29.5 KB
  Службы имен. Помимо IPадреса для сетевых подключений и подключений удаленного доступа в сети TCP IP может потребоваться средство сопоставления имен компьютеров с IPадресами. Существует четыре механизма разрешения имен: служба DNS служба WINS широковещательное разрешение имен и использование файлов Hosts и Lmhosts. В небольших сетях где IPадреса не изменяются сетевые подключения и подключения удаленного доступа могут пользоваться для разрешения имен файлами Hosts и Lmhosts.
35160. Службы имен. Администрирование DNS 28 KB
  Администрирование DNS. DNSсервер представляет собой дополнительную компоненту операционной системы Windows Server 2003. Управление серверами DNS выполняется с помощью соответствующей оснастки Microsoft Mngement Console mmc. Выполнив команду меню Действие – Подключение к DNSсерверу необходимо указать имя компьютера где установлена служба DNS.