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

редактировать

Список определений терминов и концепций, используемых в теории игр

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

Содержание

1 Определения игры
- 1.1 Условные обозначения
- 1.2 Игра в нормальной форме
- 1.3 Игра в расширенной форме
- 1.4 Кооперативная игра
- 1.5 Простая игра
2 Глоссарий
3 Ссылки

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

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

Действительные числа: $R {\ displaystyle \ mathbb {R}}$ $\ mathbb {R}$ .
Набор игроков: $N {\ displaystyle \ mathrm {N}}$ $\ mathrm {N}$ .
Пространство стратегии: $Σ = ∏ i ∈ N Σ i {\ displaystyle \ Sigma \ = \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i}}$ $\ Sigma \ = \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i}$ , где
пространство стратегии игрока i: $Σ i {\ displaystyle \ Sigma \ ^ {i}}$ $\ Sigma \ ^ {i}$ - пространство всех возможных способы, которыми игрок i может играть в игру.
Стратегия для игрока i

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

Дополняет

$σ - i {\ displaystyle \ sigma \ _ {- i}}$ $\ sigma \ _ {- i}$ элемент $Σ - я знак равно ∏ J ∈ N, J ≠ я Σ J {\ Displaystyle \ Sigma \ ^ {- i} = \ prod _ {j \ in \ mathrm {N}, j \ neq i} \ Sigma \ ^ {j}}$ $\ Sigma \ ^ {- i} = \ prod _ {j \ in \ mathrm {N}, j \ neq i} \ Sigma \ ^ {j}$ , является набор стратегий для всех игроков, кроме i.

Outcome space: $Γ {\ displaystyle \ Gamma}$ $\ Gamma$ в большинстве учебников идентичен -
Payoffs: $RN {\ displaystyle \ mathbb {R} ^ {\ mathrm {N}}}$ $\ mathbb {R} ^ {\ mathrm {N}}$ , описывающий, сколько выигрыша (денег, удовольствия и т.д.) игроки получают к концу игры.

Игра в нормальной форме

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

π: ∏ i ∈ N Σ i → RN {\ displaystyle \ pi \: \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i} \ to \ mathbb {R} ^ {\ mathrm {N}}}

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

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

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

π: ∏ i ∈ N Σ i → Γ {\ displaystyle \ pi \: \ prod _ {i \ in \ mathrm {N}} \ Sigma \ ^ {i} \ to \ Gamma}

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

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

ν: Γ → RN {\ displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}

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

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

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

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

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

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

ν: 2 P (N) → R {\ displaystyle \ nu \: 2 ^ {\ mathbb {P} (N)} \ to \ mathbb {R }}

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

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

Простая игра

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

Глоссарий

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

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

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

Коалиция: - это любое подмножество множества игроков: $S ⊆ N {\ displaystyle \ mathrm {S} \ substeq \ mathrm {N}}$ $\ mathrm {S} \ substeq \ mathrm {N}$ .

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

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

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

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

Диктатор

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

m ∈ N {\ displaystyle m \ in \ mathbb {N}}

m \ in \ mathbb {N}

является слабым диктатором, если он может гарантировать любой результат, но его стратегии для этого могут зависеть от вектора стратегии дополнения. Естественно, каждый сильный диктатор является слабым диктатором. Формально:. m - Сильный диктатор, если:.

∀ a ∈ A, ∃ σ n ∈ Σ ns. T. ∀ σ - n ∈ Σ - n: Γ (σ - n, σ n) = a {\ displaystyle \ forall a \ in \ mathrm {A}, \; \ exists \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n}: \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}

\ forall a \ in \ mathrm {A}, \; \ exists \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n}: \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a

. m является Слабым диктатором, если:.

∀ a ∈ A, ∀ σ - n ∈ Σ - n ∃ σ n ∈ Σ ns. т. Γ (σ - N, σ N) знак равно a {\ displaystyle \ forall a \ in \ mathrm {A}, \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n} \; \ существует \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}

\ forall a \ in \ mathrm {A}, \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n} \; \ exists \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a

Другой можно сказать так:

слабый диктатор

α {\ displaystyle \ alpha}

\ alpha

-эффективен для всех возможных исходов.

Сильный диктатор - это

β {\ displaystyle \ beta}

\ beta

- эффективен для всех возможных исходов.

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

См. Также «Эффективность». Антоним: пустышка.

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

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

Манекен: Игрок i является манекеном, если он не влияет на исход игры. Т.е. если исход игры нечувствителен к стратегии игрока i .; Антонимы: скажем, вето, диктатор.

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

Конечная игра: - это игра с конечным числом игроков, каждый из которых имеет конечный набор стратегий .

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

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

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

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

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

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

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

Число Шеннона: Консервативная нижняя граница сложности дерева игр шахмат (10).

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

Значение: A значение игры является рационально ожидаемым результатом . Существует несколько определений value, описывающих различные методы получения решения игры.

Veto: Вето означает возможность (или право) некоторого игрока на не допустить, чтобы конкретная альтернатива стала результатом игры. Игрок, обладающий этой способностью, называется игроком с вето .; Антоним: Манекен.

Слабо приемлемая игра: - это игра с чистым равновесием по Нэшу, некоторые из которых эффективны по Парето .

Игра с нулевой суммой: - это игра, в которой распределение является постоянным для различных исходов . Формально:. $∀ γ ∈ Γ ∑ i ∈ N ν i (γ) = c o n s t. {\ Displaystyle \ forall \ gamma \ \ in \ Gamma \ \ sum _ {i \ in \ mathrm {N}} \ nu \ _ {i} (\ gamma \) = const.}$ $\ forall \ gamma \ \ in \ Gamma \ \ sum _ {i \ in \ mathrm {N}} \ nu \ _ {i} (\ gamma \) = const.$ . w.l.g. мы можем считать эту константу равной нулю. В игре с нулевой суммой выигрыш одного игрока равен проигрышу другого игрока. Большинство классических настольных игр (например, шахматы, шашки ) имеют нулевую сумму .

Ссылки