The efficient partition surplus Owen graph value

Abstract

The Owen graph value for games with coalition structure and graph restricted communication was introduced by Vázquez-Brage et al. (Games Econ Behav 12: 42–53, 1996). It has been known that the value satisfies the axiom of component efficiency, requiring that the players of a component share the benefits generated by this component among themselves. In this paper we extend the Owen graph value to an efficient value and we provide axiomatic characterizations of this value.

1 Introduction

Cooperation among players can be depicted by a cooperative game with transferable utility (shortly, a TU-game). In this model, every subset of players can form a feasible coalition and each player in any coalition can obtain payoff from their cooperation. However, in many practical situations, the collection of feasible coalitions is restricted by some social, economical, communication, or technical structure. For this reason, one begins to consider the TU-games with cooperation structures.

Aumann and Drèze (1974) seem to be the first to consider TU-games with cooperation structure described by a coalition structure, i.e., a partition of the grand coalition. For this model, Owen (1977) introduced a modification of the Shapley value (Shapley, 1953), named the Owen value. Myerson (1977) introduced another class of TU-games with cooperation structures given by communication graphs on the player set and he proposed a famous allocation rule, called the Myerson value, applying the Shapley value to the so-called graph-restricted game. Inspired by Owen and Myerson’s study, Vázquez-Brage et al. (1996) considered TU-games with coalition and graph structures by combining the two cooperation structures above and they introduced the Owen graph value for this model.

In a TU-game with graph structure, the Myerson value satisfies component efficiency, i.e., for each component of the graph, the total payoff to its players equals the worth of that component. This means that the worth of the grand coalition is not fully distributed among its members. Casajus (2007) developed the first efficient extension of the Myerson value to prevent the surplus. Later, Béal et al. (2015) suggested the interpretation that the communication graph does not necessarily affect the productivity but can influence the way the players distribute the worth. This interpretation supports values that are efficient, i.e., values which distribute the worth of the grand coalition among the players.

A variety of efficient extensions of the Myerson value and the other values with component efficiency have been developed in the literature. For example, the efficient egalitarian Myerson value (van den Brink et al., 2012; Béal et al., 2015), the efficient two-step egalitarian surplus Myerson value (Casajus, 2007; Hu et al., 2018), the efficient $\alpha$-proportional Myerson value (Shan et al., 2019), the efficient quotient Myerson value (Li & Shan, 2020), the efficient average tree solution and the efficient compensation solution (Béal et al., 2018), the egalitarian efficient Aumann-Drèze value (Hu et al., 2019), the efficient egalitarian Owen graph value (Shan et al., 2020).

In practice, it might be not desirable that the Owen graph value satisfies component efficiency. To illustrate this, we provide an example of the research fund allocation that is similar to the one used in van den Brink et al. (2012) but now both coalition and graph structures are considered. A research fund that has money available to distribute amongst individual researchers and has the policy to stimulate interdisciplinary research, therefore a joint application of researchers from different disciplines will receive higher research grand. Moreover, it requires that only a group of researchers who can communicate can jointly submit a proposal. The set of researchers from the same discipline can be viewed as a (priori) union and two researchers are connected by a link if they can directly communicate. Hence, this situation can be described as a TU-game with coalition and graph structures (see Example 3.1). Although usually not all researchers can communicate, either directly or indirectly, still the full research budget is available and will be distributed. This requires a value to satisfy efficiency. In this paper we shall generalize the Owen graph value for a TU-game with coalition and graph structures as an efficient value.

The goal of this paper is to give an efficient extension of the Owen graph value for TU-games with coalition and graph structures, named the efficient partition surplus Owen graph value, by first assigning to each player his Owen graph value and then distributing the surplus by the two-step partition egalitarian surplus value. The two-step partition egalitarian surplus value requires that the surplus is equally distributed among all unions in the first step and then the payoff of each union in the first step is equally distributed among its players. We provide axiomatizations of this efficient value.

This article is organized as follows. In Sect. 2 we give preliminaries. Section 3 introduces the efficient partition surplus Owen graph value and we provide axiomatic characterizations of this efficient value. Section 4 contains some concluding remarks.

2 Preliminaries

2.1 TU-games and TU-games with coalition structures

A TU-game is a pair (N, v) consisting of a finite set of players $N=\{1,2,\dots ,n\}$ and a characteristic function v defined on $2^N$ with that assigns to each coalition $S\subseteq N$ a real number v(S), called the worth of S, and such that $v(\emptyset )=0$. We denote by ${\mathbb {G}}(N)$ the set of TU-games with player set N. For any coalition $S\subseteq N$, the cardinality of S is denoted by |S| or s. For simplicity, we shall write $S\cup i$, $S\setminus i$ instead of $S\cup \{i\}$ and $S\setminus \{i\}$, respectively.

For nonempty coalition $T\subseteq N$, the subgame $(T,v_T)$ of (N, v) is defined by $v_T(S) = v(S)$ for any $S\subseteq T$.

An allocation rule or a value f on ${\mathbb {G}}(N)$ is a map that assigns a vector $f(N,v)\in {\mathbb {R}}^n$ to each game (N, v). The Shapley value (Shapley, 1953) is the value defined by

$$\begin{aligned} Sh_i(N,v)= \sum _{S:\,S\subseteq N\setminus i} \frac{|S|!(|N|-|S|-1)!}{|N|!}\big [v(S\cup i)-v(S)\big ], \;\; \hbox { for any}\ i\in N. \end{aligned}$$

A coalition structure P on N is given by a partition $P=\{P_1,P_2,\ldots ,P_m\}$ of player set N. Every element of a partition is called a (priori) union. Let ${\mathbb {C}}(N)$ denote the set of all coalition structures on N. In particular, we call $P^n=\big \{\{1\},\{2\},\ldots ,\{n\}\big \}$ and $P^N=\{N\}$ the trivial coalition structures. For any $i\in P_k$, $P_{-i}\in {\mathbb {C}}(N)$ is defined as $P_{-i}=\big \{P_1,\ldots ,P_{k-1},P_{k}\setminus \{i\},P_{k+1},\ldots ,P_m,\{i\}\big \}$. For any nonempty $T\subseteq N$, the restricted coalition structure $P_T$ to T is defined by $P_T=\{P_k\cap T\ne \emptyset \,|\,k\in M\}$, where $M=\{1,2,\ldots ,m\}$.

A game with coalition structure is a triple (N, v, P) where (N, v) is a TU-game and P a coalition structure on N. We denote the set of all such games by ${\mathbb {U}}(N)$.

For any $(N,v,P)\in {\mathbb {U}}(N)$ with $P=\big \{P_k\,|\,k\in M=\{1,2,\ldots ,m\}\big \}$, the quotient game $(M,v^P)\in {\mathbb {G}}(M)$ is the TU-game in which every union is a player, concretely, $v^P(R)=v(\bigcup _{k\in R}P_k)$ for any $R\subseteq M$.

A value on ${\mathbb {U}}(N)$ is a map $f:{\mathbb {U}}(N)\rightarrow {\mathbb {R}}^n$ that assigns a payoff vector $f(N,v,P)\in {\mathbb {R}}^n$ to each $(N,v,P)\in {\mathbb {U}}(N)$. The Owen value (Owen, 1977) Ow is defined by

$$\begin{aligned} Ow_i(N,v,P)&=\sum _{R\subseteq M\setminus h}\sum _{S\subseteq P_h\setminus i}\frac{|R|!(|M|-|R|-1)!|S|!(|P_h|-|S|-1)!}{|M|!|P_h|!}\Big [v\Big (\bigcup _{r\in R}P_r\cup S\cup i\Big )\\&\quad -v\Big (\bigcup _{r\in R}P_r\cup S\Big )\Big ], \end{aligned}$$

for any $(N,v,P)\in {\mathbb {U}}(N)$ and $i\in P_h\in P$. The Owen value can be characterized by the properties of efficiency, null player, symmetry in the unions, symmetry in the quotient and additivity below.

Efficiency (E). For any $(N,v,P)\in {\mathbb {U}}(N)$, $\sum _{i\in N}f_i(N,v,P)=v(N)$.

Null player (NP). For any $(N,v,P)\in {\mathbb {U}}(N)$ and any $i\in N$, if i is a null player, i.e., $v(S\cup i)=v(S)$ for all $S\subseteq N\setminus i$, then $f_i(N,v,P)=0$.

Symmetry in the unions (SU). For any $(N,v,P)\in {\mathbb {U}}(N)$, $P_k\in P$ and $i,j\in P_k$, if $v(S\cup i)=v(S\cup j)$ for any $S\subseteq N\setminus \{i,j\}$, then $f_i(N,v,P)=f_j(N,v,P)$.

Symmetry in the quotient (SQ). For any $(N,v,P)\in {\mathbb {U}}(N)$ and $P_k,P_s\in P=\{P_1,P_2,\ldots ,P_m\}$, if $v^P(R\cup k)=v^P(R\cup s)$ for any $R\subseteq M\setminus \{k,s\}$, then $\sum _{i\in P_k}f_i(N,v,P)=\sum _{i\in P_s}f_i(N,v,P)$.

Additivity (A). For any $(N,v,P),(N,w,P)\in {\mathbb {U}}(N)$, $f(N,v+w,P)=f(N,v,P)+f(N,w,P)$ where $(v+w)(S)=v(S)+w(S)$ for any $S\subseteq N$.

2.2 TU-games with coalition and graph structures

A graph is a pair (N, L) consisting of a set N of nodes representing players and a set $L\subseteq L^N=\big \{\{i,j\}\,|\,i,j\in N, i\ne j\big \}$ of links. $L^N$ is the complete graph and each unordered pair $\{i,j\}\in L$ with $i,j\in N$ a link. For simplicity of notation, we often write ij instead of $\{i,j\}$. We denote the set of all graphs on N by g(N).

We say that two nodes i and j in L are connected if $ij\in L$ or there exists a sequence of nodes $i_1,i_2,\ldots ,i_p$ with $i=i_1, j=i_p$ such that $i_ki_{k+1}\in L$ for $k=1,2,\ldots ,p-1$. The graph (N, L) is connected if all $i,j\in N$ are connected in L. A nonempty set $S\subseteq N$ is connected if every pair of nodes in S is connected in the subgraph $(S, L_S)$ induced by S in L, in which $L_S=\{ij\in L\,|\,i,j\in S\}$. We will assume that S is connected whenever $s=1$. A set $T\subseteq N$ is called a component of the graph (N, L) if T is a maximal connected subset, i.e., T is connected in the graph and, for all $T\cup i$ is not connected for each $i\in N\setminus T$. Let C(N, L) denote the set of all components in (N, L) and C(S, L) the set of the components of S in $(S, L_S)$. The component of N containing i is often denoted by $C_i$.

The set of all links incident with the node i is denoted by $L_i=\{l\in L\,|\,i\in l\}$. For any $\delta \subseteq L$, the graph $L_{-\delta }=L\setminus \delta$ is the graph obtained from (N, L) by deleting the links in $\delta$. In particular, we shall write $L_{-ij}$ and $L_{-i}$ instead of $L_{-\{ij\}}$ and $L\setminus L_i$, respectively.

A triple (N, v, L) is a game with graph structure, or simply a graph game, consisting of a TU-game $(N,v)\in {\mathbb {G}}(N)$ and a graph $(N,L)\in g(N)$. A graph game is connected if the associated graph (N, L) is connected. The sets of graph games and connected graph games on N are denoted by ${\mathcal {G}}$ and ${\mathcal {G}}_C$, respectively. Clearly, ${\mathcal {G}}_C \subseteq {\mathcal {G}}$.

Myerson (1977) introduced the graph-restricted game $(N,v^L)$ for a $(N,v,L)\in {\mathcal {G}}$ defined by

$$\begin{aligned} v^L(S)=\sum _{T\in C(S,L)} v(T), \,\, \, \text{ for } \text{ all } S\subseteq N\text{. } \end{aligned}$$

The Myerson value is the allocation rule that assigns to every graph game (N, v, L) the Shapley value of the graph-restricted game $v^L$, i.e., $\mu (N,v,L)=Sh(N,v^L)$, and it is characterized by component efficiency (CE) and fairness (F) in Myerson (1977).

A game with coalition and graph structures, or simply a CG-game, is a quadruple (N, v, L, P), where $(N,v)\in {\mathbb {G}}(N)$, $(N,L)\in g(N)$ and $(N,P)\in {\mathbb {C}}(N)$. Let ${\mathcal {G}}_{CG}$ denote the set of all CG-games on N. A CG-game (N, v, L, P) is connected if the graph (N, L) is connected, and the set of all connected CG-games is denoted by ${\mathcal {G}}_{CG}^{C}$. Clearly, ${\mathcal {G}}_{CG}^{C}\subseteq {\mathcal {G}}_{CG}$. For any $P_k,P_s\in P$, let $L_{(P_k,P_s)}=\{ij\in L\,|\,i\in P_k, j\in P_s\}$ and $L_{-(P_k, P_s)}=L\setminus L_{(P_k,P_s)}$.

For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$, the communication quotient game $(M,v^{LP})\in {\mathbb {G}}(M)$ is defined by

$$\begin{aligned} v^{LP}(R)=v^L(\cup _{r\in R}P_r)=\sum _{S\in C(\cup _{r\in R}P_r, L)}v(S), \, \, \, \hbox { for all}\ R\subseteq M. \end{aligned}$$

The communication quotient game says that the economic output of any coalition $R\in M$ is realized by the economic output of coalition $\cup _{r\in R}P_r$ restricted by L, that is, the sum of the economic output of all components in $C(\cup _{r\in R}P_r, L)$.

The Owen graph value $\psi$ is defined in Vázquez-Brage et al. (1996) as the Owen value of the graph-restricted game $v^L$, that is,

$$\begin{aligned} \psi (N,v,L,P)=Ow(N,v^L,P). \end{aligned}$$

Let $f:{\mathcal {G}}_{CG}\rightarrow {\mathbb {R}}^n$ be a value. We recall some axioms.

Component efficiency (CE). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and any $C\in C(N,L)$,

$$\begin{aligned}\sum _{i\in C}f_i(N,v,L,P)=v(C).\end{aligned}$$

Component efficiency for trivial coalition (CETC). For any subclasses $(N,v,L,P^n) \in {\mathcal {G}}_{CG}$ and any $C\in C(N,L)$, $\sum _{i\in C}f_i(N,v,L,P^n)=v(C).$

Fairness in the graph (FG). For any $(N,v,L)\in {\mathcal {G}}$ and $ij\in L$ with $i,j\in N$,

$$\begin{aligned} f_i(N,v,L,P^n)-f_i(N,v,L_{-ij},P^n)=f_j(N,v,L,P^n)-f_j(N,v,L_{-ij},P^n). \end{aligned}$$

Note that for any $(N,v,L,P^n)\in {\mathcal {G}}_{CG}$, $\psi (N,v,L,P^n)=\mu (N,v,L)$. Furthermore, fairness in the graph (FG) is equivalent to fairness (F) for the Myerson value $\mu$ when P is the trivial coalition structure, i.e., $P=P^n$. Fairness states that $f_i(N,v,L)-f_i(N,v,L_{-ij})=f_j(N,v,L)-f_j(N,v,L_{-ij})$ for any $(N,v,L)\in {\mathcal {G}}$ and $ij\in L$.

Balanced contributions for the graph (BCG). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $i,j\in P_k$ with $P_k \in P$,

$$\begin{aligned} f_i(N,v,L,P)-f_i(N,v,L_{-j},P)=f_j(N,v,L,P)-f_j(N,v,L_{-i},P). \end{aligned}$$

Balanced contributions for the unions (BCU). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $i,j\in P_k$ with $P_k \in P$,

$$\begin{aligned} f_i(N,v,L,P)-f_i(N,v,L,P_{-j})=f_j(N,v,L,P)-f_j(N,v,L,P_{-i}). \end{aligned}$$

Fairness in the quotient (FQ). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $P_k, P_s\in P$,

$$\begin{aligned} \sum _{i\in P_k}f_i(N,v,L,P)&-\sum _{i\in P_k}f_i(N,v,L_{-(P_k, P_s)},P)=\sum _{i\in P_s}f_i(N,v,L,P)\\&-\sum _{i\in P_s}f_i(N,v,L_{-(P_k, P_s)},P). \end{aligned}$$

Quotient game property (QG). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $P_k \in P=\{P_1,P_2,\ldots ,P_m\}$ with $M=\{1,2,\ldots ,m\}$,

$$\begin{aligned} \sum _{i\in P_k}f_i(N,v,L,P)=f_k(M,v^{LP},L^M,P^m), \end{aligned}$$

where the partition $P^m=\big \{\{P_1\},\{P_2\},\ldots ,\{P_m\}\big \}$ and $L^M$ is the complete graph on M.

The axiomatizations of the Owen graph value have been developed by Vázquez-Brage et al. (1996) and Alonso-Meijide et al. (2009)

Theorem 2.1

(Vázquez-Brage et al., 1996) The Owen graph value $\psi$ is the unique solution on ${\mathcal {G}}_{CG}$ satisfying component efficiency (CE), fairness in the quotient (FQ) and either balanced contributions for the unions (BCU) or balanced contributions for the graph (BCG).

Theorem 2.2

(Alonso-Meijide et al., 2009) The Owen graph value $\psi$ is the unique solution on ${\mathcal {G}}_{CG}$ satisfying component efficiency for trivial coalition (CETC), fairness in the graph (FG), balanced contributions for the unions (BCU) and quotient game property (QG).

3 The efficient partition surplus Owen graph value

In this section we shall introduce the efficient partition surplus Owen graph value for the CG-games. As mentioned above, the Owen graph value satisfies component efficiency, that is, $\sum _{i\in C}\psi _i(N,v,L,P)=v(C)$ for any $(N,v,L,P)\in {\mathcal {G}}_{CG}$, $C\in C(N,L)$, so $\sum _{i\in N}\psi _i(N,v,L,P)=v^L(N)$.

In general, $v(N)\ne v^L(N)$. If that happens, this implies that the total Owen graph value obtained by the players in the grand coalition is $v^L(N)$ not v(N), so this will yield a surplus $v(N)-v^L(N)$. A question we are facing is how to allocate the surplus reasonably. Various approaches to distribute the surplus $v(N)-v^L(N)$ have been developed in Casajus (2007), van den Brink et al. (2012), Shan et al. (2019), Li and Shan (2020) and elsewhere.

Here we introduce a new method to distribute the surplus $v(N)-v^L(N)$.

Definition 3.1

For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $i\in P_k\in P$, the efficient partition surplus Owen graph value is defined by

$$\begin{aligned} EU\psi _i(N,v,L,P): =\psi _i(N,v,L,P)+\frac{v(N)-v^L(N)}{|P||P_k|}. \end{aligned}$$

This value EU$\psi$ first assigns to each player his Owen graph value and then distributes the surplus $v(N)-v^L(N)$ (may be zero) with the two-step partition egalitarian surplus value, in which the surplus is equally distributed among all priori unions and then the payoff gained by each priori union in the first step is equally distributed among its players.

Note that, EU$\psi (N,v,L,P)=EE\mu (N,v,L)$ when $P^n=\big \{\{1\}, \{2\},\ldots , \{n\}\big \}$ or $P^N=\{N\}$ and EU$\psi (N,v,L,P)=Ow(N,v,P)$ when $L=L^N$, i.e., L is the complete graph.

3.1 Axiomatizations of the EU$\psi$ value

In this subsection we shall characterize the efficient partition surplus Owen graph value EU$\psi$.

A value is component decomposable on ${\mathcal {G}}_{CG}$ if for any CG-game (N, v, L, P), the payoff of each player $i\in N$ is completely determined within the component $C_i$ containing i.

Component decomposability (CD). A value f is component decomposability, if for any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $i\in C_i\in C(N,L)$, $f_i(N,v,L,P)=f_i(C_i,v_{C_i},L_{C_i},P_{C_i})$.

One has observed that every value with component efficiency on ${\mathcal {G}}$ is component decomposable. This implies that the Owen graph value satisfies component decomposability.

To characterize the efficient partition surplus Owen graph value EU$\psi$, we need the following properties.

Link-fairness in the quotient (LFQ). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$, any $P_k,P_s\in P$ and any $ij\in L_{(P_k,P_s)}$,

$$\begin{aligned} \sum _{h\in P_k}f_h(N,v,L,P)&-\sum _{h\in P_k}f_h(N,v,L_{-ij},P)=\sum _{h\in P_s}f_h(N,v,L,P)\\&-\sum _{h\in P_s}f_h(N,v,L_{-ij},P). \end{aligned}$$

Link-fairness in the quotient states that the change of the total payoffs of any two unions is same when any one link joining them are severed.

Connected link-fairness in the quotient (CLFQ). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}^{C}$, any $P_k,P_s\in P$ and any link $ij \in L_{(P_k,P_s)}$,

$$\begin{aligned}&\sum _{h\in P_k}f_h(N,v,L,P)-\sum _{h\in P_k}f_h\big (C_h(N,L_{-ij}),v_{C_h(N, L_{-ij})},{(L_{-ij})}_{C_h(N, L_{-ij})},P_{C_h(N, L_{-ij})}\big )\\= & {} \sum _{h\in P_s}f_h(N,v,L,P)-\sum _{h\in P_s}f_h\big (C_h(N,L_{-ij}),v_{C_h(N, L_{-ij})},{(L_{-ij})}_{C_h(N, L_{-ij})},P_{C_h(N, L_{-ij})}\big ). \end{aligned}$$

Connected link-fairness in the quotient states that for any connected CG-game, the change of the total payoffs of any two unions $P_k$ and $P_s$ is the same if a link ij between $P_k$ and $P_s$ is removed. Connected link-fairness in the quotient compares the original payoffs of the union $P_i$ $(i=k,s)$ with the payoffs $P_i$ $(i=k,s)$ obtained if the CG-game is restricted to each player’s component when the link ij is removed and imposes an equal payoff of the union variation. This axiom is motivated by connected fairness given in Béal et al. (2015, 2018).

We show that the Owen graph value satisfies link-fairness in the quotient (LFQ).

Lemma 3.1

For $(N,v,L,P)\in {\mathcal {G}}_{CG}$, the Owen graph value $\psi (N,v,L,P)$ satisfies quasi-fairness in the quotient (LFQ).

Proof

For any $P_k,P_s\in P$ and any $ij\in L_{(P_k,P_s)}$, we let $w=v^L-v^{L_{-ij}}$. For all $R\subseteq M\setminus \{k,s\}$, clearly $w^P(R\cup k)=w^P(R\cup s)=0$. By symmetry in the quotient (SQ) of the Owen value, $\sum _{i\in P_k}Ow_i(N,w,P)=\sum _{i\in P_s}Ow_i(N,w,P)$. Then, by additivity (A) of the Owen value, we obtain

$$\begin{aligned} \sum _{i\in P_k}Ow_i(N,v^L,P)&-\sum _{i\in P_k}Ow_i(N,v^{L_{-ij}},P)=\sum _{i\in P_s}Ow_i(N,v^L,P)\\&-\sum _{i\in P_s}Ow_i(N,v^{L_{-ij}},P). \end{aligned}$$

Since $\psi (N,v,L,P)=Ow(N,v^L,P)$, $\psi (N,v,L,P)$ satisfies LFQ. $\square$

In order to give an characterization of the efficient partition surplus Owen graph value, we first give a characterization of the Owen graph value on the class of connected CG-games.

Theorem 3.1

A value f(N, v, L, P) on ${\mathcal {G}}_{CG}^{C}$ satisfies efficiency (E), connected link-fairness in the quotient (CLFQ) and balanced contributions for the unions (BCU) if and only if $f(N,v,L,P)=\psi (N,v,L,P)$ on ${\mathcal {G}}_{CG}^{C}$.

Proof

Existence. We show that the Owen graph value $\psi (N,v,L,P)$ satisfies the three properties. By Theorem 2.1, we have seen that $\psi (N,v,L,P)$ satisfies efficiency (E) and balanced contributions for the unions (BCU). We show that $\psi (N,v,L,P)$ satisfies connected link-fairness in the quotient (CLFQ). Let $ij\in L$.

If removing ij does not add new components, the property of link-fairness in the quotient (LFQ) directly implies connected link-fairness in the quotient (CLFQ).

If removing ij adds new components, then

$$\begin{aligned} \sum _{h\in P_k}\psi _h(N,v,L,P)&-\sum _{h\in P_s}\psi _h(N,v,L,P)=\sum _{h\in P_k}\psi _h(N,v,L_{-ij},P)-\sum _{h\in P_s}\psi _h(N,v,L_{-ij},P)\\&=\sum _{h\in P_k}\psi _h\big (C_h(N, L_{-ij}),v_{C_h(N, L_{-ij})},{(L_{-ij})}_{C_h(N, L_{-ij})},P_{C_h(N, L_{-ij})}\big )\\&-\sum _{h\in P_s}\psi _h\big (C_h(N, L_{-ij}),v_{C_h(N, L_{-ij})},{(L_{-ij})}_{C_h(N, L_{-ij})},P_{C_h(N, L_{-ij})}\big ), \end{aligned}$$

where the first equation holds by link-fairness in the quotient (LFQ) and the second equation follows since the Owen graph value satisfies component decomposability (CD).

Uniqueness. Let f be a value on ${\mathcal {G}}_{CG}^{C}$ satisfying the above three properties. We have to prove that $f=\psi$. We first show that $\sum _{h\in P_k}f_h(N,v,L,P)=\sum _{h\in P_k}\psi _h(N,v,L,P)$ for any $k\in M$ by induction on $|N|+|L|$.

If $|N|=1$, then clearly $f_i(N,v,L,P)=\psi _i(N,v,L,P)$ by efficiency (E). We may assume that $|N|\ge 2$ and for any $(N^\prime ,v,L^\prime ,P_{N^\prime })\in {\mathcal {G}}_{CG}^{C}$ with $|N^\prime |+|L^\prime |< |N|+|L|$, $f(N^\prime ,v,L^\prime ,P_{N^\prime })=\psi (N^\prime ,v,L^\prime ,P_{N^\prime })$ holds. Therefore, for $(N,v,L,P)\in {\mathcal {G}}_{CG}^{C}$ and any $P_k,P_s\in P$, there exists a link $ij\in L$ since L is connected. By connected link-fairness in the quotient (CLFQ) and the inductive hypothesis, we have

$$\begin{aligned} \sum _{h\in P_k}f_h(N,v,L,P)&-\sum _{h\in P_s}f_h(N,v,L,P)\\&=\sum _{h\in P_k}f_h\big (C_h(N,L_{-ij}),v_{C_h(N,L_{-ij})},{(L_{-ij})}_{C_h(N,L_{-ij})},P_{C_h(N,L_{-ij})}\big )\\&-\sum _{h\in P_s}f_h\big (C_h(N,L_{-ij}),v_{C_h(N,L_{-ij})},{(L_{-ij})}_{C_h(N,L_{-ij})},P_{C_h(N,L_{-ij})}\big )\\&=\sum _{h\in P_k}\psi _h\big (C_h(N,L_{-ij}),v_{C_h(N,L_{-ij})},{(L_{-ij})}_{C_h(N,L_{-ij})},P_{C_h(N,L_{-ij})}\big )\\&-\sum _{h\in P_s}\psi _h\big (C_h(N,L_{-ij}),v_{C_h(N,L_{-ij})},{(L_{-ij})}_{C_h(N,L_{-ij})},P_{C_h(N,L_{-ij})}\big )\\&=\sum _{h\in P_k}\psi _h(N,v,L,P)-\sum _{h\in P_s}\psi _h(N,v,L,P). \end{aligned}$$

Thus, by connectedness of L, it is easy to see that there exists a constant d for all $k\in M$ such that

$$\begin{aligned} \sum _{h\in P_k}f_h(N,v,L,P)-\sum _{h\in P_k}\psi _h(N,v,L,P)=d. \end{aligned}$$

By efficiency (E), we have

$$\begin{aligned} |M|d= \sum _{s\in M}\sum _{h\in P_s}\big (f_h(N,v,L,P)-\psi _h(N,v,L,P)\big )=v(N)-v(N)=0, \end{aligned}$$

and so $d=0$. Hence, for any $k\in M$, we have

$$\begin{aligned} \sum _{h\in P_k}f_h(N,v,L,P)=\sum _{h\in P_k}\psi _h(N,v,L,P). \end{aligned}$$

(1)

We next show that $f_i(N,v,L,P)=\psi _i(N,v,L,P)$ for any $i \in N$ by induction on |P|. For any $(N,v,L,P)\in {\mathcal {G}}_{CG}^{C}$, if there is some $P_k\in P$ such that $|P_k|=1$, say $P_k=\{i\}$, then $f_i(N,v,L,P)=\psi _i(N,v,L,P)$ by (1). Suppose that $f_i(N,v,L,P)=\psi _i(N,v,L,P)$ for $m\le |P|\le n$. We show that $f_i(N,v,L,P)=\psi _i(N,v,L,P)$ for $|P|=m-1$. Clearly, there exists a $P_k\in P$ such that $|P_k|\ge 2$. Let $i,j\in P_k$. Note that $|P_{-i}|=|P_{-j}|=m$, by balanced contributions for the unions (BCU) and the inductive hypothesis, we have

$$\begin{aligned} f_i(N,v,L,P)-f_j(N,v,L,P)= & {} f_i(N,v,L,P_{-j})-f_j(N,v,L,P_{-i})\\= & {} \psi _i(N,v,L,P_{-j})-\psi _j(N,v,L,P_{-i})\\= & {} \psi _i(N,v,L,P)-\psi _j(N,v,L,P). \end{aligned}$$

Hence, for each $i\in P_k \in P$, there exists a constant $d_{P_k}$ such that

$$\begin{aligned} f_i(N,v,L,P)-\psi _i(N,v,L,P)=d_{P_k}. \end{aligned}$$

(2)

Combining (1) and (2), we obtain

$$\begin{aligned} 0=\sum _{i\in P_k}\big (f_i(N,v,L,P)-\psi _i(N,v,L,P)\big )=|P_k|d_{P_k}, \end{aligned}$$

and so $d_{P_k}=0$. Then, for any $P_k\in P$ with $|P_k|\ge 2$ and any $i,j\in P_k$, $f_i(N,v,L,P)=\psi _i(N,v,L,P)$. Therefore, $f_i(N,v,L,P)=\psi _i(N,v,L,P)$ for all $i\in N$. $\square$

In Theorem 3.1, we characterize the Owen graph value on the class of connected CG-games. By Theorem 3.1, we are now ready to give an axiomatic characterization of the EU$\psi$ value on ${\mathcal {G}}_{CG}$.

Theorem 3.2

The efficient partition surplus Owen graph value (EU$\psi$) on ${\mathcal {G}}_{CG}$ is the unique value satisfying efficiency (E), link-fairness in the quotient (LFQ), connected link-fairness in the quotient (CLFQ) and balanced contributions for the unions (BCU).

Proof

Existence. That the value EU$\psi (N,v,L,P)$ satisfies the above four properties follows directly from the fact that the Owen graph value satisfies the axioms of component efficiency (CE), link-fairness in the quotient (LFQ) (by Lemma 3.1) and balanced contributions for the unions (BCU).

Uniqueness. Suppose that there exists a value f on ${\mathcal {G}}_{CG}$ satisfying the four properties. We have to show that $f=$EU$\psi$. If $(N,v,L,P)\in {\mathcal {G}}_{CG}^{C}$, we immediately have $f=\psi =$EU$\psi$ by Theorem 3.1. We may therefore assume that $(N,v,L,P)\in {\mathcal {G}}_{CG}\setminus {\mathcal {G}}_{CG}^{C}$. Then $|C(N,L)|\ge 2$.

For any $k\in M$, we show that the following equality holds,

$$\begin{aligned} \sum _{h\in P_k}f_h(N,v,L,P)=\sum _{h\in P_k}EU\psi _h(N,v,L,P). \end{aligned}$$

(3)

If $P=P^N$, then, by efficiency (E), we have

$$\begin{aligned} \sum _{h\in N}f_h(N,v,L,P)=v(N)=\sum _{h\in N}EU\psi _h(N,v,L,P). \end{aligned}$$

If $P\ne P^N$, we prove that the equality (3) holds by contradiction. Suppose that $f\ne$EU$\psi$. Then there must exist a $(N,v,L,P)\in {\mathcal {G}}_{CG}\setminus {\mathcal {G}}_{CG}^{C}$ such that $f(N,v,L,P)\ne$EU$\psi (N,v,L,P)$. Let L be a maximal graph such that there exists $f_i(N,v,L,P)\ne$EU$\psi _i(N,v,L,P)$ for some $i\in N$. Concretely, there exists $i\in C_i\in C(N,L)$ such that $f_i\ne$EU$\psi _i$.

Since $|C(N,L)|\ge 2$ and $|P|\ge 2$, there exist $x,y\in N$ such that x and y are neither in the same component nor in the same priori union. For such a pair x, y, we assume that $x\in P_k\cap C$ and $y\in P_s\cap C^\prime$ where $C\ne C^\prime$, $C,C^\prime \in C(N,L)$ and $s\ne k$, $s,k\in M$.

By the maximality of graph L and link-fairness in the quotient (LFQ), we have

$$\begin{aligned}&\sum _{h\in P_k}f_h(N,v,L,P)-\sum _{h\in P_s}f_h(N,v,L,P)\\&=\sum _{h\in P_k}f_h(N,v,L\cup \{xy\},P)-\sum _{h\in P_s}f_h(N,v,L\cup \{xy\},P)\\&=\sum _{h\in P_k}EU\psi _h(N,v,L\cup \{xy\},P)-\sum _{h\in P_s}EU\psi _h(N,v,L\cup \{xy\},P)\\&=\sum _{h\in P_k}EU\psi _h(N,v,L,P)-\sum _{h\in P_s}EU\psi _h(N,v,L,P). \end{aligned}$$

For any $k,s\in M$, the last expression can be rewritten as

$$\begin{aligned} \sum _{h\in P_k}f_h(N,v,L,P)&-\sum _{h\in P_k}EU\psi _h(N,v,L,P)\nonumber \\&=\sum _{h\in P_s}f_h(N,v,L,P)-\sum _{h\in P_s}EU\psi _h(N,v,L,P). \end{aligned}$$

Next, fix k and sum up over all $s\in M$. By efficiency (E), we obtain

$$\begin{aligned}&|M|\Big (\sum _{h\in P_k}f_h(N,v,L,P)-\sum _{h\in P_k}EU\psi _h(N,v,L,P)\Big )\\&=\sum _{s\in M}\sum _{h\in P_s}f_h(N,v,L,P) -\sum _{s\in M}\sum _{h\in P_s}EU\psi _h(N,v,L,P)\\&=v(N)-v(N)=0. \end{aligned}$$

Hence, for any $k\in M$, we have that

$$\begin{aligned} \sum _{h\in P_k}f_h(N,v,L,P)=\sum _{h\in P_k}EU\psi _h(N,v,L,P). \end{aligned}$$

The remainder of the proof is similar to the proof of uniqueness in Theorem 3.1. By induction on |P|, we deduce that $f_i(N,v,L,P)=$EU$\psi _i(N,v,L,P)$ for all $i\in N$. $\square$

Now we shall give an alternative characterization of the EU$\psi$ value. For this purpose, we need to generalize the axioms in Shan et al. (2019) to the setting of games with coalition and graph structures.

Proportional fair distribution of surplus between unions (PFDSU). There exists a constant c such that for each $i\in P_k\in P$ with $i\in C_i\in C(N,L)$,

$$\begin{aligned} f_i(N,v,L,P)-f_i(C_i,v_{C_i},L_{C_i},P_{C_i})=\frac{1}{|P_k|}c. \end{aligned}$$

Coherence with the Owen graph value for connected graphs (COC). For any $(N,v,L,P)\in {\mathcal {G}}_{CG}^{C}$, it holds that $f(N,v,L,P)=\psi (N,v,L,P)$.

Coherence with the Owen graph value for connected graphs requires that allocation rule f(N, v, L, P) equals the Owen graph value $\psi (N,v,L,P)$ for any $(N,v,L,P)\in {\mathcal {G}}_{CG}^{C}$. Specially, $\psi (N,v,L,P^n)$ $=\mu (N,v,L)$ when $(N,v,L,P^n)\in {\mathcal {G}}_{CG}$. Hence, coherence with the Owen graph value for connected graphs (COC) implies coherence with the Myerson value for connected graphs (CMC).

By E, COC and PFDSU, we give another characterization of the EU$\psi$ value. We omit its proof since it follows along the same lines as the one in Shan et al. (2019).

Theorem 3.3

The efficient partition surplus Owen graph value (EU$\psi$) on ${\mathcal {G}}_{CG}$ is the unique value satisfying efficiency (E), coherence with the Owen graph value for connected graphs (COC) and proportional fair distribution of surplus between unions (PFDSU).

3.2 Independence of the axioms in axiomatizations

In this subsection we show that the independence of the axioms invoked in Theorems 3.1, 3.2 and 3.3.

• The null value $\phi ^1(N,v,L,P)=0$ satisfies CLFQ, LFQ and BCU, but not E.

• The value $\phi ^2(N,v,L,P)=\frac{v(N)}{|N|}$ satisfies E, LFQ and BCU, but not CLFQ.

• For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $i\in P_k\in P$, the value

  $$\begin{aligned} \phi _i^3(N,v,L,P)=\left\{ \begin{array}{lcl} \psi _i(N,v,L,P)+\frac{v(N)-v^L(N)}{3|P||P_k\cap {\mathscr {N}}(N,v)|}, &{}i\in {\mathscr {N}}(N,v)\\[2mm] \psi _i(N,v,L,P)+\frac{2\big (v(N)-v^L(N)\big )}{3|P||P_k\setminus {\mathscr {N}}(N,v)|}, &{}i\notin {\mathscr {N}}(N,v)\end{array}\right. \end{aligned}$$

  where ${\mathscr {N}}(N,v)=\{i\in N\,|\,v(S\cup i)=v(S), S\subseteq N\setminus i\}$ represents the set of null players in (N, v). It is easily verified that $\phi _i^3$ satisfies E, LFQ and CLFQ, but not BCU.

• For any $(N,v,L,P)\in {\mathcal {G}}_{CG}$ and $i\in N$, the value $\phi _i^4(N,v,L,P)=\psi _i(N,v,L,P)+\frac{v(N)-v^L(N)}{|N|}$ satisfies E, CLFQ and BCU, but not LFQ.

• $\phi _i^4$ satisfies E and COC, but not PFDSU.

• The value $\phi _i^{5}(N,v,L,P)=\psi _i(N,v,L,P)+\frac{v(N)-v^L(N)}{2|P||P_k|}$ satisfies COC and PFDSU, but not E.

• The value $\phi _i^{6}(N,v,L,P)=\frac{v(C_i)}{|C_i|}+\frac{v(N)-v^L(N)}{|P||P_k|}$ satisfies E and PFDSU, but not COC.

3.3 An example

To illustrate the efficient partition surplus Owen graph value, we give an example of a fund allocation problem as described in the introduction.

Example 3.1

In a fund allocation problem, suppose that the budget of the fund is 90 and there are five researchers, say 1, 2, 3, 4, 5, from three different disciplines, named $P_1, P_2$ and $P_3$, where 1 is in $P_1$, 2 and 3 in $P_2$, 4 and 5 in $P_3$. An individual proposal just gives access to the fund, but does not secure any amount of money. In order to stimulate interdisciplinary cooperation, a joint application of researchers from different disciplines can receive higher research grand. Two researchers in the same discipline can secure themselves a grant of 5 when writing a proposal together, while two researchers in the different disciplines a grant of 20, three researchers a grant of 40, four researchers a grant of 60. However, researchers 1 and 2, 3 and 4, 4 and 5 are able to directly communicate, thus 1 and 2 can negotiate with each other for a proposal, while 3, 4 and 5 can negotiate with each other for a proposal.

This situation can be described as a TU-game with coalition and graph structures (N, v, L, C), where $N=\{1,2,3,4,5\}$, $L=\{12,34,45\}$, $P=\{P_1,P_2,P_3\}=\{\{1\},\{2,3\},\{4,5\}\}$ and v is defined by

$$\begin{aligned} v(S)=\left\{ \begin{array}{rcl} 0, &{} &{}|S|=1\; \\ 5, &{} &{}\text {if } S=P_2 \text { or } P_3, \\ 20, &{} &{}\text {if } S=2 \text { and } S\ne P_2, P_3,\\ 40, &{} &{}|S|=3, \\ 60, &{} &{}|S|=4, \\ 90, &{} &{}S=N. \end{array}\right. \end{aligned}$$

Next we provide different schemes to allocate the fund by using the Myerson value $\mu (N,v,L)$, the Owen value Ow(N, v, P), the Owen graph value $\psi (N,v,L,P)$ and the efficient partition surplus Owen graph value EU$\psi (N,v,L,P)$, which are shown in Table 1.

Table 1 The four values for the games

In Table 1,

• (i) The Owen value Ow assigns a higher funding 21.667 to researcher 1 and the same funding 17.083 to the other researchers. This shows that the coalition structure affects the allocation of funds and plays a protective role for priori union $P_1$ which contains only one researcher.

• (ii) When the communication graph structure is considered, the Myerson value $\mu$ and Owen graph value $\psi$ both give a low funding 10 to researchers 1 and 2, but they all assign high funding 17.5 and 16.25 to researcher 4, respectively. This illustrates the important bargaining power of 4 in the graph game. But, note that $\psi (N,v,L,P)$ gives a slightly higher funding 17.5 to researcher 3 than $\mu _3(N,v,L)=15$, this shows that interdisciplinary cooperation increases the bargaining power of researcher 3.

• (iii) The total funding for $\mu$ and $\psi$ is $v^L(N)=60$ not $v(N)=90$.

• (iv) The efficient partition surplus Owen graph value EU$\psi$ distributes the budget 90 to all researchers.

4 Concluding remarks

In this paper we introduce a new efficient extension of the Owen graph value and provide three axiomatizations of the value.

Table 2 The characterizations of the four values: Ow, $\mu$, $\psi$ and EU$\psi$

We give an overview of the values that appeared in this paper.

• (1) The Owen value

  $$\begin{aligned} Ow(N,v,P):\,(N,v,P)\rightarrow (M,v^P)\rightarrow (P_k,v^{P_k})\rightarrow Sh(P_k,v^{P_k}) \end{aligned}$$

  where $(P_k,v^{P_k})$ is the internal TU-game defined via the quotient game, $v^{P_k}(S)=Sh_{P_k}(M\setminus {P_k\cup S},v^{q}_{-P_k,+S})$ with $v^{q}_{-P_k,+S}$ being the quotient game in which $P_k$ is replaced by S.

• (2) The Myerson value $\mu (N,v,L):\,(N,v,L)\rightarrow (N,v^L)\rightarrow Sh(N,v^L)$, where $v^L$ is the graph-restricted game.

• (3) The Owen graph value $\psi (N,v,L,P):\,(N,v,L,P)\rightarrow (N,v^L,P)\rightarrow Ow(N,v^L,P)$.

• (4) The efficient partition surplus Owen graph value

  $$\begin{aligned} \mathrm{EU}\psi (N,v,L,P): \psi (N,v,L,P)+\frac{v(N)-v^L(N)}{|P||P_k|}\rightarrow \mathrm{EU}\psi (N,v,L,P). \end{aligned}$$

Actually, the distributions of the surplus $v(N)-v^L(N)$ can be modified in different fashions. For instance, Shan et al. (2020) distribute the surplus by $(v(N)-v^L(N))/n$ as in van den Brink et al. (2012). Furthermore, we can also obtain the other efficient extensions of the Owen graph value by replacing $(v(N)-v^L(N))/|P||P_k|$ in EU$\psi$ by the distribution ways of the surplus $v(N)-v^L(N)$ developed in Casajus (2007); Shan et al. (2019). These efficient Owen graph values can be similarly characterized by modifying the axioms for the EU$\psi$ value.

Finally, we summarize the axiomatizations of the Owen value Ow, the Myerson value $\mu$, the Owen graph value $\psi$ and the efficient partition surplus Owen graph value EU$\psi$ in Table 2. In Table 2, ‘+’ represents that the value satisfies the axiom, ‘–’ has the converse meaning and ‘$\oplus$’ symbols indicate the sets of axioms used for characterizations of the value. The superscripts 1, 2, 3 represent three different characterizations of the values, respectively.