Лекция 5 (Лекции (4))
Описание файла
Файл "Лекция 5" внутри архива находится в папке "Лекции (4)". PDF-файл из архива "Лекции (4)", который расположен в категории "". Всё это находится в предмете "теория игр и исследование операций" из 8 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория игр и исследование операций" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Домашнее задание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.