♟️ Теория игр

Вектор Шепли

англ. Shapley value

Правило справедливого дележа в кооперативной игре: каждому — средний предельный вклад по всем порядкам вхождения; единственный дележ, выполняющий аксиомы Шепли.

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

Считаем на двоих: $v (\emptyset) = 0$ , $v (1) = 2$ , $v (2) = 3$ , $v (12) = 8$ . Перестановка $(1, 2)$ : вклад первого $2$ , второго $8 - 2 = 6$ ; перестановка $(2, 1)$ : вклад второго $3$ , первого $8 - 3 = 5$ . Итог: $φ_{1} = (2 + 5) /2 = 3, 5$ , $φ_{2} = (6 + 3) /2 = 4, 5$ , сумма равна $8$ — весь пирог поделён. Аксиомы эффективности, симметрии, нулевой доли и аддитивности делают дележ единственным; рамка — в статье кооперативная игра, счёт порядков — в материале перестановки, размещения и сочетания, веса — через факториал, усреднение — через математическое ожидание, формулы под рукой — в шпаргалке комбинаторика.

φ_{i} (v) = S \subseteq N ∖ {i} \sum \frac{∣ S ∣ ! ( n - ∣ S ∣ - 1 )!}{n !} [v (S \cup {i}) - v (S)]

общая формула вектора Шепли: предельный вклад

v (S \cup {i}) - v (S)

взвешивается вероятностью того, что коалиция

S

уже собралась, а игрок

i

приходит очередным

Частые вопросы

Почему вклады усредняются именно по перестановкам?

Чтобы исключить произвол очереди. Коалиция могла бы формироваться в любом порядке, и «кто пришёл первым» — вопрос случая, а не заслуг. Среднее по всем $n!$ перестановкам оценивает вклад игрока при каждой возможной роли: пионер, присоединяющийся к пустой коалиции, и замыкающий, добивающий проект, получают свои доли честно. Факториальные веса в формуле — это вероятности оказаться в конкретной позиции при случайном порядке прихода.

Где применяется вектор Шепли на практике?

Везде, где надо делить совместный результат с обоснованием. Классика — распределение накладных расходов между подразделениями и тарификация общей инфраструктуры: электросети, водоснабжения, канала связи. В голосующих органах индекс Шепли — Шубика измеряет реальную власть фракции через число решающих коалиций, где её голос критичен. Экономисты применяют формулу к дележу прибыли альянсов, юристы — к разделу совместного имущества; всюду ценится аксиоматическая справедливость.