# OK to post homework
# Vikrant, Mar 06 2022, Assignment 13

# ================================================================================
# 0. Code that has been given.
# ================================================================================

read("C13.txt"):

# ================================================================================
# 1. Explain why SVpF = SVp, and why the former is faster for large n.
# ================================================================================

# Fix a player i.
# Define g from S_n to Q_n as g([p_1,p_2,...,p_n]) = {p_1,p_2,...,i}.
# Then it is clear that |g^-1(T)| = 0 if i is not in T and (|T|-1)(n-|T|) otherwise.
# One can then see that SVpF and SVp count the same thing, weighted by f, in different ways.
# SVpF can be seen as a double summation, first over T in Q_n, then over p in g^-1(T).
# SVp, on the other hand, is a summation over p in S_n.

# SVpF takes roughly n2^n operations whereas SVp takes roughly nn! operations, hence SVpF is faster.

# ================================================================================
# 2. Show SV = SVpF (thus SV = SVp).
# ================================================================================

# s = |S|.

# Let S be a subset containing i.
# From SV we can see that f[S] is counted (n-s)C(0)/s - (n-s)C(1)/(s+1) + (n-s)C(2)/(s+2) - ... + (-1)^(n-s)(n-s)C(n-s)/n = (s-1)!(n-s)!/n! times.

# Let S be a subset not containing i.
# From SV we can see that f[S] is counted -(n-s-1)C(0)/(s+1) + (n-s-1)C(1)/(s+2) - (n-s-1)C(2)/(s+3) + ... + (-1)^(n-s)(n-s-1)C(n-s-1)/n = -s!(n-s-1)!/n! times.

# Aggregating the number of times f[S] is counted for all S gives us the ith coordinate of SVpF.

# ================================================================================
# 3. Implement Generalized Shapley Value using the first formula from Wikipedia.
# ================================================================================

with(combinat,powerset):

SVC:=
    proc(f,n,C)
        local S,T,i:
        add(nops(T)!*(n-nops(T)-nops(C))!*add((-1)^(nops(C)-nops(S))*f[S union T],S in powerset(C)),T in powerset({seq(i,i=1..n)} minus C))/(n-nops(C)+1)!:
    end:

# ================================================================================
# 4. Implement Generalized Shapley Value using the second formula from Wikipedia.
# ================================================================================

SVC1:=
    proc(f,n,C)
        local T:
        local Ts:= {seq(`if`(C subset T,T,NULL),T in powerset(n))}:
        local w:=BM(f,n):
        add(w[T]/(nops(T)-nops(C)+1),T in Ts):
    end:

# ================================================================================
# 5. Implement Shapley Value to another player using the formulae from Wikipedia.
# ================================================================================

SVCij1:=
    proc(n,f,i,j)
        local S,t:
        add((nops(S)-1)!*(n-nops(S))!*(f[S]-f[S minus {i}]-f[S minus {j}]+f[S minus {i,j}])*add(1/t,t=nops(S)..n),S in powerset(n))/n!:
    end:

SVCij2:=
    proc(n,f,i,j)
        local T:
        local Ts:= {seq(`if`({i,j} subset T,T,NULL),T in powerset(n))}:
        local w:=BM(f,n):
        add(w[T]/nops(T)^2,T in Ts):
    end: