OpenMIT 14.126 Game Theory / 14.126 Теория Игр: LEC 1 Review of Basic Concepts: Normal form

Обзор основных понятий:
Нормальная форма игр
14.126 Теория Игр
Мухамет Уилдиз

nika_vero_nika 13.04.16 в 12:59

План лекции
1. Игры в нормальной форме
2. Доминирование и рационализуемость
3. Равновесие Нэша
- Существование и устойчивость
4. Байесовские Игры
- Представления игр в нормальной форме / нормальной форме с агентом
- Байесовское равновесие Нэша – эквивалент равновесия Нэша, существование и устойчивость

nika_vero_nika 13.04.16 в 12:59

Игры в нормальной форме
- Игра в нормальной форме состоит из трех элементов (N, S, u):
- N = {1, . . . , n} - множество игроков (конечное).
- S = S1 x ... x Sn, где Si это множество чистых стратегий каждого i-го игрока.
- u = (u1,.,un) множество функций платежей для каждого i-го игрока - где ui : S -> R - это функция полезности Неймана-Моргенштерна (vNM) (полезность - функция от стратегии игрока, ui - действительное число)
- Игра в нормальной форме конечна, если конечны множества S и N.
- Игра с полной информацией.

nika_vero_nika 14.04.16 в 08:28

Смешанные стратегии, ожидания
- d(X) (дельта(X)) = распределение вероятностей на X.
- d(Si) = смешанные стратегии i-го игрока.
Набор независимых стратегий:
q (сигма) = q1 x ...x qn принадлежит множеству d(S1) x ... x d(Sn)
Набор коррелирующих стратегий: Множество q принадлежащее множеству dS
- d(S-i) = возможное предположение игрока / (ожидание относительно того, какие стратегии у других игроков). [q-i принадлежит d(S-i)]/
- Игрок может думать, что у других игроков стратегии коррелируют!
- Ожидаемые выигрыши:
ui(q) = Eq(ui) = Сумма (по s принадлежащему S) q(s)*ui(S)

nika_vero_nika 14.04.16 в 08:35

Рациональность и Доминирование
- Игрок i рационален, если он максимизирует свой ожидаемый выигрыш в соответствии со своими ожиданиями.
- s* это наилучший ответ на ожидаемые независимые стратегии других игроков, тогда и только тогда, когда ...
- Bi(q-i) - наилучшие ответы на q-i
- qi строго доминирует над si тогда и только тогда, когда ...
- qi строго доминирует над si тогда и только тогда, когда ...
... причем хотя бы одно неравенство строгое
Теорема: В конечной игре, si* не является лучшим ответом ни при каких условиях на предполагаемую стратегию q-i (возможно коррелирующую), тогда и только тогда,когда si* строго доминируема (возможно смешанной стратегией).

nika_vero_nika 16.04.16 в 20:18

Доказательство теоремы:
(=>) Предположим, что
- ...
- ...
- ...
- Co(U) - выпуклая оболочка множества U= ...
Следствия: предположим, что ...
=> ...
=> ...
=> ...
Теорема о Разделяющей Гиперплоскости: Предположим, что C и D - не пустые, не пересекающиеся подмножества множества R^m, причем C замкнуто.
Следовательно, существует такое r, принадлежащее множеству R^m (за исключением 0), такое что при любом х, принадлежащем замыканию множества D, любом y, принадлежащем множеству C, r*x >= r*y.

(<=) Определим:
D = ...
- Предположим, что si* не является строго доминируемой.
- Co(U) и D не пересекаются
По Теореме о Разделяющей Гиперплоскости: ..., где ...

nika_vero_nika 17.04.16 в 15:52

Последовательное строгое доминирование и Рационализуемость

S0=S
Коррелирующие (Рационализуемые) стратегии

Независимая рационализуемость: ... тогда и только тогда, когда ... , где
... рационализована, тогда и только тогда, когда

Теорема (определение неподвижной точки): ... является наибольшим множеством, состоящим из Z1x...xZn, таких, что ... для любого i. (si рационализуема тогда и только тогда, когда si принадлежит Zi для таких Z1x...xZn)

nika_vero_nika 17.04.16 в 18:02

Основы рационализуемости
- Если игра с полной информацией и каждый игрок знает, что остальные игроки рациональны, то все игроки выбирают рационализируемые стратегии.
- Каждый рационализированный набор стратегий это результат ситуации, в которой и игра и рациональность обладают свойством полноты информации.
- В любой модели с "адаптивным" обучением, доля игроков, которые выбирают нерационализированные стратегии стремится к нулю по мере развития системы.

nika_vero_nika 18.04.16 в 18:15

Рационализуемость в Дуополии Курно
Одновременно, каждая фирама i, принадлежащая {1,2} производит qi единиц продукции с предельными издержками c, и продает по цене P = max{0,1-q1-q2}

nika_vero_nika 18.04.16 в 18:21

Рационализуемость в Дуополии Курно
- Если игрок i знает, что qj <= q, то qi > (1-c-q)/2.
- Если игрок i знает, что qj >= q, then qi < (1-c-q)/2.
- Нам известно, что qj > q0 = 0.
- Следовательно, qi < q1 = (1-c-q0)/2 = (1-c)/2 для каждого i;
- Следовательно, qi > q2 = (1-c-q1)/2 = (1-c)(1-1/2)/2 для каждого i;
- и так далее.
- Следовательно, qn < qi < q_(n+1) или q_(n+1) < qi < qn , где
q_(n+1) = (1-c-qn)/2 = (1-c)(1-1/2+1/4-...+(-1/2)^n)/2.
- Так как n стремится к бесконечности, то qn стремится к (1-c)/3. 

nika_vero_nika 20.04.16 в 07:52

Равновесие Нэша
- Следующие условия эквивалентны:
- ... равновесие Нэша
- где Bi - множество смешанных наилучших ответов
- ...
- ... При любом i, замыкание множества (носитель) равновесия Нэша, где значения стратегий ненулевые, содержится внутри или совпадает с множеством смешанных наилучших ответов.

nika_vero_nika 21.04.16 в 08:05

Существование и устойчивость

- Для любой функции F, заданной на множестве X и принимающей значения, из множества 2^Y, где X компактно, а Y ограниченно, F полунепрерывна сверху тогда и только тогда, когда F имеет замкнутый график
...
- Теорема Бержа о максимуме (существование и устойчивость оптимальной точки, в которой находится индивид): Предположим, что двухмерная функция f, заданная на множестве XxZ, принимающая значения из множества Y, непрерывна, и множества X, Y, Z - компактны. Пусть:
аргмаксимум - это подмножество Z, при котором достигается максимум f(x,z). То есть F это отображение из X в Z, которое для любого x из Х даёт соответствующее подмножество Z.
F(x) - состоит из максимальных значений функции f, при каждом X на множестве XxZ.
(f это двумерная функция. Если зафиксировать х на каком-нибудь значении - например х0, - то f(x0,z) будет одним из сечений старой функции, уже одномерной функцией. И она на каких-то z достигает максимума, F(x0) эти самые z и выдаёт.)
Следовательно, F не пуста, компактна и полунепрерывна сверху.
- Теорема Какутани о неподвижной точке: Пусть Х - выпуклое, компактное подмножество множества R^m и пусть функция F такова, что множество F(х) непусто, выпукло и имеет замкнутый график. Следовательно, существуют такие x, принадлежащие Х, что х принадлежит F(x), т.е. F(x) имеет неподвижную точку.

nika_vero_nika 23.04.16 в 02:33

Существование равновесия Нэша.
Теорема: Пусть каждое Si - выпуклое, компактное подмножество Евклидова пространства и каждое ui непрерыывна на s и квазивогнута на si. Следовательно, существует равновесие Нэша при s, принадлежащем S.
Следствие: В каждой конечной игре есть равновесие Нэша (возможно смешанное).
Доказательство следствия: Каждая смешанная стратегия Si выпукла и компактна. Каждое ui(сигма) - непрерывно и линейно на сигмаi. Следовательно, в игре с пространством смешанных стратегий Si существует равновесие Нэша сигма*, принадлежащее множеству смешанных стратегий дельта(S1) x ... x дельта(Sn).

nika_vero_nika 24.04.16 в 11:38

Доказательство теоремы о существовании.
- Пусть функция F, определенная на множестве S и принимающая значения, равные 2^s - это функция "лучшего ответа" Fi(s)=Bi(s-i)
- По теореме о Максимуме, F непуста и имеет замкнутый график/
- При условии квазивогнутости, F - выпукла.
- По теореме Каткутани о неподвижной точке, F имеет неподвижную точку s*, принадлежащую F(s*).
- s* - равновесие Нэша.

nika_vero_nika 25.04.16 в 06:30

Полунепрерывность сверху для равновесия Нэша (NE).
- X, S компактные метрические пространства.
- u^x(s) непрерывно на x принадлежащем X and s принадлежащем S.
- PNE(x) - Равновесие Нэша в чистых стратегиях при (N,S,u^x).
Теорема: NE и PNE полунепрерывны сверху.
Следствие: Если S конечно, то NE непусто, компактно и полунепрерывно сверху.
Доказательство:
- Смешанная стратегия Si компактна u^x(сигма) непрерывна на (x,сигма).
- Предположим, что .... для больших m.

nika_vero_nika 25.04.16 в 07:11

Байесовские игры

- Байесовская игра это список (N, A, Тета, T, u, p)
- N = {1, . . . , n} это (конечный) набор игроков;
- A = A1 x ... x An; Аi это набор действий i-го игрока;
- Тета - это набор параметров, соответствующих выигрышам (набор состояний Природы, Природа определяет тип игрока в соответствии с вероятностями);
- T= T1 x ... x Tn; Ti это набор типов i-го игрока;
- u = (u1,.,un); ui: Тета х A -> R это функция полезности vNM фон i-го игрока;
- p принадлежит множеству дельта(Тета xТ) - распределение вероятности по набору состояний Природы - в данном случае вероятности того, что игрок принадлежит к тому или иному типу известны до начала игры всем игрокам.
• Байесовская игра это список (N, A, Тета, T, u, p) как выше, за исключением
ui: Тета х T x A -> R
• Байесовская игра это список (N, A, T, u, p) как выше, за исключением ui:T x A -> R.
Факт: Все три формулировки эквивалентны (до тех пор, пока вы знаете, что делаете).
Факт: Мы можем заменить p на p1,.,pn, отбросив CPA - cost per action.

nika_vero_nika 26.04.16 в 06:56

Представление игры в нормальной форме

- Дана Байесовская игра Г=(N,A,Тета,T,u,p)
- Нормальная форма: G(Г)=(N,S,U):
- Si = {функции si: Ti -> Ai }
- Ui(s)= .... Ожидаемый выигрыш игрока в зависимости от действий других игроков и Природы.
- Нормальная форма с агентом: AG(Г)= (_N_,S,U):
...

Оценка игроком ожидаемого выигрыша в зависимости от собственного типа (условная вероятность).

nika_vero_nika 27.04.16 в 07:11

Равновесие Байеса-Нэша (BNE)
Определение: ... это равновесие Баеса-Нэша, тогда и толко тогда, когда для каждого i, ti,
...
Факт: ... является равновесием Байеса-Нэша в Г, тогда и только тогда, когда профиль смешанных стратегий ... является равновесием Нэша в AG(Г).
Факт: Если ... это равновесие Байеса-Нэша в Г, то оно также евляется равновесием Нэша в G(Г). Если вероятность появления каждого типа агента больше 0, то обратное также верно.

nika_vero_nika 02.05.16 в 03:43

Существование BNE

Рассмотрим игру с конечным количеством игроков и типов.
Теорема: Если
- Каждое множество действий игрока i компактно и выпукло.
- Каждый выигрыш игрока i ограничен, непрерывен и вогнут на множестве a.

то в игре Г существует равновесие Байеса-Нэша в чистых стратегиях.
Доказательство: в AG(Г) есть равновесие Нэша в чистых стратегиях.
Следствие: Если множество действий всех игроков конечно, то в игре Г существует равновесие Байеса-Нэша (возможно в смешанных стратегиях).

nika_vero_nika 03.05.16 в 07:58

Полунепрерывность сверху для BNE.
- A, T конечны, а Тета, X компактны.
- ... непрерывны на (...)
- BNE(x) - это BNE в игре
- BNE(p) - это BNE в игре
Теорема: BNE полунепрерывно сверху.
Доказательство: BNE(x)=NE(AG(Г^x))
Теорема: Предположим, что ... для компактного P. BNE(p) полунепрерывно сверху на P.
Доказательство: ... непрерывно. ...

nika_vero_nika 03.05.16 в 07:58