Measuring hierarchy

This paper presents a novel axiomatic approach to measuring and comparing hierarchical structures. Hierarchies are fundamental across a range of disciplines—from ecology to organizational science—yet existing measures of hierarchical degree often lack systematic criteria for comparison. We introduce a mathematically rigorous framework based on a simple partial pre-order over hierarchies, denoted as \(\succcurlyeq _H,\) and demonstrate its equivalence to intuitively appealing axioms for hierarchy comparisons. Our analysis yields three key results. First, we establish that for fixed-size hierarchies, one hierarchy is strictly more hierarchical than another according to \(\succcurlyeq _H\) if the latter can be derived from the former through a series of subordination removals. Second, we fully characterize the hierarchical pre-orders that align with \(\succcurlyeq _H\) using two fundamental axioms: Anonymity and Subordination Removal. Finally, we extend our framework to varying-size hierarchies through the introduction of a Replication Principle, which enables consistent comparisons across different scales.

This work is theoretical in nature; therefore, it does not involve dataset analysis or generation.

1. See, e.g., Mones et al. (2012), Corominas-Murtra et al. (2013), Krackhardt (1994), Trusina et al. (2004), Luo and Magee (2011) and Czégel and Palla (2015).

2. For additional context, see the surveys on income mobility by Maasoumi (1998), Fields and Ok (1999), and Jäntti and Jenkins (2015).

3. More precisely, \(h'{\setminus }\phi (\iota )\) can be obtained from some relabeling of \(h{\setminus }\iota \) by successive removals of subordination relations. While not explicitly mentioned in the remainder of this discussion, it is implicitly understood that two hierarchies are considered equivalent if they share the same structure, regardless of how their nodes are labeled.

4. Indeed, given h,  \(h',\) and \(h''\) in \({\mathscr {H}},\) we have

   $$ \begin{aligned}&h\succcurlyeq _Hh,&\\&[h\succcurlyeq _Hh'\; \& \;h'\succcurlyeq _Hh'']\Rightarrow [h_r\succcurlyeq _Hh'_r\; \& \;h'_r\succcurlyeq _Hh''_r]\Rightarrow h_r\succcurlyeq _Hh''_r\Rightarrow h\succcurlyeq _H h'', \end{aligned}$$

   where the relation “\(h_r\succcurlyeq _Hh''_r\)” follows from the transitivity of \(\succcurlyeq _H\) restricted to the domain \({\mathscr {H}}_n\) (Lemma 1).

   To see that \(\succcurlyeq _H,\) defined on \({\mathscr {H}},\) satisfies A, suppose that h and \(h'\) are hierarchies in \({\mathscr {H}}\) such that \(h'\) is a relabeling of h. Then h and \(h'\) have the same size, n. Since the restriction of \(\succcurlyeq _H\) to \({\mathscr {H}}_n\) satisfies A (Lemma 1), we have \(h\sim _H h'.\)

   To see that \(\succcurlyeq _H\) satisfies SR, suppose that h and \(h'\) are hierarchies in \({\mathscr {H}}\) and that \(h'\) can be obtained from h by removing a subordination relation. Then h and \(h'\) have the same size, n. Since the restriction of \(\succcurlyeq _H\) to \({\mathscr {H}}_n\) satisfies SR (Lemma 1), we have \(h\succ _H h'.\)

5. This assertion can be proven using a method entirely analogous to that employed in the proof from Footnote 4, which demonstrates that the extension of \(\succcurlyeq _H\) to \({\mathscr {H}}\) is reflexive, transitive, and satisfies the conditions A and SR.

6. Refer to Fig. 11 and its detailed explanation.

7. Poverty reduction failure is studied in Kanbur and Mukherjee (2007) and Chakravarty and D’Ambrosio (2013).

Authors and Affiliations

1. Department of Economics, Rutgers University, 75 Hamilton St., New Brunswick, NJ, 08901, USA

   Oriol Carbonell-Nicolau

Corresponding author

Correspondence to Oriol Carbonell-Nicolau.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This paper benefited from valuable comments and suggestions by the anonymous referees and the editors.

Appendix A

1.1 A.1 Preliminary lemmata

Lemma 3

For \(h,h'\in {\mathscr {H}}_n,\) \(h\sim _Hh'\) implies that there exists a bijection \(\phi \) from the set of individuals in h to the set of individuals in \(h'\) satisfying the following : 

1. (a)

   For each level-k individual i in h,  \(\phi (i)\) is a level-k individual in \(h'.\)

2. (b)

   For each individual i in h,  the number of immediate subordinates of i in h equals the number of immediate subordinates of \(\phi (i)\) in \(h'.\)

3. (c)

   For each individual i in h,  the set

   $$ \phi (I_{h(i)})=\{\phi (i):i\in I_{h(i)}\}, $$

   where \(I_{h(i)}\) denotes the set of all individuals in the sub-hierarchy h(i),  is equal to the set of all individuals in the sub-hierarchy \(h'(\phi (i)).\)

Proof

Since \(h\succcurlyeq _H h',\) there exists, by definition, a bijection \(\phi \) from the set of individuals in h to the set of individuals in \(h'\) satisfying the following:

1. (I)

   For each individual i in h such that \(\phi (i)\) is not a level-0 individual, the immediate supervisor of \(\phi (i)\) in \(h',\) \(p_{h'}(\phi (i)),\) links (via \(\phi ^{-1}\)) to a supervisor j of i in h: \(\phi ^{-1}(p_{h'}(\phi (i)))=j=p^l_h(i)\) for some l.

Similarly, since \(h'\succcurlyeq _H h,\) there exists a bijection \(\phi '\) from the set of individuals in \(h'\) to the set of individuals in h satisfying the following: for each individual i in \(h'\) such that \(\phi '(i)\) is not a level-0 individual, the immediate supervisor of \(\phi '(i)\) in h,  \(p_h(\phi '(i)),\) links (via \({\phi '}^{-1}\)) to a supervisor j of i in \(h'\): \({\phi '}^{-1}(p_h(\phi '(i)))=j=p^l_{h'}(i)\) for some l.

Let \(I_0\) (respectively, \(I'_0\)) be the set of all level-0 individuals in h (respectively, \(h'\)).

First, we show that

To see this, note that \(j\in \phi (I_0){\setminus } I'_0\) implies that there exist \(i\in I_0\) and a level-k individual j in \(h',\) where \(k>0,\) such that \(\phi (i)=j.\) But then \(\phi ^{-1}(p_{h'}(\phi (i)))\ne p^l_h(i)\) for any l,  which contradicts (I). Therefore, \(\phi (I_0){\setminus } I'_0=\emptyset ,\) which implies that \(\phi (I_0)\subseteq I'_0.\)

Similarly, we can show that \(\phi '(I'_0)\subseteq I_0.\)

Next, let \(I_l\) (respectively, \(I'_l\)) be the set of all level-l individuals in h (respectively, \(h'\)). Suppose that the containments \(\phi (I_l)\subseteq I'_l\) and \(\phi '(I'_l)\subseteq I_l\) have been proven for each \(l\in \{0,\ldots ,k\}\) and some \(k\ge 0.\) Then the containments \(\phi (I_{k+1})\subseteq I'_{k+1}\) and \(\phi '(I'_{k+1})\subseteq I_{k+1}\) can also be proven.

To see this, note first that, for each l,  the two containments \(\phi (I_l)\subseteq I'_l\) and \(\phi '(I'_l)\subseteq I_l\) imply that h and \(h'\) have the same number of level-l individuals. Indeed, if there were more level-l individuals in \(h',\) then \(\phi (I_l)\) would be a strict subset of \(I'_l,\) and, since both \(I_l\) and \(\phi (I_l)\) have the same cardinality, \(I_l\) would be a smaller set than \(I'_l,\) contradicting the containment \(\phi '(I'_l)\subseteq I_l.\) A similar contradiction can be obtained under the assumption that there are more level-l individuals in h.

Now, if \(j\in \phi (I_{k+1}){\setminus } I'_{k+1},\) since \(\phi (I_l)\subseteq I'_l\) and \(I_l\) and \(I'_l\) have the same cardinality for each \(l\in \{0,\ldots ,k\},\) we see that \(j\in \phi (I_{k+1}){\setminus }(\bigcup _{l=0}^{k+1}I'_l).\) Consequently, there exist \(i\in I_{k+1}\) and a level-\(\kappa '\) individual j in \(h',\) where \(\kappa '>k+1,\) such that \(\phi (i)=j.\) But then \(\phi ^{-1}(p_{h'}(\phi (i)))\) must be a level-\(\kappa \) individual in h,  where \(\kappa \ge k+1.\) Indeed, if \(\phi ^{-1}(p_{h'}(\phi (i)))\) where a level-l individual in h for some \(l\in \{0,\ldots ,k\},\) then \(\phi (I_l)\nsubseteq I'_l\) (since \(p_{h'}(\phi (i))=p_{h'}(j)\) is a level-(\(\kappa '-1)\) individual in \(h'\) and \(\kappa '>k+1\)), contradicting the assumed containment \(\phi (I_l)\subseteq I'_l.\) Consequently, \(\phi ^{-1}(p_{h'}(\phi (i)))\ne p^\ell _h(i)\) for any \(\ell ,\) which contradicts (I). Therefore, \(\phi (I_{k+1}){\setminus } I'_{k+1}=\emptyset ,\) which implies that \(\phi (I_{k+1})\subseteq I'_{k+1}.\)

Next, fix a level-k individual i in h. Since \(\phi (I_k)\subseteq I'_k,\) it follows that \(\phi (i)\) is a level-k individual in \(h'.\) This establishes (a).

To see that (b) holds, let i be an individual in h. Suppose that i is a level-k individual. Proceeding by contradiction, suppose that the number of immediate subordinates of i in h is not equal to the number of immediate subordinates of \(\phi (i)\) in \(h'.\) If he number of immediate subordinates of \(\phi (i)\) is greater, then (by (a)) there exists a subordinate j of \(\phi (i)\) linking (via \(\phi ^{-1}\)) to a level-\((k+1)\) subordinate \(\iota \) in h whose immediate supervisor, \(i^*,\) is not i. But then \(\phi (\iota )=j\) and \(\phi (i)\) is j’s immediate supervisor in \(h',\) and yet \(\phi (i)\) links (via \(\phi ^{-1}\)) to \(i\ne i^*,\) implying that i is not a supervisor of \(\iota ,\) which contradicts (I).

Hence, the number of immediate subordinates of i in h must be greater than or equal to the number of immediate subordinates of \(\phi (i)\) in \(h'.\)

If the number of immediate subordinates of i in h is greater than the number of immediate subordinates of \(\phi (i)\) in \(h',\) there exists an immediate subordinate \(\iota \) of i in h such that \(\phi (\iota )\)’s immediate supervisor in \(h',\) \(p_{h'}(\phi (\iota )),\) is not \(\phi (i).\) But then \(\phi ^{-1}(p_{h'}(\phi (\iota )))\) is a level-k individual different from i,  implying that \(\phi ^{-1}(p_{h'}(\phi (\iota )))\) is not a supervisor of \(\iota \) in h,  which contradicts (I).

Thus, the number of immediate subordinates of i in h is equal to the number of immediate subordinates of \(\phi (i)\) in \(h'.\) This establishes (b).

It only remains to prove (c). Fix an individual i in h,  and let \(I_{h(i)}\) (respectively, \(I_{h'(\phi (i))}\)) be the set of all individuals in the hierarchy h(i) (respectively, \(h'(\phi (i))\)). We must show that \(\phi (I_{h(i)})=I_{h'(\phi (i))}.\)

Suppose that i is a level-k individual. Note that it suffices to prove the following: Suppose that j is a level-\((k+l)\) individual in h(i) for \(l\ge 0.\) Then \(\phi (S_j)=S_{\phi (j)},\) where \(S_j\) (respectively, \(S_{\phi (j)}\)) represents the set of immediate subordinates of j (respectively, \(\phi (j)\)) in h (respectively, \(h'\)).

Suppose that j is a level-\((k+l)\) individual in h(i) for \(l\ge 0.\) Suppose that there exists \(\iota \in S_j\) such that \(\phi (\iota )\notin S_{\phi (j)}.\) Then, since \(\iota \) is a level-\((k+l+1)\) individual in h,  so that \(\phi (\iota )\) is a level-\((k+l+1)\) individual in \(h'\) (by (a)), \(\phi (\iota )\)’s immediate supervisor in \(h',\) \(p_{h'}(\phi (\iota )),\) is a level-\((k+l)\) individual in \(h'\) who links (via \(\phi ^{-1}\)) to a level-\((k+l)\) individual in h,  \(\phi ^{-1}(p_{h'}(\phi (\iota ))).\) Note that \(\phi ^{-1}(p_{h'}(\phi (\iota ))),\) being different from j (since \(\phi (\iota )\notin S_{\phi (j)}\) and so \(p_{h'}(\phi (\iota ))\ne \phi (j)\)), is not a supervisor of \(\iota \) in h. Since this contradicts (I), we see that \(\phi (S_j)\subseteq S_{\phi (j)}.\) But then \(\phi (S_j)=S_{\phi (j)},\) since \(S_j\) and \(S_{\phi (j)}\) (and hence \(\phi (S_j)\) and \(S_{\phi (j)}\)) have the same cardinality (by (b)). \(\square \)

Lemma 4

For \(h,h'\in {\mathscr {H}}_n,\) \(h\sim _Hh'\) implies that h is a relabeling of \(h'.\)

Proof

It suffices to show that there exists a bijection \(\phi \) from the set of individuals in h to the set of individuals in \(h'\) such that h(i) is a relabeling of \(h'(\phi (i))\) for each i in h.

Let \(\phi \) be the bijection given by Lemma 3. Let K be the largest level for which there are level-K individuals in h. Then all the level-K individuals in h have zero subordinates. By item (a) of Lemma 3, for any level-K individual i in h,  \(\phi (i)\) is a level-K individual in \(h';\) moreover, since \(\phi (i)\) has zero subordinates, item (b) of Lemma 3 implies that h(i) is a relabeling of \(h'(\phi (i)).\)

Suppose that h(i) has been shown to be a relabeling of \(h'(\phi (i))\) for each level-k individuals i in h,  where \(k\in \{K,K-1,\ldots ,1\}.\) Then h(i) is a relabeling of \(h'(\phi (i))\) for each level-\((k-1)\) individual i in h.

To see this, fix a level-\((k-1)\) individual i in h. Let \(S_i\) (respectively, \(S'_i\)) be the set of level-k subordinates of i (respectively, \(\phi (i)\)) in h (respectively, \(h'\)). If

were true, then, because h(j) is a relabeling of \(h'(\phi (j))\) for each \(j\in S_i,\) it would follow that h(i) is a relabeling of \(h'(\phi (i)).\) Thus, it suffices to show that \(\phi (S_i)=S'_i.\)

By items (a) and (c) of Lemma 3, we know that \(\phi (S_i)\) is a set of level-k individuals in \(h'\) contained in the set of all individuals in the sub-hierarchy \(h'(\phi (i)).\) Since \(S'_i\) is the set of all level-k individuals in \(h'(\phi (i)),\) item (a) of Lemma 3 gives \(\phi (S_i)\subseteq S'_i.\) But then \(\phi (S_i)=S'_i,\) since \(S_i\) and \(S'_i\) (and hence \(\phi (S_i)\) and \(S'_i\)) have the same cardinality (by item (b) of Lemma 3). \(\square \)

Lemma 5

For \(h,h'\in {\mathscr {H}}_n,\) if \(h'\) can be obtained from h by removing a subordination relation,  then \(h\succ _H h'.\)

Proof

We proceed by induction on n. The statement is clearly true if \(n=1.\) We now prove the statement for any \(n>1\) under the assumption that it is true for m-person hierarchies, where \(m\in \{1,\ldots ,n-1\}.\)

Because \(h'\) can be obtained from h by removing a subordination relation, there exists a level-k subordinate \(i^*\) in h,  where \(k\in \{1,\ldots ,K\}\) (and where K denotes the total number of levels in the hierarchy h), satisfying the following:

1. (i)

   If \(i^*\)’s immediate supervisor, \(p_h(i^*),\) is a level-0 individual in h,  then \(h'\) is the hierarchy in which the sub-hierarchy \(h(i^*)\) is no longer under \(p_h(i^*)\)’s supervision, \(i^*\) becomes a level-0 individual, and the sub-hierarchy that begins at \(i^*\) is \(h(i^*);\) \(h'\) is otherwise equal to h.

2. (ii)

   If \(i^*\)’s immediate supervisor in h,  \(p_h(i^*),\) is a not level-0 individual, then \(p_h(i^*)\) is an immediate subordinate of \(p^2_h(i^*),\) i.e., \(p_h(i^*)\in S_{p^2_h(i^*)}.\) In this case, \(h'\) is the hierarchy in which the sub-hierarchy \(h(i^*)\) is no longer under \(p_h(i^*)\)’s supervision, but rather under the direct supervision of \(p^2_h(i^*),\) so that \(i^*\) is no longer a level-k subordinate, but rather a level-\((k-1)\) subordinate in \(S_{p^2_h(i^*)},\) and the sub-hierarchy that begins at \(i^*\) is \(h(i^*);\) \(h'\) is otherwise equal to h.

First, we show that \(h\succcurlyeq _H h'.\) To see this, let \(\phi \) be the identity map from the set of individuals in h to the set of individuals in \(h'.\) It suffices to prove the following:

(\(*\)):

For each individual i in h such that \(\phi (i)\) is not a level-0 individual, the immediate supervisor of \(\phi (i)\) in \(h',\) \(p_{h'}(\phi (i)),\) links (via \(\phi ^{-1}\)) to a supervisor j of i in h: \(\phi ^{-1}(p_{h'}(\phi (i)))=j=p^l_h(i)\) for some l.

Note that if the sub-hierarchy \(h(i^*)\) is removed from h and the sub-hierarchy \(h'(\phi (i^*))=h'(i^*)\) is removed from \(h',\) the remaining hierarchies are identical. Therefore, for any individual i in h not in \(h(i^*),\) (\(*\)) holds.

Next, fix an individual i in \(h(i^*).\) If \(i\ne i^*,\) then, since the two sub-hierarchies \(h(i^*)\) and \(h'(i^*)\) are identical, and since \(\phi \) is the identity map, (\(*\)) holds.

It remains to prove (\(*\)) for \(i=i^*.\) Note that if \(\phi (i^*)=i^*\) is not a level-0 individual in \(h',\) then (b) must hold. But then the immediate supervisor of \(\phi (i^*)=i^*\) in \(h'\) is \(p^2_{h'}(i^*),\) which links (via \(\phi ^{-1}\)) to \(p^2_h(i^*)\) in h,  a supervisor of \(i^*\) in h,  implying that (\(*\)) holds.

Since \(h\succcurlyeq _H h',\) it remains to show that Proceeding by contradiction, \(h'\succcurlyeq _H h\) implies that \(h'\sim _H h.\) Consequently, \(h'\) is a relabeling of h (Lemma 4), contradicting that \(h'\) can be obtained from h by removing a subordination relation. \(\square \)

Lemma 6

Suppose that \(h,h'\in {\mathscr {H}}_n,\) and let \(I_0\) (respectively,  \(I'_0)\) be the set of level-0 individuals in h (respectively,  \(h').\) The following two statements are equivalent : 

1. (i)

   \(h\succcurlyeq _H h'.\)

2. (ii)

   There exists a finite partition of \(I'_0\) consisting of \(\#I_0\) elements, 

   $$ \{I'_1,\ldots ,I'_{\#I_0}\}, $$

   where \(\#I_0\) denotes the cardinality of \(I_0,\) such that for each \(i\in I_0,\) \(h(i)\succcurlyeq _H(h'(\iota ))_{\iota \in I'_i}.\)

Proof

Suppose that (ii) holds. Then there exists a finite partition of \(I'_0\) consisting of \(\#I_0\) elements,

such that for each \(i\in I_0,\) there exists a bijection \(\phi _i\) from the set of individuals in h(i) to the set of individuals in \((h'(\iota ))_{\iota \in I'_i}\) satisfying the following: for each individual j in h(i) such that \(\phi _i(j)\) is not a level-0 individual,

Define a function \(\phi \) from the set of individuals in h to the set of individuals in \(h'\) as follows:

We claim that \(\phi \) is a bijection. To see this, note first that if \(j'\) is an individual in \(h'\) then \(j'\) is an individual in the sub-hierarchy \(h'(i')\) for some \(i'\in I'_0.\) Since \(i'\in I'_0,\) there exists \(i\in I_0\) such that \(i'\in I'_i.\) Thus, \(j'\) is an individual in the sub-hierarchy \((h'(\iota ))_{\iota \in I'_i},\) and so there exists an individual j in the sub-hierarchy h(i) such that \(j=\phi ^{-1}_i(j').\) Because \(i\in I_0\) and \(j\in h(i),\) we see that

Hence, \(\phi \) is an onto map.

To see that \(\phi \) is one-to-one, note that for every j in h,  there is a unique \(i\in I_0\) such that j is an individual in the sub-hierarchy h(i),  and so there is a unique element \(I'_i\) of the partition in (10) and a unique individual \(i'\) in the sub-hierarchy \((h'(\iota ))_{\iota \in I'_i}\) such that \(\phi (j)=i'.\)

Thus, \(\phi \) is a bijection.

Next, fix an arbitrary individual j in h such that \(\phi (j)\) is not a level-0 individual. Then \(j\in h(i)\) for some \(i\in I_0\) and \(\phi (j)=\phi _i(j),\) where \(\phi _i\) is a bijection from the set of individuals in h(i) to the set of individuals in \((h'(\iota ))_{\iota \in I'_i}\) satisfying (11). Therefore, since

and

we have

and so (i) holds.

Now suppose that (i) holds. Then, there exists a bijection \(\phi \) from the set of individuals in h to the set of individuals in \(h'\) satisfying the following:

(\(*\)):

For each individual i in h such that \(\phi (i)\) is not a level-0 individual,

$$ \phi ^{-1}(p_{h'}(\phi (i)))=p^l_h(i),\quad {\text {for some }}\,l. $$

For each \(i\in I_0\) (respectively, \(i\in I'_0\)), let \(I_{h(i)}\) (respectively, \(I_{h'(i)}\)) be the set of all individuals in h(i) (respectively, \(h'(i)\)).

First, we show that

Fix \(i\in I'_0.\) Then \(\phi ^{-1}(i)\) is an individual in h. Let j be the level-0 supervisor of \(\phi ^{-1}(i)\) in h. It suffices to show that \(\phi ^{-1}(I_{h'(i)})\subseteq I_{h(j)}.\)

Proceeding by contradiction, suppose that there exists \(\iota \in \phi ^{-1}(I_{h'(i)}){\setminus } I_{h(j)}.\) Then \(\iota \in I_{h(\iota ^*)}\) for some \(\iota ^*\in I_0{\setminus }\{j\}.\) Note that \(\phi (\iota )\ne i,\) since \(\phi ^{-1}(i)\ne \iota .\) Since i is the only level-0 individual in \(h'(i),\) and since \(I_{h'(i)}\ni \phi (\iota )\ne i,\) \(\phi (\iota ),\) an individual in the sub-hierarchy \(h'(i),\) is not a level-0 individual. Therefore, by (\(*\)),

implying that

If \(p_{h'}(\phi (\iota ))\) is a level-0 individual, since \(p(\phi (\iota ))\in I_{h'(i)},\) then \(p(\phi (\iota ))=i\) (since i is the only level-0 individual in \(h'(i)\)); in this case, since \(\phi ^{-1}(i)\in I_{h(j)}\) and \(j\ne \iota ^*,\) \(\phi ^{-1}(p_{h'}(\phi (\iota )))=\phi ^{-1}(i)\) cannot be a member of \(I_{h(\iota ^*)},\) contradicting (13).

If \(p(\phi (\iota ))\) is not a level-0 individual, then, again applying (\(*\)), we see that

implying that

If \(p^2_{h'}(\phi (\iota ))\) is a level-0 individual, since \(p^2_{h'}(\phi (\iota ))\in I_{h'(i)},\) then \(p^2_{h'}(\phi (\iota ))=i;\) in this case, since \(\phi ^{-1}(i)\in I_{h(j)}\) and \(j\ne \iota ^*,\) \(\phi ^{-1}(p^2_{h'}(\phi (\iota )))=\phi ^{-1}(i)\) cannot be a member of \(I_{h(\iota ^*)},\) which contradicts (14).

If \(p^2(\phi (\iota ))\) is not a level-0 individual, again applying (\(*\)), we see that

implying that \(\phi ^{-1}(p^3_{h'}(\phi (\iota )))\in I_{h(\iota ^*)}.\) This argument can be reiterated until a contradiction is reached in finitely many steps.

This proves (12).

Next, we show that there exists a finite partition of \(I'_0\) consisting of \(\#I_0\) elements,

such that for each \(i\in I_0,\) we have

To see this, note that by (12), for each \(\iota \in I'_0,\) there exists \(j_\iota \in I_0\) such that

In addition, because \(\phi \) is a bijection, each \(j_\iota \) must be unique.

For \(i\in I_0,\) define

First, we show that

where each \(I'_i\) is defined by (16), is a partition of \(I'_0.\) First, note that for \(i,j\in I_0\) with \(i\ne j,\)

since \(j_\iota \) is uniquely defined for each \(\iota \in I'_0.\) Next, note that

To see this, note that the containment \(\bigcup _{i\in I_0}I'_i\subseteq I'_0\) is obvious, so we only need to show that \(\bigcup _{i\in I_0}I'_i\supseteq I'_0.\)

Suppose that \(\iota \in I'_0.\) Then \(\iota \in I'_{j_\iota },\) and so \(\iota \in \bigcup _{i\in I_0}I'_i.\) Thus, \(\bigcup _{i\in I_0}I'_i\supseteq I'_0.\)

Next, we prove (15) for each \(i\in I_0.\)

Fix \(i\in I_0.\) Suppose that \(j'\in \phi (I_{h(i)}).\) Then there exists \(j\in I_{h(i)}\) such that \(j'=\phi (j),\) implying that \(j'\in I_{h'(\iota )}\) for some \(\iota \in I'_0.\) If \(\iota \notin I'_i,\) then there exists \(j_\iota \in I_0{\setminus }\{i\}\) such that \(\phi ^{-1}(I_{h'(\iota )})\subseteq I_{h(j_\iota )}.\) Since \(j'\in I_{h'(\iota )},\) this implies that

But this contradicts the fact that \(j\in I_{h(i)}.\) Indeed, since \(j_\iota \ne i,\) we have

Therefore, we must have \(j'\in I_{h'(\iota )}\) for some \(\iota \in I'_i.\)

Hence, \(\phi (I_{h(i)})\subseteq \bigcup _{\iota \in I'_i}I_{h'(\iota )}.\)

Conversely, if \(j'\in I_{h'(\iota )}\) for some \(\iota \in I'_i,\) then the definition of \(I'_i\) in (16) entails that

implying that \(\phi ^{-1}(j')\in I_{h(i)},\) and so \(j'\in \phi (I_{h(i)}).\)

Consequently, \(\phi (I_{h(i)})\supseteq \bigcup _{\iota \in I'_i}I_{h'(\iota )}.\)

We conclude that (15) holds. Now let \(\phi \vert _{I_{h(i)}}\) be the restriction of \(\phi \) to \(I_{h(i)}.\)

By (15), \(\phi \vert _{I_{h(i)}}\) is a bijection from \(I_{h(i)}\) to \(\bigcup _{\iota \in I'_i}I_{h'(\iota )}.\)

By (\(*\)), \(\phi \vert _{I_{h(i)}}\) satisfies the following: for each individual j in h(i) such that \(\phi \vert _{I_{h(i)}}(j)\) is not a level-0 individual in \((h'(\iota ))_{\iota \in I'_i},\)

Consequently, \(h(i)\succcurlyeq _H(h'(\iota ))_{\iota \in I'_i}.\) Since i was arbitrary in \(I_0,\) this establishes (ii). \(\square \)

Lemma 7

Suppose that \(h,h'\in {\mathscr {H}}_n,\) and let \(I_0\) (respectively,  \(I'_0)\) be the set of level-0 individuals in h (respectively,  \(h').\) Then (i) implies (ii):

1. (i)

   \(h\succ _H h'.\)

2. (ii)

   For each \(i\in I_0,\) there exists \(I'_i\subseteq I'_0\) such that \(h(i)\succcurlyeq _H(h'(j))_{j\in I'_i};\) and there exists \(i^*\in I_0\) such that \(h(i^*)\succ _H(h'(j))_{j\in I'_{i^*}}.\)

Proof

Suppose that \(h\succ _H h'.\) Then \(h\succcurlyeq _H h',\) and so Lemma 6 implies that there exists a finite partition of \(I'_0\) consisting of \(\#I_0\) elements,

where \(\#I_0\) denotes the cardinality of \(I_0,\) such that for each \(i\in I_0,\) \(h(i)\succcurlyeq _H(h'(\iota ))_{\iota \in I'_i}.\)

If \((h'(\iota ))_{\iota \in I'_i}\succcurlyeq _Hh(i)\) for each \(i\in I_0,\) then \(h(i)\sim _H(h'(\iota ))_{\iota \in I'_i}\) for each \(i\in I_0,\) and so by Lemma 4, h(i) is a relabeling of \((h'(\iota ))_{\iota \in I'_i}\) for each \(i\in I_0.\) But then

are relabelings of each other, and so A implies that

a contradiction (recall that \(\succcurlyeq _H\) satisfies A by Proposition 1).

Therefore, there exists \(i^*\in I_0\) such that implying that \(h(i^*)\succ _H(h'(\iota ))_{\iota \in I'_{i^*}},\) and so (ii) holds. \(\square \)

1.2 A.2 Proof of Lemma 1

Lemma 1 is restated here for the reader’s convenience.

Lemma 1

The hierarchical pre-order \(\succcurlyeq _H\) defined on \({\mathscr {H}}_n\) is reflexive and transitive and satisfies A and SR.

Proof

Reflexivity follows immediately from the definition of \(\succcurlyeq _H.\)

Let \(I_{{\widetilde{h}}}\) represent the set of individuals in \({\widetilde{h}}\in \mathscr {H}_n.\)

To see that \(\succcurlyeq _H\) is transitive, suppose that

Then, there exist bijections \(\phi :I_h\rightarrow I_{h'}\) and \(\phi ':I_{h'}\rightarrow I_{h''}\) satisfying the following:

\(\{1\}\):

For each individual i in h such that \(\phi (i)\) is not a level-0 individual, the immediate supervisor of \(\phi (i)\) in \(h',\) \(p_{h'}(\phi (i)),\) links (via \(\phi ^{-1}\)) to a supervisor j of i in h,  i.e.,

$$ \phi ^{-1}(p_{h'}(\phi (i)))=j=p^l_h(i),\quad {\text {for some }}\,l. $$

\(\{2\}\):

For each individual i in \(h'\) such that \(\phi '(i)\) is not a level-0 individual, the immediate supervisor of \(\phi '(i)\) in \(h'',\) \(p_{h''}(\phi '(i)),\) links (via \({\phi '}^{-1}\)) to a supervisor j of i in \(h',\) i.e.,

$$ {\phi '}^{-1}(p_{h''}(\phi '(i)))=j=p^l_{h'}(i),\quad {\text {for some }}\,l. $$

Since \(\phi \) and \(\phi '\) are bijections, the composition \(\phi ^*:=\phi '\circ \phi \) is also a bijection (see, e.g., Blyth 1975, Theorem 5.10, p. 37). Thus, it suffices to show the following:

(\(\circ \)):

For each individual i in h such that \(\phi ^*(i)\) is not a level-0 individual, the immediate supervisor of \(\phi ^*(i)\) in \(h'',\) \(p_{h''}(\phi ^*(i)),\) links (via \({\phi ^*}^{-1}\)) to a supervisor j of i in h,  i.e.,

$$ {\phi ^*}^{-1}(p_{h''}(\phi ^*(i)))=j=p^l_h(i),\quad {\text {for some }}\,l. $$

Fix an individual i in h such that \(\phi ^*(i)\) is not a level-0 individual. Proceeding by contradiction, suppose that

Consider the sequence

This sequence can be subdivided into four-element cycles as follows:

The first and last elements of each cycle are individuals in h,  while the second and third elements of each cycle are individuals in \(h'.\) Moreover, by \(\{1\},\) the first and last elements of each cycle belong to the path connecting i and i’s level-0 supervisor in h,  i.e., if j is the first or the fourth element of a cycle, we have \(j=p^l(i)\) for some l. In addition, by construction, the second and third elements of every cycle belong to the path connecting \(\phi (i)\) and \(\phi (i)\)’s level-0 supervisor in \(h',\) i.e., if j is the second or the third element of a cycle, we have \(j=p^l_{h'}(\phi (i))\) for some l.

Note that each individual in the path connecting \(\phi (i)\) and \(\phi (i)\)’s level-0 supervisor in \(h'\) must eventually become the third element of a cycle. Hence, because

\({\phi '}^{-1}(p_{h''}(\phi ^*(i)))\) is equal to the third element of some cycle \(\ell .\) But then the fourth element of cycle \(\ell ,\) which can be expressed as

belongs to the path connecting i and i’s level-0 supervisor in h (as noted in the previous paragraph). Noting that

this contradicts our initial assumption in (17).

We conclude that (\(\circ \)) holds, implying that \(\succcurlyeq _H\) is transitive.

By Lemma 5, \(\succcurlyeq _H\) satisfies SR.

To see that \(\succcurlyeq _H\) satisfies A, let \(h'\) be a relabeling of h. Then there exists a bijection \(\phi :I_h\rightarrow I_{h'}\) with the following property: if each individual i in \(h'\) is assigned the label “\(\phi ^{-1}(i),\)” then the resulting hierarchy is identical to h.

It is easy to see that, for the bijection \(\phi ,\) the following condition is satisfied: for each individual i in h such that \(\phi (i)\) is not a level-0 individual, the immediate supervisor of \(\phi (i)\) in \(h',\) \(p_{h'}(\phi (i)),\) links (via \(\phi ^{-1}\)) to a supervisor j of i in h,  i.e.,

Hence, \(h\succcurlyeq _H h'.\)

A similar condition can be verified for the bijection \(\phi ^{-1}:I_{h'}\rightarrow I_h\): for each individual i in \(h'\) such that \(\phi ^{-1}(i)\) is not a level-0 individual, the immediate supervisor of \(\phi ^{-1}(i)\) in h,  \(p_h(\phi ^{-1}(i)),\) links (via \(\phi \)) to a supervisor j of i in \(h',\) i.e.,

Consequently, \(h'\succcurlyeq _H h\) and \(h\succcurlyeq _H h',\) implying that \(h\sim _H h'.\) \(\square \)

1.3 A.3 Proof of Theorem 1

Theorem 1

For \(h,h'\in {\mathscr {H}}_n,\) \(h\succ _H h'\) if and only if \(h'\) can be obtained from some relabeling of h by successive removals of subordination relations.

Proof

[Necessity.] First, we prove the “only if” part of the statement under the assumption that h has only one level-0 individual.

We proceed by induction on n. The statement is clearly true if \(n=1.\) We now prove the statement for any \(n>1\) under the assumption that it is true for m-person hierarchies, where \(m\in \{1,\ldots ,n-1\}.\)

Suppose that \(h\succ _H h'.\) We must show that \(h'\) can be obtained from some relabeling of h by successive removals of subordination relations.

Since \(h\succcurlyeq _H h',\) there exists a bijection \(\phi \) from the set of individuals in h to the set of individuals in \(h'\) satisfying the following:

(\(\blacksquare \)):

For each individual i in h such that \(\phi (i)\) is not a level-0 individual, the immediate supervisor of \(\phi (i)\) in \(h',\) \(p_{h'}(\phi (i)),\) links (via \(\phi ^{-1}\)) to a supervisor j of i in h,  i.e.,

$$ \phi ^{-1}(p_{h'}(\phi (i)))=j=p^l_h(i),\quad {\text {for some }}\, l. $$

Let the (unique) level-0 individual h be denoted by \(\iota .\) Then \(\phi (\iota )\) is a level-0 individual in \(h'\) (otherwise \(p_{h'}(\phi (\iota ))\) would not link (via \(\phi ^{-1}\)) to a supervisor of \(\iota ,\) contradicting (\(\blacksquare \))).

If \(\phi (\iota )\ne \iota ,\) the individuals in h can be relabeled so that \(\phi (\iota )=\iota .\) The resulting relabeling will be denoted again by h.

Let \(h{\setminus }\iota \) be the hierarchy resulting from removing individual \(\iota \) from h: in \(h{\setminus }\iota ,\) every j in the set \(S_\iota \) of all level-1 subordinates of \(\iota \) becomes a level-0 individual, and the sub-hierarchy that begins at j is h(j).

Let \(h'{\setminus }\iota \) be the hierarchy resulting from removing individual \(\iota \) from \(h'\):

• In \(h'{\setminus }\iota ,\) every j in the set of all level-1 subordinates of \(\iota \) becomes a level-0 individual, and the sub-hierarchy that begins at j is \(h'(j).\)

• The structure of \(h'\) remains otherwise intact, i.e., the sub-hierarchy that begins at any level-0 i other than \(\iota \) is \(h'(i).\)

Let \(\phi ^*\) be the restriction of \(\phi \) to the individuals in \(h{\setminus }\iota .\) Note that \(\phi ^*\) is a bijection between the individuals in \(h{\setminus }\iota \) and those in \(h'{\setminus }\iota .\) Moreover, because \(\phi \) satisfies \((\blacksquare )\) and \(\phi (\iota )=\iota ,\) \(\phi ^*\) has the following property: for each individual i in \(h{\setminus }\iota \) such that \(\phi ^*(i)\) is not a level-0 individual,

Thus, we have \(h{\setminus }\iota ,h'{\setminus }\iota \in {\mathscr {H}}_{n-1}\) and \(h{\setminus }\iota \succcurlyeq _Hh'{\setminus }\iota .\)

Suppose first that \(h'{\setminus }\iota \succcurlyeq _Hh{\setminus }\iota .\) Then, \(h{\setminus }\iota \sim _Hh'{\setminus }\iota ,\) and Lemma 4 implies that \(h{\setminus }\iota \) is a relabeling of \(h'{\setminus }\iota .\)

Since \(\iota \) is the only level-0 individual in h,  we can write

where \(I'_0\) denotes the set of all level-0 individuals in \(h'.\) Now, letting \(S_\iota \) (respectively, \(S'_\iota \)) be the set of level-1 subordinates of \(\iota \) in h (respectively, \(h'\)), we can write

Since \(h{\setminus }\iota \) is a relabeling of \(h'{\setminus }\iota ,\) there is no loss of generality in assuming that \(h{\setminus }\iota \) and \(h'{\setminus }\iota \) are identical (since the individuals in \(h{\setminus }\iota \) can always be relabeled in such a way that \(h{\setminus }\iota \) and \(h'{\setminus }\iota \) are identical). Hence,

Now let \(\{i_1,\ldots ,i_m\}\) be an enumeration of \(I'_0{\setminus }\{\iota \}\) and define the sequence of hierarchies \(h_0,\ldots ,h_m\) as follows:

• \(h_0=h.\)

• \(h_1\) is obtained from h by the removal of a subordination relation as follows: \(i_1\) is no longer a level-1 subordinate in h under the direct supervision of \(\iota ,\) but rather a level-0 individual, and the sub-hierarchy that begins at \(i_1\) is \(h(i_1);\) \(h_1\) is otherwise equal to h.

• \(h_2\) is obtained from \(h_1\) by removing a subordination relation as follows: \(i_2\) is no longer a level-1 subordinate in \(h_1\) under the direct supervision of \(\iota ,\) but rather a level-0 individual, and the sub-hierarchy that begins at \(i_2\) is \(h(i_2);\) \(h_2\) is otherwise equal to \(h_1.\)

  \(\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \vdots \)

• \(h_m\) is obtained from \(h_{m-1}\) by removing a subordination relation as follows: \(i_m\) is no longer a level-1 subordinate in \(h_{m-1}\) under the direct supervision of \(\iota ,\) but rather a level-0 individual, and the sub-hierarchy that begins at \(i_m\) is \(h(i_m);\) \(h_m\) is otherwise equal to \(h_{m-1}.\)

Since \(h_\ell \) is obtained from \(h_{\ell -1}\) by removing a 0each \(\ell \in \{1,\ldots ,m\},\) and since (18) and the definition of the sequence of hierarchies \(h_0,\ldots ,h_m\) entails \(h_m=h',\) we see that \(h'\) can be obtained from some relabeling of h by successive removals of subordination relations, as we sought.

Next, suppose that Since \(h{\setminus }\iota \succcurlyeq _Hh'{\setminus }\iota ,\) we see that \(h{\setminus }\iota \succ _Hh'{\setminus }\iota .\) Since \(h{\setminus }\iota ,h'{\setminus }\iota \in {\mathscr {H}}_{n-1}\) and \(h{\setminus }\iota \succ _Hh'{\setminus }\iota ,\) the induction hypothesis gives some relabeling of \(h{\setminus }\iota ,\) denoted again by \(h{\setminus }\iota ,\) such that

here (and in the remainder of the proof), for any two hierarchies \({\hat{h}}\) and \(\overline{h},\) “\({\hat{h}}\Leftarrow _{\textit{RS}}\overline{h}\)” means that “\({\hat{h}}\) can be obtained from \(\overline{h}\) by successive removals of subordination relations.”

Recall that h and \(h'\) can be expressed as

and that \(h{\setminus }\iota \) and \(h'{\setminus }\iota \) are expressible as

where \(S_\iota \) (respectively, \(S'_\iota \)) represents the set of level-1 subordinates of \(\iota \) in h (respectively, \(h'\)).

Because every removal of a subordination relation in the transition

affects only the players of one and only one of the sub-hierarchies in \((h(j))_{j\in S_\iota },\) there exists a partition

of the set \(S'_\iota \cup (I'_0{\setminus }\{\iota \})\) such that each \(I_j\) is a subset of the set of individuals in h(j) and

Each partition member \(I_j\) can be further partitioned into two sets: the members of \(I_j\) that are immediate subordinates of \(\iota \) in \(h',\) \(I^s_j,\) and the members of \(I_j\) that are not immediate subordinates of \(\iota \) in \(h',\) \(I^{\textit{ns}}_j\):

Using this notation, (19) can be rewritten as

Now let \(h''\) be the hierarchy obtained from the hierarchy

by adding individual \(\iota \) at the top, so that \(\iota \) is the only level-0 individual in \(h''\) and the level-1 subordinates of \(\iota \) are the members of

Similarly, let \(h^*\) be the hierarchy obtained from

by adding individual \(\iota \) at the top, so that \(\iota \) is the only level-0 individual in \(h^*\) and the level-1 subordinates of \(\iota \) are the members of \(S_\iota .\)

Note that (20) implies that

Consequently, since \(h^*=h=h(\iota ),\) we have

Note that, by successive removals of subordination relations in \(h'',\) we can, for any level-1 subordinate \(j'\) in \(\bigcup _{j\in S_\iota }I^{\textit{ns}}_j,\) move the sub-hierarchy \(h'(j')\) up to level 0,  thus obtaining the hierarchy

where \(h'''\) is a hierarchy defined as follows:

• \(h'''\) has only one level-0 individual, \(\iota .\)

• The level-1 subordinates of \(\iota \) are the members of \(\bigcup _{j\in S_\iota }I^s_j,\) and the sub-hierarchy that begins at any such level-1 subordinate \(j'\) is given by \(h'(j').\)

We therefore have

Moreover, since all the immediate subordinates of \(\iota \) in \(h'\) are the same as all the immediate subordinates of \(\iota \) in \(h'''\) and all the non-subordinates of \(\iota \) in \(h'\) are the same as all the non-subordinates of \(\iota \) in

we see that

This, together with (21)–(22), gives \(h'\Leftarrow _{\textit{RS}}h,\) as desired.

It remains to prove the “only if” part of the statement when h has more than one level-0 individual.

Suppose that \(h\succ _H h'.\) We must show that \(h'\) can be obtained from some relabeling of h by successive removals of subordination relations.

Let \(I_0\) (respectively, \(I'_0\)) be the set of level-0 individuals in h (respectively, \(h'\)). By Lemma 7, for each \(i\in I_0,\) there exists \(I'_i\subseteq I'_0\) such that \(h(i)\succcurlyeq _H(h'(j))_{j\in I'_i};\) and there exists \(i^*\in I_0\) such that \(h(i^*)\succ _H(h'(j))_{j\in I'_{i^*}}.\)

Let \(I^*\) be the set of all \(i\in I_0\) such that \(h(i)\succ _H(h'(j))_{j\in I'_i}.\) The set \(I^*\) is nonempty since \(i^*\in I^*.\) Note that, for each \(i\in I_0{\setminus } I^*,\) we have \(h(i)\sim _H(h'(j))_{j\in I'_i}.\)

From the first part of this proof, we obtain the following:

Therefore, since \(h(i)\sim _H(h'(j))_{j\in I'_i}\) for each \(i\in I_0{\setminus } I^*,\) and since the relation \(h(i)\sim _H(h'(j))_{j\in I'_i}\) implies that \((h'(j))_{j\in I'_i}\) is a relabeling of h(i) (Lemma 4), it follows that \(h'\) can be obtained from some relabeling of h by successive removals of subordination relations.

[Sufficiency.] Suppose that \(h'\) can be obtained from some relabeling of h,  denoted by \(\overline{h},\) by successive removals of subordination relations, i.e.,

for finitely many hierarchies \(h_1,\ldots ,h_L;\) here (and in the remainder of the proof), for any two hierarchies \({\hat{h}}\) and \(\underline{h},\) “\({\hat{h}}\leftarrow _{\textit{RS}}\underline{h}\)” means that “\({\hat{h}}\) can be obtained from \(\underline{h}\) by removing a subordination relation.” We must show that \(h\succ _H h'.\)

By Lemma 5,

By reflexivity and transitivity of \(\succcurlyeq _H\) (Lemma 1), it follows that \(\overline{h}\succ _Hh'\) (Sen 2017, Lemma 1*a, p. 56). Moreover, since \(\overline{h}\) is a relabeling of h,  Lemma 1 gives \(h\sim _H\overline{h}.\) Consequently,

implying that \(h\succ _Hh'\) (Sen 2017, Lemma 1*a, p. 56). \(\square \)

1.4 A.4 Proof of Proposition 1

Proposition 1

The hierarchical pre-order \(\succcurlyeq _s\) defined on \({\mathscr {H}}_n\) is reflexive and transitive and satisfies A and SR.

Proof

Reflexivity follows immediately from the definition of \(\succcurlyeq _s.\)

To see that \(\succcurlyeq _s\) is transitive, suppose that

Then, letting \(I_{{\hat{h}}}\) represent the set of individuals in hierarchy \({\hat{h}},\) there exist bijections \(\phi :I_h\rightarrow I_{h'}\) and \(\phi ':I_{h'}\rightarrow I_{h''}\) satisfying the following:

• For each individual i in h,  the number of supervisors of i in h,  \(\#_hi,\) is greater than or equal to the number of supervisors of \(\phi (i)\) in \(h',\) \(\#_{h'}\phi (i).\)

• For each individual i in \(h',\) the number of supervisors of i in \(h',\) \(\#_{h'}i,\) is greater than or equal to the number of supervisors of \(\phi '(i)\) in \(h'',\) \(\#_{h''}\phi '(i).\)

Since \(\phi \) and \(\phi '\) are bijections, the composition \(\phi ^*:=\phi '\circ \phi \) is also a bijection (see, e.g., Blyth 1975, Theorem 5.10, p. 37). Moreover, for each individual i in h,  we have

Consequently, for each individual i in h, 

implying that \(h\succcurlyeq _sh''.\)

To see that \(\succcurlyeq _s\) satisfies A, suppose that \(h'\) is a relabeling of h. Then there exists a bijection \(\phi :I_h\rightarrow I_{h'}\) with the following property: if each individual i in \(h'\) is assigned the label “\(\phi ^{-1}(i),\)” then the resulting hierarchy is identical to h.

For the bijection \(\phi ,\) the following condition is satisfied: for each i in h,  the number of supervisors of i in h is equal to the number of supervisors of \(\phi (i)\) in \(h'.\)

Hence, \(h\succcurlyeq _s h'.\)

A similar condition can be verified for the bijection \(\phi ^{-1}:I_{h'}\rightarrow I_h\): for each individual i in \(h',\) the number of supervisors of i in \(h'\) is equal to the number of supervisors of \(\phi ^{-1}(i)\) in h.

Consequently, \(h'\succcurlyeq _s h\) and \(h\succcurlyeq _s h',\) implying that \(h\sim _s h'.\)

It remains to show that \(\succcurlyeq _s\) satisfies SR. Suppose that \(h'\) can be obtained from h by removing a subordination relation. Then there exists a level-k subordinate \(i^*\) in h,  where \(k>0,\) satisfying the following:

1. (i)

   If \(i^*\)’s immediate supervisor in h,  \(p_h(i^*),\) is a level-0 individual, then \(h'\) is the hierarchy in which the sub-hierarchy \(h(i^*)\) is no longer under \(p_h(i^*)\)’s supervision, \(i^*\) becomes a level-0 individual, and the sub-hierarchy that begins at \(i^*\) is \(h(i^*);\) \(h'\) is otherwise equal to h.

2. (ii)

   If \(i^*\)’s immediate supervisor in h,  \(p_h(i^*),\) is a not level-0 individual, then \(p_h(i^*)\) is an immediate subordinate of \(p^2_h(i^*),\) i.e., \(p_h(i^*)\in S_{p^2_h(i^*)}.\) In this case, \(h'\) is the hierarchy in which the sub-hierarchy \(h(i^*)\) is no longer under \(p_h(i^*)\)’s supervision, but rather under the direct supervision of individual \(p^2_h(i^*),\) so that \(i^*\) is no longer a level-k subordinate, but rather a level-\((k-1)\) subordinate in \(S_{p^2_h(i^*)},\) and the sub-hierarchy that begins at \(i^*\) is \(h(i^*);\) \(h'\) is otherwise equal to h.

We must show that \(h\succ _s h'.\)

Note that the only individuals whose set of supervisors is altered as a result of the subordination removals specified in items (i) and (ii) are those in the sub-hierarchy \(h(i^*)\) of h containing \(i^*\) and all of \(i^*\)’s subordinates. Moreover, after the removal of a subordination relation, the individuals in \(h(i^*)\) are left with less supervisors. Consequently, if i is an individual in h not in the sub-hierarchy \(h(i^*),\) the number of supervisors of i in h is equal to the number of supervisors of i in \(h',\) while if i is in \(h(i^*),\) the number of supervisors of i in h is greater than the number of supervisors of i in \(h',\) implying that \(h\succcurlyeq _s h'.\)

It remains to show that Proceeding by contradiction, suppose that \(h'\succcurlyeq _s h.\) Then there exists a bijection \(\varphi :I_{h'}\rightarrow I_h\) such that for each i in \(h',\) the number of supervisors of i in \(h'\) is greater than or equal to the number of supervisors of \(\varphi (i)\) in h.

Let \(I^*\) be the (nonempty) set of all individuals in \(h(i^*)\) who have the most supervisors in h among all the individuals in \(h(i^*).\) Let \(s^*\) be the number of supervisors in h for the individuals in \(I^*.\) Then \(s^*-1\) is the number of supervisors in \(h'\) for the individuals in \(I^*\) (since \(h'\) can be obtained from h by removing a subordination relation and (i) and (ii) hold).

Let \(\overline{s}\) be the maximum number of supervisors that an individual in h can have. Note that \(\overline{s}\ge s^*.\)

We claim that if \(\overline{s}>s^*,\) then \(\varphi (I'_{\overline{s}})=I_{\overline{s}}.\)

To see this, note that if \(\overline{s}>s^*,\) then all the individuals in h with \(\overline{s}\) supervisors are not in the sub-hierarchy \(h(i^*),\) and so the number of individuals in h with \(\overline{s}\) supervisors, denoted by \(I_{\overline{s}},\) is equal to the number of individuals in \(h'\) with \(\overline{s}\) supervisors, denoted by \(I'_{\overline{s}}.\)

This implies that \(\varphi (I'_{\overline{s}})\supseteq I_{\overline{s}}.\) Indeed, if that were not the case, there would exist an individual \(\iota \in I_{\overline{s}}{\setminus }\varphi (I'_{\overline{s}}),\) i.e., \(\iota \) would have \(\overline{s}\) supervisors in h and any individual in \(h'\) with \(\overline{s}\) supervisors would link, via \(\varphi ,\) to an individual in h other than \(\iota .\) But since \(I_{\overline{s}}=I'_{\overline{s}},\) this would imply that for some individual in \(h'\) with less than \(\overline{s}\) supervisors, \(\iota ',\) \(\varphi (\iota ')=\iota ,\) contradicting the fact that for each i in \(h',\) the number of supervisors of i in \(h'\) is greater than or equal to the number of supervisors of \(\varphi (i)\) in h.

Since \(I_{\overline{s}}=I'_{\overline{s}}\) and \(\varphi \) is a bijection, \(\varphi (I'_{\overline{s}})\) and \(I_{\overline{s}}\) have the same cardinality, and so the containment \(\varphi (I'_{\overline{s}})\supseteq I_{\overline{s}}\) implies that \(\varphi (I'_{\overline{s}})=I_{\overline{s}}.\)

Similarly, for any \(\ell \in {\mathbb {N}}\) for which \(\overline{s}-\ell >s^*,\) we have \(\varphi (I'_{\overline{s}-\ell })=I_{\overline{s}-\ell }\) (where \(I_{\overline{s}-\ell }\) (respectively, \(I'_{\overline{s}-\ell }\)) represents the set of all individuals in h (respectively, \(h'\)) with \(\overline{s}-\ell \) supervisors).

Next, note that there exists \(\ell ^*\in \{0,1,2,\ldots \}\) such that \(\overline{s}-\ell ^*=s^*,\) since \(\overline{s}\ge s^*.\) Therefore, \(I_{\overline{s}-\ell ^*}=I_{s^*}.\) Moreover, since \(I_{s^*}\) is the set of all individuals in h with \(s^*\) supervisors, and since \(I^*\) is the set of all individuals in the sub-hierarchy \(h(i^*)\) of h with \(s^*\) supervisors, it follows that \(I_{s^*}\) contains \(I^*.\)

Next, we show that \(I'_{s^*}=I_{s^*}{\setminus } I^*.\) To see this, suppose that \(i\in I'_{s^*}.\) Then i is not in \(h(i^*).\) Indeed, if i were in \(h(i^*),\) since i has \(s^*\) supervisors in \(h',\) then i would have \(s^*+1\) supervisors in h,  contradicting the fact that those individuals in \(h(i^*)\) who have the most supervisors in h have \(s^*\) supervisors.

Since i is not in \(h(i^*),\) we have \(i\notin I^*\) (since the members of \(I^*\) are also in \(h(i^*)\)). Now, because \(h'\) can be obtained from h by removing a subordination relation and (i) and (ii) hold, and since the removal of a subordination relation specified in items (i) and (ii) does not affect the number of supervisors for those individuals not in \(h(i^*),\) \(i\in I'_{s^*}\) implies \(i\in I_{s^*}.\) Thus, \(i\in I_{s^*}{\setminus } I^*,\) and so \(I'_{s^*}\subseteq I_{s^*}{\setminus } I^*.\)

Conversely, suppose that \(i\in I_{s^*}{\setminus } I^*.\) Then i is not in \(h(i^*)\) (since \(I^*\) is the set of all individuals in \(h(i^*)\) who have \(s^*\) supervisors in h). Therefore, because the removal of a subordination relation specified in items (i) and (ii) does not affect the number of supervisors for those individuals not in \(h(i^*),\) we have \(i\in I'_{s^*}.\) Hence, \(I'_{s^*}\supseteq I_{s^*}{\setminus } I^*.\)

Now, since \(I'_{s^*}=I_{s^*}{\setminus } I^*\) and \(I^*\) is nonempty, it follows that the number of individuals in h with \(s^*\) supervisors exceeds the number of individuals in \(h'\) with \(s^*\) supervisors. Consequently, using the fact (proven earlier) that

we see that there exists some individual \(\iota \) in \(h'\) with less than \(s^*\) supervisors whose corresponding individual in h,  \(\varphi (\iota ),\) has \(s^*\) supervisors. But this contradicts the fact that the number of supervisors of \(\iota \) in \(h'\) is greater than or equal to the number of supervisors of \(\varphi (\iota )\) in h.

We conclude that

Since \(h\succcurlyeq _s h'\) and we see that \(h\succ _p h'.\) \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions