JEL Classification: C78, C72, D71, C62.
Introduction
Models of coalition formation are used in industrial organization, political economy, international trade, and public economics. See the survey by Ray and Vohra [28 ] . Within the bargaining approach to coalition formation, a central question is whether the model yields a unique vector of equilibrium payoffs. Uniqueness makes comparative statics unambiguous without specifying an equilibrium-selection rule. It also provides a single-valued expected payoff map when bargaining is embedded in a larger model.2 In bilateral bargaining, Rubinstein [29 ] established uniqueness of subgame perfect equilibrium payoffs. In multilateral environments, uniqueness of subgame perfect equilibrium payoffs can fail. Examples based on unanimity and simple-majority rules are discussed in Sutton [30 ] and Baron and Ferejohn [4 ] .
This article studies stationary expected payoffs in a model of coalitional bargaining with random recognition and transferable utility. The random-proposer formulation is related to Okada [25 , 26 ] . In every period, one player is selected as proposer and proposes either a feasible coalition that includes herself or an empty coalition. The protocol is closer to legislative bargaining, however, because members of the proposed coalition vote simultaneously and the protocol precludes the coexistence of multiple coalitions.3 The surplus generated by a coalition is proposer-independent and described by a characteristic function. The feasible family of coalitions is not assumed to be upward closed, and the characteristic function is not assumed to be monotone with respect to set inclusion. This allows negative externalities from participation, so adding a player to a coalition can make it infeasible or reduce its total surplus.
The paper makes three contributions. First, Examples 1 and 2 show that proposer independence alone does not guarantee uniqueness. The first example illustrates how delay can generate positive feedback. When a player whose participation lowers coalition surplus passes more often, the other players receive their expected payoffs more often. This can raise their expected payoffs, making them more expensive to recruit and reinforcing her incentive to pass. The example is related to multiplicity arguments based on proposer-dependent surplus, such as the example in Eraslan and Merlo [10 ] , although here the feedback arises with proposer-independent surplus. The second example illustrates with three players that multiplicity can also arise without delay, even when coalition surplus is strictly monotone.4 The positive results therefore focus on the no-delay domain and identify an additional local condition for uniqueness within that domain.5 Appendix A gives sufficient conditions for no delay.
Second, Theorem 1 establishes uniqueness of equilibrium expected payoffs throughout the no-delay domain for M ♮ M^{\natural} M ♮ -concave characteristic functions,6 allowing the recognition probabilities and discount factors to differ across players. The unique equilibrium payoff vector also depends continuously on the primitives. Corollary 1 shows that in a game with three players and simple majority rule, equilibrium expected payoffs are unique for any characteristic function, provided every equilibrium is no-delay.
The proof uses fixed point index methods.7 Equilibrium payoff vectors are characterized as fixed points of a correspondence with total index + 1 +1 + 1 . This reduces uniqueness to showing that every equilibrium payoff vector is isolated and has positive local index. When every proposer has a unique optimal coalition, we show that these properties hold. Thus multiplicity necessarily involves an equilibrium at which some proposer is indifferent between multiple coalitions. To handle ties, we show that M ♮ M^{\natural} M ♮ -concavity implies an equitable grouping property of maximizing menus at every no-delay candidate payoff vector. This property restricts how tied coalitions differ within each proposer’s menu and how recruitment patterns vary across proposers. We use this structure to deform the payoff correspondence locally to a constant map while preserving the equilibrium as its only nearby fixed point. This establishes isolation and local index + 1 +1 + 1 .
Third, we apply these results to joint ventures with coordination costs and government formation with ministerial expertise, and establish comparative statics for productivity and patience. In the first application, coalition surplus combines firms’ productive contributions with congestion and coordination costs across nested groups of firms, allowing surplus to be non-monotone. In the second, a coalition’s surplus is determined by the optimal assignment of its members to cabinet positions. In both applications, the unique equilibrium payoff vector depends continuously on the underlying parameters within the no-delay domain.
The comparative statics hold for M ♮ M^{\natural} M ♮ -concave characteristic functions without further structural assumptions. We vary one primitive at a time over an interval on which every equilibrium is no-delay. A uniform increase in a player’s contribution to every coalition containing her strictly raises her expected payoff, by no more than the surplus increase. Increasing her discount factor weakly raises her expected payoff, with equality possible only if the entire equilibrium payoff vector is unchanged. These comparisons allow maximizing menus and supporting proposal distributions to change.
Our approach builds on earlier applications of degree and fixed point index methods to coalitional bargaining. In a bargaining model with a general agreement space, Kalandrakis [17 ] characterizes pure-strategy stationary equilibria through expected payoff equations and inequalities ensuring optimal coalition choices.8 In a model with externalities in which bargaining continues after coalitions form, Gomes [14 ] characterizes equilibria using a correspondence defined on coalition expected payoffs that incorporates optimal coalition choices. Both use degree or fixed point index methods to derive determinant conditions for global uniqueness. The condition in Kalandrakis [17 ] applies to oligarchic voting rules, and he verifies it for unanimity bargaining over a fixed surplus with linear utilities. Gomes [14 ] verifies his condition for almost all three-player games in which the grand coalition is efficient. Eraslan and McLennan [9 ] establish payoff uniqueness allowing proposer-dependent families of winning coalitions, assuming every successful agreement divides the same fixed surplus.9 Their fixed point index argument uses a correspondence on proposer-specific inclusion probabilities. Our correspondence is instead defined directly on expected payoff space, analogous to Gomes [14 ] . We establish positive local indices using equitable grouping and obtain primitive sufficient conditions for payoff uniqueness through M ♮ M^{\natural} M ♮ -concavity and no delay.
For bargaining over a fixed surplus, Eraslan [7 ] establishes uniqueness in the q q q -quota version of the Baron and Ferejohn [4 ] model with general recognition probabilities and discount factors. Kalandrakis [19 ] develops a method for computing these payoffs that also recovers the uniqueness result. Theorem 1 subsumes this uniqueness result because the unit-surplus q q q -quota model has an M ♮ M^{\natural} M ♮ -concave characteristic function and rules out delay.
For more general characteristic functions, Yan [31 ] gives two uniqueness results under uniform recognition probabilities and a common discount factor. The first establishes uniqueness for symmetric nondecreasing characteristic functions, without requiring concavity in coalition size. For convex (supermodular) characteristic functions, her second result establishes payoff equivalence among stationary equilibria in which no proposed coalition can be enlarged without reducing the proposer’s surplus. Neither of these two results is subsumed by our uniqueness theorem for M ♮ M^{\natural} M ♮ -concave characteristic functions. However, Corollary 2 establishes uniqueness for symmetric nondecreasing concave characteristic functions and allows recognition probabilities and discount factors to differ across players.
In another paper, Yan [32 ] also establishes uniqueness with three players and simple majority rule for a monotone characteristic function, again under uniform recognition probabilities and a common discount factor. In contrast, Corollary 1 allows heterogeneous recognition probabilities and discount factors and non-monotone characteristic functions, provided every equilibrium is no-delay.
Coalition-dependent surplus has also been studied under other bargaining protocols. Ambrus and Lu [2 ] establish uniqueness of Markov perfect equilibrium payoffs for monotone characteristic functions in a continuous-time model with random proposal opportunities and a finite deadline. Battaglini [5 ] studies a model in which a formateur selects a coalition and subsequently negotiates the allocation of its surplus, retaining the ability to switch coalitions during negotiations. He shows that a holdup problem can lead to the formation of inefficient coalitions.
Allowing coalition-dependent surplus makes it possible to study how productivity and voting rules affect payoff distribution and coalition composition. In the additive q q q -quota model of Evdokimov [12 ] , coalition surplus is the sum of its members’ productivities. With uniform recognition probabilities and a common discount factor, an increase in the quota weakly reduces inequality in expected payoffs, as measured by the Gini coefficient. Casas, Gonzalez-Eiras and Loeper [6 ] study a q q q -quota model with productive and unproductive players, where coalition surplus consists of a fixed component Y Y Y plus a common contribution η \eta η from each productive member. When Y / η Y/\eta Y / η is sufficiently large, equilibrium coalitions can include unproductive players while excluding productive ones, making coalition composition inefficient. In both environments, monotonicity and upward-closed feasibility rule out delay by Proposition A.1 . The characteristic functions are M ♮ M^{\natural} M ♮ -concave, so Theorem 1 recovers their payoff uniqueness results within a common framework.
The rest of the paper is organized as follows. § 2 presents the model, characterizes equilibrium payoffs, and introduces the index argument. § 3 presents the multiplicity examples. § 4 introduces the no-delay restriction and the equitable grouping property, and shows that M ♮ M^{\natural} M ♮ -concavity implies this property. Section 5 establishes uniqueness and continuity of equilibrium payoffs. § 6 discusses applications, and § 7 derives comparative statics. § 8 concludes. The appendices provide sufficient conditions for no delay (Appendix A) and proofs (Appendix B). The online appendix derives the equilibrium payoffs in the multiplicity examples, establishes robustness of no-delay multiplicity, and characterizes no delay through a limited-harm condition.
The model
Setup
The set of players is denoted by N = { 1 , … , n } N = \{1,\ldots,n\} N = { 1 , … , n } , where n ≥ 2 n \ge2 n ≥ 2 is the number of players. Each player i ∈ N i \in N i ∈ N is endowed with a vector of exogenous characteristics ( p i , δ i ) (p_i,\delta_i) ( p i , δ i ) , where p i > 0 p_i > 0 p i > 0 is the probability that player i i i becomes a proposer, ∑ i ∈ N p i = 1 \sum_{i\in N} p_i = 1 ∑ i ∈ N p i = 1 , and δ i ∈ ( 0 , 1 ) \delta_i \in(0,1) δ i ∈ ( 0 , 1 ) is the discount factor of player i i i .
A coalition is a subset C ⊆ N C \subseteq N C ⊆ N . An allocation is a vector x ∈ R + n x \in\mathbb{R}^{n}_{+} x ∈ R + n , that is, x i ≥ 0 x_i \ge0 x i ≥ 0 for each i ∈ N i \in N i ∈ N . Each player i ∈ N i \in N i ∈ N values only private consumption, and her utility equals her consumption. The set of feasible coalitions is denoted by W \mathcal{W} W , with ∅ ∉ W \varnothing\notin\mathcal{W} ∅ ∈ / W . For each player i ∈ N i \in N i ∈ N , let W i = { C ∈ W : i ∈ C } \mathcal{W}^{i} = \{C \in\mathcal{W}: i \in C\} W i = { C ∈ W : i ∈ C } denote the set of feasible coalitions that include player i i i , and assume that W i \mathcal{W}^{i} W i is non-empty. Let χ : W → R + + \chi:\mathcal{W} \to\mathbb{R}_{++} χ : W → R ++ be the characteristic function and note that χ ( C ) > 0 \chi(C) > 0 χ ( C ) > 0 for all C ∈ W C \in\mathcal{W} C ∈ W . The characteristic function is not required to be monotone with respect to set inclusion, so the surplus generated by a coalition may decrease when players are added to it. Moreover, W \mathcal{W} W is not required to be upward closed, so C ∈ W C \in\mathcal{W} C ∈ W and C ⊂ D C \subset D C ⊂ D do not necessarily imply D ∈ W D \in\mathcal{W} D ∈ W .
When acting as a proposer, player i i i can either pass or propose to form any coalition C ∈ W i C \in\mathcal{W}^{i} C ∈ W i . Passing is associated with a special empty coalition C ∅ = ∅ C_{\varnothing} = \varnothing C ∅ = ∅ that generates zero surplus, χ ( C ∅ ) = 0 \chi(C_{\varnothing}) = 0 χ ( C ∅ ) = 0 . An allocation x x x is feasible for coalition C C C if ∑ j ∈ C x j ≤ χ ( C ) \sum_{j\in C} x_j \le\chi(C) ∑ j ∈ C x j ≤ χ ( C ) . A pair ( C , x ) (C,x) ( C , x ) is a proposal for player i i i if C ∈ W i ∪ { C ∅ } C \in\mathcal{W}^{i} \cup\{C_{\varnothing}\} C ∈ W i ∪ { C ∅ } and x x x is feasible for C C C . The set of all proposals that player i i i can make is denoted by P i \mathcal{P}_i P i .
In each period t = 1 , 2 , … t = 1,2,\ldots t = 1 , 2 , … , player i ∈ N i \in N i ∈ N becomes a proposer with probability p i p_i p i and makes a proposal ( C , x ) ∈ P i (C,x) \in\mathcal{P}_i ( C , x ) ∈ P i . If the proposed coalition is C ∅ C_{\varnothing} C ∅ (meaning that the proposer passes), the game moves to the next period. And if she makes a proposal ( C , x ) (C,x) ( C , x ) with C ∈ W C \in\mathcal{W} C ∈ W , then the members of C C C simultaneously vote to either accept the proposal or to reject it. If at least one player in C C C rejects the proposal, the game moves to the next period. Otherwise, the allocation x x x is implemented, each player j ∈ N j \in N j ∈ N receives payoff δ j t − 1 x j \delta_j^{t-1}x_j δ j t − 1 x j and the game ends. Each player receives a zero payoff if an agreement is never reached.
In this article, I focus on stationary strategies. A stationary mixed proposal strategy π i \pi_i π i of player i i i is a probability distribution over feasible proposals, that is, π i ∈ Δ ( P i ) \pi_i \in\Delta(\mathcal{P}_i) π i ∈ Δ ( P i ) , and a stationary voting strategy β i \beta_i β i of player i i i is a mapping β i : R → [ 0 , 1 ] \beta_i:\mathbb{R} \to[0,1] β i : R → [ 0 , 1 ] , where β i ( x i ) \beta_i(x_i) β i ( x i ) is the probability that voter i i i votes to accept the proposal that allocates x i x_i x i to player i i i . In particular, the stationary proposal strategies are history-independent and the stationary voting strategies do not depend on the history of proposals, the proposer’s identity, the proposed coalition, or the proposed shares to other players.
A stationary strategy profile σ = ( π , β ) \sigma= (\pi,\beta) σ = ( π , β ) is a stationary subgame perfect equilibrium if there are no profitable deviations given any history, any proposer i i i , and any proposal ( C , x ) (C,x) ( C , x ) .
I restrict attention to stationary subgame perfect equilibria with weakly undominated voting strategies. For the remainder of the article, I will refer to these strategy profiles as equilibria .
Expected payoffs
Any equilibrium strategy profile σ \sigma σ induces a vector of expected payoffs v ( σ ) ∈ R + n v(\sigma) \in\mathbb{R}_{+}^{n} v ( σ ) ∈ R + n , where v i ( σ ) v_i(\sigma) v i ( σ ) is the expected payoff of player i i i . Throughout the paper, v ( σ ) v(\sigma) v ( σ ) denotes the payoff vector induced by a particular strategy profile σ \sigma σ . When no strategy profile is being fixed, I write y y y for a generic expected payoff vector. Thus, y y y is a candidate payoff vector until it is shown to satisfy the equilibrium equations. Let ρ i ( σ ) \rho_i(\sigma) ρ i ( σ ) denote the distribution over coalitions induced by player i i i ’s proposal strategy π i \pi_i π i , treating rejected proposals as passing. For any vector z ∈ R n z \in\mathbb{R}^{n} z ∈ R n and subset of players C ⊆ N C \subseteq N C ⊆ N , write z C z_C z C to denote ∑ i ∈ C z i \sum_{i \in C} z_i ∑ i ∈ C z i . Using this notation, for each i ∈ N i \in N i ∈ N , we can write:
v i ( σ ) = δ i p i S i ( v ( σ ) ) + δ i ∑ j ∈ N p j ∑ C ∈ C j i ( v ( σ ) ) ρ j ( σ ) ( C ) v i ( σ ) , ρ i ( σ ) ∈ Δ ( C i ( v ( σ ) ) ) . (1) \begin{aligned}
v_i(\sigma) &= \delta_i p_i S_i(v(\sigma))+\delta_i\sum_{j\in N}p_j\sum_{C\in\mathcal{C}_j^i(v(\sigma))}\rho_j(\sigma)(C)v_i(\sigma),\\
\rho_i(\sigma)&\in\Delta(\mathcal{C}_i(v(\sigma))). \tag*{(1)}
\end{aligned} v i ( σ ) ρ i ( σ ) = δ i p i S i ( v ( σ )) + δ i j ∈ N ∑ p j C ∈ C j i ( v ( σ )) ∑ ρ j ( σ ) ( C ) v i ( σ ) , ∈ Δ ( C i ( v ( σ ))) . (1)
where
S i ( v ( σ ) ) = max C ∈ W i ∪ { C ∅ } ( χ ( C ) − v C ( σ ) ) , C i ( v ( σ ) ) = arg max C ∈ W i ∪ { C ∅ } ( χ ( C ) − v C ( σ ) ) . (2) \begin{aligned}
S_i(v(\sigma))&=\max_{C\in\mathcal{W}^i\cup\{C_{\varnothing}\}}\left(\chi(C)-v_C(\sigma)\right),\\
\mathcal{C}_i(v(\sigma))&=\underset{C\in\mathcal{W}^i\cup\{C_{\varnothing}\}}{\arg\max}\left(\chi(C)-v_C(\sigma)\right). \tag*{(2)}
\end{aligned} S i ( v ( σ )) C i ( v ( σ )) = C ∈ W i ∪ { C ∅ } max ( χ ( C ) − v C ( σ ) ) , = C ∈ W i ∪ { C ∅ } arg max ( χ ( C ) − v C ( σ ) ) . (2)
and C j i ( v ) = { C ∈ C j ( v ) : i ∈ C or C = C ∅ } \mathcal{C}_j^i(v)=\{C\in\mathcal{C}_j(v):i\in C\text{ or }C=C_{\varnothing}\} C j i ( v ) = { C ∈ C j ( v ) : i ∈ C or C = C ∅ } . We call S i ( v ( σ ) ) S_i(v(\sigma)) S i ( v ( σ )) player i i i ’s proposer surplus , the greatest gain over her expected payoff that she can obtain when recognized. Her continuation probability is ∑ j ∈ N p j ∑ C ∈ C j i ( v ( σ ) ) ρ j ( σ ) ( C ) \sum_{j\in N}p_j\sum_{C\in\mathcal{C}_j^i(v(\sigma))}\rho_j(\sigma)(C) ∑ j ∈ N p j ∑ C ∈ C j i ( v ( σ )) ρ j ( σ ) ( C ) , the probability that bargaining continues to the next period or a coalition containing i i i forms.
The expected payoff v i ( σ ) v_i(\sigma) v i ( σ ) is player i i i ’s continuation payoff if the current proposal is rejected and the game moves to the next period, discounted to the current period. In an equilibrium, weakly undominated voting requires each player i ∈ N i\in N i ∈ N to vote to accept any proposal x x x with x i > v i ( σ ) x_i>v_i(\sigma) x i > v i ( σ ) and to reject any proposal with x i < v i ( σ ) x_i<v_i(\sigma) x i < v i ( σ ) . When x i = v i ( σ ) x_i=v_i(\sigma) x i = v i ( σ ) , voter i i i is indifferent. Without loss of generality, we assume that player i i i votes to accept when indifferent.10 A proposer will also never offer a share to another player i i i that is greater than i i i ’s expected payoff v i ( σ ) v_i(\sigma) v i ( σ ) . Thus v i ( σ ) v_i(\sigma) v i ( σ ) is the cost of player i i i ’s participation in a coalition, and v ( σ ) v(\sigma) v ( σ ) is the corresponding cost vector.
With these facts in mind, consider the components of the expected payoff v i ( σ ) v_i(\sigma) v i ( σ ) for some player i ∈ N i \in N i ∈ N . With probability p i p_i p i , player i i i becomes a proposer. If she proposes an empty coalition C ∅ C_{\varnothing} C ∅ , the game moves to the next period and i i i ’s payoff equals v i ( σ ) v_i(\sigma) v i ( σ ) . If she forms a non-empty coalition C C C , then she allocates v j ( σ ) v_j(\sigma) v j ( σ ) to each other coalition member j ∈ C j \in C j ∈ C and nothing to other players. Combining these two cases, we can write the highest payoff that player i i i can obtain when recognized as v i ( σ ) + max C ∈ W i ∪ { C ∅ } ( χ ( C ) − v C ( σ ) ) v_i(\sigma) + \max_{C \in W_i \cup\{C_{\varnothing}\}}(\chi(C) - v_C(\sigma)) v i ( σ ) + max C ∈ W i ∪ { C ∅ } ( χ ( C ) − v C ( σ )) , where for convenience it is assumed that player i i i pays v i ( σ ) v_i(\sigma) v i ( σ ) to herself when forming a non-empty coalition. If S i ( v ( σ ) ) > 0 S_i(v(\sigma)) > 0 S i ( v ( σ )) > 0 , player i i i strictly prefers to form a non-empty coalition in C i ( v ( σ ) ) C_i(v(\sigma)) C i ( v ( σ )) and randomizes over these maximizers using the proposal distribution ρ i ( σ ) \rho_i(\sigma) ρ i ( σ ) ; if S i ( v ( σ ) ) = 0 S_i(v(\sigma)) = 0 S i ( v ( σ )) = 0 , she is indifferent between proposing the empty coalition C ∅ C_{\varnothing} C ∅ and any non-empty coalitions (if any) with χ ( C ) = v C ( σ ) \chi(C) = v_C(\sigma) χ ( C ) = v C ( σ ) , and randomizes over C i ( v ( σ ) ) C_i(v(\sigma)) C i ( v ( σ )) . In either case, player i i i ’s payoff (either as a share of surplus or as a continuation payoff) equals v i ( σ ) + S i ( v ( σ ) ) v_i(\sigma) + S_i(v(\sigma)) v i ( σ ) + S i ( v ( σ )) . The expression in (1) accounts for the fact that player i i i always includes herself when proposing a non-empty coalition, so p i ∑ C ∈ C i ( v ( σ ) ) ρ i ( σ ) ( C ) = p i p_i \sum_{C \in C_i(v(\sigma))} \rho_i(\sigma)(C) = p_i p i ∑ C ∈ C i ( v ( σ )) ρ i ( σ ) ( C ) = p i always holds.
When player i i i is not a proposer, she votes to accept any proposal that allocates a share of surplus to her that is at least as large as her expected payoff v i ( σ ) v_i(\sigma) v i ( σ ) . Therefore, she receives v i ( σ ) v_i(\sigma) v i ( σ ) when player j ≠ i j \ne i j = i is chosen to become a proposer, which happens with probability p j p_j p j , and either proposes an empty coalition or forms a non-empty coalition C C C that includes player i i i . This means that player i i i receives v i ( σ ) v_i(\sigma) v i ( σ ) with a total probability ∑ j ≠ i p j ∑ C ∈ C j i ( v ( σ ) ) ρ j ( σ ) ( C ) \sum_{j \ne i} p_j \sum_{C \in C_j^i(v(\sigma))} \rho_j(\sigma)(C) ∑ j = i p j ∑ C ∈ C j i ( v ( σ )) ρ j ( σ ) ( C ) , giving us the remaining component of the summation in (1) .
No-tie and tie payoff vectors
Fix an equilibrium σ \sigma σ and write y = v ( σ ) y = v(\sigma) y = v ( σ ) . For this payoff vector, let K ( y ) = { k ∈ N ∣ ∣ C k ( y ) ∣ ≥ 2 } K(y) = \{k \in N \mid|C_k(y)| \ge2\} K ( y ) = { k ∈ N ∣ ∣ C k ( y ) ∣ ≥ 2 } be the set of proposers who are indifferent between multiple coalitions. For each j ∈ N ∖ K ( y ) j \in N \setminus K(y) j ∈ N ∖ K ( y ) , denote by C j ( y ) C_j(y) C j ( y ) the unique coalition in C j ( y ) C_j(y) C j ( y ) . Next, for each i ∈ N i \in N i ∈ N , let C i ( y ) = { j ∈ N ∖ K ( y ) ∣ i ∈ C j ( y ) or C j ( y ) = C ∅ } C^i(y) = \{j \in N \setminus K(y) \mid i \in C_j(y) \text{ or } C_j(y) = C_{\varnothing}\} C i ( y ) = { j ∈ N ∖ K ( y ) ∣ i ∈ C j ( y ) or C j ( y ) = C ∅ } , so that p C i ( y ) p_{C^i(y)} p C i ( y ) is the total proposer probability of non-tied players whose selected coalition either contains i i i or is empty. Define
r i ( σ ) = ∑ k ∈ K ( y ) p k ∑ C ∈ C k ( y ) : C ∋ i or C = C ∅ ρ k ( σ ) ( C ) , i ∈ N . (3) r^i(\sigma) = \sum_{k \in K(y)} p_k \sum_{\substack{C \in C_k(y):\\ C \ni i\ \text{or}\ C=C_{\varnothing}}} \rho_k(\sigma)(C), \qquad i \in N. \tag*{(3)} r i ( σ ) = k ∈ K ( y ) ∑ p k C ∈ C k ( y ) : C ∋ i or C = C ∅ ∑ ρ k ( σ ) ( C ) , i ∈ N . (3)
original probability of being formed, offering each member her expected payoff, and passes otherwise. Since rejection and passing have the same continuation effects, this preserves every player’s expected payoff. If K ( y ) = ∅ K(y)=\varnothing K ( y ) = ∅ , then every proposer has a unique maximizing coalition and (1) becomes
y i = δ i p i S i ( y ) + δ i p C i ( y ) y i , i ∈ N . (4) y_i=\delta_i p_i S_i(y)+\delta_i p_{C_i(y)}y_i,\qquad i\in N. \tag*{(4)} y i = δ i p i S i ( y ) + δ i p C i ( y ) y i , i ∈ N . (4)
An equilibrium σ \sigma σ with K ( y ) = ∅ K(y)=\varnothing K ( y ) = ∅ is called a no-tie equilibrium , and the corresponding vector of expected payoffs y = v ( σ ) y=v(\sigma) y = v ( σ ) is called a no-tie payoff vector .
If K ( y ) ≠ ∅ K(y)\ne\varnothing K ( y ) = ∅ , then tied proposers must satisfy indifference and mixing conditions. In particular, for each k ∈ K ( y ) k\in K(y) k ∈ K ( y ) we have
χ ( C ) − y C = χ ( D ) − y D , for all C , D ∈ C k ( y ) , (5) \chi(C)-y_C=\chi(D)-y_D,\qquad\text{for all }C,D\in C_k(y), \tag*{(5)} χ ( C ) − y C = χ ( D ) − y D , for all C , D ∈ C k ( y ) , (5)
and for each i ∈ N i\in N i ∈ N we have
y i = δ i p i S i ( y ) + δ i ( p C i ( y ) + r i ( σ ) ) y i , (6) y_i=\delta_i p_i S_i(y)+\delta_i\left(p_{C_i(y)}+r^i(\sigma)\right)y_i, \tag*{(6)} y i = δ i p i S i ( y ) + δ i ( p C i ( y ) + r i ( σ ) ) y i , (6)
where r i ( σ ) r^i(\sigma) r i ( σ ) is given by (3) . An equilibrium σ \sigma σ with K ( y ) ≠ ∅ K(y)\ne\varnothing K ( y ) = ∅ is called a tie equilibrium , and the corresponding vector of expected payoffs y = v ( σ ) y=v(\sigma) y = v ( σ ) is called a tie payoff vector .
Characterization of expected payoffs
For each i ∈ N i\in N i ∈ N , let Y i = { y i ∈ R ∣ 0 ≤ y i ≤ max C ∈ W i χ ( C ) } Y_i=\{y_i\in\mathbb{R}\mid0\le y_i\le\max_{C\in\mathcal{W}_i}\chi(C)\} Y i = { y i ∈ R ∣ 0 ≤ y i ≤ max C ∈ W i χ ( C )} be the set of possible expected payoffs for player i i i , and let Y = ∏ i ∈ N Y i Y=\prod_{i\in N}Y_i Y = ∏ i ∈ N Y i . This compact set contains every equilibrium payoff vector.
Extend the notation in (2) to any candidate payoff vector y ∈ Y y\in Y y ∈ Y by setting S i ( y ) = max C ∈ W i ∪ { C ∅ } ( χ ( C ) − y C ) S_i(y)=\max_{C\in\mathcal{W}_i\cup\{C_\varnothing\}}(\chi(C)-y_C) S i ( y ) = max C ∈ W i ∪ { C ∅ } ( χ ( C ) − y C ) and C i ( y ) = arg max C ∈ W i ∪ { C ∅ } ( χ ( C ) − y C ) C_i(y)=\arg\max_{C\in\mathcal{W}_i\cup\{C_\varnothing\}}(\chi(C)-y_C) C i ( y ) = arg max C ∈ W i ∪ { C ∅ } ( χ ( C ) − y C ) . The notation K ( y ) K(y) K ( y ) , C j ( y ) C_j(y) C j ( y ) , and C i ( y ) C^i(y) C i ( y ) , and the tie/no-tie terminology, extend to these candidate vectors in the same way.
For y ∈ Y y\in Y y ∈ Y , define its type by
A ( y ) = ( K ( y ) , ( C k ( y ) ) k ∈ K ( y ) , ( C j ( y ) ) j ∉ K ( y ) ) . (7) \mathcal{A}(y)=\left(K(y),\left(C_k(y)\right)_{k\in K(y)},\left(C_j(y)\right)_{j\notin K(y)}\right). \tag*{(7)} A ( y ) = ( K ( y ) , ( C k ( y ) ) k ∈ K ( y ) , ( C j ( y ) ) j ∈ / K ( y ) ) . (7)
Define the aggregate inclusion polytope at y y y by
R ( y ) = { r ∈ [ 0 , 1 ] n ∣ r i = ∑ k ∈ K ( y ) p k ∑ C ∈ C k ( y ) : C ∋ i or C = C ∅ ρ k ( C ) , ρ k ∈ Δ ( C k ( y ) ) , k ∈ K ( y ) } . (8) R(y)=\left\{r\in[0,1]^n\mid r^i=\sum_{k\in K(y)}p_k\sum_{\substack{C\in C_k(y):\\ C\ni i\ \text{or}\ C=C_\varnothing}}\rho_k(C),\ \rho_k\in\Delta(C_k(y)),\ k\in K(y)\right\}. \tag*{(8)} R ( y ) = ⎩ ⎨ ⎧ r ∈ [ 0 , 1 ] n ∣ r i = k ∈ K ( y ) ∑ p k C ∈ C k ( y ) : C ∋ i or C = C ∅ ∑ ρ k ( C ) , ρ k ∈ Δ ( C k ( y )) , k ∈ K ( y ) ⎭ ⎬ ⎫ . (8)
If S i ( y ) > 0 S_i(y)>0 S i ( y ) > 0 for every i ∈ N i\in N i ∈ N , then
R ( y ) = ∑ k ∈ K ( y ) p k co { 1 C ∣ C ∈ C k ( y ) } , (9) R(y)=\sum_{k\in K(y)}p_k\operatorname{co}\{\mathbf{1}_C\mid C\in C_k(y)\}, \tag*{(9)} R ( y ) = k ∈ K ( y ) ∑ p k co { 1 C ∣ C ∈ C k ( y )} , (9)
where co \operatorname{co} co denotes convex hull and 1 C ∈ { 0 , 1 } n \mathbf{1}_C\in\{0,1\}^n 1 C ∈ { 0 , 1 } n is the incidence vector of coalition C C C . Note that R ( y ) = { 0 } R(y)=\{0\} R ( y ) = { 0 } when K ( y ) = ∅ K(y)=\varnothing K ( y ) = ∅ .
For y ∈ Y y\in Y y ∈ Y , define the payoff correspondence
T ( y ) = { z ∈ R n ∣ z i = δ i p i S i ( y ) + δ i ( p C i ( y ) + r i ) y i , r ∈ R ( y ) } , (10) \mathcal{T}(y)=\left\{z\in\mathbb{R}^n\mid z_i=\delta_i p_i S_i(y)+\delta_i\left(p_{C_i(y)}+r^i\right)y_i,\ r\in R(y)\right\}, \tag*{(10)} T ( y ) = { z ∈ R n ∣ z i = δ i p i S i ( y ) + δ i ( p C i ( y ) + r i ) y i , r ∈ R ( y ) } , (10)
and write Fix ( T ) = { y ∈ Y : y ∈ T ( y ) } \operatorname{Fix}(\mathcal{T})=\{y\in Y:y\in\mathcal{T}(y)\} Fix ( T ) = { y ∈ Y : y ∈ T ( y )} for its fixed point set. T ( y ) \mathcal{T}(y) T ( y ) collects the payoff updates obtained by taking y y y as continuation payoffs and varying proposal distributions over maximizing coalitions.
The following proposition establishes equilibrium existence, characterizes equilibrium expected payoffs as fixed points of T \mathcal{T} T , and gives the properties needed for the index argument. Its proof is standard and is given in Appendix B.§ 1 .
Proposition 1. For y ∈ Y y\in Y y ∈ Y , we have y ∈ T ( y ) y\in\mathcal{T}(y) y ∈ T ( y ) if and only if there exists an equilibrium σ \sigma σ such that v ( σ ) = y v(\sigma)=y v ( σ ) = y . The correspondence T : Y ⇒ Y \mathcal{T}:Y\Rightarrow Y T : Y ⇒ Y is non-empty-valued, compact-valued, convex-valued, and upper hemicontinuous. Moreover, the equilibrium payoff set Fix ( T ) \operatorname{Fix}(\mathcal{T}) Fix ( T ) is non-empty and compact.
Fixed point index and additivity
For a correspondence with the properties in Proposition 1, fixed point index theory associates an integer with any region whose boundary contains no fixed point. The formulation used here is presented in McLennan [22 ] . Our arguments use three properties of the index. Normalization assigns index + 1 +1 + 1 to a constant map on a neighborhood of its value. Continuity implies that the index remains constant along a jointly upper hemicontinuous homotopy on a fixed compact domain with no boundary fixed point. Additivity expresses the index on a region as the sum of the indices on disjoint neighborhoods within that region whose union contains all its fixed points.11 If U U U is relatively open in Y Y Y and T \mathcal{T} T has no fixed point on its relative boundary, write Λ Y ( T ∣ U ‾ ) \Lambda_Y(\mathcal{T}\mid\overline{U}) Λ Y ( T ∣ U ) for the fixed point index of the restriction of T \mathcal{T} T to U ‾ \overline{U} U . When U = Y U=Y U = Y , write Λ Y ( T ) \Lambda_Y(\mathcal{T}) Λ Y ( T ) .
The following result gives the global index that will be compared with the local indices of the fixed points.
Lemma 1. We have Λ Y ( T ) = + 1 \Lambda_Y(\mathcal{T})=+1 Λ Y ( T ) = + 1 .
Proof. Fix c ∈ Y c \in Y c ∈ Y and consider the homotopy
y ↦ ( 1 − s ) c + s T ( y ) , y ∈ Y , s ∈ [ 0 , 1 ] . y \mapsto(1-s)c+s\mathcal{T}(y), \qquad y \in Y,\quad s \in[0,1]. y ↦ ( 1 − s ) c + s T ( y ) , y ∈ Y , s ∈ [ 0 , 1 ] .
By Proposition 1 and convexity of Y Y Y , this homotopy is jointly upper hemicontinuous with non-empty compact convex values in Y Y Y . Continuity and normalization give Λ Y ( T ) = Λ Y ( c ) = + 1 \Lambda_Y(\mathcal{T})=\Lambda_Y(c)=+1 Λ Y ( T ) = Λ Y ( c ) = + 1 . ■
The following lemma reduces uniqueness to showing that every fixed point is isolated and has positive local index.
Lemma 2. Suppose that every point of Fix ( T ) \operatorname{Fix}(\mathcal{T}) Fix ( T ) is isolated relative to Y Y Y . Then Fix ( T ) \operatorname{Fix}(\mathcal{T}) Fix ( T ) is finite. Moreover, for any family ( U ‾ y ) y ∈ Fix ( T ) (\overline{U}_y)_{y\in\operatorname{Fix}(\mathcal{T})} ( U y ) y ∈ Fix ( T ) of relatively open neighborhoods in Y Y Y with pairwise disjoint closures such that U ‾ y ∩ Fix ( T ) = { y } \overline{U}_y\cap\operatorname{Fix}(\mathcal{T})=\{y\} U y ∩ Fix ( T ) = { y } , we have
1 = Λ Y ( T ) = ∑ y ∈ Fix ( T ) Λ Y ( T ∣ U ‾ y ) . 1=\Lambda_Y(\mathcal{T})=\sum_{y\in\operatorname{Fix}(\mathcal{T})}\Lambda_Y(\mathcal{T}|_{\overline{U}_y}). 1 = Λ Y ( T ) = y ∈ Fix ( T ) ∑ Λ Y ( T ∣ U y ) .
If every local index in this sum is positive, then Fix ( T ) \operatorname{Fix}(\mathcal{T}) Fix ( T ) is a singleton.
Proof. By Proposition 1, Fix ( T ) \operatorname{Fix}(\mathcal{T}) Fix ( T ) is non-empty and compact. Since every fixed point is isolated, Fix ( T ) \operatorname{Fix}(\mathcal{T}) Fix ( T ) is finite. The neighborhoods in the statement contain every fixed point of T \mathcal{T} T , so additivity gives
Λ Y ( T ) = ∑ y ∈ Fix ( T ) Λ Y ( T ∣ U ‾ y ) . \Lambda_Y(\mathcal{T})=\sum_{y\in\operatorname{Fix}(\mathcal{T})}\Lambda_Y(\mathcal{T}|_{\overline{U}_y}). Λ Y ( T ) = y ∈ Fix ( T ) ∑ Λ Y ( T ∣ U y ) .
By Lemma 1, the left-hand side equals + 1 +1 + 1 . If every term on the right-hand side is positive, each is an integer of at least one, and hence ∣ Fix ( T ) ∣ = 1 |\operatorname{Fix}(\mathcal{T})|=1 ∣ Fix ( T ) ∣ = 1 . ■
The next subsection shows that every no-tie fixed point is isolated and has local index + 1 +1 + 1 . For tie fixed points, § 4 introduces additional conditions under which Section 5 establishes isolation and a local index of + 1 +1 + 1 .
No-tie payoff vectors and local index
At a no-tie vector, each proposer i i i has a unique maximizing coalition C i C_i C i . These coalitions remain the unique maximizers on a relatively open neighborhood U U U of that vector in Y Y Y . Hence T \mathcal{T} T is single-valued on U U U and agrees with the affine map
t i ( y ) = δ i p i S i ( y ) + δ i p C i y i , i ∈ N . t_i(y)=\delta_i p_i S_i(y)+\delta_i p_{C_i}y_i,\qquad i\in N. t i ( y ) = δ i p i S i ( y ) + δ i p C i y i , i ∈ N .
The map y ↦ y − t ( y ) y \mapsto y-t(y) y ↦ y − t ( y ) has a constant Jacobian J = I n − D y t J=I_n-D_y t J = I n − D y t . Letting d i = 1 − δ i p C i > 0 d_i=1-\delta_{i p}C_i>0 d i = 1 − δ i p C i > 0 , γ i = δ i p i > 0 \gamma_i=\delta_i p_i>0 γ i = δ i p i > 0 , and W = diag ( d 1 , … , d n ) W=\operatorname{diag}(d_1,\ldots,d_n) W = diag ( d 1 , … , d n ) , we can write J = W + Γ J=W+\Gamma J = W + Γ , where Γ i j = γ i I { j ∈ C i } \Gamma_{ij}=\gamma_i \mathbb{I}\{j\in C_i\} Γ ij = γ i I { j ∈ C i } and I { ⋅ } \mathbb{I}\{\cdot\} I { ⋅ } denotes the indicator function.
Lemma 3. The matrix J J J has strictly positive determinant at every no-tie vector. Moreover, every no-tie fixed point y 0 ∈ Fix ( T ) y_0\in\operatorname{Fix}(T) y 0 ∈ Fix ( T ) is isolated relative to Y Y Y and, for every sufficiently small relatively open neighborhood U U U of y 0 y_0 y 0 in Y Y Y , we have Λ Y ( T ∣ U ‾ ) = + 1 \Lambda_Y(T|_{\overline{U}})=+1 Λ Y ( T ∣ U ) = + 1 .
Proof. Fix a no-tie vector y y y , and write C i = C i ( y ) C_i=C_i(y) C i = C i ( y ) and S i = χ ( C i ) − y C i S_i=\chi(C_i)-y_{C_i} S i = χ ( C i ) − y C i for each i ∈ N i\in N i ∈ N .
Step 1: Order the players. If j ∈ C i j\in C_i j ∈ C i and i ∈ C j i\in C_j i ∈ C j , then C i = C j C_i=C_j C i = C j and therefore S i = S j S_i=S_j S i = S j . Indeed, otherwise both coalitions would be feasible for both players, and uniqueness of maximizers would imply simultaneously χ ( C i ) − y C i > χ ( C j ) − y C j \chi(C_i)-y_{C_i}>\chi(C_j)-y_{C_j} χ ( C i ) − y C i > χ ( C j ) − y C j and χ ( C j ) − y C j > χ ( C i ) − y C i \chi(C_j)-y_{C_j}>\chi(C_i)-y_{C_i} χ ( C j ) − y C j > χ ( C i ) − y C i , a contradiction. Similarly, if j ∈ C i j\in C_i j ∈ C i and i ∉ C j i\notin C_j i ∈ / C j , then C i C_i C i is feasible for player j j j , so uniqueness of C j C_j C j implies S j > S i S_j>S_i S j > S i .
Relabel the players so that S 1 ≤ ⋯ ≤ S n S_1\leq\cdots\leq S_n S 1 ≤ ⋯ ≤ S n , keeping players with the same chosen coalition consecutive. Define i ∼ j i\sim j i ∼ j if and only if C i = C j C_i=C_j C i = C j , and let Q 1 , … , Q m Q_1,\ldots,Q_m Q 1 , … , Q m be the corresponding equivalence classes labeled according to increasing S i S_i S i .
Step 2: Block upper-triangular structure. If C i = C ∅ C_i=C_{\varnothing} C i = C ∅ , then Γ i j = 0 \Gamma_{ij}=0 Γ ij = 0 for all j j j , and moreover Γ j i = 0 \Gamma_{ji}=0 Γ j i = 0 for all j ≠ i j\ne i j = i , because i ∈ C j i\in C_j i ∈ C j for some j ≠ i j\ne i j = i would imply S i ≥ S j > 0 S_i\geq S_j>0 S i ≥ S j > 0 , contradicting S i = 0 S_i=0 S i = 0 . Now consider i ∈ Q k i\in Q_k i ∈ Q k and j ∈ Q h j\in Q_h j ∈ Q h with k > h k>h k > h and both C i , C j ≠ C ∅ C_i,C_j\ne C_{\varnothing} C i , C j = C ∅ . If j ∈ C i j\in C_i j ∈ C i , then Step 1 gives S j > S i S_j>S_i S j > S i , contradicting the ordering of the blocks. Hence j ∉ C i j\notin C_i j ∈ / C i and Γ i j = 0 \Gamma_{ij}=0 Γ ij = 0 . Therefore Γ \Gamma Γ , and hence J J J , is block upper-triangular with diagonal blocks indexed by Q 1 , … , Q m Q_1,\ldots,Q_m Q 1 , … , Q m .
Step 3: Determinant. Because J J J is block upper-triangular, det J \det J det J is the product of the determinants of its diagonal blocks. If C i = C ∅ C_i=C_{\varnothing} C i = C ∅ on a block Q k Q_k Q k , then J Q k Q k = W Q k Q k J_{Q_kQ_k}=W_{Q_kQ_k} J Q k Q k = W Q k Q k , with determinant ∏ i ∈ Q k d i > 0 \prod_{i\in Q_k}d_i>0 ∏ i ∈ Q k d i > 0 . Otherwise, all players in Q k Q_k Q k have the same chosen coalition, so J Q k Q k = W Q k Q k + ( γ i ) i ∈ Q k 1 ∣ Q k ∣ T J_{Q_kQ_k}=W_{Q_kQ_k}+(\gamma_i)_{i\in Q_k}\mathbf{1}_{|Q_k|}^{\mathsf T} J Q k Q k = W Q k Q k + ( γ i ) i ∈ Q k 1 ∣ Q k ∣ T , where ( γ i ) i ∈ Q k (\gamma_i)_{i\in Q_k} ( γ i ) i ∈ Q k is the vector of γ i \gamma_i γ i 's on that block. By the matrix determinant lemma,12 det ( J Q k Q k ) = det ( W Q k Q k ) ( 1 + 1 ∣ Q k ∣ T W Q k Q k − 1 ( γ i ) i ∈ Q k ) = ( ∏ i ∈ Q k d i ) ( 1 + ∑ i ∈ Q k γ i d i ) > 0 \det(J_{Q_kQ_k})=\det(W_{Q_kQ_k})\left(1+\mathbf{1}_{|Q_k|}^{\mathsf T}W_{Q_kQ_k}^{-1}(\gamma_i)_{i\in Q_k}\right)=\left(\prod_{i\in Q_k}d_i\right)\left(1+\sum_{i\in Q_k}\frac{\gamma_i}{d_i}\right)>0 det ( J Q k Q k ) = det ( W Q k Q k ) ( 1 + 1 ∣ Q k ∣ T W Q k Q k − 1 ( γ i ) i ∈ Q k ) = ( ∏ i ∈ Q k d i ) ( 1 + ∑ i ∈ Q k d i γ i ) > 0 . Therefore det J > 0 \det J>0 det J > 0 .
Step 4: Local index. Now suppose the no-tie vector is a fixed point, and denote it by y 0 y_0 y 0 . Choose a relatively open neighborhood U U U of y 0 y_0 y 0 in Y Y Y such that the maximizing coalitions remain unchanged on U ‾ \overline{U} U . Consider the homotopy
y ↦ ( 1 − s ) y 0 + s t ( y ) , y ∈ U ‾ , s ∈ [ 0 , 1 ] . y\mapsto(1-s)y_0+st(y),\qquad y\in\overline{U},\quad s\in[0,1]. y ↦ ( 1 − s ) y 0 + s t ( y ) , y ∈ U , s ∈ [ 0 , 1 ] .
This homotopy is jointly continuous and, since Y Y Y is convex, takes values in Y Y Y . Because t t t is affine and t ( y 0 ) = y 0 t(y_0)=y_0 t ( y 0 ) = y 0 , we have
y − ( ( 1 − s ) y 0 + s t ( y ) ) = ( ( 1 − s ) I n + s J ) ( y − y 0 ) . y-\left((1-s)y_0+st(y)\right)=\left((1-s)I_n+sJ\right)(y-y_0). y − ( ( 1 − s ) y 0 + s t ( y ) ) = ( ( 1 − s ) I n + s J ) ( y − y 0 ) .
The matrix ( 1 − s ) I n + s J (1-s)I_n+sJ ( 1 − s ) I n + s J has the same block structure as J J J , with d i d_i d i replaced by ( 1 − s ) + s d i > 0 (1-s)+sd_i>0 ( 1 − s ) + s d i > 0 and γ i \gamma_i γ i by s γ i ≥ 0 s\gamma_i\ge0 s γ i ≥ 0 . The argument in Step 3 therefore gives det ( ( 1 − s ) I n + s J ) > 0 \det((1-s)I_n+sJ)>0 det (( 1 − s ) I n + s J ) > 0 for every s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] . Thus, for every s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] , the equation y = ( 1 − s ) y 0 + s t ( y ) y=(1-s)y_0+st(y) y = ( 1 − s ) y 0 + s t ( y ) has the unique solution y 0 y_0 y 0 in U ‾ \overline{U} U . In particular, y 0 y_0 y 0 is an isolated fixed point of T T T , and no map in the homotopy has a fixed point on the relative boundary of U U U . Continuity and normalization give Λ Y ( T ∣ U ‾ ) = + 1 \Lambda_Y(T|_{\overline{U}})=+1 Λ Y ( T ∣ U ) = + 1 . ■
Consequently, if equilibrium expected payoffs are not unique, at least one equilibrium payoff vector is a tie vector. Indeed, if every fixed point were no-tie, Lemma 3 would make every fixed point isolated with local index + 1 +1 + 1 , and Lemma 2 would imply uniqueness.
Multiplicity of expected payoffs
The following examples show that expected payoffs need not be unique even when the characteristic function is independent of the proposer’s identity. In the first example, multiplicity relies on delay.
Example 1. Let n = 3 n=3 n = 3 , p i = 1 3 p_i=\frac{1}{3} p i = 3 1 , and δ i = 9 10 \delta_i=\frac{9}{10} δ i = 10 9 for all i ∈ N i\in N i ∈ N . Let the collection of winning coalitions be W = { C : ∣ C ∣ ≥ 2 } \mathcal{W}=\{C:|C|\ge2\} W = { C : ∣ C ∣ ≥ 2 } and let the characteristic function be given by χ ( C ) = min i ∈ C a i \chi(C)=\min_{i\in C}a_i χ ( C ) = min i ∈ C a i for all C ∈ W C\in\mathcal{W} C ∈ W , where each a i > 0 a_i>0 a i > 0 is an exogenous parameter. Lower values of a i a_i a i can be interpreted as corresponding to a more harmful player. Further, let a 1 = 2 5 a_1=\frac{2}{5} a 1 = 5 2 and a 2 = a 3 = 1 a_2=a_3=1 a 2 = a 3 = 1 .
In this game, there are exactly three equilibrium expected payoff vectors. Let μ ∈ [ 0 , 1 ] \mu\in[0,1] μ ∈ [ 0 , 1 ] be the probability that player 1 forms a winning coalition, conditional on being recognized, and let y ( μ ) y(\mu) y ( μ ) be the corresponding vector of expected payoffs. The three equilibrium payoff vectors are y ( 0 ) = ( 0 , 3 7 , 3 7 ) y(0)=\left(0,\frac{3}{7},\frac{3}{7}\right) y ( 0 ) = ( 0 , 7 3 , 7 3 ) , y ( 1 3 ) = ( 0 , 2 5 , 2 5 ) y\left(\frac{1}{3}\right)=\left(0,\frac{2}{5},\frac{2}{5}\right) y ( 3 1 ) = ( 0 , 5 2 , 5 2 ) , and y ( 1 ) = ( 6 425 , 6 17 , 6 17 ) y(1)=\left(\frac{6}{425},\frac{6}{17},\frac{6}{17}\right) y ( 1 ) = ( 425 6 , 17 6 , 17 6 ) .
In every equilibrium, players 2 and 3 propose the coalition { 2 , 3 } \{2,3\} { 2 , 3 } . When μ = 0 \mu=0 μ = 0 , player 1 always proposes the empty coalition. When μ = 1 \mu=1 μ = 1 , player 1 mixes uniformly between proposing { 1 , 2 } \{1,2\} { 1 , 2 } and { 1 , 3 } \{1,3\} { 1 , 3 } . When μ = 1 3 \mu=\frac{1}{3} μ = 3 1 , player 1 proposes the empty coalition with probability 2 3 \frac{2}{3} 3 2 and proposes { 1 , 2 } \{1,2\} { 1 , 2 } and { 1 , 3 } \{1,3\} { 1 , 3 } each with probability 1 6 \frac{1}{6} 6 1 .13
The mechanism is related to the example in Eraslan and Merlo [10 ] Section 3.3).14 For a given proposer surplus, a higher continuation probability raises a player’s continuation payoff and therefore makes her a less attractive coalition partner. Delay creates reinforcing feedback because when player 1 passes, players 2 and 3 both receive their continuation payoffs. If their continuation payoffs are high enough, player 1 is more likely to pass. This further raises both continuation probabilities, which raises both continuation payoffs and makes them less attractive coalition partners.
The feedback mechanism in this example relies on delay caused by the non-monotonicity of the characteristic function. The next observation shows that delay is ruled out when a 1 a_1 a 1 is sufficiently high, even though adding player 1 to { 2 , 3 } \{2,3\} { 2 , 3 } continues to reduce coalition surplus. We say that an equilibrium is no-delay , or features immediate agreement, if passing is strictly suboptimal for every player.
Observation 1. Fix the primitives of Example 1, except let a 1 ∈ ( 0 , 1 ) a_1 \in(0,1) a 1 ∈ ( 0 , 1 ) vary while a 2 = a 3 = 1 a_2=a_3=1 a 2 = a 3 = 1 . If a 1 > 3 7 a_1 > \frac{3}{7} a 1 > 7 3 , then every equilibrium is no-delay.
Proof. Fix an equilibrium σ \sigma σ and write y = v ( σ ) y=v(\sigma) y = v ( σ ) . When player 1 is recognized, players 2 and 3 together receive at most y 2 + y 3 y_2+y_3 y 2 + y 3 . When player i ∈ { 2 , 3 } i \in\{2,3\} i ∈ { 2 , 3 } is recognized, their combined payoff is at most 1. If she forms a coalition, this follows because every feasible coalition generates surplus at most 1. If she passes, S i ( y ) = 0 S_i(y)=0 S i ( y ) = 0 , so equation (1) implies y i = 0 y_i=0 y i = 0 , while the other player’s continuation payoff is at most 1. Averaging across recognition and discounting yields
y 2 + y 3 ≤ 6 7 < 1. y_2+y_3 \le\frac{6}{7}<1. y 2 + y 3 ≤ 7 6 < 1.
Thus S i ( y ) ≥ 1 − y 2 − y 3 ≥ 1 7 > 0 S_i(y)\ge1-y_2-y_3\ge\frac{1}{7}>0 S i ( y ) ≥ 1 − y 2 − y 3 ≥ 7 1 > 0 for i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } , so players 2 and 3 strictly prefer to form a non-empty coalition to passing. Suppose that passing is optimal for player 1. Then S 1 ( y ) = 0 S_1(y)=0 S 1 ( y ) = 0 , and equation (1) implies y 1 = 0 y_1=0 y 1 = 0 . Optimality of passing requires a 1 − y 1 − y 2 ≤ 0 a_1-y_1-y_2\le0 a 1 − y 1 − y 2 ≤ 0 and a 1 − y 1 − y 3 ≤ 0 a_1-y_1-y_3\le0 a 1 − y 1 − y 3 ≤ 0 . Hence y 2 , y 3 ≥ a 1 > 3 7 y_2,y_3\ge a_1>\frac{3}{7} y 2 , y 3 ≥ a 1 > 7 3 , contradicting y 2 + y 3 ≤ 6 7 y_2+y_3\le\frac{6}{7} y 2 + y 3 ≤ 7 6 .
Ruling out delay removes the feedback mechanism in Example 1, but does not guarantee uniqueness. The next example has multiple equilibrium payoff vectors even though every equilibrium is no-delay and the characteristic function is strictly monotone.15
Example 2. Let n = 3 n=3 n = 3 , p 1 = 15 16 p_1=\frac{15}{16} p 1 = 16 15 , p 2 = p 3 = 1 32 p_2=p_3=\frac{1}{32} p 2 = p 3 = 32 1 , δ 1 = 16 23 \delta_1=\frac{16}{23} δ 1 = 23 16 , and δ 2 = δ 3 = 64 65 \delta_2=\delta_3=\frac{64}{65} δ 2 = δ 3 = 65 64 . Let the collection of winning coalitions be W = 2 N ∖ { ∅ } \mathcal{W}=2^N\setminus\{\varnothing\} W = 2 N ∖ { ∅ } and let the characteristic function be given by χ ( { 1 } ) = 1 \chi(\{1\})=1 χ ({ 1 }) = 1 , χ ( { 2 } ) = χ ( { 3 } ) = 2 \chi(\{2\})=\chi(\{3\})=2 χ ({ 2 }) = χ ({ 3 }) = 2 , χ ( C ) = 5 2 \chi(C)=\frac{5}{2} χ ( C ) = 2 5 for every two-player coalition C C C , and χ ( N ) = 5 \chi(N)=5 χ ( N ) = 5 . Thus every non-empty coalition is feasible, and coalition surplus is strictly increasing with inclusion.16
proposed by player 1 and surplus 1 when proposed by players 2 or 3. Here, the characteristic function is player-independent and given by χ ( C ) = min i ∈ C a i \chi(C)=\min_{i\in C}a_i χ ( C ) = min i ∈ C a i . In this game, there are exactly three equilibrium expected payoff vectors. Let h ∈ [ 0 , 1 ] h \in[0,1] h ∈ [ 0 , 1 ] be the common probability that players 2 and 3 propose the grand coalition, conditional on being recognized, and let y ( h ) y(h) y ( h ) be the corresponding vector of expected payoffs. The three equilibrium payoff vectors are y ( 0 ) = ( 51 23 , 4 5 , 4 5 ) y(0) = \left(\frac{51}{23},\frac{4}{5},\frac{4}{5}\right) y ( 0 ) = ( 23 51 , 5 4 , 5 4 ) , y ( 1 2 ) = ( 2 , 1 , 1 ) y\left(\frac{1}{2}\right) = (2,1,1) y ( 2 1 ) = ( 2 , 1 , 1 ) , and y ( 1 ) = ( 3 2 , 7 5 , 7 5 ) y(1) = \left(\frac{3}{2},\frac{7}{5},\frac{7}{5}\right) y ( 1 ) = ( 2 3 , 5 7 , 5 7 ) .
Player 1 always proposes the grand coalition. When h = 0 h=0 h = 0 , players 2 and 3 always propose their own singletons. When h = 1 h=1 h = 1 , they always propose the grand coalition. When h = 1 2 h=\frac{1}{2} h = 2 1 , each mixes uniformly between proposing her own singleton and the grand coalition.17
The mechanism again operates through continuation probabilities and continuation payoffs. Starting from the tie equilibrium at h = 1 2 h=\frac{1}{2} h = 2 1 , consider a small increase in the common probability with which players 2 and 3 propose the grand coalition when recognized. Each of players 2 and 3 then receives her continuation payoff more often when the other proposes, raising their continuation payoffs and making them more expensive coalition partners. Since player 1 is recognized frequently and always proposes the grand coalition, these higher recruitment costs lower her continuation payoff, despite her receiving her continuation payoff more often when player 2 or 3 proposes. In this example, the fall in player 1’s continuation payoff exceeds the rise in the continuation payoff of either player 2 or player 3. Hence the cost of recruiting players 1 and 3 falls for proposer 2, and the cost of recruiting players 1 and 2 falls for proposer 3. Players 2 and 3 therefore find the grand coalition more attractive relative to their own singletons, reinforcing the initial increase in grand-coalition proposals.
The two examples show that ruling out delay removes one potential source of multiplicity but does not suffice for uniqueness. The analysis below identifies sufficient conditions for uniqueness by examining equilibrium payoff vectors with ties.
No delay and tie payoff vectors
This section first states the no-delay restriction motivated by Example 1 and shows that it is robust to small perturbations of parameters. It then introduces the equitable grouping property and shows that M ♮ M^\natural M ♮ -concavity implies it. Section 5 uses this property to establish isolation and a local index + 1 +1 + 1 at every no-delay equilibrium payoff vector.
Let Θ = R + + W × relint Δ n − 1 × ( 0 , 1 ) n \Theta= \mathbb{R}_{++}^{\mathcal{W}} \times\operatorname{relint} \Delta^{n-1} \times(0,1)^n Θ = R ++ W × relint Δ n − 1 × ( 0 , 1 ) n be the space of primitives θ = ( χ , p , δ ) \theta=(\chi,p,\delta) θ = ( χ , p , δ ) , where relint Δ n − 1 = { p ∈ ( 0 , 1 ) n : ∑ i p i = 1 } \operatorname{relint} \Delta^{n-1} = \{p \in(0,1)^n : \sum_i p_i = 1\} relint Δ n − 1 = { p ∈ ( 0 , 1 ) n : ∑ i p i = 1 } . For a primitive θ ∈ Θ \theta\in\Theta θ ∈ Θ , objects from § 2.4 are evaluated at θ \theta θ , with this dependence written explicitly when useful. Let E ( θ ) = Fix ( T θ ) \mathcal{E}(\theta)=\operatorname{Fix}(T_\theta) E ( θ ) = Fix ( T θ ) denote the set of equilibrium expected payoff vectors under primitive θ \theta θ .
No delay
A candidate payoff vector y ∈ Y ( θ ) y \in Y(\theta) y ∈ Y ( θ ) is called no-delay if S i ( y ; θ ) > 0 S_i(y;\theta) > 0 S i ( y ; θ ) > 0 for every i ∈ N i \in N i ∈ N , meaning that passing is strictly suboptimal for every proposer. Let Θ N D ⊆ Θ \Theta^{\mathrm{ND}} \subseteq\Theta Θ ND ⊆ Θ denote the set of primitives for which every equilibrium payoff vector is no-delay.
Assumption ND (no delay). The primitive satisfies θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND .
The next result shows that the no-delay restriction is robust to small perturbations of primitives. If nearby games had equilibria in which some player has zero proposer surplus, taking limits would yield such an equilibrium in the original game, contradicting Assumption ND. See Appendix B.§ 2 for the detailed proof.
Lemma 4. The set Θ N D \Theta^{\mathrm{ND}} Θ ND is open in Θ \Theta Θ .
A simple sufficient condition for Assumption ND to hold is that every singleton coalition is feasible. If S i ( y ; θ ) = 0 S_i(y;\theta) = 0 S i ( y ; θ ) = 0 for some player i i i at an equilibrium payoff vector y y y , equation (1) implies y i = 0 y_i = 0 y i = 0 . Forming her feasible singleton would then yield strictly positive proposer surplus χ ( { i } ) \chi(\{i\}) χ ({ i }) , a contradiction. Appendix A gives further sufficient conditions for Assumption ND in both monotone environments and environments with negative externalities.
Tie-difference space and equitable grouping
For a no-delay candidate payoff vector y ∈ Y y \in Y y ∈ Y , let A = A ( y ) \mathcal{A} = \mathcal{A}(y) A = A ( y ) be its type as defined in (7) . Define the tie-difference space
L A = span { 1 C − 1 D ∣ C , D ∈ C k ( y ) , k ∈ K ( y ) } ⊆ R n , (11) L_{\mathcal{A}} = \operatorname{span}\{\mathbf{1}_C - \mathbf{1}_D \mid C,D \in\mathcal{C}_k(y),\ k \in K(y)\} \subseteq\mathbb{R}^n, \tag*{(11)} L A = span { 1 C − 1 D ∣ C , D ∈ C k ( y ) , k ∈ K ( y )} ⊆ R n , (11)
and let L A ⊥ ⊆ R n L_{\mathcal{A}}^\perp\subseteq\mathbb{R}^n L A ⊥ ⊆ R n denote its orthogonal complement.
By (5) , for C , D ∈ C k ( y ) C,D \in\mathcal{C}_k(y) C , D ∈ C k ( y ) , we have χ ( C ) − y C = χ ( D ) − y D \chi(C)-y_C = \chi(D)-y_D χ ( C ) − y C = χ ( D ) − y D , or equivalently ( 1 C − 1 D ) ⊤ y = χ ( C ) − χ ( D ) (\mathbf{1}_C-\mathbf{1}_D)^\top y = \chi(C)-\chi(D) ( 1 C − 1 D ) ⊤ y = χ ( C ) − χ ( D ) . A change from y y y to y + h y+h y + h preserves this equality exactly when ( 1 C − 1 D ) ⊤ h = 0 (\mathbf{1}_C-\mathbf{1}_D)^\top h = 0 ( 1 C − 1 D ) ⊤ h = 0 . Since these difference vectors span L A L_{\mathcal{A}} L A , its orthogonal complement L A ⊥ L_{\mathcal{A}}^\perp L A ⊥ consists of payoff movements h h h that preserve all tie equalities within the maximizing menus at y y y .
The next property restricts the structure of maximizing menus at a no-delay candidate payoff vector. The first part concerns payoff movements that preserve ties within the maximizing menus. Specifically, there must exist disjoint groups of players such that the tie-preserving payoff movements are constant within these groups and zero outside these groups. The second part requires proposers within each group to recruit the same number of players from every group.
Definition 1 (Equitable grouping property). A no-delay candidate payoff vector y ∈ Y y \in Y y ∈ Y satisfies the equitable grouping property if there exist pairwise disjoint non-empty groups G 1 , … , G ℓ ⊆ N G_1,\ldots,G_\ell\subseteq N G 1 , … , G ℓ ⊆ N such that:
(i) the vectors 1 G 1 , … , 1 G ℓ \mathbf{1}_{G_1},\ldots,\mathbf{1}_{G_\ell} 1 G 1 , … , 1 G ℓ form a basis of L A ( y ) ⊥ L^\perp_{A(y)} L A ( y ) ⊥ ;
(ii) for every t , s ∈ { 1 , … , ℓ } t,s \in\{1,\ldots,\ell\} t , s ∈ { 1 , … , ℓ } , the number ∣ C ∩ G s ∣ |C \cap G_s| ∣ C ∩ G s ∣ is the same for all i ∈ G t i \in G_t i ∈ G t and C ∈ C i ( y ) C \in C_i(y) C ∈ C i ( y ) .¹⁷
It is worth looking at some examples of candidate and equilibrium payoff vectors satisfying or violating the equitable grouping property. The first example shows that the tie equilibrium payoff vector in Example 2 violates it.
Example 2 revisited. At the tie equilibrium payoff vector y = ( 2 , 1 , 1 ) y=(2,1,1) y = ( 2 , 1 , 1 ) , the maximizing menus are
C 1 ( y ) = { N } , C 2 ( y ) = { { 2 } , N } , C 3 ( y ) = { { 3 } , N } . C_1(y)=\{N\}, \qquad C_2(y)=\{\{2\},N\}, \qquad C_3(y)=\{\{3\},N\}. C 1 ( y ) = { N } , C 2 ( y ) = {{ 2 } , N } , C 3 ( y ) = {{ 3 } , N } . Consequently, L A ( y ) = span { ( 1 , 0 , 1 ) , ( 1 , 1 , 0 ) } L_{A(y)}=\operatorname{span}\{(1,0,1),(1,1,0)\} L A ( y ) = span {( 1 , 0 , 1 ) , ( 1 , 1 , 0 )} and L A ( y ) ⊥ = span { ( − 1 , 1 , 1 ) } L^\perp_{A(y)}=\operatorname{span}\{(-1,1,1)\} L A ( y ) ⊥ = span {( − 1 , 1 , 1 )} . Since L A ( y ) ⊥ L^\perp_{A(y)} L A ( y ) ⊥ contains no nonzero group indicator, part (i) fails.
The following example shows that the equitable grouping property can be violated because players in one group recruit different numbers of players from the same or another group.
Example 3. Let n = 3 n=3 n = 3 . Let the collection of winning coalitions be W = 2 N ∖ { ∅ } \mathcal{W}=2^N\setminus\{\varnothing\} W = 2 N ∖ { ∅ } and let the characteristic function be given by χ ( { 1 } ) = 5 \chi(\{1\})=5 χ ({ 1 }) = 5 , χ ( { 2 } ) = χ ( { 3 } ) = 3 \chi(\{2\})=\chi(\{3\})=3 χ ({ 2 }) = χ ({ 3 }) = 3 , χ ( C ) = 6 \chi(C)=6 χ ( C ) = 6 for every two-player coalition C C C , and χ ( N ) = 7 \chi(N)=7 χ ( N ) = 7 .
At the candidate payoff vector y = ( 2 , 2 , 2 ) y=(2,2,2) y = ( 2 , 2 , 2 ) , the maximizing menus are
C 1 ( y ) = { { 1 } } , C 2 ( y ) = { { 1 , 2 } , { 2 , 3 } } , C 3 ( y ) = { { 1 , 3 } , { 2 , 3 } } . C_1(y)=\{\{1\}\}, \qquad C_2(y)=\{\{1,2\},\{2,3\}\}, \qquad C_3(y)=\{\{1,3\},\{2,3\}\}. C 1 ( y ) = {{ 1 }} , C 2 ( y ) = {{ 1 , 2 } , { 2 , 3 }} , C 3 ( y ) = {{ 1 , 3 } , { 2 , 3 }} . We have L A ( y ) = span { ( 1 , 0 , − 1 ) , ( 1 , − 1 , 0 ) } L_{A(y)}=\operatorname{span}\{(1,0,-1),(1,-1,0)\} L A ( y ) = span {( 1 , 0 , − 1 ) , ( 1 , − 1 , 0 )} and L A ( y ) ⊥ = span { 1 N } L^\perp_{A(y)}=\operatorname{span}\{\mathbf{1}_N\} L A ( y ) ⊥ = span { 1 N } . Thus part (i) holds with the single group G 1 = N G_1=N G 1 = N . However, part (ii) fails because proposer 1’s maximizing coalition contains one member of this group, while those of proposers 2 and 3 contain two.
To see that the equitable grouping property can hold, first consider the equilibrium payoff vector in the symmetric q q q -quota version of the Baron–Ferejohn model.¹⁸
Example 4. Let 2 ≤ q < n 2 \leq q < n 2 ≤ q < n , p i = 1 n p_i=\frac{1}{n} p i = n 1 , and δ i = δ ∈ ( 0 , 1 ) \delta_i=\delta\in(0,1) δ i = δ ∈ ( 0 , 1 ) for every i ∈ N i \in N i ∈ N . Let the collection of winning coalitions be W = { C ⊆ N : ∣ C ∣ ≥ q } \mathcal{W}=\{C \subseteq N: |C| \geq q\} W = { C ⊆ N : ∣ C ∣ ≥ q } and let the characteristic function be given by χ ( C ) = 1 \chi(C)=1 χ ( C ) = 1 for every C ∈ W C \in\mathcal{W} C ∈ W .
At the equilibrium payoff vector y = ( δ n , … , δ n ) y = \left(\frac{\delta}{n},\ldots,\frac{\delta}{n}\right) y = ( n δ , … , n δ ) , each proposer’s maximizing menu consists of all q q q -player coalitions containing her. We have L A ( y ) = span { e i − e j : i , j ∈ N } L_{A(y)} = \operatorname{span}\{e_i-e_j : i,j \in N\} L A ( y ) = span { e i − e j : i , j ∈ N } and L A ( y ) ⊥ = span { 1 N } L^\perp_{A(y)} = \operatorname{span}\{\mathbf{1}_N\} L A ( y ) ⊥ = span { 1 N } , where e i e_i e i is the i i i th unit vector in R n \mathbb{R}^n R n . Thus both conditions hold with the single group G 1 = N G_1=N G 1 = N , since every maximizing coalition contains exactly q q q members of this group.
Finally, note that L A ( y ) = R n L_{A(y)} = \mathbb{R}^n L A ( y ) = R n implies L A ( y ) ⊥ = { 0 } L^\perp_{A(y)} = \{0\} L A ( y ) ⊥ = { 0 } and therefore the equitable grouping property holds trivially. The following example illustrates this possibility at an equilibrium payoff vector.
Example 5. Let n = 2 n=2 n = 2 , p 1 = p 2 = δ 1 = δ 2 = 1 2 p_1=p_2=\delta_1=\delta_2=\frac{1}{2} p 1 = p 2 = δ 1 = δ 2 = 2 1 , W = 2 N ∖ { ∅ } \mathcal{W}=2^N\setminus\{\varnothing\} W = 2 N ∖ { ∅ } , χ ( { 1 } ) = χ ( { 2 } ) = 3 \chi(\{1\})=\chi(\{2\})=3 χ ({ 1 }) = χ ({ 2 }) = 3 , and χ ( { 1 , 2 } ) = 4 \chi(\{1,2\})=4 χ ({ 1 , 2 }) = 4 . At y = ( 1 , 1 ) y=(1,1) y = ( 1 , 1 ) , the maximizing menus are
C 1 ( y ) = { { 1 } , { 1 , 2 } } , C 2 ( y ) = { { 2 } , { 1 , 2 } } . \mathcal{C}_1(y)=\{\{1\},\{1,2\}\},\qquad\mathcal{C}_2(y)=\{\{2\},\{1,2\}\}. C 1 ( y ) = {{ 1 } , { 1 , 2 }} , C 2 ( y ) = {{ 2 } , { 1 , 2 }} .
We have L A ( y ) = span { ( 1 , 0 ) , ( 0 , 1 ) } = R 2 L_{A(y)}=\operatorname{span}\{(1,0),(0,1)\}=\mathbb{R}^2 L A ( y ) = span {( 1 , 0 ) , ( 0 , 1 )} = R 2 , so L A ( y ) ⊥ = { 0 } L^\perp_{A(y)}=\{0\} L A ( y ) ⊥ = { 0 } . In fact, y = ( 1 , 1 ) y=(1,1) y = ( 1 , 1 ) is an equilibrium payoff vector, at which both players form the grand coalition.
In the next subsection, we present a condition on the set of feasible coalitions W \mathcal{W} W and the characteristic function χ \chi χ that verifies the equitable grouping property uniformly over the no-delay candidate payoff vectors in Y Y Y .
M ♮ M^\natural M ♮ -concave characteristic functions
We will now show that the equitable grouping property is implied by exchange properties of W \mathcal{W} W and χ \chi χ . For any C ⊆ N C\subseteq N C ⊆ N and i , j ∈ N i,j\in N i , j ∈ N , write C − i = C ∖ { i } C-i=C\setminus\{i\} C − i = C ∖ { i } and C + j = C ∪ { j } C+j=C\cup\{j\} C + j = C ∪ { j } . The definition below follows Murota [24 ] .
Definition 2 (M ♮ M^\natural M ♮ -concavity). A function χ : W → R \chi:\mathcal{W}\to\mathbb{R} χ : W → R is M ♮ M^\natural M ♮ -concave if, for any C , D ∈ W C,D\in\mathcal{W} C , D ∈ W and i ∈ C ∖ D i\in C\setminus D i ∈ C ∖ D , either C − i , D + i ∈ W C-i,D+i\in\mathcal{W} C − i , D + i ∈ W and
χ ( C ) + χ ( D ) ≤ χ ( C − i ) + χ ( D + i ) , (12) \chi(C)+\chi(D)\leq\chi(C-i)+\chi(D+i), \tag*{(12)} χ ( C ) + χ ( D ) ≤ χ ( C − i ) + χ ( D + i ) , (12) or there is j ∈ D ∖ C j\in D\setminus C j ∈ D ∖ C such that C − i + j , D + i − j ∈ W C-i+j,D+i-j\in\mathcal{W} C − i + j , D + i − j ∈ W and
χ ( C ) + χ ( D ) ≤ χ ( C − i + j ) + χ ( D + i − j ) . (13) \chi(C)+\chi(D)\leq\chi(C-i+j)+\chi(D+i-j). \tag*{(13)} χ ( C ) + χ ( D ) ≤ χ ( C − i + j ) + χ ( D + i − j ) . (13) This condition requires that any player in C ∖ D C\setminus D C ∖ D can be transferred from C C C to D D D , possibly replacing a player in D ∖ C D\setminus C D ∖ C who moves to C C C , while keeping both coalitions in W \mathcal{W} W and without reducing their combined surplus. It therefore restricts both the set of feasible coalitions W \mathcal{W} W
and the values of the characteristic function χ \chi χ . Note that M ♮ M^{\natural} M ♮ -concavity does not imply that the characteristic function is monotone, as illustrated in § 6.1 .
Subtracting y C y_C y C from χ ( C ) \chi(C) χ ( C ) for each coalition C ∈ W C \in\mathcal{W} C ∈ W preserves M ♮ M^{\natural} M ♮ -concavity because moving players to D D D or exchanging players with D D D leaves the sum y C + y D y_C + y_D y C + y D unchanged. The following lemma derives the equitable grouping property from this condition.
Lemma 5. Fix θ ∈ Θ \theta\in\Theta θ ∈ Θ and suppose that χ \chi χ is M ♮ M^{\natural} M ♮ -concave on W \mathcal{W} W . Every no-delay candidate payoff vector y ∈ Y ( θ ) y \in Y(\theta) y ∈ Y ( θ ) satisfies the equitable grouping property.
The proof is in Appendix B.§ 3 . It shows that the tie-difference space L A ( y ) L_A(y) L A ( y ) is generated by single-player additions, removals, and replacements within maximizing menus. These moves identify the player groups whose indicators span its orthogonal complement L A ⊥ ( y ) L_A^{\perp}(y) L A ⊥ ( y ) . Applying the exchange inequalities to coalitions from different proposers’ menus gives the common recruitment counts within each group.
The converse of Lemma 5 does not hold. Equitable grouping concerns maximizing menus, whereas M ♮ M^{\natural} M ♮ -concavity restricts values across all feasible coalitions. Its exchange inequalities can fail because of the values of coalitions that never maximize the proposer surplus anywhere on Y Y Y , as the following example shows.
Example 6. Let n = 3 n = 3 n = 3 and W = 2 N ∖ { ∅ } \mathcal{W} = 2^N \setminus\{\varnothing\} W = 2 N ∖ { ∅ } . Let the characteristic function be given by χ ( { i } ) = 3 \chi(\{i\}) = 3 χ ({ i }) = 3 for every i ∈ N i \in N i ∈ N , χ ( { 1 , 2 } ) = 4 \chi(\{1,2\}) = 4 χ ({ 1 , 2 }) = 4 , and χ ( { 1 , 3 } ) = χ ( { 2 , 3 } ) = χ ( N ) = 1 \chi(\{1,3\}) = \chi(\{2,3\}) = \chi(N) = 1 χ ({ 1 , 3 }) = χ ({ 2 , 3 }) = χ ( N ) = 1 .
At every y ∈ Y y \in Y y ∈ Y , each coalition C C C with χ ( C ) = 1 \chi(C) = 1 χ ( C ) = 1 yields strictly less proposer surplus than the proposer’s singleton, since 1 − y C < 3 − y i 1 - y_C < 3 - y_i 1 − y C < 3 − y i for every i ∈ C i \in C i ∈ C . Thus, at every no-delay candidate payoff vector, we have
C 1 ( y ) ⊆ { { 1 } , { 1 , 2 } } , C 2 ( y ) ⊆ { { 2 } , { 1 , 2 } } , C 3 ( y ) = { { 3 } } . C_1(y) \subseteq\{\{1\},\{1,2\}\}, \qquad C_2(y) \subseteq\{\{2\},\{1,2\}\}, \qquad C_3(y) = \{\{3\}\}. C 1 ( y ) ⊆ {{ 1 } , { 1 , 2 }} , C 2 ( y ) ⊆ {{ 2 } , { 1 , 2 }} , C 3 ( y ) = {{ 3 }} . The only possible ties give the differences e 2 e_2 e 2 and e 1 e_1 e 1 , respectively. Hence L A ( y ) L_A(y) L A ( y ) is spanned by a subset of { e 1 , e 2 } \{e_1,e_2\} { e 1 , e 2 } . The remaining unit vectors in { e 1 , e 2 , e 3 } \{e_1,e_2,e_3\} { e 1 , e 2 , e 3 } form a basis of its orthogonal complement L A ⊥ ( y ) L_A^{\perp}(y) L A ⊥ ( y ) . Taking the corresponding players as singleton groups, part (i) holds by construction. For example, if L A ( y ) = span { e 1 } L_A(y) = \operatorname{span}\{e_1\} L A ( y ) = span { e 1 } , then L A ⊥ ( y ) = span { e 2 , e 3 } L_A^{\perp}(y) = \operatorname{span}\{e_2,e_3\} L A ⊥ ( y ) = span { e 2 , e 3 } and the groups are G 1 = { 2 } G_1 = \{2\} G 1 = { 2 } and G 2 = { 3 } G_2 = \{3\} G 2 = { 3 } .
For part (ii), note that any tie in the maximizing menus above changes the membership of just one player, whose unit vector therefore belongs to L A ( y ) L_A(y) L A ( y ) . This player lies outside the groups, so ∣ C ∩ G s ∣ \lvert C \cap G_s\rvert ∣ C ∩ G s ∣ is constant over C ∈ C i ( y ) C \in C_i(y) C ∈ C i ( y ) for every i i i and s s s .
However, χ \chi χ is not M ♮ M^{\natural} M ♮ -concave. Taking C = { 1 , 2 } C = \{1,2\} C = { 1 , 2 } , D = { 3 } D = \{3\} D = { 3 } , and i = 1 i = 1 i = 1 , we have
χ ( { 1 , 2 } ) + χ ( { 3 } ) = 7 > 4 = χ ( { 2 } ) + χ ( { 1 , 3 } ) = χ ( { 2 , 3 } ) + χ ( { 1 } ) . \chi(\{1,2\}) + \chi(\{3\}) = 7 > 4 = \chi(\{2\}) + \chi(\{1,3\}) = \chi(\{2,3\}) + \chi(\{1\}). χ ({ 1 , 2 }) + χ ({ 3 }) = 7 > 4 = χ ({ 2 }) + χ ({ 1 , 3 }) = χ ({ 2 , 3 }) + χ ({ 1 }) . Thus both the transfer inequality (12) and the only possible replacement inequality (13) fail.
Uniqueness under M ♮ M^{\natural} M ♮ -concavity
Under M ♮ M^{\natural} M ♮ -concavity, the next lemma establishes isolation and a local index of + 1 +1 + 1 at no-delay equilibrium payoff vectors with ties, extending Lemma 3. The proof uses the equitable grouping property established in Lemma 5 .
Lemma 6. Fix θ ∈ Θ \theta\in\Theta θ ∈ Θ and suppose that χ \chi χ is M ♮ M^{\natural} M ♮ -concave on W \mathcal{W} W . Every no-delay equilibrium payoff vector y 0 ∈ E ( θ ) y_0 \in\mathcal{E}(\theta) y 0 ∈ E ( θ ) is isolated and for every sufficiently small open neighborhood U y 0 U_{y_0} U y 0 of y 0 y_0 y 0 in R n \mathbb{R}^n R n , we have Λ Y ( θ ) ( T θ ∣ U ‾ y 0 ) = + 1 \Lambda_{Y(\theta)}(\mathcal{T}_{\theta}\mid\overline{U}_{y_0})=+1 Λ Y ( θ ) ( T θ ∣ U y 0 ) = + 1 .
The proof in Appendix B.§ 4 uses two homotopies to contract the payoff correspondence y ↦ T θ ( y ) y \mapsto\mathcal{T}_{\theta}(y) y ↦ T θ ( y ) to the constant map y ↦ y 0 y \mapsto y_0 y ↦ y 0 , keeping y 0 y_0 y 0 as the only nearby fixed point throughout. The first gradually replaces proposer surpluses by their values at y 0 y_0 y 0 but uses the maximizing menus at each candidate payoff vector. To rule out other nearby fixed points, consider a fixed point y y y of any correspondence in this homotopy. Nearby payoff changes can only break existing ties. Equitable grouping then implies that the components of y − y 0 y-y_0 y − y 0 are equal within each group at y y y and zero outside their union. The proof also shows that changes in aggregate inclusion probabilities sum to zero within each group. Together with the common recruitment counts, this allows the fixed point equations to be reduced to a homogeneous system for the payoff changes across groups. An adaptation of the ordering and determinant argument in Lemma 3 shows that this system is nonsingular, so y = y 0 y=y_0 y = y 0 . The second homotopy contracts the correspondence with proposer surpluses fixed at their values at y 0 y_0 y 0 to the constant map y ↦ y 0 y \mapsto y_0 y ↦ y 0 . The usage of maximizing menus rules out other nearby fixed points during this contraction. Continuity and normalization then give the local index + 1 +1 + 1 .
Lemma 6 and the uniqueness reduction in Lemma 2 give the following result.
Theorem 1. Fix θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND and suppose that χ \chi χ is M ♮ M^{\natural} M ♮ -concave on W \mathcal{W} W . Then the equilibrium expected payoff vector is unique.
Proof. Since θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND , every equilibrium payoff vector is no-delay. Lemma 6 therefore shows that every fixed point of T θ \mathcal{T}_{\theta} T θ is isolated and has local index + 1 +1 + 1 . Lemma 2 implies that E ( θ ) \mathcal{E}(\theta) E ( θ ) is a singleton. ■
The characteristic function in Example 1 is M ♮ M^{\natural} M ♮ -concave for every choice of the positive parameters ( a 1 , a 2 , a 3 ) (a_1,a_2,a_3) ( a 1 , a 2 , a 3 ) . Thus, keeping the other primitives of Example 1 fixed and allowing a 1 a_1 a 1 to vary, Observation 1 and Theorem 1 give a unique equilibrium payoff vector whenever a 1 ∈ ( 3 / 7 , 1 ) a_1 \in(3/7,1) a 1 ∈ ( 3/7 , 1 ) .
More generally, with three players and simple majority rule, no delay is sufficient for uniqueness because every characteristic function on this feasible family is M ♮ M^{\natural} M ♮ -concave. For two distinct pairs { i , j } \{i,j\} { i , j } and { j , k } \{j,k\} { j , k } , exchanging i i i and k k k gives the same pair of coalitions. For the grand coalition { i , j , k } \{i,j,k\} { i , j , k } and a pair { i , j } \{i,j\} { i , j } , transferring k k k again gives the same pair of coalitions. The exchange inequalities in Definition 2 therefore hold with equality and Theorem 1 gives the following corollary.
Corollary 1. Suppose that n = 3 n=3 n = 3 and W = { C ⊆ N : ∣ C ∣ ≥ 2 } \mathcal{W}=\{C\subseteq N:|C|\geq2\} W = { C ⊆ N : ∣ C ∣ ≥ 2 } . For every θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND , the equilibrium expected payoff vector is unique.
Yan [32 ] establishes uniqueness of equilibrium expected payoffs with three players and simple majority rule when the characteristic function is monotone, recognition probabilities are uniform, and discount factors are common.20 Corollary 1 allows heterogeneous recognition probabilities and discount factors and non-monotone characteristic functions, provided Assumption ND holds.
Example 2 shows that no-delay multiplicity is possible when singleton coalitions are also feasible. The characteristic function used in that example is not M ♮ M^{\natural} M ♮ -concave. To see this, take C = N C=N C = N , D = { 1 } D=\{1\} D = { 1 } , and i = 2 i=2 i = 2 . Then D ∖ C = ∅ D\setminus C=\varnothing D ∖ C = ∅ , so replacement in (13) is impossible. In turn, the transfer inequality (12) fails because χ ( { 1 } ) + χ ( N ) = 6 > 5 = χ ( { 1 , 2 } ) + χ ( { 1 , 3 } ) \chi(\{1\})+\chi(N)=6>5=\chi(\{1,2\})+\chi(\{1,3\}) χ ({ 1 }) + χ ( N ) = 6 > 5 = χ ({ 1 , 2 }) + χ ({ 1 , 3 }) .
Symmetric characteristic functions that are concave in coalition size are M ♮ M^{\natural} M ♮ -concave on W \mathcal{W} W generated by quota rules. To see this, write χ ( C ) = f ( ∣ C ∣ ) \chi(C)=f(|C|) χ ( C ) = f ( ∣ C ∣ ) with f f f concave, and take C , D ∈ W C,D\in\mathcal{W} C , D ∈ W and i ∈ C ∖ D i\in C\setminus D i ∈ C ∖ D . If D ∖ C D\setminus C D ∖ C is non-empty, replacing i i i with any j ∈ D ∖ C j\in D\setminus C j ∈ D ∖ C preserves both coalition sizes, so (13) holds with equality. If D ∖ C D\setminus C D ∖ C is empty, then D D D is a proper subset of C C C , so transferring i i i from C C C to D D D preserves feasibility, and concavity gives
f ( ∣ C ∣ ) + f ( ∣ D ∣ ) ≤ f ( ∣ C ∣ − 1 ) + f ( ∣ D ∣ + 1 ) . f(|C|)+f(|D|)\leq f(|C|-1)+f(|D|+1). f ( ∣ C ∣ ) + f ( ∣ D ∣ ) ≤ f ( ∣ C ∣ − 1 ) + f ( ∣ D ∣ + 1 ) .
Thus (12) holds. If f f f is also nondecreasing, Proposition A.1 implies no delay and Theorem 1 gives the following corollary.
Corollary 2. Fix q ∈ { 1 , … , n } q\in\{1,\ldots,n\} q ∈ { 1 , … , n } and let W = { C ⊆ N : ∣ C ∣ ≥ q } \mathcal{W}=\{C\subseteq N:|C|\geq q\} W = { C ⊆ N : ∣ C ∣ ≥ q } . Suppose that χ ( C ) = f ( ∣ C ∣ ) \chi(C)=f(|C|) χ ( C ) = f ( ∣ C ∣ ) for a nondecreasing concave function f : { q , … , n } → R + + f:\{q,\ldots,n\}\to\mathbb{R}_{++} f : { q , … , n } → R ++ . Then the equilibrium expected payoff vector is unique for every p ∈ relint Δ n − 1 p\in\operatorname{relint}\Delta^{n-1} p ∈ relint Δ n − 1 and δ ∈ ( 0 , 1 ) n \delta\in(0,1)^n δ ∈ ( 0 , 1 ) n .
This result complements Yan [31 ] , who establishes uniqueness for symmetric nondecreasing characteristic functions under uniform recognition probabilities and a common discount factor, without requiring concavity in coalition size. Under concavity, Corollary 2 allows recognition probabilities and discount factors to differ across players.
The proof of Lemma 4 establishes that θ ↦ E ( θ ) \theta\mapsto\mathcal{E}(\theta) θ ↦ E ( θ ) has a closed graph and that equilibrium payoff vectors lie in a common compact set for primitives in a neighborhood of any θ ∈ Θ \theta\in\Theta θ ∈ Θ .20
These properties imply that θ ↦ E ( θ ) \theta\mapsto\mathcal{E}(\theta) θ ↦ E ( θ ) is upper hemicontinuous. Together with uniqueness in Theorem 1, this gives the following corollary.
Corollary 3. On the set of primitives θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND for which χ \chi χ is M ♮ M^{\natural} M ♮ -concave on W \mathcal{W} W , the unique equilibrium expected payoff vector depends continuously on θ \theta θ .
Finally, under Assumption ND, uniqueness of equilibrium expected payoffs also implies uniqueness of continuation probabilities. Let y y y denote the unique equilibrium expected payoff vector. Since y i > 0 y_i > 0 y i > 0 for every i ∈ N i \in N i ∈ N , equation (1) determines each player’s continuation probability uniquely. Under no delay, these are the probabilities of being included in the formed coalition, so their sum gives its expected size, which is therefore unique. Because the agreement is immediate and the coalition surplus is allocated fully, the expected surplus equals ∑ i ∈ N y i / δ i \sum_{i\in N} y_i/\delta_i ∑ i ∈ N y i / δ i and is also unique.
Applications
Many classes of M ♮ M^{\natural} M ♮ -concave functions can be used to model coalition surplus; see Murota [24 ] and Paes Leme [27 ] for surveys. We consider two applications: joint ventures with coordination costs and government formation with ministerial expertise. Although M ♮ M^{\natural} M ♮ -concavity need not survive arbitrary perturbations of the characteristic function, it is preserved by changes in the underlying parameters in these applications.
Joint ventures with coordination costs
Consider firms bargaining over membership and profit sharing in a joint venture requiring at least q q q participants, with the profit subject to congestion and coordination costs. Let w ∈ R n w \in\mathbb{R}^{n} w ∈ R n , where w i w_i w i is firm i i i ’s exogenous contribution to the joint venture profit before accounting for congestion and coordination costs. Let L \mathcal{L} L be a laminar family of subsets of N N N , meaning that any two members of L \mathcal{L} L are disjoint or one contains the other. For each A ∈ L A \in\mathcal{L} A ∈ L , let ϕ A : { 0 , … , ∣ A ∣ } → R \phi_A : \{0,\ldots,|A|\} \to\mathbb{R} ϕ A : { 0 , … , ∣ A ∣ } → R have weakly decreasing increments. Given q ∈ { 1 , … , n } q \in\{1,\ldots,n\} q ∈ { 1 , … , n } , let W = { C ⊆ N : ∣ C ∣ ≥ q } \mathcal{W} = \{C \subseteq N : |C| \ge q\} W = { C ⊆ N : ∣ C ∣ ≥ q } and define
χ ( C ) = ∑ i ∈ C w i + ∑ A ∈ L ϕ A ( ∣ C ∩ A ∣ ) , C ∈ W . \chi(C) = \sum_{i\in C} w_i + \sum_{A\in\mathcal{L}} \phi_A(|C\cap A|), \qquad C \in\mathcal{W}. χ ( C ) = i ∈ C ∑ w i + A ∈ L ∑ ϕ A ( ∣ C ∩ A ∣ ) , C ∈ W .
with parameters chosen so that χ ( C ) > 0 \chi(C) > 0 χ ( C ) > 0 for all C ∈ W C \in\mathcal{W} C ∈ W . For example, taking ϕ A = − g A \phi_A = -g_A ϕ A = − g A , where g A ( 0 ) = 0 g_A(0) = 0 g A ( 0 ) = 0 and g A g_A g A has nonnegative, weakly increasing increments, gives congestion or coordination costs associated with the participating firms in group A A A . Firms then may be partitioned into local operating groups, which are in turn grouped into regions. The local groups, regions, and N N N form a laminar family. The costs g A ( ∣ C ∩ A ∣ ) g_A(|C \cap A|) g A ( ∣ C ∩ A ∣ ) can capture congestion at facilities shared by a local group or coordination among participating firms within a region, while g N ( ∣ C ∣ ) g_N(|C|) g N ( ∣ C ∣ ) captures costs of coordinating the venture as a whole.
These characteristic functions are M ♮ M^{\natural} M ♮ -concave on W \mathcal{W} W ([24 Section 3.6, item 4, and Theorem 3.2] ).21 Note that we allow w i < 0 w_i < 0 w i < 0 . Furthermore, a firm with w i > 0 w_i > 0 w i > 0 can still lower coalition surplus when the additional coordination costs of including it exceed its contribution. Under Assumption ND, Theorem 1 gives a unique equilibrium expected payoff vector. For fixed q q q and L \mathcal{L} L , Corollary 3 implies that this vector depends continuously on w w w , the values of the functions ϕ A \phi_A ϕ A , p p p , and δ \delta δ . Proposition A.2 in Appendix A gives a sufficient condition for ND that allows non-monotone χ \chi χ .
With L = { N } \mathcal{L} = \{N\} L = { N } , coordination costs depend only on the number of participating firms. Taking w i = 1 w_i = 1 w i = 1 for every i ∈ N i \in N i ∈ N and g N ( k ) = max { k − 1 , 0 } g_N(k) = \max\{k - 1, 0\} g N ( k ) = max { k − 1 , 0 } gives χ ( C ) = 1 \chi(C) = 1 χ ( C ) = 1 for every feasible coalition, recovering the q q q -quota version of the model of Baron and Ferejohn [4 ] . With L = ∅ \mathcal{L} = \varnothing L = ∅ and w ∈ R + + w \in\mathbb{R}_{++} w ∈ R ++ , the characteristic function instead gives the additive q q q -quota environment of Evdokimov [12 ] . Both cases have monotone χ \chi χ and upward-closed W \mathcal{W} W , so Proposition A.1 gives no delay and Theorem 1 gives uniqueness. The general specification with L = { N } \mathcal{L} = \{N\} L = { N } also includes the symmetric, nondecreasing, concave characteristic functions of Corollary 2.
Government formation with ministerial expertise
Consider a model of government formation in which a coalition’s surplus depends on its members’ expertise and their assignment to cabinet positions. Let the players be parties, let T T T be a finite set of positions, and let a i t ≥ 0 a_{it} \ge0 a i t ≥ 0 be party i i i ’s contribution to government surplus when it occupies position t t t . Assume that each party has a strictly positive contribution in at least one cabinet position. Given a quota q ∈ { 1 , … , n } q \in\{1,\ldots,n\} q ∈ { 1 , … , n } , let W = { C ⊆ N : ∣ C ∣ ≥ q } \mathcal{W} = \{C \subseteq N : |C| \ge q\} W = { C ⊆ N : ∣ C ∣ ≥ q } and define
χ ( C ) = max M ∑ ( i , t ) ∈ M a i t , C ∈ W , \chi(C) = \max_{M} \sum_{(i,t)\in M} a_{it}, \qquad C \in\mathcal{W}, χ ( C ) = M max ( i , t ) ∈ M ∑ a i t , C ∈ W ,
where the maximum is taken over assignments M ⊆ C × T M \subseteq C \times T M ⊆ C × T in which each party occupies at most one position and each position is assigned to at most one party. Coalition members without a position still contribute to meeting the quota, and unassigned positions contribute zero surplus. The assignment determines the total transferable surplus of the government, which is divided through bargaining.
This assignment formula defines an M ♮ M^{\natural} M ♮ -concave function on 2 N 2^N 2 N (Murota, 2016, Section 3.6, item 6).22 Restricting feasibility to coalitions meeting the quota preserves this property, by the argument in footnote 21 . Our assumption on contributions ensures that χ ( C ) > 0 \chi(C)>0 χ ( C ) > 0 for every feasible coalition. Adding a party expands the available assignments, so the characteristic function is monotone. Proposition A.1 gives no delay, and Theorem 1 therefore yields a unique vector of stationary expected payoffs. Since each χ ( C ) \chi(C) χ ( C ) is a maximum of finitely many linear functions of ( a i t ) (a_{it}) ( a i t ) , Corollary 3 implies that equilibrium expected payoffs depend continuously on ( a i t ) (a_{it}) ( a i t ) , p p p , and δ \delta δ for fixed q q q and T T T .
This specification captures some important special cases. Let there be n n n cabinet positions. Then a diagonal matrix ( a i t ) (a_{it}) ( a i t ) gives the additive q q q -quota environment again. In turn, with identical rows in the matrix ( a i t ) (a_{it}) ( a i t ) , χ ( C ) \chi(C) χ ( C ) equals the sum of the ∣ C ∣ |C| ∣ C ∣ largest entries in the common row, so the characteristic function is symmetric, nondecreasing, and concave in coalition size [27 Section 2] . This gives a special case of Corollary 2.
Monotone comparative statics
As noted in the introduction, uniqueness makes comparisons of equilibrium expected payoffs independent of equilibrium selection. Uniqueness alone, however, does not determine the direction of payoff changes. We show that the equitable grouping property also yields comparative statics for a player’s productivity and discount factor, without imposing further structural assumptions. The comparative statics allow the maximizing menus and supporting proposal distributions to change as the player’s productivity or discount factor changes. The proofs are in Appendix B.5.
Productivity
The first comparative static fixes the collection of feasible coalitions W \mathcal{W} W and perturbs the characteristic function χ \chi χ as follows. Fix a player i ∈ N i \in N i ∈ N and a ∈ R a \in\mathbb{R} a ∈ R . Define χ a ( C ) = χ ( C ) + a I { i ∈ C } \chi_a(C)=\chi(C)+a\mathbb{I}\{i \in C\} χ a ( C ) = χ ( C ) + a I { i ∈ C } for all C ∈ W C \in\mathcal{W} C ∈ W , and let θ a = ( χ a , p , δ ) \theta_a=(\chi_a,p,\delta) θ a = ( χ a , p , δ ) .
If χ \chi χ is M ♮ M^{\natural} M ♮ -concave, then so is χ a \chi_a χ a , because both transfers and replacements preserve the total number of occurrences of player i i i in the two coalitions. In the joint venture application of § 6.1 , this perturbation replaces w i w_i w i with w i + a w_i+a w i + a while holding coordination costs and productivities of other players fixed. In the government formation application of § 6.2 , when there are n n n cabinet positions, this perturbation replaces a i t a_{it} a i t by a i t + a a_{it}+a a i t + a for every position t t t , provided the shifted contributions remain nonnegative.
Proposition 2. Fix θ = ( χ , p , δ ) ∈ Θ \theta= (\chi, p, \delta) \in\Theta θ = ( χ , p , δ ) ∈ Θ with an M ♮ M^\natural M ♮ -concave characteristic function χ \chi χ , and fix i ∈ N i \in N i ∈ N . Let I ⊆ R I \subseteq\mathbb{R} I ⊆ R be an interval such that θ a ∈ Θ N D \theta_a \in\Theta^{\mathrm{ND}} θ a ∈ Θ ND for every a ∈ I a \in I a ∈ I , and let y ( a ) y(a) y ( a ) be the unique equilibrium payoff vector under θ a \theta_a θ a . For any a , a ′ ∈ I a, a' \in I a , a ′ ∈ I with a < a ′ a < a' a < a ′ , we have
0 < y i ( a ′ ) − y i ( a ) ≤ a ′ − a . 0 < y_i(a') - y_i(a) \leq a' - a. 0 < y i ( a ′ ) − y i ( a ) ≤ a ′ − a .
Thus a player strictly benefits from a uniform increase in her productivity, and her payoff gain is at most the productivity increase.23 If W W W is upward closed and χ \chi χ is monotone, then χ a \chi_a χ a is monotone for every a ≥ 0 a \geq0 a ≥ 0 . Proposition A.1 therefore ensures that the conclusion applies throughout I = [ 0 , ∞ ) I = [0, \infty) I = [ 0 , ∞ ) .
Patience
The second comparative static fixes χ \chi χ , p p p , and the discount factors of all players other than i i i . For d ∈ ( 0 , 1 ) d \in(0,1) d ∈ ( 0 , 1 ) , write δ i d = d \delta_i^d = d δ i d = d , δ j d = δ j \delta_j^d = \delta_j δ j d = δ j for j ≠ i j \ne i j = i , and let θ d = ( χ , p , δ d ) \theta^d = (\chi, p, \delta^d) θ d = ( χ , p , δ d ) .
Proposition 3. Fix θ = ( χ , p , δ ) ∈ Θ \theta= (\chi, p, \delta) \in\Theta θ = ( χ , p , δ ) ∈ Θ with an M ♮ M^\natural M ♮ -concave characteristic function χ \chi χ , and fix i ∈ N i \in N i ∈ N . Let I ⊆ ( 0 , 1 ) I \subseteq(0,1) I ⊆ ( 0 , 1 ) be an interval such that θ d ∈ Θ N D \theta^d \in\Theta^{\mathrm{ND}} θ d ∈ Θ ND for every d ∈ I d \in I d ∈ I , and let y ( d ) y(d) y ( d ) be the unique equilibrium payoff vector under θ d \theta^d θ d . For any d , d ′ ∈ I d, d' \in I d , d ′ ∈ I with d < d ′ d < d' d < d ′ , we have
y i ( d ) ≤ y i ( d ′ ) , y_i(d) \leq y_i(d'), y i ( d ) ≤ y i ( d ′ ) , where equality holds if and only if y ( d ) = y ( d ′ ) y(d) = y(d') y ( d ) = y ( d ′ ) .
A player’s payoff is therefore weakly increasing in her own discount factor.24 If her payoff is unchanged between two discount factors, every player’s payoff is unchanged throughout the interval between them. If W W W is upward closed and χ \chi χ is monotone, Proposition A.1 ensures that the result applies throughout I = ( 0 , 1 ) I = (0,1) I = ( 0 , 1 ) .
The increase in expected payoff need not be strict, as illustrated by the following example.
Example 5 revisited. Keep the other primitives of Example 5 fixed and allow δ 1 = d \delta_1 = d δ 1 = d to vary. For every d ∈ [ 1 2 , 2 3 ] d \in\left[\frac{1}{2}, \frac{2}{3}\right] d ∈ [ 2 1 , 3 2 ] , the unique equilibrium payoff vector remains y ( d ) = ( 1 , 1 ) y(d) = (1,1) y ( d ) = ( 1 , 1 ) , at which player 1 proposes { 1 , 2 } \{1,2\} { 1 , 2 } , and player 2 proposes { 1 , 2 } \{1,2\} { 1 , 2 } with probability 2 d − 3 \frac{2}{d} - 3 d 2 − 3 and { 2 } \{2\} { 2 } otherwise.
Although Proposition 3 rules out a decrease in y i ( d ) y_i(d) y i ( d ) , the player’s ex ante expected payoff y i ( d ) d \frac{y_i(d)}{d} d y i ( d ) can decrease. In the example above, player 1’s ex ante expected payoff is 1 d \frac{1}{d} d 1 and is strictly decreasing in d ∈ [ 1 2 , 2 3 ] d \in\left[\frac{1}{2}, \frac{2}{3}\right] d ∈ [ 2 1 , 3 2 ] . In the Baron–Ferejohn model with 2 ≤ q < n 2 \leq q < n 2 ≤ q < n , Kawamori (2005, Theorem 1) shows that a player’s ex ante expected payoff is strictly decreasing in her own discount factor when recognition probabilities are sufficiently close to uniform and discount factors sufficiently close to a common value. His result also implies that, under these conditions, her expected payoff y i y_i y i is strictly increasing in her own discount factor.25
Conclusion
In this paper, we show that proposer independence does not guarantee uniqueness of stationary expected payoffs in coalitional bargaining, even with strictly monotone characteristic functions that rule out equilibrium delay. Using fixed point index methods, we show how an equitable grouping property of maximizing menus yields uniqueness under no delay. We verify this property for M ♮ M^\natural M ♮ -concave characteristic functions and establish continuity of the unique equilibrium payoff vector. We also derive comparative statics for a player’s productivity and discount factor. Applications to joint ventures and government formation illustrate these results.
In environments covered by Theorem 1, uniqueness makes comparative statics independent of equilibrium selection. A natural next step is to study the effects of changes in the quota, recognition probabilities, and more general changes in coalition surplus. These questions may require additional structure, such as the threshold structure of recruitment used in the additive model of Evdokimov [12 ] .
Another direction is to identify weaker restrictions on coalition surplus and feasibility that ensure uniqueness under no delay. M ♮ M^\natural M ♮ -concavity is a sufficient condition for the equitable grouping property. The uniqueness argument applies more generally when this property holds in a neighborhood of every equilibrium payoff vector. Identifying other primitive conditions that guarantee this property would therefore extend the result beyond M ♮ M^\natural M ♮ -concavity.
Turning to equilibrium delay, consider an equilibrium in which some players always pass and all remaining players have positive proposer surplus. Removing the passing players and all coalitions containing them yields a reduced game with adjusted recognition probabilities and discount factors. If the same partition holds across all equilibria, our analysis applies to this common reduced game. Identifying primitive conditions that justify this reduction would extend our analysis to some environments with delay. More difficult cases arise when the set of players who always pass differs across equilibria or when players with zero proposer surplus sometimes form non-empty coalitions. We leave these extensions for future work.
Sufficient conditions for no delay
This appendix gives two further sufficient conditions for Assumption ND. The first concerns the standard monotone environment, in which feasible coalitions are upward closed and coalition surplus is monotone.
Proposition A.1. Fix θ = ( χ , p , δ ) ∈ Θ \theta=(\chi,p,\delta)\in\Theta θ = ( χ , p , δ ) ∈ Θ . Suppose that the feasible family W \mathcal{W} W is upward closed, in the sense that C ∈ W C\in\mathcal{W} C ∈ W and C ⊆ D ⊆ N C\subseteq D\subseteq N C ⊆ D ⊆ N imply D ∈ W D\in\mathcal{W} D ∈ W , and that χ \chi χ is monotone on W \mathcal{W} W , in the sense that C , D ∈ W C,D\in\mathcal{W} C , D ∈ W and C ⊆ D C\subseteq D C ⊆ D imply χ ( C ) ≤ χ ( D ) \chi(C)\le\chi(D) χ ( C ) ≤ χ ( D ) . Then θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND .
Proof. Suppose that some player i i i has S i ( y ; θ ) = 0 S_i(y;\theta)=0 S i ( y ; θ ) = 0 at an equilibrium payoff vector y y y . The equilibrium equation (1) then implies y i = 0 y_i=0 y i = 0 . Moreover, not all players can have zero proposer surplus. Indeed, if S k ( y ; θ ) = 0 S_k(y;\theta)=0 S k ( y ; θ ) = 0 for every k ∈ N k\in N k ∈ N , then the equilibrium equations imply y k = 0 y_k=0 y k = 0 for every k ∈ N k\in N k ∈ N . But for any player j j j , the set W j \mathcal{W}^j W j is non-empty by assumption, so choosing any coalition C ∈ W j C\in\mathcal{W}^j C ∈ W j gives S j ( y ; θ ) ≥ χ ( C ) − y C = χ ( C ) > 0 S_j(y;\theta)\ge\chi(C)-y_C=\chi(C)>0 S j ( y ; θ ) ≥ χ ( C ) − y C = χ ( C ) > 0 , a contradiction. Thus there exists some proposer j j j with strictly positive proposer surplus. If C ∈ C j ( y ; θ ) C\in\mathcal{C}_j(y;\theta) C ∈ C j ( y ; θ ) , then upward-closed feasibility and monotonicity imply that player i i i can propose C ∪ { i } C\cup\{i\} C ∪ { i } and obtain proposer surplus at least χ ( C ) − y C > 0 \chi(C)-y_C>0 χ ( C ) − y C > 0 , a contradiction. ■
A second sufficient condition for Assumption ND compares the largest coalition surplus available to each player with the largest coalition surplus overall. For a given primitive θ = ( χ , p , δ ) \theta=(\chi,p,\delta) θ = ( χ , p , δ ) , define χ ∗ = max C ∈ W χ ( C ) \chi^*=\max_{C\in\mathcal{W}}\chi(C) χ ∗ = max C ∈ W χ ( C ) , χ i ∗ = max C ∈ W i χ ( C ) \chi_i^*=\max_{C\in\mathcal{W}^i}\chi(C) χ i ∗ = max C ∈ W i χ ( C ) , and δ ˉ = max i ∈ N δ i \bar{\delta}=\max_{i\in N}\delta_i δ ˉ = max i ∈ N δ i .
Proposition A.2. Fix primitives θ = ( χ , p , δ ) ∈ Θ \theta=(\chi,p,\delta)\in\Theta θ = ( χ , p , δ ) ∈ Θ . Suppose that χ i ∗ > δ ˉ χ ∗ \chi_i^*>\bar{\delta}\chi^* χ i ∗ > δ ˉ χ ∗ for every i ∈ N i\in N i ∈ N . Then θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND .*
Proof. Fix y ∈ E ( θ ) y\in\mathcal{E}(\theta) y ∈ E ( θ ) . Any agreement allocates at most χ ∗ \chi^* χ ∗ , and expected payoffs include at least one period of discounting. Hence y N ≤ δ ˉ χ ∗ y_N\le\bar{\delta}\chi^* y N ≤ δ ˉ χ ∗ . For any i ∈ N i\in N i ∈ N , choose C i ∈ W i C_i\in\mathcal{W}^i C i ∈ W i with χ ( C i ) = χ i ∗ \chi(C_i)=\chi_i^* χ ( C i ) = χ i ∗ . Since y C i ≤ y N y_{C_i}\le y_N y C i ≤ y N , we have S i ( y ; θ ) ≥ χ i ∗ − y C i ≥ χ i ∗ − δ ˉ χ ∗ > 0 S_i(y;\theta)\ge\chi_i^*-y_{C_i}\ge\chi_i^*-\bar{\delta}\chi^*>0 S i ( y ; θ ) ≥ χ i ∗ − y C i ≥ χ i ∗ − δ ˉ χ ∗ > 0 . Hence every equilibrium is no-delay. ■
Proposition A.2 can rule out delay even when adding a player reduces coalition surplus. This simple test is conservative, however, because it ignores recognition probabilities and their effect on expected payoffs. It also becomes increasingly demanding as players become more patient. For fixed χ \chi χ , the condition can remain satisfied as δ ˉ \bar{\delta} δ ˉ approaches one only if every player belongs to some coalition attaining the largest feasible surplus χ ∗ \chi^* χ ∗ .
Online Appendix OA.3 gives an exact characterization of no delay through a limited harm condition on reduced games. As shown in Online Appendix OA.3.1, in the setting of Observation 1 this condition holds if and only if a 1 > 3 7 a_1>\frac{3}{7} a 1 > 7 3 , compared with the bound a 1 > 9 10 a_1>\frac{9}{10} a 1 > 10 9 from Proposition A.2.
Proofs
Proof of Proposition 1
Proof. For y ∈ Y y \in Y y ∈ Y and ρ = ( ρ i ) i ∈ N \rho= (\rho_i)_{i \in N} ρ = ( ρ i ) i ∈ N with ρ i ∈ Δ ( C i ( y ) ) \rho_i \in\Delta(C_i(y)) ρ i ∈ Δ ( C i ( y )) , extend each ρ i \rho_i ρ i by assigning probability zero to coalitions outside C i ( y ) C_i(y) C i ( y ) , and define
t i ( y , ρ ) = δ i p i ( y i + S i ( y ) ) + δ i ∑ j ≠ i p j ∑ C ∈ W j ∪ { C ∅ } : C ∋ i or C = C ∅ ρ j ( C ) y i , i ∈ N . t_i(y,\rho) = \delta_i p_i(y_i + S_i(y)) + \delta_i \sum_{j \ne i} p_j \sum_{\substack{C \in\mathcal{W}^j \cup\{C_{\varnothing}\}: \\ C \ni i \text{ or } C = C_{\varnothing}}} \rho_j(C)y_i,\qquad i \in N. t i ( y , ρ ) = δ i p i ( y i + S i ( y )) + δ i j = i ∑ p j C ∈ W j ∪ { C ∅ } : C ∋ i or C = C ∅ ∑ ρ j ( C ) y i , i ∈ N .
The definition of R ( y ) R(y) R ( y ) in (8) implies that T ( y ) \mathcal{T}(y) T ( y ) defined in (10) is exactly the set of all vectors t ( y , ρ ) t(y,\rho) t ( y , ρ ) generated by such ρ \rho ρ .
Suppose first that σ \sigma σ is an equilibrium and let y = v ( σ ) y = v(\sigma) y = v ( σ ) . By (1) , there exist distributions ρ i ∈ Δ ( C i ( y ) ) \rho_i \in\Delta(C_i(y)) ρ i ∈ Δ ( C i ( y )) for each i ∈ N i \in N i ∈ N such that y = t ( y , ρ ) y = t(y,\rho) y = t ( y , ρ ) . Hence y ∈ T ( y ) y \in\mathcal{T}(y) y ∈ T ( y ) .
Conversely, suppose that y ∈ T ( y ) y \in\mathcal{T}(y) y ∈ T ( y ) . Choose distributions ρ i ∈ Δ ( C i ( y ) ) \rho_i \in\Delta(C_i(y)) ρ i ∈ Δ ( C i ( y )) such that y = t ( y , ρ ) y = t(y,\rho) y = t ( y , ρ ) . Construct a stationary strategy profile σ \sigma σ as follows. Each proposer i i i chooses a coalition C i ∈ C i ( y ) C_i \in C_i(y) C i ∈ C i ( y ) according to ρ i \rho_i ρ i . If C i = C ∅ C_i = C_{\varnothing} C i = C ∅ , she passes; otherwise she offers y j y_j y j to each j ∈ C i ∖ { i } j \in C_i \setminus\{i\} j ∈ C i ∖ { i } , offers zero to players outside C i C_i C i , and keeps the remaining surplus. Each voter i i i accepts a proposal if and only if it allocates at least y i y_i y i to her.
Let d = ∑ j ∈ N p j ρ j ( C ∅ ) d = \sum_{j \in N} p_j \rho_j(C_{\varnothing}) d = ∑ j ∈ N p j ρ j ( C ∅ ) be the ex ante probability that C ∅ C_{\varnothing} C ∅ is proposed under σ \sigma σ . Because all prescribed non-empty proposals are accepted, the payoffs induced by σ \sigma σ satisfy
v i ( σ ) = t i ( y , ρ ) + δ i d ( v i ( σ ) − y i ) , i ∈ N . v_i(\sigma) = t_i(y,\rho) + \delta_i d\bigl(v_i(\sigma) - y_i\bigr),\qquad i \in N. v i ( σ ) = t i ( y , ρ ) + δ i d ( v i ( σ ) − y i ) , i ∈ N .
Since t ( y , ρ ) = y t(y,\rho) = y t ( y , ρ ) = y and δ i d < 1 \delta_i d < 1 δ i d < 1 , it follows that v ( σ ) = y v(\sigma) = y v ( σ ) = y . By construction, every proposer i i i randomizes only over coalitions in C i ( y ) C_i(y) C i ( y ) , that is, over maximizers of χ ( C ) − y C \chi(C) - y_C χ ( C ) − y C , so no proposer can profitably deviate. The voting rule is optimal and weakly undominated because y i y_i y i is the continuation payoff of player i i i . Hence σ \sigma σ is an equilibrium.
The correspondence T \mathcal{T} T is non-empty-valued. Moreover, T \mathcal{T} T maps Y Y Y into itself. To see this, first note that t i ( y , ρ ) ≥ 0 t_i(y,\rho) \ge0 t i ( y , ρ ) ≥ 0 for all i ∈ N i \in N i ∈ N . Further, if C ∈ C i ( y ) C \in C_i(y) C ∈ C i ( y ) , then either C = C ∅ C = C_{\varnothing} C = C ∅ and y i + S i ( y ) = y i y_i + S_i(y) = y_i y i + S i ( y ) = y i , or C ≠ C ∅ C \ne C_{\varnothing} C = C ∅ and y i + S i ( y ) = y i + χ ( C ) − y C = χ ( C ) − ∑ ℓ ∈ C ∖ { i } y ℓ ≤ max D ∈ W i χ ( D ) y_i + S_i(y) = y_i + \chi(C) - y_C = \chi(C) - \sum_{\ell\in C \setminus\{i\}} y_\ell\le\max_{D \in\mathcal{W}^i} \chi(D) y i + S i ( y ) = y i + χ ( C ) − y C = χ ( C ) − ∑ ℓ ∈ C ∖ { i } y ℓ ≤ max D ∈ W i χ ( D ) . Thus both y i + S i ( y ) y_i + S_i(y) y i + S i ( y ) and y i y_i y i belong to Y i Y_i Y i . Since the total probability weight attached to these terms is at most one, it follows that t i ( y , ρ ) ∈ Y i t_i(y,\rho) \in Y_i t i ( y , ρ ) ∈ Y i for every i ∈ N i \in N i ∈ N .
For the remaining properties of T \mathcal{T} T , note that y ↦ Δ ( C i ( y ) ) y \mapsto\Delta(C_i(y)) y ↦ Δ ( C i ( y )) has compact convex values. Its values are exactly the distributions maximizing expected proposer surplus over the fixed simplex Δ ( W i ∪ { C ∅ } ) \Delta(\mathcal{W}^i \cup\{C_{\varnothing}\}) Δ ( W i ∪ { C ∅ }) , so y ↦ Δ ( C i ( y ) ) y \mapsto\Delta(C_i(y)) y ↦ Δ ( C i ( y )) is upper hemicontinuous by the maximum theorem [1 Theorem 17.31] . Since t ( y , ρ ) t(y,\rho) t ( y , ρ ) is continuous in ( y , ρ ) (y,\rho) ( y , ρ ) and affine in ρ \rho ρ , the induced correspondence T \mathcal{T} T is compact-valued, convex-valued, and upper hemicontinuous by Aliprantis and Border [1 ] . Kakutani’s fixed point theorem [1 Corollary 17.55] implies existence of y ∈ Y y \in Y y ∈ Y such that y ∈ T ( y ) y \in\mathcal{T}(y) y ∈ T ( y ) .
Finally, upper hemicontinuity and compact values imply that T \mathcal{T} T has a closed graph. Therefore Fix ( T ) \operatorname{Fix}(\mathcal{T}) Fix ( T ) is closed in the compact set Y Y Y , and hence is compact. ■
Proof of Lemma 4
Proof. Step 1: The graph of the correspondence E : Θ ⇉ R + n \mathcal{E} : \Theta\rightrightarrows\mathbb{R}_{+}^{n} E : Θ ⇉ R + n is closed. Let θ ℓ → θ \theta^{\ell} \to\theta θ ℓ → θ and y ℓ ∈ E ( θ ℓ ) y^{\ell} \in\mathcal{E}(\theta^{\ell}) y ℓ ∈ E ( θ ℓ ) with y ℓ → y y^{\ell} \to y y ℓ → y . We want to show that y ∈ E ( θ ) y \in\mathcal{E}(\theta) y ∈ E ( θ ) . Since y ℓ ∈ Y ( θ ℓ ) y^{\ell} \in Y(\theta^{\ell}) y ℓ ∈ Y ( θ ℓ ) , passing to the limit in the inequalities defining Y ( θ ℓ ) Y(\theta^{\ell}) Y ( θ ℓ ) gives y ∈ Y ( θ ) y \in Y(\theta) y ∈ Y ( θ ) .
For each ℓ \ell ℓ , choose proposal distributions ρ i ℓ ∈ Δ ( C i ( y ℓ ; θ ℓ ) ) \rho_{i}^{\ell} \in\Delta(C_{i}(y^{\ell};\theta^{\ell})) ρ i ℓ ∈ Δ ( C i ( y ℓ ; θ ℓ )) , i ∈ N i \in N i ∈ N , supporting the payoff equations at y ℓ y^{\ell} y ℓ under θ ℓ \theta^{\ell} θ ℓ . Extend each ρ i ℓ \rho_{i}^{\ell} ρ i ℓ by assigning probability zero to coalitions outside C i ( y ℓ ; θ ℓ ) C_{i}(y^{\ell};\theta^{\ell}) C i ( y ℓ ; θ ℓ ) , so that each distribution belongs to the fixed simplex Δ ( W i ∪ { C ∅ } ) \Delta(\mathcal{W}^{i} \cup\{C_{\varnothing}\}) Δ ( W i ∪ { C ∅ }) . Since each ρ i ℓ \rho_{i}^{\ell} ρ i ℓ belongs to a fixed compact simplex and there are finitely many players, we can pass to a subsequence along which every ρ i ℓ \rho_{i}^{\ell} ρ i ℓ converges. Denote the corresponding limits by ρ i \rho_{i} ρ i , i ∈ N i \in N i ∈ N .
If ρ i ( C ) > 0 \rho_{i}(C) > 0 ρ i ( C ) > 0 , then ρ i ℓ ( C ) > 0 \rho_{i}^{\ell}(C) > 0 ρ i ℓ ( C ) > 0 for all sufficiently large ℓ \ell ℓ , and therefore χ ℓ ( C ) − y C ℓ ≥ χ ℓ ( D ) − y D ℓ \chi^{\ell}(C) - y_{C}^{\ell} \geq\chi^{\ell}(D) - y_{D}^{\ell} χ ℓ ( C ) − y C ℓ ≥ χ ℓ ( D ) − y D ℓ for every D ∈ W i ∪ { C ∅ } D \in\mathcal{W}^{i} \cup\{C_{\varnothing}\} D ∈ W i ∪ { C ∅ } . Passing to the limit, we obtain C ∈ C i ( y ; θ ) C \in C_{i}(y;\theta) C ∈ C i ( y ; θ ) . Thus ρ i ∈ Δ ( C i ( y ; θ ) ) \rho_{i} \in\Delta(C_{i}(y;\theta)) ρ i ∈ Δ ( C i ( y ; θ )) for every i ∈ N i \in N i ∈ N .
Each surplus S i ( y ; θ ) S_{i}(y;\theta) S i ( y ; θ ) is continuous in ( y , θ ) (y,\theta) ( y , θ ) , because it is the maximum of finitely many continuous functions. Taking limits in the payoff equations
y i ℓ = δ i ℓ ρ i ℓ ( y i ℓ + S i ( y ℓ ; θ ℓ ) ) + δ i ℓ ∑ j ≠ i p j ℓ ∑ C ∈ W j ∪ { C ∅ } : C ∋ i or C = C ∅ ρ j ℓ ( C ) y i ℓ , i ∈ N , y_{i}^{\ell} = \delta_{i}^{\ell}\rho_{i}^{\ell}(y_{i}^{\ell} + S_{i}(y^{\ell};\theta^{\ell})) + \delta_{i}^{\ell}\sum_{j \ne i} p_{j}^{\ell} \sum_{\substack{C \in\mathcal{W}^{j} \cup\{C_{\varnothing}\}: \\ C \ni i\ \text{or}\ C=C_{\varnothing}}} \rho_{j}^{\ell}(C)y_{i}^{\ell}, \qquad i \in N, y i ℓ = δ i ℓ ρ i ℓ ( y i ℓ + S i ( y ℓ ; θ ℓ )) + δ i ℓ j = i ∑ p j ℓ C ∈ W j ∪ { C ∅ } : C ∋ i or C = C ∅ ∑ ρ j ℓ ( C ) y i ℓ , i ∈ N ,
implies that the limiting distributions satisfy the payoff equations at y y y under θ \theta θ . Hence y ∈ T θ ( y ) y \in\mathcal{T}_{\theta}(y) y ∈ T θ ( y ) , and Proposition 1 gives y ∈ E ( θ ) y \in\mathcal{E}(\theta) y ∈ E ( θ ) .
Step 2: The set Θ N D \Theta^{\mathrm{ND}} Θ ND is open in Θ \Theta Θ . Take any sequence θ ℓ ∈ Θ ∖ Θ N D \theta^{\ell} \in\Theta\setminus\Theta^{\mathrm{ND}} θ ℓ ∈ Θ ∖ Θ ND with θ ℓ → θ \theta^{\ell} \to\theta θ ℓ → θ . Fix a small neighborhood θ ∈ V ⊂ Θ \theta\in V \subset\Theta θ ∈ V ⊂ Θ with compact closure. Define Y ‾ i = [ 0 , sup θ ~ ∈ V max C ∈ W i χ ~ ( C ) ] \overline{Y}_{i} = [0,\sup_{\widetilde{\theta} \in V}\max_{C \in\mathcal{W}^{i}}\widetilde{\chi}(C)] Y i = [ 0 , sup θ ∈ V max C ∈ W i χ ( C )] for each i ∈ N i \in N i ∈ N , where θ ~ = ( χ ~ , p ~ , δ ~ ) \widetilde{\theta} = (\widetilde{\chi},\widetilde{p},\widetilde{\delta}) θ = ( χ , p , δ ) , and let Y ‾ = Y ‾ 1 × ⋯ × Y ‾ n \overline{Y} = \overline{Y}_{1} \times\cdots\times\overline{Y}_{n} Y = Y 1 × ⋯ × Y n . Then Y ( θ ~ ) ⊆ Y ‾ Y(\widetilde{\theta}) \subseteq\overline{Y} Y ( θ ) ⊆ Y for every θ ~ ∈ V \widetilde{\theta} \in V θ ∈ V , and Y ‾ \overline{Y} Y is compact. After discarding finitely many terms, we can assume that θ ℓ ∈ V \theta^{\ell} \in V θ ℓ ∈ V for every ℓ \ell ℓ . For each ℓ \ell ℓ , choose y ℓ ∈ E ( θ ℓ ) y^{\ell} \in\mathcal{E}(\theta^{\ell}) y ℓ ∈ E ( θ ℓ ) and i ℓ ∈ N i_{\ell} \in N i ℓ ∈ N such that S i ℓ ( y ℓ ; θ ℓ ) = 0 S_{i_{\ell}}(y^{\ell};\theta^{\ell}) = 0 S i ℓ ( y ℓ ; θ ℓ ) = 0 . Since N N N is finite and y ℓ ∈ Y ‾ y^{\ell} \in\overline{Y} y ℓ ∈ Y , after passing to a subsequence we can assume that i ℓ = i i_{\ell} = i i ℓ = i for all ℓ \ell ℓ and y ℓ → y ∈ Y ‾ y^{\ell} \to y \in\overline{Y} y ℓ → y ∈ Y . By Step 1, y ∈ E ( θ ) y \in\mathcal{E}(\theta) y ∈ E ( θ ) , and by continuity, S i ( y ; θ ) = 0 S_{i}(y;\theta) = 0 S i ( y ; θ ) = 0 . Hence θ ∉ Θ N D \theta\notin\Theta^{\mathrm{ND}} θ ∈ / Θ ND , so Θ ∖ Θ N D \Theta\setminus\Theta^{\mathrm{ND}} Θ ∖ Θ ND is closed and its complement Θ N D \Theta^{\mathrm{ND}} Θ ND is open. ■
Proof of Lemma 5
Proof. If y y y is a no-tie vector, then L A ( y ) = { 0 } L_{A(y)} = \{0\} L A ( y ) = { 0 } and the singleton groups G i = { i } G_i = \{i\} G i = { i } satisfy both parts of the equitable grouping property. We therefore suppose that y y y is a tie vector.
Let f ( C ) = χ ( C ) − y C f(C) = \chi(C) - y_C f ( C ) = χ ( C ) − y C for C ∈ W C \in\mathcal{W} C ∈ W . Then f f f is M ♮ M^{\natural} M ♮ -concave on W \mathcal{W} W . Moreover, because y y y is no-delay, we have C k ( y ) ⊆ W k \mathcal{C}_k(y) \subseteq\mathcal{W}^k C k ( y ) ⊆ W k for each k ∈ K ( y ) k \in K(y) k ∈ K ( y ) . For C , D ∈ W k C, D \in\mathcal{W}^k C , D ∈ W k , we have k ∈ C ∩ D k \in C \cap D k ∈ C ∩ D . Thus the transfers and replacements in Definition 2 preserve k k k ’s membership in both coalitions, so the restriction of f f f to W k \mathcal{W}^k W k remains M ♮ M^{\natural} M ♮ -concave.
By Murota [24 ] , each menu C k ( y ) \mathcal{C}_k(y) C k ( y ) is therefore M ♮ M^{\natural} M ♮ -convex: for any C , D ∈ C k ( y ) C, D \in\mathcal{C}_k(y) C , D ∈ C k ( y ) and i ∈ C ∖ D i \in C \setminus D i ∈ C ∖ D , either C − i , D + i ∈ C k ( y ) C - i, D + i \in\mathcal{C}_k(y) C − i , D + i ∈ C k ( y ) , or there is j ∈ D ∖ C j \in D \setminus C j ∈ D ∖ C such that C − i + j , D + i − j ∈ C k ( y ) C - i + j, D + i - j \in\mathcal{C}_k(y) C − i + j , D + i − j ∈ C k ( y ) .
Step 1: The group basis. We first show that the span defining L A ( y ) L_{A(y)} L A ( y ) in (11) is unchanged if we retain only single-player additions, removals, and replacements:
L A ( y ) = span { 1 C − 1 D ∣ C , D ∈ C k ( y ) , k ∈ K ( y ) , ∣ C ∖ D ∣ ≤ 1 , ∣ D ∖ C ∣ ≤ 1 } . (14) L_{A(y)} = \operatorname{span}\{\mathbf{1}_C - \mathbf{1}_D \mid C, D \in\mathcal{C}_k(y),\ k \in K(y),\ |C \setminus D| \le1,\ |D \setminus C| \le1\}. \tag*{(14)} L A ( y ) = span { 1 C − 1 D ∣ C , D ∈ C k ( y ) , k ∈ K ( y ) , ∣ C ∖ D ∣ ≤ 1 , ∣ D ∖ C ∣ ≤ 1 } . (14)
The right-hand side of (B.1) is contained in L A ( y ) L_{A(y)} L A ( y ) by definition. For the reverse inclusion, fix k ∈ K ( y ) k \in K(y) k ∈ K ( y ) . We will show by induction on m m m that 1 C − 1 D \mathbf{1}_C - \mathbf{1}_D 1 C − 1 D belongs to the right-hand side of (B.1) for every C , D ∈ C k ( y ) C, D \in\mathcal{C}_k(y) C , D ∈ C k ( y ) with ∣ C △ D ∣ ≤ m |C \mathbin{\triangle} D| \le m ∣ C △ D ∣ ≤ m , where △ \triangle △ denotes symmetric difference. The case m = 0 m = 0 m = 0 is immediate. Suppose m ≥ 1 m \ge1 m ≥ 1 and the claim holds for m − 1 m - 1 m − 1 , and take C , D ∈ C k ( y ) C, D \in\mathcal{C}_k(y) C , D ∈ C k ( y ) with ∣ C △ D ∣ = m |C \mathbin{\triangle} D| = m ∣ C △ D ∣ = m . Interchanging C C C and D D D if necessary, choose i ∈ C ∖ D i \in C \setminus D i ∈ C ∖ D . M ♮ M^{\natural} M ♮ -convexity of C k ( y ) \mathcal{C}_k(y) C k ( y ) implies that either E = C − i E = C - i E = C − i or E = C − i + j E = C - i + j E = C − i + j belongs to C k ( y ) \mathcal{C}_k(y) C k ( y ) , with j ∈ D ∖ C j \in D \setminus C j ∈ D ∖ C in the second case. Then we have ∣ E △ D ∣ ≤ m − 1 |E \mathbin{\triangle} D| \le m - 1 ∣ E △ D ∣ ≤ m − 1 and 1 C − 1 D = ( 1 C − 1 E ) + ( 1 E − 1 D ) \mathbf{1}_C - \mathbf{1}_D = (\mathbf{1}_C - \mathbf{1}_E) + (\mathbf{1}_E - \mathbf{1}_D) 1 C − 1 D = ( 1 C − 1 E ) + ( 1 E − 1 D ) . Both differences on the right belong to the right-hand side of (B.1), the first by construction and the second by induction, which proves the identity.
Next, note that the nonzero differences defining the span in (B.1) have the form ± e i \pm e_i ± e i or e i − e j e_i - e_j e i − e j , where e i e_i e i is the unit vector for player i i i . Discard every player i i i such that e i ∈ L A ( y ) e_i \in L_{A(y)} e i ∈ L A ( y ) . On the remaining players, define i ∼ j i \sim j i ∼ j if e i − e j ∈ L A ( y ) e_i - e_j \in L_{A(y)} e i − e j ∈ L A ( y ) . Since L A ( y ) L_{A(y)} L A ( y ) is a linear subspace, this is an equivalence relation. Let G 1 , … , G ℓ G_1, \ldots, G_\ell G 1 , … , G ℓ be its equivalence classes. By (B.1), a vector z z z belongs to L A ( y ) ⊥ L_{A(y)}^\perp L A ( y ) ⊥ if and only if it is zero on the discarded players and constant on each G t G_t G t . Hence L A ( y ) ⊥ = span { 1 G 1 , … , 1 G ℓ } L_{A(y)}^\perp= \operatorname{span}\{\mathbf{1}_{G_1}, \ldots, \mathbf{1}_{G_\ell}\} L A ( y ) ⊥ = span { 1 G 1 , … , 1 G ℓ } . These indicators are linearly independent because the groups are non-empty and disjoint. This proves part (i).
Step 2: Common recruitment counts. For each s s s , the count ∣ C ∩ G s ∣ |C \cap G_s| ∣ C ∩ G s ∣ is constant within every maximizing menu C i ( y ) \mathcal{C}_i(y) C i ( y ) because 1 G s ∈ L A ( y ) ⊥ \mathbf{1}_{G_s} \in L_{A(y)}^\perp 1 G s ∈ L A ( y ) ⊥ and therefore ( 1 C − 1 D ) ⊤ 1 G s = ∣ C ∩ G s ∣ − ∣ D ∩ G s ∣ = 0 (\mathbf{1}_C - \mathbf{1}_D)^\top\mathbf{1}_{G_s} = |C \cap G_s| - |D \cap G_s| = 0 ( 1 C − 1 D ) ⊤ 1 G s = ∣ C ∩ G s ∣ − ∣ D ∩ G s ∣ = 0 for all C , D ∈ C i ( y ) C, D \in\mathcal{C}_i(y) C , D ∈ C i ( y ) . It remains to show that these counts agree across proposers in the same group G t G_t G t for each t t t .
We first show that two players in G t G_t G t connected by a replacement have equal proposer surpluses. Suppose that C C C and C − i + j C - i + j C − i + j belong to some menu C k ( y ) \mathcal{C}_k(y) C k ( y ) , with i ∈ C i \in C i ∈ C and $j \notin C. Necessarily k ∉ { i , j } k \notin\{i,j\} k ∈ / { i , j } . Take any D ∈ C i ( y ) D \in C_i(y) D ∈ C i ( y ) . If j ∈ D j \in D j ∈ D , then S j ( y ) ≥ S i ( y ) S_j(y) \ge S_i(y) S j ( y ) ≥ S i ( y ) . Otherwise, apply the exchange inequalities to coalitions C − i + j C-i+j C − i + j and D D D and player j j j . If (12) applies, let E = D + j E=D+j E = D + j and F = C − i F=C-i F = C − i . Otherwise, (13) gives some j ′ ∈ D ∖ ( C − i + j ) j' \in D \setminus(C-i+j) j ′ ∈ D ∖ ( C − i + j ) , and we let E = D − j ′ + j E=D-j'+j E = D − j ′ + j and F = C − i + j ′ F=C-i+j' F = C − i + j ′ . In either case, F F F contains k k k , so f ( F ) ≤ S k ( y ) f(F) \le S_k(y) f ( F ) ≤ S k ( y ) . The exchange inequality therefore gives f ( E ) ≥ f ( D ) = S i ( y ) f(E) \ge f(D)=S_i(y) f ( E ) ≥ f ( D ) = S i ( y ) , implying S j ( y ) ≥ S i ( y ) S_j(y) \ge S_i(y) S j ( y ) ≥ S i ( y ) . Reversing the roles of i i i and j j j gives S i ( y ) = S j ( y ) S_i(y)=S_j(y) S i ( y ) = S j ( y ) .
For the same players i i i and j j j , we next show that recruitment counts agree between C i ( y ) C_i(y) C i ( y ) and C j ( y ) C_j(y) C j ( y ) . Take any D ∈ C i ( y ) D \in C_i(y) D ∈ C i ( y ) . If j ∈ D j \in D j ∈ D , then D D D also belongs to C j ( y ) C_j(y) C j ( y ) because S i ( y ) = S j ( y ) S_i(y)=S_j(y) S i ( y ) = S j ( y ) , so the counts agree because they are constant within each menu. Suppose instead that j ∉ D j \notin D j ∈ / D , and construct E E E and F F F as above. The exchange inequality gives f ( E ) + f ( F ) ≥ f ( D ) + f ( C − i + j ) = S i ( y ) + S k ( y ) f(E)+f(F) \ge f(D)+f(C-i+j)=S_i(y)+S_k(y) f ( E ) + f ( F ) ≥ f ( D ) + f ( C − i + j ) = S i ( y ) + S k ( y ) . Since f ( E ) ≤ S j ( y ) = S i ( y ) f(E) \le S_j(y)=S_i(y) f ( E ) ≤ S j ( y ) = S i ( y ) and f ( F ) ≤ S k ( y ) f(F) \le S_k(y) f ( F ) ≤ S k ( y ) , both bounds hold with equality. Thus E ∈ C j ( y ) E \in C_j(y) E ∈ C j ( y ) and F ∈ C k ( y ) F \in C_k(y) F ∈ C k ( y ) . By construction, 1 E − 1 D = 1 C − i + j − 1 F ∈ L A ( y ) \mathbf{1}_E-\mathbf{1}_D=\mathbf{1}_{C-i+j}-\mathbf{1}_F \in L_{A(y)} 1 E − 1 D = 1 C − i + j − 1 F ∈ L A ( y ) , so ∣ E ∩ G s ∣ = ∣ D ∩ G s ∣ |E \cap G_s|=|D \cap G_s| ∣ E ∩ G s ∣ = ∣ D ∩ G s ∣ for every s s s . Since recruitment counts are constant within each maximizing menu, equality for this pair D , E D,E D , E establishes that the counts agree between C i ( y ) C_i(y) C i ( y ) and C j ( y ) C_j(y) C j ( y ) .
Identity (B.1) implies any two distinct players in G t G_t G t are connected by a chain of replacements, each involving two coalitions in the same maximizing menu. To see this, suppose otherwise and choose a non-empty proper subset H ⊂ G t H \subset G_t H ⊂ G t with no replacement connecting H H H to G t ∖ H G_t \setminus H G t ∖ H . Since 1 G t ∈ L A ( y ) ⊥ \mathbf{1}_{G_t} \in L_{A(y)}^\perp 1 G t ∈ L A ( y ) ⊥ , no addition or removal within a maximizing menu involves a player in G t G_t G t , and no replacement connects G t G_t G t to its complement. Thus 1 H \mathbf{1}_H 1 H is orthogonal to every generator in (B.1), so 1 H ∈ L A ( y ) \mathbf{1}_H \in L_{A(y)} 1 H ∈ L A ( y ) . This contradicts Step 1, because 1 H \mathbf{1}_H 1 H is not constant on G t G_t G t . The equality of recruitment counts therefore extends to all proposers in G t G_t G t . Thus, for every t , s t,s t , s , the count ∣ C ∩ G s ∣ |C \cap G_s| ∣ C ∩ G s ∣ is the same for all i ∈ G t i \in G_t i ∈ G t and C ∈ C i ( y ) C \in C_i(y) C ∈ C i ( y ) , proving part (ii). ■
Proof of Lemma 6
Fix θ ∈ Θ \theta\in\Theta θ ∈ Θ and suppose that χ \chi χ is M ♮ M^\natural M ♮ -concave on W \mathcal{W} W . Further, fix y 0 ∈ E ( θ ) y_0 \in\mathcal{E}(\theta) y 0 ∈ E ( θ ) and suppose that y 0 y_0 y 0 is a no-delay vector of expected payoffs. If y 0 y_0 y 0 is no-tie, the conclusion follows from Lemma 3. Henceforth in this subsection, assume that K ( y 0 ) ≠ ∅ K(y_0) \ne\varnothing K ( y 0 ) = ∅ .26
By Proposition 1, we have y 0 ∈ T ( y 0 ) y_0 \in T(y_0) y 0 ∈ T ( y 0 ) . Hence (10) implies that there exists r 0 ∈ R ( y 0 ) r_0 \in R(y_0) r 0 ∈ R ( y 0 ) such that
y 0 , i = δ i p i S i ( y 0 ) + δ i ( p C i ( y 0 ) + r i 0 ) y 0 , i , i ∈ N . (15) y_{0,i}=\delta_i p_i S_i(y_0)+\delta_i\left(p_{C_i(y_0)}+r_i^0\right)y_{0,i}, \qquad i \in N. \tag*{(15)} y 0 , i = δ i p i S i ( y 0 ) + δ i ( p C i ( y 0 ) + r i 0 ) y 0 , i , i ∈ N . (15)
Since p C i ( y 0 ) + r 0 i ≤ 1 p_{\mathcal{C}_i}(y_0) + r_0^i \le1 p C i ( y 0 ) + r 0 i ≤ 1 , S i ( y 0 ) > 0 S_i(y_0) > 0 S i ( y 0 ) > 0 implies y 0 , i > 0 y_{0,i} > 0 y 0 , i > 0 . Solving (B.2) then gives
r 0 i = 1 δ i − p C i ( y 0 ) − p i S i ( y 0 ) y 0 , i , i ∈ N , (16) r_0^i = \frac{1}{\delta_i} - p_{\mathcal{C}_i}(y_0) - \frac{p_i S_i(y_0)}{y_{0,i}}, \qquad i \in N, \tag*{(16)} r 0 i = δ i 1 − p C i ( y 0 ) − y 0 , i p i S i ( y 0 ) , i ∈ N , (16)
which determines r 0 r_0 r 0 uniquely. We call r 0 r_0 r 0 the aggregate inclusion vector supporting y 0 y_0 y 0 . Moreover, S i ( y 0 ) > 0 S_i(y_0) > 0 S i ( y 0 ) > 0 implies that every C ∈ C i ( y 0 ) C \in\mathcal{C}_i(y_0) C ∈ C i ( y 0 ) is non-empty, so y 0 , i ≤ y 0 , C < χ ( C ) ≤ max D ∈ W i χ ( D ) y_{0,i} \le y_{0,C} < \chi(C) \le\max_{D \in\mathcal{W}_i} \chi(D) y 0 , i ≤ y 0 , C < χ ( C ) ≤ max D ∈ W i χ ( D ) for every i ∈ N i \in N i ∈ N . It follows that y 0 ∈ int Y y_0 \in\operatorname{int} Y y 0 ∈ int Y .
Coalitions that are strictly suboptimal at y 0 y_0 y 0 remain so near y 0 y_0 y 0 . We can therefore choose a neighborhood V V V of y 0 y_0 y 0 contained in int Y \operatorname{int} Y int Y such that S i ( y ) > 0 S_i(y) > 0 S i ( y ) > 0 and C i ( y ) ⊆ C i ( y 0 ) \mathcal{C}_i(y) \subseteq\mathcal{C}_i(y_0) C i ( y ) ⊆ C i ( y 0 ) for every i ∈ N i \in N i ∈ N and y ∈ V y \in V y ∈ V . Thus each proposer outside K ( y 0 ) K(y_0) K ( y 0 ) retains her unique maximizing coalition, while the ties of proposers in K ( y 0 ) K(y_0) K ( y 0 ) may break. Write K 0 = K ( y 0 ) K_0 = K(y_0) K 0 = K ( y 0 ) and keep this partition of proposers fixed for the remainder of this section.
Since all coalitions in C i ( y 0 ) \mathcal{C}_i(y_0) C i ( y 0 ) are tied at y 0 y_0 y 0 , for y ∈ V y \in V y ∈ V we have
χ ( C ) − y C = S i ( y 0 ) − ( y − y 0 ) C , C ∈ C i ( y 0 ) . \chi(C) - y_C = S_i(y_0) - (y-y_0)_C, \qquad C \in\mathcal{C}_i(y_0). χ ( C ) − y C = S i ( y 0 ) − ( y − y 0 ) C , C ∈ C i ( y 0 ) .
Therefore, within C i ( y 0 ) \mathcal{C}_i(y_0) C i ( y 0 ) , maximizing χ ( C ) − y C \chi(C) - y_C χ ( C ) − y C is equivalent to minimizing ( y − y 0 ) C = ( y − y 0 ) ⊤ 1 C (y-y_0)_C = (y-y_0)^\top\mathbf{1}_C ( y − y 0 ) C = ( y − y 0 ) ⊤ 1 C , and C i ( y ) \mathcal{C}_i(y) C i ( y ) consists exactly of the coalitions attaining this minimum. Define
F(y) = \left\{ r \in[0,1]^n \mathrel{\left|} r = \sum_{k \in K_0} p_k \sum_{C \in\mathcal{C}_k(y)} \rho_k(C)\mathbf{1}_C,\ \rho_k \in\Delta(\mathcal{C}_k(y)),\ k \in K_0 \right. \right\} \subseteq R(y_0), \tag*{(17)}
and note that for any r ∈ F ( y ) r \in F(y) r ∈ F ( y ) , player i i i ’s total inclusion probability is p C i ( y 0 ) + r i p_{\mathcal{C}_i}(y_0) + r^i p C i ( y 0 ) + r i .27
The convex-hull representation in (9) expresses R ( y 0 ) R(y_0) R ( y 0 ) as a weighted sum of convex hulls of coalition incidence vectors. In this representation, restricting each menu C k ( y 0 ) \mathcal{C}_k(y_0) C k ( y 0 ) to C k ( y ) \mathcal{C}_k(y) C k ( y ) gives the set F ( y ) F(y) F ( y ) . We will show that this restriction selects exactly the minimizing aggregates:
F ( y ) = arg min r ∈ R ( y 0 ) ( y − y 0 ) ⊤ r , y ∈ V . (18) F(y) = \underset{r \in R(y_0)}{\arg\min}\,(y-y_0)^\top r, \qquad y \in V. \tag*{(18)} F ( y ) = r ∈ R ( y 0 ) arg min ( y − y 0 ) ⊤ r , y ∈ V . (18)
First, take r ∈ F ( y ) r \in F(y) r ∈ F ( y ) and proposal distributions ρ k ∈ Δ ( C k ( y ) ) \rho_k \in\Delta(\mathcal{C}_k(y)) ρ k ∈ Δ ( C k ( y )) generating it. If r r r did not minimize ( y − y 0 ) ⊤ r (y-y_0)^\top r ( y − y 0 ) ⊤ r over R ( y 0 ) R(y_0) R ( y 0 ) , then for some k ∈ K 0 k \in K_0 k ∈ K 0 , a coalition C C C with ρ k ( C ) > 0 \rho_k(C) > 0 ρ k ( C ) > 0 would fail to minimize ( y − y 0 ) ⊤ 1 C (y-y_0)^\top\mathbf{1}_C ( y − y 0 ) ⊤ 1 C over C k ( y 0 ) \mathcal{C}_k(y_0) C k ( y 0 ) . This contradicts C ∈ C k ( y ) C \in\mathcal{C}_k(y) C ∈ C k ( y ) . Conversely, any aggregate minimizing ( y − y 0 ) ⊤ r (y-y_0)^\top r ( y − y 0 ) ⊤ r over R ( y 0 ) R(y_0) R ( y 0 ) can be generated by proposal distributions over the original menus C k ( y 0 ) \mathcal{C}_k(y_0) C k ( y 0 ) . None of these distributions can assign positive probability to a nonminimizing coalition because p k > 0 p_k > 0 p k > 0 implies that shifting this probability to a minimizing coalition would strictly lower the objective. Thus these distributions are supported on C k ( y ) \mathcal{C}_k(y) C k ( y ) .
In particular, F ( y ) F(y) F ( y ) is a non-empty face of R ( y 0 ) R(y_0) R ( y 0 ) for every y ∈ V y \in V y ∈ V .
Consider the homotopy y ↦ T λ ( y ) y \mapsto\mathcal{T}_{\lambda}(y) y ↦ T λ ( y ) , y ∈ V y \in V y ∈ V , λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , defined by
T λ ( y ) = { z ∈ R n | z i = δ i p i [ ( 1 − λ ) S i ( y 0 ) + λ S i ( y ) ] + δ i [ p C i ( y 0 ) + r i ] y i , r ∈ F ( y ) } . (19) \mathcal{T}_{\lambda}(y)=\left\{z \in\mathbb{R}^{n}\ \middle|\ z_i=\delta_i p_i\left[(1-\lambda)S_i(y_0)+\lambda S_i(y)\right]+\delta_i\left[pC_i(y_0)+r^i\right]y_i,\quad r \in F(y)\right\}. \tag*{(19)} T λ ( y ) = { z ∈ R n z i = δ i p i [ ( 1 − λ ) S i ( y 0 ) + λ S i ( y ) ] + δ i [ p C i ( y 0 ) + r i ] y i , r ∈ F ( y ) } . (19)
By the definition of F ( y ) F(y) F ( y ) , we have T 1 ( y ) = T ( y ) \mathcal{T}_1(y)=\mathcal{T}(y) T 1 ( y ) = T ( y ) on V V V , while T 0 ( y ) \mathcal{T}_0(y) T 0 ( y ) holds proposer surpluses at their values at y 0 y_0 y 0 but uses the maximizing menus at y y y . At y = y 0 y=y_0 y = y 0 , the objective in (B.5) is zero for every r ∈ R ( y 0 ) r \in R(y_0) r ∈ R ( y 0 ) , so F ( y 0 ) = R ( y 0 ) F(y_0)=R(y_0) F ( y 0 ) = R ( y 0 ) and T λ ( y 0 ) = T ( y 0 ) \mathcal{T}_{\lambda}(y_0)=\mathcal{T}(y_0) T λ ( y 0 ) = T ( y 0 ) for every λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] . Because y 0 ∈ T ( y 0 ) y_0 \in\mathcal{T}(y_0) y 0 ∈ T ( y 0 ) by Proposition 1, y 0 y_0 y 0 is a fixed point throughout the homotopy. The next result shows that the fixed point index of T \mathcal{T} T can be computed from T 0 \mathcal{T}_0 T 0 .
Lemma B.1. For every sufficiently small open neighborhood U U U of y 0 y_0 y 0 in R n \mathbb{R}^n R n , each T λ ∣ U ‾ \mathcal{T}_{\lambda}|_{\overline{U}} T λ ∣ U , λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , takes values in Y Y Y and has y 0 y_0 y 0 as its only fixed point. Moreover, we have
Λ Y ( T ∣ U ‾ ) = Λ Y ( T 0 ∣ U ‾ ) . (20) \Lambda_Y(\mathcal{T}|_{\overline{U}})=\Lambda_Y(\mathcal{T}_0|_{\overline{U}}). \tag*{(20)} Λ Y ( T ∣ U ) = Λ Y ( T 0 ∣ U ) . (20)
Proof. Step 1: Upper hemicontinuity and a common neighborhood. The same argument as in the proof of Proposition 1 shows that ( λ , y ) ↦ T λ ( y ) (\lambda,y)\mapsto\mathcal{T}_{\lambda}(y) ( λ , y ) ↦ T λ ( y ) is jointly upper hemicontinuous with non-empty compact convex values.
Now, we can shrink V V V so that T λ ( y ) ⊂ int Y \mathcal{T}_{\lambda}(y) \subset\operatorname{int}Y T λ ( y ) ⊂ int Y for every λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] and y ∈ V y \in V y ∈ V . To see this, write χ i = max D ∈ W i χ ( D ) \chi_i=\max_{D\in\mathcal{W}^i}\chi(D) χ i = max D ∈ W i χ ( D ) and note that p C i ( y 0 ) + r i ≤ 1 pC_i(y_0)+r^i \le1 p C i ( y 0 ) + r i ≤ 1 and S i ( y 0 ) ≤ χ i − y 0 , i S_i(y_0)\le\chi_i-y_{0,i} S i ( y 0 ) ≤ χ i − y 0 , i . Therefore, for z ∈ T ( y 0 ) z \in\mathcal{T}(y_0) z ∈ T ( y 0 ) generated by r ∈ R ( y 0 ) r \in R(y_0) r ∈ R ( y 0 ) , we have
0 < δ i p i S i ( y 0 ) ≤ z i ≤ δ i [ p i χ i + ( 1 − p i ) y 0 , i ] ≤ δ i χ i < χ i . 0<\delta_i p_iS_i(y_0)\le z_i\le\delta_i\left[p_i\chi_i+(1-p_i)y_{0,i}\right]\le\delta_i\chi_i<\chi_i. 0 < δ i p i S i ( y 0 ) ≤ z i ≤ δ i [ p i χ i + ( 1 − p i ) y 0 , i ] ≤ δ i χ i < χ i .
Hence the compact set T ( y 0 ) \mathcal{T}(y_0) T ( y 0 ) is contained in int Y \operatorname{int}Y int Y . Since T λ ( y 0 ) = T ( y 0 ) \mathcal{T}_{\lambda}(y_0)=\mathcal{T}(y_0) T λ ( y 0 ) = T ( y 0 ) for every λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , joint upper hemicontinuity and compactness of [ 0 , 1 ] [0,1] [ 0 , 1 ] give the claimed neighborhood V V V .
Step 2: Restrictions at nearby fixed points. Fix λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] and y ∈ V y \in V y ∈ V with y ∈ T λ ( y ) y \in\mathcal{T}_{\lambda}(y) y ∈ T λ ( y ) . Let r ∈ F ( y ) r \in F(y) r ∈ F ( y ) generate y y y in (B.6). Since y i > 0 y_i>0 y i > 0 , we have
r i = 1 δ i − p C i ( y 0 ) − p i [ ( 1 − λ ) S i ( y 0 ) + λ S i ( y ) ] y i , i ∈ N . (21) r^i=\frac{1}{\delta_i}-pC_i(y_0)-\frac{p_i\left[(1-\lambda)S_i(y_0)+\lambda S_i(y)\right]}{y_i},\qquad i \in N. \tag*{(21)} r i = δ i 1 − p C i ( y 0 ) − y i p i [ ( 1 − λ ) S i ( y 0 ) + λ S i ( y ) ] , i ∈ N . (21)
which determines r r r uniquely. Subtracting (B.3) from (B.8) gives
r i − r 0 i = p i S i ( y 0 ) y 0 , i y i ( y i − y 0 , i ) + λ p i y i [ S i ( y 0 ) − S i ( y ) ] , i ∈ N . (22) r^i-r_0^i=\frac{p_iS_i(y_0)}{y_{0,i}y_i}(y_i-y_{0,i})+\lambda\frac{p_i}{y_i}\left[S_i(y_0)-S_i(y)\right],\qquad i \in N. \tag*{(22)} r i − r 0 i = y 0 , i y i p i S i ( y 0 ) ( y i − y 0 , i ) + λ y i p i [ S i ( y 0 ) − S i ( y ) ] , i ∈ N . (22)
Let λ ℓ ∈ [ 0 , 1 ] \lambda^\ell\in[0,1] λ ℓ ∈ [ 0 , 1 ] and y ℓ ∈ V y^\ell\in V y ℓ ∈ V satisfy y ℓ ∈ T λ ℓ ( y ℓ ) y^\ell\in\mathcal{T}_{\lambda^\ell}(y^\ell) y ℓ ∈ T λ ℓ ( y ℓ ) and y ℓ → y 0 y^\ell\to y_0 y ℓ → y 0 . Then (B.9) implies that the corresponding vectors r ℓ ∈ F ( y ℓ ) r^\ell\in F(y^\ell) r ℓ ∈ F ( y ℓ ) converge to r 0 r_0 r 0 . We can further shrink V V V so that r 0 ∈ F ( y ) r_0 \in F(y) r 0 ∈ F ( y ) at every fixed point of every T λ \mathcal{T}_{\lambda} T λ in V V V . Otherwise, there would be sequences λ ℓ ∈ [ 0 , 1 ] \lambda^\ell\in[0,1] λ ℓ ∈ [ 0 , 1 ] and y ℓ ∈ T λ ℓ ( y ℓ ) y^\ell\in\mathcal{T}_{\lambda^\ell}(y^\ell) y ℓ ∈ T λ ℓ ( y ℓ ) with y ℓ → y 0 y^\ell\to y_0 y ℓ → y 0 and r 0 ∉ F ( y ℓ ) r_0 \notin F(y^\ell) r 0 ∈ / F ( y ℓ ) . By (B.5), each F ( y ℓ ) F(y^\ell) F ( y ℓ ) is a face of R ( y 0 ) R(y_0) R ( y 0 ) . Since there are finitely many such faces, we can pass to a subsequence on which F ( y ℓ ) F(y^\ell) F ( y ℓ ) is constant. But r ℓ ∈ F ( y ℓ ) r^\ell\in F(y^\ell) r ℓ ∈ F ( y ℓ ) and r ℓ → r 0 r^\ell\to r_0 r ℓ → r 0 , so closedness of this face gives r 0 ∈ F ( y ℓ ) r_0 \in F(y^\ell) r 0 ∈ F ( y ℓ ) , a contradiction.
Since r , r 0 ∈ F ( y ) r,r_0 \in F(y) r , r 0 ∈ F ( y ) , choose proposal distributions over C k ( y ) \mathcal{C}_k(y) C k ( y ) , k ∈ K 0 k \in K_0 k ∈ K 0 , generating r r r and r 0 r_0 r 0 , respectively, as in (B.4). For k ∈ K 0 ∖ K ( y ) k \in K_0 \setminus K(y) k ∈ K 0 ∖ K ( y ) , both distributions assign probability one to C k ( y ) \mathcal{C}_k(y) C k ( y ) , so proposer k k k contributes p k 1 C k ( y ) p_k\mathbf{1}_{\mathcal{C}_k(y)} p k 1 C k ( y ) to both vectors. These contributions cancel in r − r 0 r-r_0 r − r 0 . For each k ∈ K ( y ) k \in K(y) k ∈ K ( y ) , the difference of her two mixtures is a linear combination of the vectors 1 C \mathbf{1}_C 1 C , C ∈ C k ( y ) C \in\mathcal{C}_k(y) C ∈ C k ( y ) , whose coefficients sum to zero. Therefore, subtracting 1 D \mathbf{1}_D 1 D , for any D ∈ C k ( y ) D \in\mathcal{C}_k(y) D ∈ C k ( y ) , from each 1 C \mathbf{1}_C 1 C leaves this combination unchanged. Each remaining contribution is thus a linear combination of differences 1 C − 1 D \mathbf{1}_C-\mathbf{1}_D 1 C − 1 D with C , D ∈ C k ( y ) C,D \in\mathcal{C}_k(y) C , D ∈ C k ( y ) . By (11) , r − r 0 ∈ L A ( y ) r-r_0 \in L_{A(y)} r − r 0 ∈ L A ( y ) .
Moreover, every tie in A ( y ) \mathcal{A}(y) A ( y ) holds at both y y y and y 0 y_0 y 0 , so ( y − y 0 ) C = ( y − y 0 ) D (y-y_0)_C=(y-y_0)_D ( y − y 0 ) C = ( y − y 0 ) D whenever C , D ∈ C k ( y ) C,D \in\mathcal{C}_k(y) C , D ∈ C k ( y ) . By (11) , y − y 0 ∈ L A ( y ) ⊥ y-y_0 \in L_{A(y)}^\perp y − y 0 ∈ L A ( y ) ⊥ . Thus, for every y ∈ V y \in V y ∈ V and λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] with y ∈ T λ ( y ) y \in\mathcal{T}_{\lambda}(y) y ∈ T λ ( y ) , we have
r − r 0 ∈ L A ( y ) , y − y 0 ∈ L A ( y ) ⊥ . (23) r-r_0 \in L_{A(y)}, \qquad y-y_0 \in L_{A(y)}^\perp. \tag*{(23)} r − r 0 ∈ L A ( y ) , y − y 0 ∈ L A ( y ) ⊥ . (23)
Step 3: Group equations. We want to show that y 0 y_0 y 0 is the only fixed point of every T λ \mathcal{T}_{\lambda} T λ in V V V chosen above. Fix λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] and a fixed point y ∈ V y \in V y ∈ V , and let r ∈ F ( y ) r \in F(y) r ∈ F ( y ) generate y y y as in Step 2. Since χ \chi χ is M ♮ M^\natural M ♮ -concave and every proposer surplus at y y y is positive, Lemma 5 gives an equitable grouping G 1 , … , G ℓ G_1,\ldots,G_\ell G 1 , … , G ℓ at y y y . Let X = [ 1 G 1 ⋯ 1 G ℓ ] ∈ R n × ℓ X=[\mathbf{1}_{G_1}\ \cdots\ \mathbf{1}_{G_\ell}] \in\mathbb{R}^{n\times\ell} X = [ 1 G 1 ⋯ 1 G ℓ ] ∈ R n × ℓ . By part (i), the columns of X X X form a basis of L A ( y ) ⊥ L_{A(y)}^\perp L A ( y ) ⊥ . Thus (B.10) gives X T ( r − r 0 ) = 0 X^{\mathsf{T}}(r-r_0)=0 X T ( r − r 0 ) = 0 and y − y 0 = X ξ y-y_0=X\xi y − y 0 = X ξ for some ξ ∈ R ℓ \xi\in\mathbb{R}^{\ell} ξ ∈ R ℓ .
If ℓ = 0 \ell=0 ℓ = 0 , then y = y 0 y=y_0 y = y 0 and we are done. Suppose that ℓ > 0 \ell>0 ℓ > 0 . Because the groups are disjoint, y j − y 0 , j = ξ s y_j-y_{0,j}=\xi_s y j − y 0 , j = ξ s for j ∈ G s j \in G_s j ∈ G s , and y j = y 0 , j y_j=y_{0,j} y j = y 0 , j outside these groups. For i ∈ G t i \in G_t i ∈ G t , choose D i ∈ C i ( y ) D_i \in\mathcal{C}_i(y) D i ∈ C i ( y ) and write c t s = ∣ D i ∩ G s ∣ c_{ts}=|D_i\cap G_s| c t s = ∣ D i ∩ G s ∣ . By part (ii), this count is independent of both the proposer i ∈ G t i \in G_t i ∈ G t and the choice of D i D_i D i and therefore well-defined. Define the count matrix
C = ( c t s ) t , s = 1 ℓ . C=(c_{ts})_{t,s=1}^{\ell}. C = ( c t s ) t , s = 1 ℓ .
Since D i ∈ C i ( y ) ⊆ C i ( y 0 ) D_i \in\mathcal{C}_i(y) \subseteq\mathcal{C}_i(y_0) D i ∈ C i ( y ) ⊆ C i ( y 0 ) , we have S i ( y 0 ) = χ ( D i ) − y 0 , D i S_i(y_0)=\chi(D_i)-y_{0,D_i} S i ( y 0 ) = χ ( D i ) − y 0 , D i and S i ( y ) = χ ( D i ) − y D i S_i(y)=\chi(D_i)-y_{D_i} S i ( y ) = χ ( D i ) − y D i . Using the group coordinates and constant counts, for i ∈ G t i \in G_t i ∈ G t we get
S i ( y 0 ) − S i ( y ) = ( y − y 0 ) D i = ∑ s = 1 ℓ ∣ D i ∩ G s ∣ ξ s = ∑ s = 1 ℓ c t s ξ s = ( C ξ ) t . S_i(y_0)-S_i(y)=(y-y_0)_{D_i}=\sum_{s=1}^{\ell}|D_i\cap G_s|\xi_s=\sum_{s=1}^{\ell}c_{ts}\xi_s=(C\xi)_t. S i ( y 0 ) − S i ( y ) = ( y − y 0 ) D i = s = 1 ∑ ℓ ∣ D i ∩ G s ∣ ξ s = s = 1 ∑ ℓ c t s ξ s = ( C ξ ) t .
In turn, since X T ( r − r 0 ) = 0 X^{\mathsf{T}}(r-r_0)=0 X T ( r − r 0 ) = 0 , we have 1 G t T ( r − r 0 ) = ∑ i ∈ G t ( r i i − r 0 i ) = 0 \mathbf{1}_{G_t}^{\mathsf{T}}(r-r_0)=\sum_{i\in G_t}(r_i^i-r_{0}^{i})=0 1 G t T ( r − r 0 ) = ∑ i ∈ G t ( r i i − r 0 i ) = 0 . Therefore, summing (B.9) over i ∈ G t i \in G_t i ∈ G t , we get
0 = ∑ i ∈ G t ( r i i − r 0 i ) = A t ξ t + λ B t ( C ξ ) t , (24) 0=\sum_{i\in G_t}(r_i^i-r_{0}^{i})=A_t\xi_t+\lambda B_t(C\xi)_t, \tag*{(24)} 0 = i ∈ G t ∑ ( r i i − r 0 i ) = A t ξ t + λ B t ( C ξ ) t , (24)
where
A t = ∑ i ∈ G t p i S i ( y 0 ) y 0 , i y i > 0 , B t = ∑ i ∈ G t p i y i > 0. A_t = \sum_{i\in G_t} \frac{p_i S_i(y_0)}{y_{0,i}y_i} > 0,\qquad B_t = \sum_{i\in G_t} \frac{p_i}{y_i} > 0. A t = i ∈ G t ∑ y 0 , i y i p i S i ( y 0 ) > 0 , B t = i ∈ G t ∑ y i p i > 0.
Because these expressions hold for all t = 1 , … , ℓ t=1,\ldots,\ell t = 1 , … , ℓ , we can write them in matrix form
M ξ = 0 , M = diag ( A t ) t = 1 ℓ + λ diag ( B t ) t = 1 ℓ C . (25) M\xi=0,\qquad M=\operatorname{diag}(A_t)_{t=1}^{\ell}+\lambda\operatorname{diag}(B_t)_{t=1}^{\ell}C. \tag*{(25)} M ξ = 0 , M = diag ( A t ) t = 1 ℓ + λ diag ( B t ) t = 1 ℓ C . (25)
Step 4: Isolation. We will now show that M M M is nonsingular by adapting the ordering and determinant argument from Steps 1–3 of the proof of Lemma 3 to the groups G 1 , … , G ℓ G_1,\ldots,G_\ell G 1 , … , G ℓ . For each group t t t , let S ‾ t = max i ∈ G t S i ( y ) \overline{S}_t=\max_{i\in G_t}S_i(y) S t = max i ∈ G t S i ( y ) . We will show that c t s > 0 c_{ts}>0 c t s > 0 implies S ‾ s ≥ S ‾ t \overline{S}_s\geq\overline{S}_t S s ≥ S t , with equality only when the rows t t t and s s s of the count matrix C C C coincide. If c t s > 0 c_{ts}>0 c t s > 0 , choose i ∈ G t i\in G_t i ∈ G t attaining S ‾ t \overline{S}_t S t and a player j ∈ D i ∩ G s j\in D_i\cap G_s j ∈ D i ∩ G s . The coalition D i D_i D i is also feasible for proposer j j j , so proposer independence gives
S ‾ s ≥ S j ( y ) ≥ χ ( D i ) − y D i = S i ( y ) = S ‾ t . \overline{S}_s\geq S_j(y)\geq\chi(D_i)-y_{D_i}=S_i(y)=\overline{S}_t. S s ≥ S j ( y ) ≥ χ ( D i ) − y D i = S i ( y ) = S t .
If S ‾ s = S ‾ t \overline{S}_s=\overline{S}_t S s = S t , all inequalities are equalities, and D i D_i D i also belongs to C j ( y ) C_j(y) C j ( y ) . Part (ii) then gives c t v = ∣ D i ∩ G v ∣ = c s v c_{tv}=|D_i\cap G_v|=c_{sv} c t v = ∣ D i ∩ G v ∣ = c s v for every v = 1 , … , ℓ v=1,\ldots,\ell v = 1 , … , ℓ .
Partition the group indices into classes having the same value of S ‾ t \overline{S}_t S t and the same row of C C C . Order these classes by increasing S ‾ t \overline{S}_t S t , with arbitrary order between distinct classes having the same value. If the class of s s s precedes that of t t t , then S ‾ s ≤ S ‾ t \overline{S}_s\leq\overline{S}_t S s ≤ S t . If c t s > 0 c_{ts}>0 c t s > 0 , the preceding argument gives equality and identical count rows, contradicting that these classes are distinct. Hence c t s = 0 c_{ts}=0 c t s = 0 . Thus C C C is block upper triangular, with identical rows within each diagonal block. The same ordering makes M M M block upper triangular.
For each diagonal block Q Q Q and s ∈ Q s\in Q s ∈ Q , let c Q s c_{Qs} c Q s denote the common value of c t s c_{ts} c t s over t ∈ Q t\in Q t ∈ Q , and collect these counts in the column vector c Q = ( c Q s ) s ∈ Q c_Q=(c_{Qs})_{s\in Q} c Q = ( c Q s ) s ∈ Q . Then C Q = 1 ∣ Q ∣ c Q T C_Q=\mathbf{1}_{|Q|}c_Q^{\mathsf{T}} C Q = 1 ∣ Q ∣ c Q T and M Q = diag ( A t ) t ∈ Q + λ ( B t ) t ∈ Q c Q T M_Q=\operatorname{diag}(A_t)_{t\in Q}+\lambda(B_t)_{t\in Q}c_Q^{\mathsf{T}} M Q = diag ( A t ) t ∈ Q + λ ( B t ) t ∈ Q c Q T . The matrix determinant lemma gives det M Q = ( ∏ t ∈ Q A t ) ( 1 + λ ∑ t ∈ Q c Q t B t A t ) > 0 \det M_Q=\left(\prod_{t\in Q}A_t\right)\left(1+\lambda\sum_{t\in Q}c_{Qt}\frac{B_t}{A_t}\right)>0 det M Q = ( ∏ t ∈ Q A t ) ( 1 + λ ∑ t ∈ Q c Qt A t B t ) > 0 . Thus det M > 0 \det M>0 det M > 0 , so (B.11) implies ξ = 0 \xi=0 ξ = 0 and hence y = y 0 y=y_0 y = y 0 . Since y 0 ∈ T λ ( y 0 ) y_0\in\mathcal{T}_\lambda(y_0) y 0 ∈ T λ ( y 0 ) for every λ \lambda λ , every T λ \mathcal{T}_\lambda T λ has exactly this fixed point in V V V .
Step 5: Equality of indices. Let U U U be any bounded open neighborhood of y 0 y_0 y 0 with U ‾ ⊂ V \overline{U}\subset V U ⊂ V . By Steps 1 and 4, every T λ ∣ U ‾ \mathcal{T}_\lambda|_{\overline{U}} T λ ∣ U takes values in Y Y Y and has y 0 y_0 y 0 as its only fixed point. Thus no correspondence in this homotopy has a fixed point on ∂ U \partial U ∂ U . Continuity gives (B.7). ■
We are now ready to prove Lemma 6 using an argument similar to Step 4 of the proof of Lemma 3.
Proof of Lemma 6. By Lemma B.1, y 0 y_0 y 0 is isolated and, for every sufficiently small open neighborhood U U U of y 0 y_0 y 0 , it remains to show that Λ Y ( T 0 ∣ U ‾ ) = + 1 \Lambda_Y(T_0|_{\overline{U}})=+1 Λ Y ( T 0 ∣ U ) = + 1 . Consider the homotopy
y ↦ ( 1 − s ) T 0 ( y ) + s y 0 , y ∈ U ‾ , s ∈ [ 0 , 1 ] . y \mapsto(1-s)T_0(y)+sy_0,\qquad y\in\overline{U},\qquad s\in[0,1]. y ↦ ( 1 − s ) T 0 ( y ) + s y 0 , y ∈ U , s ∈ [ 0 , 1 ] .
This homotopy is jointly upper hemicontinuous with non-empty compact convex values in Y Y Y . Fix s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] and a fixed point y ∈ U ‾ y\in\overline{U} y ∈ U of this homotopy. Then y = ( 1 − s ) z + s y 0 y=(1-s)z+sy_0 y = ( 1 − s ) z + s y 0 for some z ∈ T 0 ( y ) z\in T_0(y) z ∈ T 0 ( y ) generated by r ∈ F ( y ) r\in F(y) r ∈ F ( y ) . Thus y i − y 0 , i = ( 1 − s ) ( z i − y 0 , i ) y_i-y_{0,i}=(1-s)(z_i-y_{0,i}) y i − y 0 , i = ( 1 − s ) ( z i − y 0 , i ) for every i ∈ N i\in N i ∈ N . Subtracting (B.2) from the equation for z i z_i z i in (B.6) at λ = 0 \lambda=0 λ = 0 cancels the common term δ i p i S i ( y 0 ) \delta_i p_i S_i(y_0) δ i p i S i ( y 0 ) and gives
z i − y 0 , i = δ i [ ( p C i ( y 0 ) + r i ) y i − ( p C i ( y 0 ) + r 0 i ) y 0 , i ] = δ i ( p C i ( y 0 ) + r 0 i ) ( y i − y 0 , i ) + δ i y i ( r i − r 0 i ) , i ∈ N . \begin{aligned}
z_i-y_{0,i}
&=\delta_i\left[(p_{C^i}(y_0)+r^i)y_i-(p_{C^i}(y_0)+r_0^i)y_{0,i}\right]\\
&=\delta_i(p_{C^i}(y_0)+r_0^i)(y_i-y_{0,i})+\delta_i y_i(r^i-r_0^i),\qquad i\in N.
\end{aligned} z i − y 0 , i = δ i [ ( p C i ( y 0 ) + r i ) y i − ( p C i ( y 0 ) + r 0 i ) y 0 , i ] = δ i ( p C i ( y 0 ) + r 0 i ) ( y i − y 0 , i ) + δ i y i ( r i − r 0 i ) , i ∈ N .
Substituting this expression into y i − y 0 , i = ( 1 − s ) ( z i − y 0 , i ) y_i-y_{0,i}=(1-s)(z_i-y_{0,i}) y i − y 0 , i = ( 1 − s ) ( z i − y 0 , i ) and collecting the terms gives
[ 1 − ( 1 − s ) δ i ( p C i ( y 0 ) + r 0 i ) ] ( y i − y 0 , i ) = ( 1 − s ) δ i y i ( r i − r 0 i ) , i ∈ N . \left[1-(1-s)\delta_i(p_{C^i}(y_0)+r_0^i)\right](y_i-y_{0,i})=(1-s)\delta_i y_i(r^i-r_0^i),\qquad i\in N. [ 1 − ( 1 − s ) δ i ( p C i ( y 0 ) + r 0 i ) ] ( y i − y 0 , i ) = ( 1 − s ) δ i y i ( r i − r 0 i ) , i ∈ N .
If s = 1 s=1 s = 1 , then y = y 0 y=y_0 y = y 0 . Suppose that s < 1 s<1 s < 1 . Since p C i ( y 0 ) + r 0 i ≤ 1 p_{C^i}(y_0)+r_0^i\le1 p C i ( y 0 ) + r 0 i ≤ 1 , δ i < 1 \delta_i<1 δ i < 1 , and y i > 0 y_i>0 y i > 0 , the coefficients of y i − y 0 , i y_i-y_{0,i} y i − y 0 , i and r i − r 0 i r^i-r_0^i r i − r 0 i in the preceding identity are strictly positive. Thus y i − y 0 , i y_i-y_{0,i} y i − y 0 , i and r i − r 0 i r^i-r_0^i r i − r 0 i have the same sign for every i ∈ N i\in N i ∈ N . Suppose y ≠ y 0 y\ne y_0 y = y 0 . Then we have
( y − y 0 ) ⊤ ( r − r 0 ) = ∑ i ∈ N ( y i − y 0 , i ) ( r i − r 0 i ) > 0 , (y-y_0)^\top(r-r_0)=\sum_{i\in N}(y_i-y_{0,i})(r^i-r_0^i)>0, ( y − y 0 ) ⊤ ( r − r 0 ) = i ∈ N ∑ ( y i − y 0 , i ) ( r i − r 0 i ) > 0 ,
because every term in the summation is nonnegative and at least one is strictly positive. This contradicts (B.5), since r ∈ F ( y ) r\in F(y) r ∈ F ( y ) and r 0 ∈ R ( y 0 ) r_0\in R(y_0) r 0 ∈ R ( y 0 ) imply ( y − y 0 ) ⊤ ( r − r 0 ) ≤ 0 (y-y_0)^\top(r-r_0)\le0 ( y − y 0 ) ⊤ ( r − r 0 ) ≤ 0 . Thus y 0 y_0 y 0 is the only fixed point throughout the homotopy.
Continuity and normalization then give Λ Y ( T 0 ∣ U ‾ ) = Λ Y ( y 0 ) = + 1 \Lambda_Y(T_0|_{\overline{U}})=\Lambda_Y(y_0)=+1 Λ Y ( T 0 ∣ U ) = Λ Y ( y 0 ) = + 1 . ■
Proofs of Propositions 2 and 3
Note that the arguments from Section B.4 also apply to no-delay payoff vectors without ties. At such a vector y y y , we have K ( y ) = ∅ K(y)=\varnothing K ( y ) = ∅ , R ( y ) = { 0 } R(y)=\{0\} R ( y ) = { 0 } , and L A ( y ) = { 0 } L_A(y)=\{0\} L A ( y ) = { 0 } , so we can take the singleton groups G i = { i } G_i=\{i\} G i = { i } , i ∈ N i\in N i ∈ N . At a no-tie baseline equilibrium y 0 y_0 y 0 , the supporting aggregate is r 0 = 0 r_0=0 r 0 = 0 , and the unique maximizing coalitions remain unchanged throughout a neighborhood of y 0 y_0 y 0 . The set F ( y ) F(y) F ( y ) defined in (B.4) therefore equals { 0 } \{0\} { 0 } throughout that neighborhood.
The next lemma extends the argument in Step 4 of the proof of Lemma B.1 by giving bounds on the diagonal entries of the inverse.
Lemma B.2. Fix θ ∈ Θ \theta\in\Theta θ ∈ Θ and y ∈ Y ( θ ) y \in Y(\theta) y ∈ Y ( θ ) with S j ( y ; θ ) > 0 S_j(y;\theta)>0 S j ( y ; θ ) > 0 for every j ∈ N j \in N j ∈ N . Suppose that y y y satisfies the equitable grouping property with groups G 1 , … , G ℓ G_1,\ldots,G_\ell G 1 , … , G ℓ , where ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 . For j ∈ G t j \in G_t j ∈ G t and C ∈ C j ( y ; θ ) C \in\mathcal{C}_j(y;\theta) C ∈ C j ( y ; θ ) , let c t s = ∣ C ∩ G s ∣ c_{ts}=|C \cap G_s| c t s = ∣ C ∩ G s ∣ and write C = ( c t s ) t , s = 1 ℓ C=(c_{ts})_{t,s=1}^{\ell} C = ( c t s ) t , s = 1 ℓ . For any A t , B t > 0 A_t,B_t>0 A t , B t > 0 , define M = diag ( A t ) t = 1 ℓ + diag ( B t ) t = 1 ℓ C M=\operatorname{diag}(A_t)_{t=1}^{\ell}+\operatorname{diag}(B_t)_{t=1}^{\ell}C M = diag ( A t ) t = 1 ℓ + diag ( B t ) t = 1 ℓ C . Then M M M is nonsingular and
0 < ( M − 1 ) g g < 1 A g , g = 1 , … , ℓ . (26) 0<(M^{-1})_{gg}<\frac{1}{A_g},\qquad g=1,\ldots,\ell. \tag*{(26)} 0 < ( M − 1 ) g g < A g 1 , g = 1 , … , ℓ . (26)
Proof. The counts c t s c_{ts} c t s are well-defined by part (ii) of Definition 1. By the ordering argument in Step 4 of the proof of Lemma B.1 , C C C and M M M are block upper triangular, with identical rows within each diagonal block of C C C . For each diagonal block Q Q Q and s ∈ Q s \in Q s ∈ Q , let c Q s c_{Qs} c Q s denote the common value of c t s c_{ts} c t s over t ∈ Q t \in Q t ∈ Q , and collect these counts in the column vector c Q = ( c Q s ) s ∈ Q c_Q=(c_{Qs})_{s\in Q} c Q = ( c Q s ) s ∈ Q . Then M Q = diag ( A t ) t ∈ Q + ( B t ) t ∈ Q c Q T M_Q=\operatorname{diag}(A_t)_{t\in Q}+(B_t)_{t\in Q}c_Q^{\mathsf T} M Q = diag ( A t ) t ∈ Q + ( B t ) t ∈ Q c Q T . By the matrix determinant lemma, we have
det M Q = ( ∏ t ∈ Q A t ) ( 1 + ∑ t ∈ Q c Q t B t A t ) > 0. \det M_Q=\left(\prod_{t\in Q}A_t\right)\left(1+\sum_{t\in Q}\frac{c_{Qt}B_t}{A_t}\right)>0. det M Q = t ∈ Q ∏ A t 1 + t ∈ Q ∑ A t c Qt B t > 0.
Thus every diagonal block is nonsingular, and therefore M M M is nonsingular.
Let Q Q Q be the diagonal block containing g g g . Since M M M is block upper triangular, its inverse has diagonal block M Q − 1 M_Q^{-1} M Q − 1 . By the adjugate formula, ( M Q − 1 ) g g (M_Q^{-1})_{gg} ( M Q − 1 ) g g equals the determinant of the matrix obtained by deleting row and column g g g from M Q M_Q M Q , divided by det M Q \det M_Q det M Q . Applying the matrix determinant lemma to the numerator and denominator gives
( M − 1 ) g g = ( M Q − 1 ) g g = 1 A g 1 + ∑ t ∈ Q ∖ { g } c Q t B t / A t 1 + ∑ t ∈ Q c Q t B t / A t . (M^{-1})_{gg}=(M_Q^{-1})_{gg}
=\frac{1}{A_g}\frac{1+\sum_{t\in Q\setminus\{g\}}c_{Qt}B_t/A_t}{1+\sum_{t\in Q}c_{Qt}B_t/A_t}. ( M − 1 ) g g = ( M Q − 1 ) g g = A g 1 1 + ∑ t ∈ Q c Qt B t / A t 1 + ∑ t ∈ Q ∖ { g } c Qt B t / A t .
Every maximizing coalition of a proposer in G g G_g G g contains that proposer, so c Q g = c g g ≥ 1 c_{Qg}=c_{gg}\ge1 c Q g = c g g ≥ 1 , which implies (B.12). ■
Proof of Proposition 2
Proof. Fix a 0 ∈ I a_0 \in I a 0 ∈ I , and write θ 0 = θ a 0 \theta_0=\theta_{a_0} θ 0 = θ a 0 and y 0 = y ( a 0 ) y_0=y(a_0) y 0 = y ( a 0 ) . We suppress θ 0 \theta_0 θ 0 in the notation for maximizing menus, proposer surpluses, types, and inclusion polytopes. Put K 0 = K ( y 0 ) K_0=K(y_0) K 0 = K ( y 0 ) , and let r 0 ∈ R ( y 0 ) r_0 \in R(y_0) r 0 ∈ R ( y 0 ) be the unique supporting aggregate inclusion vector given by (B.3). As shown at the start of Section B.4, y 0 ∈ int Y ( θ 0 ) y_0 \in\operatorname{int}Y(\theta_0) y 0 ∈ int Y ( θ 0 ) . We first compare y 0 y_0 y 0 with the equilibrium at every sufficiently close parameter a 0 + ε ∈ I a_0+\varepsilon\in I a 0 + ε ∈ I , and then extend the comparison to the whole interval.
Step 1: Translation and restrictions at nearby equilibria. As in the construction preceding Lemma B.1 , choose a neighborhood V ⊂ int Y ( θ 0 ) V \subset\operatorname{int}Y(\theta_0) V ⊂ int Y ( θ 0 ) of y 0 y_0 y 0 such that S j ( z ) > 0 S_j(z)>0 S j ( z ) > 0 and C j ( z ) ⊆ C j ( y 0 ) \mathcal{C}_j(z)\subseteq\mathcal{C}_j(y_0) C j ( z ) ⊆ C j ( y 0 ) for every j ∈ N j \in N j ∈ N and z ∈ V z \in V z ∈ V . For a 0 + ε ∈ I a_0+\varepsilon\in I a 0 + ε ∈ I , put y = y ( a 0 + ε ) y=y(a_0+\varepsilon) y = y ( a 0 + ε ) . To express the maximizing menus and proposer surpluses at y y y using the baseline characteristic function χ a 0 \chi_{a_0} χ a 0 , define the auxiliary candidate payoff vector z = y − ε e i z=y-\varepsilon e_i z = y − ε e i , where e i e_i e i is the i i i th standard basis vector in R n \mathbb{R}^n R n . For every C ∈ W C\in W C ∈ W ,
χ a 0 + ε ( C ) − y C = χ a 0 ( C ) − z C . (27) \chi_{a_0+\varepsilon}(C)-y_C=\chi_{a_0}(C)-z_C. \tag*{(27)} χ a 0 + ε ( C ) − y C = χ a 0 ( C ) − z C . (27)
Thus the maximizing menus and proposer surpluses at y y y under θ a 0 + ε \theta_{a_0+\varepsilon} θ a 0 + ε are exactly those at z z z under θ 0 \theta_0 θ 0 . We will obtain the desired payoff comparison by bounding z i − y 0 , i z_i-y_{0,i} z i − y 0 , i and using y i − y 0 , i = ε + ( z i − y 0 , i ) y_i-y_{0,i}=\varepsilon+(z_i-y_{0,i}) y i − y 0 , i = ε + ( z i − y 0 , i ) . Corollary 3 gives y → y 0 y\to y_0 y → y 0 and z → y 0 z\to y_0 z → y 0 as ε → 0 \varepsilon\to0 ε → 0 , so z ∈ V z\in V z ∈ V for all sufficiently small ε \varepsilon ε .
Define F ( z ) F(z) F ( z ) by (B.4), with z z z in place of y y y ; it is a non-empty face of R ( y 0 ) R(y_0) R ( y 0 ) by (B.5). Let r r r be the vector generated by the equilibrium proposal distributions of the proposers in K 0 K_0 K 0 at y y y under θ a 0 + ε \theta_{a_0+\varepsilon} θ a 0 + ε . By (B.13), r ∈ F ( z ) r\in F(z) r ∈ F ( z ) , and proposers outside K 0 K_0 K 0 retain their unique maximizing coalitions. The equilibrium payoff equations are
y j = δ j p j S j ( z ) + δ j [ p C j ( y 0 ) + r j ] y j , j ∈ N . y_j=\delta_jp_jS_j(z)+\delta_j\left[p_{C_j}(y_0)+r^j\right]y_j,\qquad j\in N. y j = δ j p j S j ( z ) + δ j [ p C j ( y 0 ) + r j ] y j , j ∈ N .
Solving for r j r^j r j and subtracting (B.3), as in (B.9), gives
r j − r 0 j = p j S j ( y 0 ) y 0 , j y j ( y j − y 0 , j ) + p j y j [ S j ( y 0 ) − S j ( z ) ] , j ∈ N . (28) r^j-r_0^j=\frac{p_jS_j(y_0)}{y_{0,j}y_j}(y_j-y_{0,j})+\frac{p_j}{y_j}\left[S_j(y_0)-S_j(z)\right],\qquad j\in N. \tag*{(28)} r j − r 0 j = y 0 , j y j p j S j ( y 0 ) ( y j − y 0 , j ) + y j p j [ S j ( y 0 ) − S j ( z ) ] , j ∈ N . (28)
Since y , z → y 0 y,z\to y_0 y , z → y 0 as ε → 0 \varepsilon\to0 ε → 0 , this identity implies r → r 0 r\to r_0 r → r 0 . The remaining arguments in Step 2 of the proof of Lemma B.1 therefore give, for all sufficiently small ε \varepsilon ε ,
r − r 0 ∈ L A ( z ) , z − y 0 ∈ L A ( z ) ⊥ . (29) r-r_0\in L_{A(z)},\qquad z-y_0\in L_{A(z)}^\perp. \tag*{(29)} r − r 0 ∈ L A ( z ) , z − y 0 ∈ L A ( z ) ⊥ . (29)
Step 2: Local payoff bounds. Since χ a 0 \chi_{a_0} χ a 0 is M ♮ M^\natural M ♮ -concave and S j ( z ) > 0 S_j(z)>0 S j ( z ) > 0 for every j ∈ N j\in N j ∈ N , Lemma 5 gives an equitable grouping G 1 , … , G ℓ G_1,\ldots,G_\ell G 1 , … , G ℓ at z z z . Let X = [ 1 G 1 ⋯ 1 G ℓ ] X=[\mathbf{1}_{G_1}\ \cdots\ \mathbf{1}_{G_\ell}] X = [ 1 G 1 ⋯ 1 G ℓ ] . By part (i) and (B.15), we have X T ( r − r 0 ) = 0 X^\mathsf{T}(r-r_0)=0 X T ( r − r 0 ) = 0 and
z − y 0 = X ξ , y − y 0 = X ξ + ε e i z-y_0=X\xi,\qquad y-y_0=X\xi+\varepsilon e_i z − y 0 = X ξ , y − y 0 = X ξ + ε e i
for some ξ ∈ R ℓ \xi\in\mathbb{R}^{\ell} ξ ∈ R ℓ . If ℓ = 0 \ell=0 ℓ = 0 , then z = y 0 z=y_0 z = y 0 and y i − y 0 , i = ε y_i-y_{0,i}=\varepsilon y i − y 0 , i = ε . Suppose that ℓ > 0 \ell>0 ℓ > 0 , and let C C C be the count matrix at z z z defined in Lemma B.2 . The surplus calculation in Step 3 of the proof of Lemma B.1 gives S j ( y 0 ) − S j ( z ) = ( C ξ ) t S_j(y_0)-S_j(z)=(C\xi)_t S j ( y 0 ) − S j ( z ) = ( C ξ ) t for j ∈ G t j\in G_t j ∈ G t . Because the groups are disjoint, y j − y 0 , j = ξ t + ε I { j = i } y_j-y_{0,j}=\xi_t+\varepsilon\mathbb{I}\{j=i\} y j − y 0 , j = ξ t + ε I { j = i } for j ∈ G t j\in G_t j ∈ G t . Summing (B.14) over j ∈ G t j\in G_t j ∈ G t and using X T ( r − r 0 ) = 0 X^\mathsf{T}(r-r_0)=0 X T ( r − r 0 ) = 0 therefore gives
0 = ∑ j ∈ G t ( r j j − r 0 j ) = A t ξ t + B t ( C ξ ) t + ε α i I { i ∈ G t } , t = 1 , … , ℓ , (30) 0 = \sum_{j\in G_t}(r_j^j-r_{0}^j)=A_t\xi_t+B_t(C\xi)_t+\varepsilon\alpha_i\mathbb{I}\{i\in G_t\},\qquad t=1,\ldots,\ell, \tag*{(30)} 0 = j ∈ G t ∑ ( r j j − r 0 j ) = A t ξ t + B t ( C ξ ) t + ε α i I { i ∈ G t } , t = 1 , … , ℓ , (30)
where
A t = ∑ j ∈ G t p j S j ( y 0 ) y 0 , j y j > 0 , B t = ∑ j ∈ G t p j y j > 0 , α i = p i S i ( y 0 ) y 0 , i y i > 0. A_t=\sum_{j\in G_t}\frac{p_jS_j(y_0)}{y_{0,j}y_j}>0,\qquad B_t=\sum_{j\in G_t}\frac{p_j}{y_j}>0,\qquad\alpha_i=\frac{p_iS_i(y_0)}{y_{0,i}y_i}>0. A t = j ∈ G t ∑ y 0 , j y j p j S j ( y 0 ) > 0 , B t = j ∈ G t ∑ y j p j > 0 , α i = y 0 , i y i p i S i ( y 0 ) > 0.
Let M = diag ( A t ) t = 1 ℓ + diag ( B t ) t = 1 ℓ C M=\operatorname{diag}(A_t)_{t=1}^{\ell}+\operatorname{diag}(B_t)_{t=1}^{\ell}C M = diag ( A t ) t = 1 ℓ + diag ( B t ) t = 1 ℓ C . If i i i does not belong to any group, (B.16) becomes M ξ = 0 M\xi=0 M ξ = 0 . Lemma B.2 gives ξ = 0 \xi=0 ξ = 0 , so z = y 0 z=y_0 z = y 0 and y i − y 0 , i = ε y_i-y_{0,i}=\varepsilon y i − y 0 , i = ε .
If i ∈ G g i\in G_g i ∈ G g , the same equations give M ξ = − ε α i e g M\xi=-\varepsilon\alpha_i e_g M ξ = − ε α i e g , where e g e_g e g is the g g g th standard basis vector in R ℓ \mathbb{R}^{\ell} R ℓ . Hence
y i − y 0 , i = ε + ξ g = ε [ 1 − α i ( M − 1 ) g g ] . y_i-y_{0,i}=\varepsilon+\xi_g=\varepsilon\left[1-\alpha_i(M^{-1})_{gg}\right]. y i − y 0 , i = ε + ξ g = ε [ 1 − α i ( M − 1 ) g g ] .
Since 0 < α i ≤ A g 0<\alpha_i\leq A_g 0 < α i ≤ A g , the bound (B.12) implies 0 < 1 − α i ( M − 1 ) g g < 1 0<1-\alpha_i(M^{-1})_{gg}<1 0 < 1 − α i ( M − 1 ) g g < 1 . Combining the cases, including ℓ = 0 \ell=0 ℓ = 0 , gives
0 < y i ( a 0 + ε ) − y i ( a 0 ) ε ≤ 1 (31) 0<\frac{y_i(a_0+\varepsilon)-y_i(a_0)}{\varepsilon}\leq1 \tag*{(31)} 0 < ε y i ( a 0 + ε ) − y i ( a 0 ) ≤ 1 (31)
for every sufficiently small nonzero ε \varepsilon ε with a 0 + ε ∈ I a_0+\varepsilon\in I a 0 + ε ∈ I . Note that the groups, and therefore X X X and ξ \xi ξ , can depend on ε \varepsilon ε .
Step 3: Comparison on the interval. For small positive ε \varepsilon ε , (B.17) gives y i ( a 0 + ε ) > y i ( a 0 ) y_i(a_0+\varepsilon)>y_i(a_0) y i ( a 0 + ε ) > y i ( a 0 ) and ( a 0 + ε ) − y i ( a 0 + ε ) ≥ a 0 − y i ( a 0 ) (a_0+\varepsilon)-y_i(a_0+\varepsilon)\geq a_0-y_i(a_0) ( a 0 + ε ) − y i ( a 0 + ε ) ≥ a 0 − y i ( a 0 ) . Because a 0 ∈ I a_0\in I a 0 ∈ I was arbitrary, these local comparisons and continuity imply that a ↦ y i ( a ) a\mapsto y_i(a) a ↦ y i ( a ) is strictly increasing and a ↦ a − y i ( a ) a\mapsto a-y_i(a) a ↦ a − y i ( a ) is nondecreasing on I I I .28 These conclusions give the stated bounds for every a < a ′ a<a' a < a ′ in I I I . ■
Proof of Proposition 3
Proof. Fix d 0 ∈ I d_0\in I d 0 ∈ I , and write θ 0 = θ d 0 \theta_0=\theta^{d_0} θ 0 = θ d 0 and y 0 = y ( d 0 ) y_0=y(d_0) y 0 = y ( d 0 ) . We suppress θ 0 \theta_0 θ 0 in the notation for maximizing menus, proposer surpluses, types, and inclusion polytopes. Put K 0 = K ( y 0 ) K_0=K(y_0) K 0 = K ( y 0 ) , and let r 0 ∈ R ( y 0 ) r_0\in R(y_0) r 0 ∈ R ( y 0 ) be the unique supporting aggregate inclusion vector given by (B.3). As shown at the start of Section B.4, y 0 ∈ int Y ( θ 0 ) y_0\in\operatorname{int}Y(\theta_0) y 0 ∈ int Y ( θ 0 ) . We first compare y 0 y_0 y 0 with y = y ( d ) y=y(d) y = y ( d ) for every sufficiently close d ∈ I d\in I d ∈ I , and then extend the comparison to the whole interval. Write γ = 1 / d 0 − 1 / d \gamma=1/d_0-1/d γ = 1/ d 0 − 1/ d , which has the same sign as d − d 0 d-d_0 d − d 0 . We will show that, for all sufficiently close d d d , either y = y 0 y=y_0 y = y 0 or y i − y 0 , i y_i-y_{0,i} y i − y 0 , i has the same sign as γ \gamma γ .
Step 1: Restrictions at nearby equilibria. As in the construction preceding Lemma B.1 , choose a neighborhood V ⊂ int Y ( θ 0 ) V\subset\operatorname{int}Y(\theta_0) V ⊂ int Y ( θ 0 ) of y 0 y_0 y 0 such that S j ( z ) > 0 S_j(z)>0 S j ( z ) > 0 and C j ( z ) ⊆ C j ( y 0 ) C_j(z)\subseteq C_j(y_0) C j ( z ) ⊆ C j ( y 0 ) for every j ∈ N j\in N j ∈ N and z ∈ V z\in V z ∈ V . Corollary 3 gives y → y 0 y\to y_0 y → y 0 as d → d 0 d\to d_0 d → d 0 , so y ∈ V y\in V y ∈ V for all sufficiently close d d d . The maximization problem (2) depends on χ \chi χ and the candidate payoff vector, but not on discount factors. Thus the maximizing menus and proposer surpluses at y y y under θ d \theta^d θ d coincide with those under θ 0 \theta_0 θ 0 .
Define F ( y ) F(y) F ( y ) by (B.4); it is a non-empty face of R ( y 0 ) R(y_0) R ( y 0 ) by (B.5). Let r ∈ F ( y ) r \in F(y) r ∈ F ( y ) be generated by the equilibrium proposal distributions of the proposers in K 0 K_0 K 0 under θ d \theta^d θ d . Proposers outside K 0 K_0 K 0 retain their unique maximizing coalitions. The equilibrium payoff equations are
y j = δ j d p j S j ( y ) + δ j d [ p C j ( y 0 ) + r j ] y j , j ∈ N . y_j=\delta_j^d p_jS_j(y)+\delta_j^d\left[pC_j(y_0)+r^j\right]y_j,\qquad j\in N. y j = δ j d p j S j ( y ) + δ j d [ p C j ( y 0 ) + r j ] y j , j ∈ N .
Since 1 / δ j d − 1 / δ j d 0 = − γ I { j = i } 1/\delta_j^d-1/\delta_j^{d_0}=-\gamma\mathbb{I}\{j=i\} 1/ δ j d − 1/ δ j d 0 = − γ I { j = i } , solving for r j r^j r j and subtracting (B.3), as in (B.9), gives
r j − r 0 j = p j S j ( y 0 ) y 0 , j y j ( y j − y 0 , j ) + p j y j [ S j ( y 0 ) − S j ( y ) ] − γ I { j = i } , j ∈ N . (32) r^j-r_0^j=\frac{p_jS_j(y_0)}{y_{0,j}y_j}(y_j-y_{0,j})+\frac{p_j}{y_j}\left[S_j(y_0)-S_j(y)\right]-\gamma\mathbb{I}\{j=i\},\qquad j\in N. \tag*{(32)} r j − r 0 j = y 0 , j y j p j S j ( y 0 ) ( y j − y 0 , j ) + y j p j [ S j ( y 0 ) − S j ( y ) ] − γ I { j = i } , j ∈ N . (32)
Since y → y 0 y\to y_0 y → y 0 and γ → 0 \gamma\to0 γ → 0 as d → d 0 d\to d_0 d → d 0 , this identity implies r → r 0 r\to r_0 r → r 0 . The remaining arguments in Step 2 of the proof of Lemma B.1 therefore give, for all sufficiently close d d d ,
r − r 0 ∈ L A ( y ) , y − y 0 ∈ L A ( y ) ⊥ . (33) r-r_0\in L_{A(y)},\qquad y-y_0\in L_{A(y)}^\perp. \tag*{(33)} r − r 0 ∈ L A ( y ) , y − y 0 ∈ L A ( y ) ⊥ . (33)
Step 2: Local payoff comparison and equality. Since χ \chi χ is M ♮ M^\natural M ♮ -concave and S j ( y ) > 0 S_j(y)>0 S j ( y ) > 0 for every j ∈ N j\in N j ∈ N , Lemma 5 gives an equitable grouping G 1 , … , G ℓ G_1,\ldots,G_\ell G 1 , … , G ℓ at y y y . Let X = [ 1 G 1 ⋯ 1 G ℓ ] X=[\mathbf{1}_{G_1}\ \cdots\ \mathbf{1}_{G_\ell}] X = [ 1 G 1 ⋯ 1 G ℓ ] . By part (i) and (B.19), we have X T ( r − r 0 ) = 0 X^\mathsf{T}(r-r_0)=0 X T ( r − r 0 ) = 0 and y − y 0 = X ξ y-y_0=X\xi y − y 0 = X ξ for some ξ ∈ R ℓ \xi\in\mathbb{R}^{\ell} ξ ∈ R ℓ . If ℓ = 0 \ell=0 ℓ = 0 , then y = y 0 y=y_0 y = y 0 . Suppose that ℓ > 0 \ell>0 ℓ > 0 , and let C C C be the count matrix at y y y defined in Lemma B.2. The surplus calculation in Step 3 of the proof of Lemma B.1 gives S j ( y 0 ) − S j ( y ) = ( C ξ ) t S_j(y_0)-S_j(y)=(C\xi)_t S j ( y 0 ) − S j ( y ) = ( C ξ ) t for j ∈ G t j\in G_t j ∈ G t . Because the groups are disjoint, y j − y 0 , j = ξ t y_j-y_{0,j}=\xi_t y j − y 0 , j = ξ t for j ∈ G t j\in G_t j ∈ G t . Summing (B.18) over j ∈ G t j\in G_t j ∈ G t and using X T ( r − r 0 ) = 0 X^\mathsf{T}(r-r_0)=0 X T ( r − r 0 ) = 0 therefore gives
0 = ∑ j ∈ G t ( r j − r 0 j ) = A t ξ t + B t ( C ξ ) t − γ I { i ∈ G t } , t = 1 , … , ℓ , (34) 0=\sum_{j\in G_t}(r^j-r_0^j)=A_t\xi_t+B_t(C\xi)_t-\gamma\mathbb{I}\{i\in G_t\},\qquad t=1,\ldots,\ell, \tag*{(34)} 0 = j ∈ G t ∑ ( r j − r 0 j ) = A t ξ t + B t ( C ξ ) t − γ I { i ∈ G t } , t = 1 , … , ℓ , (34)
where
A t = ∑ j ∈ G t p j S j ( y 0 ) y 0 , j y j > 0 , B t = ∑ j ∈ G t p j y j > 0. A_t=\sum_{j\in G_t}\frac{p_jS_j(y_0)}{y_{0,j}y_j}>0,\qquad B_t=\sum_{j\in G_t}\frac{p_j}{y_j}>0. A t = j ∈ G t ∑ y 0 , j y j p j S j ( y 0 ) > 0 , B t = j ∈ G t ∑ y j p j > 0.
Let M = diag ( A t ) t = 1 ℓ + diag ( B t ) t = 1 ℓ C M=\operatorname{diag}(A_t)_{t=1}^{\ell}+\operatorname{diag}(B_t)_{t=1}^{\ell}C M = diag ( A t ) t = 1 ℓ + diag ( B t ) t = 1 ℓ C . If i i i does not belong to any group, (B.20) becomes M ξ = 0 M\xi=0 M ξ = 0 . Lemma B.2 gives ξ = 0 \xi=0 ξ = 0 , so y = y 0 y=y_0 y = y 0 .
If i ∈ G g i\in G_g i ∈ G g , the same equations give M ξ = γ e g M\xi=\gamma e_g M ξ = γ e g , where e g e_g e g is the g g g th standard basis vector in R ℓ \mathbb{R}^{\ell} R ℓ . Hence y i ( d ) − y i ( d 0 ) = ξ g = γ ( M − 1 ) g g y_i(d)-y_i(d_0)=\xi_g=\gamma(M^{-1})_{gg} y i ( d ) − y i ( d 0 ) = ξ g = γ ( M − 1 ) g g . By (B.12), ( M − 1 ) g g > 0 (M^{-1})_{gg}>0 ( M − 1 ) g g > 0 , so y i ( d ) − y i ( d 0 ) y_i(d)-y_i(d_0) y i ( d ) − y i ( d 0 ) has the same sign as γ \gamma γ . Combining this case with the cases in which y = y 0 y=y_0 y = y 0 , we conclude that, for every sufficiently close d > d 0 d>d_0 d > d 0 , y i ( d ) ≥ y i ( d 0 ) y_i(d)\ge y_i(d_0) y i ( d ) ≥ y i ( d 0 ) , with equality only if y ( d ) = y ( d 0 ) y(d)=y(d_0) y ( d ) = y ( d 0 ) . For sufficiently close d < d 0 d<d_0 d < d 0 , the inequality is reversed and the same equality conclusion holds.
Note that the groups, and therefore X X X and ξ \xi ξ , can depend on d d d .
Step 3: Comparison and equality on the interval. Since d 0 d_0 d 0 was arbitrary, the fact in footnote 27 implies that y i y_i y i is nondecreasing on I I I . Suppose that d < d ′ d<d' d < d ′ and y i ( d ) = y i ( d ′ ) y_i(d)=y_i(d') y i ( d ) = y i ( d ′ ) . Monotonicity implies that y i y_i y i is constant on [ d , d ′ ] [d,d'] [ d , d ′ ] . At each d 0 ∈ [ d , d ′ ] d_0\in[d,d'] d 0 ∈ [ d , d ′ ] , the local equality conclusion in Step 2 therefore implies that y y y is constant on a neighborhood of d 0 d_0 d 0 in [ d , d ′ ] [d,d'] [ d , d ′ ] . Thus y y y is locally constant on [ d , d ′ ] [d,d'] [ d , d ′ ] , and hence constant on this interval. In particular, y ( d ) = y ( d ′ ) y(d)=y(d') y ( d ) = y ( d ′ ) . The converse is immediate by taking the i i i th coordinate of y y y . ■
References
Online Appendix
Equilibrium payoffs in Example 1
Following Example 1, let n = 3 n=3 n = 3 , p i = 1 3 p_i=\frac{1}{3} p i = 3 1 , and δ i = 9 10 \delta_i=\frac{9}{10} δ i = 10 9 for all i ∈ N i\in N i ∈ N . Let the collection of winning coalitions be W = { C : ∣ C ∣ ≥ 2 } \mathcal{W}=\{C:|C|\ge2\} W = { C : ∣ C ∣ ≥ 2 } and let χ ( C ) = min i ∈ C a i \chi(C)=\min_{i\in C}a_i χ ( C ) = min i ∈ C a i for all C ∈ W C\in\mathcal{W} C ∈ W , where a 1 = 2 5 a_1=\frac{2}{5} a 1 = 5 2 and a 2 = a 3 = 1 a_2=a_3=1 a 2 = a 3 = 1 .
Let y y y be an equilibrium payoff vector. When player 1 is recognized, players 2 and 3 together receive at most y 2 + y 3 y_2+y_3 y 2 + y 3 . When player i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } is recognized, their combined payoff is at most 1. If she forms a coalition, its surplus is at most 1. If she passes, S i ( y ) = 0 S_i(y)=0 S i ( y ) = 0 , so equation (1) implies y i = 0 y_i=0 y i = 0 , while the other player’s continuation payoff is at most 1. Thus
y 2 + y 3 ≤ 9 10 ( 1 3 ( y 2 + y 3 ) + 2 3 ) ⟹ y 2 + y 3 ≤ 6 7 < 1. y_2+y_3\le\frac{9}{10}\left(\frac{1}{3}(y_2+y_3)+\frac{2}{3}\right)\quad\Longrightarrow\quad y_2+y_3\le\frac{6}{7}<1. y 2 + y 3 ≤ 10 9 ( 3 1 ( y 2 + y 3 ) + 3 2 ) ⟹ y 2 + y 3 ≤ 7 6 < 1.
It follows that S i ( y ) ≥ χ ( { 2 , 3 } ) − 6 7 = 1 7 > 0 S_i(y)\ge\chi(\{2,3\})-\frac{6}{7}=\frac{1}{7}>0 S i ( y ) ≥ χ ({ 2 , 3 }) − 7 6 = 7 1 > 0 and therefore y i > 0 y_i>0 y i > 0 for i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } . In particular, players 2 and 3 never pass.
Now, we can see that the grand coalition is never optimal. Player 1 strictly prefers { 1 , i } \{1,i\} { 1 , i } to { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } for i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } . In turn, player i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } strictly prefers { 2 , 3 } \{2,3\} { 2 , 3 } to { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } for all y 1 ≥ 0 y_1\ge0 y 1 ≥ 0 . The remaining possible maximizing coalitions are:
Player 1: C ∅ C_{\varnothing} C ∅ , { 1 , 2 } \{1,2\} { 1 , 2 } , { 1 , 3 } \{1,3\} { 1 , 3 } , Player 2: { 1 , 2 } \{1,2\} { 1 , 2 } , { 2 , 3 } \{2,3\} { 2 , 3 } , Player 3: { 1 , 3 } \{1,3\} { 1 , 3 } , { 2 , 3 } \{2,3\} { 2 , 3 } .
We next show that y 2 = y 3 y_2=y_3 y 2 = y 3 . Suppose that y 2 < y 3 y_2<y_3 y 2 < y 3 . Then, player 1 never proposes { 1 , 3 } \{1,3\} { 1 , 3 } , and S 2 ( y ) ≥ S 3 ( y ) S_2(y)\ge S_3(y) S 2 ( y ) ≥ S 3 ( y ) . Let h 2 h_2 h 2 be player 2’s probability of proposing { 1 , 2 } \{1,2\} { 1 , 2 } , let h 3 h_3 h 3 be player 3’s probability of proposing { 1 , 3 } \{1,3\} { 1 , 3 } , and let μ \mu μ be player 1’s probability of forming a non-empty coalition. If h 3 > 0 h_3>0 h 3 > 0 , then { 1 , 3 } \{1,3\} { 1 , 3 } is optimal for player 3, so { 1 , 2 } \{1,2\} { 1 , 2 } is strictly optimal for player 2 and h 2 = 1 h_2=1 h 2 = 1 , and therefore h 2 ≥ h 3 h_2\ge h_3 h 2 ≥ h 3 . Then, the equilibrium payoffs of players 2 and 3 satisfy
y 2 = 3 10 ( S 2 ( y ) + y 2 ) + 3 10 y 2 + 3 10 ( 1 − h 3 ) y 2 ⟹ y 2 = 3 S 2 ( y ) 1 + 3 h 3 y_2=\frac{3}{10}(S_2(y)+y_2)+\frac{3}{10}y_2+\frac{3}{10}(1-h_3)y_2\quad\Longrightarrow\quad y_2=\frac{3S_2(y)}{1+3h_3} y 2 = 10 3 ( S 2 ( y ) + y 2 ) + 10 3 y 2 + 10 3 ( 1 − h 3 ) y 2 ⟹ y 2 = 1 + 3 h 3 3 S 2 ( y )
y 3 = 3 10 ( S 3 ( y ) + y 3 ) + 3 10 ( 1 − μ ) y 3 + 3 10 ( 1 − h 2 ) y 3 ⟹ y 3 = 3 S 3 ( y ) 1 + 3 h 2 + 3 μ , y_3=\frac{3}{10}(S_3(y)+y_3)+\frac{3}{10}(1-\mu)y_3+\frac{3}{10}(1-h_2)y_3\quad\Longrightarrow\quad y_3=\frac{3S_3(y)}{1+3h_2+3\mu}, y 3 = 10 3 ( S 3 ( y ) + y 3 ) + 10 3 ( 1 − μ ) y 3 + 10 3 ( 1 − h 2 ) y 3 ⟹ y 3 = 1 + 3 h 2 + 3 μ 3 S 3 ( y ) ,
so y 2 ≥ y 3 y_2 \ge y_3 y 2 ≥ y 3 , a contradiction. The case y 2 > y 3 y_2 > y_3 y 2 > y 3 is symmetric.
We are now ready to describe all equilibria. Write y 2 = y 3 = w y_2 = y_3 = w y 2 = y 3 = w and note that y 2 + y 3 ≤ 6 7 y_2 + y_3 \le\frac{6}{7} y 2 + y 3 ≤ 7 6 implies w ≤ 3 7 w \le\frac{3}{7} w ≤ 7 3 . Therefore, for i ∈ { 2 , 3 } i \in\{2,3\} i ∈ { 2 , 3 } , we have
χ ( { 2 , 3 } ) − y 2 − y 3 − ( χ ( { 1 , i } ) − y 1 − y i ) = 1 − 2 w − ( 2 5 − y 1 − w ) = 3 5 + y 1 − w ≥ 6 35 + y 1 > 0. \chi(\{2,3\}) - y_2 - y_3 - \left(\chi(\{1,i\}) - y_1 - y_i\right)
= 1 - 2w - \left(\frac{2}{5} - y_1 - w\right)
= \frac{3}{5} + y_1 - w
\ge\frac{6}{35} + y_1 > 0. χ ({ 2 , 3 }) − y 2 − y 3 − ( χ ({ 1 , i }) − y 1 − y i ) = 1 − 2 w − ( 5 2 − y 1 − w ) = 5 3 + y 1 − w ≥ 35 6 + y 1 > 0.
so players 2 and 3 always propose { 2 , 3 } \{2,3\} { 2 , 3 } and S 2 ( y ) = S 3 ( y ) S_2(y) = S_3(y) S 2 ( y ) = S 3 ( y ) .
Since players 2 and 3 have the same positive proposer surplus and payoff, their continuation probabilities are equal, so player 1 proposes each of { 1 , 2 } \{1,2\} { 1 , 2 } and { 1 , 3 } \{1,3\} { 1 , 3 } with probability μ 2 \frac{\mu}{2} 2 μ . Then, the equilibrium expected payoffs satisfy
y 1 = 3 10 μ ( 2 5 − w ) + 3 10 ( 1 − μ ) y 1 , y_1 = \frac{3}{10}\mu\left(\frac{2}{5} - w\right) + \frac{3}{10}(1-\mu)y_1, y 1 = 10 3 μ ( 5 2 − w ) + 10 3 ( 1 − μ ) y 1 ,
w = 3 10 ( 1 − w ) + 3 10 w + 3 10 ( 1 − μ + μ 2 ) w ⟹ w = 6 14 + 3 μ . w = \frac{3}{10}(1-w) + \frac{3}{10}w + \frac{3}{10}\left(1-\mu+\frac{\mu}{2}\right)w
\Longrightarrow w = \frac{6}{14+3\mu}. w = 10 3 ( 1 − w ) + 10 3 w + 10 3 ( 1 − μ + 2 μ ) w ⟹ w = 14 + 3 μ 6 .
If μ = 0 \mu= 0 μ = 0 , player 1 passes, so y 1 = 0 y_1 = 0 y 1 = 0 and w = 3 7 w = \frac{3}{7} w = 7 3 . If 0 < μ < 1 0 < \mu< 1 0 < μ < 1 , player 1 is indifferent between passing and proposing { 1 , 2 } \{1,2\} { 1 , 2 } or { 1 , 3 } \{1,3\} { 1 , 3 } , so y 1 = 0 y_1 = 0 y 1 = 0 and w = 2 5 w = \frac{2}{5} w = 5 2 , which gives μ = 1 3 \mu= \frac{1}{3} μ = 3 1 . Finally, if μ = 1 \mu= 1 μ = 1 , then w = 6 17 w = \frac{6}{17} w = 17 6 and y 1 = 6 425 y_1 = \frac{6}{425} y 1 = 425 6 .
Conversely, for μ = 0 , 1 3 , 1 \mu= 0,\frac{1}{3},1 μ = 0 , 3 1 , 1 , player 1’s proposer surplus from forming coalition { 1 , 2 } \{1,2\} { 1 , 2 } or { 1 , 3 } \{1,3\} { 1 , 3 } is − 1 35 -\frac{1}{35} − 35 1 , 0 0 0 , and 14 425 \frac{14}{425} 425 14 , respectively. Her prescribed proposal probabilities are therefore optimal. Players 2 and 3 strictly prefer { 2 , 3 } \{2,3\} { 2 , 3 } in each case, and all payoff equations are satisfied. By Proposition 1, these are exactly the equilibrium payoff vectors in the example.
Equilibrium payoffs in Example 2
Let y y y be an equilibrium payoff vector. Since every singleton is feasible, the argument in § 4.1 gives S i ( y ) > 0 S_i(y) > 0 S i ( y ) > 0 for every player. Equation (1) therefore gives y i > 0 y_i > 0 y i > 0 , and no player passes.
We first show that y 2 = y 3 y_2 = y_3 y 2 = y 3 . Suppose that y 2 < y 3 y_2 < y_3 y 2 < y 3 . Replacing player 3 by player 2 in { 3 } \{3\} { 3 } or { 1 , 3 } \{1,3\} { 1 , 3 } leaves coalition surplus unchanged and reduces the sum of continuation payoffs. Moreover, { 2 , 3 } \{2,3\} { 2 , 3 } and N N N are feasible for both i ∈ { 2 , 3 } i \in\{2,3\} i ∈ { 2 , 3 } . Hence S 2 ( y ) ≥ S 3 ( y ) S_2(y) \ge S_3(y) S 2 ( y ) ≥ S 3 ( y ) .
Let h i h_i h i be the probability that player i ∈ { 2 , 3 } i \in\{2,3\} i ∈ { 2 , 3 } proposes a coalition containing both players 2 and 3. If h 2 > 0 h_2 > 0 h 2 > 0 , some such coalition is maximizing for player 2. Its proposer surplus is strictly greater than the proposer surplus from either { 3 } \{3\} { 3 } or { 1 , 3 } \{1,3\} { 1 , 3 } , so player 3 always recruits player 2 and h 3 = 1 h_3 = 1 h 3 = 1 . Thus h 2 ≤ h 3 h_2 \le h_3 h 2 ≤ h 3 . Let μ i \mu_i μ i be the probability that player 1 recruits player i ∈ { 2 , 3 } i \in\{2,3\} i ∈ { 2 , 3 } . Player 1 strictly prefers { 1 , 2 } \{1,2\} { 1 , 2 } to { 1 , 3 } \{1,3\} { 1 , 3 } , while her other feasible coalitions contain both players or neither. Hence μ 2 ≥ μ 3 \mu_2 \ge\mu_3 μ 2 ≥ μ 3 .
The payoff equations for players 2 and 3 are
y 2 = 2 65 ( S 2 ( y ) + y 2 ) + 2 65 h 3 y 2 + 60 65 μ 2 y 2 ⟹ y 2 = 2 S 2 ( y ) 63 − 2 h 3 − 60 μ 2 , y 3 = 2 65 ( S 3 ( y ) + y 3 ) + 2 65 h 2 y 3 + 60 65 μ 3 y 3 ⟹ y 3 = 2 S 3 ( y ) 63 − 2 h 2 − 60 μ 3 . \begin{aligned}
y_2 &= \frac{2}{65}\left(S_2(y)+y_2\right)+\frac{2}{65}h_3y_2+\frac{60}{65}\mu_2y_2 &&\Longrightarrow&& y_2=\frac{2S_2(y)}{63-2h_3-60\mu_2},\\
y_3 &= \frac{2}{65}\left(S_3(y)+y_3\right)+\frac{2}{65}h_2y_3+\frac{60}{65}\mu_3y_3 &&\Longrightarrow&& y_3=\frac{2S_3(y)}{63-2h_2-60\mu_3}.
\end{aligned} y 2 y 3 = 65 2 ( S 2 ( y ) + y 2 ) + 65 2 h 3 y 2 + 65 60 μ 2 y 2 = 65 2 ( S 3 ( y ) + y 3 ) + 65 2 h 2 y 3 + 65 60 μ 3 y 3 ⟹ ⟹ y 2 = 63 − 2 h 3 − 60 μ 2 2 S 2 ( y ) , y 3 = 63 − 2 h 2 − 60 μ 3 2 S 3 ( y ) .
Both denominators are positive. Since S 2 ( y ) ≥ S 3 ( y ) S_2(y) \ge S_3(y) S 2 ( y ) ≥ S 3 ( y ) , h 3 ≥ h 2 h_3 \ge h_2 h 3 ≥ h 2 , and μ 2 ≥ μ 3 \mu_2 \ge\mu_3 μ 2 ≥ μ 3 , these equations imply y 2 ≥ y 3 y_2 \ge y_3 y 2 ≥ y 3 , a contradiction. The case y 2 > y 3 y_2 > y_3 y 2 > y 3 is symmetric.
We next determine which coalitions can be proposed. Write y 2 = y 3 = w y_2=y_3=w y 2 = y 3 = w . Every proposed coalition generates surplus at most 5, so summing (1) after dividing each player’s equation by her discount factor gives
y 1 δ 1 + 2 w δ 2 ≤ 5. \frac{y_1}{\delta_1}+\frac{2w}{\delta_2}\le5. δ 1 y 1 + δ 2 2 w ≤ 5.
Since y 1 > 0 y_1>0 y 1 > 0 , it follows that w < 5 2 δ 2 = 32 13 < 5 2 w<\frac{5}{2}\delta_2=\frac{32}{13}<\frac{5}{2} w < 2 5 δ 2 = 13 32 < 2 5 . The grand coalition is therefore strictly preferred to either { 1 , 2 } \{1,2\} { 1 , 2 } or { 1 , 3 } \{1,3\} { 1 , 3 } , because 5 − y 1 − 2 w > 5 2 − y 1 − w 5-y_1-2w>\frac{5}{2}-y_1-w 5 − y 1 − 2 w > 2 5 − y 1 − w is equivalent to w < 5 2 w<\frac{5}{2} w < 2 5 .
If w ≥ 2 w\ge2 w ≥ 2 , then both 2 − w 2-w 2 − w and 5 2 − 2 w \frac{5}{2}-2w 2 5 − 2 w are nonpositive. Players 2 and 3 have strictly positive proposer surplus, so both must propose the grand coalition. Their common proposer surplus is then S 2 ( y ) = S 3 ( y ) = 5 − y 1 − 2 w ≤ 1 − y 1 < 1 S_2(y)=S_3(y)=5-y_1-2w\le1-y_1<1 S 2 ( y ) = S 3 ( y ) = 5 − y 1 − 2 w ≤ 1 − y 1 < 1 . Player i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } receives S i ( y ) + w S_i(y)+w S i ( y ) + w when recognized and at most w w w otherwise. Her payoff equation therefore gives
w ≤ 64 65 ( w + S i ( y ) 32 ) ⟹ w ≤ 2 S i ( y ) < 2 , w\le\frac{64}{65}\left(w+\frac{S_i(y)}{32}\right)\Longrightarrow w\le2S_i(y)<2, w ≤ 65 64 ( w + 32 S i ( y ) ) ⟹ w ≤ 2 S i ( y ) < 2 ,
a contradiction. Thus w < 2 w<2 w < 2 , and player 1 strictly prefers the grand coalition to her singleton because 5 − y 1 − 2 w > 1 − y 1 5-y_1-2w>1-y_1 5 − y 1 − 2 w > 1 − y 1 is equivalent to w < 2 w<2 w < 2 .
Player i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } receives w w w whenever player 1 is recognized and can obtain an allocation of 2 by forming her singleton when recognized herself. Since all other payoff terms are nonnegative, her payoff equation gives
w ≥ 64 65 ( 15 16 w + 2 32 ) ⟹ w ≥ 4 5 > 1 2 . w\ge\frac{64}{65}\left(\frac{15}{16}w+\frac{2}{32}\right)\Longrightarrow w\ge\frac{4}{5}>\frac{1}{2}. w ≥ 65 64 ( 16 15 w + 32 2 ) ⟹ w ≥ 5 4 > 2 1 .
For i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } , the singleton coalition therefore gives strictly greater proposer surplus than coalition { 2 , 3 } \{2,3\} { 2 , 3 } because 2 − w > 5 2 − 2 w 2-w>\frac{5}{2}-2w 2 − w > 2 5 − 2 w is equivalent to w − 1 2 > 0 w-\frac{1}{2}>0 w − 2 1 > 0 . The remaining possible maximizing coalitions are:
Player 1: { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } , Player 2: { 2 } \{2\} { 2 } , { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } , Player 3: { 3 } \{3\} { 3 } , { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } .
For i ∈ { 2 , 3 } i\in\{2,3\} i ∈ { 2 , 3 } , h i h_i h i is therefore the probability that player i i i proposes the grand coalition.
Since players 2 and 3 have the same positive proposer surplus and payoff, their continuation probabilities are equal. Hence
p 1 + p 2 + p 3 h 3 = p 1 + p 3 + p 2 h 2 ⟹ h 2 = h 3 = h . p_1 + p_2 + p_3h_3 = p_1 + p_3 + p_2h_2 \qquad\Longrightarrow\qquad h_2 = h_3 = h. p 1 + p 2 + p 3 h 3 = p 1 + p 3 + p 2 h 2 ⟹ h 2 = h 3 = h .
Now we can write the payoff equations as follows:
y 1 = 15 23 ( 5 − 2 w ) + h 23 y 1 , w = 2 65 [ ( 1 − h ) 2 + h ( 5 − y 1 − w ) ] + 60 65 w + 2 h 65 w . \begin{aligned}
y_1 &= \frac{15}{23}(5-2w)+\frac{h}{23}y_1,\\
w &= \frac{2}{65}\left[(1-h)2+h(5-y_1-w)\right]+\frac{60}{65}w+\frac{2h}{65}w.
\end{aligned} y 1 w = 23 15 ( 5 − 2 w ) + 23 h y 1 , = 65 2 [ ( 1 − h ) 2 + h ( 5 − y 1 − w ) ] + 65 60 w + 65 2 h w .
For h ∈ [ 0 , 1 ] h \in[0,1] h ∈ [ 0 , 1 ] , these equations have the unique solution
y 1 ( h ) = 51 − 36 h 23 − 13 h , w ( h ) = 92 − 16 h − 6 h 2 5 ( 23 − 13 h ) . y_1(h)=\frac{51-36h}{23-13h}, \qquad w(h)=\frac{92-16h-6h^2}{5(23-13h)}. y 1 ( h ) = 23 − 13 h 51 − 36 h , w ( h ) = 5 ( 23 − 13 h ) 92 − 16 h − 6 h 2 .
For players 2 and 3, the grand coalition’s advantage in proposer surplus over the singleton is
Δ ( h ) = 3 − y 1 ( h ) − w ( h ) = ( 2 h − 1 ) ( 3 h + 2 ) 5 ( 23 − 13 h ) . \Delta(h)=3-y_1(h)-w(h)=\frac{(2h-1)(3h+2)}{5(23-13h)}. Δ ( h ) = 3 − y 1 ( h ) − w ( h ) = 5 ( 23 − 13 h ) ( 2 h − 1 ) ( 3 h + 2 ) .
If 0 < h < 1 0<h<1 0 < h < 1 , both coalitions are proposed with positive probability, so optimality requires Δ ( h ) = 0 \Delta(h)=0 Δ ( h ) = 0 and therefore h = 1 2 h=\frac{1}{2} h = 2 1 . The remaining possibilities are h = 0 h=0 h = 0 and h = 1 h=1 h = 1 . Thus every equilibrium payoff vector must be one of
y ( 0 ) = ( 51 23 , 4 5 , 4 5 ) , y ( 1 2 ) = ( 2 , 1 , 1 ) , y ( 1 ) = ( 3 2 , 7 5 , 7 5 ) . y(0)=\left(\frac{51}{23},\frac{4}{5},\frac{4}{5}\right), \qquad y\left(\frac{1}{2}\right)=(2,1,1), \qquad y(1)=\left(\frac{3}{2},\frac{7}{5},\frac{7}{5}\right). y ( 0 ) = ( 23 51 , 5 4 , 5 4 ) , y ( 2 1 ) = ( 2 , 1 , 1 ) , y ( 1 ) = ( 2 3 , 5 7 , 5 7 ) .
Conversely, each of these vectors satisfies 1 2 < w < 2 \frac{1}{2}<w<2 2 1 < w < 2 , so the strict comparisons excluding pairs and player 1’s singleton hold. For h = 0 , 1 2 , 1 h=0,\frac{1}{2},1 h = 0 , 2 1 , 1 , the proposer surplus from the grand coalition is 136 115 \frac{136}{115} 115 136 , 1 1 1 , and 7 10 \frac{7}{10} 10 7 , respectively, so passing is strictly suboptimal for every player. For players 2 and 3, the difference in proposer surplus Δ ( h ) \Delta(h) Δ ( h ) is − 2 115 -\frac{2}{115} − 115 2 , 0 0 0 , and 1 10 \frac{1}{10} 10 1 , respectively. Their prescribed proposal probabilities are therefore optimal, and all payoff equations are satisfied. By Proposition 1, these are exactly the equilibrium payoff vectors in the example. Both endpoint equilibria have unique maximizing coalitions for each player.
Keeping W W W fixed, multiplicity persists under sufficiently small changes in ( χ , p , δ ) (\chi,p,\delta) ( χ , p , δ ) . At each endpoint equilibrium, fix each proposer’s unique maximizing coalition. The resulting payoff equations form a nonsingular linear system by Lemma 3, so its solution varies continuously with the primitives. The nearby solutions remain in the interiors of their respective payoff domains and satisfy all strict proposal-optimality inequalities. Thus two distinct no-tie equilibrium payoff vectors persist, including under changes that break the symmetry between players 2 and 3. Each has local index +1 by Lemma 3. If they were the only equilibrium payoff vectors, additivity would give a global index of +2, contradicting Lemma 1. Hence every sufficiently nearby game has at least three equilibrium payoff vectors.
The payoff calculation also verifies the feedback mechanism described after Example 2. Varying the common proposal probability h h h around 1 2 \frac{1}{2} 2 1 , without imposing proposal optimality, gives
y 1 ′ ( 1 2 ) = − 20 33 , w ′ ( 1 2 ) = 86 165 , Δ ′ ( 1 2 ) = 14 165 > 0. y_1'\left(\frac{1}{2}\right)=-\frac{20}{33},\qquad w'\left(\frac{1}{2}\right)=\frac{86}{165},\qquad\Delta'\left(\frac{1}{2}\right)=\frac{14}{165}>0. y 1 ′ ( 2 1 ) = − 33 20 , w ′ ( 2 1 ) = 165 86 , Δ ′ ( 2 1 ) = 165 14 > 0.
Thus players 2 and 3 become more expensive for proposer 1 to recruit, but player 1’s continuation payoff falls by more than either other player’s continuation payoff rises. The combined cost of recruiting the other two players falls for each of proposers 2 and 3, making the grand coalition more attractive relative to the singleton and reinforcing the increase in h h h .
Limited harm and no delay
Observation 1 in § 3 suggests a recursive restriction on the primitives. If y y y is an equilibrium payoff vector and S i ( y ; θ ) = 0 S_i(y;\theta)=0 S i ( y ; θ ) = 0 , then y i = 0 y_i=0 y i = 0 . Moreover, no coalition with strictly positive proposer surplus can include player i i i , because she could then obtain strictly positive proposer surplus by proposing that coalition herself. Thus any delay equilibrium partitions N N N into a set A A A of players who form strictly profitable coalitions among players in A A A and a fringe set N ∖ A N\setminus A N ∖ A of harmful players who have zero payoffs.
The restriction, called limited harm , is formulated through reduced payoff equations. For any non-empty subset A ⊆ N A\subseteq N A ⊆ N , let W A = { C ∈ W : C ⊆ A } \mathcal{W}_A=\{C\in\mathcal{W}:C\subseteq A\} W A = { C ∈ W : C ⊆ A } and W A i = { C ∈ W A : i ∈ C } \mathcal{W}_A^i=\{C\in\mathcal{W}_A:i\in C\} W A i = { C ∈ W A : i ∈ C } . For z ∈ R + A z\in\mathbb{R}_+^A z ∈ R + A , let z A ∈ R + n z^A\in\mathbb{R}_+^n z A ∈ R + n be its extension by zero outside A A A : z i A = z i z_i^A=z_i z i A = z i for i ∈ A i\in A i ∈ A and z i A = 0 z_i^A=0 z i A = 0 for i ∉ A i\notin A i ∈ / A . Each player i ∈ N i\in N i ∈ N is recognized with her original probability p i p_i p i .
Each player i ∈ A i\in A i ∈ A maximizes proposer surplus over W A i ∪ { C ∅ } \mathcal{W}_A^i\cup\{C_{\varnothing}\} W A i ∪ { C ∅ } . Define S i A ( z ) = max C ∈ W A i ∪ { C ∅ } ( χ ( C ) − z C ) S_i^A(z)=\max_{C\in\mathcal{W}_A^i\cup\{C_{\varnothing}\}}\left(\chi(C)-z_C\right) S i A ( z ) = max C ∈ W A i ∪ { C ∅ } ( χ ( C ) − z C ) and C i A ( z ) = arg max C ∈ W A i ∪ { C ∅ } ( χ ( C ) − z C ) C_i^A(z)=\arg\max_{C\in\mathcal{W}_A^i\cup\{C_{\varnothing}\}}\left(\chi(C)-z_C\right) C i A ( z ) = arg max C ∈ W A i ∪ { C ∅ } ( χ ( C ) − z C ) for each i ∈ A i\in A i ∈ A . Let R A ( z ) R_A(z) R A ( z ) and C A A ( z ) \mathcal{C}_A^A(z) C A A ( z ) be the analogues of R ( y ) R(y) R ( y ) and C A ( y ) \mathcal{C}^A(y) C A ( y ) for the reduced family W A \mathcal{W}_A W A .
For each fringe player j ∉ A j\notin A j ∈ / A , allow mixing over the set D j A ( z ) = { C ∈ W j ∪ { C ∅ } : χ ( C ) − z C A = 0 } D_j^A(z)=\{C\in\mathcal{W}^j\cup\{C_{\varnothing}\}:\chi(C)-z_C^A=0\} D j A ( z ) = { C ∈ W j ∪ { C ∅ } : χ ( C ) − z C A = 0 } of coalitions yielding zero proposer surplus. Passing moves the game to the next period and gives every player in A A A her continuation payoff. Forming a non-empty coalition ends the game and gives continuation payoffs only to the members it includes. Let H A ( z ) ⊆ [ 0 , 1 ] A \mathcal{H}_A(z)\subseteq[0,1]^A H A ( z ) ⊆ [ 0 , 1 ] A collect the fringe players’ contributions to continuation probabilities when they mix over these sets:
H A ( z ) = { λ ∈ [ 0 , 1 ] A : λ i = ∑ j ∉ A p j ∑ C ∈ D j A ( z ) : C ∋ i or C = C ∅ ρ j ( C ) , ρ j ∈ Δ ( D j A ( z ) ) } . \mathcal{H}_A(z)=\left\{\lambda\in[0,1]^A:\lambda_i=\sum_{j\notin A}p_j\sum_{\substack{C\in\mathcal{D}^{A}_j(z):\\ C\ni i\ \text{or}\ C=C_{\varnothing}}}\rho_j(C),\ \rho_j\in\Delta(\mathcal{D}^{A}_j(z))\right\}. H A ( z ) = ⎩ ⎨ ⎧ λ ∈ [ 0 , 1 ] A : λ i = j ∈ / A ∑ p j C ∈ D j A ( z ) : C ∋ i or C = C ∅ ∑ ρ j ( C ) , ρ j ∈ Δ ( D j A ( z )) ⎭ ⎬ ⎫ .
I will say that z z z is an augmented reduced equilibrium on A A A if there exist r ∈ R A ( z ) r\in R_A(z) r ∈ R A ( z ) and λ ∈ H A ( z ) \lambda\in\mathcal{H}_A(z) λ ∈ H A ( z ) such that
z i = δ i p i S i A ( z ) 1 − δ i p i C i A ( z ) − δ i r i − δ i λ i , i ∈ A . z_i=\frac{\delta_i p_i S_i^A(z)}{1-\delta_i p_i C_i^A(z)-\delta_i r_i-\delta_i\lambda_i},\qquad i\in A. z i = 1 − δ i p i C i A ( z ) − δ i r i − δ i λ i δ i p i S i A ( z ) , i ∈ A .
Let E A ( θ ) E_A(\theta) E A ( θ ) denote the set of such payoff vectors.
For an outsider i ∉ A i\notin A i ∈ / A , define her entry surplus against such a payoff vector z z z by m i ∣ A ( z ) = max C ∈ W A i ( χ ( C ) − z C A ) m_{i\mid A}(z)=\max_{C\in\mathcal{W}^i_A}(\chi(C)-z^A_C) m i ∣ A ( z ) = max C ∈ W A i ( χ ( C ) − z C A ) . This is the largest net surplus that player i i i can obtain by forming a non-empty coalition in the original game when the players in A A A are priced at z z z and the fringe players are priced at zero.
Assumption LH (limited harm). For every proper non-empty subset A ⊂ N A\subset N A ⊂ N and every augmented reduced equilibrium payoff vector z z z on A A A , there exists at least one outsider i ∉ A i\notin A i ∈ / A such that m i ∣ A ( z ) > 0 m_{i\mid A}(z)>0 m i ∣ A ( z ) > 0 .
Assumption LH rules out delay configurations in which some proper subgroup sustains its own continuation payoffs while no outsider can form a profitable coalition. The next proposition shows that it characterizes Assumption ND exactly.
Proposition OA.1. Fix θ ∈ Θ \theta\in\Theta θ ∈ Θ . Assumption LH holds if and only if θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND .
Proof. Suppose first that Assumption LH holds. Let y ∈ E ( θ ) y\in E(\theta) y ∈ E ( θ ) , and choose r ∈ R ( y ) r\in R(y) r ∈ R ( y ) supporting the payoff equations at y y y . Choose proposal distributions ( ρ j ) j (\rho_j)_j ( ρ j ) j that induce r r r . Suppose, toward a contradiction, that S j ( y ) = 0 S_j(y)=0 S j ( y ) = 0 for some player j j j . Let A = { i ∈ N : S i ( y ) > 0 } A=\{i\in N:S_i(y)>0\} A = { i ∈ N : S i ( y ) > 0 } . Then A A A is a proper subset of N N N . It is also non-empty, by the same argument as in the proof of Proposition A.1 .
For every outsider j ∉ A j\notin A j ∈ / A , we have S j ( y ) = 0 S_j(y)=0 S j ( y ) = 0 , so the j j j th equilibrium equation immediately gives y j = 0 y_j=0 y j = 0 . Next, if i ∈ A i\in A i ∈ A and C ∈ C i ( y ) C\in\mathcal{C}_i(y) C ∈ C i ( y ) , then C ⊆ A C\subseteq A C ⊆ A . Otherwise some j ∈ C ∖ A j\in C\setminus A j ∈ C ∖ A would satisfy y j = 0 y_j=0 y j = 0 , so player j j j could form the same coalition C C C and obtain proposer surplus at least χ ( C ) − y C = S i ( y ) > 0 \chi(C)-y_C=S_i(y)>0 χ ( C ) − y C = S i ( y ) > 0 , contradicting j ∉ A j\notin A j ∈ / A . Therefore every coalition in C i ( y ) \mathcal{C}_i(y) C i ( y ) lies in W A i \mathcal{W}^i_A W A i .
Let z = ( y i ) i ∈ A ∈ R + A z=(y_i)_{i\in A}\in\mathbb{R}^{A}_{+} z = ( y i ) i ∈ A ∈ R + A . For each i ∈ A i\in A i ∈ A , all full-game maximizing coalitions lie in W A i \mathcal{W}^i_A W A i , so S i A ( z ) = S i ( y ) S_i^A(z)=S_i(y) S i A ( z ) = S i ( y ) and C i A ( z ) = C i ( y ) \mathcal{C}_i^A(z)=\mathcal{C}_i(y) C i A ( z ) = C i ( y ) . The restriction of the equilibrium mixing rules to the players in A A A therefore induces some vector r A ∈ R A ( z ) r_A\in R_A(z) r A ∈ R A ( z ) . For each outsider j ∉ A j \notin A j ∈ / A , every coalition C ∈ C j ( y ) C \in\mathcal{C}_j(y) C ∈ C j ( y ) satisfies χ ( C ) − z C A = χ ( C ) − y C = S j ( y ) = 0 \chi(C)-z^A_C=\chi(C)-y_C=S_j(y)=0 χ ( C ) − z C A = χ ( C ) − y C = S j ( y ) = 0 , because y y y and z A z^A z A agree on A A A and both are zero outside A A A . Hence C j ( y ) ⊆ D j A ( z ) \mathcal{C}_j(y)\subseteq D^A_j(z) C j ( y ) ⊆ D j A ( z ) for every j ∉ A j\notin A j ∈ / A . Let λ ∈ [ 0 , 1 ] A \lambda\in[0,1]^A λ ∈ [ 0 , 1 ] A be induced by the outsiders’ equilibrium mixing:
λ i = ∑ j ∉ A p j ∑ C ∈ C j ( y ) : C ∋ i or C = C ∅ ρ j ( C ) , i ∈ A . \lambda_i=\sum_{j\notin A}p_j\sum_{\substack{C\in\mathcal{C}_j(y):C\ni i\\\text{or }C=C_{\varnothing}}}\rho_j(C),\qquad i\in A. λ i = j ∈ / A ∑ p j C ∈ C j ( y ) : C ∋ i or C = C ∅ ∑ ρ j ( C ) , i ∈ A .
Then λ ∈ H A ( z ) \lambda\in\mathcal{H}_A(z) λ ∈ H A ( z ) .
Finally, fix i ∈ A i\in A i ∈ A . Because no player in A A A passes and no player in A A A proposes a coalition containing an outsider, the equilibrium payoff equation for player i i i can be decomposed into contributions from no-tie proposers in A A A , tie proposers in A A A , and outsiders:
y i = δ i p i S i ( y ) 1 − δ i p C A i ( z ) − δ i r A i − δ i λ i = δ i p i S i A ( z ) 1 − δ i p C A i ( z ) − δ i r A i − δ i λ i . y_i=\frac{\delta_i p_i S_i(y)}{1-\delta_i p C^i_A(z)-\delta_i r^i_A-\delta_i\lambda_i}
=\frac{\delta_i p_i S^A_i(z)}{1-\delta_i p C^i_A(z)-\delta_i r^i_A-\delta_i\lambda_i}. y i = 1 − δ i p C A i ( z ) − δ i r A i − δ i λ i δ i p i S i ( y ) = 1 − δ i p C A i ( z ) − δ i r A i − δ i λ i δ i p i S i A ( z ) .
Thus z ∈ E A ( θ ) z\in\mathcal{E}_A(\theta) z ∈ E A ( θ ) .
Assumption LH now implies that there exists some outsider j ∉ A j\notin A j ∈ / A such that m j ∣ A ( z ) > 0 m_{j\mid A}(z)>0 m j ∣ A ( z ) > 0 . But since y = z A y=z^A y = z A and S j ( y ) = 0 S_j(y)=0 S j ( y ) = 0 , we have m j ∣ A ( z ) = max C ∈ W j ( χ ( C ) − z C A ) = max C ∈ W j ( χ ( C ) − y C ) ≤ 0 m_{j\mid A}(z)=\max_{C\in\mathcal{W}_j}(\chi(C)-z^A_C)=\max_{C\in\mathcal{W}_j}(\chi(C)-y_C)\leq0 m j ∣ A ( z ) = max C ∈ W j ( χ ( C ) − z C A ) = max C ∈ W j ( χ ( C ) − y C ) ≤ 0 , a contradiction. Therefore every player has strictly positive proposer surplus at every equilibrium, and hence θ ∈ Θ N D \theta\in\Theta^{\mathrm{ND}} θ ∈ Θ ND .
For the converse, suppose that Assumption LH fails. Then there are a proper non-empty subset A ⊂ N A\subset N A ⊂ N and z ∈ E A ( θ ) z\in\mathcal{E}_A(\theta) z ∈ E A ( θ ) such that m j ∣ A ( z ) ≤ 0 m_{j\mid A}(z)\leq0 m j ∣ A ( z ) ≤ 0 for every j ∉ A j\notin A j ∈ / A . Set y = z A y=z^A y = z A , and choose reduced proposal distributions and fringe distributions supporting the augmented reduced payoff equations at z z z .
Every coalition C C C containing an outsider j j j satisfies χ ( C ) − y C ≤ m j ∣ A ( z ) ≤ 0 \chi(C)-y_C\leq m_{j\mid A}(z)\leq0 χ ( C ) − y C ≤ m j ∣ A ( z ) ≤ 0 . Since passing is available, each insider’s maximal proposer surplus in the full game is therefore S i A ( z ) S^A_i(z) S i A ( z ) , and her reduced maximizing proposals remain optimal. Each outsider’s maximal proposer surplus is zero, so all proposals in D j A ( z ) D^A_j(z) D j A ( z ) are also optimal in the full game. The chosen distributions thus use only maximizing coalitions. Their full-game payoff equations hold for insiders by the augmented reduced equations, and for outsiders because y j = S j ( y ) = 0 y_j=S_j(y)=0 y j = S j ( y ) = 0 .
To verify that y ∈ Y y\in Y y ∈ Y , note that the total continuation probability in each augmented reduced equation is at most one, so its denominator is at least 1 − δ i > 0 1-\delta_i>0 1 − δ i > 0 . If S i A ( z ) = 0 S^A_i(z)=0 S i A ( z ) = 0 , that equation gives z i = 0 z_i=0 z i = 0 . Otherwise, any maximizing reduced coalition C ∈ W A i C\in\mathcal{W}^i_A C ∈ W A i satisfies 0 ≤ z i ≤ z C < χ ( C ) ≤ max D ∈ W i χ ( D ) 0\leq z_i\leq z_C<\chi(C)\leq\max_{D\in\mathcal{W}^i}\chi(D) 0 ≤ z i ≤ z C < χ ( C ) ≤ max D ∈ W i χ ( D ) . Outsiders have zero payoff. Hence y ∈ Y y\in Y y ∈ Y , and Proposition 1 gives y ∈ E ( θ ) y\in\mathcal{E}(\theta) y ∈ E ( θ ) . Since A ≠ N A\neq N A = N , this equilibrium has an outsider with zero proposer surplus, so θ ∉ Θ N D \theta\notin\Theta^{\mathrm{ND}} θ ∈ / Θ ND . This proves the converse by contraposition. ■
Checking Assumption LH can be demanding because it involves the augmented reduced equilibria of every proper non-empty group of players. The condition can nevertheless be substantially less restrictive than the primitive-only bound. In the setting of Observation 1, the calculation in Section OA.3.1 shows that LH holds if and only if a 1 > 3 7 a_1 > \frac{3}{7} a 1 > 7 3 , compared with the bound a 1 > 9 10 a_1 > \frac{9}{10} a 1 > 10 9 from Proposition A.2 .
Limited harm in the delay example
Observation OA.1. Fix the primitives of Example 1, except let a 1 ∈ ( 0 , 1 ) a_1 \in(0,1) a 1 ∈ ( 0 , 1 ) vary while a 2 = a 3 = 1 a_2 = a_3 = 1 a 2 = a 3 = 1 . Assumption LH holds if and only if a 1 > 3 7 a_1 > \frac{3}{7} a 1 > 7 3 .
Proof. We first show that a 1 > 3 7 a_1 > \frac{3}{7} a 1 > 7 3 is sufficient. Consider any proper non-empty subset A ⊂ N A \subset N A ⊂ N and any augmented reduced equilibrium z z z on A A A . If A A A is a singleton, no winning coalition is feasible in the reduced game, so z = 0 z = 0 z = 0 and every outsider has positive entry surplus. If A A A is a pair, its only winning coalition must have positive proposer surplus. Otherwise the reduced payoff equations would give z = 0 z = 0 z = 0 , contradicting χ ( A ) > 0 \chi(A) > 0 χ ( A ) > 0 . Hence z A < χ ( A ) z_A < \chi(A) z A < χ ( A ) , and both players always propose A A A .
If A = { 1 , 2 } A = \{1,2\} A = { 1 , 2 } , then z 1 + z 2 < a 1 < 1 z_1 + z_2 < a_1 < 1 z 1 + z 2 < a 1 < 1 , so outsider 3 can propose { 2 , 3 } \{2,3\} { 2 , 3 } and obtain positive proposer surplus 1 − z 2 1-z_2 1 − z 2 . The case A = { 1 , 3 } A = \{1,3\} A = { 1 , 3 } is symmetric.
Let A = { 2 , 3 } A = \{2,3\} A = { 2 , 3 } . Players 2 and 3 always propose A A A , so their proposals contribute 2 3 \frac{2}{3} 3 2 to each player’s continuation probability. Since for each i ∈ { 2 , 3 } i \in\{2,3\} i ∈ { 2 , 3 } we have λ i ≤ p 1 = 1 3 \lambda_i \le p_1 = \frac{1}{3} λ i ≤ p 1 = 3 1 , the augmented reduced payoff equations give
z i = 3 10 ( 1 − z 2 − z 3 ) 1 − 9 10 ( 2 3 + λ i ) ≤ 3 ( 1 − z 2 − z 3 ) , i ∈ { 2 , 3 } . z_i = \frac{\frac{3}{10}(1-z_2-z_3)}{1-\frac{9}{10}(\frac{2}{3}+\lambda_i)} \le3(1-z_2-z_3), \qquad i \in\{2,3\}. z i = 1 − 10 9 ( 3 2 + λ i ) 10 3 ( 1 − z 2 − z 3 ) ≤ 3 ( 1 − z 2 − z 3 ) , i ∈ { 2 , 3 } .
Summing yields z 2 + z 3 ≤ 6 7 z_2+z_3 \le\frac{6}{7} z 2 + z 3 ≤ 7 6 , and therefore
m 1 ∣ A ( z ) = max { a 1 − z 2 , a 1 − z 3 , a 1 − z 2 − z 3 } = a 1 − min { z 2 , z 3 } ≥ a 1 − 3 7 > 0. m_{1|A}(z) = \max\{a_1-z_2,a_1-z_3,a_1-z_2-z_3\} = a_1-\min\{z_2,z_3\} \ge a_1-\frac{3}{7} > 0. m 1∣ A ( z ) = max { a 1 − z 2 , a 1 − z 3 , a 1 − z 2 − z 3 } = a 1 − min { z 2 , z 3 } ≥ a 1 − 7 3 > 0.
Thus LH holds whenever a 1 > 3 7 a_1 > \frac{3}{7} a 1 > 7 3 .
To show necessity, let a 1 ≤ 3 7 a_1 \le\frac{3}{7} a 1 ≤ 7 3 and consider A = { 2 , 3 } A = \{2,3\} A = { 2 , 3 } , with players 2 and 3 proposing A A A and player 1 passing. Then λ 2 = λ 3 = 1 3 \lambda_2 = \lambda_3 = \frac{1}{3} λ 2 = λ 3 = 3 1 , so the reduced payoff equations become
z i = 3 ( 1 − z 2 − z 3 ) , i ∈ { 2 , 3 } , ⟹ z 2 = z 3 = 3 7 . z_i = 3(1-z_2-z_3), \qquad i \in\{2,3\}, \qquad\Longrightarrow\qquad z_2 = z_3 = \frac{3}{7}. z i = 3 ( 1 − z 2 − z 3 ) , i ∈ { 2 , 3 } , ⟹ z 2 = z 3 = 7 3 .
At this vector, proposing A A A gives players 2 and 3 proposer surplus 1 7 > 0 \frac{1}{7} > 0 7 1 > 0 . These choices therefore support an augmented reduced equilibrium. The only outsider is player 1, whose entry surplus is m 1 ∣ A ( z ) = a 1 − 3 7 ≤ 0 m_{1|A}(z) = a_1-\frac{3}{7} \le0 m 1∣ A ( z ) = a 1 − 7 3 ≤ 0 . Hence LH fails for a 1 ≤ 3 7 a_1 \le\frac{3}{7} a 1 ≤ 7 3 .