A Restricted Markov Tree Model for Inference and Generation in Social Choice with Incomplete Preferences

We introduce a probabilistic graphical model of ranked preferences for social choice based on a restricted version of a kth-order Markov tree. The system is similar to Plackett's model, and is based on the intuition that, in some domains, an agent's next most preferred alternative is highly predictable given a few of the immediately preceding alternatives. We provide a bound on the data requirements to learn the parameters of such a model and show eventual consistency between most probable sequences of the model and both the centroid of a Mallows model and the induced ranking of a RUM, theoretically and on artificial data; this is followed by a full evaluation of the model as a social choice system, including comparisons with existing approaches on 6 real world datasets. An application of the system to a simulated multiagent coordination task is also demonstrated, in which the proposed system offers pronounced advantages over existing approaches.