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

The purpose of this article is not to learn programming, but to better understand economics using a tool called programming.
If you find any inadequacies, please leave a comment.
Addition: I noticed after posting, but some people have already implemented it in Python. "Calculate contribution value with shapley value" by shiibass

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

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.