методичка Теория игр 2014. Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014
 Скачать 1.28 Mb.
|
|
1. Пусть ) , ,... ( 1 m p p x и ) , ,... ( 1 n q q y – оптимальные смешанные стратегии игроков A и B , и ) , ( y x H v A – цена игры. Оптимальная смешанная стратегия x игрока A смешивается только из тех стратегий А m i , 1 , те. отличными от нуля будут только те вероятности i p , для которых выполнены равенства ) , ( 1 y i H q a v A n j j ij (10) Аналогично для игрока B : оптимальная смешанная стратегия y игрока A смешивается только из тех стратегий j B n j , 1 , те. отличными от нуля будут только те вероятности j q , для которых выполнены равенства ) , ( 1 j x H p a v A m i i ij (11) В формулах (10)-(11) знак i в аргументе функции ) , ( y x H A означает, что игрок A выбрал свою чистую стратегию Аи, соответственно, j означает, что игрок B выбрал свою чистую стратегию j B . Кроме того, выполняются соотношения n j j ij m i n j j ij m i y m i i ij n j x m i i ij n j q a q a p a p a v 1 1 1 1 1 1 1 1 max max min min max min . (12) Соотношение (12) можно переписать ив такой форме ). , ( max ) , ( max min ) , ( min max ) , ( min * 1 1 1 а) 2. Для того, чтобы ситуация ) , ( y x была ситуацией равновесия в матричной игре, и число ) , ( y x H v A – ценой игры, необходимо и достаточно, чтобы выполнялись следующие неравенства ) , ( ) , ( ) , ( j x H y x H y i H A A A , для любых m i , 1 , n j , 1 . (13) 3. Для того, чтобы ситуация ) , ( y x была ситуацией равновесия в матричной игре, необходимо и достаточно выполнения следующего равенства (см. равенство (а ) , ( min ) , ( max j x H y i H A j A i (14) 4. В матричной игре множества оптимальных смешанных стратегий игроков A и B являются выпуклыми многогранниками [4, гл, § 5]. 5. Пусть платежная матрица P матричной игры является кососимметрической, те. ji ij a a для j i . Тогда, если x – оптимальная смешанная стратегия игрока A , то такую же оптимальную стратегию имеет и игрок B : x y , при этом цена игры На этих свойствах основаны методы решения матричных игр. 1.4. РЕШЕНИЕ МАТРИЧНОЙ ИГРЫ 2 2 [1, гл, § 3-4], [2, гл, § 5.1], [3, гл, § 5], [6, гл, § 3-4]. Рассмотрим матричную игру размера 2 2 , которая является простейшим случаем конечной игры. Пусть платежная матрица P игры имеет вид 22 21 12 Пусть игра не имеет решения в чистых стратегиях, те. v v . Это означает, что решение следует искать в смешанных стратегиях. Рассмотрим аналитический способ решения. Пусть ) 1 , ( , 2 1 p p p p x , 1 0 p – смешанная стратегия игрока A (если 0 p , то это означает, что игрок A выбрал свою чистую стратегию 2 A ; если 1 p , то это означает, что игрок A выбрал свою чистую стратегию 1 A , что в данном случае недопустимо. Таким образом, обе стратегии игрока A являются активными (определение приведено в разделе 1.5.2). Тогда из свойства 1 и равенства (11) (см. также (в) в 1.5.2) следует, что какую бы чистую стратегию не выбрал игрок B , если ) 1 , ( p p x – оптимальная стратегия игрока A , то цена игры v будет определяться из следующих равенств ). 2 , ( ) 1 ( ), 1 , ( ) 1 ( 22 12 21 11 x H p a p a v x H p a p a v A A (15) Отсюда получим следующее решение 21 12 22 11 21 22 1 a a a a a a p p , 21 12 22 11 12 11 2 a a a a a a p , 21 12 22 11 21 12 11 Аналогичные рассуждения можно провести и для игрока B : если ) 1 , ( , 2 1 q q q q y , 1 0 q – оптимальная смешанная стратегия игрока B , то из свойства 1 и равенства (10) следует, что ). , 2 ( ) 1 ( ), , 1 ( ) 1 ( 22 21 12 11 y H q a q a v y H q a q a v A A (16) Отсюда имеем 21 12 22 11 12 22 1 a a a a a a q q , 21 12 22 11 21 11 а) Так, решение игры из примера 1 будет иметь следующий вид , 1 ) 1 ( , ) 1 ( 1 2 1 2 1 p p v p p v 1 2 1 p p ) 1 ( ) 1 ( 1 1 1 1 p p p p 1 2 1 2 1 1 p p 2 1 1 p 2 1 2 p Таким образом, оптимальной стратегией игрока A будет 2 1 ; 2 1 x , а цена игры Аналогично для игрока B : , 1 ) 1 ( , ) 1 ( 1 2 1 2 1 q q v q q v 1 2 1 q q 2 1 1 q и 2 1 2 q , Значит, игроками при многократном проведении игры следует применять обе свои стратегии в пропорции 1:1. Приведем геометрическое решение игры 2 Отложим по оси абсцисс Ox единичный отрезок 2 1 A A : точка 1 A ( 0 x ) изображает стратегию 1 A , а все промежуточные точки этого отрезка – смешанные стратегии ) , ( 2 1 p p x игрока A , причем расстояние от x до правого конца 2 A – это вероятность 1 p выбора стратегии 1 A , а расстояние долевого конца 1 A вероятность 2 p выбора стратегии 2 A . На перпендикулярных осях I-I и II-II откладываются выигрыши при стратегиях 1 A и 2 A Если игрок B выберет стратегию 1 B , то она даст игроку выигрыши 11 a и 21 a на осях I-I и II-II, соответствующие стратегиями. Обозначим эти точки на осях I-I и II-II буквой 1 B . Средний выигрыш 1 v , соответствующий смешанной стратегии ) , ( 2 1 p p x , определяется тогда по формуле 2 21 1 11 1 p a p a v , и равен ординате точки 1 M , принадлежащей отрезку 1 1 B B и имеющей абсциссу x (см. риса. x I I A 1 0 II II A 2 y x B 1 B 1 a 11 a 21 p 2 v 1 M 1 1 p 1 x I I A 1 0 II II A 2 y x B 2 B 2 a 12 a 22 p 2 v 2 M 2 1 Риса Рис.1б Аналогично, строим отрезок 2 2 B B , соответствующий применению игроком B его стратегии 2 B . При этом средний выигрыш 2 v определяется по формуле 2 22 1 12 2 p a p a v , и равен ординате точки 2 M , принадлежащей отрезку 2 2 B B (см. рис.1б). Объединим риса и рис.1б и покажем графическое решение на рис. A 1 v x * B 2 M 1 A 2 B 2 2 p 1 p B 1 B 1 a 22 I II y x I 0 II a 21 a 11 a 12 Рис В соответствии с принципом максимина оптимальная стратегия x такова, что минимальный выигрыш игрока A (при наихудшем поведении игрока B ) обращается в максимум. Ординаты точек, лежащих на выделенной ломаной 2 1 MB B , на рис показывают минимальный выигрыш игрока A при использовании им любой смешанной стратегии участок M B 1 – против стратегии 1 B , участок 2 MB – против стратегии 2 B ). Оптимальную стратегию определяет точка M , в которой минимальный выигрыш достигает максимума, а ее ордината равна цене игры Пример 3. Применим данный геометрический метод к нахождению оптимальной стратегии игрока A в игре с платежной матрицей 1 3 5 Найдем сначала максимин v и минимакс v : 2 } 1 , 2 max{ v , 3 } 5 , 3 min{ v . Итак, решение нужно искать в смешанных стратегиях. B 2 v x * x 1 I y I A 1 1 A 2 2 p 1 p 0 II II B 1 3 M B 1 2 B 2 5 Рис На рис приведено геометрическое решение примера 3. Используя рис, вычислим точку пересечения прямых 1 1 B B и 2 2 B B . Уравнение прямой 1 1 B B , проходящей через точки (0; 2) и (1; 3): 2 3 2 0 1 Уравнение прямой 2 2 B B , проходящей через точки (0; 5) и (1; 1): 4 1 5 0 1 0 y x 5 Тогда координаты точки пересечения M прямых 1 1 B B и 2 определяются из системы 5 3 , 2 x y x y 5 3 2 x x 5 3 x 5 Таким образом, 5 3 2 x p , 5 2 1 2 1 p p , цена игры 5 Аналогичным способом, приведенным выше, можно определить оптимальную стратегию игрока B , если поменять местами игроков A и B , и вместо максимума нижней границы 2 1 MB B (рис) в соответствии с принципом минимакса рассмотреть минимум верхней границы 2 рис. Абсцисса точки N на ломаной 2 1 NA A определяет значение 2 q в оптимальной стратегии ) , ( 2 1 q q y игрока B , а ордината этой точки – цену игры v N v y * 0 I y I 2 q 1 q A 1 A 2 для игрока B x B 2 II II A 1 a 12 = 5 A 2 a 22 = 1 a 11 = 2 a 21 = Рис Итак, на рис показан графический способ отыскания оптимальной стратегии игрока B в примере 3. Найдем координаты точки N пересечения прямых 1 1 A A и 2 2 A A . Для этого составим уравнения этих прямых. Уравнение прямой 1 1 A A , проходящей через точки (0; 2) и (1; 5): 2 5 2 0 1 0 y x 2 Уравнение прямой 2 2 A A , проходящей через точки (0; 3) и (1; 1): 3 1 3 0 1 0 y x 3 Значит, координаты точки пересечения N прямых 1 1 A A и 2 определяются из системы 3 2 , 2 3 x y x y 3 2 2 3 x x 5 1 x 5 Таким образом, 5 1 2 x q , 5 4 1 2 1 p q , цена игры 5 Сделаем проверку полученного решения. Используем формулу (6): 5 13 25 3 36 10 16 5 1 5 3 1 5 4 5 3 3 5 1 5 2 5 5 4 5 Таким образом, решение найдено Оптимальные смешанные стратегии игроков A и B следующие ; 5 3 ; 5 2 x 5 1 ; 5 Отметим, что графический способ решения годиться ив том случае, если игра имеет решение в чистых стратегиях (подробнее см. [1 гл, § 4]). Если платежная матрица P содержит отрицательные числа, то при графическом решении удобнее перейти к новой матрице, содержащей только положительные числа. Для этого нужно ко всем элементам матрицы P добавить подходящее положительное число. Ответ на вопрос о том, как при этом изменится решение игры с новой матрицей, дает следующая лемма. Лемма (о масштабе, аффинное правило Пусть x и y – оптимальные стратегии двух игроков, а v – цена игры в матричной n m - игре с платежной матрицей P , причем P P , (17) где и – некоторые числа, 0 . Тогда в матричной игре с платежной матрицей P оптимальные стратегии будут такими же, как ив матричной игре с платежной матрицей P , а цена игры v v (18) Лемма о масштабе показывает стратегическую эквивалентность двух игр, отличающихся только началом отсчета выигрышей и масштабом их измерения. 1.5. ГРАФИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР [2, гл, § 1.3], [3, гл, § 6], [4, гл, § 6-7], [5, гл, § 4], [6, гл, § 6]. Рассмотрим матричные игры, число стратегий в которых у одного из игроков равно двум. В этом случае, как и для матричной (игры, решение можно получить геометрически. 1.5.1. РЕШЕНИЕ МАТРИЧНОЙ (ИГРЫ В этом случае платежная матрица P игры имеет вид n n a a a a a a P 2 22 21 1 12 11 (19) Согласно указанным выше свойствам оптимальных стратегий 1-3 нахождение цены игры v и оптимальной стратегии игрока A равносильно разрешению уравнения (см. ф ) 1 ( min max ) 1 ( min 2 1 1 1 0 2 1 1 p a p a p a p a |