Complexity of predicting winners in plurality voting with abstentions

Subgame-Perfect Nash Equilibria of Plurality Voting with Abstention: a PSPACE-Completeness Result for Restricted Ballots

Computer Science and Game Theory

Summary

This paper looks at a type of voting where people vote one after another and may choose not to vote at all. Each voter has a list of favorite candidates and can only vote for some of the top ones in their list or abstain. The authors study how hard it is to figure out whether a certain candidate can win if everyone votes strategically, thinking about how others will vote. They find that this problem is very complex and belongs to a class called PSPACE-complete, meaning it is generally tough to solve with a computer. This answers a question left open by earlier work on voting strategy.

What this means in practice

  • For election system designers: Assess the computational limits of predicting strategic outcomes in sequential plurality elections with voting constraints.
  • For game theory software developers: Understand the complexity barriers when building tools to analyze equilibria in voting games with restricted ballots and abstentions.

A theory result. No direct application yet.

Authors

Edith Elkind

Abstract

We consider sequential Plurality elections in which each voter may abstain or vote for a single candidate. Each voter assigns utilities to all candidates; for each voter, this induces a (weak) order over the candidates. Ties are resolved uniformly at random, and voting has a small positive cost, so that a voter prefers to abstain when their vote cannot change the election outcome. We consider a variant of this model where, for each voter, we additionally specify a prefix of her ranking, so that she is only allowed to vote for a candidate from that prefix (or abstain). We prove that for this variant of the model, deciding whether a designated candidate is among the election winners in a subgame-perfect equilibrium of the associated extensive-form game is PSPACE-complete. This partially resolves an open problem from the work of Desmedt and Elkind [2010].
View PDFOpen arXiv