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

ПиСИ). Двухходовая игра. Подходы Штакельберга и Гермейера.
Общая модель динамической игры

с ПиСИ. Обратная индукция и рациональность игроков.
Модели, основанные на динамических играх с ПиСИ.

и совершенную информацию.
Информацию считают полной, если все игроки имеют общую

информацию о правилах игры и функциях выигрыша. Это понятие относится как к статическим так и динамическим играм.
Понятие совершенной информации относится только к динамическим играм, в которых игроки делают ходы последовательно в разные моменты времени

становятся известны всем игрокам, динамическая игра обладает совершенной информацией.

которой каждый игрок может сделать несколько ходов и по крайней

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

в развернутой форме должно включать :
множество вершин дерева игры, в

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

во времени следующим образом:
Ход 1. Игрок 1 выбирает некоторые действия

a1 A1
Ход 2. Игрок 2, зная совершенный игроком 1 выбор a1, выбирает некоторое действие a2 A2

функция выигрыша известны обоим игрокам. Поэтому игрок 1 может спрогнозировать

ответные действия игрока 2 с помощью множества наилучших ответов:


В случае однозначности наилучших ответов прогноз поведения игрока2 в ответ на любые действия игрока 1 является точным.

действие из условия максимизации выигрыша u1(a1,R2(a1)).
Обозначим через a1* оптимальные действия

игрока 1 с учетом прогноза ответных действий игрока 2 в случае однозначности наилучших ответов:
max [ u1(a1,R2(a1)) ] = u1(a1* ,R2(a1* ))

Обозначим через a2* = R2(a1*) оптимальный ответ игрока 2 на оптимальное действие игрока 1.

max [ u1(a1,a2) ] = max [u1(a1* , a2)]

a1 € A1 a2 € R2(a1) a2 € R2(a1* )


В экономических приложениях чаще используется подход Штакельберга, т.к. в случае безразличия лучше пойти навстречу партнеру. ( бесплатная услуга, может потом мне это как-то зачтется)

min [ u1(a1,a2) ] = min [u1(a1* ,

a2)]
a1 € A1 a2 € R2(a1) a2 € R2(a1* )
Гермейер исходил из общего принципа гарантированного результата. Если у нас есть информация о доброжелательности партнера в случае равного для него выигрыша, то можем пользоваться подходом Штакельберга. Но если такой информации нет, то только совет к максимальному гарантированному результату

всю игру с учетом всей поступающей информации.
Игрок 1 выбирает действие,

не имея никакой дополнительной информации. Поэтому его множество стратегий S1 =A1 совпадает с множеством действий.

уже совершенном действии игрока 1. Но стратегию он должен выбрать

до игры, поэтому его стратегия это отображение S2 : A1→A2 , которая каждому действию a1 игрока 1 ставит в соответствие некоторое действие s2(a1) A2
Положим u1(s1, s2)= u (s, s2 (s1 )).
Если у каждого игрока было по два возможных действия, то в двухходовой игре у игрока 1 будет две стратегии, а у игрока 2 станет четыре стратегии.

. Решение игры можно найти в предположении, что игроки рациональны

и что рациональность и структура игры являются общеизвестными фактами.
При этом естественно воспользоваться методом обратной индукции. В соответствии с этим методом игру разматывают с конца.

поскольку предпочитает выигрыш 1 выигрышу −1. Таким образом, исход игры

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

позиции имеет игрок i(m). В этой позиции все зависит от

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

(L2,R1).
Если выигрыши всех игроков во всех конечных вершинах различны, то

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

даёт хотя бы одно решение

совершенной информацией с помощью обратной индукции.
Другой подход состоит в

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

игру в нормальной форме. Как мы помним, описание игры в

нормальной форме состоит из:
задания множества игроков,
множества стратегий каждого игрока,
функции выигрыша каждого игрока на множестве исходов.

план действий игрока: что он будет делать в каждой из

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

можно условно представить следующим образом. Каждый игрок до начала игры

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

множество решений, получаемых обратной индукцией, совпадает с множеством СПРН (

совершенное по подыграм равновесие Нэша).