Контрольные, курсовые, рефераты, тесты – готовые и на заказ!
 Гарантия качества, доступные цены, индивидуальный подход
 Работы выполняют высококвалифицированные специалисты
Войти      Регистрация
 тел. 8-912-388-82-05
  std72@mail.ru
> 20 лет успешной работы
> 50000 выполненных заказов
Отзывы/вопросы

Форма входа



Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы в экономике

Тема 4. Элементы теории игр
22.12.2011, 13:32

Основные понятия. Игры в чистых стратегиях

     Во многих экономических задачах часто возникают ситуации, когда две или более сторон разрешают одну и ту же проблему, но преследуют различные цели, их интересы противоположны.  Подобные ситуации называютсяконфликтными. Примерами таких ситуаций служат отношения между продавцом и покупателем, адвокатом и прокурором, кредитором и дебитором, истцом и ответчиком и т.д.
     Математические методы анализа конфликтных ситуаций объединяются под названием теории игр, сама конфликтная ситуация носит название игры, а стороны, участвующие в конфликте, называются игроками. Исход игры называется выигрышем (или проигрышем) игроков. Если в игре участвуют только два игрока, то игра называетсяпарной. Будем рассматривать в дальнейшем только парные игры. Если выигрыш одного игрока равен проигрышу другого, то игра называется антагонистической
     Рассмотрим следующую модель. Игрок А желает принять решение, на результат которого влияет другой игрок В, цели которого противоположны А. Игрок В анализирует все возможные варианты А и принимает такое решение, которое приводит к наименьшему выигрышу А (соответственно максимальному своему выигрышу). 
     Пусть игрок А может выбрать в качестве действий одну из п альтернатив (вариантов) своих возможных действий:А1, А2,…, Аn. Эти альтернативы в теории игр принято называть стратегиями. Аналогично, игрок В может принять одну из m своих стратегий В1, В2,…, Вm. Предположим, что известны выигрыши (проигрыши) игрока А при любой выбранной им стратегии Аi и любом ответе ему игроком В – стратегии Вj. Пусть этот результат выражен числом аij (которое может быть и отрицательным в случае проигрыша А). Величины аij образуют матрицу:
    

 
В1
В2
Вm
А1
a11
a12
a1m
А2
a21
a21
a2m
 
 
 
Аn
an1
an2
anm

     Эта матрица называется платежной или матрицей игры
     Рассмотрим игру со стороны А. Он, выбирая свою стратегию Аi, понимает, что В ответит ему такой стратегией Вj, чтобы выигрыш А был минимальным. Поэтому, из всех наихудших вариантов (минимальных элементов каждой строки платежной матрицы) , игроку А выгодно выбрать стратегию, соответствующую максимальному из этих элементов:
     .
     Величина a называется нижнейценой игры или максимином. Это гарантированный выигрыш игрока А. С другой стороны, игрок В выбирая свою стратегию Вj понимает, что игрок А ответит такой стратегией Аi, чтобы его выигрыш был максимален. Поэтому из наилучших вариантов для А (максимальных элементов каждого столбца)  игроку В рационально выбрать свою стратегию, соответствующую минимальному из этих чисел:
     .
     Величина β называется верхней ценой игры или минимаксом. Это максимальный проигрыш игрока В. Реальный результат решения конфликтной ситуации, называемый ценой игры n, заключен между верхней и нижней ценой: . В случае, если верхняя и нижняя цены совпадают , то игра имеет решение в чистых стратегиях, то есть можно точно определить стратегии , которые выгодны для обоих сторон. Если одна сторона отойдет от своей оптимальной стратегии, то ее выигрыш от этого только уменьшится. 
     Пример: Дебитор А желает выбрать один из четырех условий займа: А1, А2, А3, А4. Кредитор может на любой вариант займа ответить вариантом предоставления кредита В1, В2, В3, В4, В5. Процентные ставки для дебитора при любом варианте кредитора представлены платежной матрицей:

 
В1
В2
В3
В4
В5
А1
6
1
8
7
4
А2
4
3
2
6
5
А3
3
7
6
9
8
А4
2
6
7
8
3

     Находим минимальные элементы каждой строки платежной матрицы αI и из них находим максимальное значение. Из максимальных элементов каждого столбца βj выбираем минимальный. 

 
В1
В2
В3
В4
В5
αi
А1
6
1
8
4
4
1
А2
9
6
7
5
8
5
А3
3
7
6
2
8
2
А4
2
6
7
3
3
2
βj
9
7
8
5
8
 

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

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

     Рассмотрим теперь ситуацию, когда верхняя и нижняя цены не совпадают . В этом случае игра решается всмешанных стратегиях. Смешанный стратегии предполагают, что каждый игрок будет выбирать случайно из возможно допустимых чистых стратегий (но выбирать их с вероятностями), либо частично реализовывать чистые стратегии в заданных пропорциях. Нахождение этих вероятностей (или пропорций) и является решением игры. Таким образом, в общем виде, решением игры являются смешанные стратегии  и , где  и  - вероятности чистых стратегий  в смешанной. 
     Рассмотрим сначала простейший случай игры, решаемой в смешанных стратегиях – игру 2х2, когда у каждого игрока имеется лишь по две стратегии. Платежная матрица такой игры есть:

 
B1
B2
A1
a11
a12
A2
a21
a22

     Решение игры  и , где . Цена игры равна 
     Пример. Игрок А прячет в одной из рук монету. Игрок В пытается угадать руку с монетой. Если В не угадывает, то Аполучает от В 1 у.е. Если В угадывает руку с монетой и эта рука правая, то он получает от А 1 у.е. Если В находит монету в левой руке, то он получает от А 2 у.е. Определить оптимальные стратегии поведения для каждого игрока и средний выигрыш для А
     Пусть стратегии игроков: А1 – спрятать в правой; В1 – искать в правой; А2 – спрятать в левой; В2 – искать в левой.  Игровая матрица для данной ситуации относительно игрока А имеет вид:
    
 
B1
B2
A1
-1
1
A2
1
-2

     Тогда вероятности чистых стратегий в смешанной равны:
     . Цена игры равна 
     Таким образом, игроку А нужно случайно чередовать руки с монетой, но в правой руке прятать в среднем в трех случаях из пяти, а в левой в двух случаях из пяти. В это случае в каждой игре в среднем А получит (-1/5) руб., то есть теряет 20 коп., игра для А не выгодная. Для игрока В выгодно также чередовать руки в которых он ищет монету, но в правой руке искать в 3 случаях из 5, что приведет к среднему выигрышу для него в 20 коп. за игру. 
     В некоторых случаях удается аналогичным образом решить и игровые ситуации с платежными матрицами, большего размера, упростив их до игры 2х2. При этом используются следующие правила:
     1)  Если все элементы какой-либо строки платежной матрицы не превышают соответствующих элементов любой другой строки, то строка с меньшими элементами соответствует стратегии, которая для игрока А заведомо не выгодна при любом ответе игрока В. Поэтому из платежной матицы строку с меньшими элементами можно вычеркнуть, тем самым выведя из рассмотрения соответствующую ей стратегию.  
     2) С другой стороны, для игрока В невыгодна заранее, независимо от ответа А, стратегия, которой соответствует столбец платежной матрицы, у которого все элементы больше или равны соответствующим элементам любого другого столбца. Столбец с большими элементами также можно вывести из рассмотрения, вычеркнув из платежной матрицы. 
     Пример
     Директор транспортной компании А, оказывающей транспортные услуги по перевозке пассажиров в областном центре, планирует открыть один или несколько маршрутов: А1, А2, А3 и А4. Для этого было закуплено 100 микроавтобусов. Он может поставить весь транспорт на одном из маршрутов (наиболее выгодном), либо распределить по нескольким маршрутам. Спрос на транспорт, а соответственно и прибыль компании во многом зависит от того, какие маршруты в ближайшее время откроет главный конкурент - компания В. Ее руководство полностью владеет ситуацией и может открыть несколько из пяти маршрутов В1, В2, В3, В4 и В5. Оценки прибыли компании А (млн. руб.) при любом ответе В представлена платежной матрицей:
    
 
В1
В2
В3
В4
В5
А1
5
6
4
6
9
А2
6
5
3
4
8
А3
7
6
6
7
5
А4
6
7
5
4
3

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

 
B3
B5
A1
4
9
A3
6
5

     Тогда вероятности чистых стратегий компании А в смешанной  равны: . Цена игры равна . Следовательно, 1/6 часть автопарка (17 машин) нужно направить на маршрут А1, а остальные 5/6 парка (83 машины) на маршрут А3. Маршруты А2 и А4 использовать не рационально. При этом прибыль, не зависимо от ответа компании В будет составлять 34/6 млн. руб. 
     Рассмотрим случай, когда платежную матрицу нельзя упростить до размера 2х2. Пусть упрощенная платежная матрица имеет вид: . Тогда для нахождения вероятностей  и  смешанных стратегий  и , необходимо решать прямую и двойственную задачи линейного программирования вида:
                    
     Из решения задач линейного программирования находятся цена игры  и вероятности состояний
     Пример. Построить прямую и двойственную задачи линейного программирования для решения матричной игры, заданной платежной матрицей:  
     Прямая и двойственная задачи линейного программирования имеют вид:
                
     Из решения можно найти игры цену игры  и вероятности состояний .

Игры с природой

     В рассмотренных ранее задачах соперником игрока А был другой «мыслящий» игрок В. Однако часто таким «соперником» может быть некоторое стечение обстоятельств, неконтролируемое человеком. Выбор стратегии стороной В происходит случайно, совершенно не рассматривая, выгодно это А или нет. Такие ситуации называются играми с природой
     Предположим, что игрок А имеет п альтернатив решения ситуации, которые обозначим . Результат выбора (выигрыш А) зависит от того, как будит развиваться ситуация, на которую этот игрок повлиять ни как не может. Предположим, что возможны m вариантов развития ситуации, которые обозначим . Данные варианты в теории игр называют «Состояниями природы», т.к. в большинстве реальные задачи этого типа связаны с погодными, климатическими, социальными и другими стихийными явлениями. 
     Допустим, что известен результат для игрока А (выраженный количественно) при каждой альтернатива Ai и развитии ситуации Bj. Обозначим его . Получаем матрицу , которую называют матрицей выигрышей или матрицей потерь, в зависимости от того, максимизируется или минимизируется результат для игрока А. 
     В соответствии с реальными условиями, существует несколько критериев принятия решений в условиях неопределенности. Для более наглядного описания этих методов, рассмотрим их на примерах. Изучим сначала критерии максимизации результата, когда показатели привлекательности   чем больше, тем лучше для А.
     ПРИМЕР 1.
     Директор торговой фирмы, продающей телевизоры марки «Zarya» решил открыть представительство в областном центре. У него имеются альтернативы либо создавать собственный магазин в отдельном помещении, либо организовывать сотрудничество с местными торговыми центрами. Всего можно выделить 5 альтернатив решения:  Успех торговой фирмы зависит от того, как сложится ситуация на рынке предоставляемых услуг. Эксперты выделяют 4 возможных варианта развития ситуации  Прибыль фирмы для каждой альтернативы при каждой ситуации представлена матрицей выигрышей  (млн. р./год).

 
B1
B2
B3
B4
А1
8
12
14
5
А2
9
10
11
10
А3
2
4
9
22
А 4
12
14
10
1
А 5
15
6
7
14

     Рассмотрим основные критерии, позволяющие выбирать оптимальную альтернативу для принятия решения.
     1) Критерий Лапласа.
     Он основан на предположении, что каждый вариант развития ситуации (состояния «природы») равновероятен. Поэтому, для принятия решения, необходимо рассчитать функцию полезности  для каждой альтернативы, равную среднеарифметическому показателей привлекательности по каждому «состоянию природы»:
     .
     Выбирается та альтернатива, для которой функция полезности максимальна. Для примера:
     
     Видно, что функция полезности максимальна для альтернативы А5, следовательно ее рациональнее всего принять. 
     2) Критерий Вальда.
     Данный критерий основывается на принципе максимального пессимизма, то есть на предположении, что скорее всего произойдет наиболее худший вариант развития ситуации и риск наихудшего варианта нужно свести к минимуму. Для применения критерия нужно для каждой альтернативы выбрать наихудший показатель привлекательности  (наименьшее число в каждой строке матрицы выигрышей) и выбрать ту альтернативу, для которой этот показатель максимальный. Для нашего примера:   Видно, что наилучшим из наихудших показателей обладает альтернатива А2 , для нее  наибольшее.
     3) Критерий максимального оптимизма.
     Наиболее простой критерий, основывающийся на идее, что ЛПР, имея возможность в некоторой степени управлять ситуацией, рассчитывает, что произойдет такое развитие ситуации, которое для него является наиболее выгодным. В соответствии с критерием принимается альтернатива, соответствующая максимальному элементу матрицы выигрышей. Для приведенного примера эта величина , поэтому выбираем альтернативу 
     4) Критерий Сэвиджа.
     Он основан на принципе минимизации потерь, связанных с тем, что игрок А принял не оптимальное решение. Для решения задачи составляется матрица потерь, которая называется матрицей рисков , которая получается из матрицы выигрышей  путем вычитания из максимального элемента каждого столбца  всех остальных элементов. В рассматриваемом примере эта матрица есть:
    
 
B1
B2
B3
B4
А1
7
2
0
17
А2
6
4
3
12
А3
13
10
5
0
А4
3
0
4
21
А5
0
8
7
8

     Далее, для каждой альтернативы определяем величины , равные максимальному риску (наибольшее число в каждой строке матрицы рисков) и выбирают ту альтернативу, для которой максимальный риск минимален. В нашем примере:      минимально  Принимаем альтернативу А2
     5) Критерий Гурвица.
     Это самый универсальный критерий, который позволяет управлять степенью «оптимизма - пессимизма» игрока А. Введем некоторый коэффициент a, который назовем коэффициентом доверия или коэффициентом оптимизма. Этот коэффициент можно интерпретировать как вероятность, с которой произойдет наилучший для А исход. Исходя из этого, наихудший вариант можно ожидать с вероятностью (1-α). Коэффициент доверия a показывает, насколько игрок А может управлять ситуацией и в той или иной степени рассчитывает на благоприятный для него исход. Если вероятности благоприятной и неблагоприятной ситуации для А равны, то следует принять α=0,5. 
     Для реализации критерия определяются наилучшие  и наихудшие  значение каждой альтернативе по формулам . Далее, вычисляются функции полезности по формуле: 
      .
     Выбирается та альтернатива, для которой функция полезности максимальна. 
     Предположим, что для нашего примера игрок А достаточно уверен в положительном результате и оценивает вероятность максимального успеха в α=0,7. Тогда:
     
     В соответствии с расчетами игроку А следует выбрать альтернативу А3. Если же, например, А не очень уверен в положительном исходе и расценивает его вероятность порядка α=0,2, то функции полезности равны:
     
     Видно, что в этом случае следует принять А2, для которого функция полезности максимальна.
     Следует отметить, что при α=0, критерий Гурвица переходит в пессимистический критерий Вальда, а при α=1 – в критерий максимального оптимизма.  
     В случае, если показатель привлекательности по критерию   минимизируются (чем меньше, тем лучше для А, например затраты, риск и др.), то критерии принятия оптимального решения несколько меняются. Рассмотрим эти отличия.
     Критерий Лапласа определяет оптимальное решение по минимальной функции полезности. Применяя критерийВальда необходимо вычислять максимальный показатель каждой альтернативы (строки)  и принимать альтернативу, где этот показатель минимален. Критерий максимального оптимизма позволяет определить оптимальное решение, соответствующее минимальному элементу матрицы выигрышей (которую в случае минимизации часто называют матрицей потерь). Матрица рисков в критерии Сэвиджа получается в результате вычитания из каждого элемента матрицы потерь  минимального элемента каждого столбца .  Для реализации критерия Гурвица вычисляются максимальные и минимальные показатели для каждой альтернативы  и функции полезности рассчитываются по формуле:  . Выбирается альтернатива с наименьшей функцией полезности. Рассмотрим пример.
     ПРИМЕР 2.   Нефтяная компания собирается построить в районе крайнего севера нефтяную вышку. Имеется 4 проекта A, B, C и D. Затраты на строительство (млн. руб.) зависят от того, какие погодные условия будут в период строительства. Возможны 5 вариантов погоды . Выбрать оптимальный проект для строительства используя критерии Лапласа, Вальда, максимального оптимизма, Сэвиджа и Гурвица при . Матрица затрат имеет вид:
    
 
S1
S2
S3
S4
S5
A1
7
12
8
10
5
A2
9
10
7
8
9
A3
6
8
15
9
7
A4
9
10
8
11
7

     Критерий Лапласа.
      
     Следует выбрать альтернативу А1.
     Критерий Вальда: среди наихудших вариантов α1=12, α2=10, α3=15, α4=11, наилучший соответствует α2=10, следовательно принимаем альтернативу А2
     Критерий максимального оптимизма. Соответствует альтернативе, для которой  минимальное. 
     Критерии Сэвиджа имеет матрицу рисков:
    
 
S1
S2
S3
S4
S5
A1
1
4
1
2
0
A2
3
2
0
0
4
A3
0
0
8
1
2
A4
3
2
1
3
2

     Максимальные элементы для каждого критерия матрицы рисков равны: β1=4; β2=4; β3=8; β4=3. Принимаем альтернативу, соответствующую минимальному значению β4=3, то есть А4.
     В соответствии с критерии Гурвица на уровне , функции полезности равны:
     
     Принимаем альтернативу А2 с наименьшей функцией полезности .

http://math.immf.ru/




БАНКОВСКОЕ ДЕЛО
БУХГАЛТЕРСКИЙ, УПР. И ФИН. УЧЕТ
БЮДЖЕТ И БЮДЖЕТНАЯ СИСТЕМА РФ
ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ
ГУМАНИТАРНЫЕ НАУКИ
ДОКУМЕНТОВЕДЕНИЕ И ДЕЛОПРОИЗВОДСТВО
ИНВЕСТИЦИИ
ИНФОРМАЦИОННЫЕ СИСТЕМЫ В ЭКОНОМИКЕ
ИССЛЕДОВАНИЕ СИСТЕМ УПРАВЛЕНИЯ
МАРКЕТИНГ
МЕНЕДЖМЕНТ
МЕТ. РЕКОМЕНДАЦИИ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
МИРОВАЯ ЭКОНОМИКА И МЭО
НАЛОГИ И НАЛОГООБЛОЖЕНИЕ
ПЛАНИРОВАНИЕ И ПРОГНОЗИРОВАНИЕ
ПРАВОВЕДЕНИЕ
РАЗРАБОТКА УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
РЫНОК ЦЕННЫХ БУМАГ
СТАТИСТИКА
УПРАВЛЕНИЕ ПЕРСОНАЛОМ
УЧЕБНИКИ, ЛЕКЦИИ, ШПАРГАЛКИ (СКАЧАТЬ)
ФИНАНСОВЫЙ МЕНЕДЖМЕНТ
ФИНАНСЫ, ДЕНЕЖНОЕ ОБРАЩЕНИЕ И КРЕДИТ
ЦЕНЫ И ЦЕНООБРАЗОВАНИЕ
ЭКОНОМИКА
ЭКОНОМИКА, ОРГ-ЦИЯ И УПР-НИЕ ПРЕДПРИЯТИЕМ
ЭКОНОМИКА И СОЦИОЛОГИЯ ТРУДА
ЭКОНОМИЧЕСКАЯ ТЕОРИЯ (МИКРО-, МАКРО)
ЭКОНОМИЧЕСКИЙ АНАЛИЗ
ЭКОНОМЕТРИКА
Оформить заказ
Ваше имя *
Ваш e-mail *
Контактный телефон
Город *
Учебное заведение *
Предмет *
Тип работы *
Тема работы/вариант *
Кол-во страниц
Срок выполнения *
Прикрепить файл
Дополнительные условия


Статистика
Онлайн всего: 12
Гостей: 12
Пользователей: 0