Вектор Шепли

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

Для кооперативной игры рассмотрим некоторое упорядочение множества игроков ${\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-ядро

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (9 июля 2021)