Рассмотрим несколько простых примеров.
Пример. Джо изобрел новое лекарство. Джо не может самостоятельно наладить производство этого лекарства, но он может продать рецептуру лекарства либо компании 2, либо 3. Компания, получившая рецептуру, получит прибыль в 1 млн. долл., часть которой получит Джо. Построим характеристическую функцию.
Решение. Пусть в данном случае Джо будет игроком 1, компания 2 - игроком 2, а компания 3 - игроком 3. Тогда
v({l}) = v({2}) = v({3}) = v({2,3}) = 0,
v({l,2}) = v({l,3}) = v({l,2,3}) = l ООО ООО.
Пример. Игрок 1 имеет земельный участок, который он оценивает в 10 000 долл. Игрок 2 является агентом, который, разбив его на более мелкие участки, может довести его стоимость до 20 ООО долл. Игрок 3 может за счет разбивки и улучшения качества участков довести цену до 30 ООО долл.
В этом случае мы получаем следующую характеристическую функцию v({l}) = 10000, v({2}) = v({3}) = 0, v({l,2}) = 20 000,
v({2,3}) = 0, v({l,3}) = 30 000, v({l,2,3}) = 30000,
Характеристическая функция v(S) обладает свойством суперадцитив-ности, а именно: для любых двух непересекающихся подмножеств АиВ выполнено:
V(AuB) >v(A)-v(B),
Действительно, если члены коалиции АВ действуют совместно, то один из вариантов совместных действий состоит в том, что члены коалиции А действуют только в интересах членов коалиции А, а члены коалиции В действуют только в интересах членов коалиции 5. Тогда по-крайней мере они обеспечат себе выигрыш v{A) + v (В).
Пусть вектор x=(?q,jc2,...,x„) является вектором выигрышей, т.е. Х- - выигрыш /-г0 игрока. Необходимыми условиями для того, чтобы вектор X являлся решением игры, являются условия:
4) = Z/ (фупповая рациональность),(5.20)
jCy > v({/}) ,/=!,...,« (индивидуальная рациональность).(5.21)
Определение. Если вектор х удовлетворяет условиям (5.20) и (5.21), то он называется дележом.
Условие (5.20) гарантирует, что мы полагаем, что сумма индивидуальных выигрышей не должна быть меньше того, что может себе обеспечить коалиция в целом.
С другой стороны, условие (5.21) означает, что выигрыш каждого игрока Х- не должен быть меньше того количества, которое он может себе
обеспечить самостоятельно.
Решением игры п лиц (ядром игры) является множество недоминируемых дележей.
5.3.4. Ядро игры п лиц. Прежде всего, определим понятие доминирования.
Определение. Мы говорим, что дележ > доминирует дележ х по коалиции S (обозначается у> х\ если
S>,<v(5) их >x,-ieS.
Если у> х ,то справедливы следующие утверждения.
1.Каждый член коалиции S предпочитает дележ у по сравнению с дележом X.
2.Так как X v(5), члены коалиции S могут достичь выигрышей из
дележа
Основатели теории игр Джон фон Нейман и Оскар Моргенштерн полагали, что разумным решением игры п лиц является множество недоминируемых дележей.
Определение. Ядром игры п лиц называется множество недоминируемых дележей.
Пример. Рассмотрим игру трех лиц со следующей характеристической функцией:
v({l}) = v({2}) = v({3}) = 0, v({l,2}) = 0,l, v({2,3}) = 0,2 v({l,3}) = 0,2 v({l,2,3}) = l. Пусть x = (0,05; 0,90; 0,05), & y = (0,10; 0,80; 0,10). Покажите, что
Решение. Сначала убедимся, что х и у являются дележами. Далее заметим, что дележ у обеспечивает игрокам 1 и 3 больше, чем дележ х. В сумме выигрыши 1-го и 3-го игрока при дележе у составляет 0,10 + 0,10=0,20. Поэтому условие (2) выполнено, поскольку v({l,3})=0,2. Поэтому игроки 1 и 3 предпочтут дележ у.
Находить ядра игр п лиц помогает следующая теорема. Теорема 13. Дележ х=(х1,л,...,л;,) принадлежит ядру игры гг лиц, тогда и только тогда, когда для любого подмножества S множества выполнено
Sx,>v(S).
Теорема утверждает, что дележ х принадлежит ядру (т.е. х не доминируем) тогда и только тогда, когда для любой коалиции S сумма выигрышей игроков (в соответствии с дележом х) не меньше чем v(.S). Из этой теоремы следует, что непустота ядра равносильна разрешимости системы линейных неравенств.
Построим ядро для двух приведенных примеров.
Пример (производство нового лекарства). В этой игре вектор x = (xi,X2,X2) будет дележом тогда и только тогда, когда
х,>0,(5.22)
Х2>0,(5.23)
хз>0,(5.24)
х,+Х2+Хз= 1 000 ООО.(5.25)
Теорема утверждает, что дележ будет принадлежать ядру, если помимо выполнения условий (5.22)-(5.25), будут выполнены условия
Xi+X2> 1 000 ООО,(5.26)
Х1+Хз> 1 000 ООО,(5.27)
Х2+Хз>0,(5.28)
х,+Х2+Хз> 1 000 ООО.(5.29)
Для решения этой системы неравенств заметим, что, сложив неравенства (5.26)-(5.29), получим