[ «Содержание 1 Introduction 2 1.1 Quotes............................................... 2 1.2 About..................................... ...»
- состояние 2, если был сыгран исход () ;
- состояние 1, если был сыгран исход () ;
- состояние 1, если был сыгран исход () ;
- состояние 2, если был сыгран исход () ;
В состоянии 2 сделать ход.
Из состояния 2 перейти в:
- состояние 1, если был сыгран исход () ;
- состояние 2, если был сыгран исход () ;
- состояние 2, если был сыгран исход () ;
- состояние 1, если был сыгран исход () ;
Алгоритм первого игрока можно коротко записать табличкой:
Алгоритм второго игрока имеет вид:
при () при () при () при () Второй игрок также как и первый, начинает 1-ую партию в состоянии 1. а) Какие исходы будут сыграны в игре ?
б) В каком состоянии оказались бы игроки, если бы в первой партии был сыгран исход () ?
Комментарий: сами игроки, конечно, такой исход бы в 1-ой партии не сыграли.
в) В каком состоянии оказались бы игроки, если бы в первых двух партиях были сыграны исходы {(), ()} ?
г) Какие исходы будут сыграны в подыгре с предысторией {(), (), ()} ? д) Какие исходы будут сыграны в подыгре с предысторией {(), (), (), ()} ?
Задача 6.18.
Запишите в алгоритмическом виде (с помощью таблички) следующие стратегии: а) Стратегию «Всегда делать ход ».
б) Наивную стратегию переключения;
в) Стратегию переключения;
Задача 6.19.
Поиск NE, SPNE в бесконечноповторяемой игре:
Стратегия:
В первой партии с (можно менять) В -ой партии:
Если в предыстории только (, ), то сыграть Если в предыстории только (, ) или (, ) то сыграть в четной партии и в нечетной партии Иначе сыгрыть Стратегия антипереключения:
В первой партии сыграть Если в предыстории только (, ), то сыграть Иначе сыграть Задача 6.20.
Рассмотрим антагонистическую игру :
Если происходит исход (, ), (, ) или (, ), то игра сразу заканчивается.
Если оба игрока выбирают, то игра начинается заноново. Но платежи дисконтируются с коэффициентом = 0.5. Если исход (, ) выбирается еще раз, то игра опять начинается заново, и платежи дисконтируются повторно. И т.д. Если оба игрока выбирают бесконечное количество раз, то каждый получает полезность 0.
Найдите равновесие по Нэшу в смешанных стратегиях.
Hint: предположите, что у игры существует цена...
Задача 6.21.
Двукратное повторение. Рассмотрим одновременную игру 0 с таблицей выигрышей Представим теперь, что эта игра повторяется дважды. Все, что происходило в первом периоде, становится общим знанием во втором. Выигрыши первого и второго периодов суммируются (без дисконтирования). Обозначим эту двухпериодную игру.
1. Как устроено дерево этой игры? Как задаются стратегии участников?
2. Сколько имеется чистых совершенных по подыграм равновесий в ? Указание: нужно перебрать всевозможные варианты равновесий в подыграх второго периода, для каждого из них прибавить выигрыши к выигрышам первого периода и исследовать полученную однопериодную игру (будем обозначать ее ).
3. Обратимся к смешанному расширению игры (в поведенческих стратегиях). Пусть равновесные исходы подыгр второго периода зафиксированы и, таким образом, игра сведена к некоторой однопериодной игре. Может ли профиль чистых стратегий, неравновесный в исходной игре 0, участвовать на первом шаге в совершенном равновесии игры ? Может ли в одной и той же игре быть более одного равновесия, обладающего таким свойством?
4. Более сложный вопрос: сколько всего чистых и смешанных совершенных равновесий в игре ?
Указание: достаточно выяснить, какие из игр имеют более одного равновесия. В этом может помочь пункт 3.
Источник: БЗИ.
Задача 6.22.
Суперравновесия.
1. Пусть каждый участник применяет стратегию наказания Nash reversion (“один раз отклонишься — впредь буду всегда играть равновесие Нэша”). Какие профили коррелированных выигрышей можно реализовать таким образом как равновесия в бесконечно повторяющейся игре?
2. Изобразите на плоскости множество коррелированных выигрышей, достижимых в суперравновесиях в силу Народной теоремы.
3. Рассмотрим такую попытку реализовать выигрыши (2, 3): в начальный момент играется (, ), а далее игрок 1 играет, если на предыдущем ходу игрок 2 сыграл и, если ; игрок действует симметричным образом:, если и, если. Является ли эта пара стратегий равновесием Нэша в бесконечно повторяющейся игре (при, достаточно близком к 1)? Если да, то является ли равновесие совершенным по подыграм?
Источник: БЗИ.
Задача 6.23.
Затянувшийся семейный спор. Рассмотрим стандартный семейный спор, когда ФФ=(3,2); ФТ=(1,1);
ТФ=(0,0); ТТ=(2,3). Возможно ли, что при его многократном (но конечном) повторении совершенное на подыграх равновесие будет таким, что:
в первом периоде будет сделан ход ФТ;
в первом периоде будет сделан ход ТФ?
Опишите пример, или докажите обратное.
Источник: НМУ, экзамен 2004, Леша Савватеев.
7 Статические игры Парето-оптимальный исход - это платеж, обладающий каким-либо свойством.
Из работы на пересдаче теории игр Задача 7.1.
Конструктор Придумайте биматричную игру размером (4 4), в которой с помощью вычеркивания строго доминируемых стратегий можно оставить ровно один исход, причем существует единственная последовательность вычеркиваний.
Задача 7.2.
Конструктор Придумайте биматричную игру размером (3 3), в которой с помощью вычеркивания нестрого доминируемых стратегий можно оставить ровно один исход, причем результат зависит от порядка вычеркивания.
Задача 7.3.
Студенты и волшебная шкатулочка Вася и Петя нашли волшебную шкатулочку. Если в нее положить деньги и сказать «Ахалай Махалай», то сумма, лежащая в шкатулке увеличивается в полтора раза. Один недостаток: работает только раз! Петя и Вася решили поступить так: каждый положит в шкатулку сколько хочет, потом они скажут «Ахалай Махалай» и поделят всю сумму поровну.
а) Представьте эту игру в нормальной форме. Можно ли ее представить в матричной форме? Почему?
б) Найдите равновесия по Нэшу. Является ли оно равновесием в строго доминирующих стратегиях?
Задача 7.4.
Фанаты и просто любители футбола На футбольный матч пришли фанаты вместе с главарем и просто любители футбола. Главарю абсолютно все равно, как смотреть футбол: стоя или сидя. Остальные фанаты получают более высокую полезность когда повторяют действия главаря. Любой просто любитель футбола хочет смотреть футбол сидя, но если человек перед ним встанет и закроет обзор, то просто любителю тоже лучше встать, чтобы лучше видеть. Фанаты с главарем заняли весь первый ряд, на остальных рядах сидят просто любители.
Найдите равновесия по Нэшу.
Задача 7.5.
Детские игры[13] Пусть задана детская игра (детерминистическая игра двух игроков с полной и совершенной информацией, в которой игроки ходят по очереди, а ничья исключена; например, Ним, правила которого изложены в задаче 1.2.). Запишем эту игру в матричной форме. Выигрыш первого игрока равен единице, если он выигрывает и минус единице, если проигрывает. Будем проводить вычеркивание стратегий по раундам. Один раунд означает вычеркивание нестрого доминируемых стратегий сначала за первого, затем за второго игрока.
а) Докажите, что, либо у первого, либо у второго игрока есть выигрышная стратегия, т.е. стратегия, гарантирующая выигрыш вне зависимости от действий другого игрока;
б) Сколько раундов вычеркивания потребуется, чтобы матрица платежей оказалась заполнена равными числами? (либо только единицами, либо только минус единицами - в зависимости от того, у кого есть выигрышная стратегия);
в) Пусть в детской игре допускается ничья. Докажите, что после двух раундов вычеркиваний матрица платежей будет заполнена равными числами (на этот раз вся матрица может быть заполнена единицами, минус единицами или нулями).
Тигр: Дилемма заключенного - это недетская игра!
г) А если в детской игре возможных исходов, то сколько раундов потребуется?
Задача 7.6.
Студенты и экзамен [О] Петя и Вася прогуляли экзамен... Они знали, что профессор очень любит путешествия, и придумали для него историю про то, как они отправились в автомобильное путешествие по России и очень хотели вернуться в день экзамена, но по дороге обратно у них сломалось колесо... Профессор согласился дать им отдельный экзамен. Он посадил их по разным аудиториям и задал один и тот же вопрос:
«Какое колесо сломалось?»
а) Представьте эту игру в нормальной форме;
б) Сколько равновесий по Нэшу существует в данной игре?
Тигр: Это по правде было?
Задача 7.7.
Дуополия Бертрана Две фирмы назначают цены на свою продукцию. Предельные издержки обеих фирм равны нулю.
Рыночный спрос описывается функцией = max {, 0}, где > 0 и > 0. Весь спрос достается фирме, назначившей наименьшую цену; если фирмы назначили одинаковую цену, то спрос делится между ними поровну.
а) Изобразите на плоскости стратегии равновесные по Нэшу и Парето оптимальные точки;
Задача 7.8.
Дуополия Бертрана с компенсацией! [О] Грандиозное предложение! Фирмы снова одновременно назначают цены, но каждая фирма обязуется вернуть покупателю разницу в цене товара, если конкурент продает дешевле. Покупатель прекрасно осведомлен о ценах.
а) Как изменятся множества равновесных по Нэшу стратегий и Парето оптимальных точек?
Задача 7.9.
Петя задумывает одно из чисел от 1 до 5. Вася пробует угадать. Если Вася угадал, то Петя выплачивает ему соответствующее количество золотых монет (например, за угаданное число 5 платится золотых монет) Найдите равновесие по Нэшу.
Задача 7.10.
Кто где...[Т] Два игрока, Иван Далекий и Василий Близкий, называют одновременно любое число из отрезка [0; 1]. Выигрыш Ивана Далекого (проигрыш Василия Близкого) - это расстояние между числами.
а) Существуют ли равновесия по Нэшу в чистых стратегиях?
б) Найдите все равновесия по Нэшу в смешанных стратегиях.
Задача 7.11.
Делим пирог Мама спрашивает двух братьев, какую часть пирога каждый хотел бы получить. Братья получают то, что попросили, если пирога хватает. Если братья вместе запросили больше, чем целый пирог, то они не получают ничего.
а) Представьте игру в нормальной форме;
б) Найдите все равновесия по Нэшу в чистых стратегиях.
Задача 7.12.
Около среднего [Cramton] Три игрока одновременно называют любое число из отрезка [0; 1]. Выигрыш в сто рублей получает тот, чье число окажется ближе всего к среднему. Если несколько игроков оказались одинаково близки к среднему, то они делят выигрыш поровну.
а) Представьте игру в нормальной форме;
б) Найдите все равновесия по Нэшу в чистых стратегиях;
в) Найдите все равновесия в смешанных стратегиях, если игроки могут называть только концы отрезка (числа 0 и 1);
г) Найдите все равновесия по Нэшу в чистых стратегиях, если выигрывает тот, кто назовет число, наиболее удаленное от среднего.
Задача 7.13.
Камень-Ножницы-Бумага а) Представьте игру «Камень-Ножницы-Бумага» в нормальной форме; Тигр: Те, кто не знают правила, автоматом получают «незачет». Я попрошу в деканате.
б) Найдите наилучший ответ первого игрока на стратегии второго = (0, 0, 1), = 1, 1, 2, в) Найдите все равновесия по Нэшу в смешанных стратегиях.
Задача 7.14.
Три игрока Три игрока одновременно называют одно из чисел: ноль или один. Если все трое называют единицу, то их выигрыш равен 10, если все трое называют ноль, то их выигрыш равен 5.
а) Найдите все равновесия по Нэшу в чистых стратегиях;
б) Найдите все равновесия по Нэшу в смешанных стратегиях.
Задача 7.15.
Где равновесие [Polishi] а) Придумайте игру (2 2) двух игроков, в которой ни у одного из игроков нет доминируемой стратегии (даже нестрого), причем равновесие по Нэшу единственно.
б) Докажите, что в такой игре равновесие всегда будет в смешанных стратегиях.
Задача 7.16.
Continuous Colonel Blotto Two generals have the same amount of units (continuous) to compete over three battlefields in a campaign.
In each battlefield, the general who assigns more units wins. The general winning 2 battlefields wins the entire campaign. They simultaneously announce their decision of unit distribution over the three battlefields. So, if you are one of the generals, and know absolutely nothing about your opponent, how will you distribute your units over the three battlefields?
Hint: is it true that in any mixed NE the amount of units sent to each battlefield should be uniform?
Hint2: is it possible that 1 + 2 + 3 = 1 and - uniform?
Ответ: да.
Решение: RAND, colonel Blotto hard one Задача 7.17.
Limbo.
До весны 2007 года в Швеции существовала необычная лотерея «Limbo». Правила выглядят следующим образом. Вы можете выбрать любое натуральное число. Победителем объявляется тот, кто назвал самое маленькое число, никем более не названное. Например, если игроки назвали числа 1, 3, 1, 2, 4, то победителем будет тот, кто назвал число 2. Если наименьшего никем более не названного нет, то приз остается у организаторов.
а) Опишите все равновесия по Нэшу в чистых стратегиях для игроков б) Найдите симметрическое равновесие для трех игроков (т.е. равновесие, в котором все игроки используют одинаковые стратегии) в) Почему была закрыта эта лотерея?
Подсказка для «б»: какие есть известные законы распределения на N?
Задача 7.18.
Три игрока одновременно выбирают одно число из множества {1, 2, 3}. Если все три игрока выбрали одно и то же число, то выигрыш каждого равен нулю. В ином случае игрок выбравший наименьшее непарное число получает 2 рубля, а остальные двое - платят по одному рублю. Например, если игроки назвали числа 1, 3 и 1, то победителем будет игрок назвавший двойку.
а) Найдите все равновесия по Нэшу в чистых стратегиях б) Найдите симметричное равновесие по Нэшу в смешанных стратегиях Задача 7.19.
Имеется антагонистическая игра 2 (2 стратегии у первого игрока и - у второго), где 2.
Всегда ли можно вычеркнуть стратегии так, чтобы игра превратилась в игру 2 2, а цена игры при этом не изменилась?
Задача 7.20.
О, донна Анна!
Братья Антонио и Джованни познакомились с тремя доннами: блондинкой Анной и брюнетками Изабеллой и Марией. Каждый из братьев истинный джентльмен, и будет ухаживать только за одной особой. Если оба выберут одну и ту же особу, то их судьбу решит дуэль на шпагах.
Параметр (0; +) отражает предпочтения Антонио и Джованни.
а) Найдите равновесия по Нэшу в чистых стратегиях в зависимости от ;
б) [T] Найдите все равновесия по Нэшу в зависимости от ;
в) [T] Как зависят от вероятности исходов?
Задача 7.21.
Петя выбирает место где спрятаться внутри круга единичного радиуса. Одновременно Вася выбирает место, где будет искать Петю. Вася замечает Петю, если расстояние между ними не превосходит половины радиуса. Если Вася нашел Петю, то Петя платит Васе рубль. Если Вася не нашел Петю, то Вася - Пете.
а) Найдите равновесие по Нэшу и цену игры.
б) Решите задачу, если игроки прячутся на отрезке длины Источник: Lones Smith.
Задача 7.22.
Экология Три фирмы, использующие воду из одного озера, одновременно решают, очищать ли им сточные воды, сбрасываемые в то же озеро. Очистка воды означает издержки равные единице. Если воду не очищают две или три фирмы, то каждая из трех фирм несет дополнительные издержки в размере трех единиц. Найдите все равновесия по Нэшу в смешанных стратегиях.
Источник: Gintis.
Задача 7.23.
Рассмотрим статическую игру двух игроков с конечным множеством стратегий. Стратегия игрока называется полностью смешанной (completely mixed), если каждая чистая стратегия играется со строго положительной вероятностью. Известно, что чистая стратегия первого игрока является наилучшим ответом на некоторую полностью смешанную стратегию второго игрока. Может ли стратегия нестрого доминироваться другой стратегией первого игрока?
Источник: LSE exam, 2002.
Задача 7.24.
Что предложил Warren Buffet?
Парламент поделен на две партии: республиканцы и демократы. Для принятия реформы необходима ее поддержка обеими партиями. Реформа безразлична обеим партиям. Warren Buffet предложил, чтобы какой-нибудь миллиардер выступил со следующим обещанием: Если реформа не будет принята, то партия, поддержавшая реформу во время голосования получит 1000000000$ (Один миллиард долларов). Партии голосуют одновременно (можно проголосовать только за или против реформы).
Каждая партия хотела бы получить деньги и не хотела бы, чтобы деньги достались конкурентам.
Партии верят заявлению миллиардера.
а) Представьте игру в нормальной форме.
б) Найдите равновесие по Нэшу;
Тигр: сам Buffet с подобным заявлением не выступил!
Источник: Game theory at work.
Задача 7.25.
Можно ли придумать такую матрицу игры, чтобы в ней можно было вычеркнуть одну стратегию так, чтобы все старые равновесия по Нэшу остались, и еще одно равновесие по Нэшу появилось?
Задача 7.26.
Курно и вычеркивание стратегий Получите результат дуополии Курно вычеркиванием нестрого доминируемых стратегий.
Верно ли, что равновесие по Нэшу в модели Курно с тремя олигополистами также получается путем последовательного вычеркивания нестрого доминируемых стратегий?
Задача 7.27.
Вычеркивание стратегий и строгое доминирование Пусть в матричной игре () (), стратегия () одного игрока строго доминирует стратегию ().
Из матрицы вычеркнули стратегию (), причем неизвестно, чья это стратегия: того же игрока, или другого. Верно ли, что в сокращенной матрице () ()?
Задача 7.28.
Президент Два гражданина борются за пост президента страны. Каждый из них выбирает свою политическую позицию. Под позицией мы будем понимать натуральное число от 1 до 99, где число один означает крайне левую позицию, а 99 - крайне правую. Если оба гражданина занимают одну политическую позицию, то голоса делятся поровну. Если позиции различны, то каждый житель (в стране 99 жителей) выбирает того кандидата, к которому он ближе расположен. Если жителю все равно, то его голос делится поровну между кандидатами.
Найдите все исходы, которые остаются в результате последовательного вычеркивания нестрого доминируемых стратегий.
Задача 7.29.
Президент в непрерывном случае Два гражданина борются за пост президента страны. Каждый из них выбирает свою политическую позицию. Под позицией мы будем понимать число из отрезка [0; 1], где число ноль означает крайне левую позицию, а один - крайне правую. Если оба гражданина занимают одну политическую позицию, то голоса делятся поровну. Если позиции различны, то каждый житель (в стране континуум жителей) выбирает того кандидата, к которому он ближе расположен. Другими словами, доля голосов, поданных за кандидата, это длина отрезка жителей расположенных ближе к нему, чем к его конкуренту.
а) Найдите равновесие по Нэшу в чистых стратегиях.
б) Найдите равновесие по Нэшу в смешанных стратегиях Задача 7.30.
«Реже, но лучше»
Теннисист, делающий подачу, может бросить мяч либо под правую руку (forehand) соперника, либо под левую руку (backhand) соперника. Если принимающий подачу заранее угадывает место падения мяча, то у него больше шансов отразить мяч. С другой стороны, мяч под правую руку отражается легче, чем мяч под левую руку (это может быть связано как непосредственно с легкостью приема мяча справа, так и с трудностью подачи под правую руку). Вероятности отразить мяч занесены в таблицу:
Т.е. если подача идет под правую руку, а принимающий подачу игрок ожидает подачи под левую, то вероятность отражения мяча равна 0,3. а) Найдите равновесия по Нэшу при = 0, б) Найдите равновесия по Нэшу при произвольном в) Как зависит от вероятность того, что подача будет осуществляться под правую руку? Прокомментируйте.
г) Как зависит от вероятность того, что подача будет отражена?
Источник: Gintis, 4.18.
Задача 7.31.
«Своя игра»
В финал «Своей игры» вышло 3 участника. У них на руках соответственно > > > 0 очков.
Для нормировки предположим, что = 1. Сейчас игроки независимо и одновременно определяют размер своей ставки (размер ставки не может превосходить имеющегося количества очков). После того, как игроки выберут свои ставки им будет предложен один вопрос. Предположим, что каждый игрок независимо от других ответит на этот вопрос с вероятностью. Игрок правильно ответивший на вопрос получает обратно свою ставку в удвоенном размере. Игрок набравший больше всех очков получает Очень Большой Приз, остальные игроки получают столько денег, сколько очков они набрали. Предположим, что в игре нет однозначного лидера (т.е. < 2).
Исследуйте эту игру а) Почему важно сравнение 3 ?
б) Верно ли, что ожидаемый выигрыш игрока положительно зависит от его очков?
в) Найдите оптимальные стратегии г) Решите задачу для двух игроков Source: Lones Smith Задача 7.32.
Эквивалентность стратегий С точки зрения первого игрока стратегии и полностью эвкивалентны, т.е. вне зависимости от действий другого игрока они приносят одинаковый выигрыш. С точки зрения второго игрока стратегии и полностью эквивалентны.
Возможно ли, что исход (, ) лучше исхода (, ) для обоих игроков?
Задача 7.33.
Бар в Бобруйске В Бобруйске можно смотреть на звезды... А еще в Бобруйске есть очень маленький бар «Для двоих».
Там хорошо быть одному или вдвоем. Тигр: полное официальное название бара ООО «Для не больше чем двоих». Три жителя Бобруйска одновременно решают, как им провести вечер. Примем звезды за точку отсчета. Чтобы добраться до бара, надо воспользоваться трамваем, билет стоит две единицы.
Полезность от бара равна шести, если там не больше двух человек и единице, если там больше двух человек.
а) Найдите все равновесия по Нэшу в чистых стратегиях;
б) Найдите все равновесия по Нэшу в смешанных стратегиях;
в) Найдите средний выигрыш игроков в равновесии в смешанных стратегиях и объясните, почему бар в Бобруйске не нужен.
г) Верно ли, что назначив определенную плату за вход в бар, можно добиться увеличения общественного благосостояния трех жителей Бобруйска?
Источник: Gintis, 4.15.
Задача 7.34.
Два тигра Два тигра заметили двух антилоп. Маленькую, весом в один условный килограмм, и большую, весом в > 1 условных килограммов. Они одновременно принимают решение, за какой антилопой погнаться. Тигры всегда догоняют антилоп. Тигр: Если хотят, то конечно. Если тигры выберут одну антилопу, то они поделят ее поровну.
а) Запишите игру в матричной форме;
б) Найдите все равновесия по Нэшу в чистых и смешанных стратегиях в зависимости от Тигр: Очень важная задача!
Задача 7.35.
Воробьи и Толстый кот Толстый кот спрятался за деревом и изготовился к прыжку... Стайка из воробушков клюет хлебные крошки. Каждый из воробушков иногда отрывается от завтрака и оглядывается. Если хотя бы один заметит выпрыгивающего кота, то вся стайка успеет улететь. Если кот успеет выпрыгнуть незамеченным, то он схватит первого попавшегося воробья, а остальные улетят. Верно ли, что каждому воробью выгодно добровольно отвлекаться от еды и иногда оглядывать окрестности?
Более формально... Для упрощения рассмотрим эту игру как статическую. Удовольствие кота от пойманного воробья равно > 0, неудовольствие от потраченного впустую прыжка равно > 0.
Выберем единицы измерения так, чтобы + = 1. У кота две стратегии: выпрыгивать или не выпрыгивать. Ценность собственной жизни для воробья равна единице. У каждого воробья две стратегии:
наблюдать или кушать. Издержки наблюдения равны > 0. Смешанная стратегия означает, что время на еду и наблюдение распределяется пропорционально вероятностям. а) При каких условиях на исходные параметры существует симметричное равновесие по Нэшу в смешанных стратегиях (каждый воробей наблюдает с вероятностью, а Толстый кот выпрыгивает с вероятностью )?
б) Найдите это равновесие и определите как и зависят от параметров задачи. Прокомментируйте;
в) Что изменится, если шансы быстро улететь при обнаружении выпрыгивающего Толстого кота будут равны ?
г) У воробьев новая опасность. На этот раз за деревом притаился Хулиган Вася. Отличие Хулигана Васи от Толстого кота состоит в том, что у Васи заготовлена сеть, и в случае удачи он поймает сразу всю стайку. Ответьте на вопросы «а», «б» и «в».
Задача 7.36.
Две вороны Двум воронам где-то бог послал по кусочку сыра. Вороны взгромоздились на соседние ветки ели и одновременно выбирают: либо позавтракать своим кусочком, либо провести стремительное нападение на соседку и, похитив ее кусочек сыра, позавтракать в другом месте...
а) Найдите все равновесия по Нэшу в этой игре;
б) Как зависит от параметра вероятности блицкрига и завтрака в смешанном равновесии?
Задача 7.37.
Человеку плохо. Рядом на остановке стоит человек. Каждый из них может либо вызвать скорую с помощью мобильного, либо дождаться троллейбуса и уехать. Если никто не вызовет скорую, то человек умрет. Если человек умирает, то полезность каждого равна 0, если человек остается в живых, то полезность каждого равна 1. Издержки телефонного звонка равны (0; 1).
а) Найдите все равновесия по Нэшу в чистых стратегиях;
б) Найдите симметричное равновесие по Нэшу в смешанных стратегиях (все игроки используют одну и ту же стратегию);
в) Как зависит от вероятность оказания помощи отдельным прохожим?
г) Как зависит от вероятность получения помощи?
Задача 7.38.
Поиск Истины Собрались Мудрых тараканов и решили одновременно искать Истину. Каждый может добросовестно искать или отдыхать. Если Мудрый таракан ищет Истину, то он находит ее независимо от других с вероятностью. Если Истина будет найдена хотя бы одним Мудрым тараканом, то он расскажет ее всем, и все получат полезность +1. Поиск Истины связан с издержками (0; ).
а) Будет ли одинокий Мудрый таракан искать истину ( = 1)?
б) Найдите равновесие по Нэшу в чистых стратегиях для произвольного в) Найдите симметричное равновесие по Нэшу в смешанных стратегиях для произвольного д) Как зависит от доля Мудрых тараканов ищущих Истину?
е) Как зависит от вероятность того, что Истина будет найдена?
Задача 7.39.
Предположим, что платежи в биматричной игре выбираются случайным образом. Каждый выигрыш нормально распределен с матожиданием 0 и дисперсией 1. Каково ожидаемое количество равновесий по Нэшу в чистых стратегиях? Дисперсия?
Задача 7.40.
Мост Из пункта в пункт можно попасть двумя путями - через B или через C. Если по дороге AB едет машин, то время в пути каждой из них будет равно () = + 32. Для других отрезков пути функции равны: () = 5 + 1, () = + 32 и () = 5 + 1. Каждое утро из города в город едет 6 машин.
а) Сколько машин и по какой дороге едет в равновесии по Нэшу? Сколько им требуется времени, чтобы добраться из в ?
б) Как изменятся ответы, если между городами и построен удобный мост, такой что = 0?
Задача 7.41.
Два человека пришли в кабак. У одного из них 10 золотых, у второго - 6 золотых. Каждый может тратить деньги на выпивку или на музыку. Музыка является общественным благом - ее слышат все.
Выпивка - частным. Полезности равны 1 = (1 + 2 )1 и 2 = (1 + 2 )2, где и - расходы -го человека на музыку и выпивку. Предположим, что деньги бесконечно делимы.
а) Найдите равновесие по Нэшу б) Что изменится в случае, если у второго 2 золотых?
в) Являются ли эти равновесия оптимальными по Парето?
Задача 7.42.
Поиск функции плотности Два спортсмена готовятся к соревнованиям. Каждый из них выбирает свой уровень усилий [0; 1]. Побеждает тот, кто приложил больше усилий при подготовке. Если оба приложили одинаковое количество усилий, то не побеждает никто. Победитель получает платеж равный 1. Издержки по приложению усилий равны = 22 для каждого игрока.
а) Существует ли равновесие по Нэшу в чистых стратегиях?
б) Найдите равновесие по Нэшу, в котором уровень усилий каждого игрока имеет функцию плотности (), отличную от нуля на [; ].
Задача 7.43.
В осях (, ) изобразите все точки, для которых стратегия первого игрока + (1 ) является равновесной в чистых или смешанных стратегиях.
Задача 7.44.
Имеется антагонистическая игра с матрицей.
Найдите все равновесия по Нэшу в чистых и смешанных стратегиях и цену игры, если:
b), = () · (), где и положительные функции с), = () + (), где и - произвольные функции d), = Задача 7.45.
Пачка типовых биматричных игр Автор: Эх, кто из нынешних бакалавров знает разницу между корешком и пачкой?
Тигр: Корешок - это сто купюр, обернутых ленточкой, пачка - десять корешков, упакованных в если не будут брать? А если не будут брать - отключим газ!
В каждой игре найдите:
Равновесия по Нэшу в чистых стратегиях;
Множество возможных платежей, если игроки используют смешанные стратегии;
Парето-оптимальные исходы в чистых стратегиях;
Все равновесия по Нэшу в смешанных стратегиях;
Парето-оптимальные точки в смешанных стратегиях [T];
Строго и нестрого доминируемые стратегии;
Тигр: Найдите и перепрячьте!
а) 1. 1 (3; 2) (2; 0) ; 2. 1 (1; 0) (2; 1) ; 3. 1 (1; 4) (2; 5) ; 4. 1 (2; 6) (2; 0) б) 1. 1 (1; 6) (2; 7) ; 2. 1 (2; 1) (2; 0) ; 3. 1 (2; 2) (2; 3) ; 4. 1 (2; 6) (2; 0) в) 1. 1 (2; 6) (2; 6) ; 2. 1 (1; 1) (1; 1) ; 3. 1 (2; 0) (0; 0) ; 4. 1 (1; 3) (3; 3) г) 1. 1 (1; 3) (0; 1) ; 2. 1 (1; 3) (3; 0) ; 3. 1 (3; 3) (3; 0) ; 4. 1 (1; 0) (2; 3) д) 1. 1 (3; 1) (1; 3) ; 2. 1 (1; 1) (0; 0) ; 3. 1 (1; 3) (2; 3) ; 4. 1 (1; 1) (3; 0) е) 1. 1 (1; 3) (3; 3) ; 2. 1 (2; 3) (1; 3) ; 3. 1 (1; 1) (1; 1) ; 4. 1 (0; 3) (1; 3) Задача 7.46.
В городке две школы, которые никак не отличаются по качеству образования. Отличие между ними состоит в том, что одна - бесплатная, а вторая - платная, оплата равна > 0. По уровню интеллекта школьники городка равномерно распределены на отрезке [0; 1].
Если школьник с интеллектом выбирает бесплатную школу, то его полезность равна = (1 + )(1 + ), где - средний интеллект школьников, выбравших бесплатную школу.
Если же школьник с интеллектом выбирает платную школу, то его полезность равна = (1 + )(1 + ), где - средний интеллект школьников, выбравших платную школу.
а) Рассмотрим Машеньку и Вовочку, с уровнями интеллекта >. Возможно ли, что в равновесии по Нэшу Машенька идет в бесплатную школу, а Вовочка - в платную?
б) Найдите все равновесия по Нэшу в зависимости от.
Задача 7.47.
Придумайте игру (2 2) двух игроков, в которой вычеркивание нестрого доминируемых стратегий приводит к потере одного из двух равновесий по Нэшу.
Задача 7.48.
Несколько простых вопросов:
а) Может ли игра в развернутой форме быть антагонистической?
б) Сколько смешанных стратегий у первого игрока, если у первого игрока две чистых стратегии, а у второго - три чистых стратегии?
в) Может ли быть исключенной Парето-оптимальная точка при вычеркивании строго доминируемых стратегий?
г) Может ли в игре двух игроков с бесконечным количеством стратегий не быть Парето-оптимальных точек?
Задача 7.49.
Задана антагонистическая игра а) Найдите равновесия по Нэшу в чистых стратегиях;
б) Найдите равновесия по Нэшу в смешанных стратегиях;
в) Найдите Парето-оптимальные точки в чистых стратегиях;
г) Найдите Парето-оптимальные точки в смешанных стратегиях;
Тигр: Кто-то за эту задачу незачет получил...
Задача 7.50.
Парадокс председателя приемной комиссии В приемной комиссии три человека, включая председателя. Обсуждается, что поставить по теории игр тунеядцу Сидорову. Члены комиссии одновременно предлагают оценку. Ставится оценка, получившая наибольшее число голосов. Если ни одна из оценок не получила большинства голосов, то председатель ставит оценку по своему желанию.
Предпочтения членов комиссии выглядят следующим образом: Председатель: 2 3 4. Двоечник он, и точка! Тигр: Зараза!
Второй член комиссии: 4 2 3. Да он знает на четверку! Если что, пересдаст на четыре!
Третий член комиссии: 3 4 2. Нормальная тройка, ну чуть ближе к четверке.
а) Найдите все равновесия по Нэшу в этой игре; Тигр: Обрадуйтесь!
б) Укажите несколько различных способов вычеркнуть нестрого доминируемые стратегии.
Задача 7.51.
Найдите все равновесия по Нэшу в смешанных стратегиях Задача 7.52.
Доминирование а) Рассчитайте платежи от смешанных стратегий 1 1 + 2 2, 1 1 + 2 2 + б) Укажите все смешанные стратегии, доминирующие чистую стратегию в) Найдите все равновесия по Нэшу в смешанных стратегиях Задача 7.53.
Доминирование а) Пусть = 5. При каких существует смешанная стратегия, строго доминирующая чистую стратегию 1 ?
б) Изобразите на плоскости множество таких пар (, ), при которых существует чистая стратегия, строго доминирующая стратегию 1.
в) Изобразите на плоскости множество таких пар (, ), при которых существует смешанная стратегия, строго доминирующая стратегию 1.
Задача 7.54.
Всеобщность знания В уездном городе живут игроки двух типов: «безумцы» и рациональные. При встрече в городе принято играть в игру, изображенную слева.
s (1;1) (-2;-1) c (-1;-2) (-1;-1) Рациональные игроки играют стратегию, приносящую наибольший платеж, а безумцы - стратегию Как-то случилось Петя попасть в этот город и встретится с одним рациональным аборигеном. Они никогда раньше не виделись и никогда больше не увидятся. Петя знает, что абориген - рационален.
Абориген знает, что Петя - рационален. Петя ошибочно полагает, что абориген считает его безумцем.
Абориген знает о Петиной ошибке.
Найдите все равновесия по Нэшу в этой матрице. Какое из них будет сыграно?
Задача 7.55.
Гипербола На плоскости (, ) нарисуйте точки, при которых существует смешанная стратегия вида = · + (1 ) ·, строго доминирующая стратегию в антагонистической игре:
Задача 7.56.
Оптимальный ответ В игре 1 (2; 8) (1; 4) (9; 20) а) Найдите все смешанные стратегии (смешиваются 2 и 3 ), которые строго доминируют чистую стратегию 1.
б) Какая стратегия является оптимальным ответом второго игрока на стратегию 2 ?
в) Какая стратегия является оптимальным ответом второго игрока на стратегию 3 1 + 2 2 ?
Задача 7.57.
Футбол Четыре команды играют в футбол. Сначала проводится полуфинал (первая команда играет со второй, третья - с четвертой), затем две команды победительницы участвуют в финале. Выигравшая чемпионат команда получает приз равный. Перед началом чемпионата каждая команда выбирает затраты на тренировки (неотрицательное число). Если встречаются команды с затратами и, то вероятность выигрыша первой равна +.
Тигр: А может быть это фирмы дают взятки чиновникам?
а) Найдите симметричное равновесие по Нэшу (т.е. равновесие в котором все команды выбирают одинаковый уровень усилий);
б) Пусть команд будет восемь, а игра проходит по схеме четвертьфинал-полуфинал-финал. Докажите, что симметричного равновесия по Нэшу не существует.
Тигр: А если вторая производная окажется равной нулю?
Автор: Тсс!
в) Докажите, что симметричное равновесие по Нэшу отсутствует, если число туров превышает два.
г) [Т] Докажите, что если число туров превышает два, то в любом равновесии по Нэшу будет команда с нулевым уровнем тренировки.
Тигр: Среди кандидатов в президенты есть те, кто не надеется победить, среди студентов есть те, кто не готовится к экзамену... Все это звенья одной цепи!
Задача 7.58.
Компенсация ущерба Простая модель арбитража: потерпевший называет свою оценку ущерба, адвокаты ответчика одновременно предлагают свою оценку. Затем арбитр выбирает тот вариант, который ему кажется более справедливым, ближе к некоторому идеальному. Арбитр знает, стороны - не знают.
а) Найдите равновесие по Нэшу, если [0; 1] ;
б) Найдите равновесие по Нэшу, если (; 2 ) Источник: Gibbons.
Задача 7.59.
Платон мне друг, но Истина дороже Докажите или опровергните следующие утверждения:
а) При вычеркивании строго доминируемых стратегий результат не зависит от порядка вычеркивания.
б) При вычеркивании нестрого доминируемых стратегий результат не зависит от порядка вычеркивания.
в) Если в результате вычеркивания строго доминируемых стратегий остается ровно один исход, то при вычеркивании стратегий, не являющихся наилучшим ответом, также остается ровно один исход.
г) Если в конечной игре двух игроков чистая стратегия не является наилучшим ответом ни на какую смешанную стратегию, то существует смешанная стратегия доминирующая.
д) Множества стратегий остающиеся в результате вычеркивания строго доминируемых стратегий и в результате вычеркивания стратегий, никогда не являющихся наилучшим ответом, совпадают.
е) Если в результате вычеркивания строго доминируемых стратегий остается ровно один исход, то он является равновесием по Нэшу.
ж) Равновесие по Нэшу рационализуемо з) В конечной игре в смешанных стратегиях существует равновесие по Нэшу.
и) В любой игре существует хотя бы одно равновесие по Нэшу.
к) В любой игре существует хотя бы одна Парето оптимальная точка.
л) Хотя бы одна из Парето оптимальных точек в любой игре является равновесием по Нэшу.
Задача 7.60.
Два игрока одновременно называют числа от 1 до 100. Пусть это числа 1 и 2. Если 1 +, тогда каждый игрок получает рублей. Если 1 + 2 > 100 и <, то игрок получает рублей, а игрок получает (100 ) рублей. Если 1 + 2 > 100 и =, то игроки получают по 50 рублей.
Если коротко, то платежи определяются так: игроки всегда получают в сумме не более 100 рублей, самый нежадный получает то, что просит. а) Найдите все исходы, которые остаются в результате последовательного вычеркивания нестрого доминируемых стратегий.
б) Найдите равновесие по Нэшу Задача 7.61.
Придумайте биматричную игру, в которой у первого игрока две стратегии ( и ) и у второго игрока две стратегии ( и ). Стратегия строго доминирует стратегию, стратегия строго доминирует стратегию. Исход (, ) доминирует по Парето исход (, ).
Задача 7.62.
: Абстрактная “биматричная” игра.
Взяв свое имя как бесконечную последовательность символов типа “иваниваниван...”, задайте выигрыши первого игрока так: 1 (1, 2 ) =“и”, 1 (1, 2 ) =“в”,1 (1, 2 ) =“а”, 1 (1, 2 ) =“н”, 1 (1, 2 ) =“и”, 1 (1, 2 ) =“в”,1 (1, 2 ) =“а”, 1 (1, 2 ) =“н”,1 (1, 2 ) =“и”.
Подставьте вместо каждой буквы имени число = ее номер в алфавите. Аналогично используя свою фамилию, задайте выигрыши второго игрока 2 (.). Найти все известные вам типы некооперативных решений в нормальной форме:,,,,, (для, для простоты решения, превратить игру в антагонистическую, заменив выигрыши второго игрока — выигрышами первого с обратным знаком), а из кооперативных концепций — сильную и слабую Парето-границы, и обычное -ядро (за уровень полезности достижимый индивидуально — взять максимальногарантированный выигрыш).
(Сокращения: – Dominant Equilibrium, – MaxiMin, - Nash Equilibrium, – Stackelberg Equilibrium, – Sophisticated Equilibrium, – Nash Equilibrium in Mixed stratagies.) Источник: БЗИ, НГУ.
Задача 7.63.
(Пионерлагерь=) Сторож колхозного поля и вор. На поле можно забраться 4 путями: A,B,C,D, удаленными от сторожки на расстояния, соответственно, 2, 4, 6, 8 (сот метров). В случае поимки вора, сторож ожидает с него штраф $10, а неприятность каждой сотни метров ходьбы от сторожки для себя оценивает в $1. Хоть один из путей сторож обязан покараулить в любом случае. Найти все смешанные равновесия Нэша: будет ли вор пользоваться в разные дни разными путями, и разные ли пути будет караулить сторож?
Источник: БЗИ, Savvateev.
Задача 7.64.
Задача про лыжников. Двое бегут по лыжной трассе навстречу друг другу. У каждого две стратегии: уступить или не уступить (для определенности предположим, что лыжники руководствуются принципом правостороннего движения). Уступивший дорогу теряет на этом 2 сек., а если столкнулись, то будут распутываться 10 сек.
1. Найдите все (и чистые, и смешанные) равновесия в данной игре, предполагая, что проигрыш участников определяется потерянным временем. Какие из равновесий являются эффективными (оптимальными по Парето в сильном или слабом смысле)?
2. Решить задачу 1 в предположении, что можно еще уступить половину лыжни — мы ведь бегаем классикой! При этом теряется 1 сек. (в дополнение к возможным десяти). Сколько будет равновесий? Что на сей раз можно сказать об их эффективности?
Источник: БЗИ, NES.
Задача 7.65.
Торговцы на станции. На станции Тайга трое местных предпринимателей, Александр, Василий и Семен (,, ), промышляют тем, что продают пассажирам, соответственно, пиво, воблу и соленые орешки. Утром приходят сразу два поезда, поэтому каждый спешит поставить свою торговую точку на первой или второй платформе. Если торговец работает на платформе в одиночку, его выручка (в рублях) от продажи товаров пассажирам соответствующего поезда определяется из таблицы:
Если в одном месте продаются и пиво, и закуска, то этих товаров удается продать на 50% больше из-за эффекта дополняемости. Впрочем, если продавцы закуски находятся на одной платформе, то вследствие конкуренции оба выручают вдвое меньше, чем когда они на разных платформах.
1. Формализуйте взаимодействие торговцев как игру в нормальной форме, предполагая, что до установки торговой точки никто из них не может получить информацию о том, где будут 2. Найдите все чистые и смешанные равновесия Нэша в этой игре.
3. Что изменится, если Александр будет в одиночку зарабатывать на второй платформе не 100, Источник: БЗИ, NES.
Задача 7.66.
“Гладкая” игра. Играют двое. Стратегии игроков задаются вещественными параметрами и (, [1, 1]). Выигрыши равны, соответственно, 2 2 и 3 3. Изобразите кривые реакции обоих участников (если возможно, разными цветами или стилями линий) и найдите все равновесия Нэша в чистых стратегиях для = 3, = 1 и = 2.
Источник: БЗИ, NES.
Задача 7.67.
Продавцы мороженого на пляже. На городском пляже стоят два ларька ( и ), торгующие мороженым. Продавцы независимо устанавливают цены, [0, ); издержками пренебрегаем.
Все выглядит примерно так:
Народ равномерно распределился по пляжу и загорает. В этот день очень жарко, поэтому каждый из отдыхающих готов переплатить за лакомство рубль, только бы не идти лишние 100м по раскаленному песку.
1. Предположим, что каждый, во что бы то ни стало, стремится приобрести себе стаканчик мороженого. Полностью опишите отображения наилучшего ответа, изобразите на плоскости (, ) кривые реакции и найдите все равновесия Нэша. Естественно, все в чистых стратегиях.
2. Выполните задание п. 1 в предположении, что ценность стаканчика мороженого составляет 0, т. е. каждый потребитель был бы готов заплатить за мороженое цену, если бы оно продавалось рядом (как нетрудно видеть, в п. 1 = ). Рассмотрите все возможные случаи. Указание: чтобы избежать лишней возни с несущественными кусками кривых, можете исключить что-нибудь по доминированию.
Источник: БЗИ, NES.
Задача 7.68.
Продавцы мороженого в Игарке.
Два конкурирующих продавца мороженого независимо выбирают места для своих торговых точек.
Покупатели, естественно, идут к ближайшему ларьку (в Игарке 50o C). Если расстояния до ларьков одинаковы (в частности, если ларьки находятся в одной точке), то место покупки мороженого выбирается покупателем случайно и равновероятно.
1. Пусть цена мороженого фиксирована и все хотят его купить. Найти все равновесия в чистых стратегиях.
2. Предположим, что в задаче 1 покупатели из-за риска замерзнуть не ходят дальше 1 км от дома.
Найдите все равновесия.
3. А что будет, если в задаче 1 продавцов не два, а три?
4. Решить задачу 3, предполагая, что три продавца выбирают свое местоположение вдоль Московской кольцевой автомобильной дороги.
Источник: БЗИ, NES.
Задача 7.69.
Дуополия с дифференцированными товарами.
Эти товары частично взаимозаменяемы и спрос на них формируется по закону где 1, 2 0 — цены, а 1, 2 0 — выпуски. Затраты на производство единицы продукции составляют, соответственно, 1 и 2 (1, 2 0).
1. Пусть фирмы независимо устанавливают свои цены, после чего удовлетворяют возникший на рынке спрос. При каких 1 и 2 реализуется равновесие с положительными ценами и выпусками?
Найдите для этого случая равновесные 1, 2, 1, 2.
2. А теперь, наоборот, пусть фирмы выбирают, сколько они будут производить, а цены на рынке формируются в соответствии с законом спроса (1) (если правая часть какой-либо из получающихся формул отрицательна, то считаем соответствующую цену нулевой). Ответьте на те же 3. Сравните равновесия, реализующиеся при ценовой и количественной конкуренции. Отдельно рассмотрите случай 1 = 2.
Источник: БЗИ, NES.
Задача 7.70.
Аукцион печенья. Имеется пакет с печеньем, который нужно поделить между участниками.
Количество печенья в пакете всем известно. Каждый участник тайно от других пишет на листке бумаги свое имя и сколько продукта он хотел бы получить. Все заявки упорядочиваются по возрастанию, после чего ведущий по очереди выдает каждому запрошенное им количество, начиная с самых “скромных”. Если в некоторый момент печенье кончается, то заявившие слишком много, увы, остаются ни с чем (если оставшегося печенья оказывается недостаточно, чтобы обслужить несколько одинаковых заявок, то делим между ними поровну). Если же остались лишние печенья, их съедает ведущий.
1. Найдите все симметричные равновесия в чистых стратегиях. Дискретностью печенья можно пренебречь.
2. Есть ли в этой игре несимметричные чистые равновесия? Если есть, приведите пример, а если нет, то объясните, почему.
Источник: БЗИ, NES.
Задача 7.71.
Паша, Саша и Наташа решают, куда сходить в поход: в Московскую Область (МО), в Тверскую Область (ТО) или в Республику Марий-Эл (МЭ). С точки зрения Паши, в порядке предпочтения идут МО-ТО-МЭ; с точки зрения Саши ТО-МЭ-МО, и наконец, с точки зрения Наташи — МЭ-МОТО. Голосуют одновременно, и решают по большинству. Если у всех разное, решает Паша (он — их командир). Решить игру по доминированию.
Источник: НМУ, экзамен 2004, Леша Савватеев.
Задача 7.72.
Пример симметричной игры.
Двое играют на деньги. Каждый участник в тайне от другого пишет на листке бумаги число от до. После этого листки открывают и сравнивают числа. Если оказалось поровну, то ничья. Если числа отличаются на 1, то тот, у кого больше, выигрывает 2. В остальных случаях тот, у кого меньше, выигрывает 1.
Можно ли, не производя никаких вычислений, определить цену игры в смешанных стратегиях?
Приведите соображения, обосновывающие ваш ответ.
Пусть < 5. Как надо играть в эту игру?
Пользуясь результатами, полученными в предыдущих пунктах, найдите решение игры для произвольного.
Источник: НМУ, экзамен 2004, Леша Савватеев.
Задача 7.73.
В погоне за призом.
Трое участвуют в телеигре за большой приз (бутылка коньяка «Белый Аист»). Правила игры такие:
каждый записывает тайком натуральное число (0,1,...). Побеждает тот, кто назвал наименьшее число, не названное больше никем. Если все три называют одно число, приз получает телеведущий.
Найдите все равновесия Нэша в чистых стратегиях.
А теперь пусть можно называть только 0,1,2. Найдите все симметричные равновесия Нэша в смешанных стратегиях.
Источник: НМУ, экзамен 2004, Леша Савватеев.
Задача 7.74.
Вновь за призом.
Газета объявила, что выставит ящик водки (1000 рублей) одному или по ящику каждому из двух людей, приславших ей «запрос». Стоимость конверта для высылания запроса равна 1. Участвуют 1002 человека, и каждый решает, прислать ли запрос. Если приславших более двух, никто ничего не получает.
Найдите все чистые равновесия Нэша;
Найдите симметричное смешанное равновесие Нэша.
Источник: НМУ, экзамен 2004, Леша Савватеев.
Задача 7.75.
Существует ли последовательная игра двух игроков с полной совершенной информацией, матрица которой имела бы вид Если Ваш ответ «да», то постройте дерево, если «нет», то докажите.
7.1 Игры с нулевой суммой Задача 7.76.
Примеры игр с нулевой суммой. Найти максимин и минимакс в чистых стратегиях, а также все седловые точки (они же равновесия Нэша) и цену игры в смешанных стратегиях:
Источник: БЗИ, NES.
Задача 7.77.
Два пальца. Есть такая замечательная игра. Участники одновременно показывают один или два пальца. Потом считают сумму (она может получиться от двух до четырех). Если четно, то второй игрок выиграл у первого долларов, если же нечетно, то наоборот, выиграл первый.
1. Найдите седловую точку в смешанных стратегиях и цену игры. Справедлива ли игра, и, если нет, то кому лучше?
2. Те же вопросы для игры “три пальца” (можно выбрасывать от одного до трех пальцев).
Источник: БЗИ, NES.
Задача 7.78.
Еще одна игра “на пальцах”.
сколько-то пальцев (от 1 до ). Если оказалось поровну, то ничья. Если число пальцев, показанных одним и другим игроком, отличается на 1, то тот, у кого меньше, выигрывает $2. В остальных случаях тот, у кого больше, выигрывает $1.
1. Можно ли, не производя никаких вычислений, определить цену игры в смешанных стратегиях?
Приведите соображения, обосновывающие ваш ответ.
2. Пусть = 3. Как надо играть?
3. Верно ли, что при любом в игре имеется ровно одно смешанное равновесие?
Источник: БЗИ, NES.
Задача 7.79.
Решите по доминированию Источник: БЗИ.
Задача 7.80.
Итерационные игры. Играют участников. Функция полезности участника с номером имеет вид (1,..., ). Можно ли решить игру по доминированию? Если надо, сделайте какие-нибудь разумные предположения.
Источник: БЗИ.
Задача 7.81.
Инвесторы.
Два инвестора соревнуются. Организатор выдает каждому один рубль. Инвесторы одновременно выбирают способ вложения своего рубля. Каждый инвестор может выбрать себе любую случайную величину с () = 1 в качестве результата инвестирования. Победитель (тот, у кого окажется больше денег после инвестирования) получает от проигравшего 1 рубль, результаты инвестирования достаются организаторам.
Как выглядит оптимальная стратегия, если:
а) Результат инвестирования может принимать отрицательные значения?
б) Результат инвестирования не может принимать отрицательные значения?
в) Что изменится, если результат инвестирования может принимать значения на [0; ], > 1, а победитель в качестве выигрыша получает результат инвестиций проигравшего?
Источник: Ferguson?.
Задача 7.82.
Саша и Алеша.
У Маши два поклонника - Саша и Алеша. Маша прилетает в аэропорт в свой родной город в 12:00.
Саша и Алеша независимо друг от друга выбирают, когда приехать ее встречать. Каждый ухажер нетерпелив, поэтому приехав в аэропорт он либо сразу забирает Машу, которая уже прилетела; либо сразу уезжает, если Маши нет (она могла еще не прилететь или ее мог забрать другой ухажер).
Получивший Машу получает +1, проигравший -1; если Маша не досталась никому, то 0:0. Если Саша и Алеша приезжают одновременно - 0:0. Если до 13:00 Машу никто не встретит, она уезжает на такси.
Найдите равновесие по Нэшу Источник: Ferguson.
8 статические игры (а ля байесовские) Задача 8.1.
Вариант «Битвы полов»
Саша не совсем уверен, предпочитает ли Маша его компанию, или склонна избегать его. С точки зрения Саши:
с вероятностью 3 игра имеет вид: (2; 1) (0; 0) с вероятностью 3 игра имеет вид: (2; 0) (0; 2) Маша в отличие от Саши точно знает, в какую игру она играет. Тигр: Да, с такими Машами опасно играть!
В матрицах платеж Саши указан первым.
а) Укажите количество типов каждого игрока;
б) Сформулируйте чистые стратегии Саши и Маши;
в) Найдите равновесие по Нэшу в чистых стратегиях;
г) И в смешанных!
Задача 8.2.
Без слов Природа выбирает матрицу игры. Тигр: Я даже знаю, как зовут эту Природу!
С вероятностью 5 матрица имеет вид: (1; 2) (1; 3) С вероятностью 5 матрица имеет вид: (2; 1) (4; 6) Первый игрок знает, какую матрицу выбрала природа, второй - нет.
а) Укажите количество типов каждого игрока;
б) Сформулируйте чистые стратегии игроков;
в) Найдите равновесие по Нэшу в чистых стратегиях;
г) И в смешанных!
Задача 8.3.
Непрерывный вариант Значение 1 известно первому игроку, а значение 2 - второму.
а) Найдите равновесие по Нэшу.
Задача 8.4.
Равновесная стратегия для второго игрока?
Значение 1 известно первому игроку, а значение 2 - второму.
а) Найдите равновесие по Нэшу.
Задача 8.5.
Инвестиции Два партнера инвестируют 1 и 2 в совместное предприятие. Значение случайной величины известно первому игроку, а значение 2 - второму. Оба игрока знают, что 1 [0; 1], 2 [0; 1].
а) Найдите равновесие по Нэшу, в котором стратегии игроков имеют вид ( ) = +, где и - некоторые константы.
Задача 8.6.
Конверты... [О] В пяти конвертах спрятаны суммы в 10$, 20$, 40$, 80$ и 160$. Случайным образом выбираются два конверта с соседними суммами и выдаются игрокам. Тигр: А в конвертах - это взятки? Каждый игрок открывает свой конверт и выбирает, хочет ли он оставить себе сумму или хочет обменяться.
Обмен происходит, если оба игрока согласны обменяться.
а) Сколько чистых стратегий у каждого игрока?
б) Найдите все равновесия по Нэшу в чистых и смешанных стратегиях.
Источник: Jannssen, HSE-exam.
Задача 8.7.
Мусоросжигательный завод [Т] В стране городов. Около одного из них нужно построить большой мусоросжигательный завод.
Предположим, что ущерб от мусоросжигательного завода для жителей каждого города - случайная величина, равномерно распределенная на отрезке [0; 1]. Каждый город объявляет компенсацию, требуемую за постройку мусоросжигательного завода поблизости. Завод строят около города, запросившего наименьшую компенсацию. Деньги выплачивают остальные города в равной пропорции.
Найдите симметричное равновесие по Нэшу в чистых стратегиях;
Задача 8.8.
Величины и независимы и распределены равномерно на отрезке [0; 1]. Вася узнает предлагаемый ему приз, Петя узнает предлагаемый ему приз. Дальше каждый из игроков решает: брать свой приз или претендовать на приз противника. Игрок, выбравший свой приз, немедленно получает его.
Если оба игрока решили претендовать на приз противника, то никто ничего не получает. Если один игрок решил взять свой приз, а второй решил претендовать на приз противника, то оба получают сумму, на которую согласился первый игрок.
а) Найдите равновесие по Нэшу б) Придумайте смысловой текст в) Вариация в Величины и независимы и распределены равномерно на отрезке [0; 1]. Вася узнает предлагаемый ему приз, Петя узнает предлагаемый ему приз. Дальше каждый из игроков решает: брать свой приз или претендовать на приз противника. Игрок, выбравший свой приз, немедленно получает его.
Если оба игрока решили претендовать на приз противника, то каждый получает приз противника.
Если один игрок решил взять свой приз, а второй решил претендовать на приз противника, то претендующий на приз противника не получает ничего.
Найдите равновесие по Нэшу.
в) Вариация в Величины и независимы и распределены равномерно на отрезке [0; 1]. Вася узнает предлагаемый ему приз, Петя узнает предлагаемый ему приз. Дальше каждый из игроков решает: брать свой приз или претендовать на приз противника. Если игроки выбрали разные призы, то они получают их. Если игроки выбрали один и тот же приз, то они делят его поровну.
Найдите равновесие по Нэшу.
в) Вариация в Величины и независимы и распределены равномерно на отрезке [0; 1]. Вася узнает предлагаемый ему приз, Петя узнает предлагаемый ему приз. Дальше каждый из игроков решает: брать свой приз или претендовать на приз противника. Если игроки выбрали один и тот же приз, то они получают его (каждый в полном объеме). Если игроки выбрали разные призы, то они не получают ничего.
Найдите равновесие по Нэшу.
Задача 8.9.
Рынок «лимонов» [Slantchev] Встречаются два игрока: продавец и покупатель машины. Машина может быть хорошего качества («персик», для продавца ценность такой машины равна 3000, а для покупателя - 4000) с вероятностью и плохого качества («лимон», для продавца ценность такой машины равна 0, а для покупателя с вероятностью (1 ). Продавец знает качество машины, а покупатель - нет. Похожая машина судя по объявлениям в газете была продана за сумму. Продавец и покупатель одновременно принимают решение: соглашаться ли на сделку по сумме. Сделка происходит только в том случае, если обе стороны согласны.
Найдите равновесие по Нэшу в зависимости от и и определите вероятности торговли «лимонами»
и «персиками» в найденном равновесии.
Задача 8.10.
На рынке корову старик продавал... [Sloth] Покупатель и продавец одновременно называют цены и. Если, то обмен происходит по цене + ; если нет, то обмена не происходит. Ценность коровы для покупателя и продавца - независимые случайные величины и, распределенные равномерно на [0; 1]. Если обмен произошел по цене, то выигрыши равны = и =. Пусть - константа из [0; 1]. Рассмотрим следующую пару стратегий: продавец называет цену, если <, и 1 иначе; покупатель называет цену, если >, и 0 иначе.
а) При каких такая пара стратегий будет равновесием по Нэшу?
б) В осях ( ; ) нарисуйте множество, для которого обмен происходит. С какой вероятностью происходит обмен? Всегда ли происходит обмен в случае < ?
в) Как зависят ожидаемые выигрыши покупателя и продавца от ?
Пусть игроки используют линейные стратегии ( ) = + и ( ) = +.
г) Найдите равновесие по Нэшу в случае линейных стратегий.
д) В осях ( ; ) нарисуйте множество, для которого обмен происходит. С какой вероятностью происходит обмен? Всегда ли происходит обмен в случае < ?
Задача 8.11.
Две игры[22] Игроки будут играть в одну из двух игр. С вероятностью - в игру 1 (; 0) (0; ) С вероятностью (1 ) в игру 1 (0; ) (; 0) Известно, что 0 < <.
а) Найдите все равновесия по Нэшу в каждой из игр;
б) Пусть оба игрока не знают, в какую игру они играют. Найдите все равновесия по Нэшу в зависимости от параметра.
в) Пусть только второй игрок точно знает матрицу игры. Представьте эту игру, как статическую игру с неполной информацией: сколько типов у каждого игрока? сколько стратегий? Найдите все равновесия по Нэшу для каждого. Представьте эту игру, как динамическую игру с несовершенной информацией.
г) Найдите все равновесия по Нэшу для каждого, если только первый игрок точно знает матрицу игры.
Задача 8.12.
Выкуп доли Доля Маши в ЗАО «Красивое платье» составляет, а доля Кати - (1 ). Маша и Катя решили отказаться от дальнейшего сотрудничества. У ЗАО должна быть одна владелица! Ценность ЗАО для каждой владелицы - случайная величина равномерно распределенная на [0; 1].
а) Маша и Катя решили попробовать аукцион. Оба игрока одновременно называют цену ЗАО. Тот, кто назвал более высокую цену, должен выкупить акции партнера по предложенной им самим цене (более высокой). Найдите равновесие по Нэшу в линейных стратегиях, т.е. предлагаемая каждым игроком цена должна иметь вид = +, где - его оценка стоимости ЗАО, а и - константы.
Не забудьте случай = 0, т.е. Маша продавец, а Катя - покупатель. Возможно ли, что акции достанутся тому, кто их меньше ценит?
б) Маша и Катя снова экспериментируют. Оба игрока называют цену ЗАО. Тот, кто назвал более высокую цену, должен выкупить акции партнера по предложенной партнером цене (более низкой).
Найдите равновесие по Нэшу в линейных стратегиях, т.е. предлагаемая каждым игроком цена должна иметь вид = +, где - его оценка стоимости ЗАО, а и - константы. Возможно ли, что акции достанутся тому, кто их меньше ценит?
Задача 8.13.
Простой покер Юля и Петя делают ставку по 1$. Далее каждый из них тайно от противника узнает свое число.
Числа, получаемые Юлей и Петей, независимы и равномерно распределены на отрезке от нуля до единицы. Затем Юля и Петя одновременно выбирают, доложить ли еще по 5$, или сбросить карты.
Если оба игрока сбросили карты, то оба теряют свою первоначальную ставку в пользу казино; если один сбросил, а другой увеличил ставку, то увеличивший забирает себе все, что находится на кону;
если оба игрока увеличили ставку, то победителем считается тот, у кого число больше.
Найдите равновесия по Нэшу в этой игре (для простоты можно исключить нестрого доминируемые стратегии);
Задача 8.14.
Снова простой покер Юля и Петя делают ставку по 1$. Далее они по очереди тянут из шляпы бумажки с числами. В шляпе лежат натуральные числа от 1 до. Затем Юля и Петя одновременно выбирают, доложить ли еще по 5$, или сбросить карты. Если оба игрока сбросили карты, то оба теряют свою первоначальную ставку в пользу казино; если один сбросил, а другой увеличил ставку, то увеличивший забирает себе все, что находится на кону; если оба игрока увеличили ставку, то победителем считается тот, у кого число больше.
Найдите все равновесия по Нэшу в этой игре для = 3;
Задача 8.15.
Издержки в секрете Рассмотрите следующий вариант модели Курно. Функция спроса имеет вид =, где = 1 + 2. Предельные издержки обоих фирм - независимые одинаково распределенные случайные Пусть и свои, и чужие предельные издержки известны обеим фирмам.
а) Найдите равновесие по Нэшу;
Пусть каждая фирма наблюдает реализацию только своих предельных издержек. б) Найдите равновесие по Нэшу;
в) Сравните матожидание и дисперсию равновесного выпуска в обоих случаях.
Источник: Colell.
Задача 8.16.
Два игрока одновременно выбирают действительные числа 1 и 2, соответственно. Платежные функции имеют вид игроку, а значение 2 - второму.
Найдите равновесие по Нэшу в чистых стратегиях;
Задача 8.17.
Коррелированное равновесие Рассмотрим повнимательнее игру, которая играется один раз:
а) Найдите равновесие по Нэшу;
б) Найдите вероятности каждого из четырех исходов;
в) Изобразите на плоскости множество возможных платежей и множество равновесных платежей.
Допустим, перед началом игры оба игрока наблюдают результат подбрасывания монетки.
г) Как изменится множество стратегий игроков?
д) Как изменятся ответы на пункты а, б и в?
Допустим, перед началом игры происходит одно из трех равновероятных событий, или.
Первый игрок знает, произошло ли, или нет. Второй игрок знает, произошло ли.
е) Ответьте на аналогичные вопросы для новой игры.
Задача 8.18.
Два игрока одновременно выбирают действительные числа 1 и 2, соответственно. Платежные функции могут иметь один из ) двух видов:
Первый игрок точно знает, какой вид имеют платежные функции, второй знает только закон распределения.
а) Найдите равновесие по Нэшу в чистых стратегиях;
б) Предположим, что первый игрок до того, как второй игрок сделает свой ход, может послать ему один из двух сигналов «А» или «Б» (не обязательно достоверный!). Найдите равновесие по Нэшу в таком варианте игры.
Задача 8.19.
Меньше знаешь - крепче спишь Матрица игры имеет один из двух видов (вероятность каждого вида равна 0,5). Первый игрок знает матрицу игры, второй - нет. (1; 2/3) (1; 0) (1; 1) или (1; 2/3) (1; 1) (1; 0) а) Найдите равновесие по Нэшу и платеж второго игрока;
б) Допустим, что второй игрок также знает матрицу игры. Найдите новое равновесие по Нэшу;
в) Почему не срабатывает рассуждение «второй игрок может отказаться от лишней информации, поэтому его платеж не может упасть»?
Тигр: Многие знания означают многие печали Задача 8.20.
Байесовский семейный спор или “капризная жена”.
футбол ( ) или на балет (). Все осложняется тем обстоятельством, что жена может находиться в хорошем настроении (и тогда стремится быть вместе с мужем), а может и в плохом (и тогда видеть его не может). Короче, вот таблица игры. Строки соответствуют мужу, а столбцы — жене, чей выигрыш зависит от настроения (, ):
Найдите все байесовские равновесия, предполагая, что настроения и наступают с равными вероятностями. Не забудьте про смеси.
Источник: БЗИ, NES.
Задача 8.21.
Rendez-vous-1. Александра и Виктор живут на одной улице (считаем, что их места жительства являются случайными точками, равномерно и независимо распределенными на отрезке [1, 1]). Для того, чтобы договориться о встрече, они сообщают друг другу, где живут, и встречаются ровно посередине между названными точками. Сообщения делаются одновременно и независимо и необязательно правдивы (но все же в пределах [1, 1]). Полезность каждого из участников равна пройденному расстоянию, взятому со знаком “минус”.
1. Найдите оптимальный ответ Александры на правдивую стратегию Виктора (когда он в любом случае сообщает свое фактическое место жительства).
2. Докажите, что если каждый из участников будет играть, как Александра в п. 1, то получится байесово равновесие. Будет ли оно эффективным?
3. Разработайте механизм наподобие схемы Гровса, делающий равновесие ex-post эффективным.
Источник: БЗИ, NES.
8.1 Аукционы Фигура, изображающая правосудие!-провозгласил аукционист.– Бронзовая. В полном порядке. Пять рублей. Кто больше?
Задача 8.22.
Общее решение аукциона первой цены Ценность лота для каждого из покупателей - случайная величина, имеющая функцию плотности (). Игроки одновременно подают заявки с указанием цены покупки. Лот достается тому, кто указал наибольшую цену. Выигравший акцион платит названную им цену.
Найдите симметричное равновесие по Нэшу Задача 8.23.
auction in which the highest bidder wins, and pays the average of all the other bids. Private values that are uniformly distributed on [0, 1]. The question asks for the symmetric Bayse-Nash equilibrium and best response to truthful bidding Задача 8.24.
There is an auction with N players. Some painting is saling by auction. B is a bet for each player and this bet depends on player’s value V, i.e. Vi V[0;1] and B = f(Vi) Задача 8.25.
Василий, покажите публике «Правосудие»
В пассаже на Петровке на аукцион выставлена «Фигура, изображающая правосудие» (бронзовая, в полном порядке). Тигр: Я в полный рост с весами в лапе. Ценность фигуры для каждого из двоих покупателей - случайная величина, распределенная равномерно на отрезке [0; 1]. Игроки одновременно подают заявки с указанием цены покупки. Фигура достается тому, кто указал наибольшую цену. Если игроки указали одинаковую цену, то их платежи равны 1 ( ).
а) Укажите количество типов каждого игрока;
б) Пусть первый игрок использует линейную стратегию 1 (1 ) = 1 +. Найдите ожидаемый выигрыш второго игрока, при условии, что ценность «Правосудия» для него равна 2, а указал он цену 2.
в) Найдите равновесие по Нэшу, в котором оба игрока используют одинаковую линейную стратегию.
Укажите среднюю выручку продавца в этом равновесии.
Задача 8.26.
Аукцион второй цены За право купить стулья работы мастера Гамбса на аукционе столкнулись покупателей. Для покупателя ценность стульев равна, причем 1 > 2 >... > > 0. Аукцион проходит по следующим правилам: покупатели одновременно предлагают цены, товар получает тот, кто назовет наибольшую цену. При этом победитель аукциона платит наивысшую цену, названную остальными (!) игроками (не ту, что назвал он сам!). Так, например, если были предложены цены 4, 2, 7, 1, 3, 5, то стулья достаются покупателю, назвавшему цену 7, а платит он 5.
Уточнение:
Если наивысшая цена была названа сразу несколькими игроками, то товар получает один из них равновероятно, а платит он эту самую наивысшую цену.
а) Представьте эту игру нормальной форме. Классифицируйте ее.
б) Верно ли, что стратегия = (декларировать свою истинную ценность стульев) нестрого доминирует остальные стратегии покупателя ?
в) Найдите как минимум 3 различных равновесия по Нэшу в чистых стратегиях Задача 8.27.
Аукцион первой и второй цены. На аукционе, в котором участвуют два покупателя, продается картина. Ценность ее для покупателя составляет, = 1, 2, где 1, 2 — независимые случайные величины, равномерно распределенные на отрезке [0, 1]. Информация об доступна только -му участнику. Игрок тайно заявляет цену и запечатывает заявку в конверт, на котором пишет свою фамилию.
1. Пусть картина достается тому, кто назвал наибольшую цену, каковую он и платит. Предполагая стратегии игроков такими, что размер заявки пропорционален субъективной ценности картины, найти байесовское равновесие. Будут ли игроки декларировать свои истинные оценки картины?
2. Тот же вопрос для аукциона “второй цены”, когда картина достается тому, кто назвал наибольшую цену, но платит он цену, заявленную проигравшим аукцион.
Источник: БЗИ, NES.
8.2 Коррелированное равновесие Задача 8.28.
рованных равновесий для следующих игр:
Источник: БЗИ.
Задача 8.29.
Возможности необязывающих соглашений. Имеются два участника, каждый из которых может вести себя эгоистически () или кооперативно (). Если оба играют, то получают по. Если один играет, а другой, то выигрыши составляют, соответственно, и (0 < < < ). Если оба эгоисты, то по нулям.
1. С какими весами надо смешивать исходы игры, чтобы получилось коррелированное равновесие? Задайте ответ в виде выпуклой оболочки нескольких наборов весов.
2. Найдите максимально возможный суммарный выигрыш, реализуемый в коррелированных равновесиях. В каких случаях он превышает то, что достижимо в равновесиях Нэша?
Источник: БЗИ.
Задача 8.30.
Коррелированное равновесие. Двое бегут друг навстречу другу по лыжне. Можно либо уступить пол-лыжни, либо не уступать вовсе. Решение принимается одновременно. Если вы уступили, а вам — нет, то вы вынуждены быстренько уступить ещё и вторую половину, и ваш выигрыш от этого равен 0, а выигрыш наглеца равен 3. Если оба вежливо уступили, то обоим по 2; если оба наглецы, то столкнулись, и обоим по (1). Осознав, что в игре существуют два несимметричных равновесия, а наилучший исход недостижим при некооперативном поведении, игроки решили использовать «коррелированные» смешанные стратегии. А именно, они пригласили арбитра, продиктовали ему вероятности всех четырёх исходов, предложили ему разыграть в тайне от них соответствующую лотерею, и каждому игроку на ушко шепнуть, как ему ходить. Дальше, разумеется, каждый волен решать, следовать ли ему полученному предписанию. Возможно ли таким образом добиться чеголибо большего, чем просто кидая монетку, и в случае решки разыгрывая одно из равновесий Нэша, а при орле — другое? Какие выигрыши достижимы при таком механизме?
Источник: НМУ, экзамен 2004, Леша Савватеев.
9 динамические игры с несовершенной информацией You might ask, «Will reading this book help me make money?» A true game-theoretic answer might be that since you have probably already bought this book, I don’t really care what benefit you would receive from reading it, so why should I bother answering the question?
James Miller, Game theory at work Задача 9.1.
Судья и потерпевший Ущерб - случайная величина, равновероятно принимающая любое значение из {0; 1;...; 99}. Потерпевший точно знает величину ущерба, а судья знает лишь распределение. Потерпевший выбирает один из двух вариантов: честно задекларировать величину ущерба или не говорить ничего. Судья выбирает величину компенсации.
Полезность потерпевшего 1 =. Полезность судьи 2 = ( )2.
Найдите равновесия по Нэшу, совершенные в подыграх.
Задача 9.2.
Снова конверты Десять неотличимых друг от друга конвертов. В каждом из девяти лежит по 1000 рублей, в десятом не лежит ничего. Маша выбирает наугад один из десяти конвертов и тайно от Пети вскрывает его.
Петя, по-прежнему не зная о содержимом конверта, назначает цену. Если Маша согласна с ценой, то конверт переходит к Пете, а оговоренная цена уплачивается Петей. Если Маша не согласилась с ценой, то конверт остается у нее.
а) Найдите все равновесия по Нэшу в чистых стратегиях;
б) Найдите все равновесия по Нэшу в смешанных стратегиях;
в) Изменится ли результат игры, если сразу после вскрытия конверта Маша дополнительно будет выбирать, предоставлять ли Пете право выкупа?
Задача 9.3.
Два коллекционера [Cramton] Два известных коллекционера хотят заполучить одну картину. Оба оценивают для себя эту картину в 10 миллионов рублей. Аукцион проходит по следующим правилам:
Игроки по очереди выбирают, повысить ли ставку на пол-лимона или выйти из аукциона (при этом картина достается сопернику). Когда аукцион окончился, оба игрока платят последнюю названную ими цену. Если игроки повышают ставку постоянно, то их платежи равны минус бесконечности. а) Найдите два равновесия по Нэшу в чистых стратегиях;
б) Найдите совершенное подыгровое равновесие по Нэшу следующего вида: первый игрок на каждом раунде повышает ставку с вероятностью, а второй - с вероятностью. Сколько в таком равновесии стоит право первого хода?
в) Есть ли в игре другие равновесия по Нэшу?
Задача 9.4.
«Лохотрон»
У индивидов есть уникальная возможность получить чудо-швабру! Только у нас! В каждом раунде индивиды одновременно решают, внести ли дополнительно один рубль, либо выйти из игры. Внесенные деньги не возвращаются. Чудо-швабру ценности рублей получает последний оставшийся. Если несколько игроков вносят деньги бесконечно долго, то их выигрыши равны минус бесконечности.
а) Найдите равновесия по Нэшу совершенные в подырграх в чистых стратегиях.
б) Как изменится ответ, если индивиды принимают решения по очереди?
Задача 9.5.
Ультиматум [О] Два брата снова делят пирог. Старший предлагает, как его поделить. Затем младший одобряет, или не одобряет дележ. Если младший не одобряет дележ, то мама уносит пирог на работу.
а) Найдите все совершенные подыгровые равновесия по Нэшу б) Мама уже разрезала пирог на частей! Теперь, старший брат предлагает, кому сколько кусочков достанется. Найдите все совершенные подыгровые равновесия по Нэшу.
в) Что происходит, если стремится к бесконечности?
г) Найдите совершенные подыгровые равновесия в непрерывном и дискретном вариантах «Ультиматума», если братья завидуют друг другу, т.е. когда первому брату досталась доля, он получает удовольствие в размере (1 ), где (0; 1) - коэффициент зависти.
Задача 9.6.
Простейший покер Маша и Саша положили на кон по одному доллар. Маша берет из колоды одну карту. Известно, что выигрышная для Маши карта придет с вероятностью. Узнав, какая карта ей досталась, Маша может либо сразу открыть карту, либо удвоить ставку. Если ставка удвоена, то Саша может либо отказаться от удвоения ставки (и проиграть один доллар), либо поддержать удвоение ставки. Затем карта открывается.
а) Найдите секвенциальное равновесие в зависимости от.
Тигр: Во многих книжках авторы пишут «секвенциальное равновесие», хотя имеют ввиду не более, чем равновесие по Нэшу. Я не знаю почему, наверное, звучит похоже на «сексуальное».
б) Постройте график зависимости цены игры от.
в) При каком игра справедлива, если ставка увеличивается не вдвое, а в раз?
г) Попробуйте поиграть со своей девушкой (молодым человеком)!
Задача 9.7.
Лес [Colell, Sloth] На каждом дереве найдите:
Совершенные Байесовские равновесия;
Секвенциальные равновесия;
Равновесия по Нэшу; Для этого переведите деревья в матричную форму (для деревьев с тремя игроками будем считать, что первый игрок выбирает матрицу игры, второй - строку, а третий столбец);
p=0. p=0. (0;2) (2;2) Тигр: Настоящие зубры могут попытаться работать в смешанных стратегиях!
Задача 9.8.
Выкуп доли- Доля Маши в ЗАО «Красивое платье» составляет, а доля Кати - (1 ). Маша и Катя решили отказаться от дальнейшего сотрудничества. У ЗАО должна быть одна владелица!
Сначала Маша называет цену - сколько по ее мнению стоит все ЗАО. Затем Катя выбирает выкупить ли за Машину долю или продать Маше свою долю за (1 ). Ценность ЗАО для каждой владелицы - случайная величина равномерно распределенная на [0; 1].
Найдите совершенное равновесие по Байесу;
Задача 9.9.
p=0. (-1;4;-1) (0;2;0) (-1;3;-1) p=0. Недостоверное наблюдение Вася Лимонадов очень любит лимонад. Берет с собой обычно одну бутылку (L), но может взять и две (R). По натуре Вася Лимонадов жадный и не любит, когда его просят поделиться лимонадом.
Коля Безлимонадов может либо попросить у Васи попробовать лимонад (l), либо молча завидовать (r). Конечно, лучше спрашивать Васю, когда у того с собой много лимонада...
а) Найдите равновесия по Нэшу в чистых стратегиях. Какие из них являются совершенными в подыграх?
б) Предположим, что Коля не знает, взял ли Вася одну или две бутылки лимонада. Нарисуйте новое дерево игры. Найдите равновесия по Нэшу. Найдите слабые секвенциальные равновесия.
в) Предположим, что Коля ошибается в оценке количества бутылок, взятых Васей с вероятностью, т.е., например, если Вася взял одну бутылку лимонада, то с вероятностью Коля думает, что у Васи две бутылки. Нарисуйте новое дерево игры. Найдите равновесия по Нэшу. Найдите слабые секвенциальные равновесия.
Задача 9.10.
Рассмотрим игру двух игроков. Сначала Природа выбирает тип первого игрока, известные только ему. Первый игрок может быть рациональным с вероятностью 0.7 и импульсивным с вероятностью 0.3. Затем второй игрок выбирает между «стоп» (игра оканчивается платежом (0;0)) и «вперед» (ход переходит к первому). Далее первый игрок выбирает между «стоп» (игра оканчивается платежом (2;-1)) и «вперед» (ход переходит ко второму). Импульсивный игрок всегда выбирает «вперед». Далее второй игрок выбирает между «стоп» (игра оканчивается платежом (1;1)) и «вперед» (ход переходит к первому). Далее первый игрок выбирает между «стоп» (игра оканчивается платежом (3;0)) и «вперед» (игра оканчивается платежом (2;2)). Импульсивный игрок всегда выбирает «вперед».
а) Нарисуйте дерево игры б) Найдите слабые секвенциальные равновесия в) Найдите секвенциальные равновесия Source: Lones Smith Задача 9.11.
SPNE=WSE?
Тигр: Все бюрократы прячутся за красивые сокращения вроде TLA и ETLA!
Автор: Three Letter Acronym и Extended Three Letter Acronym.
б) Найдите все равновесия в чистых стратегиях, совершенные в подыграх;
(0;3;3) (0;0;2) (0;4;0) (3;1;1) в) Найдите все слабые секвенциальные равновесия в чистых стратегиях;
Задача 9.12.
Вхождение в отрасль Фирма Новичок (Entrant) решает, входить или не входить на рынок; если она входит на рынок, то случайным образом определяется, какие у нее будут издержки производства, высокие (с вероятностью 3 ) или низкие (с вероятностью 2 ). Затем фирма Старожил (Incumbent) решает, развязывать ли ценовую войну или выбирать молчаливый сговор. Издержки фирмы Новичка достоверны известны только ей самой.
Выигрыши определяются так:
(0; 10), если Новичок не входит на рынок;
(1; 9), если у Новичка высокие издержки, а Старожил выбирает ценовую войну;
(6; 7), если у Новичка высокие издержки, а Старожил выбирает молчаливый сговор;
(4; 4), если у Новичка низкие издержки, а Старожил выбирает ценовую войну;
(8; 7), если у Новичка низкие издержки, а Старожил выбирает молчаливый сговор;
а) Изобразите игру в развернутой форме;
б) Укажите, сколько стратегий у каждого игрока;
в) Переведите игру в матричную форму;
г) Найдите равновесия по Нэшу;
д) Укажите, какие из найденных равновесий по Нэшу являются совершенными в подыграх.
Задача 9.13.
Вхождение на рынок (Entry-deterrence game) Фирма Новичок (Entrant) решает, входить или не входить на рынок; если она входит на рынок, то фирма Старожил (Incumbent) решает, бороться ли с новичком (to Fight) или нет (to Accommodate).
Векторы платежей (первым указан платеж фирмы Новичка) равны: (0; 3), если фирма Новичок не входит на рынок; (1; ), если фирма Новичок входит, а фирма Старожил выбирает борьбу; (1; 1), если фирма Новичок входит, а фирма Старожил отказывается от борьбы. Значение величины является частной информацией фирмы Старожила. Фирме Новичку известны априорные вероятности а) Сформулируйте все чистые стратегии обеих фирм;
б) Нарисуйте дерево игры (возможно два варианта);
в) Найдите совершенное равновесие по Байесу.
Задача 9.14.
Повторяемая игра «Вхождение на рынок»
Рассмотрите игру, заключающуюся в двукратном повторении игры, предложенной в задаче (...).
После первого раунда фирма Новичок узнает значение. Дисконт фактор = 0, 8.
а) Сформулируйте все чистые стратегии обеих фирм;
б) Найдите совершенное равновесие по Байесу.
Задача 9.15.
Настоящие ковбои заказывают бифштекс!
У первого игрока два типа: настоящий ковбой ( ! ) и сладкоежка ( ), которые природа выбирает с вероятностями 0,9 и 0,1 соответственно. Оба игрока знают эти вероятности, но только первый игрок видит ход Природы. Первый игрок делает заказ у стойки бара в тот момент, когда в бар входит второй игрок.
Второй игрок - довольно буйный тип. Тигр: тип не в смысле теории игр, а просто тип. Он заходит в бар, чтобы подраться, однако он трус и не хотел бы встретиться с настоящим ковбоем. У второго игрока есть выбор: завязывать драку (F) или не завязывать (N). Перед своим ходом второй игрок видит выбор первого игрока.
Первый игрок может заказать бифштекс (S) или пудинг (P). Настоящие ковбои предпочитают бифштекс, а сладкоежки - пудинг. а) Сформулируйте все чистые стратегии обоих игроков;
б) Найдите совершенное равновесие по Байесу.
в) Найдите секвенциальное равновесие;
Задача 9.16.
Быть или не быть?
Докажите или опровергните следующие утверждения б) Любое равновесие, слабо-совершенное по Байесу-Нэшу, является совершенным в подыграх;
в) Любое равновесие, совершенное в подыграх, является слабо-совершенным по Байесу-Нэшу;
Задача 9.17.
Вето Петя и Вася должны выбрать одну из четырех альтернатив. Они по очереди вычеркивают по одной альтернативе из списка, до тех пор, пока не останется одна невычеркнутая. Первым ходит Петя.
Предпочтения Пети -, предпочтения Васи - диаметрально противоположные.
а) Найдите совершенное подыгровое равновесие по Нэшу;
б) Пусть предпочтения Васи с вероятностью совпадают с Петиными, и с вероятностью (1 ) являются противоположными. Петя точно знает свои предпочтения, а Вася знает только априорные вероятности. Найдите совершенное равновесие по Байесу-Нэшу в зависимости от.
Задача 9.18.
Где мел?
Чтобы никто не воспользовался хорошим мелом в ее отсутствие, учительница Марь Ивановна Сидорова решила спрятать куски хорошего мела. Она может спрятать их либо в самой классной комнате, либо в лаборантской. Учитель математики Иванов И.И. будет искать мел или только в лаборантской, или только в классной комнате (у него урок уже начинается). Если он находит мел, то получает полезность 1, если нет, то ему приходится писать плохим мелом, и он получает полезность 0. Утром следующего дня Марь Ивановна обнаруживает, что забыла, где спрятала мел. Если она находит мел с первой попытки, то получает полезность 2, если только со второй попытки - полезность 1, и полезность 0, если весь хороший мел использован Иваном Ивановичем.
а) Представьте игру в развернутой форме;
б) Является ли эта игра игрой с совершенной памятью (perfect recall)?
в) Переведите игру в матричную форму;
г) Найдите все равновесия по Нэшу в чистых и смешанных стратегиях Задача 9.19.
К берегу водохранилища подошли трое...
а) Является ли эта игра игрой с совершенной памятью?
б) Какие профили стратегий приводят к игре, и ?
в) Придумать к этому дереву платежи и текст задачи, начинающийся словами «К берегу водохранилища подошли трое»
Задача 9.20.
Большой аукцион [Colell] На рынке покупателей, каждый из которых хочет купить одного говорящего попугая. Ценность попугая для покупателей различна: 1 < 2 <... < 1 <. На рынке доступно всего < попугаев. Покупатели одновременно называют цену. Попугаи достаются покупателям, назвавшим наивысшие цены. Если одинаковых предложений слишком много, то попугаи распределяются так:
сначала каждый покупатель имеет шанс добровольно отказаться от покупки, если после всех отказов желающих осталось больше, чем попугаев, то попугаи распределяются случайным образом. Найдите равновесие по Нэшу, в котором все покупатели предлагают одинаковую цену.
Задача 9.21.
Залезьте на дерево и (0;2) а) Найдите слабые секвенциальные равновесия в зависимости от ;
б) Найдите секвенциальные равновесия в зависимости от ;
Источник: Colell.
Задача 9.22.
Это война! [Slantchev] Две страны, Левая и Правая, хотят поделить территорию в виде отрезка [0; 1]. Столицы стран находятся на концах отрезка. Природа выбирает издержки ведения войны: - для Левой и для Правой, величины и независимы и равномерно распределены на отрезке [0; 1]. Издержки известны только Левой стране. Издержки известны обеим странам. Правая страна выдвигает свои требования к границе [0; 1]. Левая страна либо удовлетворяет требования Правой, либо развязывает войну. Правая страна побеждает в войне с экзогенной вероятностью (0; 1). Странепобедительнице достается вся территория.
а) Найдите равновесия по Нэшу в чистых стратегиях; совершенные равновесия по Байесу-Нэшу.
б) Найдите вероятность войны и средние выигрыши игроков в равновесии.
в) Предположим, что издержки ведения войны были бы общеизвестны. Какова была бы вероятность войны и средние выигрыши стран в равновесии?
г) Ответьте на пункты «а» и «б», если требования выдвигает Левая страна.
Задача 9.23.
Наследство [Slantchev] В игре два игрока: родственник графа и продавец соседнего имения. После смерти граф оставил своему далекому родственнику сумму. В отличие от родственника продавец соседнего имения не знает точной суммы наследства. По оценкам продавца это либо 1000 рублей с вероятностью, либо 2000 рублей с вероятностью (1 ). Продавец назначает свою цену имения, а родственник выбирает, выкупать близлежащее имение или нет. У родственника нет других денег кроме наследства от графа, а имение он оценивает больше чем в 2000 рублей.
Найдите равновесие по Нэшу в зависимости от Задача 9.24.
Неправильная монетка выпадает «орлом» с вероятностью. Первый игрок знает результат выпадения монетки, второй - нет. Первый игрок объявляет второму, как выпала монетка (при этом он может, как сказать правду, так и соврать). Затем второй делает свою догадку о том, как в действительности выпала монетка. За свою правдивость первый игрок получает единицу полезности и еще две единицы получает в том случае, если второй скажет «орел». Второй игрок получает единицу полезности, если верно угадает, как выпала монетка.
Представьте игру в форме дерева;
Найдите все равновесия по Нэшу при = 0, 7 ;
Найдите все равновесия по Нэшу в зависимости от ;
Задача 9.25.
Текстовое описание Первый игрок выбирает в какой руке спрятать пуговицу. Затем второй игрок пытается угадать в какой руке находится пуговица. За неугаданную руку второй платит первому два рубля. За угаданную левую руку первый платит второму один рубль, за угаданную правую - три рубля.
а) С какой вероятностью монета следует прятать в левой руке?
б) В чью пользу эта игра?
Задача 9.26.
Вариация на тему «21»
Цель игры - набрать в сумме как можно большее количество очков, но не больше трех. Предположим, что каждая карта взятая из колоды приносит игроку количество очков, равномерно распределенное на отрезке [1; 3], независимо от предыдущих карт. Сначала первый игрок берет по одной столько карт, сколько захочет. Затем второй игрок, зная только сколько карт взял первый игрок, берет себе по одной столько карт, сколько захочет. Выигрывает тот, кто набрал наибольшую сумму, не превосходящую 3 очка. Если на руках у каждого игрока больше 3 очков, то выигрывает второй игрок.
Найдите равновесие по Нэшу Источник: Lones Smith.
Задача 9.27.
Разница между стратегиями а) Укажите число чистых стратегий каждого игрока;
б) Является ли эта игра игрой с совершенной памятью (perfect recall)?
в) Приведите пример эквивалентных поведенческой и смешанной стратегии;
г) Можно ли найти смешанную стратегию, для которой не существует эквивалентной поведенческой?
д) Можно ли найти поведенческую стратегию, для которой не существует эквивалентной смешанной?
е) Приведите пример профиля стратегий, приводящего к игре, и.
Задача 9.28.
“Лабиринт”. 2-а игрока играют на графе (дереве) игры: первый игрок с именем выбирает вверх или вниз, затем второй игрок с именем - влево или вправо, и т.д. Это дерево с корнем < 1 >, с 12-ю вершинами (типа up-righ-up-right), глубиной 4 хода можно представить так:
K3dlK3dr | | | | S4dld S4drd / / / / О К О В Р Г Е Й Взяв свое имя как бесконечную последовательность символов типа “коковинкокови...”, свое имя типа “сергейсергейсер...” задайте выигрыши первого и вторго игроков в вершинах, как на рисунке; пара букв в каждой вершине.
Подставьте вместо каждой буквы имени число — ее номер в алфавите, либо решайте непосредственно в буквах: более поздняя больше ст’оит.
1)Найти,. 2)Найти в альтернативном предположении, что второй ход (вершины 2, 2) производит природа, случайно, с вероятностями 0.5, и оба игрока не способны определить, влево или вправо произошел выбор.
Источник: БЗИ, Коковин.
Задача 9.29.
Соседи. Антон и Борис, соседи по общежитию, каждый день тратили по 20 мин. на поход в магазин за продуктами. Им это надоело и, чтобы сэкономить время, они договорились в течение ближайших четырех дней ходить в магазин по очереди и покупать на всех: в первый день Антон, затем Борис и т. д. Покупка продуктов для соседа отнимает лишние 5 мин, поэтому у идущего в магазин появляется соблазн нарушить соглашение и купить продукты только себе. Если кто-то хоть раз так сделает, то в последующие дни ходить в магазин снова будут по отдельности (да и в этот день обманутому соседу придется прогуляться).
Антон всегда действует сообразно обстоятельствам (в каждый из двух своих дней может выбирать, выполнить или нарушить соглашение), а вот Борис может являться оппортунистом, как Антон, а может быть и честным, т. е. всегда выполнять соглашение (в этом случае у него оба раза по единственному возможному действию). Антон верит, что Борис с вероятностью > 0 является честным.
1. Как выглядит развернутая форма игры, если полезности участников равны выигранному времени?
2. При каких существует секвенциальное равновесие, в котором Антон в первый день играет честно (выполняет соглашение)?
Источник: БЗИ, NES.
Задача 9.30.
Пример “Масти и Картинки”.
Здесь предполагается, что строчный игрок выберет: Старшие или Младшие, потом столбцовый Красные или Черные, потом строчный - конкретную картинку из уже названной группы (из Старших или из Младших), потом столбцовый - конкретную масть из уже названного цвета. Найти SPE, INDW.
Вариант 2: Усложнение задачи - найти SPE, INDW, PBE если последний ход решается жребием подбрасыванием монетки.
Вариант 3: То же, но результат подбрасывания известен до ходов второму игроку, и только ему.
Вариант 4: Найти SPE, INDW, PBE если первый ход решается жребием - подбрасыванием монетки, и никто не видит его.
Источник: БЗИ.
Задача 9.31.
Пример “Trivial quize” (упрощенный покер)?? Разыгрывая 1 рубль, Анна тянет карту из колоды, смотрит, и не показывая Борису (у которого открыт Валет, а карты от 10-ки до Туза), или удваивает ставку, или пасует и имеет -1, а Борис 1. Если удвоено, Борис или пасует и имеет -2, а Анна 2, или удваивает, и карта открывется. Если она больше, чем Валет, то Анна выиграла 4 у Бориса 4, иначе проигрывает 4. Найти PBE (частоты ходов при каждой карте).
Источник: БЗИ.
Задача 9.32.
«