## 1 Introduction

In their seminal paper, Shapley and Shubik (

1972) introduced assignment games to study two-sided matching markets where there are indivisible goods which are traded between sellers and buyers in exchange for money. They proved the nonemptiness of the core and provided a description of the core in terms of the underlying nonnegative pairwise surplus matrix that induces the game via maximal assignment optimization. Thus, the core of an assignment game can be determined without the explicit computation of the (in the number of players exponentially many) coalitional values. Solymosi and Raghavan (

2001) presented efficiently verifiable properties of the matrix which characterize various properties of the induced assignment game, for example, stability of the core, largeness of the core, exactness of the game, convexity of the game.

In this paper, following a similar approach, we characterize the assignment games which admit a population monotonic allocation scheme, a concept for core refinement introduced by Sprumont (

1990). An allocation scheme for a cooperative game specifies how to allocate the worth of every coalition. It is population monotonic if each player’s payoff increases as the coalition to which the player belongs to grows larger. Sprumont (

1990) showed that, essentially, a game has a population monotonic allocation scheme (PMAS) if and only if it is a positive linear combination of monotonic (simple) games with (individual) veto control. We will see that veto control not only by a single player but also by a seller-buyer pair are the key features of PMAS-admissibility for assignment games.

An obvious necessary condition for a game to admit a PMAS is that the core of each of its subgames is nonempty, that is the game is totally balanced. Sprumont (

1990) observed that in an (individually) veto-controlled monotonic game, we get a PMAS if in each subgame the (or in case of several veto players, a fixed) veto player receives the entire worth and all other players receive nothing. This easy-to-implement rule, however, only leads to a single (extreme) core allocation. We might also be interested in which other core allocations can be extended to a full scheme of population monotonic subgame core allocations. Another sufficient condition for the existence of a PMAS is convexity of the game. Sprumont (

1990) showed that in a convex game all core allocations can be reached by a PMAS. In particular, the Shapley value allocation of the game can be extended to a PMAS if we take the Shapley value allocation in each subgame. The PMAS-extendability of all core allocations in convex games seems natural, since convex games exhibit “increasing returns to cooperation” when a player is joining a disjoint coalition.

In this respect, assignment games are quite different from convex games, players on the same side of the market are substitutes rather than complements. No wonder, the class of PMAS-admissible assignment games is “quite slim”, although, as we will see, larger than the “very slim” class of convex assignment games. As Sprumont (

1990) demonstrated, if the pairwise surplus matrix contains a

\(2\times 2\) positive submatrix, no PMAS is possible in the associated assignment game. Our goal is to fully explore the structure of the underlying matrix which allows a PMAS in the assignment game. We give our structural characterization in terms of efficiently verifiable matrix properties as well as in terms of decomposibility in “elementary” assignment games with veto control (that provides PMAS-admissibility). We also show that in an assignment game either none or all core allocations are PMAS-extendable. Finally, we prove that in PMAS-admissible assignment games, the nucleolus (Schmeidler

1969) and the tau-value (Tijs

1981) coincide.

There is a rich literature on subclasses of totally balanced games in which certain extra conditions are sufficient (and maybe also necessary) for admitting a population monotonic allocation scheme. Without even attempting comprehensiveness, we only mention a few well-known classes of games, for example, minimum cost spanning tree games (Norde et al

2004), bankruptcy games (Grahn and Voorneveld

2002), simple games (Çiftçi et al

2010), vertex cover games (Xiao et al

2020), weighted multi-sided glove games (Moretti and Norde

2021), and independent set games (Wang et al

2022). Abe and Liu (

2019) discuss monotonic allocation paths in assignment games, a topic closely related to population monotonic allocation schemes. El Obadi and Miquel (

2019) consider an “almost” two-sided variation of assignment games, where there is a special player, called the central player, who is a seller and a buyer at the same time, and has veto control.

Particularly closely related to our work is the recent paper by Xiao and Fang (

2022). The authors characterize PMAS-admissible matching games defined on edge-weighted undirected networks. Since assignment games are of this type of matching games defined on two-sided networks, the main characterization of Xiao and Fang (

2022) naturally applies to assignment games too. Our paper, developed independently, focuses only on assignment games, but also establishes that in assignment games either none or all core allocations are PMAS-extendable, and that in the latter case, the nucleolus and the tau-value coincide.

The rest of the paper is organized as follows. In the next section, we recall the necessary background and establish two important features of population monotonic allocation schemes, namely that they are independent of inessential coalitions and are decomposable. In Sect.

3, assignment games with two types of veto control are investigated, namely, when there is a veto player, or when there is a seller-buyer pair with veto control. It is proved in Sect.

4 that any PMAS-admissible assignment game is the composition of some of these two “elementary” types of assignment games, and that in any PMAS-admissible assignment game all core allocations are PMAS-extendable. In Sect.

5, the equivalence of the nucleolus and the tau-value on the class of PMAS-admissible assignment games is proved, and it is illustrated by examples that this coincidence may not hold if either PMAS-admissibility or the assignment nature of the game is lifted. Section

6 concludes.

## 2 Preliminaries

A transferable utility cooperative game on the nonempty finite set of players, N, is defined by a coalitional function \(w:2^N \rightarrow {\mathbb {R}}\) satisfying \(w(\emptyset )=0\). The function w specifies the worth of every coalition \(S\subseteq N\). We denote the family of nonempty subsets of players by \({\mathcal {P}}(N)=2^N\setminus \{\emptyset \}\). Coalition \(S\in {\mathcal {P}}(N)\) is called inessential in game w if \(w(S)\le w(S_1)+\ldots +w(S_k)\) for some of its nontrivial partition \(S=S_1\cup \ldots \cup S_k\) consisting of \(k\ge 2\) pairwise disjoint nonempty coalitions \(S_1,\ldots ,S_k\in {\mathcal {P}}(N)\). Coalitions which are not inessential in w are called essential in w. We denote the set of essential coalitions in game w by \({\mathcal {E}}(w)\). Notice that every singleton coalition \(\{i\}\), \(i\in N\), is essential in any game (N, w).

Given a game (N, w), a payoff allocation \(x\in {\mathbb {R}}^N\) is called efficient, if \(x(N)=w(N)\); and coalitionally rational, if \(x(S) \ge w(S)\) for all \(S \subseteq N\); where, by the standard notation, \(x(S)=\sum _{i\in S} x_i\) if \(S\ne \emptyset \), and \(x(\emptyset )=0\). We denote by \({\textbf{C}}(N,w)\) the core, that is the set of efficient and coalitionally rational payoffs, of the game (N, w). Observe that the core is always the same as the essential-core, where coalitional rationality is required only for the essential coalitions in the game, i.e., \({\textbf{C}}(N,w)=\{x\in {\mathbb {R}}^N: x(N)=w(N),\; x(S)\ge w(S) \;\forall S \in {\mathcal {E}}(w)\}\). A game is called balanced, if its core is not empty, and totally balanced, if all subgames of the game are balanced. Convex games and assignment games form two (quite distinct, although not disjoint) subclasses of totally balanced games such that also all their subgames belong to the same subclass. Game (N, v) is convex if \(v(S\cup \{i\})-v(S)\le v(T\cup \{i\})-v(T)\) holds for all \(i\in N\) and \(S\subseteq T\subseteq N\setminus \{i\}\). Assignment games will be defined in the next section.

The composition of games \((N_1,w_1),\ldots ,(N_k,w_k)\) with pairwise disjoint player sets is the game (N, w) with player set \(N:=N_1\cup \ldots \cup N_k\) and coalitional function \(w(S):=w_1(S\cap N_1)+\ldots +w_k(S\cap N_k)\) for all \(S\subseteq N\). If all games \((N_1,w_1),\ldots ,(N_k,w_k)\) are (totally) balanced then also the composite game (N, w) is (totally) balanced, moreover, \(x\in {\textbf{C}}(N,w)\) if and only if \(x=(x^1,\ldots ,x^k)\) for some \(x^1\in {\textbf{C}}(N_1,w_1),\ldots ,x^k\in {\textbf{C}}(N_k,w_k)\). A game is said to be decomposable, if its player set can be partitioned into at least two nonempty coalitions such that the game is the composition of the corresponding subgames. Notice that in a decomposable game, a coalition which contains players from at least two of the component subgames is inessential in the game.

Sprumont (

1990) introduced the concept of a

population monotonic allocation scheme (PMAS) as a refinement of core allocations.

It is clear that only totally balanced games can admit a PMAS, and only core allocations can be PMAS-extendable. Sprumont (

1990) showed that every 3-player superadditive and balanced (hence totally balanced) game is PMAS-admissible, moreover, in these games all core allocations are PMAS-extendable. He also showed that convexity of the game is another sufficient property for PMAS-admissibility of the game and PMAS-extendability of all core allocations.

In one of his characterizations of PMAS-admissible games, Sprumont (

1990) used monotonic veto-controlled games as a kind of elementary PMAS-admissible games. Game (

N,

w) is

monotonic, if

\(w(S)\le w(T)\) whenever

\(S\subseteq T\subseteq N\). Monotonic games are trivially

nonnegative games, i.e., all coalitional values are nonnegative. In nonnegative game (

N,

w), player

\(i\in N\) is a

veto player, if

\(w(S)=0\) whenever

\(S\subseteq N\setminus \{i\}\). A nonnegative game is called

veto-controlled, if there is a veto player in the game. Sprumont (

1990) observed that in a monotonic veto-controlled game, if we give to a fixed veto player the entire worth of every coalition to which he belongs to and zero to the other coalition members, we get a PMAS. However, in contrast to 3-player totally balanced games and convex games, in a monotonic veto-controlled game the set of PMAS-extendable allocations might be a strict subset of the core, as illustrated in Example

1 below.

On the negative side, existence of a PMAS is not guaranteed for all totally balanced games with at least 4 players. Sprumont (

1990) used assignment games to demonstrate this. He showed that “

every assignment game with at least two sellers and two buyers, and such that each seller-buyer pair derives a positive gain from trade, lacks a PMAS.” We will see that this is only a sufficient, but not a necessary condition for an assignment game not to admit a PMAS, as there are certain

\(2\times 2\) assignment games with only three strictly profitable seller-buyer pairs which are not PMAS-admissible.

For reference, we summarize the aformentioned basic results.

We remark that Sprumont (

1990) also described the finitely generated convex cone of PMAS-admissible games in terms of linear inequalities reminescent of the well-known (Bondareva and Shapley) balancedness conditions for nonemptiness of the core. His dual characterization was substantially strengthened by Norde and Reijnierse (

2002). Although streamlining their characterization to assignment games could give further valuable insights to the combinatorial nature of these two-sided matching games, we do not explore this dual approach here.

We start our discussion with two general observations on population monotonic allocation schemes. They highlight the inherent structural similarities between PMAS-es and the core. First, inessential coalitions are redundant for a PMAS, the suballocations corresponding to the essential coalitions determine the entire PMAS. Secondly, the composition of PMAS-es gives a PMAS for the composite game. Since we will frequently employ (but have not found references to) these basic properties of PMAS-es, we also present the proofs.

The following monotonic veto-controlled game demonstrates that not necessarily all core allocations are PMAS-extendable, even if some are.

We have two main goals in this paper: (i) characterize which assignment games admit a PMAS, and (ii) answer the question whether all core allocations are PMAS-extendable in PMAS-admissible assignment games. It follows from (Sprumont

1990) (cf. Theorem

1) that assignment games with a single seller (or with a single buyer) are PMAS-admissible, because in these (zero-normalized) monotonic games the single seller (or the single buyer) is a veto player. Secondly, as observed by Solymosi and Raghavan (

2001), precisely those assignment games are convex games which are decomposable in their subgames corresponding to the positive-valued mixed-pair (composed of one seller and one buyer) coalitions. We will also identify those PMAS-admissible assignment games which are not convex and contain no veto player. It will turn out that decomposibility in subgames where a single-player or a mixed-pair has veto power is the key structural feature of PMAS-admissible assignment games. We will also show that in an assignment game either none or all core allocations are PMAS-extendable.

## 3 Assignment games

Given two disjoint finite sets S and T, we call \(\mu \subseteq S\times T\) an (S, T)-assignment, if it is a bijection from some \(S'\subseteq S\) to some \(T'\subseteq T\) such that \(\vert S'\vert =\vert T'\vert =\min (\vert S\vert ,\vert T\vert )\). Trivially, \(\mu =\emptyset \), if \(S=\emptyset \) or \(T=\emptyset \). We shall write \((i,j)\in \mu \) as well as \(\mu (i)=j\) and \(\mu (j)=i\). We denote by \({\mathcal {M}}(S,T)\) the set of all (S, T)-assignments. Obviously, \({\mathcal {M}}(S,T)=\{\emptyset \}\), if \(S=\emptyset \) or \(T=\emptyset \).

A game (

N,

w) is called an

assignment game, if there exists a partition

\(N=I\cup J\),

\(I\cap J=\emptyset \), of the player set and a nonnegative matrix

\(A=[a_{ij}]_{i\in I, j\in J}\) such that

$$\begin{aligned} w(S)=w_A(S):=\max _{\mu \in {\mathcal {M}}{(S\cap I, S\cap J)}} \; \sum _{(i,j)\in \mu } a_{ij} \qquad \text{ for } \text{ all } S\subseteq N. \end{aligned}$$

A matching

\(\mu \in {\mathcal {M}}(S\cap I, S\cap J)\) such that

\(w_A(S)=\sum _{(i,j)\in \mu }a_{ij}\) is an

optimal matching for coalition

\(S\subseteq N\). Due to the non-negativity of

A, we can (and will) assume (without loss of generality) that any optimal matching is a complete matching for the ‘short side’ of the coalition. We denote by

\({\mathcal {M}}_A^*(S\cap I,S\cap J)\) the set of optimal matchings for coalition

S. A player in

I or

J is called a row or column player, respectively. Coalitions containing one row player and one column player are called mixed-pair coalitions and will also be written as ordered pairs of the two players, always the row player written first. More formally, (

i,

j) denotes the mixed-pair coalition

\(\{i,j\}\),

\(i\in I\),

\(j\in J\). Notice that

\(w_A(\{i,j\})=a_{ij}\) for all mixed-pair coalitions (

i,

j), and

\(w_A(\{k\})=0\) for all players

\(k\in I\cup J\), thus, only the single-player and the positive-valued mixed-pair coalitions are essential in assignment game

\((I\cup J,w_A)\). Formally,

\({\mathcal {E}}(w_A)=\big \{ \{k\}: k\in I\cup J\big \} \cup \big \{ \{i,j\}: a_{ij}>0, i\in I, j\in J\big \}\).

It is easily checked that assignment games are zero-normalized and superadditive, hence nonnegative and monotonic. Shapley and Shubik (

1972) proved that every assignment game

\((I\cup J,w_A)\) is totally balanced, and the core is the set of solutions to quadratic many linear constraints given in terms of the underlying matrix

A. Namely, with any fixed optimal matching

\(\mu ^*\in {\mathcal {M}}_A^*(I,J)\),

where

\(I{\setminus }\mu ^*(J)\) and

\(J{\setminus }\mu ^*(I)\) denote, respectively, the set of row and column players unmatched under

\(\mu ^*\).

Shapley and Shubik (

1972) also proved that the core of any assignment game has a

row-optimal extreme point where each row player receives his core maximum payoff and each column player receives her core minimum payoff. Similarly, the core also has a

column-optimal extreme point where each column player receives her core maximum payoff and each row player receives his core minimum payoff. We denote the row-optimal and the column-optimal core allocations by

\((\overline{u},\, \underline{v})\) and

\((\underline{u},\, \overline{v})\), respectively, where

\(\overline{u}_i=\max \{u_i: (u,v)\in {\textbf{C}}(w_A)\}\) and

\(\underline{u}_i=\min \{u_i: (u,v)\in {\textbf{C}}(w_A)\}\) for all

\(i\in I\), similarly,

\(\overline{v}_j=\max \{v_j: (u,v)\in {\textbf{C}}(w_A)\}\) and

\(\underline{v}_j=\min \{v_j: (u,v)\in {\textbf{C}}(w_A)\}\) for all

\(j\in J\).

The average of the two side-optimal core allocations was recommended by Thompson (

1981) as the “fair” allocation favoring neither side in the core. It was shown to coincide with the tau-value (the definition is presented later) of the assignment game by Núñez and Rafels (

2002). We remark that in assignment games the tau-value is “typically” different from the nucleolus (see e.g. Example

3), let alone from the Shapley value (that is “typically” not even in the core). We will show (in Theorem

9), however, that in PMAS-admissible assignment games the tau-value and the nucleolus coincide, yet they could be different from the Shapley value (even if that allocation happens to be in the core).

Since in convex games the Shapley value is always a core allocation and the array of Shapley values of the subgames form a PMAS (Sprumont

1990), for reference, we recall the following characterization of convex assignment games.

The Shapley value, the nucleolus, and the tau-value are well known to coincide in 2-player superadditive (or equivalently, convex or assignment) games. Combined with the decomposability of the Shapley value and the nucleolus on the class of totally balanced games, Proposition

3 and Theorem

9 (where we prove that the nucleolus and the tau-value are the same in PMAS-admissible, in particular in convex games) imply that all three aforementioned point-valued solutions coincide in convex assignment games.

In the following subsections we discuss special types of assignment games which will turn out to be the key building blocks for our main characterization result (Theorem

7).

### 3.1 Assignment games with a veto player

Suppose assignment game \((I\cup J, w_A)\) is free of null players (i.e., there is no player i such that \(w_A(S\cup \{i\})=w_A(S)\) for all \(S\subseteq N\setminus \{i\}\)), or equivalently, that the underlying matrix A contains neither a full zero row nor a full zero column. Then there is a veto player in \(w_A\) if and only if \(\vert I\vert =1\) or \(\vert J\vert =1\) or both. In other words, row player \(i\in I\) is a veto player in assignment game \((I\cup J, w_A)\) if and only if all positive entries of A are in row i. In this case all row players in \(I\setminus \{i\}\) (if any) are null players. Similarly for column player \(j\in J\). It is then clear that there is a veto player in assignment game \((I\cup J, w_A)\) if and only if only one row or only one column of A contains positive entries.

We know from (Sprumont

1990) that the “veto player gets everything and all other players get nothing” allocation rule generates a PMAS in any monotonic veto-controlled game (a veto player is obviously also a veto player in any subgame). The natural question arises whether this extreme allocation is the only PMAS-extendable core allocation in monotonic veto-controlled games? It is clear that any other player in any subgame not containing a veto player is a null player, hence should get zero in any core allocation in the subgame. Could this be otherwise in subgames containing the veto player?

Next we show that if a monotonic veto-controlled game is an assignment game then all core allocations are PMAS-extendable.

### 3.2 Assignment games with two row and two column players

Let us summarize first what we know about the four-player assignment games with no veto player. They must contain at least two row and at least two column players, none of them is a null player. Thus, the underlying surplus matrix must be one of the following three types of

\(2\times 2\) matrices:

By Propossition

3, Type A assignment games are convex games, so by Theorem

1, they admit a PMAS and all their core allocations are PMAS-extendable.

In contrast, by Theorem

1, Type C assignment games admit no PMAS.

Next we fill the gap and show that certain Type B assignment games, although not convex games, also admit a PMAS and all their core allocations are PMAS-extendable, while the rest of the Type B assignment games are not PMAS-admissible.

### 3.3 Assignment games with a veto mixed pair

We say that nonnegative matrix \(A=\big [a_{ij}\ge 0\big ]_{i\in I, j\in J}\) with \(\vert I\vert ,\vert J\vert \ge 2\) has a \(\Gamma \)-shaped support if there exist a row player \(i_1\in I\) and a column player \(j_1\in J\) such that \(a_{kl}>0\) if \(k=i_1\) and/or \(l=j_1\), but \(a_{kl}=0\) whenever \(k\ne i_1\) and \(l\ne j_1\). We call entry \(a_{i_1 j_1}\) the corner of the \(\Gamma \)-shaped support, and say that it is dominant, if \(a_{i_1 j_1}\ge a_{i_1 l}+a_{k j_1}\) whenever \(k\ne i_1\) and \(l\ne j_1\).

If assignment game \((I\cup J,w_A)\) is induced by \(A=\big [a_{ij}\ge 0\big ]_{i\in I, j\in J}\) which has a \(\Gamma \)-shaped support with (dominant) corner \(a_{i_1 j_1}\), we call coalition \(\{i_1,j_1\}\) a (dominant) veto mixed pair because the worth of a coalition is zero if it does not contain at least one of these two players, i.e., \(w_A(S)=0\) whenever \(S\subseteq (I{\setminus }\{i_1\})\cup (J{\setminus }\{j_1\})\). Notice, however, that if an assignment game is controlled by a veto mixed pair, i.e., it is induced by a nonnegative matrix with \(\Gamma \)-shaped support, none of the players is a veto player or a null player.

For example, the support of matrix

is

\(\Gamma \)-shaped if

\(a_{ij}>0\) for all

\(1\le i\le \vert I\vert \) and

\(1\le j\le \vert J\vert \). Its corner is dominant if

\(a_{11}\ge a_{1\,l}+a_{k1}\) for all

\(2\le k\le \vert I\vert \) and

\(2\le l\le \vert J\vert \). In the corresponding assignment game, the corner mixed pair coalition

\(\{i_1,j_1\}\) has veto power, although neither

\(i_1\) nor

\(j_1\) is a veto player.

In the sequel we assume (without loss of generality) that the \(\Gamma \)-shaped support of the underlying matrix is composed of the first row and the first column, and starting from the corner the other entries are arranged in a weakly decreasing order in both directions, that is \(a_{1\,l}\ge a_{1\,l'}\) for all \(2\le l<l'\le \vert J\vert \), and \(a_{k1}\ge a_{k'1}\) for all \(2\le k<k'\le \vert I\vert \).

As expected, the characterization of the

\(2\times 2\) type B assignment games (Proposition

5) extends to larger games induced by matrices with

\(\Gamma \)-shaped support.

## 5 The nucleolus and the tau-value

We investigate the relation of the nucleolus and the tau-value in PMAS-admissible assignment games. We find that, although they are “typically” different in assignment games, they coincide on the PMAS-admissible subclass.

The tau-value was introduced by Tijs (

1981) as an efficient compromise value between an upper vector and a lower vector which, in balanced games, specify (not necessarily sharp) upper, respectively lower bounds for core payoffs. The

upper vector in game (

N,

v) consists of the marginal contribution of the players to the grand coalition,

\(M_i(v)=v(N)-v(N\setminus \{i\})\) for all

\(i\in N\). The

lower vector is defined by

\(m_i(v)=\max _{S: S\ni i} \left( v(S)-\sum _{j\in S{\setminus }\{i\}} M_j(v) \right) \) for all

\(i\in N\). In balanced game (

N,

v), for any

\(x\in {\textbf{C}}(v)\), the relations

\(m_i(v)\le x_i\le M_i(v)\) hold for all

\(i\in N\). Thus, there is a unique number

\(0\le \kappa \le 1\) for which

\(\sum _{i\in N} \tau _i(v)=v(N)\), where

\(\tau _i(v):=\kappa M_i(v)+(1-\kappa ) m_i(v)\) is called the

tau-value of player

\(i\in N\) in balanced game (

N,

v). In line with the standard terminology, the tau-value of the game is the vector of the individual tau-values of the players,

\(\tau (v)=\left( \tau _i(v): i\in N \right) \).

In an arbitrary balanced game the tau-value need not be a core allocation. Driessen (

1988) gave necessary and sufficient conditions for the tau-value to lie in the core. He also demonstrated that, unlike the core and the nucleolus, the tau-value is not independent of the inessential coalitions by presenting two different games with identical cores, but different tau-values, one of them even lying outside the core. For assignment games, Núñez and Rafels (

2002) proved that the tau-value is the midpoint of the line segment joining the row-optimal and the column-optimal core vertices, hence it is a core allocation, moreover, it is a locus of the core.

The nucleolus was introduced by Schmeidler (

1969). For balanced games, it is the unique core allocation which lexicographically maximizes the nondecreasingly ordered vector of the satisfactions of coalitions over the core, where we define the

satisfaction of coalition

S at allocation

x as

\(f(S,x)=x(S)-v(S)\). Huberman (

1980) showed that for balanced games, the essential coalitions are sufficient to determine the nucleolus, the inessential coalitions can be ignored, just like for the core. Consequently, for balanced games, the general criterion of Kohlberg (

1971) can also be simplified to contain only the essential coalitions as follows.

We use this criterion in two balanced games to check whether the tau-value is the nucleolus. The first one is the veto-controlled monotonic, hence PMAS-admissible game of Example

1. The second one is a

\((2+2)\)-player assignment game with no PMAS as discussed in Case 2 of Proposition

5.

We show that if the assignment game is PMAS-admissible then the tau-value and the nucleolus coincide.

The decomposibility of both the nucleolus and the tau-value on the class of assignment games are key elements of the above proof. It could be easily seen that the decomposibility of the nucleolus extends to the class of totally balanced games. The following example shows that this is not the case for the tau-value, as it fails to be decomposable on convex games, an important subclass of totally balanced games.

We close this section by showing that if we take the nucleolus (tau-value) for each subgame of an assignment game, we get a PMAS if and only if the game is convex.

## 6 Conclusion

We have characterized the assignment games which admit a population monotonic allocation scheme in terms of efficiently verifiable properties of the pairwise surplus matrix that induces the assignment game. We have proved that an assignment game is PMAS-admissible if and only if the underlying nonnegative matrix, up to row and column permutations, is a block-diagonal matrix where each block is either a single row vector, or a single column vector, or has a \(\Gamma \)-shaped support whose corner element itself dominates the value of any other assignment in the block. Translated in game theoretic terms it means that an assignment game is PMAS-admissible if and only if it contains a veto (row or column) player or a dominant veto mixed pair or it is a composition of these two types of special assignment games.

Since any monotonic game with a veto player admits a PMAS (Sprumont

1990), it readily follows that assignment games with a single row or column player admit a PMAS. We have identified another type of “elementary” PMAS-admissible assignment games, those in which no single player has veto control, but a mixed pair coalition has veto power (i.e., all coalitions with positive value contain at least one of these players), and showed that such assignment games are PMAS-admissible if and only if the veto mixed pair is dominant (i.e., its value equals the grand coalition value). Our proof has revealed that when the veto mixed pair is dominant, the assignment game can be expressed as the sum of two assignment games, one is veto-controlled by the row player, the other is by the column player of the dominant pair. This is in accordance with Sprumont (

1990)’s general characterization of PMAS-admissible games as precisely those games which can be written as a positive linear combination of monotonic games with veto player. The decomposability of any PMAS-admissible assignment game in subgames of these two types of veto control is mainly driven by the well known fact that no assignment game with a

\((2+2)\)-player subgame induced by a positive

\((2\times 2)\)-submatrix admits a PMAS (Sprumont

1990).

We have also shown that PMAS-admissibility of the assignment game implies that all core allocations can be extended to a PMAS, similarly to convex games, but unlike in arbitrary veto-controlled monotonic games where some core allocations might not be PMAS-extendable. Finally, we have proved that in a PMAS-admissible assignment game, the nucleolus and the tau-value coincide, but computing them for each subgame generates a PMAS only for convex assignment games (when they coincide with the Shapley-value).

To facilitate our discussions, we have made some (to best of our knowledge new) useful general observations. We have shown, for example, that population monotonic allocation schemes are independent of inessential coalitions, and are decomposable on the class of totally balanced games, exactly like the core and the nucleolus, but unlike the tau-value. As we have illustrated, the tau-value is not decomposable on the class of convex games, hence it cannot be independent of inessential coalitions either. In light of this difference, the proven equivalence of the nucleolus and the tau-value on the class of PMAS-admissible assignment games seems even more interesting.

## Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.