logo search
Теория игр

Свойства характеристической функции

Имеется коалиционная игра Г=<I,{Si}, , {Hi}>.

Опр. Вещественная функция v(k), определенная на семействе k I (всех подмножеств k из I), называется характеристической функцией.

Содержательно определенная характеристическая функция должна удовлетворять 3 свойствам:

  1. Персональность

  2. Супераддитивность

  3. Дополнительность

Персональность: выигрыш участников коалиции определяется не только их числом, но и персональным составом коалиции. v( )=0.

Супераддитивность: отражает заинтересованность двух групп, K и L, в коалиции: v(K L) v(K) + v(L)

Дополнительность: v(K) + v(I/K) = v(I), следовательно характеристическая функция показывает ресурс игры v(I) между коалицией К и лицами, не вошедшими в нее (I/K). А значит, если известны характеристические функции всех возможных коалиций, т.е. v(K) для , об игре известно все.

Надо так нормировать выигрыши всех игроков, чтобы v(I)=1. Тогда v(K) [0,1] .

Игра, в которой v(K) [0,1] , называется коалиционной игрой в 0,1-редуцированной форме.

ТЕОРЕМА. Всякая коалиционная игра Г приводится к единственной коалиционной игре в 0,1-редуцированной форме.

Рассмотрим некоторые свойства характеристической функции в 0,1-редуцированной коалиционной игре:

  1. Всякая характеристическая функция является неотрицательной и неубывающей функцией.

  2. Если K L, то v(K) + v(L/K) v(L)

  3. Всякая характеристическая функция в игре из n игроков, I={1,2,…,n}, описывается 2n-1 числом параметров, а при приведении игры в 0,1-редуцированную форму накладывается n+1 дополнительных связей, и, следовательно, получается (2n - n - 2) свободных параметров.

Рассмотрим, сколько будет свободных параметров в зависимости от числа игроков:

n=2 22-2-2=0 v(1)=v(2)=0

v(1,2)=1

n=3 23-3-2=3 v(1)=v(2)=v(3)=0

v(1,2)=c3 , v(1,3)=c2 , v(2,3)=c1 3 параметра

v(1,2,3)=1

Пример. Рассмотренная ранее игра в 0,1-редуцированной форме (см. пример про продавца и покупателей):

v(Пр,П1)=b-a || v( )=v(П1)=v(П2)=v(П1,П2)=0

v(Пр,П2)=c-a || v(Пр)=а-а=0

v(Пр,П1)=

v(Пр,П2)=1

v(Пр,П1,П)=1

Если при анализе 0,1-редуцированной игры учитывать свойство дополнительности, то на наибольшее число параметров накладывается еще одно условие. Содержательно игру в 0,1-редуцированной форме можно определить, если число участников n 3.

После определения выигрыша коалиции возникает задача дележа выигрыша между участниками коалиции. Задача определения справедливых дележей рассматривается в кооперативных играх.