Лекция 4 (545621)

Файл №545621 Лекция 4 (Лекции (4))Лекция 4 (545621)2015-08-22СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Домашнее задание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.

Характеристики

Тип файла
PDF-файл
Размер
90,57 Kb
Материал
Тип материала
Высшее учебное заведение

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6486
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее