Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Когда в июне 2013 года Николай Леонидович Сомов был избран депутатом Самарской Губернской Думы, за короткий срок он сумел не просто активно включиться...полностью>>
'Документ'
Школьная Лига КВН Санкт-Петербурга, Дом детского творчества «Преображенский», ГБОУ ЦО «Санкт-Петербургский городской Дворец творчества юных» приглашаю...полностью>>
'Документ'
Понятие культуры. Роль духовной культуры в жизни общества и человека. Проблема диалога культур и исторического самоопределения Беларуси в глобализирую...полностью>>
'Документ'
Определение общества. Общество как целостная система. Общественные отношения. Возникновение и развитие общества. Признаки общества. Важнейшие институт...полностью>>

Главная > Решение

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Лабораторная работа № 3

Тема: Теория игр и принятие решений в условиях неопределенности

Цель: Приобрести навыки поиска рациональных решений в условиях неопределенности вызванной конфликтом интересов.

Порядок выполнения работы:

1) Задание 1: решение игры с заданной матрицей платежей

  1. Изучение теории.

  2. Определение по заданной матрице платежей нижней и верхней цены игры. Существует ли в игре равновесие в чистых стратегиях?

  3. Сведение задачи теории матричных игр к задаче линейного программирования (ЛП)

  4. Решение задачи ЛП с помощью пакета MS Excel (определение цены игры и оптимальной стратегии для каждого из игроков).

2) Задание 2: решение игры

  1. Изучение примеров.

  2. Построение матрицы платежей.

  3. Сведение задачи теории матричных игр к задаче ЛП

  4. Решение задачи ЛП с помощью пакета MS Excel и ответы на дополнительные вопросы задания.

3) Составление отчёта по лабораторной работе, в котором для каждого задания представляется:

  • формулировка задания;

  • снимки экрана монитора, содержащие матрицу игры, формулировку задачи ЛП, найденное решение (цену игры и оптимальные стратегии игроков) и ответы на дополнительные вопросы.

Теория

В теории игр рассматриваются ситуации, связанные с принятием решений, в которых два или более разумных противника имеют конфликтующие цели. Само слово «игра» применяется для обозначения некоторого набора правил и соглашений, составляющих данный вид игры, например: футбол, карточная игра, шахматы. Эти ситуации принятия решений отличаются от рассмотренных ранее, где природа, хотя и могла находиться в различных состояниях, но не преследовала каких-либо целей и, следовательно, не рассматривалась в роли соперника.

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

Для игр характерна неопределенность результата. Причины или источники неопределенности относятся к трем группам:

1) Комбинаторные источники (шахматы);

2) Случайные факторы (игра в орлянку, кости, карточные игры, где случаен расклад);

3) Неопределенность имеет стратегическое происхождение: игрок не знает, какого рода образа действий придерживается его противник. Здесь неопределенность исходит от другого лица.

Далее мы будем рассматривать игровые модели конфликтов, в которых участвуют два противника, каждый из которых имеет конечное число вариантов выбора решений. С каждой парой решений связан платеж, который один из игроков выплачивает другому (т.е. выигрыш одного игрока равен проигрышу другого). Такие игры принято называть конечными играми двух лиц с нулевой суммой.

В игре принимают участие два игрока: A и B. В распоряжении каждого игрока имеется конечное множество вариантов выбора — стратегий. Пусть — множество стратегий игрока A, — множество стратегий игрока B. С каждой парой стратегий связан платеж, который один из игроков выплачивает другому. Т.е., когда игрок А выбирает стратегию (свою i-ю стратегию), а игрок В — стратегию , то результатом такого выбора становится платеж . Поскольку стратегий конечное число, то платежи образуют матрицу размерности n x m, называемую матрицей платежей (или матрицей игры). Строки этой матрицы соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В.

Пусть два игрока А и В играют в игру, основанную на подбрасывании монеты. Игроки одновременно и независимо друг от друга выбирают герб (Г) или решку (Р). Если результаты двух подбрасываний монеты совпадают (т.е. ГГ или РР), то игрок А получает один доллар от игрока В. Иначе игрок А платит один доллар игроку В.

Для каждого из игроков возможны 2 варианта результатов: выпадения герба или решки, следовательно матрица платежей имеет размерность 2 х 2.

ВГ

ВР

АГ

АР

Если результаты двух подбрасываний (т.е. подбрасываний монеты игроками А и В) совпадают, то платеж в 1 доллар получает игрок А. Будем строить матрицу игры, с точки зрения игрока А, т.е. его выигрыши оценивать как положительные, а проигрыши — как отрицательные (с точки зрения В все будет наоборот и мы вполне могли бы построить матрицы платежей, ориентируясь на его точку зрения).

ВГ

ВР

АГ

1

АР

1

Если результаты подбрасывания различаются, то доллар получает В, значит платеж А равняется –1 доллар. В игре с нулевой суммой выигрыш игрока B равносилен проигрышу игрока A и равен поэтому .

ВГ

ВР

АГ

1

–1

АР

–1

1

Т.о., мы построили матрицу игры, описывающую заданную ситуацию. Предполагается, что матрица игры обоим игрокам известна.

Исход игры зависит от поведения обоих игроков, которое основывается на выборе правильных стратегий игры, т.е. таких вариантов, при которых так платеж данному игроку будет наибольшим. Однако, в отличие от методов оптимизации, в теории игр игрок не может просто стремиться к максимуму, он вынужден считаться с действиями соперника. Существенно, что ни один из партнеров не знает, какую стратегию применит его противник. Таким образом, имеет место ситуация полной неопределенности, при которой теория вероятности также не может помочь игрокам в выборе решения.

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

В1

В2

В3

А1

2

-3

4

А2

-3

4

-5

А3

4

-5

6

Т.е., А предполагает, что В умен и будет вести себя так, чтобы доставить противнику набольшие неприятности. Тогда, при выборе 1-й стратегии, А может рассчитывать лишь на худший для себя результат –3. При выборе 2-й и 3-й стратегий он может рассчитывать на –5. Из всех возможных стратегий целесообразнее выбрать ту, что принесет максимальный возможный доход (минимальные возможные убытки, как в нашем случае). В нашем случае это стратегия 1.

Принято говорить, что при таком образе действий игрок А руководствуется принципом максиминного выигрыша. Этот выигрыш определяется формулой

.

Величина называется нижней ценой игры, максиминным выигрышем, или сокращенно максимином. Это тот гарантированный минимум, который игрок А может себе обеспечить, придерживаясь наиболее осторожной стратегии.

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

.

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

— больше этой суммы игрок В точно не потеряет. Величина называется верхней ценой игры, иначе — «минимаксом».

Принцип осторожности, который определяет выбор партнерами стратегий, соответствующих максиминному выигрышу или минимаксному проигрышу, часто называют принципом минимакса, а стратегии, вытекающие из этого принципа, — минимаксными стратегиями. Можно доказать, что всегда , чем и объясняются названия "нижняя цена" и "верхняя цена".

В1

В2

В3

αi

А1

2

-3

4

-3

А2

-3

4

-5

-5

А3

4

-5

6

-5

βj

4

4

6

Матрица игры в общем виде

В1

В2

Вm

αi

А1

a11

a12

a1m

α1

А2

a21

a22

a2m

α2

An

an1

an2

anm

αm

βj

β1

β2

βn

Нижняя цена игры  = – 3; верхняя цена игры  = 4. Наша максиминная стратегия есть А1; применяя ее систематически, мы можем твердо рассчитывать выиграть не менее –3 (проиграть не более 3). Минимаксная стратегия противника есть любая из стратегий В1 и В2, применяя их систематически, он, во всяком случае, может гарантировать, что проиграет не более 4. Если мы отступим от своей максиминной стратегии (например, выберем стратегию А2), противник может нас «наказать» за это, применив стратегию В3 и сведя наш выигрыш к — 5. Но если противник выберет стратегию B3, то мы в свою очередь можем выбрать A3 и он проиграет 6 и т.д. Таким образом, положение, при котором оба игрока пользуются своими минимаксными стратегиями, является неустойчивым и может быть нарушено поступившими сведениями о стратегии противной стороны.

Однако существуют некоторые игры, для которых минимаксные стратегии являются устойчивыми. Это те игры, для которых нижняя цена равна верхней:

 = 

Если нижняя цена игры равна верхней, то их общее значение называется ценой игры, и обозначают .

Например, в игре, матрица которой приведена ниже, верхняя и нижняя цены игры оказываются равными:  =  =  = 0.6.

Элемент 0,6, выделенный в платежной матрице, является одновременно минимальным в своей строке и максимальным в своем столбце. В геометрии точку на поверхности, обладающую аналогичным свойством (одновременный минимум по одной координате и максимум по другой), называют седловой точкой. По аналогии этот термин применяется и в теории игр. Элемент матрицы, обладающий этим свойством, называется седловой точкой матрицы, а про игру говорят, что она имеет седловую точку.

В1

В2

В3

В4

αi

А1

0,4

0,5

0,7

0,3

0,3

А2

0,8

0,4

0,3

0,7

0,3

А3

0,7

0,6

0,8

0,9

0,6

A4

0,7

0,2

0,4

0,6

0,2

βj

0,8

0,6

0,8

0,9

Для игр с седловой точкой решение игры обладает следующим замечательным свойством. Если один из игроков (например А) придерживается своей оптимальной стратегии, а другой игрок (В) будет любым способом отклоняться от своей оптимальной стратегии, то для игрока, допустившего отклонение, это никогда не может оказаться выгодным. Это утверждение легко проверить на примере рассматриваемой игры с седловой точкой.

В этом случае наличие у любого игрока сведений о том, что противник избрал свою оптимальную стратегию, не может изменить собственного поведения игрока: если он не хочет действовать против своих же интересов, он должен придерживаться своей оптимальной стратегии. Т.е. пара оптимальных стратегий в игре с седловой точкой является как бы «положением равновесия».

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

Для матричной игры nm обозначим через — смешанную стратегию игрока А, где и . Через обозначим смешанную стратегию игрока В, где и . Здесь — вероятности использования игроком А в смешанной стратегии своих чистых стратегий . и — вероятности использования игроком B в смешанной стратегии своих чистых стратегий .

Математическое ожидание выигрыша игрока А запишется в виде

.

Смешанная стратегия, которая гарантирует игроку наибольший возможный средний выигрыш (или наименьший возможный средний проигрыш), называется его оптимальной смешанной стратегией. Пусть P* — смешанная стратегия игрока А, Q* — смешанная стратегия игрока В. Пара смешанных стратегий (P*, Q*), при которой M(P,Q*)  M(P*,Q*)  M(P*,Q), называют седловой точкой игры, а математическое ожидание выигрыша  = M(P*, Q*) — ценой игры, причем всегда  .



Похожие документы:

  1. Задачи для самостоятельного решения 17 Глава 3 принятие решений в условиях неопределенности и риска (игры с природой) 18

    Документ
    ... теории игр и пример ее применения вынесены в прило­жение. Отличие игр, описанных в главе 3 «Принятие решений в условиях неопределенности и риска (игры ... произвольно­сти выбора критерия принятия решения), оно тем не менее создает некоторое упорядочение ...
  2. Принятие решений в условиях полной и частичной неопределённости

    Документ
    ... и методологии теории принятия решений. Эта теория предполагает, что решениям, связанным с ... принятии решений в условиях неопределенности. Скорее всего, это связано с тем, что поведение ЛПР, обусловленное неопределенностью ... если участник «игры» или событий ...
  3. Рабочая программа по дисциплине математическое моделирование и теория принятия решений всего учебных часов, час./ зач ед

    Рабочая программа
    ... 3 – Теория игр и принятия решений в условиях неопределенности Тема 3.1. Основные понятия теории игр. Графическое решение задач. Основные понятия теории игр и постановка задачи. Матричные игры. Игры с «природой ...
  4. Методические указания Объектом исследования теории игр (ТИ) является принятие решений в условиях неопределенности Выделить отличия антагонистических игр, некооперативных и кооперативных игр

    Методические указания
    ... проблемы, получила название теории игр. Задачи теории игр относятся к области принятия решений в условиях неопределенности, а их специфика ... игра имеет решение в смешанных стратегиях. Значение и нетривиальность теоремы обусловлены прежде всего тем ...
  5. Игра ( здесь ) математическая модель проблемы конфликтного принятия решения. 

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

Другие похожие документы..