Value theory without symmetry (Q1423676)

A cooperative game with \(n\) participants can be characterized by its characteristic function \(v(S)\) -- that describes, for each set \(S\subseteq I=\{1,2,\ldots,n\}\), the amount that players from \(S\) can gain if they team together against all others. One of the main questions of cooperative game theory is how to transform this description into a fair division \((x_1,\ldots,x_n)\) of the overall gain \(v(I)\). In 1953, Shapley formulated natural requirements that a fair function \(v\to x\) should satisfy, and showed that under these requirements, there is only one such function -- Shapley value. Computing the Shapley value requires that we process the values \(v(S)\) for all \(2^n\) subsets \(S\). For realistic conflict situations with hundreds of participants, the resulting exponential (\(2^n\)) number of computational steps is unrealistically high. This problem can be solved if we take into account that the Shapley value \(x_i\) of \(i\)-th player is equal to the expected value of the marginal gain \(v(\{i_1,\ldots,i_k=i\})-v(\{i_1,\ldots,i_{k-1}\})\) of this player when we add the players in random order \(i_1<i_2<\ldots\) Because of this equality, we can efficiently compute \(x_i\) by using Monte-Carlo simulations. One of the conditions behind Shapley value is the condition of symmetry -- that the results should not depend on the ordering of the players. This requirement makes sense if all the players are participants of equal status. However, in some conflict situations, we have several different classes of players: e.g., patients, medical doctors, and insurance companies. While it makes sense to require symmetry between different patients, there is no symmetry between a patient and a doctor. To describe such situations, researchers have proposed \textit{quasi-values}, i.e., mappings \(v\to x\) that satisfy all Shapley's requirements except for symmetry. Quasi-values are often defined explicitly, which raises the same computational problem as with the Shapley value. The author shows that, similar to the Shapley value, every quasi-value can be described (and thus computed) as the expected marginal gain in a random ordering based on the ordering of random values \(\chi_i\) -- where, in contrast to the original Shapley value, we may have different probability distributions for different \(\chi_i\).