Оптимальность по Парето

Вильфредо Парето (1848–1923) – итальянский экономист.

Определение. Будем говорить, что стратегия u Î u доминирует (по Парето) стратегию v Î u, а соответствующий вектор выигрышей (g ¹(u),…, g^m (u)) доминирует вектор (g ¹(v),…, g^m (v)), если для всех i= 1,…, m выполняются неравенства gⁱ (u)³ gⁱ (v), а для некоторого k выполняется строгое неравенство g^k (u)> g^k (v).

Определение. Стратегия u Î u, и соответствующий вектор выигрышей (g ¹(u),…, g^m (u)) называются эффективными (оптимальными по Парето), если не существует стратегии v Î u, которая доминировала бы стратегию u.

Полезно иметь в виду следующую геометрическую интерпретацию данного определения. Вектор выигрышей (g ¹(v),…, g^m (v)) является эффективным, если пересечение множества всех возможных векторов выигрышей  и конуса  состоит из одной точки (g ¹(v),…, g^m (v)).

Множество эффективных векторов выигрышей, вообще говоря, не выпукло.

Пример. Пусть , g ¹(u)= u ₁, g ²(u)= u ₂. Множество эффективных векторов в этой задаче представляет собой четверть окружности  и, следовательно, не выпукло.

Множество эффективных векторов может быть и не замкнутым.

Пример. Пусть ,  

Эффективное множество в этой задаче состоит из двух дуг и одной точки . это множество не замкнуто, поскольку точки (3,1/3) и (1/3,3) являются предельными для него, но не доминируются точкой (3,3).

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

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

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

Определение. Стратегия u Î u, и соответствующий вектор выигрышей (g ¹(u),…, g^m (u)) называются слабо эффективными, если не существует стратегии v Î u, которая сильно доминировала бы стратегию u.

Лемма. Пусть множество u компактно, а функции  непрерывны. Тогда множество слабо эффективных стратегий компактно.

Доказательство. Пусть точка v не является слабо эффективной. Тогда найдется такая точка u, что выполняются неравенства  в силу непрерывности функций gⁱ найдется настолько малая окрестность o точки v, что неравенства  будут выполняться для любой точки w из O, то есть множество точек, которые не являются слабо эффективными, является открытым.

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

Пусть множество u компактно, а функции  непрерывны. Определим по индукции множества . Положим

  .

Лемма. Всякая точка из множества u_m является эффективной.

Доказательство. Допустим противное. Пусть точка v Î u доминирует точку u. тогда найдется такой номер k, что  для i =1,…, k –1, и g^k (u)< g^k (v). Так как точка u Î u ₁, выполняется неравенство g ¹(u)³ g ¹(v), то есть на самом деле g ¹(u)= g ¹(v) и, следовательно, v Î u ₁. Но тогда в силу включения u Î u ₂, имеем g ²(u)³ g ²(v). Продолжая эти рассуждения, получим v Î u_k. но тогда справедливо неравенство g^k (u)³ g^k (v), которое противоречит условию g^k (u)< g^k (v). Полученное противоречие доказывает лемму.

Следствие. Пусть множество u компактно, а функции непрерывны. Тогда множество эффективных точек не пусто.

Доказательство. В силу теоремы Вейерштрасса, непрерывная функция g ¹ достигает своего максимума на компактном множестве u ₀, то есть множество u ₁ не пусто. Множество u ₁ замкнуто, так как является прообразом компактного множества (точки действительно прямой) при непрерывном отображении g ¹. Замкнутое множество u ₁ является подмножеством компактного множества u ₀. поэтому u ₁ компактно.

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