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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Глоссарий теории игр»  -  новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Определения игры [ править ]

Условные обозначения [ править ]

Действительные числа

${\ Displaystyle \ mathbb {R}}$.

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

${\ Displaystyle \ mathrm {N}}$.

Пространство стратегии

${\ Displaystyle \ Sigma \ = \ prod _ {я \ in \ mathrm {N}} \ Sigma \ ^ {i}}$, куда

Пространство стратегии игрока i

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

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

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

Дополнения

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

Исходное пространство

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

Выплаты

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

Игра в нормальной форме [ править ]

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

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

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

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

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

функция исход игры (некоторые авторы называют эту функцию «игровой форме»), а также :

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

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

Игра с расширенными формами [ править ]

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

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

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

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

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

Простая игра [ править ]

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

Глоссарий [ править ]

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

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

Размещение товаров

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

Лучший ответ

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

Коалиция

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

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

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

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

В отношении теории игр относится к вопросу о существовании алгоритма, который может и будет давать ответ о том, можно ли решить игру или нет. ^[1]

Решительность

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

Определенная игра (или строго определенная игра )

В теории игр строго определенная игра - это игра с нулевой суммой для двух игроков, которая имеет по крайней мере одно равновесие по Нэшу, когда оба игрока используют чистые стратегии . ^{[2] [3]}

Диктатор

Игрок - сильный диктатор, если он может гарантировать любой результат независимо от других игроков. является слабым диктатором, если он может гарантировать какой-либо результат, но его стратегии для этого могут зависеть от вектора стратегии дополнения. Естественно, каждый сильный диктатор - слабый диктатор. Формально: m - Сильный диктатор, если: m - Слабый диктатор, если:${\displaystyle m\in \mathbb {N} }$

${\displaystyle \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}$

${\displaystyle \forall a\in \mathrm {A} ,\;\forall \sigma \ _{-n}\in \Sigma \ ^{-n}\;\exists \sigma \ _{n}\in \Sigma \ ^{n}\;s.t.\;\Gamma \ (\sigma \ _{-n},\sigma \ _{n})=a}$

Другими словами:

слабый диктатор является -эффективным для каждого возможного результата.${\displaystyle \alpha }$

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

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

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

Преобладающий результат

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

Результат a является доминирующим для коалиции S, если все игроки в S предпочитают какой-либо другой исход a . См. Также Победитель Кондорсе .

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

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

Дурачок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Элементом стратегического пространства игры является точка чистого равновесия по Нэшу, если ни один игрок i не может получить выгоду, отклонившись от своей стратегии , при условии, что другие игроки играют . Формально: . Никакая точка равновесия не доминирует.${\displaystyle \sigma \ =(\sigma \ _{i})_{i\in \mathrm {N} }}$${\displaystyle \sigma \ _{i}}$${\displaystyle \sigma }$
${\displaystyle \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 ¹²⁰ ).

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

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

Ценить

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

Вето

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

Антоним: Пустышка .

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

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

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

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

Ссылки [ править ]