Вектор Шепли

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

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

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

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

[math]\displaystyle{ \Phi(v) = \frac{1}{n!}\sum_{\tau \in T}x_{\tau}, }[/math]

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

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

[math]\displaystyle{ \Phi(v)_{i} = \sum_{i \in K}\frac{(k-1)!(n-k)!}{n!}\left(v(K)-v(K \setminus i)\right), }[/math]

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

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

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

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

[math]\displaystyle{ \Phi(v+w) = \Phi(v) + \Phi(w); }[/math]

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

[math]\displaystyle{ \Phi(\alpha v) = \alpha \Phi(v). }[/math]

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

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

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

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

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

Литература

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

См. также

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