Лекция 3 (545618)
Текст из файла
Домашнее задание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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
