WikiDer > Модель Вальдса Максимина - Википедия

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

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

Определение

Общая модель максимина Вальда выглядит следующим образом:

${ displaystyle v ^ {*}: = max _ {d in D} min _ {s in S (d)} f (d, s)}$

куда ${ displaystyle D}$ обозначает пространство решений; ${ Displaystyle S (d)}$ обозначает набор состояний, связанных с решением ${ displaystyle d}$ и ${ displaystyle f (d, s)}$ обозначает выигрыш (результат), связанный с решением ${ displaystyle d}$ и государство ${ displaystyle s}$.

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

Вышеупомянутая модель является классический формат модели максимина Вальда. Есть эквивалент математическое программирование (MP) формат:

${ displaystyle v ^ {*}: = max _ {d in D, , z in mathbb {R}} {z: z leq f (d, s), forall s in S (г) }}$

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

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

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

называется уровень безопасности решения ${ displaystyle d}$.

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

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

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

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

История

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

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

Пример

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

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

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

Оптимальное решение - (красный) точка перевала ${ Displaystyle (х, у) = (0,0)}$.

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

Есть много случаев, когда удобно «организовать» модель Maximin / Minimax в виде «таблицы». Согласно соглашению, строки таблицы представляют решения, а столбцы представляют состояния.

Пример

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

Добавление Худшая выплата столбец и Наихудшая выплата столбца в таблицу выплат, получаем

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

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

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

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

Savage's минимаксная модель сожаления^[11] представляет собой приложение минимаксной модели Уолда к «сожалениям», связанным с выплатами. Его можно сформулировать так:

${ displaystyle min _ {d in D} max _ {s in S} r (d, s)}$

куда

${ displaystyle r (d, s): = max _ {d , ' in D} f (d ,', s) -f (d, s)}$

сожаление о расплате ${ displaystyle f (d, s)}$ связанный с парой (решение, состояние) ${ displaystyle (d, s)}$.

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

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

Пример

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

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

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

куда ${ displaystyle dist (d, s)}$ обозначает расстояние ${ displaystyle s}$ из ${ displaystyle d}$. Обратите внимание, что в этой задаче ${ Displaystyle S (d)}$ не зависит от ${ displaystyle d}$.

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

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

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

Замаскированные модели Максимина

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

Пример

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

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

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

${ Displaystyle max _ {Y substeq X} {| Y |: g (x) leq 0, forall x in Y }.}$

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

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

Модели с ограничениями максимина

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

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

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

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

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

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

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

Пример

Рассмотрим простой случай, когда есть два решения, d 'и d ", и где S (d') = S (d") = [a, b]. Тогда модель Максимина выглядит следующим образом:

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

Теперь рассмотрим пример, показанный

Отметим, что хотя выигрыш, связанный с решением d ', больше, чем выигрыш, связанный с решением d "по большей части пространства состояний S = [a, b], наилучший наихудший случай согласно модели Вальда обеспечивается решением d". Следовательно, согласно модели Вальда, решение d "лучше, чем решение d '.

Алгоритмы

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

Пример

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

${ Displaystyle { begin {align} 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 {align}}}$

куда ${ Displaystyle f_ {s} (d) Equiv f (d, s)}$.

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

Рекомендации