11institutetext:  University of New South Wales, Sydney, Australia
11email<EMAIL_ADDRESS>22institutetext: National
Institute of Technology, Warangal, India
22email<EMAIL_ADDRESS>33institutetext: University of Southampton,
Southampton, UK
33email<EMAIL_ADDRESS>
# Approval-Based Committee Voting under Uncertainty

Hariz Aziz 11 Venkateswara Rao Kagita 22 Baharak Rastegari 33 Mashbat Suzuki
11

###### Abstract

We study approval-based committee voting in which a target number of
candidates are selected based on voters’ approval preferences over candidates.
In contrast to most of the work, we consider the setting where voters express
uncertain approval preferences and explore four different types of uncertain
approval preference models. For each model, we study the problems such as
computing a committee with the highest probability of satisfying axioms such
as justified representation.

###### Keywords:

Approval preferences, Committee voting, ABC voting

##  1 Introduction

Multi-agent collective decision making is one of the fundamental issues in
computer science and economics. We consider the ubiquitous problem of
selecting a given number of candidates based on voters’ approval preferences
over candidates. The problem has been referred to as approval-based committee
(ABC) voting  or multi-winner voting under approval preferences [17, 19].
Prominent concerns in ABC voting include proportional representation of voters
and finding committees that are desirable and representative. One of the most
widely studied concepts for fairness in ABC voting is justified representation
(JR) and stronger variants [4, 8, 19].

Almost all of the focus in ABC voting has been on voters with deterministic
preferences. While proportional representation in ABC voting has received
tremendous interest, especially in recent years (see, e.g., [19]), there is
little prior work on computing desirable representative committees under
uncertain preferences. Uncertain approval preferences are useful when the
central planner only has imprecise information about the voters’ preferences.
This estimated information could be based on historical preferences, past
selections, or online clicks or views. For example, if a voter $i$ has
selected a certain candidate $c$ 70% of the times in previous situations, one
could use that information to assume that the approval probability of voter
$i$ for candidate $c$ is 0.7. The information could also be based on
situations where each voter actually represents a group of people who may not
have identical approval preferences. For example, if 60% of the group approved
a certain candidate, one could assume that approval probability of voter $i$
for candidate $c$ is 0.6. The estimated information could also represent the
confidence of a machine learning or a recommendation technique that is
employed to predict the unobserved (dis)approvals of voters for candidates.
Collaborative filtering techniques can be applied in scenarios with a
partially observed matrix depicting voter-candidate interactions through
approval/disapproval entries [14, 16]. These techniques enable the prediction
of unknown entries with a confidence level of $(1-\varepsilon)$, where
$\varepsilon$ represents the probability of making an error. To illustrate,
consider an algorithm that predicts approval with a confidence level of 70%.
In this case, the probability that a voter approves a candidate is 0.7, while
the probability of disapproval is 0.3.

In this paper, we initiate work on problems where voters’ uncertain approval
preferences are taken into account to compute desirable committees that
satisfy representation with high probability. We consider four different types
of uncertain approval preferences. In the _Joint Probability model_ , there is
a probability distribution of approval profiles. In the _Lottery model_ , each
voter has an independent probability distribution over approval sets. In the
_Candidate-Probability model_ , there is a probability for a given voter
approving a given candidate. We also consider a restricted version of the
latter model. For each of the uncertain approval models, we consider problems
such as computing a committee with the highest probability of being JR. Such
an outcome can be viewed as being fair under uncertain information.

#### Contributions

We undertake a detailed computational complexity analysis of several problems
with respect to the four preference uncertainty models. For each of the
preference models, we consider problems such as JR-Probability (computing the
probability that a given committee satisfies JR); IsPossJR (deciding whether a
given committee satisfies JR with non-zero probability); IsNecJR (deciding
whether a given committee satisfies JR with probability one); ExistsNecJR
(deciding whether there exists a committee that satisfies JR with probability
one); and MaxJR (computing a committee that has the highest probability of
satisfying JR). Our central focus is on justified representation (JR) but we
also present several results for stronger proportional representation axioms
such as PJR and EJR. We show that ExistsNecJR is NP-complete for all the
models that we consider. IsPossJR is computationally hard for the lottery
model and polynomial-time solvable for the other models. Our results are
summarized in Table 1.

|  Joint Prob. |  Lottery |  Candidate Prob. |  3VA
---|---|---|---|---
Problems |  |  |  |
JR-Probability |  in P |  NP-h (C. 2) |  #P-complete (T. 6.2) |  #P-complete (T. 6.2), in P if $p_{i,c}\in\\{0,1\\}$, $\forall i\in V$ & $\forall c\in W$ (T. 6.3)
IsPossJR |  in P (remark) |  NP-c (T. 4.1) |  in P (Mod. of [15]) |  in P [15]
IsPossEJR/ IsPossPJR |  coNP-c (C. 4) |  coNP-c (C. 4) |  coNP-c (C. 4) |  coNP-c (C. 4)
IsNecJR |  in P (remark) |  in P (T. 5.1) |  in P (Mod. of [15]) |  in P [15]
IsNecEJR/ IsNecPJR |  coNP-c (C. 4) |  coNP-c (C. 4) |  coNP-c (C. 4) |  coNP-c (C. 4)
ExistsNecJR |  NP-c (T. 5.3), even if there are only 2 _plausible_ approval profiles (T. 5.4) |  NP-c (T. 5.3), in P if all _plausible_ approval sets are of size 1 (T. 5.5) |  NP-c (T. 5.2), in P if $0<p_{i,c}<1$ $\forall i\in V\&\forall c\in C$ (Cor. of L. 2) |  NP-c (C. 1), in P if $0<p_{i,c}<1$ $\forall i\in V\&\forall c\in C$ (Cor. of L. 2)
ExistsNecEJR/ ExistsNecPJR |  coNP-h (T. 7.2) |  coNP-h (T. 7.2) |  coNP-h (T. 7.1) |  coNP-h (T. 7.1)
MaxJR |  NP-h (C. 3) |  NP-h (C. 3) |  NP-h(C. 3) |  NP-h (C. 3)
MaxEJR/ MaxPJR |  coNP-h (C. 5) |  coNP-h (C. 5) |  coNP-h (C. 5) |  coNP-h (C. 5)

Table 1: Summary of results. Please see Sections 3 for notations and
definitions.

##  2 Related Work

Our central model is approval-based committee (ABC) voting. One of the main
questions within ABC voting is how to produce committees which choose
candidates “proportional” to the support they receive from voters. Aziz et al.
[3] initiated a study of approval-based committee voting based on the idea of
“justified representation” for cohesive groups. The study has led to a large
body of work focusing on representation axioms and voting rules which produce
committees satisfying these axioms [4, 8] look more at query complexity and
approximate (E)JR For a detailed survey of the recent work on approval-based
committee voting, we refer the readers to the book of Lackner and Skowron
[19]. Bredereck et al. [7] take an experimental view of committees satisfying
JR/PJR/EJR and also examine the complexity of counting committees satisfying
these properties.

Uncertainty in preferences in voting problems has received interest in many
papers. Konczak and Lang [18] study winner determination with incomplete
preferences under ranking- based single-winner rules (such as plurality and
Borda). Hazon et al. [13] examine the probability of a particular candidate
winning an election under uncertain preferences for various voting rules such
as Plurality and Borda. Menon and Larson [20] studied facility location under
uncertain information. Our work combines aspects of uncertainty in preferences
with approval-based committee voting.

The two papers, recently published, that are most closely related to ours are
[15] and [12]. In one of the first detailed papers to consider approval-based
committee voting under uncertain preferences, Imber et al. [15] proposed
several models of incomplete information. Unlike our work, the input
information in their paper does not have quantitative information about
probabilities and the authors do not examine problems such as maximizing the
probability of satisfying an axiomatic property such as justified
representation. Three of the four uncertain preference models that we consider
are not explored by Imber et al. [15]. One of the models that we consider
(3VA) was also studied by Imber et al. [15]. For their incomplete information
models, they consider the problem of checking whether a given committee is
possibly or necessarily JR. For our uncertain preferences models, we also
consider other problems such as checking the existence of possibly or
necessarily JR and also computing the committee that maximizes the probability
of satisfying JR. Halpern et al. [12] looked at query complexity and
approximating JR and EJR for the problem of selecting comments based on
agreements and disagreements in platforms for online civic participation.
Their set-up is equivalent to ABC voting. In their work voters (users of the
platform) are randomly chosen and queried to express their
approval/disapproval on a small set of candidates (comments), generating
uncertaint/noisy information. Previously, Barrot et al. [6] also examined
single and multi-winner voting under uncertain approvals. Terzopoulou et al.
[22] examined the problem of checking whether an incomplete approval profile
admits a completion within a certain restricted domain of approval
preferences.

Uncertain preferences have been explored in other contexts as well, including
matching and allocations. Aziz et al. [1] study the problem of computing
stable matchings under uncertain preferences in the context of two-sided
matching. Aziz et al. [2] undertake a detailed complexity analysis of Pareto
optimal allocation under uncertain preferences. Aziz et al. [5] examine the
envy-free allocation under uncertain preferences. The Lottery and Joint
Probability models that we study are inspired by similar models in the context
of allocation and matching problems mentioned above. The Candidate-Probability
model that we introduce in the paper captures scenarios where the approval
probability may be based on a history of past choices.

##  3 Preliminaries

For any $t\in\mathbb{N}$, let $[t]\coloneqq\\{1,2,\dots,t\\}$. An _instance_
of the (deterministic) approval-based committee (ABC) voting is represented as
a tuple $(V,C,\mathcal{A},k)$, where:

  * •

$V=[n]$ and $C=[m]$ are the set of _voters_ and _candidates_ , respectively.

  * •

An approval set is a subset of candidates. Denote by $A_{i}$ voter $i$’s
approval set. $\mathcal{A}=(A_{1},A_{2},\dots,A_{n})$ is voters’ _approval
profile_. The set of all possible approval profiles is denoted as
$\mathbf{{A}}$.

  * •

$k$ is a positive integer representing the committee size.

A _winning committee_ $W\subseteq C$ is of size $k$. In the following, we
introduce proportional representation axioms, and begin with the central
notion of this paper, which is _justified representation (JR)_ [3].

######  Definition 1 (JR)

Given instance $(V,C,\mathcal{A},k)$, a committee $W$ is said to satisfy
_justified representation (JR)_ if for every group of voters
$V^{\prime}\subseteq V$ with $|V^{\prime}|\geq\frac{n}{k}$ and $\bigcap_{i\in
V^{\prime}}A_{i}\neq\emptyset$, it holds that $A_{i}\cap W\neq\emptyset$ for
some $i\in V^{\prime}$.

JR has been strengthened to stronger notions, of which _proportional justified
representation (PJR)_ [21] and _extended justified representation (EJR)_ [3]
are two important ones. In order to reason about the two notions, we first
introduce the concept of a cohesive group. For any positive integer $\ell$, a
group of voters $V^{\prime}\subseteq V$ is said to be _$\ell$ -cohesive_ if
$|V^{\prime}|\geq\ell\cdot\frac{n}{k}$ and $|\bigcap_{i\in
V^{\prime}}A_{i}|\geq\ell$.

######  Definition 2 (PJR and EJR)

Given instance $(V,C,\mathcal{A},k)$, a committee $W$ is said to satisfy _PJR_
(resp., _EJR_) if for every positive integer $\ell$ and every $\ell$-cohesive
group of voters $V^{\prime}\subseteq V$, it holds that $|\left(\bigcup_{i\in
V^{\prime}}A_{i}\right)\cap W|\geq\ell$ (resp., $|A_{i}\cap W|\geq\ell$ for
some $i\in V^{\prime}$).

As the definitions suggest, EJR $\implies$ PJR $\implies$ JR.

###  3.1 Uncertain Preference Models

We consider ABC voting where voters may be _uncertain_ about their approval
ballots. Specifically, we consider the following uncertainty models:

  1. 1.

Joint Probability model: We are given a probability distribution
$\Delta(\mathbf{{A}})\coloneqq\\{(\lambda_{r},\mathcal{A}_{r})\\}_{r\in[s]}$
over $s$ approval profiles with $\sum_{r\in[s]}\lambda_{r}=1$, where for each
$r\in[s]$, the approval profile $\mathcal{A}_{r}$ is associated with a
positive probability $\lambda_{r}>0$. We write
$\Delta(\mathcal{A}_{r})=\lambda_{r}$.

  2. 2.

Lottery model: For each voter $i\in V$, we are given a probability
distribution
$\Delta_{i}(2^{C})\coloneqq\\{(\lambda_{r},S_{r})\\}_{r\in[s_{i}]}$ over
$s_{i}$ approval sets with $\sum_{r\in[s_{i}]}\lambda_{r}=1$, where for each
$r\in[s_{i}]$, the candidate set $S_{r}\subseteq C$ is associated with a
positive probability $\lambda_{r}>0$. We write
$\Delta_{i}(S_{r})=\lambda_{r}$. We assume that the probability distributions
of voters are independent.

  3. 3.

Candidate-Probability model: Each voter $i$ approves each candidate $c$
independently with probability $p_{i,c}$, i.e., for each $i\in V$ and each
$c\in C$, $p_{i,c}\in[0,1]$.

  4. 4.

Three-Valued Approval (3VA) model: Each voter specifies a subset of candidates
that are approved and a subset of candidates that are disapproved. The
remaining candidates could be approved or disapproved with equal probability.
That is, $p_{i,c}\in\\{0,0.5,1\\},\forall i\in V,c\in C$, wherein 0 denotes
disapproval, 1 indicates approval, and 0.5 represents unknown.

The Joint Probability and Lottery models have been studied in other contexts
including two-sided stable matching problem and assignment problem [2, 1]. The
3VA model has been studied in the ABC voting [15]. The Candidate-Probability
model is a direct generalisation of the 3VA model. Under Candidate-Probability
and 3VA models, $p_{i,c}$’s are assumed to be independent. We refer to an
approval profile that can occur with positive probability, under any of the
uncertainty models, as a _plausible_ approval profile.

###### Proposition 1

There is a unique Joint Probability model representation for preferences given
in the Lottery model.

###### Proof

The Joint Probability representation entails the probability distribution
across each distinct profile of approval sets for all voters. In the Lottery
model, the probability distribution of voters for various approval sets is
known. The Joint Probability of a profile comprising approval sets from all
voters can be obtained by multiplying the individual voter’s approval
probabilities i.e.,
$\Delta(\mathcal{A})=\prod_{i}\Delta_{i}(\mathcal{A}_{i}),\forall\mathcal{A}\in\mathbf{{A}}$.

###### Proposition 2

There is a unique Lottery model representation for preferences given in
Candidate-Probability model.

###### Proof

The probability distribution across approval sets can be deduced from a
probability distribution over candidates albeit with an exponential increase
in complexity. The probability of voter $i$ approving a candidate set $S$ can
be computed as $\Delta_{i}(S)=\prod_{c\in S}(p_{i,c})\times\prod_{c\in
C\setminus S}(1-p_{i,c})$.

_Example:_ This example illustrates the transition from an instance in the
Candidate Probability model, where voters have probabilities for individual
candidates, to an instance in the Lottery model, where probabilities are
assigned to sets of candidates. Assume there are 3 candidates and one voter.
The approval probabilities of voter $1$ for the three candidates are
$p_{1,1}=0.9,~{}p_{1,2}=0.6,$ and $p_{1,3}=0.5$. The probability of voter $1$
approving a candidate set, say $\\{1,3\\}$, is calculated as
$\Delta_{1}({1,3})=0.9\times(1-0.6)\times 0.5=0.18$.

###  3.2 Computational Problems

We are interested in extending the quest for a committee that satisfies JR,
PJR or EJR to the realm of uncertainty. For ease of exposition, we use JR as
an exemplary property to introduce the most natural computational problems of
interest.

#### Possible JR

In Section 4, we examine computational problems related to _possible JR_.
Possible JR refers to the property that a committee has non-zero probability
of satisfying JR. Fix any uncertain preference model defined in Section 3.1.
Given as input voters’ uncertain preferences,

  * •

IsPossJR is the problem of deciding whether a given committee $W$ satisfies JR
with non-zero probability;

  * •

ExistsPossJR is the problem of deciding whether there exists a committee $W$
that satisfies JR with non-zero probability.

#### Necessary JR

In Section 5, we examine computational problems related to _necessary JR_. Fix
any uncertain preference model. Given as input voters’ uncertain preferences,

  * •

IsNecJR is the problem of deciding whether a given committee $W$ satisfies JR
with probability $1$;

  * •

ExistsNecJR is the problem of deciding whether there exists a committee $W$
that satisfies JR with probability $1$.

#### JR Probability

In Section 6, we examine the problem referred to as JR-Probability. It is the
problem of computing the probability that a given committee $W$ satisfies JR.
Since we are interested in computing desirable committees under uncertainty,
we also provide results for the following problem: MaxJR: Computing a
committee $W$ that has the highest probability of satisfying JR. Note that
ExistsNecJR reduces to MaxJR.

Finally, in Section 7 we examine the same set of computational problems for
PJR and EJR.

##  4 Possible JR

In this section, we examine problems related to the Possible JR. Firstly, we
note that ExistsPossJR trivially has a yes answer for all of our probability
models. This is due to the fact that for any _plausible_ approval profile
there exists a committee $W$ that satisfies JR (Theorem 1 in [3]). Note that
$W$ satisfies JR with non-zero probability iff there exists a _plausible_
approval profile for which $W$ satisfies JR.

Given a committee $W$, IsPossJR can be solved in polynomial time for the Joint
Probability model. The polynomial-time procedure involves taking each
_plausible_ approval profile, which are explicitly provided in the input, in
turn and checking whether $W$ satisfies JR for any such profiles. The latter
can be done in polynomial time (see Theorem 2 in [3]). This problem is also in
complexity class P for the 3VA and candidate-probability models (corollaries
of Theorem 13 in [15]). Under the lottery model, however, IsPossJR in NP-
complete.

###### Theorem 4.1

IsPossJR, the problem of deciding whether a given committee $W$ satisfies JR
with non-zero probability, is NP-complete for the Lottery model, even when
each voter assigns positive probability to at most three approval sets and
$k=\frac{n}{2}$.

###### Proof

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.

_Example:_ To aid the reader in understanding the above proof, we provide the
following example illustrating the reduction. Consider the following 3CNF
formula: $(x_{1}\lor x_{2}\lor x_{3})\land(x_{1}\lor
x_{2}\lor\bar{x_{3}})\land(\bar{x_{3}}\lor\bar{x_{2}}\lor
x_{4})\land(x_{1}\lor x_{2}\lor x_{4})$. This instance has 4 clauses and 4
variables. To reduce to an instance of IsPossJR, we create a voter per clause,
hence $V=\\{1,2,3,4\\}$. We will have three types of candidates. Let
$C_{1}=\\{\ell_{1},\ldots,\ell_{12}\\}$, let
$C_{2}=\\{c_{2,8},c_{3,6},c_{3,7},c_{5,8},c_{8,11}\\}$, and add a dummy
candidates set $\\{c_{1},c_{2}\\}$. We have $k=\frac{4}{2}=2$ and
$W=\\{c_{1},c_{2}\\}$. Each voter assigns a positive probability to exactly 3
approval sets:

  * •

Voter 1: $\\{\ell_{1}\\}$, $\\{\ell_{2},c_{2,8}\\}$,
$\\{\ell_{3},c_{3,6},c_{3,7}\\}$

  * •

Voter 2: $\\{\ell_{4}\\}$, $\\{\ell_{5},c_{5,8}\\}$, $\\{\ell_{6},c_{3,6}\\}$

  * •

Voter 3: $\\{\ell_{7},c_{3,7}\\}$, $\\{\ell_{8},c_{2,8},c_{5,8},c_{8,11}\\}$,
$\\{\ell_{9}\\}$

  * •

Voter 4: $\\{\ell_{10}\\}$, $\\{\ell_{11},c_{8,11}\\}$, $\\{\ell_{12}\\}$

##  5 Necessary JR

In this section, we examine problems related to the Necessary JR. Firstly, we
note that IsNecJR, the problem of deciding whether a given committee $W$
satisfies JR with probability one, is trivially in P for the joint probability
model. The polynomial time procedure involves taking each _plausible_ approval
profile in turn and checking whether $W$ satisfies JR for each _plausible_
profiles. The latter can be done in polynomial time (see Theorem 2 in [3]).
This problem is in P also for the 3VA and candidate-probability models
(immediate corollary of Theorem 13 in [15]). This problem is in P for the
Lottery model too.

###### Theorem 5.1

IsNecJR, the problem of deciding whether a given committee $W$ satisfies JR
with probability 1, is solvable in polynomial time for the Lottery model.

###### Proof

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.

ExistsNecJR, the problem of deciding whether there exists a committee $W$ that
satisfies JR with probability 1, is NP-complete for our four models. We prove
by reducing from the following problem, which we will show is NP-complete.
Note that in the definition of JR (see Definition 1) the size of $W$ was set
to be equal to $k$, the size of the committee to be selected. One can however
modify this and let $W$ be of size at most $k$, allowing to choose a committee
of size smaller than $k$.

###### Definition 3

SizeJR is the problem of deciding, given an instance $(V,C,\mathcal{A},k)$ of
ABC voting and a positive integer $r<k$, whether there exists a committee $W$,
$|W|=r$, such that $W$ satisfies JR.

###### Lemma 1

SizeJR is NP-complete.

###### Proof

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.

###### Lemma 2

Let $I=(V,C,[p_{i,c}],k)$ be an instance of ABC voting under Candidate-
Probability model. If $0<p_{i,c}<1$ for all voters $i$ and candidates $c$,
then a committee $W$ satisfies JR with probability 1 iff $W=C$ and $k=|C|$.

###### Proof

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

###### Theorem 5.2

ExistsNecJR, the problem of deciding whether there exists a committee $W$ that
satisfies JR with probability 1, is NP-complete for the Candidate-Probability
model.

###### Proof

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.

###### Corollary 1

ExistsNecJR is NP-complete for the 3VA models.

We can show that ExistsNecJR is NP-complete for the Lottery model and Joint
Probability model, using an almost identical argument as to the one presented
in the proof of Theorem 5.2. The main variation is the instance reduction due
to a different problem setting.

###### Theorem 5.3

ExistsNecJR, the problem of deciding whether there exists a committee $W$ that
satisfies JR with probability 1, is NP-complete for the Lottery model and
Joint Probability model.

###### Proof

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.

_Lottery model:_ Given an instance $I=(V,C,\mathcal{A},k,r)$ of SizeJR, we
reduce to an instance
$I^{\prime}=(V^{\prime},C^{\prime},[\Delta_{i}],k^{\prime})$ of ExistsNecJR
under the Lottery 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 $2k-r$ new candidates $\\{1+m,\ldots,2k-r+m\\}$. Each
voter in $V$ approves of $A_{i}$ with probability 1, i.e.
$\Delta_{i}(A_{i})=1$. For each voter $i\in V^{+}$ we have
$\Delta_{i}(\\{j+m\\})=\frac{1}{2k-r}$, for all $j\in[1,2k-r]$. Let
$k^{\prime}=2k$.

_Joint Probability model:_ Given an instance $I$ 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. $V^{\prime}$ and $C^{\prime}$
are defined as in above. Let
$\Delta(A_{1},\ldots,A_{n},\\{j+m\\},\dots,\\{j+m\\})=\frac{1}{2k-r}$, for all
$j\in[1,2k-r]$. That is, there are exactly $2k-r$ _plausible_ approval
profiles, each voter $i\in V$ approves of $A_{i}$ under all _plausible_
approval profiles, and the new voters all approve of exactly one new
candidate, and only that candidate, in exactly one _plausible_ approval
profile. Let $k^{\prime}=2k$.

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.

We observe that, under the Joint Probability model, ExistsNecJR is NP-complete
even when minimal uncertainty is present.

###### Theorem 5.4

ExistsNecJR is NP-complete for the Joint Probability model even if there are
only two approval profiles $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ associated
with a positive probability; i.e., $s=2$ and $\lambda_{1}=1-\lambda_{2}$.

###### Proof

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.

ExistNecJR is in P for the Lottery model when each voter approves of only one
candidate in each _plausible_ approval profile.

###### Theorem 5.5

ExistNecJR is in P for the Lottery model when each voter specifies a
probability distribution over approval sets, with each set containing a single
candidate.

###### Proof

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.

##  6  JR-Probability

JR-Probability is the problem of determining the probability that a given $W$
satisfies JR, which is defined as follows:
$p(W~{}\text{satisfies}~{}JR)=\sum_{\mathcal{A}\in\mathbf{{A}}}\Delta(\mathcal{A})\times\mathcal{I}(\text{\sc
IsJR}(W,\mathcal{A})),$ where $\mathcal{I}$ is an indicator function that
returns 1 when IsJR$(W,\mathcal{A})$ is a YES instance, i.e. $W$ satisfies JR
for $\mathcal{A}$, and 0 otherwise.

Given a set $W$ and an approval profile $\mathcal{A}$, we can check in
polynomial time whether $W$ satisfies JR or not (see Theorem 2 in [3]). The
Joint Probability model takes approval profiles and their corresponding
probability distributions as input. Therefore,

###### Theorem 6.1

JR-Probability  is in P for the Joint probability model.

The decision variant of the JR-Probability involves assessing whether the JR
probability of $W$ exceeds a designated threshold, denoted as $\tau$. Notably,
when $\tau$ is set to zero, the problem transforms into IsPossJR which is NP-
complete (Theorem 4.1). Therefore,

###### Corollary 2

JR-Probability is NP-hard for the Lottery model.

JR-Probability is #P-complete for the 3VA model, and hence consequently for
the Candidate Probability model. We prove by reducing from #VertexCovers, the
problem of counting the number of vertex covers for a given graph, that we
will show is #P-complete by a short proof.

###### Lemma 3

#VertexCovers (#VC) is #P-complete.

###### Proof

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

Solving JR-Probability for the 3VA model involves counting the number of
_plausible_ approval profiles for which the given $W$ satisfies JR.

###### Theorem 6.2

JR-Probability is #P-complete for the 3VA model.

###### Proof

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

###### Theorem 6.3

JR-Probability is in P for the 3VA model if $p_{i,c}\in\\{0,1\\}$, $\forall
i\in V$ and $\forall c\in W$.

###### Proof

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.

The above process ultimately computes the count of _plausible_ approval
profiles where $W$ satisfies JR, divided by the total number of _plausible_
approval profiles. It is essential to note that the same computation will not
work when each profile has a different probability, as is the case in the
candidate probability model. We also observe that for the 3VA model, the
computation of JR-Probability is achievable in polynomial time if $n=k$.

###### Theorem 6.4

In the 3VA model, counting the _plausible_ approval profiles where $W$
satisfies JR can be computed in polynomial time if $k=n$. Hence, JRProbability
is in P when $k=n$.

###### Proof

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

Note that ExistsNecJR reduces to MaxJR. The following result then follows from
the NP-completeness of ExistsNecJR for all of our four uncertainty models.

###### Corollary 3

MaxJR is NP-hard for all of our four uncertainty models.

##  7 Results for PJR and EJR

In this section, we provide answers to the computational problems under the
stronger concepts of PJR and EJR. Our proofs rely on the coNP-complete
problems of IsEJR and IsPJR (see [3, 4]). IsEJR (resp. IsPJR) is the problem
of deciding, given an instance $(V,C,\mathcal{A},k)$ of ABC voting and a
committee $W$, whether $W$ satisfies EJR (resp. PJR). The coNP-completeness of
these problems gives us the following result immediately.

###### Corollary 4

IsNecEJR (resp. IsNecPJR), the problem of deciding whether a given committee
$W$ satisfies EJR (resp. PJR) with probability 1, and IsPossEJR (resp.
IsPossPJR), the problem of deciding whether a given committee $W$ satisfies
EJR (resp. PJR) with non-zero probability, are both coNP-complete for all of
our four uncertainty models.

###### Theorem 7.1

ExistsNecEJR (resp. ExistsNecPJR), the problem of deciding whether there
exists a committee $W$ that satisfies EJR (resp. PJR) with probability 1 is
coNP-hard for the Candidate-Probability and 3VA models.

###### Proof

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^{+}$)111Set $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.

We can show that ExistsNecEJR (resp. ExistsNecPJR) is coNP-hard for the
Lottery and Joint Probability models, using an almost identical argument as to
the one presented in the proof of Theorem 7.1 . The main variation is the
instance reduction due to a different problem setting. We omit the proof due
to shortage of space.

###### Theorem 7.2

ExistsNecEJR (resp. ExistsNecPJR) is coNP-hard for the Lottery and Joint
Probability models.

###### Proof

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.

_Lottery model:_ Given an instance $I=(V,C,\mathcal{A},W,k)$ of IsEJR, we
reduce to an instance
$I^{\prime}=(V^{\prime},C^{\prime},[\Delta_{i}],k^{\prime})$ of ExistsNecEJR
under the Lottery 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$,
$\Delta_{i}(A_{i})=1$. For each voter $i\in V^{+}$ we have
$\Delta_{i}(\\{c_{j}\\})=\frac{1}{2k},~{}\forall c_{j}\in W\cup C^{+}$. Let
$k^{\prime}=2k$. As $|V^{\prime}|=2|V|$ we have that
$|V^{\prime}|/k^{\prime}=|V|/k=n/k$.

_Joint Probability model:_ Given an instance $I=(V,C,\mathcal{A},W,k)$ of
IsEJR, we reduce to an instance
$I^{\prime}=(V^{\prime},C^{\prime},\Delta,k^{\prime})$ of ExistsNecEJR under
the Joint 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}\\}$. Let
$\Delta(A_{1},A_{2},\ldots,A_{n},\\{c_{j}\\},\ldots,\\{c_{j}\\})=\frac{1}{2k}$,
$\forall c_{j}\in W\cup C^{+}$. Let $k^{\prime}=2k$. As $|V^{\prime}|=2|V|$ we
have that $|V^{\prime}|/k^{\prime}=|V|/k=n/k$.

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.

MaxEJR (resp. MaxPJR) is the problem of computing a committee $W$ that has the
highest probability of satisfying EJR (resp. PJR). Note that ExistsNecEJR
(resp. ExistsNecPJR) reduces to MaxEJR (resp. MaxPJR). The following result
then follows from the coNP-hardness of ExistsNecEJR (resp. ExistsNecPJR).

###### Corollary 5

MaxEJR (resp. MaxPJR) is coNP-hard for all of our four uncertainty models.

###### Proof

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.

##  8 Conclusion

We have formalized uncertain preferences models for a well-studied committee
selection problem. We focused primarily on a fundamental concept of
proportional representation called justified representation (JR). Our work
suggests several directions including exploring other axiomatic properties
such as Pareto optimality, welfare maximization, or other notions of fairness.
In our study, the central problem is MaxJR. It will be interesting to explore
approximation or fixed-parameter tractable (FPT) algorithms for this problem.
Finally, another direction is to explore restricted versions of approval
preferences [9, 22].

#### Acknowledgments

This work was supported by the NSF-CSIRO grant on “Fair Sequential Collective
Decision-Making" (Grant No. RG230833). Venkateswara Rao Kagita is grateful to
Science and Engineering Research Board (SERB) for providing financial support
for this research through the SERB-SIRE project (Project Number:
SIR/2022/001217). Mashbat Suzuki is supported by the ARC Laureate Project
FL200100204 on “Trustworthy AI”. Baharak Rastegari is grateful to UNSW
Sydney’s Faculty of Engineering for supporting her research visit through
Diversity in Engineering Academic Visitor Funding Scheme.

## References

  * Aziz et al. [2020] Aziz, H., Biró, P., Gaspers, S., de Haan, R., Mattei, N., Rastegari, B.: Stable matching with uncertain linear preferences. Algorithmica 82(5), 1410–1433 (2020)
  * Aziz et al. [2019] Aziz, H., Biró, P., de Haan, R., Rastegari, B.: Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity. Artificial Intelligence 276, 57–78 (2019)
  * Aziz et al. [2017] Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., Walsh, T.: Justified representation in approval-based committee voting. Social Choice and Welfare 48(2), 461–485 (2017)
  * Aziz et al. [2018] Aziz, H., Elkind, E., Huang, S., Lackner, M., Fernández, L.S., Skowron, P.: On the complexity of extended and proportional justified representation. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (2018)
  * Aziz et al. [2024] Aziz, H., Iliffe, I., Li, B., Ritossa, A., Sun, A., Suzuki, M.: Envy-free house allocation under uncertain preferences. In: Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, pp. 9477–9484, AAAI Press (2024)
  * Barrot et al. [2013] Barrot, N., Gourvès, L., Lang, J., Monnot, J., Ries, B.: Possible winners in approval voting. In: Proceedings of Algorithmic Decision Theory - Third International Conference, ADT 2013, Lecture Notes in Computer Science, vol. 8176, pp. 57–70, Springer (2013)
  * Bredereck et al. [2019] Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Niedermeier, R.: An experimental view on committees providing justified representation. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, pp. 109–115, ijcai.org (2019)
  * Brill et al. [2017] Brill, M., Freeman, R., Janson, S., Lackner, M.: Phragmén’s voting methods and justified representation. In: 31st, pp. 406–413, AAAI Press (2017)
  * Elkind et al. [2022] Elkind, E., Lackner, M., Peters, D.: Preference restrictions in computational social choice: A survey. CoRR abs/2205.09092 (2022)
  * Garey and Johnson [1979] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
  * Greenhill [2000] Greenhill, C.S.: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complex. 9(1), 52–72 (2000)
  * Halpern et al. [2023] Halpern, D., Kehne, G., Procaccia, A.D., Tucker-Foltz, J., Wüthrich, M.: Representation with incomplete votes. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence and 35th Conference on Innovative Applications of Artificial Intelligence and 13th Symposium on Educational Advances in Artificial Intelligence (AAAI/IAAI/EAAI), pp. 5657 – 5664, AAAI Press (2023)
  * Hazon et al. [2012] Hazon, N., Aumann, Y., Kraus, S., Wooldridge, M.: On the evaluation of election outcomes under uncertainty. Artificial Intelligence 189, 1–18 (2012)
  * Himabindu et al. [2018] Himabindu, T.V., Padmanabhan, V., Pujari, A.K.: Conformal matrix factorization based recommender system. Information Sciences 467, 685–707 (2018)
  * Imber et al. [2022] Imber, A., Israel, J., Brill, M., Kimelfeld, B.: Approval-based committee voting under incomplete information. In: 36th, pp. 5076–5083, AAAI Press (2022)
  * Kagita et al. [2017] Kagita, V.R., Pujari, A.K., Padmanabhan, V., Sahu, S.K., Kumar, V.: Conformal recommender system. Information Sciences 405, 157–174 (2017)
  * Kilgour [2010] Kilgour, D.M.: Approval balloting for multi-winner elections. In: Laslier, J.F., Sanver, M.R. (eds.) Handbook on Approval Voting, chap. 6, pp. 105–124, Springer (2010)
  * Konczak and Lang [2005] Konczak, K., Lang, J.: Voting procedures with incomplete preferences. In: Multidisciplinary Workshop on Advances in Preference Handling, pp. 124–129 (2005)
  * Lackner and Skowron [2023] Lackner, M., Skowron, P.: Multi-Winner Voting with Approval Preferences. Springer Briefs in Intelligent Systems, Springer (2023)
  * Menon and Larson [2019] Menon, V., Larson, K.: Mechanism design for locating a facility under partial information. In: Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), pp. 49–62, Springer (2019)
  * Sánchez-Fernández et al. [2017] Sánchez-Fernández, L., Elkind, E., Lackner, M., Fernández, N., Fisteus, J.A., Basanta Val, P., Skowron, P.: Proportional justified representation. In: 31st, AAAI Press (2017)
  * Terzopoulou et al. [2021] Terzopoulou, Z., Karpov, A., Obraztsova, S.: Restricted domains of dichotomous preferences with possibly incomplete information. In: 35th, pp. 5726–5733, AAAI Press (2021)