Теория игр (8 семестр)

# Теория игр (8 семестр)  <a class="btn btn-primary hidden-print" role="button" href="#Вопросы"></a> <a class="btn btn-primary" href="#FAQ" role="button"> FAQ</a> <a class="btn btn-danger" href="https://github.com/egormkn/ifmo-kt/releases/download/8.games/conspect.pdf" role="button"> Скачать PDF</a> <a class="btn btn-info" href="https://hackmd.io/s/ryUHFWfY4" role="button"> Открыть на HackMD</a> <a class="btn btn-danger" href="https://t.me/year2015" role="button"> year2015</a> <style> #doc.markdown-body, .ui-infobar {max-width: 900px;} #doc.markdown-body ul, #doc.markdown-body ol {padding-left: 10px !important;margin-left: 10px !important;} </style> [TOC] ## Ссылки [Теория игр]: http://vkist.ru/9888/9888.pdf - [Справка по $\LaTeX$](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) + [Short Math Guide v2.0](http://ctan.altspu.ru/info/short-math-guide/short-math-guide.pdf) - [Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В. — Теория игр][Теория игр] - [Теормин year2014](https://docs.google.com/document/d/1jkPGlw9e0zgXs81YTqjjUjzz02yyTMHUKZEIJYzPi7c/edit) + [FAQ year2014](https://docs.google.com/spreadsheets/d/1AEz9N07lHiF8JCEiM2DFvQJI3JhcZrnpIFJ13IWr0yg/edit#gid=0) (всё перенесено на hackmd) - [Курс Йельского университета](https://oyc.yale.edu/economics/econ-159) ## Вопросы > ✅ — готов > 🔄 — не совсем готов > 🔴 — совсем не готов :::info В книге [Теория игр] есть билеты 1,2,4,5,6,7,8,9 ::: ### ✅ 1. Предмет теории игр. Классификации и формы задания игр. Примеры. > Привести этот билет в порядок на основе того, что давали на парах + сихнронизироваться с обозначениями из билетов ниже **Игра** — это процесс, описывающий некоторую конфликтную ситуацию двух и более сторон. Мы будем называть их **игроками**. У каждого игрока есть некоторые ходы, действия в игре и их мы назовем **стратегиями**. Каждая стратегия может принести нам некоторый выигрыш или, наоборот, проигрыш. Важно отметить, что, как это часто бывает и в жизни, проигрыш одной стороны — это выигрыш для другой. Численное значение проигрыша или выигрыша (иначе это можно назвать *полезностью*) от той или иной стратегии мы назовем **ценой стратегии**, а функцию, которая ставит стратегии ту или иную полезность (цену) мы назовем **функцией полезности**. Функция, как известно из курса матанализа, может быть задана в различных формах, в том числе матричной. Собственно говоря, функция полезности часто и задается как таблица, где различным стратегиям приписывается различная полезность. #### Классификация игр: - По неопределённости: - Детерминированные — условия, в которых принимаются решения, известны полностью - Стохастические — известно множество возможных вариантов условий и их вероятностное распределение - Неопределённые — известно множество возможных вариантов, но без какой-либо информации об их вероятностях - По описанию - Нормальная форма (матрица платежей) - Экстенсивная форма (дерево игры) — более наглядное представление - По кооперации - Безкоалиционные — каждая коалиция состоит из одного игрока - Кооперативные — временные объединения игроков с последующим разделением выигрыша или принятия решений - Коалиционные — игроки объединены в фиксированные коалиции - По характеру получения информации - игры в нормальной форме — игроки получают всю информацию до начала игры - динамические игры — информация поступает игрокам в процессе развития игры - По выигрышу (обычно выигрыш — число, потому что иначе сложно) - С нулевой суммой (антагонистические) - С ненулевой суммой - По числу стратегий - Конечные - Бесконечные **Коалиция** — множество игроков, действующих совместно **Типы стратегий**: - **Чистая стратегия** — даёт полную определённость, каким образом игрок продолжит игру. В частности, она определяет результат для каждого возможного выбора, который игроку может придётся сделать. Пространством стратегий называют множество всех чистых стратегий, доступных данному игроку. - **Смешанная стратегия** — является указанием вероятности каждой чистой стратегии. Это означает, что игрок выбирает одну из чистых стратегий в соответствии с вероятностями, заданными смешанной стратегией. Выбор осуществляется перед началом каждой игры и не меняется до её конца. Каждая чистая стратегия является частным случаем смешанной, когда вероятность одной из чистых стратегий равна единице, а остальных возможных чистых стратегий — нулю. Игра может быть представлена в виде **дерева игры** и в виде **матрицы платежей**. Представление игры в виде дерева является универсальным, т.е. любая игра может быть представлена в виде дерева, матричное представление не является универсальным – не любая игра может быть приведена к матричной форме. **Игра в нормальной форме** — состоит из трех элементов: множества игроков, множества множеств чистых стратегий каждого игрока, множества платежных функций каждого игрока. $G = \langle N, X, U \rangle$: - $N=\{1,2,\ldots,n\}$ — множество игроков - $X=\{X_1,X_2,\ldots,X_n\}$ — множество множеств чистых стратегий каждого игрока - $U=\{U_1,U_2,\ldots,U_n\}$ — множество функций платежей для каждого игрока У каждого игрока $i\in N$ имеется конечный набор чистых стратегий $X_i=\{1,2,\ldots,m_i\}$ и функция полезности (функция платежа) $U_i : X_1 \times X_2 \times \ldots \times X_n \rightarrow \mathbb{R}$. Исход игры — это комбинация чистых стратегий каждого игрока: $\vec{x}=(x_1, x_2,\ldots, x_n), \quad x_1 \in X_1, x_2 \in X_2, \ldots, x_n \in X_n$ Игру в нормальной форме можно представить в виде n-мерной матрицы (таблицы), элементы которой это n-мерные платежные вектора. Эта таблица называется **платёжной матрицей**. Игры в **экстенсивной**, или **развернутой форме**, представляются в виде ориентированного дерева, где каждая вершина определяет выбор соответствующего игрока. От каждой вершины отходят ветви, обозначающие стратегии данного игрока. Платежи игроков записываются внизу дерева и принадлежат игрокам по порядку. Пример: ![](https://i.imgur.com/wlI65Wb.png) **Антагонистическая игра** или **игра с нулевой суммой** (zero-sum game) — некооперативная игра, особая разновидность игр с постоянной суммой, то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. **Матричная игра** — игра с нулевой суммой игроков, имеющих конечное число стратегий. Выигрыш определяется матрицей игры (матрицей платежей), она же является нормальной формой игры. [Wiki: Нормальная форма игры](https://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%B8%D0%B3%D1%80%D1%8B) [Wiki: Развёрнутая форма игры](https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B2%D1%91%D1%80%D0%BD%D1%83%D1%82%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%B8%D0%B3%D1%80%D1%8B) ### ✅ 2. Антагонистические игры (определение, примеры, максиминные и минимаксные стратегии, ситуации равновесия и их свойства) > Нужно указание на доказательства из учебника (просто номер страницы), а так же убрать/добавить теоремы, которые у нас не были/были на парах + больше примеров **Антагонистическая игра** или **игра с нулевой суммой** — некооперативная игра, в которой участвуют два игрока, чьи выигрыши противоположны. **Антагонистическая игра в нормальной форме** — система $$\Gamma = \langle X, Y, K \rangle$$ где $X$ и $Y$ — непустые множества, и функция $K: X \times Y \to \mathbb{R}$. Элементы $x \in X, \, y \in Y$ называются **стратегиями** игроков $1$ и $2$ соответственно в игре $\Gamma$, пары стратегий $(x, y)$ из декартова произведения $X \times Y$ — **ситуациями**, а функция $K$ — **функцией выигрыша** игрока $1$. Выигрыш игрока 2 в ситуации $(x,y)$ полагается равным $(−K(x,y))$, поэтому функция $K$ также называется функцией выигрыша самой игры $\Gamma$, а игра $\Gamma$ — **игрой с нулевой суммой**. Таким образом, используя принятую терминологию, для задания игры $\Gamma$ необходимо определить множества стратегий $X$, $Y$ игроков $1$ и $2$, а также функцию выигрыша $K$, заданную на множестве всех ситуаций $X \times Y$. Игра $\Gamma$ интерпретируется следующим образом: игроки одновременно и независимо выбирают стратегии $x \in X, y \in Y$, после чего игрок $1$ получает выигрыш, равный $K(x,y)$, а игрок $2$ — выигрыш $(−K(x,y))$. Антагонистические игры, в которых оба игрока имеют конечные множества стратегий, называются **матричными**. Если игрок $1$ имеет $m$ стратегий, а игрок $2$ имеет $n$ стратегий, то игра $\Gamma$ полностью определяется матрицей $A = \{a_{ij}\} = \{K(x_i, y_j)\}, \quad 1 \leq i \leq m, \; 1 \leq j \leq n$ Игру $\Gamma$ с матрицей выигрышей $A$ обозначим $\Gamma_A$ и назовем $(m \times n)$-игрой согласно размерности матрицы $A$. *Пример*: камень, ножницы, бумага. | |:gem:|:scissors:|:page_facing_up:| |:--------------:|:-:|:-:|:-:| |:gem: | 0 | 1 |-1 | |:scissors: |-1 | 0 | 1 | |:page_facing_up:| 1 |-1 | 0 | **Нижнее значение игры**: $\alpha = \sup\limits_{x \in X} \inf\limits_{y \in Y} K(x, y)$. Если достигается внешний экстремум, то $\alpha$ называется максимином и представляет собой минимальный гарантированный выигрыш игрока $1$. **Верхнее значение игры**: $\beta = \inf\limits_{y \in Y} \sup\limits_{x \in X} K(x, y)$. Если достигается внешний экстремум, то $\beta$ называется минимаксом и представляет собой максимальный гарантированный проигрыш игрока $2$. **Максиминный принцип** — принцип выбора эффективной стратегии, при котором максимизируется минимальный выигрыш (показатель эффективности): $\alpha_i = \min\limits_{y \in Y} K(x_i, y), \; x_i \in X$ — показатель эффективности **Минимаксный принцип** — принцип выбора эффективной стратегии, при котором минимизируется максимальный проигрыш (показатель неэффективности): $\beta_i = \max\limits_{x \in X} K(x, y_i), \; y_i \in Y$ — показатель неэффективности Пусть задана матричная $(m \times n)$-игра $\Gamma_A$. Тогда внешние экстремумы достигаются, а нижнее и верхнее значения игры соответственно равны $\alpha = \max\limits_{1 \leq i \leq m} \min\limits_{1 \leq j \leq n} K(x_i, y_j)$ $\beta = \min\limits_{1 \leq j \leq n} \max\limits_{1 \leq i \leq m} K(x_i, y_j)$ **Лемма** (стр. 17): В антагонистической игре $\Gamma$: $\alpha \leq \beta$ В антагонистической игре $\Gamma = \langle X, Y, K \rangle$ ситуация $(x^*, y^*)$ называется **ситуацией равновесия** или седловой точкой, если $K(x, y^*) \leq K(x^*, y^*) \leq K(x^*, y), \quad \forall x \in X, \forall y \in Y$ Множество всех ситуаций равновесия в игре $\Gamma$ обозначим через $Z(\Gamma) \subset X \times Y$. **Определение**: игры, в которых существуют ситуации равновесия, называются вполне определенными. **Теорема** (стр. 18): Пусть $(x_1^*, y_1^*)$, $(x_2^*, y_2^*)$ — две произвольные ситуации равновесия в антагонистической игре $\Gamma$. Тогда: 1) $K(x_1^*, y_1^*) = K(x_2^*, y_2^*)$; 2) $(x_1^*, y_2^*) \in Z(\Gamma)$ 3) $(x_2^*, y_1^*) \in Z(\Gamma)$. > Смысл: функция выигрыша принимает одно и то же значение во всех ситуациях равновесия **Следствие**: обозначим $X^∗$ и $Y^∗$ проекции множества $Z(\Gamma)$ на $X$ и $Y$ соответственно: $X^* = \{x^* \in X \; | \; \exists y^* \in Y, (x^*, y^*) \in Z(\Gamma)\}$ $Y^* = \{y^* \in Y \; | \; \exists x^* \in X, (x^*, y^*) \in Z(\Gamma)\}$ Тогда $Z(\Gamma) = X^∗ \times Y^∗$. **Определение**: $X^∗$ и $Y^∗$ — множества оптимальных стратегией игроков, а элементы этих множеств называются оптимальными стратегиями игроков $1$ и $2$ соответственно. **Определение**: Пусть $(x^*, y^*)$ — ситуация равновесия в игре $\Gamma$. Тогда число $v = K(x^*, y^*)$ называется значением игры $\Gamma$. **Лемма о масштабе** (стр. 19): Пусть $\Gamma = \langle X, Y, K \rangle$ и $\Gamma' = \langle X, Y, K' \rangle$ — две антагонистические игры, причем $K' = bK + a$, $\;b > 0$, $\;a = const$, $\;b = const$. Тогда: 1. $Z(Γ') = Z(Γ)$ 2. $v_{Γ'} = bv_{Γ} + a$ > Смысл: оптимальность поведения игроков не изменится, если в игре множества стратегий остаются прежними, а функция выигрыша умножается на положительную константу (или к ней прибавляется постоянное число) **Теорема** (стр. 20): Для того, чтобы в игре $\Gamma$ существовала ситуация равновесия (или по-другому: игра была вполне определена), необходимо и достаточно, чтобы существовали минимакс и максимин и выполнялось их равенство: $\alpha = \max\limits_{x \in X} \inf\limits_{y \in Y} K(x, y) = \min\limits_{y \in Y} \sup\limits_{x \in X} K(x, y) = \beta$ > Смысл: критерий вполне определённости ### 🔄 3. Линейное программирование. Симплекс-метод. Теоремы о двойственности. **Задача линейного программирования** — задача минимизации (максимизации) значения **целевой функции** нескольких переменных, с учетом **ограничений** на значения этих переменных, выраженных явно, или через уравнения связи, где все зависимости являются линейными. - Standard form (все ограничения — неравенства) $\begin{cases} \begin{array}{rcl} \sum\limits_{j=1}^n c_jx_j & \to & \max \\[1ex] \sum\limits_{j=1}^n a_{ij}x_j & \leq & b_i \quad \forall i=1,2,\ldots,m \\[1ex] x_j & \geq & 0 \end{array} \end{cases}$ - Slack form (все ограничения — равенства, кроме неотрицательности) Можно посмотреть [тут](http://rain.ifmo.ru/cat/data/theory/unsorted/simplex-method-2003/article.pdf) + [Кормен, стр. 846](http://index-of.co.uk/Algorithms/Introduction%20to%20Algorithms%203rd%20Edition%20Sep%202010.pdf) ### ✅ 4. Решение антагонистических игр в смешанных стратегиях (понятие решения в смешанных стратегиях и решение матричных игр методами линейного программирования, примеры). > Нужно указание на доказательства из учебника (просто номер страницы), а так же убрать/добавить теоремы, которые у нас не были/были на парах + примеры **Определение**: случайная величина, значениями которой являются стратегии игрока, называется его смешанной стратегией. Детерминированные стратегии, определённые ранее, назовём чистыми стратегиями. Таким образом, смешанные стратегии $x$ и $y$ игроков $1$ и $2$ соответственно: $x = (\xi_1, \ldots, \xi_m), \quad \sum\limits_{i=1}^m \xi_i = 1, \; \xi_i \geq 0, \; \forall i = 1, \ldots, m$ $y = (\eta_1, \ldots, \eta_n), \quad \sum\limits_{j=1}^n \eta_j = 1, \; \eta_j \geq 0, \; \forall j = 1, \ldots, n$ где $\xi_i$ и $\eta_j$ — вероятности выбора чистых стратегий $i \in M$ и $j \in N$. Обозначим через $X$ и $Y$ множества смешанных стратегий первого и второго игроков. **Определение**: Пусть $x = (\xi_1, \ldots, \xi_m) \in X$ — смешанная стратегия игрока $1$. Тогда множество индексов $M_x = \{i \; | \; i \in M,\; \xi_i > 0\}$, где $M = \{1, 2, \ldots, m\}$, назовем спектром стратегии $x$. Аналогично определим спектр стратегии $y$: $M_y = \{j \; | \; j \in N,\; \eta_j > 0\}$ > Смысл: спектр смешанной стратегии состоит из таких чистых стратегий, которые выбираются с положительными вероятностями **Определение**: Пара $(x, y)$ смешанных стратегий игроков в матричной игре $Γ_A$ называется ситуацией в смешанных стратегиях. Определим выигрыш игрока $1$ в ситуации $(x,y)$ в смешанных стратегиях для матричной $(m \times n)$-игры $\Gamma_A$ как математическое ожидание его выигрыша при условии, что игроки используют смешанные стратегии соответственно $x$ и $y$. Выбор стратегий игроками осуществляется независимо друг от друга, поэтому математическое ожидание выигрыша $K(x, y)$ в ситуации $(x, y)$ в смешанных стратегиях $x=(\xi_1, \ldots, \xi_m)$, $y=(\eta_1, \ldots, \eta_n)$ равно $K(x, y) = \sum\limits_{i=1}^m \sum\limits_{j=1}^n a_{ij} \xi_i \eta_j = (xA)y = x(Ay)$ Таким образом, от матричной игры $\Gamma_A$ мы перешли к новой игре $\overline\Gamma_A = \langle X, Y, K \rangle$, где $X$ и $Y$ — множества смешанных стратегий в игре $\Gamma_A$, а $K$ — функция выигрыша в смешанных стратегиях (математическое ожидание выигрыша). Назовём $\overline\Gamma_A$ **смешанным расширением** игры $\Gamma_A$. **Определение**: Ситуация $(x^∗ , y^∗)$ в игре $\overline\Gamma_A$ образует ситуацию равновесия, а число $v = K(x^∗ , y^∗)$ является значением игры $\overline\Gamma_A$, если для всех $x ∈ X$ и $y ∈ Y$: $K(x, y^∗) ≤ K(x^∗ , y^∗) ≤ K(x^∗ , y)$. **Лемма** (стр. 24): Пусть $Γ_A$ и $Γ_A'$ — две матричные $(m \times n)$-игры, где $A' = aA + B, \quad a > 0, \; a = const, \; B = \{b_{ij}\} = \{b_{const}\}$ Тогда: 1. $Z(\overline\Gamma_{A'}) = Z(\overline\Gamma_A)$ 2. $v_{A'} = av_A + b$, где $\overline\Gamma_{A'}$ и $\overline\Gamma_{A}$ — смешанные расширения игр $\Gamma_{A'}$ и $\Gamma_{A}$ соответственно, а $v_{A'}$, $v_A$ — значения игр $\overline\Gamma_{A'}$ и $\overline\Gamma_A$. > Смысл: лемма о масштабе для смешанных игр **Основная теорема матричных игр** (стр. 29): Всякая матричная игра имеет ситуацию равновесия в смешанных стратегиях [Фон Нейман, 1928]. > Смысл: факт существования решения в классе смешанных стратегий означает, что игроки всегда могут снять неопределенность выбора стратегии, с которой они столкнулись перед началом игры, рандомизируя множество чистых стратегий. Следует отметить, что не всегда в антагонистических играх существует решение в смешанных стратегиях. Таким образом, решение матричной игры свелось к задаче линейного программирования, при этом алгоритм решения игры $\overline\Gamma_{A'}$ следующий: 1. По матрице $A'$ строится строго положительная матрица $A = A' + B$, где $B = \{β_{ij}\}$, $β_{ij} = β > 0$. 2. Решаются задачи линейного программирования (прямая и двойственная ей): $\begin{array}{lcc} \min xu, & xA \geq w, & x \geq 0 \\ \max yw, & Ay \leq u, & y \geq 0 \end{array}$ где $u = (1, \ldots, 1) \in \mathbb{R}^m$, $w = (1, \ldots, 1) \in \mathbb{R}^n$ По теореме о двойственности линейного программирования обе задачи имеют оптимальные решения $\overline{x}$ и $\overline{y}$, при этом $\overline{x}u = \overline{y}w = \Theta > 0$ 3. Строятся оптимальные стратегии игроков $1$ и $2$ соответственно, $x^∗ = \overline{x}/\Theta, \; y^∗ = \overline{y}/\Theta$. 4. Вычисляется значение игры $\overline\Gamma_{A'}$: $\;v_{A'} = 1/\Theta − β$. ### ✅ 5. Теоремы о свойствах оптимальных смешанных стратегий в антагонистических играх. Теорема о дополняющей нежесткости. Примеры. **Теорема** (30 стр): Для того, чтобы ситуация $(x^*, y^*)$ была равновесной в игре $\overline\Gamma_A$, а число $v = K(X^*, Y^*)$ — значением игры, необходимо и достаточно выполнение следующих неравенств для всех $i \in M, j \in N$: $K(i,y^*) \leq K(x^*, y^*) \leq K(x^*, j)$ **Следствие**: пусть $(i^*,j^*)$ — ситуация равновесия в игре $\Gamma_A$ (в чистых стратегиях). Тогда она равновесна и в смешанном расширении $\overline\Gamma_A$. **Теорема** (стр. 32): Пусть $\Gamma_A$ — $(m \times n)$-игра. Для того, чтобы ситуация $(x^*,y^*)$ в $\overline\Gamma_A$ была равновесной, необходимо и достаточно выполнения равенства: $\max\limits_{1 \leq i \leq m} K(i, y^*) = \min\limits_{1 \leq j \leq n} K(x^*,j)$ **Теорема** (стр. 33): Для матричной игры $\overline\Gamma_{A}$ справедливо следующее соотношение: $\max\limits_{x} \min\limits_{j} K(x, j) = v_A = \min\limits_{y} \max\limits_{i} K(i, y)$, причем экстремумы по смешанным стратегиям $x$ и $y$ достигаются на оптимальных стратегиях игроков. **Теорема** (стр. 33): В матричной игре $\overline\Gamma_A$ множества оптимальных смешанных стратегий $X^∗$ и $Y^∗$ игроков являются выпуклыми многогранниками. **Теорема о доп.нежесткости** (стр. 35): Пусть $x^∗ = (\xi_1^∗, \ldots, \xi_m^∗)$ и $y^∗ = (\eta_1^∗, \ldots, \eta_n^∗)$ — оптимальные стратегии в игре $\overline\Gamma_{A}$, и $v_{A}$ — значение игры. Тогда для любого $i$, при котором $K(i, y^∗) < v_A$, имеет место равенство $\xi_i^∗ = 0$, а для любого $j$ такого, что $v_A < K(x^∗, j)$ имеет место равенство $η_j^* = 0$. Обратно, если $\xi_i^∗ > 0$, то $K(i, y^∗) = v_A$, а если $η^ ∗_ j > 0$, то $K(x^∗, j) = v_A$. **Определение**: Чистая стратегия $i \in M$ $(j \in N)$ игрока $1$ ($2$) называется существенной или активной стратегией, если существует оптимальная стратегия $x^∗ = (\xi_1^∗, \ldots, \xi_m^∗)$ $(y^∗ = (\eta_1^*, \ldots, \eta_n^*))$ этого игрока, для которой $\xi_i^* > 0$ $(η_j^* > 0)$. > Если чистая стратегия игрока существенна, то она уравновешивает любую оптимальную стратегию противника **Определение**: Говорят, что стратегия $x'$ игрока $1$ доминирует стратегию $x''$ в $(m \times n)$-игре $\Gamma_A$, если для всех чистых стратегий $j \in \{1, \ldots, n\}$ игрока $2$ выполняются неравенства $x' a^j \geq x'' a^j$. Аналогично, стратегия $y'$ игрока $2$ доминирует его стратегию $y''$, если для всех чистых стратегий $i \in \{1, \ldots, m\}$ игрока $1$ выполняются неравенства $a_i y' \leq a_i y''$. Теорема о том, что можно понизить размерность таблицы, вычеркивая доминируемые строки или столбцы кажется важной. В полученной матрице проще найти решение. :::danger Возможно, тут нужна куча теорем о доминировании (стр. 38-43) ::: :::danger Нужны примеры ::: ### 🔄 6. Принципы оптимальности в неантагонистических играх (примеры неантагонистических игр, равновесие по Нэшу, сильное равновесие по Нэшу, равновесие по Парето). Сравнение с антагонистическими играми. Примеры. **Определение**: Система $Γ = \langle N, \; \{X_i\}_{i ∈ N}, \{H_i\}_{i∈N} \rangle$, в которой $N = \{1, 2, . . . , n\}$ — множество игроков, $X_i$ — множество стратегий игрока $i$, $H_i$ — функция выигрыша игрока $i$, определенная на декартовом произведении множеств стратегий игроков $X = \prod^n_{i=1} X_i$ (множество ситуаций игры), называется бескоалиционной игрой. **Обозначение**: Пусть $x = (x_1, . . . , x_{i−1}, x_{i}, x_{i+1}, . . . , x_{n})$ — произвольная ситуация в игре $Γ$, а $x_{i}$ — некоторая стратегия игрока $i$. Построим ситуацию, которая отлична от $x$ только тем, что стратегия $x_i$ игрока $i$ заменена на стратегию $x^′{_i}$. В результате мы получаем ситуацию, которую будем обозначать через $(x∥x^′_i )$. **Определение**: ситуация $x^* = (x_1^*, \ldots, x_n^*)$ называется **равновесной по Нэшу**, если $\forall x_i \in X_i$: $\quad H_i(x^* ∥ x_i) \leq H_i(x^*)$. > Смысл: ситуация при которой ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют **Определение**: Стратегия $x_i^* \in X_i$ называется равновесной по Нэшу, если она входит хотя бы в одну ситуацию равновесия по Нэшу. **Определение**: Ситуация $x^∗$ называется сильно равновесной по Нэшу, если для любой коалиции $S ⊂ N$ и $x_S ∈ ∏_{i∈S} X_i$, существует игрок $i_0 ∈ S$, для которого выполняется строгое неравенство: $H_{i_0} (x^∗) > H_{i_0} (x^∗∥x_S)$. > Смысл: это условие гарантирует нецелесообразность соглашения между игроками с целью вступления в некоторую коалицию $S$, так как в любой коалиции существует игрок, которого это соглашение не устраивает. Любая сильно равновесная ситуация является равновесной по Нэшу (на практике условие сильного равновесия не выполняется в широком классе игр). Если строгое неравенство выполняется только для $\lvert S \rvert = 1$ — равновесие по Нэшу, если для множества $S = N$ — равновесие по Парето (следование, а не эквивалентность). **Определение**: ситуация $\overline x \in \prod\limits_i X_i :$ называется оптимальной по Парето, если не существует ситуации $x'$ такой, что 1) $\forall i \in N : H_i(x') \geq H_i(\overline x)$ 2) $\exists i \in N : H_i(x') \gt H_i(\overline x)$ > Смысл: ситуация при которой не существует другой ситуации, которая была бы предпочтительной для всех игроков, т.е. улучшала бы выигрыш хотя бы одному, не ухудшая при этом выигрыш всех остальных Отметим содержательное различие понятий ситуации равновесия по Нэшу и ситуации, оптимальной по Парето. В первой ситуации ни один игрок, действуя в одиночку, не может увеличить своего выигрыша, во второй — все игроки, действуя совместно, не могут (даже не строго) увеличить выигрыш каждого. **Пример**: [Wiki: Дилемма заключенных](https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%B7%D0%B0%D0%BA%D0%BB%D1%8E%D1%87%D1%91%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE) [[EN](https://en.wikipedia.org/wiki/Prisoner%27s_dilemma)] - Оба молчат: не равновесна по Нэшу (один может сдать другого), оптимальна по Парето - Один сдал другого: не равновесна по Нэшу (тому, кого сдали, выгодней, когда оба сознались), оптимальна по Парето - Оба сознались: равновесна по Нэшу, но не оптимальна по Парето (лучше бы молчали оба) - Все ситуации примера не являются сильно равновесными по Нэшу. **Пример**: [Wiki: Битва полов](https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D0%BB%D0%BE%D0%B2_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B8%D0%B3%D1%80)) - Обе равновесные ситуации сильно равновесны по Нэшу и оптимальны по Парето, но не являются взаимозаменяемыми :::danger Нужно сравнение с антагонистическими играми ::: ### ✅ 7. Равновесие по Штакельбергу в неантагонистических играх. Теорема о борьбе за лидерство. Примеры. Рассмотрим игру двух лиц: $Γ = (X = \{X_1, X_2\}, H = \{ H_1, H_2 \})$ Обозначим за $Z^i$ множество наилучших ответов игрока $i$: $Z^1 = \{(x_1, x_2)\ |\ H_1(x_1, x_2) = \sup\limits_{x'_1\in X_1} H_1(x'_1, x_2)\}$ $Z^2 = \{(x_1, x_2)\ |\ H_2(x_1, x_2) = \sup\limits_{x'_2\in X_2} H_2(x_1, x'_2)\}$ **Определение**: ситуация $(x_1, x_2)$ в игре двух лиц $\Gamma$ называется $i$-равновесием по Штакельбергу, а $\overline H_i$ — $i$-выигрышем, если $(x_1, x_2) \in Z^j$ и выполняется равенство: $\overline H_i = H_i(x_1, x_2) = \sup\limits_{(y_1, y_2) \in Z^j} H_i(y_1, y_2), \; \text{где} \; i = 1, 2; \; i \neq j \tag{*}$ > Смысл: понятие $i$-равновесия можно интерпретировать следующим образом. Игрок $1$ (лидер) знает функции выигрыша обоих игроков $H_1$, $H_2$, а тем самым и множество наилучших ответов $Z^2$ игрока $2$ (ведомого) на любую стратегию $x_1$ игрока $1$. Тогда он, обладая этой информацией, максимизирует свой выигрыш, выбирая стратегию $x_1$ из условия $(*)$. Таким образом, $\overline H_i$ — это выигрыш $i$-го игрока, действующего оптимально в качестве «лидера» в игре $\Gamma$. **Определение**: Будем говорить, что в игре двух лиц $Γ = (X_1, X_2, H_1, H_2)$ имеет место борьба за лидерство, если не существует такой ситуации $(x_1, x_2) ∈ X_1 × X_2$, что $\overline H_i \leq H_i(x_1, x_2), \; i = 1, 2$. > Смысл: имеет место борьба за лидерство, если нет выигрыша лучше, чем тот выигрыш, когда $i$-ый игрок знает заведомо все оптимальные стратегии второго **Лемма** (стр. 128): Пусть $Z(Γ)$ — множество ситуаций равновесия по Нэшу в игре двух лиц $Γ$. Тогда $Z(Γ) = Z_1 ∩ Z_2$, где $Z_1$, $Z_2$ — множества наилучших ответов игроков 1,2 в игре $Γ$. **Теорема о борьбе за лидерство** (стр. 128): Если игра двух лиц $Γ = (X_1, X_2, H_1, H_2)$ имеет по крайней мере две оптимальных по Парето и равновесных по Нэшу ситуации $(x_1, x_2)$, $(y_1, y_2)$ с различными векторами выигрышей $(H_1(x_1, x_2), H_2(x_1, x_2)) \ne (H_1(y_1, y_2), H_2(y_1, y_2))$, то в игре $Γ$ имеет место борьба за лидерство. **Примеры**: игры [Wiki: Битва полов](https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%B2%D0%B0_%D0%BF%D0%BE%D0%BB%D0%BE%D0%B2_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B8%D0%B3%D1%80)) и «перекресток» удовлетворяют условиям теоремы, поэтому в них имеет место борьба за лидерство. ### 🔴 8. Теоремы о свойствах ситуаций равновесия в неантагонистических матричных играх. Вполне смешанные игры. Теорема о нахождении оптимальных вполне смешанных стратегий в неантагонистических играх. Примеры. Стратегия $x$ $(y)$ игрока $1$ $(2)$ называется **вполне смешанной**, если ее спектр состоит из множества всех стратегий игрока, т. е. $M_x=M(N_y=N)$. Ситуация равновесия $(x^∗,y^∗)$ называется **вполне смешанной**, если стратегии $x^∗$ и $y^∗$ — вполне смешанные. Игра $\Gamma_A$ называется **вполне смешанной**, если каждая ситуация равновесия в ней является вполне смешанной. Про "Теорема о нахождении оптимальных вполне смешанных стратегий в неантагонистических играх" ищите на 142 сранице. ![](https://i.imgur.com/n2dZT9D.png) ### 🔄 9. Равновесие в совместных смешанных стратегиях. Теорема о связи с ситуациями равновесия в смешанных стратегиях. **Совместная смешанная стратегия игроков** — это распределение вероятностей на всем множестве возможных чистых стратегий всех игроков Формально, это такая функция $\mu : R^{n\times m} \mapsto R$, $\mu_{i, j} \ge 0$, $\sum{\mu_{i, j}} = 1$ **Пример**: семейный спор ||Балет (ж)|Футбол (ж)| |-:|:-:|:-:| |Балет (м)|(1, 4)|(0, 0)| |Футбол (м)|(0, 0)|(4, 1)| _То есть, грубо говоря, муж и жена заранее договариваются: кто-то (возможно, кто-то третий (в данном случае это $\mu$) — важно, что ни один участник не контролирует этот результат, но оба имеют к нему доступ) вечером подбросит монетку (возможно, нечестную), и если выпадет орел, то они вместе пойдут на балет, а если решка — на футбол._ На этом примере функция $\mu$ может быть определна так: ||Балет (ж)|Футбол (ж)| |-:|:-:|:-:| |Балет (м)|0.4|0| |Футбол (м)|0|0.6| **Выигрыш $k^{ого}$ игрока**: $K_k = \sum_{i, j}U_k(i, j) \cdot \mu_{i, j}$ — линейная комбинация чистых стратегий игроков **Равновесие в совместных смешанных стратегиях** — это такое распределение вероятностей $\mu$ на множестве чистых стратегий $\mathbf S_1 \times \mathbf S_2$, что $\forall i, i' \in \mathbf S_1, j, j' \in \mathbf S_2: \\ \sum\limits_{j}U_1(i, j)\mu_{i, j} \ge \sum\limits_{j}U_1(i',j)\mu_{i, j}, \quad \sum\limits_{i}U_2(i, j)\mu_{i, j} \ge \sum\limits_{i}U_2(i,j')\mu_{i, j}$ **Теорема**: $\sqsupset x, y$ - ситуации равновесия в смешанных стратегиях $\iff$ $\mu=xy^T$ — ситуация равновесия в совместных смешанных стратегиях. ### 🔴🔄 10. Экстенсивная форма. Оптимальность по подыграм. Примеры. > Экстенсивная == развернутая Экстенсивная форма - представление игры в виде ориентированного дерева, каждая вершина определяет выбор соответствующего игрока. От каждой вершины отходят ветви, обозначающие стратегии данного игрока. Платежи игроков записываются внизу дерева. ![](https://i.imgur.com/9PY6H4I.png) > оптимальность подагры где-то в районе 39 страницы около 1.8.2 теоремы наверное ™ [Wiki: Равновесие, совершенное по подыграм](https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B2%D0%BD%D0%BE%D0%B2%D0%B5%D1%81%D0%B8%D0%B5,_%D1%81%D0%BE%D0%B2%D0%B5%D1%80%D1%88%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8B%D0%B3%D1%80%D0%B0%D0%BC) ### 🔴 11. Повторяющиеся игры. Способы вычисления выигрышей. Фольклорная теорема. Примеры. [Wiki: Folk theorem](https://en.wikipedia.org/wiki/Folk_theorem_(game_theory)) ![](https://i.imgur.com/tZQDirF.png) ![](https://i.imgur.com/GcbxAlV.png) [Презентация: Фольклорная теорема](https://compscicenter.ru/media/courses/2012-spring/spb-game-theory/slides/game_theory_lecture_210312.pdf) + [Зеркало](https://github.com/egormkn/ifmo-kt/releases/download/8.games/subgames.pdf) [Презентация: Повторяющиеся игры](http://www.pisaruk-9591.appspot.com/static/slides/games/repeated.pdf) + [Зеркало](https://github.com/egormkn/ifmo-kt/releases/download/8.games/repeated.pdf) ### 🔴 12. Правила определения победителя при голосовании. Теорема Эрроу. [Wiki: Теорема Эрроу](https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%AD%D1%80%D1%80%D0%BE%D1%83) > Можно посмотреть часть этого мини-курса: https://www.intuit.ru/studies/courses/1052/304/info (в 240p (удачи рассмотреть формулы)) > Достаточно отрывками 1 и 2 видео, а так же полностью третье. ## FAQ ### Как проверить, что смешанная ситуация - ситуация равновесия? Используем, что $K(i, y^*) \leq K(x^*, y^*) \leq K(x^*, j)$ ### Фольклорная теорема Пусть у нас есть совместная стратегия для игроков. Если кто-то от неё отклоняется, остальные игроки будут его наказывать: играть так, чтобы выигрыш отклонившегося был минимальным. Утверждается, что при достаточно большом $\delta$ любая стратегия, в которой доход каждого игрока больше минимального - является равновесным (т.е. мы можем наказывать достаточно долго, чтобы отход от нашей стратегии был невыгоден). feasible + enforceable --> равновесие по Нэшу равновесие по Нэшу --> enforceable > сверху какая-то хуйня, чек 11 билет Не очень хуйня, [тут](https://en.wikipedia.org/wiki/Folk_theorem_(game_theory)) примерно это и написано. ![](https://i.imgur.com/z10wRbJ.png) ### Награды в повторяющихся играх 1) предел среднего 2) $\Sigma(b^j * r_j)$, где b от 0 до 1 Чек 11 билет ### Мы решаем задачу о нахождении оптимальной смешанной страгении в антогонистических играх через задачу линейного программирования. А какой смысл в её двойственной задаче? Через двойственную задачу находится оптимальная стратегия для второго игрока. ### Как так получается, что в бесконечной игре заключенных оптимально всегда не сдавать другого? В конечной игре так не работает. > Тут, наверное, написан какой-то бред, как в вопросе, так и в ответе, так как в бесконечной игре работает стратегия с тем, чтобы сначала не сдавать, а потом повторять предыдущий ход оппонента (око за око). Но нужно убедиться в этом, чекните. Есть стратегия: сначала всегда не сдаём, если другой нас сдаст, то будем его постоянно сдавать. Очевидно, от неё невыгодно отклоняться (при адекватном подсчёте наград). ### Для чего нужна оптимальность по подыграм? [wiki without any credible sources](https://en.wikipedia.org/wiki/Non-credible_threat) Чтобы исключать недостоверные угрозы (такие, которые наносят ущерб угрожающему) ### Зачем нужны смешанные стратегии? Пример. В антагонистических играх с чистыми стратегиями ситуации равновесия может не быть, мы можем добавить смешанные, решить задачу линейного программирования и получить ситуацию равновесия, так как в смешанных она существует всегда. ### Знают ли в совместных стратегиях игроки куда пойдут другие? Нет, не знают. В совместных стратегиях мы как бы определяем матрицу общую для всех игроков по которой выбираются чистые стратегии, она может быть устроена так что выбор одних зависит от выбора других. Однако когда игроку говорят, какая стратегия ему выпала, ему не сообщают, какая стратегия выпала второму. ### Как искать ситуацию равновесия в смешанных стратегиях? Если речь об антогонистических играх, то c помощью линейного программирования, см. 4 билет. ## Рандомные определения (засмеялся - проиграл) ### Вполне определенные игры ### Игры, в которых существуют ситуации равновесия, называются вполне определенными. ### Cмешанные расширения игр ### Таким образом, от матричной игры $Γ_A= (M,N,A)$ мы перешли к новой игре $\overline Γ_A=(X,Y,K)$, где $X$ и $Y$ — множества смешанных стратегий в игре $Γ_A$ и $K$ — функция выигрыша в смешанных стратегиях (математическое ожидание выигрыша). Игру $\overline Γ_A$ будем называть смешанным расширением игры $Γ_A$. Игра $Γ_A$ является подыгрой для $\overline Γ_A$, т. е. $Γ_A ⊂ \overline Γ_A$. > В дальнейшем, говоря о матричной игре $Γ_A$, будем предполагать, что речь идет о ее смешанном расширении $Γ_A$