Introduction
Modeling user preferences as probability distributions over rankings is a fundamental task in recommendation systems and social choice theory. The Mallows model is widely regarded as the standard for such distributions. However, a significant computational barrier exists: performing exact inference—calculating the probability that a user's preferences, expressed as a partial order (poset), are consistent with the model—is #P-complete. This complexity arises because a single poset can represent an exponential number of linear rankings.
The RIMDP Algorithm
To address this, we introduce RIMDP, a dynamic programming algorithm designed for the Repeated Insertion Model (RIM), a generative framework that includes the Mallows model as a special case. RIM constructs rankings by inserting items one by one into a list according to specific insertion probabilities.
The RIMDP algorithm mirrors this generative process. At each insertion step $i$, the algorithm maintains a state representing the probability of all consistent placements for the items currently "active" in the constraints.
Cover Width and Complexity
The efficiency of RIMDP is governed by a novel structural metric called cover width ($cw$). Cover width measures how many items in a partial ranking are directly related to items yet to be inserted. We demonstrate that RIMDP runs in $O(m^{cw(\sigma)+2})$ time, where $m$ is the number of items. This implies that if the cover width remains bounded by a constant, the inference problem becomes polynomially tractable.
This finding highlights that the difficulty of inference depends not just on the preference structure itself, but on its alignment with the model's reference ranking $\sigma$. When preferences align well with $\sigma$, the cover width remains small, enabling fast computation.
Empirical Results
We evaluated RIMDP using synthetic workloads with reference rankings of lengths $m \in \{30, 60, 100\}$. The results confirm that runtime is primarily driven by cover width rather than the total number of items or traditional poset metrics like width or density.
As shown in the experimental data, for $m=30$, the algorithm successfully processes posets with cover widths up to 15 within a 20-minute threshold. As the reference ranking length increases to $m=100$, the tractable cover width threshold shifts to approximately 6. Furthermore, the algorithm exhibits excellent scalability; a multi-threaded implementation achieved nearly linear speedup (up to 12x on a 12-core processor), making it suitable for high-performance environments.
Conclusion
RIMDP provides a robust framework for exact inference in ranking models by exploiting the sequential nature of the Repeated Insertion Model. By identifying cover width as the key complexity driver, this work offers a clear path for determining the tractability of preference modeling tasks. Future research will explore extending these techniques to more complex hierarchical models and investigating the parameterized complexity of the inference problem.
Summary updated