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


 

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

80696. ЗНАЧЕНИЕ НАЛОГОВЫХ ВОПРОСОВ 77 KB
  Иначе трудно бы было понять почему в условиях полной свободы движения капиталов компании продолжают действовать в странах с уровнем корпорационного налога в 450 и не перебираются в налоговые гавани где ставки этого налога 25 или он вовсе не применяется. Но даже и для базовых компаний не осуществляющих никакой деятельности в стране своего местонахождения а только управляющих активами обслуживающих или контролирующих деятельность в д ругих странах размещение в стране с нормальным уровнем налогообложения...
80697. Налоги, включаемые в цену продукции 58.96 KB
  Объект налогообложения обороты по реализации товаров работ услуг; товары ввозимые на территорию России; обороты по реализации всех товаров как собственного производства так и приобретенные на стороне; обороты товаров работ услуг внутри предприятия для нужд собственного потребления затраты по которым не относятся на издержки производства и обращения а так же реализуемые своим работникам; обороты по передаче безвозмездно или с частичной предоплатой товаров работ услуг другим предприятиям или физическим лицам; обороты по...
80698. Налог на пользователей автомобильных дорог 76 KB
  Объект налогообложения Объектом налогообложения является выручка полученная от реализации продукции работ услуг и сумма разницы между продажной и покупной ценами товаров реализованных в результате заготовительной снабженческосбытовой и торговой деятельности. По плательщикам налога осуществляющим реализацию товаров продукции работ услуги по ценам не выше фактической себестоимости для целей налогообложения применяются рыночные цены на аналогичные товары продукцию работы услуги сложившиеся на момент реализации но...
80699. Налог на реализацию горюче-смазочных материалов 56.5 KB
  Плательщики налога Плательщиками налога на реализацию горюче смазочных материалов автобензин дизельное топливо масла дизельные масла для карбюраторных двигателей масла для карбюраторных и дизельных двигателей сжатый и сжиженный газ используемый в качестве моторного топлива являются юридические лица предприятия учреждения организации объединения далее организации граждане осуществляющие предпринимательскую деятельность без образования юридического лица далее предприниматели реализующие указанные материалы....
80700. The problem of linguistic meaning. Types of linguistic meaning. Main approaches to the definition of meaning 37.66 KB
  Semasiology (or semantics ) is a branch of linguistics which studies meaning. There are three main categories of definitions which may be referred to as: -analytical or referential definition of meaning - functional or contextual definition of meaning,- operational or information-oriented definition of meaning
80701. Synonymy 32.44 KB
  Synonyms are the words of the same part of speech different in their sound-form but similar in their meaning and interchangeable at least in one context. There are very few perfect synonyms. They usually differ in some aspect of their meaning — according to this they can be ideographic
80702. Antonymy (semantic opposition). Antonyms are words which express opposite or contrasting meanings 32.49 KB
  Antonyms are subdivided into. Gradable — represent the extremes of the quality. There are often adjectives that can be placed on the scale between them (hot-cold). Contradictory-complimentary — cannot exist without each other (dead-alive; leave-stay)3. Conversive — describe opposite attributes of the same situation (to buy-to sell — when one buys another sells)
80704. THE MORPHEMIC STRUCTURE OF THE WORD. TYPES OF MORPHEMES. ALLOMORPHS nd mening: they dont possessed grmmticl mening. 30.83 KB
  The morpheme is the smallest meaningful unit of form. A form in these cases a recurring discrete unit of speech. Morphemes occur in speech only as constituent parts of words, not independently, although a word may consist of single morpheme. Even a cursory examination of the morphemic structure of English words reveals that they are composed of morphemes of different types: root-morphemes and affixational morphemes. Words that consist of a root and an affix are called derived words or derivatives and are produced by the process of word building known as affixation (or derivation).