Примеры функций выбора

1. Выбор по скалярному критерию.

На множестве вариантов Ω определена функция f:Ω→ R – скалярный критерий. Из предъявленного множества вариантов X⊂Ω выбираются те, для которых критерий имеет максимальное значение:

C(X)={x∈X | ∀x’∈X f(x)≥f(x’)}.

Если функция f(x) принимает в точке x свое максимальное значение, принято писать x = arg max f(x). С использованием этого обозначения предыдущую формулу можно переписать так: C(X)={x∈X | x = arg max f(x)}.

2. Выбор по Парето.

На множестве вариантов Ω задан набор критериев f_i(x), i=1,2,…,m. Сопоставляя каждому варианту x вектор

f(x) = (f₁(x), f₂(x), …, f_m(x)),

получаем отображение f:Ω→ R ^m , называемое векторным критерием. Будем говорить, что y предпочтительнее x, и писать f(x)<f(y), если f₁(x)≤f₁(x), f₂(x))≤f₂(y), … f_m(x)≤f_m(y), причем хотя бы одно из неравенств строгое. Из предъявленного множества вариантов X выбираются те, для которых в X отсутствуют более предпочтительные варианты:

C(X) = {x∈X | (∃y∈X f(x)<f(y))}.

3. Турнирный выбор.

На множестве

ΩЧΩ = {(x,y) | x, y∈Ω}

задана функция f(x,y), принимающая значения 0; 1 и 2, такая, что f(x,y)+f(y,x)=2 для любых x,y∈Ω, x≠y. Кроме того, мы считаем, что f(x,x)=0 для любого x. Можно считать, что функция f(x,y) представлена в виде турнирной таблицы, в которой значение f(x,y) располагается в строке x и столбце y. При x≠y значение 2 соответствует победе (x над y), значение 0 – поражению, значение 1 – ничьей. Из предъявляемого множества вариантов X выбираются «победители» турнира, то есть варианты, набравшие максимальное число очков. Более точно, для X⊂Ω и x∈X пусть

h_X(x)=Σ_y∈Xf(x,y)

– число очков, набранных вариантом x. Тогда

C(X) = {x∈X | x = arg max h_X(x)}.

Примеры 1 и 2 иллюстрируют общие способы построения функции выбора по отношению, заданному на множестве вариантов, которые мы рассмотрим ниже.

Пусть R – бинарное отношение на множестве вариантов Ω. Будем писать xRy, если (x,y)∈R. Для X⊂Ω положим

C_R(X)={x∈X | ∀y∈X xRy};

C^R(X)={ x∈X | ∀y∈X (yRx)}.

В случае скалярного критерия f:Ω→R полагаем xRy, если f(x)≥f(y). Тогда C_R(X) – это выбор по скалярному критерию. В случае векторного критерия f:Ω→R^m полагаем yRx, если f(x)<f(y) (y не хуже, чем x по любому критерию, а по одному из них превосходит x). Тогда, по закону де Моргана для предикатов, C^R(X) – это выбор по Парето.

Между функциями вида C_R(X) и C^R(X) имеется тесная связь. Чтобы ее описать, введем понятие двойственного отношения. Пусть R – произвольное бинарное отношение на Ω. Двойственное к R отношение R^d определяется формулой

1−=RRd.

Таким образом,

xR^dy⇔yRx.

Например, если R – это отношение нестрогого порядка ≤ на множестве действительных чисел, то R^d – это отношение строгого порядка >:

x>y ⇔ (y≤x).

Ясно, что

R^dd=R.

Из формул де Моргана следует, что

(R∩S)^d=R^d∪S^d , (R∪S)^d=R^d∩S^d.

Непосредственно из определений вытекает, что

)()(XCXCdRR=; C)()(XCXdRR=.

Функцию выбора C^R называют функцией блокировки по отношению R. Функции выбора вида C^R будем называть нормальными. Поскольку любая функция выбора вида C_R является функцией блокировки по двойственному отношению, любая такая функция нормальна.

Не все функции выбора нормальны.

Пример. Рассмотрим следующую функцию выбора на двухэлементном множестве Ω={x,y}:

C({x})={x}; C({y})=∅; C({x,y})={y}.

Покажем, что она не является нормальной. Предположим противное, то есть, что C=C^R – это функция блокировки по некоторому отношению R. Так как C({y})=∅, то yRy. Но y∈C({x,y}) означает, что (xRy)∧(yRy), откуда yRy. Полученное противоречие показывает, что предположение о нормальности функции неверно.􀀀

Не нашли, что искали? Воспользуйтесь поиском: