Cooperative games with additive multiple attributes

Abstract

This paper studies cooperative games in which players have multiple attributes. Such games are applicable to situations in which each player has a finite number of independent additive attributes in cooperative games and the payoffs of coalitions are endogenous functions of these attributes. The additive attributes cooperative game, which is a special case of the multiattribute cooperative game, is studied with respect to the core, the conditions for existence and boundedness and methods of transformation regarding a general cooperative game. A coalitional polynomial form is also proposed to discuss the structure of coalition. Moreover, a Shapley-like solution called the efficient resource (ER) solution for additive attributes cooperative games is studied via the axiomatical method, and the ER solution of two additive attribute games with equivalent total resources coincides with the Shapley value. Finally, some examples of additive attribute games are given.

Keywords

Multiple attributes cooperative games Shapley value core solution

1 Introduction

The classical model of cooperative games with transferable utility (TU games) describes a situation in which every coalition of players can obtain certain transferable payoffs by means of cooperation. A TU game consists of a set of players and a characteristic function that assigns exogenously to each subset of players (coalition) a real number representing the value of the coalition (payoff). The solutions of cooperative games are divided into set-valued solutions and single-valued solutions. Set-valued solutions are typically represented by cores [24]. There are many single-valued solutions, such as the Shapley value, nucleolus, kernel, and τ value, of which the Shapley value is particularly important [21].

Symmetry is one of the essential axioms of the Shapley value axiomatic system. As a result, the Shapley value does not reflect individual differences among players, which makes the Shapley value limited in some practical applications. Shapley himself was the first to admit that differences in the bargaining power of alliance members may undermine the assumption of symmetry [21]. According to Winter, asymmetry in the alliance members may result from many factors, such as communication problems among members [2]. For example, in a two-person zero-normalized cooperative game, the Shapley value is the allocation whereby the profits from cooperation are distributed equally between the two players [8, 13]. If one of the players devotes more resources or effort or has greater negotiation ability in the collaboration, he or she should obtain more benefits than the other. Shapley was the first to study this problem and proposed the weighted Shapley value, which exogenously grants each player a positive weight. In this way, in certain cases, the Shapley value can become a weighted Shapley value in which all players have the same weight. Kailai modeled the nonsymmetries through nonsymmetric weighting systems defined on the players of games [13]. Owen suggested that the special weights in Shapley’s thesis should be regarded as coefficients of the slowness of reaching a decision [18]. He presented a generalization of the Shapley value for a multilinear extension of an n-person game [19]. Myerson described the Shapley value for a restricted game, now called the Myerson value, by assuming that the nodes in the graph are the players and that each link represents a direct bilateral communication channel [15, 16]. According to González-Arangüena et al., the weight of a link can be interpreted as the capacity of the communication channel, the flow across it, the intimacy or intensity of the relation, the distance between two incident nodes/players, the cost of building or maintaining the communication link or even the probability of the relation [5, 9]. Haeringer proposed a new weighting scheme for the Shapley value that allows us to interpret weights as a bargaining power measure [10]. Belau provided a computationally efficient formula for the Owen value (and the component-restricted Shapley value) for glove games in the case of minimal winning coalitions [3]. There are many studies of cooperative games in which players have weights. Most of them employ Shapley-based allocation rules [9 , 25]. There are still two problems in the application of weighted Shapley values. First, the weights of players can only reflect differences in one aspect. However, players will differ in many aspects. For example, in the cooperation between two players, there are often differences in the investment of funds, the effective time, fixed assets and individual ability. Second, the weights of players are exogenously given, as is the profit of the coalition, so there will be an inconsistency between them. For example, players with fewer resources (small weights) have greater marginal contributions and vice versa. This kind of inconsistency caused by exogenous assignment has generated controversy and confusion regarding the allocation of grand coalition profits in practical applications. Focusing on these problems, we propose additive attribute games, that is, assigning players a positive vector weight to reflect the differences between players. Each component of the vector represents a kind of difference, which we call an attribute in this paper. These vectors are also called resource vectors to describe the various attributes that a player has. In this article, these attributes are limited to additive properties. Their values are measured by the transferable utility in the economy. That is, in terms of numerical value, each attribute unit has a unified standard scale. For example, in the glove market [22 –24], players have left-handed gloves or right-handed gloves, and the value of the coalition is the number of matched gloves. Alternatively, the assignment game is divided into buyers and sellers, and the value of the coalition is the number of matched demands of both parties. Inspired by this, we propose a class of cooperative games with multiattribute players in which the payoffs of the coalitions are only derived from the attributes of the players in the coalition. There are many works on cooperative games with multiattributes. In the early literature, the notion of multiple attributes focused on committee control [6] or skill [27]. These models are obviously different from our model in terms of the definition of characteristic functions. Multiattribute coalitional games (MACGs) were proposed by Samuel Ieong and Yoav Shoham [12]. In MACGs, the value of cooperation among the agents is solely determined by the attributes that the agents possess, with no assumption of how these attributes jointly determine this value. Hence, the MACG model is suitable for updates. Our model differs from the MACG model in two ways: One is in the operations over the attributes, for which there is no restriction on the operation in the MACG model, whereas ours is the opposite. The other is the relation between the attribute model and the value function, which are clearly separated in the MACG model but are consistent in our model. TU games with multiple attributes (TU-MA games) were proposed by S. Borkotokey et al., who defined the characteristic function as a function that “defines the worth of a coalition with multiple attributes based on the values obtained from the original TU games associated with it and a suitable aggregation function that aggregates players’ contributions in different attributes" [4]. The TU-MA games mainly extend the notion of cooperative games with fuzzy coalitions. In the TU-MA model, the characteristic function depends on two factors: the characteristic function of the original TU games and the multiattribute matrix, both of which are exogenous. However, the characteristic function in our model is determined endogenously only by the resource matrix. In addition, our paper mainly focuses on the mechanism of cooperation, such as superadditivity and the coalition structure, and the relationship between different cooperative games and the additive attribute games, such as the transformation conditions and methods between general cooperative games and multiattribute cooperative games. The rest of this paper is organized as follows. In Section 2, we review some notions of cooperative games. In Section 3, we propose an additive attributes cooperative game and describe its properties. In Section 4, the coalition polynomial form for the additive attribute game is proposed. In Section 5, the efficient resource (ER) solution of the additive attributes cooperative game is proposed, and the axiomatic system of the solution is established. In Section 6, the core of the additive attribute game is discussed. In Section 7, the ER value of the additive attribute game is compared with the Shapley value via some examples in which the ER solution of two additive attribute games with total resource equivalents coincides with the Shapley value. Our conclusions are presented in Section 7.

2 Preliminary

A TU game is a pair (N, v), where N = {1, 2, …, n} is a finite set of players and $v : 2^{N} \to ℝ$ is a characteristic function assigning to each coalition of players, S ∈ 2^N, its payoff v (S), with v (∅) =0. The members of S can obtain the total joint payoff v (S). The class of TU games with fixed player set N is denoted by $G^{N}$ . A game (N, v) is monotonic if v (T) ≤ v (S) for ∀T ⊆ S ⊆ N . A game (N, v) is convex if v (S) + v (T) ≤ v (S ∪ T) + v (S ∩ T) for all S, T ⊆ N . A game (N, v) is superadditive if v (S) + v (T) ≤ v (S ∪ T) for ∀S, T ⊆ N and S ∩ T = ∅ . A real-valued vector x = (x₁, x₂, ⋯ , x_n) is said to be an imputation if x (N) = v (N) and x_i ≥ v ({i}) for all i ∈ N, where x (N) = ∑_i∈Nx_i . The core is the set of all imputations x for which x (S) ≥ v (S) for all S ⊂ N, $C (x) = {x \in ℝ^{n} : x (N) = v (N), x (S) \geq v (S), \forall S \subset N} .$ A value on G (N) is a function φ that assigns a unique vector $φ (v) \in ℝ^{n}$ to each game (N, v) ∈ G (N), where φ_i (v) represents the payoff to player i ∈ N. One of the well-known single values for TU games is the Shapley value, defined by ${Sh}_{i} (v) = \sum_{S \subseteq N \ {i}} \frac{| S |! (n - | S | - 1)!}{n!} [v (S \cup {i}) - v (S)],$ (1) for any game (N, v) ∈ G (N) and any i ∈ N . For each T ⊆ N, the unanimity game u_T is defined by u_T (S) =1 if T ⊆ S, and u_T (S) =0 otherwise. Every game (N, v) ∈ G (N) can be uniquely written as $v = \sum_{T \subseteq N : T \neq \emptyset} Δ_{v} (T) u_{T},$ (2) where the coefficients Δ_v (T) are the Harsanyi dividends [11]. By applying the Möbius transformation, it follows that $Δ_{v} (S) = \sum_{T \subseteq S} (- 1)^{| S | - | T |} v (T), \forall S \subseteq N .$ (3) Some values for TU games are defined based on distributing the Harsanyi dividend of each coalition T among the players in T, such as the so-called Harsanyi solutions [1 , 26], the Shapley value [11, 21] and the weighted Shapley value [13, 17].

3 Additive attribute games

In the real world, players engaged in cooperation always differ in some respect. These differences enable them to complement one another to achieve cooperation and mutual benefit. Therefore, the payoff from cooperation is often greater than the sum of individual payoffs in the coalition. Inspired by the example of the glove market, we construct a cooperative game in which the players have the multiple attribute set $A = {a_{1}, a_{2}, \dots, a_{m}}$ . Assuming that the payoffs from cooperation are entirely determined by the attributes of the players and ignoring the effect of other extraneous factors, the attribute set $A$ satisfies attribute independence and completeness, which means that the attributes can be changed independently without affecting other attributes while simultaneously not being affected by other attributes. The completeness of the attribute set also means that the generation of each unit of payoff contains one unit for each attribute in the attribute set. Our model is based on this assumption. Taking the glove market as an example, in the attribute set $A = {a_{1}, a_{2}}$ , a₁ represents a left-hand glove, and a₂ represents a right-hand glove. Then, each player has two values for this attribute set as the vector (n₁, n₂), which represent the numbers of left-hand gloves and right-hand gloves, respectively, and the characteristic value is the minimum value of the matching gloves. If player set N = {1, 2}, player 1 is (3, 0), player 2 is (0, 5), and then V ({1, 2}) = min {3, 5} =3. Not only the glove market but also products such as cell phones and automobiles are composed of a number of accessories, the production of which is undertaken by different manufacturers. If the manufacturer is regarded as a player, different accessories correspond to different attributes, and the assembly of accessories into intermediate products or final products will produce different values, which is also the result of the cooperation of players. In practical applications, the generation of cooperative value is completed by multiple independent attributes, such as assembly line production, logistics and transportation, which have the common feature that the final output is determined by the minimum attribute of resources. This phenomenon is also known as the "bucket effect" (also known as Cannikin’s law, Leibig’s law of the minimum, the barrel effect, and the cask effect), which refers to a bucket filled with water. How much water a bucket holds depends not on the longest piece of wood but on the shortest piece of wood. It was introduced by Laurence J. Peter. Our proposed model can be viewed as a quantitative application of this effect. Therefore, we present the following definition.

Definition 1. Suppose that the payoffs of a cooperative game (N, v) are only related to the additive attribute set $A^{+} = {α_{1}, α_{2}, \dots, α_{m}}$ and that the elements in the attribute set are independent. The index set of $A^{+}$ is M = {1, 2, ⋯ , m}. Each player i has a vector R (i) = (a_i,1, a_i,2, ⋯ , a_i,m) ≥0, which is called the player’s resource vector. A = (a_i,j) _n×m is called the resource matrix. Let the vectors have a normal vector addition operation; then, the coalition S also corresponds to a vector R (S) = (∑_i∈Sa_i,1, ∑_i∈Sa_i,2, ⋯ , ∑_i∈Sa_i,m), with respect to the attribute set $A^{+}$ . The characteristic function is defined as follows: $v_{A} (S) = min_{j \in M} \sum_{i \in S} a_{i, j}, for \forall S \in 2^{N} and v (\emptyset) = 0 .$ (4) This cooperative game is called a cooperative game with players of attributes $A^{+}$ . For simplicity, we call this game an additive attribute game, denoted by (N, v_A). All additive attribute games are denoted by ${AG}^{+}$ .

From the definition, it is obvious that the characteristic function of the additive attribute game (N, v_A) can be determined when the matrix A is given. For example, the additive attribute set $A^{+}$ is a finite set determined by the actual problem. A cooperative game with m additive attributes, game $(N, v_{A}) \in {AG}^{+}$ , is called a single-attribute game when m = 1, a two-attribute game when m = 2, and so forth.

Definition 2. An attribute is called a key attribute if the characteristic function changes when the attribute is cut off. The attribute is called a redundant attribute if there is no change in the characteristic function when the attribute is cut off.

Theorem 1. For any single-attribute game $(N, v_{A}) \in {AG}^{+}, A = (a_{i})_{n \times 1}$ , (N, v_A) is an inessential and constant-sum game.

Proof. A = (a_i) _n×1, i.e., (N, v_A) is a single-attribute game, ∀S ⊆ N, v_A (S) = ∑_i∈Sa_i, it holds that, for ∀S, T ⊆ N, S∩ T = ∅, $v_{A} (S) + v_{A} (T) = \sum_{i \in S} a_{i} + \sum_{j \in T} a_{j} = \sum_{i \in S \cup T} a_{i} = v_{A} (S \cup T) .$ Thus, (N, v_A) is inessential. Let T = N \ S, and then we have v_A (S) + v_A (N \ S) = v_A (N); therefore, (N, v_A) is also a constant-sum game.

From Theorem 1, we discuss the essential additive attribute game in which players have more than two attributes in the following paragraph.

Definition 3. For any additive attribute game $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m} \geq 0, M = {1, 2, \dots, m},$ game (N, v_A) satisfies the resource proportion property (RPP) if v_kA (S) = kv_A (S) , ∀ k > 0, S ⊆ N .

Property 1. Any additive attribute game $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m} > 0, M = {1, 2, \dots, m},$ satisfies monotonicity, superadditivity and RPP.

Proof. Suppose that ∀T ⊆ S ⊆ N, from Definition 1, it holds that $\begin{matrix} v_{A} (T) & = & min_{j \in M} \sum_{i \in T} a_{i, j} \leq min_{j \in M} (\sum_{i \in T} a_{i, j} + \sum_{i \in S \ T} a_{i, j}) \\ = & min_{j \in M} \sum_{i \in S} a_{i, j} = \leq v_{A} (S), \end{matrix}$ which shows that (N, v_A) satisfies monotonicity. Superadditivity is proven below. ∀S, T⊆ N, S ∩ T = ∅, it holds that $\begin{matrix} v_{A} (S) + v_{A} (T) & = & min_{1 \leq j \leq m} \sum_{i \in S} a_{i, j} + min_{1 \leq j \leq m} \sum_{i \in T} a_{i, j} \\ \leq & min_{1 \leq j \leq m} \sum_{i \in S \cup T} a_{i, j} \\ = & v_{A} (S \cup T) . \end{matrix}$ Therefore, (N, v_A) satisfies superadditivity. For any k > 0, A ≥ 0, it follows that kA = (ka_i,j) _n×m ≥ 0 . Hence, for any S ⊆ N, it holds that $v_{kA} (S) = min_{j \in M} \sum_{i \in S} k a_{i, j} = k min_{j \in M} \sum_{i \in S} a_{i, j} = {kv}_{A} (S),$ which shows that (N, v_A) satisfies RPP. The proof is complete.

Property 2. For any additive attribute game $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m} > 0, M = {1, 2, \dots, m}$ , if there exists an attribute k ∈ M such that a_i,k = 0 for ∀i ∈ S ⊆ N, then v (S) =0 .

Proof. By definition 1, and S ⊆ N, ∃ k ∈ M such that a_i,k = 0, , it holds that $v_{A} (S) = min_{j \in M} \sum_{i \in S} a_{i, j} = \sum_{i \in S} a_{i, k} = 0 .$

Note that the additive attribute game $(N, v_{A}) \in {AG}^{+}$ may satisfy superadditivity but not convexity, e.g., N = 1, 2, 3 and the players’ resource vectors are (1, 0) , (0, 1) , (0, 2). Hence, $A = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 2 \end{matrix}),$ and its characteristic function is v_A (∅) =0, v_A ({i}) =0, i = 1, 2, 3, v_A ({2, 3}) =0, v_A ({1, 2}) = v_A ({1, 3}) = v_A ({1, 2, 3}) =1. One can easily check the superadditivity; however, v_A ({1, 2}) + v_A ({1, 3}) ≥ v_A ({1, 2, 3}) + v_A ({1}), which shows that convexity is not satisfied. The following definitions are given to facilitate the following discussion.

Definition 4. A vector $\bar{r} = (r, r, \dots, r)$ is said to be a resource equalization (RE) vector if each row consists of the same elements. A matrix $\bar{C}$ is said to be an RE matrix if each row of the matrix consists of RE vectors. $\begin{matrix} \bar{C} = {(\begin{matrix} c_{1} & c_{1} & \dots & c_{1} \\ c_{2} & c_{2} & \dots & c_{2} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ c_{n} & c_{n} & \dots & c_{n} \end{matrix})}_{n \times m} . \end{matrix}$ An additive attribute game $(N, v_{A}) \in {AG}^{+}$ is called an RE game if A is an RE matrix.

Property 3. For any $(N, v_{A}), (N, v_{A^{'}}) \in {AG}^{+}$ , any constant k > 0 and any constant numbers $c_{1}, c_{2}, \dots, c_{n} \geq 0, A^{'} = A + \bar{C}$ , where $\bar{C}$ is an n × m-dimensional RE matrix, v_A′ (S) = kv_A (S) + ∑_i∈Sc_i .

Proof. Let A = (a_i,j) _n×m, M = {1, 2, ⋯ , m}, and $A^{'} = kA + \bar{C} = ({ka}_{i, j} + c_{i})_{n \times m} .$ For ∀S ∈ 2^N \ {∅} , $\begin{matrix} v_{A^{'}} (S) & = & min_{j \in M} \sum_{i \in S} ({ka}_{i, j} + c_{i}) \\ = & min_{j \in M} \sum_{i \in S} k a_{i, j} + \sum_{i \in S} c_{i} \\ = & k min_{j \in M} \sum_{i \in S} a_{i, j} + \sum_{i \in S} c_{i} \\ = & k v_{A} (S) + \sum_{i \in S} c_{i} \end{matrix}$ and the proof is complete.

Definition 5. Given two cooperative games u and v, if there exists a constant k > 0 and a real number a_i such that $v (S) = ku (S) + \sum_{i \in S} a_{i}, \forall S \subseteq N,$ then u and v are said to be strategically equivalent, denoted by u ∼ v .

Corollary 1. For any $(N, v_{A}), (N, v_{A^{'}}) \in {AG}^{+}$ , any constant k > 0 and any constant numbers $c_{1}, c_{2}, \dots, c_{n} \geq 0, A^{'} = A + \bar{C}$ , where $\bar{C}$ is an n × m-dimensional RE matrix, (N, v_A) and (N, v_A′) are strategic equivalences.

Proof. By definition 5 and property 3, it holds that (N, v_A) ∼ (N, v_A′).

Theorem 2. Given attribute game $(N, v_{\bar{A}}) \in {AG}^{+}$ , $\bar{A}$ is an n × m-dimensional RE matrix; then, $(N, v_{\bar{A}})$ is an inessential and constant-sum game.

Proof. ∀S, T⊆ N, S ∩ T = ∅, $\bar{A} = (a_{i, j})_{n \times m}$ is an RE matrix, M = {1, 2, ⋯ , m} , it holds that $\begin{matrix} v_{\bar{A}} (S) + v_{\bar{A}} (T) & = & min_{j \in M} \sum_{i \in S} a_{i, j} + min_{j \in M} \sum_{i \in T} a_{i, j} \\ = & min_{j \in M} \sum_{i \in S \cup T} a_{i, j} \\ = & v_{\bar{A}} (S \cup T) \end{matrix}$ Therefore, $(N, v_{\bar{A}})$ is inessential. $\begin{matrix} v_{\bar{A}} (S) + v_{\bar{A}} (N \ S) & = & min_{j \in M} \sum_{i \in S} a_{i, j} + min_{j \in M} \sum_{i \in N \ S} a_{i, j} \\ = & min_{j \in M} \sum_{i \in N} a_{i, j} \\ = & v_{\bar{A}} (N), \end{matrix}$ so $(N, v_{\bar{A}})$ is also constant-sum. The proof is complete.

The characteristic value of attribute games is endogenous to the players’ resource vectors, so the characteristic values on coalitions must be bounded. The following discusses the upper and lower bounds of the characteristic value of attribute games.

Theorem 3 (boundedness) Given an arbitrary additive attribute game $(N, v_{A}) \in {AG}^{+}$ with any constant 1 ≤ k ≤ n and cluster D = {S|S ∈ 2^N \ ∅ , |S| = k}, it holds that $\sum_{S \in D : | S | = k} v_{A} (S) \leq C_{n - 1}^{k - 1} v_{A} (N) .$ (5)

Proof. Let N = {1, 2, ⋯ , n} be the player set, A = (a_i,j) _n×m be the player resource matrix, and $A^{+} = {α_{1}, α_{2}, \dots, α_{m}}$ be the additive attribute set. By Definition 1, it follows that $v_{A} (N) = min_{1 \leq j \leq m} \sum_{i \in N} a_{i, j}$ . Without loss of generality, on the attribute $α_{t} \in A^{+}$ , we have v_A (N) = ∑_i∈Na_i,t with 1 ≤ t ≤ m. For ∀S ∈ D, it holds that $v_{A} (S) = min_{1 \leq j \leq m} \sum_{i \in S} a_{i, j} \leq \sum_{i \in S} a_{i, t}$ From the definition of D, it follows that $| D | = C_{n}^{k}$ ; since |S| = k, then the total number of ∑_i∈Na_i,t in D is $k C_{n}^{k} / n$ , which is also the total number of v (N). Therefore, add all the v (S) corresponding to all S in D to obtain $\begin{matrix} \sum_{S \in D} v_{A} (S) & = & \sum_{S \in D} {min_{j} \sum_{i \in S} a_{i, j}} \\ \leq & \sum_{S \in D} \sum_{i \in S} a_{i, t} \\ = & \frac{k}{n} C_{n}^{k} v_{A} (N) \\ = & C_{n - 1}^{k - 1} v_{A} (N) . \end{matrix}$ The proof is complete.

As a special case, we have the following corollary.

Corollary 2. Given an arbitrary additive single-attribute game $(N, v_{A}) \in {AG}^{+}$ with any constant 1 ≤ k ≤ n and cluster D = {S|S ∈ 2^N \ ∅ , |S| = k}, it holds that $\begin{matrix} \sum_{S \in D} v_{A} (S) = C_{n - 1}^{k - 1} v_{A} (N) . \end{matrix}$ From the proof of the above theorem, we can obtain the following corollary.

Corollary 3. Given an arbitrary additive attribute game $(N, v_{A}) \in {AG}^{+}$ with constant 0 ≤ k ≤ n and cluster D = {S|S ∈ 2^N \ ∅ , |S| = k}, it holds that $\begin{matrix} \sum_{S \in D} \sum_{i \in S} l_{i} \leq \sum_{S \in D} v_{A} (S) \leq C_{n - 1}^{k - 1} v_{A} (N) \leq \sum_{S \in D} \sum_{i \in S} L_{i}, \end{matrix}$ where l_i = min {a_i,j| ∀ j ∈ M} is the minimum resources of player i and L_i = min {a_i,j| ∀ j ∈ M} is the maximum resources of player i.

Next, we discuss the method of transforming a given cooperative game into an attribute game and what conditions can be satisfied to convert it into an attribute game.

Theorem 4. For a given cooperative game (N, v) ∈ G, there exists an attribute game $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m} \geq 0, M = {1, 2, \dots, m}$ such that $v_{A} (S) = v (S), \forall S \in 2^{N},$ (6) if and only if the equations corresponding to attribute game (N, v_A) have a solution $\prod_{j = 1}^{m} [\sum_{i \in S} x_{i, j} - v (S)] = 0,$ (7) $\sum_{i \in S} x_{i, j} \geq v (S),$ (8) where ∀S ∈ 2^N and ∀j ∈ M.

Proof. By the Definition 1 of an additive attribute game, it holds that $min_{j \in M} \sum_{i \in S} x_{i, j} = v (S), \forall S \in 2^{N} .$ (9) The resource matrix M can be determined when Equation (9) has a solution and vice versa. Therefore, WLOG, there exists an attribute k such that ∑_i∈Sx_i,k = v (S), and it follows that Equations (7) and (8) hold. If there is no solution to Equations (7) and (8), and thus Equation (9) cannot hold for any attribute, then there is no attribute game $(N, v_{A}) \in {AG}^{+}$ satisfying v_A (S) = v (S) for ∀S ∈ 2^N.

Example 1. Consider the game (N, v) with N = {1, 2, 3}, and the characteristic function is given by v (∅) =0, v (i) =0 for i = 1, 2, 3, v (1, 2) =2, v (1, 3) =0, v (2, 3) =1, v (1, 2, 3) =3. Suppose that we need to find a two-attribute game (N, v_A) to satisfy Equation (6). According to Theorem 4, we have the nonlinear equations ${\begin{matrix} x_{1, 1} x_{1, 2} = 0 \\ x_{2, 1} x_{2, 2} = 0 \\ x_{3, 1} x_{3, 2} = 0 \\ (x_{1, 1} + x_{2, 1} - 2) (x_{1, 2} + x_{2, 2} - 2) = 0 \\ (x_{1, 1} + x_{3, 1}) (x_{1, 2} + x_{3, 2}) = 0 \\ (x_{2, 1} + x_{3, 1} - 1) (x_{2, 2} + x_{3, 2} - 1) = 0 \\ (x_{1, 1} + x_{2, 1} + x_{3, 1} - 3) (x_{1, 2} + x_{2, 2} + x_{3, 2} - 3) = 0 . \\ x_{i, j} \geq 0, i \in N, j \in M . \end{matrix}$ One of the solutions of the equations is {(0, 2) , (3, 0) , (0, 1)}, which is the resource vector of 3 players. This solution is not unique because {(2, 0) , (0, 3) , (1, 0)} is also one of its solutions. Equivalently, we can also obtain the same result by solving the following system of equations: ${\begin{matrix} min {x_{1, 1}, x_{1, 2}} = 0 \\ min {x_{2, 1}, x_{2, 2}} = 0 \\ min {x_{3, 1}, x_{3, 2}} = 0 \\ min {x_{1, 1} + x_{2, 1}, x_{1, 2} + x_{2, 2}} = 2 \\ min {x_{1, 1} + x_{3, 1}, x_{1, 2} + x_{3, 2}} = 0 \\ min {x_{2, 1} + x_{3, 1}, x_{2, 2} + x_{3, 2}} = 1 \\ min {x_{1, 1} + x_{2, 1} + x_{3, 1}, x_{1, 2} + x_{2, 2} + x_{3, 2}} = 3 . \end{matrix}$ If we need to find a three-attribute game (N, v_A) to satisfy Equation (6), then equations similar to the above nonlinear equations from Equation (9) can be solved, and one of the solutions is {(0, 2, 2) , (3, 0, 0) , (0, 1, 1)}.

Theorem 5. For an arbitrary cooperative game (N, v) ∈ G, all the additive attribute games (N, v_A) such that Equation (9) holds are strategically equivalent.

Proof. By Theorem 4, each game (N, v_A) is strategically equivalent to game (N, v).

Theorem 6. For an arbitrary cooperative game (N, v) ∈ G, there are additive attribute games $(N, v_{A}) \in {AG}^{+}$ such that Equation (9) holds, whose necessary condition is that game (N, v) satisfies monotonicity, superadditivity and boundedness.

Proof. By property 1 and Theorem 3, the necessity is obvious.

Example 2. Consider the cooperative game (N, v) with N = 1, 2, 3; the characteristic function is given by v (∅) =0, v ({i}) =1 for i = 1, 2, 3, v ({1, 2}) =2, v ({1, 3}) =4, v ({2, 3}) =2, v ({1, 2, 3}) =4.

One can verify that game (N, v) satisfies monotonicity and boundedness but not superadditivity for v (1, 3) + v (2) > v (1, 2, 3). If some of the values of the coalition change, i.e., v (1, 2, 3) =5, then superadditivity will be satisfied. One solution of the two-attribute game is {(3, 1) , (1, 1) , (1, 3)}, and the solution of the three-attribute game may be {(1, 3, 1) , (1, 1, 1) , (3, 1, 3)}; both solutions are strategically equivalent by Theorem 5. Furthermore, suppose that v (3) =3; then, there is no solution to game (N, v), again because monotonicity and superadditivity cannot be satisfied but boundedness can be satisfied. This demonstrates the independence of superadditivity and boundedness.

4 The coalition polynomial form of the additive attribute game

In this section, a coalition polynomial form is proposed to express the coalition structure in the additive attribute game. In the previous discussion, the coalition is expressed by the resource vector, which is the accumulation of the resource vectors of players who make up the coalition. Moreover, the payoffs of the coalitions and players can be uniquely determined by their resource vectors in the additive attribute games. Next, the features will be used to build the coalition polynomial form in the resource vector space.

Definition 6. Let σ: $R^{m} \times R^{m} \to R^{m}$ be a vector function defined by $σ (x, y) = (σ_{1} (x_{1}, y_{1}), σ_{2} (x_{2}, y_{2}), \dots, σ_{m} (x_{m}, y_{m}))$ where x = (x₁, x₂, ⋯ , x_m), y = (y₁, y₂, ⋯ , y_m),and $σ_{i} : R \times R \to R, (i = 1, 2, \dots, m)$ is a real-valued binary function on the components of the vector. Suppose that σ satisfies

Commutativity:σ ( x , y ) = σ ( y , x ),

Distributivity: σ ( x , y ± z ) = σ ( x , y ) ± σ ( x , z ) .

The vector function is called an operative operator, σ ( x , y ) denoted by x ⊗ y .

Definition 7. Given an additive attribute game (N, v_A), let x _i be the resource vector of the player i, so the resource matrix A = ( x₁ , x₂ , ⋯ , x_m ) ^T. For any coalition S ⊆ N, the coalition polynomial form of S is denoted by P (S), $P (S) = x_{i_{1}} \otimes x_{i_{2}} \otimes \dots \otimes x_{i_{k}},$ where x_i ∈ S, (t = 1, 2, ⋯ , k) .

Without confusion, the cooperative operator ’⊗’ can be substituted with the common times operator ’×’ for simplification. Therefore, for any S ⊆ N, $P (S) = \prod_{i \in S} x_{i} .$ (10)P (S) represents the resource vector of coalition S. We stipulate that x_i ⁰ = 1 for any $x_{m} \in R^{m}$ , so the empty coalition ∅ is represented by ’1’ in coalition polynomial form, i.e., $P (\emptyset) = \prod_{i \in \emptyset} x_{i} = 1 .$ (11)

Therefore, the coalitional polynomial form of the power set of N can be described as follows: $P (2^{N}) = \prod_{i \in N} (1 + x_{i}) .$ For example, let N = {1, 2}; then, 2^N = {∅ , {1} , {2} , {1, 2}}, and P (2^N) = (1 + x₁ ) (1 + x₂ ) =1 + x₁ + x₂ + x₁x₂ , which shows that all subsets of N are only in coalitional polynomial form.

Definition 8. Given an additive attribute game (N, v_A), let $γ : R^{n} \to R$ be an aggregation function over the resource vector of coalition and γ (∅) =0. If γ satisfies γ (P (S)) = v_A (S) and γ (P (S) + P (T)) = γ (P (S)) + γ (P (T)) for any S, T ⊆ N and S⋂ T = ∅, especially γ (P (∅)) = γ (1) =0, then γ is called the payoff function. By Definition 1, the payoff function is a "min" operator over the resource vector; however, it can be another operator in other cooperative games with multiple attributes. The same applies for the operative operator in Definition 6. For an additive attribute game (N, v_A), the characteristic function v_A (S) is definitively determined by the resource vector of coalition S, i.e., $v_{A} (S) = γ (P (S)), \forall S \in 2^{N},$ (12) For simplicity, we use $v_{A}^{γ} (S)$ to denote γ^-1 (v_A (S)), and it holds that $\begin{matrix} v_{A}^{γ} (S) = γ^{- 1} (v_{A} (S)) = P (S), \forall S \in 2^{N} . \end{matrix}$ The $v_{A}^{γ} (S)$ is the resource vector of coalition S. For an additive attribute game (N, v_A), the coalition polynomial form $v_{A}^{γ} (S) = P (S)$ plays the same important role as the characteristic function v_A (S), and the coalition polynomial form has more equivalent forms.

Theorem 7. Given an additive attribute game (N, v_A), for any S ⊆ N, T ⊆ S, it holds that $\sum_{T \subseteq S} (- 1)^{| S | - | T |} \prod_{i \in T} x_{i} = \prod_{j \in S} (x_{j} - 1)$ (13) $\sum_{T \subseteq S} \prod_{i \in T} (x_{i} - 1) + 1 = \prod_{j \in S} x_{j}$ (14) $\sum_{T \subseteq S} \prod_{i \in T} x_{i} + 1 = \prod_{j \in S} (x_{j} + 1)$ (15) $\sum_{T \subset S} [\prod_{i \in T} x_{i} \prod_{j \in S / T} (1 - x_{j})] = 1$ (16)

Proof. One can easily check these formulations by mathematical induction. Equation (16) can be derived from the following equation by expanding the left side, $\prod_{i \in S} (x_{i} + (1 - x_{i})) = 1 .$ All of the equations in Theorem 7 are multilinear, and they are useful not only in the additive attribute cooperative games but also in general cooperative games, fuzzy cooperative games and their extensions. We believe that the coalitional polynomial form of cooperative games provides interesting future directions to explore.

Since the relation between the characteristic function dovetails with the coalitional polynomial form, the characteristic function v_A (S) can be changed into the coalition polynomial form $v_{A}^{γ} (S) = P (S)$ , which makes some of the derivations simpler and cleaner. Consider the Harsanyi dividends given by Equation (3); for any S⊆ N, S ≠ ∅, it holds that $\begin{matrix} Δ_{v_{A}} (S) & = & \sum_{T \subseteq S} (- 1)^{| S | - | T |} v_{A} (T) \\ = & \sum_{T \subseteq S} (- 1)^{| S | - | T |} γ (P (T)) \\ = & γ (\sum_{T \subseteq S} (- 1)^{| S | - | T |} P (T)) \\ = & γ (\sum_{T \subseteq S} (- 1)^{| S | - | T |} \prod_{i \in T} x_{i}) \\ = & γ (\prod_{i \in S} (x_{i} - 1)) . \end{matrix}$ By Equation (2) and Equation (14), for any S⊆ N, S ≠ ∅, it follows that $\begin{matrix} v_{A} (S) & = & \sum_{T \subseteq S : T \neq \emptyset} Δ_{v_{A}} (T) u_{T} \\ = & \sum_{T \subseteq S : T \neq \emptyset} γ (\prod_{i \in T} (x_{i} - 1)) u_{T} \\ = & γ [\sum_{T \subseteq S : T \neq \emptyset} \prod_{i \in T} (x_{i} - 1) u_{T}] \\ = & γ (\prod_{i \in S} x_{i} - 1) \\ = & γ (\prod_{i \in S} x_{i}) \\ = & γ (P (S)), \end{matrix}$ which shows that Equation (12) also holds in unanimity games and that the coalitional polynomial can simplify some computing results.

Theorem 8. Given an additive attribute game (N, v_A), for any S ⊆ N, T ⊆ S, R ⊆ T, it holds that $\sum_{T \subseteq S} \sum_{R \subseteq T} (- 1)^{| T | - | R |} \prod_{i \in R} x_{i} = \prod_{i \in S} x_{i}$ (17)

Proof. For |S|=1, by Equation (11), it holds that $\begin{matrix} \sum_{T \subseteq S} (- 1)^{| S | - | T |} \prod_{i \in T} x_{i} & = & \prod_{i \in S} x_{i} - \prod_{i \in \emptyset} x_{i} \\ = & x - 1 \\ = & \prod_{j \in S} (x_{j} - 1) \end{matrix}$ Assuming the equation(17) is true for |S| = k - 1 . Therefore, by Equation (13) and Equation (14), for any S ⊆ N, T ⊆ S, R ⊆ T, it follows that $\sum_{T \subseteq S} \sum_{R \subseteq T} {(- 1)}^{| T | - | R |} \prod_{i \in R} x_{i} = \sum_{\begin{matrix} T \subseteq S \\ T \neq \emptyset \end{matrix}} \sum_{R \subseteq T} {(- 1)}^{| T | - | R |} \prod_{i \in R} x_{i} + \sum_{T = \emptyset} \sum_{R \subseteq T} {(- 1)}^{| T | - | R |} \prod_{i \in R} x_{i} n = \sum_{T \subseteq S} \prod_{i \in T} (x_{i} - 1) + 1 n = \prod_{i \in S} x_{i} .$ So the Equation (17) is true for any S ⊆ N, T ⊆ S, R ⊆ T . The proof is complete.

By theorem 8, we can obtain the following corollary.

Corollary 4. Given an additive attribute game (N, v_A), for any S ⊆ N, T ⊆ S, R ⊆ T, it holds that $\begin{matrix} \sum_{T \subseteq S} \sum_{R \subseteq T} (- 1)^{| T | - | R |} v (R) = v (S) . \end{matrix}$

Theorem 9. Given an additive attribute game (N, v_A), for any S ⊆ N and |S|≥2, if $γ (\prod_{i \in S} (x_{i} - 1)) \geq 0,$ then the game (N, v_A) is convex, i.e., v_A (A) + v_A (B) ≤ v_A (A ∪ B) + v_A (A ∩ B) for all A, B ⊆ N .

Proof. Because the conditions of convex games are equivalent to ∀S ⊆ N, k, j ∈ S, k ≠ j, $v_{A} (S \ {k}) + v_{A} (S \ {j}) \leq v_{A} (S) + v_{A} (S \ {k, j}) .$ By Equation (14), if the condition of the theorem holds, then ∀S ⊆ N, k, j ∈ S, k ≠ j, $\begin{matrix} v_{A} (S) + v_{A} (S \ {k, j}) - v_{A} (S \ {k}) - v_{A} (S \ {j}) \\ = & γ (\prod_{i \in S} x_{i}) + γ (\prod_{i \in S \ {k, j}} x_{i}) - γ (\prod_{i \in S \ {k}} x_{i}) \\ - γ (\prod_{i \in S \ {j}} x_{i}) \\ = & γ (\prod_{i \in S} x_{i} + \prod_{i \in S \ {k, j}} x_{i} - \prod_{i \in S \ {k}} x_{i} - \prod_{i \in S \ {j}} x_{i}) \end{matrix}$ $\begin{matrix} = & γ [\sum_{T \subseteq S} \prod_{i \in T} (x_{i} - 1) + \sum_{T \subseteq S \ {k, j}} \prod_{i \in T} (x_{i} - 1) \\ - \sum_{T \subseteq S \ {k}} \prod_{i \in T} (x_{i} - 1) - \sum_{T \subseteq S \ {j}} \prod_{i \in T} (x_{i} - 1)] \\ = & γ [\sum_{k \in T \subseteq S} \prod_{i \in T} (x_{i} - 1) + \sum_{k \in T \subseteq S \ {j}} \prod_{i \in T} (x_{i} - 1)] \\ = & γ [\sum_{k, j \in T \subseteq S} \prod_{i \in T} (x_{i} - 1)] \\ = & \sum_{k, j \in T \subseteq S} γ [\prod_{i \in T} (x_{i} - 1)] \geq 0 . \end{matrix}$ The proof is complete. The coalitional polynomial is suitable for a cooperative game that can be transformed to an additive attribute game by Theorem 4. When the scale of the player set is larger, the characteristic function is too massive to calculate the solution of games such as the Shapley value. However, the vectorization of the player and coalition in additive attribute games can make things different, and the characteristic function is determined solely by the resource vector of players in the coalition. Hence, each payoff of the coalition does not need to be calculated, and some work on local games or subgames may proceed. The coalitional polynomial is also suitable for cooperative games with restricted alliances and fuzzy games.

5 The additive attribute game solution

In this section, the allocation rules of additive attribute games are discussed.

Example 3. Given a game $(N, v_{A}) \in {AG}^{+}$ with player 1’s resource vector (3, 1, 0) and player 2’s resource vector (0, 0, 1), by Definition 1, it follows that the characteristic function is v (∅) =0, v (1) =0, v (2) =0, v (1, 2) =1.

In the example, player 1 has more resources than player 2, while there is no difference between them in the characteristic function. By the symmetric property axiom, they have the same allocation in terms of the Shapley value. There are many analogous examples that are unfair for players who have more resources than others but do not have allocation profits with respect to their resources. Based on this point, we propose an ER solution. For a $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m} \geq 0, M = {1, 2, \dots, m},$ and by Definition 1, for ∀S ⊆ N, it holds that $v_{A} (S) = min_{1 \leq j \leq m} \sum_{i \in S} a_{i, j}, for \forall S \in 2^{N} and v (\emptyset) = 0 .$ The sum of the resources of players is divided into two parts: one is the part that is no more than v_A (S), which represents the ERs. The other part is the remainder that is greater than v_A (S), which represents the redundant resources. Suppose that π is a permutation of N = {1, 2, ⋯ , n}, which is the order of players taking part in the grand coalition. The redundant part of the payoff v (N) of the grand coalition is composed of the resources of the players who are behind the permutation. The resources of the remaining players, that is, the players at the front of the queue, are efficient. For the given permutation π, suppose that π (N) = {π₁, π₂, ⋯ , π_n}; the ER of every player i about attribute j, which is denoted as $e_{j}^{π} (i)$ , can be calculated by the following piecewise function. For ∀j ∈ M, S = {π₁, π₂, ⋯ , π_k} and the π_k+1 is player i, $e_{j}^{π} (i) = {\begin{matrix} a_{i, j}, if \sum_{i \in S \cup {i}} a_{i, j} - v_{A} (N) \leq 0 \\ a_{i, j} - \sum_{i \in S \cup {i}} a_{i, j} + v_{A} (N), \\ if 0 < \sum_{i \in S \cup {i}} a_{i, j} - v_{A} (N) \leq a_{i, j} \\ 0, otherwise . \end{matrix}$ (18) It is obvious that ∑_i∈Ne_j (i) = v_A (N) for any attribute j ∈ M. If all permutations of N are considered, player i’s ER is the expected value of attribute j, which is denoted as E_j (i). In ${AG}^{+}$ , we calculate the expected value of the ER of each attribute of the player in v_A (N). For each attribute, we need to calculate the expected value of the ER of each position of player i in the array. Then, we accumulate the expected values of the ERs of all attributes and average them according to the attribute cardinality to obtain the ER value of player i. Now, the ER solution of the additive attribute game is defined as the following:

Definition 9. Let $(N, v_{A}) \in {AG}^{+}$ and A = (a_i,j) _n×m≥ 0, M = {1, 2, ⋯ , m} ; the ER solution $φ : {AG}^{+} \to ℝ^{n}$ can be defined by $\begin{matrix} φ_{i} (N, v_{A}) \\ = & \frac{1}{m} \sum_{j \in M} E_{j} (i) \end{matrix}$ (19) $= \frac{1}{m} \sum_{j \in M} \sum_{i \in N} \frac{| S |! (n - | S | - 1)!}{n!} e_{j} (i)$ (20)

By the above formulation, φ_i (N, v_A) =0 iif the resource vector of i is a zero vector when v_A (N) >0. The axiomatic characteristic properties of solutions of additive attribute games are discussed in the following paragraph. Let φ be a value of ${AG}^{+}$ . Efficiency. For any $(N, v_{A}) \in {AG}^{+}$ , it holds that $\begin{matrix} \sum_{i \in N} φ_{i} (N, v_{A}) = v (N) . \end{matrix}$

Resource Homogeneity. (RH) For any $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m}, M = {1, 2, \dots, m}$ and any constant k > 0, it holds that $φ_{i} (N, v_{kA}) = k φ_{i} (N, v_{A}) .$

Efficient Resource Monotonicity. (ERM) For any $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m}, M = {1, 2, \dots, m}$ , E_k (i) is player i’s ER value on attribute k; if $\sum_{k \in M} E_{k} (i) \leq \sum_{k \in M} E_{k} (j), for \forall i, j \in N,$ it holds that φ_i (N, v_A) ≤ φ_j (N, v_A) , especially, φ_i (N, v_A) = φ_j (N, v_A) when ∑_k∈ME_k (i) = ∑_k∈ME_k (j) .

Theorem 10. The ER value is the unique value for the additive attribute game (N, v_A) that satisfies efficiency, RH and ERM.

Proof. Existence. We have to show that φ satisfies efficiency, RH and ERM. For any $(N, v_{A}) \in {AG}^{+}, M = {1, 2, \dots, m}$ , $\begin{matrix} \sum_{i \in N} φ_{i} (N, v_{A}) \\ = & \sum_{i \in N} {\frac{1}{m} \sum_{j \in M} \sum_{i \in N} \frac{| S |! (n - | S | - 1)!}{n!} e_{j} (i)} \\ = & \frac{1}{m} \sum_{j \in M} \sum_{i \in N} \frac{| S |! (n - | S | - 1)!}{n!} {\sum_{i \in N} e_{j} (i)} \\ = & \frac{1}{m} \sum_{j \in M} \sum_{i \in N} \frac{| S |! (n - | S | - 1)!}{n!} v (N) \\ = & \frac{1}{m} \sum_{j \in M} v (N) \\ = & v (N) . \end{matrix}$ showing that φ satisfies efficiency. By Definition 1 and property 1, for any constant k > 0, it follows that $v_{kA} (S) = k v_{A} (S), \forall S \in 2^{N},$ so v_kA (N) = kv_A (N). By formulation (18) and Definition 1, it holds that $\begin{matrix} φ_{i} (N, v_{kA}) & = & \frac{1}{m} \sum_{j \in M} \sum_{i \in N} \frac{| S |! (n - | S | - 1)!}{n!} k e_{j} (i) \\ = & \frac{k}{m} \sum_{j \in M} \sum_{i \in N} \frac{| S |! (n - | S | - 1)!}{n!} e_{j} (i) \\ = & k φ_{i} (N, v_{A}) . \end{matrix}$ showing that φ satisfies RH. If ∑_k∈ME_k (i) ≤ ∑_k∈ME_k (j) for ∀i, j ∈ N, by formulation (19), it holds that $\begin{matrix} φ_{i} (N, v_{A}) = \frac{1}{m} \sum_{k \in M} E_{k} (i) & \leq & \frac{1}{m} \sum_{k \in M} E_{k} (j) \\ = & φ_{j} (N, v_{A}), \end{matrix}$ especially φ_i (N, v_A) = φ_j (N, v_A), when ∑_k∈ME_k (i) = ∑_k∈ME_k (j) , which shows that φ satisfies ERM. Uniqueness. Let ψ be a value of $(N, v_{A}) \in {AG}^{+}$ that satisfies efficiency, RH and ERM. Below, we prove that ψ_i (v_A) = φ_i (N, v_A) for any i ∈ N. Let λ_i = ∑_k∈ME_k (i) for simplicity; then, $φ_{i} (N, v_{A}) = \frac{λ_{i}}{m} .$ By efficiency, it holds that $\begin{matrix} \sum_{i \in N} ψ_{i} (N, v_{A}) & = & v_{A} (N) = \frac{1}{m} \sum_{i \in N} λ_{i} \\ = & \sum_{i \in N} φ_{i} (N, v_{A}), \forall i \in N . \end{matrix}$

If λ_i = 0 for i ∈ N, by ERM and formulation (19), $ψ_{i} (N, v_{A}) = \frac{λ_{i}}{m} = 0 = φ_{i} (N, v_{A}) .$ If λ_i > 0 for i ∈ N, by RH and ERM, ψ_i (N, v_A) is in direct proportion to λ_i, and suppose that ψ_i (N, v_A) = dλ_i, where $d \in R$ and d > 0 . Since $φ_{i} (N, v_{A}) = \frac{λ_{i}}{m}$ , we need to prove that $d = \frac{1}{m}$ . The following is the method of proof to the contrary. Suppose that $d \neq \frac{1}{m};$ by efficiency and RH, for any k > 0, it holds that $\sum_{i \in N} ψ_{i} (N, v_{kA}) - \sum_{i \in N} φ_{i} (N, v_{kA}) = 0 .$ Then, $\begin{matrix} k \sum_{i \in N} ψ_{i} (N, v_{A}) - k \sum_{i \in N} φ_{i} (N, v_{A}) & = & 0 \\ \sum_{i \in N} d λ_{i} - \sum_{i \in N} \frac{λ_{i}}{m} & = & 0 \\ dmv (N) - v (N) & = & 0 \\ d & = & \frac{1}{m}, \end{matrix}$ contrary to our supposition about d; therefore, $ψ_{i} (N, v_{A}) = \frac{λ_{i}}{m} = φ_{i} (N, v_{A})$ for any i ∈ N. This complete the proof.

6 The core of the additive attribute game

The core is a vital set-value solution of cooperative games.

Theorem 11. Let C (v_A) be the core of $(N, v_{A}) \in {AG}^{+}$ , x = (x₁, x₂, ⋯ , x_n) ∈ C (v_A); if A′ = (A, x^T) _n×(m+1), where x^T is the transpose of vector x; then, v_A′ (S) = v_A (S) for ∀S∈ 2^N \ ∅.

Proof. x ∈ C (v_A) , holds that x (S) ≥ v_A (S) for ∀S∈ 2^N \ ∅ ; by Definition 2, x is a redundancy attribute in matrix A′ = (A, x) _n×(m+1) . Therefore, v_A′ (S) = v_A (S) for ∀S ∈ 2^N \ ∅ , which completes the proof.

From theorem 11 and the definition of the core, one can conclude the following corollary.

Corollary 5. For any $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m},$ M = {1, 2, ⋯ , m} , if attribute k ∈ M is a redundancy attribute and ∑_i∈Na_i,k = v_A (N), then $x = (a_{1, k}, a_{2, k}, \dots, a_{n, k}) \in C (v_{A}) .$

Theorem 12. Given an arbitrary cooperative game $(N, v) \in G^{N}$ , if there exists a constant 1 ≤ k ≤ n and cluster D = {S|S ∈ 2^N \ ∅ , |S| = k} satisfying $\sum_{S \in D : | S | = k} v (S) > C_{n - 1}^{k - 1} v (N),$ (21) then the core of (N, v) is empty.

Proof. Suppose that C (v)≠ ∅ and x = (x₁, x₂, ⋯ , x_n) ∈ C (v). Let A = x^T; we construct a single-attribute game $(N, v_{A}) \in {AG}^{+}$ , and it follows that $v_{A} (N) = x (N) = \sum_{i \in N} x_{i} = v (N)$ . $v_{A} (S) = x (S) = \sum_{i \in S} x_{i} \geq v (S), \forall S \in 2^{N} \ \emptyset$ From corollary 2, for any constant 1 ≤ k ≤ n, it holds that $\sum_{S \in D : | S | = k} v_{A} (S) = C_{n - 1}^{k - 1} v_{A} (N) = C_{n - 1}^{k - 1} v (N)$ If there exists a constant 1 ≤ k ≤ n satisfying inequality (21), then it follows that $\begin{matrix} v (N) & = & v_{A} (N) = \frac{1}{C_{n - 1}^{k - 1}} \sum_{S \in D : | S | = k} v_{A} (S) \\ \geq & \frac{1}{C_{n - 1}^{k - 1}} \sum_{S \in D : | S | = k} v (S) > v (N), \end{matrix}$ which is a contradiction; hence, the proof is complete.

Example 4. Consider game (N, v) ∈ Gⁿ with N = {1, 2, 3}; the characteristic function is given by $v (\emptyset) = 0, v ({i}) = 0 (i = 1, 2, 3), v ({1, 2}) = \frac{2}{3}, v ({1, 3}) = \frac{3}{4}, v ({2, 3}) = \frac{3}{5}, v ({1, 2, 3}) = 1 .$ Then, by Theorem 12, when k = 2, D = {{1, 2} , {1, 3} , {2, 3}} , it follows that $\begin{matrix} v ({1, 2}) + v ({1, 3}) + v ({2, 3}) & = & \frac{121}{60} \\ > & 2 v ({1, 2, 3}) = 2 . \end{matrix}$ Hence, by Theorem 12, the core of game (N, v) is empty.

7 The Shapley value of an additive attribute game

Next, we discuss the differences in some properties between the Shapley value and ER value in an additive attribute game. Suppose that φ is a value of ${AG}^{+}$ . Constant Separation Property. For any $(N, v_{A}) \in {AG}^{+}$ and any constants c₁, c₂, ⋯ , c_n ≥ 0, let $A^{'} = A + \bar{C},$ , where $\bar{C} = (c_{i})_{n \times 1} \times (1)_{1 \times m}$ is a constant RE matrix, it holds that $φ_{i} (N, v_{A^{'}}) = φ_{i} (N, v_{A}) + c_{i}, \forall i \in N .$ Shapley values are calculated independently of ERs but are related to the marginal payoffs of players. Hence, we have the following:

Theorem 13. For any $(N, v_{A}) \in {AG}^{+}, A = (a_{i, j})_{n \times m},$ M = {1, 2, ⋯ , m} , and any constants c₁, c₂, ⋯ , c_n ≥ 0, let $A^{'} = A + \bar{C},$ , where $\bar{C} = (c_{i})_{n \times 1} \times (1)_{1 \times m}$ , the Shapley value satisfies the constant separation property.

Proof. From formulation (1) and property 3, it holds that $\begin{matrix} v_{A^{'}} (S) & = & min_{j \in M} \sum_{i \in S} (a_{i, j} + c_{i}) \\ = & min_{j \in M} \sum_{i \in S} a_{i, j} + \sum_{i \in S} c_{i} \\ = & v_{A} (S) + \sum_{i \in S} c_{i}, \end{matrix}$ and similarly, v_A′ (S ∪ k) = v_A (S ∪ k) + ∑_i∈S∪kc_i, ∀k ∈ N \ S . $\begin{matrix} {Sh}_{k} (N, v_{A^{'}}) \\ = & \sum_{S \subseteq N \ {k}} \frac{| S |! (n - | S | - 1)!}{n!} [v_{A^{'}} (S \cup {k}) - v_{A^{'}} (S)] \\ = & \sum_{S \subseteq N \ {k}} \frac{| S |! (n - | S | - 1)!}{n!} [v_{A} (S \cup k) + \sum_{i \in S \cup k} c_{i} - \\ v_{A} (S) - \sum_{i \in S} c_{i}] \\ = & \sum_{S \subseteq N \ {k}} \frac{| S |! (n - | S | - 1)!}{n!} [v_{A} (S \cup k) - v_{A} (S) + c_{k}] \\ = & \sum_{S \subseteq N \ {k}} \frac{| S |! (n - | S | - 1)!}{n!} [v_{A} (S \cup k) - v_{A} (S)] + c_{k} \\ = & {Sh}_{k} (N, v_{A}) + c_{k}, \end{matrix}$ which shows that the Shapley value satisfies the constant separation property. This completes the proof.

From the definition of the Shapley value, one can easily prove that it satisfies the constant separation property. However, the ER value does not satisfy it, as shown in the following example.

Example 5. Given three games $(N, v_{A}) \in {AG}^{+}$ with the resource matrix A′, A and constant RE matrix $\bar{C}$ , $A^{'} = (\begin{matrix} 2 & 2 & 3 \\ 2 & 3 & 3 \end{matrix}), A = (\begin{matrix} 1 & 1 & 2 \\ 0 & 1 & 1 \end{matrix}), \bar{C} = (\begin{matrix} 1 & 1 & 1 \\ 2 & 2 & 2 \end{matrix}) .$ The Shapley value of (N, v_A′) , (N, v_A) is (1, 0) , (2, 2), which shows that the constant separation property is satisfied. However, the ER value of (N, v_A′) , (N, v_A) is (0.6667, 0.3333) , (1.8333, 2.1667), which means that the ER value does not satisfy the constant separation property.

The Shapley value satisfies the symmetry axiom, which is shown below: Symmetry. For any $(N, v) \in G^{N}$ and symmetric players i, j ∈ N, it holds that φ_i (v) = φ_j (v), where two players i, j ∈ N are symmetric in (N, v) if v (S ∪ {i}) = v (S ∪ {j}) for ∀S ⊆ N \ {i, j}. However, the ER value does not satisfy the symmetry axiom because the redundancy attribute may be different between i and j, although it holds that v (S ∪ {i}) = v (S ∪ {j}) for ∀S ⊆ N \ {i, j}. The difference will result in ER_i ≠ ER_j; i.e., (1 0 0) and (0 1 1) can be symmetric players in two-player cooperative games, and the 3rd attribute is the redundancy attribute according to Definition 1. However, they do not obtain the same allocation in the ER solution, although they obtain the same Shapley value. This example implies that the ER solution does not satisfy the symmetry property. Null-player property. For any $(N, v_{A}) \in {AG}^{+}$ and null-player i ∈ N, it holds that φ_i (N, v_A) =0, where player i ∈ N is a null player in (N, v_A) if v (S ∪ {i}) = v (S) for ∀S ⊆ N \ {i}. φ does not satisfy the null-player property. For any $(N, v_{A}) \in {AG}^{+}$ and any null-player i ∈ N, given that the resource vector of player i is (x₁, x₂, ⋯ , x_n), any S ⊆ N \ {i}, it follows that v (S ∪ {i}) = v (S). This means that when S = ∅ , v (i) =0, the minimum of {x₁, x₂, ⋯ , x_n} is 0, and for any key attribute k of S, we have x_k = 0. However, if there is an attribute t that is not the key attribute of any S, for example, suppose that x_t > 0, then, by formulation (19), it follows that φ_i (v_A) >0.

We introduce the following example to compare the Shapley value and ER solution.

Example 6. Given three games (N, v_A) , (N, v_B) , $(N, v_{C}) \in {AG}^{+}$ with the resource matrix A, B, C, $A = (\begin{matrix} 1 & 0 & 2 \\ 0 & 3 & 3 \\ 4 & 2 & 0 \end{matrix}), B = (\begin{matrix} 2 & 0 & 2 \\ 0 & 3 & 3 \\ 4 & 2 & 0 \end{matrix}), C = (\begin{matrix} 2 & 0 & 2 \\ 0 & 1 & 3 \\ 3 & 4 & 0 \end{matrix})$ the characteristic functions of game (N, v_A) are v_A (∅) =0, v_A ({i}) =0 (i = 1, 2, 3) , v_A ({1, 2}) =1, v_A ({1, 3}) =2, v_A ({2, 3}) =3, v_A ({1, 2, 3}) =5, the Shapley value is Sh (v_A) = (1.1667, 1.1667, 2.1667), and the ER solution is φ (v_A) = (1, 2, 2) . The characteristic functions of game (N, v_B) are v_B (∅) =0, v_B ({i}) =0 (i = 1, 2, 3) , v_B ({1, 2}) =2, v_B ({1, 3}) =2, v_B ({2, 3}) =3, v_B ({1, 2, 3}) =5, the Shapley value is Sh (v_B) = (1.3333, 1.8333, 1.8333), and the ER solution is φ (v_B) = (1.1667, 2, 1.8333) . Comparing game (N, v_A) and game (N, v_B), only the resource of player 1 increases from 1 to 2 on the first attribute, which increases the Shapley value of player 1 accordingly. However, the Shapley value of player 2 increases, and the Shapley value of player 3 decreases. In the ER solution, the distribution of player 1 is increased, that of player 2 is unchanged, and that of player 3 is reduced. This is because v (N) =5 in the RE game (N, v_A), and all the resources are effective, whereas in the game (N, v_B), some resources of the first attribute are invalid, which affects player 1 and player 3. The characteristic functions of game (N, v_C) are v_C (∅) =0, v_C ({i}) =0 (i = 1, 2, 3) , v_C ({1, 2}) =1, v_C ({1, 3}) =2, v_C ({2, 3}) =3, v_C ({1, 2, 3}) =5, the Shapley value is Sh (v_C) = (1.1667, 1.1667, 2.1667), and the ER solution is φ (v_C) = (1.3333, 1.3333, 2.3333). Comparing game (N, v_A) and game (N, v_C), although the resources of players have changed, the characteristic function values are the same, i.e., v_A (S) = v_C (S), for ∀S ∈ 2^N, which results in both games having the same Shapley value, showing that the Shapley value is not sensitive to changes in resources; in other words, the Shapley value does not satisfy ERM. In the ER solution, the distributions of player 1 and player 3 are increased, and that of player 2 is reduced, which corresponds to changes in the ERs of the players.

This example shows that in additive attribute game $(N, v_{A}) \in {AG}^{+}$ , once the resource matrix A is given, its characteristic function and the ERs of each player are determined. The ER value is more appropriate for ERs than the Shapley value.

Definition 10. A matrix C = (c_i,j) _n×m is said to be a total resource equalization matrix if the total of each column of the matrix C is the same $\sum_{i = 1}^{n} c_{i, j} = \sum_{i = 1}^{n} c_{i, k},$ where 1 ≤ j, k ≤ m .

Theorem 14. Given $(N, v_{A}) \in {AG}^{+}$ is a two-attribute total resource equality (TRE) game, A = (a_i,j) _n×m is a resource matrix with n players and m additive attributes, n ∈ N, m ∈ M, and M is the attribute set. If game (N, v_A) exhibits TRE, it holds that ${ER}_{i} (v) = \frac{1}{m} \sum_{j \in M} a_{i, j}$ (22)

Proof. Because (N, v_A) exhibits resource equality, then ∀i ∈ N, ∀ j ∈ M, a_i,j is an ER, and it follows that ${ER}_{i} (v) = \frac{1}{m} \sum_{j \in M} {Exp}_{i \in N} {e_{j} (i)}$ (23) $= \frac{1}{m} \sum_{j \in M} a_{i, j}$ (24)

Theorem 15. Let $(N, v) \in {AG}^{+}$ , A = (a_i,j) _n×2 be a total resource equalization matrix, M = {1, 2}; it holds that ${Sh}_{i} (v) = {ER}_{i} (v) = \frac{1}{2} \sum_{j \in M} a_{i, j}$ (25)

Proof. Let player i’s resource vector be (x_i, y_i), π be a permutation of N, and π^-1 be the reverse permutation of N. For a given permutation π, the position of player i is symmetric on the permutation π and the reverse permutation π^-1, and it follows that π (i) = n - π^-1 (i) +1. ∀S ⊆ N \ {i} , let $Δ_{S}^{π} (i) = v (S \cup {i}) - v (S)$ ; then, $Δ_{N \ (S \cup {i})}^{π^{- 1}} (i) = v (N \ S) - v (N \ (S \cup {i}))$ . In the additive attribute game, the resource vectors of coalition S are (x_S, y_S); since (N, v_A) exhibits TRE, x_N = y_N. By the definition of a character operator, it holds that $\begin{matrix} Δ_{S}^{π} (i) + Δ_{N \ (S \cup {i})}^{π^{- 1}} (i) \\ = & v (S \cup {i}) - v (S) + v (N \ S) \\ - v (N \ (S \cup {i})) \\ = & ⋀ {x_{S \cup {i}}, y_{S \cup {i}}} - ⋀ {x_{S}, y_{S}} \\ + ⋀ {x_{N \ S}, y_{N \ S}} - ⋀ {x_{N \ (S \cup {i})}, y_{N \ (S \cup {i})}} \\ = & ⋀ {x_{S} + x_{i}, y_{S} + y_{i}} + ⋀ {x_{N \ S}, y_{N \ S}} \\ - ⋀ {x_{S}, y_{S}} - ⋀ {x_{N} - x_{S \cup {i}}, y_{N} - y_{S \cup {i}}} \\ = & ⋀ {x_{S} + x_{i}, y_{S} + y_{i}} + ⋀ {x_{N} - x_{S}, y_{N} - y_{S}} \\ - ⋀ {x_{S}, y_{S}} - ⋀ {x_{N} - x_{S} - x_{i}, y_{N} - y_{S} - y_{i}} \end{matrix}$ We discuss the result above in four cases.

If x_S + x_i < y_S + y_i and x_S < y_S, then $\begin{matrix} Δ_{S}^{π} (i) + Δ_{N \ (S \cup {i})}^{π^{- 1}} (i) \\ = & x_{S} + x_{i} - x_{S} + y_{N} - y_{S} - y_{N} + y_{S} + y_{i} \\ = & x_{i} + y_{i} . \end{matrix}$

If x_S + x_i ≥ y_S + y_i and x_S ≥ y_S, then $\begin{matrix} Δ_{S}^{π} (i) + Δ_{N \ (S \cup {i})}^{π^{- 1}} (i) \\ = & y_{S} + y_{i} - y_{S} + x_{N} - x_{S} - x_{N} + x_{S} + x_{i} \\ = & x_{i} + y_{i} . \end{matrix}$

If x_S + x_i < y_S + y_i and x_S ≥ y_S, then $\begin{matrix} Δ_{S}^{π} (i) + Δ_{N \ (S \cup {i})}^{π^{- 1}} (i) \\ = & x_{S} + x_{i} - y_{S} + x_{N} - x_{S} - y_{N} + y_{S} + y_{i} \\ = & x_{i} + y_{i} . \end{matrix}$

If x_S + x_i ≥ y_S + y_i and x_S < y_S, then $\begin{matrix} Δ_{S}^{π} (i) + Δ_{N \ (S \cup {i})}^{π^{- 1}} (i) \\ = & y_{S} + y_{i} - x_{S} + y_{N} - y_{S} - x_{N} + x_{S} + x_{i} \\ = & x_{i} + y_{i} . \end{matrix}$

Taking the four cases into consideration, it holds that

Δ_{S}^{π} (i) + Δ_{N \ (S \cup {i})}^{π^{- 1}} (i) = x_{i} + y_{i} .

In the Shapley value formulation, the number of all players in the permutation π is n !, and the number of reverse permutations π^-1 is n !. The Shapley value according to permutation π is

\begin{matrix} {Sh}_{i}^{π} (v) \\ = & \sum_{S \subseteq N \ {i}} \frac{| S |! (| N | - | S | - 1)!}{| N |!} (v (S \cup {i}) - v (S)) \\ = & \sum_{S \subseteq N \ {i}} \frac{| S |! (| N | - | S | - 1)!}{| N |!} Δ_{S}^{π} (i), \forall i \in N, \end{matrix}

which is the same as the Shapley value on permutation π^-1.

\begin{matrix} {Sh}_{i}^{π^{- 1}} (v) \\ = & \sum_{S \subseteq N \ {i}} \frac{| S |! (| N | - | S | - 1)!}{| N |!} v (N \ S) \\ - v (N \ (S \cup {i})) \\ = & \sum_{S \subseteq N \ {i}} \frac{| S |! (| N | - | S | - 1)!}{| N |!} Δ_{N \ (S \cup {i})}^{π^{- 1}} (i), \\ \forall i \in N . \end{matrix}

Both of the above results are ${Sh}_{i}^{π} (v) = {Sh}_{i}^{π^{- 1}} (v), \forall i \in N .$ By the linear and additivity of the Shapley value, ∀i ∈ N $\begin{matrix} {Sh}_{i}^{π} (v) + {Sh}_{i}^{π^{- 1}} (v) \\ = & \sum_{S \subseteq N \ {i}} \frac{| S |! (| N | - | S | - 1)!}{| N |!} [Δ_{S}^{π} (i) + Δ_{N \ (S \cup {i})}^{π^{- 1}} (i)] \\ = & \sum_{S \subseteq N \ {i}} \frac{| S |! (| N | - | S | - 1)!}{| N |!} (x_{i} + y_{i}) \\ = & x_{i} + y_{i} . \end{matrix}$ Thus, we obtain ${Sh}_{i}^{π} (v) = {Sh}_{i}^{π^{- 1}} (v) = \frac{x_{i} + y_{i}}{2}, \forall i \in N .$ By Theorem 14 and the result of the additive attribute game with N players and two attributes, it holds that $φ_{i} (v) = \frac{x_{i} + y_{i}}{2} .$ Thus, ${Sh}_{i} (v) = {ER}_{i} (v) = \frac{1}{2} \sum_{j \in M} a_{i, j} .$ (26) This completes the proof of the theorem.

Example 7. Given a two-attribute equivalence game (N, v), the characteristic function is as follows: v {∅} =0, v {1} =3, v {2} =7, v {3} =0, v {1, 2} =13, v {1, 3} =5, v {2, 3} =7, v {1, 2, 3} =15 . By Theorem 4, we can obtain a two-attribute equivalence game with player P₁ = {8, 3} , P₂ = {7, 10} , P₃ = {0, 2} . By Theorem 15, we calculate the mean of each weight vector to obtain the ER value (5.5, 8.5, 1), which coincides with the Shapley value (5.5, 8.5, 1) . This example shows that if a game (N, v) can be converted to a two-attribute TRE game, the Shapley value can be obtained more simply by calculating the ER value.

8 Conclusion

In this paper, a cooperative game with an endogenous characteristic function, which is called an additive attribute game, was studied to obtain its solution and compare it with the Shapley value. The game not only explains why the cooperative coalition can produce more profit than the total payoff of each player but also transforms the general cooperative game into an additive attribute game when monotonicity, superadditivity and boundedness need to be satisfied. All players and coalitions can be expressed by a uniform type of resource vector, for which a coalitional polynomial form is derived to discuss the structure of the coalition. In addition, the general cooperative game can be transformed into an additive game under certain conditions. Consequently, the additive attribute game can also be used as a method to analyze the characteristics of players in a general cooperative game, and some calculations in the social network will be simplified. These aspects will be studied in our future work.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Nos. 71771025, 11661048 and 71701084). The authors are thankful to the editor of this journal and the anonymous reviewers for their invaluable comments and suggestions.

References

Algaba

, et al., Harsanyi power solutions for games on union stable systems, Ann Oper Res 225(1) (2015), 27–44.

Aumann

R.J.

, Hart

, Handbook of Game Theory with Economic Applications Volume 1 (Handbooks in Economics) North-Holland, 1992.

Belau

, A note on the owen value for glove games, International Game Theory Review 17(4) (2015), 1–8.

Borkotokey

, et al., Cooperative games with multiple attributes, International Journal of General Systems 48(8) (2019), 825–842.

Calvo

, et al., Values of games with probabilistic graphs, Mathematical Social Sciences 37(1) (1999), 79–95.

Curiel

, et al., On balanced games and games with committee control, OR Spectrum 11(2) (1989), 83–88.

Derks

, et al., Characterizations of the random order values by Harsanyi payoff vectors, Math Meth Oper Res 64(1) (2006), 155–163.

Gilles

R.P.

, The Cooperative Game Theory of Networks and Hierarchies, Berlin: Springer, 2010.

González-Arangüena

, et al., Values of games with weighted graphs, European Journal of Operational Research 243(1) (2015), 248–257.

10.

Haeringer

, A new weight scheme for the Shapley value, Mathematical Social Sciences 52(1) (2006), 88–98.

11.

Harsanyi

J.C.

, A bargaining model for cooperative n-person games, In: Tucker AW, Luce RD (eds) Contributions to the theory of games IV, Princeton University Press, (1959), 325–355.

12.

Ieong

, Shoham

, Proceedings of the 7th ACM Conference on Electronic Commerce. EC’06. New York, NY, USA: Association for Computing Machinery, Multi-Attribute Coalitional Games (2006), 170–179.

13.

Kalai

, Samet

, On weighted Shapley values, International Journal of Game Theory 16(3) (1987), 205–222.

14.

Liao

Y.H.

, The excess formulations and related results for the normalized Banzhaf index and the Shapley value, TOP 24(1) (2016), 233–241.

15.

Myerson

R.B.

and Evanston, Conference structures and fair allocation rules, Journal of Game Theory 9(3) (1980), 169–182.

16.

Myerson

R.B.

, Graphs and cooperation in games, Mathematics of Operations Research 2(3) (1977), 225–229.

17.

Nowak

A.S.

, Radzik

, On axiomatizations of the weighted Shapley values, Games Econ Behav 8(2) (1995), 389–405.

18.

Owen

, Communications to the EditorâA note on the shapley value, Management Science 14(11) (1968), 731–732.

19.

Owen

, Multilinear extensions of games, Management Science 18(5-part-2) (1972), 64–79.

20.

Palanci

, et al., Cooperative grey games and the grey shapley value, Optimization 64(8) (2015), 1657–1668.

21.

Shapley

L.S.

, Shapley-Thesis, Princeton University, 1953.

22.

Shapley

L.S.

, The solutions of a symmetric market game, Santa Monica, CA: RAND Corporation, 1958.

23.

Shapley

L.S.

, Shubik

, Pure competition, coalitional power, and fair division, International Economic Review 10(3) (1969), 337–362.

24.

Shapley

L.S.

, Shubik

, The assignment game I: The core, International Journal of Game Theory 1(1) (1971), 111–130.

25.

Shapley

L.S.

, Roth

A.E.

, The Shapley Value: Essays in Honor of Lloyd S. Shapley, Cambridge University Press, 1988.

26.

van den Brink

, et al., Harsanyi power solutions for graph-restricted games, Int J Game Theory 40(1) (2011), 87–110.

27.

Yokoo

, et al., Coalitional games in open anonymous environments, IJCAI International Joint Conference on Artificial Intelligence (2005), 1668–1669.