Approval-Based Committee Voting under Uncertainty

IsPossJR is in NP, since given a committee $W$ and a plausible approval profile, we can check in polynomial time whether $W$ satisfies JR (Theorem 2 in [3]).

To show NP-hardness, we reduce from 3-SAT [10]. Let $I$ be a $3CNF$ formula consisting of $n$ clauses and $m$ variables $x_{1},\ldots,x_{m}$. W.l.o.g. we can assume that $n$ is even. We reduce to an instance $I^{\prime}=(V,C,[\Delta_{i}],k=\frac{|V|}{2},W)$ of IsPossJR as follows. We have one voter per clause in $V$, so $|V|=n$. Fix an ordering on the literals in each clause of the $3CNF$. Let $C_{1}=\{\ell_{1},\ldots,\ell_{3n}\}$ where candidate $\ell_{1}$ corresponds to the first literal in the first clause, candidate $\ell_{2}$ corresponds to the second literal in the first clause, and so on. Each voter $i$ assigns positive probability to exactly 3 approval sets, each corresponding to a literal in the voter’s corresponding clause. The $j$’th approval set of voter $i$ includes $\ell_{3(i-1)+j}$. For any two $\ell_{i}$ and $\ell_{j}$, $i<j$, that are associated with two distinct clauses, if $\ell_{i}=\bar{\ell_{j}}$ we create a candidate $c_{i,j}$ and add it to the two corresponding approval sets. Let $C_{2}$ denote the set of all such candidates $c_{i,j}$. Additionally, we create $c_{1},\ldots c_{k}$ dummy candidates and include them all in $W$. An example illustrating this reduction is provided after the proof. We claim that $I$ admits a satisfying assignment iff $W$ satisfies JR for a plausible approval profile in $I^{\prime}$. Note that as $W$ has no candidate in common with any of the voters’ plausible approval sets, it satisfies JR iff no $\frac{n}{k}=2$ voters approve of the same candidate. Note that the only candidates that can be approved by more than one voters are $c_{i,j}$’s.

Assume that $I$ admits a satisfying assignment $T$. Therefore at least one literal in each clause is set to True. Consider the approval sets in $I^{\prime}$ corresponding to True literals. For each voter, there exists at least one approval set corresponding to a True literal. If there are more than one, select one randomly. We claim that in the resulting approval profile, no two voters approve of the same candidate. Assume for contradiction that two voters do approve of the same candidate $c_{i,j}$. This implies that in $T$ a literal and its negation were both set to true, which contradicts that $T$ is a satisfying assignment.

Now assume that $W$ satisfies JR for a plausible approval profile $\mathcal{A}$ in $I^{\prime}$. For each voter $i$, set the literal corresponding to their approval set to True in $I$. We claim that the resulting truth assignment $T$ is feasible (does not set a literal and its negation to true) and satisfies $I$. Assume for contradiction that $T$ sets a literal and its negation to true. This implies that two voters approve of the same candidate, say $c_{i,j}$, contradicting that $W$ satisfies JR for $\mathcal{A}$. One approval set is picked for each voter, so one literal is set to True in $T$ for each clause, hence $T$ satisfies $I$. The proof is now complete.

Consider a committee $W$. Define the set $V^{*}\subseteq V$ to be the set of voters who are not represented in $W$ under at least one of their plausible approval sets. That is, $V^{*}=\{i:S_{r}\cap W=\emptyset\text{ for some }r\in[s_{i}]\}$. For each $c\in C\setminus W$, we check whether $\frac{n}{k}$ or more voters in $V^{*}$ have $c$ in at least one of their plausible approval sets. If yes, then there exits a plausible approval profile for which $W$ does not satisfy JR and hence $W$ does not satisfy JR with probability 1. If this condition does not hold for any $c\in C\setminus W$, then $W$ clearly satisfies JR under all plausible approval profiles.

SizeJR is in NP. Give a committee $W$ one can easily check in polynomial time whether $W$ satisfies JR (Theorem 2 in [3]). To show NP-hardness, we reduce from the NP-complete problem of CandidateCover which is to decide, given an instance $I=(V,C,\mathcal{A},r)$ where $V$ is a set of voters, $C$ a set of candidates, $\mathcal{A}$ an approval profile where $A_{i}\neq\emptyset,\forall i\in V$, and $r\leq|C|$ a positive integer, whether there exists a committee $W$ of size $r$ such that each voter is represented in $W$ , i.e. $A_{i}\cap W\neq\emptyset$. (Note that CandidateCover is SetCover [10] described in voting terminology.)

We reduce from an instance $I$ of CandidateCover to an instance $I^{\prime}=(V,C,\mathcal{A},k=|V|,r)$ of SizeJR. To satisfy JR every subset $V^{*}$ of voters, $|V^{*}|\geq\frac{|V|}{k}=1$, has to be represented, implying that every voter has to be represented. Thus it is straightforward to see that every YES instance of $I$ is a YES instance of $I^{\prime}$ and vice versa.

Take any candidate $c\in C$. Let $\mathcal{A}_{c}$ be the approval profile in which each voter’s approval set is exactly $\{c\}$. $\mathcal{A}_{c}$ is a plausible approval profile. As all the voters only approve of $c$, to satisfy JR for $\mathcal{A}_{c}$, $W$ must contain $c$. Our argument was independent of the choice of $c$, hence for $W$ to satisfy JR for all plausible approval profiles it must be that $W=C$ and $k=|C|$.

ExistsNecJR is in NP because IsNecJR is in P (immediate corollary of Theorem 13 in [15]). To prove NP-hardness we reduce from SizeJR that we have shown is NP-complete (see Lemma 1).

Given an instance $I=(V,C,\mathcal{A},k,r)$ of SizeJR, we reduce to an instance $I^{\prime}=(V^{\prime},C^{\prime},[p_{i,c}],k^{\prime})$ of ExistsNecJR under the Candidate-Probability model as follows. Suppose $|V|=n$ and $|C|=m$. Let $V^{\prime}=V\cup V^{+}$ where in $V^{+}$ we have $n$ new voters. Let $C^{\prime}=C\cup C^{+}$ where in $C^{+}$ we have $2k-r$ new candidates $\{1+m,\ldots,2k-r+m\}$. Each voter in $V$ has the same approval set as in $\mathcal{A}$, implying that for each voter $i\in V$, $p_{i,c}=1$, $\forall c\in A_{i}$ and $p_{i,c^{\prime}}=0$, $\forall c^{\prime}\in C^{\prime}\setminus A_{i}$. Each voter $i\in V^{+}$ disapproves of all candidates in $C$ (i.e. $p_{i,c}=0,\forall c\in C$) and finds all new candidates possibly acceptable (i.e. $0<p_{i,c}<1,\forall c\in[1+m,2k-r+m]$). Let $k^{\prime}=2k$. As $|V^{\prime}|=2|V|$ we have that $\frac{|V^{\prime}|}{k^{\prime}}=\frac{|V|}{k}=\frac{n}{k}$. This reduction can be done in polynomial time. It remains to show that every YES instance of $I$ is a YES instance of $I^{\prime}$ and vice versa.

Suppose $I$ is a YES instance of SizeJR. Then there exists a committee $W$, $|W|=r$, that satisfies JR in $I$. Let $W^{\prime}=W\cup C^{+}$. We claim that $W^{\prime}$ satisfies JR under all plausible approval profiles of $I^{\prime}$. Note that $|W^{\prime}|=r+2k-r=2k$ and hence of the correct size. By construction we have that $C^{+}\subset W^{\prime}$, therefore all voters in $V^{+}$ are represented in $W^{\prime}$. Voters in $V$ do not approve of any candidate in $C^{+}$. $W$ satisfies JR in $I$, implying that there does not exist a candidate $c\in C\setminus W$ who is approved by at least $\frac{n}{k}$ voters in $V$ none of whom is represented in $W$. Therefore $W^{\prime}$ satisfies JR under all plausible approval profiles and hence $I^{\prime}$ is a YES instance.

Suppose that $I^{\prime}$ is a YES instance of ExistsNecJR. Then there exists a committee $W^{\prime}$, $|W^{\prime}|=2k$, that satisfies JR under all plausible approval profiles of $I^{\prime}$. Voters in $V^{+}$ do not approve of any candidates in $C$, hence it follows from Lemma 2 that $C^{+}\subset W^{\prime}$. Let $W=W^{\prime}\setminus C^{+}$ and so we have that $|W|=2k-(2k-r)=r$. Voters in $V$ do not approve of any candidates in $C^{+}$, so they can only be represented by candidates in $C$. Therefore, for $W^{\prime}$ to satisfy JR under all plausible approval profiles it must be that there does not exist a candidate $c\in C\setminus W$ who is approved by at least $\frac{n}{k}$ voters in $V$ none of whom is represented in $W$. Hence $W$ satisfies JR in $I$ and $I$ is a YES instance.

We present the instance reductions in the settings of Lottery and Joint Probability models below, building upon the proof argument mentioned earlier in Theorem 5.2.

The above reductions can be done in polynomial time. It is easy to see, following similar arguments presented in the proof of Theorem 5.2, that every YES instance of $I$ is a YES instance of $I^{\prime}$ and vice versa.

Given an instance $I=(V,C,\mathcal{A},k,r)$ of SizeJR, we reduce to an instance $I^{\prime}=(V^{\prime},C^{\prime},\Delta,k^{\prime})$ of ExistsNecJR under the Joint Probability model as follows. Suppose $|V|=n$. Let $V^{\prime}=V\cup V^{+}$ where in $V^{+}$ we have $n$ new voters and $C^{\prime}=C\cup C^{+}$ where in $C^{+}$ we have $2k-r$ new candidates. Let $\Delta(\mathbf{{A}})=\{(\lambda_{1},\mathcal{A}_{1}\},(\lambda_{2},\mathcal{A}_{2}\})$, such that $0<\lambda_{1}<1$ and $\lambda_{2}=1-\lambda_{1}$.That is, there are exactly 2 plausible approval profiles. Let $\mathcal{A}_{1}=(A_{1},\ldots,A_{n},\frac{n}{k}\times\{m+1\},\frac{n}{k}\times\{m+2\}\dots,\frac{n}{k}\times\{m+\frac{2k-r}{2}\},\{\},\ldots\{\})$ and $\mathcal{A}_{2}=(A_{1},\ldots,A_{n},\frac{n}{k}\times\{m+\frac{2k-r}{2}+1\},\dots,\frac{n}{k}\times\{m+(2k-r)\},\{\},\ldots,\{\})$. The notation $\frac{n}{k}\times\{c\}$ indicates that exactly $\frac{n}{k}$ voters approved a candidate set $\{c\}$. Note that empty approval sets represent the dummy voters who do not approve of any candidates and are added to make the total number of voters $2n$. Each voter $i\in V$ approves of $A_{i}$ under both approval profiles. All the new voters approve of exactly one new candidate, and every new candidate is approved by $\frac{n}{k}$ new voters. Let $k^{\prime}=2k$. As $|V^{\prime}|=2n$ we have that $\frac{|V^{\prime}|}{k^{\prime}}=\frac{n}{k}$. This reduction can be done in polynomial time. We claim that every YES instance of $I$ is a YES instance of $I^{\prime}$ and vice versa.

Suppose $I$ is a YES instance of SizeJR. Then there exists a committee $W$, $|W|=r$, that satisfies JR in $I$. Let $W^{\prime}=W\cup C^{+}$. We claim that $W^{\prime}$ satisfies JR under all plausible approval profiles of $I^{\prime}$. Note that $|W^{\prime}|=r+2k-r=2k$ and hence of the correct size. As $C^{+}\subset W^{\prime}$, it follows from the construction of the approval profiles that all voters in $V^{+}$ are represented in $W^{\prime}$. $W$ satisfies JR in $I$, implying that there does not exist a candidate $c\notin W$ who is approved by at least $\frac{n}{k}$ voters in $V$ none of whom is represented in $W$. Therefore $W^{\prime}$ is necessarily JR in $I^{\prime}$ and $I^{\prime}$ is a YES instance.

Suppose that $I^{\prime}$ is YES instance of ExistsNecJR. Then there exists a committee $W^{\prime}$, $|W^{\prime}|=2k$, that satisfies JR under all plausible approval profiles of $I^{\prime}$. It follows from the construction of the plausible approval profiles that for any given $c\in C^{+}$, it is possible that $\frac{n}{k}$ voters in $V^{+}$ have $\{c\}$ as their approval set. Therefore, for $W^{\prime}$ to satisfy JR under all plausible approval profiles, it must be that $C^{+}\subset W^{\prime}$. Let $W=W^{\prime}\setminus C^{+}$ and so we have that $|W|=2k-(2k-r)=r$. Voters in $V$ do not approve of any candidates in $C^{+}$, so they can only be represented by candidates in $C$. Therefore, for $W^{\prime}$ to satisfy JR under all plausible approval profile, it must be that there does not exist a candidate $c\notin W$ who is approved by at least $\frac{n}{k}$ voters in $V$ none of whom is represented in $W$. Hence $W$ satisfies JR in $I$ and $I$ is a YES instance.

For each candidate, we count the number of voters who potentially approve it. For $W$ to satisfy JR under all plausible approval profiles, any candidate $c$ with a count $\geq\frac{n}{k}$ must be in $W$. This is because if $c$ is not in $W$ then $W$ does not satisfy JR under the plausible approval profile in which all voters who potentially approve of $c$ have $\{c\}$ as their approval set. Therefore, if there are more than $k$ candidates with a count $\geq\frac{n}{k}$, then there is no $W$ that satisfies JR with probability 1. Otherwise it is easy to see that any winning committee $W$ that contains all candidates with a count $\geq\frac{n}{k}$ satisfies JR with probability 1.

For any given graph, a set $S\subseteq V$ is a vertex cover if and only if the subset $V\setminus S$ is an independent set [10]. It is well known that counting independent sets of a graph is #P-complete [11].

We prove the statement by proving that #IsJR, the problem of counting the number of plausible approval profiles for which a given committee $W$ satisfies JR, is #P-complete for the 3VA model. Since the total number of plausible approval profiles can be computed easily (the count is $\prod_{i\in V}2^{x_{i}}$ where $x_{i}$ is $|\{c\in C\mid p_{i,c}=0.5\}|$) and all plausible approval profiles are equiprobable, the theorem will follow.

Consider an instance $I^{\prime}=G(V^{\prime},E^{\prime})$ of the #VC , where a graph $G$ is given with $V^{\prime}$ as the set of $n$ vertices and $E^{\prime}$ as the set of $m$ edges. We reduce to an instance $I=(V,C,[p_{i,c}],k,W)$ of #IsJR such that there is a one to one correspondence between vertex covers and plausible approval profiles for which $W$ satisfies JR. We have one voter per vertex, so $|V|=n$. For each edge $(i,j)$, $i<j$, in $E^{\prime}$ we create a candidate $c_{i,j}$ and have voters $i$ and $j$ approve of $c_{i,j}$ with probability 1. Other voters disapprove of $c_{i,j}$. That is, $p_{i,c_{i,j}}=p_{j,c_{i,j}}=1$ and $p_{t,c_{i,j}}=0,\forall t\in V\setminus\{i,j\}$. We additionally create a set of $k=\frac{n}{2}$ candidates $C^{+}=\{c^{+}_{1},c^{+}_{2},...,c^{+}_{k}\}$, so we have $|C|=m+k$. Each voter approves of $c^{+}_{1}$ with probability 0.5, i.e., $p_{i,c^{+}_{1}}=0.5,\forall i\in V$, and disapproves of the rest of the candidates in $C^{+}$, i.e., $p_{i,c^{+}_{j}}=0,\forall i\in V,\forall j\in[2,k]$. We set $W=C^{+}$. Note that $\frac{n}{k}=2$. This reduction can be done in polynomial time.

We claim that every vertex cover in $I^{\prime}$ corresponds to a unique plausible approval profile in $I$ for which $W$ satisfies JR, and vice versa. Given a subset of vertices $S\subseteq V^{\prime}$, we define a plausible approval profile $\mathcal{A}^{S}$ as follows. Voters $V^{S}\subseteq V$ corresponding to $S$ approve of $c^{+}_{1}$ and the remaining voters disapprove of $c^{+}_{1}$.

We first show that if $S$ is a vertex cover then $W$ satisfies JR with respect to $\mathcal{A}^{S}$. $S$ being a vertex cover implies that at least one end point of every edge is in $S$. This implies that, in $\mathcal{A}^{S}$, of any two voters who approve of the same candidate, at least one approves of $c^{+}_{1}$ also, and is hence represented in $W$. Hence $W$ satisfies JR. Conversely, we show that if $S$ is not a vertex cover then $W$ does not satisfy JR in $\mathcal{A}^{S}$. $S$ not being a vertex cover implies that there is at least one edge $(i,j)$ whose end points $i$ and $j$ are not in $S$. This implies that, in $\mathcal{A}^{S}$, the corresponding voters $i$ and $j$ both approve of the same candidate $c_{i,j}$ and disapprove of $c^{+}_{1}$. Hence there is a set of candidates of size $\frac{n}{k}=2$ who approve of the same candidate and neither is represented in $W$, implying that $W$ does not satisfy JR in $\mathcal{A}^{S}$.

Let $V^{\prime}$ be the set of voters who have not approved any candidate in $W$. Define $n^{+}_{j}$ (respectively, $n^{1}_{j}$ and $n^{u}_{j}$) as the number of voters from $V^{\prime}$ who approved candidate $j$ with $p_{i,j}>0$ (respectively, $p_{i,j}=1$ and $p_{i,j}=0.5\}$). So $n^{+}_{j}=n^{1}_{j}+n^{u}_{j}$. If $\exists j\in C\setminus W$ such that $n^{1}_{j}\geq\frac{n}{k}$, then the probability of $W$ being JR is zero. In the case where $n^{1}_{j}<\frac{n}{k}$, we utilize the following procedure to calculate the probability of $W$ being JR. Note that since all plausible approval profiles are equiprobable under 3VA, it is sufficient to count the number of plausible approval profiles and those that violate JR.

For each candidate $j\in C\setminus W$, we count the number of plausible assignments of voters’ unknown approvals under which $W$ does not satisfy JR because of $j$. A plausible assignment is obtained by setting $p_{i,j}$ to 0 or 1 wherever $p_{i,j}=0.5$. This results in $2^{n^{u}_{j}}$ plausible assignments. Out of these, we count the number of assignments that violate JR because of $j$, denoted as $t_{j}$, as follows: $t_{j}=\sum_{l=\frac{n}{k}-n^{1}_{j}}^{n^{u}_{j}}{n_{j}^{u}\choose l}.$ Therefore, the probability that $W$ violates JR because of candidate $j$ is $p_{j}(W\text{ violates }JR)=\frac{t_{j}}{2^{n^{u}_{j}}}$. When $n^{+}_{j}<\frac{n}{k}$, $t_{j}=0$. The probability of $W$ satisfying JR can be expressed as the product of individual probabilities, where each term corresponds to 1 minus the probability of $W$ violating JR because of each candidate $j\in C\setminus W$: $p(W\text{ being JR })=\prod_{j\in C\setminus W}\big{(}1-p_{j}(W\text{ violates }JR)\big{)}.$ This computation can be done in polynomial time.

When $k=n$, we have $\frac{n}{k}=1$ and so ensuring JR for a plausible approval profile requires that each voter who approves at least one candidate must have at least one of their approved candidates represented in the winning committee $W$. Hence, for each voter $i$, the objective is to count the number of plausible approval sets for $i$ under which either $i$ is represented in $W$ or $i$ does not approve of any candidate. We let $t_{i}$ denote this count which can be computed in polynomial time as follows. If $i$ approves of any candidate in $W$ with probability 1 then $t_{i}$ will be $2^{x_{i}}$ where $x_{i}$ is the number of candidates $i$ is unsure about. Otherwise (if $i$ doesn’t assign probability 1 to any candidate in $W$) then let $y_{i}$ be the number of candidates in $W$ that $i$ is unsure about. Then $t_{i}=(2^{y_{i}}-1)\times 2^{x_{i}-y_{i}}$ if there exists a candidate that $i$ approves with probability 1, and $t_{i}=(2^{y_{i}}-1)\times 2^{x_{i}-y_{i}}+1$ otherwise (the last term counts for the case where $i$ does not approve of any candidate.) The overall number of plausible approval profiles where $W$ satisfies JR is the product of these individual counts, i.e., $\prod_{i}{t_{i}}$.

We provide the proof for ExistsNecEJR . The proof for ExistsNecPJR is identical and requires only to substitute IsEJR with IsPJR. We prove ExistsNecEJR is coNP-hard by reducing from IsEJR that is known to be coNP-complete  [3].

Given an instance $I=(V,C,\mathcal{A},k,W)$ of IsEJR, we reduce to an instance $I^{\prime}=(V^{\prime},C^{\prime},[p_{i,c}],k^{\prime})$ of ExistsNecEJR under the Candidate-Probability model as follows. Suppose $|V|=n$. Let $V^{\prime}=V\cup V^{+}$ where in $V^{+}$ we have $n$ new voters. Let $C^{\prime}=C\cup C^{+}$ where in $C^{+}$ we have $k$ new candidates $\{c^{+}_{1},\ldots,c^{+}_{k}\}$. Each voter in $V$ has the same approval set as in $\mathcal{A}$, implying that for each voter $i\in V$, $p_{i,c}=1$, $\forall c\in A_{i}$ and $p_{i,c^{\prime}}=0$, $\forall c^{\prime}\in C^{\prime}\setminus A_{i}$. Each voter $i\in V^{+}$ disapproves of all candidates in $C\setminus W$ (i.e. $p_{i,c}=0,\forall c\in C\setminus W$) and finds all the other candidates possibly acceptable (i.e. $0<p_{i,c}<1,\forall c\in W\cup C^{+}$)¹¹1Set $p_{i,c}=0.5$, in case of 3VA model.. Let $k^{\prime}=2k$. As $|V^{\prime}|=2|V|$ we have that $\frac{|V^{\prime}|}{k^{\prime}}=\frac{n}{k}$. This reduction can be done in polynomial time. It remains to demonstrate that every YES instance of $I$ is a YES instance of $I^{\prime}$, and vice versa.

Suppose $I$ is a YES instance of IsEJR. Then $W$ satisfies EJR in $I$. Let $W^{\prime}=W\cup C^{+}$. Clearly $|W^{\prime}|=2k=k^{\prime}$. We claim that $W^{\prime}$ satisfies EJR under all plausible approval profiles of $I^{\prime}$. Voters in $V^{+}$ do not approve of any candidate in $C\setminus W$; by construction, we have that $C^{+}\subset W^{\prime}$ and $W\subset W^{\prime}$. Therefore, $W^{\prime}$ satisfies EJR for every $\ell\in[1,k]$ and every $\ell$-cohesive group of voters in $V^{\prime}$. Therefore, $W^{\prime}$ satisfies EJR with probability 1 and $I^{\prime}$ is a YES instance.

If $I$ is a NO instance of IsEJR, then $W$ violates EJR w.r.t. a set of voters in $V$. In $I^{\prime}$, voters in $V^{+}$ do not approve of any candidate in $C\setminus W$ and can possibly approve every candidate in $C^{+}\cup W$. Consequently, to satisfy EJR under all plausible approval profiles, a winning committee $W^{\prime}$ must include all candidates in $C^{+}\cup W$. As $|C^{+}\cup W|=2k=k^{\prime}$, $W^{\prime}$ cannot include any other candidate. Since voters from $V$ do not approve of any candidates from $C^{+}$ and $W$ does not satisfy EJR with respect to $V$ and $\frac{n}{k}$, $W^{\prime}$ cannot satisfy JR for any plausible approval profile. As a result, $I^{\prime}$ is a NO instance of ExistsNecEJR.

The proof argument is identical to that presented in Theorem 7.1, with the only variation being the instance reduction due to a different problem setting. Therefore, we present the instance reductions in the settings of lottery and joint probability models below, building upon the proof argument mentioned earlier in Theorem 7.1.

The above reductions are polynomial time. It is easy to see, following similar arguments presented in the proof of Theorem 7.1, that every YES instance of I is a YES instance of I’ and vice versa under both models.

ExistsNecEJR (resp. ExistsNecPJR), the problem of finding a committee $W$ with a probability of being EJR (resp. PJR) equal to 1 was proven to be coNP-hard for all the four uncertainty models: 3VA, Candidate Probability, Lottery and Joint Probability models (refer Table 1). If there exist a polynomial time algorithm to solve MaxEJR (resp. MaxPJR) in any of these four models, it can be used to solve ExistsNecEJR (resp. ExistsNecPJR) in the corresponding model. Thus, MaxEJR and MaxPJR are coNP-hard for the 3VA, Candidate Probability, Lottery and Joint Probability models.