ISSN (Print) 0473-453X

Discussion Paper No. 1166

ISSN (Online) 2435-0982

SIGNALING UNDERDOUBLE-CROSSING PREFERENCES:
THE CASE OFDISCRETE TYPES
Chia-Hui Chen
Junichiro Ishida
Wing Suen

March 2022

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

Signaling under Double-Crossing Preferences:
The Case of Discrete Types
CHIA-HUI CHEN
Kyoto University

JUNICHIRO ISHIDA
Osaka University

WING SUEN
University of Hong Kong
March 3, 2022

Abstract. The class of double-crossing preferences, where signaling is cheaper
for higher types than for lower types at low signaling levels and the opposite
is true at high signaling levels, underlines the phenomenon of countersignaling. We show that under the D1 refinement, the equilibrium signaling action
must be quasi-concave in type and generally exhibits pooling, with intermediate types choosing higher actions than higher and lower types. We provide
an algorithm to systematically construct an equilibrium and use this algorithm
to establish its existence for this general class of preferences with an arbitrary
discrete-type distribution.
Keywords. countersignaling; weak pairwise-matching condition; minimum allocation; low types separate and high types pairwise-pool
JEL Classification. D82; I21
The first author acknowledges financial support from JSPS KAKENHI (20K01560). The second author
acknowledges financial support from JSPS KAKENHI (18H03640, 19H01468, 20H05631, 21H04398), andthe Joint Usage/Research Center for Behavioral Economics at ISER and Osaka University for its International
Joint Research Promotion Program.

1.

Introduction

Despite its widespread use in signaling models, the single-crossing property imposes strong
restrictions on the structure of preferences, and its validity is not necessarily evident ineconomic applications.1 To bridge this gap in the literature, in Chen et al. (2021b), we
introduce a double-crossing property and provide a general analysis of signaling under
this property. That paper identifies some fundamental features of double-crossing preferences, which enables us to obtain a full characterization of equilibria and establish equilibrium existence under such environments, when agent types are distributed continuously.
From the practical point of view, however, discrete-type models are often more useful, oreven indispensable, as many applied settings are naturally cast in discrete types. For thisframework to be of use for applied work, it is important to discern which insights of thecontinuous-type model hold generally and which need amendment when agent types are
discrete.
In this paper, we extend the continuous-type model of Chen et al. (2021b) to an arbitrary number of types. The extension is not as straightforward as it may appear. Specifically, there are two technical issues that confront us. One issue is that in Chen et al.
(2021b), we first establish the continuity of the equilibrium action above some threshold
and then exploit this feature to derive other equilibrium properties. This approach is notapplicable to a discrete-type model that has no corresponding notion of continuity. The
other issue is that with discrete types, agents may randomize over different actions, so
we need to explicitly consider mixed strategies. This substantially enlarges the strategy
space, as it is now a set of probability distributions over actions, whereas the equilibrium
strategy can be represented simply by a (piecewise continuous) function of agent type in
the continuous-type model. These issues prevent us from applying the results of Chen etal. (2021b) directly to a discrete-type model, both for obtaining a characterization and forestablishing equilibrium existence, and force us to explore different avenues.
Central to our analysis are the general characterization and existence results that holdfor any number of types. In Section 3, we provide a characterization of equilibria that satisfy the D1 refinement (hereafter, D1 equilibria): types above some threshold are pairwise
1

Hörner (2008) notes, “Little is known about equilibria when single-crossing fails, as may occur in applications.” There are now several applications which deal with the situation where the single-crossing
property fails to hold (Feltovich et al., 2002; Kolev and Prusa, 2002; Daley and Green, 2014; Bobtcheff andLevy, 2017; Frankel and Kartik, 2019; Chen et al., 2021a; Degan and Li, 2021).

1

matched, and the equilibrium action is quasi-concave in type. Our characterization result
thus confirms that the key insights of Chen et al. (2021b) hold in a qualitative sense, butalso reveals that there are some properties that are specific to the discrete-type model. The
most symbolic difference is captured by what we call the weak pairwise-matching condition,
which plays an essential role in ensuring global incentive compatibility. In the continuoustype model, pairwise matching is characterized by a bijective mapping, where all types
above the threshold pool with some other type. In the discrete-type model, the mapping isoften an injection, and the lower end of types may be left unmatched when types are notdense enough. This result illuminates a fundamental property of signaling under doublecrossing preferences: it is the higher end of types above the threshold who need to bepooled with lower types, but not vice versa. Understanding this property is crucial when
we construct an equilibrium.
In Section 5, we provide an algorithm to construct a D1 equilibrium that works forany double-crossing preferences and any number of types, and show by construction thata D1 equilibrium always exists. In the continuous-type model, equilibrium is essentiallycharacterized by a system of differential equations, and the problem to find an equilibrium
reduces to a standard initial value problem, to which we can apply standard arguments
to establish the existence of solutions. No such techniques can be used when types are
discrete. In the discrete-type model, we must consider the possibility of mixed strategies,
and equilibrium is characterized by a set of probability distributions over actions. The
strategy space thus expands substantially as the number of types increases. Moreover,since the equilibrium conditions (i.e., incentive compatibility and D1) in the discrete-typemodel generally appear as inequality constrains, there is a continuum of possible actions
for each type to be considered, making it complicated to pin down an equilibrium.
A conceptual advancement on this front is what we call the minimum allocation. Our
equilibrium construction centers around this notion. Given our characterization result on
pairwise matching, we choose types in the lower end of the type distribution to matchwith the highest remaining type in each round of our algorithm, and move down until
we run out of types to match. The problem is that in each round, we need to determine
which fractions of types to match with the highest remaining type and which fractions toremain fully separated, so as to satisfy all the equilibrium conditions. The adjustment process could be highly complicated and easily become intractable, as there are a multitude
of possible choices in each round due to inequality constraints. We show that this process can be substantially simplified and guaranteed to always end up with a well-behaved2equilibrium by searching for the minimum allocation repeatedly in each round.
One important economic insight we gain from the class of models with double-crossing
preferences is countersignaling—a phenomenon where higher and lower types are pooled
at a low signaling action while some intermediate types separate by choosing a higher
action (Feltovich et al., 2002; Araujo et al., 2007). While real-life examples of countersignaling abound,2 analyzing this phenomenon in general terms has proved to be difficult andelusive, and our understanding of countersignaling has been limited to specific contexts
despite its potential social implications: for instance, Feltovich et al. (2002)—the seminal
work on countersignaling—consider only three types and restrict attention to pure-strategy
equilibria. Our analysis provides a flexible framework to understand countersignaling under general payoff and distribution functions and can be used to analyze this perverse yetpervasive phenomenon in a variety of applied contexts.

2.

Model

We consider a model with an arbitrary number I ≥ 2 of types. The type space is {1, . . . , I}
where we use i to denote a generic type. The type of an agent is his private information.
In the following analysis, it is often convenient to distinguish between agent n andtype i. We suppose that there is a continuum of agents with unit measure, each indexed
by n ∈ [0, 1]. Agents are partitioned into types i = 1, . . . , I by (F0 , . . . , F I ), where F0 = 0,
F I = 1, and Fi < Fi+1 for i = 0, 1, . . . , I − 1. The partition (F0 , . . . , F I ) summarizes the type
distribution with Fi 0 = P(i ≤ i 0 ). Let ι(n) indicate the type of agent n, where(ι(n) =

i

if n ∈ [Fi−1 , Fi ) for i < I,I

if n ∈ [F I−1 , F I ].

We adopt the above convention because it is useful for representing mixed strategies. Suppose type i randomizes between actions a00 and a0 with probabilities z and 1 − z respectively. This is equivalent to having agent n00 ∈ [Fi−1 , (1 − z)Fi−1 + zFi ) choose a00 and agent
n0 ∈ [(1 − z)Fi−1 + zFi , Fi ) choose a0 .3 Under this convention, we need to pay special attention to agents in the set B := {F0 , . . . , F I−1 }. We refer to B as the set of “threshold
2

Feltovich et al. (2002) raise a number of examples drawn from common observations, such as “Thenouveau riche flaunt their wealth, but the old rich scorn such gauche displays,” and provide experimental
evidence in support of countersignaling. Also see Araujo et al. (2007) and the references therein. Dixit andNalebuff’s (2008) book, The Art of Strategy, has a section devoted to countersignaling.
3
In this example, if i = I, then our convention would have agent n0 = F I also choose action a0 .

3agents.”
Let u(a, t, i) denote the payoff to an agent of type i, where a is the signaling action hechooses and t is the market’s perception of his type, or his “reputation,” i.e., t = E[i | a] ∈[1, I]. Our specification of double-crossing preferences follows Chen et al. (2021b).
Assumption 1. u : R+ × [1, I] × {1, . . . , I} → R is twice continuously differentiable, strictlyincreasing in t and strictly decreasing in a.
Assumption 2. For any i 0 > i 00 , there exists a continuous function D(·; i 0 , i 00 ) : [1, I] → R+such that:(a) if a < a0 ≤ D(t 0 ; i 0 , i 00 ), thenu(a, t, i 00 ) ≤ u(a0 , t 0 , i 00 ) =⇒ u(a, t, i 0 ) < u(a0 , t 0 , i 0 );(b) if a > a0 ≥ D(t 0 ; i 0 , i 00 ), thenu(a, t, i 00 ) ≤ u(a0 , t 0 , i 00 ) =⇒ u(a, t, i 0 ) < u(a0 , t 0 , i 0 ).
Assumption 3. For any t, D(t; i 0 , i 00 ) strictly decreases in i 0 and in i 00 .
Assumption 1 states that signaling is costly and that the agent benefits from a higher
reputation. The “dividing line” D(·; i 0 , i 00 ) specified in Assumption 2 partitions the (a, t)space into two regions for each pair of types. For actions to the left of the dividing line,
the standard single-crossing property holds for types i 0 and i 00 . To the right of the dividing
line, the reverse single-crossing property holds: whenever the lower type i 00 is indifferent
between two allocations, the higher type i 0 strictly prefers the one with the lower action.
We place no restriction on the shape of D(·; i 0 , i 00 ), other than that it is a continuous functionof t.
When there are only two types, Assumptions 1 and 2 provide enough structure to analyze signaling under double-crossing preferences because D(·; 2, 1) is the only dividing
line. When there are more than two types, there are I(I − 1)/2 dividing lines to be considered. The analysis would clearly become unmanageable without further restriction.
Assumption 3 provides the restriction we adopt.
The restrictions imposed by Assumptions 1 to 3 can also be expressed in terms of themarginal rate of substitution between a and t. Letm(a, t, i) := −4ua (a, t, i)u t (a, t, i)represent the marginal rate for type i at (a, t), and let t = φ(a, u0 , i) represent the indifference curve of type i at utility level u0 . The marginal rate of substitution is always
positive under Assumption 1. If type i 00 attains utility level u0 at (a0 , t 0 ), then for i 0 > i 00 ,the difference in their marginal rates along the indifference curve of type i 00 ism(a, φ(a, u0 , i 00 ), i 0 ) − m(a, φ(a, u0 , i 00 ), i 00 ).
Chen et al. (2021b) show that Assumption 2 is equivalent to the requirement that theabove difference is strictly single-crossing from below in a, with crossing point at a =a0 = D(t 0 ; i 0 , i 00 ). Furthermore, if an indifference curve φ(·, u0 , i 00 ) crosses the dividing
line D(·; i 0 , i 00 ) at (a0 , t 0 ), then a < D(φ(a, u0 , i 00 ); i 0 , i 00 ) for all a < a0 , i.e., an indifference
curve can cross a dividing line only once in the (a, t)-space.4
Assumption 3 is related to how the marginal rate behaves with respect to type. Specifically, it requires that for any (a, t),m(a, t, i) − m(a, t, i − 1)is strictly single-crossing from below in i. These restrictions are different from the standard setting with single-crossing preferences, in which a higher type always has a lower
marginal rate of substitution than a lower type at all levels of a and t.
We consider equilibria that satisfy the D1 refinement (Cho and Kreps, 1987). In thestandard setting with single-crossing preferences, this refinement implies that the uniqueequilibrium outcome is given by the least-cost separating solution, also known as the Riley outcome (Riley, 1979). The model described here is identical to that of Chen et al.
(2021b), except that the type space is now discrete. The reader can refer to that paper fora fuller discussion of the modeling assumptions, as well as examples of economic environments in which preferences satisfy these assumptions.

3.

Equilibrium Characterization

Let (a(n), t(n)) denote the allocation of agent n where a(·) and t(·) are generally step
functions. It is without loss of generality to assume that a(·) is weakly monotone withineach type interval. If a(·) is constant on the type interval [Fi−1 , Fi ), type i adopts a pure
Suppose an indifference curve φ(·, u0 , i 00 ) of type i 00 crosses D(·; i 0 , i 00 ) at a1 and a2 . Indifference curvesof the higher type i 0 that cross φ(·; u0 , i 00 ) must be steeper than the latter between a1 and a2 , which implies
that type i 0 strictly prefers the lower action a1 to the higher action a2 . This would violate Assumption 2(a).
45strategy; otherwise, type i randomizes over different actions. Let Q(a) be the set of agents
who choose action a in equilibrium. We say that Q(a) is a pooling set if it contains morethan one type. For the subsequent analysis, it is convenient to define for a given n ∈ [0, 1],
φ ∗ (·; ι(n)) := φ(·, u(a(n), t(n), ι(n)), ι(n)),
which is the indifference curve of type ι(n) that passes through his equilibrium allocation(a(n), t(n)); for brevity, we refer to it as the equilibrium indifference curve of type ι(n).
Chen et al. (2021b) show that equilibrium under double-crossing preferences with acontinuum of types exhibits a particular form of pooling, labeled as Low types Separateand High types Pairwise-Pool (LSHPP). There are two important properties of an LSHPP
equilibrium. First, the equilibrium action is quasi-concave in type. Second, there is a
threshold type above which types are pooled in a pairwise manner, where two distinct
types, or two disjoint intervals of types, choose the same action. While intuition suggeststhat some extended version of these properties would continue to hold for an arbitrary
number of types, the results of Chen et al. (2021b) cannot be applied directly to the present
context because the proof in that paper exploits the continuity of a(·) above the threshold
type—a notion that has no counterpart in the discrete-type model.
In the continuous-type model, incentive compatibility and D1 impose tight restrictions
on the feasible range of equilibrium actions. Specifically, suppose that the type space isgiven by [θ , θ ], where we use θ as the generic notation of the agent type. Then, there
are two threshold types θ0 and θ ∗ and a mapping p : (θ ∗ , θ ] → [θ0 , θ ∗ ) such that for eachtype θ ∈ (θ ∗ , θ ], there is a paired type p(θ ) ∈ [θ0 , θ ∗ ) who chooses the same action. Dueto the denseness of the type space, the mapping is always bijective, and hence Q(a(θ ))is a pooling set for all θ ∈ [θ0 , θ ∗ ). Moreover, the marginal rates of substitution must
be exactly equalized at the end points of each pooling set (except when the pooling set
includes the highest type): if there is any pooling at (a p , t p ), then types min Q(a p ) andmax Q(a p ) must have the same marginal rate of substitution.
Equilibrium characterization is more involved in the discrete-type model because those
nice properties do not hold exactly when there are no arbitrarily close “adjacent types.”
We can still show, however, that a weaker version of pairwise matching still holds.
Definition 1. The weak pairwise-matching condition holds if the following two conditions
are satisfied:(a) There exists n∗ ∈ (0, 1) such that for any action a(n0 ) chosen by agent n0 > n∗ , there
exists n00 < n∗ such that agent n00 chooses the same action a(n0 ).
6

(b) If there is pooling at (a p , t p ), then Q(a p ) = [n1 , n2 ) ∪ [n3 , n4 ) with n2 ≤ n∗ ≤ n3 , wherem(a p , t p , ι(n3 )) ≥ m(a p , t p , ι(n2 − ")),(m(a p , t p , ι(n1 ))if n1 6∈ B,m(a p , t p , ι(n4 − ")) ≤m(a p , t p , max{ι(n1 ) − 1, 1}) if n1 ∈ B,
for an arbitrarily small " > 0.
Part (a) of the above definition requires that every action chosen by a type higher thanι(n ) is also chosen by another type below ι(n∗ ). In other words every type above ι(n∗ )∗is pooled with some type(s) below ι(n∗ ). The flip side of this, however, is not required by
the weak pairwise-matching condition. In particular, suppose the lowest type that pools
with type I is type i0 . Then Definition 1(a) does not rule out the possibility that some type
between i0 and ι(n∗ ) may choose an action that separates from all other types. This isqualitatively different from the continuous-type case where no type above a gap type θ0chooses a fully separating action.
Since each agent type is defined by a left-closed, right-open interval, in Definition 1(b)Q(·) is also defined as the union of left-closed, right-open intervals (except when it includes
agent F I = 1, in which case the set is defined by a closed interval). If Q(a p ) = [n1 , n2 ) ∪[n3 , n4 ) and n2 is a “threshold agent,” then for a small " > 0, type ι(n2 − ") chooses a p but
type ι(n2 ) does not. This is why we write ι(n2 −") and ι(n4 −") in Definition 1(b). Instead ofrequiring equality of marginal rates of substitution, Definition 1(b) leaves some degree of
freedom for the marginal rates of substitution among types that are pooled. The rationale
for the direction of inequalities stated in the definition will become apparent when we
explain below the restrictions on off-equilibrium beliefs imposed by the D1 refinement.
Proposition 1. In any equilibrium, a(·) is weakly quasi-concave and the weak pairwisematching condition holds.
Proof. Quasi-concavity. Suppose to the contrary that min{a(n1 ), a(n3 )} > a(n2 ) for somen1 < n2 < n3 . There are three possibilities: (i) a(n3 ) > a(n1 ) > a(n2 ); (ii) a(n1 ) = a(n3 ) >a(n2 ); and (iii) a(n1 ) > a(n3 ) > a(n2 ).
Case (i). Since agent n1 chooses a higher action than agent n2 , it must be thata(n1 ) > D(t(n1 ); ι(n2 ), ι(n1 )).
7

Moreover, since agent n1 chooses a lower action than agent n3 , we havea(n1 ) < D(t(n1 ); ι(n3 ), ι(n1 )).
These two equations imply that D(t(n1 ); ·, ι(n1 )) is increasing, which is a contradiction.
Case (ii). Let (a p , t p ) represent the pooling action and the associated reputation chosen
by agents n1 and n3 in this case. Let i and i be respectively the lowest and the highest typethat choose a p in equilibrium. Note that m(a p , t p , i) − m(a p , t p , i − 1) is single-crossing
from below in i if and only if m(a p , t p , ι(n)) is quasi-convex in n. Hence either type i ortype i has the highest marginal rate of substitution among all types pooling at action a p .
Because types are discrete, actions slightly below a p are off-path. By D1, a slight downward
deviation from a p is attributed to either type i or type i. If a p > D(t p ; i, i), then the offequilibrium belief associated with downward deviation is i. This cannot be an equilibrium,
because i > t p . So we must have a p ≤ D(t p ; i, i) ≤ D(t p ; ι(n3 ), i). But a(n2 ) < a p implies
a p > D(t p ; ι(n2 ), i). This means that D(t p ; ι(n2 ), i) < a p ≤ D(t p ; ι(n3 ), i), which contradicts
the monotonicity of D(t p ; ·, i).
Case (iii). Because signaling is costly, a(n1 ) > a(n3 ) implies t(n1 ) > t(n3 ). Sincen1 < n3 , either Q(a(n1 )) or Q(a(n3 )) (or both) must be a pooling set. Furthermore, if we
let n0 = sup Q(a(n1 )) and n00 = inf Q(a(n3 )), we must have n0 > n00 . If n0 > n2 , then foragents n1 < n2 < n0 , we have a(n0 ) = a(n1 ) > a(n2 ). This reduces to case (ii) above. If
n0 ≤ n2 , then for agents n00 < n2 < n3 , we have a(n00 ) = a(n3 ) > a(n2 ). Again this reduces
to case (ii).
Weak pairwise-matching condition. Quasi-concavity of a(·) implies that any pooling set
must consist of at most two intervals, i.e., there exists n∗ such that for any pooling actiona p , Q(a p ) = [n1 , n2 ) ∪ [n3 , n4 ) with n2 ≤ n∗ ≤ n3 .
To show that every type above ι(n∗ ) pools with a type below ι(n∗ ), suppose the opposite
is true. Specifically let n0 be the lowest agent in (n∗ , F I ] who chooses an action a0 which
is not chosen by agents in [F0 , n∗ ]. The corresponding reputation satisfies t(n0 ) ≥ n0 . By
quasi-concavity of a(·), Q(a(n∗ )) must be either a singleton or an interval. Therefore,
we have sup Q(a(n∗ )) < n0 , and so t(n∗ ) ≤ t(n0 ). On the other hand, quasi-concavityof a(·) implies a(n0 ) < a(n∗ ). Thus, every agent would strictly prefer (a(n0 ), t(n0 )) to(a(n∗ ), t(n∗ )), a contradiction.
Let the reputation corresponding to pooling action a p be t p . Recall that m(a p , t p , ι(n))
is quasi-convex in n, and hence the type in the pooling set Q(a p ) with the highest marginal
8

rate of substitution is either ι(n1 ) or ι(n4 − ε) (for some small ε > 0). When agent n1 is
not a “threshold agent” (i.e., when n1 6∈ B), if m(a p , t p , ι(n4 − ε)) > m(a p , t p , ι(n1 )), thena downward deviation from a p to an off-equilibrium action a0 < a p would be attributed totype ι(n4 − ε) under D1, leading to a profitable deviation. When n1 is a “threshold agent,”
the same conclusion holds unless type ι(n1 ) − 1 has even greater incentive to deviate toa0 . Only if type ι(n1 ) − 1 is indifferent between his own allocation and (a p , t p ), and ifm(a p , t p , ι(n4 − ε)) ≤ m(a p , t p , ι(n1 ) − 1), would the off-equilibrium belief be assigned totype ι(n1 ) − 1 rather than type ι(n4 − ε), preventing such a deviation.
Finally, we show m(a p , t p , ι(n3 )) ≥ m(a p , t p , ι(n2 −ε)). Note that quasi-concavity of a(·)
implies a(n0 ) > a p for n0 ∈ [n2 , n3 ). Costly signaling in turn implies that t(n0 ) > t p . On
one hand, the higher type ι(n0 ) prefers the higher action a(n0 ) to the lower action a p while
the lower type ι(n2 − ε) has the opposite preference. Thus the standard single-crossing
property holds between these two types. On the other hand, the higher type ι(n3 ) prefers
the lower action a p to a(n0 ) while the lower type ι(n0 ) has the opposite preference. Thus
the reverse single-crossing property holds between n0 and n3 . These two observations
imply thatm(a p , t p , ι(n0 )) < min m(a p , t p , ι(n2 − ε)), m(a p , t p , ι(n3 ))Because m(a p , t p , ι(n)) is quasi-convex in n, this in turn implies that the type with the lowest marginal rate of substitution in the pooling set Q(a p ) is either ι(n2 −ε) or ι(n3 ). If, contrary to the weak pairwise-matching condition, we have m(a p , t p , ι(n3 )) < m(a p , t p , ι(n2 −ε)), then an upward deviation from a p would be attributed to type ι(n3 ) under D1. To
prevent off-equilibrium deviations, it must be that t p ≥ n3 . But this would lead to a contradiction, because t(n0 ) > t p ≥ n3 while Q(a(n0 )) consists of types weakly lower than
ι(n3 ).
Proposition 2. In any equilibrium, the following properties hold:(a) Types i ≥ ι(n∗ ) do not randomize over different allocations;(b) If type i < ι(n∗ ) randomizes over a set of allocations, only the lowest allocation in theset can be separating.
Proof. Part (a). Suppose there is some type i 0 > ι(n∗ ) who randomizes over two different
allocations (a1 , t 1 ) and (a2 , t 2 ), where a1 < a2 and t 1 < t 2 . Let i 00 be the largest typebelow ι(n∗ ) who pools at (a1 , t 1 ). Then, by the weak pairwise-matching condition, we
have m(a1 , t 1 , i 00 ) ≤ m(a1 , t 1 , i 0 ), which in turn implies that φ ∗ (a; i 00 ) < φ ∗ (a; i 0 ) for all
9

a > a1 . This is a contradiction because type i 00 must strictly prefer (a2 , t 2 ) to (a1 , t 1 ). The
possibility that type ι(n∗ ) randomizes will be ruled out by part (b); we will come back tothat point later.
Part (b). Suppose some type i 0 < ι(n∗ ) randomizes over (a1 , t 1 ) and (a2 , t 2 ), witha1 < a2 and t 1 < t 2 , where (a2 , t 2 ) is separating. Let Q(a1 ) = [n1 , n2 ) ∪ [n3 , n4 ). Recall
that the type with the lowest marginal rate of substitution in the pooling set Q(a1 ) is either
ι(n2 − ε) or ι(n3 ). Therefore, under D1, a deviation to a0 slightly above a1 (but below a2 )would be given an off-equilibrium belief t 0 ≥ ι(n2 −ε) ≥ i 0 = t 2 . Thus type i 0 would strictlyprefer (a0 , t 0 ) to (a2 , t 2 ).
Finally, we can use this argument to show that type ι(n∗ ) cannot randomize either.
Suppose to the contrary that type ι(n∗ ) randomizes over (a1 , t 1 ) and (a2 , t 2 ) where a1 < a2
and t 1 < t 2 . Note that we only need to consider the case where (a2 , t 2 ) is separating.
(If Q(a2 ) is a pooling set, all type ι(n∗ ) + 1 agents must choose (a2 , t 2 ), in which case we
can just redefine n∗ to be in [Fι(n∗ ) , Fι(n∗ )+1 ).) This means that there must be some agent
n0 ∈ [Fι(n∗ )−1 , n∗ ) who pools with a higher type at (a1 , t 1 ). We can then apply the argument
in part (b) to derive a contradiction.
The equilibrium requirements described in Propositions 1 and 2 are illustrated in Figure
1. Agent n0 in this figure is the lowest agent pooling with type I = 15. The signaling
function a(·) below n0 is determined by the least-cost separating solution. We pick anarbitrary agent choosing the highest action and label this agent n∗ . Each type higher thanι(n∗ ) (i.e., types 11 to 15) adopt a pure strategy, and each type pools with some typebelow ι(n∗ ). Note that some types between ι(n0 ) and ι(n∗ ) (specifically, types 6 and 7)
may choose separating actions, and when type 7 randomize between a separating action
and a pooling action, the separating action is lower. The signaling function in Figure 1 isquasi-concave.

4.

Equilibrium Construction with a Small Number of Types

In contrast to the extant literature on countersignaling, the general model in this paper
allows an arbitrary number of discrete types. We will provide in Section 5 an algorithm
to construct an equilibrium for the general case. Because this algorithm is unavoidably
complex in order to accommodate all possible double-crossing preferences and all type
distributions, in this section we first illustrate the main ideas and difficulties of our equilibrium construction using very simple type distributions.
10Figure 1. The signaling function is quasi-concave and satisfies the weak pairwise-matching condition.

Consider the simplest case with only two types, in which case there is only one dividing
line D(·; 2, 1). Let s∗ (i) denote the least-cost separating solution, where type 1 is indifferent
between (s∗ (1), 1) and (s∗ (2), 2), with s∗ (1) = 0. When s∗ (2) ≤ D(2; 2, 1), the equilibrium
indifference curve of type 1 stays strictly to the left of the dividing line for a ≤ s∗ (2). Because the single-crossing property prevails in the relevant region, the least-cost separating
solution is an equilibrium. Also, by standard argument, no other equilibrium can satisfy
D1 (Cho and Kreps, 1987).
When s∗ (2) > D(2; 2, 1), no separating equilibrium exists because type 2 has a higher
marginal rate of substitution at (s∗ (2), 2), giving him an incentive to deviate to a lower
action. In an equilibrium that involves some pooling, the pooling allocation must be onD(·; 2, 1), for otherwise the higher type would have an incentive to deviate either to aslightly higher action or to a slightly lower action.
Let (â, t̂) be the intersection of the dividing line D(·; 2, 1) and the indifference curve oftype 1 passing through (0, 1). If t̂ > E[i], the only possible equilibrium is a semi-pooling11equilibrium in which type 1 randomizes between (0, 1) and (â, t̂) and type 2 chooses (â, t̂).
Observe that the equilibrium indifference curve of type 2 is flatter than that of type 1 tothe left of the dividing line D(·; 2, 1), and is steeper than that of type 1 to the right ofthe dividing line. Hence any deviation from that allocation which weakly benefits type 2
would strictly benefit type 1. Under D1, such a deviation would be attributed to type 1,
which makes the deviation unprofitable. If t̂ ≤ E[i], both types strictly prefer to choose(â, t̂), and the only equilibrium is a fully pooling equilibrium at a p = D(E[i]; 2, 1) andt p = E[i].
Proposition 3. When there are two types, there exists a unique D1 equilibrium. Moreover,
if such an equilibrium is not fully separating, the pooling allocation must lie on the dividing
line D(·; 2, 1).
This proposition is established in the preceding discussion. The uniqueness of D1 equilibrium in specific instances of double-crossing preferences has been pointed out in Daleyand Green (2014) and Chen et al. (2021a).
Next consider a model with three types. Although it is possible to enumerate all thepossible equilibrium configurations, such an exercise would be rather tedious. Instead wewill explain why equilibrium construction may be difficult even in this very simple caseand how our characterization results help narrowing down the set of possible equilibrium
configurations. Suppose we are interested in finding an equilibrium that exhibits countersignaling with two actions (i.e., the signaling function a(·) is nonmonotone and takes
two values). Even in this particular class of equilibria, there are still many possible configurations: some type 1 or type 3 agents (or both) may pool with type 2 agents at the highaction; or some type 2 agents may pool with type 1 and type 3 agents at the low action.
Our characterization result suggests, however, that many of these configurations are inconsistent with the equilibrium conditions and can hence be ruled out at the outset. Moreprecisely, Proposition 2(a) states that neither type 2 nor type 3 can randomize, meaningthat all type 2 agents must choose the high action while all type 3 agents must choose
the low action in any countersignaling equilibrium with three types and two actions. This
leaves us with only two possible forms of countersignaling equilibrium, depending only
on whether type 1 randomizes between the two actions or not. Moreover, Proposition
2(a) also implies that the pooling action chosen by type 3 must be the second highest in
any countersignaling equilibrium with three types,5 which further narrows down the set
5

If the action chosen by type 3 is the highest, we cannot have countersignaling because the equilibrium12

of possible equilibrium configurations.
When there are four or more types, the situation becomes much more complicated andincreasingly intractable, even with the help of our characterization. For instance, withfour types, even if we just consider pure-strategy countersignaling equilibria, there are
five possible patterns of countersignaling.6 Added to the complication is that Assumption
3 does not impose any restriction on the relative location of the dividing lines D(·; 4, 1)
and D(·; 3, 2). Clearly a more systematic approach to finding an equilibrium is called forwhenever the model has many types.

5.

Equilibrium Existence

Under single-crossing preferences, it is well known that the least-cost separating equilibrium satisfies the D1 refinement. Because of this, finding a D1 equilibrium in this environment is conceptually straightforward and equilibrium existence is never an issue, evenwhen the number of types is very large: each separating action can be pinned down by
the corresponding local incentive compatibility constraint alone, and an equilibrium canbe constructed from bottom up. This is not the case under double-crossing preferences,where equilibrium may entail some pooling and the equilibrium conditions (i.e., incentive
compatibility and D1) impose joint restrictions on payoff and type distribution functions.
As discussed in the previous section, finding an equilibrium under double-crossing preferences by brute force can be extremely tedious, especially when there are many types.
Moreover, there is no easy way to tell whether a D1 equilibrium exists for any given preferences and type distribution.
In this section, to overcome these issues, we provide a systematic way to find a D1
equilibrium under double-crossing preferences. The algorithm developed here works forany double-crossing preferences and type distribution, and can be used to establish theexistence of a D1 equilibrium by construction.
action must be quasi-concave. Suppose there are two actions above the action chosen by type 3. Then, foreach of these actions, there must be a type adopting a pure strategy of choosing that action by Proposition
2(a). This implies that type 1 must adopt a pure strategy and choose a higher action than type 3, which
necessarily violates the weak pairwise-matching condition.
6
We can have types 1 and 4 pool while types 2 and 3 pool at a higher action; types 1 and 4 pool while
types 2 and 3 separate at two higher actions; types 1 and 2 pool with type 4 while type 3 separates; types
1 pools with types 3 and 4 while type 2 separates; or types 2 and 4 pool while type 1 separates at a lower
action and type 3 separates at a higher action.

13

5.1.

An overview of the algorithm for equilibrium construction

Because the signaling function is quasi-concave, our construction finds the actions chosen
by agents near the two ends of the agent distribution first. Then, in successive rounds,
we find the actions chosen by agents nearer the middle part of the agent distribution until
the highest equilibrium action is pinned down. One of the agents choosing that highest
action corresponds to the equilibrium n∗ . Each round of this construction is designed torespect local incentive compatibility (each agent has no incentive to deviate to adjacent
allocations) and the weak pairwise-matching condition. We show later that these two
restrictions together are sufficient to guarantee global incentive compatibility.
We also make sure that Bayes’ rule for belief consistency is satisfied at any equilibrium
pooling action. Suppose Q(a p ) = [n1 , n2 ) ∪ [n3 , n4 ) for some a p . Bayes’ rule requires thatfor all n ∈ Q(a p ),
R n2

R n4

1

n3

t(n) =

ι(n) dn +nι(n) dn(n2 − n1 ) + (n4 − n3 ).

It is particularly convenient to define
R n0µ(n00 , n0 ; i) :=n00

ι(n) dn +

R Fi
Fi−1

ι(n) dn(n0 − n00 ) + (Fi − Fi−1 ),for n00 ≤ n0 ≤ Fi−1 . This formula gives the expected type when agents from n00 to n0 poolwith all type i agents. When agents in [p, q) pool with all agents of type j, Bayes’ rule canbe written as t(n) = µ(p, q; j) for n ∈ [p, q). The following properties of µ(·) will be useful:(a) µ(n00 , n0 ; i) is continuously increasing in n00 and equals i at n00 = n0 ; and (b) µ(n00 , n0 ; i)decreases in n0 when µ(n00 , n0 ; i) > ι(n0 ) and increases in n0 when µ(n00 , n0 ; i) < ι(n0 ).
Our algorithm for equilibrium construction exploits a key property established in Propositions 1 and 2—namely, each type i ≥ ι(n∗ ) adopts a pure strategy and pools with someagents below n∗ . We therefore propose an algorithm with multiple rounds. In the firstround, we find a set of agents, say [p1 , q1 ), who pool with type I at some candidate allocation (a1 , t 1 ). (If p1 > 0, we also determine the tentative allocations (a(n), t(n)) forn ∈ [0, p1 ) based on that candidate allocation). In round 2, the allocations to agentsin [q1 , F I−1 ) remains to be determined. Among these remaining agents, we find a set of
agents, [p2 , q2 ), who pool with type I − 1 at a weakly higher tentative allocation (a2 , t 2 )(along with the allocations chosen by n ∈ [q1 , p2 ) if p2 > q1 ). In round 3, the allocations
14

to agents in [q2 , F I−2 ) remains to be determined, and so on. The algorithm finds an equilibrium when by the end of some round, the allocations to all agents in [0, 1] have been
determined. It is possible that we cannot find a tentative allocation at some round k before
the algorithm stops with a full solution. In that case, the algorithm specifies how the tentative allocation at some round k0 < k should be adjusted and the algorithm proceeds toround k0 + 1 again with the adjusted tentative allocation for round k0 as the starting point.
The proof of equilibrium existence essentially boils down to showing that this algorithm
will always end with a full solution for the allocations of all agents in [0, 1].
To introduce the notation for this algorithm, for k ≥ 1, define j := I + 1 − k to be
the highest type among all agents whose allocation remains to be determined in roundk. The tentative solution in round k is represented by a 4-tuple, (ak , t k , pk , qk ), with theinterpretation that agents in [pk , qk ) pool with all type j agents at allocation (ak , t k ). Let
sk := (ak−1 , t k−1 , nk ) represent the state in round k, which is inherited from the tentative
solution in round k−1: (ak−1 , t k−1 ) is the allocation chosen in the previous round, and nk =qk−1 is the lowest agent whose allocation is yet to be determined. At the beginning of thealgorithm, we initialize the state to s1 = (0, 1, 0) where the allocation (0, 1) corresponds
to the least-cost separating solution for type 1.
As we will detail below, the pair (t k , pk ) provides enough information for finding anequilibrium, while ak and qk can be uniquely pinned down from (t k , pk ). Instead of working
with the 4-tuple (ak , t k , pk , qk ), we thus denote the tentative allocation in round k simply
by ck := (t k , pk ) ∈ [t k−1 , I]×[qk−1 , F j−1 ). Let (c1 , . . . , ck0 ) be the allocation path up to roundk0 .
Among all allocations ck in round k that will satisfy incentive compatibility and theweak pairwise-matching condition, the algorithm only considers a special subset of these
allocations, which we call the candidate set and denote by Ck . The candidate set depends
on the state sk = (ak−1 , t k−1 , nk ), but since ak−1 and nk = qk−1 can be derived from ck−1 wesometimes write Ck (ck−1 ) to emphasize this dependence. When the candidate set is welldefined, it can be a singleton or it can contain more than one element. If Ck contains morethan one element, we argue below that there is a linear order k defined on Ck such thatany two elements in this set can be compared, despite the fact that a typical element of Ck
is two dimensional. We use ck and ck to denote the highest and lowest element of Ck .
We are now in a position to provide a high-level description of our main algorithm forequilibrium construction:

15

Main algorithm. Each round k ≥ 1 inherits the allocation path (c1 , . . . , ck−1 ) from earlier
iterations of the algorithm. Given ck−1 = (t k−1 , pk−1 ), apply Bayes’ rule to find the qk−1
which is the smallest solution to µ(pk−1 , qk−1 ; j + 1) = t k−1 .
1. If qk−1 = F j :• stop with a well-defined equilibrium characterized by the existing allocation
path (c1 , . . . , ck−1 )2. If the equation µ(pk−1 , qk−1 ; j + 1) = t k−1 does not admit a solution for qk−1 on[pk−1 , F j ]:• adopt the adjustment procedure to modify the allocation path to (c01 , . . . , c0k−1 )• return to the beginning of round k
3. Otherwise:• update the state to sk = (ak−1 , t k−1 , nk ) with nk = qk−1
• compute the candidate set Ck (ck−1 );• if the minimum allocation cminexists in Ck (ck−1 ), pick ck = cmin
; otherwise pickkkck = ck ∈ Ck (ck−1 )• append ck to the allocation path (c1 , . . . , ck−1 ) and go to the beginning of round
k+1
The remainder of this section will specify precisely how the candidate set Ck is deter(as well as the highest allocation
mined (Section 5.2), define the minimum allocation cminkck ) and explain its role in equilibrium construction (Section 5.3), and elaborate on theadjustment procedure that produces a modified allocation path from the original path
(Section 5.4). Finally, we will show that the main algorithm will always stop at some finite round k and produce a well-defined allocation for all agents. Since the solution so
produced satisfies Bayes’ rule, local incentive compatibility, weak pairwise-matching, andis quasi-concave by construction, equilibrium existence can be guaranteed by showing that
local incentive compatibility also implies global incentive compatibility (Section 5.5).

16

5.2.

The candidate set

Since agents in [pk , qk ) pool with type j to produce reputation t k , we define the following
mapping from ck = (t k , pk ) to qk to ensure that Bayes’ rule is satisfied:πk (ck ) := min q ∈ [pk , F j−1 ] : µ(pk , q; j) = t k .
Because µ(pk , ·; j) is decreasing then increasing, there can be multiple values of q thatsatisfy the specified condition, and in that case we pick the smallest solution. It is possiblethat the specified condition admits no solution, in which case πk (ck ) is undefined.
The candidate set Ck depends on the state sk = (ak−1 , t k−1 , nk ), where nk = πk−1 (ck−1 ).
This set is undefined whenever πk−1 (ck−1 ) is undefined. In this subsection, we assume
that Ck is well defined. The determination of the candidate set depends on whether nk is a“threshold agent” (i.e., nk ∈ B) or not (i.e., nk 6∈ B). We deal with these two cases in turn.
Suppose first that nk ∈/ B. This means that type ι(nk ) must be randomizing between
ak−1 (determined in previous iterations of the algorithm) and a higher action ak (to be
determined). But part (b) of Proposition 2 requires that type ι(nk ) agents with n > nk
cannot take a fully separating action. This implies that we must choose pk = nk for ck .
Since type ι(nk ) agents randomize, any tentative allocation (ak , t k ) must be on the indifference curve of type ι(nk ) that passes through (ak−1 , t k−1 ). Also, since they pool with typej agents, we require the tentative allocation to be on D(·; j, ι(nk )) so that it satisfies the
weak pairwise-matching condition. Define (â( j, i; ãk , t̃ k ), t̂( j, i; ãk , t̃ k )), or (âk ( j, i), t̂ k ( j, i))for short, to be the intersection of the relevant indifference curve and dividing line whenthe “reservation allocation” is (ãk , t̃ k );7 i.e., it is the (ak , t k ) that satisfies:u(ak , t k , i) = u(ãk , t̃ k , i),ak = D(t k ; j, i).
If pk = nk , the reservation allocation is simply the allocation chosen in the previous round,i.e., (ãk , t̃ k ) = (ak−1 , t k−1 ). Then, we let(
ck =t̂ k ( j, ι(nk )) , nk(t k−1 , nk )if t̂ k ( j, ι(nk )) > t k−1 ,if t̂ k ( j, ι(nk )) ≤ t k−1 .

The candidate set Ck is a singleton containing ck when nk 6∈ B.
7

As we will see below, the reservation allocation (ãk , t̃ k ) is determined by ck−1 and pk .

17

Note that the action ak can be determined once ck is pinned down, and we denote thisrelationship by ak = αk (ck ), where(
αk (ck ) =âk ( j, ι(nk )) if t̂ k ( j, ι(nk )) > t k−1 ,if t̂ k ( j, ι(nk )) ≤ t k−1 .

ak−1

The case where αk (ck ) = ak−1 corresponds to “mass pooling” of the continuous-type caseof Chen et al. (2021b), where more than two types pool at the same allocation.
Next suppose that nk ∈ B. This means that type ι(nk ) − 1 chooses action ak−1 , while
types ι(nk ) and above may potentially choose separating actions. In this case, we first construct a least-cost separating solution given the initial condition.8 We denote this solution
by sk∗ (i). There are two possibilities.
Case (i). If sk∗ ( j) ≤ D( j; j, j−1), then there is a separating equilibrium for types between
ι(nk ) and j because the standard single-crossing property holds in the relevant region. In
this case, the separating solution for these types, together with the allocation path derived
from previous iterations of the algorithm, will constitute an equilibrium. Formally, we
specify ck = ( j, F j−1 ) to be the only element of our candidate set Ck , together with αk (ck ) =sk∗ ( j). With pk = F j−1 , the solution to µ(pk , qk ; j) = j is qk = F j−1 , and so the main algorithm
will stop with a well-defined equilibrium.
Case (ii). Otherwise, we find ik∗ := max{i : sk∗ (i) < D(i; j, i)}; this is the largest type thatcan choose a separating action.9 If sk∗ (ι(nk )) ≤ D(ι(nk ); j, ι(nk )) and ik∗ is not well defined,
we adopt the convention to denote ik∗ = ι(nk ) − 1. Observe that when ik∗ = ι(nk ) − 1, typeι(nk ) agents cannot take a separating action, and the only feasible choice of pk is nk . Ifik∗ ≥ ι(nk ), we may pick any pk ∈ [nk , Fik∗ ]. In either case, once we pick pk , we can identify

the feasible range of t k . If pk ∈/ B, the relevant indifference curve of type ι(pk ) is the onethat passes through his reservation allocation (sk∗ (ι(pk )), ι(pk )), and the relevant dividing
line is D(·; j, ι(pk )). We can uniquely pin down the intersection (âk ( j, ι(pk )), t̂ k ( j, ι(pk ))and set t k = t̂ k ( j, ι(pk )). If pk ∈ B and ι(pk ) > 1, any candidate allocation must bebounded between the indifference curves of types ι(pk ) − 1 and ι(pk ) that pass throughIn round 1, the initial condition requires s1∗ (1) = 0; in all subsequent rounds, type ι(nk ) − 1 must be
indifferent between (sk∗ (ι(nk )), ι(nk )) and (ak−1 , t k−1 ).
9To see this, note that if type ιk∗ +1 chooses a separating action, it must be to the right of D(ik∗ +1; j, ik∗ +1)
8

by definition. As type ik∗ + 1 has a lower marginal rate of substitution than type j, it is not possible to find apooling allocation that satisfies the weak pairwise-matching condition.

18

the reservation allocation given by((ãk , t̃ k ) =sk∗ (ι(pk ) − 1), ι(pk ) − 1

if pk > nk ,(ak−1 , t k−1 )if pk = nk .

(1)

Moreover, the weak pairwise-matching condition requires that, for pk ∈ B such that ι(pk ) >1, any candidate allocation (ak , t k ) must satisfy:
D(t k ; j, ι(pk ) − 1) ≥ ak ≥ D(t k ; j, ι(pk )).
Therefore, the feasible range of t k is [max{ t̂ k ( j, ι(pk )), t k−1 }, t̂ k ( j, ι(pk ) − 1)]. Finally, if
pk ∈ B and ι(pk ) = 1 (i.e., pk = 0), we have a special case because there are no lower
types to separate from and hence no payoff upper bound. The feasible range of t k in thiscase is unbounded and is given by [max{ t̂ k ( j, 1), 1}, ∞). This fact will play a crucial rolein our algorithm.
To sum up, in case (ii), the candidate set Ck is the set of (t k , pk ) such that(pk ∈ [nk , Fik∗ ]

and

tk

= t̂ k ( j, ι(pk ))∈ max t̂ k ( j, ι(pk )), t̃ k , t̂ k ( j, ι(pk ) − 1)

if pk 6∈ B,
if pk ∈ B,

where t̂( j, 0) = ∞.10 Even though the candidate set is more complicated in this case because Ck is not a singleton, three properties of this set are important. First, when there
is a range of feasible choices for pk , t k is uniquely pinned down and fixed (type ι(pk )is choosing the same (ak , t k ) with different probabilities); and when there is a range offeasible choices for t k , pk is uniquely pinned down and fixed (type ι(pk ) is choosing different allocations (ak , t k ) that are all consistent with incentive compatibility and the weak
pairwise-matching condition). Second, Ck is connected in that if (t k0 , pk ), (t k00 , pk ) ∈ Ck witht 0 > t 00 , then (t k , pk ) ∈ Ck for any pk and t k ∈ (t k00 , t k0 ); and if (t k , pk0 ), (t k , pk00 ) ∈ Ck withp0 > p00 , then (t k , pk ) ∈ Ck for any t k and pk ∈ (pk00 , pk0 ). Third, if both (t k0 , pk0 ) and (t k00 , pk00 )belong to Ck , then t k00 ≥ t k0 if and only if pk00 ≤ pk0 . These properties of Ck are illustrated in
Figure 2. They are important because they allow us to order allocations in the candidate
set continuously, as we will discuss below.
For any ck ∈ Ck , we can also determine the corresponding value of ak , denoted αk (ck ). However, since
the precise definition of αk (ck ) is cumbersome in case (ii), and is not germane to the discussion of the mainalgorithm, we leave the details to the Appendix.
10

19

Figure 2. The candidate set Ck contains pairs (t k , pk ) that lie on the blue line. The arrows indicate
the linear order on this set: the point at the southeast end of Ck is ck and the point at the northwest
end of ck .

5.3.

The minimum allocation

If the candidate set Ck is not a singleton, there are more than one way to pick a tentative
allocation in round k that would satisfy incentive compatibility and the weak pairwisematching condition. When this allocation is carried to the next round, and when Ck+1
is also not a singleton, the multiplicity of tentative allocation paths expands, making thesearch for an equilibrium difficult. Our main algorithm takes advantage of the fact that elements of the candidate set can be linearly ordered, even though they are two-dimensional.
In this subsection we formally define this order relation and introduce a way to systematically pick a particular tentative allocation from a candidate set.
Recall that µ(pk , qk ; j) is decreasing in qk when it is larger than ι(qk ) and is increasingin qk when it is smaller than ι(qk ). Let µ∗k (pk ) := minq∈[pk ,F j−1 ] µ(pk , q; j) represent thelowest possible reputation when type j pools with an interval of agents starting from pk .
Because µ(pk , ·; j) is continuous and strictly increasing, so is µ∗k (·). Defineτk (ck ) := t k − µ∗k (pk ).
This function is continuous and strictly increasing in t k and strictly decreasing in pk . We20

say that ck is “higher than” c0k , and write ck  c0k , if and only if τk (ck ) ≥ τk (c0k ) (and weuse  to denote the corresponding strict ordering). Given the properties of Ck , allocationsin this set can be linearly ordered according to the relation . Figure 2 illustrates how
allocations in Ck are ordered. The allocation with the highest value of t k and lowest valueof pk is the highest element of Ck and is denoted ck . The allocation with the lowest valueof t k and highest value of pk is the lowest element of Ck and is denoted ck . Of course,when Ck is a singleton the two coincide.
We say that an allocation ck is a minimum allocation if τk (ck ) = 0, and denote it bycmin= (t kmin , pkmin ).
kThis is the allocation which admits a solution in qk to the equationµ(pk , qk ; j) = t k for the first time as we gradually increase ck (according to the order )
in Ck . In other words, πk (ck ) is undefined whenever cmin
 ck . It is clear that there existska unique cminin Ck if and only if τk (ck ) ≥ 0 ≥ τk (ck ). This follows from the fact that Ck iskconnected, and τk (·) is continuous and strictly increasing in ck .
A minimum allocation path is an allocation path (c1 , . . . , ck0 ) in which ck0 = cmin
, i.e.,k0
an allocation path in which the minimum allocation is chosen in the latest round. The
following statement establishes some convenient properties of a minimum allocation path.
, then), then t kmin ≤ ι(qk ). (c) If ck = cmin
) ∈ B. (b) If qk = πk (cminLemma 1. (a) πk (cminkkk
0 > τk+1 (ck+1 ). (d) cmin
∈ C1 .
1
Proof. (a) Because µ(pkmin , q; j) is decreasing in q when it is larger than ι(q) and it reaches
a minimum at q = π(cmin), we must have ι(q) < t kmin for q ∈ [pkmin , πk (cmin)). Similarly,kkµ(pkmin , q; j) is increasing in q when it is smaller than ι(q); therefore, ι(q) ≥ t kmin for q ∈(πk (cmin), F j−1 ]. This shows that ι(·) must jump up at q = πk (cmin), and so πk (cmin) mustkkk
be a “threshold agent.” Also, if µ(pkmin , ·; j) is monotonically decreasing, then πk (cmin)=
k
F j−1 ∈ B.
(b) If qk = πk (cmin) ∈ B, then µ(pkmin , ·; j) must be weakly increasing on (πk (cmin), Fι(qk ) ].
kkThis means t kmin ≤ ι(qk ). This property also holds when µ(pkmin , ·; j) is monotonically decreasing, because qk = F j−1 and so t kmin < j = ι(qk ).
(c) Since nk+1 = qk and cminis a minimum allocation, by parts (a) and (b), we haveknk+1 ∈ B and t k ≤ ι(nk+1 ). Moreover, because nk+1 ∈ B, the lowest allocation in thecandidate set Ck+1 (cmin) satisfies:
k


(

∗

∗
t̂ k j − 1, ik+1
+ 1 − µ∗k+1 Fik+1
τk+1 ck+1 =t k − µ∗k+1 Fι(nk+1 )−1
21∗
if ik+1≥ ι(nk+1 ),if ik∗ = ι(nk+1 ) − 1.

∗∗∗∗ ), we have τ
Since t̂ k ( j − 1, ik+1
+ 1) ≤ ik+1
+ 1 < µ∗ (Fik+1
k+1 (ck+1 ) < 0 if ik+1 ≥ ι(nk+1 ). If∗
ik+1= ι(nk+1 ) − 1, t k ≤ ι(nk+1 ) < µ∗k+1 (Fι(nk+1 )−1 ) implies τk+1 (ck+1 ) < 0.

(d) The candidate set C1 is special because once p1 reaches 0, we do not require agent
n = 0 to be indifferent between (a1 , t 1 ) and the reference allocation given by the state(a0 , t 0 ) = (0, 1) (type 1 may strictly prefer the former allocation to the latter). In otherwords, C1 is unbounded because the initial state only specifies a payoff lower bound fortype ι(0) = 1. Once p1 reaches 0, therefore, the reputation t 1 can be raised without bounds
along D(·; I, 1), and we will eventually have τ1 (t 1 , 0) > 0 for a sufficiently large t 1 .
According to our main algorithm, an allocation path (c1 , . . . , ck0 ) constitutes an equilibrium if πk0 (ck0 ) = F j 0 −1 for some k0 and j 0 = I + 1 − k0 . Parts (a) and (b) of Lemma 1
suggest that if we can find a minimum allocation in a round with two or three remaining
types (i.e., nk ∈ [F j−3 , F j−1 )), the resulting allocation path necessarily constitutes an equilibrium. To see this, consider some round k0 such that nk0 ∈ [F j 0 −3 , F j 0 −1 ) and we find aminimum allocation cmin
. We then have either (i) πk0 (cmin) = F j 0 −1 ; or (ii) πk0 (cmin) = F j 0 −2
k0
k0
k0
and t kmin
≤ ι(F j 0 −2 ) = j 0 − 1. In case (i), the allocation path (c1 , . . . , cmin
) is an equilibrium.
0
k0
In case (ii), we let all type j 0 − 1 agents separate at the top if t kmin
< j 0 − 1, and pool at0= j 0 − 1.11 Since there are only a finite number of types,
if t kmin
the same allocation cmin0
k0
this means that we can find an equilibrium, as long as we can consistently find a minimum
allocation in the current round by adjusting the allocation path.
Parts (c) and (d) of Lemma 1 imply that we can always start with the minimum allocation in round 1 of the main algorithm. Moreover, in the next round, we have n2 ∈ B,
which allows us to obtain c2 and c2 . Since τ2 (c2 ) < 0 by Lemma 1(c), we just need tocheck τ2 (c2 ). If τ2 (c2 ) ≥ 0, the minimum allocation cminexists in C2 (cmin). We can then2
1
continue with the minimum allocation path and proceed to round 3 with n3 ∈ B. If we cankeep on finding the minimum allocation in every round, the algorithm will eventually findan equilibrium at some point. If we fail to find the minimum allocation in some round,the candidate set for the next round is undefined, and we will have to go back to previous
rounds and adopt an adjustment procedure to modify the allocation path.
0min
If t kmin= j 0 − 1, then µ(pkmin
for q ∈ [F j 0 −2 , F j 0 −1 ]. Therefore, we can extend pooling all the0
0 , q; j ) = t k 0
way to agent F j .
11

22

5.4.

The adjustment procedure

Starting with the minimum allocation cmin, the main algorithm keeps appending the mini1
mum allocation in the next round to the allocation path. If at some round k0 the algorithm
fails to find a minimum allocation, Lemma 1(c) implies that this occurs when τk0 (ck0 ) < 0.
Because even the highest allocation is “too low” to satisfy the belief consistency requirement, our adjustment procedure will try to pick a “higher” allocation (according to theorder ) than the existing one. However, since ck0 is already the highest allocation in Ck0 ,we need to go back to previous rounds to make the adjustment. The basic rule of thumbis that we always increase the allocation in the latest round before k0 that has still room tobe adjusted upward. Definek̂(k0 ) := max{k ≤ k0 : ck  ck },as the “round of adjustment.” We often simply write k̂ for short, and let ĵ := I + 1 − k̂.
Observe that k̂ is always well defined because C1 is not a singleton and is not bounded.
For any round k < k0 with ck = ck , there is no room to be adjusted upward; notethat this includes all rounds with nk ∈/ B, because Ck is a singleton and ck = ck = ck .
Therefore, if ck̂+1 = ck̂+1 , we can uniquely pin down ck̂+1 from ck̂ . By repeatedly applying
this process, we can uniquely pin down ck̂+m from ck̂ if ck = ck for all k = k̂ + 1, . . . , k̂ + m.
Let ck̂+m = ζm (ck̂ ) denote this mapping.
k̂

Lemma 2. Suppose ck = ck for k = k̂ + 1, . . . , k̂ + m, such that ζm (·) is well defined. Then,k̂ζm (·) is strictly increasing.
k̂

Proof. When ck = ck , t k = t̂ k ( j, ι(nk )) and pk = nk . Consider a slight increase in ck̂
according to the order . There are two ways to do this, either by increasing t k̂ or bydecreasing pk̂ . If t k̂ increases while pk̂ remains fixed, the indifference curve of type ι(nk̂+1 )passing through the point (ak̂ , t k̂ ) shifts up, and so t k̂+1 = t̂ k̂+1 ( ĵ − 1, ι(nk̂+1 )) (given by theintersection of this indifference curve and the dividing line D(·; ĵ − 1, ι(nk̂+1 )) increases.
Moreover, a higher t k̂ also reduces qk̂ = nk̂+1 (because µ(pk̂ , qk̂ ; ĵ) = t k̂ and µ(·) is locallydecreasing in qk̂ ). As a consequence, pk̂+1 = nk̂+1 also decreases. Therefore ck̂+1 becomes
higher according to . If pk̂ decreases while t k̂ remains fixed, this reduces qk̂ (becauseµ(pk̂ , qk̂ ; ĵ) = t k̂ and µ(·) is increasing in pk̂ ). Thus pk̂+1 = nk̂+1 = qk̂ falls, while there is nochange in t k̂+1 . Again, ck̂+1 becomes higher according to . By repeatedly applying this,we show that ck increases for all k = k̂ + 1, . . . , k̂ + m if ck̂ increases slightly.
23

We are now in a position to describe our adjustment procedure.
Adjustment procedure. The current allocation path is (c1 , . . . , ck0 ) and the candidate set
Ck0 +1 is undefined. Go to round k̂ and raise ck̂ . Compute the corresponding ck̂+m = ζm (ck̂ )k̂for m = 1, . . . , k0 − k̂. Keep raising ck̂ and updating the allocations for rounds k̂ +1 throughk0 to the latest values of ζm (ck̂ ) until one of the following occurs.
k̂

0

1. If for some m0 = 1, . . . , k0 − k̂, the nk̂+m0 corresponding to ζm (ck̂ ) decreases to a pointk̂

nk̂+m0 ∈ B:
• reset k̂ to k̂ + m0 and go back to the beginning of the adjustment procedure withthe updated allocation path.
2. If ck̂ is raised to ck̂ :• reset k̂ to max{k ≤ k̂ : ck  ck } and go back to the beginning of the adjustment
procedure with the updated allocation path.
0

3. If ζk −k̂ (ck̂ ) becomes equal to the minimum allocation cmin
∈ Ck0 :k0k̂

• exit the adjustment procedure and return to the main algorithm at round k0
with the updated allocation path.
We argue that in part 2 of the adjustment procedure, ck̂ will reach ck̂ when t k̂ is still
below ĵ. Suppose we set t k̂ = ĵ, but we still have τk0 (ck0 ) < 0. If t k̂ = ĵ, then t k̂+1 must
be greater than ĵ − 1. Therefore τk̂+1 (ck̂+1 ) = t k̂+1 − µ∗ (pk̂+1 ) > 0 for any pk̂+1 . Sincek̂+1

we change τk̂+1 (·) continuously during the adjustment procedure, and since τk̂+1 (·) < 0
at the beginning of the adjustment, there must be a smaller allocation c0 and the induced
allocation c0

k̂+1

such that τk̂+1 (c0

k̂+1

k̂

) = 0. By repeating this argument, there is an evensmaller allocation c00 and the induced allocation c00k0 such that τk0 (c00k0 ) = 0 where j 0 :=k̂

N + 1 − k0 . However, this is a contradiction because we would have reached part 3 of theadjustment procedure before we reach that point.
This argument also implies that our adjustment procedure can always return a minimum allocation path up to round k0 to the main algorithm. Since we always try to find theminimum allocation, whenever we fail to find it for the first time, we know τk0 (ck0 ) < 0.
We then adjust the allocation path continuously until we find the minimum allocation. It
is thus without loss of generality to assume τk0 (ck0 ) < 0 in any round where Ck0 +1 is undefined. Now suppose that we set ck = ck for all k = 2, . . . , k0 − 1 but still have τk0 (ck0 ) < 0.

24

In this case, we increase c1 , which is unbounded, and in particular raise t 1 to I while fixing p1 at 0. By the same argument, there must be an allocation c1 smaller than (I, 0) andthe induced allocation c0k0 such that τk0 (ck0 ) = 0. Given that we start from an allocationthat is too low, by continuity, we must find the minimum allocation before we reach thatpoint. Since Ck0 +1 is well defined whenever the allocation in the previous round is a minimum allocation, this means that the main algorithm can proceed to round k0 + 1 after the
adjustment procedure.
5.5.

Global incentive compatibility

Because the adjustment procedure can always return an allocation path to the main algorithm that allows the algorithm to proceed to the next round, the algorithm will eventuallystop (the number of rounds cannot exceed I). In each round of this construction, the allocations are chosen in such a way that they satisfy Bayes’ rule, local incentive compatibility,
and the weak pairwise-matching condition (which guarantees the D1 refinement is met).
Equilibrium existence is therefore proven if we can show that the allocation path obtainedat the end of the main algorithm satisfies global incentive compatibility.
In any equilibrium, there can only be a finite number of allocations that are chosenLon the equilibrium path. We thus denote by {(a` , t ` )}`=1
the set of equilibrium allocations

where a`+1 > a` and t `+1 > t ` for all ` = 1, . . . , L − 1; throughout the proof, we assume
L ≥ 3 because there is no distinction between local and global incentive compatibility
when L < 3. We say that local incentive compatibility holds for agent n ∈ Q(a` ) if heweakly prefers (a` , t ` ) to (amin{`+1,L} , t min{`+1,L} ) and (amax{`−1,1} , t max{`−1,1} ). Our algorithm
ensures that local incentive compatibility holds for all agents.
For each `, use i ` and i ` to represent respectively the lowest and highest type choosing(a` , t ` ). The following fact is useful toward establishing the main existence result.
Lemma 3. Consider some agent n0 such that ι(n0 ) ≤ i L and his equilibrium allocation000(a` , t ` ). At any point on φ ∗ (a; ι(n0 )) for a < a` , type ι(n0 ) has a lower marginal rateof substitution than any lower type i < ι(n0 ).
00

Proof. We claim that for any n0 such that ι(n0 ) ≤ i L , a` < D(t ` ; ι(n0 ), ι(n0 ) − 1), i.e., the000

corresponding allocation (a` , t ` ) must locate to the left of D(t ` ; ι(n0 ), ι(n0 )−1). There are00three cases. First, if Q(a` ) is a pooling set and `0 < L, Q(a` ) is disconnected. Then, by the000

weak pairwise-matching condition, (a` , t ` ) must locate to the left of D(t ` ; ι(n0 ), ι(n0 )−1).
0

Second, if Q(a` ) is a pooling set and `0 = L, Q(a L ) must be an interval. Since the lowest
25

type who chooses (a L , t L ) must have the highest marginal rate of substitution, (a L , t L ) must
000locate to the left of D(t L ; i L , i L −1). Finally, if (a` , t ` ) is fully separating and Q(a` ) contains
000

only one type of agents, we must again have (a` , t ` ) to the left of D(t ` ; ι(n0 ), ι(n0 ) − 1),for otherwise incentive compatibility cannot be satisfied.
Since any indifference curve can cross a dividing line once, the equilibrium indifference0

curve of type ι(n0 ) cannot cross D(·; ι(n0 ), ι(n0 ) − 1) at any point to the left of a` . This0means a < D(φ ∗ (a; ι(n0 )); ι(n0 ), ι(n0 ) − 1) for all a < a` . Then, by Assumption 2, we have0

a < D(φ ∗ (a; ι(n0 )); ι(n0 ), i) for all a < a` and i < ι(n0 ), which proves the lemma.
Proposition 4. There always exists a D1 equilibrium.
Proof. We first show that local incentive compatibility implies global incentive compatibility for all types i ≤ i L . Consider some agent n0 such that ι(n0 ) ≤ i L and his equilib00rium allocation (a` , t ` ). Suppose there exists some `00 > `0 + 1 such that agent n0 strictly
00

00

0

0

prefers (a` , t ` ) to (a` , t ` ). Local incentive compatibility suggests that there is some agent
00

00

00

00

n00 > n0 with ι(n00 ) > ι(n0 ) who weakly prefers (a` −1 , t ` −1 ) to (a` , t ` ).12 This means that00φ ∗ (·; ι(n0 )) must cross φ ∗ (·; ι(n00 )) from above at some a < a` . This contradicts Lemma 3
because type ι(n0 ) must have a higher marginal rate of substitution than type ι(n00 ) at any
00

point on φ ∗ (a; ι(n0 )) for a < a` . Similarly, suppose there exists some `00 < `0 − 1 such that
00

00

0

0

agent n0 strictly prefers (a` , t ` ) to (a` , t ` ). Then, by local incentive compatibility, there
00

00

00

00

is some agent n00 < n0 with ι(n00 ) < ι(n0 ) who weakly prefers (a` +1 , t ` +1 ) to (a` , t ` ).
This means that φ ∗ (·; ι(n0 )) must cross φ ∗ (·; ι(n00 )) from below at some a < a`0 +1 . This isagain a contradiction because type ι(n0 ) must have a lower marginal rate of substitution
0

than type ι(n00 ) at any point on φ ∗ (a; ι(n0 )) for a < a` +1 .
If Q(a L ) is a pooling set, there exists agent n0 such that i L ≥ ι(n0 ) > i L . By the weak
pairwise-matching condition, for any such n0 , we have m(a L , t L , i L ) ≥ m(a L , t L , ι(n0 )). Thismeans φ ∗ (a; i L ) < φ ∗ (a; ι(n0 )) for all a < a L . Since type i L prefers (a L , t L ) to any otherallocation, so does type ι(n0 ).
0Finally, consider agent n0 such that ι(n0 ) > i L . If there is some agent n00 ∈ Q(a` ) such
0

0

0

0

that ι(n00 ) < ι(n0 ) and m(a` , t ` , ι(n0 )) = m(a` , t ` , ι(n00 )), then φ ∗ (a; ι(n0 )) ≥ φ ∗ (a; ι(n00 ))00

for all a by the double-crossing property. Since agent n00 prefers (a` , t ` ) to any otherallocation, so does agent n0 . If there are no such agents who have the same marginal rate
To see this, observe that Q(a` −1 ) cannot contain any type ι(n0 ) agent because otherwise agent n0 must
0
0
00
00
be indifferent between (a` , t ` ) and (a` −1 , t ` −1 ). If this is the case, local incentive compatibility implies
0
00
00
0
that agent n0 weakly prefers (a` , t ` ) to (a` , t ` ).
12

00

26

0

of substitution, by the weak pairwise-matching condition, there must be agent n00 ∈ Q(a` )00such that ι(n0 ) > ι(n00 ) > i ` and m(a` , t ` , ι(n00 )) < m(a` , t ` , ι(n0 )) < m(a` , t ` , i ` ). This
0

0

0

0

0

0

0

means that φ ∗ (a; ι(n0 )) > φ ∗ (a; ι(n00 )) for all a > a` and φ ∗ (a; ι(n0 )) > φ ∗ (a; i ` ) for00

all a < a` , i.e., φ ∗ (·; ι(n0 )) stays above the lower envelope of φ ∗ (·; ι(n00 )) and φ ∗ (·; i ` ).
00

Since both types ι(n00 ) and i ` prefer (a` , t ` ) to any other allocation, so does type ι(n0 ).
00This proves that local incentive compatibility implies global incentive compatibility for all
agents.
We remark that except in the case of I = 2 described by Proposition 3, equilibrium
is typically not unique. There are generally many equilibria because the candidate set
specified for our main algorithm is only a subset of all the possible allocations that satisfy
local incentive compatibility and the weak pairwise-matching condition. To illustrate thispossibility, define§ªιmax (a, t) := min arg max m(a, t, i) ,
i=1,...,I§ªιmin (a, t) := min arg min m(a, t, i) ,
i=1,...,Ifor a given allocation (a, t),13 and consider a full pooling equilibrium in which all types
choose (a p , E[i]). This constitutes a perfect Bayesian equilibrium under some off-equilibrium
beliefs if a p satisfiesu(a p , E[i], 1) ≥ u(0, 1, 1).

(2)

Moreover, this pooling equilibrium satisfies D1 ifE[i] ≥ max ιmax a p , E[i] , ιmin a p , E[i] .

(3)

It is easy to see that for any given E[i], there is a range of a p that satisfies (2). Thismeans that we may have a continuum of pooling equilibria if there is a range of a p that
also satisfies (3). This is generally the case if there are three or more types. Suppose,
for instance, that there are three types with E[i] ≥ 2. In this case, (3) is satisfied if
ιmax (a p , E[i]) = 1 and ιmin (a p , E[i]) = 2, which hold for any allocation that is bounded between D(·; 3, 2) and D(·; 3, 1); i.e., any (a p , E[i]) such that D(E[i]; 3, 2) ≤ a p ≤ D(E[i]; 3, 1).
13

When types are discrete, arg maxi=1,...,I m(a, t, i) and arg mini=1,...,I m(a, t, i) may not be singleton. In thiscase, we always pick the smaller type because D1 has no bite and we can assign an arbitrary off-equilibrium
belief.

27

As such, if there is some action a p such that (2) holds with strict inequality and also
D(E[i]; 3, 2) < a p < D(E[i]; 3, 1), both (2) and (3) continue to hold for any a in a smallneighborhood of a p . If there are only two types, on the other hand, E[i] ∈ (1, 2) and (3)can be satisfied if and only if ιmax (a p , E[i]) = ιmin (a p , E[i]) = 1, i.e., the allocation (a p , E[i])must be exactly on the dividing line as stated in Proposition 3. Since the dividing line isa function of t, there is a unique value of a p that can satisfy this, thereby eliminating any
possibility of multiple equilibria.

6.

Conclusion

In this paper we obtain a characterization of signaling equilibrium under double-crossing
preferences that holds for an arbitrary number of discrete types, and based on this characterization, provide a recipe that allows an explicit construction of equilibrium, complementing our earlier work for the case of continuous types. This recipe is useful because
equilibrium construction for even a small number of types (say, three or four) is generally
difficult. We also illustrate why equilibrium uniqueness obtains in the special case of two
types but a continuum of equilibria emerges when there are three or more types.

28

References
Araujo, Aloisio, Daniel Gottlieb, and Humberto Moreira, “A Model of Mixed Signals
with Applications to Countersignalling,” RAND Journal of Economics, 2007, 38 (4),1020–1043.
Bobtcheff, Catherine and Raphael Levy, “More Haste, Less Speed? Signaling throughInvestment Timing,” American Economic Journal: Microeconomics, 2017, 9 (3), 148–
186.
Chen, Chia-Hui, Junichiro Ishida, and Wing Suen, “Reputation Concerns in Risky Experimentation,” Journal of the European Economic Association, 2021, 19 (4), 1981–2021.
,

, and

, “Signaling under Double-Crossing Preferences,” Econometrica, 2021, (forth-coming).
Cho, In-Koo and David M. Kreps, “Signaling Games and Stable Equilibria,” Quarterly
Journal of Economics, 1987, 102 (2), 179–221.
Daley, Brendan and Brett Green, “Market Signaling with Grades,” Journal of Economic
Theory, 2014, 151, 114–145.
Degan, Ariana and Ming Li, “Perasuasion with Costly Precision,” Economic Theory, 2021,
72 (3), 869–908.
Dixit, Avinash K. and Barry Nalebuff, The Art of Strategy, New York, NY: W. W. Norton,
2008.
Feltovich, Nick, Richmond Harbaugh, and Ted To, “Too Cool for School? Signalling andCountersignalling,” RAND Journal of Economics, 2002, 33 (4), 630–649.
Frankel, Alex and Navin Kartik, “Muddled Information,” Journal of Political Economy,
2019, 127 (4), 1739–1776.
Hörner, Johannes, “Signalling and Screening,” The New Palgrave Dictionary of Economics,
2d. ed., 2008, 15. Basingstoke, UK: Palgrave Macmillan.
Kolev, Dobrin R. and Thomas J. Prusa, “Dumping and Double Crossing:

The(In)efficiency of Cost-Based Trade Policy under Incomplete Information,” International
Economic Review, 2002, 43 (3), 895–918.
29

Riley, John G., “Informational Equilibrium,” Econometrica, 1979, 47 (2), 331–359.

30

Appendix: The Set of Candidate Allocations
In this appendix, we provide a more detailed account of how we construct the candidate
set Ck when nk ∈ B. Since case (i) (where there is a separating equilibrium for types
between ι(nk ) and j) is fully described in the main text, we here focus on case (ii) where
it is not feasible to construct a separating equilibrium for types between types ι(nk ) andj. In this case, the set of candidate allocations often traces the indifference curve of somerelevant type that passes though his reservation allocation. To obtain the corresponding
action ak = α(t k ) from the choice of t k , it is thus convenient to define an indifference
curve as a function of reputation t: define ψ(·, i; ãk , t̃ k ), or ψk (·, i) for short, to be theindifference curve of type i that passes through some reservation allocation (ãk , t̃ k ). Also,
as in the main text, define (âk ( j, i), t̂ k ( j, i)) such thatu(âk ( j, i), t̂ k ( j, i), i) = u(ãk , t̃ k , i),âk ( j, i) = D( t̂ k ( j, i); j, i),for a given reservation allocation (ãk , t̃ k ). It is important to note that the reservation allocation (ãk , t̃ k ) depends on ck−1 and pk ; as such, both ψk (·, i) and (ãk , t̃ k ) depend on themas well, although we do not explicitly indicate this dependence for brevity.
We have already shown that when nk ∈ B, the candidate set Ck is given by(pk ∈ [nk , Fik∗ ]

and

tk

= t̂ k ( j, ι(pk ))if pk 6∈ B,∈ [max{ t̂ k ( j, ι(pk )), t k−1 }, t̂ k ( j, ι(pk ) − 1)]

if pk ∈ B,

where we let t̂( j, 0) = ∞. In each round of our algorithm, we need to search for a tentative
allocation over this two-dimensional space Ck . Below, we will describe how we pin down
the corresponding action ak = α(t k ) from ck = (t k , pk ) ∈ Ck .
First, if pk ∈/ B, some type ι(pk ) agents choose a separating action. We can thenuniquely pin down t k = t̂ k ( j, ι(pk )) with (ãk , t̃ k ) = (sk∗ (ι(pk )), ι(pk )). This is the easy caseto deal with, because we can also uniquely pin down
ak = α t̂ k ( j, ι(pk ) = âk ( j, ι(pk )) .
Second, if pk ∈ B and ι(pk ) > 1, type ι(pk ) separates from type ι(pk ) − 1 and pool with
type j. Both types ι(pk ) − 1 and ι(pk ) are relevant, and any candidate allocation must bebounded between ψk (·, ι(pk ) − 1) and ψk (·, ι(pk )) with the reservation allocation given by31

(1). Moreover, to pool with type j, the weak pairwise-matching condition requires thatany candidate allocation must be bounded between D(·; j, ι(pk )) and D(·; j, ι(pk )−1). The
feasible range of t k is thereforet k ∈ max t̂ k ( j, ι(pk )) , t̃ k , t̂ k ( j, ι(pk ) − 1) ,where t̃ k ≤ t̂ k ( j, ι(pk )) only if pk = Fik∗ . For t k in this range, if the reservation allocation
is to the left of D(·; j, ι(pk )), we first move up along the dividing line D(·; j, ι(pk )) until ithits ψk (·, ι(pk ) − 1), and then trace this indifference curve; if the reservation allocation isto the right of D(·; j, ι(pk )), we simply trace ψk (·, ι(pk ) − 1). To sum up,αk (·) = max {D (·; j, ι(pk )) , ψk (·, ι(pk ) − 1)} .
Figure 3 illustrates how to construct Ck and also how to “increase” the allocation in thisset when ik∗ > ι(nk ).
Finally, if pk = 0, the set of candidate allocations is unbounded; observe that this canhappen only in round 1. Any allocation on D(·; I, 1) can be a candidate allocation as longas it gives type 1 a payoff at least as large as the reservation allocation (ã1 , t̃ 1 ) = (0, 1).
The feasible range of t 1 is therefore t 1 ∈ [max{ t̂ 1 (I, 1), 1}, ∞) withα1 (·) = max {D(·; I, 1), 0} .

32

B

A

Figure 3. When pk is set to its highest level Fi ∗ , a candidate allocation must be bounded betweenkψk (·, ik∗ ) and ψk (·, ik∗ + 1), with the reservation allocation given by (sk∗ (ik∗ ), ik∗ ), and also between
D(·; j, ik∗ + 1) and D(·; j, ik∗ ). Point A represents ck , which is the lowest possible allocation in roundk. Starting from this point, we first move up along D(·; j, ik∗ + 1) until it hits ψk (·; ik∗ ) and then traceψk (·; ik∗ ) until it reaches point B, as indicated by the thick line. At point B, we lower pk from Fi ∗ tok

Fi ∗ −1 . Once pk reaches Fi ∗ −1 , we switch the reservation allocation to (sk∗ (ik∗ − 1), ik∗ − 1), draw thekkindifference curve of type ik∗ − 1 that passes through (sk∗ (ik∗ − 1), ik∗ − 1) and repeat the same process.

33