Axiomatizations of the Shapley value for cooperative games on antimatroids (Q1395144)

The paper provides an axiomatization of the Shapley value in cooperative games in which asymmetries in allowable coalitions is described by restricting the set of possible coalitions to be {antimatroids}. Asymmetries among the players of a cooperative game have been studied in the literature in different ways. In one class of models, the possibilities of coalition formation are determined by the positions of the players in a communication graph. Another type of asymmetry is where the possible coalitions are determined by the positions of players in a hierarchical permission structure. Yet another type of asymmetry is introduced in peer group games in which there are some assumed dependencies among players which is described by a rooted tree. Games on antimatroids includes several such asymmetries as special cases. The paper provides a generalization of axioms given for the permission structures to obtain an axiomatization of the restricted Shapley value for cooperative games on antimatroids. Some details follow. Let \(( N,v) \) denote a cooperative game with \(N=\{1,\dots,n\}\) denoting a finite set of players and \(v:2^{N}\to R\) denoting a characteristic function on \(N.\) An antimatroid \(\mathcal{A}\) on \(N\) is a subset of \(2^{N}\) satisfying A1. \(\emptyset \in \mathcal{A}\), A2. (accessibility) If \(E\in \mathcal{A}\), \(E\neq \emptyset \) then there exists \(i\in E\) \(E\backslash \{i\}\in \mathcal{A}\), A3. (closed under union) If \(E,F\in \mathcal{A}\) then \(E\cup F\in \mathcal{A}\). The paper confines attention to the case of normality, i.e., A.4. For every \(i\in N\) there exists an \(E\in \mathcal{A}\) s.t. \(i\in E.\) The interior operator \(\text{int}_{\mathcal{A}}: 2^{N}\to \mathcal{A}\) is defined by \(\text{int}_{\mathcal{ A}}( E) =\bigcup _{F\subset E,F\in \mathcal{A}}F\in \mathcal{A}\) for all \(E\subset N\). The restricted game \(v_{\mathcal{A}}\) on \(\mathcal{A}\) is defined by \(v_{\mathcal{A}}( E) =v( \text{int}_{\mathcal{A} }( E) )\). The restricted Shapley value is obtained by applying the Shapley value to the game \(v_{\mathcal{A}}\), i.e., \[ \text{Sh}_{i}( v_{\mathcal{A}}) =\sum_{E\subset N,i\in E}\frac{d_{v_{ \mathcal{A}}}( E) }{| E| } \] where \(d_{v}( E) =\sum_{T\subset E}( -1) ^{| E| -| T| }v( T) \) denotes the dividend of the coalition \(E\) in the game \(v\). The paper shows that the restricted Shapley value on such antimatroid games is characterized by the following six axioms: Axiom 1. (Efficiency) For every cooperative game \(v\) and antimatroid \( \mathcal{A}\) on \(N\), \(\sum_{i\in N} f_{i}( v,\mathcal{A}) =v( N.) \) Axiom 2. (Additivity) For every pair of cooperative games \(v,w,f(v+w, \mathcal{A})=f( v,\mathcal{A}) +f( w,\mathcal{A}) .\) Axiom 3. (Necessary player property) For every \(v\) and \(\mathcal{A}\), if \( i\in N\) satisfies \(v( E) =0\) for all \(E\subset N\backslash \{i\}\) then \(f_{i}( v,\mathcal{A}) f_{j}( v,\mathcal{A}) \) for all \(j\in N.\) An endpoint or extreme point of \(E\in \mathcal{A}\) is a player \(i\in E\) s.t. \(E\backslash \{i\}\in \mathcal{A}\), i.e. those players who can leave a coalition. A set \(E\) in \(\mathcal{A}\) is called an \(i\)-{path} if it has \(i\) as a single endpoint. Denote the set of { \(i\)-paths} by \(A( i) .\) Player \(i\) is a {null player} if \( v( E) =v( E\backslash \{i\}) \) for all \(E\subset N.\) The {path group} of player \(i,P^{i}\) is the set of players in some \(i\)-path, i.e., \(P^{i}=\bigcup _{E\in A(i)}E.\) Player \(i\) is an {inessential } player if \(i,\) as well as all players \(j\) s.t. \(i\in P^{j},\) are null players. Axiom 4 (Inessential player property) For every \(v\) and \(\mathcal{A}\), if \(i\) is an inessential player then \(f_{i}( v,\mathcal{A}) =0.\) The basic path group, \(P_{i}\), of a player \(i\), is the set of players in every \(i\)-path (and so without them \(i\) cannot be in any coalition), i.e., \(P_{i}=\bigcap _{EA( i) }E.\) A monotone cooperative game \(v\) is one satisfying \(v( E) \leq v( F) \) whenever \( E\subset F\subset N.\) Axiom 5. (Structural monotonicity) For any \(v\), \(\mathcal{A}\), if \(v\) is monotone then for all \(i,j\) in \(N\) satisfying \(i\in P_{j}\) we have \( f_{i}( v,\mathcal{A}) \leq f_{j}( v,\mathcal{A}) .\) Axiom 6. (Fairness) For any \(v\), \(\mathcal{A}\), if \(E\in \mathcal{A}\) is s.t. \(\mathcal{A}\backslash \{E\}\) is also an antimatroid on \(N\) then \( f_{i}( v,\mathcal{A}) -f_{i}( v,\mathcal{A}\backslash \{E\}) =f_{j}( v,\mathcal{A}) -f_{j}( v,\mathcal{A} \backslash \{E\}) \) for all \(i,j\in E.\) Poset antimatroids are the unique antimatroids such that every player has an unique path. Axioms 1 to 5 characterize the Shapley value for this more restricted class of antimatroid games. An application is provided for some auction situations.