Русская Википедия:Вектор Шепли
Вектор Шепли — принцип оптимальности распределения выигрыша между игроками в задачах теории кооперативных игр. Представляет собой распределение, в котором выигрыш каждого игрока равен его среднему вкладу в благосостояние тотальной коалиции при определенном механизме её формирования. Назван в честь американского экономиста и математика Ллойда Шепли.[1][2]
Формальное определение
Для кооперативной игры рассмотрим некоторое упорядочение множества игроков <math>N</math>. Обозначим через <math>K_i</math> подмножество, содержащее <math>i</math> первых игроков в данном упорядочении. Вкладом <math>i</math>-го по счету игрока назовем величину <math>v(K_i)-v(K_{i-1})</math>, где <math>v</math> — характеристическая функция кооперативной игры.
Вектором Шепли кооперативной игры называется такое распределение выигрыша, в котором каждый игрок получает математическое ожидание своего вклада в соответствующие коалиции <math>K_i</math>, при равновероятном возникновении упорядочений:
где <math>n</math> — количество игроков, <math>T</math> — множество упорядочений множества игроков <math>N,\ x_{\tau}</math> — распределение выигрыша, в котором игрок, стоящий на месте <math>i</math> в упорядочении <math>\tau</math>, получает свой вклад в коалицию <math>K_i</math> (точка Вебера).
Более распространенная формула для вычисления вектора Шепли, не требующая нахождения <math>n!</math> точек Вебера, имеет вид:
где <math>n</math> — количество игроков, <math>k</math> — количество участников коалиции <math>K</math>.
Аксиоматика вектора Шепли
Вектор Шепли удовлетворяет следующим свойствам:
1. Линейность. Отображение <math>\Phi(v)</math> представляет собой линейный оператор, то есть для любых двух игр с характеристическими функциями <math>v</math> и <math>w</math>
и для любой игры с характеристической функцией <math>v</math> и для любого <math>\alpha</math>
2. Симметричность. Получаемый игроком выигрыш не зависит от его номера. Это означает, что если игра <math>w</math> получена из игры <math>v</math> перестановкой игроков, то её вектор Шепли <math>\Phi(w)</math> есть вектор <math>\Phi(v)</math> с соответствующим образом переставленными элементами.
3. Аксиома болвана. Болваном в теории кооперативных игр называется бесполезный игрок, не вносящий вклада ни в какую коалицию, то есть игрок <math>i</math> такой, что для любой коалиции <math>K</math>, содержащей <math>i</math>, выполнено: <math>v(K)-v(K \setminus i)=0</math>.
Аксиома болвана состоит в том, что если игрок <math>i</math> — болван, то <math>\Phi(v)_i = 0</math>.
4. Эффективность. Вектор Шепли позволяет полностью распределить имеющееся в распоряжении тотальной коалиции благосостояние, то есть сумма компонент вектора <math>\Phi(v)</math> равна <math>v(N)</math>.
Теорема Шепли. Для любой кооперативной игры <math>v</math> существует единственное распределение выигрыша, удовлетворяющее аксиомам 1 — 4, задаваемое приведенной выше формулой.
Приложения
Одним из современных приложений вектора Шепли в машинном обучении является оценка влияния отдельных признаков примера на прогнозируемое значение при решении задачи классификации[3] или регрессии[4].
Примечания
Литература
- Васин А. А., Морозов В. В. Теория игр и модели математической экономики - М.: МГУ, 2005, 272 с.
- Воробьев Н. Н. Теория игр для экономистов-кибернетиков — М.: Наука, 1985
- Мазалов В. В. Математическая теория игр и приложения — Изд-во Лань, 2010, 446 с.
- Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр — СПб: БХВ-Петербург, 2012, 432 с.
- Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы — Изд-во Европейского ун-та в С.-Петербурге, 2004, 459 с.
См. также
Шаблон:Викифицировать книги Шаблон:Нет сносок
