методичка Теория игр 2014. Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014
 Скачать 1.28 Mb.
|
|
D , то решением будет являться весь единичный квадрат ] 1 , 0 [ p , Если 0 D , 0 , то решением является либо 0 q , либо Если 0 D , то получим следующие решения 1) если 0 q , то D p ; 2) если 1 q , то D p ; 3) если 1 0 q , то Если 0 D , то решения будут следующие 1) если 0 q , то D p ; 2) если 1 q , то D p ; 3) если 1 0 q , то Графическая интерпретация множества решений игрока B : Риса Рис.11б 1 1 0 p q C > 0 (p, /C ) 1 1 0 p q C < 0 (p, /C ) 1 1 0 p q D> 0 ( /D, q) 1 1 0 p q D< 0 ( /D, q) Решением игры является пересечение множеств решений для игроков A и B . Графически решение будет выглядеть как пересечение двух зигзагов, варианты которых приведены на рисунках выше. При этом эти зигзаги могут быть как противоположными, таки одинаковой направленности. В первом случае мы получим три точки пересечения, те. три состояния равновесия, а во втором – одну. Укажем решения конкретных примеров. Пример 1. Рассмотрим игру борьба за рынки. Платежные матрицы игроков A и B имеют следующий вид 1 1 2 10 A , 1 1 2 Вычисляем коэффициенты C , , D и : 14 1 1 2 10 C , 3 2 1 , 9 1 ) 1 ( ) 2 ( 5 D , Так как 0 C , то решения для игрока A будут следующие 1) если 0 p , то 14 3 q ; 2) если 1 p , то 14 3 q ; 3) если 1 0 p , то 14 Так как 0 D , то решения для игрока B будут следующие 1) если 0 q , то 9 2 p ; 2) если 1 q , то 9 2 p ; 3) если 1 0 q , то 9 Нанесем полученные решения на график. для игрока для игрока объединение Риса Рис.12б Рис.12в Точка пересечения построенных зигзагов – это точка равновесия. Она имеет координаты 14 / 3 ; 9 / 2 ) , ( * * q p . Тогда оптимальной смешанной стратегией игрока A будет 9 / 7 ; 9 / 2 * A x , ау игрока B : Средние выигрыши игроков вычисляем по формулам (60а)-(61а): 7 4 1 14 3 2 9 2 ) 3 ( 14 3 9 2 14 14 3 ; 9 2 A H , 14 3 ; 9 2 B H 3 1 1 14 3 2 9 2 3 14 3 9 2 9 1 1 0 p q 14 3 1 1 0 p q 2/9 1 1 0 p q 2/9 14 3 Разобьем данную биматричную игруна две матричные с нулевой суммой и найдем их решения. 1. Игра с матрицей 1 1 2 10 A P имеет следующее решение (см. (15)-(16)): 7 6 ; 7 1 * A x (оптимальная стратегия игрока A ), оптимальная стратегия игрока B ), 7 4 * A v (цена игры. 2. Игра с матрицей 1 1 2 5 B P имеет такое решение 9 оптимальная стратегия игрока A ), 3 / 2 ; 3 / 1 * B y (оптимальная стратегия игрока B ), 3 / 1 * B v (цена игры. Сравнивая полученные решения с решением биматричной игры, видим, что 1. оптимальный средний выигрыш игрока в матричной игре совпадает сего выигрышем при равновесной ситуации в биматричной; 2. по своей матрице игрок может определить только оптимальную стратегию (равновесную по Нэшу) другого игрока, ноне свою, а для определения своей стратегии нужна матрица противника. Полученные выводы можно использовать для решения биматричных игр большей размерности, чем 2 2. Для этого нужно всего лишь решить две матричные игры той же размерности. В биматричных играх принцип равновесия по Нэшу не всегда приводит к ситуации, выгодной обоим игрокам. Рассмотрим в связи с этим второй пример "дилемма узников. Пример 2. В игре "дилемма узников" выигрыши игроков описываются матрицами 6 0 9 1 A , 6 9 0 Решаем эту игру как биматричную: 2 6 0 ) 9 ( 1 C , 3 ) 9 ( 6 , 2 6 ) 9 ( 0 1 D , Так как 0 C , то решения для игрока A будут следующие 1) если 0 p , то 2 3 q ; 2) если 1 p , то 2 3 q ; 3) если 1 0 p , то 2 Так как 0 D , то решения для игрока B будут следующие 1) если 0 q , то 2 3 p ; 2) если 1 q , то 2 3 p ; 3) если 1 0 q , то 2 Нанесем полученные решения на график (см. рис. Из рис видно, что зигзаги для и B пересекаются только водной точке (0,0). Это ситуация ситуация равновесия, в которой каждый из игроков выбирает вторую чистую стратегию "сознаться" и они теряют полет, те. 6 0 ; 0 Как уже отмечалось ранее, отклонение от ситуации равновесия одного из игроков не дает ему никаких преимуществ. Однако при одновременном отклонении обоих игроков каждый из них может получить больший выигрыш, чем в равновесной ситуации. Именно, в ситуации ) 1 , 1 ( ) , ( q p , когда каждый из игроков A и B выбирает первую чистую стратегию "молчать, они теряют лишь 1 (год. При этом очевидно, что ситуация (1, 1) неустойчива, так как любой из игроков, изменяя свою стратегию, может увеличить свой выигрыш (избежать наказания. Решим данную биматричную игру как две матричные с нулевой суммой. 1. Для игры с матрицей 6 0 9 1 A P получим следующее решение 1 ; 0 * A x , 1 ; 0 * B y , 6 * A v (цена игры. 2. Игра с матрицей 6 9 0 1 B P имеет такое решение 0 ; 1 * A x , 0 ; 1 * B y , 1 * B v (цена игры. Те. игроку B рекомендуется придерживаться второй стратегии, а игроку A – первой, но тогда 0 , 9 B A H H . Такая ситуация хуже для игрока A , чем для игрока Таким образом, в биматричной игре ситуация равновесия обоих игроков определяется не столько стремлением увеличить собственный выигрыш, сколько стремлением минимизировать выигрыш другого игрока. 2.4. ОПТИМАЛЬНОСТЬ ПО ПАРЕТО Дадим определение другого способа определения оптимальности в биматричных играх, который основан на принципе оптимальности по Парето. Ситуация ) , ( q p в биматричной игре двух лиц A и B называется оптимальной по Парето, если из того, что А В p q 0 1 3/2 1 3/2 Рис. q p H q p H A A , , , q p H q p H B B , , (63) следуют равенства q q p p , , те. не существует ситуации q p, , для которой имеют место неравенства (63). Среди этих неравенств по крайней мере одно должно быть строгим. В оптимальной по Парето ситуации, все игроки, действуя совместно, не могут увеличить выигрыш каждого, не уменьшив при этом выигрыш одного из них. В отличие от этого, в ситуации равновесия по Нэшу ни один из игроков, действуя в одиночку, не может увеличить своего собственного выигрыша. Покажем, как на практике отыскать оптимальную по Парето ситуацию в биматричной игре 2 2. Введем обозначения q p H U A , , q p H V B , , (64) и рассмотрим плоскость ) , ( V U . На плоскости ) , ( V U найдем целевую точку, в качестве координат которой часто выбирается сочетание наилучших значений U и V . В данном случае это будет точка ) , ( m ax m ax V U T , где ) , ( max , max q p H U A q p , Вследствие того, что обычно такая точка T при заданных ограничениях не реализуется, ее называют точкой утопии. Далее, строим множество точек, отвечающее соотношениям (64), определяем на нем множество Парето, отвечающее заданным условиям на переменные q p, , и находим на нем точку, ближайшую к точке утопии T. Именно такая точка и будет идеальной точкой ) , ( П П V U P , отвечающей принципу оптимальности по Парето. Найдя идеальную точку P , можно определить (используя соотношения (64)) и значения П П q p , , при которых она достигается. Здесь ) , ( П П q p – это оптимальная ситуация по Парето. Множество Парето – это множество тех граничных точек, отвечающих соотношениям (64), перемещение которых по границе построенного множества уменьшает одну из координат здесь U или V ) при одновременном увеличении другой (см. рис, дуга ). Построим множество Парето в примере 2 и найдем точку оптимальную по Парето. По формулам (60а)-(61а) находим , 6 3 6 2 ) , ( , 6 6 3 2 ) , ( q p pq q p H V q p pq q p H U B A 1 , 0 q p (65) P T U V 0 V max U max V * U * Рис. Найдем границы множества точек, удовлетворяющих (65). Для этого можно рассматривать крайние значения переменных p и q : 1) при 0 p имеем 6 3 , 6 6 q V q U 9 2 / 1 U V , 6 9 , 0 6 V U ; 2) при 1 p имеем q V q U , 9 8 8 / ) 9 ( U V , 0 1 , 1 9 V U ; 3) при 0 q имеем 6 6 , 6 3 p V p U U V 2 18 , 0 6 , 6 9 V U ; 4) при 1 q имеем 9 8 , p V p U 9 8 U V , 1 9 , 0 На рис изображено множество, удовлетворяющее уравнениям (65). Получился четырехугольник с вершинами в точках ) 0 , 9 ( A , ) 1 , 1 ( B , ) 9 , 0 ( C , Точкой утопии здесь будет точка T(0; 0), так как 0 m ax U и 0 m Множеству Парето здесь отвечают отрезки прямых при 1 p и 1 q . Как видно из рис ближайшей точкой множества Парето к точке утопии T является точка ) 1 ; 1 ( B P , те. 1 , 1 П П V U . Решая систему уравнений 1 ) , ( П П A q p H , 1 ) , ( П П В q p H , находим, что П, П. Это означает, что оптимальной ситуацией по Парето будет ситуация ) 1 , 1 ( ) , ( П П q p (те. игроки A и B применяют свои первые чистые стратегии. Заметим, что точка ) 6 ; 6 ( D соответствует точке равновесия по Нэшу в данном примерено при этом эта точка намного дальше от точки утопии, чем точка P . Ясно, что оптимальная ситуация по Парето здесь лучше, чем по Нэшу. В заключение укажем оптимальные ситуации по Парето в других рассмотренных примерах. Так, в примере 1 "борьба за рынки" оптимальной ситуацией по Парето будет ситуация ) 0 , 0 ( ) , ( П П q p , те. 1 , 1 П П V U . В примере 3 "семейный спор" есть две оптимальные T P D q =1 p =1 B A C U V 0 –1 –1 –6 –6 –9 –9 p =0 Рис. ситуации по Парето, именно ) 0 , 1 ( ) , ( 1 1 П П q p и ) 1 , 0 ( ) , ( 2 2 П П q p , при этом они одновременно являются и ситуациями равновесия по Нэшу (есть также одна ситуация равновесия по Нэшу в смешанных стратегиях, но она хуже указанных выше двух. В примере 4 "студент-преподаватель" оптимальной ситуацией по Парето будет ситуация ) 1 , 1 ( ) , ( П П q p , она же будет и равновесной по Нэшу. СПИСОК ВОПРОСОВ ПО КУРСУ ТЕОРИЯ ИГР Задачи теории игр. Примеры, виды игровых задач. Антагонистические матричные игры. Примеры игр. Максимин и минимакс. Выигрыши двух игроков. Ситуации равновесия в игре. Понятие седловой точки. Чистые стратегии двух игроков. Смешанные стратегии двух игроков в матричной игре. Выигрыши игроков в игре. Теорема Дж. фон Неймана о ситуации равновесия. Аналитическое решение игры 2 2. Геометрическое решение игры 2 2. Лемма о масштабе. Условия эквивалентности смешанных стратегий двух игр. Свойства оптимальных смешанных стратегий в матричной игре. Графический метод решения матричной игры (2 n). Графический метод решения матричной игры (m 2). Активные (существенные) стратегии игроков. Теоремы об активных стратегиях. Принцип доминирования стратегий двух игроков. Теоремы о доминируемых стратегиях. Вполне смешанная игра. Решение матричной игры n n методом обратной матрицы. Сведение матричной игры n m к двойственной задаче линейного программирования. Общий подход. Постановка задач линейного программирования. Примеры, различные формы задачи подходы решения. Задача линейного программирования в канонической форме. Основные теоремы о множествах оптимальных решений этой задачи. Допустимые базисные решения. Аналитический метод решения задачи линейного программирования m n (симплекс-метод). Симплекс-таблицы. Метод искусственного базиса в симплекс-методе. Двойственные задачи линейного программирования. Решение матричной игры симплекс-методом. Сведение к двойственной задаче линейного программирования. 21. Биматричные неантагонистические игры. Постановка задачи. Функции выигрышей. Примеры биматричных игр борьба за рынки, дилемма узников, семейный спор, студент-преподаватель. Ситуация равновесия по Нэшу в чистых стратегиях в биматричной игре. Пример поиска ситуаций равновесия для игры 2 2. Ситуация равновесия по Нэшу в смешанных стратегиях в биматричной игре. Теорема Нэша. Свойства ситуаций равновесия. Ситуация равновесия по Нэшу в смешанных стратегиях для игры 2 2. Поиск решений для двух игроков. Графическая интерпретация решения биматричной игры 2 2 по Нэшу. Принцип оптимальности по Парето в биматричной игре. Пример для игры 2 2. Поиск оптимальных стратегий по Парето в биматричной игре 2 2. Множество Парето. Точка утопии. |