Коалиционные игры

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

Пусть имеется участников:

Рассмотрим возможные стратегии сотрудничества:

– каждый из участников действует независимо от других;

– коалиция из двух участников, первого и второго;

– коалиция первого и третьего участников;

– коалиция второго и третьего участников;

– коалиция из трех участников.

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

– выигрыш участников при стратегии

– если первый и второй участники вступят в коалицию, то их общий выигрыш составит 25 и т.д.

– выигрыш трех участников, если они все вступят в коалицию.

Таким образом, чтобы описать коалиционную игру, необходимо задать характеристическую функцию.

Характеристическая функция должна обладать свойством супераддитивности. Для любой пары непересекающихся коалиций должно выполняться неравенство:

.

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

Если , то такая игра несущественна, так как нет смысла вступать в коалиции.

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

где – выигрыш участника в коалиции (1, 2), – выигрыш участника в коалиции (1, 2) и т.д. При этом

.

Видим, что при определении выигрышей участников коалиций возникает проблема дележа.