2.4. Механизмы согласованного выбора1

Рассмотрим модель активной системы (АС), состоящей из управляющего органа – центра – и одного управляемого субъекта – активного элемента (АЭ). Стратегией АЭ является выбор действия y  A из конечного множества A = {y₁, y₂, ..., y_n}, стратегией центра является выбор механизма стимулирования, то есть назначение плана x  X  A и выбор функций штрафов _ij за отклонения выбора АЭ y_j от плана x_i и дохода АЭ h_j, i, j  I = {1, 2, ..., n}.

Целевая функция АЭ f_ij, определенная на множестве A  X представляет собой разность между доходом h_j и штрафами _ij. Выбирая при заданном плане и штрафах действие, АЭ стремится максимизировать свою целевую функцию.

Пусть на функции дохода и штрафов наложены следующие ограничения:

(1) l_i  h_i  b_i, i  I,

(2) d_ij  _ij  c_ij, d_ii = c_ii = 0, i, j  I.

Механизм стимулирования (штрафов), при котором АЭ выгодно выполнять планы, назначаемые центром, называется согласованным.

Задача согласованного выбора заключается в ответе на вопрос – существует ли механизм, согласованный на заданном подмножестве X множества A.

Выпишем условия согласованности для множества X в предположении благожелательности АЭ к центру (в случае равенства АЭ выполняет план):

(3) h_i  h_j - _ij, i  J, j  I,

где J  I – множество индексов, соответствующих множеству X.

Преобразуя (3) к h_j - h_j  _ij, i, j  I, получаем, что штрафы следует выбирать как можно большими, то есть _ij = c_ij. Тогда (3) примет вид:

(4) h_j – h_i  c_ij, i  J, j  I.

Пусть j  J, тогда соответствующая часть условий h_j – h_i  c_ij, i  J, j  I, приводится к виду

(5) h_i  h_j - c_ij, i  J, j  I.

Очевидно, следует взять h_j = l_j. Получаем ограничение на выбор h_i:

(6) h_i  g_i =   (l_j – c_ij), i  J.

Обозначим _i = max {l_i; g_i}, i  J.

Итак, задача свелась к определению набора {h_i}, удовлетворяющих следующим условиям:

(7) a_i  h_i  b_i, i  J,

(8) h_j – h_i  c_ij, i, j  J.

Определим полный граф G(X) с q вершинами, где q = |J| – число элементов множества X, и длинами луг c_ij. Задача (7)-(8) является задачей о потенциалах. Из результатов раздела 1.2 следует справедливость следующей теоремы¹.

Теорема 8 [10, 19]. Для разрешимости системы неравенств (7)-(8) необходимо и достаточно отсутствия в графе G(X) контуров отрицательной длины и выполнения условий:

(9) L_ij  a_j – b_i, i, j  J,

где L_ij – длина минимального пути, соединяющего вершину i с вершиной j.

Если функции штрафов неотрицательны, то есть c_ij  0, то граф G(X) не имеет контуров отрицательной длины. Тогда (9) дает необходимые и достаточные условия существования согласованного механизма. Для поиска минимальных или максимальных {h_ij}, обеспечивающих согласованность, достаточно воспользоваться модификацией алгоритма Данцига: выбираем h_i(0) = a_i (соответственно, h_i(0) = b_i, где «0» – номер шага алгоритма) и вычисляем последовательно h_i(q) =   [h_j(q-1) - L_ij] (h_i(q) =   [h_j(q-1) + L_ij]). За конечное число итераций получаем { } ({ }) такие, что  -    L_ij, i, j  J.

Отметим, что не существует системы стимулирования, обеспечивающей согласованность механизма на множестве X с меньшими значениями {h_i}. Интересно также отметить, что решение задачи, если оно есть всегда существует на множестве так называемых сильно согласованных механизмов [14, 30], то есть механизмов, функция штрафов в которых удовлетворяет «неравенству треугольника»: _ij + _jk  _ik, i, j, k  J.

Осталось определить значения h_i, _ij для i, j  J, а также _ij для i  J, j  J и для i  J, j  J. Очевидно, что значения _ij i  J, j  I не влияют на согласованность механизма на множестве J. Значения h_i, i  J можно взять минимальными: h_i = l_i, а _ij для i  J, j  J - максимальными: _ij = c_ij.

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

(10) q_ij  f_ij  r_ij.

Тогда из условий согласованности h_j – h_i  _ij  h_j - q_ij получаем необходимые и достаточные условия: h_i  q_ij, i  J, j  I.

Таким образом, если b_i    q_ij, то задача имеет решение:

(11)  = max [l_i ;   q_ij], i  J,

 = l_i, i  J,

_ij^’ =   - q_ij, i  J, j  I

 - r_ij  _ij^’    - q_ij, i  J, j  I.

В работах [10, 19] рассмотрены обобщения описанной модели на случаи: L-согласованных планов (при которых назначение плана x  X приводит к тому, что АЭ выбирает действие из множества L(x)  A), неопределенности относительно информации о функции дохода АЭ, наличия нескольких взаимосвязанных АЭ.