Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Теория игр

Читайте также:
  1. I. ДЖОРДЖ КАСПАР ХОМАНС: БИХЕВИОРИСТСКАЯ ТЕОРИЯ ОБМЕНА
  2. I. ЛЬЮИС КОЗЕР: ФУНКЦИОНАЛЬНАЯ ТЕОРИЯ КОНФЛИКТА
  3. I. ТЕОРИЯ КУЛЬТУРНЫХ СУПЕРСИСТЕМ
  4. II. ПИТЕР БЛАУ: ИНТЕГРАТИВНАЯ ТЕОРИЯ ОБМЕНА
  5. II. РАЛЬФ ДАРЕНДОРФ: ДИАЛЕКТИЧЕСКАЯ ТЕОРИЯ КОНФЛИКТА
  6. II. ТЕОРИЯ СОЦИАЛЬНОЙ СТРАТИФИКАЦИИ И СОЦИАЛЬНОЙ МОБИЛЬНОСТИ
  7. Q Кнут Викселль - экономист-теоретик и публицист q Концепция кумулятивного процесса q Теория общего равновесия и концепция процента И. Фишера q Теория денег И. Фишера
  8. Q«Цепочка» Джевонса q Теория обмена Эджуорта
  9. Ассоциативно - рефлекторная теория обучения.
  10. Б. Норманнская теория образования Русского государства, ее сторонники и противники. Этапы в истории образования Древнерусского государства
  11. Базисная теория таможенного тарифа.
  12. Биология как наука. Сущность жизни. Свойства живого. Уровни организации живого. Клеточная теория.

8.5.1 Общие понятия

 

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

Игра — это совокупность правил, описывающих сущность кон­фликтной ситуации. Эти правила устанавливают:

─ выбор образа действия игроков на каждом этапе игры;

─ информацию, которой обладает каждый игрок при осуществлении таких выборов;

─ плату для каждого игрока после завершения любого этапа игры.

Игру можно определить следующим образом:

─ имеются n конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;

─ сформулированы правила выбора допустимых стратегий, извест­ные игрокам;

─ определен набор возможных конечных состояний игры (напри­мер, выигрыш, ничья, проигрыш);

─ всем игрокам (участникам игры) заранее известны платежи, со­ответствующие каждому возможному конечному состоянию.
Платежи задаются в виде матрицы

 

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

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

 

8.5.2 Игры двух лиц с нулевой сум­мой

 

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

Если первый игрок имеет m стратегий, а второй — n стратегий, то говорят, что имеют дело с игрой m×n. Рассмотрим игру m×n. Пусть заданы множество стратегий: для первого игрока {АI}, для второго игрока {Bj}, платежная матрица , где аij — выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий Аi и Вj соответственно. Каждый из игроков выбирает однозначно с вероятностью 1 некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры бу­дет в чистых стратегиях. Поскольку интересы игроков противопо­ложны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш.



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

. (32)

 

Первый игрок (при любых ответах противника) будет стремить­ся найти такую стратегию, при которой αi, обращается в максимум:

(33)

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

Аналогично определим по каждому столбцу матрицы , найдем минимальное значение β j:

(34)

 

Величина β называется верхней ценой игры. Ей соответствует минимаксная стратегия второго игрока. Величина β представляет собой гарантированный проигрыш второго игрока при любой стра­тегии первого игрока.

Пример. Дана платежная матрица 3x4, которая определяет выигрыши игрока А. Вычислить нижнюю и верхнюю цены задан­ной игры.

Решение Представим нашу игру в виде следующей таблицы:

Если игрок А выбирает первую стратегию, он может получить выигрыш в размере 10, 4, 11 или 7 д. е. в зависимости от выбранной стратегии игроком В. При этом выигрыш игрока будет не меньше α1 = min{10; 4; 11; 7} = 4 д. е. независимо от поведения игрока В. Аналогично при выборе игроком А второй стратегии гарантирован­ный выигрыш α2 = min{7; 6; 8; 20} = 6 д. е. При выборе игроком А третьей стратегии выигрыш α3 = min{6; 23; 1; 11} = 1 д. е.

Таким образом, минимальные значения аi, i = 1,3 опреде­ляют минимально гарантированный выигрыш для игрока А, если он выбирает соответствующую стратегию i. Величина д.е. будет гарантированным выигрышем игрока А при любых стратегиях игрока В. Выбранная игроком А вторая стратегия называется максиминной стратегией, а соответствующее ее значение выигрыша α2 = 6 д. е. будет нижней ценой игры.

Второй игрок стремится минимизировать свой проигрыш. Вы­брав первую стратегию β1, игрок В может проиграть не более чем β1 = max{10; 7; 6} = 10 д. е. независимо от выбора стратегии игроком А. Аналогично рассуждая, получим следующие результаты (д. е.):

β2 = max{4; 6; 2} = 6; β3 = max{11; 8; 1} = 11;

β4 = max{7; 20; 11} = 20/

 

Игрок В выбирает стратегию β2, которая минимизирует его мак­симальные проигрыши:

Величина β = 6 д. е. будет гарантированным проигрышем игро­ка В при любых стратегиях игрока A. Выбранная игроком В вторая стратегия называется минимаксной стратегией, а соответствующее ее значение проигрыша β2 = 6 д. е. будет верхней ценой игры.

Следует отметить, что для любой матрицы выполняет­ся неравенство β ≥ α

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

Величина С = β = α называется ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при ис­пользовании ими оптимальных стратегий. В нашем примере цена игры С = 6 д. е., оптимальная пара стратегий — А2 и В2.

 

8.5.3 Понятия «доминирующий столбец» и «доминируе­мая строка»

 

Если в платежной матрице А все элементы строки Аi = (аi1, аi2, ..., ain) не меньше соответствующих элементов строки Ak = (ak1, ak2,…, akn), a no крайней мере один строго больше, то строка Ai- назы­вается доминирующей, а строка Ak доминируемой.

Аналогичны понятия «доминирующий столбец» и «доминируе­мая строка».

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

Пример Для игры с платежной матрицей A найдите стратегии игроков и цену игры.

 

Решение

Элемент a32 = -1 является наименьшим в третьей строке и на­ибольшим во втором столбце, т. е. он является седловой точкой. Поэтому цена игры С= -1, а оптимальные стратегии игроков: первого — А3, а второго — B2.

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

В матрице А третья строка доминирует над второй, поэтому вторую можно изъять из платежной матрицы. В результате полу­чится матрица

В матрице A1 первый и третий столбцы доминируют над вто­рым, следовательно, их можно изъять. В результате платежная ма­трица принимает вид

В матрице А2 вторая строка доминирует. После вычеркивания получится матрица A3, состоящая из одного элемента:

А3 = (-1). Элемент матрицы А3 и определяет решение задачи.

 

8.5.4 Понятие смешан­ной стратегии

 

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

(35)

где Pj — вероятность выбора i-й стратегии игроком и удовлетворяет следу­ющим условиям:

(36)

Аналогично смешанная стратегия игрока В представляет собой вектор

(37)

где qj — вероятность выбора j-й стратегии игроком В — удовлетворяет дующим условиям;

Платежная матрица игры имеет следующий вид:

Игрок А выбирает стратегию Pi, так, чтобы максимизировать на­именьший ожидаемый выигрыш по столбцам платежной матрицы, тогда как игрок В выбирает стратегию qj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически критерий минимакса при смешанных стратегиях может быть опи­сан следующим образом. Игрок А выбирает стратегию Pi дающую

(38)

Игрок В выбирает стратегию qj, дающую

(39)

 

Когда стратегии и оптимальны, то выполняется строгое равенство между максиминным ожидаемым выигрышем и мини­максным проигрышем, а результирующее значение равно опти­мальному (ожидаемому) значению игры.

Этот вывод следует из теоремы фон Неймана о минимаксе. Те­орема утверждает, что выражения (38), (39) имеют одно и то же значение M(P0,Q0), называемое ценой игры. Если и — опти­мальные решения для обоих игроков, каждому элементу платежной матрицы aij соответствует вероятность *. Следовательно, оп­тимальное ожидаемое значение игры

(40)

Цена игры заключена между нижней и верхней ценами, т. е. α≤М(Р0, Q0) ≤β.

Решить конечную игру — это значит нужно найти векторы Р и Q (оптимальные стратегии), удовлетворяющие теореме о минимак­се, а следовательно, получить величину ожидаемого платежа М(Р0, Q0) – цену игры.

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

Решение игры обладает одним важным свойством: если игрок А использует свою оптимальную стратегию, а игрок В смешивает свои стратегии в любых пропорциях, то средний выигрыш игрока А не уменьшается. Стратегии, которые смешиваются для получе­ния оптимальной стратегии, будем называть полезными. Доказано, что у игры m×n существует такое оптимальное решение, что чис­ло полезных стратегий с каждой стороны не превосходит мини­мального из чисел тип. Известно несколько методов нахождения оптимальных стратегий в играх двух лиц с нулевой суммой. Рас­смотрим один из методов — метод линейного программирования для нахождения решения игр.

 

<== предыдущая лекция | следующая лекция ==>
Критерий Лапласа | Метод линейного программирования для нахождения оптимальных стратегий в играх двух лиц с нулевой суммой

Дата добавления: 2014-01-04; Просмотров: 367; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:



studopedia.su - Студопедия (2013 - 2018) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление ip: 54.84.236.168
Генерация страницы за: 0.007 сек.