  Partial orders are a natural model for the social hierarchies that may
constrain "queue-like" rank-order data. However, the computational cost of
counting the linear extensions of a general partial order on a ground set with
more than a few tens of elements is prohibitive. Vertex-series-parallel partial
orders (VSPs) are a subclass of partial orders which admit rapid counting and
represent the sorts of relations we expect to see in a social hierarchy.
However, no Bayesian analysis of VSPs has been given to date. We construct a
marginally consistent family of priors over VSPs with a parameter controlling
the prior distribution over VSP depth. The prior for VSPs is given in closed
form. We extend an existing observation model for queue-like rank-order data to
represent noise in our data and carry out Bayesian inference on "Royal Acta"
data and Formula 1 race data. Model comparison shows our model is a better fit
to the data than Plackett-Luce mixtures, Mallows mixtures, and "bucket order"
models and competitive with more complex models fitting general partial orders.
