Контрольная работа по курсу
«Теория игр и экономическое моделирование», 2009 год
Решения.
Задача 1. На каждый из следующих вопросов принимаются только исчерпывающие ответы с доказательством или контрпримером.
а) Верно ли, что в конечной игре двух лиц для существования равновесия Нэша (РН) в чистых стратегиях достаточно существования доминирующей стратегии хотя бы у одного игрока? Справедливо ли это утверждение для игры 
лиц при 
?
Если в игре двух лиц у одного игрока есть доминирующая стратегия, то достаточно взять на нее наилучший ответ другого игрока, чтобы получить РН, поскольку доминирующая стратегия является наилучшим ответом на любую стратегию.
При существования доминирующей стратегии у одного игрока мало, поскольку при этой стратегии для любых двух игроков может возникнуть, например, антагонистическая игра без РН в чистых стратегиях. Существование у 
игроков доминирующей стратегии влечет существование РН.
б) Можно ли утверждать, что в конечной развернутой игре с полной и точной информацией в совершенном по подыграм РН (СПРН) выигрыши игроков определены однозначно?
Нет. В учебники есть пример, когда существуют два СПРН с разными векторами выигрышей. Достаточным условием для этого утверждения является приведенное в учебнике условие однозначности выигрышей в финальных позициях.
в) Приведите пример игры в развернутой форме, в которой информационная структура не удовлетворяет условию полной памяти.
Представьте дерево конечной двухходовой игры двух лиц, в которой игрок 1, совершая второй ход, не помнит, какой он сделал первый ход. Изобразите такое дерево самостоятельно, полагая, что на каждом шагу у каждого игрока есть два действия.
г) В бесконечной повторяющейся игре 
будем называть стратегии игроков марковскими, если действие игрока в момент 
зависит только от действий игроков в момент 
. Может ли в игре существовать СПРН в марковских стратегиях, отличное от повторения некоторого РН в исходной игре 
?
Простой ответ состоит в том, что чередовать два РН игры. Но и в случае одного РН можно построить марковское СПРН. Остановимся на дилемме заключенного
L | R | |
L | 1,1 | 5,0 |
R | 0,5 | 4,4 |
и рассмотрим стратегии 
«как ты, так и я»: 
,
. Если игроки придерживаются таких стратегий, реализуется последовательность выигрышей 4,4,… Если, скажем, игрок 1 отклонился, сыграв L, то он получит 5 в одном повторении. Но потом последует серия из 1, пока игрок 1 не вернется на R. Если он вернется мгновенно, то условие невыгодности отклоняться примет вид: 
. Если игрок 1 сыграет L два раза подряд, то условие невыгодности отклонения примет вид 
, которое с учетом предыдущего условия автоматически выполняется при 
и т. д. Значит, «как ты так и я» образуют марковское СПРН при 
, как и в случае релейных стратегий.
Задача 2. Рассмотрим следующую игру в нормальной форме, в которой игрок 1 выбирает строки, а игрок 2 – столбцы.
a | b | c | d | e | |
A | (2,5) | (0,2) | (1,2) | (5,1) | (2,3) |
B | (0,2) | (3,8) | (4,6) | (4,9) | (2,3) |
а) Найдите все равновесия Нэша в чистых стратегиях.
Есть только одно РН в чистых стратегиях: (A, a).
б) Найдите все наилучшие ответы игрока 2 на каждую смешанную стратегии игрока 1. Подсказка: Изобразите графически зависимости выигрыша игрока 2 от вероятности выбора стратегии В игроком 1 при фиксированной стратегии игрока 2.
в) Найдите все РН в смешанных стратегиях.
Пусть 
– вероятность выбора игроком 1 стратегии B. Изобразим графически зависимость от ожидаемого выигрыша игрока 2 для каждой из пяти его чистых стратегий:
Верхняя огибающая семейства этих прямых дает значение выигрыша игрока 2 при наилучшем ответе. Заметим, что среди чистых наилучших ответов встречаются только a, b,d. В точке 1/3 есть два чистых наилучших ответа, а значит, и любая их смесь является наилучшим ответом на стратегию (2/3,1/3) игрока 1. В этой точке пересекаются прямые a и b, а другие линии проходят ниже. Получим РН смешанных стратегиях по соответствующей игре 2х2: ((2/3,1/3),(3/5,2/5,0,0,0)). Другое РН в смешанных стратегиях получается при пересечении линий b и d в точке 1/2: ((1/2,1/2),(0,1/4,0,3/4,0)).
г) Пусть теперь игрок 1 делает ход первым, а игрок 2, зная выбор игрока 1, делает ход вторым. Сколько стратегий у каждого игрока в этой игре? Найдите совершенное по подыграм РН в этой игре.
У игрока 1 две стратегии, у игрока 2 теперь 52=25 стратегий по числу функций, определенных на множестве из 2-х элементов и принимающих 5 значений. СПРН приводит к исходу Bd с выигрышами (4,9), что лучше для обоих, чем (2,5) в исходном РН. Чтобы понять это, достаточно посмотреть на приведенную выше матрицу с подчеркнутыми наилучшими ответами и выбрать строку, в которой больше выигрыш игрока 1 с учетом подчеркивания по игроку 2.
д) Пусть теперь игрок 2 делает ход первым, а игрок 1, зная выбор игрока 2, делает ход вторым. Сколько теперь стратегий у каждого игрока в этой игре? Найдите СПРН в этой игре.
У игрока 2 теперь 5 стратегий, а у игрока 1 их 25=32 по числу функций, определенных на множестве из 5-и элементов и принимающих 2 значения. СПРН приводит к исходу Bb и выигрышам (3,8).
Значит, обоим игрокам выгодно, чтобы фиксированный порядок ходов был, причем чтобы первым делал ход игрок 1.
Задача 3. Фирма 1 собирается выйти на рынок, который монопольно обслуживает фирма 2. Если фирма 1 решит все же воздержаться от выхода на этот рынок, то она получит выигрыш, равный 0, а фирма 2 получит 10 (скажем, миллионов долларов). Если фирма 1 все-таки выйдет на рынок, то фирма 2 может либо отреагировать мирно, либо вступить в борьбу против фирмы 1. Если фирма 2 отреагирует мирно, то обе фирмы получат выигрыш по 5. Если фирма 2 вступит в борьбу, то теперь у фирмы 1 есть выбор: принять вызов или покинуть рынок. Если фирма 1 примет вызов и останется, то с учетом затрат на борьбу фирма 1 получит выигрыш 1, в то время как фирма 2 получит 2. Если фирма 1 решит покинуть рынок, не вступая в борьбу, то с учетом затрат на вход в рынок фирма 1 получит выигрыш, равный -1, а фирма 2 получит 6.
а) Изобразите дерево соответствующей игры в развернутой форме.
б) Найдите СПРН методом обратной индукции.
СПРН показано стрелками. Оно соответствует мирному дележу рынка.
в) Постройте нормальную форму данной игры.
В сокращенном виде в нормальной форме у игрока 1 три стратегии: Н (не входит на рынок), ВБ (входить и бороться, если придется), ВП (входить, но покидать рынок, не вступая в борьбу). У игрок 2 две стратегии: Б (бороться) или М (мириться).
Б | М | |
Н | 0,10 | 0,10 |
ВБ | 1,2 | 5,5 |
ВП | -1,6 | 5,5 |
г) Найдите все РН.
Других РН в этой игре нет.
Задача 4. Рассмотрим следующую статическую игру
А | Б | В | |
а | 4,1 | 0,0 | 5,0 |
б | 0,0 | 1,4 | 0,0 |
в | 0,0 | 0,5 | 3,3 |
а) Найдите все РН в чистых и смешанных стратегиях в этой игре.
В чистых стратегиях есть два РН: (а, А) и (б, Б). Есть еще РН в смешанных стратегиях: ((4/5,1/5,0), (1/5,4/5)), в котором выигрыш каждого игрока равен 4/5.
Предположим, что эта игра разыгрывается несколько раз, причем продолжение игры происходит с вероятностью , а с вероятностью 
игра заканчивается. Выигрышем игрока в такой повторяющейся игре 
считается ожидаемая сумма его выигрышей во всех состоявшихся до окончания игры повторениях.
б) Можно ли утверждать, что при некотором 
игра с дисконтированием выигрышей эквивалентна игре ?
В игре вероятность того, что игра повторится раз равна 
. Пусть игрока ожидает выигрыш 
в повторении , если до него дойдет дело, т. е. игра не закончится ранее. Тогда ожидаемый выигрыш равен 
. Значит, игра с ожидаемыми выигрышами совпадает игрой при 
. Отметим, что это верно для любой конечной игры .
в) Можно ли в игре построить СПРН, в котором игроки будут играть (в, В) по всех повторениях до окончания игры?
Здесь прямо нельзя использовать «народную теорему», поскольку нет РН в чистых стратегиях с выигрышами менее 3 для обоих игроков. Один путь – перейти на РН в смешанных стратегиях при отклонении. Другой путь – использовать обычные релейные стратегии с переключением на выгодное равновесие. Например, для игрока 1 выбирать «в», пока игрок 2 тоже выбирает «В», а если игрок 2 выбирает не «В», то переключиться на «а». Аналогично, для игрока 2 переключение происходит на «Б».
Задача 5. человек являются свидетелями преступления. Каждый из них может позвонить в полицию или не звонить. Каждый из них хочет, чтобы полиция была проинформирована, но позвонить самому, значит, понести определенные психологические затраты. Пусть выигрыш от информирования полиции оценивается величиной 
, причем неважно, кто именно и сколько человек позвонит, а затраты оцениваются величиной 
. Пусть 
. Считается, что выигрыш индивида равен 0, если никто не позвонил, равен , если позвонил кто-то другой и равен 
, если позвонил он сам.
а) Найдите РН в чистых стратегиях в этой игре.
Один любой игрок звонит в полицию, а другие нет. Получается РН.
б) Найдите симметричное РН в смешанных стратегиях, в котором каждый игрок звонит в полицию с вероятность 
.
в) Проанализируйте найденное в б) РН в зависимости от параметров и . Что будет происходить с возрастанием с вероятность звонка в полицию фиксированного свидетеля и вероятностью того, что хотя бы кто-то позвонит?
В этом симметричном смешанном РН выигрыш игрока в случае обоих действий должен быть одинаковым. Если игрок звонит, то получает с вероятностью 1. Если он не звонит, то получит с вероятностью 
, что кто-то другой позвонит. Итак, должно быть 
. Чем больше относительные затраты 
, тем меньше вероятность звонка.
При возрастании числа свидетелей вероятность в равновесии уменьшается и стремится к нулю. Вероятность, что никто не позвонит, равна 
и стремится к относительным затратам для больших групп свидетелей. Чем ближе к , тем больше вероятность, что никто не позвонит.
