The complexity of online voter control in sequential elections

An exception is a paper by Fitzsimmons et al. [16] that is, regarding their earliest appearing versions, more recent than the present paper, and studies a mixed model involving both a chair and manipulators, in which the manipulative voters set their votes after control action by the chair. (We mention in passing that if one looks beyond the study of control, uncertainty appears in many election, selection, and preference-aggregation settings, see, e.g., the book [39] and, as one among many possible examples, the work of Mattei et al. [33].)

Actually, as our previous example suggested, our model is a bit more flexible and allows one to ask such questions starting at an intermediate point at which some actions have already been taken, potentially by a different admissions staff member.

Note that this maxi-min-inspired (but with more quantifiers) approach is really about alternating quantifiers. We are asking if there exists a current action of the chair, such that for all potential revealed vote values that come between now and the next time the chair has to decide on an action, there exists a next action by the chair, such that for all \(\ldots \) \(\ldots \) the chair reaches her goal.

Why do we provide an ordering \(\sigma \) rather than just providing as a list the set of candidates who are good enough to count as reaching our goal? For the decision-problem version of online voter control, which is our formulation here, providing such a set would be just as good. But by making \(\sigma \) a part of the input, we make the model compatible, for the future, with the interesting optimization problem of trying to find the most preferred candidate within \(\sigma \) for which the chair can ensure that there is among the winner set one of the candidates in the segment from that candidate to the top candidate in \(\sigma \).

Also, to avoid any confusion, we note that in our “d chooses an upper (constructive case) or lower (destructive case) segment of the candidates” approach, the non-online version’s situation that the destructive goal “opposing” a constructive goal is specified in the same way not longer holds (although we could have defined things in a less natural way so that that would hold). That is, in the non-online setting, the distinguished candidate d in the constructive case is saying who the chair wants to win, and in the destructive case is saying who the chair wants to not win; d in one case is defined in the problem definition to denote the beloved candidate and in the other case is defined to denote the despised candidate. However, in our case, we are giving an order \(\sigma \), and it would be perverse and confusing to have > mean one thing for constructive and another for destructive. And so, as we have defined things, if the chair’s stated ordering \(\sigma \) is \(v_1> v_2> v_3> v_4 > v_5\) and \(d=v_2\), in the constructive case that means that the chair wants at least one of \(v_1\) or \(v_2\) to win. To state the destructive-case goal—which in some sense is the “flip” of that constructive-case goal—of having neither \(v_1\) nor \(v_2\) be a winner, one would give as the chair’s ordering \(v_5> v_4> v_3> v_2 > v_1\) and \(d=v_2\), since this specifies that \(v_2\) and \(v_1\) are the chair’s two most despised candidates and are the ones the chair wants to prevent from being winners.

These comments simply refer to the way various “opposite” goals happen to be expressed. None of the above is saying that the constructive problem (viewed as a set) and the destructive problem (viewed as a set) are each other’s complements. Due to the quantification involved regarding the actions being taken such as by the chair, that is not true.

The statement of Theorem 1 holds even for election systems whose winner problems are in \(\mathrm {PSPACE}\).

Recall that each path of a polynomial-time alternating Turing machine has as its individual (leaf) value either Accept or Reject, and the overall action of the Turing machine is determined by the thought-experiment of applying the existential and universal node actions of the machine to those leaf values, resulting in an Accept or Reject at the root that determines the machine’s acceptance or rejection on the given input.

Are elections with just one candidate ever interesting in the real world? We feel they sometimes are. For example, a popular referendum—or for that matter a vote in a legislature on a bill—is essentially an up-or-down vote on one “candidate.” So is a vote on whether to recall an elected official, or to impeach a judge, or to ratify a person who has been nominated for a sports hall of fame.

Sure enough, u’s top choice could be one of those candidates that end up having only few votes, so adding u could be a wasted addition that will block some future good addition in some vote sequences, but in the worst case all future voters put first a candidate disliked by the chair; so our action is fine within the quantifier structure of the problem.