Презентация на тему: Лекция 5 Динамические игры с полной информацией

Реклама. Продолжение ниже
Лекция 5 Динамические игры с полной информацией
Полная и совершенная информация ( ПиСИ ).
Полная и совершенная информация ( ПиСИ ).
Динамические игры с полной информацией
Динамические игры с полной информацией
Двухходовая игра
Двухходовая игра
Двухходовая игра
Подход Штакельберга
Подход Гермейера.
Двухходовая игра
Двухходовая игра
Двухходовая игра
Игра «Террорист»
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Обратная индукция
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Концепция равновесия Нэша
Концепция равновесия Нэша
Концепция равновесия Нэша
Концепция равновесия Нэша
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
Лекция 5 Динамические игры с полной информацией
1/35
Средняя оценка: 5.0/5 (всего оценок: 27)
Код скопирован в буфер обмена
Скачать (722 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Лекция 5 Динамические игры с полной информацией

1 Лекция 5 Динамические игры с полной информацией Полная и совершенная информация ( ПиСИ ). Двухходовая игра. Подходы Штакельберга и Гермейера. Общая модель динамической игры с ПиСИ. Обратная индукция и рациональность игроков. Модели, основанные на динамических играх с ПиСИ.

Изображение слайда
1/1
2

Слайд 2: Полная и совершенная информация ( ПиСИ )

2 Полная и совершенная информация ( ПиСИ ). В динамических играх различают полную и совершенную информацию. Информацию считают полной, если все игроки имеют общую информацию о правилах игры и функциях выигрыша. Это понятие относится как к статическим так и динамическим играм. Понятие совершенной информации относится только к динамическим играм, в которых игроки делают ходы последовательно в разные моменты времени

Изображение слайда
1/1
3

Слайд 3: Полная и совершенная информация ( ПиСИ )

3 Полная и совершенная информация ( ПиСИ ). Если все сделанные ходы сразу становятся известны всем игрокам, динамическая игра обладает совершенной информацией.

Изображение слайда
1/1
4

Слайд 4: Динамические игры с полной информацией

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

Изображение слайда
1/1
5

Слайд 5: Динамические игры с полной информацией

Описание динамической игры (с совершенной информацией) в развернутой форме должно включать : множество вершин дерева игры, в том числе одну начальную вершину; для каждой вершины, кроме начальной,— единственную вершину, которая непосредственно ей предшествует; при этом цепь предшествующих вершин, построенная из любой вершины, должна заканчиваться в начальной вершине (что предполагает, в том числе, отсутствие циклов); множество игроков ; для каждой вершины, кроме конечных,— единственного игрока, которому принадлежит ход в данной вершине; для каждой конечной вершины, т. е. такой, которая не предшествует ни одной другой вершине,— вектор выигрышей всех игроков. 5

Изображение слайда
1/1
6

Слайд 6: Двухходовая игра

6 Двухходовая игра Пусть есть всего два игрока N= {1,2 }, и игра разворачивается во времени следующим образом: Ход 1. Игрок 1 выбирает некоторые действия a 1 A 1 Ход 2. Игрок 2, зная совершенный игроком 1 выбор a 1, выбирает некоторое действие a 2 A 2

Изображение слайда
1/1
7

Слайд 7: Двухходовая игра

7 Двухходовая игра Предполагаем, что информация является полной, т.е. правила игры и функция выигрыша известны обоим игрокам. Поэтому игрок 1 может спрогнозировать ответные действия игрока 2 с помощью множества наилучших ответов : В случае однозначности наилучших ответов прогноз поведения игрока2 в ответ на любые действия игрока 1 является точным.

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Двухходовая игра

8 Двухходовая игра С учетом этого прогноза игроку 1 следует выбирать свое действие из условия максимизации выигрыша u 1 (a 1,R 2 (a 1 )). Обозначим через a 1 * оптимальные действия игрока 1 с учетом прогноза ответных действий игрока 2 в случае однозначности наилучших ответов: max [ u 1 (a 1,R 2 (a 1 )) ] = u 1 (a 1 *,R 2 (a 1 * )) Обозначим через a 2 * = R 2 (a 1 * ) оптимальный ответ игрока 2 на оптимальное действие игрока 1.

Изображение слайда
1/1
9

Слайд 9: Подход Штакельберга

9 Подход Штакельберга Подход Штакельберга – доброжелательность партнера : max max [ u 1 (a 1,a 2 ) ] = max [ u 1 (a 1 *, a 2 ) ] a 1 € A 1 a 2 € R 2 (a 1 ) a 2 € R 2 (a 1 * ) В экономических приложениях чаще используется подход Штакельберга, т.к. в случае безразличия лучше пойти навстречу партнеру. ( бесплатная услуга, может потом мне это как-то зачтется )

Изображение слайда
1/1
10

Слайд 10: Подход Гермейера

10 Подход Гермейера. Подход Гермейера - гарантированный результат или осторожность: max min [ u 1 (a 1,a 2 ) ] = min [ u 1 (a 1 *, a 2 ) ] a 1 € A 1 a 2 € R 2 (a 1 ) a 2 € R 2 (a 1 * ) Гермейер исходил из общего принципа гарантированного результата. Если у нас есть информация о доброжелательности партнера в случае равного для него выигрыша, то можем пользоваться подходом Штакельберга. Но если такой информации нет, то только совет к максимальному гарантированному результату

Изображение слайда
1/1
11

Слайд 11: Двухходовая игра

11 Двухходовая игра Стратегия в теории игр – это план действий на всю игру с учетом всей поступающей информации. Игрок 1 выбирает действие, не имея никакой дополнительной информации. Поэтому его множество стратегий S 1 =A 1 совпадает с множеством действий.

Изображение слайда
1/1
12

Слайд 12: Двухходовая игра

12 Двухходовая игра Игрок 2 перед выбором своего действия получает информацию о уже совершенном действии игрока 1. Но стратегию он должен выбрать до игры, поэтому его стратегия это отображение S 2 : A 1 →A 2, которая каждому действию a 1 игрока 1 ставит в соответствие некоторое действие s 2 (a 1 ) A 2 Положим u 1 (s 1, s 2 )= u (s, s 2 (s 1 )). Если у каждого игрока было по два возможных действия, то в двухходовой игре у игрока 1 будет две стратегии, а у игрока 2 станет четыре стратегии.

Изображение слайда
1/1
13

Слайд 13: Двухходовая игра

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

Изображение слайда
1/1
14

Слайд 14: Игра «Террорист»

14 Игра «Террорист»

Изображение слайда
Изображение для работы со слайдом
1/2
Реклама. Продолжение ниже
15

Слайд 15

15

Изображение слайда
Изображение для работы со слайдом
1/2
16

Слайд 16

В этой игре действия пилота несложно предсказать—он полетит в Нью-Йорк, поскольку предпочитает выигрыш 1 выигрышу −1. Таким образом, исход игры однозначен: пилот посадит самолет в Нью-Йорке, а террорист не станет взрывать бомбу. Изобразим полученное решение на дереве. Те действия, которые были игроком в каждой из вершин, изобразим жирными пунктирными линиями. Исход игры определяется траекторией, состоящей из выбранных действий, и идущей из начальной вершины в одну из конечных вершин 16

Изображение слайда
1/1
17

Слайд 17

17

Изображение слайда
Изображение для работы со слайдом
1/2
18

Слайд 18: Обратная индукция

Рассмотрим предфинальную позицию m. Пусть право хода в этой позиции имеет игрок i(m). В этой позиции все зависит от только от игрока i, и он может выбрать наилучшую для себя следующую вершину m : из всего множества. Сократим дерево игры, объявив позицию m финальной, приписав ей выигрыши u(m : ). Такой процесс сокращения дерева игры можно проводить до начальной позиции. В этом и заключается суть метода обратной индукции. 18

Изображение слайда
1/1
19

Слайд 19

19

Изображение слайда
Изображение для работы со слайдом
1/2
20

Слайд 20

20 Игра «Рэкет»

Изображение слайда
Изображение для работы со слайдом
1/2
21

Слайд 21

21

Изображение слайда
1/1
22

Слайд 22

22

Изображение слайда
Изображение для работы со слайдом
1/2
23

Слайд 23

23

Изображение слайда
Изображение для работы со слайдом
1/2
24

Слайд 24

В этой игре обратная индукция дает два решения : (L1,R2) и (L2,R1). Если выигрыши всех игроков во всех конечных вершинах различны, то неоднозначность при использовании обратной индукции не возникает, поэтому решение должно быть единственным. В конечной игре с совершенной информацией алгоритм обратной индукции дает хотя бы одно решение. 24

Изображение слайда
1/1
25

Слайд 25

25 Теорема. В конечной игре с совершенной информацией алгоритм обратной индукции даёт хотя бы одно решение

Изображение слайда
Изображение для работы со слайдом
1/2
26

Слайд 26: Концепция равновесия Нэша

Мы рассмотрели, как находить решение динамической игры с совершенной информацией с помощью обратной индукции. Другой подход состоит в том, чтобы применить к динамической игре концепцию равновесия Нэша, так же как мы применяли ее к статическим играм. 26

Изображение слайда
1/1
27

Слайд 27: Концепция равновесия Нэша

Для того чтобы это сделать, следует записать динамическую игру в нормальной форме. Как мы помним, описание игры в нормальной форме состоит из: задания множества игроков, множества стратегий каждого игрока, функции выигрыша каждого игрока на множестве исходов. 27

Изображение слайда
1/1
28

Слайд 28: Концепция равновесия Нэша

В игре в развернутой форме (чистая) стратегия —это полный план действий игрока: что он будет делать в каждой из вершин, в которой ход принадлежит ему. Это должен быть действительно полный план, т. е. в нем должно быть определено, что игрок выберет в любой своей вершине, даже если из каких-либо соображений ясно, что процесс игры вряд ли может привести в эту вершину. 28

Изображение слайда
1/1
29

Слайд 29: Концепция равновесия Нэша

Процесс игры для динамической игры в нормальной форме можно условно представить следующим образом. Каждый игрок до начала игры сообщает выбранную им стратегию организатору игры. Организатор, руководствуясь этими стратегиями, осуществляет за игроков их ходы. Когда последовательность ходов приведет организатора в конечную вершину, он раздает всем игрокам выигрыши, соответствующие этой конечной вершине. При такой интерпретации мы, по сути, имеем статическую игру в которой выигрыши определяются с помощью только что описанного алгоритма. 29

Изображение слайда
1/1
30

Слайд 30

30

Изображение слайда
Изображение для работы со слайдом
1/2
31

Слайд 31

31

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
32

Слайд 32

32

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
33

Слайд 33

33

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
1/3
34

Слайд 34

34 Игрок 2 3 IBM 3 Mac Игрок 1 0 0 b+c c

Изображение слайда
Изображение для работы со слайдом
1/2
35

Последний слайд презентации: Лекция 5 Динамические игры с полной информацией

35 Теорема. В игре с совершенной информацией и конечным числом ходов множество решений, получаемых обратной индукцией, совпадает с множеством СПРН ( совершенное по подыграм равновесие Нэша).

Изображение слайда
1/1
Реклама. Продолжение ниже