Вектор Шепли

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

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

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

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

$\mathrm{\Phi <!--\; \Phi \; -->}(v)=\frac{1}{n!}\underset{\mathrm{\tau <!--\; \tau \; -->}\in <!--\; \in \; -->T}{\sum <!--\; \sum \; -->}{x}_{\mathrm{\tau <!--\; \tau \; -->}},$$\Phi (v)={\frac {1}{n!}}\sum _{\tau \in T}x_{\tau },$ 

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

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

$\mathrm{\Phi <!--\; \Phi \; -->}(v{)}_i=\underset{i\in <!--\; \in \; -->K}{\sum <!--\; \sum \; -->}\frac{(k-<!--\; -\; -->1)!(n-<!--\; -\; -->k)!}{n!}\left(v(K)-<!--\; -\; -->v(K\setminus <!--\; \setminus \; -->i)\right),$$\Phi (v)_{i}=\sum _{i\in K}{\frac {(k-1)!(n-k)!}{n!}}\left(v(K)-v(K\setminus i)\right),$ 

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

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

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

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

$\mathrm{\Phi <!--\; \Phi \; -->}(v+w)=\mathrm{\Phi <!--\; \Phi \; -->}(v)+\mathrm{\Phi <!--\; \Phi \; -->}(w);$$\Phi (v+w)=\Phi (v)+\Phi (w);$ 

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

$\mathrm{\Phi <!--\; \Phi \; -->}(\mathrm{\alpha <!--\; \alpha \; -->}v)=\mathrm{\alpha <!--\; \alpha \; -->}\mathrm{\Phi <!--\; \Phi \; -->}(v).$$\Phi (\alpha v)=\alpha \Phi (v).$ 

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

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

Аксиома болвана состоит в том, что если игрок $i$$i$  — болван, то $\mathrm{\Phi <!--\; \Phi \; -->}(v{)}_i=0$$\Phi (v)_{i}=0$ .

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

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

ЛитератураПравить

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

См. такжеПравить

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