Минимакс

Минимакс (иногда Минмакс , мм ^[1] или седловая точка ^[2]) — правило принятия решения, используемое в искусственном интеллекте , теории принятия решений , теории игр , статистике и философии для минимизации возможных потерь для наихудшего сценария ( максимальные потери) . Когда речь идет о выигрыше, его называют «максимином» — максимизировать минимальный выигрыш. для нескольких игроков с нулевой суммой Первоначально сформулированная для теории игр , охватывающая как случаи, когда игроки делают попеременные ходы, так и случаи, когда они делают одновременные ходы, она также была распространена на более сложные игры и на общее принятие решений в присутствии неопределенности.

Теория игр

В общих играх

Максиминное значение — это наивысшее значение, которое игрок может быть уверен получить, не зная действий других игроков; эквивалентно, это наименьшее значение, которое другие игроки могут заставить игрока получить, когда они знают действие игрока. Его формальное определение таково: ^[3]

{\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}

Где:

$i$ — индекс интересующего игрока.
$-i$ обозначает всех остальных игроков, кроме игрока $i$ .
$a_{i}$ — действие, предпринятое игроком $i$ .
$a_{-i}$ обозначает действия, предпринятые всеми остальными игроками.
$v_{i}$ — функция ценности игрока $i$ .

Вычисление максиминного значения игрока производится в наихудшем случае: для каждого возможного действия игрока мы проверяем все возможные действия других игроков и определяем наихудшую возможную комбинацию действий – ту, которая дает игроку $i$ наименьшее значение. ценить. Затем мы определяем, какое действие $я$ могу предпринять, чтобы убедиться, что это наименьшее значение является максимально возможным.

Например, рассмотрим следующую игру для двух игроков, где первый игрок («игрок в ряд») может выбрать любой из трех ходов, обозначенных $T$ , $M$ или $B$ , а второй игрок («игрок в столбец») может выбрать любой из два хода $L$ или $R.$ , Результат комбинации обоих ходов выражается в таблице выигрышей:

{\begin{array}{c|cc}\hline &L&R\\\hline T&3,1&2,-20\\M&5,0&-10,1\\B&-100,2&4,4\\\hline \end{array}}

(где первое число в каждой ячейке — это выплата игрока по строке, а второе число — это выплата игрока по столбцу).

Для примера мы рассматриваем только чистые стратегии . Проверьте каждого игрока по очереди:

Игрок в ряду может сыграть $T$ , что гарантирует ему выигрыш как минимум 2 (игра $B$ рискованна, поскольку может привести к выигрышу −100 , а игра $M$ может привести к выигрышу −10 ). Следовательно: ${\underline {v_{row}}}=2$ .
Игрок колонны может сыграть $L$ и получить выигрыш как минимум 0 (игра $R$ подвергает его риску получить $-20$ ). Следовательно: ${\underline {v_{col}}}=0$ .

Если оба игрока используют свои максиминные стратегии $(T,L)$ , вектор выигрыша равен $(3,1)$ .

Минимаксное значение игрока — это наименьшее значение, которое другие игроки могут заставить игрока получить, не зная о его действиях; эквивалентно, это наибольшая ценность, которую игрок может быть уверен получить, зная действия других игроков. Его формальное определение таково: ^[3]

{\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}

Определение очень похоже на определение значения максимина – только порядок операторов максимума и минимума обратный. В приведенном выше примере:

Игрок ряда может получить максимальное значение $4$ (если другой игрок играет $R$ ) или 5 (если другой игрок играет $L$ ), поэтому: ${\overline {v_{row}}}=4\ .$
Игрок столбца может получить максимальное значение $1$ (если другой игрок играет $T$ ), 1 (если $M$ ) или 4 (если $B$ ). Следовательно: ${\overline {v_{col}}}=1\ .$

Для каждого игрока $i$ максимин не более чем минимакс:

{\underline {v_{i}}}\leq {\overline {v_{i}}}

Интуитивно понятно, что в максимине максимизация следует за минимизацией, поэтому игрок $i$ пытается максимизировать свою ценность, прежде чем узнает, что сделают остальные; в минимаксе максимизация предшествует минимизации, поэтому игрок $i$ находится в гораздо лучшем положении — он максимизирует свою ценность, зная, что сделали другие.

Другой способ понять обозначения — читать справа налево: Когда мы пишем

{\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}=\min _{a_{-i}}{\Big (}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}{\Big )}

первоначальный набор результатов $\ v_{i}(a_{i},a_{-i})\$ зависит от обоих $\ {a_{i}}\$ и $\ {a_{-i}}\ .$ Сначала мы маргинализируемся ${a_{i}}$ от $v_{i}(a_{i},a_{-i})$ , максимизируя более $\ {a_{i}}\$ (для каждого возможного значения ${a_{-i}}$ ) для получения набора предельных результатов $\ v'_{i}(a_{-i})\,,$ что зависит только от $\ {a_{-i}}\ .$ Затем мы минимизируем более $\ {a_{-i}}\$ над этими результатами. (Обратно для максимина.)

Хотя это всегда так $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ и $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ вектор выигрыша, возникающий в результате того, что оба игрока используют свои минимаксные стратегии, $\ (2,-20)\$ в случае $\ (T,R)\$ или $(-10,1)$ в случае $\ (M,R)\,,$ аналогичным образом не может быть сопоставлен с вектором выигрыша $\ (3,1)\$ в результате того, что оба игрока придерживаются своей максиминной стратегии.

В играх с нулевой суммой

для двух игроков В играх с нулевой суммой минимаксное решение совпадает с равновесием Нэша .

В контексте игр с нулевой суммой теорема о минимаксе эквивалентна: ^[4]^{[ не удалось пройти проверку ]}

двух лиц Для каждой игры с нулевой суммой с конечным числом стратегий существует значение $V$ и смешанная стратегия для каждого игрока, такие что
(a) Учитывая стратегию Игрока 2, наилучший возможный выигрыш для Игрока 1 равен $V$ , и
(b) Учитывая стратегию Игрока 1, наилучший возможный выигрыш для Игрока 2 равен − $V$ .

Аналогично, стратегия Игрока 1 гарантирует ему выигрыш $V$ может гарантировать себе выигрыш в размере − $V.$ независимо от стратегии Игрока 2, и аналогичным образом Игрок 2 Название «минимакс» возникло потому, что каждый игрок минимизирует максимально возможный выигрыш для другого – поскольку игра ведется с нулевой суммой, они также минимизируют свои собственные максимальные потери (т. е. максимизируют свой минимальный выигрыш).См. также пример игры без значения .

Пример

Матрица выигрышей для игрока А
	Б выбирает Б1	Б выбирает Б2	Б выбирает Б3
А выбирает А1	+3	−2	+2
А выбирает А2	−1	+ 0	+4
А выбирает А3	−4	−3	+1

Следующий пример игры с нулевой суммой, в которой A и B делают одновременные ходы, иллюстрирует максиминные решения. Предположим, что у каждого игрока есть три варианта выбора, и рассмотрим матрицу выигрышей для игрока А, отображаемую в таблице («Матрица выигрышей для игрока А»). Предположим, что матрица выигрышей для B — это та же самая матрица с обратными знаками (т. е. если выбраны варианты A1 и B1, то B платит 3 игроку A ). Тогда максиминный выбор для A — это A2, поскольку наихудший возможный результат — это необходимость заплатить 1, тогда как простой максиминный выбор для B — это B2, поскольку худшим возможным результатом будет отсутствие выплаты. Однако это решение нестабильно, поскольку если B считает, что A выберет A2, то B выберет B1, чтобы получить 1; тогда, если A считает, что B выберет B1, тогда A выберет A1, чтобы получить 3; и тогда B выберет B2; и в конце концов оба игрока осознают сложность выбора. Поэтому необходима более стабильная стратегия.

Некоторые варианты выбора доминируют над другими и могут быть исключены: А не выберет А3, поскольку либо А1, либо А2 дадут лучший результат, независимо от того, что выберет Б ; B не выберет B3, поскольку некоторые смеси B1 и B2 дадут лучший результат, независимо от того, что A. выберет

Игрок А может избежать необходимости уплачивать ожидаемый платеж на сумму более ⁠ 1/3 с вероятностью ⁠ выбрав A1 ⁠ 1/6 A2 с ⁠ и вероятностью ⁠ 5/6 A ⁠ : игрока Ожидаемый выигрыш для составит 3 × ⁠ 1 /  6  ⁠ − 1 × ⁠ 5 /  6  ⁠ = ⁠− + 1/3 B −2 ⁠   в случае, если выбрал B1 и × ⁠ 1 / 6  ⁠ + 0 × ⁠ 5 /  6  ⁠ = ⁠− + 1/3 выбрал B ⁠   в случае, если B2 . Аналогичным образом, B может обеспечить ожидаемый выигрыш в размере, по крайней мере, ⁠ 1/3 , ⁠ , независимо от того, что выберет A используя рандомизированную стратегию выбора B1 с вероятностью ⁠ 1/3 B2 с ⁠ и вероятностью ⁠ 2 / 3 ⁠ . Эти смешанные минимаксные стратегии не могут быть улучшены и теперь стабильны.

Максимин

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

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

В повторяющихся играх

Минимаксные значения очень важны в теории повторяющихся игр . Одна из центральных теорем этой теории, народная теорема , опирается на минимаксные значения.

Комбинаторная теория игр

В комбинаторной теории игр существует минимаксный алгоритм решения игр.

Простая крестики версия минимаксного алгоритма , изложенная ниже, касается таких игр, как -нолики , где каждый игрок может выиграть, проиграть или сыграть вничью. Если игрок А может выиграть за один ход, его лучший ход — это выигрышный ход. Если игрок Б знает, что один ход приведет к ситуации, когда игрок А сможет выиграть за один ход, а другой ход приведет к ситуации, когда игрок А может в лучшем случае сыграть вничью, то лучшим ходом игрока Б будет тот, который приведет к рисовать. В конце игры легко увидеть, какой ход является «лучшим». Алгоритм минимакса помогает найти лучший ход, действуя в обратном направлении от конца игры. На каждом этапе предполагается, что игрок А пытается максимизировать шансы на победу А, в то время как на следующем ходу игрок Б пытается минимизировать шансы на победу А (т. е. максимизировать собственные шансы на победу Б).

Минимаксный алгоритм с поочередными ходами

алгоритм Минимаксный ^[5] — это рекурсивный алгоритм выбора следующего хода в игре с участием n игроков , обычно в игре с двумя игроками. Значение связано с каждой позицией или состоянием игры. Это значение вычисляется с помощью функции оценки позиции и показывает, насколько хорошо для игрока было бы достичь этой позиции. Затем игрок делает ход, который максимизирует минимальное значение позиции, возникающей в результате возможных последующих ходов противника. Если настала игрок очередь хода игрока A, A присваивает значение каждому из своих допустимых ходов.

Возможный метод распределения состоит в присвоении определенного выигрыша для A как +1, а для B как -1. Это приводит к комбинаторной теории игр , разработанной Джоном Х. Конвеем . Альтернативой является использование правила, согласно которому, если результатом хода является немедленный выигрыш для A , ему присваивается положительная бесконечность, а если это немедленный выигрыш для B , — отрицательная бесконечность. Ценность любого другого хода для A — это максимум значений, полученных в результате каждого из B. возможных ответов По этой причине A называется максимизирующим игроком , а B — минимаксным игроком , отсюда и название минимаксного алгоритма . Приведенный выше алгоритм присвоит значение положительной или отрицательной бесконечности любой позиции, поскольку значение каждой позиции будет значением некоторой окончательной выигрышной или проигрышной позиции. Часто это вообще возможно только в самом конце сложных игр, таких как шахматы или го , поскольку с вычислительной точки зрения невозможно заглянуть вперед до завершения игры, кроме как ближе к концу, и вместо этого позициям присваиваются конечные значения. как оценки степени уверенности в том, что они приведут к победе того или иного игрока.

Это можно расширить, если мы сможем предоставить эвристическую функцию оценки, которая присваивает значения нефинальным состояниям игры, не рассматривая все возможные последующие полные последовательности. Затем мы можем ограничить минимаксный алгоритм просмотром только определенного количества ходов вперед. Это число называется «прогнозированием» и измеряется в « слоях ». Например, шахматный компьютер Deep Blue (первый, кто обыграл на тот момент действующего чемпиона мира Гарри Каспарова ) просматривал вперед как минимум 12 ходов, а затем применил эвристическую функцию оценки. ^[6]

Алгоритм можно рассматривать как исследование узлов дерева игры . Эффективный каждого узла (т. е. среднее количество допустимых ходов коэффициент ветвления дерева — это среднее количество дочерних элементов в позиции). Количество узлов, подлежащих исследованию, обычно увеличивается экспоненциально с увеличением количества слоев (оно меньше экспоненциального при оценке вынужденных перемещений или повторяющихся позиций). Таким образом, количество узлов, которые необходимо исследовать для анализа игры, примерно равно коэффициенту ветвления, возведенному в степень числа ходов. Поэтому непрактично полностью анализировать такие игры, как шахматы, с использованием минимаксного алгоритма.

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

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

Псевдокод

Псевдокод минимаксного алгоритма с ограниченной глубиной приведен ниже.

function minimax(node, depth, maximizingPlayer) is    if depth = 0 or node is a terminal node then        return the heuristic value of node    if maximizingPlayer then        value := −∞        for each child of node do            value := max(value, minimax(child, depth − 1, FALSE))        return value    else (* minimizing player *)        value := +∞        for each child of node do            value := min(value, minimax(child, depth − 1, TRUE))        return value

(* Initial call *)minimax(origin, depth, TRUE)

Функция минимакс возвращает эвристическое значение для конечных узлов (терминальных узлов и узлов на максимальной глубине поиска). Неконечные узлы наследуют свое значение от дочернего листового узла. Эвристическая ценность — это оценка, измеряющая благосклонность узла для максимизирующего игрока. Следовательно, узлы, приводящие к благоприятному результату, например выигрышу, для максимизирующего игрока, имеют более высокие баллы, чем узлы, более благоприятные для минимизирующего игрока. Эвристическое значение для конечных узлов (окончания игры) — это очки, соответствующие победе, проигрышу или ничьей для максимизирующего игрока. Для нетерминальных конечных узлов при максимальной глубине поиска функция оценки оценивает эвристическое значение узла. Качество этой оценки и глубина поиска определяют качество и точность конечного минимаксного результата.

Minimax рассматривает в своем коде двух игроков (максимизирующего игрока и минимизирующего игрока) отдельно. На основании наблюдения, что $\ \max(a,b)=-\min(-a,-b)\ ,$ минимакс часто можно упростить до алгоритма негамакс .

Пример

Предположим, что в игре имеется максимум два возможных хода на игрока за ход. Алгоритм генерирует дерево справа, где кружки представляют ходы игрока, запускающего алгоритм ( максимизация игрока ), а квадраты представляют ходы противника ( минимизация игрока ). Из-за ограничения вычислительных ресурсов, как объяснялось выше, дерево ограничено просмотром вперед на 4 хода.

Алгоритм оценивает каждый листовой узел с помощью эвристической функции оценки и получает показанные значения. Ходам, при которых выигрывает максимизирующий игрок, присваивается положительная бесконечность, а ходам, приводящим к победе минимизирующего игрока, присваивается отрицательная бесконечность. На уровне 3 алгоритм выберет для каждого узла наименьшее из значений дочернего узла и назначит его тому же узлу (например, узел слева выберет минимум между «10» и «+∞», поэтому присвоив себе значение «10»). Следующий шаг на уровне 2 состоит в выборе для каждого узла наибольшего из значений дочернего узла . И снова значения присваиваются каждому родительскому узлу . Алгоритм продолжает поочередно оценивать максимальные и минимальные значения дочерних узлов, пока не достигнет корневого узла , где он выбирает ход с наибольшим значением (представленным на рисунке синей стрелкой). Это ход, который должен сделать игрок, чтобы минимизировать максимально . возможные потери .

Минимакс для индивидуальных решений

Минимакс перед лицом неопределенности

Теория минимакса была распространена на решения, в которых нет другого игрока, но последствия которых зависят от неизвестных фактов. Например, решение о разведке полезных ископаемых влечет за собой затраты, которые будут потрачены впустую, если полезных ископаемых нет, но принесут значительную выгоду, если они есть. Один из подходов состоит в том, чтобы рассматривать это как игру против природы (см. «Ход по природе ») и, используя образ мышления, аналогичный закону Мерфи или сопротивлению , принять подход, который минимизирует максимально ожидаемые потери, используя те же методы, что и в нуле для двух человек. -игры с суммой.

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

Минимаксный критерий в статистической теории принятия решений

В классической статистической теории принятия решений у нас есть оценщик $\ \delta \$ который используется для оценки параметра $\ \theta \in \Theta \ .$ Мы также предполагаем функцию риска $\ R(\theta ,\delta )\ .$ обычно указывается как интеграл от функции потерь . В этих рамках $\ {\tilde {\delta }}\$ называется минимаксом, если он удовлетворяет условию

\sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\ \sup _{\theta }\ R(\theta ,\delta )\ .

Альтернативным критерием в рамках теории принятия решений является оценка Байеса при наличии априорного распределения. $\Pi \ .$ Оценщик является байесовским, если он минимизирует средний риск.

\int _{\Theta }R(\theta ,\delta )\ \operatorname {d} \Pi (\theta )\ .

Невероятностная теория принятия решений

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

Кроме того, минимакс требует только порядкового измерения (чтобы результаты сравнивались и ранжировались), а не интервальных измерений (чтобы результаты включали «насколько лучше или хуже»), и возвращает порядковые данные, используя только смоделированные результаты: вывод минимаксного анализа : «Эта стратегия является минимаксной, поскольку наихудший случай (результат) менее плох, чем любая другая стратегия». Сравните с анализом ожидаемой стоимости, вывод которого имеет вид: «Эта стратегия дает $ℰ$ ( $X$ ) = $n$ ». Таким образом, Minimax можно использовать с порядковыми данными и он может быть более прозрачным.

Минимакс в политике

Концепцию голосования « меньшего зла » (LEV) можно рассматривать как форму минимаксной стратегии, при которой избиратели, столкнувшись с двумя или более кандидатами, выбирают того, кого они считают наименее вредным или «наименьшим злом». Для этого «голосование не следует рассматривать как форму личного самовыражения или морального суждения, направленную в отместку кандидатам от основных партий, которые не отражают наши ценности, или как коррумпированную систему, предназначенную для ограничения выбора теми, которые приемлемы для корпоративной элиты». », а скорее как возможность уменьшить ущерб или потери. ^[7]

Максимин в философии

В философии термин «максимин» часто используется в контексте Джона Ролза » «Теории справедливости , где он ссылается на него в контексте « Принципа различия» . ^[8] Ролз определил этот принцип как правило, которое гласит, что социальное и экономическое неравенство должно быть организовано так, чтобы «оно приносило наибольшую пользу наименее обеспеченным членам общества». ^[9]^[10]

См. также

Ссылки

^ Бахус, Баруа (январь 2013 г.). Провинциальный индекс здравоохранения за 2013 г. (PDF) (Отчет). Институт Фрейзера. п. 25.
^ Профессор Рэймонд Флад. Тьюринг и фон Нейман (видео). Грешем-Колледж – через YouTube .
^ Jump up to: ^а ^б Машлер, Майкл; Солан, Эйлон ; Замир, Шмуэль (2013). Теория игр . Издательство Кембриджского университета . стр. 176–180. ISBN 9781107005488 .
^ Осборн, Мартин Дж.; Рубинштейн, А. (1994). Курс теории игр (печатная ред.). Кембридж, Массачусетс: MIT Press. ISBN 9780262150415 .
^ Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход (4-е изд.). Хобокен: Пирсон. стр. 149–150. ISBN 9780134610993 . LCCN 20190474 .
^ Сюй, Фэн-Сюн (1999). «Шахматные гроссмейстерские фишки IBM Deep Blue» . IEEE микро . 19 (2). Лос-Аламитос, Калифорния, США: Компьютерное общество IEEE: 70–81. дои : 10.1109/40.755469 . Во время матча 1997 года программный поиск расширил поиск примерно до 40 слоев вдоль силовых линий, хотя нерасширенный поиск достиг всего около 12 слоев.
^ Ноам Хомский и Джон Халле, « Краткий обзор из восьми пунктов для LEV (меньшее злое голосование) », New Politics , 15 июня 2016 г.
^ Ролз, Дж. (1971). Теория справедливости . п. 152.
^ Эрроу, К. (май 1973 г.). Ролза «Некоторые ординалистско-утилитаристские заметки по теории справедливости » . Журнал философии . 70 (9): 245–263. дои : 10.2307/2025006 . JSTOR 2025006 .
^ Харсаньи, Дж. (июнь 1975 г.). «Может ли принцип максимина служить основой морали? Критика теории Джона Ролза» (PDF) . Американский обзор политической науки . 69 (2): 594–606. дои : 10.2307/1959090 . JSTOR 1959090 . S2CID 118261543 .

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

«Принцип минимакса» , Математическая энциклопедия , EMS Press , 2001 [1994]
«Смешанные стратегии» . Cut-the-knot.org . Учебная программа: Игры. — Апплет визуализации
«Принцип максимина» . Словарь философских терминов и названий . Архивировано из оригинала 7 марта 2006 г.
«Минимакс» . Словарь алгоритмов и структур данных . США НИСТ .

[1] Бахус, Баруа (январь 2013 г.). Провинциальный индекс здравоохранения за 2013 г. (PDF) (Отчет). Институт Фрейзера. п. 25.

[2] Профессор Рэймонд Флад. Тьюринг и фон Нейман (видео). Грешем-Колледж – через YouTube .

[ZMS2013-3] Jump up to: ^а ^б Машлер, Майкл; Солан, Эйлон ; Замир, Шмуэль (2013). Теория игр . Издательство Кембриджского университета . стр. 176–180. ISBN 9781107005488 .

[Osborne-4] Осборн, Мартин Дж.; Рубинштейн, А. (1994). Курс теории игр (печатная ред.). Кембридж, Массачусетс: MIT Press. ISBN 9780262150415 .

[5] Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход (4-е изд.). Хобокен: Пирсон. стр. 149–150. ISBN 9780134610993 . LCCN 20190474 .

[6] Сюй, Фэн-Сюн (1999). «Шахматные гроссмейстерские фишки IBM Deep Blue» . IEEE микро . 19 (2). Лос-Аламитос, Калифорния, США: Компьютерное общество IEEE: 70–81. дои : 10.1109/40.755469 . Во время матча 1997 года программный поиск расширил поиск примерно до 40 слоев вдоль силовых линий, хотя нерасширенный поиск достиг всего около 12 слоев.

[7] Ноам Хомский и Джон Халле, « Краткий обзор из восьми пунктов для LEV (меньшее злое голосование) », New Politics , 15 июня 2016 г.

[Rawls-1971-8] Ролз, Дж. (1971). Теория справедливости . п. 152.

[9] Эрроу, К. (май 1973 г.). Ролза «Некоторые ординалистско-утилитаристские заметки по теории справедливости » . Журнал философии . 70 (9): 245–263. дои : 10.2307/2025006 . JSTOR 2025006 .

[10] Харсаньи, Дж. (июнь 1975 г.). «Может ли принцип максимина служить основой морали? Критика теории Джона Ролза» (PDF) . Американский обзор политической науки . 69 (2): 594–606. дои : 10.2307/1959090 . JSTOR 1959090 . S2CID 118261543 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v т и Структуры данных и алгоритмы
Data structures	Array Associative array Binary search tree Fenwick tree Graph Hash table Heap Linked list Queue Segment tree Stack String Tree Trie
Algorithms	Backtracking Binary search Breadth-first search Brute-force search Depth-first search Divide and conquer Dynamic programming Graph traversal Fold Greedy Hash function Minimax Online Randomized Recursion Root-finding Sorting Streaming Sweep line String-searching Topological sorting
List of data structures List of algorithms

v т и Темы теории игр
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Electronic mail game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Miscellaneous	Alpha–beta pruning Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons

v т и Теория принятия решений
Decisions	Expected utility hypothesis Intertemporal choice
Concepts	Decision-matrix method Decision matrix Expected utility Strategic dominance Minimax Leximin Principle of indifference Risk Allais paradox Ellsberg paradox St. Petersburg paradox Heuristics in judgment and decision-making Probability theory Bayesian epistemology Risk aversion Game theory Social choice theory Causal decision theory Emotional choice theory Evidential decision theory