Technically Exists

Non-deterministic criterion extension

Non-deterministic criterion extension is a means of taking a criterion meant only for deterministic voting methods and creating a new version of it that can also apply to non-deterministic voting methods. This may be useful for making criteria robust to otherwise-deterministic voting methods that must occasionally resort to breaking ties randomly, as is standard behavior for many real-world elections. It is unclear to what extent this technique is useful for extending criteria that assume determinism to voting methods designed around randomness, such as random ballot.

Before this extension can be defined, some notation needs to be specified. In the following definition, {0,1}∞\{0, 1\}^\infty refers to the set of all possible infinite bitstrings, EE refers to the set of all elections (where an election is just a list of ballots), and CC refers to the set of all candidates.

For a given criterion, a voting method mm passes the extended version of that criterion if there exists a function f:{0,1}∞×E→Cf : \{0, 1\}^\infty \times E \rightarrow C such that both of the following hold:

  1. For r∈{0,1}∞r \in \{0, 1\}^\infty chosen uniformly at random, Pr⁡[f(r,e)=c]=Pr⁡[m(e)=c]\Pr[f(r, e) = c] = \Pr[m(e) = c] for all e∈Ee \in E and c∈Cc \in C.
  2. For all r∈{0,1}∞r \in \{0, 1\}^\infty, the deterministic voting method mr=f(r,⋅)m_r = f(r, \cdot) passes the original criterion.

The idea here is that ff is essentially the same as mm except with the randomness isolated to a single variable rr. This makes it possible to ignore that randomness and compare the original criterion to ff via mrm_r. At the same time, the extension only requires some function ff with the right properties to exist in order to prevent the extended criterion from being dependent on the internal workings of the voting method, specifically how it uses its randomness.

The input rr is chosen from the set of infinite bitstrings in order to ensure that ff has an arbitrarily large number of random bits at its disposal. If for some reason this is insufficient, rr could instead be drawn from a set with a greater cardinality, such as the power set of {0,1}∞\{0, 1\}^\infty.

Validity

It is trivial to show that any deterministic method mdm_d that passes the original criterion will also pass the extended version. Consider the function fd(r,e)=md(e)f_d(r, e) = m_d(e). It is clear that Pr⁡[fd(r,e)=c]=Pr⁡[md(e)=c]\Pr[f_d(r, e) = c] = \Pr[m_d(e) = c] for all values of ee and cc, and it is also clear that for all values of rr, the voting method mr=fd(r,⋅)=mdm_r = f_d(r, \cdot) = m_d will pass any criterion that mdm_d passes. Thus, fdf_d meets both conditions and mdm_d passes the extended criterion.