# Describe all irreducible voting systems with two outcomes

A situation where $n$ voters choose between two candidates can be modelized by a $n$-uple $(a_1,\ldots,a_n)\in\lbrace 0,1 \rbrace^n$, where $a_i$ denotes the wish of the $i$-th voter. So the voting system (the rule which decides which candidate will be elected from the uple) can be described as a boolean map $f:\lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace$. The following assumptions are natural on $f$ :

(1) Symmetry : $f(1-a_1,1-a_2,\ldots,1-a_n)=1-f(a_1,\ldots,a_n)$ for any uple $a_1,\ldots,a_n$.

(2) Monotonicity : if $a_k\leq b_k$ for every $k$, then $f(a_1,\ldots,a_n) \leq f(b_1,\ldots,b_n)$.

If $I\subsetneq \lbrace 1,2,\ldots, n \rbrace$ is such that $f$ does not depend on the coordinates $a_j$ for $j\not\in I$, we say that $I$ is a (nontrivial) coalition ; the trivial coalition is $I=\lbrace 1,2,\ldots, n \rbrace$. When there is no nontrivial coalition, we say that $f$ is irreducible.

The question is, what are the irreducible maps $f:\lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace$ satisfying (1) and (2) ? When $n$ is odd, there is an obvious solution of "choosing the candidate with the most votes". I couldn't find any other examples.

My thoughts :

This is very closely related to Arrow's theorem and similar results, of course. But everything I've found so far only dealt with voting systems with at least three outcomes.

Update: The question can also be expressed in "measure-theoretic" terms. Indeed, if for $A\subsetneq \lbrace 1,2,\ldots, n \rbrace$ we denote by $i_A$ the indicator uple of $A$ (i.e. the uple $u=(u_1,\ldots,u_n)$ with $u_a=1$ when $a\in A$ and $0$ otherwise) and put $\mu(A)=f(i_A)$, then for the "measure" $\mu$, (1) means that $\mu(A)\leq\mu(B)$ when $A\subseteq B$, and (2) means that $\mu(A^{c})=1-\mu(A)$ where $A^{c}$ denotes the complement of $A$.

## 2 Answers

You can generalize your majority vote idea by assigning weights to the voters such that there can never be a tie between the sums of the weights on either side (e.g. if the sum of the weights is odd).

Here's code that finds all symmetric, monotonic, irreducible voting systems for up to $6$ voters. Up to $5$ voters, they can all be described by weight assignments, but this is not the case for $6$ voters.

For $3$ voters, majority vote is the only option.

For $4$ voters, there is also only one type of voting system, where one special voter can only be overridden by a unanimous vote of the other three, corresponding to weight vectors $(2,1,1,1)$ etc., of which there are $4$.

For $5$ voters, there are three types of voting systems in addition to majority vote.

In the first type, one special voter can only be overridden by a unanimous vote of the other four, corresponding to weight vectors $(3,1,1,1,1)$ etc., of which there are $5$.

In the second type, two voters decide if they agree, and otherwise the other three decide by majority vote, corresponding to weight vectors $(2,2,1,1,1)$ etc., of which there are $10$.

In the third type, two voters decide if they agree, else two other voters decide if they agree, else the fifth voter decides, corresponding to weight vectors $(3,3,2,2,1)$ etc., of which there are $30$.

Thus, in total there are $1+5+10+30=46$ different voting systems for $5$ voters.

For $6$ voters, there are $2284$ different voting systems, of which $1322$ with $14$ permutationally inequivalent types can be specified by weights as follows:

\begin{array}{c|c} \text{weights}&\text{count}\\\hline 2,1,1,1,1,1&6\\ 4,1,1,1,1,1&6\\ 2,2,2,1,1,1&20\\ 3,2,1,1,1,1&30\\ 3,3,2,1,1,1&60\\ 3,2,2,2,1,1&60\\ 3,3,2,2,2,1&60\\ 4,3,3,1,1,1&60\\ 5,2,2,2,1,1&60\\ 4,2,2,1,1,1&60\\ 4,3,2,2,1,1&180\\ 4,3,3,2,2,1&180\\ 5,3,3,2,1,1&180\\ 5,4,3,2,2,1&360 \end{array}

But there are also $962$ voting systems with $9$ permutationally inequivalent types that can't be specified by weights. Here are the minimal coalitions needed to achieve the outcome $1$ (with the coalitions extending in the vertical direction to save space, so the rows correspond to voters):

$12$ voting systems with $10$ minimal coalitions:

0000011111
0011100011
0101101100
1010110100
1101010001
1110001010


$20$ voting systems with $10$ minimal coalitions:

0000001111
0001110001
0110110110
1011011010
1101101100
1110000001


$90$ voting systems with $7$ minimal coalitions:

0000111
0011001
0101010
0110100
1001100
1110011


$90$ voting systems with $10$ minimal coalitions:

0000000011
0000111100
0111001101
1011010110
1101101010
1110110001


$90$ voting systems with $11$ minimal coalitions:

00000011111
00011100011
01100100101
10101001001
11010111000
11111010110


$120$ voting systems with $10$ minimal coalitions:

0000001111
0001110001
0110010010
1010111100
1101100110
1111001001


$180$ voting systems with $7$ minimal coalitions:

0000011
0001100
0110101
0111010
1010110
1101001


$180$ voting systems with $10$ minimal coalitions:

0000000111
0001111001
0110011010
1010101100
1101010100
1111100011


$180$ voting systems with $11$ minimal coalitions:

00000001111
00001110001
01110010011
10110100101
11011011100
11101101010

• Nice! All those first results look promising indeed. Commented Jun 1, 2016 at 18:55
• @EwanDelanoy: Unfortunately the results for $6$ voters are more complicated. I don't see how to describe them more systematically. You might want to take a look at this question (though it doesn't have any answers yet). Commented Jun 1, 2016 at 21:25

There are definitely other irreducible functions that satisfy the monotonicity and symmetry conditions; here is one example. (The numbers $F_k$ below are the Fibonacci numbers.)

Take $n=7$, and let voter $k$ have $F_k$ votes for $k=1,\ldots,7$; the winning candidate is the one who gets the larger number of votes. (This is well-defined, since $\sum_{k=1}^7F_k=33$ is odd.) This is clearly not straight majority rule, since $f(\langle 0,0,0,0,0,1,1\rangle)=1$, and it clearly satisfies the monotonicity and symmetry conditions.

Suppose that $I\subseteq[7]$ is a coalition; clearly we must have $\sum_{k\in I}F_k\ge 17$, so at least one of $6$ and $7$ must belong to $I$. If $7\notin I$, then $5\in I$. Then for any $a=\langle a_1,\ldots,a_7\rangle\in\{0,1\}^7$ such that $a_5\ne a_6$, $f(a)$ depends on $a_7$, so we must have $7\in I$.

Suppose that $6\notin I$, and that $a_k=1-a_7$ for $k\in I\setminus\{7\}$. If $\sum_{k\in I\setminus\{7\}}F_k\ge 9$, then voter $6$ has enough votes to determine the outcome, so If $\sum_{k\in I\setminus\{7\}}F_k\le 8$. But then $\sum_{k\in[7]\setminus I}F_k\ge 12$, and the voters not in $I$ have enough votes to determine the outcome. Thus, $6\in I$.

Suppose that $5\notin I$, and that $a_6\ne a_7$. If $\sum_{k\in[7]\setminus I}F_k\ge 9$, then the voters in $[7]\setminus I$ have enough votes to determine the outcome. Otherwise, $\sum_{k\in[7]\setminus I}F_k\le 8$, so

$$12\le\sum_{k\in I\setminus\{7\}}F_k\le 15\;,$$

and voter $5$ has enough votes to determine the outcome when voter $7$ disagrees with the rest of $I$. Thus, $5\in I$.

It’s straightforward to check in similar fashion that $4\in I$, then that $3\in I$, and finally that $I=[7]$ and hence that $f$ is irreducible.

I’ve not yet really tried to see how much this idea can be generalized — quite a bit, I suspect.

• (+1) A slightly easier way to prove that this $f$ is irreducible: $13+3=16$, so if these two vote against the other five, each of the five can make a difference by switching their vote. On the other hand, $13+3+1=17$, so if these three vote against the other four, each of the three can make a difference by switching their vote. Thus everyone can make a difference. Commented Jun 1, 2016 at 17:50
• @joriki: For some reason it wasn’t immediately obvious to me initially that if every voter can make a difference in at least one situation, then $f$ is irreducible. Na ja, da hatte ich ein Brett vorm Kopf. Commented Jun 1, 2016 at 17:59
• Wow, where did you pick up the nice German? :-) (To your credit, the description of irreducibility in the question somewhat distracts from this simpler characterisation.) Commented Jun 1, 2016 at 18:00
• @joriki: Thanks! I wish it were better, actually: my reading comprehension is decent, if slow — I do read some German fiction for pleasure, not to mention a number of online German news sites — but my production is much poorer, since I rarely have occasion to exercise it. Commented Jun 1, 2016 at 18:15
• Well, you got a number of subtleties right in that one sentence (not to mention the idiom itself) :-) Commented Jun 1, 2016 at 18:17