An Adaptive Model of Demand Adjustment in Weighted Majority Games

Abstract

This paper presents a simple adaptive model of demand adjustment in cooperative games and analyzes this model in weighted majority games. In the model, a randomly chosen player sets her demand to the highest possible value subject to the demands of other coalition members being satisfied. This basic process converges to the aspiration set. By introducing some perturbations into the process, we show that the set of separating aspirations, i.e., demand vectors in which no player is indispensable in order for other players to achieve their demands, is the one most resistant to mutations. We then apply the process to weighted majority games. We show that in symmetric majority games and in apex games, the unique separating aspiration is the unique stochastically stable one.

1. Introduction

Consider a situation in which there are three players, any pair of players can cooperate and generate 30 money units but the addition of the third player to the pair does not bring additional benefits. The situation can be seen as a weighted majority game with three symmetric players dividing a budget: two are enough to form a coalition and agree on a division; the third player’s participation does not increase the budget. Each of the three players may formulate a payoff demand, with the understanding that the player is willing to join any coalition that satisfies the demand. A coalition can only form if the demands of its members are satisfied. Clearly, not all demand combinations are equally stable. If the first two players make a demand of 15 and the third player makes a demand of 20, the third player will find that no coalition can satisfy her demand and may reduce it. Similarly, if the first two players make a demand of 15 and the third player makes a demand of 10, the third player may realize that it is possible to increase her demand and still find coalitions that can satisfy it. Demand combinations such that each player makes the highest demand that can still be satisfied are called aspirations in the literature on cooperative games. (The terminology comes from Bennett [1]; earlier papers on aspirations include [2,3].)

Even if we restrict ourselves to the set of aspirations, not all demand combinations appear equally stable. For example, suppose the first two players demand 20 each whereas the third player demands 10. There are two feasible coalitions, both of which contain the third player. Because the third player is indispensable, we expect her to be able to increase the demand. There are several solution concepts defined on the space of aspirations, all of which assume that competition for scarce players will drive their price (demand) up. The main ones are the set of partnered aspirations [1,3] and the set of balanced aspirations, also known as the aspiration core [2].

The research agenda of making connections between cooperative solution concepts and noncooperative games is known as the Nash [4] program. Our paper contributes to this approach by explicitly modeling the process of adjustment of players’ demands in a multilateral Nash demand game with the aim of providing foundations for one of the aspiration solution concepts. The game is played repeatedly, but players are myopic and do not take into account the effect of their decisions on future periods. The way in which we model demand adjustment is that, at every period, a player is randomly chosen and “selects from the whole set of feasible coalitions that one which will give him the highest possible return given the demands or payoff expectations of the necessary allies” (Cross [2], p. 185). In doing so, the player’s demand is adjusted to the residual value after paying the coalition partners’ demands. This type of myopic best-response adjustment in cooperative games is analyzed in Bennett et al. [5], who show that processes of this kind converge to the set of aspirations.

To be able to select a subset of the set of aspirations, we introduce small mutations into the process. In particular, we assume that with a small probability, a player experiments with a different demand, which is most likely to be a higher demand than the original one. We look for the set of aspirations that is stochastically stable (see, e.g., [6]) under such mutations. If a set of aspirations is stochastically stable, the process spends most of the time in this set as the probability of mutations becomes small. Intuitively, if getting out of the set requires more mutations than reaching the set from outside, the set is stochastically stable. We find that the set of aspirations that is robust to the mutation of one player coincides with the set of separating aspirations (a subset of partnered aspirations). In a separating aspiration, no player is indispensable to another player; each player’s demand can be satisfied by several coalitions. Thus, separating aspirations are the prime candidates for being stochastically stable.

The literature on demand adjustment in cooperative games (reviewed in Section 6 of [7] and discussed further in Section 2) uses similar adaptive processes but focuses on games with a nonempty core. In contrast, we study a particular class of games with an empty core, weighted majority games (the example at the beginning of the introduction is an example of such a game). Unlike the core, aspiration solution concepts are non-empty in these games, thus allowing predictions to be made about possible outcomes. Within this class, we show that in symmetric majority games and in apex games, there is a unique stochastically stable aspiration, which coincides with the unique separating aspiration.

The next section discusses the related literature. In Section 3, we describe the concept of aspirations and its variants in (transferable utility) cooperative games and define our dynamic process of demand adjustment. We also state useful auxiliary results about the process. In Section 4, we focus on weighted majority games, stating our main results about the stochastic stability of separating aspirations in symmetric majority games and in apex games. We conclude the section with examples of other weighted majority games in which there are sets of aspirations among which the process can move with mutations of one player, never reaching a separating one. Section 5 provides overall conclusions.

2. Related Literature

The starting point of our model is Cross [2], who presents a first attempt to formalize the competition for players whose “price” (as represented by their demand) is too low. This competition can be thought of as driving prices up for players that are indispensable for others to satisfy their demand. This concept underlies the approach used in Maschler and Peleg [8] for payoff vectors feasible for the grand coalition and in Albers [3] and Bennett [1] for more general payoff vectors.

Treating players’ behavior as setting a demand has an obvious connection with Nash’s [4] demand game that models two-player bargaining. Young [9] is the first who considers a process of best responding (to finite samples of past observations) in this game. He also introduces mutations into the process and finds that the payoff division related to the Nash bargaining solution is the unique stochastically stable one. Bennett et al. [5] apply a similar best-response process to general cooperative games, although they do not allow mutations. Their process converges to the whole set of aspirations. Since then, other papers have analyzed dynamic processes in cooperative games, as reviewed in Section 6 of the survey paper [7]. The most relevant of these papers are also discussed below.

Several papers in this literature study demand adjustment processes in cooperative games (from [10,11] to more recent [12,13,14,15,16,17,18]). While these papers differ in the details of the process (such as whether adjustment by coalitions is allowed, whether players only set a demand or also specify coalition partners, or which (if any) mutations are more likely), they all focus on games with a non-empty core. Payoff allocations in the core are obtained by the adjustment process, with the possibility of mutations allowing in some cases further selection within the core, as in [13,15,17]. Other papers, such as [19,20,21,22,23] obtain similar results for assignment games and matching problems with non-empty core.

The one paper that has a result for games with an empty core is Nax [18], whose process cycles through all coalition structures (including the one with all players being singletons) in such games. (In Nax [18], players’ individual demands are called their “aspirations”, not the whole demand vectors, as in Bennett [1] and in our paper.) The mechanism relies on joint deviations by coalitions: in the process, with a positive probability, any (potentially profitable) coalition can be selected to adjust demands jointly, but demands are made individually and may be incompatible, in which case the players split into singletons. In contrast, in the (basic) process used in this paper (which is based on [5]), only one player makes adjustments at a time, and a coalition always forms. We find that in important classes of weighted majority games, only minimal winning coalitions form in stochastically stable states.

Our model is closely related in spirit to the above-mentioned models. In common with those models, players adjust myopically, taking into account the current demands of other players. Furthermore, in common with the above models, we have that not all players adjust simultaneously (in our case only one player adjusts at a time, while some of the other papers allow adjustment by larger coalitions of players). In contrast with the literature, the adjusting player can guarantee himself a place in a coalition, by satisfying the demands of the other coalition members. We further allow for mutations, which are more likely to be demand increases (in the spirit of “intentional mistakes” in [24]). Also in contrast to the literature, we focus on weighted majority games, which have an empty core. For some classes of such games, our model allows quite a sharp prediction, selecting among aspirations those that are separating.

3. The Model

3.1. Aspirations in Cooperative Games

Let $(N,v)$ be a transferable-utility cooperative game, where $N=\{1,2,\dots ,n\}$ is the set of players and $v:2^N\to \mathbb{R}$ with $v(⌀)=0$ is the characteristic function. Any subset S of the player set N is called a coalition. We assume that the game is zero-normalized, $v\left(\right\{i\left\}\right)=0$ for all $i\in N$. A demand vector is an n-tuple $x=(x_1,\dots ,x_n)\in {\mathbb{R}}_{+}^n$. Let $x\left(S\right):={\sum }_{i\in S}{x}_i$. The following concepts will be useful:

Definition 1.

A demand vector x is an aspiration if it is maximal ($x\left(S\right)\ge v\left(S\right)$ for all S) and feasible (for all i, there exists $S\ni i$ such that $x\left(S\right)\le v\left(S\right)$).

Definition 2.

For given aspiration x, the generating collection $GC\left(x\right)=\{S:x(S)=v(S\left)\right\}$ is the set of coalitions that can satisfy the demands of their members.

With some demand vectors (aspirations), one player, i, may be able to satisfy his demand only if coalitions that satisfy this demand also include one particular another player, j, while player j can satisfy her demand without player i. The following defines aspirations where this cannot happen. Let $\mathcal{C}$ be a collection of coalitions. For each $i\in N$, let $C_i=\{S\in \mathcal{C}:i\in S\}$.

Definition 3.

A collection $\mathcal{C}$ of coalitions is partnered if $C_i$ is nonempty for all i and for any i, j in N:

$C_i\subseteq C_j\Rightarrow C_j\subseteq C_i.$

Definition 4.

An aspiration x is partnered if $GC\left(x\right)$ is partnered.

There are two ways in which an aspiration can be partnered: either both i and j need each other (in which case $C_i=C_j$) or none of the two players need each other (in which case $C_i\backslash C_j$ and $C_j\backslash C_i$ are both nonempty). The latter of these conditions will be important in our analysis.

Definition 5.

A collection $\mathcal{C}$ of coalitions is separating if $C_i\backslash C_j$ and $C_j\backslash C_i$ are both nonempty for any $i,j$.

Definition 6.

An aspiration x is separating if $GC\left(x\right)$ is separating.

In a separating aspiration, any pair $i,j$ of players are “separated” in the sense that each of them can find a coalition to satisfy their demand without the other player. Clearly, being separating is a stronger concept for an aspiration than being partnered (indeed, unlike the set of partnered aspirations, the set of separating aspirations can be empty in general games). The term “partnered” comes from Bennett [1]. Payoff vectors that we call “separating” are called “completely separating” in Maschler and Peleg [8] but are referred to as “minimally partnered” in Reny et al. [25] (in both these papers the focus is on demand vectors feasible for the grand coalition N of all players, whereas we consider aspirations, which are not necessarily feasible for N.) We think that “separating” is a better term, emphasizing that any pair of players do not depend on each other, i.e., can be separated.

Another concept that will be useful is the following:

Definition 7.

An aspiration x is balanced if x solves the problem

$\begin{array}{c}{\mathit{min}}_x\sum _{i\in N}{x}_i\\ s.t.x\left(S\right)\ge v\left(S\right)\mathit{for}\mathit{all}S\subseteq N.\end{array}$

The term “balanced” is from Bennett [1], although the concept itself is introduced in Cross [2]. It is particularly useful for the weighted majority games that we study.

3.2. The Basic Demand Adjustment Process

The process works as follows. Time is discrete: $t=1,2,\dots$. At the beginning of any period t, there is a vector of demands $x^{t-1}=(x_1^{t-1},\dots ,x_n^{t-1})$; we will drop the superscript when no confusion arises. At $t=1$, vector $x^0$ is exogenously given; at $t>1$, $x^{t-1}$ emerges from the previous period as described below. One of the players is randomly chosen to adjust his demand. We assume that all players have a non-zero probability to be chosen. We can think of the chosen player as proposing a coalition; the assumption of one randomly chosen proposer is common in the coalition formation literature (see Baron and Ferejohn [26]). The chosen player searches for the coalition that leaves him the highest payoff, provided that the demands of all other players in the coalition are satisfied. That is, the player solves

(1)$\underset{S:i\in S}{max}\{v\left(S\right)-x(S\backslash i)\}.$

Denote the maximum value for the above problem by $y_i$. Note that $y_i\ge 0$, since player i can always choose $S=\left\{i\right\}$, in which case $v\left(S\right)-x(S\backslash i)=0$. Player i proposes one of the coalitions that solve the maximization problem, say coalition Q, and sets a demand equal to $y_i$. (In particular, if no coalition involving other players is feasible given their demands, player i forms a singleton coalition and sets $y_i=v\left(\left\{i\right\}\right)=0$.) Hence the new vector of demands is $x^t=(x_1^t,\dots ,x_n^t)$, where $x_i^t=y_i$ and $x_j^t=x_j^{t-1}$ for $j\ne i$. We assume that all coalitions that solve the maximization problem are proposed with a positive probability. The actual payoffs to the players at period t are

(2)$u_j^t=\left\{\begin{array}{c}{x}_j^t\mathrm{for}j\in Q,\\ 0\mathrm{for}j\notin Q,\end{array}\right.$

i.e., players in Q get their demands, while players outside Q receive nothing. The state of the process at the end of period t is described by the demand vector $x^t=(x_1^t,\dots ,x_n^t)$. We refer to a state as an aspiration state if $x^t$ is aspiration.

Player i’s behavior can be described as adaptive in that i plays a best response to the other players’ past choices. Since the other players are not able to change their demands in the current period, we can also view i’s decision as rational (though myopic, since the effect of actions on future periods is not taken into account). We interpret coalition Q as a transitory arrangement that exists for period t only; it plays no role in subsequent decisions of the players.

We will denote by $\mathrm{\Psi }$ the correspondence that, for a given state $x^t$ at time t, assigns the set of states that can result at time $t+1$ with positive probability according to the process described above, so that $\mathrm{\Psi }\left(x\right)$ denotes the set of states that can be reached from x in one step.

Let $\mathcal{S}$ be the set of all possible states of the process. Given $\mathcal{A}\subseteq$$\mathcal{S}$, $\mathrm{\Psi }\left(\mathcal{A}\right):={\cup }_{x\in \mathcal{A}}\mathrm{\Psi }\left(x\right)$ is the set of states that can be reached in one step from a state in the set $\mathcal{A}.$

Definition 8.

A set of states $\mathcal{A}\subseteq$$\mathcal{S}$ is absorbing if $\mathrm{\Psi }\left(\mathcal{A}\right)=\mathcal{A}.$ An absorbing set $\mathcal{A}$ is minimal if no strict subset of $\mathcal{A}$ is absorbing.

Definition 9.

The absorbing set solution is the union of all minimal absorbing sets.

A set of states is absorbing if, starting from a state in this set, the process cannot get out of the set. The absorbing set solution contains all the long-run outcomes of the process since the process will eventually reach one of the minimal absorbing sets starting from outside the absorbing set solution (if this was not the case, the complement of the absorbing set solution would also be absorbing; therefore, it would contain a minimal absorbing set that would have to be included in the absorbing set solution, a contradiction). We have taken the term absorbing set solution from Inarra et al. [27]; this concept also appears in [28] as dynamic solution.

We now show that the absorbing set solution for this process coincides with the set of all aspirations. Given a demand vector x, player i’s demand is not feasible if $x\left(S\right)>v\left(S\right)$ for all $S\ni i$. Player i’s demand is not maximal if there exists $S\ni i$ such that $x\left(S\right)<v\left(S\right)$.

Lemma 1.

Let $x^{t-1}$ be the demand vector at $t-1$. Suppose i is randomly selected at time t to adjust his demand. Then:

• (i) 

  If player i’s demand $x_i^{t-1}$ is not feasible, $x_i^t<x_i^{t-1}.$

• (ii) 

  If player i’s demand $x_i^{t-1}$ is not maximal, $x_i^t>x_i^{t-1}.$

Proof. 

Player i always sets $x_i^t={max}_{S:i\in S}\{v\left(S\right)-x^{t-1}(S\backslash i)\}$ (recall that this value is always nonnegative because i can always choose $S=\left\{i\right\}$).

• (i). Because ${max}_{S:i\in S}\{v\left(S\right)-x^{t-1}(S\backslash i)\}<x_i^{t-1}$ (given that $x_i^{t-1}$ is not feasible), it follows that $x_i^t<x_i^{t-1}$.

• (ii). Because ${max}_{S:i\in S}\{v\left(S\right)-x^{t-1}(S\backslash i)\}>x_i^{t-1}$ (given that $x_i^{t-1}$ is not maximal), it follows that $x_i^t>x_i^{t-1}$.

 □

Our process is therefore a variant of the process of Bennett et al. [5], since the demand adjustment part of it satisfies their three assumptions:

• (i). only one player adjusts at a time;

• (ii). a player will increase his demand if some coalition can support the larger demand, given the demands of others;

• (iii). a player will decrease his demand if no coalition can support his current demand, given the demands of others.

Note that Bennett et al. [5] assume that demands adjust in this way, but they do not make any explicit assumptions about coalition formation. Since our demand adjustment satisfies their three assumptions, the results of [5] that demands converge to the set of aspirations also hold in our model. That only one player adjusts at a time justifies the underlying myopic rationality of choosing the coalition with the maximum available surplus, which simplifies proofs considerably. (It is sufficient for the results of this section that the players have independent positive probability of adjustment in each period, which implies inertia in the process, as, e.g., in [16]. On the other hand, if all players adjust simultaneously, then the process can cycle, never reaching an aspiration because all players simultaneously lower or raise their demands.)

Proposition 1.

If $x^t$ is an aspiration, $x^{t+1}=x^t$.

Proof. 

Consider any state $x^t$ that is an aspiration. Suppose player i is randomly chosen at period $t+1$ to adjust his demand. By feasibility, there exists $S\ni i$ such that $x^t\left(S\right)=v\left(S\right),$ or equivalently $v\left(S\right)-x^t(S\backslash i)=x_i^t$. By maximality, any coalition $Q\ni i$ satisfies $v\left(Q\right)-x^t\left(Q\right)\le 0$, which implies $v\left(Q\right)-x^t(Q\backslash i)\le x_i^t$. From these two conditions it follows that $y_i=x_i^t$. Then player i proposes some coalition S that leaves $x_i^t$ to him, thus $x_i^{t+1}=x_i^t$. The demands of the other players do not change, and therefore $x^{t+1}=x^t$. □

It follows that the set of aspirations is absorbing. Indeed, each aspiration vector x is a minimal absorbing set. The following proposition shows that there are no other minimal absorbing sets, and hence the absorbing set solution is precisely the set of aspirations.

Proposition 2.

For any initial demand vector $x^0$, there exists a period T such that there is a positive probability that $x^T$ is an aspiration.

Proof. 

Let $H^t$ denote the set of players whose demands are not feasible given $x^t$, and let $L^t$ denote the set of players whose demands are not maximal given $x^t$.

Let $x^0$ be the vector of demands at the beginning of period 1. Player i in $H^0$ is selected with a positive probability to adjust his demand. Since ${max}_{S:i\in S}\{v\left(S\right)-x(S\backslash i)\}\ge 0$ (e.g., $S=\left\{i\right\}$), the adjusted demand $x_i^1$ of player i will be feasible. Hence, $|H^1|<|H^0|$ and $|L^1|\le |L^0|,$ since player i chooses a maximal coalition. Repeating the argument for players in $H^1$, $H^2$, … with a non-zero probability the process moves to a state with $H^t=⌀.$

Suppose now that player $j\in L^t$ is selected. For such a player, it holds that $y_j>x_j^t$. Player j increases her demand to claim the maximal surplus available, and thus $|L^{t+1}| < |L^t|$. This increase may turn some previously feasible demands unfeasible. However, from the previous paragraph, when such players are selected, the process can reach a period with $H=⌀$ without increasing $\left|L\right|$. Thus, with a positive probability, a situation with $H^r=⌀,$$|L^r| < |L^t|$ is reached. Continuing in this fashion, a period T with $H^T=⌀$ and $L^T=⌀$ is reached. □

Thus, an aspiration can be reached from any demand vector $x^0$ (or, more generally, $x^t$) in a finite number of steps. Since once an aspiration is reached, then $x^t=x^T$ for all subsequent $t>T$ (Proposition 1), it follows that

Corollary 1.

The process converges to an aspiration with probability 1.

The aspiration approach can be criticized because players are assumed to increase their demands whenever they are not maximal, irrespective of the probability of getting those demands. Note that in our model this probability is 1 by construction, since the player who is selected to adjust also forms a coalition that is able to satisfy the demands of its members.

Which aspiration the process converges to depends on the initial state $x^0$ (together with which players are selected to adjust). To select among aspirations, the next subsection allows certain perturbations in the process.

3.3. The Demand Adjustment Process with Mutations

We will assume from now on that the values $v\left(S\right)$ are rational numbers. Let m be a common denominator of these numbers, and let $\delta =\frac{1}{lm}$. The number l controls how fine the grid is. We assume that the demands of the players belong to a finite grid ${\mathrm{\Gamma }}_{\delta }=\{k\delta :k\in \{0,\dots ,K\}\}$ where K is a sufficiently large number (e.g., $K=\frac{V}{\delta }$, where $V={max}_{S}v\left(S\right)$). We consider only demand vectors belonging to the grid. Note that the grid is chosen in such a way that for all $x\in {\mathrm{\Gamma }}_{\delta }\times \dots \times$${\mathrm{\Gamma }}_{\delta }$, if $x\left(S\right)<v\left(S\right)$, any player $i\in S$ can increase the demand to a point $y_i\in {\mathrm{\Gamma }}_{\delta }$ so that $x\left(S\right)=v\left(S\right)$. The state space $\mathcal{S}$ of the demand adjustment process consists of demand vectors x on the grid. With this finite grid, the demand adjustment process is a finite Markov chain. For a sufficiently fine grid, the set of aspirations restricted to the grid is non-empty (an irrational $\delta$ with all $v\left(S\right)$ rational would make $x\left(S\right)=v\left(S\right)$ impossible to achieve and thus lead to an empty set of aspirations on the grid). The finite grid also contains some partnered aspirations.

Lemma 2.

If $v\left(S\right)$ is a rational number for all $S\subseteq N$, there is at least one partnered aspiration with rational coordinates.

Proof. 

See Appendix A.1. □

The restriction to the finite grid thus retains some aspirations with desirable properties.

Given the state space $\mathcal{S}$, let M be the matrix such that $M_{ab}$ specifies the probability of moving from state a to state b in one step according to the demand adjustment process. Matrix M is the transition matrix of the Markov chain on this state space. A probability distribution on the (finite) state space $\mathcal{S}$ is a $1\times \left|\mathcal{S}\right|$ vector $\mu$, where ${\mu }_a$ is the probability of state a. The vector $\mu$ is a stationary distribution of the Markov chain M if $\mu M=\mu$. Note that M may have more than one stationary distribution.

The concept of absorbing sets can be naturally applied to Markov chains. A set of states $\mathcal{A}\subseteq$$\mathcal{S}$ is absorbing if for any distribution $\mu$ such that the support of $\mu$ is in $\mathcal{A}$, it holds that the support of $\mu M$ is also in $\mathcal{A}$. Because the process cannot permanently stay out of the absorbing set solution, the support of any stationary distribution of the Markov chain must be contained in the support of the absorbing set solution.

From the previous subsection, the absorbing set solution is precisely the set of aspirations (Propositions 1 and 2). Therefore, the support of any stationary distribution consists only of aspiration states. Note that for each particular aspiration x, there is a stationary distribution whose support only includes x. Hence there are many stationary distributions.

We extend the basic process to allow for the possibility of rare occasions in which the players’ behavior differs from the one described before. We will refer to such an event as a “mutation”. Mutations make the process move between aspirations and may help to select among them. The set of separating aspirations is important because such aspirations will be robust against a mutation by one player, while other aspirations are not.

The basic model assumes that the adjusting player selects the demand that solves the maximization problem (1). We now allow the possibility that this player “mutates”. We assume that the player more likely mutates to a higher demand than to a lower demand. That is, with probability $1-\epsilon$, there is no mutation (and the player adjusts in the usual way), and with probability $\epsilon$ there is a mutation. Conditional on a mutation having occurred, the new demand is within the set $\{x_i^{t-1},\dots ,V\}$ with probability $1-\epsilon$, and it is within the set $\{0,\dots ,x_i^{t-1}\}$ with probability $\epsilon$. (The conditional probability could be a different value $\nu \ne \epsilon$, but we can assume that $\nu =O\left(\epsilon \right)$ without changing the results. Setting $\nu =\epsilon$ allows us to summarize the likelihood of various mutations with one parameter.) Note that if $x_i^{t-1}=V$, then the most likely “mutation” is $x_i^t=x_i^{t-1}$. This model of mutations is similar to intentional idiosyncratic play in [24]: players most likely “experiment” with demands that can give them a higher payoff (if the other players adjust). Note that when $\epsilon =0$, the process is the same as our basic process. We will consider the case where $\epsilon$ goes to 0.

We denote the transition matrix of the Markov chain of the process with mutation probability $\epsilon$ by $M^{\epsilon }$. A Markov chain is irreducible if there is a positive probability of moving from any state to any other state in a finite number of periods. The introduction of mutations makes the process irreducible, since any vector of demands can arise as a result of n consecutive mutations, one by each player. This implies that the Markov chain $M^{\epsilon }$ has a unique stationary distribution for $\epsilon >0$ (see, e.g., [6], pp. 48–49). The states that have a positive probability in the limit of this stationary distribution as $\epsilon$ goes to 0 are much more likely to be visited in the long run. The limit stationary distribution, denoted by ${\mu }^0={lim}_{\epsilon \to 0}{\mu }^{\epsilon }$, exists (see [6], p. 56).

Definition 10.

A state x is stochastically stable if it has a positive probability in the limit stationary distribution as ε goes to 0, that is, ${\mu }_x^0>0$.

For our model of mutations, the set of separating aspirations is robust to the introduction of one mutation of the most likely type, i.e., from $x_i$ to a higher demand.

Lemma 3.

Consider state x where x is a separating aspiration. Suppose player i mutates, from $x_i$ to a higher demand. Then the adjustment process without mutations will return to state x.

Proof. 

Suppose $x_i^t>x_i^{t-1}$. If player i is selected to adjust his demand at $t+1$, because of maximality of the original $x^{t-1}$, he will form a coalition and get $x_i^{t-1}$, in which case his demand returns to its original value. If another player j is selected to update her demand, she will form a coalition without i and get $x_j^t=x_j^{t-1}.$ Since none of the players needed i to achieve their demands, no demands will change until player i is selected to adjust his demand, in which case $x_i$ will return to its original value. □

On the other hand, if an aspiration is not separating, then a mutation by one player can lead to a different aspiration.

Lemma 4.

Consider state x where x is an aspiration that is not separating. There exists a player i such that, if player i mutates from $x_i$ to $x_i+\delta$, the adjustment process without mutations converges to a different aspiration with a positive probability.

Proof. 

Since x is not a separating aspiration, there exist two players, i and j, such that either j needs i to achieve her demand but i does not need j, or i and j both need each other. Now suppose i mutates to $x_i+\delta$. If player j is selected next, she can no longer find a coalition that supports her demand and has to settle for $y_j=x_j-\delta$, supported for example by a coalition Q such that i, $j\in Q$ and Q is in the generating collection of the previous aspiration x. The new state is $y=(x_1,\dots ,x_i+\delta ,\dots ,x_j-\delta ,\dots ,x_n)$, with $Q\in CG\left(y\right)$, $i,j\in Q$. This state is not necessarily an aspiration since some of the other players’ demands may become unfeasible after an increase in player i’s demand. Such players will lower their demands in the next periods with a positive probability, but player i will never lower his demand, since coalition Q has become feasible for i after j’s adjustment. Another aspiration will be reached with player i demanding a bit more, and some players, e.g., player j demanding a bit less. □

That some states are resistant to one (most likely) mutation and other states are not can be helpful in identifying what states can be stochastically stable. If there are sets of states that can be disturbed only with multiple mutations, only such sets can be stochastically stable.

Definition 11.

We call a set of states $\mathcal{B}$ locally stable if (i) all states in $\mathcal{B}$ are in an absorbing set; (ii) for any $\mathcal{S}\subseteq \mathcal{B}$, after a mutation of one player to a higher demand the basic process converges to a state in $\mathcal{B}$; (iii) there is no proper subset of $\mathcal{B}$ that has this property.

This definition is based on the definition in Nöldeke and Samuelson [29]. It implies that there is a sequence of mutations, one at a time, that allows to move between any two states in $\mathcal{B}$ (otherwise a subset of $\mathcal{B}$ would be locally stable). It is also related to the “one-deviation” property of Newton and Sawa [20], although they define this property for more general mutation structures.

Proposition 3.

If state x is stochastically stable, then $x\in \mathcal{B}$, where $\mathcal{B}$ is in a locally stable set of states.

The proposition is a restatement of Proposition 1 in Nöldeke and Samuelson [29] and their proof applies. Intuitively, the “cost” (in terms of the number of most likely mutations) of moving away from a locally stable set $\mathcal{B}$ is more than 1. From states not in a locally stable set, the cost of moving away is 1. If the probability of mutations goes to zero, the process spends almost all the time in those states that are part of a locally stable set.

Lemma 3 shows that each separating aspiration is in a locally stable set, but there may be other (non-singleton and consisting of aspirations that are not separating) locally stable sets. Below we analyze the stochastic stability of aspirations in a class of weighted majority games. We show that in important subclasses of these games separating aspirations are indeed the only ones that are locally, and thus stochastically, stable. However, in other weighted majority games, there exist non-singleton locally stable sets; thus aspirations that are not separating can still be stochastically stable.

4. Demand Adjustment in Weighted Majority Games

4.1. Weighted Majority Games

A simple voting game is a transferable utility game $(N,v)$ such that $v\left(S\right)=0$ or 1 for all $S\subseteq N$. We will assume that $v\left(S\right)=1$ implies $v\left(T\right)=1$ for all $T\supseteq S$ (monotonicity). A coalition S is called winning if $v\left(S\right)=1$, and losing if $v\left(S\right)=0$. The set of winning coalitions is denoted by W. A minimal winning coalition S is a coalition that is just large enough to win, that is, S is winning but no $TS$ is winning. The set of minimal winning coalitions is denoted by $W^m$.

We only consider simple voting games that are proper, that is, if $S,T\in W$, then $S\cap T\ne ⌀$. If a simple game is proper, it is not possible for two disjoint coalitions to be winning. A stronger condition is the following:

Definition 12.

A simple voting game is constant-sum if $v\left(S\right)+v(N\backslash S)=1$.

In a constant-sum game, the partition of the set of players into two sets always results in one winning coalition and one losing coalition.

A veto player is a player who is in all winning coalitions. A null player is a player such that $v\left(S\right)=v(S\cup \{i\left\}\right)$ for any S; such a player does not belong to any coalition in $W^m$. We assume henceforth that there are no null players, that is, each player belongs to at least one coalition in $W^m$.

A simple voting game is weighted if it is possible to assign a number of votes (weight) $w_i\ge 0$ to each player and to set a threshold q such that S is winning if and only if ${\sum }_{i\in S}{w}_i\ge q$. The combination $[q;w_1,\dots ,w_n]$ is a representation of the voting game. There are many representations $[q;w_1,\dots ,w_n]$ that are equivalent in that they produce the same set of winning coalitions.

Definition 13.

A representation $[q;w_1,\dots ,w_n]$ is called homogeneous if all minimal winning coalitions have the same total weight q.

Definition 14.

A game that admits a homogeneous representation is a homogeneous game.

For example, $[3;2,1,1,1]$ is a homogeneous game because each minimal winning coalition has exactly three votes. In contrast, $[5;2,2,2,1,1,1]$ is not a homogeneous game. Coalition $\{1,2,3\}$ is minimal winning but has six votes, while other minimal winning coalitions (such as $\{1,2,4\}$) have five votes. Moreover, it is not possible to find an alternative representation of this game that would be homogeneous.

Two players, i and j, are of the same type if $v(S\cup \{i\left\}\right)=v(S\cup \{j\left\}\right)$ for all $S\subset N$, $i,j\notin S$. If $w_i=w_j$, i and j are of the same type, though the converse is not necessarily true. It will sometimes be useful to refer to coalition types by listing the player types that form the coalition, as in $[3;2,1,1,1]$ having two types of minimal winning coalition, $\left[21\right]$ and $\left[111\right]$.

Weighted majority games have an empty core unless there are veto players. Constant-sum games have no veto players, except for the trivial case in which there is one veto player who is also a dictator, that is, $\left\{i\right\}\in W$.

4.2. Aspirations in Weighted Majority Games

We focus on constant-sum homogeneous games. For games in this class, there is an aspiration vector with desirable properties.

Remark 1.

Let $(N,v)$ be a constant-sum homogeneous game and $[q;w_1,\dots ,w_n]$ a homogeneous representation of this game. The aspiration vector ${\left(\frac{w_i}{q}\right)}_{i\in N}$ is balanced and separating and has rational coordinates.

For constant-sum homogeneous games, Peleg [30] (Theorem 3.5) shows that the nucleolus [31] is the only homogeneous representation that has ${\sum }_{i\in N}{w}_i=1$ (hence the homogeneous representation is unique up to a multiplicative constant in this class of games). Given that the nucleolus is a representation, the vector ${\left(\frac{w_i}{q}\right)}_{i\in N}$, where w is the nucleolus and q is ${\sum }_{i\in S}{w}_i$ for any minimal winning coalition S, is an aspiration vector and the generating collection for this aspiration vector is $W^m$. The nucleolus is proportional to a representation with integer weights (see [30]); hence ${\left(\frac{w_i}{q}\right)}_{i\in N}$ has rational coordinates. This aspiration is separating, since for any i and j there is a feasible coalition that contains i but not j. To see this, consider $S\in W^m$ such that $S\ni i$. If $j\notin S$, the result follows. Suppose $j\in S$. Since the game is constant-sum, $N\backslash S$ is losing and $\left\{i\right\}\cup N\backslash S$ is winning. Furthermore, since the game is homogeneous, there exists a coalition $T\subseteq \left\{i\right\}\cup N\backslash S$ such that $i\in T$ and $w\left(T\right)=q$; this coalition is feasible for i and does not involve j. That this aspiration vector is also balanced follows from [32]. It is the only balanced aspiration vector (see [33], Remark 10).

That the balanced aspiration has rational coordinates allows us to select the grid size $\delta$ in such a way that the grid contains the balanced aspiration. Peleg [30] shows that a constant-sum homogeneous game has a unique integer representation $[q;w_1,\dots ,w_n]$ with ${min}_{i\in N}{w}_i=1$. If $\delta =\frac{1}{lq}$, then the balanced aspiration is on the grid.

For constant-sum homogeneous games, we have established that there is a unique balanced aspiration vector, which is also a separating aspiration vector and has rational coordinates. There may be many other separating aspirations, as the example below illustrates.

Example 1.

(Aspirations that are separating but not balanced.) Consider the game $[4;2,2,1,1,1]$. All demand vectors of the form $x=(a,a,\frac{1-a}{2},\frac{1-a}{2},\frac{1-a}{2})$, where $\frac{1}{2}\le a\le 1$ are separating aspirations for this game. If $a>\frac{1}{2}$, the only coalitions in $GC\left(x\right)$ are of the form $\left[211\right]$. No player depends on any other; in particular, players with two votes do not depend on any particular player with one vote to obtain their demands. Aspirations with $a>\frac{1}{2}$ are separating but not balanced, since the aspiration $(\frac{1}{2},\frac{1}{2},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ has a smaller total sum.

The example also shows that separating aspirations can result in a very unequal distribution between types, as in the case of $x=(1,1,0,0,0)$.

If we relax the assumption that the game is constant-sum and homogeneous, it is possible for an aspiration vector to be balanced but not partnered (and therefore not separating; see Appendix A.2).

4.3. Symmetric Majority Games

The simplest class of games to which we can apply our adjustment process is the following. Consider the symmetric majority game with n players and $w_i=1$ for all players:

$[q;1,\dots ,1].$

If $q=n$, then the game is a unanimity game (all players are needed to form a winning coalition; all players are veto players). In this game, there are no separating aspirations and all demand vectors with $x_1+\dots +x_n=1$ are in the core. Therefore, we consider $\frac{n}{2}<q<n$. The three-player simple majority example in the introduction is the symmetric majority game with $n=3$ and $q=2$.

The balanced aspiration is $\left(\frac{1}{q},\dots ,\frac{1}{q}\right)$, which is also separating. Other aspirations include, for example $(0,\dots ,0,1,\dots ,1)$, with $q-1$ players demanding 0. There, aspirations are clearly non-partnered, with players with demand 1 depending on players with demand 0.

Proposition 4.

The unique stochastically stable state for a symmetric majority game with $\frac{n}{2}<q<n$ is the balanced aspiration $\left(\frac{1}{q},\dots ,\frac{1}{q}\right)$.

Proof. 

Consider an aspiration $x=(x_1,\dots ,x_n)$ with $x_m={min}_{i=1,\dots ,n}{x}_i<x_M={max}_{i=1,\dots ,n}{x}_i$. Since $\frac{1}{q}$ is on the grid, $x_m\le \frac{1}{q}-\delta$ (otherwise there are players whose demands are not feasible) and $x_M\ge \frac{1}{q}+\delta$ (otherwise there are coalitions that are not maximal).

In any coalition in $GC\left(x\right)$, players with demand $x_m$ are included, and any excluded players demand $x_M$. Let $x_i=x_m$ and $x_j=x_M$. Suppose player i mutates to $x_m+\delta$. If player j is selected to adjust, she sets her demand to $x_M-\delta$. Other players with demand $x_M$ may need to adjust downwards by $\delta$, but in a new aspiration y, $y_m\ge x_m$ and if $y_m=x_m$, then the number of players with demand $x_m$ is smaller in y than in x. Continuing the mutations in this fashion, aspiration with $x_m=\frac{1}{q}$ is reached. Then $x_M=\frac{1}{q}$, and the balanced aspiration is reached.

Since the balanced aspiration is separating, it constitutes a locally stable set. The previous argument shows that there are no other locally stable sets. By Proposition 3, the balanced aspiration is stochastically stable. □

4.4. Apex Games

Apex games are weighted majority games with one major player (the apex player) and $n-1\ge 2$ minor players (or base players). They can be described as

$[n-1;n-2,1,\cdots ,1],$

with the apex player having $n-2$ votes, each of the $n-1$ minor players having 1 vote, and $n-1$ (out of total $2n-3$) votes are needed to win. In terms of the characteristic function, an apex game is given by $v\left(S\right)=1$ if $1\in S$ and $\left|S\right|>1$, or if $S=\{2,\dots ,n\}$, and $v\left(S\right)=0$ otherwise. Player 1 needs only one minor player to form a winning coalition, whereas the only way to win in the absence of the apex player is if all minor players form a coalition. Apex games have received a lot of attention in the literature since von Neumann and Morgenstern [34] from both theoretical and experimental perspectives (see [35,36,37,38,39] for theoretical developments and [39,40,41,42,43] for experimental studies).

The set of aspirations in apex games can be divided into several subsets. If $x_1<\frac{n-2}{n-1}$, then in an aspiration, every $x_i>\frac{1}{n-1}$, and $x\left(\right\{2,\dots ,n\left\}\right)>1$. This implies that $x_i=1-x_1$ for all $i=2,\dots ,n$, with $GC\left(x\right)=\left\{{\{1,i\}}_{i=2,\dots ,n}\right\}$ if $x_1>0$ and $GC\left(x\right)=\{\left\{1\right\},{\{1,i\}}_{i=2,\dots ,n}\}$ if $x_1=0$. If $x_1>\frac{n-2}{n-1}$, in an aspiration ${min}_{\{2,\dots ,n\}}{x}_i=1-x_1<\frac{1}{n-1}$, ${max}_{\{2,\dots ,n\}}{x}_i>\frac{1}{n-1}$, and ${\sum }_{i=2}^n{x}_i=1$. The generating collection of such aspirations consists of the coalition of minor players $\{2,\dots ,n\}$, and one or more coalitions $\{1,i\}$. If $x_1=1$, also some singleton coalitions are feasible. Finally, there is aspiration $x=\left(\frac{n-2}{n-1},\frac{1}{n-1},\dots ,\frac{1}{n-1}\right)$ with $GC\left(x\right)=\{\{2,\dots ,n\},{\{1,i\}}_{i=2,\dots ,n}\}=W^m$. This aspiration is the unique balanced aspiration, and it is separating.

For our demand adjustment process with mutations, the following proposition holds:

Proposition 5.

The unique stochastically stable state for apex games is the balanced aspiration $\left(\frac{n-2}{n-1},\frac{1}{n-1},\dots ,\frac{1}{n-1}\right)$.

Proof. 

Consider an aspiration x with $x_1>\frac{n-2}{n-1}$. If there is only one coalition $\{1,i\}$ in $GC\left(x\right)$, player 1 needs player i. If player i mutates to $x_i+\delta$ and player 1 is then selected to adjust her demand, player 1 is forced to reduce her demand. Other players may need to lower their demands as well, but in the new aspiration y, it holds that $y_1<x_1$.

If there is more than one coalition $\{1,i\}$ in $GC\left(x\right)$, player 1 does not depend on any player, but there is a player k with $x_k={max}_{\{2,\dots ,n\}}{x}_i>\frac{1}{n-1}$ that does depend on player i. Suppose player i mutates to $x_i+\delta$ and player k is selected to adjust. Player k will propose coalition $\{2,\dots ,n\}$ with probability 1 (since $x_1\ge \frac{n-2}{n-1}+\delta$ and $x_k\ge \frac{1}{n-1}+\delta$, it cannot be optimal for k to propose $\{1,k\}$) so that player i receives $x_i+\delta$ and player k receives $x_k-\delta$. No other player needs to adjust, but coalition $\{1,i\}$ is not feasible for the new aspiration vector. Repeating the reasoning if necessary, a chain of mutations, happening one at a time, leads to an aspiration x in which only one coalition $\{1,i\}$ is in $GC\left(x\right)$.

Repeating the steps of the last two paragraphs, from any aspiration x with $x_1>\frac{n-2}{n-1}$ there is a chain of mutations, happening one at a time, and possible adjustment of demands according to the basic process, leading to the aspiration $\left(\frac{n-2}{n-1},\frac{1}{n-1},\dots ,\frac{1}{n-1}\right)$.

Consider now aspiration x with $x_1<\frac{n-2}{n-1}$. Since $\{2,\dots ,n\}$ is not feasible, any minor player i needs player 1. Suppose player 1 mutates to $x_1+\delta$ and player $j\ne 1$ is selected to adjust. Player j proposes coalition $\{1,j\}$, giving a payoff $x_1+\delta$ to player 1 and lowering her own demand to $x_j-\delta$. Furthermore, all other minor players also lower their demands when selected because the coalitions with player 1 became unfeasible. When a new aspiration y is reached, it holds that $y_1>x_1$. Repeating the step if necessary, there is a chain of mutations (happening one at a time) and subsequent adjustment according to the basic process, leading to the partnered aspiration $\left(\frac{n-2}{n-1},\frac{1}{n-1},\dots ,\frac{1}{n-1}\right)$.

The balanced aspiration itself cannot be upset by one mutation according to Lemma 3; thus it is locally stable. The previous reasoning shows that there are no other locally stable sets. According to Proposition 3, this implies the result. □

4.5. Stochastic Stability in Other Weighted Majority Games

Allowing intentional “mutations” works to select the unique separating aspiration in the classes of symmetric majority games and apex games. The players that demand too little can start demanding a bit more, and, since other players depend on them to satisfy their demands, the competition for scarce players drives the demands to the separating aspiration.

However, we will see below that the process does not always lead to this strong result. While for some games, only separating aspirations are stochastically stable (Example 1), we show that for other games there exist locally stable sets that do not contain separating aspirations (Examples 2 and 3). Thus, the strong result for symmetric game and apex games from the previous subsections does not easily generalize to other weighted majority games.

Example 1 (continued).

Consider the game $[4;2,2,1,1,1]$. Recall that in this game, separating aspirations are of the form $(a,a,\frac{1-a}{2},\frac{1-a}{2},\frac{1-a}{2})$ for $\frac{1}{2}\le a\le 1$ (this set includes the unique balanced aspiration $(\frac{1}{2},\frac{1}{2},\frac{1}{4},\frac{1}{4},\frac{1}{4})$.)

Consider an aspiration x with $x_1+x_2=1$ and $x_1<x_2$ (the case $x_1>x_2$ can be analyzed analogously). In x, player 2 depends on player 1: if there was a coalition $S\in GC\left(x\right),2\in S,1\notin S$, then coalition $S\backslash \left\{2\right\}\cup \left\{1\right\}$ would not be maximal. Since $x_1+x_2=1$ and $\frac{1}{2}$ is on the grid, then $x_1\le \frac{1}{2}-\delta$ and $x_2\ge \frac{1}{2}+\delta$. If player 1 mutates to $x_1+\delta$ and player 2 adjusts to $x_2-\delta$, then a new aspiration y is eventually reached with $y_1>x_1$ and $y_1+y_2=1$. Continuing if necessary, an aspiration with $x_1=x_2=\frac{1}{2}$ can be reached by a sequence of mutations, one player (player 1) at a time.

Consider now aspiration x with $x_1=x_2=\frac{1}{2}$. Such aspirations are of the form $(\frac{1}{2},\frac{1}{2},b,\frac{1}{2}-b,\frac{1}{2}-b)$, $(\frac{1}{2},\frac{1}{2},\frac{1}{2}-b,b,\frac{1}{2}-b)$ or $(\frac{1}{2},\frac{1}{2},\frac{1}{2}-b,\frac{1}{2}-b,b)$, with $b\le \frac{1}{4}$. If $b=\frac{1}{4}$, then we have the balanced aspiration. Suppose $b<\frac{1}{4}$ and let $x_i=b$ and $x_j=x_k=\frac{1}{2}-b$. Since $x_i<x_j=x_k$, players j and k both depend on player i. Suppose player i mutates and players j and k are selected to adjust. Then a new aspiration y is reached, with $y_i>x_i$ and $y_j<x_j,y_k<x_k$. Continuing if necessary, the balanced aspiration $\left(\frac{1}{2},\frac{1}{2},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$ is reached.

Consider now an aspiration x with $x_1+x_2>1$. Such aspirations are of the form $(a,a,b,1-a-b,1-a-b)$, $(a,a,1-a-b,b,1-a-b)$, or $(a,a,1-a-b,1-a-b,b)$ with $a>\frac{1}{2}$ and $b\le 1-a-b$ (equivalently, $b\le \frac{1-a}{2}$). If $b=\frac{1-a}{2}$, then x is a separating aspiration. Otherwise, let $x_i=b<x_j=x_k=1-a-b$. Since the only feasible coalitions are $\left[211\right]$, a maximal such coalition has to include player i, and therefore players 1 and 2 depend on player i. Suppose player i mutates to $x_i+\delta$. If players 1 and 2 are subsequently selected to adjust, they both lower their demand. If then $x_1+x_2=1$, then we are in one of the cases in the previous paragraphs. Continuing if necessary, either an aspiration with $x_1+x_2=1$ is reached or an aspiration with $x_3=x_4=x_5$. If the former, the process continues as described in the previous paragraphs. If the latter, a separating aspiration $\left(a,a,\frac{1-a}{2},\frac{1-a}{2},\frac{1-a}{2}\right)$ with $\frac{1}{2}\le a\le 1$ has been reached. Therefore from any aspiration, a sequence of mutations, one player at a time, can reach the set of separating aspirations $\left(a,a,\frac{1-a}{2},\frac{1-a}{2},\frac{1-a}{2}\right)$ with $\frac{1}{2}\le a\le 1$. This set is the unique locally stable set. Therefore, stochastically stable states are within this set of separating aspirations.

The previous example shows that there are games other than apex games in which only the separating aspirations are stochastically stable in the demand adjustment process with mutations (even if the set is larger than the unique balanced aspiration), because locally stable sets contain only separating aspirations. However, in other games, there are locally stable sets that contain other aspirations (including non-partnered ones).

Example 2.

Consider the game $[7;5,2,2,1,1,1,1]$. Consider aspiration $x=(0.8,a,0.7-a,0.1,0.1,0.1,0.1)$ with $0.2<a<0.5$. In x, no player depends on any other player, except players 2 and 3, who depend on each other. Thus, it is partnered but not separating.

Suppose that the process is at x. If a player other than player 2 or 3 mutates upwards, then no other player would need to adjust; the process will return to x. Suppose player 2 mutates upwards to $y_2$ (mutations by player 3 can be analyzed analogously). The only other player who would need to adjust is player 3. If $y_2<0.5$, player 3 adjusts to $y_3=0.7-y_2$, and in the new aspiration players 2 and 3 still depend on each other and there are no other dependencies among the players. If $y_2\ge 0.5$, then player 3 adjusts to $y_3=0.2$ (with coalition $\{1,3\}$). If $y_2=0.5$, then y is an aspiration. If $y_2>0.5$, player 2’s demand is unfeasible and he has to lower the demand to $0.5$. In either case, aspiration $y=(0.8,0.5,0.2,0.1,0.1,0.1,0.1)$ is reached. This aspiration is not partnered, since player 2 depends on player 3 but not vice versa. If player 3 now mutates upwards, then player 2 would need to adjust, but the adjustment would lead either to aspiration $z=(0.8,0.2,0.5,0.1,0.1,0.1,0.1)$ or to an aspiration like x.

Therefore, the set of aspirations $(0.8,a,0.7-a,0.1,0.1,0.1,0.1)$ with $0.2\le a\le 0.5$ is a locally stable set. The set contains non-partnered aspirations ($a=0.2$ or $a=0.5$). Aspirations in the set can be reached one from another by a series of mutations, one at a time, but no aspiration outside of the set (including the unique balanced aspiration $\left(\frac{5}{7},\frac{2}{7},\frac{2}{7},\frac{1}{7},\frac{1}{7},\frac{1}{7},\frac{1}{7}\right)$) can be reached from it by one mutation.

Example 3.

Consider the game $[8;2,2,2,2,2,2,1,1,1]$, with nine players; players 1–6 have two votes each and players 7–9 have one vote each. Minimal winning coalitions in this game can be either four players with two votes $\left(\right[2222\left]\right)$ or three players with two votes and two players with one vote $\left(\right[22211\left]\right)$.

In this game, the unique balanced aspiration is $\left(\frac{2}{8},\dots ,\frac{2}{8},\frac{1}{8},\frac{1}{8},\frac{1}{8}\right)$. Consider aspiration $x=\left(\frac{2}{8},\frac{2}{8}+\delta ,\dots ,\frac{2}{8}+\delta ,\frac{1}{8}-\delta ,\frac{1}{8}-\delta ,\frac{1}{8}-\delta \right)$, in which only one player with two votes demands $\frac{2}{8}$, while other such players demand $\delta$ more. It is non-partnered, with all players depending on player 1. Mutations of players other than player 1 will result in the process going back to x. Suppose player 1 mutates upwards. If any of players 2–6 adjust, the adjustment is to $\frac{2}{8}$. Player 1 then adjusts to $\frac{2}{8}+\delta$, leading to an aspiration that is a permutation of x (within types of players). If player 7 adjusts, the adjustment is to $\frac{1}{8}-2\delta$. Player 1 then adjusts to $\frac{2}{8}+\delta$ and the new aspiration is $y=\left(\frac{2}{8}+\delta ,\dots ,\frac{2}{8}+\delta ,\frac{1}{8}-2\delta ,\frac{1}{8}-\delta ,\frac{1}{8}-\delta \right)$ (if players 8 or 9 adjusts, the new aspiration is a permutation of y). In y, all players depend on player 7. If player 7 mutates upwards, then either players 8 or 9 adjust to $\frac{1}{8}-2\delta$, leading to an aspiration that is a permutation of y, or any of the players 1–6 adjust to $\frac{2}{8}$, leading to an aspiration that is a permutation of x. The process thus can move between aspirations such as x and y with one mutation but cannot reach any other aspiration with one mutation. The set of aspirations that are permutations of x and y is locally stable, even though none of these aspirations is partnered.

Note that the reasoning in the previous paragraph does not depend (much) on the size of $\delta$: if, for example, ${\delta }^{\prime }=\delta /2$, the same reasoning applies. There is also nothing special about it being only $\delta$ away from the balanced aspiration. Consider aspiration $x^{\prime }=(\frac{2}{8}+a\delta ,\frac{2}{8}+(a+1)\delta ,\dots ,\frac{2}{8}+(a+1)\delta ,\frac{1}{8}-(\frac{3}{2}a+1)\delta ,\dots ,\frac{1}{8}-(\frac{3}{2}a+1)\delta )$, with integer a divisible by 2 and $0\le a\le \frac{1}{12\delta }-\frac{4}{3}$ (the example in the previous paragraph is obtained by setting $a=0$). In $x^{\prime }$, all players depend on player 1. Similarly to the discussion in the previous paragraph, mutations of one player can move between permutations of $x^{\prime }$ and $y^{\prime }=(\frac{2}{8}+(a+1)\delta ,\dots ,\frac{2}{8}+(a+1)\delta ,\frac{1}{8}-(\frac{3}{2}a+2)\delta ,\frac{1}{8}-(\frac{3}{2}a+1)\delta ,\frac{1}{8}-(\frac{3}{2}a+1)\delta )$. The set of aspirations which are permutations of $x^{\prime }$ and $y^{\prime }$ is again locally stable.

These last two examples show that it is not necessarily the case that only separating aspirations are contained in a locally stable set. The analysis of stochastic stability in these games then requires going beyond locally stable sets, looking also at mutations that are not the most likely ones. We leave this analysis for future research.

5. Conclusions

This paper presented a simple best-reply adaptive model of demand adjustment in cooperative games. Our basic process without mutations converges to the set of aspirations; by introducing certain mutations in the process, we are able to select a plausible subset of the set of aspirations.

In particular, our model of mutations, based on the intuitive desire to try to achieve a higher payoff, allows players to experiment with higher demands more often than with lower ones. This model identifies the set of separating aspirations, in which no player is indispensable in order for other players to achieve their demands, as the set that is most resistant to change.

For two particular classes of weighted majority games, namely symmetric games and apex games, we show that, with such infrequent mutations, the unique separating aspiration in each game is stochastically stable. In this way we provide sharp predictions for these important classes of games with an empty core.

Author Contributions

Conceptualization, M.M. and A.P.; formal analysis, M.M. and A.P.; writing—original draft preparation, M.M. and A.P.; writing—review and editing, M.M. and A.P. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Bennett, E. The aspiration approach to predicting coalition formation and payoff distribution in sidepayment games. Int. J. Game Theory; 1983; 12, pp. 1-28. [DOI: https://dx.doi.org/10.1007/BF01756101]

2. Cross, J. Some theoretic characteristics of economic and political coalitions. J. Confl. Resolut.; 1967; 11, pp. 184-195. [DOI: https://dx.doi.org/10.1177/002200276701100205]

3. Albers, W. Core- and kernel- variants based on imputations and demand profiles. Game Theory and Related Topics; Moeschlin, O.; Palaschke, D. North-Holland: Amsterdam, The Netherlands, 1979.

4. Nash, J. Two-person cooperative games. Econometrica; 1953; 21, pp. 128-140. [DOI: https://dx.doi.org/10.2307/1906951]

5. Bennett, E.; Maschler, M.; Zame, W. A demand adjustment process. Int. J. Game Theory; 1997; 26, pp. 423-438. [DOI: https://dx.doi.org/10.1007/BF01813883]

6. Young, H.P. Individual Strategy and Social Structure: An Evolutionary Theory of Institutions; Princeton University Press: Princeton, NJ, USA, 1998.

7. Newton, J. Evolutionary game theory: A renaissance. Games; 2018; 9, 31. [DOI: https://dx.doi.org/10.3390/g9020031]

8. Maschler, M.; Peleg, B. A characterization, existence proof and dimension bounds for the kernel of a game. Pac. J. Math.; 1966; 18, pp. 289-328. [DOI: https://dx.doi.org/10.2140/pjm.1966.18.289]

9. Young, H.P. An evolutionary model of bargaining. J. Econ. Theory; 1993; 59, pp. 145-168. [DOI: https://dx.doi.org/10.1006/jeth.1993.1009]

10. Green, J.R. The stability of Edgeworth’s recontracting process. Econometrica; 1974; 42, pp. 21-34. [DOI: https://dx.doi.org/10.2307/1913682]

11. Feldman, A.M. Recontracting stability. Econometrica; 1974; 42, pp. 35-44. [DOI: https://dx.doi.org/10.2307/1913683]

12. Agastya, M. Adaptive play in multiplayer bargaining situations. Rev. Econ. Stud.; 1997; 64, pp. 411-426. [DOI: https://dx.doi.org/10.2307/2971721]

13. Agastya, M. Perturbed adaptive dynamics in coalition form games. J. Econ. Theory; 1999; 89, pp. 207-233. [DOI: https://dx.doi.org/10.1006/jeth.1999.2574]

14. Arnold, T.; Schwalbe, U. Dynamic coalition formation and the core. J. Econ. Behav. Organ.; 2002; 49, pp. 363-380. [DOI: https://dx.doi.org/10.1016/S0167-2681(02)00015-X]

15. Newton, J. Recontracting and stochastic stability in cooperative games. J. Econ. Theory; 2012; 147, pp. 364-381. [DOI: https://dx.doi.org/10.1016/j.jet.2011.11.007]

16. Rozen, K. Conflict leads to cooperation in demand bargaining. J. Econ. Behav. Organ.; 2013; 87, pp. 35-42. [DOI: https://dx.doi.org/10.1016/j.jebo.2012.12.005]

17. Sawa, R. Stochastic stability under logit choice in coalitional bargaining problems. Games Econ. Behav.; 2019; 113, pp. 633-650. [DOI: https://dx.doi.org/10.1016/j.geb.2018.11.009]

18. Nax, H.H. Uncoupled aspiration adaptation dynamics into the core. Ger. Econ. Rev.; 2019; 20, pp. 243-256. [DOI: https://dx.doi.org/10.1111/geer.12160]

19. Klaus, B.; Klijn, F.; Walzl, M. Stochastic stability for roommate markets. J. Econ. Theory; 2010; 145, pp. 2218-2240. [DOI: https://dx.doi.org/10.1016/j.jet.2010.07.006]

20. Newton, J.; Sawa, R. A one-shot deviation principle for stability in matching problems. J. Econ. Theory; 2015; 157, pp. 1-27. [DOI: https://dx.doi.org/10.1016/j.jet.2014.11.015]

21. Nax, H.H.; Pradelski, B.S.R. Evolutionary dynamics and equitable core selection in assignment games. Int. J. Game Theory; 2015; 44, pp. 903-932. [DOI: https://dx.doi.org/10.1007/s00182-014-0459-1]

22. Nax, H.H.; Pradelski, B.S.R. Core stability and core selection in a decentralized labor matching market. Games; 2016; 7, 10. [DOI: https://dx.doi.org/10.3390/g7020010]

23. Klaus, B.; Newton, J. Stochastic stability in assignment problems. J. Math. Econ.; 2016; 62, pp. 62-74. [DOI: https://dx.doi.org/10.1016/j.jmateco.2015.11.002]

24. Naidu, S.; Hwang, S.H.; Bowles, S. Evolutionary bargaining with intentional idiosyncratic play. Econ. Lett.; 2010; 109, pp. 31-33. [DOI: https://dx.doi.org/10.1016/j.econlet.2010.07.005]

25. Reny, P.J.; Winter, E.; Wooders, M. The partnered core of a game with side payments. Soc. Choice Welf.; 2012; 39, pp. 521-536. [DOI: https://dx.doi.org/10.1007/s00355-012-0651-9]

26. Baron, D.P.; Ferejohn, J.A. Bargaining in legislatures. Am. Political Sci. Rev.; 1989; 83, pp. 1181-1206. [DOI: https://dx.doi.org/10.2307/1961664]

27. Inarra, E.; Kuipers, J.; Olaizola, N. Absorbing and generalized stable sets. Soc. Choice Welf.; 2005; 24, pp. 433-437. [DOI: https://dx.doi.org/10.1007/s00355-003-0307-x]

28. Shenoy, P.P. On coalition formation: A game-theoretic approach. Int. J. Game Theory; 1979; 8, pp. 133-164. [DOI: https://dx.doi.org/10.1007/BF01770064]

29. Nöldeke, G.; Samuelson, L. An evolutionary analysis of backward and forward induction. Games Econ. Behav.; 1993; 5, pp. 425-454. [DOI: https://dx.doi.org/10.1006/game.1993.1024]

30. Peleg, B. On weights of constant-sum majority games. SIAM J. Appl. Math.; 1968; 16, pp. 527-532. [DOI: https://dx.doi.org/10.1137/0116042]

31. Schmeidler, D. The nucleolus of a characteristic function game. SIAM J. Appl. Math.; 1969; 17, pp. 1163-1170. [DOI: https://dx.doi.org/10.1137/0117107]

32. Kohlberg, E. On the nucleolus of a characteristic function game. SIAM J. Appl. Math.; 1971; 20, pp. 62-66. [DOI: https://dx.doi.org/10.1137/0120009]

33. Morelli, M.; Montero, M. The demand bargaining set: General characterization and application to majority games. Games Econ. Behav.; 2003; 42, pp. 137-155. [DOI: https://dx.doi.org/10.1016/S0899-8256(02)00532-8]

34. von Neumann, J.; Morgenstern, O. Theory of Games and Economic Behavior; Princeton University Press: Princeton, NJ, USA, 1944.

35. Davis, M.; Maschler, M. The kernel of a cooperative game. Nav. Res. Logist. Q.; 1965; 12, pp. 223-259. [DOI: https://dx.doi.org/10.1002/nav.3800120303]

36. Aumann, R.J.; Myerson, R. Endogenous formation of links between players and of coalitions: An application of the Shapley value. The Shapley Value, Essays in Honor of Lloyd Shapley; Roth, A. Cambridge University Press: Cambridge, UK, 1988.

37. Bennett, E.; van Damme, E. Demand commitment bargaining: The case of apex games. Game Equilibrium Models, Vol. III, Strategic Bargaining; Selten, R. Springer: Berlin, Germany, 1991; pp. 118-140.

38. Montero, M. Noncooperative bargaining in apex games and the kernel. Games Econ. Behav.; 2002; 41, pp. 309-321. [DOI: https://dx.doi.org/10.1016/S0899-8256(02)00501-8]

39. Fréchette, G.; Kagel, J.; Morelli, M. Behavioral identification in coalitional bargaining: An experimental analysis of demand bargaining and alternating offers. Econometrica; 2005; 73, pp. 1893-1937. [DOI: https://dx.doi.org/10.1111/j.1468-0262.2005.00641.x]

40. Selten, R.; Schuster, K.G. Psychological variables and coalition-forming behavior. Risk and Uncertainty; Borch, K.; Mossin, J. Macmillan: London, UK, 1968; pp. 221-241.

41. Rapoport, A.; Kahan, J.; Funk, S.; Horowitz, A. Coalition Formation by Sophisticated Players; Springer: Berlin, Germany, 1979.

42. Funk, S.G.; Rapoport, A.; Kahan, J.P. Quota vs. positional power in 4-person apex games. J. Exp. Soc. Psychol.; 1980; 16, pp. 77-93. [DOI: https://dx.doi.org/10.1016/0022-1031(80)90037-2]

43. Rapoport, A. Test of the kernel and two bargaining set models in four- and five-person games. Experimental Studies of Interactive Decisions; Theory and Decision Library Volume 5 Kluwer: Dordrecht, The Netherlands, 1990; pp. 183-209.

44. Freixas, J.; Molinero, X. On the existence of a minimum integer representation for weighted voting systems. Ann. Oper. Res.; 2009; 166, pp. 243-260. [DOI: https://dx.doi.org/10.1007/s10479-008-0422-2]