Вектор Шепли

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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