Equal treatment without large numbers

Abstract

We provide a necessary and sufficient condition under which core allocations of arbitrary TU-games treat substitute players equally. The core satisfies the equal treatment property if and only if no player needs the participation of all of her substitutes to attain her core payoffs. We show how, without the requirement of a large number of players, this condition generalizes and unifies other sufficient conditions proposed in the literature (in the context of large games and economies) and it helps derive new results for particular classes of games.

1 Introduction

Fairness and coalitional stability are two important principles in cooperative game theory. The Shapley value is the most well-known example of a fair division of value, while the core is the most used stability solution concept. It is well-known that the two are not necessarily compatible outside of particular classes of games. For example, if the game is not “convex” Shapley (1971) (or simply if the core is empty) the Shapley value may not be a stable allocation. This paper investigates the relationship between the core and a weaker notion of fairness: equal treatment of equals.

Two agents in a pure-exchange economy are considered “equals” and are called substitutes if they have the same endowments and preferences. Two players in a transferable utility (TU) game are substitutes if they contribute equally to every coalition. A solution concept treats equal players equally—and thus satisfies the equal treatment property (ETP)—if it assigns equal payoffs to substitute players. While the Walrasian allocations, the Shapley value, the kernel, the nucleolus, and most well-known bargaining solutions satisfy this principle, the core stands out as one of the few game theoretic concepts which fails to comply with ETP; given an arbitrary TU-game, substitute players may receive different payoffs at some core allocation. On the other hand, it is known that the unequal treatment of substitute players at (approximate) core payoffs is attenuated as the number of players in the game increases. This suggests that the increased competition among coalitions to lure players away by offering them valuable alternative options is central to eliminating inequality between substitute players. Our paper makes this idea precise by deriving a necessary and sufficient condition for the core of an arbitrary TU-game to satisfy ETP.

The equal treatment property, as formulated above, may be seen as too strong of a requirement for a multi-valued solution concept such as the core.¹ Aumann (1987) argues, for example, that symmetry is a more reasonable requirement in this case. The core is indeed symmetric in the sense that interchanging two substitute players does not change the core as a whole. We think that both notions are important and meaningful in the context of a multi-valued solution concept like the core. The following analogy is useful in drawing the comparison between the two. If each of n identical agents is offered an equal chance of winning a prize according to the outcome of throwing an n-sided die, then agents are treated equally ex-ante, but not necessarily ex-post. Throwing the die is, therefore, an “equal opportunity” mechanism which may result in unequal allocations. Similarly, symmetry guarantees that the core, as a policy instrument, is “ex-ante fair” to substitute players, while ETP insures its “ex-post fairness.” The goal of this paper is to explain what drives such “ex-post” equal treatment at a core allocation.

Dating back to Edgeworth (1881), and Debreu and Scarf (1963), it is known that equal treatment is achieved at a core allocation of an economy when the number of agents of each type is the same (and some convexity and monotonicity conditions are satisfied). What drives the result is the following argument: if one player of a certain type is the worst treated among his/her peers, then that player could form a coalition with all worst treated individuals of each type and be better off. It is also known that this argument fails if the sets of agents’ types are of different cardinality (with their largest common divisor equal to 1). In that case, the coalition of worst treated individuals may not have enough resources to support an improving allocation and therefore, the core of such an economy may fail to satisfy ETP. The fundamental difference between these two cases, which triggers the differential treatment of substitute players, is the availability of outside options (for every player of a certain type).

We show how this simple insight obtained from replica economies can be translated to arbitrary TU-games and used to derive a necessary and sufficient condition for the equal treatment of equals at the core allocations of such games (or some core extensions, when the core is empty). We prove that the core of a game satisfies ETP if and only if no player needs the participation of all of her equals (or substitute players) in order to attain her core payoffs. Intuitively, not needing all of a player’s substitutes boils down to not needing any particular substitute to attain a core payoff. The availability of outside options without depending on a particular player, a concept reminiscent of objections in the context of bargaining sets Aumann and Maschler (1964), is precisely what allows a player to improve upon any payoff distribution in which a substitute fairs better than her.

A similar idea appears in the context of equilibrium pricing of perfect complement and perfect substitute goods. If $x\in \mathbb {R}^n_+$ is a consumption vector of n goods and $u: \mathbb {R}^n_+\rightarrow \mathbb {R}$ denotes the utility of an agent, both perfect complements (goods i, j for which u(x) depends on $(x_i, x_j)$ only through $\min \{x_i, x_j\}$) and perfect substitutes (u(x) depends on $(x_i, x_j)$ through $x_i+ x_j$) contribute to the agent’s utility equally, in the sense that $u(x)=u(x^{i\leftrightarrow j})$, where $x^{i\leftrightarrow j}$ is the consumption bundle obtained from x by swapping $x_i$ and $x_j$. In that sense, perfect complements and perfect substitutes are similar to substitute players in a TU-game. This analogy is made precise in direct markets Shapley and Shubik (1969) and assignment markets Shapley and Shubik (1971), for which the following core equivalence result holds: the sets of Walrasian equilibrium prices of those markets coincide with the cores of their associated games. Yet, perfect complements (which have to be consumed together to generate utility for the agent) need not be priced equally at a Walrasian equilibrium, while perfect substitutes must sell at equal prices.

The literature on cooperative games has been limited to obtaining sufficient conditions for ETP to hold in the core. Furthermore, such sufficient conditions are applicable to very specific situations: replica games of partitioning games, or games with a sufficiently large number of players. On the other hand, in the context of pure-exchange economies, Green (1972) and Khan and Polemarchakis (1978) derive a necessary condition for identical consumers to receive identical allocations at a core outcome. The literature on market games points out that there is a close connection between cooperative games and economies by showing that certain subclasses of cooperative games can be mapped, bijectively, into particular classes of economies (see, for example, Shapley and Shubik (1969), or Garratt and Qin (2000) for mappings between cooperative games and pure-exchange economies, and Billera (1970) or Bejan and Gómez (2012) for production economies). Yet, the sufficient conditions appearing in the cooperative games literature and the necessary condition for pure-exchange economies are not directly comparable. Our paper makes this comparison possible. We derive a condition that is both necessary and sufficient for the core of a TU-game to satisfy ETP. When applied to quasi-linear pure-exchange economies, our condition strengthens Green (1972) decomposability assumption; within the class of TU-games, it weakens several proposed sufficient conditions for the ETP to hold in large games.

The idea that outside options play an important role for the equal treatment of equal players at core allocations appeared in the literature before, in various forms. For example, Section 5 in Wooders (2010) comments on the importance of alternative opportunities for achieving almost equal treatment. Wooders (1983, 2010) show that, under certain conditions, and if a game is large enough, most equal players are treated nearly equally at a core allocation. This means that, as the number of players in a game increases, some substitute players receive allocations that are very close to each other, and the fraction of those who do not shrinks to zero (see also Hildenbrand and Kirman (1973) for similar results in the context of economies). Green (1972) shows that equal treatment at core outcomes of an economy cannot happen unless such outcomes can be “attained through the independent actions of two disjoint subeconomies.” We improve upon these results in several ways. First, we weaken the condition and show that it is enough to hold for balanced families of coalitions supporting the core allocations (rather than partitions of the set of players). Second, we show that this new condition is both necessary and sufficient for the equal treatment of equals in the core. Third, our result can also be extended to non-balanced games, as our condition can be applied to the aspiration core Bennett (1983), a non-empty core extension, and to certain types of epsilon-cores. Finally, the condition applies to arbitrary TU-games, regardless of the number of players in the game.

Our characterization of the games in which the core satisfies the ETP has interesting implications in a variety of settings. We show how it can be used to obtain new results for particular classes of games. For partitioning games Kaneko and Wooders (1982), we obtain a new sufficient condition which is reminiscent of the “small group effectiveness” condition used by Wooders (2010) to prove almost equal treatment at approximate core allocations of sufficiently large replica games. Our condition, by contrast, applies to any partitioning game and delivers exact equal treatment. On the class of multi-assignment games, we prove that the core satisfies ETP whenever no two players in different families are substitutes to each other. Finally, we propose a new way of defining replica games which has the advantage that the (approximate) core of every game along the sequence satisfies ETP. This allows for more streamlined convergence results.

The paper is organized as follows. Section 2 introduces the definitions and notation, and presents our main result which applies to balanced games. Section 3 extends the results to core-like concepts defined over the space of non-balanced games. Section 4 links our characterization to the rest of the literature and shows how it applies to various classes of games and the convergence of replica games, while Sect. 5 illustrates how the result can be applied to quasi-linear economies.

2 TU-games

A TU-game is a pair (N, v) such that N is a finite set of players with cardinality n and $v:2^N \rightarrow \mathbb {R}$ is a function such that $v(\emptyset )=0$. The family of all TU-games is called $\Gamma$. Let $\mathcal {N}$ denote the collection of all non-empty subsets of N. Every such subset is called a coalition. For every $S \in \mathcal {N}$, v(S) is called the worth of coalition S. The game (N, v) is said to be super-additive if $v(S \cup T) \ge v(S) + v(T)$ for every $S,T \in \mathcal {N}$ such that $S \cap T = \emptyset$.

A possible outcome of the game (N, v) is represented by a payoff vector $x \in \mathbb {R}^N$ that assigns to every player i a payoff $x_i$. Given $x \in \mathbb {R}^N$ and $S \subseteq N$, let $x(S):=\sum _{i \in S} x_i$, with the convention that $x(\emptyset )=0$. A payoff vector $x\in \mathbb {R}^N$ is feasible for coalition S if $x(S)\le v(S)$. We say that a coalition S is able to improve upon the outcome $x \in \mathbb {R}^N$ if $x(S)<v(S)$. For every payoff vector $x \in \mathbb {R}^N$, define its generating collection as $\mathcal {GC}(x) :=\{S \in \mathcal {N} \; | \; x(S) \le v(S) \},$ that is, the family of coalitions for which x is feasible.

A solution concept on the set of games $\Gamma$ is a mapping that assigns to every game $(N,v)\in \Gamma$ a (possibly empty) set of payoff vectors $\sigma (N,v) \subseteq \mathbb {R}^N$. The core Shapley (1955), Gillies (1959)² is a solution concept on $\Gamma$ defined as

$$\begin{aligned} C(N,v) :=\left\{ x\in \mathbb {R}^N \mid x(S) \ge v(S) \; \forall S \in \mathcal {N} \text { and } x(N) = v(N) \right\} . \end{aligned}$$

2.1 Equal treatment property

Given a game $(N,v) \in \Gamma$, two players $i,j \in N$ are called substitute players if they contribute equally to every coalition. That is, for every (possibly empty) set of players $T \subseteq N {\setminus } \{i,j\}$, $v(T \cup \{ i \} ) = v(T \cup \{ j \} )$. This equivalence relation, denoted as $i \sim j$, partitions the set N into equivalence classes. Let $\mathcal {A}(N,v)$, or just $\mathcal {A}$ when there is no ambiguity, be the family of all such equivalence classes. An element $A \in \mathcal {A}$ is called a class of substitutes. For every coalition $S \in \mathcal {N}$, let $\rho (S)\in \mathbb {Z}_+^{\mathcal {A}}$ be the profile of S, defined for every $A \in \mathcal {A}$ as $\rho _A(S):=|S\cap A|$. Two coalitions $S,T \in \mathcal {N}$ are called substitute coalitions if $\rho (S)=\rho (T)$, and we denote this by $S \sim T$. Notice that $S \sim T$ implies $|S|=|T|$ and $v(S) = v(T)$.

Definition 2.1

Given a game $(N,v)\in \Gamma$, a payoff vector $x \in \mathbb {R}^N$ is said to satisfy the Equal Treatment Property (ETP) over the set of players $S \subseteq N$ in game (N, v) if, for every $i,j \in S$, $i \sim j$ implies $x_i = x_j$. If no set of players S is specified, it is understood that $S=N$. A set $X \subseteq \mathbb {R}^N$ satisfies ETP if every $x\in X$ satisfies ETP. A solution concept $\sigma$ on the family of games $\Gamma$ is said to satisfy ETP if, for every $(N,v) \in \Gamma$, $\sigma (N,v)$ satisfies ETP.

It is well known that, in general, the core does not satisfy ETP. The following example illustrates this point.

Example 2.2

The n -player bridge game: Let $(N,v^n_{br})$ be the TU-game defined by $N=\{1,\ldots ,n\}$ and $v^n_{br}(S)=\left[ \frac{|S|}{4}\right]$ for every $S\subseteq N$, where [x] denotes the greatest integer smaller than or equal to x. All players are substitutes of each other in this game. However, for $n=4$, the core of this game coincides with the three-dimensional unit simplex of $\mathbb {R}^4$, thus violating ETP.

2.2 Balancedness and essential coalitions

A family of coalitions $\mathcal {B} \subseteq \mathcal {N}$ is called balanced if every $S \in \mathcal {B}$ can be associated with a non-negative number $\lambda _S$ such that, for every $i \in N$, $\sum _{S \in \mathcal {B}, S \ni i} \lambda _S = 1$. The numbers $\lambda _S$ are called balancing weights. The game (N, v) is said to be balanced if and only if, every balanced family $\mathcal {B}$, with weights $(\lambda _S)_{S \in \mathcal {B}}$, satisfies that $\sum _{S \in \mathcal {B}} \lambda _S v(S) \le v(N)$. If all members of a balanced family are proper coalitions (that is, non-empty, strict subsets of N), such family is said to be proper. The balanced family $\mathcal {B}$ is called optimally balanced if it maximizes $\sum _{S \in \mathcal {B}} \lambda _S v(S)$ over the set of balanced families. Such maximum always exists and it is denoted by $\bar{v}(N)$. As $\{N\}$ is a balanced family, the game (N, v) is balanced if and only if $\bar{v} (N) = v(N)$. It is well known that the core of a game is non-empty if and only if the game is balanced Bondareva (1963), Shapley (1967).

Definition 2.3

For every game (N, v), a coalition $S^*$ is said to be essential if there exists an optimally balanced family of coalitions $\mathcal {B}$, with associated weights $(\lambda _S)_{S \in \mathcal {B}}$, such that $S^* \in \mathcal {B} \subseteq \mathcal {N} {\setminus } \{N\}$ and $\lambda _{S^*} > 0$. The set of essential coalitions is denoted by Ess(N, v).

Essential coalitions play a particularly important role in our ETP result. The reason is that, as the following lemma explains, a player belonging to an essential coalition has a different way, other than the formation of the grand coalition, of achieving her core payoffs. Next section shows how these outside options prevent unequal treatment of substitute players.

Lemma 2.4

If $x \in C(N,v)$ and $S^*$ is an essential coalition, then $x(S^*) = v(S^*)$.

Proof

Let $\mathcal {B}$ be an optimally balanced family of coalitions with associated weights $(\lambda _S)_{S \in \mathcal {B}}$, such that $S^* \in \mathcal {B}\subseteq \mathcal {N} {\setminus } \{N\}$ and $\lambda _{S^*} > 0$. Assume that $x(S^*) > v(S^*)$. Since $x(S) \ge v(S)$ for every $S \in \mathcal {B}$, multiplying each of these inequalities by the corresponding $\lambda _S$ and adding over the members of $\mathcal {B}$ we obtain that:

$$\begin{aligned} v(N) = x(N) = \sum _{S \in \mathcal {B}} \lambda _S x(S) > \sum _{S \in \mathcal {B}} \lambda _S v(S) = \bar{v}(N), \end{aligned}$$

where the inequality is a consequence of $\lambda _{S^*}$ being strictly positive.

However, this is a contradiction to $\bar{v}(N)=v(N)$, and therefore $x(S^*) = v(S^*)$. $\square$

Lemma 2.5

If $S^*$ is an essential coalition and $S^* \sim T^*$, then $T^*$ is also essential.

Proof

Let $\mathcal {B}$ be an optimally balanced family of coalitions with associated weights $(\lambda _S)_{S \in \mathcal {B}}$, such that $S^* \in \mathcal {B}\subseteq \mathcal {N} {\setminus } \{N\}$ and $\lambda _{S^*} > 0$. Consider a bijection $\phi :N \longrightarrow N$ such that:

• 1. For every $i \in N$, $i \sim \phi (i)$.

• 2. $\phi (S^*) = T^*$.

Then,

$$\begin{aligned} \sum _{S \in \mathcal {B}} \lambda _S v(\phi (S)) = \sum _{S \in \mathcal {B}} \lambda _S v(S) = \bar{v}(N), \end{aligned}$$

and thus $T^* = \phi (S^*)$ must be essential. $\square$

2.3 Main characterization

Our main result characterizes the set of games for which the core satisfies ETP.

Theorem 2.6

Let (N, v) be a balanced game. Its core satisfies ETP if and only if, for every class of substitute players $A \in \mathcal {A}$ with $|A| \ge 2$, there exists an essential coalition $S^*_A$ that contains at least one but not all members of A.

Proof

Sufficiency: Let $A \in \mathcal {A}$ be a multiple-player class of substitutes such that the essential coalition $S^*_A$ contains at least one but not all members of A. We will show that every $x \in C(N,v)$ satisfies ETP over any such A.

Pick arbitrary players $i \in S^*_A \cap A$ and $j \in A {\setminus } S^*_A$. Thus, $i \sim j$, $S^*_A \sim (S^*_A {\setminus } \{i\}) \cup \{j\}$ and, due to Lemma 2.5, $(S^*_A {\setminus } \{i\}) \cup \{j\}$ is also an essential coalition. We now use Lemma 2.4 to conclude that any payoff vector x such that $x_i < x_j$ cannot belong to the core. Indeed, x can be improved upon by $S^*$ because

$$\begin{aligned} v(S^*) = v((S^* {\setminus } \{i\}) \cup \{j\})=x((S^* {\setminus } \{i\}) \cup \{j\})>x(S^*). \end{aligned}$$

To prove necessity we need the following result:

Lemma 2.7

For every balanced game (N, v), there exists a vector $\bar{x} \in C(N,v)$ such that $\mathcal {GC}(\bar{x}){\setminus } \{N\}\subseteq Ess(N,v)$.

Proof of the lemma

Consider the game $(N,v_{ess}^{\varepsilon })$ defined as $v_{ess}^{\varepsilon }(S)=v(S)$ if S is essential or $S=N$, and $v_{ess}^{\varepsilon }(S)=v(S) + \varepsilon$ otherwise. We claim that, for $\varepsilon$ small enough , $\bar{v}_{ess}^{\varepsilon }(N) = v(N)$. If this claim is proved, then $v_{ess}^{\varepsilon }$ is balanced and any vector $\bar{x} \in C(N,v_{ess}^{\varepsilon })$ also belongs to C(N, v). Then, if $\bar{x}(S) = v(S)$, it must be the case that S is essential, otherwise the definition of $v_{ess}^{\varepsilon }$ would imply that $\bar{x}(S) < v(S) + \varepsilon = v_{ess}^{\varepsilon }(S)$, a contradiction.

We detail next the construction of $\varepsilon$. A balanced family of coalitions is said to be minimal balanced if no proper subcollection is balanced. It is known that (see Kannai 1992): (i) If $\mathcal {B} \subseteq \mathcal {N}$ is minimal balanced, then $|\mathcal {B}| \le n$ and its corresponding weights are rational, strictly positive, and unique, (ii) There is only a finite number of minimal balanced families of coalitions, and (iii) There is a minimal balanced family $\mathcal {B}$ with associated weights $(\lambda _S)_{S \in \mathcal {B}}$ such that $\sum _{S \in \mathcal {B}} \lambda _S v(S) = \bar{v}(N)=v(N)$.

Consequently, it is always possible to choose $\varepsilon$ so that

$$\begin{aligned} 0< \varepsilon < \frac{\bar{v} (N) - \sum _{S \in \mathcal {B}'} \lambda _S v(S)}{n} \end{aligned}$$

for every minimal balanced collection $\mathcal {B}'$ that is not optimally balanced. For any such $\mathcal {B}'$, using that $|\mathcal {B}'| \le |N|$, we have:

$$\begin{aligned} \sum _{S \in \mathcal {B}'} \lambda _S v_{ess}^{\varepsilon }(S) \le \sum _{S \in \mathcal {B}'} \lambda _S v(S) + \varepsilon \sum _{S \in \mathcal {B}'} \lambda _S \le \sum _{S \in \mathcal {B}'} \lambda _S v(S) + |N|\varepsilon < \bar{v}(N). \end{aligned}$$

Hence $\bar{v}_{ess}^{\varepsilon }(N)$ will be achieved by using a minimal and optimally balanced family of coalitions in the original game v. It follows that $\bar{v}_{ess}^{\varepsilon }(N)=\bar{v}(N)=v(N)$, as we wanted. $\square$

Necessity: Suppose that a multiple-player class of substitutes $A \in \mathcal {A}$ is such that, if coalition $S^*$ is essential, then $S^* \cap A \in \{ \emptyset , A \}$. We will show that, in such case, C(N, v) cannot satisfy ETP over A.

Let $\bar{x}\in C(N,v)$ be as described in Lemma 2.7. By assumption, not every proper coalition S satisfies $\bar{x}(S) = v(S),$ otherwise every proper coalition would be essential and some essential coalition would separate the elements of A. Therefore, we can choose $\varepsilon$ such that

$$\begin{aligned} 0< \varepsilon < \min \big \{\bar{x}(S) - v(S) \; | \; S \in \mathcal {N} \quad \text { and } \quad \bar{x}(S) \ne v(S) \big \}. \end{aligned}$$

Let $i,j \in A$ be such that $i \ne j$ and define the payoff vector $\hat{x}$ as follows. Let $\hat{x}_i = \bar{x}_i + \varepsilon$, $\hat{x}_j = \bar{x}_j - \varepsilon$ and, for every $k \in N {\setminus } \{i,j\},$ define $\hat{x}_k = \bar{x}_k$. Our choice of $\varepsilon$ implies that $\hat{x}(S) > v(S)$ whenever $\bar{x}(S) > v(S)$. Also, if $\bar{x}(S) = v(S)$ and $S \in \mathcal {N} {\setminus } \{N\}$, S is essential so $S \cap A \in \{ \emptyset , A \}$ and $\hat{x}(S) = v(S)$. Clearly $\hat{x}(N) = \bar{x}(N) = \bar{v}(N)$, so $\hat{x} \in C(N,v)$. However, $\bar{x}$ and $\hat{x}$ cannot simultaneously satisfy ETP, reaching a contradiction. $\square$

The main driver of the sufficiency proof is the existence of an outside option (namely, forming coalition $S^*$) that prevents a given player to be treated unfairly with respect to her substitutes. Our result reinforces the idea that the existence of outside options is intrinsically related to equal treatment.

For example, going back to the bridge game (see Example 2.2), four bridge players do not have alternative options and thus are vulnerable to be treated differently. This does not happen in the 8-player bridge game, whose core is a singleton assigning the same amount to every player. Intuitively, as the number of players in a game increases, the opportunities for outside options increase as well, thus explaining why inequality tends to disappear in large enough games.

The same type of dynamic is at work in the well-known gloves game.

Example 2.8

Consider the gloves game with $l \ge 1$ left gloves and $r \ge 1$ right gloves, denoted by $(N, v_{gl}^{l,r})$. The set of players is $N = L \cup R$ where $|L| = l$, $|R|=r$, and $L \cap R = \emptyset$. For every $S \subseteq N$ define $v_{gl}^{l,r}(S) = \min \{ |S \cap L|, |S \cap R| \}$. As long as $l\ge 2$ (or $r\ge 2$) all players in L (respectively R) form a class of substitutes. To obtain a positive payoff, each player in L (respectively R) does not need to associate with her substitutes and the conditions of Theorem 2.6 are satisfied.Thus, its core (which is known to be non-empty) satisfies ETP. Notice that, if $r = l = 1$ then ETP is not satisfied. In this case, even though each player owns a different type of glove, they are substitutes of each other. The only option each player has is to associate with her substitute, explaining how the conditions of Theorem 2.6 fail to hold.

The main idea behind the necessity portion of the theorem is that a “thick” core cannot satisfy ETP. If the relative interior of the core is non-empty, it is possible to take away a small amount of payoff from a player and give it to one of her substitutes without leaving the core. However, the new vector does not satisfy ETP. In a nutshell, we show that violating our condition leads to a “thick” core.

How “thin” must the core be to satisfy ETP? The previous discussion might suggest that, if a game satisfies the condition of Theorem 2.6 and thus ETP holds at every core allocation, then the projection of the core on a family $\mathcal {A}$ of substitute players must be a singleton.³ As the next example illustrates, that need not be true.

Example 2.9

Consider the four-player game $(\{1,2,3,4\}, v_{gl}^{2,2})$. Say that players 1 and 2 own a right glove while players 3 and 4 own a left glove. Then, $C(N, v_{gl}^{2,2})= \{(a,a,1-a,1-a) \;|\; a \in [0,1]\}$ and it satisfies ETP, but its projection on $\{1,2\}$ is not a singleton.

3 Empty-core games

A number of important economic settings (indivisibilities, non-convexities and externalities among others) give rise to non-balanced games. The next two subsections describe alternative solution concepts for empty-core games. The approximate (or epsilon) core approach makes it harder for proper coalitions to form and improve upon payoff vectors. On the other hand, the aspiration approach relaxes the feasibility condition, so that the grand coalition is no longer required to form. The remaining subsections extend our results for both settings, making our characterization applicable to general TU-games.

3.1 Approximate cores

One way to tackle empty-core games and enforce the formation of the grand coalition is to make it more costly for proper coalitions to form by “taxing” their members. With a large enough tax, every TU-game will eventually have feasible payoff vectors which cannot be improved upon by any coalition. The literature on this type of approximate cores focuses on asymptotic results showing that, as the number of players grows, the tax needed to prevent an empty core converges to zero.

The approximate cores (see Shapley and Shubik 1966) are defined as follows. For every $\varepsilon \in \mathbb {R}$ the strong $\varepsilon$-core of (N, v) is

$$\begin{aligned} C^\varepsilon (N,v) :=\left\{ x\in \mathbb {R}^N \mid x(N) = v(N) \quad \text { and }\quad x(S) \ge v(S) - \varepsilon , \; \forall S \in \mathcal {N} \right\} \end{aligned}$$

and the per-capita (or weak) $\varepsilon$-core is

$$\begin{aligned} C_\varepsilon (N,v) :=\left\{ x\in \mathbb {R}^N \mid x(N) = v(N) \quad \text { and }\quad x(S) \ge v(S) - \varepsilon |S|, \; \forall S \in \mathcal {N} \right\} . \end{aligned}$$

Note that $C^{\varepsilon }(N, v) = C(N, v^{\varepsilon })$ and $C_{\varepsilon }(N, v) = C(N, v_{\varepsilon })$, where $(N, v^{\varepsilon })$ and $(N, v_{\varepsilon })$ are defined as follows: $v^{\varepsilon }(N) =v_{\varepsilon }(N)= v(N)$, $v^{\varepsilon }(S) = v(S)-\varepsilon ,$ and $v_{\varepsilon }(S) = v(S)-\varepsilon |S|$, for every $S\subsetneq N$. Then $C_{\varepsilon }(N, v) \ne \emptyset$ if and only if the game $(N,v_{\varepsilon })$ is balanced, which is equivalent to $\sum _{S \in \mathcal {B}} \lambda _S v(S) \le v(N) + n\varepsilon$ for every proper balanced family $\mathcal {B}$ with weights $(\lambda _S)_{S \in \mathcal {B}}$. A game (N, v) that satisfies this last property is said to be $\varepsilon$-balanced.

The strong least core Maschler et al. (1979) $\overline{LC}(N,v)$ (respectively per-capita least core $\underline{LC}(N,v)$Young et al. 1982) is defined as the intersection of all non-empty strong $\varepsilon$-cores (respectively per-capita $\varepsilon$-cores) of the game. Both least core concepts are non-empty for every TU-game.

Proposition 3.1

With the possible exception of the strong and per-capita least cores, every other non-empty $\varepsilon$-core violates ETP.

Proof

Define $\underline{\varepsilon }$ in such a way that $C_{\underline{\varepsilon }}(N,v)=\underline{LC}(N,v)$. Let $\underline{\varepsilon }<\varepsilon$ and choose $x \in \underline{LC}(N,v) \subsetneq C_{\varepsilon }(N,v)$. Then, for every $S\subseteq N$, $x(S)\ge v(S)-\underline{\varepsilon }|S|>v(S)-\varepsilon |S|.$ Pick two substitute players i and j and construct a new vector, $\tilde{x} \in \mathbb {R}^N$, by taking away an amount $\delta$ from $x_i$ and adding it to $x_j$. The above inequality ensures that, for small enough $\delta$, $\tilde{x}$ still belongs to $C_{\varepsilon }(N,v)$. It is then clear that either x or $\tilde{x}$ violates ETP. An analogous argument works for the strong version of the $\varepsilon$-core and its corresponding least core. $\square$

A similar argument shows that a necessary condition for the core to satisfy ETP is that v(N) be “tight” relative to the worth of proper coalitions or, in other words, that $v(N) = \sum _{S \in \mathcal {B}} \lambda _S v(S)$ for some balanced family $\mathcal {B}$, with weights $(\lambda _S)_{S \in \mathcal {B}}$ and $N \notin \mathcal {B}$. A related necessary condition for the equal treatment of equals at a core allocation, called strong-superadditivity, was proposed, in the context of market economies, by Green (1972). In Sect. 5 we show how our condition strengthens Green (1972) on the domain of quasi-linear economies. On the other hand, Zhao (2001) linked the “tightness” of v(N) to the non-emptiness of the core and its relative interior. As the following example illustrates, although necessary,“tightness” of v(N) is not sufficient for the equal treatment of equals.

Example 3.2

The following example shows that the strong and per-capita least cores may violate ETP. Consider the following game with set of players $N=\{1,2,3\}$. Let $v(1)=1$, $v(2) = v(3) = v(1,2) = v(1,3) =0$, and $v(2,3) = v(1,2,3) = 2$. Then $\overline{LC}(N,v) = \left\{ \left( \frac{1}{2},x,\frac{3}{2} - x\right) \in \mathbb {R}^3 \; \mid \; x \in \left[ -\frac{1}{2},2\right] \right\}$ and $\underline{LC}(N,v) = \left\{ \left( \frac{2}{3},x,\frac{4}{3} - x\right) \in \mathbb {R}^3 \; \mid \; x \in \left[ -\frac{1}{3}, \frac{5}{3}\right] \right\}$. Despite the fact that players 2 and 3 are substitutes, they may receive unequal allocations at either the strong or the weak least core. Note also that $\overline{LC}(N,v)=C(N, v^{\frac{1}{2}})$, $\underline{LC}(N,v) = C(N, v_{\frac{1}{3}})$ and both games, $v^{\frac{1}{2}}$ and $v_{\frac{1}{3}}$, are “tight”.

Lemma 3.3

Let two games $(N,v_1)$ and $(N,v_2)$ differ only in the worth they assign to the grand coalition. Then, $\underline{LC}(N,v_1)$ satisfies ETP if and only if $\underline{LC}(N,v_2)$ satisfies ETP.

Proof

We will show that $\underline{LC}(N,v_2) = \underline{LC}(N,v_1) + \left\{ \frac{1}{n} ( v_2(N) - v_1(N)) \mathbf 1_N\right\}$, and then the result follows. Let ${\underline{\varepsilon }}_i$ be such that $C_{\underline{\varepsilon }_i}(N,v)=\underline{LC}(N,v_i)$ for $i \in \{1,2\}$. By definition, $x \in \underline{LC}(N,v_1)$ if and only if:

$$\begin{aligned} x(N)= & {} v_1(N) \text { and } x(S) \ge v_1(S) - |S|\underline{\varepsilon }_1 \;\;\; \forall S \ne N\\ x(N)= & {} v_1(N) \text { and } x(S) + |S|(\underline{\varepsilon }_1-\underline{\varepsilon }_2)\ge v_2(S) - |S|\underline{\varepsilon }_2\;\;\; \forall S \ne N\\ y(N)= & {} v_1(N) + n(\underline{\varepsilon }_1-\underline{\varepsilon }_2) \text { and } y(S) \ge v_2(S) - |S|\underline{\varepsilon }_2\;\;\; \forall S \ne N \end{aligned}$$

where, for every $i \in N$, $y_i = x_i + \underline{\varepsilon }_1-\underline{\varepsilon }_2$. The $\varepsilon$-balancedness condition implies that $v_1(N) + n \underline{\varepsilon }_1 = v_2(N) + n \underline{\varepsilon }_2$ so that $\underline{\varepsilon }_1-\underline{\varepsilon }_2 = \frac{1}{n} ( v_2(N) - v_1(N))$. Finally, $y(N) = v_1(N) + n(\underline{\varepsilon }_1-\underline{\varepsilon }_2) = v_2(N)$. We conclude that $x \in \underline{LC}(N,v_1)$ iff $y = x + \frac{1}{n} (v_2(N) - v_1(N)) \mathbf 1_N \in \underline{LC}(N,v_2)$ as desired. $\square$

Given a game (N, v), let $M = \max \sum _{S \in \mathcal {B}}\lambda _S v(S)$ where the maximum is taken over all proper balanced families $\mathcal {B}$ with weights $(\lambda _S)_{S \in \mathcal {B}}$. Note that $M\ne \bar{v}(N)$ only if $Ess(N,v)=\emptyset$. Define then the game $(N,v_M)$ as $v_M(N)=M$ and $v_M(S)=v(S)$ for $S \ne N$.

Lemma 3.4

The per-capita least core and the core of $(N,v_M)$ coincide: $\underline{LC}(N,v_M)=C(N, v_M)$.

Proof

If $\varepsilon =0$ then $C_\varepsilon (N,v_M) = C(N,v_M)$ which is non-empty by definition of M. Also, if $\varepsilon$ is negative and $C_\varepsilon (N,v_M) \ne \emptyset$, $\varepsilon$-balancedness implies that, for every proper balanced family $\mathcal {B}$ with weights $(\lambda _S)_{S \in \mathcal {B}}$, $\sum _{S \in \mathcal {B}}\lambda _S v(S) \le M + n\varepsilon < M$, contradicting the definition of M. Therefore, $\underline{LC}(N,v_M) = C(N,v_M)$ as desired. $\square$

Even when the core is empty or it violates ETP, our characterization remains useful to analyze the per-capita least core.

Theorem 3.5

The per-capita least core of a game (N, v) satisfies ETP if and only if, for every class of substitute players $A \in \mathcal {A}$ with $|A| \ge 2$, there exists an essential coalition $S^*_A \in Ess(N,v_M)$ that contains at least one but not all members of A.

Proof

By Lemmas 3.3 and 3.4, $\underline{LC}(N,v)$ satisfies ETP iff $\underline{LC}(N,v_M)=C(N,v_M)$ satisfies ETP. Theorem 2.6 applied to $(N,v_M)$, together with the fact that $\mathcal {A}(N,v) = \mathcal {A}(N,v_M)$, finishes the proof. $\square$

Note that if $Ess(N,v) \ne \emptyset$, then $M=\bar{v}(N)$ and $Ess(N,v_M)=Ess(N,v)$. This could happen either if the game (N, v) is non-balanced, or if it is balanced and “tight.”

The following example shows that the condition of Theorem 3.5 is not necessary for the strong least core to satisfy ETP.

Example 3.6

Let (N, v) be the game defined by $v(\{1\})=2$, $v(\{2\})=v(\{3\})=0$, $v(\{1,2\})=v(\{1,3\})=6$, $v(\{2,3\})=8$, and $v(\{1,2,3\})=7$. Players 2 and 3 are substitutes. This game is non-balanced and, even though no member of $Ess(N,v) = Ess(N, v_M)= \{ \{1\}, \{2,3\} \}$ contains just one of them, the strong least core, $\overline{LC}(N,v) = \{(1,3,3) \}$, satisfies ETP.

3.2 Aspirations

The feasibility assumption of the core implies that the outcome of the game brings all players together to form the grand coalition. In many games, for example when the core is empty, this is not a reasonable assumption. The idea behind the concept of aspirations is to allow players to obtain their payoff via the formation of proper coalitions. The core-like competition between players to lure potential coalition members will lower their aspirations, refining the set of likely outcomes. This process leads to a new solution concept.

Definition 3.7

The aspiration core Bennett (1983) of the game (N, v) is defined as

$$\begin{aligned} AC(N,v):= \arg \min \left\{ x(N)\; | \; x \in \mathbb {R}^N, x(S)\ge v(S), \forall S\in \mathcal {N} \right\} . \end{aligned}$$

One important advantage of considering proper coalitions is expanding the applicability of core-based ideas to a considerably more general scope of situations. Indeed, we will show that our characterization remains valid for arbitrary TU-games via the aspiration core. The next proposition shows a number of useful properties of the aspiration core. For their proofs and discussion we refer the reader to Bennett (1983) and Bejan and Gómez (2009).

Proposition 3.8

Bennett (1983) For every game $(N,v) \in \Gamma$, the aspiration core satisfies the following:

• 1. $AC(N,v) \ne \emptyset$,

• 2. If $C(N,v) \ne \emptyset$, then $AC(N,v)= C(N,v)$,

• 3. $AC(N,v) = \{x\in \mathbb {R}^N \mid x(S) \ge v(S) \; \forall S \in \mathcal {N} \text { and } x(N) = \bar{v}(N) \}$.

Arribillaga (2015), working with the class of partitioning games, shows that, as a game is replicated sufficiently many times, the $\varepsilon$-core converges to the aspiration core as $\varepsilon$ goes to zero. Theorem 3.9 shows that the relation between these two solution concepts is far deeper, as it is not limited to either partitioning or large games. The literature seldom relates approximate cores with the aspiration approach. We establish the close link between these two, up to now seemingly far apart, branches of the literature.

Theorem 3.9

For every game (N, v) let $\varepsilon _0=\min \{\varepsilon \ge 0\;|\; C_\varepsilon (N,v)\ne \emptyset \}.$ Then, $C_{\varepsilon _0}(N,v) = AC(N,v) - \{ \varepsilon _0 \cdot \mathbf{1}_N\}$.

Proof

Define $\varepsilon ^*:=\frac{\bar{v}(N)-v(N)}{n}$. We prove first that $C_{\varepsilon ^*}(N,v) = AC(N,v) - \{ \varepsilon ^* \mathbf{1}_N \}$ and second that $\varepsilon ^*=\varepsilon _0$. Let $x \in AC(N, v)$ and define the payoff vector $x^* := x - \varepsilon ^*{\mathbf 1}_N$. Then

$$\begin{aligned} x \in AC(N,v)\iff & {} x(S) \ge v(S) \; \; \forall S \in \mathcal {N} \; \text { and } \; x(N) = \overline{v}(N),\\\iff & {} x^*(S) \ge v(S) - \varepsilon ^* |S| \; \; \forall S \; \text { and } \; x^*(N) + n\varepsilon ^* = \overline{v} (N),\\\iff & {} x^*(S) \ge v(S) - \varepsilon ^* |S| \; \; \forall S \; \text { and } \; x^*(N) = v(N),\\\iff & {} x^* \in C_{\varepsilon ^*}(N,v), \end{aligned}$$

and the first claim is proved. Non-emptiness of the aspiration core implies then that $C_{\varepsilon ^*}(N,v) \ne \emptyset$.

We show next that if $\varepsilon \ge 0$ and $C_\varepsilon (N,v)\ne \emptyset$, then $\varepsilon \ge \varepsilon ^*$. In such case the $\varepsilon$-balancedness condition implies that for every balanced family of coalitions $\mathcal {B}$ with associated weights $(\lambda _{S})_{S \in \mathcal {B}}$, $\sum _{S \in \mathcal {B}} \lambda _{S}v(S) \le v(N) + n \varepsilon .$ In particular, if $\mathcal {B}$ is an optimally balanced family, we have that $v(N) \ge \overline{v}(N) - \varepsilon n$ and, consequently, $\varepsilon \ge \frac{\overline{v}(N) - v(N)}{n} = \varepsilon ^*,$ as desired. $\square$

The previous proposition, which shows the bijection between the aspiration core and the per-capita $\varepsilon$-core, helps to clarify when the aspiration core satisfies ETP. In fact, the following theorem generalizes our main result to the entire family of TU-games.

Theorem 3.10

The aspiration core of a game (N, v) satisfies ETP if and only if, for every class of substitute players $A \in \mathcal {A}$ with $|A| \ge 2$, there exists an essential coalition $S^*_A$ that contains at least one but not all members of A.

Proof

If $C(N,v) \ne \emptyset$, then $AC(N,v) = C(N,v)$ and the result follows because of Theorem 2.6. If $C(N,v) = \emptyset$, then Theorem 3.9 delivers the result. $\square$

Example 3.11

Consider again the n-player bridge game, $(N, v^n_{br})$ (described in Example 2.2) for $n\ge 5$. In this case $C(N, v^n_{br}) \ne \emptyset$ only if n is a multiple of four. Still, the family of all 4-player coalitions of this game is an optimally balanced family (with all weights equal to ${n-1 \atopwithdelims ()3}^{-1}$) that satisfies the conditions of Theorem 3.10 and thus AC(N, v) satisfies ETP. In fact, for $n \ge 5$, $AC(N,v^n_{br}) = \{(\frac{1}{4}, \dots , \frac{1}{4}) \}$.

4 Applications

In this section we analyze the implications of our main result for different types of cooperative games.

4.1 Partitioning games

Partitioning games are those for which a set of “fundamental” coalitions determines the worth of every other coalition in the game. For example, the worth of any coalition is dictated by four-player coalitions in the bridge game and particular two-player coalitions in the gloves game. Partitioning games were first defined by Kaneko and Wooders (1982). The formal definition is given below.

Given a finite set of players N, let $\mathcal {F} \subseteq \mathcal {N}$ be a family of coalitions such that, for every $i \in N$, $\{i\} \in \mathcal {F}$. The elements of $\mathcal {F}$ are called basic coalitions. For every $S \in \mathcal {N}$ denote by $\Pi (S)$ the set of all partitions of S. A partition $\pi \in \Pi (S)$ is called an $\mathcal {F}$-partition of S if $\pi \subseteq \mathcal {F}$. Let $\Pi _{\mathcal {F}}(S)$ denote the set of $\mathcal {F}$-partitions of S.

Definition 4.1

Given a finite set of players N, a partitioning gameKaneko and Wooders (1982) with respect to the basic family $\mathcal {F} \subseteq \mathcal {N}$ is a super-additive game, denoted by $(N, \mathcal {F}, v)$, which satisfies, for every $S \in \mathcal {N}$,

$$\begin{aligned} v(S) := \max \left\{ \sum _{F \in \pi } v(F) \; | \; \pi \in \Pi _{\mathcal {F}}(S) \right\} .\ \end{aligned}$$

Clearly, every super-additive game is a partitioning game with respect to the basic family $\mathcal {F} = \mathcal {N}$. However, partitioning games that are of interest for applications are those whose families of basic coalitions are strict (and typically small) subsets of $\mathcal {N}$. For example, the bridge game (with an arbitrary number of players) is a partitioning game in which the family of basic coalitions consists of sets with at most four elements.

Lemma 4.2

Every partitioning game has an optimally balanced family containing only basic coalitions.

Proof

Let $\mathcal {B}$ be an optimally balanced family of coalitions with weights $(\lambda _S)_{S \in \mathcal {B}}$. For every $S \in \mathcal {B}$ there exists a partition $\pi (S) \in \Pi _{\mathcal {F}}(S)$ such that $v(S)= \sum _{F\in \pi (S)} v(F).$

Let $\mathcal {B}' = \bigcup _{S \in \mathcal {B}} \pi (S)$. It is enough to show that $\mathcal {B}' \subseteq \mathcal {F}$ is optimally balanced. Define, for every $F \in \mathcal {B}'$, $\lambda '_F= \sum _{\pi (S) \ni F} \lambda _S$. The family $\mathcal {B}'$ is balanced because, for every $i \in N$,

$$\begin{aligned} \sum _{F \in \mathcal {B}', F \ni i} \lambda '_F =\sum _{F \in \mathcal {B}', F \ni i} \; \; \sum _{\pi (S) \ni F} \lambda _S = \sum _{S \in \mathcal {B}, S \ni i} \lambda _S = 1. \end{aligned}$$

$\mathcal {B}'$ is also optimally balanced as

$$\begin{aligned} \sum _{F \in \mathcal {B}'} \lambda '_F v(F)= \sum _{F \in \mathcal {B}'} \sum _{\pi (S) \ni F} \lambda _S v(F)= \sum _{S \in \mathcal {B}} \sum _{F \in \pi (S)} \lambda _S v(F)=\sum _{S \in \mathcal {B}} \lambda _S v(S) = \bar{v} (N). \end{aligned}$$

This completes the proof. $\square$

Our next theorem provides a characterization of the basic families that is enough to guarantee that ETP is satisfied at any (aspiration) core allocation.

Theorem 4.3

Let $(N,\mathcal {F}, v)$ be a partitioning game such that no basic coalition contains an entire class $A \in \mathcal {A}$ with $|A| \ge 2$. Then the core (and more generally the aspiration core) of the game satisfies ETP. If the core is empty, the per-capita least core satisfies ETP.

Proof

By Lemma 4.2, there exists an optimally balanced family of basic coalitions $\mathcal {B}'$. Without loss of generality assume strictly positive weights $(\lambda '_S)_{S \in \mathcal {B}'}$ so that every proper member of $\mathcal {B}'$ is essential. For every $A\in \mathcal {A}$ such that $|A|\ge 2$, there is a basic coalition $F^* \in \mathcal {B}'$ such that $F^* \cap A \ne \emptyset$. As $F^*$ is basic, the assumption of the theorem implies that $F^*\cap A\subsetneq A$. Thus, $F^*$ is an essential coalition that contains some but not all the members of A. This procedure can be followed for every multi-player class $A \in \mathcal {A}$ so Theorem 2.6 (and 3.10) implies that the core (and the aspiration core) satisfies ETP. Finally, if the core is empty, Theorem 3.9 implies that the per-capita least core satisfies ETP. $\square$

The assumption of the previous theorem guarantees that the worth of every coalition can be obtained by forming smaller sub-coalitions, which do not include all members of any particular class of substitutes. The condition resembles, to some extent, Wooders (2010) “small group effectiveness”, which was proved to be sufficient for the near equal treatment of most players of the same type in sufficiently large games.

4.2 Assignment games

Among partitioning games, the so-called assignment games have a special place because of their relation to the matching literature. They were introduced by Shapley and Shubik, who also showed that two-sided assignment games (arising from two-sided matching markets) always have a non-empty core (see also Kaneko 1982). By contrast, m-sided assignment games with $m>2$ may have empty cores Quint (1991).

Definition 4.4

Given an integer $m \ge 2$, an m-sided assignment gameShapley and Shubik (1971) is defined as a partitioning game such that:

• 1. The set of players N can be partitioned into m disjoint assignment families of players, namely $(K_t)_{t = 1, \dots ,m}$.

• 2. The set of basic coalitions is defined as

  $$\begin{aligned} \mathcal {F} = \Big \{ \{i\} : i \in N \Big \} \cup \Big \{ S \in \mathcal {N} : |S \cap K_t| = 1 \; \forall t \Big \}. \end{aligned}$$

The following example shows that the set of classes of substitute players $\mathcal {A}$ and the set of assignment families $\{K_1, \dots , K_t\}$ need not be the same.

Example 4.5

Consider a real estate assignment game with three assignment families: buyers, sellers, and agents. Basic coalitions have a member of each family and are worth 1. Consider the game with one buyer, one seller and two realtors where $N=\{b,s,r_1,r_2\}$. Notice that $b \sim s$ and $r_1 \sim r_2$, so there are only two equivalence classes of substitute players. The core of this game does not satisfy ETP. Indeed, $C(N,v)=\{(a,1-a,0,0) \; | \; a \in [0,1]\}.$

In the previous example substitute players b and s, who are treated differently by core payoff vectors, belong to different assignment families. The following theorem generalizes this observation for general assignment games.

Theorem 4.6

The core (and more generally the aspiration core) of an m-sided assignment game satisfies ETP if every pair of subsitute players belongs to the same assignment family.

Proof

Let $(N, \mathcal {F}, v)$ be an m-sided assignment game with families $K_t$ such that $N = \bigcup _{t=1}^m K_t$. For every equivalence class $A \in \mathcal {A}$ with $|A| \ge 2$, choose two substitute players $i, j \in A$. By Lemma 4.2, there is an essential and basic coalition $F^* \in \mathcal {F}$ such that $i \in F^*$. Since, by assumption, i and j belong to the same assignment family and $F^*$ is basic, then $j \notin F^*$. Theorem 2.6 (and 3.10) implies then that the core (and the aspiration core) satisfies ETP. $\square$

4.3 Replica games

Definition 4.7

Given $r \ge 1$, the $r^{th}$ replica of the super-additive game (N, v) is defined as the partitioning game $(N_r,\mathcal {F}_r, v_r)$ (or simply $(N_r, v_r)$) where:

• (i) $N_r=N \times \{1, \dots , r \}$ and the typical player $(i, q) \in N_r$ is called the $q^{th}$ replica of player i.

• (ii) The profile function $\rho ^r: 2^{N_r} \longrightarrow \mathbb {Z}_+^{\mathcal {A}}$ is defined, for every $S_r \subseteq N_r$ and every $A \in \mathcal {A}$, as $\rho ^r_A(S_r): = \big |S_r \cap \{(i,q) \in N_r \; | \; i \in A\}\big |.$

• (iii) $\mathcal {F}_r:=\left\{ S_r \subseteq N_r | \exists S \in \mathcal {N} \text { such that } \rho ^r(S_r)=\rho (S)\right\} .$

• (iv) For every $S_r \in \mathcal {F}_r$, let $S \in \mathcal {N}$ be such that $\rho ^r(S_r)=\rho (S)$. Then $v_r(S_r) := v(S)$.

A few remarks are in order. First, the basic function $v_r: \mathcal {F}_r \longrightarrow \mathbb {R}$ is well-defined: if two coalitions $S, S' \in \mathcal {N}$ are such that, for some $S_r \subseteq N_r$, $\rho (S_r) = \rho (S) = \rho (S'),$ then $S \sim S'$ and $v_r(S_r)=v(S) = v(S')$. Also, super-additivity of the game (N, v) ensures that it coincides with its first replica $(N_1,v_1)$. Finally, notice that for every $S_r,T_r \in N_r$, $\rho ^r(S_r)=\rho ^r(T_r)$ implies $v_r(S_r)=v_r(T_r)$. Then we conclude that players $(i,q),(i',q')\in N_r$ are substitutes in the replica game if and only if i and $i'$ are substitutes in the original game. Thus, every equivalence class in $\mathcal {A}(N_r,v_R)$ is of the form $\{(i,q) \in N_r : i \in A\}$ for some $A \in \mathcal {A}(N,v).$

Similar replication techniques have been defined in the context of partitioning games. In our setting, the vector $\rho (S_r)$ has $|\mathcal {A}|$ coordinates, each of them counting the number of substitutes within an equivalence class $A \in \mathcal {A}$ contained in $S_r$. In Kaneko and Wooders (1982) and Arribillaga (2015), the vector $\rho (S_r)$ has |N| coordinates, each of them counting the number of replicas of a player $i \in N$ contained in $S_r$. If the original game contains no pairs of substitute players, the two definitions are equivalent. However, if players $i,j \in N$ are such that $i \sim j$, the next example shows that, according to Kaneko and Wooders (1982) definition, players (i, 1) and (j, 1) may fail to be substitutes in subsequent replicas.

Example 4.8

Consider the second replica of the 4-player Bridge Game. All players are substitutes in the original game, so any four-player coalition is basic. Thus, our second replication delivers the 8-player Bridge Game. With the Kaneko and Wooders (1982) and Arribillaga (2015) replication techniques,

$$\begin{aligned} v_r(\{(2,1),(2,2),(3,2),(4,2)\})=0 \end{aligned}$$

while

$$\begin{aligned} v_r(\{(1,1),(2,2),(3,2),(4,2)\})=1 \end{aligned}$$

and thus, even though $1 \sim 2$ in the original game, (1, 1) is not a substitute of (2, 1) in the $r^{th}$ replica for $r\ge 2$.

The role of the equal treatment property in this type of games is clear: it allows a direct comparison between solution concepts of replica games and solution concepts in the original game. The next result describes the behavior of the core as a TU-game is replicated.

Theorem 4.9

If $r \ge 2$, the core (and, more generally, the aspiration core) of the $r^{th}$ replica of a game satisfies ETP. Moreover, if the core is empty, the per-capita least core of the $r^{th}$ replica satisfies ETP.

Proof

For every equivalence class in the replica game, $A^r = \{(i,q) \in N_r \;|\; i \in A\}$, we have that $|A^r|=r|A|$. However, basic coalitions contain at most |A| players of $A^r$. Thus, the condition of Theorem 4.3 is satisfied, which implies the result. $\square$

A similar result, in the context of NTU-games was obtained by Wooders (1983) by imposing a condition related to ours, called the “minimum efficient scale.” While Wooders (1983) result applies to more general sequences of replicas than the ones described here, it only obtains the (almost) equal treatment of substitute players in the (aspiration) core allocations of sufficiently large games .

Our condition for ETP at core allocations and its link to replica games allows for more streamlined convergence results. Previous findings in the literature invariably referred to the equal treatment portion of the $\varepsilon$-core of the replica games. However, allowing players to collaborate across replicas with players of their same type implies that every vector in the per-capita least core treats substitute players equally.

Let (N, v) be a game, let $(N_r, v_r)_r$ be its sequence of replicas, and define the core subset $C^{ET}(N, v):=\{x\in C(N, v)\;|\; x \text { satisfies ETP }\}$. For every $x\in \mathbb {R}^n$, denote by $x^r \in \mathbb {R}^{rn}$ its $r^{th}$ replica defined as $x^r(i,q)=x_i$, for every $i \in N$ and every $q \in \{1, \dots , r\}$. The next proposition shows that the allocations in the core of a replica game can be naturally embedded in the core of the original game. In fact, all payoff vectors that violate ETP are eliminated as early as the second replica.

Theorem 4.10

Considered a balanced game (N, v). For every $r\ge 2$, the core of its $r^{th}$ replica is the $r^{th}$ replica of the subset of the core that satisfies ETP. In other words, $C(N_r, v_r) = \{x^r \in \mathbb {R}^{rn} \;|\; x \in C^{ET}(N, v) \}$.

Proof

Step 1: $C(N_r, v_r) \subseteq \{x^r \in \mathbb {R}^{rn} \;|\; x \in C^{ET}(N, v) \}$

Let $x_r \in C(N_r, v_r)$ and define $\bar{x} \in \mathbb {R}^n$ as $\bar{x}_i:=x_r(i,1)$, for every $i \in N$. By Theorem 4.9, $x_r$ satisfies ETP in $(N_r,v_r)$ and, therefore, $x_r = \bar{x}^r$ and $\bar{x}$ satisfies ETP in the original game. It suffices then to show that $\bar{x} \in C(N, v)$.

For every coalition $S \subseteq N$, define $S_1 = \bigcup _{i \in S} \{(i,1)\} \subsetneq N_r$. Then $\bar{x}(S) = x_r(S_1) \ge v_r(S_1) = v(S),$ which shows that $\bar{x}$ is stable in (N, v). We show next that $v_r(N_r)=rv(N)$, which implies that $\bar{x}(N)=\frac{1}{r} x_r(N_r) = \frac{1}{r} v_r(N_r)=v(N)$, and thus concludes the first part of the proof.

Consider the partition of $N_r$ into the r replicas of the set N, that is, the family $\left\{ \bigcup _{i \in N} \{(i,t)\} | t=1,\dots , r\right\}$. Then $v_r(N_r) \ge \sum _{t=1}^r v_r(\bigcup _{i \in N} \{(i,t)\}) = rv(N)$. On the other hand, there is a partition of basic coalitions $\pi (N_r) \in \Pi (N_r)$ such that $v_r(N_r) = \sum _{T_r \in \pi (N_r)} v_r(T_r)$. For every $T_r \in \pi (N_r)$ choose a coalition $T \subset N$ such that $\rho ^r(T_r) = \rho (T)$. Notice that the family of such coalitions T is balanced with weights equal to $\frac{1}{r}$. Then, the fact that the original game is balanced implies that $v_r(N_r) = \sum _{T_r \in \pi (N_r)} v_r(T_r) = \sum _T v(T) = r\sum _T \frac{1}{r} v(T) \le rv(N).$

Step 2: $\{x^r \in \mathbb {R}^{rn} \;|\; x \in C^{ET}(N, v) \} \subseteq C(N_r, v_r)$

Let $x \in C^{ET}(N, v)$. We know that $x^r(N_r) = rv(N) = v_r(N_r)$. For every $S_r \subseteq N_r$ there is a partition of basic coalitions $\pi (S_r) \in \Pi (S_r)$ such that $v_r(S_r) = \sum _{T_r \in \pi (S_r)} v_r(T_r)$. For every $T_r \in \pi (S_r)$ choose a coalition $T \subset N$ such that $\rho ^r(T_r) = \rho (T)$. Then $v_r(S_r) = \sum _{T_r \in \pi (S_r)} v_r(T_r) = \sum _T v(T) \le \sum _T x(T)$. As x satisfies ETP in (N, v), $v_r(S_r) \le \sum _T x(T) = \sum _{T_r \in \pi (S_r)} x^r(T_r) = x^r(S_r),$ as desired. $\square$

The next result extends Theorem 4.10 to the family of non-balanced games.

Theorem 4.11

If a game (N, v) is not balanced, then

$$\begin{aligned} \lim _{r \rightarrow \infty } \underline{LC}(N_r, v_r) = \left\{ x^r \in \mathbb {R}^{rn} \; | \; x \in AC^{ET}(N,v) \right\} . \end{aligned}$$

Proof

Let $\underline{\varepsilon }_r$ be such that $\underline{LC}(N_r, v_r) = C_{\underline{\varepsilon }_r}(N_r, v_r)$. Since the original game has an empty core, $\underline{\varepsilon }_r > 0$. By Theorem 3.9, we then know that $\underline{LC}(N_r, v_r) = AC(N_r, v_r) - \{\underline{\varepsilon }_r \cdot \mathbf 1_N \}$ and $\underline{\varepsilon }_r = \frac{\bar{v}_r(N_r) - v_r(N_r)}{rn}$. On the other hand, the arguments in the proof of Theorem 4.10 can be generalized to show that $AC(N_r, v_r)=\{ x^r \in \mathbb {R}^{rN} \; | \; x \in AC^{ET}(N,v) \}.$ Hence, all that remains to be proved is that $\lim _{r \rightarrow \infty } \underline{\varepsilon }_r =0$.

We know that $\bar{v}(N) = \sum _{S \in \mathcal {B}} \lambda _Sv(S)$ for some balanced family of coalitions $\mathcal {B}$ and (rational) weights $\lambda _S$. Let m be the least common denominator of all the balancing weights. Then:

$$\begin{aligned} m\bar{v}(N) = \sum _{S \in \mathcal {B}} k_S v(S), \end{aligned}$$

where the integers $(k_S)_{S\in \mathcal {B}}$ satisfy $\sum _{S \ni i, S \in \mathcal {B}} k_S = m$ $\forall i \in N$. This shows a way of arranging the m (or any multiple of m) replicas of N so that $\bar{v}_m(N_m) = v_m(N_m)$.

Let $r=am+b$ where a and b are integers and $0 \le b < m$. Then

$$\begin{aligned} \underline{\varepsilon }_r = \frac{\bar{v}_r (N_r) - v_r(N_r)}{rn} \le \frac{\bar{v}_r (N_r) - \bar{v}_{am}(N_{am})}{rn} =\frac{b \bar{v} (N)}{rn}, \end{aligned}$$

which converges to zero as r grows large. $\square$

5 ETP in the core of quasi-linear economies

We show next that Theorem 2.6, when applied to the TU-game associated with a quasi-linear pure-exchange economy, is closely related to Green (1972) necessary condition for ETP.

Consider a pure-exchange economy with L consumption goods indexed by $l=1,\ldots ,L$ and a medium of exchange, called money, which is used to make transfers. The economy is populated by a finite set of agents N, which is partitioned into disjoint classes $A \in \mathcal {A}$ such that $\bigcup _{A \in \mathcal {A}} A = N$. All agents within a class A have identical preferences and endowments represented by the utility function $U^A: \mathbb {R} \times \mathbb {R}_+^L \rightarrow \mathbb {R}$ with $U^A(m, y)=m+u^A(y)$ and $u^A:\mathbb {R}_+^L\rightarrow \mathbb {R}$ continuous and strictly concave, and, respectively, the vector $\omega ^A \in \mathbb {R}_{++}^L$. There is no endowment of money. Such economy is denoted by $[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$.

For every coalition of agents $S \subseteq N$, define an allocation for S as a vector $(m,y) \in \mathbb {R}^{|S|}\times \mathbb {R}_+^{|S|L}$ that assigns the bundle of goods and transfers $(m^i, y^i) \in \mathbb {R} \times \mathbb {R}^{L}_+$ to every agent $i \in S$. An allocation (m, y) is said to be feasible for S if $\sum _{i \in S} y^i = \sum _{i \in S} \omega ^i$ and $\sum _{i \in S} m^i = 0$. An allocation (m, y) for N can be improved upon by a coalition $S \subseteq N$ if there exists a feasible allocation $(\hat{m},\hat{y})$ for S such that, for every $i \in S$, $U^i(\hat{m}^i, \hat{y}^i) \ge U^i(m^i, y^i)$, with strict inequality for some $j \in S$. The core of the economy is the set of allocations that cannot be improved upon by any coalition $S \subseteq N$ and it is denoted by $C[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$. The core satisfies the equal treatment property if and only if, for every $(m,y) \in C[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$, every $A \in \mathcal {A}$ and every $i,j \in A$, $(m^i,y^i)=(m^j,y^j)$.

A Walrasian equilibrium of $[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$ is a vector $(p^*, (m^*,y^*)) \in \mathbb {R}_+^L \times \mathbb {R}^n\times \mathbb {R}_+^{nL}$ such that

• (i) For every $A \in \mathcal {A}$ and every $i \in A$, $(m^{*i}, y^{*i})$ maximizes $U^A$ over the budget set $\{(m,y)\in \mathbb {R}\times \mathbb {R}_+^{L}\;|\; m+p^* y \le p^* \omega ^A\}$.

• (ii) $\sum _{i \in N} y^{*i} = \sum _{A \in \mathcal {A}} |A|\omega ^A$ and $\sum _{i \in N} m^{*i} =0$.

Our assumptions guarantee the existence of a Walrasian equilibrium. Also, every equilibrium allocation belongs to the core of the economy.

A subeconomy of $[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$ is an economy $[S, (u^{A}, \omega ^{A})_{\{A \in \mathcal {A} | A\cap S\ne \emptyset \}}]$ consisting of a subset of agents $S \subsetneq N$ who inherit their utility functions and endowments from the original economy.

Theorem 5.1

The core of the economy $[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$ satisfies ETP if and only if, for every $A \in \mathcal {A}$ with $|A| \ge 2$, there exists a coalition $S^*_A \subsetneq N$ which contains at least one but not all members of A, and a price $p^* \in \mathbb {R}^L_+$ which is an equilibrium vector for the subeconomy $[S^*_A, (u^{A }, \omega ^{A})_{\{A \in \mathcal {A}| A\cap S^*_A\ne \emptyset \}}]$ as well as its complement, $[N {\setminus } S^*_A, (u^{A}, \omega ^{A})_{\{A \in \mathcal {A}| A \cap (N {\setminus } S^*_A)\ne \emptyset \}}]$.

Proof

For every non-empty coalition $S \subseteq N$ define its worth as

$$\begin{aligned} v(S)= \max _{y\in \mathbb {R}^{L |S|}_{++}}\left\{ \sum _{i \in S} u^i(y^i)\;|\;\sum _{i \in S} y^{i} = \sum _{i\in S} \omega ^i \right\} \end{aligned}$$

Clearly, for every $A \in \mathcal {A}$ and every $i, j \in A$, players i and j are substitutes in the associated game (N, v). Moreover, since each $u^A$ is strictly concave, $C[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$ satisfies ETP if and only if C(N, v) does. This allows us to use our TU-game characterization to prove the result.

Sufficiency: Fix a class $A\in \mathcal {A}$ and let $S_A^*$ be the coalition satisfying the hypotheses of the theorem. Then, according to Theorem 2.6, it is enough to prove that $\{S_A^*, N {\setminus } S_A^* \}$ is an optimally balanced family, which amounts to proving that $v(S_A^*)+v(N {\setminus } S_A^*)=v(N)$.

For any $p\in \mathbb {R}_+^L$, let $D^i(p) \in \mathbb {R} \times \mathbb {R}_+^{L}$ denote agent i’s demand at price p. Since preferences are strictly convex, the demand is single-valued. Let $p^*$ be an equilibrium price vector for $[S_A^*, (u^B, \omega ^B)_{\{B \in \mathcal {A}| B\cap S_A^*\ne \emptyset \}}]$ and $[N {\setminus } S_A^*, (u^B, \omega ^B)_{\{B \in \mathcal {A}| B\cap (N{\setminus } S_A^*)\ne \emptyset \}}]$. Then $p^*$ is also an equilibrium price vector for $[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$. Using the first welfare theorem we have that

$$\begin{aligned} v(S_A^*) + v(N {\setminus } S_A^*)= & {} \sum _{i \in S_A^*} U^i(D^i(p^*)) + \sum _{i \in N {\setminus } S_A^*} U^i(D^i(p^*))\\= & {} \sum _{i \in N} U^i(D^i(p^*)) = v(N), \end{aligned}$$

as we wanted.

Necessity: Suppose that the core of the economy $[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$ satisfies ETP. Let $(p^*,(m^*, y^*))$ be a Walrasian equilibrium for economy $[N, (u^A, \omega ^A)_{A \in \mathcal {A}}]$. Then, the payoff vector $x^* \in \mathbb {R}^N$, defined for every $i \in N$ as $x^{*i} = U^i(m^*, y^{*i})$, belongs to C(N, v). Since C(N, v) satisfies ETP, Theorem 2.6 implies that, for every $A \in \mathcal {A}$ such that $|A| \ge 2$, there exists an essential coalition $S^*_A$ which contains at least one but not all members of A.

Since $S^*_A$ is essential, there exists an allocation (m, y) which is feasible for $S^*_A$ and satisfies $x^*(S^*_A) = v(S^*_A) = \sum _{i \in S^*_A} u^i(y^i)$. Define then a new allocation $(\hat{m}, \hat{y})$ for $S^*_A$ as follows. For every $i \in S^*_A$, let $\hat{y}^i = y^i$ and $\hat{m}^i = x^{*i} - u^i(y^i)$. Notice that $(\hat{m}, \hat{y})$ is feasible for $S^*_A$ and, for every $i \in S^*_A$, $U^i(\hat{m}^i, \hat{y}^i) = U^i(m^{*i}, y^{*i})$. Strict concavity of utilities implies then that

$$\begin{aligned} \hat{m}^i+p^*\hat{y}^i \ge m^{*i}+p^*y^{*i}, \end{aligned}$$

with equality if and only if $\hat{y}^i = y^{*i}$ and $\hat{m}^i = m^{*i}$. Summing up these inequalities over $i \in S^*_A$ and using Walras’ law we obtain that each inequality must hold with equality and thus $(\hat{m}^i, \hat{y}^i)=(m^{*i}, y^{*i})=D^i(p^*)$. This implies that the vector $(m^{*i}, y^{*i})_{i \in S^*_A}$ is feasible for $S^*_A$ and, therefore, that $(m^{*i}, y^{*i})_{i \in N {\setminus } S^*_A}$ is feasible for $N {\setminus } S^*_A$. We conclude that $p^*$ is a price equilibrium vector for both the subeconomy $[S^*_A, (u^{A }, \omega ^{A})_{\{A \in \mathcal {A}| A\cap S^*_A\ne \emptyset \}}]$ and its complementary subeconomy. $\square$

The necessity of the condition is equivalent to the conclusion of Lemmas 1 and 2 in Green (1972). Sufficiency is a new result. Therefore, we proved that Green (1972) necessary condition is “almost” tight, in the sense that it is also sufficient for the core allocations to satisfy ETP if the economy is quasi-linear.