  The computational complexity of winner determination is a classical and
important problem in computational social choice. Previous work based on
worst-case analysis has established NP-hardness of winner determination for
some classic voting rules, such as Kemeny, Dodgson, and Young.
  In this paper, we revisit the classical problem of winner determination
through the lens of semi-random analysis, which is a worst average-case
analysis where the preferences are generated from a distribution chosen by the
adversary. Under a natural class of semi-random models that are inspired by
recommender systems, we prove that winner determination remains hard for
Dodgson, Young, and some multi-winner rules such as the Chamberlin-Courant rule
and the Monroe rule. Under another natural class of semi-random models that are
extensions of the Impartial Culture, we show that winner determination is hard
for Kemeny, but is easy for Dodgson. This illustrates an interesting separation
between Kemeny and Dodgson.
