Глоссарий теории игр

Теория игр — это раздел математики , в котором игры изучаются , то есть модели, описывающие поведение человека. Это глоссарий некоторых терминов по этой теме.

Определения игры

Условные обозначения

Реальные числа

$\mathbb {R}$.

Набор игроков

$\mathrm {N}$.

Стратегическое пространство

$\Sigma \ =\prod _{i\in \mathrm {N} }\Sigma \ ^{i}$, где

Стратегическое пространство игрока i

$\Sigma \ ^{i}$ — это пространство всех возможных способов, которыми игрок i может играть в игру.

Стратегия для игрока i

$\sigma \ _{i}$ является элементом $\Sigma \ ^{i}$.

Дополняет

$\sigma \ _{-i}$ элемент $\Sigma \ ^{-i}=\prod _{j\in \mathrm {N} ,j\neq i}\Sigma \ ^{j}$, представляет собой кортеж стратегий для всех игроков, кроме i .

Пространство результата

$\Gamma$ в большинстве учебников идентично -

Выплаты

$\mathbb {R} ^{\mathrm {N} }$, описывающий, сколько выигрыша (денег, удовольствия и т. д.) получают игроки к концу игры.

Игра нормальной формы

Игра в нормальной форме — это функция:

$\pi \ :\prod _{i\in \mathrm {N} }\Sigma \ ^{i}\to \mathbb {R} ^{\mathrm {N} }$

Учитывая кортеж стратегий , выбранных игроками, дается распределение выплат (в виде действительных чисел).

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

$\pi \ :\prod _{i\in \mathrm {N} }\Sigma \ ^{i}\to \Gamma$

функция результата игры (некоторые авторы называют эту функцию «игровой формой») и:

$\nu \ :\Gamma \ \to \mathbb {R} ^{\mathrm {N} }$

распределение выигрышей (или преференций ) игрокам для каждого исхода игры.

Игра расширенной формы

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

Кооперативная игра

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

$\nu \ :2^{\mathbb {P} (N)}\to \mathbb {R}$

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

Простая игра

Простая игра — это упрощенная форма совместной игры, в которой возможный выигрыш принимается равным «0» или «1». Простая игра — это пара ( N , W ), где W — список «победивших» коалиций , способных получить добычу («1»), а N — набор игроков.

Глоссарий

Приемлемая игра

Это форма игры , в которой для всех возможных профилей предпочтений игра имеет чистые равновесия Нэша , все из которых эффективны по Парето .

Распределение товаров

это функция $\nu \ :\Gamma \ \to \mathbb {R} ^{\mathrm {N} }$. Распределение является кардинальным подходом к определению блага (например, денег), которое игроки получают при различных результатах игры.

Лучший ответ

лучший ответ на данное дополнение $\sigma \ _{-i}$ это стратегия $\tau \ _{i}$ это максимизирует игрока i платеж . Формально мы хотим:
$\forall \sigma \ _{i}\in \ \Sigma \ ^{i}\quad \quad \pi \ (\sigma \ _{i},\sigma \ _{-i})\leq \pi \ (\tau \ _{i},\sigma \ _{-i})$.

Коалиция

— это любое подмножество множества игроков: $\mathrm {S} \subseteq \mathrm {N}$.

Победитель Кондорсе

Учитывая предпочтение ν в пространстве исходов , исход a является победителем по Кондорсе, если все игроки, не являющиеся фиктивными, предпочитают a всем остальным исходам.

Разрешимость

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

Определенность

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

Решительная игра (или Строго определенная игра )

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

Диктатор

Игрок является сильным диктатором , если он может гарантировать любой результат независимо от других игроков. $m\in \mathbb {N}$ является слабым диктатором , если он может гарантировать любой результат, но его стратегия достижения этого может зависеть от вектора стратегии дополнения. Естественно, каждый сильный диктатор является слабым диктатором. Формально:
n является сильным диктатором, если:
$\forall a\in \mathrm {A} ,\;\exists \sigma \ _{n}\in \Sigma \ ^{n}\;s.t.\;\forall \sigma \ _{-n}\in \Sigma \ ^{-n}:\;\Gamma \ (\sigma \ _{-n},\sigma \ _{n})=a$
m является слабым диктатором, если:
$\forall a\in \mathrm {A} ,\;\forall \sigma \ _{-m}\in \Sigma \ ^{-m}\;\exists \sigma \ _{m}\in \Sigma \ ^{m}\;s.t.\;\Gamma \ (\sigma \ _{-m},\sigma \ _{m})=a$

Другой способ выразить это:

– Сильный диктатор это $\alpha$- эффективен для всех возможных результатов.

– Слабый диктатор это $\beta$- эффективен для всех возможных результатов.

В игре может быть не более одного сильного диктатора . В некоторых играх есть несколько слабых диктаторов (в игре «камень-ножницы-бумага» оба игрока являются слабыми диктаторами, но ни один из них не является сильным диктатором ).

Также см. Эффективность . Антоним: манекен .

Доминирующий результат

Учитывая предпочтение ν в пространстве результатов , мы говорим, что результат a доминирует над результатом b (следовательно, b является доминирующей стратегией), если его предпочитают все игроки. Если, кроме того, какой-то игрок строго предпочитает b, а не a , то мы говорим, что a доминируется строго . Формально:
$\forall j\in \mathrm {N} \;\quad \nu \ _{j}(a)\leq \ \nu \ _{j}(b)$ ради господства и
$\exists i\in \mathrm {N} \;s.t.\;\nu \ _{i}(a)<\nu \ _{i}(b)$ за строгое господство.
Результат a является (строго) доминируемым , если над ним (строго) доминирует какой-либо другой результат .
Исход a является доминантным для коалиции S , если все игроки в S предпочитают какой-то другой исход вместо a . См. также победитель Кондорсе .

Доминируемая стратегия

мы говорим, что в стратегии (сильно) доминирует стратегия $\tau \ _{i}$ если для любого кортежа дополнительных стратегий $\sigma \ _{-i}$, игрок I получает выгоду от игры $\tau \ _{i}$. Формально говоря:
$\forall \sigma \ _{-i}\in \ \Sigma \ ^{-i}\quad \quad \pi \ (\sigma \ _{i},\sigma \ _{-i})\leq \pi \ (\tau \ _{i},\sigma \ _{-i})$ и
$\exists \sigma \ _{-i}\in \ \Sigma \ ^{-i}\quad s.t.\quad \pi \ (\sigma \ _{i},\sigma \ _{-i})<\pi \ (\tau \ _{i},\sigma \ _{-i})$.
Стратегия σ является (строго) доминируемой , если она (строго) доминируется какой-либо другой стратегией .

Дурачок

Игрок i является болваном, если он не влияет на исход игры. То есть, если исход игры нечувствителен к игрока . стратегии

Антонимы: скажи , вето , диктатор .

Эффективность

Коалиция (или одиночный игрок) S эффективна для a, если она может заставить a стать результатом игры. S является α-эффективным, если члены S имеют стратегии st, независимо от того, что делает дополнение S , результатом будет a .

S является β-эффективным, если на любые стратегии дополнения S члены S могут отвечать стратегиями, обеспечивающими результат a .

Конечная игра

— игра с конечным числом игроков, каждый из которых имеет конечный набор стратегий .

Большая коалиция

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

Смешанная стратегия

для игрока i — это распределение вероятностей P на $\Sigma \ ^{i}$. Понятно, что игрок выбирает стратегию случайным образом в соответствии с P. i

Смешанное равновесие Нэша

То же, что чистое равновесие Нэша , определенное в пространстве смешанных стратегий . Каждая конечная игра имеет смешанное равновесие Нэша .

Парето-эффективность

Результат если a игры формы π (сильно) эффективен по Парето, он не доминируется ни при каких профилях предпочтений .

Профиль предпочтений

это функция $\nu \ :\Gamma \ \to \mathbb {R} ^{\mathrm {N} }$. Это порядковый подход к описанию результата игры. Предпочтение описывает, насколько игроки «довольны» возможными результатами игры. См. распределение товаров .

Чистое равновесие Нэша

Элемент $\sigma \ =(\sigma \ _{i})_{i\in \mathrm {N} }$ Стратегического пространства игры является чистой точкой равновесия по Нэшу , если ни один игрок i не может получить выгоду, отклонившись от своей стратегии. $\sigma \ _{i}$, учитывая, что другие игроки играют в $\sigma$. Формально:
$\forall i\in \mathrm {N} \quad \forall \tau \ _{i}\in \ \Sigma \ ^{i}\quad \pi \ (\tau \ ,\sigma \ _{-i})\leq \pi \ (\sigma \ )$.
Ни одна точка равновесия не является доминирующей.

Сказать

Игрок i имеет слово Say, если он не является пустышкой , т. е. если существует некоторый набор дополнительных стратегий st π (σ_i) не является постоянной функцией.

Антоним: Манекен .

Число Шеннона

Консервативная нижняя граница сложности дерева игры в шахматах (10 ¹²⁰ ).

Решенная игра

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

Ценить

Ценность ожидаемый игры – это рационально результат . Существует немало определений ценности , описывающих различные методы получения решения игры.

Вето

Вето означает способность (или право) какого-либо игрока не допустить того, чтобы конкретная альтернатива стала результатом игры. Игрок, обладающий такой способностью, называется игроком с правом вето .

Антоним: Манекен .

Слабо приемлемая игра

Это игра, в которой есть чистые равновесия Нэша, некоторые из которых эффективны по Парето .

с нулевой суммой Игра

Это игра, в которой распределение является постоянным в зависимости от исхода . Формально:
$\forall \gamma \ \in \Gamma \ \sum _{i\in \mathrm {N} }\nu \ _{i}(\gamma \ )=const.$
wlg мы можем предположить, что эта константа равна нулю. В игре с нулевой суммой выигрыш одного игрока равен проигрышу другого игрока. Большинство классических настольных игр (например, шахматы , шашки ) имеют нулевую сумму .

Внешние ссылки

• Словарь теории игр - Game Theory.net