Shapley value calculation in Python

Introduction

Hello, this is leisurely it leisurely. (I was told on Twitter that leisurely is hard to call.) Since I studied cooperative game theory, I implemented Shapley value calculation in Python after reviewing. We've just implemented programming what we can do by hand, and we won't actually calculate the Shapley value, which is hard to find by hand. It seems that R has a package to calculate the Shapley value, so you should use R (I wonder if the package name was matchingR). So implementing it is a complete hobby.

Let's start coding after a little explanation of the Shapley value.

・ References [Introduction to Shigeo Muto Game Theory](https://www.amazon.co.jp/%E3%82%B2%E3%83%BC%E3%83%A0%E7%90%86%E8%AB%96 % E5% 85% A5% E9% 96% 80-% E6% 97% A5% E7% B5% 8C% E6% 96% 87% E5% BA% AB% E2% 80% 95% E7% B5% 8C% E6% B8% 88% E5% AD% A6% E5% 85% A5% E9% 96% 80% E3% 82% B7% E3% 83% AA% E3% 83% BC% E3% 82% BA-% E6 % AD% A6% E8% 97% A4-% E6% BB% 8B% E5% A4% AB / dp / 4532108292 / ref = sr_1_5? __mk_ja_JP =% E3% 82% AB% E3% 82% BF% E3% 82 % AB% E3% 83% 8A & crid = 3JR92N3EW4M6 & dchild = 1 & keywords =% E3% 82% B2% E3% 83% BC% E3% 83% A0% E7% 90% 86% E8% AB% 96% E5% 85% A5% E9% 96% 80 & qid = 1585324546 & sprefix = ge-murironnnyuumon% 2Caps% 2C373 & sr = 8-5) [Yukihiko Funaki Exercise Game Theory](https://www.amazon.co.jp/%E6%BC%94%E7%BF%92%E3%82%B2%E3%83%BC%E3%83% A0% E7% 90% 86% E8% AB% 96-% E6% BC% 94% E7% BF% 92% E6% 96% B0% E7% B5% 8C% E6% B8% 88% E5% AD% A6 % E3% 83% A9% E3% 82% A4% E3% 83% 96% E3% 83% A9% E3% 83% AA-% E8% 88% B9% E6% 9C% A8-% E7% 94% B1 % E5% 96% 9C% E5% BD% A6 / dp / 4883840727 / ref = sr_1_1? __ mk_ja_JP =% E3% 82% AB% E3% 82% BF% E3% 82% AB% E3% 83% 8A & dchild = 1 & keywords = % E6% BC% 94% E7% BF% 92% E3% 82% B2% E3% 83% BC% E3% 83% A0% E7% 90% 86% E8% AB% 96 & qid = 1585323768 & sr = 8-1)

Usual notes

What is the Shapley value?

It considers how much each player contributes to the formation of a partnership, and determines the distribution of gain to each player based on the degree of contribution. In cooperative game theory, the question is how to distribute the gain after the alliance, and I interpret that one of the distribution methods is the Shapley value. There are also negotiation sets, jin, kernels, etc. as solution concepts, but I think it is easier to apply the Shapley value, which uniquely determines the distribution if the conditions are met. (There is not enough study around here.)

The Shapley value is derived from four axioms, ・ Overall rationality ・ Characteristics related to null players ・ Symmetrical player properties ・ The nature of the sum of the game It meets the above properties. Shapley has proved that there is only one solution that satisfies these four properties. Now is the definition of the Shapley value formula. $ v $: Characteristic function, $ S $: Suppose you have a partnership. Shapley value of player $ i \ in N $ in game $ (N, v) : $ \phi_i(v) = \sum_{S: i \in S \subseteq N} \frac{(s-1)!(n-s)!}{n!}(v(S)-v(S \setminus \{ i \} ))$ here,s = |S|, n = |N|It is said. Also, $ v(S)-v(S \setminus \{ i \} ) $$ Represents the marginal contribution of player $ i \ in S $ in affiliated $ S $. Implement the calculation of this Shapley value.

coding

There are various ways to enter the number of players and affiliated values, but it was easy for me to implement. See also commenting out in the code for more details.

Generate a set of players and partnerships

First, enter the number of players and create a set of alliances.

import itertools
import math

n = int(input()) #Enter the number of players

seq = [str(i+1) for i in range(n)] #Preparation to make a set of alliances
All_set = []
for i in range(n): #A set of alliances(list)Generate a
    comb = list(itertools.combinations(seq,i+1)) 
  #itertools.Generate a unique combination with combination
    All_set.extend(comb)

new_All_set = ['0'] #Keep 0 tie-ups for later calculations
for i in range(len(All_set)): 
    #In the list generated above, each tie-up is a tuple, so modify it to str
    s=""
    a = All_set[i]
    for j in a:
        s += j
    new_All_set.append(s)

zero_set = list(0 for _ in range(len(new_All_set))) #A set of all 0 alliance values(list)

S = new_All_set #A collection of all alliances(list)
V = zero_set    #Set of all affiliated values(list)After that, enter the tie-up value. Still 0 here

Enter tie-up value

If the tie-up value of the tie-up between players 1 and 2 is 2, enter "12 2". I don't think it's neat to have a separate list of tie-ups and tie-up values, but personally it was easier to handle.

for i in range(len(new_All_set)):
    inp = (input().split()) #Process the input of the tie-up value here
    if inp[0] in S: #Input processing if the entered alliance is in the set of alliances
        position = S.index(inp[0])
        V[position] = int(inp[1])
    if inp[0] == "ZERO":
        #When all the remaining tie-up values to be entered become 0, enter ZERO to exit the for statement.
        break

Calculation of Shapley value

sv = []
for i in range(n):
    res = 0
    i_in = [s for s in S if str(i+1) in s] #A set of alliances to which i belongs(list)
    i_not_in = [s for s in S if str(i+1) not in s] #A set of alliances to which i does not belong(list)
    for j in range(len(i_in)):
        res += math.factorial(len(i_in[j])-1) * math.factorial(n-len(i_in[j])) / math.factorial(n) \
        * (V[S.index(i_in[j])] - V[S.index(i_not_in[j])])
    #Calculate Shapley value here
    sv.append(["player"+str(i+1) ,res]) #List each player's Shapley value
print(sv)

that's all. Before I implemented it, I thought it would be longer code, but when I implemented it, it was unexpectedly short.

I'll put the whole code together. (I think it would be nice to put it on Github) You should be able to copy and use it. If you get an error, please let us know in the comments.

import itertools
import math

n = int(input())

seq = [str(i+1) for i in range(n)]

All_set = []
for i in range(n): 
    comb = list(itertools.combinations(seq,i+1))
    All_set.extend(comb)

new_All_set = ['0']
for i in range(len(All_set)): 
    s=""
    a = All_set[i]
    for j in a:
        s += j
    new_All_set.append(s)
    
zero_set = list(0 for _ in range(len(new_All_set))) 

S = new_All_set
V = zero_set

for i in range(len(new_All_set)):
    inp = (input().split())
    if inp[0] in S:
        position = S.index(inp[0])
        V[position] = int(inp[1])
    if inp[0] == "ZERO":
        break

sv = []
for i in range(n):
    res = 0
    i_in = [s for s in S if str(i+1) in s]
    i_not_in = [s for s in S if str(i+1) not in s]
    for j in range(len(i_in)):
        res += math.factorial(len(i_in[j])-1) * math.factorial(n-len(i_in[j])) / math.factorial(n) \
        * (V[S.index(i_in[j])] - V[S.index(i_not_in[j])])
    sv.append(["player"+str(i+1) ,res])
print(sv)

Try to solve the problem

Although it is a standard, let's find the Shapley value in a three-player majority game. (Refer to Exercise Game Theory P.173)

The number of players is three. The tie-up values for each tie-up are as follows.

v(123) = v(12) = v(13) = v(23) = 1 \\
v(1) = v(2) = v(3) = 0

To summarize the input at this time

3 

123 1
12 1 
13 1 
23 1
ZERO

It looks like. The calculation result is as follows.

[['player1', 0.3333333333333333], ['player2', 0.3333333333333333], ['player3', 0.3333333333333333]]

The Shapley value of each player is properly $ \ frac {1} {3} $. That's all for this article. If you have any mistakes or problems, please report them in the comments.

Recommended Posts

Shapley value calculation in Python
Date calculation in python
Date calculation in Python
Quantum chemistry calculation in Python (Psi4)
Accelerometer Alan Variance Calculation in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
[Python] Invert bool value in one line
Constant in python
Let's make a combination calculation in Python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
String → Bool value conversion in Python Consideration
Time comparison: Correlation coefficient calculation in Python
Float calculation circuit (ry-No. 1.1 (float value in hexadecimal notation)
File DL, byte value and delete in Python3
Calculation result after the decimal point in Python
Find the divisor of the value entered in python
Sorted list in Python
Daily AtCoder # 36 in Python
Clustering text in Python
Daily AtCoder # 2 in Python
Implement Enigma in python