= Solution
First give $w$ the vote of every voter whose allowed <set> contains $w$. Let their number be $K$. This loses no possible strict victory: starting with any winning assignment, changing such a ballot to $w$ increases $w$'s score and weakly decreases an opponent's score. Thus a winning assignment exists exactly when one exists with these $K$ ballots fixed.
Every remaining voter must now be assigned to an allowed opponent, and \b[each opponent may receive at most $K-1$ votes]. If any allowed <set> is empty, there is no valid election assignment. With at least two candidates, $K=0$ immediately makes a unique victory impossible. With only the candidate $w$, every nonempty ballot <set> forces that candidate, so the answer is yes under the question's strict-comparison definition.
For the remaining case $K\geq1$, make a <flow network> with a <vertex> for each remaining voter and each opponent. Add source-to-voter arcs of <flow network edge capacity> one, voter-to-opponent arcs of <flow network edge capacity> one for the allowed choices, and opponent-to-sink arcs of <flow network edge capacity> $K-1$. Compute an integral <maximum flow>. Then
$$
\boxed{w\text{ can be the unique winner}\iff |f_{\max}|=n-K.}
$$
A <flow> saturating all voter arcs assigns each remaining voter to exactly one allowed opponent, by integrality and <flow conservation>. The sink-arc <capacity constraints> give every opponent strictly fewer than $K$ votes. Conversely, any winning assignment with the fixed $K$ votes defines just such a saturating <feasible flow>. The <flow network> has at most $n+m+2$ <vertices> and $O(n+m+\sum_i|C_i|)$ arcs, hence the decision takes <polynomial time>.
Back to article page
