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


 

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

20399. Искусство защиты в суде присяжных 2.34 MB
  Искусство защиты в суде присяжных: Учеб. заведующий сектором НИИ проблем укрепления законности и правопорядка при Генеральной прокуратуре РФ; заслуженный юрист России доктор юридических наук Книга является своеобразной энциклопедией ведения искусной эффективной и надежной защиты в суде присяжных Рассматриваются социальная ценность духовный и правозащитный потенциал суда присяжных роль здравого смысла и совести как интеллектуальной и нравственной основы этой формы судопроизводства процессуальные тактические и психологические особенности...
20400. Проблемы борьбы с преступлениями в сфере безопасности дорожного движения: уголовно-правовые и криминологические аспекты 626.5 KB
  Мешалкин Проблемы борьбы с преступлениямив сфере безопасности дорожного движения:уголовноправовые и криминологические аспекты Монография Домодедово 2003 ББК 67. Проблемы борьбы с преступлениями в сфере безопасности дорожного движения: уголовноправовые и криминологические аспекты: Монография. В монографии освещаются уголовноправовые и криминологические проблемы борьбы с преступными нарушениями безопасности движения и эксплуатации транспортных средств на основе комплексного анализа сравнительноправового метода исследования....
20401. Оперативно-розыскная тактика и особенности легализации полученной информации в ходе предварительного следствия 362.5 KB
  ПОПОВ Оперативнорозыскная тактика и особенности легализации полученной информации в ходе предварительного следствия Учебнопрактическое пособие ББК 67. В учебнопрактическом пособии рассматриваются оперативнорозыскные мероприятия способы отображения полученной оперативнорозыскной информации в соответствующих документах. Основное внимание уделено технологии превращения оперативнорозыскной информации в криминалистически значимую являющуюся одним из источников доказательств по делу доступную для использования в ходе предварительного или...
20402. Административный процесс и административная ответственность в Украине 1.1 MB
  24 КУоАП; б меры воздействия применяемые к несовершеннолетним ст. 241 КУоАП и в административные взыскания применяемые к юридическим лицам. 24 КУоАП и меры воздействия применяемые к несовершеннолетним согласно ст. 241 КУоАП но и дисциплинарные взыскания в отношении физических лиц за совершение административных проступков согласно ст.
20403. ПРОБЛЕМЫ ИНФОРМАТИЗАЦИИ В МВД РОССИИ 2.52 MB
  Сложность информационного обеспечения процессов принятия решений часто связана с ограниченностью информации ее вероятностным характером негарантированной достоверностью отсутствием у субъекта управления необходимого времени. Информатизация управления преследует следующие цели: повышение научной обоснованности и качества принимаемых решений благодаря использованию математических методов и моделей; повышение гибкости управления его способности реагировать на изменения условий деятельности органов внутренних дел; повышение...
20404. КРИМИНАЛИСТИЧЕСКАЯ ЭКСПЕРТИЗА МАТЕРИАЛОВ, ВЕЩЕСТВ И ИЗДЕЛИЙ 573 KB
  66 M67 ІВ книге рассматриваются научные основы и современное состояние экспертной практики криминалистического исследования материалов веществ и изделий с помощью комплекса аналитических методов спектральных рентгенографических хроматографических и других. ВИТАЛИЙ СТЕПАНОВИЧ МИТРИЧЕВ КРИМИНАЛИСТИЧЕСКАЯ ЭКСПЕРТИЗА МАТЕРИАЛОВ ВЕЩЕСТВ И ИЗДЕЛИЙ ИБ 568 Редактор Л. Советская криминалистика опираясь на достижения естественных и технических наук призвана вооружать следователей самыми современными и эффективными научными приемами...
20405. УГОЛОВНЫЙ ПРОЦЕСС США (досудебные стадии) 840.5 KB
  Пешков УГОЛОВНЫЙ ПРОЦЕСС США досудебные стадии УЧЕБНОЕ ПОСОБИЕ Москва ЗАО Бизнесшкола ИнтелСинтез 1998 махов В. У26 Уголовный процесс США досудебные стадии. Через структуру досудебных стадий уголовного процесса США авторы рассматривают в книге проблемы защиты конституционных прав личности механизм действия ареста и обыска правовой статус и полномочия государственного обвинителя прокурора электронное наблюдение и прослушивание институт сделки о признании вины в уголовном процессе США. На большом фактическом материале проведен...
20406. Право социального обеспечения 1.41 MB
  Право социального обеспечения. ГОРБАЧЕВА ПРАВО СОЦИАЛЬНОГО ОБЕСПЕЧЕНИЯ 3Е ИЗДАНИЕ; ПЕРЕРАБОТАННОЕ И ДОПОЛНЕННОЕ РЕКОМЕНДОВАНО МИНИСТЕРСТВОМ ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ В КАЧЕСТВЕ УЧЕБНОГО ПОСОБИЯ ДЛЯ СТУДЕНТОВ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ ОБУЧАЮЩИХСЯ ПО СПЕЦИАЛЬНОСТИ СОЦИАЛЬНАЯ РАБОТА Москва Книжный мир 2001 {==1} {==2} РАЗДЕЛ 1 ОБЩАЯ ЧАСТЬ ГЛАВА 1 ПОНЯТИЕ СОЦИАЛЬНОГО ОБЕСПЕЧЕНИЯ 1. Понятие социального обеспечения. {==3} В 2030е годы изучением социального обеспечения и социального страхования...
20407. Международное частное право и нотариальная деятельность 1.66 MB
  Вопервых это особенности правоприменительного процесса в котором особое содержание приобретают такие его традиционные стадии как квалификация материального правоотношения выбор применимых норм права и собственно их применение гл. В этом смысле деятельность нотариуса при столкновении с правовой ситуацией имеющей связь с иностранным правопорядком включает несколько стадий: ┌───────────────────────────────────────────────────────────────────────┐ │ Квалификация правовой ситуации как включающий иностранный элемент │...