• $n$ possible alternatives satisfying some unknown linear ordering,

  • a multiset of pairwise votes, i.e., a matrix $M\in\mathbb{N}^{n\times n}$: $M_{i,j}$ counts the number of votes for which $i<j$.

I am interested in computing the most likely maximum when we assume that all linear orders have same prior probability, and that each vote reflects the true ordering with probability $p>1/2$ independently.

According to Young, APSR'88: Condorcet's Theory of Voting it has long been known that for $p$ close to $1/2$ it is the Borda Winner (hence easy to compute), whereas for high enough $p$ it has been shown that the most likely maximum is a Kemeny Winner (hence computing a candidate is $P^{NP[log]}$ complete).

My main question is: what do we know for intermediate values of $p$? For instance, is there something like a dichotomy depending on $p$?

A side question is whether the complexity of the max-likelihood problem could for some $p$ be lower when the input vote matrix is restricted to those obtained by combining the votes of several rankings (or whether there are results "of that kind" in some other natural settings).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.