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

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

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

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

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

По очереди, начиная с ходаигрока 1, игроки ставят свои фишки в свободные кдетки. После того как вся досказаполнена, игрок 1 выигрывает число, равное значению игры получившейсяматрицы. Показать, что у игрока 1 есть стратегия, выбирая которую он никогда непроиграет (т.е. его выигрыш будет неотрицательный).И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20126 / 20Конечное число стратегийКонечное число стратегий ⇒ оптимальные стратегии всегда естьИ.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20127 / 20Конечное число стратегийКонечное число стратегий ⇒ оптимальные стратегии всегда естьА если у игроков бесконечное число стратегий?И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20127 / 20Конечное число стратегийКонечное число стратегий ⇒ оптимальные стратегии всегда естьА если у игроков бесконечное число стратегий?.Упражнение.Придуматьигру, где нет оптимальных (смешанных) стратегий.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20127 / 20ПримерРассмотрим следующую бесконечную антагонистическую игру со счетныммножеством стратегий X = Y = {1, 2, .

. . , m, . . .} у каждого из игроков. Через Xбудем обозначать множество стратегий игрока 1, а через Y− множествостратегий игрока 2. Стратегиями игроков являются целые положительные числа.Если игрок 1 выберет число, большее чем игрок 1, то он выигрывает 1, еслименьшее, то проигрывает 1. Если они выберут одинаковые числа, то ихвыигрыши равны 0. Функция выигрыша K(m, n) запишется следующим образом:1,K(m, n) = 0,−1,И.В.Кацев (СПб ЭМИ)> n,если m = n,если m < n.если mБесконечные антагонистические игры20128 / 20Бесконечные диагональные игрыРассмотрим игру с матрицей0 ...0 ... A =  0 a22...

... ... ...где aiia110> 0.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20129 / 20Бесконечные диагональные игрыРассмотрим игру с матрицей0 ...0 ... A =  0 a22... ... ... ...где aii.a110> 0.Утверждение.Если число стратегий конечно, то оптимальные стратегии таковы:x∗1aii= y∗ , xi = ∑ ∞1.j=1 ajj.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры20129 / 20Бесконечные диагональные игры.Утверждение.∑∞ 1В бесконечной диагональной игре, если рядj=1 ajj сходится, тооптимальные стратегии таковы:x∗1aii= y∗ , xi = ∑ ∞1.j=1 ajj.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201210 / 20Бесконечные диагональные игры.Утверждение.∑∞ 1В бесконечной диагональной игре, если рядj=1 ajj сходится, тооптимальные стратегии таковы:x∗1aii= y∗ , xi = ∑ ∞1.j=1 ajj.Что делать, если ряд расходится?И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201210 / 20ε−оптимальные стратегииРассмотрим бесконечную антагонистическую игру Γ = ⟨X, Y, K⟩, гдеK : X × Y → R− функция выигрыша игрока 1.

Предположим, что функциявыигрыша K ограничена. Тогда определены величины supx∈X K(x, y),infy∈Y K(x, y).Пусть ε произвольное положительное число. Пара стратегий (xε , yε ) называетсяε−седловой точкой функции K(x, y), если для всех x ∈ X, y ∈ Y выполняютсянеравенстваK(x, yε ) − ε ≤ K(xε , yε ) = vε ≤ K(xε , y) + ε.Если в игре Γ функция выигрыша обладает ε−седловыми точками для любогоε > 0, то составляющие ε−седловых точек называются ε−оптимальнымистратегиями игроков, а limε→0 vε = v – значением игры.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201211 / 20ε−оптимальные стратегии.Теорема.Выполнение равенстваsup inf K(x, y)x∈X y∈Y= inf sup K(x, y),y∈Y x∈Xэквивалентно существованию то в игре ⟨X, Y, K⟩ ε−оптимальных стратегийу.

обоих игроков для любого ε > 0.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201212 / 20Бесконечные антагонистические игры.Утверждение.∑∞ 1В бесконечной диагональной игре, если рядj=1 ajj расходится, то значениеигры равно нулю, любая стратегия игрока 1 оптимальна, а у игрока 2.имеются ε−оптимальные стратегии для любого ε > 0.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201213 / 20Бескоалиционные игрыКонечное множество игроков NИ.В.Кацев (СПб ЭМИ)= {1, 2, . .

. , n}.Бесконечные антагонистические игры201214 / 20Бескоалиционные игрыКонечное множество игроков N = {1, 2, . . . , n}.Бескоалиционной игрой (в нормальной форме) называется тройкаΓ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩,где Xi , i ∈ N− множество стратегий игрока i ∈ N, которое может быть∏произвольным множеством, Ki : i∈N Xi → R− функция игрока i ∈ N,сопоставляющая каждой ситуации x = (x1 , . . .

, xn ), т.е. набору стратегий,выбранных всеми игроками, некоторый его выигрыш Ki (x1 , . . . , xn ) = Ki (xi , xi ).И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201214 / 20Бескоалиционные игрыКонечное множество игроков N = {1, 2, . . . , n}.Бескоалиционной игрой (в нормальной форме) называется тройкаΓ = ⟨N, {Xi }i∈N , {Ki }i∈N ⟩,где Xi , i ∈ N− множество стратегий игрока i ∈ N, которое может быть∏произвольным множеством, Ki : i∈N Xi → R− функция игрока i ∈ N,сопоставляющая каждой ситуации x = (x1 , . . .

, xn ), т.е. набору стратегий,выбранных всеми игроками, некоторый его выигрыш Ki (x1 , . . . , xn ) = Ki (xi , xi ).Если в игре Γ все множества Xi , iИ.В.Кацев (СПб ЭМИ)∈ N конечны, то игра называется конечной.Бесконечные антагонистические игры201214 / 20Доминирование стратегийСтратегия xi игрока i∈ N (строго) доминирует стратегию yi , еслиKi (xi , xi )И.В.Кацев (СПб ЭМИ)≥ (>)Ki (yi , xi ) для всех xi ∈ Xi ,Бесконечные антагонистические игры201215 / 20Доминирование стратегийСтратегия xi игрока i∈ N (строго) доминирует стратегию yi , еслиKi (xi , xi )≥ (>)Ki (yi , xi ) для всех xi ∈ Xi ,Стратегия xi игрока i ∈ N называется доминирующей, если данные неравенствавыполняются для всех yi ∈ Xi , и для всех xi ∈ Xi .И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201215 / 20Доминирование стратегийСтратегия xi игрока i∈ N (строго) доминирует стратегию yi , еслиKi (xi , xi )≥ (>)Ki (yi , xi ) для всех xi ∈ Xi ,Стратегия xi игрока i ∈ N называется доминирующей, если данные неравенствавыполняются для всех yi ∈ Xi , и для всех xi ∈ Xi .Если у каждого игрока i ∈ N в игре Γ найдется доминирующая стратегия x∗i , тоситуация x∗ = (x∗1 , .

. . , x∗n ) называется равновесием в доминирующихстратегиях.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201215 / 20Пример(И.В.Кацев (СПб ЭМИ)1, 1 0, 11, 0 0, 0)Бесконечные антагонистические игры201216 / 20Оптимальность по ПаретоСитуация x = (x1 , . . . , xn ) в игре Γ называется оптимальной по Парето, если несуществует такой ситуации y = (y1 , .

. . , yn ), в которой Ki (y) ≥ Ki (x) для всехi ∈ N, и хоть для одного игрока это неравенство строго.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201217 / 20Оптимальность по ПаретоСитуация x = (x1 , . . . , xn ) в игре Γ называется оптимальной по Парето, если несуществует такой ситуации y = (y1 , . . . , yn ), в которой Ki (y) ≥ Ki (x) для всехi ∈ N, и хоть для одного игрока это неравенство строго..Утверждение.В конечной бескоалиционной игре существуют оптимальные по Паретоситуации..И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201217 / 20Равновесие по НэшуСитуация x∗ называется ситуацией равновесия по Нэшу, если для всех iвсех стратегий xi ∈ Xi выполняются неравенстваKi (x∗ )И.В.Кацев (СПб ЭМИ)∈Nи≥ Ki (xi , x∗i ).Бесконечные антагонистические игры201218 / 20Вогнутые игры.Теорема.Если в бескоалиционной игре двух лиц на единичном квадрате(X1 = X2 = [0, 1]), функции выигрыша игроков непрерывны и вогнуты(выпуклы вверх) по стратегии данного игрока (K1 вогнута по x1 , K2 вогнутапо.

x2 ), то в такой игре существует ситуация равновесия.И.В.Кацев (СПб ЭМИ)Бесконечные антагонистические игры201219 / 20.