Поиск вектора Шепли

Цель практической работы: познакомиться с кооперативной игрой, реализовать алгоритм поиска Шепли в коалиционной игре.

Задачи по практике:

1. Рассмотреть кооперативной игру.
2. Вектор Шепли как результат дележа
3. Запрограммировать алгоритм поиска вектора Шепли.

Кооперативные игры.

Определение кооперативной игры заключается в задании множества игроков N и функции, которая каждой коалиции ставит в соответствие цену этой коалиции.

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

Вектор a = ( a1, a2, …an ) , удовлетворяющий условиям:

• что любой элемент этого вектора по крайней мере не меньше значения характеристической функции соответствующего индекса
• сумма значений вектора равна значению характеристической функции максимальной коалиции

называется дележом.

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

Вектору Шепли можно дать следующее содержательное истолкование:

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

2. Предположим, что все порядки прибытия игроков (т. е. все их перестановки) равновероятны, т. е. имеют одну и ту же вероятность 1 / n! . Далее предположим, что если игрок i , прибывая, застает на месте только членов коалиции S i \ { } (остальные игроки еще не подошли), то он получает выигрыш v S v S i ( ) ( \ ) - { } . Иначе говоря, его выигрышем является тот вклад, который он вносит в гарантированный выигрыш новой коалиции.

3. Тогда компонента вектора Шепли 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]

Заключение.

• Игры, в которых допускаются совместные действия игроков и

перераспределение выигрыша, можно формализовать как игры в

форме характеристической функции.

• Основным понятием для игры в форме характеристической

функции является понятие дележа.

• Вектор Шепли предлагает единственный дележ в качестве

решения любой кооперативной игры.