Антюхов В.И.. Тема 4. Модели конечных стратегических игр Лекция : Парные матричные игры с седловой и без седловой точки Учебные вопросы: 1.Принцип оптимальности. - презентация

1 Антюхов В.И.

2 Тема 4. Модели конечных стратегических игр Лекция : Парные матричные игры с седловой и без седловой точки Учебные вопросы: 1.Принцип оптимальности решения матричных игр (принцип минимакса) 2.Решение игр в смешанных стратегиях 3.Упрощение игр 4.Игра 2 х 2

3 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса)

4 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Рассмотрим игру m x n с матрицей Буквой i будем обозначать номер нашей стратегии, а буквой j – номер стратегии противника A j \ B j B1B1 B2B2 BnBn A1A1 a 11 …a1na1n A2A2 a 21 a 22 …a2na2n …………… AmAm am1am1 am2am2 …a mn

5 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Отбросим вопрос о смешанных стратегиях и будем рассматривать пока только чистые Поставим задачу: определить наилучшую среди наших стратегий А 1, А 2,…, А m Проанализируем последовательно каждую из них, начиная с А 1 и заканчивая А m Выбирая А i, мы должны рассчитывать, что противник ответит на нее той из стратегий B j, для которой наш выигрыш минимален

6 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Найдем минимальное из чисел a ij в i-ой строке и обозначим его α i : α i = min j a ij (1) Знак min j обозначает минимальное значение данного параметра при всех возможных j Рассмотрим игру m x n с матрицей

7 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Выпишем числа α i (минимумы строк) рядом с матрицей справа в виде добавочного столбца A j \ B j B1B1 B2B2 BnBn αiαi (Минимумы строк) A1A1 a 11 …a1na1n α1α1 A2A2 a 21 a 22 …a2na2n α2α2 ……………… AmAm am1am1 am2am2 …a mn αmαm βjβj β1β1 β2β2 …βnβn (Максимумы столбцов)

8 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Выбирая какую-то стратегию А i, мы должны рассчитывать на то, что в результате разумных действий противника мы выиграем только α i. Естественно, действуя наиболее осторожно (то есть избегая всякого риска), мы должны предпочесть другим ту стратегию, для которой число α i максимально Обозначим это максимальное значение α: α = max j α i, или принимая во внимание формулу (1): α = max i min j a ij (2)

9 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Величина α называется нижней ценой игры, иначе – максиминным выигрышем или максимином Та стратегия игрока А i, которая соответствует максимуму α, называется максиминной стратегией

10 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Очевидно, что если мы будем придерживаться максиминной стратегии, то нам при любом поведении противника гарантирован выигрыш, во всяком случае, не меньший α Поэтому величина α и называется «нижней ценой игры». Это – тот гарантированный минимум, который мы можем себе обеспечить, придерживаясь своей наиболее осторожной («перестраховочной») стратегии

11 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Очевидно, аналогичное рассуждение можно провести и за противника В. Он заинтересован в том, чтобы обратить наш выигрыш в минимум; значит он должен просмотреть все свои стратегии, выделяя для каждой из них максимальное значение выигрыша Выпишем внизу матрицы максимальное значение a ij по столбцам: β = max j a ij и найдем из них минимальное: β i = min j β j или β = min j max i a ij (3)

12 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Величина β называется верхней ценой игры, иначе минимаксным выигрышем или минимаксом Соответствующая выигрышу β стратегия противника называется его минимаксной стратегией Придерживаясь своей наиболее осторожной минимаксной стратегии, противник гарантирован, что в любом случае он выиграет не больше β

13 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Принцип осторожности, диктующий игрокам выбор соответствующих стратегий (максиминной или минимаксной), является в теории игр основным и называется принципом минимакса. Он вытекает из предположения о разумности каждого игрока, стремящегося достигнуть цели, противоположной цели противника Наиболее «осторожные» максиминную и минимаксную стратегии часто обозначают общим термином «минимаксные стратегии»

14 Учебный вопрос 1. Принцип оптимальности решения матричных игр (принцип минимакса) Построим платёжную матрицу, определим нижнюю и верхнюю цены игры, а также минимаксные стратегии для ряда примеров

15 Пример 1. Игра «Поиск» Имеется два игрока А и В, игрок А прячется, а В его ищет В распоряжении А имеется два убежища (I и II), любое из которых он может выбрать по своему усмотрению Условия игры таковы: - если В найдет А в том убежище, где А спрятался, то А платит ему штраф 1 руб.; - если В не найдет А (то есть будет искать в другом убежище), то он сам должен заплатить А такой же штраф Требуется: построить платежную матрицу, найти нижнюю и верхнюю цены игры, а также минимаксные стратегии

16 Пример 1. Игра «Поиск» Решение: Игра состоит всего из двух ходов, оба – личные У нас (А) – две стратегии: А 1 – прятаться в убежище I; А 2 – прятаться в убежище II У противника (В) – две стратегии: В 1 – искать в убежище I; В 2 – искать в убежище II

17 Пример 1. Игра «Поиск» Перед нами игра 2*2. Ее матрица имеет вид: На примере этой игры, как она ни элементарна, можно уяснить себе некоторые важные идеи теории игр B1B1 B2B2 A1A1 1 A2A2 1

18 Пример 1. Игра «Поиск» Предположим сначала, что данная игра выполняется только один раз (играется единственная «партия») Тогда, очевидно, что нет смысла говорить о преимуществах тех или других стратегий – каждый из игроков может с равным основанием принять любую из них Однако при многократном повторении игры положение меняется

19 Пример 1. Игра «Поиск» Действительно, допустим, что мы (игрок А) выбрали какую-то стратегию (скажем, А 1 ) и придерживаемся ее Тогда, уже по результатам первых нескольких партий, противник догадается о нашей стратегии, начнет всегда искать в убежище I и выигрывать То же будет, если мы выберем стратегию А 2

20 Пример 1. Игра «Поиск» Нам явно не выгодно придерживаться одной какой-то стратегии: чтобы не оказаться в проигрыше, мы должны чередовать их Однако, если мы будем чередовать убежища I и II в какой-то определенной последовательности (скажем, через одну партию), противник тоже догадается об этом и ответит наихудшим для нас образом Очевидно, надежным способом, гарантирующим нас от верного проигрыша, будет такая организация выбора в каждой партии, когда мы сами его наперед не знаем Например, можно бросить монету, и, если выпадет герб, выбрать убежище I, а если решка – убежище II

21 Пример 1. Игра «Поиск» Печальное положение, в котором оказался игрок А (чтобы не проигрывать, выбирать убежище случайным образом), очевидно, присуще не только ему, но и его противнику В, для которого справедливы все приведенные выше рассуждения Оптимальной стратегией каждого оказывается «смешанная» стратегия, в которой две возможные стратегии игрока чередуются случайным образом, с одинаковыми вероятностями

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

23 Пример 1. Игра «Поиск» Определим минимумы строк α i и максимумы столбцов β j получим: Так как величины α i и β j постоянны и равны соответственно -1 и +1, нижняя и верхняя цены игры также равны -1 и +1: α = -1, β = +1. B1B1 B2B2 αiαi A1A1 1 A2A2 1 βjβj 11

24 Пример 1. Игра «Поиск» Любая стратегия игрока А является его максиминной, а игрока В – его минимаксной стратегией Вывод тривиален: придерживаясь любой из своих стратегий, игрок А может гарантировать, что он проиграет не более 1 руб.; то же может гарантировать и игрок В при любой своей стратегии

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

26 Пример 1. Игра «Три пальца» У каждого игрока по три стратегии: - показывать один, два или три пальца Матрица игры 3*3 имеет вид: Проанализируем ситуацию. Очевидно, на любую нашу стратегию противник может ответить наихудшим для нас образом B1B1 B2B2 B3B3 A1A A2A2 4-5 A3A3 4 6

27 Пример 2. Игра «Три пальца» Например: - если мы выбираем А 1, он нам ответит В 2, и мы проиграем 3 руб.; - на стратегию А 2 он нам ответит В 3, и мы проиграем 5 руб.; - на стратегию А 3 он нам ответит В 2, и мы снова проиграем 5 руб. Очевидно, некоторое преимущество имеет стратегия А 1 (при ней проигрыш минимален), но и она для нас явно невыгодна, так как всегда ведет к проигрышу Однако попробуем стать на точку зрения второго игрока (В). Его положение тоже не из блестящих: - если он выберет В 1, мы ответим ему А 3 и он отдаст нам 4 руб.; - если он выберет В 2, мы ответим ему А 2 и снова получим 4 руб.; - на В 3 у нас есть ответ А 3, приводящий к еще худшему результату: В проиграет 6 руб.

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

29 Пример 1. Игра «Три пальца» Теперь, выписывая минимумы строк и максимумы столбцов, найдем нижнюю цену игры α = -3 и верхнюю β = 4 B1B1 B2B2 B3B3 αiαi A1A A2A2 4-5 A3A3 4 6 βjβj 446

30 Пример 2. Игра «Три пальца» Наша максиминная стратегия А 1 (применяя ее систематически, мы гарантируем, что выиграем не меньше -3, то есть проиграем не больше 3) Минимаксная стратегия противника – любая из стратегий В 1 и В 2 : применяя их систематически, он может гарантировать, что не отдаст более 4 Если мы отступим от своей максиминной стратегии (например, выберем А 2 ), то противник может нас «наказать» за это, применив В 3 и сведя наш выигрыш к -5 Равным образом и отступление противника от его минимаксной стратегии может быть «наказано» увеличением его проигрыша до 6

31 Пример 2. Игра «Три пальца» Следует обратить внимание на то, что минимаксные стратегии в данном случае не устойчивы Действительно, пусть, например, противник выбрал одну из своих минимаксных стратегий В 1 и придерживается ее. Узнав об этом, мы перейдем к стратегии А 3 и будем выигрывать 4 На это противник ответит стратегией В 2 и будет выигрывать 5 На это мы, в свою очередь, ответим стратегией А 2 и будем выигрывать 4 и т.д. Таким образом, положение, при котором оба игрока пользуются своими минимаксными стратегиями, является неустойчивым и может быть нарушено поступившими сведениями о стратегии, которую применяет противная сторона Однако такая неустойчивость наблюдается не всегда. Это можно увидеть из следующего примера

32 Пример 3. Игра «Вооружение и самолёт» В нашем распоряжении имеется три вида вооружения: А 1, А 2 и А 3, у противника – три вида самолетов: В 1, В 2 и В 3 Наша задача – поразить самолет Задача противника – сохранить его непораженным Наш личный ход – выбор типа вооружения Личный ход противника – выбор самолета для боевых действий

33 Пример 3. Игра «Вооружение и самолёт» В данной игре имеется еще и случайный ход – применение вооружения: - вооружением А 1 самолеты В 1, В 2 и В 3 поражаются соответственно с вероятностями 0.5; 0.6; 0.8; - вооружением А 2 самолеты В 1, В 2 и В 3 поражаются соответственно с вероятностями 0.9; 0.7; 0.8; - вооружением А 3 самолеты В 1, В 2 и В 3 поражаются соответственно с вероятностями 0.7; 0.5; 0.6 Требуется: построить платежную матрицу, найти нижнюю и верхнюю цены игры, минимаксные стратегии и проанализировать ситуацию

34 Пример 3. Игра «Вооружение и самолёт» Решение: Матрица игры 3*3 имеет вид: В этой матрице выигрыш – вероятность поражения самолета (мы стремимся его максимизировать, а противник – минимизировать) B1B1 B2B2 B3B3 A1A A2A A3A

35 Пример 3. Игра «Вооружение и самолёт» Эта игра обладает некоторыми особыми свойствами, незаметными на первый взгляд Станем вначале на точку зрения игрока А и переберем одну за другой все его стратегии: - на А 1 противник ответит нам В 1, и мы выиграем 0.5; - на А 2 противник ответит нам В 2, и мы выиграем 0.7; - на А 3 противник ответит нам В 2, и мы выиграем 0.5 Очевидно, некоторое преимущество над другими имеет стратегия А 2 – при ней мы выигрываем больше, а именно 0.7

36 Пример 3. Игра «Вооружение и самолёт» Станем теперь на точку зрения противника, а он хочет отдать поменьше: - при стратегии В 1 – мы отвечаем ему А 2 и он отдает 0.9; - при стратегии В 2 – мы отвечаем ему А 2 и он отдает 0.7; - при стратегии В 3 – мы отвечаем ему А 2 и он отдает 0.8. Естественно, противник предпочтет В 2, чтобы отдать только 0.7

37 Пример 3. Игра «Вооружение и самолёт» Мы видим, что в данном примере стратегии А 2 и В 2 с выигрышем 0.7 являются наивыгоднейшими сразу для обеих сторон: - игроку А выгоднее всего выбирать стратегию А 2 ; - игроку В выгоднее всего выбирать стратегию В 2, и максимальный выигрыш А совпадет с минимальным проигрышем В

38 Пример 3. Игра «Вооружение и самолёт» Достигнуто как бы положение равновесия: - если А выберет стратегию А 2, то В не может найти лучшего выхода, чем В 2 и наоборот: - если В выберет стратегию В 2, то А не может найти лучшего выхода, чем А 2 В дальнейшем мы увидим, что пара стратегий, обладающих таким свойством, являются оптимальными стратегиями сторон и образуют так называемое решение игры

39 Пример 3. Игра «Вооружение и самолёт» Определим теперь нижнюю и верхнюю цены игры: В данном случае нижняя цена игры равна верхней: α = β = 0.7 B1B1 B2B2 B3B3 αiαi A1A A2A A3A βjβj

40 Пример 3. Игра «Вооружение и самолёт» Минимаксные стратегии А 2 и В 2 являются устойчивыми: если один из игроков придерживается своей минимаксной (максиминной) стратегии, то другой игрок никак не может улучшить свое положение, отступая от своей Таким образом, мы видим, что существуют игры, для которых нижняя цена равна верхней: α = β

41 Учебный вопрос 2. Решение игр в смешанных стратегиях

42 Учебный вопрос 2. Решение игр в смешанных стратегиях Среди конечных игр, имеющих практическое значение, не так уж часто встречаются игры с седловой точкой Более типичным является случай, когда нижняя и верхняя цены игры различны Если проанализировать такие матрицы таких игр, можно сделать вывод: - если каждому игроку предоставить выбор одной-единственной чистой стратегии, то в расчете на разумного противника этот выбор должен определяться принципом минимакса При этом игрок А гарантирует себе выигрыш, равный нижней цене игры α

43 Учебный вопрос 2. Решение игр в смешанных стратегиях Возникает вопрос: нельзя ли гарантировать выигрыш, больший α, если применять не одну-единственную, «чистую» стратегию, а чередовать случайным образом несколько стратегий? Такие стратегии, состоящие в случайном чередовании чистых стратегий, называются в теории игр смешанными При пользовании смешанной стратегией перед каждой партией игры пускается в ход какой-то механизм случайного выбора (бросание монеты, игральной кости или вычитание машиной случайного числа от 0 до 1), обеспечивающий появление каждой стратегии с некоторой вероятностью, и затем принимается та стратегия, на которую пал жребий

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

45 Учебный вопрос 2. Решение игр в смешанных стратегиях Введем специальное обозначение для смешанных стратегий Пусть имеется игра, в которой: - у нас (А) m стратегий А 1, А 2,…, А m ; - у противника (В) – n стратегий: В 1, В 2,…, В n Будем обозначать: S A = (p 1, p 2,…, p m ) нашу смешанную стратегию, в которой стратегии А 1, А 2,…, А m применяются соответственно с вероятностями p 1, p 2,…, p m, причем p 1 + p 2 +…+ p m = 1 Аналогичное обозначение для смешанной стратегии противника будет: S B = (q 1, q 2,…, q n ), где q 1 + q 2 +…+ q n = 1

46 Учебный вопрос 2. Решение игр в смешанных стратегиях Очевидно, каждая чистая стратегия является частным случаем смешанной: все стратегии, кроме данной, имеют вероятности, равные нулю, а данная – единице Оказывается, если допустить не только чистые, но и смешанные стратегии, то можно для каждой конечной игры найти решение, то есть пару устойчивых оптимальных стратегий игроков Решением игры называется пара оптимальных стратегий S A *, S B *, в общем случае смешанных, обладающих следующим свойством: - если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей

47 Учебный вопрос 2. Решение игр в смешанных стратегиях Выигрыш, соответствующий решению, называется ценой игры Будем обозначать ее (как и раньше чистую цену) буквой ν Существует так называемая основная теорема теории игр, состоящая в следующем: - каждая конечная игра имеет по крайней мере одно решение, возможно, в области смешанных стратегий Из основной теоремы следует, что каждая конечная игра имеет цену. Цена игры ν всегда лежит между нижней ценой игры α и верхней ценой игры β: ν α β

48 Учебный вопрос 2. Решение игр в смешанных стратегиях Действительно, α есть максимальный гарантированный выигрыш, который мы можем себе обеспечить, применяя только свои чистые стратегии Так как смешанные стратегии содержат в качестве частного случая все чистые, то, допуская кроме чистых еще и смешанные стратегии, мы, во всяком случае, не ухудшим своих возможностей, значит: ν α Аналогично, рассматривая возможности противника, видно, что: ν β, откуда: α ν β

49 Учебный вопрос 2. Решение игр в смешанных стратегиях Предположим, что в игре m x n нами найдено решение, состоящее из двух оптимальных стратегий: S A * = (p 1, p 2,…, p m ); S B * = (q 1, q 2,…, q n ) В общем случае, некоторые из чисел p 1, p 2,…, p m ; q 1, q 2,…, q n могут быть равными нулю, то есть не все стратегии, доступные игроку, входят в его оптимальную смешанную стратегию Будем называть активными стратегиями игрока те, которые входят в его оптимальную смешанную стратегию с отличными от нуля вероятностями

50 Учебный вопрос 2. Решение игр в смешанных стратегиях Для решения игр существенное значение имеет следующая теорема об активных стратегиях: - если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры ν, независимо от того, что делает другой игрок, если только тот не выходит за пределы своих активных стратегий (то есть пользуется любой из них в чистом виде или смешивает их в любых пропорциях)

51 Учебный вопрос 3. Упрощение игр

52 Учебный вопрос 3. Упрощение игр Если игра m x n не имеет седловой точки, то отыскание ее решения, особенно при больших m и n, представляет собой довольно трудоемкую задачу Иногда эту задачу удается упростить, если предварительно «редуцировать» игру, то есть сократить число стратегий путем вычеркивания некоторых излишних Излишние стратегии бывают двух родов: - дублирующие; - заведомо невыгодные

53 Учебный вопрос 3. Упрощение игр Рассмотрим, например, игру с матрицей А i \ В j В1В1 В2В2 В3В3 В4В4 А1А А2А А3А А4А4 4310

54 Учебный вопрос 3. Упрощение игр Из матрицы видно, что стратегия A 3 в точности повторяет («дублирует») стратегию A 1, потому любую из этих двух стратегий можно вычеркнуть Далее, сравнивая почленно строки A 1 и A 2 видим, что все элементы строки A 2 меньше (или равны) соответствующих элементов строки A 1 Значит, стратегия A 2 для нас, желающих выиграть, заведомо невыгодна Вычеркивая A 3 и A 2, приведем матрицу к более простому виду

55 Учебный вопрос 3. Упрощение игр А i \ В j В1В1 В2В2 В3В3 В4В4 А1А А4А4 4310

56 Учебный вопрос 3. Упрощение игр Далее замечаем, что для противника стратегия В 3 заведомо невыгодна, вычеркиваем и её, и матрица приведена к виду: Таким образом, игра 4 х 4 сведена к игре 2 х 3 А i \ В j В1В1 В2В2 В4В4 А1А1 123 А4А4 430

57 Учебный вопрос 3. Упрощение игр Иногда удается упростить игру искусственным введением вместо чистых стратегий – смешанных Пусть, например, имеется игра 3 х 4 с матрицей: А i \ В j В1В1 В2В2 В3В3 В4В4 А1А А2А А3А3 5511

58 Учебный вопрос 3. Упрощение игр Рассматривая матрицу замечаем, что, в силу симметрии элементов столбцов В 1 и В 2, В 3 и В 4, а также строк А 1 и А 2, эти стратегии, если входят в решение, то только с одинаковыми вероятностями: p 1 = p 2 ; q 1 = q 2 ; q 3 = q 4 Отсюда возникает идея: заранее объединить стратегии В 1 и В 2 в одну смешанную стратегию В 12, состоящую наполовину из В 1, наполовину из В 2 Также можно поступить со стратегиями В 3 и В 4, то есть объединить их в одну смешанную стратегию В 34, в которую В 3 и В 4 входят с одинаковыми вероятностями ½

59 Учебный вопрос 3. Упрощение игр Приводим матрицу к виду: Теперь видно, что если противник пользуется стратегиями В 12, В 34, стратегии А 1 и А 2 дублируют друг друга А i \ В j В 12 В 34 А1А1 2,53,5 А2А2 2,53,5 А3А3 51

60 Учебный вопрос 3. Упрощение игр Вычеркивая какую-либо из них (или объединяя А 1 и А 2 в одну А 12 ), приводим матрицу к виду 2 х 2: Таким образом, игра 3 х 4 сведена к игре 2 х 2 А i \ В j В 12 В 34 А 12 2,53,5 А3А3 51

61 Учебный вопрос 3. Упрощение игр Приступая к решению любой игры m x n, необходимо прежде всего выполнить следующие процедуры: - посмотреть, нет ли в матрице седловой точки: если есть, решение уже найдено; - если седловой точки нет, сравнить между собой почленно столбцы и строки с целью вычеркивания дублирующих и заведомо невыгодных стратегий; - посмотреть, нельзя ли уменьшить число стратегий путем замены некоторых групп чистых – смешанными

62 Учебный вопрос 4. Игра 2 х 2

63 Учебный вопрос 4. Игра 2 х 2 Наиболее простым случаем конечной игры является игра 2х2, где у каждого игрока две стратегии Рассмотрим игру 2х2 с матрицей: А i \ В j В1В1 В2В2 А1А1 a 11 a 12 А2А2 a 21 a 22

64 Учебный вопрос 4. Игра 2 х 2 Здесь могут встретиться два случая: - игра имеет седловую точку; - игра не имеет седловой точки В первом случае решение очевидно: это – пара стратегий, пересекающихся в седловой точке. Нетрудно доказать, что если игра 2х2 имеет седловую точку, то в этой игре всегда какая-нибудь из стратегий может быть отброшена как заведомо невыгодная или дублирующая Второй случай: предположим, что в матрице 2х2 седловой точки нет. При этом нижняя цена игры не равна верхней: α β Решение должно быть в смешанных стратегиях

65 Учебный вопрос 4. Игра 2 х 2 Найдем это решение, то есть пару оптимальных смешанных стратегий: S A * = (p 1, p 2 ); S B * = (q 1, q 2 ) Сначала определим оптимальную смешанную стратегию S A * Согласно теореме об активных стратегиях (если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры ν, независимо от того, что делает другой игрок, если только тот не выходит за пределы своих активных стратегий (то есть пользуется любой из них в чистом виде или смешивает их в любых пропорциях))

66 Учебный вопрос 4. Игра 2 х 2 Если будем придерживаться этой стратегии, то, независимо от образа действий противника (если он только не выходит за пределы своих активных стратегий), выигрыш будет оставаться равным цене игры ν В игре 2х2 обе стратегии противника являются активными (иначе игра имела бы седловую точку) Значит, если мы придерживаемся своей оптимальной стратегии S A * = (p 1, p 2 ), то противник может, не меняя выигрыша, применять любую из своих чистых стратегий

67 Учебный вопрос 4. Игра 2 х 2 Отсюда имеем два уравнения: a 11 p 1 + a 21 p 2 = ν, a 12 p 1 + a 22 p 2 = ν, (1) Из этих уравнений, принимая во внимание условие p 1 + p 2 = 1, получим:

68 Учебный вопрос 4. Игра 2 х 2 Цену игры ν найдем, подставляя значения p 1, p 2 в любое из уравнений (1):

69 Учебный вопрос 4. Игра 2 х 2 Аналогично находится оптимальная стратегия противника: S B * = (q 1, q 2 ) из уравнений: a 11 q 1 + a 21 q 2 = ν, a 12 q 1 + a 22 q 2 = ν, (4) откуда:

70 Учебный вопрос 4. Игра 2 х 2 Пример 1. Найти решение игры «поиск». Решение: Игра 2х2 с матрицей: не имеет седловой точки: α = -1, β = +1 А i \ В j В1В1 В2В2 А1А1 1 А2А2 1

71 Учебный вопрос 4. Игра 2 х 2 Ищем решение в смешанных стратегиях По формулам (2), (3), (5) получаем: p 1 = 1/2; p 2 = 1/2; ν = 0; q 1 = 1/2; q 2 = 1/2; S A * = (1/2; 1/2); S B * = (1/2; 1/2)

72 Учебный вопрос 4. Игра 2 х 2 Следовательно, оптимальная стратегия каждого игрока состоит в том, чтобы случайным образом чередовать свои чистые стратегии, пользуясь каждой из них с вероятностью ½; при этом средний выигрыш будет равен нулю (этот вывод уже был получен нами из интуитивных соображений) Рассмотрим игру, решение которой не является столь очевидным

73 Учебный вопрос 4. Игра 2 х 2 Пример 2. Игра «Два бомбордировщика и истребитель» Сторона А посылает в район расположения противника В два бомбардировщика I и II; I летит спереди, II – сзади Один из бомбардировщиков (заранее неизвестно, какой) должен нести бомбу; другой выполняет только функцию сопровождения В районе противника бомбардировщики подвергаются нападению истребителя стороны В Оба бомбардировщика вооружены пушками

74 Учебный вопрос 4. Игра 2 х 2 Если истребитель атакует задний бомбардировщик, то по нему ведут огонь пушки только этого бомбардировщика, поражающие истребитель с вероятностью 0.3 Если же истребитель атакует передний бомбардировщик, по нему ведут огонь пушки как переднего, так и заднего бомбардировщика; совместно они поражают его с вероятностью: 1 – (1 – 0.3) 2 = 0.51

75 Учебный вопрос 4. Игра 2 х 2 Если истребитель не сбит ответным огнем бомбардировщика, то он поражает выбранную им цель с вероятностью 0.8 Задача бомбардировщика – донести бомбу до цели; задача истребителя – воспрепятствовать этому Требуется: найти оптимальную стратегию сторон: - для стороны А – какой бомбардировщик сделать носителем? - для стороны В – какой бомбардировщик атаковать?

76 Учебный вопрос 4. Игра 2 х 2 Решение: Составим матрицу игры, для чего найдем средний выигрыш при каждой комбинации стратегий Выигрыш – вероятность не поражения носителя 1. А 1 В 1 – носитель I, атакуется I Носитель не будет поражен, если бомбардировщики собьют истребитель, или же если они его не собьют, но и он не поразит свою цель. Вероятность того, что оба бомбардировщика вместе поразят истребитель, равна 0.51, поэтому: a 11 = (1 – 0.51)(1 – 0.8) = A 2 B 1 – носитель II, атакуется I ; а 21 = 1 3. A 1 B 2 – носитель I, атакуется II; а 12 = 1 4. A 2 B 2 – носитель II, атакуется II; а 22 = *0.2 = 0.44

77 Учебный вопрос 4. Игра 2 х 2 Матрица игры с добавочным столбцом и строкой: А i \ В j В1В1 В2В2 αiαi А1А А2А βjβj 11

78 Учебный вопрос 4. Игра 2 х 2 Нижняя – цена игры α = 0.608, верхняя – β = 1 Игра не имеет седловой точки; решение достигается в смешанных стратегиях По формулам (2), (3), (5) находим ( с точностью до третьего знака после запятой):

79 Учебный вопрос 4. Игра 2 х 2 В данном случае q 1 = p 1 ; q 2 = p 2 в силу того, что: a 12 = a 21 Итак, оптимальные стратегии сторон и цена игры найдены: S A * = (0.588, 0.412); S B * = (0.588, 0.412); ν = 0.768, то есть наша оптимальная стратегия состоит в том, чтобы в 58.8% всех случаев (с вероятностью 0.588) делать носителем I, а в 41.2% случаев – II Аналогично противник должен с вероятностью атаковать первый бомбардировщик, а с вероятностью – второй. При этом сторона А будет выполнять свою задачу – доносить бомбы до цели – с вероятностью 0.768, что больше нижней цены игры и меньше верхней цены игры, равной 1

80 Учебный вопрос 4. Игра 2 х 2 Посмотрим, как решается задача 2 х 2 Рассмотрим матричную игру, в которой каждый игрок имеет две чистых стратегии:

81 Учебный вопрос 4. Игра 2 х 2 Будем считать, что седловой точки в данной игре нет Пусть: Р = (р, 1 - р) Т – произвольная смешанная стратегия игрока I; Q = (q, 1 - q) T – произвольная смешанная стратегия игрока II Смешанная стратегия первого игрока однозначно определяется вероятностью выбора им своей первой чистой стратегии – р Аналогично, смешанная стратегия второго игрока определяется вероятностью q

82 Учебный вопрос 4. Игра 2 х 2 Пусть второй игрок выбрал свою первую стратегию Тогда вероятность р должна удовлетворять уравнению: Если второй игрок выберет свою вторую стратегию, тогда:

83 Учебный вопрос 4. Игра 2 х 2 Решив эту систему из двух уравнений с двумя неизвестными, получим: Рассуждая аналогично, для второго игрока получим: