What happens when you apply a Permutation function to a Set-function?

53 Views Asked by At

This question is motivated by the original Shapley values paper. On page 70 of this paper, Shapley defines a set of permutation functions $\pi$:

Let $\Pi(U)$ denote the set of permutations of $U$ - that is, the one to one mappings of $U$ onto itself. If $\pi \in \Pi(U)$, then, writing $\pi S$ for the image of $S$ under $\pi$, we may define the function $\pi v$ by: $$\pi v(\pi S) = v(S) \;\;\;\;\;\; (\text{all} \; S \subseteq U )$$

where $U$ is the "universe of all possible players", and $S$ is a subset of all those players. $\Pi (U)$ represents the set of all the possible orderings of players in the universe of players $U$. $v$ is a "superadditive set-function" defined by Shapley as:

$$ v(0) = 0 \\ v(S) \geq v(S \cap T) + v(S - T) \;\;\;\;\; (\text{all}\; S,T \subseteq U).$$

As you can see, $\pi$ can be applied to either $S$ or $v$. The former case is represented by $\pi S$ and makes intuitive sense to me, the function rearranges the elements of the set $S$ into some definite order and returns it.

However, I find the latter case confusing. Applying $\pi$ to something seems to imply that you're rearranging its elements into some definite order. What does that mean when it's applied to the superadditive set function $v$, giving $\pi v$?