Minimax Approval Voting Rule (COMSOC)

Definition

Minimax Approval Voting Rule (COMSOC)

The minimax approval voting rule selects a committee $C^{\ast }\subseteq C$ minimising the maximum Hamming distance (symmetrical distance) between $C^{\ast }$ and $A_i$, i.e.,

$$\mathrm{MAV}(A_1,\dots ,A_n;k):=\underset{\begin{array}{c}{C}^{\ast }\subseteq C,\\ |C^{\ast }|=k\end{array}}{\mathrm{argmin}}\underset{v_i\in V}{\max }|A_i△C^{\ast }|$$

Intuition

Represent each approval ballot and committee as a binary row over the alternatives: $1$ means approved or selected, and $0$ means not approved or not selected. The Hamming distance counts the columns in which the two rows differ.

For example, let $C=\{a,b,c,d\}$ and $k=2$. Suppose a voter approves $A_i=\{a,c\}$:

	$a$	$b$	$c$	$d$
ballot $A_i$	$1$	$0$	$1$	$0$
committee $\{a,b\}$	$1$	$1$	$0$	$0$

The rows disagree at $b$ and $c$, so

$$|A_i△\{a,b\}|=\underset{c\text{ approved but omitted}}{\underbrace{1}}+\underset{b\text{ selected but unapproved}}{\underbrace{1}}=2.$$

The rule performs this comparison for every voter. For each proposed size-$k$ committee, it keeps only that committee’s largest distance:

$$C^{\ast }⟼\underset{\text{worst represented voter}}{\underbrace{\underset{i\in V}{\max }|A_i△C^{\ast }|}}.$$

There are $\left(\genfrac{}{}{0ex}{}{|C|}{k}\right)$ possible size-$k$ committees. A direct exact algorithm evaluates all of them and chooses those with the smallest maximum distance. Thus a committee cannot compensate for representing one voter very poorly by representing many others perfectly. The objective instead makes the worst disagreement as small as possible; this is the minimax principle.

Complexity

Computing a minimax approval committee is NP-hard when the committee size $k$ is part of the input.

The corresponding decision problem additionally receives a distance bound $d$ and asks:

$$\exists C^{\ast }\subseteq C:|C^{\ast }|=k\wedge \underset{i\in V}{\max }|A_i△C^{\ast }|\le d?$$

This problem belongs to NP: a committee $C^{\ast }$ is a certificate, and its size and distance from every ballot can be checked in $O(nm)$ time, where $n=|V|$ and $m=|C|$. Since the decision problem is also NP-hard, it is NP-complete.

Exhaustive search examines all $\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ size-$k$ committees and evaluates each in $O(nm)$ time, giving

$$O\left(\left(\genfrac{}{}{0ex}{}{m}{k}\right)nm\right).$$

This is polynomial in $m$ when $k$ is fixed, because $\left(\genfrac{}{}{0ex}{}{m}{k}\right)=O(m^k)$, but not when $k$ varies with the input.

The definition does not require every implementation to enumerate all committees. More sophisticated exact methods may prune candidates or encode the problem for an optimiser. NP-hardness means that no polynomial-time exact algorithm is known for unrestricted $k$; it does not prove that every algorithm must explicitly inspect all $\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ committees.

Example

Selecting two alternatives

Let $C=\{c_1,c_2,c_3,c_4,c_5\}$, let $k=2$, and consider the approval ballots

$$\begin{array}{rlrlrl}{A}_1& =\{c_1,c_2,c_3\},& A_2& =\{c_2\},& A_3& =\{c_3\},\\ A_4& =\{c_1,c_2,c_4,c_5\},& A_5& =\{c_1,c_2,c_4,c_5\}.& & \end{array}$$

For the proposed committee $C^{\ast }=\{c_1,c_2\}$, the five distances are

$$\begin{array}{rlrlrl}|A_1△C^{\ast }|& =1,& |A_2△C^{\ast }|& =1,& |A_3△C^{\ast }|& =3,\\ |A_4△C^{\ast }|& =2,& |A_5△C^{\ast }|& =2.& & \end{array}$$

Its minimax value is therefore $\max \{1,1,3,2,2\}=3$. Repeating this calculation for every size-$2$ committee gives:

Committee $C^{\ast }$	Distances to $(A_1,A_2,A_3,A_4,A_5)$	Maximum
$\{c_1,c_2\}$	$(1,1,3,2,2)$	$3$
$\{c_1,c_3\}$	$(1,3,1,4,4)$	$4$
$\{c_1,c_4\}$	$(3,3,3,2,2)$	$3$
$\{c_1,c_5\}$	$(3,3,3,2,2)$	$3$
$\{c_2,c_3\}$	$(1,1,1,4,4)$	$4$
$\{c_2,c_4\}$	$(3,1,3,2,2)$	$3$
$\{c_2,c_5\}$	$(3,1,3,2,2)$	$3$
$\{c_3,c_4\}$	$(3,3,1,4,4)$	$4$
$\{c_3,c_5\}$	$(3,3,1,4,4)$	$4$
$\{c_4,c_5\}$	$(5,3,3,2,2)$	$5$

The smallest maximum is $3$. Hence the co-winning committees are

$$\mathrm{MAV}(A_1,\dots ,A_5;2)=\{\{c_1,c_2\},\{c_1,c_4\},\{c_1,c_5\},\{c_2,c_4\},\{c_2,c_5\}\}.$$