Постановка задачи в дискретном случае. Множество Парето.

Биматричная игра задана матрицей вида (1.3):

Необходимо построить множество паретооптимальных решений исходя из условий

В случае, если значения критериальных функций V и W заданы в дискретном виде, множество W представляет собой конечное множество точек (решений), каждая из которых определяется парой стратегий Непрерывная граница множества W отсутствует, идеальную точку в общем случае найти невозможно. Решить задачу можно двумя способами:

1) Попарное сравнение всех исходов (решений) матрицы (1.3) по следующему правилу: если W(A_i, B_k)> W(A_s, B_p) и V(A_i, B_k) V(A_s, B_p) или W(A_i, B_k) W(A_s, B_p) и V(A_i, B_k)> V(A_s, B_p), то решение (A_s, B_p) из дальнейшего рассмотрения исключается, как заведомо не являющееся паретооптимальным решением. После завершения всех парных сравнений будет сформировано множество паретооптимальных решений, из которого ЛПР выбирает наилучшее, по его мнению, решение исходя из своего опыта и интуиции (заметим, что наша задача ограничивается построением множества паретооптимальных решений). В связи с тем, что этот способ является очень трудоемким, так как он фактически сводится к полному перебору попарных сравнений всех решений матрицы вида (1.3), целесообразно использовать графический способ.

2) Графический способ, который предполагает нанесение на плоскость (W, V) точек, соответствующих исходам (решениям) при выборе пар стратегий матрицы вида (1.3). В множество паретооптимальных решений включаются решения, которым соответствуют крайние точки на плоскости (W, V) в направлениях "север", "восток" либо "северо-восток".

Рассмотрим реализацию графического способа с помощью следующего примера.

Пример 3.2. (дискретный случай)

Игра задана с помощью таблицы 2 (пример 2.1). Требуется:

а) Построить множество паретооптимальных решений.

б) Провести сравнительный анализ результатов данного примера с результатами, полученными в примере 2.1.

Р е ш е н и е

Решим задачу, используя графический способ.

а). Пронумеруем пары исходов игроков А и Б следующим образом:

(1) - (V₁₁, W₁₁)=(2, 4); (7) - (V₂₃, W₂₃)=(2, 6);

(2) - (V₁₂, W₁₂)=(7, 5); (8) - (V₂₄, W₂₄)=(7, 5);

(3) - (V₁₃, W₁₃)=(-3, 3); (9) - (V₃₁, W₃₁)=(6, 1);

(4) - (V₁₄, W₁₄)=(6, 2); (10) - (V₃₂, W₃₂)=(6, 4);

(5) - (V₂₁, W₂₁)=(5, 9); (11) - (V₃₃, W₃₃)=(10, 6);

(6) - (V₂₂, W₂₂)=(4, 2); (12) - (V₃₄, W₃₄)=(8, 7).

б). На плоскости (V, W) нанесем точки (1),…, (12), представленные на рисунке 3.9.

в). В данном дискретном случае границу Парето представляют три крайние точки в направлениях «север», «восток», «северо-восток» - (11), (12), (5). Таким образом, построим множество Парето:

{(А₃, В₃), (А₃, В₄), (А₂, В₁)} (3.11)

с оценками исходов, соответственно

{(10, 6), (8, 7), (5, 9)}.

Сравнивая попарно решения (3.11), убедимся, что ни одно решение не может быть улучшено одновременно по обоим значениям функций V и W:

V₃₃=10 > V₃₄=8, но W₃₃=6< W₃₄=7,

V₃₃=10> V₂₁=5, но W₃₃=6< W₂₁=9,

V₃₄=8> V₂₁=5, но W₃₄=7< W₂₁=9.

г). Сравним множество паретооптимальных решений (3.11) с множеством (2.4) устойчивых решений {(А₁, В₂) и (А₃, B₄)}, полученных в примере 2.1. Решение (А₃, B₄) с оценками исходов (V₃₄=8, W₃₄=7) является одновременно и устойчивым, и паретооптимальным. Очевидно, это решение и может быть рекомендовано ЛПР для окончательного выбора.

Замечание. Отличие ситуации равновесия от ситуации, оптимальной по Парето, состоит в следующем:

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

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

Предлагаю ознакомиться с аналогичными статьями: