Лекция 4 (Лекции (4))

Домашнее задание2. Оптимальные стратегии (x∗ , y∗ ) называются вполне смешанными, еслиx∗i > 0, y∗j > 0 для всех i, j. Игра, у которой любые оптимальные стратегииигроков вполне смешанные, называется вполне смешанной. Докажите, что еслиматричная игра вполне смешанная, то количества чистых стратегий у игроковсовпадают, а оптимальные стратегии игроков x∗ , y∗ единственные.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20121 / 17Домашнее задание3. Квадратная матрица a = ∥aij ∥ называется кососимметрической, еслиaij = −aji для всех i, j.

Матричная игра называется симметричной, если еематрица кососимметрична. Докажите, чтоа. выигрыши игроков при использовании оптимальных стратегий равны нулю.б. множества оптимальных стратегий игроков в симметричной игре совпадают.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20122 / 17Домашнее задание4. Игрок 2 прячет предмет в один из n ящиков. Первый игрок пытается найти его,открывая последовательно 2 ящика.

Если он обнаружит предмет в ящикеk = 1, ..., n , то его выигрыш равен δk > 0, , в противном случае его выигрышравен нулю. Найти значение игры и оптимальные стратегии игроков.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20123 / 17Домашнее задание5. Петя и Вася хотят назначить Ане свидание. Никто из молодых людей не знаетточно, когда она будет дома. Известно, что она с равной вероятностью можетвозвратиться домой в 3, 4 и 5 часов. Каждый может позвонить в один из этихчасов.

Дозвонившийся первым назначает свидание. Если оба позвонятодновременно, Аня отдаст предпочтение Пете. Выигрыш каждого из игроков —Пети и Васи — равен 1, если ему удастся назначить свидание, 0, если свиданиене состоится и -1, если Аня идет на свидание с другим.Составить матрицу выигрышей и найти оптимальные стратегии Пети и Васи, т.е.вероятности звонков в 3,4 и 5 часов соответственно.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20124 / 17Домашнее задание7. Имеется доска размером 3х3.

На неглавной диагонали стоят числаa13 = a22 = a31 = 0. Остальные клетки свободны. У игрока 1 имеются фишки счислами 1,2,3. У игрока 2 – фишки с числами -1,-2,-3. По очереди, начиная с ходаигрока 1, игроки ставят свои фишки в свободные кдетки. После того как вся досказаполнена, игрок 1 выигрывает число, равное значению игры получившейсяматрицы. Показать, что у игрока 1 есть стратегия, выбирая которую он никогда непроиграет (т.е. его выигрыш будет неотрицательный).И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20125 / 17Домашнее задание8. Рассматриваем бесконечную диагональную игру.

Докажите, что если ряд∑∞ 1j=1 ajj расходится, то значение игры равно нулю, любая стратегия игрока 1оптимальна, а у игрока 2 имеются ε−оптимальные стратегии для любого ε >И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20120.6 / 17Домашнее задание9. Имеется два игрока, которым нужно разделить 100 долларов. Игрок 1предлагает сумму x ∈ [0, 100] игроку 2. Если игрок 2 соглашается, то онполучает x, а игрок 1 получает 1 − x. Если он не соглашается, то оба получаютпо 0.

Найдите все равновесия по Нэшу в этой игре.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20127 / 17Домашнее задание10. Рассматриваем игру с постройкой магазинов, которая описывалась назанятии: жители города равномерно распределены по отрезку [A, B]. n игроковвыбирают места для постройки своих магазинов. Выигрыш игрока равен меремножества людей, для которых его магазин является ближайшим (люди, длякоторых несколько магазинов являются ближайшими, ”делятся” поровну междуэтими магазинами).а) Пусть n = 4.

Найдите все равновесия по Нэшу.б) Пусть n = 5. Найдите все равновесия по Нэшу.в) Найдите все значения n, для которых в игре нет равновесия по Нэшу.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20128 / 17Домашнее задание11. Рассмотрим игру из предыдущей задачи в пространстве большейразмерности.а) Существует ли такое множество ненулевой меры (вместо отрезка [A, B]),чтобы для n = 3 было равновесие по Нэшу?б) Существует ли такое выпуклое множество?И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20129 / 17Домашнее задание12. Рассматриваем аукцион первой цены, на котором разыгрываются двеединицы товара. То есть сначала человек, назначивший макисмальную цену,покупает товар по этой цене, затем тот, кто назначил вторую по величине цену,покупает второй экземпляр товара по этой цене.

Найдите хотя бы одноравновесие по Нэшу в данной игре.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201210 / 17Равновесие по НэшуРассмотрим положение xИ.В.Кацев (СПб ЭМИ)= (x1 , x2 , ..., xn ).Бесконечные антагонистические игры201211 / 17Равновесие по НэшуРассмотрим положение x= (x1 , x2 , ..., xn ).i-тый игрок хочет перейти в положение (x1 , ..., xi−1 , BRi (x), xi+1 , ..., xn )И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201211 / 17Равновесие по НэшуРассмотрим положение x= (x1 , x2 , ..., xn ).i-тый игрок хочет перейти в положение (x1 , ..., xi−1 , BRi (x), xi+1 , ..., xn )Равновесие по Нэшу - неподвижная точка отображенияx= (x1 , x2 , ..., xn ) → (BR1 (x), BR2 (x), ..., BRn (x)).И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201211 / 17Теоремы о неподвижных точках.Теорема (Брауэр).Любое непрерывное отображение замкнутого шара в себя в конечномерномевклидовомпространстве имеет неподвижную точку..И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201212 / 17Теоремы о неподвижных точкахМногозначная функция из X в Y сопоставляет каждой точке X некотороеподмножество Y.

Многозначная функция φ называется замкнутой, еслимножество {(x, y) : y ∈ φ(x)} замкнуто.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201213 / 17Теоремы о неподвижных точкахМногозначная функция из X в Y сопоставляет каждой точке X некотороеподмножество Y. Многозначная функция φ называется замкнутой, еслимножество {(x, y) : y ∈ φ(x)} замкнуто..Теорема (Какутани).Пусть S - непустое компактное выпуклое множество в Rn .

Если многозначнаяфункция φ : S → S является замкнутой и φ(x) - выпукло для любого x ∈ S, то.φ имеет неподвижную точку.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201213 / 17Теорема Нэша.Теорема (Нэш, 1950).Предположим, что в игре ⟨N, {Xi }i∈N , {Ki }i∈N ⟩ все множества Xi - выпуклыекомпакты, а функции выигрыша Ki - непрерывны и вогнуты по своей.переменной (то есть Ki вогнута по xi ). Тогда существует равновесие по Нэшу.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201214 / 17Смешанное расширение игрыПусть есть игра Γ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩.

Ее смешанным расширениемназывается игра Γ′ = ⟨N, {X′i }i∈N , {K′i }i∈N ⟩, гдеX′i - выпуклая оболочка XiK′i - линейна и совпадает с Ki на X1И.В.Кацев (СПб ЭМИ)× X2 × ... × XnБесконечные антагонистические игры201215 / 17Смешанное расширение игрыПусть есть игра Γ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩. Ее смешанным расширениемназывается игра Γ′ = ⟨N, {X′i }i∈N , {K′i }i∈N ⟩, гдеX′i - выпуклая оболочка XiK′i - линейна и совпадает с Ki на X1× X2 × ... × Xn.Теорема.Пусть Γ - конечная игра. Тогда в ее смешанном расширении Γ′ существуетравновесиепо Нэшу..И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201215 / 17.