  Various voting rules are based on ranking the candidates by scores induced by
aggregating voter preferences. A winner (respectively, unique winner) is a
candidate who receives a score not smaller than (respectively, strictly greater
than) the remaining candidates. Examples of such rules include the positional
scoring rules and the Bucklin, Copeland, and Maximin rules. When voter
preferences are known in an incomplete manner as partial orders, a candidate
can be a possible/necessary winner based on the possibilities of completing the
partial votes. Past research has studied in depth the computational problems of
determining the possible and necessary winners and unique winners.
  These problems are all special cases of reasoning about the range of possible
positions of a candidate under different tiebreakers. We investigate the
complexity of determining this range, and particularly the extremal positions.
Among our results, we establish that finding each of the minimal and maximal
positions is NP-hard for each of the above rules, including all positional
scoring rules, pure or not. Hence, none of the tractable variants of
necessary/possible winner determination remain tractable for extremal position
determination. Tractability can be retained when reasoning about the top-$k$
positions for a fixed $k$. Yet, exceptional is Maximin where it is tractable to
decide whether the maximal rank is $k$ for $k=1$ (necessary winning) but it
becomes intractable for all $k>1$.

Computer Science and Game Theory;Computational Complexity