Теория игр и экономическое моделирование 2010 год Время выполнения- 2 часа 50 минут.
Работа добавлена на сайт samzan.net:
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.
Динамический сценарий игры:
- Природа размещает за одной дверью автомобиль, а за двумя другими по козе, причем вероятности того, что автомобиль окажется за любой дверью, одинаковы.
- Хозяин знает, за какой дверью автомобиль, а гость нет.
- Гость показывает на любую дверь.
- Хозяин обязан открыть одну из двух других дверей, и показать Гостю, что за ней.
- Наконец, гость выбирает любую из трех дверей и получает то, что за ней.
- Выигрыш Гостя равен , а выигрыш Хозяина равен , если Гость нашел автомобиль, и они оба получают выигрыш, равный 0, если за выбранной Гостем дверью оказалась коза.
а) Опишите формально эту динамическую игру с неполной информацией.
Введем множество позиций, соответствующим четырем ходам игры: Природа – Гость – Хозяин – Гость. У нас получится дерево длины 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», но найти СБР это не особенно помогло.
2. утопических претензий на рациональное преобразование общества восходящих к СенСимону и Конту; в России а
3. Крупнейшие фирмы-разработчики операционных систем и программных средств
4. Дипломная работа- Особливості подружніх конфліктів
5. 032003 г Приказ Минздрава РФ 127 от 28
6. от антигенов; 2 от кровопотери; 3 от внутрисосудистого свертывания
7. Насильство як засіб домінування й панування
8. I. участия в массовом катании на ледовой арене Желающим принять участие в массовом катании на льду необхо
9. Тема - Інвестиційна діяльність комерційних банків Методичні вказівки до- Ситуації 1- 1 Чиста теперіш
10. Рельеф и полезные ископаемые Африки
11. 254151 198329 93827 Прибыль до налогообложения тыс.html
12. Долгосрочный план экономического развития региона Российской Федерации на примере Республики Ингушетия
13. 14 Инфекции Эпидемиологический процесс распространение инфекционных заболеваний среди людей
14. на тему Новогодняя открытка Дата 13
15. Театрализация в детском саду
16. Cree 2 имеет силу свечения 70 люмен
17. Основной задачей обеспечения безопасности информационных компьютерных систем является задача ограничения
18. С~леметсіз бе саламатсыз ба Амансыз ба есенсіз бе ~айырлы та~ ~айырлы к~н ~айырлы кеш деп а
19. To py your wy through college to keep in touch with smb to communicte with somebody especilly by writing to them or telephoning them to keep-sty on top of things in control of wht is
20. Степень формализации находится в прямой зависимости от размеров предприятия- чем крупнее фирма тем в больш