betaFeedback

WorksEconomics, Econometrics and Finance

On the equilibrium lattice of supermodular games

Abstract

This paper shows how the meet and join of any pair of equilibria in a super- modular game can be constructed. The method relies on two one-directional best-response processes that I call contagion up and contagion down. Starting from any action profile, applying this pair of processes in opposite orders produces two equilibria that define its equilibrium envelope. The endpoints of the envelope are precisely the least and greatest equilibria reachable through arbitrary asynchronous best-response dynamics, and can only move closer together as players revise their actions. These and other results show how appending one-directional adjustment processes to the familiar equilibrium lattice structure allows us to explore the relationships between equilibria further.

Introduction

It is well known that the set of pure-strategy Nash equilibria of a supermodular game forms a complete lattice [19, 20]. In this paper, I explore what more can be learned about equilibrium structure and best-response dynamics by introducing two one-directional adjustment processes: contagion up and contagion down. In the former, only players whose best responses are higher than their current actions are allowed to revise; for the latter, it’s the opposite. While I do not view these dynamics as realistic descriptions of how players behave, they turn out to be useful analytical tools, both when applied in isolation and, especially, when combined.

The classic lattice theorem establishes that the meet and join of two equilibria are themselves equilibria, but says nothing about how to construct them. My first result shows how to do so and is easy to explain. Take any two incomparable equilibria and form their componentwise minimum and maximum. While neither of these profiles need be an equilibrium, applying contagion down to the minimum and contagion up to the maximum recovers the meet and join of the original pair of equilibria in the equilibrium lattice.3

Things become even more interesting when the two processes are combined in a new way: applying them successively, one after the other. For example, starting from any action profile, applying contagion down followed by contagion up is a procedure that terminates at a Nash equilibrium. Running up and then down does also. Moreover, these two equilibria turn out to be precisely the least and greatest equilibria reachable through arbitrary asynchronous best-response dynamics, and together define what I call the equilibrium envelope of the initial profile. While both endpoints of the envelope are reachable via a path of best responses, equilibria lying strictly inside the envelope need not be.

Two more results concern how the equilibrium envelope evolves as players revise their actions. The first is that the envelope can only contract: as players best respond, its lower endpoint can only rise and its upper endpoint can only fall. The second is that the envelope must eventually stabilise, even if the underlying best-response dynamics cycle indefinitely. Perhaps most strikingly, these last two results hold regardless of the revision protocol.4

To illustrate the results, I use a six-player example of the binary-action threshold model of Neary and Newton [14] in which all players have a common threshold. With only six players, the environment is manageable enough to make the adjustment processes transparent, and yet rich enough to illustrate the main ideas. Binary-action games also make the contagion-up and contagion-down operators particularly transparent: at any profile, players can be partitioned into at most four sets according to their current action and best response. Under either contagion up or contagion down, only one of these sets is eligible to revise initially and only two of the four sets at any point throughout. By contrast, under standard best-response dynamics, players from two sets are initially eligible to revise, but over time there can be jostling among all four.

In fact, I restrict attention to binary-action supermodular games throughout the paper. While this is done primarily for clarity and intuition, as discussed above, little is lost by doing so: all but one of the results extend to supermodular games with totally ordered action sets and unique best responses (with a mild qualifier for one of them). The exception is Theorem 2, on generating equilibrium intervals, whose proof relies heavily on the binary-action assumption and whose extension remains an open question.

The balance of the paper is organised as follows. § 3 introduces supermodular games and the two contagion processes. § 4 establishes the main results on equilibrium structure, and § 5 illustrates them with an example. In § 6, I characterise the equilibria reachable through best-response dynamics and in § 7 study how the equilibrium envelope evolves as players revise their actions. § 8 concludes.

Relation to the literature

Bulow et al. [5] formally distinguished between strategic substitutes and complements in the context of oligopoly. Supermodular games provide the right framework for studying strategic complementarities. Topkis [18] and Vives [20] established classic results on the existence and lattice structure of Nash equilibria.

Three papers are particularly relevant to my analysis. The first is Milgrom and Roberts [9], who show how monotone best responses can bound long-run behaviour under a broad class of adaptive dynamics. Whereas their bounds are determined by the extremal equilibria of the game, the equilibrium envelopes in my analysis depend on the initial action profile and identify the least and greatest equilibria that are reachable.

One-directional best-response adjustment processes are not new to the literature on supermodular games, going back at least to Topkis [18]. Echenique [7] used them to develop an algorithm for finding all equilibria in games of strategic complements. More recently, Morris et al. [11] study information design in binary-action supermodular games, making use of precisely the contagion up and contagion down operations that I consider. My interest is instead in what these adjustment processes can reveal about equilibrium structure and best-response dynamics.

Other related work examines how strategic complementarities shape adjustment, contagion (broadly construed), and equilibrium selection. Echenique [6] characterises games of strategic complements, establishing connections with the absence of cycles in Cournot dynamics. Oyama et al. [17] study equilibrium selection under perfect-foresight dynamics, while Oyama and Takahashi [15] examine the contagion and uninvadability of conventions in local-interaction games, including the role of network structure. Finally, Oyama and Takahashi [16] characterise robustness to incomplete information in binary-action supermodular games using monotone potentials.

Supermodular games and directional contagion

Consider a finite game (N,(Xi)i∈N,(πi)i∈N)(N, (X_i)_{i \in N}, (\pi_i)_{i \in N}), where N={1,…,n}N = \{1,\ldots,n\} is the set of players, Xi={a,b}X_i = \{a,b\} with a<ba < b is player ii’s action set, and πi:X→R\pi_i: \mathbf{X} \to\mathbb{R} is her payoff function, with X=∏i∈NXi\mathbf{X} = \prod_{i \in N} X_i. An action profile is denoted by x=(x1,…,xn)∈X\mathbf{x} = (x_1,\ldots,x_n) \in\mathbf{X}, and x−i\mathbf{x}_{-i} denotes the actions of all players other than ii. The action space X\mathbf{X} is equipped with the componentwise order: x≤y\mathbf{x} \leq\mathbf{y} if xi≤yix_i \leq y_i for every i∈Ni \in N, and x<y\mathbf{x} < \mathbf{y} if x≤y\mathbf{x} \leq\mathbf{y} and x≠y\mathbf{x} \neq\mathbf{y}; under this order, X\mathbf{X} is a lattice with meet x∧y\mathbf{x} \wedge\mathbf{y} and join x∨y\mathbf{x} \vee\mathbf{y} given by the componentwise minimum and maximum, respectively.

The games I consider are supermodular: for every player ii, the payoff function πi\pi_i has increasing differences in her own action and the actions of the other players. Equivalently, πi(x∨y)+πi(x∧y)≥πi(x)+πi(y)\pi_i(\mathbf{x} \vee\mathbf{y}) + \pi_i(\mathbf{x} \wedge\mathbf{y}) \geq\pi_i(\mathbf{x}) + \pi_i(\mathbf{y}) for all x,y∈X\mathbf{x},\mathbf{y} \in\mathbf{X} satisfying xi=bx_i = b, yi=ay_i = a, and x−i≤y−i\mathbf{x}_{-i} \leq\mathbf{y}_{-i}. I assume that best responses are unique and denote player ii’s best response by BRi(x−i)\mathrm{BR}_i(\mathbf{x}_{-i}). Supermodularity ensures that each player’s best-response function BRi\mathrm{BR}_i is nondecreasing in x−i\mathbf{x}_{-i}.

An asynchronous best-response path is a sequence of action profiles in which, at each step, one player who is not best responding revises her action. I also consider two variants: contagion up permits only best-responses from aa to bb, while contagion down only allows best-responses from bb to aa. Starting from any profile x\mathbf{x}, let U(x)U(\mathbf{x}) denote the terminal profile obtained by contagion up, and let D(x)D(\mathbf{x}) denote the terminal profile obtained by contagion down. Supermodularity ensures that each terminal profile is unique, i.e., is independent of the order in which eligible players revise.

One behavioural distinction between the directional processes and general best-response dynamics concerns which players can and will revise. At any action profile, we can partition the population NN into four subsets according to each player’s current action and their best response. Under contagion up (contagion down is the mirror image), only one of these subsets is initially eligible to revise, and only players from two of the four subsets can ever change their behaviour. By contrast, under arbitrary best-response dynamics, players from two subsets are initially eligible to revise, but players from all four may eventually do so.

The following result collects properties of the two contagion operators.

Proposition 1 (Contagion operators). For every profile x\boldsymbol{x}, contagion up and contagion down terminate at profiles U(x)U(\boldsymbol{x}) and D(x)D(\boldsymbol{x}) that are independent of the order in which players revise. For any x,y∈X\boldsymbol{x},\boldsymbol{y} \in\mathbf{X} with x≤y\boldsymbol{x} \le\boldsymbol{y}, we have

D(x)≤x≤U(x),D(x)≤D(y),U(x)≤U(y).D(\boldsymbol{x}) \le\boldsymbol{x} \le U(\boldsymbol{x}), \qquad D(\boldsymbol{x}) \le D(\boldsymbol{y}), \qquad U(\boldsymbol{x}) \le U(\boldsymbol{y}).

Moreover, both operators are idempotent in that D2=DD^2 = D and U2=UU^2 = U, and a profile x\boldsymbol{x} is a pure strategy Nash equilibrium if and only if D(x)=x=U(x)D(\boldsymbol{x}) = \boldsymbol{x} = U(\boldsymbol{x}).

Proof. Each contagion process terminates after at most nn revisions, since every player can revise at most once. By supermodularity, a profitable upward revision cannot make another upward revision unprofitable. Consequently, every player who becomes eligible to revise upward remains eligible until she revises, so the terminal profile is independent of the order of revisions. The argument for contagion down is symmetric.

By construction, D(x)≤x≤U(x)D(\boldsymbol{x}) \le\boldsymbol{x} \le U(\boldsymbol{x}). To establish monotonicity, suppose x≤y\boldsymbol{x} \le\boldsymbol{y}. Every upward revision available from x\boldsymbol{x} is also profitable at any higher profile in which that player still chooses aa. Thus, U(x)≤U(y)U(\boldsymbol{x}) \le U(\boldsymbol{y}). The argument for D(x)≤D(y)D(\boldsymbol{x}) \le D(\boldsymbol{y}) is symmetric but opposite.

Since neither contagion process admits further revisions at its terminal profile, it must be that D2=DD^2 = D and U2=UU^2 = U. Finally, it is immediate that x\boldsymbol{x} is a Nash equilibrium precisely when D(x)=x=U(x)D(\boldsymbol{x}) = \boldsymbol{x} = U(\boldsymbol{x}).

Equilibrium structure

Let E\mathcal{E} denote the set of pure Nash equilibria. It is well known that E\mathcal{E} forms a complete lattice under the order inherited from X\mathbf{X}: for any x,y∈E\boldsymbol{x},\boldsymbol{y} \in\mathcal{E}, their meet x∧Ey\boldsymbol{x} \wedge_{\mathcal{E}} \boldsymbol{y} is the greatest equilibrium below both, while their join x∨Ey\boldsymbol{x} \vee_{\mathcal{E}} \boldsymbol{y} is the least equilibrium above both. The next proposition shows that these two equilibria can be constructed by applying the appropriate one-directional best-response process to the componentwise meet and join of the two equilibria, respectively.

Proposition 2 (Constructing the meet and join). Let x,y∈E\mathbf{x},\mathbf{y}\in\mathcal{E}. Then

x∧Ey=D(x∧y),x∨Ey=U(x∨y).\mathbf{x}\mathbin{\wedge_{\mathcal{E}}}\mathbf{y}=D(\mathbf{x}\wedge\mathbf{y}),\qquad\mathbf{x}\mathbin{\vee_{\mathcal{E}}}\mathbf{y}=U(\mathbf{x}\vee\mathbf{y}).

Proof. I show only the argument for the meet: x∧Ey=D(x∧y)\mathbf{x}\mathbin{\wedge_{\mathcal{E}}}\mathbf{y}=D(\mathbf{x}\wedge\mathbf{y}). The argument for the join is virtually identical.

Let z=x∧y\mathbf{z}=\mathbf{x}\wedge\mathbf{y}. Every player choosing aa in z\mathbf{z} chooses aa in at least one of the equilibria x\mathbf{x} and y\mathbf{y}. Since z\mathbf{z} is no higher than either equilibrium, these players must also prefer aa at z\mathbf{z}. Thus, no upward revision is profitable at z\mathbf{z}. Contagion down only makes action aa more attractive and terminates when no downward revision is profitable. Hence D(z)D(\mathbf{z}) is a Nash equilibrium.

Now let h\mathbf{h} be any equilibrium satisfying h≤x,y\mathbf{h}\leq\mathbf{x},\mathbf{y}. Then h≤z\mathbf{h}\leq\mathbf{z}. By monotonicity of contagion down shown in Proposition 1 and the fact that D(h)=hD(\mathbf{h})=\mathbf{h} since h\mathbf{h} is an equilibrium, we have h≤D(z)\mathbf{h}\leq D(\mathbf{z}). Since h\mathbf{h} was arbitrary, it follows that D(z)D(\mathbf{z}) is the greatest equilibrium below both x\mathbf{x} and y\mathbf{y}.

While Proposition 2 shows that applying the “correct” directed contagion operator to the componentwise meet or join of two equilibria generates their meet or join in the equilibrium lattice, it is clear that U(x)U(\mathbf{x}) and D(x)D(\mathbf{x}) need not be Nash equilibria for an arbitrary profile x\mathbf{x}. However, Theorem 1 below shows that applying contagion up and contagion down successively, in either order, always produces a Nash equilibrium. Moreover, the resulting equilibria may differ, and when they do, they are ordered.

Theorem 1 (Equilibrium envelope). For every profile x\mathbf{x}, the profiles e‾(x):=U(D(x))\underline{e}(\mathbf{x}):=U(D(\mathbf{x})) and e‾(x):=D(U(x))\overline{e}(\mathbf{x}):=D(U(\mathbf{x})) are Nash equilibria satisfying

U(D(x))≤D(U(x)).(1)U(D(\mathbf{x}))\leq D(U(\mathbf{x})). \tag*{(1)}

Thus, every profile x\mathbf{x} has an associated equilibrium interval J(x):=[e‾(x),e‾(x)]E\mathcal{J}(\mathbf{x}):=[\underline{e}(\mathbf{x}),\overline{e}(\mathbf{x})]_{\mathcal{E}}.

Proof. Fix a profile x\mathbf{x} and let z=D(x)\mathbf{z}=D(\mathbf{x}). By construction, BR⁡i(z−i)=b\operatorname{BR}_{i}(\mathbf{z}_{-i})=b for every player ii with zi=bz_i=b. Suppose player jj makes a profitable upward revision, producing

z′≥zz' \ge z. By strategic complementarities, BRi(z−i′)≥BRi(z−i)=b\mathrm{BR}_i(z'_{-i}) \ge\mathrm{BR}_i(z_{-i}) = b for every player i≠ji \ne j with zi=bz_i = b. Moreover, BRj(z−j′)=b\mathrm{BR}_j(z'_{-j}) = b, since player jj has just made a profitable best response. Thus, no player has a profitable downward revision at z′z'. Repeating this argument along contagion up, we conclude that U(D(x))U(D(x)) is a Nash equilibrium. The argument for D(U(x))D(U(x)) is the mirror image.

It remains to establish the ordering. Since D(x)≤xD(x) \le x, monotonicity of UU gives U(D(x))≤U(x)U(D(x)) \le U(x). And now, because U(D(x))U(D(x)) is a Nash equilibrium, it is fixed by DD. Applying DD to both sides therefore yields D(U(D(x)))=U(D(x))≤D(U(x))D(U(D(x))) = U(D(x)) \le D(U(x)), as required.

The first observation follows directly from strategic complementarities: once contagion down has eliminated all profitable downward revisions, subsequent upward revisions cannot create new ones. (And vice versa.) The more interesting observation is that the resulting equilibria are ordered: applying down and then up produces an equilibrium that is no higher than up followed by down. The resulting interval is itself a complete sublattice of E\mathcal{E}, whose endpoints can be constructed directly through best-response dynamics.5

While Theorem 1 associates an interval of the equilibrium lattice with every initial profile, a natural question is whether every interval can arise in this way. The following result answers this in the affirmative.6

Theorem 2 (Generating equilibrium intervals). For any two comparable equilibria x≤yx \le y, there exists a profile zz such that D(z)=xD(z) = x and U(z)=yU(z) = y. Moreover, such a profile can be constructed in polynomial time. Consequently, J(z)=[x,y]E\mathcal{J}(z) = [x,y]_{\mathcal{E}}.

The way in which we construct zz is to start at the upper equilibrium and successively lower individual actions, retaining each change whenever applying contagion up to the profile still reaches the upper equilibrium, yy. Once no further lowering of an individual action allows contagion up to reach yy, I then show that contagion down from the resulting profile must reach the lower equilibrium xx. Otherwise, a player “surviving” above the lower equilibrium (i.e., still choosing bb) could have their action lowered and subsequently restored by contagion up, contradicting the fact that no further reduction was possible.

Proof. Fix equilibria x≤yx \le y. If x=yx = y, then we are done, so assume that x<yx < y (given the assumption on unique best-responses, this means that xx and yy must differ in the behaviour of at least two players). The goal is to construct a profile zz that satisfies the conditions with x<z<U(z)=yx < z < U(z) = y.

Step 1: Construction. Start by setting z=yz = y, and consider the set of players ii for whom xi=ax_i = a and zi=bz_i = b. We consider each such player in turn. For each player ii, let z′z' be the profile obtained by changing player ii’s action from bb to aa. If U(z′)=yU(z') = y, update zz by setting z=z′z = z'; otherwise, leave zz unchanged. Once every such player has been considered, the resulting profile zz satisfies U(z)=yU(z) = y and x<z<yx < z < y.

Step 2: Minimality. We now show that, starting from the profile zz constructed in Step 1, any further lowering of actions from bb to aa followed by applying UU will lead to a profile below yy. Again, consider the set of players ii for whom xi=ax_i = a and zi=bz_i = b. For each such player ii, let z′z' be the profile obtained by switching player ii’s action from bb to aa, leaving all other actions unchanged. We will show that U(z′)<yU(z') < y.

Since player ii still chooses bb in zz, lowering her action when she was considered in Step 1 did not preserve the contagion-up outcome yy. Since then, other players’ actions may have been lowered, but none have been raised. By monotonicity of UU, lowering player ii’s action now cannot produce a higher contagion-up outcome than when the change was tested in Step 1. We therefore conclude that U(z′)<yU(z') < y, as required.

Step 3: Contagion down. It remains to show that D(z)=xD(z) = x. By monotonicity, D(z)≥D(x)=xD(z) \ge D(x) = x. Suppose that D(z)>xD(z) > x. We will show that there exists a player ii with xi=ax_i = a and zi=bz_i = b who is best responding at zz. Indeed, some player ii chooses bb in D(z)D(z) but aa in xx. Since D(z)D(z) is stable against downward revisions, player ii prefers bb at D(z)D(z), and so player ii must also prefer bb at zz, since the other players’ actions are at least as great. Thus, player ii is best responding at zz. Now let z′z' be obtained from zz by changing player ii’s action from bb to aa. Since player ii was best responding at zz and the other players’ actions are unchanged, player ii has a profitable upward revision at z′z' that restores zz. By the order-independence of contagion up, U(z′)=U(z)=yU(z') = U(z) = y. But this contradicts Step 2, which established that lowering any player with xi=ax_i = a and zi=bz_i = b must yield U(z′)<yU(z') < y. Therefore D(z)=xD(z) = x, as required.

Step 4: Polynomial time. Consider the profile zz constructed in Step 1. The construction considers at most nn players, and for each player considered we ran contagion up once, with each run having a maximum of nn individual best-responses. Thus, constructing zz requires at most n2n^2 individual best-response revisions.

An example

In this section I illustrate the preceding results using the binary action threshold model of Neary and Newton [14]. Players occupy the vertices of a connected undirected graph and play a two-action coordination game with each of their neighbours. Coordination on either action yields a positive payoff, while any kind of miscoordination yields zero. In this example, the payoff matrix for an interaction between players ii and jj is

abaγ,γ0,0b0,01−γ,1−γ\begin{array}{c|cc} & a & b \\ \hline a & \gamma,\gamma& 0,0 \\ b & 0,0 & 1-\gamma,1-\gamma \end{array}

where γ∈(0,1)\gamma\in(0,1) is common to all players.7 Each player must choose the same action with all her neighbours, and her total utility is the sum of the resulting payoffs. A player prefers bb when the proportion of her neighbours choosing bb exceeds γ\gamma, and prefers aa otherwise. Thus, γ\gamma is the common threshold for choosing bb.

Consider the six-player network in Figure 1, with the players labelled 1 through 6, and the edge set given E={{1,6},{6,2},{2,3},{2,4},{4,5}}E = \{\{1,6\},\{6,2\},\{2,3\},\{2,4\},\{4,5\}\}. Set γ=0.6\gamma= 0.6, so that each player prefers bb whenever more than 60% of her neighbours choose bb. (For this value of γ\gamma, no player is indifferent at any profile.)

The six-player network

Figure 1. The six-player network.

The game has exactly four Nash equilibria, denoted by e0=(a,a,a,a,a,a)e^{0} = (a,a,a,a,a,a), e1=(a,b,b,b,b,a)e^{1} = (a,b,b,b,b,a), e2=(b,b,b,a,a,b)e^{2} = (b,b,b,a,a,b), and e3=(b,b,b,b,b,b)e^{3} = (b,b,b,b,b,b). The equilibria e0e^{0} and e3e^{3} are the least and greatest equilibria, respectively, while e1e^{1} and e2e^{2} are incomparable. Figure 2 depicts the equilibrium lattice, with light vertices representing players that choose action aa and dark vertices representing those who play bb.

The equilibrium lattice

Figure 2. The equilibrium lattice.

Consider first the construction of the meet and the join. The componentwise meet of e1e^{1} and e2e^{2} is (a,b,b,a,a,a)(a,b,b,a,a,a). Starting from this profile, contagion down leads to e0e^{0}: player 2 adopts aa, followed by player 3. Thus, the meet of the two equilibria in the equilibrium lattice is D(e1∧e2)=e0D(e^{1}\wedge e^{2})=e^{0}. Their componentwise join is already e3e^{3}, so U(e1∨e2)=e3U(e^{1}\vee e^{2})=e^{3}.

Next, consider the non-equilibrium profile x=(a,b,a,b,b,b)\boldsymbol{x}=(a,b,a,b,b,b). If population behaviour begins there, then contagion down leads to universal adoption of aa, whereas contagion up leads to universal adoption of bb: D(x)=e0D(\boldsymbol{x})=e^{0} and U(x)=e3U(\boldsymbol{x})=e^{3}. Consequently, the two orders of contagion give e‾(x)=U(D(x))=e0\underline{e}(\boldsymbol{x})=U(D(\boldsymbol{x}))=e^{0} and e‾(x)=D(U(x))=e3\overline{e}(\boldsymbol{x})=D(U(\boldsymbol{x}))=e^{3}. The equilibrium envelope is therefore J(x)=[e0,e3]E=E\mathcal{J}(\boldsymbol{x})=[e^{0},e^{3}]_{\mathcal{E}}=\mathcal{E}.

Finally, the example illustrates the equilibrium intervals. Starting from the non-equilibrium y=(a,b,a,b,b,a)\boldsymbol{y}=(a,b,a,b,b,a), then D(y)=e0D(\boldsymbol{y})=e^{0} and U(y)=e1U(\boldsymbol{y})=e^{1}, and hence J(y)=[e0,e1]E\mathcal{J}(\boldsymbol{y})=[e^{0},e^{1}]_{\mathcal{E}}. Similarly, starting with z=(a,b,b,b,b,b)\boldsymbol{z}=(a,b,b,b,b,b) gives J(z)=[e1,e3]E\mathcal{J}(\boldsymbol{z})=[e^{1},e^{3}]_{\mathcal{E}}.

Equilibrium reachability

In this section I consider how far standard asynchronous best-response dynamics, allowing for best responses in either direction, can travel in a supermodular game. Given an action profile x\boldsymbol{x}, write R(x)\mathcal{R}(\boldsymbol{x}) for the set of equilibria reachable from x\boldsymbol{x} through any such adjustment process.

Although equilibria are only partially ordered, the set of equilibria reachable from any initial profile has a unique minimum and maximum:

Theorem 3 (Extremal reachable equilibria). For every initial profile x\boldsymbol{x},

min⁡R(x)=U(D(x))=e‾(x),max⁡R(x)=D(U(x))=e‾(x).(2)\min\mathcal{R}(\boldsymbol{x})=U(D(\boldsymbol{x}))=\underline{e}(\boldsymbol{x}), \qquad\max\mathcal{R}(\boldsymbol{x})=D(U(\boldsymbol{x}))=\overline{e}(\boldsymbol{x}). \tag*{(2)}

In particular, every reachable equilibrium lies in J(x)\mathcal{J}(\boldsymbol{x}).

Proof. Throughout any best-response path from x\boldsymbol{x}, players choosing bb in D(x)D(\boldsymbol{x}) continue to choose bb, while players choosing aa in U(x)U(\boldsymbol{x}) continue to choose aa. Hence every reachable equilibrium z\boldsymbol{z} satisfies D(x)≤z≤U(x)D(\boldsymbol{x})\leq\boldsymbol{z}\leq U(\boldsymbol{x}). Since z\boldsymbol{z} is an equilibrium, U(D(x))≤z≤D(U(x))U(D(\mathbf{x})) \le z \le D(U(\mathbf{x})). The lower endpoint is reached by contagion down followed by contagion up; the upper by contagion up followed by contagion down.

The monotonicity of UU and DD limits what can be achieved by varying the order of adjustments. The extremal reachable equilibria can therefore be obtained by completing just two successive contagion phases, one in each direction. The updating order matters for which other equilibria are reached, but it cannot take population behaviour beyond these two limits. The following is immediate.

Corollary 1 (Unique reachable equilibrium). The set R(x)\mathcal{R}(\mathbf{x}) contains exactly one equilibrium if and only if e(x)=e‾(x)e(\mathbf{x}) = \overline{e}(\mathbf{x}).

For every action profile, the associated envelope defines the lowest and highest equilibria that can be reached. But this does not mean that every equilibrium in the envelope is reachable. To see this, let’s return to the example in § 5, and consider the initial profile x=(a,b,a,b,b,b)\mathbf{x} = (a,b,a,b,b,b). We already established that J(x)=E\mathcal{J}(\mathbf{x}) = \mathcal{E}, so all four equilibria lie inside the envelope. However, only three are reachable: R(x)={e0,e1,e3}\mathcal{R}(\mathbf{x}) = \{e^0,e^1,e^3\}. Figure 3 illustrates a best-response path to each.

Three asynchronous best-response paths from x = (a, b, a, b, b, b)

Figure 3. Three asynchronous best-response paths from x=(a,b,a,b,b,b)\mathbf{x} = (a,b,a,b,b,b). Arrow labels indicate the revising players in order. Red indicates upward revisions (a→ba \to b), while blue indicates downward revisions (b→ab \to a). Light vertices choose aa and dark vertices choose bb.

Consider what would have to happen to reach the remaining equilibrium, e2=(b,b,b,a,a,b)e^{2} = (b,b,b,a,a,b), from x=(a,b,a,b,b,b)x = (a,b,a,b,b,b). For player 4 to switch to aa, player 2 must first switch to aa. But for player 2 to make this switch, player 3 must still be choosing aa. Once player 2 switches to aa, player 3 no longer has an incentive to switch to bb. Thus, players 2 and 3 cannot both return to bb, as required by e2e^{2}. Hence e2e^{2} is unreachable.

The example shows that an equilibrium may lie within the envelope without being reachable. The following result establishes a further restriction: equilibria strictly contained in an envelope must be incomparable with the profile that generated it.

Proposition 3 (Intermediate equilibria). Let xx be an action profile. Every equilibrium in J(x)\mathcal{J}(x) other than its two endpoints is incomparable with xx.

Proof. Let e∈J(x)e \in\mathcal{J}(x) and suppose x≤ex \le e. By monotonicity, U(x)≤U(e)=eU(x) \le U(e) = e. Since e∈J(x)e \in\mathcal{J}(x), we have e≤D(U(x))≤U(x)≤ee \le D(U(x)) \le U(x) \le e. Hence e=eˉ(x)e = \bar{e}(x). The case where x≥ex \ge e is virtually the same just with signs reversed.

An immediate consequence of Proposition 3 is that reaching an equilibrium strictly inside the envelope, if possible, necessarily involves best-responses in both directions.

Envelope contraction

Having characterised the extremal equilibria reachable from any initial profile, I finish by considering how the equilibrium envelope evolves under best-response dynamics. Theorem 4 shows that the envelope can only contract. Importantly, this holds regardless of the revision protocol.

Theorem 4 (Envelope contraction). Suppose that yy is obtained from xx by allowing any subset of players to simultaneously best respond to xx. Then J(y)⊆J(x)\mathcal{J}(y) \subseteq\mathcal{J}(x), or equivalently,

e‾(x)≤e‾(y)≤eˉ(y)≤eˉ(x).(3)\underline{e}(x) \le\underline{e}(y) \le\bar{e}(y) \le\bar{e}(x). \tag*{(3)}

Proof. By definition, D(x)D(x) admits no profitable downward revisions and therefore D(x)≤yD(x) \le y. A symmetric argument gives y≤U(x)y \le U(x). Now,

U(D(x))=idempotence of DU(D(D(x)))≤since D(x)≤yU(D(y)).U(D(x)) \mathrel{\overset{\text{idempotence of }D}{=}} U(D(D(x))) \mathrel{\underset{\text{since }D(x)\le y}{\le}} U(D(y)).

The argument for the upper endpoint is analogous, giving D(U(y))≤D(U(x))D(U(y)) \le D(U(x)). Hence J(y)⊆J(x)\mathcal{J}(y) \subseteq\mathcal{J}(x).

The key point is that, whatever combination of upward and downward best-responses occurs, the new profile remains between the contagion-down and contagion-up outcomes of the original profile. Applying contagion down followed by contagion up can therefore only raise the lower endpoint of the equilibrium envelope, while reversing the order can only lower the upper endpoint. If only one player best responds, the result is sharper. For example, an upward revision leaves the upper endpoint unchanged and may raise the lower one. Since contagion up would eventually make this revision anyway, making it in advance does not change the outcome. Put simply: best responses can rule out some eventual equilibrium outcomes, but cannot restore possibilities already ruled out.

This observation admits an interpretation in terms of Lyapunov functions. For an action profile xx, define V(x)V(x) as the number of players whose actions differ between the two endpoints of the equilibrium envelope, i.e., V(x)=∣{i∈N:e‾i(x)≠e‾i(x)}∣V(x) = |\{i \in N : \underline{e}_i(x) \ne\overline{e}_i(x)\}|. Theorem 4 implies that VV is weakly decreasing along every best-response path, including those with simultaneous revisions. In this sense, VV is a discrete weak Lyapunov function for the adjustment process. Even when best-response dynamics cycle, the equilibrium envelope must eventually stabilise. Moreover, since VV is integer-valued, every strict contraction decreases it by at least one. We therefore obtain the following.

Corollary 2 (Envelope stabilisation). Along any sequence of best-responses starting from xx, at most V(x)≤nV(x) \le n best responses can strictly change the equilibrium envelope.

Consider again the example in § 5, starting from x=(a,b,a,b,b,b)x=(a,b,a,b,b,b), whose envelope is E\mathcal{E} and hence V(x)=6V(x)=6. If player 3 is selected to best respond, she revises upward, raising the lower endpoint from e0e^{0} to e1e^{1}, while the upper endpoint remains e3e^{3}, reducing VV from 6 to 2. Alternatively, if player 6 best responds by switching from bb to aa, the upper endpoint falls from e3e^{3} to e1e^{1}, while the lower endpoint remains e0e^{0}, reducing VV from 6 to 4. If player 1 is selected to best respond, she switches to bb, collapsing the envelope to {e3}\{e^{3}\}, after which a best response by player 3 leaves it unchanged. Whenever a best response involves a change of action that strictly reduces the equilibrium envelope, at least one disagreement between its endpoint equilibria is eliminated. Once eliminated, any such disagreement can never reappear.

Conclusion

This paper shows how two one-directional best-response processes, contagion up and contagion down, can be used to further explore the equilibrium structure of supermodular games. When combined appropriately, these processes not only construct the meet and join of equilibria, but also identify the extremal outcomes of unrestricted best-response dynamics. The broader lesson is that, at least in supermodular games, quite a lot can be learned about unrestricted best-response dynamics by studying their easier-to-follow one-directional counterparts.

References

  1. [1]Ken Binmore and Larry Samuelson. Muddling through: Noisy equilibrium selection. Journal of Economic Theory, 74(2):235–265, 1997.
  2. [2]Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5(3):387–424, 1993.DOI
  3. [3]Lawrence E. Blume. The statistical mechanics of best-response strategy revision. Games and Economic Behavior, 11(2):111–145, 1995.
  4. [4]Lawrence E. Blume. How noise matters. Games and Economic Behavior, 44(2):251–271, 2003.
  5. [5]Jeremy I. Bulow, John D. Geanakoplos, and Paul D. Klemperer. Multimarket oligopoly: Strategic substitutes and complements. Journal of Political Economy, 93(3):488–511, 1985.DOI
  6. [6]Federico Echenique. A characterization of strategic complementarities. Games and Economic Behavior, 46(2):325–347, 2004.DOI
  7. [7]Federico Echenique. Finding all equilibria in games of strategic complements. Journal of Economic Theory, 135(1):514–532, 2007.DOI
  8. [8]Sanjeev Goyal and Fernando Vega-Redondo. Network formation and social coordination. Games and Economic Behavior, 50(2):178–207, 2005. doi: 10.1016/j.geb.2004.01.005.DOI
  9. [9]Paul Milgrom and John Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica, 58(6):1255–1277, 1990.DOI
  10. [10]Stephen Morris. Contagion. Review of Economic Studies, 67(1):57–78, 2000.DOI
  11. [11]Stephen Morris, Daisuke Oyama, and Satoru Takahashi. Implementation via information design in binary-action supermodular games. Econometrica, 92(3):775–813, 2024.
  12. [12]Philip R. Neary. Multiple-Group Games. PhD thesis, University of California, San Diego, 2011.
  13. [13]Philip R. Neary. Competing conventions. Games and Economic Behavior, 76(1):301–328, 2012.DOI
  14. [14]Philip R. Neary and Jonathan Newton. Heterogeneity in preferences and behavior in threshold models. Journal of Mechanism and Institution Design, 2(1):141–159, 2017.DOI
  15. [15]Daisuke Oyama and Satoru Takahashi. Contagion and uninvadability in local interaction games: The bilingual game and general supermodular games. Journal of Economic Theory, 157:100–127, 2015.DOI
  16. [16]Daisuke Oyama and Satoru Takahashi. Generalized belief operator and robustness in binary-action supermodular games. Econometrica, 88(2):693–726, 2020.DOI
  17. [17]Daisuke Oyama, Satoru Takahashi, and Josef Hofbauer. Monotone methods for equilibrium selection under perfect foresight dynamics. Theoretical Economics, 3(2):155–192, 2008.
  18. [18]Donald M. Topkis. Equilibrium points in nonzero-sum n-person submodular games. SIAM Journal on Control and Optimization, 17(6):773–787, 1979.DOI
  19. [19]Donald M. Topkis. Supermodularity and Complementarity. Princeton University Press, Princeton, NJ, 1998. ISBN 9780691032443.
  20. [20]Xavier Vives. Nash equilibrium with strategic complementarities. Journal of Mathematical Economics, 19(3):305–321, 1990.DOI

Paper details

vlnc:W_6av2s4km
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Economics, Econometrics and Finance

Not recorded for this paper

View statement
Looking for related papers…
Contents