Максиминная модель Уолда

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

Оно также известно под множеством других названий, таких как правило максимина Уолда, принцип максимина Уолда, парадигма максимина Уолда и критерий максимина Уолда. Часто « минимакс вместо «максимина» используется ».

Определение

Эта модель представляет собой игру для двоих, в которой $\max$ игрок играет первым. В ответ второй игрок выбирает худшее состояние из $S(d)$ , а именно состояние в $S(d)$ это минимизирует выигрыш $f(d,s)$ над $s$ в $S(d)$ . Во многих приложениях второй игрок представляет неопределенность. Однако существуют максиминные модели, которые полностью детерминированы.

Вышеупомянутая модель представляет собой классический формат максимин-модели Вальда. Существует эквивалентный формат математического программирования (МП):

где $\mathbb {R}$ обозначает реальную линию.

Как и в теории игр , наихудший выигрыш связан с принятием решения. $d$ , а именно

v(d):=\min _{s\in S(d)}f(d,s)\ ,\ d\in D

называется уровнем безопасности решения $d$ .

Минимаксный вариант модели получается путем замены позиций $\max$ и $\min$ операции в классическом формате:

v^{\circ }:=\min _{d\in D}\max _{s\in S(d)}f(d,s).

Эквивалентный формат MP выглядит следующим образом:

v^{\circ }:=\min _{d\in D,\,z\in \mathbb {R} }\{z:z\geq f(d,s),\forall s\in S(d)\}

История

Вдохновленный теорией игр, Абрахам Вальд разработал эту модель. ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]} как подход к сценариям, в которых есть только один игрок (лицо, принимающее решения). Игрок 2 демонстрирует мрачный подход к неопределенности. В максиминной модели Уолда игрок 1 ( $\max$ игрок) играет первым, а игрок 2 ( $\min$ игрок) знает решение игрока 1, когда тот выбирает свое решение. Это существенное упрощение классической игры с нулевой суммой для двоих , в которой два игрока выбирают свои стратегии, не зная выбора другого игрока. Игра максимин-модели Вальда также является игрой двух лиц с нулевой суммой , но игроки выбирают последовательно.

С появлением современной теории принятия решений в 1950-х годах эта модель стала ключевым компонентом в формулировке невероятностных моделей принятия решений в условиях серьезной неопределенности. ^{[ 4 ]}^{[ 5 ]} Он широко используется в различных областях, таких как теория принятия решений , теория управления , экономика , статистика , робастная оптимизация , исследование операций , философия и т. д. ^{[ 6 ]}^{[ 7 ]}

Пример

Одним из наиболее известных примеров модели максимин/минимакс является

\min _{x\in \mathbb {R} }\max _{y\in \mathbb {R} }\ \{x^{2}-y^{2}\}

где $\mathbb {R}$ обозначает реальную линию. Формально мы можем установить $D=S(d)=\mathbb {R}$ и $f(d,s)=d^{2}-s^{2}$ . Картина вот эта

Оптимальным решением является (красная) седловая точка . $(x,y)=(0,0)$ .

Таблицы решений

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

Пример

Анри собирается на прогулку. Может светить солнце, а может идти дождь. Должен ли Анри носить зонтик? Анри не любит носить с собой зонтик, но еще больше он не любит промокать. Его « матрица выигрышей », рассматривающая это как игру Максимина, противопоставляющую Анри природе, выглядит следующим образом.

	Солнце	Дождь
Нет зонтика	5	−9
Зонтик	1	−5

Добавляя столбцы «Худший выигрыш» и « Лучший худший выигрыш» к таблице выигрышей, мы получаем

	Солнце	Дождь	Худшая выплата	Лучшая худшая выплата
Нет зонтика	5	−9	−9
Зонтик	1	−5	−5	−5

Худший случай, если Анри выйдет без зонтика, определенно хуже, чем (лучший) худший случай с зонтиком. Поэтому Анри берет с собой зонтик.

Вариации на тему

За прошедшие годы было разработано множество связанных моделей, главным образом для того, чтобы смягчить пессимистический подход, продиктованный ориентацией модели на наихудший случай. ^{[ 4 ]}^{[ 5 ]}^{[ 8 ]}^{[ 9 ]}^{[ 10 ]} Например,

Минимаксное сожаление Сэвиджа

Сэвиджа Минимаксная модель сожаления ^{[ 11 ]} связано с сожалениями о выплате.

Детерминированные модели

Наборы состояний $S(d),d\in D,$ не обязательно представляет неопределенность. Они могут представлять (детерминированные) изменения значения параметра.

Пример

Позволять $D$ быть конечным множеством, представляющим возможные местоположения «нежелательного» общественного объекта (например, свалки мусора), и пусть $S$ обозначают конечный набор мест в окрестностях планируемого объекта, представляющих существующие жилища.

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

\max _{d\in D}\min _{s\in S}dist(d,s)

где $dist(d,s)$ обозначает расстояние $s$ от $d$ . Обратите внимание, что в этой задаче $S(d)$ не меняется в зависимости от $d$ .

В тех случаях, когда желательно жить рядом с объектом, целью может быть минимизация максимального расстояния от объекта. Это дает следующую минимаксную задачу:

\min _{d\in D}\max _{s\in S}dist(d,s)

Это общие проблемы с размещением объектов .

Модели Maximin в маскировке

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

Пример

Рассмотрим следующую проблему:

Учитывая конечное множество $X$ и вещественнозначная функция $g$ на $X$ , найдите наибольшее подмножество $X$ такой, что $g(x)\leq 0$ для каждого $x$ в этом подмножестве.

Максиминная формулировка этой задачи в формате MP выглядит следующим образом:

\max _{Y\subseteq X}\ \{|Y|:g(x)\leq 0,\forall x\in Y\}.

Общие проблемы этого типа возникают при анализе устойчивости. ^{[ 12 ]}^{[ 13 ]}

Было показано, что модель радиуса стабильности и модель устойчивости информационного разрыва являются простыми примерами максимин-модели Вальда. ^{[ 14 ]}

Ограниченные максиминные модели

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

v^{*}:=\max _{d\in D}\min _{s\in S(d)}\ \{f(d,s):g(d,s)\leq 0,\forall s\in S(d)\}.

Его эквивалентный формат MP выглядит следующим образом:

v^{*}:=\max _{d\in D,\,z\in \mathbb {R} }\{z:z\leq f(d,s),g(d,s)\leq 0,\forall s\in S(d)\}.

Такие модели очень полезны для надежной оптимизации .

Цена надежности

Одной из «слабостей» модели Maximin является то, что за обеспечиваемую ею надежность приходится платить . ^{[ 10 ]} Действуя осторожно, модель Максимина склонна генерировать консервативные решения, цена которых может быть высокой. Следующий пример иллюстрирует эту важную особенность модели.

Пример

Предположим, есть два варианта: $x'$ и ⁠. $x''$ ⁠ , и где $S(x')=S(x'')=[a,b]$ . Тогда модель выглядит следующим образом:

\max _{d\in D}\min _{s\in S(d)}f(d,s)=\max _{d\,',d\,''}\ \min _{a\leq s\leq b}f(d,s)=\max \ \{\min _{a\leq s\leq b}f(d\,',s),\min _{a\leq s\leq b}f(d\,'',s)\}

Алгоритмы

Универсальных алгоритмов решения максиминных задач не существует. Некоторые проблемы решить очень просто, другие очень сложно. ^{[ 9 ]}^{[ 10 ]}^{[ 15 ]}^{[ 16 ]}

Пример

Рассмотрим случай, когда переменная состояния является «индексом», например, пусть $S(d)=\{1,2,\dots ,k\}$ для всех $d\in D$ . Соответствующая максиминная задача тогда выглядит следующим образом:

{\begin{aligned}\max _{d\in D}\min _{s\in S(d)}f(d,s)&=\max _{d\in D}\min _{1\leq s\leq k}\{f_{1}(d),\dots ,f_{k}(d)\}\\&=\max _{d\in D,z\in \mathbb {R} }\{z:z\leq f_{s}(d),\forall s=1,2,\dots ,k\}\end{aligned}}

где $f_{s}(d)\equiv f(d,s)$ .

Если $d\in \mathbb {R} ^{n}$ , все функции $f_{s},s=1,2,\dots ,k,$ линейны и $d\in D$ задается системой линейных ограничений на $d$ , то эта проблема является задачей линейного программирования , которую можно решить с помощью алгоритмов линейного программирования, таких как симплекс-алгоритм .

Ссылки

^ Уолд, А. (1939). Вклад в теорию статистического оценивания и проверки гипотез. Анналы математики, 10 (4), 299–326.
^ Уолд, А. (1945). Статистические функции принятия решений, которые минимизируют максимальный риск. Анналы математики, 46 (2), 265–280.
^ Уолд, А. (1950). Статистические функции принятия решений, Джон Уайли, Нью-Йорк.
^ Jump up to: ^а ^б Резник, доктор медицины (1987). Выбор: введение в теорию принятия решений, Университет Миннесоты, Миннеаполис.
^ Jump up to: ^а ^б Френч, С. (1986). Теория принятия решений: введение в математику рациональности, Эллис Хорвуд, Чичестер.
^ Снедович, М. (2007). Искусство и наука моделирования принятия решений в условиях жесткой неопределенности. Принятие решений в производстве и сфере услуг, 1(1-2), 111-136.
^ Снедович, М. (2008). Максимин-модель Уолда: скрытое сокровище! Журнал рискового финансирования, 9 (3), 287–91.
^ Кувелис П. и Ю Г. (1997). Робастная дискретная оптимизация и ее приложения, Клювер, Бостон.
^ Jump up to: ^а ^б Бен-Тал А., Эль Гауи Л., Немировский А. (2009). Надежная оптимизация. Издательство Принстонского университета, Принстон.
^ Jump up to: ^а ^б ^с Берцимас Д. и Сим М. (2004). Цена надежности. Исследование операций, 52(1), 35-53.
^ Сэвидж, Л. (1951). Теория статистического решения. Журнал Американской статистической ассоциации, 46, 55–67.
^ Л. Джо Моффитт, Джон К. Странлунд и Крейг Д. Остин (2008). Надежные протоколы обнаружения сомнительных интродукций инвазивных видов. Журнал экологического менеджмента, 89 (4), 293–299.
^ Джонатан Розенхед, Мартин Элтон, Шив К. Гупта. (1972). Надежность и оптимальность как критерии стратегических решений. Ежеквартальный журнал операционных исследований, 23 (4), 413–431.
^ Снедович, М. (2010). Взгляд с высоты птичьего полета на теорию принятия решений при информационном дефиците. Журнал рискового финансирования, 11(3), 268-283.
^ Римстем, Р. и Р\{укманн, Дж. (1998). Полубесконечное программирование, Клювер, Бостон.
^ Рустем Б. и Хоу М. (2002). Алгоритмы проектирования наихудшего случая и приложения к управлению рисками, Princeton University Press, Принстон.

[wald39-1] Уолд, А. (1939). Вклад в теорию статистического оценивания и проверки гипотез. Анналы математики, 10 (4), 299–326.

[wald45-2] Уолд, А. (1945). Статистические функции принятия решений, которые минимизируют максимальный риск. Анналы математики, 46 (2), 265–280.

[wald50-3] Уолд, А. (1950). Статистические функции принятия решений, Джон Уайли, Нью-Йорк.

[resnik-4] Jump up to: ^а ^б Резник, доктор медицины (1987). Выбор: введение в теорию принятия решений, Университет Миннесоты, Миннеаполис.

[french-5] Jump up to: ^а ^б Френч, С. (1986). Теория принятия решений: введение в математику рациональности, Эллис Хорвуд, Чичестер.

[ms07-6] Снедович, М. (2007). Искусство и наука моделирования принятия решений в условиях жесткой неопределенности. Принятие решений в производстве и сфере услуг, 1(1-2), 111-136.

[ms08-7] Снедович, М. (2008). Максимин-модель Уолда: скрытое сокровище! Журнал рискового финансирования, 9 (3), 287–91.

[kouvelis-8] Кувелис П. и Ю Г. (1997). Робастная дискретная оптимизация и ее приложения, Клювер, Бостон.

[ben-tal09-9] Jump up to: ^а ^б Бен-Тал А., Эль Гауи Л., Немировский А. (2009). Надежная оптимизация. Издательство Принстонского университета, Принстон.

[sim04-10] Jump up to: ^а ^б ^с Берцимас Д. и Сим М. (2004). Цена надежности. Исследование операций, 52(1), 35-53.

[savage51-11] Сэвидж, Л. (1951). Теория статистического решения. Журнал Американской статистической ассоциации, 46, 55–67.

[moffitt08-12] Л. Джо Моффитт, Джон К. Странлунд и Крейг Д. Остин (2008). Надежные протоколы обнаружения сомнительных интродукций инвазивных видов. Журнал экологического менеджмента, 89 (4), 293–299.

[rosenhead72-13] Джонатан Розенхед, Мартин Элтон, Шив К. Гупта. (1972). Надежность и оптимальность как критерии стратегических решений. Ежеквартальный журнал операционных исследований, 23 (4), 413–431.

[MS10-14] Снедович, М. (2010). Взгляд с высоты птичьего полета на теорию принятия решений при информационном дефиците. Журнал рискового финансирования, 11(3), 268-283.

[reemstem98-15] Римстем, Р. и Р\{укманн, Дж. (1998). Полубесконечное программирование, Клювер, Бостон.

[rustem02-16] Рустем Б. и Хоу М. (2002). Алгоритмы проектирования наихудшего случая и приложения к управлению рисками, Princeton University Press, Принстон.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]