Shapley value

Angol

Főnév

Shapley value (tsz. Shapley values)

(informatika) A Shapley-érték a kooperatív játékelmélet egyik legismertebb fogalma, amelyet Lloyd Shapley vezetett be 1953-ban. Olyan helyzetekben alkalmazható, ahol több szereplő együttműködik (pl. cégek, ügynökök, játékosok), és az a kérdés, hogy az együttműködés révén elért közös hasznot hogyan lehet méltányosan elosztani a résztvevők között.

1. Motiváció

Tegyük fel, hogy három vállalat közösen fejleszt egy új technológiát. Egyenként vagy kisebb csoportokban nem tudják megvalósítani, de együtt létre tudják hozni, és így 100 egység profitot termelnek. Mennyit érdemel mindegyik cég?

A Shapley-érték segít objektíven meghatározni, hogy kinek mekkora hozzájárulása volt a teljes eredményhez.

2. Alapfogalmak

a) Kooperatív játék

Van egy játékoshalmaz: ${\textstyle N=\{1,2,...,n\}}$
A játékhoz tartozik egy értékfüggvény: ${\textstyle v(S)}$ , amely megadja, hogy egy ${\textstyle S\subseteq N}$ koalíció mennyi hasznot tud elérni.
A cél: osszuk el ${\textstyle v(N)}$ értéket méltányosan.

b) Shapley-érték definíciója

A Shapley-érték egy játékos hozzájárulását a lehetséges koalíciókhoz való belépése szerinti várható marginális hozzájárulása alapján számítja.

Formálisan:

$\phi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!(n-|S|-1)!}{n!}}\cdot [v(S\cup \{i\})-v(S)]$

– ahol:

${\textstyle \phi _{i}(v)}$ : az ${\textstyle i}$ -edik játékos Shapley-értéke
${\textstyle v(S)}$ : a koalíció értéke
Az összeg az összes ${\textstyle i}$ -t nem tartalmazó koalícióra megy

3. Intuitív értelmezés

Képzeljünk el minden lehetséges sorrendet, amelyben a játékosok beléphetnek a koalícióba. Minden sorrendben megnézzük, hogy egy játékos mennyit ad hozzá a már meglévő csapat értékéhez. Az összes sorrendre átlagolva ezt kapjuk meg Shapley-értékként.

4. Tulajdonságai

A Shapley-érték az egyetlen értékosztás, amely az alábbi négy axiómát teljesíti:

Hatékonyság (Efficiency): A Shapley-értékek összege egyenlő a teljes koalíció értékével:

$\sum _{i\in N}\phi _{i}(v)=v(N)$
Szimmetria (Symmetry): Ha két játékos azonos hozzájárulást nyújt minden koalícióhoz, akkor ugyanazt az értéket kapják.
Nullajátékos (Dummy player): Ha egy játékos semmilyen koalícióhoz nem ad hozzá értéket, akkor Shapley-értéke 0.
Additivitás: Két játék összegére a Shapley-érték az értékek összege.

5. Egyszerű példa – 3 játékos

Legyen ${\textstyle N=\{A,B,C\}}$ , és a koalíciós értékek:

${\textstyle v(\{A\})=0}$
${\textstyle v(\{B\})=0}$
${\textstyle v(\{C\})=0}$
${\textstyle v(\{A,B\})=100}$
${\textstyle v(\{A,C\})=100}$
${\textstyle v(\{B,C\})=100}$
${\textstyle v(\{A,B,C\})=100}$

Ez azt jelenti, hogy bármely 2 játékos eléri a maximumot, a harmadik nem növeli tovább.

Shapley-érték számítása:

Minden játékos 2 faktoriál szorzóval szerepel 6 sorrendben. Megnézzük, hogy ki mennyit ad hozzá minden belépéskor.

A: 33.3
B: 33.3
C: 33.3

➡ Egyenlő Shapley-értékek, mert szimmetrikus a játék.

6. Alkalmazások

Gazdaság: profitmegosztás vállalatok vagy országok között
Politológia: szavazati erő elemzése (pl. koalíciókban)
Hálózatelemzés: csomópontok fontosságának mérése
Adattudomány, AI: Shapley value attribútumfontosság számításra (pl. SHAP az ML modellek interpretálhatóságához)
Erőforrás-megosztás: számítási költség vagy haszon elosztása több fél között

7. Shapley-érték gépi tanulásban

A SHAP (SHapley Additive exPlanations) módszer a Shapley-értéken alapul, és a gépi tanulási modellek döntéseinek magyarázatára szolgál. A cél: meghatározni, hogy egy-egy bemeneti változó milyen mértékben járult hozzá egy adott jósláshoz.

8. C++ példa – Shapley-érték számítása (kis N-re)

#include <iostream>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

int factorial(int n) {
    return (n <= 1) ? 1 : n * factorial(n - 1);
}

// Koalíciók binárisan reprezentálva (pl. 101 = A és C)
double shapleyValue(int player, const map<int, double>& v, int n) {
    double value = 0;
    for (int S = 0; S < (1 << n); ++S) {
        if (S & (1 << player)) continue; // player nem lehet benne
        int Ssize = __builtin_popcount(S);
        int withPlayer = S | (1 << player);

        double coeff = (double)(factorial(Ssize) * factorial(n - Ssize - 1)) / factorial(n);
        value += coeff * (v.at(withPlayer) - v.at(S));
    }
    return value;
}

int main() {
    int n = 3; // játékosok száma: A, B, C
    map<int, double> v = {
        {0b000, 0}, {0b001, 0}, {0b010, 0}, {0b100, 0},
        {0b011, 100}, {0b101, 100}, {0b110, 100}, {0b111, 100}
    };

    for (int i = 0; i < n; ++i) {
        double phi = shapleyValue(i, v, n);
        cout << "Játékos " << char('A' + i) << " Shapley-értéke: " << phi << endl;
    }
    return 0;
}

9. Nehézségek és korlátok

Kombinatorikus robbanás: ${\textstyle n}$ játékos esetén ${\textstyle 2^{n}}$ koalíció létezik – nagy számítási igény
Heurisztikák, közelítések szükségesek nagy rendszereknél
Csak akkor használható jól, ha a teljes értékfüggvény (v) ismert

10. Összefoglalás

A Shapley-érték egy elegáns, axiomatikusan megalapozott eszköz:

Méltányosan osztja el a közösen elért hasznot
Minden játékos várható hozzájárulását értékeli
Alkalmazható gazdaságtól kezdve a mesterséges intelligenciáig
Bár elméletben tökéletes, nagy rendszerekhez közelítések szükségesek

További információk

Shapley value - Szótár.net (en-hu)
Shapley value - Sztaki (en-hu)
Shapley value - Merriam–Webster
Shapley value - Cambridge
Shapley value - WordNet
Shapley value - Яндекс (en-ru)
Shapley value - Google (en-hu)
Shapley value - Wikidata
Shapley value - Wikipédia (angol)