Вектор Шепли (Fytmkj Oyhln)
Вектор Шепли — принцип оптимальности распределения выигрыша между игроками в задачах теории кооперативных игр. Представляет собой распределение, в котором выигрыш каждого игрока равен его среднему вкладу в благосостояние тотальной коалиции при определенном механизме её формирования. Назван в честь американского экономиста и математика Ллойда Шепли.[1][2]
Формальное определение
[править | править код]Для кооперативной игры рассмотрим некоторое упорядочение множества игроков . Обозначим через подмножество, содержащее первых игроков в данном упорядочении. Вкладом -го по счету игрока назовем величину , где — характеристическая функция кооперативной игры.
Вектором Шепли кооперативной игры называется такое распределение выигрыша, в котором каждый игрок получает математическое ожидание своего вклада в соответствующие коалиции , при равновероятном возникновении упорядочений:
где — количество игроков, — множество упорядочений множества игроков — распределение выигрыша, в котором игрок, стоящий на месте в упорядочении , получает свой вклад в коалицию (точка Вебера).
Более распространенная формула для вычисления вектора Шепли, не требующая нахождения точек Вебера, имеет вид:
где — количество игроков, — количество участников коалиции .
Аксиоматика вектора Шепли
[править | править код]Вектор Шепли удовлетворяет следующим свойствам:
1. Линейность. Отображение представляет собой линейный оператор, то есть для любых двух игр с характеристическими функциями и
и для любой игры с характеристической функцией и для любого
2. Симметричность. Получаемый игроком выигрыш не зависит от его номера. Это означает, что если игра получена из игры перестановкой игроков, то её вектор Шепли есть вектор с соответствующим образом переставленными элементами.
3. Аксиома болвана. Болваном в теории кооперативных игр называется бесполезный игрок, не вносящий вклада ни в какую коалицию, то есть игрок такой, что для любой коалиции , содержащей , выполнено: .
Аксиома болвана состоит в том, что если игрок — болван, то .
4. Эффективность. Вектор Шепли позволяет полностью распределить имеющееся в распоряжении тотальной коалиции благосостояние, то есть сумма компонент вектора равна .
Теорема Шепли. Для любой кооперативной игры существует единственное распределение выигрыша, удовлетворяющее аксиомам 1 — 4, задаваемое приведенной выше формулой.
Приложения
[править | править код]Одним из современных приложений вектора Шепли в машинном обучении является оценка влияния отдельных признаков примера на прогнозируемое значение при решении задачи классификации[3] или регрессии[4].
Примечания
[править | править код]- ↑ Shapley, Lloyd S. Notes on the n-Person Game – II: The Value of an n-Person Game . Santa Monica, Calif.: RAND Corporation (21 августа 1951). Дата обращения: 30 апреля 2023. Архивировано 30 апреля 2023 года.
- ↑ The Shapley Value: Essays in Honor of Lloyd S. Shapley. — Cambridge : Cambridge University Press, 1988. — ISBN 0-521-36177-X. — doi:10.1017/CBO9780511528446.
- ↑ Igantov, Dmitry I.; Kwuida, Leonard (2022). "On Shapley value interpretability in concept-based learning with formal concept analysis". Ann Math Artif Intell. 90: 1197—1222. Дата обращения: 30 апреля 2023.
- ↑ Strumbelj, Erik; Kononenko, Igor (2014). "Explaining prediction models and individual predictions with feature contributions". Knowl. Inf. Syst. 41: 647–665. Дата обращения: 30 апреля 2023.
Литература
[править | править код]- Васин А. А., Морозов В. В. Теория игр и модели математической экономики - М.: МГУ, 2005, 272 с.
- Воробьев Н. Н. Теория игр для экономистов-кибернетиков — М.: Наука, 1985
- Мазалов В. В. Математическая теория игр и приложения — Изд-во Лань, 2010, 446 с.
- Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр — СПб: БХВ-Петербург, 2012, 432 с.
- Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы — Изд-во Европейского ун-та в С.-Петербурге, 2004, 459 с.
См. также
[править | править код]В статье есть список источников, но не хватает сносок. |