Help14:=proc(): print(` WMG(L,q), SSV(L,q), SSVc(L,q)  `):  end:
with(combinat):

#WEIGHTED MAJORITY GAME; Shapley-Shubik Values
#DEF: A WEIGHTED MAJORITY GAME IS A LIST of POSITIVE INTEGERS L
# AND a cutoff q
#PAYOFF f[S]=0 if Sum(S)<q; f[S}=1 if Sum(S)>=q
#IN ISRAEL sum(L)=120, q=61

#WMG(L,q): INPUTS a WIEGHTED-MAJORITY GAME L,q outputs the TABLE of
#PAYOFFS FOR ALL SUBESTS OF {1,..,n} n:=nops(L);
WMG:=proc(L,q) local n,PN,S,f,s:
n:=nops(L):
PN:=powerset(n):

for S in PN do
if add(L[s], s in S)>=q then
 f[S]:=1:
else
 f[S]:=0:
fi:
od:
op(f):
end:

#SSV(L,q): The Shapley-Shubik vector of values of the Weighted Majority game L,q 
SSV:=proc(L,q) : SV( WMG(L,q)   , nops(L)):end:  


#DEF. A PLAYER IS PIVOTAL IF IN A GIVEN ORDERING THE VALUE CHANGES FROM 0 to 1
#PLAYER J is PIVOTAL IF HE ENTER THE ROOM AS THE k-th i_k=J
#L[i1]+L[i2],...+L[i_{k-1}]<q BUT L[i1]+L[i2]+...+L[i_{k-1}]+L[J]>=q
#IN OTHER WORDS player J is PIVOTAL IF HE ENTERS THE ROOM AS the k-th entrant
#FOR ANY PLAYER J, TO GET HIS SHAPLEY VALUE
#
#LOOK at ALL PERMUTATIONS [i1,i2,..i_{k-1}, J, i_{k+1}, ... i_n] such that
#L[i1]+L[i2]+..+L[i_{k-1}]<q, L[i1],L[i2],..L[i_{k-1}]+L[J]>=q
#
#
#   {i_1,..., i_{k-1}  }  J  {i_{k+1}, ..., i_n}
#
#  (k-1)!  *(n-k)!
#
#GIVEN a SET {L[1], ..., L[n]} how may subsets of {1,...,n} are there
#with k elements that they add-up to N
#
#F(k,N): coefficient of z^k*x^N in (1+z*x^L[1])*...*(1+z*x^L[n])

#SSVc(L,q): The Shapley-Shubik vector of values of the Weighted Majority game L,q 
#THE CLEVER WAY
SSVc:=proc(L,q) local n,z,x,f,J,V,i1,k:
n:=nops(L):
V:=[]:

for J from 1 to n do
f:=mul(1+z*x^L[i1],i1=1..J-1)*mul(1+z*x^L[i1],i1=J+1..n):
f:=add(coeff(f,x,i1),i1=q-L[J]..q-1):
V:=[op(V),   add( coeff(f,z,k-1)*(k-1)!*(n-k)!,k=1..n)]:
od:
V/n!:
end:
 
##OLD STUFF
#Maple Code for Lecture 13 of Dr. Z.'s Experimental Mathematics (Game Theory) class
Help13:=proc(): print(`RSG(n,K), SV(f,n), SVp(f,n), SVpF(f,n) `): end:



#RSG(n,K): A random SUPER-ADDITIVE n-person cooperative game
RSG:=proc(n,K) :FM(RG(n,K),n):end:


##SV(f,n): Inputs a Coalition function a function defined on powerset(n) and outputs the list
#of length n, call it L, such that L[i] is the Shapley value
SV:=proc(f,n)  local V,i,g,PN,S,val:
#LET V[i]: The current Shapley value of Player i 

  for i from 1 to n do
    V[i]:=0:
 od:
 g:=BM(f,n):

#g[S]: means: corresponds to the game where the members of S are symmetric to each other and all the
#other players are NULL players, and they get together g[S]
  PN:=powerset(n):
 for S in PN do
   val:=g[S]:
 for i in S do
   V[i]:=V[i]+val/nops(S):
 od:
od:
[seq(V[i],i=1..n)]:
end:

#SVp(f,n): Shapley value with the permutation approach
SVp:=proc(f,n) local S,V,i,pi:

for i from 1 to n do
    V[i]:=0:
 od:

S:=permute(n):

for pi in S do
 for i from 1 to n do
  V[pi[i]]:=V[pi[i]]+ f[{op(1..i,pi)}]-f[{op(1..i-1,pi)}]:
 od:
od:
[seq(V[i]/n!,i=1..n)]:
end:



#Added after class
#SVi(f,n,i): The Shapley value of Player i in the n-person game given by f
#This uses Eq. (13) (and (12), note the typo: n should be n!, i.e. gamma_n(s)=(s-1)!*(n-s)!/n!, where s=|S|)
SVi:=proc(f,n,i) local PS,S:
PS:=powerset(n) minus {{}}:
add((nops(S)-1)!*(n-nops(S))!*(f[S]-f[S minus {i}]),S in PS)/n!:
end:

#SVpF(f,n): Yet another version of SV(f,n), using the above SVi
SVpF:=proc(f,n) local i: [seq(SVi(f,n,i),i=1..n)]:end:


#Stuff from Lecture 12: 
#C12.txt

Help12:=proc(): print(`Ex1(), RG(n,K), FM(f,n), BM(f,n) `): end:

Ex1:=proc():table([({3})=18,({2})=12,({})=0,({1, 3})=60,({2, 3})=90,({1, 2})=30,({1})=6,({1, 2, 3})=120]):end:


with(combinat):

#RG(n,K): inputs an and K outputs a random "n-person game" with entries in [0,K]
RG:=proc(n,K) local ra,PS,S,f:
ra:=rand(0..K):
f[{}]:=0:
PS:=powerset(n):

for S in PS minus {{}} do
f[S]:=ra():
od:
op(f):
end:

#FM(f,n): inputs a function from 2^{1,...n} to pos. real numbres
#we want g(T)= Sum of g(S) over all subsets S of T
FM:=proc(f,n) local S,PS,PN,g,S1:
PN:=powerset(n):
for S in PN do
PS:=powerset(S):
g[S]:=add(f[S1], S1 in PS):
od:
op(g):
end:

#BM(f,n): inputs a function from 2^{1,...n} to pos. real numbres
#we want g(T)= Sum of (-1)^(|T|-|S|)*g(S) over all subsets S of T
BM:=proc(f,n) local S,PS,PN,g,S1:
PN:=powerset(n):
for S in PN do
PS:=powerset(S):
g[S]:=add( (-1)^(nops(S)-nops(S1))*f[S1], S1 in PS):
od:
op(g):
end: