SciresolSciresolhttps://indjst.org/author-guidelinesIndian Journal of Science and Technology0974-564510.17485/IJST/v15i40.1099research articleConsolidation of an Efficient and a Non-Efficient Solution in a Cooperative Game: The Egalitarian Banzhaf ValueBoraAbhijit1SaikiaMintu1BoraPranjal Kumarpranjaly2k@gmail.com2Department of Mathematics, Dibrugarh UniversityDibrugarh, 786004, AssamIndiaCenter for Computer Science and Applications, Dibrugarh University786004, AssamIndia2910202215402077255202210920222022Abstract
Objective: The principles of marginalism and egalitarianism are handy tools for sharing worth among the players of a group in a TU game. Here, our objective is to combine two such solutions to generate a new value that keeps in mind the need of each player required for the survival of a group in a TU game. Methods:Here, the Banzhaf value and the equal division value were merged to establish a new consolidated solution. Method of induction is used over unanimity games and symmetric games to characterize the proposed value using some well-known as well as some freshly defined axioms of cooperative game theory. Findings:To describe the new value, we first looked at a number of intuitive axioms linked to it and the uniqueness of the value is obtained by characterizing it using the defined axioms. The value is then extended to the class of simple games. Novelty:The proposed solution is a non-efficient solution that allocates a portion of the total worth to the players and keeps a portion undistributed to use for the purpose of further investment by the group.
Cooperative games are socioeconomic situations wherein the agents or players form an alliance, known as a coalition, and generate value under legally binding agreements. Any such alliance explains one particular aspect that the parties will coordinate while planning their actions. Even if a specific alliance is eventually established, the distribution of profits among the allies will be heavily impacted by the various alliances they may have opted into. The main challenge is to obtain a suitable allocation scheme to divide this worth among the agents forming the grand coalition. The strategy to share the worth among the group members is called the solution concept. The Banzhaf value 1, the equal division value 2, Generalized solidarity value 3are some of the most useful solution concepts in cooperative game theory.
Banzhaf value divides the worth of a game based on the marginal contributions of players to the game. Surprisingly, the proposed value is a unique value that meets four acceptable axioms. The first one is super additivity which ensures that the sum of the 4 provided a characterization using consistency. Another important study of Banzhaf value which highlighted its applications can be found in 5. This value has been studied for games with proximity relations in 6. Banzhaf value also has great importance in determining voting power indices.
While distributing the worth based on marginal contributions, the solutions give nothing to players who do not contribute to the game, i.e., the null players. This is a challenging assignment since some gain must be transferred to unproductive persons for a group to survive. To resolve the issue, other solution concepts have been introduced based on the average marginal contributions of players. Such value takes care of those players who do not contribute or cannot contribute to the game. This seems practical as a disabled person or a person on maternity leave may not contribute to specific situations for some acceptable reasons. Also, they may be socially connected to those players who participated in solidarity on occasion. In our society, there is frequently gain transfer to unemployed individuals in modern cultures. As we can see in practice, solidarity is intended to keep individuals socially connected so that they can improve their standard of living by pursuing better work opportunities and completing training to adapt to the labour market supply. In contrast, an equal division value distributes the total profit of the game equally among all the involved players. The shortcoming of this technique is that it assumes that all actors in a coalition must behave in solidarity with one another without considering their contribution to the game. As a result, a null player may be able to obtain a more advantageous position through value transfers. This solution is characterized by using four standard axioms. The first one is efficiency, which says that players share among themselves all the resources available to the grand coalition. The second one is Nullifying player property which says that if any player annihilates the contribution of all coalitions, then that player must receive zero payoffs. The other two axioms used in the characterization of the value are linearity and equal treatment.
It is observed that both Banzhaf value and equal division value have their limitations while allocating worth to null players. One of the most effective ways to resolve the issue is to consolidate marginalized solutions with other allocation rules so that those null players get a fraction of the profit for their survival. Such mixing of marginalized and egalitarian values is common in game-theoretic literature. For instances, 7 introduced the concept of α-egalitarian Shapley value that consolidates Shapley value and equal division value. In 2020, 8generalized the value-based size of the coalition that allocates different α-egalitarian Shapley values by assigning different values of α to different sizes of coalitions. Then some characterizations of the value have been given. In the same year, 9 investigated another consolidated value which allocates Shapley value to larger coalitions and Egalitarian value to smaller coalitions. However, all of this literature revolves around consolidating two efficient values whose output is also efficient. In this paper, we consolidate an efficient solution with a non-efficient value and then study the behaviour of the new solution. A convex combination of both solutions is considered to maintain the level of marginality in the game to decide how much egalitarianism the players will show to the unproductive players.
For efficient values, the whole generated wealth is distributed among the players forming the grand coalition. But in general, there may be the wish of the group to keep a portion aside for future investment. Moreover, it is seen in our society that most business groups keep a portion of their profit for charity or donation. Here, a non-efficient value is considered keeping in mind the above-mentioned situations to keep an amount of the value of the grand coalition unshared for future utilization. It might be later used for paying taxes, donations for charity, further investment, or any other purposes after completion of the game. Also, if an amount is kept for further investment of the group, this increases the chance to bind the players together. Otherwise, the grand coalition will break once the game is completed. Moreover, the value is constructed by introducing a parameter α in such a way that the solution can be made efficient by altering the value of α. This parameter also allows to choose the level of marginality in the game and decide how much value to be transferred to unproductive players.
The rest of the paper is organized as follows. In section 2, we discuss basic definitions and some solution concepts of cooperative game theory, important axioms satisfied by these solutions, followed by their characterization using the defined axioms. In section 3, we present the main results of our paper about introducing a new value function obtained by consolidating two other solutions, viz equal division value and Banzhaf values, respectively. We named this value the egalitarian-Banzhaf value. Then we define some new axioms to characterize the defined value. Then we discuss the properties of the new function in a class of simple games and characterize it in that particular class of games. Section 4 is devoted to the discussion of the result and its application possibilities. Section 5 includes the concluding remarks future scope of our research.
Preliminaries2.1 TU game
Consider the set of players, N={1,2,3,...,n}, where n is a finite positive integer greater than one. Each set S⊆N is called a coalition. The collection of all the coalitions of N is denoted by 2N. The set N formed eventually by the binding agreement of all players is called the grand coalition. We use respective small letters for the size of coalitions, viz., s,n for S,N etc. A cooperative n-person game with transferable utility or simply a TU-game is an ordered pair(N,v) where N is the set of players and v:2N→R is a map that assigns a real number to each coalition S in 2N such that v(∅)=0. The function v is called the characteristic function or coalition function that guarantees a unique value v(S) for each coalition S⊆N. If no ambiguity arises on N, we denote a TU only by the function v. The set of all TU games over N is denoted by GN. Given a TU game, the marginal contribution of player i for any coalition S⊆N\{i}, is MCiv(S)=v(S∪{i})-v(S).
2.2 Solutions and bases for TU games
A value or solution is a map Φ:GN→Rn assigning to each game where ith component of the vector represents the utility attributed to the player i∈N. Thus, Φ(v) represents the share of the worth v(N) of the grand coalition N. We focus our study only on the single-valued functions. The Banzhaf value, ΦB and the egalitarian value, ΦED corresponds to each game v∈GNare the vectors, defined as follows:
ΦiBv=12n-1∑S⊆N\{i}MCiv(S)ΦEDv=vNn
For every coalition S⊆N with S≠∅, define games uT:2N→R and vT:2N→R as follows,
u_T(S)= \begin{cases}1, & \text { if T } \subseteq S \\ 0, & \text { otherwise }\end{cases}
These are the standard bases for the class{\;G}^N with the player set N. They are called the unanimity basis and the identity basis respectively. These two games are used for the characterization of Banzhaf value and equal division value respectively. Another important basis in cooperative game theory is the basis for the symmetric games s_T which is defined for \vert T\vert\leq k as
s_T(S)= \begin{cases}1, & \text { if }|T \cap S| \geq k \\ 0, & \text { otherwise }\end{cases}
Symmetric games ensure that all participants in coalitions S whose intersection with T results in a coalition greater than k earn an equal amount. Thus, player payoffs are determined only by the size of the coalition, not by who is playing the game. This basis is employed in 10to characterize the Banzhaf value.
2.3 Methodology
The study is primarily based on the theoretical development of a solution concept by combining two well-defined values in the existing literature on game theory. To accomplish this, two solution concepts, namely Banzhaf value 1and equal division value 2were investigated and then consolidated them using a parameter. First, the model is formulated for the corresponding value. Secondly, some new axioms are defined which are satisfied by the proposed value and then showed that these axioms define the proposed value uniquely. For the characterization of the proposed value, the induction hypothesis is used over the unanimity game and the symmetric game. The concept of amalgamation of players is used to serve this purpose. Additionally, the value is extended to the class of simple games and similar procedures were used to show the uniqueness of the value.
2.4 Basic definitions and axioms
In the following, we list some of the important axioms that are relevant to this paper. Before that, we define the following:
Definition 1. A player i\in N is a null player in v if MC_i^v(S)=0 for every coalition S\subseteq N\backslash\{i\}.
Definition 2. A player i\in N is a nullifying player if v(S)=0 for every coalition S with i\in S.
Definition 3. Two players i,j\in N are called symmetric with respect to the game v if for all S\subseteq N\backslash\left(i,\;j\right\}, v satisfies v(S\cup\{i\})=v(S\cup\left(j\right\}).
Definition 4. A player i\in N is said to be a dummy player in v if v\left(S\cup\left(i\right\}\right)-v(S)\;=\;v(\{i\}) for all S\subseteq N\backslash\{i\}.
Let \Phi:\;G^N\rightarrow R^n be a value. Here we list different axioms for \Phiwhich will be used for characterization and showing the uniqueness of the defined solution. They are listed as below.
Axiom 1. 2-efficiency (2E): For every T\subseteq N such that \vert T\vert=2,\;{\sum\nolimits_{i\in T}{\Phi_i\left(v\right)=}}\Phi_T(v_T).
Axiom 2. Efficiency (EFF): For the game (N,v), \Phi is efficient if \;{\sum\nolimits_{i\in N}{\Phi_i\left(v\right)=}}v(N).
Axiom 3. Dummy Player Property (D): If i\in N is a dummy player; then \Phi_i(v)=\;v(\{i\}).
Axiom 4. Nullifying Player Property (NPP): \Phi satisfies NPP if v\left(S\cup\{i\}\right)=0 implies \Phi_i(v)=0 for all S\subseteq N\backslash\{i\},
Axiom 5. Linearity (LI): For two games u and v; \Phi(k(u+v))\;=k\Phi(u)+k\Phi(v) for k\in R.
Axiom 6. Equal Treatment (ET): For two symmetric players i and j in N; \Phi_i(v)=\Phi_j(v).
Axiom 7. Super Additivity (SA): \Phi is super additive if \Phi_i\left(v\right)+\Phi_j\left(v\right)\leq\;\Phi_T(v) for every two-players-coalition T such that T=\{i,j\}.
Axiom 8. Transfer Property (TP): For two games u and v , \Phi\;satisfies transfer property if \;\Phi(v\vee u)+\Phi(v\wedge u)=\Phi(v)+\Phi(u)
Banzhaf value is a non-efficient value that satisfies certain standard axioms and is uniquely defined by these axioms. Some of the essential characterizations of the Banzhaf value are listed below.
Theorem 1.10 Given that \Phi is equal to the Banzhaf value in all the two players’ games, the “2-efficiency” axiom uniquely determines the Banzhaf value.
Theorem 2. 10\;\Phi satisfies (D), (ET), (LI) and (SA) for every v,u\in G^N if and only if \Phi is the Banzhaf value on G^N.
Theorem 3. 2\Phi satisfies (EFF), (ET), (LI) and (NPP) for every v,u\in G^N if and only if \Phi\;is the equal division value on G^N.
The Egalitarian-Banzhaf value3.1 The model
We now introduce the egalitarian-Banzhaf value, \Phi^{α−EB}, a new value for cooperative games. We take an approach similar to 7 allocating \alpha portion of the egalitarian value along with (1−α) portion of the marginalized value. Also, we follow a procedure where participants are permitted to join a coalition based on permutation, presuming that all conceivable permutations of admission have equal probability. For \alpha\in\lbrack0,\;1\rbrack, the \Phi^{α−EB} value is defined as
Observe that the value \Phi^{\alpha-EB}coincides with the Banzhaf value for \alpha=0 and the eEqual division value for \alpha=1. Now we compare the Banzhaf value and the egalitarian-Banzhaf value with the help of an example. We also observe how the value of the null player changes in both situations.
Example 1. Consider the game of three brothers namely\;A,\;B and C, living and running their family business together. Suppose A\;and B can make an output of one-third of a unit each when doing business individually. In contrast, their brother C is a disabled person and cannot contribute anything. Furthermore, we assume that A and C together can generate an output of one unit. Then the game (N,\;v) for N\;=\;\{A,\;B,\;C\} can be represented as
If sharing of worth is done according to Shapley value, then being a null player, C will receive nothing. Suppose they distribute their earnings according to Banzhaf value. Under this sharing situation, C will receive nothing in the end. If A and B take responsibility for their brother C, then a portion of their income will be shifted to C. The value transfer from A and B to C under \Phi^{\alpha-EB}value is shown in the table, taking \alpha=\frac12.
Players
Banzhaf Value
\Phi^{\alpha-EB}Value
Value Shifted
A
\frac12
\frac5{12}
-\frac1{12}
B
\frac12
\frac5{12}
-\frac1{12}
C
0
\frac16
+\frac2{12}
It is seen that player C received a one-sixth portion of the game for his survival. This value can be manipulated by changing the value of α depending on the game’s conditions and the players’ wishes. Thus, it seems a convenient way of allocation for situations mentioned above.
3.2 Characterization of the value
This section deals with the characterization of the \alpha- egalitarian Banzhaf value for \alpha\in R. These characterizations are inspired by Theorem (2) and Theorem (6) in the spirit of 10. For that, we modified the dummy player property with \alpha-dummy player property.
Axiom 7. \alpha-Dummy Property (\alpha-D): A value \Phi is said to satisfy (\alpha-D) if every game v and for every dummy player i\in N;{\;\Phi}_i(v)\;=\frac\alpha n+(1-\alpha)v(\{i\}).
This property ensures that each dummy player in each game obtains its worth along with the fixed fraction of the per capita income.
Theorem 4.\Phi satisfies (\alpha-D), (ET), (LI) and (SA) for every u,v\in G^N if and only if \Phi is equal to the\;\Phi^{\alpha-EB} value on G.
Proof: Since the Banzhaf value and the egalitarian value satisfy (LI); (ET); (SA). So, by linearity, \Phi^{\alpha-EB} also satisfies these properties. Moreover, it can be easily shown that the value also satisfies (\alpha-D).
For the converse part, we use the method of induction on v. For that, we show that the axiom system determines the values of \Phi in the class of unanimity games. We assume that \Phi is already determined on the games with n players and on the games of the type u_T such that\left|T\right|\leq k. Furthermore, we assume that
\Phi_i\left(u_T\right)=\left\{\begin{array}{c}
\frac{\alpha}{n}+\frac{1-\alpha}{2|T|-1}, \quad \text { if } i \in T \\
\frac{\alpha}{n}, \quad \text { otherwise }
\end{array}\right.
Let T\subseteq\{1,\;2,\;3,\;\;\cdots,n+1\} and \vert T\vert=k\;+1. Let us denote T^'=\;T\backslash\{i\} for i\in T. Then\vert T^'\vert=k. Now by (LI) we have
For i,j\in T, amalgamating player i\;to player j\;in u_T, we derive the game u_{T^'} of k players. Hence, by (SA);\;2a\leq\frac{2\alpha}n+\frac{1-\alpha}{2^{k-1}}; which implies
Since v’ is a game with a lesser number of players, so by the induction hypothesis and (SA), we have \Phi_{\overset-{ij}}\left(v\right)=2b\leq\frac{2\alpha}n\;+\frac{k\left(1-\alpha\right)}{2^{k-1}}; which implies
Comparing (5) and (8), the inequalities of (6) and (7) become equality. Thus, for i\in T we get a=\frac\alpha n+\frac{\left(1-\alpha\right)}{2^{\left(T\right|-1}} as desired. Similarly, we get c\;=\frac\alpha n for i\not\in T. Therefore;
\Phi_i\left(u_T\right)=\left\{\begin{array}{c}
\frac{\alpha}{n}+\frac{1-\alpha}{2^{|T|-1}}, \quad \text { if } i \in T \\
\frac{\alpha}{n}, \quad \text { otherwise }
\end{array}\right.
for\;\vert T\vert=\;k+1. Thus, by the induction hypothesis, it holds for all T where \vert T\vert is finite.
Now, we show that the total value of all the players involved in the game is always less than or equal to the worth of the grand coalition.
Lemma 1. For the game \left(N,v\right) , {\sum\nolimits_{i\in N}{\Phi^{EB}(v)\leq v\left(N\right)}}.
Proof: We proceed with the proof on the class of unanimity games, u_T. From theorem 4, for all i\in N, we have \Phi_i^{EB}\left(u_T\right)=\frac\alpha n+\frac{1-\alpha}{2^{\left(T\right|-1}} for i\in T and \Phi_i^{EB}\left(u_T\right)=\frac\alpha n for i\not\in T. Now, using the linearity of \Phi^{EB}, we get
Thus, we have {\sum\nolimits_{i\in N}{\Phi_i^{EB}\left(u_T\right)}}\leq u_T(N), which shows that the total value of all the players collected out of the game is less than or equal to the value of the grand coalition. This completes the proof.
3.3 Egalitarian-Banzhaf value for Simple Games
A simple game is a game (N,v) where v\left(S\right)\in\{0,1\} for all S\subseteq N. All the coalitions, S\subseteq N with v(S)=1 are called winning and all the rest losing. Axioms that characterize the \Phi^{\alpha-EB} value on G^N need not characterize the value in the class of simple games. However, (LI); (ET); (SA) and (TP) do characterize \Phi^{\alpha-EB} on the class G_S^N which consists of all simple games on N. (TP) is required for pairs of simple games u,v\in G_S^N for which the sum game(u+v) also is simple. One of the characterizations of the Banzhaf value in the class of G_S^N is given below.
Theorem 5.10\Phi satisfies (D), (ET), (TP) and (SA) for every u,v\in G_S^N if and only if \Phi is the Banzhaf value.
Now we characterize the \Phi^{\alpha-EB} on G_S^N on the line of the above theorem. For that, we replace (D) with (\alpha-D).
Theorem 6.\;\Phi satisfies (\alpha-D), (ET), (TP) and (SA) for every u,v\in G_S^N if and only if \Phi is the Banzhaf value.
Proof. We assume that \Phi is already determined on the class of simple games G_S^N of n players of the type u_T. Furthermore, we have
\Phi_i\left(u_T\right)=\left\{\begin{array}{l}
\frac{\alpha}{n}+\frac{1-\alpha}{2^{|T|-1}}, \quad \text { if } i \in T \\
\frac{\alpha}{n}, \quad \text { otherwise }
\end{array}\right.
Now, we show that \Phi holds on u_T for n+1 players. Let u and v be two simple games. For any coalition S\subseteq N; define the games u\vee v and u\wedge v as follows:
Comparing (14) and (17), the inequalities of (15) and (16) become equality. Thus, for i\in T, we get a=\frac\alpha n+\frac{\left(1-\alpha\right)}{2^{k-1}} as desired. Similarly, we get d=\frac\alpha n for i\not\in T. Therefore;
\Phi_i\left(u_T\right)=\left\{\begin{array}{c}
\frac{\alpha}{n}+\frac{(1-\alpha)}{2^{k-1}}, \quad \text { if } i \in T \\
\frac{\alpha}{n}, \quad \text { otherwise }
\end{array}\right.
for \vert T\vert=k+1. Thus, by the induction hypothesis, it holds for all T where |T\vert is finite.
Discussion and Application
The participants act uniquely under the Banzhaf value-sharing technique. Every player will have a value that is only determined by their marginal contribution to any coalitions that may emerge. The value of an agent in a coalition is the marginal value across all conceivable orders in which the agents might join the coalition. This value does not allow the players to financially support their weaker partners. But, as envisaged above, each player can contribute a percentage of his money to raise the contentment of the weaker players with the approval of other players in the game. It is assumed that they agree to assist their weaker companions by consent. We demonstrated that the recommended value may improve the Banzhaf value and equal division value solutions for certain situations. Suppose a group of people set up a new start-up with certain resources. They create an alliance and make profits through the collaboration of their funds and labour. The egalitarian-Banzhaf value takes a part of the worth of the grand coalition and divides it equally among all the agents in the group. This asserts that all agents will surely receive an amount from the game. It increases players’ incentives to join a coalition, making the establishment of the grand coalition easier. Then the remaining portion is distributed (partially or fully) according to the Banzhaf value. This part asserts that a player contributing more to the game, will surely receive more profit. If any portion remains after sharing, it will be utilised for collective objectives such as charity or future investment. This value may be used in a wireless network to distribute joint payoff via the cooperation of each node, and the flexibility can be maintained based on the performance of the node by adjusting the value of the parameter\alpha.
Concluding remarks
Banzhaf value and Egalitarian value have their importance based on the game’s structure, but the consolidation of both values seems more effective in certain situations. So, a consolidated value is introduced. A new property called (α-D) is introduced, allowing a portion of the game’s gain to distribute equally among all players. The remaining portion is distributed according to their marginal contributions. Then the newly defined value is characterized using (α-D), (ET), (LI) and (SA). Also, (α-D), (ET), (TP), and (SA) characterize the value of the class of simple games. In our future work, we aim to generalize our new value based on the size of the coalition and study the weighted value of the defined solution by assigning weights to players in the TU- game.
Acknowledgement
The authors acknowledge Dibrugarh University for providing the necessary resources during the preparation of the manuscript.
ReferencesBanzhafJ F IWeighted voting does not work: A mathematical analysisBrinkR Van DenNull or nullifying players: The difference between the Shapley value and equal division solutionsLiDeng-FengYeYin-FangFeiWeiExtension of generalized solidarity values to interval-valued cooperative gamesPérezJoss Erick SánchezCharacterization of the Banzhaf Value Using a Consistency AxiomDubeyPradeepNeymanAbrahamWeberRobert JamesValue Theory Without EfficiencyGallegoInésFernándezJulio RJiménez-LosadaAndrésOrdóñezManuelA Symmetric Banzhaf Cooperation Value for Games with a Proximity Relation among the AgentsJoostenRDynamics, equilibria and values. Ph.D. thesis, Maastricht University, The Netherland1996ChoudhuryDhrubajitBorkotokeySurajitKumarRajnishSarangiSudiptaThe Egalitarian Shapley value: a generalization based on coalition sizesChoudharyDBorkotokeySKumarRSarangiSConsolidating Marginalism and Egalitarianism: A New value Transferable utility gamesLehrerEAn axiomatization of the Banzhaf value