Вектор Шепли

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

Формальное определение

Для кооперативной игры рассмотрим некоторое упорядочение множества игроков $N$. Обозначим через $K_i$ подмножество, содержащее $i$ первых игроков в данном упорядочении. Вкладом $i$-го по счету игрока назовем величину $v(K_i)-v(K_{i-1})$, где $v$ — характеристическая функция кооперативной игры.

Вектором Шепли кооперативной игры называется такое распределение выигрыша, в котором каждый игрок получает математическое ожидание своего вклада в соответствующие коалиции $K_i$, при равновероятном возникновении упорядочений:

$\mathrm{\Phi }(v)=\frac{1}{n!}\sum _{\tau \in T}{x}_{\tau },$

где $n$ — количество игроков, $T$ — множество упорядочений множества игроков $N,x_{\tau }$ — распределение выигрыша, в котором игрок, стоящий на месте $i$ в упорядочении $\tau$, получает свой вклад в коалицию $K_i$ (точка Вебера).

Более распространенная формула для вычисления вектора Шепли, не требующая нахождения $n!$ точек Вебера, имеет вид:

$\mathrm{\Phi }(v{)}_i=\sum _{i\in K}\frac{(k-1)!(n-k)!}{n!}(v(K)-v(K\setminus i)),$

где $n$ — количество игроков, $k$ — количество участников коалиции $K$.

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

Вектор Шепли удовлетворяет следующим свойствам:

1. Линейность. Отображение $\mathrm{\Phi }(v)$ представляет собой линейный оператор, то есть для любых двух игр с характеристическими функциями $v$ и $w$

$\mathrm{\Phi }(v+w)=\mathrm{\Phi }(v)+\mathrm{\Phi }(w);$

и для любой игры с характеристической функцией $v$ и для любого $\alpha$

$\mathrm{\Phi }(\alpha v)=\alpha \mathrm{\Phi }(v).$

2. Симметричность. Получаемый игроком выигрыш не зависит от его номера. Это означает, что если игра $w$ получена из игры $v$ перестановкой игроков, то её вектор Шепли $\mathrm{\Phi }(w)$ есть вектор $\mathrm{\Phi }(v)$ с соответствующим образом переставленными элементами.

3. Аксиома болвана. Болваном в теории кооперативных игр называется бесполезный игрок, не вносящий вклада ни в какую коалицию, то есть игрок $i$ такой, что для любой коалиции $K$, содержащей $i$, выполнено: $v(K)-v(K\setminus i)=0$.

Аксиома болвана состоит в том, что если игрок $i$ — болван, то $\mathrm{\Phi }(v{)}_i=0$.

4. Эффективность. Вектор Шепли позволяет полностью распределить имеющееся в распоряжении тотальной коалиции благосостояние, то есть сумма компонент вектора $\mathrm{\Phi }(v)$ равна $v(N)$.

Теорема Шепли. Для любой кооперативной игры $v$ существует единственное распределение выигрыша, удовлетворяющее аксиомам 1 — 4, задаваемое приведенной выше формулой.

Приложения

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

Литература

• Васин А. А., Морозов В. В. Теория игр и модели математической экономики - М.: МГУ, 2005, 272 с.
• Воробьев Н. Н. Теория игр для экономистов-кибернетиков — М.: Наука, 1985
• Мазалов В. В. Математическая теория игр и приложения — Изд-во Лань, 2010, 446 с.
• Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр — СПб: БХВ-Петербург, 2012, 432 с.
• Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы — Изд-во Европейского ун-та в С.-Петербурге, 2004, 459 с.

См. также

• Кооперативная игра (математика)
• С-ядро
• N-ядро