Describe all irreducible voting systems with two outcomes

Question

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$.

Answer 1

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

Answer 2

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.