Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE \* MERGEFORMAT 7
Экзаменационная работа по курсу с решениями задач.
«Теория игр и экономическое моделирование», 2010 год
Время выполнения: 2 часа 50 минут.
Задача 1. Два соседа решают, сколько времени потратить на реконструкцию их общей дороги. Если сосед 1 потратит времени, а сосед 2 – , то качество дороги будет оцениваться величиной . Затраты соседа 1 оцениваются величиной , а соседа 2 – величиной , где . Сосед 2 знает , а сосед 1 не знает , но полагает, что с вероятностью величина равна 0.5, а с вероятностью величина равна 1.
а) Сформулируйте соответствующую байесовскую игру.
, где .
б) Найдите РБН в этой игре, как функцию от параметра .
Стратегии: у игрока 1 стратегии , у игрока 2 стратегии .
Нужно найти из условий наилучшего ответа игрока 1 и двух типов игрока 2.
Для игрока 2 типа 0.5 найдем максимум функции по :
. Значит, .
Для игрока 2 типа 1 найдем максимум функции по :
. Значит, .
Для игрока 1 найдем наилучший ответ на смешанную стратегию: с вероятностью , с вероятностью . В силу линейности по удобно ввести средний вклад игрока 2: .
Для игрока 1 найдем максимум ожидаемого выигрыша как максимум функции по :
Значит, .
Поскольку , то
,, .
в) Сравните численно случаи .
При получаем Симметричный случай с полной информацией.
При получаем Асимметричный случай с полной информацией: более эффективный сосед больше работает.
При получаем игру с неполной информацией и РБН, равным . Интерпретация ясна: .
Прочите начало лекции 10 (стр. 123-125). Там разбирается полностью аналогичная задача. Увы… Я думал, ее решат почти все.
Задача 2. Рассмотрим конкуренцию двух фирм, производящих программное обеспечение, которые продают операционные системы (OS) для персональных компьютеров (PC). Каждая из двух фирм предлагает «взятку» в виде контракта производителю PC. Будем считать, что производитель соглашается на большую из взяток и , а меньшую взятку отвергает. При равенстве взяток выбор фирмы определяется бросанием симметричной монеты.
Отвергнутая фирма получает выигрыш 0. Победившая фирма платит производителю PC . Производитель PC выпускает компьютер, совместимый только с программными продуктами фирмы , и фирма становится монополистом на рынке с заданной обратной функцией спроса , где – выпуск продукта, а – цена на рынке при выпуске .
Предельные затраты фирм являются независимыми и равномерно распределенными случайными величинами из отрезка [0,1]. Это информация является общей для фирм. Каждая фирма знает , но не знает реализацию .
а) Сколько продукции выпустит монополист программного обеспечения, и каков будет его выигрыш (прибыль без учета взятки)?
Найдем максимум ,
получим , .
б) Опишите байесовскую игру между производителями OS.
. Типы распределены равномерно и независимо друг от друга. Доход победителя , подавшего большую взятку, равен . Его выигрыш равен . Доход проигравшего равен 0.
в) Найдите симметричное равновесие Байеса-Нэша в этой игре для заданной формы стратегий: .
Заметим, что при функция такого вида монотонно убывает от до . Найдем вероятность победы игрока при взятке , т.е. события , или . Если , то правая часть неравенства отрицательная, а левая – нет. Поэтому такую взятку давать нет смысла. При вероятность победы равна
.
Тогда выигрыш будет равен . Для удобства максимизации возведем выигрыш в квадрат и умножим его на : .
Из условий 1-го порядка получаем: , или
Отсюда: , . В РБН .
г) Предположим, что спрос на РС пропорционален спросу на программное обеспечение. Выгодно ли производителю PC принимать максимальную взятку в долгосрочном плане? Обоснуйте свой вывод.
В РБН большую взятку дает фирма с меньшими затратами. У нее и монопольный выпуск больше, поэтому и спрос на PC будет больше. Так что, и сейчас взятка больше, и потом доходы у производителя PC будут больше.
Задача 3. Рассмотрим следующую игру.
а) Постройте нормальную форму для этой игры в развернутой форме и найдите в ней все равновесия Нэша.
|
Aa |
1,1.2 |
2.6,1 |
|
Ad |
1.6,1.2 |
2,1.6 |
|
Da |
0.6,1.2 |
1.8,0.6 |
|
Dd |
1.2,1.2 |
1.2,1.2 |
Ясно, что РН в чистых стратегиях нет. Ясно также, что у игрока 1 стратегия Ad строго доминирует стратегии Da и Dd. После их вычеркивания останется подматрица, в которой находится РН в смешанных стратегиях:
|
Aa |
1,1.2 |
2.6,1 |
2/3 |
|
Ad |
1.6,1.2 |
2,1.6 |
1/3 |
|
1/2 |
1/2 |
Итак, нашли РН в смешанных стратегиях:
с выигрышами (1.8,1.2).
б) Найдите все СБР. Приведите полное доказательство.
Выигрыш игрока 2 при ходе : .
Выигрыш игрока 2 при ходе : .
Ход лучше хода при .
Перебираем стратегии игрока 1.
Aa. Тогда , а игрок 2 ответит ходом . Игроку 1 выгодно отклониться ходом d.
Ad. Тогда , а игрок 2 ответит ходом . Игроку 1 отклоняться выгодно ходом a.
Da. Тогда , а игрок 2 ответит ходом . Игроку 1 выгодно отклониться ходом d.
Dd. Вне равновесного пути представления игрока 2 могут быть любыми. Но, как бы ни пошел игрок 2, игроку 1 выгодно отклониться от D.
Итак, в игре нет СБР в чистых стратегиях.
Чтобы найти СБР в смешанных стратегиях, нужно найти такое , чтобы ходы и игрока 2 приносили бы ему одинаковые выигрыши:
.
Вероятность хода A игрока 1 должна быть равна 1, поскольку этот ход дает положительный ожидаемый выигрыш, против выигрыша 0 после хода D. По правилу Байеса вероятность хода a должна быть равна 2/3, чтобы 0.6 (2/3) равнялось бы 0.4. Значит, вероятность хода d равна 1/3.
Осталось найти условия на вероятность хода , чтобы игроку 1 играть a также выгодно, как и играть d: . Итак, мы нашли целое семейство СБР в смешанных стратегиях. Выпишем вероятности ходов в таблицу:
|
A |
D |
a |
d |
|||
|
1 |
0 |
2/3 |
1/3 |
1/2 |
1/2 |
Задача 4. Рассмотрим следующую игру
а) Сколько стратегий у игроков 1 и 2?
У игрока 1: стратегий. У игрока 2: стратегий.
а) Найдите все СПРН в чистых стратегиях в этой игре.
В этой игре есть две собственные подыгры. Выпишем их нормальные формы.
|
A |
B |
C |
|
|
u |
0,3 |
3,0 |
2,2 |
|
m |
1,1 |
1,1 |
2,2 |
|
d |
3,0 |
0,3 |
2,2 |
В этой подыгре есть только одно РН: Cm. В смешанных стратегиях m доминируется полусуммой u и d. После исключения m получаем
|
A |
B |
C |
|
|
u |
0,3 |
3,0 |
2,2 |
|
d |
3,0 |
0,3 |
2,2 |
Смешанное равновесие в подматрице
|
A |
B |
|
|
u |
0,3 |
3,0 |
|
d |
3,0 |
0,3 |
не расширяется на всю игру, поскольку ожидаемый в РН выигрыш 1.5 меньше 2, что делает выгодным, например, отклонение игрока 2 с выбором C.
Итак, в этой подыгре есть только одно равновесие (m,C) с выигрышами (2,2).
В другой подыгре с нормальной формой
|
G |
H |
|
|
J |
1,1 |
0,5 |
|
K |
5,0 |
3,3 |
Стратегия H строго доминирует стратегию G. Есть одно РН: (K,H) с выигрышами (3,3).
Получается одно СПРН: RHKCm с выигрышами (3,3).
б) Какие из найденных СПРН могут быть достроены до СБР, а какие – нет?
Найденное СПРН не может быть достроено до СБР, потому, что при m игрок 1 получает выигрыш 1, при u: , а при d: . Если взять , то минимум этого выражения достигается в точке и равен 1.5, что больше выигрыша при m. Значит, m не может согласоваться ни с одним представлением . Хотя это информационное множество лежит вне равновесного пути, но u оптимальна , d оптимальна , а смешанная стратегия (0.5,0,0.5) (как и любая другая смешанная стратегия) оптимальна при . Только m не оптимально никогда.
в) Найдите СБР в смешанных стратегиях.
{R,H,K,C,(0.5u+0m+0.5d),}. Выигрыши в этом равновесии равны (3,3).
Можно стратегию 0.5u+0m+0.5d заменить на любую другую, которая не даст игроку 2 получить выигрыш, больше 2.
Задача 5. Хозяин и гость стоят перед тремя закрытыми дверьми гаражей: L, M, R.
Динамический сценарий игры:
а) Опишите формально эту динамическую игру с неполной информацией.
Введем множество позиций, соответствующим четырем ходам игры: Природа – Гость – Хозяин – Гость. У нас получится дерево длины 4.
Позиции мы будем обозначать набором букв a,ab,abc,abcd. Каждая буква принимает значение из множества {L,M,R}.
По правилам игры должно быть выполнено условие и .
Отображение , которое указывает предшественника позиции стирает крайнюю правую букву (если их больше двух). Итак, дерево игры задано.
Выигрыши в финальных вершинах abcd определяются равенством букв a и d: при равенстве выиграл Гость, иначе нулевая ничья.
Осталось задать информационные множества Гостя. После хода Природы есть информационное множество для однобуквенных позиций. Для трехбуквенных позиций (второй ход гостя) есть 6 информационных множеств:
при . Каждое такое множество состоит из трех элементов abc. На каждом таком информационном множестве у Гостя есть по два хода .
У Хозяина есть 9 одноточечных информационных множеств после хода Природы и Гостя, и два хода в каждой такой позиции.
б) Сколько стратегий у Хозяина? Есть ли у него доминируемые стратегии? Какие?
Формально у Хозяина стратегий. Конечно, открывать дверь с машиной, если на нее не показал Гость, это доминируемая стратегия.
в) Найдите СБР в этой игре.
Находясь перед последним ходом во множестве Гость может выбрать дверь . Пусть он выбрал , а на первом шаге выбрал дверь равновероятно. Пусть Хозяин на своем ходе равновероятно выбирает козу, если Гость указал на машину и оставшуюся козу, если Гость указал на козу. Покажем, что мы получили СБР.
В этом СБР все траектории могут реализоваться с положительной вероятностью, все допустимые, кроме траекторий, когда Хозяин сам использует доминируемые стратегии. Это значит, что все информационные множества лежат на равновесном пути. Представления на них определяются по правилу Байеса автоматически и условия согласования выполнены.
Пусть машина стоит, например, за дверью L, а Гость показал на М. Тогда Хозяин вынужден открыть дверь R. Смена двери на М приносит Гостю победу. Если машина стоит за дверью M, то Хозяин может открывать либо L, либо R, сохраняя 50% шансов на победу Гостя. Ожидаемый выигрыш Гостя положителен в СБР.
г) Кому эта игра выгоднее: Хозяину или Гостю. Обоснуйте свой вывод.
Игра выгоднее Гостю, поскольку ожидаемый выигрыш Гостя положителен в СБР и равен 1 с вероятностью 2/3, если первый раз Гость указал на козу. Если Гость первый раз указал на машину, то в СБР вероятность выигрыша 1 равна ½. Итак, ожидаемый выигрыш Гостя равен .
Многие знали про этот парадокс, в частности, из фильма «21», но найти СБР это не особенно помогло.