В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: max&;nbsp;f(X)&;nbsp;= min&;nbsp;g(Y). - Теория игр

Значит и

Вторая теорема двойственности (теорема о дополняющей нежесткости)

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

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

Если

Если

Если

Если

Проверим, какие из ограничений задачи второго игрока превращаются в равенства, а какие в неравенства:

Значит

Подставляем в систему ограничений задачи первого игрока

Полученное оптимальное решение имеет вид:

Перейдем к исходным переменным:

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

В данной задаче такое решение было очевидно еще при анализе матрицы

Имеется точка равновесия (2;1).

Рассматривается корпоративная игра с тремя игроками. Известны значения характеристической функции, определяющие соответственно выигрыши первого, второго и третьего игроков, когда каждый из них играет в одиночку, не кооперируясь ни с кем из других игроков: V(1)=1500; V(2)=1200; V(3)=1000; а также выигрыши, которые они могут обеспечить себе, действуя попарно: V(1,2)=3000; V(1,3)=2700; V(2,3)=2400; и общий выигрыш, который могут обеспечить себе игроки, образуя максимально большую коалицию, состоящую из трех игроков V(1,2,3)=4400. Требуется:

Проверить выполнение условий супераддитивности и существенности для данной кооперативной игры;

Выразить значение характеристической функции в 0-1 редуцированной форме;

Проверить условия, определяющие непустоту С-ядра и найти один из вариантов решения игры (дележ Х);

Определить выигрыши каждого из игроков в случае их объединения на основе использования вектора Шепли. Проверить принадлежность вектора Шепли С-ядру.

Решение.

Пусть N = {1,..., n} -- множество всех игроков. Любое непустое подмножество S N называется коалицией.

Свойство супераддитивности. (Определение) Характеристической функцией игры n лиц будем называть вещественную функцию х, определенную на коалициях S N, при этом для любых непересекающихся коалиций Т, S (Т С N, S С N) выполняется неравенство

V{T) +v{S) < u(TS), v()=0

В данной задаче

V(1)=1500; V(2)=1200; V(3)=1000; V(1,2)=3000; V(1,3)=2700; V(2,3)=2400; V(1,2,3)=4400.

Также

Значит свойство супераддитивности выполняется.

Теорема. Каждая существенная кооперативная игра эквивалентна некоторой игре в (0-1) -- редуцированной форме.

Если н -- характеристическая функция произвольной существенной игры (Н, н), то

Есть (0 - 1) - нормализация, соответствующая функции н.

Получили такую редуцированную функцию

Проверим условия, определяющие непустоту С-ядра и найдем один из вариантов решения игры (дележ ).

Определение. Множество недоминируемых дележей кооперативной игры (N, н)называется ее С-ядром.

Теорема. Для того чтобы дележ а принадлежал С-ядру, необходимо и достаточно выполнение для всех S N неравенств

С-ядро не пусто тогда и только тогда, когда для всех |S| = 1,..., n имеет место неравенство

Таким образом, С-ядро непусто тогда и только тогда, когда не существует промежуточной коалиции S, в которой средняя доля каждого игрока больше соответствующей величины в коалиции Н.

В нашей задаче средняя доля каждого игрока в коалиции Н равна

Условия непустоты С-ядра выполняются.

Чтобы дележ а принадлежал С-ядру, необходимо и достаточно выполнение следующих неравенств:

Например a=(3/7; 3/7; 1/7) или a=(6/14; 5/14; 3/14)

Определим выигрыши каждого из игроков в случае их объединения на основе использования вектора Шепли. Проверим принадлежность вектора Шепли С-ядру.

В соответствие каждой кооперативной игре (Н, х)можно поставить вектор ц(н) = (ц1[х],..., цз[н]), компоненты которого будем интерпретировать как выигрыши, полученные игроками в результате соглашения или решения арбитра. При этом будем считать, что указанное соответствие удовлетворяет следующим аксиомам.

Аксиомы Шепли.

1. Если S -- любой носитель игры (Н, н), то

    2. Для любой подстановки р и i N 3. Если (N, u) и (Н, v) -- две любые кооперативные игры, то

Определение. Пусть ц -- функция, ставящая в соответствие согласно аксиомам 1--3 каждой игре (N, н) вектор ц[н]. Тогда ц[v] называется вектором значений или вектором Шепли игры (Н, н).

Для 0-1 редуцированной формы игры с тремя игроками вектор Шепли рассчитывается следующим образом:

Ф1(v) = 1/6 (2 - 2C1 + C2 + C3)

Ф2(v) = 1/6 (2 - 2C2 + C1 + C3)

Ф3(v) = 1/6 (2 - 2C3 + C1 + C2)

Где где C1 = v(2,3); C2 = v(1,3); C3 = v(1,2).

Соответственно

Проверим принадлежность вектора Шепли С-ядру.

Чтобы дележ ф принадлежал С-ядру, необходимо и достаточно выполнение следующих неравенств:

Все условия выполняются, значит дележ ф принадлежит ядру.

В нередуцированной форме

Получили

Чтобы дележ ф принадлежал С-ядру, необходимо и достаточно выполнение следующих неравенств:

Все условия выполняются, значит дележ ф принадлежит ядру.

V(1)=1500; V(2)=1200; V(3)=1000; V(1,2)=3000; V(1,3)=2700; V(2,3)=2400; V(1,2,3)=4400.

Похожие статьи




В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: max&;nbsp;f(X)&;nbsp;= min&;nbsp;g(Y). - Теория игр

Предыдущая | Следующая