26498

Модели задач принятия решений в стратегических играх

Реферат

Менеджмент, консалтинг и предпринимательство

Постановка задачи в моделях матричной игры. Кроме стратегических игр различают еще статистические и позиционные игры. Позиционные игры предполагают пошаговую последовательность принятия решений причем решение принятое на первом этапе определяет множество возможных решений на последующих. Математическое описание игры предполагает четкое определение или задание следующих факторов: правила действия сторон.

Русский

2013-08-18

29.79 KB

6 чел.

4

Модели задач принятия решений в стратегических играх.

  1.  Классификация задач принятия решений в условиях неопределенности.
  2.  Постановка задачи в моделях матричной игры.

1.Классификация задач принятия решений в условиях неопределенности.

Ситуации, в которых сталкиваются интересы сторон, называются конфликтными.

В качестве примера конфликта могут рассматриваться конкуренция за рынки сбыта, попытки выяснить конфиденциальной информации, действия сторон в условиях конфликта являются стратегией.

Теория стратегических игр – это математическая дисциплина, которая занимается разработкой модели описания конфликтной ситуации и описанием действий участников конфликта. Кроме стратегических игр различают еще статистические и позиционные игры.

В статистических играх решающая сторона – природа. Действия природы не носят осознанный характер. Позиционные игры предполагают пошаговую последовательность принятия решений, причем решение, принятое на первом этапе определяет множество возможных решений на последующих. Основополагающей работой по теории игр являются монография «Теория игр и экономическая деятельность».

Игра должна протекать строго по определенным правилам. Игра – это упрощенная формализованная модель конфликтной ситуации. Математическое описание игры предполагает четкое определение или задание следующих факторов:

- правила действия сторон.

- четкий перечень вариантов действия сторон.

- определение возможных исходов игры для каждого варианта.

- наличие определенных объемов информации для каждой стороны о поведении других участников игры.

Участники игры – это игроки. Действия в процессе игры – это ход. То есть выбор одного из действий. Набор правил, которые однозначно указывают, какой выбор должен сделать игрок называется стратегией. В каждой игре правилами предусматривается определенный выигрыш для игрока в зависимости от применяемой стратегии и предполагаемого исхода. Оптимальной называется стратегия, которая обеспечивает каждому игроку максимально возможный выигрыш и минимально возможный проигрыш.

В зависимости от параметров стратегические игры могут быть классифицированы следующим образом:

  1.  по количеству игроков – парные, множественные.
  2.  по количеству стратегий – конечные, бесконечные.
  3.  по характеру взаимодействия игроков в процессе игры – коалиционные, бескоалиционные, кооперативные.

Если правилами разрешено игрокам объединяться в коалиции, игра называется коалиционной. Если в игре заранее разрешены коалиции, то это будет кооперативная игра.

  1.  по характеру выигрыша – с нулевой суммой и ненулевой суммой. С нулевой суммой предусматривает выполнение условия, при котором суммарный выигрыш всех игроков =0. Игра двух игроков с нулевой суммой называется антагонистической. В таких играх выигрыш одного равен проигрышу другого. В играх с ненулевой суммой все участники игры могут получить выигрыш.
  2.  по количеству ходов в игре различают игры одношаговые и многошаговые. Одношаговая игра заканчивается после одного хода.
  3.  в зависимости от количества информации, которой располагает игрок перед ходом игры бывают с полной информацией и с неполной информацией.

Если каждый игрок перед каждым ходом знает все примененные предыдущим игроком стратегии, то такая игра классифицируется как игра с полной информацией. Игры с полной информацией, как правило, имеют решение.

  1.  В зависимости от принимаемых игроком стратегий игры делятся на игры с чистыми стратегиями или смешанными. Если применяется одна стратегия, то такая игра относится к чистым стратегиям. Если игроки применяют более одной чистой стратегии – смешанные.
  2.  по виду функции выигрыша игры делятся на матричные, биматричные, выпуклые, непрерывные, сепарабельной.
  3.  Матричная игра – конечная игра двух игроков с нулевой суммой, которая представляется в виде платежной матрицы. Элементы платежной матрицы задают выигрыши игрока А, которые равны проигрышу игрока Б. Элементы матрицы А= ||aij||.
  4.  Биматричная игра – это конечная игра двух игроков с ненулевой суммой и в этой игре выигрыши каждого из игроков задаются отдельными платежными матрицами.  
  5.  Непрерывными считаются игры, в которых функция выигрыша является непрерывной функцией в зависимости от выбранной стратегии.
  6.  Если выигрыш представляется выпуклой функцией – выпуклая игра.
  7.  Если функция выигрыша может быть представлена в виде суммы произведений функции одного аргумента, то такая игра называется раздельной или сепарабельной.

2.Постановка задачи в модели матричной игры.

  1.  Решение матричных игр в чистых стратегиях.

Матричная игра – это парная конечная игра с нулевой суммой. Описывается матрицей, которая называется платежной или матрицей выигрыша. В платежной матрице строки соответствуют номерам стратегий первого игрока, а столбцы номерам стратегий второго игрока.

Стратегия

A

Стратегия B

B1

B2

Bj

An

A1

a11

a12

a1j

a1n

A2

Ai

aij

Am

am1

am2

amj

amn

Элемент матрицы Aij– это выигрыш игрока А, если он будет применять стратегию аи, а игрок B будет использовать стратегию bij.

Допустим, игрок А применяет стратегию первую. Тогда независимо от того, какую стратегию использует игрок B, для игрока А гарантируется некий минимальный выигрыш α1, который равен минимуму а1j   A1 α1 min a1j

Для второй стратегии A2 α2 min a2j. Для стратегии mAm αm min amj.

Очевидно, что минимальный гарантированный выигрыш игрока А представляет собой максимальное из всех минимальных значений αi.

То есть значение α будет равно α=. Величина α обеспечивающая минимальный гарантированный выигрыш игрока А называется нижней ценой игры. А стратегия аi0 называется максимильной стратегией.

Таким образом, если игрок А будет придерживаться стратегии Аi0, то его выигрыш будет не меньше, чем величина α.

Задача – построить поведение игрока B. Игрок B за счет выбора оптимальной стратегии должен стремиться к максимальному уменьшению своего проигрыша. В частности, если игрок B применяется стратегию B1, то  B1 β1 max ai1. Аналогично, для стратегии B2 β2 max ai2. Для стратегии nBn βn max ain.

Игрок А стремится минимизировать максимально возможный проигрыш. Таким образом, величина α= – верхняя цена игры, то есть она минимизирует максимально возможный проигрыш и стратегия, которая позволяет решить проблему минимизировать максимально возможный проигрыш называется минимаксная стратегия – Вj0.

Таким образом, применяя максиминную стратегию Аi0, игрок А обеспечивает себе гарантированный выигрыш в размере α. А игрок B, используя минимаксную стратегию, уменьшает свой максимальный проигрыш до величины β.

Существует класс стратегических игр, для которых нижняя цена и верхняя цена равны между собой. Такие игры называются играми с седловой точкой. Седловая точка – это элемент матрицы аij, который одновременно является минимальным в строке и максимальным в столбце. Величина ν, которая определяется как ν=α=β называется чистой ценой игры. Решение такой игры – это совокупность стратегии Аi0 и Бj0, соответствующих седловой точке. Для участников игры выгодно придерживаться оптимальных стратегий. В том случае, если игрок B откажется от стратегии Bj0, то его проигрыш может только увеличиться. Если игрок А начнет искать лучший вариант, он может только уменьшить свой выигрыш.

  1.  Решение стратегический игр в смешанных стратегиях.

При смешанной стратегии игрок использует полный набор вероятностей применения его стратегий.

Допустим, для игрока А определены m стратегий A1...AiAm. И полный набор вероятностей для их применения pi – вероятность применения стратегии Аi.

Для этих стратегий справедливы соотношения pi0, .

Аналогично для игрока B определены n стратегий B1...BjBn и определены вероятности применения этих стратегий qj0, .

Решение игры в чистых стратегиях является частным случаем игры в смешанных стратегиях.

Рассмотрим более подробно алгоритм решения игры в смешанных стратегиях. Стратегия называется активной, если вероятность ее применения не равна 0.

Если задана платежная матрица, то первым шагом решения игры смешанных стратегий является проверка наличия седловой точки. При выполнении требований наличия седловой точки, поиск решения проводится в чистых стратегиях.

Если игра не имеет седловой точки, то следующий шаг этой игры предназначен для упрощения платежной матрицы и в целом игры. Этот шаг состоит в уменьшении количества возможных стратегий.

Считается, что стратегия Аk доминирует над стратегией Аz для всех значений j, где элемент akjazj. Иначе говоря, элементы k-й строки больше либо равны элемента строки z и среди элементов имеется хотя бы один, значение которого больше элементов строки z.

Для игрока B стратегия Br доминирует над стратегией Bs для всех значений i, где элемент birbis.

Стратегия Аk дублирует стратегию Аz или стратегия Br дублирует стратегию Bs, если значения этих величин равны(akjazj, birbis). Е

сли для игрока А стратегия Аk лучше, чем стратегия Аz, то стратегию Аz можно исключить из рассмотрения. Аналогично, то что касается игрока B. Если стратегия Br обеспечивает меньший проигрыш по сравнению со стратегией Bs, то ее тоже можно исключить из рассмотрения. В результате таких преобразований, размерность матрицы сокращается и игра упрощается.

Для преобразованной матрицы находятся оптимальные стратегии. Игрок А выбирает стратегию .

Игрок B выбирает .

Для вычисления этих стратегий можно использовать метод линейного программирования, либо любой известный итерационный алгоритм.

  1.  Решение матричной игры в смешанных стратегиях путем перехода к задаче линейного программирования. 

Предположим, что задано множество стратегий игрока А и множество стратегий игрока B и также определена платежная матрица ||аij||. Для решения такой игры в смешанных стратегиях может быть применена процедура сведения этой игры к двойственной задаче линейного программирования.

Двойственной задачей линейного программирования называется потому, что рассматривается стратегия поведения двух игроков. Эта процедура базируется на одной из основных теорем теории игр, которая известна как теорема Данцеля.

Суть этой теоремы состоит в следующем: каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях. Это решение определяет для игроков А и B оптимальные стратегии, которые имеют следующие свойства:

- отказ игрока А от оптимальной стратегии не увеличивает его выигрыш.

- отказ игрока B от оптимальной стратегии не уменьшает его проигрыш. На основании теоремы Данцеля может быть предложена следующая схема рассуждений, которая позволяет определить значение вероятности pi, при использовании игроком А стратегии Аi. Допустим, что игрок B применяет первую стратегию, то есть стратегию B1, тогда мат. ожидание игрока А будет выглядеть следующим образом MA(B1)=p1 a11+p2 a21+...+pm am1. В соответствии с данной теоремой, значение мат. ожидания должно быть больше или равно цене игры ν. То есть мат. ожидание игрока А есть    

MA(B1)=p11 a11+p2 a21+...+pm am1ν

MA(B2)=p1 a12+p2 a22+...+pm am2ν

MA(Bn)=p1 a1n+p2 a2n+...+pm amnν

p1+p2+…+pm=1 pi≥0


 

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

12168. Свойства в Delphi 83 KB
  Свойства Понятие свойства Помимо полей и методов в объектах существуют свойства. При работе с объектом свойства выглядят как поля: они принимают значения и участвуют в выражениях. Но в отличие от полей свойства не занимают места в памяти а операции их чтения и записи а
12169. Быстродействие процессора 17.54 KB
  Быстродействие процессора Быстродействие процессора это одна из важнейших его характеристик определяющая эффективность работы всей микропроцессорной системы в целом. Быстродействие процессора зависит от множества факторов что затрудняет сравнение быстродействи...
12170. Установка основных компонентов ПК 284.24 KB
  Лабораторная работа №14 Установка основных компонентов ПК 1. Цель работы Научиться собирать все компоненты ПК 2. Теоретические сведения Сборка компьютера подобна игре в Кубик Рубика: пока вы не собрали его в первый раз это кажется невозможным но когда вам покажут...
12171. Изучение конструкции блока питания АТ и АТХ 132.85 KB
  Лабораторная работа №15 Изучение конструкции блока питания АТ и АТХ 1. Цель работы Изучения конструкции блока питания АТ и АТХ 2. Теоретические сведения Назначение и принципы работы блоков питания Главное назначение блоков питания преобразование электрической...
12172. Диагностика работоспособности материнской карты с помощью POST card 35.25 KB
  Лабораторная работа № 16 Диагностика работоспособности материнской карты с помощью POST card 1. Цель работы Научиться пользоваться POST картой 2. Теоретические сведения POST карта тестер для диагностики и ремонта материнских плат ...
12173. Строение, принцип действия и тех.обеспечение ИБП 116.11 KB
  Лабораторная работа №19 Строение принцип действия и тех.обеспечение ИБП 1. Цель работы Изучение принципа работы ИБП 2. Теоретические сведения Составные части ИБП Реализация основной функции достигается работой устройства от аккумуляторов установленных в корпу...
12174. Сборка разборка ПК. Замена основных узлов 652.51 KB
  Лабораторная работа №20 Сборка разборка ПК. Замена основных узлов 1. Цель работы Научиться собирать и разбирать ПК 2. Теоретические сведения Подготовка к сборке компьютера Итак перед вами лежат все необходимые комплектующие вашего будущего системного блока. ...
12175. Работа операционной системы MS-DOS 99.52 KB
  Лабораторная работа № 21 Работа операционной системы MSDOS 1. Цель работы Изучение работы с операционной системой MSDOS 2. Теоретические сведения Работа в MSDOS Как компьютер хранит данные Вы должны знать как компьютер хранит данные в своей памяти. В первую очередь ...
12176. Установка операционной системы семейства Windows 270.69 KB
  Лабораторная работа №22 Установка операционной системы семейства Windows. 1. Цель работы Изучение процесса установки Windows XP 2. Теоретические сведения Windows XP – это одна из самых популярных операционных систем с удобным пользовательским интерфейсом. Она инсталлируетс...