Bayesian inference for partial orders from random linear extensions: power relations from 12th Century Royal Acta

Technical Summary: Bayesian Inference for Partial Orders from Random Linear Extensions

Problem Statement
The paper addresses the statistical challenge of inferring a time-evolving social hierarchy from rank-order data where the underlying structure is not necessarily a complete (total) order. The authors analyze 371 witness lists from 12th-century English and Norman Royal Acta (legal documents), recording the order in which 67 bishops were listed. Historians hypothesize that this ordering reflects a social hierarchy based on status, seniority, and political influence. However, the data is noisy, incomplete (subsets of bishops appear in each list), and the underlying hierarchy may contain incomparable pairs of actors (a partial order), rather than a single linear ranking. Existing models for rank data, such as Mallows and Plackett-Luce, typically assume a total order or context-independent probabilities, which may be inappropriate for this historical context where transitivity is expected but the order is partial.

Methodology
The authors propose a Bayesian Hidden Markov Model (HMM) where the latent state is an evolving partial order (poset) and the observed data are random linear extensions of that poset.

1. Latent Variable Parameterization:

   • The poset at time $t$, denoted $h(t)$, is generated from a latent $K$-dimensional status matrix $Z(t)$.
   • For each bishop $j$, a latent authority vector $U^{(t)}_j$ evolves over time as a vector autoregression (VAR) of order 1.
   • A covariate effect $\beta_{s_{t,j}}$ based on seniority is added to the authority vector to form the status vector: $Z^{(t)}_j = U^{(t)}_j + \mathbf{1}_K \beta_{s_{t,j}}$.
   • The poset $h(t)$ is defined by the intersection of $K$ total orders derived from the columns of $Z(t)$. Bishop $i$ precedes $j$ in the poset if and only if $Z^{(t)}_{i,k} > Z^{(t)}_{j,k}$ for all $k=1,\dots,K$.
   • The dimension $K$ is chosen as $\lfloor D/2 \rfloor$ (where $D$ is the maximum number of active bishops), ensuring the model can represent any possible poset (universal representation property).

2. Observation Model (Queue-Jumping):

   • The observed lists are modeled as "noisy" linear extensions of the true poset.
   • The authors introduce a "queue-jumping" mechanism: with probability $p$, the next actor in the list is chosen uniformly at random (ignoring the poset constraints); otherwise, the actor is chosen according to a random linear extension of the remaining sub-order.
   • This allows for "noise" where the observed order contradicts the underlying hierarchy, while maintaining the constraint that valid linear extensions are more probable.
   • The model handles incomplete lists (subsets of bishops) by conditioning on the sub-order induced by the present actors.

3. Priors and Consistency:

   • The prior on the poset process is constructed to be marginally consistent, meaning the distribution of a sub-order (induced by a subset of actors) is consistent with the distribution of the full order. This is achieved by using a specific prior on the latent vectors $U$ and the correlation parameter $\rho$.
   • A hyperparameter $\rho$ controls the "depth" of the poset (the length of the longest chain). The prior is designed to be non-informative regarding depth, avoiding the concentration on depth-3 posets seen in uniform priors over all posets.
   • The seniority effects $\beta$ are constrained to be ordered ($\beta_1 > \beta_2 > \dots$) to reflect historical expectations that seniority correlates with status, though unconstrained models are also tested.

4. Inference:

   • Posterior inference is performed using Markov Chain Monte Carlo (MCMC) with Metropolis-Hastings updates.
   • The likelihood involves counting linear extensions, a #P-complete problem. The authors utilize recursive counting algorithms (specifically the lecount package) which are feasible for the small number of actors ($m \le 22$) in this dataset but limit scalability to larger problems.

Key Contributions

• Novel Model Class: The paper introduces a general framework for modeling time-series rank data where the underlying structure is a partial order, generalizing existing models like Mallows and Plackett-Luce.
• Marginal Consistency: The authors derive and prove that their latent-variable prior for posets is marginally consistent, a property often violated in ad-hoc priors for partial orders.
• Universal Representation: They demonstrate that with a latent dimension $K \ge \lfloor D/2 \rfloor$, the model can represent any possible poset time-series, ensuring no structural bias against complex hierarchies.
• Historical Application: This is the first statistical analysis of 12th-century Royal Acta witness lists to explicitly model the social hierarchy as a partial order, separating the effects of seniority from personal authority.

Results

• Model Fit: The poset-based model outperforms simpler alternatives (Vertex-Series-Parallel orders, Bucket Orders) and a Plackett-Luce time-series mixture model in terms of goodness-of-fit (measured by Leave-One-Out Cross Validation and Bayes Factors).
• Seniority vs. Authority: The analysis confirms a strong dependence of status on seniority, with the effect of seniority decreasing as the rank number increases. However, the model successfully isolates "authority" (deviations from seniority).
• Historical Insights:
  • Norman Bishops: The model detects a decline in the status of Norman bishops (e.g., from Avranches, Bayeux, Évreux) relative to English bishops starting in the early 12th century, a trend not previously quantified.
  • Political Influence: The status of specific bishops, such as Henry de Blois (brother of King Stephen) and Nigel of Ely, fluctuates in ways that correlate with political favor or disgrace, independent of their seniority.
  • Hierarchy Structure: The reconstructed consensus posets are relatively shallow, typically consisting of a few groups of middle-ranked bishops with a small number of actors above or below, rather than a deep, rigid hierarchy.

Significance and Claims
The paper claims that its primary contribution is the development of a statistically rigorous method for inferring evolving partial orders from noisy, incomplete rank data. By applying this to historical Acta, the authors provide quantitative evidence for how social hierarchies functioned in the 12th century, specifically distinguishing between structural seniority and fluid political authority.

The authors are modest regarding the computational scalability of their method, acknowledging that the #P-complete nature of counting linear extensions limits the model to datasets with small numbers of actors (around 20). They suggest that for larger datasets, restricted classes of posets (like VSP or Bucket Orders) might be necessary compromises. They also note that while their model fits the data well, the "noise" model assumes errors occur in one direction (queue jumping), and future work could explore bidirectional noise models.

Ultimately, the paper argues that assuming a total order (as in standard ranking models) is unjustified for this type of social data and that partial order models offer a more accurate and interpretable representation of historical social structures.