Лекция 5 (545624)
Текст из файла
Домашнее задание13. Найти все ситуации равновесия в игре(И.В.Кацев (СПб ЭМИ)(0, 0) (2, 2)(1, 1) (0, 0)Позиционные игры).20121 / 17Домашнее задание14. Найти все ситуации равновесия в игре(0, 0) (5, 4) (4, 5)(4, 5) (0, 0) (5, 4) .(5, 4) (4, 5) (0, 0)И.В.Кацев (СПб ЭМИ)Позиционные игры20122 / 17Домашнее задание15. Найти все ситуации равновесия в игре трех лиц, в которой игрок 1 выбираетстроку, игрок 2 выбирает столбец. а игрок 3 выбирает матрицу.()(0, 0, 0) (6, 5, 4)(5, 4, 6) (0, 0, 0)И.В.Кацев (СПб ЭМИ)()(4, 6, 5) (0, 0, 0)(0, 0, 0) (0, 0, 0)Позиционные игры20123 / 17Домашнее задание16. Рассматривается конечная бескоалиционная игра двух игроков, где у первогоn (чистых) стратегий, а у второго m.а) Каковы минимальное и максимальное возможные количества равновесий поНэшу в чистых стратегиях?б) Тот же вопрос про смешанные стратегии.И.В.Кацев (СПб ЭМИ)Позиционные игры20124 / 17Домашнее задание17.
Рассмотрим аукцион, где множество стратегий каждого игрока равно [0,1], афункции выигрыша равны1 − xi ,1Ki (x) =− xik−xiесли xi> x(i),если | arg maxj∈N xj |если xi= k, xi ∈ arg maxj∈N xj ,< x(i),где x(i) = supj̸=i xj .а) Докажите, что в данной игре нет равновесия по Нэшу в чистых стратегияхб) Найдите хотя бы одно равновесие по Нэшу в данной игре.И.В.Кацев (СПб ЭМИ)Позиционные игры20125 / 17Рафинирование равновесий по НэшуИ.В.Кацев (СПб ЭМИ)Позиционные игры20126 / 17Рафинирование равновесий по НэшуСитуация x∗ ( в чистых стратегиях) называется ситуацией сильного равновесия вигре Γ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩, если для любой коалиции игроков S ⊂ N и любойее стратегии xS = (xi )i∈S найдется такой игрок i ∈ S, чтоKi (x∗S , xS )И.В.Кацев (СПб ЭМИ)≤ Ki (x∗ ).Позиционные игры20126 / 17Рафинирование равновесий по НэшуСитуация x∗ ( в чистых стратегиях) называется ситуацией сильного равновесия вигре Γ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩, если для любой коалиции игроков S ⊂ N и любойее стратегии xS = (xi )i∈S найдется такой игрок i ∈ S, чтоKi (x∗S , xS )≤ Ki (x∗ ).Общий смысл - никакой коалиции невыгодно отклоняться от положенияравновесия.И.В.Кацев (СПб ЭМИ)Позиционные игры20126 / 17Рафинирование равновесий по НэшуСитуация x∗ ( в чистых стратегиях) называется ситуацией сильного равновесия вигре Γ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩, если для любой коалиции игроков S ⊂ N и любойее стратегии xS = (xi )i∈S найдется такой игрок i ∈ S, чтоKi (x∗S , xS )≤ Ki (x∗ ).Общий смысл - никакой коалиции невыгодно отклоняться от положенияравновесия..Упражнение.Приведитепример игры, где нет ситуаций сильного равновесия..И.В.Кацев (СПб ЭМИ)Позиционные игры20126 / 17Рафинирование равновесий по НэшуУстойчивость по отношению к ошибкам ”дрожащей руки”.И.В.Кацев (СПб ЭМИ)Позиционные игры20127 / 17Рафинирование равновесий по НэшуУстойчивость по отношению к ошибкам ”дрожащей руки”.Пусть Γ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩, Xi - конечные множества, Mi - множествосмешанных стратегий игрока i ∈ N.
Через M0 ⊂ Mi обозначим подмножествовполне смешанных стратегий игрока i.И.В.Кацев (СПб ЭМИ)Позиционные игры20127 / 17Рафинирование равновесий по НэшуУстойчивость по отношению к ошибкам ”дрожащей руки”.Пусть Γ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩, Xi - конечные множества, Mi - множествосмешанных стратегий игрока i ∈ N. Через M0 ⊂ Mi обозначим подмножествовполне смешанных стратегий игрока i.Ситуация µ∗ ∈ M называется ситуацией совершенного равновесия, еслисуществует последовательность µk ∈ M0 , такая чтоlimk→∞µki (xi )= µ∗i (xi ), ∀i ∈ N, xi ∈ Xi ,(1)µ∗i ∈ arg max Ki (µki , τi ) ∀i ∈ N.(2)τi ∈MiИ.В.Кацев (СПб ЭМИ)Позиционные игры20127 / 17Совершенное равновесие.Утверждение.Любаяситуация совершенного равновесия является равновесием по Нэшу..И.В.Кацев (СПб ЭМИ)Позиционные игры20128 / 17Совершенное равновесие.Утверждение.Любаяситуация совершенного равновесия является равновесием по Нэшу...Теорема.В любой конечной бескоалиционной игре существует ситуация совершенногоравновесия..И.В.Кацев (СПб ЭМИ)Позиционные игры20128 / 17Позиционные игры.И.В.Кацев (СПб ЭМИ)Позиционные игры20129 / 17Позиционные игры.Рассмотрим следующую игру:Имеются два игрока и две карты: старшая (С) и младшая (М).Игрок 1 с вероятностью 1/2 получает одну из них, видит ее, но игрок 2 не знает,какую карту получил игрок 1.Дальше ходит игрок 1: в обоих случаях он может либо спасовать, и тогда игразаканчивается, и он проигрывает 1, либо продолжить игру.Если он продолжает, то далее ходит игрок 2, который также имеет возможностьлибо спасовать, и тогда заканчивается и игрок 2 проигрывает 1, либо попроситьигрока 1 открыть карту.Если у игрока 1 оказалась карта С, то игрок 1 выигрывает 2, если оказалась картаМ, то проигрывает 2.
Игра антагонистическая, то есть выигрыш одного игрокаравен проигрышу другого.И.В.Кацев (СПб ЭМИ)Позиционные игры20129 / 17Позиционные игры.n + 1 тип ходов - ходы каждого из игроков и случайные ”ходы природы”.Информационное множество - множество позиций, который не может различитьданный игрок i.Окончательная (терминальная) позиция - позиция, в которой нет ходов.Партией называется путь, соединяющий начальную позицию с окончательной.И.В.Кацев (СПб ЭМИ)Позиционные игры201210 / 17Игры с полной информациейИгрой с полной информацией называется позиционная игра, всеинформационные множества которой состоят из одной позиции.И.В.Кацев (СПб ЭМИ)Позиционные игры201211 / 17Игры с полной информациейИгрой с полной информацией называется позиционная игра, всеинформационные множества которой состоят из одной позиции..Теорема (Цермело–Нейман).Конечные игры n лиц с полной информацией имеют ситуации равновесия вчистыхстратегиях..И.В.Кацев (СПб ЭМИ)Позиционные игры201211 / 17Общее знаниеИгрок 1 рационален (выбирает лучшую альтернативу)И.В.Кацев (СПб ЭМИ)Позиционные игры201212 / 17Общее знаниеИгрок 1 рационален (выбирает лучшую альтернативу)Игрок 2 знает, что игрок 1 рационаленИ.В.Кацев (СПб ЭМИ)Позиционные игры201212 / 17Общее знаниеИгрок 1 рационален (выбирает лучшую альтернативу)Игрок 2 знает, что игрок 1 рационаленИгрок 1 знает, что игрок 2 знает, что игрок 1 рационаленИ.В.Кацев (СПб ЭМИ)Позиционные игры201212 / 17Общее знаниеИгрок 1 рационален (выбирает лучшую альтернативу)Игрок 2 знает, что игрок 1 рационаленИгрок 1 знает, что игрок 2 знает, что игрок 1 рационаленИгрок 2 знает, что игрок 1 знает, что игрок 2 знает, что игрок 1 рационаленИ.В.Кацев (СПб ЭМИ)Позиционные игры201212 / 17Дуополия КурноДва производителя товара.
Стратегия = объем производства qi ∈ [0, a]. Затратына производство: ci (qi ) = cqi , i = 1, 2. Цена на рынке P зависит от количестватовара на рынке Q = q1 + q2 и равна{P(Q)=a − Q,0,< a,если Q ≥ a.если QФункция выигрыша каждого игрока равна прибыли:Ki (q1 , q2 )И.В.Кацев (СПб ЭМИ)= P(Q)qi − cqi , i = 1, 2.Позиционные игры201213 / 17Дуополия КурноДва производителя товара. Стратегия = объем производства qi ∈ [0, a]. Затратына производство: ci (qi ) = cqi , i = 1, 2. Цена на рынке P зависит от количестватовара на рынке Q = q1 + q2 и равна{P(Q)=a − Q,0,< a,если Q ≥ a.если QФункция выигрыша каждого игрока равна прибыли:Ki (q1 , q2 )= P(Q)qi − cqi , i = 1, 2.Стратегии наилучшего ответа:qiИ.В.Кацев (СПб ЭМИ)1= (a − qj − c), i, j = 1, 2, i ̸= j.2Позиционные игры201213 / 17Дуополия КурноДва производителя товара.
Стратегия = объем производства qi ∈ [0, a]. Затратына производство: ci (qi ) = cqi , i = 1, 2. Цена на рынке P зависит от количестватовара на рынке Q = q1 + q2 и равна{P(Q)=a − Q,0,< a,если Q ≥ a.если QФункция выигрыша каждого игрока равна прибыли:Ki (q1 , q2 )= P(Q)qi − cqi , i = 1, 2.Стратегии наилучшего ответа:qi1= (a − qj − c), i, j = 1, 2, i ̸= j.2Равновесие:qiИ.В.Кацев (СПб ЭМИ)=a−c3,P =a + 2c3, Ki =Позиционные игры(a − c)29201213 / 17Дуополия ШтаккельбергаФирмы выходят на рынок по очереди.И.В.Кацев (СПб ЭМИ)Позиционные игры201214 / 17Дуополия ШтаккельбергаФирмы выходят на рынок по очереди.Вторая фирма (по рациональности) на ход q1 будет отвечать q2 = 12 (a − q1 − c).Следовательно, цена будет равна P = a − Q = 21 (a − q1 + c) и выигрыш первойфирмы составит K1 = 12 (a − q1 − c)q1 .
То есть задача сводится к максимизации12 (a − q1 − c)q1И.В.Кацев (СПб ЭМИ)Позиционные игры201214 / 17Дуополия ШтаккельбергаФирмы выходят на рынок по очереди.Вторая фирма (по рациональности) на ход q1 будет отвечать q2 = 12 (a − q1 − c).Следовательно, цена будет равна P = a − Q = 21 (a − q1 + c) и выигрыш первойфирмы составит K1 = 12 (a − q1 − c)q1 . То есть задача сводится к максимизации12 (a − q1 − c)q1Результат:q1И.В.Кацев (СПб ЭМИ)=a−c2, q2 =Позиционные игрыa−c4201214 / 17Смешанные и поведенческие стратегииСмешанная стратегия - выпуклая комбинаций чистых стратегийИ.В.Кацев (СПб ЭМИ)Позиционные игры201215 / 17Смешанные и поведенческие стратегииСмешанная стратегия - выпуклая комбинаций чистых стратегийПоведенческая стратегия говорит, с какими вероятностями надо выбирать ходы вкаждом информационном множестве.И.В.Кацев (СПб ЭМИ)Позиционные игры201215 / 17Полная памятьНеформально, игрок i имеет в игре полную память, если при каждом его ходе онпомнит, через в каких информационные множества он уже побывал к этомумоменту, и какие ходы он там делал.
Фактически это определение означаетналичие полной информации игрока о самом себе.И.В.Кацев (СПб ЭМИ)Позиционные игры201216 / 17Полная памятьНеформально, игрок i имеет в игре полную память, если при каждом его ходе онпомнит, через в каких информационные множества он уже побывал к этомумоменту, и какие ходы он там делал. Фактически это определение означаетналичие полной информации игрока о самом себе..Теорема (Кун, 1953).Для того чтобы смешанная стратегия µi игрока i была эквивалентна егоµсоответствующей стратегии поведения βi необходимо и достаточно,.чтобы игрок i имел в игре полную память.И.В.Кацев (СПб ЭМИ)Позиционные игры201216 / 17Subgame perfect equilibriumНабор поведенческих стратегий называется совершенным подыгровымравновесием (СПРН), если для любой подыгры (под-игры?) данный наборстратегий является равновесием по Нэшу.И.В.Кацев (СПб ЭМИ)Позиционные игры201217 / 17Subgame perfect equilibriumНабор поведенческих стратегий называется совершенным подыгровымравновесием (СПРН), если для любой подыгры (под-игры?) данный наборстратегий является равновесием по Нэшу..Теорема.В.
любой позиционной игре с полной информацией существует СПРН.И.В.Кацев (СПб ЭМИ)Позиционные игры201217 / 17.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.