02.10.07

Доминирование и ядро

Дележи

Определение. Вектор называется дележом в игре <N,v>, если выполняются условия

1. 
   (коллективная рациональность);
   
2. 
   xⁱ≥v(i) для всех iN (индивидуальная рациональность).
   

В дальнейшем для краткости будем использовать следующее обозначение. Если x – дележ, а K – коалиция, то . В частности, x({i})=xⁱ, x(N)=v(N).

Лемма. Множество дележей не пусто.

Доказательство. Определим вектор условиями x¹=v(1),…,x^n–1= v(n–1), . В силу свойства супераддитивности выполняется неравенство xⁿ≥v(n), значит этот вектор является дележом.

Лемма. В несущественной игре дележ единственный.

Доказательство. Если – дележ, то для всех iN выполняются неравенства xⁱ≥v(i). Суммируя их, получим

(последнее равенство выполняется в силу несущественности игры). Значит на самом деле все сложенные неравенства на самом деле являются равенствами, то есть единственный дележ – вектор (v(1),…,v(n))/

Доминирование

Определение. Дележ x доминирует дележ y по коалиции K, если выполняются условия

1. 
   x(K)v(K);
   
2. 
   xⁱ>yⁱ для всех iN.
   

Если x доминирует дележ y по коалиции K, то будем писать .

Лемма. Отношение доминирования по коалиции K обладает свойствами строгого порядка

1. 
   для любого дележа x не верно, что xy (антисимметричность);
   
2. 
   для любых дележей x,y,z из условий xy и yz следует отношение xz (транзитивность).
   

Доказательство. Лемма немедленно следует из того, что указанными свойствами обладает отношение «больше».

Лемма. Отношение xy не выполняется ни для каких дележей x и y.

Доказательство. Если xy, то xⁱ>yⁱ для любого iN. Суммируя эти равенства, получим (равенства выполняются в силу определения дележа). Получено противоречие.

Лемма. Отношение xy не выполняется ни для какого игрока i и ни для каких дележей x и y.

Доказательство. Если xy, то v(i)≥xⁱ>yⁱ≥v(i) (первые два неравенства выполняются в силу определения доминирования, а последе – так как y – дележ). Получено противоречие.

Лемма. Если xy, то xx+(1–)y для любого [0,1].

Определение. Дележ x доминирует дележ y, если найдется такая коалиция K, что xy.

Если дележ x доминирует дележ y, то будем писать xy.

Пример. Пусть в игре трех лиц v(K)=1, если коалиция K состоит из двух или трех игроков, и v(K)=0 в остальных случаях. Тогда дележ доминирует дележ по коалиции {1,2}, а дележ доминирует дележ по коалиции {1,3}. Но дележ не доминирует дележ . Следовательно, отношение доминирования, вообще говоря, не транзитивно.

Пример. Пусть в игре пяти лиц v(K)=0, если K содержит менее двух игроков, , если K содержит двух или трех игроков и v(N)=1. Тогда дележ доминирует дележ по коалиции {1,2}, а дележ y доминирует дележ x по коалиции {3,4}. Значит, отношение доминирования не является, вообще говоря, и антисимметричным.

Лемма. Если в некоторой игре найдутся дележи x и y такие, что xy и yx, то число игроков в этой игре не меньше пяти.

Доказательство. Если и , то коалиции K и L не пересекаются, так как если , то xⁱ>yⁱ>xⁱ, что не возможно. В силу доказанного выше, каждая из этих двух коалиций содержит не менее двух игроков. Не ограничивая общности, можно считать, что K={1,2}, L={3,4}. Так как , то x¹+x²v({1,2}). Так как , то x³+x⁴<y³+y⁴v({3,4}). Отсюда x¹+x² x³+x⁴<v({1,2})+v({3,4})v(N). Если игроков кроме 1,2,3 и 4 нет, это противоречит определению дележа.

• 
  Ex. Доминирование в 0–1-игре трех лиц с условием дополнительности.
  
• 
  Ex. Доминирование в общей 0-1-игре трех лиц.
  

C-ядро

Определение. C-ядром игры <N,v> называется множество недоминируемых дележей.

C-ядро игры <N,v> будем обозначать символом C(v).

• 
  Gillies D.B., 1953.
  
• 
  -ядро
  

Теорема (о характеризации ядра). C-ядро совпадает с множеством векторов , удовлетворяющим условиям

1. 
   для любой коалиции K;
   
2. 
   .
   

Доказательство. Пусть дележ x удовлетворяет условиям 1 и 2, а дележ y доминирует x. Тогда найдется коалиция такая K, что y доминирует x по коалиции K, в частности yⁱ>xⁱ для всех iK. Суммируя эти неравенства, получим

.

Но это противоречит определению доминирования по коалиции. Значит, такого дележа y не существует, и дележ x не доминируем, то есть принадлежит C-ядру.

Обратно, пусть x – такой дележ, что для некоторой коалиции K выполняется неравенство . Рассмотрим дележ y, определенный условиями

где , , а k – число игроков в коалиции K.

Тогда

По предположению >0, следовательно yⁱ>xⁱ≥v(i) для iK. В силу супераддитивности функции v выполняется неравенство >0, поэтому yⁱ>xⁱ≥v(i) для iN\K. Значит, y – действительно дележ.

Кроме того, и yⁱ>xⁱ для iK. Значит построенный дележ y доминирует дележ x по коалиции K и, следовательно, дележ x не принадлежит C-ядру.

Следствие. Ядро – компактный выпуклый многогранник.

Теорема. Если игры <N,v> и <N,v> являются аффинно эквивалентными и для любой коалиции i выполняется равенство , то .

Доказательство. Пусть x – дележ из ядра игры <N,v>. Тогда . Отсюда или . Кроме того, . Отсюда или . Значит, в силу предыдущей теоремы . Следовательно, . Обратное включение доказывается аналогично.

Лемма. В несущественной игре C-ядро состоит из одного дележа.

Доказательство. Так как в несущественной игре дележ единственный, он принадлежит C-ядру.

Определение. Игра <N,v> называется игрой с постоянной суммой, если для любой коалиции K выполняется равенство

v(N)=v(K)+v(N\K),

Лемма. В существенной игре с постоянной суммой C-ядро пусто.

Доказательство. Допустим противное. Пусть дележ x принадлежит ядру. Тогда для любого игрока i выполняются неравенства

,

v(i)xⁱ.

Складывая эти неравенства, получим

Но так как рассматривается игра с постоянной суммой . Значит, все приведенные выше неравенства обращаются в равенства, в частности xⁱ=v(i), что в силу произвольности i противоречит существенности игры.

Лемма. Во всякой игре двух лиц C-ядро совпадает с множеством всех дележей.

Доказательство. Доминирование по коалициям {1},{2},{1,2} не возможно, а других коалиций в игре двух лиц нет.

Лемма. Если дележ x принадлежит внутренности C-ядра, то он не может доминировать никакой другой дележ.

Доказательство. Допустим противное: пусть xy. Тогда по доказанному выше xx+(1–)y для любого [0,1]. Но при достаточно близких к 1 значениях  дележ x+(1–)y принадлежит ядру. Получено противоречие.

• 
  Пример: симметричная игра
  

Сбалансированные игры

Определение. Коалиция K называется собственной, если она не совпадает с множеством всех игроков N.

Определение. Сбалансированным покрытием множества всех игроков N называется отображение , ставящее в соответствие каждой собственной коалиции K действительное число _K из отрезка [0,1] так, что для всех игроков iN выполняются равенства .

Определение. Игра <N,v> называется сбалансированной, если для любого сбалансированного покрытия  выполняется неравенство .

Теорема. Ядро игры <N,v> не пусто тогда и только тогда, когда игра сбалансирована.

Доказательство. Докажем достаточность. Допустим, что ядро игры пусто. Тогда в силу теоремы о характеризации ядра минимум функции на множестве, задаваемом системой неравенств

, KN

строго больше v(N).

В силу теоремы Куна–Такера, если x₀ – точка минимума, то найдутся неотрицательные множители Лагранжа такие, что пара (x₀,) будет седловой точкой функции

.

Перегруппируем в этой формуле слагаемые, выделив переменные xⁱ:

.

Так как (x₀,) – седловая точка, то функция

достигает своего максимума, а это возможно лишь в том случае, когда она постоянна, то есть для всех игроков iN выполняются равенства . В этом случае искомый минимум равен и по сделанному предположению он строго больше v(N). Получено противоречие.

Необходимость доказывается проще. Пусть дележ x принадлежит ядру и  – сбалансированное покрытие. Тогда в силу теоремы о характеризации ядра

, KN.

Умножая эти неравенства на _K и суммируя, получим

.

Поменяем порядок суммирования:

.

Учитывая, что  – сбалансированное покрытие, окончательно получим

.

Теорема доказана.

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

Пример. Рассмотрим игру трех лиц. Сбалансированное покрытие задается шестью числами ₁, ₂, ₃, ₁₂, ₁₃ и ₂₃. Условие сбалансированности выделяет трехмерное подпространство в , задаваемое равенствами

₁+₁₂+₁₃=1, ₂+₁₂+₂₃=1, ₃+₁₃+₂₃=1.

Условия неотрицательности чисел ₁, ₂, ₃, ₁₂, ₁₃ и ₂₃ задает искомый многогранник.

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

Если нулю равны числа ₁, ₂ и ₃, получаем ₁₃=1/2, ₂₃=1/2, ₂₃=1/2 и условие непустоты ядра v({1,2})+ v({1,3})+ v({2,3})2v({1,2,3}).

Если нулю равны числа ₁, ₂ и ₁₂, то ₃=–1 и указанная точка не принадлежит многограннику. Аналогично рассматриваются два случая, когда нулю равны числа ₁, ₃ и ₁₃ и когда нулю равны числа ₂, ₃ и ₂₃.

Если нулю равны числа ₁, ₂ и ₁₃, то ₃=1, ₁₂=1, и ₂₃=0 и получаем условие v({3})+ v({1,2})v({1,2,3}), совпадающее с условием супераддитивности. Аналогично рассматривается еще пять случаев, получающихся перестановкой игроков.

Если нулю равны числа ₁, ₁₂ и ₁₃, то немедленно получается противоречие. Так же рассматриваются еще два симметричных случая.

Если нулю равны числа ₁, ₁₂ и ₂₃, то ₂=1, ₃=0, и ₁₃=1 и получаем условие v({2})+ v({1,3})v({1,2,3}), совпадающее с условием супераддитивности. Аналогично рассматривается еще пять случаев, получающихся перестановкой игроков.

Наконец, если нулю равны числа ₁₂, ₁₃ и ₂₃, то ₁=1, ₂=1, и ₃=1 и получаем условие v({1})+ v({2})+ v({3})v({1,2,3}), совпадающее с условием супераддитивности.

Все возможности рассмотрены и мы убедились, что необходимым и достаточным условием непустоты ядра является выполнение неравенства

v({1,2})+ v({1,3})+ v({2,3})2v({1,2,3}).

Выпуклые игры

Определение. Игра <N,v> называется выпуклой, если для любых двух коалиций I и K выполняется неравенство .

Лемма. Игра <N,v> является выпуклой тогда и только тогда, когда для любых двух коалиций I и K, не содержащих игрока i, включение IK влечет неравенство .

Доказательство. Докажем сначала необходимость. Рассмотрим две коалиции I и K, не содержащих игрока i, и удовлетворяющих условию IK. В силу выпуклости игры

,

откуда

,

что и требуется доказать.

Докажем достаточность. Рассмотрим две коалиции I и K, удовлетворяющих условию IK и произвольную коалицию RN\K. Пусть R={i₁,…,i_r}. Тогда для любого k=1,…,r выполняется неравенство

.

Суммируем эти неравенства по k от 1 до r. Получим неравенство

,

справедливое для любых коалиций IK и любой коалиции RN\K.

Возьмем произвольные коалиции S и T. В силу предыдущего неравенства

,

или

.

Лемма доказана.

Теорема. В выпуклой игре C-ядро не пусто.

Доказательство. Определим дележ x следующим образом. Положим x¹=v(1), xⁱ=v({1,…,i})-v({1,…,i–1}). Докажем, что он принадлежит C-ядру.

Рассмотрим произвольную коалицию S={i₁,…,i_s} и определим две коалиции I_p={i₁,i₂,…,i_p–1} и K_p={1,2,…,i_p–1} (p=1,…,s). Очевидно, I_pK_p, поэтому в силу предыдущей леммы

v({i₁,…,i_k})– v({i₁,…,i_k–1})=v({1,…,i_k})– v({1,…,i_k–1})=.

Суммируя эти неравенства по k от 1 до s, получим

.

Так как коалиция S произвольна, в силу теоремы о характеризации ядра дележ x принадлежит C-ядру.

• 
  Взлетные полосы
  

Примеры

• 
  Ex. Ядро в 0–1-игре трех лиц.  – непусто,  – пусто.
  
• 
  Ex. Симметричные игры (Мулен, стр. 188) Необходимое и достаточное условие непустоты – в центре.
  
• 
  Условие непустоты ядра в 0-1-игре трех лиц. c₁+c₂+c₃2.
  
• 
  Ex. Джаз-оркестр.: v(SPD)=1000, v(SP+=800, v(DP)=300,v(DS)=500, v(P)=300, v(S)=200, v(D)=0. Ядро ­– выпуклая оболочка точек (350,450,200), (350,500,150), (300,500,200). S – певец, P – пианист, D(drummer) – ударник.
  

Задачи

1. 
   Какой многогранник образуют сбалансированные покрытия в игре трех лиц?
   
2. 
   Докажите, что .
   
3. 
   Пусть <N,v>, где N={1,…,n} – игра n диц, а <N,v> – игра n+1 игрока, определенная условием N={0,1,…,n}, v(K)=v(K), если KN и в противном случае (a – заданное число). Известно C-ядро игры <N,v>. Найдите C-ядро игры <N,v>.
   

Литература

1. 
   Воробьев Н.Н. Теория игр для экономистов–кибернетиков. М.: Наука, 1985.
   
2. 
   Мулен Э. Кооперативное принятие решений: Аксиомы и модели. М.: Мир.1991.
   
3. 
   Кукушкин Н.С., Морозов В.В. Теория неантагонистических игр. М.: МГУ. 1984.
   
4. 
   Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.: Высшая школа. 1998.
   
5. 
   Оуэн Г. Теория игр. М.: Мир. 1971.