You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Quasi-Owen Value for Games on Augmenting Systems with a Coalition Structure

Article type: Research Article

Authors: Tang, Jie1 | Li, Zijun2 | Meng, Fanyong1; ∗

Affiliations: [1] The Research Institute for Risk Governance and Emergency Decision-Making, School of Management Science and Engineering, Nanjing University of Information Science & Technology, Nanjing 210044, China | [2] School of Business, Central South University, Changsha 410083, China

Correspondence: [∗] Corresponding author.

Keywords: cooperative game with a coalition structure, augmenting system, axiomatic system, quasi-Owen value

DOI: 10.15388/23-INFOR524

Journal: Informatica, vol. 34, no. 3, pp. 635-663, 2023

Received February 2023
|
Accepted August 2023
|
Published: 2023
Get PDF open access

Abstract

This paper focuses on games on augmenting systems with a coalition structure that can be seen as an extension of games with a coalition structure and games on augmenting systems. Considering the player payoffs, the quasi-Owen value is defined. To show the rationality of this payoff index, five representative axiomatic systems are established. The population monotonic allocation scheme (PMAS) and the core are introduced. Moreover, the relationships between the PMAS and quasi-Owen value as well as the core and quasi-Owen value are discussed. Finally, an illustrative example is given to show the concrete application of the new payoff indices.

1Introduction

In some cooperative situations, the players join in coalitions that form a partition or coalitional structure of the set of players to get more payoffs or to gain the competitive advantage. Aumann and Dreze (1974) first established a model of games with a coalition structure, where the coalitions are independent with each other. Different from the cooperative model in reference (Aumann and Dreze, 1974; Owen, 1977) introduced games with a coalitional structure where the probability of cooperation among coalitions is considered and defined the Owen value for this type of games, which is an extension of the Shapley value (Peleg, 1986). Following the idea of the Banzhaf value, Owen (1978) further proposed the Banzhaf-Owen value for games with a coalitional structure. Later, Alonso-Meijde and Fiestras-Janeiro (2002) noted that the Banzhaf-Owen value dissatisfies the symmetry in quotient games and gave another solution concept for games with a coalition structure, which is known as the symmetric Banzhaf value. Meanwhile, the axiomatic systems of the Owen value are studied in references (Hart and Kurz, 1983; Peleg, 1989; Hamiache, 1999; Khmelnitskaya and Yanovskaya, 2007; Albizuri, 2008; Lorenzo-Freire, 2019; Hu, 2021), and the axiomatic characterizations of the Banzhaf-Owen coalition value are discussed in the literature (Amer et al., 2002; Alonso-Meijide et al., 2007; Lorenzo-Freire, 2017).

Different from games with a coalitional structure (Aumann and Dreze, 1974; Owen, 1977), due to political, economic and/or other reasons, not all coalitions can be formed in some cooperation. People usually call such games as games under precedence constraints. Myerson (1977) first considered this situation and introduced games with communication structures using graph theory. Then, the Shapley value for this type of games is researched. Faigle and Kern (1992) discussed a special type of games under precedence constraints that satisfies the offered order relationship and closes under union and intersection and discussed the axiomatic system of the given Shapley value using hierarchical strength. Following the work of Edelman and Jamison (1985), Bilbao (1998) introduced games on convex geometries. Further, Bilbao (1998) and Bilbao and Edelman (2000) studied the characterizations of the Shapley value for games on convex geometries using chain axiom and hierarchical strength, respectively. Bilbao et al. (1998, 1999) researched the Banzhaf value and the core of games on convex geometries. Later, Bilbao et al. (2001, 2002) discussed another special kind of games under precedence constraints, which is named as games on matroids. Considering the player payoffs, the authors researched the Shapley value for two cases of games on matroids. Algaba et al. (2003) presented games on antimatroids and researched the Shapley value for this kind of games. Recently, Bilbao (2003) proposed the concept of games on augmenting systems and discussed the relationship between augmenting system, antimatroid and convex geometry. Then, the author introduced the Shapley value and the Banzhaf value for games on augmenting systems. Further, Bilbao and Ordonez (2009) researched two axiomatic systems of the Shapley value for games on augmenting systems using hierarchical strength and chain axiom. Algaba et al. (2010) proposed the α value for games on augmenting systems by generalizing the Myerson value for graph games and the Shapley value for games with permission structures. Wang et al. (2022) provided a new axiomatization of the α value for games on augmenting systems in view of marginality. In addition, Meng et al. (2023) studied the profit allocation on a four-echelon supply chain from the perspective of cooperative games on augmenting systems.

In general, games with a coalition structure are formed by the players’ internal factor for obtaining more payoffs, while games under precedence constraints are due to the external factor as listed above. Considering these two aspects simultaneously, Meng and Zhang (2012) introduced games on convex geometries with a coalition structure, where all feasible coalitions in each union and in the coalition structure both form a convex geometry. After that, Meng and Zhang (2012) and Meng et al. (2015) studied three payoff indices for this type of cooperative games. However, as Meng et al. (2015) noted the application of convex geometries has limitations. Recently, Meng et al. (2016) introduced games on augmenting systems with a coalition structure, where all subsets of the coalition structure and those of each union both form an augmenting system. Then, the authors defined the augmenting symmetric Banzhaf coalitional value that is used as the payoff index of the players. However, this payoff index does not satisfy the efficiency, which is one of the most important properties of indices. To address this issue, this paper defines another payoff index for games on augmenting systems with a coalition structure: the quasi-Owen value, which can be seen as an extension of the Owen value (Owen, 1977). Then, we build five axiomatic systems to show its rationality. The first two axiomatic systems are based on linearity, the third one uses strong monotonicity, the fourth one employs the potential function, and the last one adopts the balanced contributions. Then, the concepts of the population monotonic allocation scheme (PMAS) and the core of games on augmenting systems with a coalition structure are introduced. Further, the relationship between the quasi-Owen value and the core is discussed, and the sufficient conditions for the quasi-Owen value to be a PMAS are provided.

The rest of this paper is organized as follows: In Section 2, some notations and basic definitions that will be used in the following sections are reviewed. In Section 3, the concept of games on augmenting systems with a coalition structure is introduced, and the quasi-Owen value is defined. Meanwhile, five axiomatic systems are built, each of which can be used to prove the existence and uniqueness of the quasi-Owen value. In Section 4, the core and the PMAS for games on augmenting systems with a coalition structure are introduced, and the relationships between them and the quasi-Owen value are studied. In Section 5, a numerical example is provided to concretely illustrate the application of the new indices. The conclusion is made in the last section.

2Some Basic Concepts

Let N={1,2,…,n} be the finite player set. The cardinality of any coalition S⊆N is denoted by the corresponding lower case s. As we know, the coalitional values of a cooperative game can be seen as a fuzzy measure, and the unique proofs of some payoff functions are based on the Möbius transformation. Thus, let us first review the expression of fuzzy measures using the Möbius transformation.

Let f:{0,1}n→ℜ be a pseudo-Boolean function. Grabisch (1997) noted that any fuzzy measure μ can be seen as a particular case of the pseudo-Boolean function and put under a multilinear polynomial with n variables:

(1)
μ(A)=∑T⊆N[aT∏i∈Tyi],∀A⊆N,
where aT∈ℜ, y=(y1,y2,…,yn)∈{0,1}n, and yi=1 if and only if i∈A.

The set of coefficients aT with T⊆N corresponds to the Möbius transformation, denoted by aT=∑S⊆T(−1)|T∖S|μ(S). Because the transformation is inversible, μ can be recovered from aT by μ(A)=∑B⊆AaB.

2.1Games with a Coalition Structure

For the finite set N={1,2,…,n}, a coalition structure Γ on N is a partition of N, i.e. Γ={B1,B2,…,Bm} is a coalition structure if it satisfies ⋃1⩽h⩽mBh=N and Bh∩Bl=∅ for all h,l∈M={1,2,…,m} with h≠l, denoted by (N,Γ). We also assume Bk≠∅ for all k∈M. Each Bk∈Γ is called a “union”. There are two trivial coalition structures: Γ={N} and Γ={{1},{2},…,{n}}, where each union is a singleton.

Let L(N,Γ)={S|S=⋃l∈R⊆M∖{k}Bl∪T,∀T⊆Bk,∀k∈M}. A game with a coalition structure is a set function v:L(N,Γ)→ℜ+ such that v(∅)=0. By G(N,Γ), we denote the set of all games with a coalition structure. The restriction of Γ to S is Γ|S={T∈L(N,Γ):T⊆S} for any S∈L(N,Γ). In order to denote simply, we will omit braces for singleton, e.g. writing ∅, i, k instead of {∅}, {i} and {k} for any {i}⊆N and any {k}⊆M .

Let v∈G(N,Γ), Owen (1977) defined the following Owen value:

(2)
ψi(N,v,Γ)=∑R⊆M∖k∑i∈S⊆Bkr!(m−r−1)!m!(s−1)!(bk−s)!bk!(v(Q∪S)−v((Q∪S)∖i)),∀i∈N,
where Q=⋃l∈RBl, m and r denote the cardinalities of M and R, respectively.
Definition 1

Definition 1(Alonso-Meijde and Fiestras-Janeiro, 2002).

Let v∈G(N,Γ), if vB(R)=v(⋃r∈RBr) for any R⊆M, then vB is said to be a quotient game on (N,Γ), where Γ and M as given above, denoted by (M,vB).

2.2Games on Augmenting Systems

A set system on N is a pair of (N,F), where F⊆2N is a family of subsets.

Definition 2

Definition 2(Bilbao, 2003).

An augmenting system is a set system (N,F) with the following properties:

  • A1: ∅∈F;

  • A2: If S,T∈F with S∩T≠∅, then S∪T∈F;

  • A3: If S,T∈F with S⊆T then there is i∈T∖S such that S∪i∈F.

It is noteworthy that when A2 is defined as: if S,T∈F, then S∩T∈F. (N,F) is a convex geometry system (Bilbao, 2003). Further, when we delete the condition S∩T≠∅ in A2, then (N,F) is an antimatroid system (Bilbao, 2003).

Because the power set of N is an augmenting system, traditional games are also games on augmenting systems. When N=⋃S∈FS, then the augmenting system (N,F) is normal. Bilbao and Ordonez (2009) introduced the following concepts:

A compatible ordering of an augmenting system (N,F), as the total ordering of N, is given by i1<i2<⋯<in such that {i1,i2,…,ij}∈F for all j=1,2,…,n. A compatible ordering of (N,F) corresponds to a maximal chain in F. The set of all maximal chains in F is denoted by Ch(F). Given an element i∈N and a compatible ordering C∈Ch(F), let C(i) be the maximal chain C with i being the last element. For a set S∈F, let S∗={i∈N∖S:S∪i∈F}. The restriction of F to S is F|S={T∈F:T⊆S} for any S∈F.

Similar to Faigle and Kern (1992), Bilbao and Ordonez (2009) introduced the Shapley value for games on augmenting systems as:

(3)
ϕi(N,v,F)=∑{S∈F:i∈S∗}c(S)c(S∪i,N)c(N)(v(S∪i)−v(S)),∀i∈N,
where the set function v:(N,F)→ℜ+ is a game on augmenting systems such that v(∅)=0, c(N)=|Ch(F)| is the total number of maximal chains in F, c(S)=c(∅,S) and c(N)=c(∅,N) are the numbers of maximal chains from ∅ to S and from ∅ to N, respectively, and c(S∪i,N) is the number of maximal chains from S∪i to N.

3Games on Augmenting Systems with a Coalition Structure

In this section, we discuss cooperative games on augmenting systems with a coalition structure, which can be seen as an extension of games with a coalition structure (Owen, 1977, 1978) and games on convex geometries with a coalition structure (Meng and Zhang, 2012; Meng et al., 2015).

3.1The Concept of Games on Augmenting Systems with a Coalition Structure

Similar to the concept of augmenting system on N, Meng et al. (2016) gave the concept of augmenting systems on M={1,2,…,m} for Γ={B1,B2,…,Bm}, namely, an augmenting system on M is a set system (M,FM) with the following properties:

  • M1: ∅∈FM;

  • M2: If K,H∈FM with K∩H≠∅, then K∪H∈FM;

  • M3: If K,H∈FM with K⊆H, then there is l∈H∖K, such that K∪l∈FM.

The number of maximal chains from R to K is denoted by c(R,K), and c(R) is the number of maximal chains from ∅ to R.

From Definition 2, one can check when the domain of N is restricted to Bk, we get an augmenting system (Bk,FBk), where FBk⊆2Bk is a family of subsets that satisfies the conditions given in Definition 2. Augmenting systems with a coalition structure mean that the subsets of M={1,2,…,m} and those of each Bk∈Γ (k∈M) form an augmenting system, respectively, denoted by (N,Γ,F). Let

(4)
L(N,Γ,F)={S|S=⋃l∈R∈FM,k∈R∗Bl∪T,∀T∈FBk,∀k∈M}
with R∗={k∈M∖R:R∪k∈FM}, which denotes the set of formed coalitions.
Definition 3.

A game on augmenting system with a coalition structure is a set function v:L(N,Γ,F)→ℜ+ such that v(∅)=0.

Let G(N,Γ,F) be the set of all games on augmenting systems with a coalition structure. Without special explanation, for any (N,Γ,F), we always assume Bk∈FBk for any k∈M and M∈FM, namely, the augment systems on each union and on the coalition structure are normal.

For (N,Γ,F) with N∈F, following the works of Faigle and Kern (1992) and Bilbao and Ordonez (2009), Meng et al. (2016) defined the hierarchical strength hSBk(i) of i∈S for the coalition S∈FBk as follows:

(5)
hSBk(i)=|{C∈Ch(FBk):S⊆C(i)}|c(Bk),
where Ch(FBk) is the set of all maximal chains in FBk, c(Bk)=|Ch(FBk)| is the number of maximal chains in FBk, and hSBk(i) is the average number of maximal chains in which the player i∈S is the last member of S in the chain (Bilbao and Ordonez, 2009).

Similarly, we define the hierarchical strength hRM(k) of k∈R for the coalition R∈FM as follows:

(6)
hRM(k)=|{C∈Ch(FM):R⊆C(k)}|c(M),
where C(k)={kis the last element inR∈FM}, Ch(FM) is the set of all maximal chains in FM, and c(M)=|Ch(FM)| is the total number of maximal chains in FM.

Example 1.

Let N={1,2,3,4,5}, and Γ={B1,B2} be a coalition structure on N, where B1={1,2,3} and B2={4,5}. If FB1={∅,{1},{3},{1,2},{2,3},B1}, FB2={∅,{4},{5},B2} and FM={∅,{2},M}, then it is an augmenting system with a coalition structure, where

L(N,Γ,F)={∅,{4},{5},{4,5},{1,4,5},{3,4,5},{1,2,4,5},{2,3,4,5},{1,2,3,4,5}}.
Then, we have hSB1(3)=1/2 for S={3}, and we get hRM(2)=1 for R={2}.

Because {1,3}∉FB1, one can check that FB1 is not an antimatroid. Further, FB1 is not a convex geometry for {1,2}∩{2,3}∉FB1.

Definition 4.

Let v∈G(N,Γ,F). T∈L(N,Γ,F) is said to be a carrier if v(S∩T)=v(S) for any S∈L(N,Γ,F).

Because v is defined on L(N,Γ,F), the value v(S∩T) can be any real number for S∩T∉L(N,Γ,F). In this case, we assume that v(S∩T)=v(S) for defining the concept of carrier. For instance, in Example 1, if T={1,2} and S={2,3}, then S∩T={2}∉FB1∈L(N,Γ,F). In this case, we consider v(2)=v(2,3), where v(2) is not real existence for {2} being a virtual coalition. Note that when in the above case, we adopt this process.

3.2The Quasi-Owen Value

Similar to Owen (1977) and Bilbao and Ordonez (2009), the quasi-Owen value for games on augmenting systems with a coalition structure is expressed as:

(7)
φi(N,Γ,v,F)=∑{R∈FM:k∈R∗}∑{S∈FBk:i∈S∗}c(R)c(R∪k,M)c(M)c(S)c(S∪i,Bk)c(Bk)×(v(Q∪S∪i)−v(Q∪S)),∀i∈N,
where R∗={k∈M∖R:R∪k∈FM}, S∗={i∈Bk∖S:S∪i∈FBk} and Q=⋃l∈RBl.

From R∈FM, we know that Q=⋃l∈RBl can be formed. When there is only one union in M, then the quasi-Owen value degenerates to the Shapley value for games on augmenting systems. When we restrict the domain of (N,Γ,F) in the setting of (N,Γ), then the quasi-Owen value degenerates to the Owen value. In summary, the quasi-Owen value is an extension of the Owen value, which is used for games on augmenting systems with a coalition structure.

For any T∈L(N,Γ,F)∖∅, we define the unanimity game uT as

uT(S)=1,T⊆S∈L(N,Γ,F),0,otherwise.

Lemma 1

Lemma 1(Meng et al., 2016).

Let v∈G(N,Γ,F), then there is a unique set of coefficients {cT:∅≠T∈L(N,Γ,F)} such that v=∑∅≠T∈L(N,Γ,F)cTuT. Moreover,

(8)
cT=∑{H∈FM:H⊆R}(−1)r−h(∑{D∈FBk:D⊆A}(−1)a−dv(Q∪D)),
where T=A⋃l∈R∈FM,k∈R∗Bl, A∈FBk∖∅ and Q=⋃l∈HBl, r and h denote the cardinalities of R and H, respectively.

Let f be a solution on G(N,Γ,F). To show the axiomatic systems of the augmenting symmetric Banzhaf coalitional value, Meng et al. (2016) introduced the following two properties:

  • • Linearity(L). Let v1,v2∈G(N,Γ,F) and α,β∈ℜ, then

    (9)
    f(N,Γ,αv1+βv2,F)=αf(N,Γ,v1,F)+βf(N,Γ,v2,F).

  • • Hierarchical strength in coalitions (HSC). Let v∈G(N,Γ,F). For any T∈L(N,Γ,F), without loss of generality, suppose T=S⋃l∈R∈FM,k∈R∗Bl such that S∈FBk∖∅. For all i,j∈S,

    (10)
    hSBk(j)fi(N,Γ,uT,F)=hSBk(i)fj(N,Γ,uT,F).
    Similar to the axiomatizations of the Owen value (Owen, 1977) and the Shapley value for games on augmenting systems (Bilbao and Ordonez, 2009), we introduce the following two properties:

  • • Efficiency (EFF-1). Let v∈G(N,Γ,F). If T is a carrier, then v(T)=∑i∈Tfi(N,Γ,v,F).

  • • Hierarchical strength on unions (HSU). Let v∈G(N,Γ,F). For any H∈FM and all k,p∈H,

    (11)
    hHM(k)∑j∈Bpfj(N,Γ,uT,F)=hHM(p)∑i∈Bkfi(N,Γ,uT,F),
    where T∈L(N,Γ,F) with ⋃l∈HBl∈T.

Remark 1.

If there is only one coalition in Γ, then hierarchical strength in coalitions degenerates to hierarchical strength for games on augmenting system. If all subsets of M and those of each Bk∈Γ are both feasible, then hierarchical strength in coalitions and hierarchical strength on unions degenerate to symmetry in the unions and symmetry in the quotient games for games with a coalition structure, respectively. It is noteworthy that hierarchical strength on unions defined in Meng et al. (2016) is different from the above one.

Next, we apply the above listed axioms to show the existence and uniqueness of the quasi-Owen value. First, let us consider the following lemma:

Lemma 2.

Let v∈G(N,Γ,F). Then, the quasi-Owen value defined on the unanimity game uT can be expressed as:

(12)
φi(N,Γ,uT,F)=hRM(k)hSBk(i),ifi∈S,0,otherwise,
where T=S⋃l∈R∈FM,k∈R∗Bl and S∈FBk∖∅.

Proof.

From the expression of the quasi-Owen value, we have

(13)
φi(N,Γ,uT,F)=1c(M)∑H∈Ch(FM)(1c(Bk)∑C∈Ch(FBk)(uT(Q∪C(i))−uT((Q∪C(i))∖i))).
Case (1): If T⊄Q∪C(i), then uT(Q∪C(i))−uT((Q∪C(i))∖i)=0.

Case (2): If T⊆Q∪C(i) and i∉S, then T⊆Q∪C(i) implies T⊆(Q∪C(i))∖i, and uT(Q∪C(i))−uT((Q∪C(i))∖i)=0.

Case (3): If T⊆Q∪C(i) and i∈S, we derive uT(Q∪C(i))−uT((Q∪C(i))∖i)=1. Thus, for every chain C∈Ch(FBk) and H∈Ch(FM), we obtain

(14)
(uT)Bk(C(i))−(uT)Bk(C(i)∖i)=uS(C(i))−uS(C(i)∖i)=1
and
(15)
uTB(H(k))−uTB(H(k)∖k)=uR′(H(k))−uR′(H(k)∖k)=1,
where S⊆C(i), R′⊆H(k), R′=R∪k and uR′(H)=1,R′⊆H,0,otherwise.

Thus,

(16)
uT(Q∪C(i))−uT((Q∪C(i))∖i)=(uS(C(i))−uS(C(i)∖i))(uR′(H(k))−uR′(H(k)∖k)).
We get φi(N,Γ,uT,F)=hRM(k)hSBk(i). The result is obtained.  □

Theorem 1.

There is a unique solution f defined on G(N,Γ,F) that satisfies L, EFF-1, HSC and HSU.

Proof.

Existence. From Eq. (7), we know that L holds.

From Definition 4 and Eq. (7), we have φi(N,v,Γ,F)=0 for any i∈N∖T. When i∈T, let vQ(S)=v(Q∪S)−v(Q) for any S∈FBk, then

∑i∈Tφi(N,v,Γ,F)=∑i∈Nφi(N,v,Γ,F)=∑i∈N∑{R∈FM:k∈R∗}∑{S∈FBk:i∈S∗∧i∈Bk}c(R)c(R∪k,M)c(M)c(S)c(S∪i,Bk)c(Bk)×(v(Q∪S∪i)−v(Q∪S))=∑i∈N∑{R∈FM:k∈R∗}∑{S∈FBk:i∈S∗∧i∈Bk}c(R)c(R∪k,M)c(M)c(S)c(S∪i,Bk)c(Bk)×(vQ(S∪i)−vQ(S))=∑k∈M∑{R∈FM:k∈R∗}c(R)c(R∪k,M)c(M)∑i∈Bk∑{S∈FBk:i∈S∗}c(S)c(S∪i,Bk)c(Bk)×(vQ(S∪i)−vQ(S))=∑k∈M∑{R∈FM:k∈R∗}c(R)c(R∪k,M)c(M)vQ(Bk)=∑k∈M∑{R∈FM:k∈R∗}c(R)c(R∪k,M)c(M)(vB(R∪k)−vB(R))=vB(M)=v(N)=v(T).
Thus, EFF-1 holds.

From Lemma 2, we get HSC.

Further, according to Lemma 2 we have

(17)
φi(N,Γ,uT,F)=hHM(k)hSBk(i)
and
(18)
φj(N,Γ,uT,F)=hHM(p)hEBP(j).
From EFF-1, we obtain
(19)
∑i∈Bkφi(N,Γ,uT,F)=∑i∈BkhHM(k)hSBk(i)=hHM(k)
and
(20)
∑j∈Bpφj(N,Γ,uT,F)=∑j∈BphHM(p)hEBP(j)=hHM(p).
Thus, HSU holds.

Uniqueness. From Lemma 1 and L, we only need to prove the uniqueness of Eq. (7) on uT for any T∈L(N,Γ,F) with T≠∅. Let M′={k∈M:Bk∩T≠∅} and Bk′=Bk∩T for any k∈M, define the unanimity quotient game uTB on Γ as follows:

(21)
uTB(R)=1,M′⊆R,0,otherwise,
where R⊆M.

Let f be a solution on (N,Γ,uT,F) that satisfies the above axioms. From EFF-1 and HSU, we have

(22)
∑i∈Bkfi(N,uT,Γ,F)=0,k∉M′,hM′M(k),k∈M′.
For any k∈M′, from HSC we get
(23)
hBk′Bk(j)fi(N,Γ,uT,F)=hBk′Bk(i)fj(N,Γ,uT,F).
From ∑i∈Bk′hBk′Bk(i)=1, we derive
(24)
fi(N,Γ,uT,F)=0,i∈Bk∖Bk′,hM′M(k)hBk′Bk(i),i∈Bk′.
According to Lemma 2, we know that f and φ coincide on uT.  □

Similar to Bilbao and Ordonez (2009), we define the identify game for G(N,Γ,F) to research another axiomatization of the quasi-Shapley value. For any S∈L(N,Γ,F)∖∅, the identify game δS:L(N,Γ,F)→ℜ is defined as:

(25)
δS(T)=1,S=T,0,otherwise.
Using the identify game, we offer the following axiom which is an extension of Chain axiom for games on augmenting systems (Bilbao and Ordonez, 2009).

  • • Chain axiom in coalitions (CAC). Let v∈G(N,Γ,F). For any T∈L(N,Γ,F), without loss of generality, suppose that T=S⋃l∈R∈FM,k∈R∗Bl, where S∈FBk∖∅. Then, for all i,j∈exS, we have

(26)
c(S∖i)fj(N,Γ,δS,F)=c(S∖j)fi(N,Γ,δS,F).
From Eq. (7), one can easily check that the quasi-Owen value can be equivalently expressed as:
(27)
φi(N,Γ,v,F)=∑{R∈FM:k∈R∗}∑{S∈FBk:i∈exS∧i∈Bk}c(R)c(R∪k,M)c(M)c(S∖i)c(S,Bk)c(Bk)×(v(Q∪S)−v((Q∪S)∖i)).∀i∈N,
where exS={i∈S:S∖i∈FBk}.

Theorem 2.

There is a unique solution f defined on G(N,Γ,F) that satisfies L, EFF-1, CAC and HSU.

Proof.

From uS=∑S⊆TδT for any S∈L(N,Γ,F)∖∅ and Theorem 1, one can easily derive the conclusion.  □

Next, let us consider another axiomatization of the quasi-Owen value. Young (1985) proposed a characterization of the Shapley value using strong monotonicity. According to Young (1985), we propose strong monotonicity in the framework of games on augmenting systems with a coalition structure.

  • • Strong monotonicity (SM). Let v,w∈G(N,Γ,F). If v(S∪i)−v(S)⩾w(S∪i)−w(S) for any S∈L(N,Γ,F)∖∅ with i∈S∗, then fi(N,Γ,v,F)⩾fi(N,Γ,w,F).

Theorem 3.

There is a unique solution f defined on G(N,Γ,F) that satisfies EFF-1, HSC, HSU and SM.

Proof.

From Theorem 1 and Eq. (7), it is easy to conclude that φ satisfies these properties. Next, let us consider the uniqueness. From Lemma 1, for any v∈G(N,Γ,F) it can be uniquely expressed as:

(28)
v=∑∅≠T∈L(N,Γ,F)cTuT.
Let I be the minimum number of non-zero terms in some expression for v in (5). As in Young (1985), the theorem is proved using induction on I.

  • (I) If cT=0 for all T∈L(N,Γ,F)∖∅, it is easy to derive fi(N,Γ,v,F)=0 for any i∈N.

  • (II) If there is one T∈L(N,Γ,F)∖∅ such that cT≠0, we get v=cTuT. From EFF-1, HSC and HSU, we derive

    (29)
    fi(N,Γ,cTuT,F)=0,i∈Bk∖Bk′,cThM′M(k)hBk′Bk(i),i∈Bk′,
    where M′ and B′ as shown in Theorem 1.

  • (III) Assume that f is unique whenever the index of v is at most I. Let v have the index I+1 with the following expression:

    (30)
    v=∑r=1I+1cTruTr,
    where Tr∈L(N,Γ,F)∖∅ such that cTr≠0.

Let T=⋂r=1I+1Tr, for any i∈N∖T we construct the game

(31)
w=∑r:(Tr)i≠0cTruTr.
Then, the index of w is at most I, Because v(S∪i)−v(S)=w(S∪i)−w(S) for all S∈L(N,Γ,F) with i∈S∗ and i∈N∖T. According to induction and SM, we have
(32)
fi(N,Γ,w,F)=fi(N,Γ,v,F)=0,otherwise,∑r:(Tr)i≠0cTrhMTrM(k)hBTrkBk(i),i∈BTrk∗,
where MTr={k∈M:Bk∩TTr≠∅} and BTrk=Bk∩TTr for any k∈M.

On the other hand, for any i∈T, by EFF-1, HSC and HSU we obtain

(33)
fi(N,Γ,v,F)=∑r=1I+1cTrhMTrM(k)hBTrkBk(i).
The conclusion is obtained.  □

Next, we will give another two axiomatic systems to characterize the quasi-Owen value from the perspective of the potential function and balanced contributions, respectively.

Hart and Mas-Colell (1989) first introduced the concept of the potential function. Later, Winter (1992) extended the potential function to games with a coalition structure, by which an axiomatic system of the Owen value (Owen, 1977) was characterized. Now, we define the potential function for games on augmenting systems with a coalition structure to characterize the quasi-Owen value.

Definition 5.

Let v∈G(N,Γ,F). Given a function P:G(N,Γ,F)→ℜm, where Pk(∅,Γ,v,F)=0. Let Γ={B1,B2,…,Bm}. The marginal contribution of player i to G(N,Γ,v,F) is

(34)
DiP(N,Γ,v,F)=P(N,Γ,v,F)−P(N∖i,Γ|N∖i,v,F|N∖i),
P is said to be a potential function for the game G(N,Γ,v,F) if it satisfies
(35)
∑i∈BkDiP(N,Γ,v,F)=DkP(M,vB,FM)
for all k∈M, and
(36)
∑i∈NDiP(N,Γ,v,F)=v(N).
Using the potential function for games on augmenting systems with a coalition structure, we offer the following theorem for the quasi-Owen value.

Theorem 4.

There is a unique potential function P for the game G(N,Γ,v,F). Moreover, for any v∈G(N,Γ,F) and any i∈N, DiP(N,Γ,v,F)=φi(N,Γ,v,F), where φ is the quasi-Owen value.

Proof.

Existence. For any Bk∈Γ and any T∈L(N,Γ,F), let

(37)
dT(Bk)=cTm′bk′,Bk∩T≠∅,0,Bk∩T=∅,
where m′ and bk′ are the cardinalities of M′={k∈M:Bk∩T≠∅} and Bk′=Bk∩T, k∈M, respectively, and cT as shown in Eq. (28).

Let

P(N,Γ,v,F)=(∑∅≠T∈L(N,Γ,F)dT(B1),∑∅≠T∈L(N,Γ,F)dT(B2),…,∑∅≠T∈L(N,Γ,F)dT(Bm)).
Without loss of generality, suppose that i∈Bk for any i∈T, we have
(38)
DiP(N,Γ,v,F)=∑∅≠T∈L(N,Γ,F)dT(Bk)−∑∅≠T∈L(N,Γ,F)dT(Bk∖i)=∑∅≠T∈L(N,Γ,F)dT(Bk)=φi(N,Γ,v,F).
From φk(M,vB,FM)=∑i∈Bkφi(N,Γ,v,F), we have
(39)
DkP(M,vB,FM)=φk(M,vB,FM)=∑i∈Bkφi(N,Γ,v,F)=∑i∈BkDiP(N,Γ,v,F).
From Eq. (38) and EFF-2, P satisfies Eq. (36). Therefore, P is a potential function.

Uniqueness. Note that Eq. (35) can be written as

(40)
P(N,Γ,v,F)=1bk(DkP(M,vB,FM)+∑i∈BkP(N∖i,Γ|N∖i,v,F|N∖i)),
where bk is the cardinality of Bk.

When there is only one union in the coalition structure, we can conclude that there is the Hart-Mas-Colell potential function (Hart and Mas-Colell, 1989) which is known to be unique. By Eq. (35) and Eq. (36), we further derive that P defined on (M,vB,FM) is unique. Then, we can obtain the uniqueness of P(N,Γ,v,F) recursively according to Eq. (40) with the initial condition P(∅,Γ,v,F)=0.  □

Different to EFF-1, which is defined in view of carrier, we define the following EFF-2 which will be used in the following two axiomatic systems.

  • • Efficiency (EFF-2). Let v∈G(N,Γ,F), then v(N)=∑i∈Nfi(N,Γ,v,F).

Next, we consider the last axiomatic system of the quasi-Owen value. Myerson (1980) proposed a characterization of the Myerson value using Balanced contributions. Later, Zou et al. (2020) presented the Intracoalitional quasi-balanced contributions with respect to α and Coalitional quasi-balanced contributions with respect to α to characterize the α-Egalitarian Owen value for cooperative games with a coalition structure. Now, we propose Intra-coalitional balanced contributions and Coalitional balanced contributions for games on augmenting system with a coalition structure as:

  • • Intra-coalitional balanced contributions (IBC). Let v∈G(N,Γ,F). For any T∈L(N,Γ,F), without loss of generality, suppose that T=S⋃l∈R∈FM,k∈R∗Bl, where S∈FBk∖∅. Then

    (41)
    fi(N,Γ,v,F)−fi(N∖j,Γ|N∖j,v,F|N∖j)=fj(N,Γ,v,F)−fj(N∖i,Γ|N∖i,v,F|N∖i)
    for all i,j∈S∈FBk such that i≠j.

  • • Coalitional balanced contributions (CBC). Let v∈G(N,Γ,F), then

    (42)
    ∑i∈Bkfi(N,Γ,v,F)−∑i∈Bkfi(N∖Bl,Γ|N∖Bl,v,F|N∖Bl)=∑i∈Blfi(N,Γ,v,F)−∑i∈Blfi(N∖Bk,Γ|N∖Bk,v,F|N∖Bk)
    for all k,l∈R∈FM such that k≠l.

Theorem 5.

There is a unique solution f defined on G(N,Γ,F) that satisfies EFF-2, IBC, and CBC, which equals to φ.

Proof.

Existence. Obviously, φ satisfies EFF-2. From Theorem 4, we know that φi(N,Γ,v,F)=DiP(N,Γ,v,F), where P is the unique potential function for the game v∈G(N,Γ,F). Therefore, for any T∈L(N,Γ,F), without loss of generality, suppose that T=S⋃l∈R∈FM,k∈R∗Bl, where S∈FBk∖∅. Then,

φi(N,Γ,v,F)−φj(N,Γ,v,F)=DiP(N,Γ,v,F)−DjP(N,Γ,v,F)=Pj(N∖j,Γ,v,F)−Pj(N∖i,Γ|N∖i,v,F|N∖i)=Pj(N∖j,Γ|N∖j,v,F|N∖j)−Pj(N∖ij,Γ|N∖ij,v,F|N∖ij)+Pj(N∖ij,Γ|N∖ij,v,F|N∖ij)−Pj(N∖i,Γ|N∖i,v,F|N∖i)=φi(N∖j,Γ|N∖j,v,F|N∖j)−φj(N∖i,Γ|N∖i,v,F|N∖i)
for all i,j∈S∈FBk such that i≠j.

Thus, IBC holds.

Similarly, one can show that CBC is true.

To prove uniqueness, we just need to show that f admits a potential function. Let v∈G(N,Γ,F). For any T∈L(N,Γ,F), without loss of generality, suppose that T=S⋃l∈RBl, where S∈FBk and R∈FM∖k. When t=1 with t being the cardinality of T, by EFF-2 we have fi(T,ΓT,v,FT)=v(i)=DiP(T,ΓT,v,FT), where P is the unique potential function for the game G(N,Γ,v,F). By induction, when t⩽n−1 (n⩾2), for any i∈S, we have

(43)
fi(T,Γ|T,v,F|T)=DiP(T,Γ|T,v,F|T)=P(T,Γ|T,v,FT)−P(T∖i,Γ|T∖i,v,F|T∖i).
By Eq. (43), we derive
(44)
∑i∈Sfi(T,Γ|T,v,FT)=∑i∈Bkfi(T,Γ|T,v,FT)=∑i∈BkDiP(T,Γ|T,v,F|T).
From the definition of the potential function and Eq. (44), we get
(45)
∑i∈Bkfi(T,Γ|T,v,FT)=DkP(R∪k,vB,FM|R∪k).
Next, we prove the conclusion is true when t = n. By CBC, we obtain
∑i∈Bkfi(N,Γ,v,F)−∑i∈Bkfi(N∖Bl,Γ|N∖Bl,v,F|N∖Bl)=∑i∈Blfi(N,Γ,v,F)−∑i∈Blfi(N∖Bk,Γ|N∖Bk,v,F|N∖Bk).
By Eq. (45), we derive
∑i∈Bkfi(N,Γ,v,F)−DkP(M∖l,vB,FM|M∖l)=∑i∈Blfi(N,Γ,v,F)−DlP(M∖k,vB,FM|M∖k)
by which we get
∑i∈Bkfi(N,Γ,v,F)+P(M∖k,vB,FM|M∖k)=1m(∑l∈M∑i∈Blfi(N,Γ,v,F)+∑l∈MP(M∖l,vB,FM|M∖l)).
According to EFF-2, we derive
∑i∈Bkfi(N,Γ,v,F)+P(M∖k,vB,FM|M∖k)=1m(v(N)+∑l∈MP(M∖l,vB,FM|M∖l)).
From the concept of the potential function, we obtain
(46)
∑i∈Bkfi(N,Γ,v,F)=P(M,vB,FM)−P(M∖k,vB,FM|M∖k)=DkP(M,vB,FM).
By IBC, we get
fi(N,Γ,v,F)−fj(N,Γ,v,F)=fi(N∖j,Γ|N∖j,v,F|N∖j)−fj(N∖i,Γ|N∖i,v,F|N∖i)=P(N∖j,Γ|N∖j,v,F|N∖j)−P(N∖i,Γ|N∖i,v,F|N∖i)
for all i,j∈S∈FBk.

Then,

(47)
fi(N,Γ,v,F)−1bk∑j∈Bkfj(N,Γ,v,F)=1bk∑j∈BkP(N∖j,Γ|N∖j,v,F|N∖j)−P(N∖i,Γ|N∖i,v,F|N∖i),
where bk is the cardinality of Bk.

From Eq. (46), we have

(48)
fi(N,Γ,v,F)+P(N∖i,Γ|N∖i,v,F|N∖i)=1bk(DkP(M,vB,FM)+∑j∈BkP(N∖j,Γ|N∖j,v,F|N∖j)).
By Eq. (40), we know that the right hand side of Eq. (48) equals to P(N,Γ,v,F). Thus, Eq. (43) is true for t=n. Theorem 4 shows that the conclusion is obtained.  □

In this subsection, we focus on the axioms of the quasi-Owen value and give five axiomatic systems. These axiomatic systems can be divided into two categories in view of the axiom of linearity. The first two are based on linearity, while other three suggest alternative foundations of the quasi-Owen value without linearity. It is noteworthy that we can similarly build other axiomatic systems.

4The Core and the PMASs

In this section, we introduce the core and the PMAS for games on augmenting systems with a coalition structure. Further, the relationship between the quasi-Owen value and the core is discussed, and the conditions for the quasi-Owen value to be a PMAS are given.

4.1The Concept of the Core

In a similar way to the core of games with a coalition structure (Pulido and Sánchez-Soriano, 2009), the definition of the core of games on augmenting systems with a coalition structure is defined as:

Definition 6.

Let v∈G(N,Γ,F). The core C(N,Γ,v,F) of v is defined as:

(49)
C(N,Γ,v,F)={x∈ℜn|∑i∈Nxi=v(N),∑i∈Sxi⩾v(S),∀S∈L(N,Γ,F)}.
Now, we investigate some properties of the core, which are extended from reference (Pulido and Sánchez-Soriano, 2009). First, we introduce the concept of reduced games for games on augmenting systems with a coalition structure.

Definition 7.

Let v∈G(N,Γ,F), and let x be a corresponding solution. For any S∈L(N,Γ,F), the reduced game G(S,ΓS,vSx,FS) is defined as:

(50)
vSx=0,T=∅v(N)−x(N∖T),T=Smax{v(T∪R)−x(R):R⊆N∖S,T∪R∈L(N,Γ,F)},T∈F|S∖{∅,S},
where x(R)=∑i∈Rxi, v(N)−x(N∖T)=x(T) and vNx=v.

From reduced games, we further offer the following concepts of the coalitional reduced game property (C-RGP) and the coalitional converse reduced game property (C-CRGP).

Definition 8.

Let v∈G(N,Γ,F), S∈L(N,Γ,F)∖∅ and σ be a solution. If x∈σ(N,Γ,v,F) implies xS∈σ(S,ΓS,vSx,FS), then the solution σ satisfies C-RGP. Further, if xS∈σ(S,ΓS,vSx,FS) means x∈σ(N,Γ,v,F), then the solution σ satisfies C-CRGP, where xS denotes the restriction of x to the coalition S.

Lemma 3.

Let v∈G(N,Γ,F). The core C(N,Γ,v,F) satisfies C-RGP.

Proof.

Let S∈L(N,Γ,F)∖∅. For any x∈C(N,Γ,v,F) and any T∈FS, if T=S, then

vSx(T)=v(N)−x(N∖T)=x(T)=x(S).
Otherwise,
vSx(T)−x(T)=max{v(T∪R)−x(R):R⊆N∖S,T∪R∈L(N,Γ,F)}−x(T)=max{v(T∪R)−x(T∪R):R⊆N∖S,T∪R∈L(N,Γ,F)}⩽0.
Hence, vSx(T)⩽x(T). Therefore, the conclusion is true.  □

Next, we show that the core satisfies C-CRGP. To do this, let us consider the following lemma.

Definition 9.

If for any k∈M and any i∈Bk, we have k∈FM and i∈FBk, then we call (N,Γ,F) an atomic augmenting system with a coalition structure.

Lemma 4.

Let (N,Γ,F) be an atomic augmenting system with a coalition structure. For any S∈L(N,Γ,F)∖{N,∅} and any j∈N∖S such that S∪j∈L(N,Γ,F), there is a player i∈S such that {i,j}∈L(N,Γ,F).

Proof.

From the assumption, we have S∪j∈L(N,Γ,F). Since (N,Γ,F) is atomic, we have j∈L(N,Γ,F). Then, there is a chain from j to S∪j. In this chain, there is a set {i,j}∈L(N,Γ,F) such that {j}⊆{i,j}⊆S∪j. Therefore, i∈S, which concludes the proof.  □

According to Lemma 4, we offer the following proof of C-CRGP.

Lemma 5.

Let v∈G(N,Γ,F), (N,Γ,F) be an atomic augmenting system with a coalition structure, and x be a solution. If xS∈σ(S,ΓS,vSx,FS) for all S∈L(N,Γ,F) with s=2, then x∈σ(N,Γ,v,F), where s is the cardinality of S.

Proof.

If n⩽2, the statement obviously holds. Assume that n⩾3. We show that the statement still holds for all S∈L(N,Γ,F) with s=2. Let ∑i∈Nxi=x(N)=v(N) such that xS∈C(S,ΓS,vSx,FS) for all S∈L(N,Γ,F) with s=2. From S∈L(N,Γ,F)∖{N,∅} and Lemma 4, we know that there are two players i∈S and j∈N∖S such that {i,j}∈L(N,Γ,F). Since (N,Γ,F) is atomic and x{i,j}∈C({i,j},Γ{i,j},v{i,j}x,F{i,j}), we have v{i,j}x(i)−xi⩽0. Then,

v{i,j}x(i)−xi=max{v(i∪R)−x(R):R⊆N∖{i,j},R∪i∈L(N,Γ,F)}−xi=max{v(R∪i)−x(R∪i):R⊆N∖{i,j},R∪i∈L(N,Γ,F)}⩾v(S)−x(S).
Therefore, v(S)⩽x(S).  □

The following corollary is immediate from Lemma 5, which shows that the core of v∈G(N,Γ,F) satisfies the C-CRGP when (N,Γ,F) is atomic.

Corollary 1.

Let v∈G(N,Γ,F), and (N,Γ,F) be an atomic augmenting system with a coalition structure. Then, the core C(N,Γ,v,F) satisfies C-CRGP.

To build the axiomatic system of the core C(N,Γ,v,F), we further review the property of the individual rationality (IR): Let v∈G(N,Γ,F) and x be a solution. If xi⩾v(i) for any i∈L(N,Γ,F), then the solution x owns IR.

From the above analysis, one can check that the core of games on atomic augmenting systems with a coalition structure satisfies: EFF-2, IR, C-RGP and C-CRGP. In fact, these four properties can characterize the core of games on atomic augmenting systems with a coalition structure.

Theorem 6.

Let v∈G(N,Γ,F). If (N,Γ,F) is an atomic augmenting system with a coalition structure, then the core C(N,Γ,v,F) is the unique solution on v that satisfies EFF-2, IR, C-RGP and C-CRGP.

Proof.

The proof of Theorem 6 is similar to that of Theorem 5.14 in Peleg (1986), hence it is omitted.  □

Remark 2.

If there is only one coalition in Γ, then C-RGP and C-CRGP degenerate to the reduced game property (RGP) and the converse reduced game property (CRGP) for games on augmenting system, respectively. If all subsets of M and those of each Bk∈Γ are both feasible, then C-RGP and C-CRGP degenerate to the corresponding properties for traditional games with a coalition structure, respectively.

Similar to the Owen value for games with a coalition structure, we can prove that the quasi-Owen value for games on augmenting systems with a coalition structure belongs to the core. Based on the work of Pulido and Sánchez-Soriano (2009), we first give the following definition of quasi coalitional strong-convex games.

Definition 10.

Let v∈G(N,Γ,F). It is said to be quasi coalitional strong-convex if v(S)+v(T)⩽v(S∪T)+v(S∩T) for any S,T∈L(N,Γ,F) such that S∪T,S∩T∈L(N,Γ,F).

Following the work of Pulido and Sánchez-Soriano (2009), one can conclude that the quasi Owen value belongs to the core of quasi coalitional strong-convex games. However, as the next example shows, even if the game v∈G(N,v,Γ,F) is not quasi coalitional strong-convex, the quasi Owen value may still belong to the core.

Example 2.

Let N={1,2,3,4,5} be the player set, and Γ={B1,B2} be a coalition structure on N, where B1 = {1, 2, 3} and B2={4,5}. If FB1={∅,{1},{3},{1,2},{2,3},B1}, FB2={∅,{4},{5},B2} and FM={∅,{1},{2},M}, then it is an augmenting system with a coalition structure, where

L(N,Γ,F)={∅,{1},{3},{4},{5},{4,5},{1,2},{2,3},{1,2,3},{1,4,5},{3,4,5},{1,2,3,4},{1,2,3,5},{1,2,3,5},{1,2,4,5},{2,3,4,5},{1,2,3,4,5}}.
Further, the values of the coalitions are v(1,2)=v(1,2,3)=v(2,3,4,5)=1, v(1,4,5)=v(1,2,3,4)=v(1,2,3,5)=v(1,2,4,5)=1, v(N)=3, and v(S)=0 for other coalitions in S∈L(N,v,F).

Notice that this game is not quasi coalitional strong-convex as v(1,2)+v(1,4,5)>v(1,2,4,5)+v(1). However, one can easily check that the quasi Owen value φ(N,v,Γ,F)=(54,12,14,12,12) is an element in the core according to Definition 6. To fill this gap, we relax the condition and consider the convexity of the coalitions in the same chain.

Definition 11.

Let v∈G(N,Γ,F). It is said to be a quasi-chain coalitional convex game if for each k∈R∗ such that R∈FM,

v((S∪T)∪⋃l∈RBl)+v((S∩T)∪⋃l∈RBl)⩾v(S∪⋃l∈RBl)+v(T∪⋃l∈RBl)
for any S,T∈FBk such that S⊆T.

According to Definition 11, one can easily check that the game offered in Example 2 is a quasi-chain coalitional convex. By Definitions 10 and 11, one can conclude that quasi coalitional strong-convex game is quasi-chain coalitional convex game. Similar to classical case, we derive the following theorem.

Theorem 7.

Let v∈G(N,Γ,F). If v is quasi-chain coalitional convex, then (φi(N,Γ,v,F))i∈N∈C(N,Γ,v,F).

Proof.

For any S∈L(N,Γ,F), without loss of generality, suppose that S=T∪⋃kl∈HBkl, where T∈FBkp, H∈FM, and kp∈H∗. Then, there is a compatible ordering from ∅ to H∪kp and a compatible ordering from ∅ to T. Assume that {∅,{k1},{k1,k2},…,H,H∪kp,H∪kp∪kq,…,M}∈Ch(M) and {∅,{i1kp},{i1kp,i2kp},…,T,T∪{ijkp},…,{i1kp,i2kp,…,ibkpkp}}∈Ch(Bkp), where bkp is the cardinality of coalition Bkp. {∅,{i1kl},{i1kl,i2kl},…,{i1kl,i2kl,…,ibklkl}}∈Ch(Bkl) for any kl∈M∖kp. Let

xi1k1=v(i1k1),xi2k1=v(i1k1,i2k1)−v(i1k1),…,xibk1k1=v(Bk1)−v(Bk1∖ibk1k1),xibk1+1k1=v(Bk1∪i1k2)−v(Bk1),…,xn=v(N)−v(N∖ibkmkm).
It is obvious that ∑i∈Nxi=v(N).

If T≠Bkp, then N∖S=(Bkp∖T)∪⋃kl∈M∖HBkl={ijkp,ij+1kp,…,ibkpkp}∪⋃kl∈M∖HBkl, where Bkp∖T={ijkp,ij+1kp,…,ibkpkp}. Let Q=(T∪ijkp)∪⋃kl∈HBkl, then S∪Q=S∪ijkp and S∩Q=Q∖ijkp. From the quasi-chain coalitional chain convexity of v, we get ∑i∈Sxi−v(S)⩾∑i∈S∪ijkpxi−v(S∪ijkp).

If T=Bkp, then N∖S=⋃kl∈M∖HBkl. Let Q=⋃kl∈H∪kpBkl∪i1kq, where i1kq∈FBkq. Since kq∈(H∪kp)∗, by the quasi-chain coalitional chain convexity of v, we get ∑i∈Sxi−v(S)⩾∑i∈S∪i1kqxi−v(S∪i1kq).

By recursive relation, we get ∑i∈Sxi−v(S)⩾∑i∈Nxi−v(N)=0. Thus, (xi)i∈N∈C(N,v,Γ,F). From Eq. (7), we know that (φi(N,Γ,v,F))i∈N is a convex combination of c(M)∑k∈Mc(Bk)! elements in C(N,v,Γ,F). Since C(N,v,Γ,F) is a convex set, we get (φi(N,Γ,v,F))i∈N∈C(N,Γ,v,F).  □

The above theorem shows that when games on augmenting systems with a coalition structure are convex, there is no player who can make his own payoff larger than the quasi-Owen value without reducing other players’ payoff. Hence, there are no incentive to deviate from this allocation scheme.

4.2The Concept of PMASs

Inspired by Sprumont (1990) who first introduced and studied the concept of PMASs for traditional cooperative games, we here introduce the notion of PMASs for games on augmenting systems with a coalition structure.

Definition 12.

Let v∈G(N,Γ,F). If the vector x=(xi(S))i∈S satisfies

  • (i) ∑i∈Sxi(S)=v(S) for any S∈L(N,Γ,F);

  • (ii) xi(S)⩽xi(T) for all i∈S and all S,T∈L(N,Γ,F) such that S⊆T; then x=(xi(S))i∈S is called a PMAS.

Next, we study the conditions under which the quasi-Owen value is a PMAS.

Theorem 8.

Let v∈G(N,Γ,F), and S,T∈L(N,Γ,F) with S⊆T. Without loss of generality, suppose that S=D⋃l∈R∈FM,k∈R∗Bl and T=Y⋃l∈Q∈FM,k∈Q∗Bl, where R⊆Q and D⊆Y∈FBk.

  • (i) If FMQ∪k={PP=U∪O∈FM,whereO⊆Q∖RandU∈FMR∪k} and Q=R∪h such that h∈M∖R, we have

    (51)
    c(U)c(U∪l,R∪k)c(R∪k)⩽c(U)c(U∪l,R∪k∪h)c(R∪k∪h)+c(U∪h)c(U∪h∪l,R∪k∪h)c(R∪k∪h),
    where l∈R∗;

  • (ii) If FBkY={EE=A∪C∈FBk,whereC⊆Y∖DandA∈FBkD} and Y=D∪j such that j∈Y∖D, we obtain

    (52)
    c(A)c(A∪i,D)c(D)⩽c(A)c(A∪i,D∪j)c(D∪j)+c(A∪j)c(A∪j∪i,D∪j)c(D∪j),
    where j∈A∗;

  • (iii) If v is quasi-chain coalitional convex, then the quasi-Owen value (φi(N,Γ,v,F))i∈N is a PMAS.

Proof.

From Eq. (7), one can easily derive the condition (i) in Definition 12. As for the condition (ii), it is proved recursively. Suppose that S∪j=T, where j∉S. From Eq. (7), we have

(53)
φi(S,ΓS,vS,FS)=∑{U∈FMR∪k:k∈U∗}∑{A∈FBkD:i∈A∗}c(U)c(U∪k,R∪k)c(R∪k)c(A)c(A∪i,D)c(D)×(v(W∪A∪i)−v(W∪A))
for any i∈S, where W=⋃l∈U∈FMR∪kBl.

Case 1. T=Y⋃l∈R∈FM,k∈R∗Bl, where Y∈FBk and Y=D∪j. Then,

(54)
φi(T,ΓT,vT,FT)=∑{U∈FMR∪k:k∈U∗}∑{E∈FBkD∪j:i∈B∗}c(U)c(U∪k,R∪k)c(R∪k)c(E)c(E∪i,D∪j)c(D∪j)×(v(W∪E∪i)−v(W∪E))
for any i∈S.

By condition (ii), we have FBkY=FBkD∪j={EE=A∨A∪j∈FBk,whereA∈FBkD}. By the property A2, we have i∈(A∪j)∗ for any i∈A∗. Then, Eq. (55) can be written as:

(55)
φi(T,ΓT,vT,FT)=∑{U∈FMR∪k:k∈U∗}∑{A∈FBkD:i∈A∗}[c(U)c(U∪k,R∪k)c(R∪k)c(A)c(A∪i,D∪j)c(D∪j)×(v(W∪A∪i)−v(W∪A))+c(U)c(U∪k,R∪k)c(R∪k)c(A∪j)c(A∪j∪i,D∪j)c(D∪j)×(v(W∪A∪j∪i)−v(W∪A∪j))].
According to the condition (iii) we obtain
(56)
v(W∪A∪i)−v(W∪A)⩽v(W∪A∪j∪i)−v(W∪A∪j).
By condition (ii), we have
(57)
c(U)c(U∪k,R∪k)c(R∪k)c(A)c(A∪i,D)c(D)⩽c(U)c(U∪k,R∪k)c(R∪k)×(c(A)c(A∪i,D∪j)c(D∪j)+c(A∪j)c(A∪j∪i,D∪j)c(D∪j)).
According to Eqs. (54), (56) to (58), we derive φi(S,ΓS,vS,FS)⩽φi(T,ΓT,vT,FT) for all i∈S.

Case 2. T=D⋃l∈Q∈FM,k∈Q∗Bl, where Q=R∪h and Bh={j}. From Eq. (7), we have

(58)
φi(T,ΓT,vT,FT)=∑{U∈FMR∪k∪h:k∈P∗}∑{A∈FBkD:i∈A∗}c(U)c(U∪k,R∪k∪h)c(U∪k∪h)c(A)c(A∪i,D)c(D)×(v(W∪A∪i)−v(W∪A))
for any i∈S, where W=⋃l∈U∈FMR∪hBl.

By condition (i), we obtain FMQ∪k={PP=U∨U∪h∈FM,whereU∈FMR∪k}. By the property A2, we have k∈(U∪h)∗ for any k∈U∗. Then, Eq. (59) can be written as:

(59)
φi(T,ΓT,vT,FT)=∑{U∈FMR∪k:k∈U∗}∑{A∈FBkD:i∈A∗∧i∈Bk}[c(U)c(U∪k,R∪k∪h)c(R∪k∪h)c(A)c(A∪i,D)c(D)(v(W∪A∪i)−v(W∪A))+c(U∪h)c(U∪k∪h,R∪k∪h)c(R∪k∪h)c(A)c(A∪i,D)c(D)×(v(W∪j∪A∪i)−v(W∪j∪A))].
By conditions (i) and (iii), we have φi(S,ΓS,vS,FS)⩽φi(T,ΓT,vT,FT) for all i∈S.

Hence, (φi(N,Γ,v,F))i∈N is a PMAS.  □

Remark 3.

If there is only one coalition in Γ, we get the conditions for the Shapley value for games on augmenting systems to be a PMAS. If all subsets of M and those of each Bk∈Γ are feasible, the three conditions in Theorem 8 reduce to the condition for the Owen value for games with a coalition structure to be a PMAS.

5An Illustrative Example

In this section, we provide an application of games on augmenting system with a coalition structure in the food supply chain. Set up a supply chain consisting of food raw material supplier, food packaging supplier, food processing manufacturer, wholesaler and retailer. For the convenience of expression, the above members are set as 1, 2, 3, 4 and 5, respectively. The model of the food supply chain is shown in Fig. 1.

Fig. 1

The model of the food supply chain.

The model of the food supply chain.

In this food supply chain, to gain more profits with lower cost, companies 1, 2 and 3 decide to cooperate and form the production union {1,2,3} denoted as B1, and companies 4 and 5 decide to cooperate and form the sales union {4,5} denoted as B2. Because their skill levels and working procedures are different, they cannot cooperate freely. For example, the wholesaler 4 and retailer 5 carry on their work only after suppliers 1, 2 and manufacturer 3 have finished their production. Thus, when B1 and B2 cooperate, the coalitions that can be formed are ∅, {B1} and {B1,B2}. For the same reason, the coalitions formed by the companies 4 and 5 are ∅, {4} and B2. In the union {1,2,3}, the coalitions {1,3} and {2,3} can be formed for production. In addition, 1 and 2 are the suppliers of 3, which have a competitive relationship with each other, so the supply coalition {1,2} can’t be formed. However, the coalition {1,2,3} can be formed since the participation of 3. In conclusion, the formed coalitions are ∅, {1}, {2}, {1,3}, {2,3} and B1. The coalition values (million dollars/week) are offered as shown in Table 1. Thus, v is a game on augmenting system with a coalition structure denoted by G(N,Γ,v,F), where Γ={B1,B2}, FB1={∅,{1},{2},{1,3},{2,3},B1}, FB2={∅,{4},B2} and FM={∅,{B1},{B1,B2}}.

Table 1

The coalition values (million dollars/week).

Sv(S)(S)
∅0{2,3}9
{1}3{1,2,3}13
{2}4{1,2,3,4}17
{1,3}8{1,2,3,4,5}20

From Eq. (7), the quasi-Owen values of enterprises are

φ1(N,Γ,v,F)=3.5,φ2(N,Γ,v,F)=4.5,φ3(N,Γ,v,F)=5,φ4(N,Γ,v,F)=4,φ5(N,Γ,v,F)=3.
It is apparent that v is quasi-chain coalitional convex. From Eq. (49), the core is defined as:
C(N,Γ,v,F)={(x1,x2,x3,x4,x5)|∑i=15xi=20,x1⩾3,x2⩾4,x1+x3⩾8,x2+x3⩾9x1+x2+x3⩾13,x1+x2+x3+x4⩾17}.
One can easily check that (φi(N,Γ,v,F))i∈N∈C(N,Γ,v,F). It shows that no enterprise can make its own payoff greater than the quasi-Owen value without reducing other players’ payoffs. Namely, the quasi-Owen value is one of the best rule to distribute the coalition payoffs of the companies in the food supply chain.

This example shows that L(N,Γ,F)={∅,{1},{2},{1,3},{2,3},{1,2,3},{1,2,3,4},{1,2,3,4,5}}. For all S,T∈L(N,Γ,F), such that S⊆T, one can check that the conditions in Theorem 8 are satisfied. Further, one can show that the quasi-Owen value is a PMAS. For example, when S={1,3} and T={1,2,3}, we have

φ1(S,ΓS,vS,FS)=3⩽φ1(T,ΓT,vT,FT)=3andφ3(S,ΓS,vS,FS)=3⩽φ3(T,ΓT,vT,FT)=5.
From the above results, we know that each enterprise can get more payoffs from the larger coalitions than from the smaller coalitions.

6Conclusion

From the relationships among augmenting system, antimatroid and convex geometry (Bilbao and Ordonez, 2009), one can easily check that when augmenting systems on a coalition structure and on each union are closed under intersection, they turn to games on convex geometries with a coalition structure. Further, when augmenting systems on a coalition structure and on each union are closed under union, they become games on antimatroids with a coalition structure. It is noteworthy that the power set is also an augmenting system. Thus, game on augmenting systems with a coalition structure is an extension of game with a coalition structure.

The above relationships about different types of games show that the quasi-Owen value can be seen as a payoff index for them under the corresponding special conditions. Further, all listed axiomatic systems still hold for the quasi-Owen value in the setting of the above mentioned cooperative games, where axiomatic systems are defined under the associated conditions. This paper only studies a special kind of games under precedence constraints with a coalition structure, and it will be interesting to take into account other types of games under precedence constraints. Moreover, similar to the offered numerical example, we can apply the quasi-Owen value into other practical cooperative cases.

References

1 

Albizuri, M.J. ((2008) ). Axiomatizations of the Owen value without efficiency. Mathematical Social Sciences, 55: (1), 78–89.

2 

Algaba, E., Bilbao, J.M., van den Brink, R., Jiménez-Losada, A.J. ((2003) ). Axiomatizations of the Shapley value for cooperative games on antimatroids. Mathematical Methods of Operations Research, 57: (1), 49–65.

3 

Algaba, E., Bilbao, J.M., Slikker, M. ((2010) ). A value for games restricted by augmenting systems. SIAM Journal on Discrete Mathematics, 24: (3), 992–1010.

4 

Alonso-Meijde, J.M., Fiestras-Janeiro, M.G. ((2002) ). Modification of the Banzhaf value for games with a coalition structure. Annals of Operations Research, 109: (1–4), 213–227.

5 

Alonso-Meijide, J.M., Carreras, F.M., Fiestras-Janeiro, G., Owen, G. ((2007) ). A comparative axiomatic characterization of the Banzhaf-Owen coalitional value. Decision Support Systems, 43: (3), 701–712.

6 

Amer, R., Carreras, F., Giménez, J.M. ((2002) ). The modified Banzhaf value for games with coalition structure: an axiomatic characterization. Mathematical Social Sciences, 43: (1), 45–54.

7 

Aumann, R., Dreze, J. ((1974) ). Cooperative games with coalition structures. International Journal of Game Theory, 3: (3), 217–237.

8 

Bilbao, J.M. ((1998) ). Axioms for the Shapley value on convex geometries. European Journal of Operational Research, 110: (2), 368–376.

9 

Bilbao, J.M. ((2003) ). Cooperative games under augmenting systems. SIAM Journal of Discrete Mathematics, 17: (1), 122–133.

10 

Bilbao, J.M., Ordón¯ez, M. ((2009) ). Axiomatizations of the Shapley value for games on augmenting systems. European Journal of Operational Research, 196(3): , 1008–1014.

11 

Bilbao, J.M., Edelman, P.H. ((2000) ). The Shapley value on convex geometries. Discrete Applied Mathematics, 103: (1), 33–40.

12 

Bilbao, J.M., Jimenez, A., Lopez, J.J. ((1998) ). The Banzhaf power index on convex geometries. Mathematical Social Sciences, 36: (2), 157–173.

13 

Bilbao, J.M., Lebrón, E., Jiménez, N. ((1999) ). The core of games on convex geometries. European Journal of Operational Research, 119: (2), 365–372.

14 

Bilbao, J.M., Driessen, T.S.H., Jiménez-Losada, A.J., Lebrón, E. ((2001) ). The Shapley value for games on matroids: the static model. Mathematical Methods of Operations Research, 53: (2), 333–348.

15 

Bilbao, J.M., Driessen, T.S.H., Jiménez-Losada, A., Lebrón, E. ((2002) ). The Shapley value for games on matroids: the dynamic model. Mathematical Methods of Operations Research, 56: (2), 287–301.

16 

Edelman, P.H., Jamison, R.E. ((1985) ). The theory of convex geometries. Geometriae Dedicata, 19: (3), 247–270.

17 

Faigle, U., Kern, W. ((1992) ). The Shapley value for cooperative games under precedence constraints. International Journal of Game Theory, 21: (3), 249–266.

18 

Grabisch, M. ((1997) ). k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems, 92: (2), 167–189.

19 

Hamiache, G. ((1999) ). A new axiomatization of the Owen value for games with coalition structures. Mathematical Social Sciences, 37: (3), 281–305.

20 

Hart, S., Kurz, M. ((1983) ). Endogeneous formation of coalitions. Econometrica, 51: (4), 1047–1064.

21 

Hart, S., Mas-Colell, A. ((1989) ). Potential value and consistency. Econometrica, 57: (3), 589–614.

22 

Hu, X.F. ((2021) ). New axiomatizations of the Owen value. Mathematical Methods of Operations Research, 93: (3), 585–603.

23 

Khmelnitskaya, A.B., Yanovskaya, E.B. ((2007) ). Owen coalitional value without additivity axiom. Mathematical Methods of Operations Research, 66: (2), 255–261.

24 

Lorenzo-Freire, S. ((2017) ). New characterizations of the Owen and Banzhaf–Owen values using the intracoalitional balanced contributions property. Top, 25: , 579–600.

25 

Lorenzo-Freire, S. ((2019) ). On the Owen value and the property of balanced contributions within unions. Journal of Optimization Theory and Applications, 183: (2), 757–762.

26 

Meng, F.Y., Zhang, Q. ((2012) ). Cooperative games on convex geometries with a coalition structure. Journal of Systems Science Complexity, 25: (5), 909–925.

27 

Meng, F.Y., Chen, X.H., Zhang, Q. ((2015) ). A coalitional value for games on convex geometries with a coalition structure. Applied Mathematics and Computation, 266: , 605–614.

28 

Meng, F.Y., Zhang, Q., Chen, X.H. ((2016) ). A value for games on augmenting systems with a coalition structure. Operations Research Letters, 44: (3), 324–328.

29 

Meng, F.Y., Li, Z.J., Dong, Q., Fu, L.X., Zhang, Y.Q. ((2023) ). Profit allocation on a four-echelon supply chain in perspective of cooperative games on augmenting systems. Expert Systems with Applications, 219: , 119639.

30 

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

31 

Myerson, R.B. ((1980) ). Conference structures and fair allocation rules. International Journal of Game Theory, 9: (3), 169–182.

32 

Owen, G. ((1977) ). Values of games with a priori unions. In: Henn, R., Moeschlin, O. (Eds.), Mathematical Economics and Game Theory., Lecture Notes in Economics and Mathematical Systems, Vol. 141: . Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45494-3_7.

33 

Owen, G. ((1978) ). Characterization of the Banzhaf-Coleman index. SIAM Journal on Applied Mathematics, 35: (2), 315–327.

34 

Peleg, B. ((1986) ). On the reduced game property and its converse. International Journal of Game Theory, 15: (3), 187–200.

35 

Peleg, B. (1989). Introduction to the Theory of Cooperative Games, chapter 8 the Shapley value. RM 88 Center for Research in Mathematical Economics and Game Theory, The Hebrew University, Jerusalem Israel.

36 

Pulido, M.A., Sánchez-Soriano, J. ((2009) ). On the core the weber set and convexity in games with a priori unions. European Journal of Operational Research, 193(2): , 468–475.

37 

Sprumont, Y. ((1990) ). Population monotonic allocation schemes for cooperative games with transferable utility. Games and Economic Behavior, 2: (4), 378–394.

38 

Wang, G.M., Cui, Z.G., Shan, E.F. ((2022) ). An axiomatization of the value α for games restricted by augmenting systems. Mathematics, 10: (15), 2803.

39 

Winter, E. ((1992) ). The consistency and potential for values of games with coalition structure. Games and Economic Behavior, 4: (1), 132–144.

40 

Young, H. ((1985) ). Monotonic solutions of cooperative games. International Journal of Game Theory, 14: (1), 65–72.

41 

Zou, R., Xu, G.J., Li, W.Z., Hu, X.F. ((2020) ). A coalitional compromised solution for cooperative games. Social Choice and Welfare, 55: (4), 735–758.

Show more