Цель практической работы: познакомиться с кооперативной игрой, реализовать алгоритм поиска Шепли в коалиционной игре.
Задачи по практике:
- Рассмотреть кооперативной игру.
- Вектор Шепли как результат дележа
- Запрограммировать алгоритм поиска вектора Шепли.
Определение кооперативной игры заключается в задании множества игроков N и функции, которая каждой коалиции ставит в соответствие цену этой коалиции.
Основной проблемой теории кооперативных игр является не задача выбора тех или иных стратегий игроками, а проблема достижения справедливого раздела общего выигрыша
Вектор a = ( a1, a2, …an ) , удовлетворяющий условиям:
- что любой элемент этого вектора по крайней мере не меньше значения характеристической функции соответствующего индекса
- сумма значений вектора равна значению характеристической функции максимальной коалиции
называется дележом.
Вектор Шепли — принцип оптимальности распределения выигрыша между игроками в задачах теории кооперативных игр. Представляет собой распределение, в котором выигрыш каждого игрока равен его среднему вкладу в благосостояние тотальной коалиции при определенном механизме её формирования.
Вектору Шепли можно дать следующее содержательное истолкование:
-
Предположим, что игроки решили встретиться в определенном месте и в определенное время с целью переговоров по дележу выигрыша максимальной коалиции. Естественно, что из-за случайных отклонений все они будут прибывать в различные моменты времени.
-
Предположим, что все порядки прибытия игроков (т. е. все их перестановки) равновероятны, т. е. имеют одну и ту же вероятность 1 / n! . Далее предположим, что если игрок i , прибывая, застает на месте только членов коалиции S i \ { } (остальные игроки еще не подошли), то он получает выигрыш v S v S i ( ) ( \ ) - { } . Иначе говоря, его выигрышем является тот вклад, который он вносит в гарантированный выигрыш новой коалиции.
-
Тогда компонента вектора Шепли j ( ) i v , являясь по определению дележа долей выигрыша игрока i от суммарного выигрыша максимальной коалиции, представляет собой математическое ожидание выигрыша игрока i в соответствии с данной схемой.
Вектор Шепли предлагает единственный дележ в качестве решения любой кооперативной игры.
Ход работы:
Для введения характеристической функции удобно взять такую структуру данных, как словарь, по которому можно будет вытаскивать значения при различных коалициях.
# python code
function = {
'1': 20,
'2': 30,
'3': 0,
'12': 80,
'13': 50,
'23': 65,
'123': 100
}
Количество игроков определяется константой:
N_COUNT = 3
Для вычислений используется вспомогательная функция факториала:
# python code
def fac(n):
if n == 0:
return 1
return fac(n - 1) * n
Для вычисления вклада игрока необходима следующая функция, которая бы сравнивала коалицию с этим игроком и коалицию без этого игрока:
# python code
def player_profit(coalition, player):
with_player = function.get(coalition)
without_player = function.get(coalition.replace(str(player), ''), 0)
return with_player - without_player
Для определения количества различных вариантов порядка включения игрока в полную коалицию, в которой i-ый игрок расположен на k-ом месте нужна следующая функция:
# python code
def number_of_inclusions(n, coalition):
fact_nk = fac(N_COUNT - len(coalition))
fact_k1 = fac(len(coalition) - 1)
fact_n = fac(N_COUNT)
return (fact_nk * fact_k1) / fact_n
Здесь n – общее количество игроков в игре, len(coalition) – номер, каким i-ый игрок был включен в коалицию. Учитывается количество перестановок игроков, вступивших в коалицию до i-ого игрока (которые стоят на (k-1) первых местах), и количество перестановок игроков, которые вступили в коалицию после i-ого игрока (которые стоят на (n-k) последних местах).
# python code
vector = []
for i in range(N_COUNT):
value = 0
player = i + 1
for key in function.keys():
if str(player) in key:
value += number_of_inclusions(N_COUNT, key) * player_profit(key, player)
vector.append(value)
print("Вектор Шепли: " + str(vector))
Результат работы программы:
Вектор Шепли: [34.99999999999999, 47.5, 17.5]
Заключение.
- Игры, в которых допускаются совместные действия игроков и
перераспределение выигрыша, можно формализовать как игры в
форме характеристической функции.
- Основным понятием для игры в форме характеристической
функции является понятие дележа.
- Вектор Шепли предлагает единственный дележ в качестве
решения любой кооперативной игры.