#OK to post homework 
#Natalya Ter-Saakov, March 6, Assignment 12
read "C13.txt":

#Problem 1

#Claim: SVpF(f,n)=SVp(f,n)
#Proof: 
#To compare, lets look at the value for player i:
#SVpF(f,n)[i]=add((nops(S)-1)!*(n-nops(S))!*(f[S]-f[S minus {i}]),S in PS)/n!
#SVp[i]=add(f[{op(1..i,pi)}]-f[{op(1..i-1,pi)}], pi in permute(n))
#Consider that no matter what order the first i-1 people come in, or what order the remaining people come in, f[{op(1..i,pi)}]-f[{op(1..i-1,pi)}] will be the same.
# So, since there are  (nops(S)-1)! ways to order everyone before i and (n-nops(S))! ways to order everyone after i, these procedures alwats give the same result

#SVpF is faster (for sufficiently large n) because instead of checking all n! permutations, it only looks at 2^n subsets.

#Problem 2
#Claim: The Shapley value found by the axioms is equal to that found by permutations.
#Proof: Let N be the set {1..n} and t=|T|, s = |S|.  We start by manipulating the formula for the Shapley value found using the axioms. 
#SV(f,n)[i] = Sum_{S subset of N, i in S} 1/s * Sum_{T subset S} (-1)^(t-s)*f(T)
# = Sum_{T subset of N} (-1)^t*f(T) * Sum_{S subset of N, superset of T, i in S} (-1)^S/s
# = Sum_{T subset of N, i in T} [(-1)^t*f(T) * Sum_{t<=s<=n} (-1)^s*(n-t choose s-t)/s + Sum_{T subset of N, i not in T} [(-1)^t*f(T) * Sum_{t+1<=s<=n} (-1)^s*(n-t-1 choose s-t-1)/s
# = Sum_{T subset of N, i in T} (-1)^t*(f[T]-f[T minus {i}]) * Sum_{t<=s<=n} (-1)^s*(n-t choose s-t)/s
# = Sum_{T subset of N, i in T} (f[T]-f[T minus {i}]) * Sum_{0<=s<=n-t} (-1)^s*(n-t choose s)/(s+t)

# We wish to show that this is equal to 
# Sum_{T subset of N} t*(f[T]-f[T minus i])/(n choose t) = Sum_{T subset of N, i in T} t*(f[T]-f[T minus i])/(n choose t)
# So we have reduced the problem to showing that 
# Sum_{0<=s<=n-t} (-1)^s*(n-t choose s)/(s+t) = t/(n choose t)

#This is the same as proving that Z(n,t) = Sum_{0<=s<=n-t} u(n,t,s) =1 where  u(n,t,s) = (-1)^s*(n-t choose s)*n! / ((s+t)*(t-1)!*(n-t)!) = (-1)^s*n!/((s+t)*s!*(n-t-s)!*(t-1)!)
#It can be verified that
# u(n+1,t,s)-u(n,t,s) = w(n,t,s+1)-w(n,t,s)
# where w(n,t,s) = u(n,t,s)*s*(s+t) / ((t+s-n-1)*(n-t+1)).
#We can sum the pervious equation from s=0 to n-t to get
# Z(n+1, t)-Z(n,t) = G(n,t,n-t+1) - G(n,t,0) = 0 
# which tells us that Z(k,t) = Z(t,t) for all k>=t.
#Then Z(n,t) = Z(t,t) = u(t,t,0) = 1

#Therefore, the value found using atomic games is the same as the one found by permutations.

#Problem 3
#SVC(f,n,C) inputs a game f, n and a coalition C and outputs the Generalized Shapley value for that coalition

SVC:= proc(f,n,C) local c,N, PN, PC, v, t, T, i, S:
c:=nops(C): 
v:=0:
N:={seq(i,i=1..n)} minus C:
PN:= powerset(N):
PC:=powerset(C):
for T in PN do
	t:=nops(T):
	v+=(n-t-c)!*t!/(n-c+1)!*(add((-1)^(c-nops(S))*f[S union T], S in PC)):
od:
v:
end:

#Problem 4
#SVC1(f,n,C) inputs a game f, n and a coalition C and outputs the Generalized Shapley value for that coalition

SVC1:= proc(f,n,C) local g, c, N, PN, i, S, v:
c:=nops(C):
v:=0:
g:=BM(f,n):
N:={seq(i,i=1..n)} minus C:
PN:=powerset(N):
for S in PN do
	v+=g[S union C]/(nops(S)+1):
od:
v:
end:

#Problem 5
#SVij1(n,f,i,j) and SVij2(n,f,i,j)
SVij1:= proc(n,f,i,j) local N, PN, S, s, t, v,k:
v:=0:
N:={seq(k,k=1..n)} minus {i,j}:
PN:=powerset(N):
for S in PN do
	S:=S union {i,j}:
	s:=nops(S):
	v:=v+(s-1)!*(n-s)!*(f[S]-f[S minus {i}]-f[S minus {j}]+f[S minus {i,j}])*add(1/t, t=s..n)/n!:
od:
v:	
end:

SVij2:=proc(n,f,i,j) local N, PN, S, v, g,k:
v:=0: 
g:=BM(f,n):
N:={seq(k,k=1..n)} minus {i,j}:
PN:=powerset(N):
for S in PN do
	v+=g[S union {i,j}]/(nops(S union {i,j}))^2:
od:
v:
end:

CheckEqual:=proc(n,K) local f, j, i:
f:=RSG(n,K):
for i from 1 to n do
if not (add(SVij1(n,f,i,j),j=1..n)=SVi(f,n,i) and add(SVij2(n,f,i,j),j=1..n)=SVi(f,n,i)) then return false: fi:
od:
true:
end:

#CheckEqual returns true!