on 07-May-2017 (Sun)

A commonly used model, adopted widely in machine learning is the Mallows φ-model (Mallows, 1957). It is parameterized by a modal or reference ranking σ and a dispersion parameter φ ∈ (0, 1]; and for any rank- ing r we define: P (r; σ, φ) = 1 Z φ d(r,σ ) , where d is the Kendall tau distance and Z = r φ d(r ,σ ) = 1 ·(1 + φ) · (1 +φ + φ 2 ) ···(1 +···+φ m−1 ) is a normalization constant. 6 When φ = 1 we obtain the uniform distribution over rankings (i.e., impar- tial culture), and as φ → 0 we approach the distribution that concentrates all mass on σ .

First, it is easy to observe that if the number m of alternatives A is bounded—assuming voters are not weighted (we briefly discuss weighted voters in what follows) and the voting rule satisfies anonymity—then both PW and NW are computable in polynomial time if the voting rule supports polynomial winner determination (Conitzer et al., 2007; Walsh, 2007). This is so because there are only a constant number of distinct votes b = m! that may be cast by any voter. By anonymity, the number of voters casting each vote is sufficient to determine a winner, and there are at most (n + 1) b such “count” profiles that need to be enumerated