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
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)
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.
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
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
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)
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