Volume 90, Issue 5 pp. 2187-2214
Original Articles
Open Access

Information Hierarchies

Benjamin Brooks

Corresponding Author

Benjamin Brooks

Department of Economics, University of Chicago

Search for more papers by this author
Alexander Frankel

Alexander Frankel

Booth School of Business, University of Chicago

Search for more papers by this author
Emir Kamenica

Emir Kamenica

Booth School of Business, University of Chicago

Search for more papers by this author
First published: 14 October 2022
Citations: 3
We thank Ozan Candogan, Eddie Dekel, Simone Galperti, Stephen Morris, Xiaosheng Mu, Ludvig Sinander, Alex Smolin, and Bruno Strulovici for helpful comments. We thank Oguz Bayraktar and Cheryl Wu for research assistance. Kamenica thanks the Neubauer Family Faculty Fellowship for research support.

Abstract

If experiment A is Blackwell more informative than experiment B, it is always possible that A and B are induced by signals A′ and B′ such that A′ is a refinement of B′, that is, A′ entails observing B′ plus some additional information. We first show that this result does not extend beyond pairs of experiments: There exist collections of experiments that cannot be induced by a collection of signals so that whenever two experiments are Blackwell ordered, the associated signals are refinement ordered. In other words, sometimes it is impossible for more informed agents to know everything that less informed agents know. More broadly, define an information hierarchy to be a partially ordered set that ranks experiments in terms of informativeness. Is it the case that for any choice of experiments indexed on the hierarchy such that higher experiments are Blackwell more informative, there are signals that induce these experiments with higher signals being refinements of lower signals? We show that the answer is affirmative if and only if the undirected graph of the information hierarchy is a forest.

1 Introduction

There are two distinct things we might mean when we say that A is more informed than B. One is that A's information about some state of the world is more accurate than B's. The other is that A knows everything that B knows; that is, A observes what B observes, plus something else. The first notion is typically formalized by representing a source of information as an experiment, that is, a distribution of posterior beliefs (Blackwell (1953)). We then say that A is Blackwell more informed than B if A's beliefs are a mean-preserving spread of B's beliefs. The second notion is formalized by representing a source of information as a partition of some expanded state space urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0001 (Green and Stokey (1978)). This formulation distinguishes payoff-relevant states (Ω) from the realizations of signals conditional on those states (X). We then say that A knows everything that B knows if A's partition is a refinement of B's partition.

These two formalisms are closely related. Every signal, that is, partition of the expanded state space, induces an experiment. If one signal is a refinement of another, then the experiment it induces is Blackwell more informative. Moreover, Green and Stokey (1978) established a partial converse: given two Blackwell-ordered experiments, there exist refinement-ordered signals that induce those experiments. In other words, if A's information is more accurate than B's, it is always possible that A knows everything that B knows.

A natural question is whether Green and Stokey's result extends beyond pairs of experiments. Suppose we have some collection of experiments. Is it always the case that we can construct a collection of signals that induce those experiments, and whenever two experiments are Blackwell ordered, the two corresponding signals are refinement ordered?

We show that the answer is negative. We construct an example where A is Blackwell more informed than B and C, who are in turn more informed than D, and yet it cannot be that A knows everything that B and C know and that all three know everything that D knows.

To examine this issue more generally, we introduce the notion of an information hierarchy, which is simply a partially ordered set. We consider experiment allocations that assign an experiment to each element of the hierarchy, with the property that a higher element's experiment is Blackwell more informative than a lower element's experiment. We say an experiment allocation is constructible if it is possible to assign a signal to every element of the hierarchy so that each signal induces the corresponding experiment, and a higher element's signal is a refinement of a lower element's signal. If every monotone experiment allocation is constructible, we say that the information hierarchy is universally constructible.

Our main theorem characterizes the set of information hierarchies that are universally constructible. A partially ordered set (and thus an information hierarchy) is associated with an undirected graph, whose nodes are the elements of the set and whose edges are determined by the partial order. We establish that an information hierarchy is universally constructible if and only if this graph is a forest.

We also establish a generalization of this result. We consider a class of other economically meaningful orders on signals, and we show that, if we replace refinement with any one of these orders in our notion of constructibility, our theorem continues to hold.

We discuss two applications of our theorem. First, suppose there is an agent who observes information from several sources and an econometrician who does not know the data generating process behind these sources. We analyze the conditions under which the econometrician can rationalize the agent's reactions to this information. In particular, we show that two necessary conditions, Bayes plausibility and Blackwell monotonicity, do not suffice for rationalizability when there are more than two sources of information. Second, we study information design in organizations under the constraint that managers must have access to the information of their subordinates.

The rest of this paper proceeds as follows. Section 2 establishes basic definitions. Section 3 presents motivating examples. Section 4 contains the remaining definitions and our main result. Section 5 discusses extensions. Section 6 provides two applications. We discuss related literature in probability theory and information economics in Section 7. Section 8 is a conclusion.

2 States, Signals, and Experiments

There is a finite state space Ω and a prior urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0007.

A signal π is a finite partition of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0008 s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0009, where S is the set of non-empty Lebesgue-measurable subsets of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0010 (Green and Stokey (1978), Gentzkow and Kamenica (2017)). An element urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0011 is a signal realization. The interpretation of this formalism is that a random variable x, drawn uniformly from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0012, determines the signal realization conditional on the state. Thus, the conditional probability of s given ω is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0013 where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0014 denotes the Lebesgue measure. Importantly, if we know that one agent observed some signal, say urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0015, and another agent observed some signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0016, we can deduce not only how informed each agent is about ω, but also the joint distribution of their signal realizations (and thus their higher-order beliefs).

In contrast, a (Blackwell) experiment only specifies how informed an agent is about ω, without specifying her information about the beliefs of other agents. The standard definition of an experiment is a map from Ω to distributions over signal realizations, but for ease of exposition we identify each experiment with the distribution of beliefs it induces. Thus, we define an experiment, denoted by τ, as an element of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0017 that has finite support and satisfies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0018.

We write urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0019 if π is a refinement of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0020, that is, every element of π is a subset of some element of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0021. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0023, an agent who observes π has access to all the information available to the agent who observes urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0024 (and thus knows those agent's beliefs). We write urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0025 if τ is Blackwell more informative than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0026, that is, τ is a mean-preserving spread of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0027. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0028, an agent who observes τ obtains a higher payoff than the agent who observes urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0029 in any decision problem.

We denote the set of all signals by Π. The pair urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0030 is a lattice and we let ∨ denote the join, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0031 is the coarsest refinement of both π and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0032. Note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0033 is the signal that is equivalent to observing both π and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0034.

Each signal π induces an experiment, denoted urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0035, according to
urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0036
where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0037 is the unconditional probability of signal realization s and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0038 is the posterior belief about ω conditional on s. Moreover, given signal π, we let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0044 denote the belief-valued random variable on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0045 that is the posterior induced by the observation of the signal realization from π. Note that the refinement order implies a belief-martingale property: if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0046, then urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0047. In other words, observing additional information cannot change one's belief on average.

3 Illustrative Examples

There are four experiments, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0048, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0049, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0050, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0051, some of which might be Blackwell more informative than others. We wish to know whether there exist signals urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0052 for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0053 such that

  • (C1) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0054 and
  • (C2) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0055 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0056.

As we discussed in the Introduction, the answer to this question will shed light on (i) whether Green and Stokey's (1978) result on the equivalence of representing information as experiments versus signals generalizes beyond pairwise comparisons, and (ii) whether it is always possible that a more informed agent knows what all less informed agents know.

As we will see, for some Blackwell rankings of the experiments, the answer is yes, no matter what the the exact experiments are. For other rankings, this is not the case; there exist experiments for which there do not exist signals satisfying (C1) and (C2). We illustrate these results through three examples, depicted in Figure 1.

Details are in the caption following the image

Example hierarchies.

Chain

Suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0057. When experiments are ordered in this way, it is always possible to construct signals that satisfy (C1) and (C2), regardless of the particular experiments. This follows from Green and Stokey (1978): For any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0058 and τ with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0059, there exists a π such that (i) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0060 and (ii) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0061. In other words, take any signal that induces some experiment; there is a refinement of this signal that induces any particular more-informative experiment.

Now, consider any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0062 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0063. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0064, there exists some signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0065 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0066. Similarly, there is a urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0067 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0068. Finally, there is a urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0069 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0070. Hence, we constructed signals that satisfy (C1) and (C2).

Tree

Next, suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0071, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0072, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0073 is not comparable with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0074 or urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0075. In this case, it is again always possible to construct signals so that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0076 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0077 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0078. The argument, however, is more subtle than for the chain. To see the issue, suppose we first go “up the tree” and proceed as in the previous example: we construct urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0079 and then urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0080 that induce urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0081 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0082. Now, to assign a signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0083, we have to go “down the tree.” But there is no guarantee that, given the urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0084 we constructed, there exists a urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0085 that is coarser than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0086 and induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0087.

We establish a result (Lemma 1), however, that tells us we can construct urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0088 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0089 and has the property that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0090. (To do so, we build a urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0091 whose realizations are independent of the state given the realization of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0092.) Then, we replace the “provisional” urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0093 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0094 (which is of course also finer than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0095). We then apply a similar procedure to assign urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0096 and update the provisional urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0097 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0098. Hence, we constructed signals that satisfy (C1) and (C2). This algorithm is discussed in greater detail in Section 4.

Diamond

Finally, suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0099, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0100, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0101 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0102 are not (necessarily) comparable. We now give an example of four experiments ordered in this manner such that there do not exist signals that satisfy (C1) and (C2).

Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0103 with a uniform prior. Since the state space is binary, we associate each belief with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0104. The rows in Figure 2 depict the four experiments, with the number of dots in a circle proportional to the probability mass on that belief. It is easy to see that these four experiments satisfy the given Blackwell ordering, with arrows (solid or dashed) showing the unique way to obtain a higher-ranked distribution as a mean-preserving spread of a lower-ranked distribution.

Details are in the caption following the image

The diamond hierarchy is not universally constructible.

Now, to obtain a contradiction, suppose that the signals urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0105, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0106, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0107, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0108 satisfy (C1) and (C2). First, note that these signals do not merely induce the respective marginal distributions of beliefs (i.e., the experiments), but they also determine the joint distribution of these beliefs. In particular, as noted earlier, whenever urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0109, we must have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0110.

We use this fact to show that when urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0111, (i) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0112 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0113, while (ii) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0114 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0115 with a strictly positive probability. To see (i), note that when urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0116, we must have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0117 and thus urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0118 (since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0119 if and only if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0120). To see (ii), note that when urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0121, there is a strictly positive probability that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0122 (since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0123 if and only if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0124); and when urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0125, there is a strictly positive probability that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0126 (since all of the other beliefs in the support of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0127 are strictly lower than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0128). Thus, we have reached a contradiction.

4 Universal Constructibility

4.1 Information Hierarchies and Constructibility

These examples motivate the following issue. Partially order a collection of experiments so that higher experiments are Blackwell more informative than lower experiments. Is it possible to find signals that induce these experiments, and that satisfy the property that signals inducing higher experiments are refinements of signals inducing lower ones? We argued that this was in fact always possible when the ranking on experiments corresponded to the chain or the tree example above but was not necessarily possible when experiments were ranked as a diamond. The main result of this paper is an if-and-only-if characterization of the rankings of experiments such that suitable refinement-ordered signals exist for any experiments whose Blackwell order is consistent with the ranking.

We now provide the remaining definitions needed to state our result. An information hierarchy H is a finite partially ordered set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0129. We refer to elements of N as nodes. Given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0130, we say that n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0131 if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0132 and there does not exist urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0133 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0134. The graph of H, denoted urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0135, is an undirected graph whose nodes are the elements of N with an edge between two nodes if one covers the other. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0136 is a forest if there is at most one path between any two nodes.

Fix an information hierarchy H and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0169. An experiment allocation on H is a map that assigns an experiment to every node; experiment allocation β is monotone if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0170 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0171, that is, higher nodes are Blackwell more informed than lower nodes. A signal allocation on H is a map that assigns a signal to every node; signal allocation σ is monotone if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0172 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0173, that is, signals associated with higher nodes refine signals associated with lower nodes. A signal allocation σ induces an experiment allocation β if, for all n, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0174. A (monotone) experiment allocation on H is constructible if there exists a monotone signal allocation that induces it.

We say that H is universally constructible if, for every Ω and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0176, every monotone experiment allocation is constructible.

4.2 Main Result

We now present the main result of the paper:

Theorem 1.An information hierarchy is universally constructible if and only if its graph is a forest.

To relate this result to our motivating examples, both the chain and the tree are examples of information hierarchies whose graphs are forests; hence, every monotone experiment allocation is constructible. The graph of the diamond, however, is not a forest because there are two paths from A to D, namely the path going through B and the path going through C; hence, we were able to present a monotone experiment allocation that is not constructible.

A rigorous proof of Theorem 1 is in the Appendix. The remainder of this section sketches the argument.

4.3 Proof Sketch: if

We begin by explaining why, if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0177 is a forest, then any monotone experiment allocation can be constructed. We illustrate this for the special case when urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0178 is a tree. One can then obtain the general case by applying the same argument on each of the disjoint trees that make up the forest.

The proof relies on the following result, which is of independent information-theoretic interest. We say that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0179 is statistically redundant given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0180 if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0181, that is, observing urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0182 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0183 yields the same beliefs as observing urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0184 only.

Lemma 1.Fix signals urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0195 and π, with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0196, and an experiment urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0197 that is Blackwell less informative than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0198. There exists a signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0199 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0200 and is statistically redundant given any signal that is between π and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0201 in the refinement order.

To better understand the content of Lemma 1, it is helpful to note that the following, stronger, conjecture does not hold. One might think that, analogously to the aforementioned result of Green and Stokey (1978), for any π and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0202 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0203 Blackwell less informative than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0204, there exists a urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0205 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0206 and is coarser than π. This is not the case. Lemma 1 implies, however, that we can nonetheless find a urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0211 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0212 and is statistically redundant given π, even though we cannot guarantee that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0213. Moreover, the lemma further implies we can find a urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0214 so that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0215 is statistically redundant given any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0216 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0217.

Why do we need the upper bound urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0218? Once we fix any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0219 and π, we can construct urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0220 that is statistically redundant given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0221, π, and anything in between. But, suppose we only fix π and consider an arbitrary urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0222. As long as urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0223 is not coarser than π, there is always some refinement of π, say urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0224, such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0225 is not statistically redundant given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0226.

The proof of Lemma 1 is constructive. To see how the construction works, consider the example in Figure 3. The state is either L or R. Each of the four rows represents a signal, that is, a partition of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0227. The two rectangles in each row represent the unit interval crossed with the two states. Each signal realization is indicated by its pattern. Note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0228, and while urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0229, it is not the case that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0230 nor that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0231.

Details are in the caption following the image

Illustration of Lemma 1.

To establish the claim in Lemma 1, we need to construct a signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0232 that induces the same beliefs as urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0233, but is statistically redundant given π, and given any refinement of π up to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0234. The bottom row illustrates such a construction. Each signal realization of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0235 corresponds to a signal realization of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0236, with the same likelihood in each state. However, the “locations” of the signal realizations in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0237 are rearranged so that the conditional probability of each signal realization of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0238 in state ω given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0239 is (i) the same for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0240 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0241, and (ii) the same for any elements of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0242 that refine the same element of π. Property (i) ensures that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0243 is statistically redundant given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0244, while (i) and (ii) together ensure that it is also redundant given any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0245 s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0246. The proof in the Appendix generalizes this construction.

With Lemma 1 in hand, we can now establish the universal constructibility of trees. Consider the tree hierarchy described in Section 3. Take some monotone experiment allocation β on this hierarchy. We construct a sequence of monotone signal allocations on progressively larger subsets of N, adding one node at a time. The signal assigned to a given node may be revised as the sequence progresses.

In Step 1, we pick an arbitrary node, say node D. Given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0247, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0248 be any signal that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0249. In Step 2, we pick a node connected to D, node A. Node A is above node D and so we follow the same procedure as in the chain example to tentatively assign a suitable signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0250 to A, with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0251 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0252; the signal to D is unchanged in this step, that is, we let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0253. In Step 3, we pick an unassigned node connected to A or D, which here must be node B. Since B is below A, a complication in assigning a signal to B is that there may not exist a signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0254 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0255 and yet urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0256. This is where Lemma 1 comes into play. Applying Lemma 1 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0257 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0258, we conclude that there exists a signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0259 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0260 and is statistically redundant with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0261, so that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0262. We then set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0263, we replace the initial assignment to A with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0264, and we leave the signal at D unchanged at urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0265. Finally, in Step 4, we move to the final node C, below the previously assigned node B. We now apply Lemma 1 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0266, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0269, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0270 to obtain a new signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0271 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0272 and is statistically redundant with the previously assigned signals at nodes above C. We then set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0273 and replace the signals of the previously assigned nodes above C as in Step 3.

This completes the construction of a monotone signal allocation inducing experiment allocation β. The full details of this procedure, applied to any hierarchy whose graph is a forest, are the heart of the formal proof of the if direction.

Which properties of a tree are used in this argument? When we apply this procedure to trees (or forests more generally), we can add the nodes in a way so that the new node n always covers or is covered by exactly one node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0274 to which we have previously assigned a signal. When n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0275, we can apply Green and Stokey's (1978) result to obtain the new signal at n. When n is covered by urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0276, we can apply Lemma 1 instead. If the hierarchy is not a forest, however, no matter how we add the nodes, we will inevitably find ourselves in a situation where the new node covers or is covered by more than one node, in which case neither Green and Stokey's (1978) result nor Lemma 1 is of use.

4.4 Proof Sketch: Only if

We now sketch the proof of the other direction of Theorem 1: a hierarchy is universally constructible only if its graph is a forest. The proof consists of three main steps. Step 1 introduces a notion of a closed subhierarchy and establishes that a hierarchy is universally constructible only if its closed subhierarchies are as well. Step 2 shows that every hierarchy that is not a forest contains a closed subhierarchy that is one of two types. Step 3 shows that both of these types are not universally constructible, thus completing the proof.

Step 1: Given a hierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0277, a subset of nodes urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0278 induces the hierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0279, which we refer to as a subhierarchy of H, with the partial order being the restriction of ≥ to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0280. Say that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0281 is closed if, for every urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0282 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0283, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0284 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0285. In other words, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0286 contains all the nodes from N that are “between” the nodes of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0287. Lemma 2 in the Appendix shows that if H is universally constructible, then every closed subhierarchy of H is also universally constructible. The argument is as follows. Fix a closed subhierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0288. We show that any monotone experiment allocation β on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0289 can be extended to a monotone experiment allocation on all of H. This step uses the hypothesis that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0290 is closed, since it means that in extending β, we never have to fill in beliefs for “in between” nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0291. As H is universally constructible, there is a monotone signal allocation on H that induces the extension of β, and the restriction of this signal allocation to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0292 is a monotone signal allocation on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0293 that induces β. Since β is arbitrary, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0294 is universally constructible.

Step 2: Say that a hierarchy H is cyclic if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0295 is not a forest. Suppose H is cyclic. Given that N is finite and H is cyclic, it follows that H contains a minimal cyclic closed subhierarchy (MCC), that is, a subhierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0296 such that: urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0297 is cyclic, closed, and there does not exist urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0298 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0299 is cyclic and closed. Any MCC urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0300 must fall into one of the following categories:

  • urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0301 is a union of non-comparable paths (UNP): It contains a maximal node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0302 and a minimal node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0303, and its graph consists of at least two paths between urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0304 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0305. Moreover, nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0306 are comparable only if they are in the same path. The diamond is an example of a UNP; another example is depicted in Figure 4(a).
  • urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0307 is a crown: It contains exactly four nodes, which we label F(ather), M(other), S(on), D(aughter), and the partial order consists of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0308, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0309, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0310, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0311. A crown is depicted in Figure 6(a).
Details are in the caption following the image

For adjacent nodes, the node that is higher in the figure covers the node that is lower. (a) A UNP. Nodes A, B, and C are in different paths, and therefore are not comparable. (b) A between set which is not an MCC. There are two overlapping (directed) paths that go from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0312 to A to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0313, one that goes through B and one that does not. There is a smaller cyclic closed subhierarchy, namely the nodes between A and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0314.

This taxonomy takes considerable effort to prove formally, but the high level argument is as follows. An MCC urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0315 contains maximal nodes, which are not covered by any other node, and minimal nodes, which do not cover any other nodes. We distinguish two cases on these maximal and minimal nodes.

In the first case, every maximal node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0316 covers every minimal node. Then, the fact that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0317 is minimal, together with the existence of a cycle, implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0318 contains exactly four nodes and is in fact a crown.

Alternatively, there is a maximal node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0319 that does not cover a minimal node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0320. Then, we show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0321 is a UNP. To see this, note the following two subcases. First, it may be that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0322 is simply the set of nodes that are between urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0323 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0324, that is, a between set. Then, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0325 consists of a series of directed paths between urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0326 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0327. Now, if nodes in distinct paths were comparable, then it would be possible to find a smaller cyclic closed subhierarchy, as illustrated in Figure 4(b), violating the fact that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0328 is minimal. Thus, nodes must not be comparable across paths and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0329 is a UNP. The second subcase is that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0330 is not a between set. Lemma 4 in the Appendix shows that then every cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0331 must contain every node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0332. Any such spanning cycle can be decomposed into two undirected paths between a maximal node and a minimal node. If any nodes in these two paths were comparable, we could find a smaller cycle that does not contain every node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0333, which would contradict Lemma 4. As a result, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0334 is a UNP.

Step 3: Finally, we show that UNPs and crowns are not universally constructible. The former is demonstrated in Lemma 6 in the Appendix using a similar construction as we used for the diamond in Section 3. Indeed, the diamond is an example of a UNP in which there are exactly two undirected paths from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0335 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0336.

For the crown, we construct a particular monotone experiment allocation that is not constructible: Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0337 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0338, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0339, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0340. We represent each belief as a pair urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0341 in the triangle urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0342, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0343 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0344. Consider the experiment allocation β that assigns to F, M, S, and D the experiments indicated in Figure 5(a). Each belief realization is a circle, the letters inside the circle indicate the nodes for which this belief is in the support, and the area of the circle is the likelihood of the belief (which is the same for all nodes attached to the belief). For example, the belief urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0345 can be realized for F, S, and D, with likelihood of 1/2 in each case. It is easy to see from Figure 5 that β assigns higher nodes more informative signals. For example, going from D to M (Figure 5(b)), the mass on the east and west beliefs stays the same, but the mass on the central belief is spread out in the north-south directions.

Details are in the caption following the image

The crown is not universally constructible.

Lemma 7 in the Appendix formally defines this experiment allocation and shows that it is not constructible. To see what goes wrong, suppose there is a monotone signal allocation that induces β. Such a signal allocation induces a joint distribution over beliefs at all four nodes. Consider first the joint distribution of beliefs between D, M, and S. The center D belief occurs if and only if the M belief is north or south (Figure 5(b)). The center belief of S occurs if and only if the M belief is east or west (Figure 5(c)). Hence, the probability of both D and S having the center belief is zero. Now consider the joint distribution of beliefs between D, F, and S. The belief at D is in the center if and only if the belief at F is in the center (Figure 5(d)), and the belief at S is in the center if and only if the belief at F is in the center (Figure 5(e)). So, the probability that both D and S have the center belief is positive, yielding a contradiction.

5 Discussion

5.1 Binary States

A key step in our proof of the only-if direction of Theorem 1 shows that the crown is not universally constructible. Specifically, Figure 5 presents a particular experiment allocation involving three states that is not constructible.

It is natural to ask whether there is an example of a non-constructible allocation on the crown using two states. No such example exists: when the state space is binary, every monotone experiment allocation on the crown is constructible. The reason is as follows. Take an arbitrary monotone experiment allocation β on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0346. It is known that the set of experiments under the Blackwell order is a lattice when the state space is binary (Kertz and Rösler (2000), Müller and Scarsini (2006)). Thus, there exists an experiment urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0347 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0348, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0349, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0350 for any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0351. We can therefore expand the crown hierarchy by adding a T(utor) whom F(ather) and M(other) hired to oversee the children: urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0352, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0353, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0354, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0355. We refer to this hierarchy as the cross, which is depicted in Figure 6(b). Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0356 be the experiment allocation on the cross that sets urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0357 for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0358 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0359. The allocation urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0360 is monotone by construction. The cross is a forest, and hence by Theorem 1, it is universally constructible. Thus, there is a monotone signal allocation urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0361 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0362. Restricting urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0363 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0364 yields a monotone signal allocation on the crown that induces β.

Details are in the caption following the image

The crown and cross hierarchies.

This example illustrates that the binary state space is special. With three or more states, every monotone experiment allocation is constructible if and only if the hierarchy is a forest. With binary states, being a forest is sufficient for constructibility, but it is not necessary. A natural direction for future research is to characterize necessary and sufficient conditions for every monotone experiment allocation to be constructible for the case of binary states.

5.2 Beyond the Refinement Order

As we mentioned at the outset, there are various things one might mean by “A is more informed than B.” One is that A's signal is Blackwell more informative than B's, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0365. Another is that A has observed all of B's information, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0366. These, however, are not the only economically relevant comparisons of signals. For instance, it might be that A knows B's belief about the state. Or, it might be that if A observed B's information, A's belief about the state of the world would not change, that is, that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0367 is statistically redundant given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0368. In a companion paper (Brooks, Frankel, and Kamenica (2022)), we explore these and other relations on signals in more detail. In this section, we explain how our results extend to a large class of notions of “more informed,” including those just mentioned.

First, consider the belief-martingale relation on Π, denoted urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0369, defined by urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0370 if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0371 for any prior. (We use the word relation rather than order because urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0372 is not transitive.) Note that the refinement order implies the belief-martingale relation, which in turn implies the Blackwell order:
urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0376

Many economically relevant comparisons of signals are “in between” refinement and the belief-martingale relation, that is, they are weaker than the former and stronger than the latter. For example, the two aforementioned comparisons—A knowing B's belief or B's signal being statistically redundant given A's—fall in this in-between category. Formally, we say a binary relation urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0377 on Π is proper if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0378.

Our main result can be extended by replacing the refinement order with any proper relation. In particular, say a signal allocation σ on H is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0379-monotone if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0380 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0381. The experiment allocation β on H is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0382-constructible if β is induced by some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0383-monotone signal allocation on H. A hierarchy is said to be urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0384-universally constructible if every monotone experiment allocation is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0385-constructible for any Ω and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0386. With this terminology, we have the following:

Theorem 2.Fix any proper relation urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0387. A hierarchy H is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0388-universally constructible if and only if its graph is a forest.

The if direction follows immediately from Theorem 1, since ⊵-universal constructibility implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0389-universal constructibility for any proper urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0390. For the only if direction, the key is to recognize that the proofs of Lemmas 6 and 7 in the Appendix establish not only that UNPs and crowns are not ⊵-universally constructible, but also that they are not urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0391-universally constructible. With that change, the remainder of the proof of the only if direction of Theorem 1 (replacing every instance of “universally constructible” with “urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0392-universally constructible”) establishes that if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0393 is not a forest, it is not urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0394-universally constructible. A fortiori, it is not urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0395-universally constructible for any proper urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0396.

6 Applications

6.1 Rationalizing Reaction to Unknown Sources of Information

Consider an agent who obtains information from multiple sources. If we do not know the information-generating process, what restrictions does the agent's rationality impose on her potential reactions to this information? Concretely, suppose a decision maker has access to a set of information sources urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0397. Suppose further that our data set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0398 tells us the distribution of beliefs conditional on observing any non-empty subset of information sources. When can we rationalize a given data set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0399 in the sense that we can associate each information source urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0400 with some signal (i.e., an element of Π) and conclude that belief formation is consistent with Bayes's rule?

To be rationalized, belief distributions (i.e., experiments) in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0401 have to satisfy two obvious properties. First, there is Bayes plausibility: the average belief cannot differ across sets of information sources, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0402 for any two subsets S and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0403. Second, there is Blackwell monotonicity: observing a superset of sources necessarily induces a more dispersed distribution of beliefs, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0404 is a mean-preserving spread of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0405 if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0406. A natural question is whether these are the only properties imposed by Bayesian updating.

Theorem 1 tells us that, when there are three or more sources, the answer is no. In this case, Bayesian updating requires more than just Bayes plausibility and Blackwell monotonicity. To see why, consider the set-inclusion information hierarchy H where each non-empty collection of sources urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0408 is associated with a node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0409 and the partial order is the superset order: urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0410 if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0411. As illustrated in Figure 7, the graph of this information hierarchy is not a forest. By Theorem 1, this means that there is some monotone experiment allocation on H, call it β, that cannot be induced by any monotone signal allocation on H. Now, we can associate with this β a data set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0412 by setting urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0413. Note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0414 necessarily satisfies Bayes plausibility and Blackwell monotonicity (since β is monotone). If we could rationalize urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0415 by associating each urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0416 with some signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0417, then the signal allocation urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0418 would induce β and be monotone (since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0419 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0420), contradicting Theorem 1. Thus, we know that there are data sets that satisfy Bayes plausibility and Blackwell monotonicity, yet cannot be rationalized.

Details are in the caption following the image

The set-inclusion hierarchy.

A fruitful direction for future research would be to fully characterize which reactions to unknown sources of information are rationalizable.

6.2 Information Design

Suppose a sender provides information to a set of agents. Moreover, she faces certain types of monotonicity constraints such as some agents must know the beliefs of some other agents or some agents must have access to others' information. Then, we can think of agents as elements of an information hierarchy, and the information design problem consists of selecting a (suitably monotone) signal allocation on this hierarchy. Our results shed light on how such monotonicity constraints affect the information design problem.

For example, consider organizations. A long literature in organization economics emphasizes the importance of the hierarchical structure of managerial relationships (Williamson (1967)). One important aspect of organizational design is deciding how much information to provide—about individuals' prospects for promotion, about the overall performance of the organization, etc.—to each member of the organization. It is often suboptimal to provide full transparency and share full information with everyone (Fuchs (2007), Jehiel (2015), Smolin (2017)).

A natural constraint that an information designer might face is that anyone in the organization ought to have access to the information that is available to her subordinates, that is, that the allocation of signals within the organization should be monotone with respect to the management structure, so that the signal of a superior refines the signals of their subordinates. This constraint interacts with the organization structure. Theorem 1 implies that, if an organization has the feature that every subordinate has at most one superior, the aforementioned constraint can always be satisfied as long as individuals who are higher up in the organization are more informed in the Blackwell sense. Furthermore, if the information designer's objectives only depend on each agent's experiment, then one could reformulate the information design problem in terms of the choice of monotone experiment allocation, rather than choosing monotone signal allocations directly. With richer managerial relationships, however, Theorem 1 also tells us there could be desirable allocations of information which are incompatible with the monotonicity constraint, even though they provide (Blackwell) more information to those higher up in the organization.

7 Related Literature

We now discuss the connection between our results and related literature in probability theory and in information economics.

7.1 Connections to Probability Theory

Mathematically, our results are close to a literature in probability theory on the relationship between orders on probability distributions and stochastic processes. Because the connection to this literature is technical, our discussion is somewhat formal and detailed.

Fix two distributions urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0421. We say that τ is greater than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0422 in the convex order if, for every convex function urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0423, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0424. The Sherman–Stein theorem says that the following are equivalent: (i) τ is greater than urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0425 in the convex order; (ii) τ can be obtained from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0426 via mean-preserving spreads. Blackwell (1953, Section 3) observed that his result is implied by the Sherman–Stein theorem, since we can interpret τ as an experiment and the convex function ϕ as the maximum utility obtained in a decision problem given a belief. Importantly, the mean-preserving spread from τ to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0427 is a probability transition kernel which defines a martingale on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0428. Thus, an equivalent way of stating (ii) is that there exists a two-period martingale on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0429 such that the marginals are τ and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0430.

This equivalence was later generalized by Strassen (1965, Theorem 8): the sequence urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0431 is increasing in the convex order if and only if there exists an M-period martingale with marginals urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0432. This result is closely related to Green and Stokey (1978) and, more broadly, whether experiments can be represented as partitions: When the set of realizations of the martingale is finite, the martingale generates a filtration urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0433, where each urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0434 is generated by a finite partition urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0435 of the underlying probability space, and the partitions are increasing in the refinement order. We can therefore view the probability space itself as an expanded state space, so that the urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0436 are refinement-ordered signals that induce the given experiments. In our terminology, Strassen's theorem implies that the chain is universally constructible.

There is a substantial literature that further generalizes and strengthens Strassen's theorem. See Hirsch, Profeta, Roynette, and Yor (2011) for a survey. To our knowledge, Juillet (2016) is the only paper in this literature to study collections of distributions that are indexed on partially ordered sets. He presented examples that illustrate various ways in which Strassen's theorem does not generalize. Most closely related to the present study, Juillet (2016, Section 4.1) constructed a collection urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0437, where X is the diamond and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0438, such that the collection is increasing in the convex order but there does not exist a real-valued martingale on X with the given marginals. The distributions in Juillet's example are similar in spirit to (but distinct from) our example of a non-constructible belief allocation given in Section 3. Our Theorem 1 implies that the equivalence between urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0439 increasing in the convex order and induced by a martingale holds if and only if X is a forest.

Also related is Fill, Allen, and Machida (2001), who studied an analogue of the problem of Juillet (2016), but where the convex order is replaced by a generalization of first-order stochastic dominance. Specifically, Fill, Allen, and Machida (2001) considered collections of distributions indexed on a partially ordered set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0440, where each urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0441 is a distribution on a different partially ordered set S. They defined a notion of stochastic monotonicity for distributions on S that reduces to first-order stochastic dominance when S is totally ordered. A pair urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0442 is monotonicity equivalent if the following condition holds: a collection urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0443 is stochastically monotone if and only if there is a distribution over non-decreasing functions urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0444 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0445 is the marginal distribution of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0446. Monotonicity equivalence is analogous to universal constructibility, but with stochastic monotonicity in place of the Blackwell order. In the special case that S contains a sub-poset that is either a cycle or a crown, Fill, Allen, and Machida (2001) showed that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0447 is monotonicity equivalent if and only if X is a forest. The cases where X is a diamond or a crown also feature prominently in their proof, which follows a similar strategy of showing that if X is not a forest, then it contains a sub-poset on which monotonicity equivalence fails, and then extending the counterexample to all of X.

7.2 Connections to Information Economics

Our paper connects to various threads in the economics literature studying information and beliefs. In addition to the aforementioned classical literature on information orders, Bergemann and Morris (2016) studied an extension of the Blackwell order to type spaces, and Mu, Pomatto, Strack, and Tamuz (2019) considered comparisons of repeated experiments.

We contribute to the literature on higher order beliefs (Harsanyi (1967), Mertens and Zamir (1985), Brandenburger and Dekel (1993)). Specifically, we characterize when restrictions of the form “player i knows player j's type” place constraints on i's and j's first-order beliefs, beyond the obvious constraint that i must be Blackwell more informed than j.

We also study how signals can be combined to produce more informative signals. Gentzkow and Kamenica (2017) studied this issue in the context of a communication game with a receiver who combines information provided by multiple senders. Börgers, Hernando-Veciana, and Krähmer (2013) studied the interaction between signals from the perspective of whether signals are substitutes or complements.

We also contribute to the growing literature on information design (Kamenica and Gentzkow (2011), Bergemann and Morris (2016)). Arieli, Babichenko, Sandomirskiy, and Tamuz (2021) characterized feasible joint belief distributions of a group of agents in a binary state case. Mathevet and Taneva (2020) analyzed the implications of information design for organizational structure.

Finally, Shmaya and Yariv (2016) studied behavior by subjects in lab experiments when the experimental protocol potentially generates information. Their analysis led them to a question that is related to the result we present in Section 6.1. In particular, given data on how an agent behaves following any sequence of signal realizations, Shmaya and Yariv derived necessary and sufficient conditions for the behavior to be consistent with Bayesian updating if the data generating process, the agent's preferences, and the agent's prior are not known. On a similar topic, Molavi (2021) studied which belief dynamics are consistent with Bayesian updating, but allowed for the possibility that the agent has an incorrect model of the data generating process.

8 Conclusion

We conclude with a brief discussion of an important direction for future work. Our analysis has focused on the question of when an information hierarchy is universally constructible. That condition requires that every monotone experiment allocation is constructible. Of course, even when not every monotone experiment allocation is constructible, some are. A natural goal would therefore be to characterize, for a given information hierarchy, the set of constructible monotone experiment allocations. Such a characterization would be of particular interest in the case of the set-inclusion hierarchy (Figure 7), which would identify the exact sufficient and necessary conditions for rationalizability of reactions to unknown sources of information, as discussed in Section 6.1.

  • 1 This definition is equivalent to the prior-free formulation of an experiment as a map from the state to distributions over signal realizations.
  • 2 The standard representation of a partially ordered set as a directed graph encodes the partial order by placing an edge from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0002 if n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0003, that is, if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0004 and there is no urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0005 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0006. We associate with each information hierarchy the undirected version of this directed graph.
  • 3 Bayes plausibility requires that the agent's average belief does not vary across the sets of observed information sources. Blackwell monotonicity requires that when an agent observes additional sources, her beliefs become more dispersed.
  • 4 We then also say urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0022 is coarser than π.
  • 5 Note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0039. For any s with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0040, we have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0041. For those s with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0042, we can set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0043 to be any arbitrary belief.
  • 6 Throughout the paper, when we say two random variables are equal, we mean almost surely.
  • 7 This result first appears as Theorem 1 in Green and Stokey (1978). It is stated and proved using the notation in our paper by Gentzkow and Kamenica (2017).
  • 8 The mathematical details of this example are presented in the proof of Lemma 6 in the Appendix.
  • 9 It is standard to represent a partially ordered set as a directed graph, for example, as we do in Figure 1. Our main theorem relates constructibility of a hierarchy to a property of its undirected analogue; this is why we define urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0137 as the undirected version. Formally, the directed graph urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0138 is the pair urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0139, where N is the set of nodes, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0140 is the set of directed edges, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0141 if n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0142. A directed path from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0143 is an alternating sequence of nodes and directed edges urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0144, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0145, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0146, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0147, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0148 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0149, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0150 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0151, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0152. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0153 is the pair urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0154, where N is the set of nodes, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0155 is the set of undirected edges, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0156 if n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0157 or urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0158 covers n. An undirected path from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0159 is an alternating sequence of nodes and undirected edges urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0160, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0161, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0162, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0163, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0164 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0165, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0166 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0167, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0168.
  • 10 It is immediate that any constructible experiment allocation is monotone because urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0175.
  • 11 If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0185 is statistically redundant given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0186, we then also say urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0187 is statistically sufficient for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0188. It may be helpful to contrast statistical sufficiency/redundancy with the stronger notion of refinement/coarsening. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0189, we do not merely have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0190, we also have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0191 for any signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0192. For example, in Figure 3, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0193 is not a coarsening of π, but (as explained in the discussion below) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0194 is statistically redundant given π.
  • 12 For example, suppose that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0207 but the support of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0208 has more elements than the number of signal realizations in π. Then, no urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0209 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0210 could be a coarsening of π.
  • 13 In general, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0267 is taken to be the join of all signals previously assigned to nodes above the new node, which in this case is simply urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0268.
  • 14 In Brooks, Frankel, and Kamenica (2022), we illustrate that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0373 is not transitive and that, given two signals π and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0374, the equality urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0375 might hold for one prior but not for another.
  • 15 When there are only two sources, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0407, it is easy to show that the answer is indeed affirmative. Any reaction to two unknown sources of information that satisfies Bayes plausibility and Blackwell monotonicity is consistent with Bayesian updating.
  • 16 For instance, suppose that the CEO oversees two middle managers who share the oversight of an employee.
  • 17 Our inquiry also leads us to answer a pure graph-theoretic question regarding whether a partially ordered set contains subsets of a particular form. Similar questions have been studied in combinatorics and graph theory (e.g., Lu (2014)); within economics, results of this form are used by Curello and Sinander (2019) to study rankings on preference relations.
  • 18 We thank Ludvig Sinander and Aniko Oery for drawing our attention to this literature.
  • 19 It is straightforward to adapt Juillet's example to show that the diamond is not universally constructible. But unlike our example from Section 3, his example is not easily adapted for general UNPs.
  • 20 In the language of type spaces, “player i knows player j's type” is analogous to the refinement order. As discussed in Section 5.2, we also study relations that are weaker than refinement.
  • 21 The experiment is given as a sequence of ordered pairs of a probability and a belief.
  • 22 To see that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0977 is a mean-preserving spread of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0978, note that we can obtain urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0979 from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0980 by spreading the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0981 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0982 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0983 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0984 and leaving the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0985 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0986 unchanged. To see that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0987 is a mean-preserving spread of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0988, note that we can obtain urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0989 from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0990 by spreading the realizations urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0991 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0992 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0993 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0994 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0995 and leaving the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0996 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0997 unchanged. The argument for why urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0998 is symmetric.
  • 23 For any two random variables X and Y, if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1015 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1016, X must be a strict mean-preserving spread of Y.
  • Appendix: Proofs

    A.1 Proof of Lemma 1

    Proof of Lemma 1.Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0448 be a signal s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0449. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0450, there exists a garbling urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0451 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0452 urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0453, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0454. For every urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0455, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0456 denote the element of π s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0457. (This element exists since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0458.) Now, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0459, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0460 be a partition of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0461 s.t. ∀ω, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0462, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0463. Such a partition exists because urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0464 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0465. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0466 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0467. We now show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0468 satisfies (i) and (ii). To show (i), it suffices to show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0469 for every urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0470 and ω. We have

    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0471
    To show (ii), consider some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0472 s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0473 and some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0474. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0475, there is a partition of ŝ, say urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0476 s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0477 for all i. It will suffice to show that for every ω, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0478, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0479, we have
    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0480
    Consider some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0481. Note that there exists urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0482 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0483 since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0484. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0485. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0486, for every ω, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0487. Note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0488 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0489. Now, we know that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0490 for some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0491. By definition of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0492, we know that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0493 for some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0494. Hence,
    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0495
    where the last equality follows from the fact that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0496, and hence urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0497 if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0498 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0499 is empty if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0500. Hence,
    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0501
    Hence,
    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0502
    which completes the proof of Lemma 1. Q.E.D.

    A.2 Proof of Theorem 1: if

    Let H be an information hierarchy and suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0503 is a forest. Let β be a monotone experiment allocation on H. We will construct a monotone signal allocation that induces β. To do so, we construct a sequence of subhierarchies of H, adding nodes of H one by one, until we reach the full hierarchy H. At each step, we assign a signal to the newly added node and potentially reassign the signals allocated to the previously added nodes.

    We begin with some notation and terminology. A construction procedure f is a bijection from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0504 to N that specifies the order in which the nodes are added. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0505. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0506, we say that n was added at time l, and we refer to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0507 as the previously added nodes. For any subset urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0508, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0509, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0510, and
    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0511

    Now, consider a construction procedure f of the following form. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0512 be any node in N. For urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0513, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0514 be an arbitrary element of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0515. Note that for any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0516, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0517 is not empty.

    Claim 1.For each urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0518, there is at most one edge in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0519 between urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0520 and nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0521.

    Proof of Claim 1.Suppose toward contradiction that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0522 has an edge in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0523 with distinct n,urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0524. Since n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0525 both have an edge with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0526, they must belong to the same tree in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0527. Moreover, there must be a path between n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0528 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0529. To see this, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0530 be the node that was added earliest to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0531 among the nodes in the tree to which n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0532 belong. For every other node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0533 from this tree, we must have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0534, which in turn means that there is a path from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0535 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0536 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0537 and thus in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0538. Hence, there is a path from both n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0539 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0540 and thus a path between n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0541 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0542. So, there must be a path between n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0543 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0544 that does not go through urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0545. But, because urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0546 has an edge with both n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0547, there is another path from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0548 that goes through urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0549. However, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0550 is a forest, so there cannot be multiple paths between two nodes; we have reached a contradiction. Q.E.D.

    Now, given this construction procedure f, we assign signals to nodes as follows. At step l, we expand urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0551 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0552 and assign signals according to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0553. We proceed by induction and show that, as long as the signals previously allocated to nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0554 are monotone on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0555 and induce appropriate experiments (i.e., for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0556, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0557), then the urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0558 we specify is monotone on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0559 induces appropriate experiments.

    First, to node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0560, we assign an arbitrary signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0561 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0562. Note we are vacuously satisfying the base case of the induction argument: the signal allocation to the single node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0563 induces appropriate experiments. For urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0564, there are three cases: urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0565, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0566, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0567.

    We first consider the case urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0568 urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0569. Note that, by Claim 1, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0570 covers exactly one node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0571 (call this node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0572) and is not covered by any nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0573. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0574, there exists some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0575 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0576 (which follows from Theorem 1 of Green and Stokey (1978)). We set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0577 and we keep the signal allocation for nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0578 unchanged, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0579 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0580. It is clear that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0581 induces appropriate experiments (by the inductive hypothesis for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0582 and by construction for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0583). We also need to show that this signal allocation is monotone on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0584. Consider any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0585 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0586. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0587, either urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0588 or urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0589. In the former case, we know urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0590 by the inductive hypothesis. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0591, we know urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0592. By the inductive hypothesis, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0593 and thus urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0594. That completes the proof for this case.

    Now consider the case where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0595. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0596 be the node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0597 that covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0598. Denote urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0599, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0600, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0601. By Lemma 1, we know urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0602 such that (i) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0603, and (ii) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0604 s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0605, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0606. We set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0607. For urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0608, if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0609, we set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0610; otherwise, we set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0611. We need to show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0612 is monotone on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0613 and induces appropriate experiments. We have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0614. For urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0615, first consider cases where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0616, so urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0617. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0618 (recall that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0619 covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0620), by the inductive hypothesis, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0621; moreover, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0622; hence, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0623. For urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0624 s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0625, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0626. Since by the inductive hypothesis, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0627, we have established that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0628 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0629. We now need to show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0630 is monotone. Consider any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0631 s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0632. There are three cases. First, suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0633. In that case, we know that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0634 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0635. Since (by the inductive hypothesis) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0636, we know that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0637, and hence urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0638. The second case is where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0639 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0640. Then, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0641 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0642. Since (by the inductive hypothesis) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0643, we have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0644. Finally, suppose that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0645 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0646. Then, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0647 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0648. Since (by the inductive hypothesis) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0649, we have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0650.

    Finally, suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0651. We assign an arbitrary signal urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0652 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0653 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0654, and we keep the signal allocation to nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0655 unchanged, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0656 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0657. It is clear that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0658 induces appropriate experiments (by the inductive hypothesis for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0659 and by construction for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0660). Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0661 is not comparable to any node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0662, the fact that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0663 is a signal allocation on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0664 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0665 is monotone on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0666. This completes the proof. □

    A.3 Proof of Theorem 1: Only if

    Lemma 2.If an information hierarchy H is universally constructible and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0667 is a closed subhierarchy of H, then urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0668 is universally constructible.

    Proof of Lemma 2.Suppose H is an information hierarchy that is universally constructible under urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0669. Fix a state space Ω and a prior urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0670. Suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0671 is a closed subhierarchy of H. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0672 be a monotone experiment allocation on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0673. We need to construct a monotone signal allocation on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0674 that induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0675. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0676 defined as follows: (i) if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0677, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0678; (ii) if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0679 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0680 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0681, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0682; and (iii) if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0683 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0684 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0685, let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0686.

    Claim 2.β is monotone on H.

    Proof of Claim 2.Consider urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0687 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0688. We show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0689 by considering four exhaustive cases:

    If n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0690 are both in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0691, this follows from the fact that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0692 is monotone on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0693.

    If n and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0694 are both not urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0695, consider two subcases. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0696 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0697, then urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0698. Otherwise, since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0699 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0700 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0701, it must be that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0702 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0703, so urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0704.

    If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0705 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0706, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0707.

    Finally, if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0708 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0709, then there cannot exist an urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0710 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0711. If such an urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0712 did exist, then since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0713 is closed and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0714, we would have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0715, a contradiction. Thus, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0716. Q.E.D.

    Since β is a monotone experiment allocation on H and H is universally constructible, there exists a monotone signal allocation σ on H that induces β. Clearly, the restriction of σ to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0717 induces urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0718 and is monotone on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0719. Q.E.D.

    Recall that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0720 is the directed graph associated with the hierarchy H (see footnote ). The next result shows that if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0721 is a closed subhierarchy of H, then urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0722 is the subgraph of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0723 obtained by dropping edges with nodes that are not in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0724.

    Lemma 3.Fix a hierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0725 and a closed subhierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0726. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0727 be the set of edges in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0728. Then urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0729, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0730.

    Proof of Lemma 3.Fix urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0731. We need to show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0732 if and only if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0733. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0734, then n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0735 in H, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0736 and there is no urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0737 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0738. A fortiori, there is no urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0739 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0740; hence, n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0741 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0742, so urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0743. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0744, then n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0745 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0746. As a result, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0747. If there exists urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0748 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0749, then, since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0750 is closed, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0751, so n must not cover urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0752 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0753, a contradiction. As a result, n covers urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0754 in H as well, so urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0755. Q.E.D.

    The between set of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0756 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0757 is defined as
    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0758
    Clearly, the subhierarchy induced by the between set of any pair of nodes is closed. Moreover, a subhierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0759 is closed if and only if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0760 contains urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0761 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0762. We say that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0763 is simple if every node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0764 belongs to exactly one directed path in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0765 from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0766. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0767 is a minimal cyclic closed subhierarchy (MCC) of H if it is cyclic, closed, and there is no cyclic and closed subhierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0768 of H with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0769. We say that a cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0770 is a spanning cycle if every node in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0771 is in the cycle.

    Lemma 4.Fix a hierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0772 and a subhierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0773. Suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0774 is an MCC of H. Then, either (i) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0775 is a simple between set in H, or (ii) every cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0776 is a spanning cycle.

    Proof of Lemma 4.For this proof, all between sets are defined relative to H, and we simply write urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0777 for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0778. Similarly, by closed we mean closed in H. Note that by Lemma 3, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0779 is the subgraph of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0780 obtained by dropping edges with nodes that are not in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0781. In particular, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0782 is cyclic if and only if H contains a cycle whose nodes are in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0783. This fact is used freely below.

    We consider two cases. First, suppose there are two nodes urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0784 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0785 and there are two distinct paths from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0786 in the directed graph urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0787. Note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0788 is closed, so that these paths are in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0789 as well, so that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0790 is cyclic. Moreover, since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0791 is closed, we have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0792. Hence, since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0793 is an MCC, we must have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0794. It remains to show that the between set urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0795 is simple. Suppose to the contrary there is some node urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0796 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0797 belongs to two distinct paths from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0798 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0799. Then, there are either two distinct directed paths from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0800 or two distinct directed paths from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0801 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0802; thus, either urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0803 or urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0804 must be cyclic. Since both urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0805 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0806 are closed and strict subsets of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0807, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0808 must not be an MCC, so we have reached a contradiction. Thus, we have established that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0809 must be a simple between set.

    Now consider the second case where for every urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0810, there is at most one path from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0811 in the directed graph urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0812. Given a path P (either directed or undirected), let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0813 denote the set of nodes that appear in P. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0814 is an MCC, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0815 contains a cycle urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0816 where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0817, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0818. We will argue that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0819 is closed. The fact that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0820 will then follow directly from the hypothesis that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0821 is an MCC.

    Let us then suppose that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0822 is not closed, in order to reach a contradiction. Given a directed path urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0823, its undirected analogue is the undirected path urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0824 where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0825. Say that a directed path P in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0826 only contains edges in C if every edge in the undirected analogue of P is in C. A directed path P in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0827 is an external directed connection (EDC) from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0828 if (i) P is a directed path from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0829; (ii) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0830; and (iii) P does not only contain edges in C. Say that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0831 are an externally connected pair (ECP) if there is an external directed connection from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0832 or from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0833 to n. An ECP urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0834 is said to be minimally close if, for every urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0835, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0836 is an ECP only if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0837 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0838.

    Claim 3.Given any two nodes urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0839, if P is the unique directed path in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0840 from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0841, then urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0842.

    Proof of Claim 3.If there are two non-comparable nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0843, there would be two distinct directed paths from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0844. Hence, all nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0845 are comparable. Therefore, there is a directed path from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0846 whose nodes are urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0847. Since there is a unique directed path from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0848, the set of nodes in P is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0849. Q.E.D.

    Claim 4.There exist urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0850 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0851 is a minimally close ECP.

    Proof of Claim 4.We know there is a pair of nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0852 that are an ECP. Otherwise, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0853 would be closed. Moreover, since L is finite, there is a pair of nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0854 that are a minimally close ECP. Q.E.D.

    Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0855 be a minimally close ECP s.t. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0856. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0857 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0858. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0859 denote the external directed connection from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0860 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0861. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0862 be the undirected path urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0863 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0864 from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0865 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0866 in C. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0867 denote the undirected path from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0868 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0869 that “goes in the other direction” from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0870 in C, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0871. Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0872.

    Claim 5.urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0873 is cyclic.

    Proof of Claim 5.It suffices to show there are two distinct undirected paths from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0874 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0875 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0876. One path is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0877. The other path is the undirected analogue of the external directed connection urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0878. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0879 is external, these two undirected paths must be distinct. Q.E.D.

    Claim 6.S is closed.

    Proof of Claim 6.Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0880. We will show that Y is closed and that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0881.

    First we show that Y is closed. Consider any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0882 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0883. By definition of Y, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0884 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0885, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0886 for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0887. Hence, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0888 and thus urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0889.

    It remains to show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0890. Given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0891, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0892. Moreover, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0893. Hence, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0894.

    Now, consider some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0895. We need to show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0896. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0897, then we are done. Otherwise, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0898. We know urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0899 for some urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0900. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0901, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0902. Suppose instead that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0903. We will reach a contradiction. Let P denote the directed path from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0904 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0905 whose nodes include n. Because urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0906 is a minimally close ECP, path P must only include edges in C. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0907, the nodes in path P cannot be a subset of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0908. Thus, the nodes in P contain the nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0909, including urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0910 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0911. The sequence of nodes and edges in P between urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0912 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0913 is a directed path between those nodes, and thus is equal to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0914 (by uniqueness of the directed path). Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0915 contains an edge which is not in C, we have contradicted the hypothesis that P only contains edges in C. Thus, we have established that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0916. Q.E.D.

    We have established that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0917 is cyclic and closed and that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0918. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0919 is an MCC, it must be that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0920. But since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0921, it must be that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0922. All nodes in a between set are comparable, by the hypothesis that directed paths are unique, and so all nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0923 are comparable. Hence, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0924 must be the undirected analogue of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0925. This contradicts the hypothesis that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0926 is an ECP. Q.E.D.

    Lemma 5.If the hierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0927 is such that every cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0928 is a spanning cycle, then for any pair of nodes urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0929, there exist two undirected paths from n to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0930 such that the union of the nodes in the two paths is N and the intersection of the nodes in the two paths is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0931.

    Proof of Lemma 5.Since there exists a spanning cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0932, for any pair of nodes urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0933, there exist two paths urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0934 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0935 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0936 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0937 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0938, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0939 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0940. We need to show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0941. Suppose to the contrary that there exists urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0942 with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0943. We know there exist urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0944 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0945 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0946. Now, consider the path urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0947 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0948. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0949, this is a well-defined path. But it is a cycle that is not spanning and thus we have reached a contradiction. Q.E.D.

    Suppose a hierarchy H has nodes
    urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0950
    with urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0951, such that for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0952, (i) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0953, (ii) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0954, (iii) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0955, (iv) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0956 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0957 are comparable for every urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0958, and (v) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0959 is not comparable to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0960 if urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0961. In this case, we say that H is a union of non-comparable paths (UNP).

    Lemma 6.If the hierarchy H is a UNP, then H is not universally constructible.

    Proof of Lemma 6.Let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0962. We will present a monotone experiment allocation based on the allocation on the diamond in Section 3 and show that it is not constructible. Consider the experiment allocation given by urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0963; urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0964, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0965 for urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0966; and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0967 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0968 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0969. These are the experiments depicted in Figure 2, where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0970; urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0971; for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0972, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0973; and for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0974 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0975, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0976. Monotonicity of β is immediate from the mean-preserving spreads depicted in Figure 2.

    Toward a contradiction, suppose σ is monotone signal allocation that induces β. We begin by establishing that it must be the case that, along any undirected path from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-0999 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1000, the realized beliefs must be equal across the interior nodes on that path.

    Claim 7.For all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1001, we have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1002 for all urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1003.

    Proof of Claim 7.It suffices to establish that for any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1004, we have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1005. We know urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1006 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1007 are comparable. Assume that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1008; the case where urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1009 is analogous and omitted. Since σ is monotone, we have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1010. As the refinement order implies the belief-martingale property, we have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1011. Now suppose toward contradiction that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1012. We would conclude that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1013 is a strict mean-preserving spread of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1014. But that would mean that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1017 is not equal to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1018 in distribution and thus that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1019. Q.E.D.

    We will now reach a contradiction by establishing that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1020 is equal to zero and is strictly bigger than zero.

    Step 1: We show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1021. First, note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1022 since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1023 and the support of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1024 lies above 0. Moreover, since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1025, we must also have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1026. A similar argument establishes that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1027 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1028. Claim 7 tells us that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1029. Hence, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1030.

    Step 2: We show that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1031. It suffices to show that (a) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1032, and (b) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1033.

    Arguments analogous to the ones in Step 1 yield urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1034. Because urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1035, this in turn implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1036. Thus, Claim 7 tells us that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1037. Therefore, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1038, establishing part (a).

    Now, note that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1039 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1040. Moreover, since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1041, we have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1042, establishing (b). Q.E.D.

    Lemma 7.The crown is not universally constructible.

    Proof.Consider the experiment allocation given by urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1043, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1044, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1045, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1046. These experiments are depicted in Figure 5. To see that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1047 is a mean-preserving spread of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1048, note that we can obtain urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1049 from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1050 by (i) spreading the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1051 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1052 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1053 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1054, (ii) leaving the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1055 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1056 unchanged, and (iii) spreading the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1057 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1058 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1059. To see that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1060 is a mean-preserving spread of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1061, note that we can obtain urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1062 from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1063 by (i) leaving the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1064 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1065 unchanged, (ii) spreading the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1066 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1067 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1068 in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1069, and (iii) leaving the realization urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1070 unchanged. The argument for why urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1071 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1072 are mean-preserving spreads of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1073 is symmetric. Hence, β is monotone.

    We claim that β is not constructible. As before, consider the joint distribution of beliefs on urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1074 induced by any monotone signal allocation σ, and recall that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1075 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1076. Specifically, consider the conditional probability of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1077 given urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1078. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1079, we have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1080. Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1081, we have that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1082. Hence, the joint probability of urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1083 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1084 must be zero, that is, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1085. But, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1086 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1087, and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1088 implies urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1089. Hence, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1090, a contradiction. Q.E.D.

    Lemma 8.If the hierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1091 is cyclic and N is a simple between set in H, then H is not universally constructible.

    Proof of Lemma 8.Since urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1092 is cyclic and N is a simple between set, H must be a UNP. Therefore, Lemma 6 establishes that H is not universally constructible. Q.E.D.

    Lemma 9.If the hierarchy H is cyclic and not a crown, and every cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1093 is a spanning cycle, then H is not universally constructible.

    Proof of Lemma 9.Suppose that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1094 is cyclic and not a crown, and that every cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1095 is a spanning cycle. We say an element urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1096 of N is maximal if there is no urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1097 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1098. We say an element urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1099 of N is minimal if there is no urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1100 such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1101.

    Claim 8.There exist urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1102 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1103 in N that are maximal and minimal, respectively, such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1104 does not cover urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1105.

    Proof of Claim 8.Suppose toward contradiction that every maximal element covers every minimal element. Hence, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1106 is a complete bipartite graph of maximal and minimal elements. If there were only one maximal element or only one minimal element, there could not be a cycle. So, there must be at least two of each. Take any urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1107 consisting of exactly two maximal and two minimal elements, and let urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1108. urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1109 is a crown and therefore is cyclic. Moreover, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1110 is clearly closed, so that by Lemma 3, the nodes in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1111 are part of a cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1112 as well. Since every cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1113 is a spanning cycle, we must have urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1114, and thus H is a crown subhierarchy, and we have reached a contradiction. Q.E.D.

    By Claim 8, we can find urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1115 and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1116 in N that are maximal and minimal, respectively, such that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1117 does not cover urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1118. By Lemma 5, there are two distinct undirected paths P and Q in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1119 from urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1120 to urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1121 such that the union of the nodes in the two paths is N and the intersection of the nodes in the two paths is urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1122. As a result, H is a UNP. Lemma 6 therefore implies that H is not universally constructible. Q.E.D.

    Proof of Theorem 1: Only if.Suppose urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1123 is not a forest, that is, it contains a cycle. Since N is finite, H contains a subhierarchy urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1124 that is an MCC of H. By Lemma 4, either (i) urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1125 is a simple between set in H, or (ii) every cycle in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1126 is a spanning cycle. Consider case (i). Because urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1127 is closed and urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1128 is a simple between set in H, urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1129 is also a simple between set in urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1130. Thus, Lemma 8 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1131 is not universally constructible. Now consider case (ii). If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1132 is not a crown, then Lemma 9 implies that urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1133 is not universally constructible. If urn:x-wiley:00129682:media:ecta200444:ecta200444-math-1134 is a crown, Lemma 7 implies it is not universally constructible. Therefore, by Lemma 2, H is not universally constructible. Q.E.D.

      The full text of this article hosted at iucr.org is unavailable due to technical difficulties.