Department of Computer Science, University of California, Santa Barbara,
USAcsonar@cs.ucsb.eduhttps://orcid.org/0000-0002-1825-0097Department of
Computer Science, University of California, Santa Barbara<EMAIL_ADDRESS>Department of Computer Science, New York University, Shanghai,
<EMAIL_ADDRESS>Jane Open Access and Joan R. Public [100]Theory of
computation $\xrightarrow{}$ Randomness geometry and discrete structures
$\xrightarrow{}$ Computational geometry John Q. Open and Joan R. Access 2 42nd
Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December
24–27, 2016 Little Whinging, United Kingdom 42 23

# Fault Tolerance in Euclidean Committee Selection

Chinmay Sonar  Subhash Suri  Jie Xue

###### Abstract

In the committee selection problem, the goal is to choose a subset of size $k$
from a set of candidates $C$ that collectively gives the best representation
to a set of voters. We consider this problem in Euclidean $d$-space where each
voter/candidate is a point and voters’ preferences are implicitly represented
by Euclidean distances to candidates. We explore _fault-tolerance_ in
committee selection and study the following three variants: (1) given a
committee and a set of $f$ failing candidates, find their optimal replacement;
(2) compute the worst-case replacement score for a given committee under
failure of $f$ candidates; and (3) design a committee with the best
replacement score under worst-case failures. The score of a committee is
determined using the well-known (min-max) Chamberlin-Courant rule: minimize
the maximum distance between any voter and its closest candidate in the
committee. Our main results include the following: (1) in one dimension, all
three problems can be solved in polynomial time; (2) in dimension $d\geq 2$,
all three problems are NP-hard; and (3) all three problems admit a constant-
factor approximation in any fixed dimension, and the optimal committee problem
has an FPT bicriterion approximation.

###### keywords:

Multiwinner elections, Fault tolerance, Geometric Hitting Set, EPTAS

###### category:

##  1 Introduction and Problem Statement

We consider the computational complexity of adding fault tolerance into
spatial voting. In spatial voting [6, 1, 32], the voters and the candidates
are both modeled as points in some $d$-dimensional space, where each dimension
represents an independent _policy issue_ that is important for the election,
and each voter’s preference among the candidates is implicitly encoded by a
distance function. For example, in the simplest $1$-dimensional setting,
voters and candidates are points on a line indicating their real-valued
preference on a single issue. The specific setting for our work is
_multiwinner_ spatial elections, also called _committee selection_ , in $d$
dimensions where we have a set $V$ of $n$ voters, a set $C$ of $m$ candidates,
and a committee size (integer) $k$. The goal is to choose a subset of $k$
candidates, called the _winning committee_ , that collectively best represents
the preferences of all the voters [9, 11, 12].

One aspect of committee selection that appears not to have been investigated
is _fault tolerance_ , that is, how robust a chosen committee is against the
possibility that some of the winning members may default. Committee selection
problems model a number of applications in the social sciences and in computer
science where such defaults are not uncommon, such as democratic elections,
staff hiring, choosing public projects, locations of public facilities, jury
selection, cache management, etc. [23, 14, 29, 2, 3, 25, 13]. In this paper,
we are particularly interested in designing algorithms to address questions of
the following kind: If some of the winning members default, how badly does
this affect the overall score of the committee? Or, how much does the
committee score suffer if a _worst-case_ subset of size $f$ defaults? Finally,
can we _proactively_ choose a committee in such a way that it can tolerate up
to $f$ faults with the minimum possible score degradation? We begin by
formalizing these problems more precisely and then describing our results.

Suppose $V=\\{v_{1},\ldots,v_{n}\\}$ is a set of $n$ voters and
$C=\\{c_{1},\ldots,c_{m}\\}$ is a set of $m$ candidates, modeled as points in
$d$-dimensional Euclidean space. (We occasionally call the tuple $(V,C)$ an
election $E$.) Given a positive integer $k$, we want to elect $k$ candidates,
called the _committee_ , using the well-known Chamberlin-Courant voting rule
[4]. This rule assigns a score to each committee as follows. Let $T\subseteq
C$ be a committee. For each voter $v$, the score of $T$ for $v$ is defined as
$\sigma(v,T)=\min_{c\in T}d(v,c)$, namely, the distance from $v$ to its
closest candidate in $T$.111Originally, Chamberlin and Courant [4] defined a
voting rule on Borda scores (also known as Borda-CC). In this paper, similarly
to [2], we study a min-max version of this rule on a more general scoring
function, which in our case is based on voter-candidate distances. The _score_
of the committee $T$ is defined as $\sigma(T)=\max_{v\in V}\sigma(v,T)$,
namely, the largest distance between any voter and its closest neighbor in
$T$. (In facility location parlance, this is the well-known $k$-center
problem.)

The fault tolerance of a committee is parameterized by a positive integer $f$,
which is the upper bound on the number of candidates that can fail.222In our
work, we will allow any subset of size $f$ from $C$ to fail, so the faults can
also include candidates not in the selected committee $T$. This only makes the
problem harder because the adversary can always limit the faults to $T$, and
elimination of candidates from $C\setminus T$ makes finding replacements for
failing committee members more difficult. Throughout the paper, we use the
notation $J$ to denote a failing set of candidates. We are allowed to replace
the failing members of $J$ with any set of at most $|T\cap J|$ candidates from
$C\setminus J$. We often denote this set of _replacement_ candidates by $R$.
However, _we must keep all the non-failing members of $T$ in the committee_ —
that is, the replacement committee is the set $(T\setminus J)\cup R$ — and
throughout the paper our goal is to optimize this committee’s score, namely
$\sigma((T\setminus J)\cup R)$.

We consider the following three versions of fault-tolerant committee
selection, presented in increasing order of complexity. The first problem is
the simplest: given a committee and a failing set, find the best replacement
committee.

Optimal Replacement Problem (ORP) Input: An election $E=(V,C)$, a committee
$T\subseteq C$ and a failing set $J\subseteq C$. Goal: Find a replacement set
$R\subseteq C\setminus J$ of size at most $|T\cap J|$ minimizing
$\sigma((T\setminus J)\cup R)$.

Our second problem is to quantify the fault tolerance of a given committee $T$
over worst-case faults. That is, what is the largest score of $T$’s
replacement when a worst-case subset of $f$ faults occur? We introduce the
following notation as $T$’s measure of $j$-fault-tolerance, for any $0\leq
j\leq f$: $\sigma_{j}(T)\leavevmode\nobreak\ \leavevmode\nobreak\
=\leavevmode\nobreak\ \leavevmode\nobreak\ \max_{J\subseteq
C\leavevmode\nobreak\ s.t.\leavevmode\nobreak\ |J|\leq j}\sigma((T\setminus
J)\cup R),$ where $R$ is an optimal replacement set with size at most $|T\cap
J|$. We want to compute $\sigma_{f}(T)$. Occasionally, we also use the
notation $\sigma_{0}(T)$ for the no-fault score of $T$, namely $\sigma(T)$.

Fault-Tolerance Score (FTS) Input: An election $E=(V,C)$, a committee
$T\subseteq C$ and a fault-tolerance parameter $f$. Goal: Compute
$\sigma_{f}(T)$.

Our third and final problem is to compute a committee with optimal fault-
tolerance score.

Optimal Fault-Tolerant Committee (OFTC) Input: An election $E=(V,C)$, a
committee size $k$ and a fault-tolerance parameter $f$. Goal: Find $T\subseteq
C$ of size at most $k$ minimizing $\sigma_{f}(T)$.

###  1.1 Our Results

We first show that even in one dimension, fault-tolerant committee problems
are nontrivial. In particular, while the Optimal Replacement Problem (ORP) is
easily solved by a simple greedy algorithm, the other two problems, Fault-
Tolerance Score (FTS) and Optimal Fault-Tolerant Committee (OFTC), do not
appear to be easy. Our main result in one dimension is the design of efficient
dynamic-programming-based algorithms for these two problems. Along the way, we
solve a _fault-tolerant_ Hitting Set problem for points and unit intervals,
which may be of independent interest.

In two dimensions and higher, OFTC is NP-hard because of its close connection
to the $k$-center problem. However, we show that even the seemingly simpler
problem of optimal replacement (ORP) is also NP-hard. Our main results include
a constant-factor approximation for all three problems in any fixed dimension
(in fact, in any metric space), as well as a novel bicriterion FPT
approximation via an EPTAS whose running time has the form
$f(\epsilon)n^{\mathcal{O}(1)}$. For ease of reference, we show these results
in the following table.

|  One-dimensional instances | Dimension $d\geq 2$
---|---|---
| Complexity | Approximation | Bounded $f$
ORP |  | P
---
(Theorem 2.1)
| NP-hard
---
(Theorem 3.1)
| 3-approx.
---
(Lemma 3.11)
| P
---
(Section 3.1.3)
FTS |  | P
---
(Theorem 2.7)
| NP-hard
---
(Theorem 3.1)
| 3-approx.
---
(Lemma 3.14)
| P
---
(Section 3.1.3)
OFTC |  | P
---
(Theorem 2.12)
| NP-hard
---
(Theorem 3.1)
| 5-approx.
---
(Lemma 3.20)
Bicriterion-EPTAS
(Theorem 3.28)
| NP-hard
---
(Section 3.1.3)
3-approx.
(Theorem 3.19)
Table 1: Summary of our results.

###  1.2 Related Work

To the best of our knowledge, the issue of fault tolerance in committee
selection has not been studied in voting literature — their primary focus is
on protocols and algorithms for choosing candidates [11, 12, 27, 30, 31, 8].
However, the following two lines of work consider some related issues. First,
in the “unavailable candidate model” [24, 16] the goal is to choose a _single
winner_ with maximum expected score when candidates fail according to a given
probability distribution; in contrast, we consider multiwinner elections under
worst-case faults. In the second line of work, a set of election control
problems are considered where candidates are added [10] or deleted [18] to
change the outcome of the election. In this setting, the candidate set is
modified to obtain a favorable election outcome, which is a rather different
problem than ours.

In the facility-location research, there has been prior work on adding fault
tolerance to $k$-center or $k$-median solutions [5, 22, 21, 34, 17], but the
main approach there is to assign each user (voter) to multiple facilities
(candidates). In particular, the “$p$-neighbor $k$-center” framework [5]
minimizes the maximum distance between a user and its $p$th center as a way to
protect against $p-1$ faults. This formulation, however, differs from our
optimal fault-tolerant committee problem (OFTC) because in our setting the
replacement candidates are chosen _after_ failing candidates are announced.
Therefore, in the OFTC problem, the designer does not have to _simultaneously_
allocate $p$ neighbors for all the voters. Furthermore, to the best of our
knowledge, neither of our first two problems — Optimal Replacement (ORP) and
Fault-Tolerance Score (FTS) — have been studied in the facility-location
literature, and initiate a new research direction. We also formulate and solve
a fault-tolerant hitting set problem in one dimension, which may be of
independent interest.

##  2 Fault-Tolerant Committees in One Dimension

Even in one dimension, computing the fault-tolerance score of a given
committee or finding a committee with minimum fault-tolerance score is
nontrivial. The optimal replacement problem, however, is easy — a simple
greedy algorithm works. Our main result in this section is to design efficient
dynamic-programming algorithms for the former two problems. In doing so, we
also solve the fault-tolerant version of Hitting Set for points and unit
segments.

###  2.1 Optimal Replacement Problem

In the Optimal Replacement Problem (ORP), we are given a committee $T\subseteq
C$ and a failing set $J\subseteq C$, and we must find a replacement set $R$
minimizing the score $\sigma((T\setminus J)\cup R)$, where $|R|\leq|T\cap J|$.
Since this score is always the distance between some voter-candidate pair, it
suffices to solve the following decision problem: Is there a replacement set
with score at most $r$? We can then try all possible $O(nm)$ distances to find
the smallest feasible replacement score.

This decision problem is equivalent to the following hitting set problem: for
each voter $v\in V$, let $I_{v}$ be the interval of length $2r$ centered at
$v$, and let $\mathcal{I}=\\{I_{v}:v\in V\\}$ be the set of these $n$ (voter)
intervals. A subset of candidates is a hitting set for $\mathcal{I}$ if each
interval contains at least one of the candidates. In our problem, we are given
a hitting set $T$ and a failing subset of candidates $J$, and we must find the
minimum-size replacement hitting set. Such a replacement is easily found using
the standard greedy algorithm, as follows. We first remove all of the
intervals from $\mathcal{I}$ that are already hit by a candidate in
$T\setminus J$, and we also remove all the failing candidates $J$ from $C$.
For the leftmost remaining interval, we then choose the rightmost candidate
$c$ contained in it, add it to $R$, delete all intervals hit by $c$, and
iterate until all remaining intervals are hit. If we ever encounter an
interval containing no candidate, or if the size of the replacement set is
larger than $|T\setminus J|$, the answer to the decision problem is no.
Otherwise, the solution is $R$. The greedy algorithm is easily implemented to
run in time $\mathcal{O}((m+n)\log(m+n))$. To find the optimal replacement
set, we can do a binary search over $O(nm)$ values of $r$ and find the
smallest $r$ for which $|(T\setminus J)\cup R|\leq k$.

######  Theorem 2.1.

The Optimal Replacement Problem can be solved in time
$\mathcal{O}((m+n)\log^{2}(m+n))$ for one-dimensional Euclidean elections.

###  2.2 Computing the Fault-Tolerance Score (FTS) of a Committee

We now come to the more difficult problem of computing the fault-tolerance
score $\sigma_{f}(T)$ of a committee $T$ in one dimension, which is the worst
case over all possible failing sets of $T$. Once again it suffices to solve
the following decision problem: given a size-$k$ committee $T$ and a real
number $r$, can we find a replacement with score at most $r$ for _every_
failing subset of size $f$? Using our hitting set formulation,
$\sigma_{f}(T)\leq r$ if and only if $T$ is an _$f$ -tolerant hitting set_ of
$\mathcal{I}$, that is, for any failing set $J\subseteq C$ of size at most
$f$, there exists a replacement set $R\subseteq C\setminus J$ such that
$|(T\setminus J)\cup R|\leq|T|$ and $(T\setminus J)\cup R$ hits $\mathcal{I}$.
(Recall that each member of $\mathcal{I}$ is an interval of length $2r$
centered at one of the voter positions.) We can then compute the fault-
tolerance score of $T$ by trying each of the $O(nm)$ voter-candidate distances
to find the smallest $r$ for which this decision problem has a positive
answer.

We solve this fault-tolerant hitting set decision problem by observing that
the size of a _smallest_ hitting set equals the size of a _maximum_
independent set, defined with respect to candidate points and voter intervals
in the following way. Suppose the intervals of
$\mathcal{I}=\\{I_{1},\dots,I_{n}\\}$ are sorted left to right. First, we can
assume without loss of generality that $|I_{i}\cap C|>f$ for all $i\in[n]$,
since otherwise there is no $f$-tolerant hitting set for $\mathcal{I}$. Given
a set of points $X$ in $\mathbb{R}$, we say that a set of intervals is
$X$-disjoint if each point in $X$ is contained in at most one interval. (That
is, $X$-disjoint intervals can be thought of as _independent_ in that they
contain disjoint sets of points in $X$). The following claim is easy to prove.

######  Lemma 2.2.

Given a set of points $X$ and a set of intervals $\mathcal{J}$ on the real
line, the size of a minimum hitting set $X^{\prime}\subseteq X$ of
$\mathcal{J}$ equals the maximum size of an $X$-disjoint subset of
$\mathcal{J}$.

Figure 1: The figure shows an interval hitting set instance with four
intervals and five points. The set $\\{c_{2},c_{4}\\}$ is a feasible hitting
set. For $X=\\{c_{2},c_{3},c_{5}\\}$, the intervals $I_{1},I_{3},I_{4}$ are
$X$-disjoint.

Thus, if $T\subseteq C$ is an $f$-tolerant hitting set for $\mathcal{I}$, then
for any failing set $J\subseteq C$, the size of any $(C\setminus J)$-disjoint
subset of $\mathcal{I}$ is at most $|T|$. One should note that the size of the
maximum $(C\setminus J)$-disjoint subset in $\mathcal{I}$ is a monotonically
increasing function of $|J|$ — as more candidates fail, more intervals can
become disjoint. Our goal is to find the maximum size of such a disjoint
interval family over all possible failure sets $J$ of size at most $f$. We
will do this using dynamic programming, by combining solutions of subproblems,
where each subproblem corresponds to an index range $[i,j]$, over the set of
candidate points $c_{1},\ldots,c_{m}$. Assuming that the candidate points
$C=\\{c_{1},\dots,c_{m}\\}$ are ordered from left to right, our subproblems
are defined as follows, for $1\leq i\leq j\leq m$:

  * •

$C_{i,j}=\\{c_{i},\dots,c_{j}\\}$ is the set of candidates in the range
$[c_{i},c_{j}]$.

  * •

$\mathcal{I}_{i,j}=\\{I\in\mathcal{I}:I\cap C\subseteq C_{i,j}\\}$ is the set
of intervals that only contain points from $C_{i,j}$.

  * •

For any $J\subseteq C_{i,j}$, $\delta_{i,j}(J)$ is the maximum size of a
$(C_{i,j}\backslash J)$-disjoint subset of $\mathcal{I}_{i,j}$.

  * •

The subproblems we want to solve are the values
$\delta_{i,j}(f)=\max_{J\subseteq C_{i,j},|J|\leq f}\delta_{i,j}(J)$.

The key technical lemma of this section is the following claim.

######  Lemma 2.3.

$T\subseteq C$ is an $f$-tolerant hitting set of $\mathcal{I}$ if and only if
$|T\cap C_{i,j}|\geq\delta_{i,j}(f)$, for all $1\leq i\leq j\leq m$.

######  Proof 2.4.

We first show the “if” part of the lemma. Assume $|T\cap
C_{i,j}|\geq\delta_{i,j}(f)$ for all $i,j\in[m]$ with $i\leq j$. To see that
$T$ is an $f$-tolerant hitting set of $\mathcal{I}$, consider a failing set
$J\subseteq C$ of size at most $f$. We have to show the existence of a
replacement set $R\subseteq C\backslash J$ such that $|(T\backslash J)\cup
R|\leq|T|$ and $(T\backslash J)\cup R$ is a hitting set of $\mathcal{I}$. We
write $T\backslash J=\\{c_{i_{1}},\dots,c_{i_{p}}\\}$, where
$i_{1}<\cdots<i_{p}$. For convenience, set $i_{0}=0$ and $i_{p+1}=m+1$. By our
assumption, every interval $I\in\mathcal{I}$ is hit by some point in $C$.
Thus, either $I$ is hit by $T\backslash J$ or $I$ belongs to
$\mathcal{I}_{i,j}$ where $i=i_{t-1}+1$ and $j=i_{t}-1$ for some index
$t\in[p+1]$. Now consider an index $t\in[p+1]$. We write $T_{t}=T\cap C_{i,j}$
and define $R_{t}\subseteq C_{i,j}\backslash J$ as a minimum hitting set of
$\mathcal{I}_{i,j}$. By Lemma 2, the size of $R_{t}$ is equal to the maximum
size of a $(C_{i,j}\backslash J)$-disjoint subset of $\mathcal{I}_{i,j}$,
which is nothing but $\delta_{i,j}(J\cap C_{i,j})$. Also, by assumption, we
have $|T_{t}|=|T\cap C_{i,j}|\geq\delta_{i,j}(f)\geq\delta_{i,j}(J\cap
C_{i,j})$. Therefore, $|R_{t}|\leq|T_{t}|$. Finally, we define
$R=\bigcup_{t=1}^{p+1}R_{t}$. Clearly, $(T\backslash J)\cup R$ hits
$\mathcal{I}$. So it suffices to show that $|(T\backslash J)\cup R|\leq|T|$.
Since $|R_{t}|\leq|T_{t}|$ for all $t\in[p+1]$, we have

$|(T\backslash J)\cup R|=|T\backslash
J|+\sum_{t=1}^{p+1}|R_{t}|\leq|T\backslash J|+\sum_{t=1}^{p+1}|T_{t}|=|T|,$

which completes the proof of the “if” part.

Next, we prove the “only if” part of the lemma. Assume $T\subseteq C$ is an
$f$-tolerant hitting set of $\mathcal{I}$. Consider two indices $i,j\in[m]$
with $i\leq j$. To show $|T\cap C_{i,j}|\geq\delta_{i,j}(f)$, it suffices to
show that $|T\cap C_{i,j}|\geq\delta_{i,j}(J)$ for all $J\subseteq C_{i,j}$
with $|J|\leq f$. Since $T$ is an $f$-tolerant hitting set of $\mathcal{I}$,
there exists $R\subseteq C\backslash J$ such that $|(T\backslash J)\cup
R|\leq|T|$ and $(T\backslash J)\cup R$ is a hitting set of $\mathcal{I}$. For
brevity, let $T^{\prime}=(T\backslash J)\cup R$. By definition, the intervals
in $\mathcal{I}_{i,j}$ can only be hit by the points in $C_{i,j}$. Thus,
$T^{\prime}\cap C_{i,j}$ is a hitting set of $\mathcal{I}_{i,j}$. As
$T^{\prime}\cap C_{i,j}\subseteq C_{i,j}\backslash J$, by Lemma 2.2, the size
of $T^{\prime}\cap C_{i,j}$ is at least the maximum size of a
$(C_{i,j}\backslash J)$-disjoint subset of $\mathcal{I}_{i,j}$, i.e.,
$|T^{\prime}\cap C_{i,j}|\geq\delta_{i,j}(J)$. Furthermore, because
$J\subseteq C_{i,j}$, we have $(T\backslash J)\backslash C_{i,j}=T\backslash
C_{i,j}$. It follows that $T\backslash C_{i,j}\subseteq T^{\prime}\backslash
C_{i,j}$ and thus $|T\backslash C_{i,j}|\leq|T^{\prime}\backslash C_{i,j}|$.
For a committee $T$, we can partition $T$ into two parts: the part containing
candidates in $C_{i,j}$ and the part containing candidates outside of
$C_{i,j}$. Hence, $|T|=|T\cap C_{i,j}|+|T\backslash C_{i,j}|$ and
$|T^{\prime}|=|T^{\prime}\cap C_{i,j}|+|T^{\prime}\backslash C_{i,j}|$.
Because $|T^{\prime}|\leq|T|$ and $|T^{\prime}\backslash
C_{i,j}|\geq|T\backslash C_{i,j}|$, we have $|T^{\prime}\cap
C_{i,j}|\leq|T\cap C_{i,j}|$. Therefore, $|T\cap C_{i,j}|\geq\delta_{i,j}(J)$.
This completes the proof of Lemma 2.3.

In order to decide if $\sigma_{f}(T)\leq r$, therefore, we just have to
compute $\delta_{i,j}(f)$, for all $i,j$, and check the condition $|T\cap
C_{i,j}|\geq\delta_{i,j}(f)$. We now show how to do that efficiently.

##### Efficiently Computing $\delta_{i,j}(f)$

For ease of presentation, we show how to compute $\delta_{1,m}(f)$; computing
other $\delta_{i,j}(f)$ is similar. We have $C_{1,m}=C$,
$\mathcal{I}_{1,m}=\mathcal{I}$, and $\delta_{1,m}(f)$ is size of the largest
subset of $\mathcal{I}$ that is $(C\backslash J)$-disjoint for any failing set
$J\subseteq C$ with $|J|\leq f$. The intervals of
$\mathcal{I}=\\{I_{1},I_{2},\ldots,I_{n}\\}$ are in the left to right sorted
order and, for each $i\in[n]$, let $C(I_{i})=C\cap I_{i}$ be the set of points
in $C$ that hits $I_{i}$. Define $\varGamma[i][j]$ as the maximum size of an
$(C\setminus X)$-disjoint subset $\mathcal{J}\subseteq\\{I_{1},\dots,I_{i}\\}$
such that $X\subseteq C$ and $|X|\leq j$.

######  Lemma 2.5.

We have the following recurrence

$\varGamma[i][j]\leavevmode\nobreak\ =\leavevmode\nobreak\
\max\left\\{\begin{array}[]{l}\varGamma[i-1][j],\\\ \max\limits_{0\leq
i^{\prime}\leq i}1+\varGamma[i^{\prime}][j-|C(I_{i})\cap
C(I_{i^{\prime}})|]\end{array}\right\\}$

Clearly, $\delta_{1,m}(f)=\varGamma[n][f]$. The base case for our dynamic
program is $\varGamma[0,j]=0$ for all $j\in[f]$ and $\varGamma[i][j]=-\infty$
for $j<0$ and all $i\in[n]$. Our dynamic program runs in time
$\mathcal{O}(n^{2}mf)$. In the same way, we can compute the values of
$\delta_{i,j}(f)$ for all $i,j\in[m]$ with $i\leq j$.

######  Lemma 2.6.

$\delta_{i,j}(f)$, for all $1\leq i\leq j\leq m$, can be computed in time
$\mathcal{O}(n^{2}m^{3}f)$.

Given a hitting set $T\subseteq C$ and the values $\delta_{i,j}(f)$, we can
verify the condition in Lemma 2.3 in time $\mathcal{O}(m^{3})$. We can then
use binary search to find the smallest value of $r$ for which $T$ is an
$f$-tolerant hitting set. This establishes the following result.

######  Theorem 2.7.

The fault-tolerance score of a $1$-dimensional committee $T$ can be computed
in time $\mathcal{O}(n^{2}m^{3}f\log(nm))$.

###  2.3 Optimal Fault-Tolerant Committee

We now address the problem of _designing_ a fault-tolerant committee: select a
committee $T$ of size $k$ whose fault-tolerance score $\sigma_{f}(T)$ is
minimized. Thus, our goal is _not_ to optimize the fault-free score of $T$,
namely $\sigma_{0}(T)$, but rather the score that the best replacement will
have after a worst-case set of $f$ faults in $T$, namely $\sigma_{f}(T)$.
Following the earlier approach, we again focus on the decision question: given
some $r\geq 0$, is there a committee of size $k$ with $\sigma_{f}(T)\leq r$?
For a given value of $r$, we construct our hitting set instance with
candidate-points and voter-intervals, and compute a minimum-sized $f$-tolerant
hitting set $T\subseteq C$ as follows:

  1. 1.

Compute the value of $\delta_{i,j}(f)$, for all $1\leq i\leq j\leq m$.

  2. 2.

Compute a minimum subset $T\subseteq C$ satisfying $|T\cap
C_{i,j}|\geq\delta_{i,j}(f)$, for all $1\leq i\leq j\leq m$.

  3. 3.

If $|T|\leq k$, we have a solution; otherwise, the answer to the decision
problem is no.

Step (1) is implemented using the dynamic program of the previous subsection,
and so it suffices to explain how to implement step (2). We assume without
loss of generality that $|C_{i,j}|\geq\delta_{i,j}(f)$ for all $i,j$, because
otherwise there is no solution. We compute a set $T$ using the following
greedy algorithm.

  * •

Initialize $T=\emptyset$.

  * •

For each $c_{k}$ for $k\in[m]$, if there exists $i,j\in[m]$ with $i\leq k\leq
j\leq m$ such that $\delta_{i,j}(f)\geq|T\cap C_{i,j}|+(j-k+1)$, then add
$c_{k}$ to $T$.

The algorithm runs in time $\mathcal{O}(m^{3})$. To prove correctness, we
first claim the following.

######  Lemma 2.8.

$|T\cap C_{i,j}|\geq\delta_{i,j}(f)$, for all $1\leq i\leq j\leq m$.

######  Proof 2.9.

Suppose not, so we have $|T\cap C_{i,j}|<\delta_{i,j}(f)$, for some $i\leq j$.
We recall that for any interval $I_{i}\in\mathcal{I}$, $|I_{i}\cap C|>f$.
Therefore, for any failing set $J$, $C_{i,j}\setminus J$ is a hitting set of
$\mathcal{I}_{i,j}$, and $|C_{i,j}|\geq\delta_{i,j}(f)$. This implies that
there exists some point among $c_{i},\dots,c_{j}$ that is not in $T$. Let
$k\in\\{i,\dots,j\\}$ be the largest index such that $c_{k}\notin T$. For
convenience, we use $T^{\prime}$ to denote the set $T$ in the iteration of our
algorithm that considers $c_{k}$. Note that $T\cap C_{i,j}=(T^{\prime}\cap
C_{i,j})\cup\\{c_{k+1},\dots,c_{j}\\}$ and $(T^{\prime}\cap
C_{i,j})\cap\\{c_{k+1},\dots,c_{j}\\}=\emptyset$. Therefore, $|T^{\prime}\cap
C_{i,j}|=|T\cap C_{i,j}|-(j-k)<\delta_{i,j}(f)-(j-k)$. This implies
$|T^{\prime}\cap C_{i,j}|+(j-k+1)\leq\delta_{i,j}(f)$. By our algorithm, in
this case we should include $c_{k}$ in $T$, which contradicts the fact that
$c_{k}\notin T$.

We now argue that $T$ has the minimum size among all subsets of $C$ satisfying
the property of Lemma 2.8. Let $\mathsf{opt}$ be the minimum size of a subset
of $C$ satisfying the desired property. We write
$T=\\{c_{k_{1}},\dots,c_{k_{r}}\\}$, where $k_{1}<\cdots<k_{r}$.

######  Lemma 2.10.

For any $t\in[r]$, there exists a subset $T^{*}\subseteq C$ such that (1)
$|T^{*}\cap C_{i,j}|\geq\delta_{i,j}(f)$ for all $i,j\in[m]$ with $i\leq j$,
(2) $|T^{*}|=\mathsf{opt}$, and (3) $\\{c_{k_{1}},\dots,c_{k_{t}}\\}\subseteq
T^{*}$.

######  Proof 2.11.

We prove the observation by induction on $t$. For $t=0$, the statement
trivially holds. Suppose the statement holds for $t-1$, i.e., there exists a
subset $T^{*}\subseteq C$ satisfying the first two conditions in Lemma 2.10
and $\\{c_{k_{1}},\dots,c_{k_{t-1}}\\}\subseteq T^{*}$. We show the statement
holds for $t$. Specifically, we shall modify $T^{*}$ to make it satisfy
$\\{c_{k_{1}},\dots,c_{k_{t}}\\}\subseteq T^{*}$ while maintaining the first
two conditions in the observation.

First, we notice that $T^{*}$ must contain a point other than
$c_{k_{1}},\dots,c_{k_{t-1}}$. To see this, suppose
$T^{*}=\\{c_{k_{1}},\dots,c_{k_{t-1}}\\}$. Since our algorithm added
$c_{k_{t}}$ to $T$, there exist $i,j\in[m]$ with $i\leq k_{t}\leq j$ such that
$\delta_{i,j}(f)\geq|\\{c_{k_{1}},\dots,c_{k_{t-1}}\\}\cap
C_{i,j}|+(j-k_{t}+1)$. This implies that
$\delta_{i,j}(f)>|\\{c_{k_{1}},\dots,c_{k_{t-1}}\\}\cap C_{i,j}|$, that is,
$\delta_{i,j}(f)>|T^{*}\cap C_{i,j}|$, which contradicts the fact that $T^{*}$
satisfies the first condition in the lemma. Thus, $T^{*}$ contains a point
other than $c_{k_{1}},\dots,c_{k_{t-1}}$.

Now let $k$ be the smallest index such that $c_{k}\in
T^{*}\backslash\\{c_{k_{1}},\dots,c_{k_{t-1}}\\}$. If $k=k_{t}$, then
$\\{c_{k_{1}},\dots,c_{k_{t}}\\}\subseteq T^{*}$ and we are done. Otherwise,
we remove $c_{k}$ from $T^{*}$ and add $c_{k_{t}}$ to $T^{*}$. After this
modification, it is clear that $|T^{*}|=\mathsf{opt}$ and
$\\{c_{k_{1}},\dots,c_{k_{t}}\\}\subseteq T^{*}$. So it suffices to show
$|T^{*}\cap C_{i,j}|\geq\delta_{i,j}(f)$ for all $i,j\in[m]$ with $i\leq j$.
Consider indices $i,j\in[m]$ with $i\leq j$. By assumption, before the
modification we have $|T^{*}\cap C_{i,j}|\geq\delta_{i,j}(f)$. If $j\geq
k_{t}$, then $|T^{*}\cap C_{i,j}|$ does not decrease after the modification,
and is thus at least $\delta_{i,j}(f)$. So assume $j<k_{t}$. In this case,
$T\cap C_{i,j}=\\{c_{k_{1}},\dots,c_{k_{t-1}}\\}\cap C_{i,j}\subseteq
T^{*}\cap C_{i,j}$. Since $|T\cap C_{i,j}|\geq\delta_{i,j}(f)$ by Lemma 3, we
have $|T^{*}\cap C_{i,j}|\geq\delta_{i,j}(f)$.

We use binary search to find the smallest $r$ such that the reduced instance
has an $f$-tolerant hitting set of size at most $k$. Therefore, the following
theorem holds.

######  Theorem 2.12.

Optimal Fault-Tolerant Committee can be solved in time
$\mathcal{O}(n^{2}m^{3}f\log(nm))$ for one-dimensional Euclidean elections.

######  Remark 2.13.

Our dynamic programming algorithm works as long as either the set $V$ or the
set $C$ is embedded in $\mathbb{R}$ (i.e., has a linear ordering), while the
other set can have an arbitrary $d$-dimensional embedding. Moreover, we can
also extend our algorithms to ordinal elections with (widely studied) single-
peaked preferences [2, 26] to compute an optimal fault-tolerant Chamberlin-
Courant committee.

##  3 Fault-Tolerant Committees in Multidimensional Space

We now consider fault tolerance in multidimensional elections. Unsurprisingly,
the optimal committee design problem is intractable — it is similar to
facility location — but it turns out that the seemingly simpler variants ORP
and FTS are also intractable.

###  3.1 Hardness Results

######  Theorem 3.1 ($\star$).

All three problems (Optimal Replacement, Fault-Tolerance Score, and Optimal
Fault-Tolerant Committee) are NP-hard, in any dimension $d\geq 2$ under the
Euclidean norm, where size of the committee $k$ and the failure parameter $f$
are part of the input.

We will use a single construction to show NP-hardness all three problems. Our
proof uses a reduction from the NP-complete problem Planar Monotone 3-SAT
(PM-3SAT) [7]. An input to this problem is a _monotone_ 3-CNF formula $\phi$
where each clause contains either three positive literals or three negative
literals, and whose variable-clause incidence graph has a planar embedding
which is given as a part of the input. Given an instance $\phi$ of PM-3SAT,
our reduction constructs a 2-dimensional Euclidean election. The general
outline follows a scheme used in [32] to show the hardness of committee
selection under _ordinal_ preferences, but generalizing the proof to _fault-
tolerant committees_ requires several technical modifications and a new proof
of correctness.

(a)

(b)

Figure 2: Figure (a) shows rectangular embedding of the PM-3SAT instance given
as a part of the input. In figure (b), we show a transformation of rectangular
embedding to orthogonal embedding useful for our construction. Here, each
variable $x_{i}$ in the rectangular embedding is replaced by the variable
reference point $\hat{x_{i}}$ and each clause is replaced $z_{i}$ is replaced
by the clause reference point $\hat{z_{i}}$.

For ease of referencing, we adapt the terminologies from [32]. In the planar
embedding of the formula $\phi$, each variable/clause is drawn as an (axis-
parallel) rectangle in the plane, and so this is called a rectangular
embedding. See Figure 2(a) for an illustration. The rectangles for the
variables are drawn along the $x$-axis, while the rectangles for the positive
(resp., negative) clauses lie above (resp., below) the $x$-axis. If a clause
contains a variable, then there is a vertical segment connecting the clause
rectangle and the variable rectangle. Each such vertical segment is disjoint
from all the rectangles except the two it connects.

The rectangular embedding of $\phi$ can be modified to another embedding which
is easier to work with called _orthogonal embedding_. We refer the reader to
[33] for details of the modification (See figure 2(b) for intuition). The
intersection points of vertical and horizontal segments in the orthogonal
embedding are _connection points_. To build the intuition for the orthogonal
embedding, we now give its properties as stated in [33]:

  1. (i)

Vertical and horizontal segments do not cross.

  2. (ii)

Each horizontal segment corresponds to a clause in $\phi$. Moreover, it
intersects exactly three vertical segments corresponding to the literals in
that clause.

  3. (iii)

The endpoints of all segments are connection points.

For each horizontal segment, we will refer to the middle connection point as
the _reference point_ of a the clause (notice that from properties (ii) and
(iii) each horizontal segment has three connection points and two of those are
the left and the right endpoint of the segment). The reference points for the
variables $x_{1},\ldots,x_{n}$ are denoted by $\hat{x_{1}},\ldots,\hat{x_{n}}$
and for the clauses $z_{1},\ldots,z_{m}$ they are denoted by
$\hat{z_{1}},\ldots,\hat{z_{m}}$. With shifting/scaling of the orthogonal
embedding without changing its topology, we can ensure that the
$x$-coordinates ($y$-coordinates) of vertical (resp., horizontal) segments are
distinct even integers in the range $\\{1,\ldots,2n\\}$ (resp.,
$\\{-2m,\ldots,2m\\}$). This guarantees that all connection points have even
integer coordinates and the embedding is contained in $[1,2n]\times[-2m,2m]$
rectangle. Now using the integral points on each segment $s$, we can partition
$s$ into $\ell(s)$ parts each of unit length where $\ell(s)$ is the length of
$s$. These unit length segments are called _pieces_ of the orthogonal
embedding. We use $N$ to denote the total number of pieces. Note that
$N=\mathcal{O}(nm)$.

We now construct a Euclidean election $E=(V,C)$ with voters and candidates as
points in $\mathbb{R}^{2}$.

Variable gadgets. For each variable $x_{i}$, we choose two additional points
near (but not equal to) $x_{i}$ as follows. Recall that there are two vertical
pieces incident to $\hat{x}_{i}$ in the orthogonal embedding: one above
$\hat{x}_{i}$, and the other below $\hat{x}_{i}$. We choose a point with
distance $0.2$ from $\hat{x}_{i}$, on each of the two pieces. Next, we put
$f+1$ candidates on each of these two points and a (single) candidate at
$\hat{x_{i}}$ (we set the value of $f$ later in the construction).
Furthermore, we place a voter on each of these three points. We call these
candidates/voters the $x_{i}$-gadget. See figure 3(a). For $i\in[n]$, we
construct the $x_{i}$-gadget for each variable $x_{i}$. Overall, the variable
gadgets have $(2f+3)n$ candidates and $3n$ voters.

Clause gadgets. Next, we construct a set of candidates/voters for the clauses
$z_{1},\dots,z_{m}$. For each clause $z_{i}$, we put a voter at the reference
point $\hat{z}_{i}$, and call this voter the $z_{i}$-gadget. See figure 3(b).
The total number of voters in the clause gadgets is $m$. Clause gadgets do not
have any candidates.

Piece gadgets. Finally, we construct a set candidates/voters to connect the
variable and clause gadgets. Consider a piece $s$ of the orthogonal embedding.
Recall that $s$ is a unit-length segment. Let $s^{-}$ and $s^{+}$ be the two
endpoints of $s$. We identify these endpoints as follows: For a vertical piece
$s$ above (resp., below) the $x$-axis, we say $s^{-}$ is the bottom (resp.,
top) endpoint of $s$ and $s^{+}$ is the top (resp., bottom) endpoint of $s$.
For a horizontal piece $s$, $s$ must belong to the horizontal segment of some
clause $z_{i}$. Suppose $s$ is to the left (resp., right) of the reference
point $\hat{z}_{i}$, then $s^{-}$ is the left (resp., right) endpoint of $s$
and $s^{+}$ be the right (resp., left) endpoint of $s$. For every piece $s$
that is not adjacent to any clause reference point, we choose four points near
$s^{+}$ and add candidates/voters on them as follows: We place $f+1$
candidates each on a point which is $0.3$ below and $0.3$ to the right of
$s^{+}$, and on a point which is $0.4$ above and $0.3$ to the left of $s^{+}$,
and on a point at $s^{+}$. Further, we place a candidate at a point which is
$0.3$ above $s^{+}$. Lastly, we place one voter at each of these four points.
We call these the candidates/voters of the $s$-gadget. See figure 3(c). Note
that pieces adjacent some clause reference points do not have gadgets.
Therefore, the total number of candidates in the piece gadgets is
$(3f+4)(N-3m)$, as each clause reference point is adjacent to three pieces,
and the number of voters is $4(N-3m)$.

Combining these three constructed gadgets, our election $E=(V,C)$ has
$4N-11m+3n$ voters and $(3N-9m+2n)f+4N-12m+3n$ candidates. We set the
committee size $k$ equals to $N+n-3m$. Clearly, the construction can be done
in a polynomial time. The main intuition behind the construction is the
following.

Candidates in the constructed instance can be partitioned into two types:

  * •

_Robust candidates_ $(C_{rob}\subseteq C)$ is the set of candidates such that
for each candidate, there are $f$ other candidates at the exact same location
as it. Note that for any failing set $J\subseteq C$, at least one candidate is
live in each of these locations.

  * •

_Covering candidates_ $(C_{cov}\subseteq C)$ is the set of candidates such
that for each candidate in the set, it is the unique candidate at its
location. Note that $|C_{cov}|=k$.

(a) Vertex gadget

(b) Edge gadget

(c) Piece gadget

Figure 3: Gadgets in our construction. Here, a disk and a cross at the same
location indicates a voter and a candidate at the same location. Similarly, a
circle and a cross at the same location indicates a voter and $(f+1)$
candidates at the same location.

In the constructed election, the following lemma holds.

######  Lemma 3.2.

In the constructed election $E=(V,C)$, we have $\sigma(C_{cov})\leq 0.75$
where $C_{cov}\subseteq C$ is the set of covering candidates.

######  Proof 3.3.

For all voters $v\in V$, we will show that $d(v,C_{cov})\leq 0.75$.

First, we consider the voters in the variable gadget. For a variable $x_{i}$,
the candidate at $\hat{x}_{i}$ belongs to $C_{cov}$. All three voters in the
variable gadget are within distance $0.2$ from $\hat{x}_{i}$. Therefore, all
the voters in the variable gadget have $d(v,C_{cov})\leq 0.75$.

Next, we consider the clause-gadgets. The closest candidate in $T$ for a voter
placed at $\hat{z}_{i}$ is at a distance $0.7$ from it; therefore, all voters
in the clause gadgets all have $d(v,C_{cov})\leq 0.75$.

Finally, we consider the piece gadgets. For each piece $s$, $C_{cov}$ contains
a candidate at a distance $0.3$ above $s^{+}$. It can be verified that all
four voters in the piece gadget have their closest candidate in $C_{cov}$
within distance $\sqrt{0.45}<0.7$ (See figure 3(c)).

Hence, for all voters in the piece gadgets, $d(v,C_{cov})\leq 0.75$. This
completes the proof of Lemma 3.2.

The election constructed above will be used to show hardness for all three
problems. Let the distance $r=0.75$. Recall that $k=N+n-3m$. We will now, we
describe the decision version of each of our problems along with the
construction of additional elements necessary in their input:

  1. (i)

ORP: In the input of ORP we additionally need a committee $T\subseteq C$ and a
failing set $J\subseteq C$. We set $T=J=C_{cov}$.

We ask if there exists a replacement $R\subseteq C\setminus C_{cov}$ such that
$\sigma(R)\leq r$?

  2. (ii)

FTS: In the input of FTS we additionally need a committee $T\subseteq C$ and a
fault-tolerance parameter $f$. We set $T=C_{cov}$ and $f=k$.

We ask if $\sigma_{f}(T)\leq r$?

  3. (iii)

OFTC: In the input of OFTC we additionally need a committee size $k^{\prime}$
and a fault-tolerance parameter $f$. We set $k^{\prime}=k$ and $f=k$.

We ask if there exists a $k$-sized committee $T\subseteq C$ with
$\sigma_{f}(T)\leq r$?

To show the equivalence, we will show that the answer to each of the above
question is yes if and only if $\phi$ is satisfiable.

The following lemma shows the proof of equivalence for problem (i).

######  Lemma 3.4.

There exists a committee $R\subseteq C\setminus C_{cov}$ with size $k$ such
that $\sigma(R)\leq r$ if and only if $\phi$ is satisfiable where
$k=|C_{cov}|=N+n-3m$, $N$ is the total number of pieces, and $m$ (resp., $n$)
is the number of clauses (resp., variables) in $\phi$, respectively.

In the next two subsections, we give the proof of Lemma 3.4.

####  3.1.1 Forward direction of Lemma 3.4

In this section, we will show that if $\phi$ is satisfiable, then there exists
a $k$-sized committee $R\subseteq C\setminus C_{cov}$ such that $\sigma(R)\leq
r$ (recall that $r=0.75$).

Suppose $\phi$ is satisfiable. Let
$\pi:X\rightarrow\\{\mathsf{true},\mathsf{false}\\}$ be an assignment which
makes $\phi$ true. We construct a $k$-sized committee $R\subseteq C\backslash
C_{cov}$ with $\sigma(R)\leq r$ using $\phi$. We include one candidate from
the every variable gadget and every piece gadget to $R$ as follows:

  * •

Replacement candidates from variable gadgets: Consider a variable $x_{i}$. By
our construction, the $x_{i}$-gadget contains $2f+3$ candidates which have the
same $x$-coordinates as $\hat{x}_{i}$. If $\pi(x_{i})=\mathsf{true}$ (resp.,
$\pi(x_{i})=\mathsf{false}$), we include in $R$ one of the topmost (resp.,
bottommost) candidates in the $x_{i}$-gadget.

  * •

Replacement candidates from piece gadgets: Consider a piece $s$ not adjacent
to a clause reference point (recall that pieces adjacent to some clause
reference point do not have gadgets on them). We begin by defining a variable
as an _associated_ variable of $s$ in the same way as described in [33]: When
$s$ is vertical, the associated variable of $s$ is just the variable whose
vertical segment contains $s$. For when $s$ is horizontal, then $s$ must
belong to the horizontal segment of some clause $z_{j}$. Then, if $s$ to the
left of the reference point $\hat{z_{j}}$ then the associated variable of $s$
is the variable whose vertical segment intersects the left endpoint of the
horizontal segment of $z_{j}$, and vice versa when $s$ to the right of the
reference point $\hat{z_{j}}$.

Let $x_{i}$ be the associated variable of $s$. Then,

    1. (i)

If $\pi(x_{i})=\mathsf{true}$: We include in $R$ a candidate in the $s$-gadget
that is $0.4$ above and $0.3$ to the left (resp., $0.4$ below and $0.3$ to the
right) of $s^{+}$ if $s$ is above (resp., below) the $x$-axis.

    2. (ii)

If $\pi(x_{i})=\mathsf{false}$: We include in $R$ a candidate in the
$s$-gadget that is $0.3$ below and $0.3$ to the right (resp., $0.3$ above and
$0.3$ to the left) of $s^{+}$ if $s$ is below (resp., above) the $x$-axis.

This finishes the construction of the committee $R$. Recall that the total
number of variable and the piece gadgets is $N+n-3m=k$. Therefore, $|R|=k$.
The following lemma completes the “if” part of Lemma 3.4.

######  Lemma 3.5.

$\sigma(R)\leq r$.

######  Proof 3.6.

For all voters $v\in V$ in the constructed instance, we will show that
$d(v,R)\leq r$.

First, we consider the voters in the variable gadget. For a variable $x_{i}$,
either a candidate $0.2$ above or $0.2$ below $\hat{x}_{i}$ belongs to $R$.
Hence, for all three voters, $d(v,R)\leq 0.6$. Recall that $r=0.75$.
Therefore, all the voters in the variable gadget have $d(v,T)\leq r$.

Next, we consider the clause-gadgets. For a clause $z_{i}$, consider the voter
$v$ placed at $\hat{z}_{i}$. The closest candidate in $R$ for this voter, is
the candidate placed at $0.4$ above and $0.3$ to the left of $s^{+}$ from a
clause gadget with $d(\hat{z}_{i},s^{+})=1$. Hence, $d(v,R)=\sqrt{0.45}<r$.

Finally, we consider the piece gadgets. We consider two cases: piece gadget
not adjacent to a variable reference point and piece gadget adjacent to a
variable reference point. Let $x_{i}$ be the associated variable with the
piece gadget $s$, and $\pi(x_{i})=\mathsf{true}$ (the case when
$\pi(x_{i})=\mathsf{false}$ is symmetric). Let $s$ be a piece gadget not
adjacent to any variable reference point. Suppose $s$ is above $x$-axis, and
$\hat{s}$ is the gadget below $s$ (the case when $s$ is below the $x$-axis is
symmetric; hence, we leave the proof for that to the reader). Recall that the
piece gadgets contains four voters: Let $v_{1},v_{2},v_{3}$, and $v_{4}$ be
the voters placed at distances $0.4$ above and $0.3$ to the left of $s^{+}$,
$0.3$ above $s^{+}$, at $s^{+}$, and $0.3$ below and $0.3$ to the right of
$s^{+}$, respectively. We know that a candidate placed at the location of
voter $v_{1}$ (say $c_{1}$) belongs to $R$. Notice $v_{1},v_{2}$ and $v_{3}$
have a distance at most $0.5$ from this voter but $v_{4}$ has a distance
$\sqrt{0.85}>r$. But consider the gadget corresponding to $\hat{s}$. Here, we
know $R$ contains a candidate (say $c_{1}^{\prime}$) placed at $0.4$ above and
$0.3$ to the left of $\hat{s}^{+}$. It can be verified that
$d(v_{4},c_{1}^{\prime})=\sqrt{0.45}<r$. Therefore, $d(v_{4},R)\leq r$. We now
consider the case when $s$ is adjacent to a variable reference points (say
$\hat{x}_{i}$). We know $s$ has four voters $v_{1},v_{2},v_{3}$, and $v_{4}$
placed at distances $0.4$ above and $0.3$ to the left of $s^{+}$, $0.3$ above
$s^{+}$, at $s^{+}$, and $0.3$ below and $0.3$ to the right of $s^{+}$,
respectively. We know that a candidate placed at the location of voter $v_{1}$
(say $c_{1}$) belongs to $R$, and this candidate is at a distance at most
$0.5$ from $v_{1},v_{2}$, and $v_{3}$. Recall that $\pi(x_{i})=\mathsf{true}$,
$R$ contains a candidate at a distance $0.2$ above $\hat{x_{i}}$. Notice that
this candidate is at a distance $\sqrt{0.34}$ from $v_{4}$. Therefore,
$d(v_{4},R)<r$. This completes the proof of Lemma 3.5.

####  3.1.2 Reverse direction of Lemma 3.4

Suppose $R\subseteq C\setminus C_{cov}$ is a $k$-sized committee with
$\sigma(R)\leq r$. We will show how to recover a satisfying assignment
$\pi:X\rightarrow\\{\mathsf{true},\mathsf{false}\\}$ using $R$. The structure
of our proof is similar to the reverse direction argument in [33]. First, we
observe the following property of $R$.

######  Lemma 3.7.

$R$ contains exactly one candidate from every variable and piece gadget.

######  Proof 3.8.

We begin with the variable gadgets. Consider an $x_{i}$-gadget corresponding
to the variable $x_{i}$. Recall that we place three voters in the
$x_{i}$-gadget: One voter at $\hat{x_{i}}$ (say $v_{1}$), and one voter each
at a distance $0.2$ above and $0.2$ below of $\hat{x_{i}}$ . Observe that for
$v_{1}$, its distance to any candidate from the adjacent piece gadgets is at
least $\sqrt{(0.7)^{2}+(0.3)^{2}}=\sqrt{0.58}$ which is strictly greater than
$r$. Hence, $R$ must include at least one candidate from the $x_{i}$-gadget to
ensure $d(v_{1},R)\leq r$. We now consider the piece gadgets. Let $v_{1}$ be
the voter placed at $s^{+}$. The nearest candidate to $v_{1}$ from the
adjacent piece gadgets is at a distance at least $\sqrt{0.58}$ which is
strictly greater than $r$. Therefore, $R$ must contain at least one candidate
from each piece gadget to ensure $d(v_{1},R)\leq r$.

Finally, recall that the committee size is $k=N+n-3m$ and the number of
variable (piece) gadgets is $n(N-3m)$, respectively. Therefore, by a simple
counting argument, we can conclude that $T$ must contain exactly one candidate
from each variable gadget and each piece gadget. This completes the proof of
Lemma 3.7.

We will now use $R$ to recover a satisfying assignment $\pi$ for $\phi$. For
an arbitrary variable $x_{i}$, using Lemma 3.7, we know $R$ contains exactly
one candidate (say $c_{i}$) from the $x_{i}$-gadget. We set $\pi(x_{i})$ as
follows:

  * •

If $c_{i}$ is above the $x$-axis, we set $\pi(x_{i})=\mathsf{true}$.

  * •

If $c_{i}$ is below the $x$-axis, we set $\pi(x_{i})=\mathsf{false}$.

To complete the proof, we need to show that $\pi$ is a satisfying assignment
of $\phi$. It is enough to show that for each clause, at least one of its
variables is set to $\mathsf{true}$. Since the argument for positive and
negative clauses is similar, we will only that for each positive clause, at
least one its variables is set to $\mathsf{true}$. We begin by proving the
following important structural property of the committee $R$.

######  Lemma 3.9.

For a piece $s$ above the $x$-axis that is not adjacent to any clause
reference point, suppose $x_{i}$ is the associated variable of $s$. If $R$
contains the candidate in the $s$-gadget which is $0.4$ above and $0.3$ to the
left of $s^{+}$, then $\pi(x_{i})=\mathsf{true}$.

######  Proof 3.10.

Let $s$ be piece as described in the above lemma with the associated variable
$x_{i}$. We will show that if $R$ contains the candidate in the $s$-gadget
which is $0.4$ above and $0.3$ to the left of $s^{+}$, then $R$ contains a
candidate $0.2$ above $\hat{x_{i}}$ in the $x_{i}$-gadget. The choice of
candidate in $R$ from the $s$-gadget to the $x_{i}$-gadget percolates as
follows:

  * •

When $s$ is not adjacent to a variable reference point $\hat{x_{i}}$: Let
$v_{1},v_{2},v_{3}$, and $v_{4}$ be the voters placed at distances $0.4$ above
and $0.3$ left of $s^{+}$, $0.3$ above $s^{+}$, at $s^{+}$, and $0.3$ below
and $0.3$ to the right of $s^{+}$, respectively. We know that the candidate
placed at $s^{+}$ belongs to $J$. From the set of $f+1$ candidates placed at
the locations of $v_{1},v_{2}$ and $v_{4}$, we denote a candidate by
$c_{1},c_{2}$, and $c_{3}$, respectively. Moreover, let $s^{\prime}$ be the
piece below (resp., to the left of) $s$ when $s$ is a vertical (resp.,
horizontal) piece. We denote the corresponding candidate in $s^{\prime}$ by
$c_{1}^{\prime},c_{2}^{\prime}$, and $c_{3}^{\prime}$. Assume that $c_{1}\in
R$. We observe that $d(v_{4},c_{1})=\sqrt{0.85}>r$ but
$d(v_{4},c_{1}^{\prime})=\sqrt{0.45}<r$. Moreover, $c_{1}^{\prime}$ is the
only alive candidate from $s^{\prime}$-gadget within distance $r$ from
$v_{4}$. Using Lemma 2, we know $R$ only includes $c_{1}$ from $s$. Hence, to
satisfy $d(v_{4},R)\leq r$, $R$ must include the candidate $c_{1}^{\prime}$.
Observe that we can repeat the above argument for all pieces below (resp., to
the left of) $s$, which implies that for all pieces $s_{i}$ below (resp., to
the left of) $s$, $R$ includes the candidate in $s_{i}$-gadget placed $0.4$
above and $0.3$ to the left of $s_{i}^{+}$.

  * •

When $s$ is adjacent to a variable reference point $\hat{x_{i}}$: Let
$v_{1},v_{2},v_{3}$, and $v_{4}$ be the voters placed at distances $0.4$ above
and $0.3$ left of $s^{+}$, $0.3$ above $s^{+}$, at $s^{+}$, and $0.3$ below
and $0.3$ to the right of $s^{+}$, respectively. Moreover, let $c_{1},c_{2}$,
and $c_{3}$ denote an arbitrary candidate placed at the locations of voters
$v_{1},v_{2}$, and $v_{4}$, respectively. We know that for voter $v_{4}$, the
set of candidates within distance $r$ is $\\{c_{2},c_{3},c_{4}\\}$ where
$c_{4}$ is the candidate placed $0.2$ above $\hat{x}_{i}$. Using Lemma 3.7, we
know $R$ only includes ${c}_{1}$ from the piece $\hat{s}$. Hence, to ensure
$d(v_{4},R)\leq r$, $R$ must include candidate $c_{4}$. Recall that for a
variable $x_{j}$ for $j\in[n]$, if $R$ includes a candidate above the
reference point $\hat{x}_{j}$, we set $x_{j}=\mathsf{true}$. Since, $c_{4}\in
R$ and $c_{4}$ lies above $\hat{x}_{i}$, we set $x_{i}=\mathsf{true}$.

This completes the proof of Lemma 3.9.

Using Lemma 3.7 and Lemma 3.9 we are now ready to show that the constructed
assignment $\pi$ satisfies $\phi$. Since the argument for positive and
negative clauses is similar, we will only show for the positive clauses. Our
argument is similar to the one in [33] but we include it here for
completeness.

Consider a positive clause $z_{i}$. We will show that at least one variable of
$z_{i}$ is set to $\mathsf{true}$ by $\pi$. We denote the pieces adjacent to
the reference point $\hat{z_{i}}$ by $s_{1},s_{2},s_{3}$. Without loss of
generality, let $s_{1}$ be to the left of $\hat{z}_{i}$, $s_{2}$ be to the
right of $\hat{z}_{i}$, and $s_{3}$ be below $\hat{z}_{i}$. Notice that
$\hat{z}_{i}=s_{1}^{+}=s_{2}^{+}=s_{3}^{+}$. Recall that $\hat{z_{i}}$ is a
connection point. Since all connection points have even coordinates and
$s_{1}^{-},s_{2}^{-},s_{3}^{-}$ are at a unit distance from $\hat{z_{i}}$,
$s_{1}^{-},s_{2}^{-},s_{3}^{-}$ are not connection points. Hence, let
$s_{4},s_{5},s_{6}$ be the pieces such that the right endpoint of $s_{4}$ is
$s_{1}^{-}$, the left endpoint of $s_{5}$ is $s_{2}^{-}$, and the top endpoint
of $s_{6}$ is $s_{3}^{-}$. Therefore, $s_{1}^{-}=s_{4}^{+}$,
$s_{2}^{-}=s_{5}^{+}$, and $s_{3}^{-}=s_{6}^{+}$. Let $c_{4}$ be a candidate
in $s_{4}$-gadget such that $c_{4}$ is $0.4$ above and $0.3$ to the left of
$s_{4}^{+}$. Moreover, let the candidates $c_{5}$ and $c_{6}$ defined in the
similar way such that $c_{5}$ belongs to the $s_{5}$-gadget and $c_{6}$
belongs to the $s_{6}$-gadget. For the voter at the reference point
$\hat{z_{i}}$, only the candidates $c_{4},c_{5},c_{6}$ are within distance
$r$. This is because all pieces except $s_{1},\dots,s_{6}$ have distances at
least $2$ from $\hat{z}_{i}$. Since $\sigma(R)\leq r$, $R$ must contain at
least one of these three candidates. Therefore, using Lemma 3.9, we conclude
that at least one of the associated variables of $s_{4},s_{5},s_{6}$ is true.
Since these are exactly the three variables in clause $z_{i}$; hence, $z_{i}$
is true under the assignment $\pi$. This completes the “only if” part of our
proof.

The argument above completes the proof of Lemma 3.4 and completes the argument
of equivalence for our decision problem $(i)$.

##### Argument of equivalence for the decision problem $(ii)$:

Recall that for the FTS decision problem instance stated above, the input
committee is $T=C_{cov}$ and the fault-tolerance parameter is $f=k$. Notice
that $T$ contains one candidate from each vertex and each piece gadget.
Suppose a subset $J\subset C$ with $|J|\leq f$ fails. Consider the committee
$T^{\prime}=T\setminus J$. All voters in the vertex gadgets and the piece
gadgets which have a non-empty intersection with $T^{\prime}$ have a committee
member within distance $r$ (i.e., suppose $V^{\prime}\subseteq V$ is the
subset of all such voters then $\sigma(V^{\prime},T^{\prime})\leq r$). For the
voters in $V\setminus V^{\prime}$, we build a committee $R$ using the
candidates in vertex and piece gadgets with have an empty intersection with
$T^{\prime}$ in the same way as we constructed a replacement committee in the
forward direction of proof of Lemma 3.4 (Section 3.1.1) (to replace the
candidates from set $T\cap J$). Notice that it is always possible to construct
such a replacement $R$ because all candidates in $R$ are robust candidates
(meaning that there are $f+1$ identical copies of each of these candidates)
and the failure set $J$ has size at most $f$.

Since the total number of vertex and edge gadgets is $k$, the new committee
$(T\setminus J)\cup R$ has size $k$. Using the same argument as in Section
3.1.1, we can show that $\sigma((T\setminus J)\cup R)\leq r$. This completes
the argument in the forward direction (that is, if $\phi$ is satisfiable then
$\sigma_{f}(T)\leq r$).

To show the reverse direction, suppose $\sigma_{f}(T)\leq r$. Therefore, when
failing set $J=C_{cov}$, there exists a $k$-sized replacement $R\subseteq
C_{rob}$ such that $\sigma(R)\leq r$. Hence, using Lemma 3.4, we can conclude
that $\phi$ is satisfiable.

##### Argument of equivalence for the decision problem $(iii)$:

Recall that for the OFTC decision problem instance stated above, the input is
the committee size $k=N+n-3m$ and the fault-tolerance parameter $f=k$.

The argument for the forward direction is trivial, as we know when $\phi$ is
satisfiable, the $k$-sized committee $T=C_{cov}$ has $\sigma_{f}(T)\leq r$. In
the reverse direction, suppose $T\subseteq C$ is a $k$-sized committee with
$\sigma_{f}(T)\leq r$. Therefore, in this case, for a size $f$ failing set
$J=C_{cov}$, there exists a replacement $R\subseteq C\setminus C_{cov}$ such
that $|(T\setminus J)\cup R|\leq k$ and $\sigma((T\setminus J)\cup R)\leq r$.
Since $(T\setminus J)\cup R=R$ and $R\subseteq C_{rob}$; using Lemma 3.4, we
can conclude that $\phi$ is satisfiable.

####  3.1.3 Hardness when $f$ is bounded

##### ORP and FTS

Consider an election $E=(V,C)$, a committee $T\subseteq C$ of size $k$ and a
fault-tolerance parameter $f$ which is a constant. It is easy to see that we
can solve ORP optimally in time $nm^{\mathcal{O}(f)}k$ by trying all possible
replacement sets and choosing the best one. Similarly, by trying all possible
failing sets of size at most $f$ (note that there are $m^{\mathcal{O}(f)}$
such sets) and computing optimal replacement for each set, we can compute
$\sigma_{f}(T)$ in time $nm^{O(f)}k$.

##### OFTC

We will now show that for any integer $f\geq 0$, OFTC is NP-hard using a
simple reduction from the $k$-supplier problem [28]: Fix $f\geq 0$. Let
$(\mathcal{C},F)$ along with an integer $k$ be a $k$-supplier instance where
$\mathcal{C}$ is the set of customers and $F$ is a set of facilities embedded
in $\mathbb{R}^{2}$. In the decision version of $k$-supplier, given a real
number $r$, we ask if there exists a size $k$ set $F^{\prime}\subseteq F$ such
that $\sigma(\mathcal{C},F^{\prime})\leq r$.

We construct an election $E=(V,C)$ in $\mathbb{R}^{2}$ as follows. We set
$V=\mathcal{C}$. Further, we construct the set of candidates $C$ by adding
$f+1$ identical candidates on each point in $F$. We set the committee size to
$k$. It is easy to see that there exists a $k$-sized committee $T\subset C$
with $\sigma_{f}(T)\leq r$ if and only if there exists a $k$-sized subset
$F^{\prime}\subseteq F$ such that $\sigma(\mathcal{C},F^{\prime})\leq r$ where
$r$ is a real number.

###  3.2 Optimal Replacement Problem

A simple greedy algorithm achieves a $3$-approximation for the Optimal
Replacement Problem in any fixed dimension $d$ as well as in any metric space.

######  Lemma 3.11.

We can find a $3$-approximation for ORP in time $O(k(nk+m))$.

######  Proof 3.12.

Let $T\subseteq C$ be the given committee and let $J\subseteq T$ be the
failing set. In order to find the replacement set $R$, we initialize
$\hat{T}=T\setminus J$, and then repeat the following two steps $|T\cap J|$
times: (1) Choose the farthest voter from $\hat{T}$, namely, choose
$\hat{v}=\operatorname*{arg\,max}_{v\in V}d(v,\hat{T})$, and (2) Add to
$\hat{T}$ the candidate $\hat{c}\notin\hat{T}$ that is closest to $\hat{v}$.
Upon termination, we clearly have $|\hat{T}|=|T|$.

We will now show that $R$ is a $3$-approximate replacement committee. Let
$|T\cap J|=r$. Suppose $R^{*}=\\{c_{1}^{*},c_{2}^{*},\ldots,c_{r}^{*}\\}$ is
an optimal replacement such that $T^{*}=(T\setminus J)\cup R^{*}$ has
$\sigma(T^{*})=\sigma^{*}$. Let $V_{1}^{*},V_{2}^{*},\ldots,V_{r}^{*}\subseteq
V$ be disjoint set of voters such that $c_{i}^{*}$ is the closest candidate in
$T^{*}$ for all voters in $V_{i}^{*}$ for $i\in[r]$. We define
$V^{\prime}=\bigcup_{i=1}^{r}V_{i}^{*}$.

Let $R=\\{c_{1},c_{2},\ldots,c_{r}\\}$ be the replacement set constructed by
our algorithm and let $\hat{v_{1}},\hat{v_{2}},\ldots,\hat{v_{r}}$ be the
voters chosen by our algorithm. Recall that $\hat{T}=(T\setminus J)\cup R$. It
is easy to see that $\sigma(V\setminus V^{\prime},T^{*})=\sigma(V\setminus
V^{\prime},\hat{T})\leq\sigma^{*}$ since $(T\setminus J)\subseteq T^{*}$ and
$(T\setminus J)\subseteq\hat{T}$. Next, using a simple case analysis we will
show that $\sigma(V^{\prime},\hat{T})\leq 3\sigma^{*}$.

Our cases are based on the voters $\hat{v_{1}},\hat{v_{2}},\ldots,\hat{v_{r}}$
as follows:

  * •

If $\hat{v_{i}}\in V\setminus V^{\prime}$ for $i\in[r]$, then the farthest
voter (aka $\hat{v_{i}}$) in the $i^{th}$-iteration of the algorithm satisfies
$\sigma(\hat{v_{i}},\hat{T})\leq\sigma(V\setminus
V^{\prime},\hat{T})\leq\sigma^{*}$, and hence,
$\sigma(V^{\prime},\hat{T})\leq\sigma^{*}$.

  * •

Next, suppose for some $i,j,k\in[r]$, we have $\hat{v_{i}},\hat{v_{j}}\in
V_{k}^{*}$. Without loss of generality, let $j>i$. Then, in the
$j^{th}$-iteration, the farthest voter (aka $\hat{v_{j}}$) among all voters in
$V$ has $d(\hat{v_{j}},\hat{T_{j-1}})\leq 3\sigma^{*}$ where $\hat{T_{j-1}}$
is a committee after $j-1$ iterations of adding replacement candidates. This
is because $d(\hat{v_{j}},\hat{T_{j-1}})\leq
d(\hat{v_{j}},\hat{v_{i}})+d(\hat{v_{i}},\hat{c_{i}})$, and we know
$d(\hat{v_{j}},\hat{v_{i}})=d(\hat{v_{j}},c_{i}^{*})+d(c_{i}^{*},v_{i})\leq
2\sigma^{*}$ and $d(\hat{v_{i}},\hat{c_{i}})\leq\sigma^{*}$ since $c_{i}$ is
the closest candidate to $v_{i}$ which is not in the committee. This implies
that $\sigma(\hat{T_{j-1}})\leq 3\sigma^{*}$. Since
$\hat{T_{j-1}}\subseteq\hat{T}$; therefore, $\sigma(V^{\prime},\hat{T})\leq
3\sigma^{*}$.

  * •

Finally, we consider the case for when $i\in[r]$, we have $\hat{v_{i}}\in
V_{i}^{*}$. We will now show that for $v\in V_{i}^{*}$, $\sigma(v,\hat{T})\leq
3\sigma^{*}$. We know $d(v,\hat{c_{i}})\leq
d(v,\hat{v_{i}})+d(\hat{v_{i}},\hat{c_{i}})$. Notice that
$d(v,\hat{v_{i}})\leq d(v,c_{i}^{*})+d(c_{i}^{*},\hat{v_{i}})\leq
2\sigma^{*}$, and $d(\hat{v_{i}},\hat{c_{i}})\leq\sigma^{*}$. Therefore,
$d(v,\hat{c_{i}})\leq 3\sigma^{*}$. This implies, $\sigma(V^{\prime},R)\leq
3\sigma^{*}$, and hence, $\sigma(V^{\prime},\hat{T})\leq 3\sigma^{*}$.

Finally, it is easy to see that the algorithm runs for at most $k$ iterations
and each iteration can be trivially implemented in time $O(nk+m)$. This
completes the proof of Lemma 3.11.

###  3.3 Computing the Fault-Tolerance Score

We can also approximate the optimal fault-tolerance score of a committee
within a factor of $3$. Specifically, if the optimal fault-tolerance score of
$T$ is $\sigma_{f}(T)=\sigma^{*}$, then our algorithm returns a real number
$\sigma^{\prime}$ such that $\sigma^{*}\leq\sigma^{\prime}\leq 3\sigma^{*}$.

For each voter $v$, let $d_{f}(v)$ be $v$’s distance to its $(f+1)^{th}$
closest candidate, and let $d^{\prime}=\max_{v\in V}d_{f}(v)$ be the maximum
of these values over all voters. The basic idea behind our approximation is
simple and uses the following two facts: (1) $\sigma^{*}\geq d^{\prime}$, and
(2) $\sigma^{*}\geq\sigma(T)$. The first one holds because $d^{\prime}$ is the
best score possible if some voter’s $f$ nearest candidates fail, and the
second one holds because a failure can only worsen the score (that is,
$\sigma_{f}(T)\geq\sigma(T)$ for any $f>0$). Therefore, the distance
$\sigma^{\prime}=d^{\prime}+2\sigma(T)$ is clearly within a factor of $3$ of
the optimal $\sigma^{*}$. We claim that for any failing set $J\subseteq C$,
there exists a replacement $R\subseteq C\setminus J$ of size at most $|T\cap
J|$ such that $\sigma((T\setminus J)\cup R)\leq\sigma^{\prime}$.

######  Claim 1.

For a committee $T\subseteq C$ and a failing set $J\subseteq C$, there exists
a replacement $R\subseteq C\setminus J$ of size at most $|T\cap J|$ such that
$\sigma((T\setminus J)\cup R)\leq\sigma^{\prime}$ where
$\sigma^{\prime}=d^{\prime}+2\sigma(T)$.

######  Proof 3.13.

Let $T\cap J=\\{c_{1},\ldots,c_{r}\\}$ and let $V_{1},\ldots,V_{r}$ be
disjoint sets of voters such that $c_{i}$ is the closest candidate in $T$ to
all voters in $V_{i}$ for $i\in[r]$. We define
$\overline{V}=\bigcup_{i=1}^{r}V_{i}$ and $V^{\prime}=V\setminus\overline{V}$.
For each voter $v\in V^{\prime}$, its closest candidate in $T$ is still
available; hence, $\sigma(v,T\setminus J)\leq\sigma(T)$. Therefore, we only
need to show that $\sigma(\overline{V},R)\leq\sigma^{\prime}$.

We build a replacement $R$ as follows: We initialize $R=\emptyset$. Next, for
$r$ iterations, let $i$ be the iteration index then,

  * •

Select an arbitrary voter $v_{i}\in V_{i}$.

  * •

Let $\hat{c_{i}}\in C\setminus J$ be the closest available candidate to
$v_{i}$. Add $\hat{c_{i}}$ to $R$.

To show $\sigma(\overline{V},R)\leq\sigma^{\prime}$, we will now show that for
all $i\in[r]$, $\sigma(V_{i},\hat{c_{i}})\leq\sigma^{\prime}$. For $v\in
V_{i}$, we know $d(v,\hat{c_{i}})\leq d(v,v_{i})+d(v_{i},\hat{c_{i}})$ where
$v_{i}$ is the voter selected in the $i^{th}$-iteration. First, observe that
$d(v_{i},\hat{c_{i}})\leq d^{\prime}$ as at most $f$ closest candidates to
$v_{i}$ belong to $J$. Second, $d(v,v_{i})\leq d(v,c_{i})+d(c_{i},v_{i})\leq
2\sigma(T)$ (recall that $c_{i}\in T\cap J$). Hence, $d(v,\hat{c_{i}})\leq
2\sigma(T)+d^{\prime}=\sigma^{\prime}$. Therefore, for the constructed
replacement $R$, $\sigma(\overline{V},R)\leq\sigma^{\prime}$.

We have the following result.

######  Lemma 3.14.

The fault-tolerance score of a committee can be approximated within a factor
of $3$ in time $\mathcal{O}(nm\log(f))$.

###  3.4 Optimal Fault-Tolerant Committee

We now discuss how to design approximately optimal fault-tolerant committees
in multiwinner elections. Specifically, given a set of voters $V$ and a set of
candidates $C$ in $d$-space, along with parameters $k$ (committee size) and
$f$ (number of faults), we want to compute a size $k$ committee $T\subseteq C$
with the minimum fault-tolerance score $\sigma_{f}(T)$. We prove two
approximation results for this problem: (1) We can solve this problem in
polynomial time within an approximation factor of $3$ in polynomial time if
the parameter $f$ is treated as a constant (while $k$ remains possibly
unbounded). If $f$ is not assumed to be a constant, we can solve the problem
within an approximation factor of $5$. (2) We give an EPTAS with running time
$(1/\varepsilon)^{O(1/{\varepsilon^{2d}})}(m+n)^{O(1)}$ which is a
_bicriterion_ approximation, where the output committee $T$ is fault-tolerant
for at least $(1-\varepsilon)n$ voters with
$\sigma_{f}(T)\leq(1+\varepsilon)\sigma^{*}$. The next two subsections discuss
these results.

####  3.4.1 3-Approximation for Bounded $f$

Let $\sigma^{*}$ be the optimal $f$-tolerant score of a committee of size $k$.
We compute the approximation solution via an approximate decision algorithm,
which takes as input a number $\sigma\geq\sigma_{f}(C)$ and returns a
committee $T\subseteq C$ of size at most $k$ with $\sigma_{f}(T)\leq 3\sigma$
if $\sigma\geq\sigma^{*}$. (We slightly abuse notation to introduce a
convenient quantity $\sigma_{f}(C)$, which is the $f$-fault-tolerance score of
a committee with all the input candidates. This is clearly a lower bound on
any size $k$ committee’s score.)

For a committee $T\subseteq C$ and a failing set $J\subseteq C$, let
$\delta(T,J)$ denote the score obtained after finding an optimal replacement
$K$. That is,

$\delta(T,J)=\min_{K\in C\backslash J,|K|=|T\cap J|}\sigma_{0}((T\backslash
J)\cup K).$

Thus, $\sigma_{f}(T)=\max_{J\subseteq C,|J|\leq f}\delta(T,J)$. Our
approximation algorithm is shown in Algorithm 1. It begins with an empty
committee $T$ (line 1), and as long as there exists a failing set $J$ of size
at most $f$ for which $\delta(T,J)>3\sigma$, 333We can check this condition by
iterating over all failing sets of size $f$ and computing an optimal
replacement set in each case. we do the following.

First, we remove all candidates in $J$ from $T$ (line 3). Then, whenever there
exists a voter $v\in V$ with $d(v,T)>3\sigma$, we add to $T$ a candidate $c\in
C\backslash J$ whose distance to $v$ is at most $\sigma$ (lines 5-6). Such a
$c$ always exists because $\sigma$ is at least the distance to the
$(f+1)^{th}$ closest neighbor to $v$.

We call this voter $v$ the witness of $c$, denoted by $\mathsf{wit}[c]$ (line
7). Adding $c$ to $T$ guarantees that $d(v,T)\leq\sigma$. We repeat this
procedure (the inner while loop) until $d(v,T)\leq 3\sigma$ for all $v\in V$.
Finally, the outer while loop terminates when $\delta(T,J)\leq 3\sigma$ for
all $J\subseteq C$ of size at most $f$, i.e., $\sigma_{f}(T)\leq 3\sigma$. At
this point, we return the committee $T$.

Algorithm 1 Approximate decision algorithm

1:Input: a set $V$ of voters, a set $C$ of candidates, the committee size $k$,
the fault-tolerance parameter $f$, and a number $\sigma\geq\sigma_{f}(C)$

2:$T\leftarrow\emptyset$

3:while $\exists$ $J\subseteq C$ such that $|J|\leq f$ and
$\delta(T,J)>3\sigma$ do

4: $T\leftarrow T\backslash J$

5: while $\exists$ $v\in V$ such that $d(v,T)>3\sigma$ do

6: $c\leftarrow$ a candidate in $C\backslash J$ satisfying $d(v,c)\leq\sigma$

7: $T\leftarrow T\cup\\{c\\}$

8: $\mathsf{wit}[c]\leftarrow v$

9:return $T$

######  Lemma 3.15.

Let $T$ be the committee computed by Algorithm 1. Then
$d(\mathsf{wit}[c],\mathsf{wit}[c^{\prime}])>2\sigma$ for any two distinct
$c,c^{\prime}\in T$.

######  Proof 3.16.

Let $c,c^{\prime}\in T$ such that $c\neq c^{\prime}$. When the committee $T$
is constructed in Algorithm 1, the candidates are added to $T$ one by one
(line 6). Therefore, without loss of generality, we can assume that
$c^{\prime}$ is added to $T$ after $c$. Consider the iteration of the inner
while-loop (line 4-7) of Algorithm 1 in which we add $c^{\prime}$ to $T$. At
the beginning of this iteration, we have $d(v,T)>3\sigma$ where
$v=\mathsf{wit}[c^{\prime}]$. Note that $c\in T$ at this time, and thus
$d(\mathsf{wit}[c^{\prime}],c)>3\sigma$. Furthermore, we have
$d(\mathsf{wit}[c],c)\leq\sigma$ by construction. Therefore,

$d(\mathsf{wit}[c],\mathsf{wit}[c^{\prime}])\geq
d(\mathsf{wit}[c^{\prime}],c)-d(\mathsf{wit}[c],c)>2\sigma,$

by the triangle inequality.

######  Lemma 3.17.

If $\sigma\geq\sigma^{*}$, then Algorithm 1 outputs a size $k$ committee $T$
with $\sigma_{f}(T)\leq 3\sigma$.

######  Proof 3.18.

The condition of the outer while loop of Algorithm 1 guarantees that
$\delta(T,J)\leq 3\sigma$ for all $J\subseteq C$ of size at most $f$, which
implies $\sigma_{f}(T)\leq 3\sigma$. To prove $|T|\leq k$, suppose
$T=\\{c_{1},\dots,c_{r}\\}$. By Lemma 3.15, the pairwise distances between the
voters $\mathsf{wit}[c_{1}],\dots,\mathsf{wit}[c_{r}]$ are all larger than
$2\sigma$ and thus larger than $2\sigma^{*}$ (as $\sigma\geq\sigma^{*}$ by our
assumption). Now consider a committee $T^{*}\subseteq C$ of size $k$
satisfying $\sigma_{f}(T^{*})=\sigma^{*}$. For each $\mathsf{wit}[c_{i}]$,
there exists $c_{i}^{*}\in T^{*}$ such that
$d(\mathsf{wit}[c_{i}],c_{i}^{*})\leq\sigma^{*}$. Observe that
$c_{1}^{*},\dots,c_{r}^{*}$ are all distinct. Indeed, if $c_{i}^{*}=c_{j}^{*}$
and $i\neq j$, then by the triangle inequality,

$d(\mathsf{wit}[c_{i}],\mathsf{wit}[c_{j}])\leq
d(\mathsf{wit}[c_{i}],c_{i}^{*})+d(\mathsf{wit}[c_{j}],c_{j}^{*})\leq
2\sigma^{*},$

contradicting the fact that
$d(\mathsf{wit}[c_{i}],\mathsf{wit}[c_{j}])>2\sigma^{*}$. Since $|T^{*}|=k$
and $c_{1}^{*},\dots,c_{r}^{*}\in T^{*}$, we have $r\leq k$, which completes
the proof.

Using these two lemmas, we can compute a $3$-approximate solution using
Algorithm 1 as follows. First, we compute $\sigma_{f}(C)$ in $O(nm^{f+1})$
time by enumerating all failing sets $J\subseteq C$ of size at most $f$. For
every voter $v\in V$ and every candidate $c\in C$ such that
$d(v,c)\geq\sigma_{f}(C)$, we run Algorithm 1 with $\sigma=d(v,c)$. Among all
the committees returned of size at most $k$, we pick the one, say $T^{*}$,
that minimizes $\sigma_{f}(T^{*})$. To see that $\sigma_{f}(T^{*})\leq
3\sigma^{*}$, note that $\sigma^{*}$ must be the distance between a voter and
a candidate. Thus, there is one call of Algorithm 1 with $\sigma=\sigma^{*}$,
which returns a committee $T\subseteq C$ of size at most $k$ such that
$\sigma_{f}(T)\leq 3\sigma=3\sigma^{*}$, by Lemma 3.17. We have
$\sigma_{f}(T^{*})\leq\sigma_{f}(T)$ by construction, which implies
$\sigma_{f}(T^{*})\leq 3\sigma^{*}$.

_Overall running time._ We will show that each run of Algorithm 1 takes
$O(nm^{2f+1})$ time. We can check the condition of while loop in Step 2 in
time $O(m^{2f})$. This is because there are at most $O(m^{f})$ failing sets of
size at most $f$ (the precise upper bound is $2m^{f}$), and for each failing
set, we can find an optimal replacement in time $O(m^{f})$ by bruteforce.
Next, each iteration of the while loop takes $O(nm)$ time, that is, the time
required to compute all voter-candidate pairwise distances. Therefore, the
overall running time of the algorithm is $O(n^{2}m^{2f+2})$.

Thus, we have the following result.

######  Theorem 3.19.

We can find a $3$-approximation for Optimal Fault-tolerant Committee in time
$O(n^{2}m^{2f+2})$, assuming the fault-tolerance parameter $f$ is a constant.

Next, for a non-constant $f$, we give a $5$ approximation using a greedy rule.

######  Lemma 3.20.

We can find a $5$-approximation for Optimal Fault-Tolerant Committee in time
$\mathcal{O}(mnk)$.

Our algorithm is quite simple and uses the classical “farthest next” greedy
rule [15]. Specifically, let $C$ and $V$ be the set of candidates and voters,
respectively. We begin with an empty committee $T=\emptyset$ and an empty set
$\hat{V}$ of picked voters. Then we repeat the following step: pick the voter
$\hat{v}\in V\backslash\hat{V}$ farthest to the current committee $T$, add
$\hat{v}$ to $\hat{V}$, and add to $T$ the candidate $\hat{c}\in C$ closest to
$\hat{v}$. The procedure terminates when $|T|=k$ or the candidate $\hat{c}$
computed is already in $T$. Formally, our algorithm is shown in Algorithm 2.

Algorithm 2 $\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
5$-approximation algorithm for OFTC

1:Input: a set $V$ of voters, a set $C$ of candidates, the committee size $k$,
and the fault-tolerance parameter $f$

2:$i\leftarrow 0$ and $T\leftarrow\emptyset$

3:while $|T|\leq k$ do

4: $i\leftarrow i+1$

5: $v_{i}\leftarrow\arg\max_{v\in V\backslash\hat{V}}d(v,T)$

6: $c_{i}\leftarrow\arg\min_{c\in C}d(v_{i},c)$

7: if $c_{i}\in T$ then

8: break

9: $T\leftarrow T\cup\\{c_{i}\\}$

10:return $T$

We now move on to the proof of correctness. Denote by $\sigma^{*}$ the optimal
$f$-tolerant score of a size-$k$ committee. First, using the same analysis as
the one for the $k$-center problem [20], we can show that $\sigma(T)\leq
3\sigma^{*}$.

######  Lemma 3.21.

Let $T$ be the committee computed by Algorithm 2. Then $\sigma(T)\leq
3\sigma^{*}$.

The proof Lemma 3.21 is easy and we refer the reader to [20] for details. We
now show that $T$ is a $5$-approximate solution to OFTC.

######  Lemma 3.22.

Let $T$ be the committee computed by Algorithm 2. Then $\sigma_{f}(T)\leq
5\sigma^{*}$.

######  Proof 3.23.

It suffices to show that for any failing set $J\subseteq C$ of size at most
$f$, there exists a replacement set $K\subseteq C\backslash J$ such that
$|K|=T\cap J$ and $\sigma_{0}((T\backslash J)\cup K)\leq 5\sigma^{*}$. Suppose
$T=\\{c_{1},\dots,c_{r}\\}$, where $c_{i}$ is the candidate selected in the
$i$-th iteration of Algorithm 2. Let $v_{1},\dots,v_{r}$ be the voters
computed in line 4 of Algorithm 2. For a failing set $J\subseteq C$, we
construct the replacement set $K$ as follows: For each index $i\in[r]$ such
that $c_{i}\in J$, we include in $K$ the candidate $c_{i}^{\prime}\in
C\backslash J$ closest to $v_{i}$. Clearly, $|K|=|T\cap J|$.

Now we show that $\sigma_{0}((T\backslash J)\cup K)\leq 5\sigma^{*}$. Using
Lemma 3.21, we know that $d(v,T)\leq 3\sigma^{*}$ for any voter $v\in V$.
Based on this, we bound $\sigma_{0}((T\backslash J)\cup K)$ as follows.
Observe that $\sigma_{0}((T\backslash J)\cup K)=\max_{v\in V}d(v,(T\backslash
J)\cup K)$. So it suffices to show that $d(v,(T\backslash J)\cup K)\leq
5\sigma^{*}$ for all $v\in V$. Let $c_{i}\in T$ be the candidate closest to
$v$; thus, $d(v,c_{i})=d(v,T)\leq 3\sigma^{*}$. If $c_{i}\notin J$, we are
done. Otherwise, $c_{i}^{\prime}\in K$ and hence $d(v,(T\backslash J)\cup
K)\leq d(v,c_{i}^{\prime})$. By the triangle inequality, we have

$d(v,c_{i}^{\prime})\leq d(v,c_{i})+d(c_{i},v_{i})+d(v_{i},c_{i}^{\prime}).$

As argued before, $d(v,c_{i})\leq 3\sigma^{*}$. Furthermore,
$d(c_{i},v_{i})\leq d(v_{i},c_{i}^{\prime})\leq\sigma^{*}$, because
$c_{i}^{\prime}$ is the candidate in $C\backslash J$ closest to $v_{i}$.
Therefore, the above inequality implies $d(v,c_{i}^{\prime})\leq 5\sigma^{*}$.

By the above lemma, we know that Algorithm 2 achieves an approximation ratio
of 5. Its running time is clearly $O(mnk)$. This completes the proof of Lemma
3.20.

All of these approximations hold not just for $d$-dimensional Euclidean space,
for any fixed $d$, but also for any metric space.

####  3.4.2 A bicriterion EPTAS

Finally, we design a bicriterion FPT approximation scheme with running time
$f(\varepsilon)\cdot n^{\mathcal{O}(1)}$, which finds a size-$k$ committee
whose fault-tolerance score for at least a $(1-\varepsilon)$ fraction of the
voters is within a factor of $(1+\varepsilon)$ of the optimum. Formally, we
say a committee $T$ is $(r,\rho)$-good if there exists a subset
$V^{\prime}\subseteq V$ of size at least $\rho n$ such that the $f$-tolerant
score of $T$ with respect to only the voters in $V^{\prime}$ is at most $r$.
Then our approximation scheme can output a size-$k$ committee which is
$((1+\varepsilon)\sigma^{*},1-\varepsilon)$-good. The core of our
approximation scheme is the following (approximation) decision algorithm. The
decision algorithm takes the problem instance and an additional number $r>0$
as input. The output of the algorithm has two possibilities: it either (i)
returns YES and gives a size-$k$ committee that is
$((1+\varepsilon)r,1-\varepsilon)$-good or (ii) simply returns NO.
Importantly, the algorithm is guaranteed to give output (i) as long as
$r\geq\sigma^{*}$. Note that this decision algorithm directly gives us the
desired approximation scheme. Indeed, we can apply it with $r=d(v,c)$ for all
$v\in V$ and $c\in C$. Let $r^{*}$ be the smallest $r$ that makes the
algorithm give output (i). The size-$k$ committee $T^{*}$ obtained when
applying the algorithm with $r^{*}$ is
$((1+\varepsilon)r^{*},1-\varepsilon)$-good. We have $r^{*}\leq\sigma^{*}$
because the algorithm must be applied with $r=\sigma^{*}$ at some point and it
is guaranteed to give output (i) at that time. Thus, $T^{*}$ is
$((1+\varepsilon)\sigma^{*},1-\varepsilon)$-good, as desired.

For simplicity of exposition, we describe our decision algorithm in two
dimensions. By scaling, we may assume that the given number is $r=1$. To solve
the decision problem, our algorithm uses the shifting technique [19]. Let $h$
be an integer parameter to be determined later. For a pair of integers
$i,j\in\mathbb{Z}$, let $\Box_{i,j}$ denote the $h\times h$ square
$[i,i+h]\times[j,j+h]$. A square $\Box_{i,j}$ is nonempty if it contains at
least one voter or candidate. We first compute the index set
$\widetilde{I}=\\{(i,j):\Box_{i,j}\text{ is nonempty}\\}$. This can be easily
done in time $\mathcal{O}((n+m)h^{2})$.

Consider a pair $(x,y)\in\\{0,\dots,h-1\\}^{2}$. Let $L_{x,y}$ be the set of
all integer pairs $(i,j)$ such that $i\pmod{h}\equiv x$ and $j\pmod{h}\equiv
y$. We write $\widetilde{I}_{x,y}=\widetilde{I}\cap L_{x,y}$. For a voter
$v\in V$ and a square $\Box_{i,j}$, we say $v$ is a boundary voter for
$\Box_{i,j}$ if $v\notin[i+2,i+h-2]\times[j+2,j+h-2]$. Furthermore, we say $v$
conflicts with $(x,y)$ if $v$ is a boundary voter in $\Box_{i,j}$ for some
$(i,j)\in\widetilde{I}_{x,y}$.

######  Lemma 3.24.

There exists a pair $(x,y)\in\\{0,\ldots,h-1\\}^{2}$ such that at most
$\frac{4h-4}{h^{2}}\cdot|V|$ voters conflict with $(x,y)$.

######  Proof 3.25.

A voter $v\in V$ may conflict with $(x,y)$ only if for some
$(i,j)\in\widetilde{I}_{x,y}$, we have $v\in\Box_{i,j}$ but
$v\notin[i+2,i+h-2]\times[j+2,j+h-2]$. Therefore, out of the total of $h^{2}$
pairs $(x,y)$, $v$ can only conflict with at most $h^{2}-(h-2)^{2}$ pairs.
Hence, using an averaging argument, there exists a pair $(x,y)$ with at most
$\frac{h^{2}-(h-2)^{2}}{h^{2}}\cdot|V|$ conflicting voters from $V$.

We fix a pair $(x,y)\in\\{0,\ldots,h-1\\}^{2}$ that conflicts with the minimum
number of voters. For $(i,j)\in\widetilde{I}_{x,y}$, we define the set of
(non-boundary) voters
$V_{i,j}=\\{v\in\Box_{i,j}:v\in[i+2,i+h-2]\times[j+2,j+h-2]\\}$, and the set
of candidates $C_{i,j}=\\{c\in C:c\in\Box_{i,j}\\}$. Note that for
$(i,j)\in\widetilde{I}_{x,y}$, the $C_{i,j}$’s are disjoint and form a
partition of $C$. Next, we show an important lemma which allows our algorithm
to divide our problem into smaller subproblems, solve them individually, and
combine the solutions to solve the overall problem.

######  Lemma 3.26.

Let $V_{1},V_{2},\ldots,V_{s}$ be subsets of $V$ and let
$T_{1},T_{2},\ldots,T_{s}$ be pairwise disjoint subsets of $C$ such that
$T_{i}$ is a fault-tolerant committee for $V_{i}$ with
$\sigma_{f}(T_{i})=\sigma$. Then, $T=\bigcup_{i=1}^{s}T_{i}$ is a fault-
tolerant committee of $\bigcup_{i=1}^{s}V_{i}$ with $\sigma_{f}(T)=\sigma$.

######  Proof 3.27.

We will show that for any failing set $J\subseteq C$, there exists a
replacement set $R$ with $|R|\leq|J\cap T|$ such that $\sigma_{0}((T\setminus
J)\cup R)\leq\sigma$. For $i\in[s]$, let $J_{i}\subseteq J$ be the restriction
of $J$ to $T_{i}$, i.e., $J_{i}=J\cap T_{i}$. We know $|J|\leq f$. Since
$T_{i}$ is a fault-tolerant committee for $V_{i}$; hence, there exists a valid
replacement $R_{i}\subseteq C\backslash J$ such that $|R_{i}|\leq|J_{i}|$ and
$\sigma_{0}((T_{i}\backslash J_{i})\cup R_{i})\leq\sigma$. Let
$R=\bigcup_{i=1}^{s}R_{i}$ (note that the $R_{i}$’s need not be disjoint).
Then we have $|R|\leq\sum_{i=1}^{s}|J_{i}|\leq|J\cap T_{i}|$ which implies
$|R|\leq|J\cap T|$, and we have $\sigma_{0}((T\backslash J)\cup R)\leq\sigma$.
This completes the proof of Lemma 3.26.

Consider a pair $(i,j)\in\widetilde{I}_{x,y}$. Let $\overline{T}_{i,j}$ be a
smallest fault-tolerant committee for $V_{i,j}$ with
$\sigma_{f}(\overline{T}_{i,j})\leq 1$. We observe that any inclusion-minimal
fault-tolerant committee $T_{i,j}$ for $V_{i,j}$ satisfies $T_{i,j}\subseteq
C_{i,j}$. This is because any candidate outside $C_{i,j}$ has distance more
than $1+6/h$ to any voter in $V_{i,j}$ (for a large enough value of $h$). In
the next section we will show how to compute a fault-tolerant committee
$T_{i,j}\subseteq C_{i,j}$ for $V_{i,j}$ such that
$|T_{i,j}|\leq|\overline{T}_{i,j}|$ and $\sigma_{f}(T_{i,j})\leq 1+6/h$ in
$h^{O(h^{4})}n^{O(1)}$ time. Assuming we can compute the above-mentioned
committee $T_{i,j}$, our overall algorithm is as follows:

  1. 1.

Fix a pair $(x,y)\in\\{0,\ldots,h-1\\}^{2}$ conflicting with the minimum
number of voters, and set $h$ to be the smallest integer such that
$(4h-4)/h^{2}\leq\varepsilon$ and $6/h\leq\varepsilon$.

  2. 2.

For each pair $(i,j)\in\widetilde{I}_{x,y}$, compute $T_{i,j}\subseteq
C_{i,j}$.

  3. 3.

Let $T=\bigcup_{(i,j)\in\widetilde{I}_{x,y}}T_{i,j}$. If $|T|\leq k$, return
YES (along with $T$); otherwise, return NO.

Let $V^{\prime}=\bigcup_{(i,j)\in\widetilde{I}_{x,y}}V_{i,j}$. Since the
$C_{i,j}$’s are disjoint, using Lemma 3.26, we conclude that $T$ is a fault-
tolerant committee for $V^{\prime}$. Furthermore, from our choice of $(x,y)$,
we have $|V^{\prime}|\geq(1-\varepsilon)n$. It is easy to show that the
$f$-tolerant score of $T$ with respect to the voters in $V^{\prime}$ is at
most $1+\varepsilon$, and in addition, if $\sigma^{*}\geq 1$, we have $|T|\leq
k$; we give a formal argument below. This proves correctness of our decision
algorithm. The overall algorithm takes
$(1/\varepsilon)^{O(1/\varepsilon^{4})}(m+n)^{O(1)}$ time. We note that the
algorithm can be directly generalized to the $d$-dimensional case with running
time $(1/\varepsilon)^{O(1/{\varepsilon^{2d}})}(m+n)^{O(1)}$. Therefore, we
have the following result.

######  Theorem 3.28.

Given a $d$-dimensional Fault-Tolerant Committee Selection instance, we can
compute a size-$k$ committee $T$ such that the $f$-tolerant score of $T$ with
respect to at least $(1-\varepsilon)n$ voters is at most
$(1+\varepsilon)\sigma^{*}$, where $\sigma^{*}$ is the optimal $f$-tolerant
score of a size-$k$ committee (with respect to the entire set $V$). This
algorithm runs in time
$(1/\varepsilon)^{O(1/{\varepsilon^{2d}})}(m+n)^{O(1)}$.

##### Correctness for the Decision Algorithm.

Recall that, in our decision algorithm, we set $h$ to be the smallest integer
such that $(4h-4)/h^{2}\leq\varepsilon$ and $6/h\leq\varepsilon$. Moreover,
using Lemma 3.24 and our choice of $(x,y)$, we have
$|V^{\prime}|\geq(1-\varepsilon)n$. If the computed committee $T$ has size at
most $k$, our algorithm returns YES; otherwise, it returns NO. To see the
correctness our algorithm, recall that $\sigma^{*}$ is an optimum score of a
fault-tolerant committee for $V$. If $r\geq\sigma^{*}$, then there exists a
size-$k$ fault-tolerant committee with score $r$ for $V$, and hence for
$V^{\prime}$ (as $V^{\prime}\subseteq V$).

Recall that for $(i,j)\in\tilde{I}_{x,y}$, the computed committee $T_{i,j}$
has $|T_{i,j}|\leq|\overline{T}_{i,j}|$ where $\overline{T}_{i,j}$ is the
smallest committee for $V_{i,j}$ with $\sigma_{f}(\overline{T}_{i,j})\leq 1$.
Therefore, when $r\geq\sigma^{*}$, for
$T=\bigcup_{(i,j)\in\tilde{I}_{x,y}}T_{i,j}$, we have $|T|\leq k$ and our
algorithm returns YES. On the other hand, if there is no size-$k$ committee
whose $f$-tolerant score is at most $(1+\varepsilon)r$ for at least
$(1-\varepsilon)n$ voters, we must have $|T|>k$ and thus our algorithm returns
NO. This completes the argument for the proof of correctness.

##### Algorithm to Compute $T_{i,j}$

We now present the most challenging piece of our algorithm: the computation of
the $T_{i,j}$’s. Consider a box $\Box_{i,j}$. Suppose there exists a fault-
tolerant committee $T\subseteq C$ for $V_{i,j}$ with $\sigma_{f}(T)\leq 1$.
Our task is to compute a fault-tolerant committee $T_{i,j}\subseteq C$ for
$V_{i,j}$ such that $|T_{i,j}|\leq|T|$ and $\sigma_{f}(T_{i,j})\leq 1+6/h$.

We divide $\Box_{i,j}$ into $h^{4}$ smaller cells each with size
$\frac{1}{h}\times\frac{1}{h}$, and we denote the set of these cells by
$L=\\{l_{1},\ldots,l_{h^{4}}\\}$. (See Figure 4.) Our algorithm is based on
two key observations:
$(i)$ A committee with a candidate in every nonempty cell has $f$-tolerant
score within a difference of at most $2/h$ from the optimum score. Since the
number of cells is $h^{4}$, this implies that the size of a smallest
approximately optimal committee is bounded by $h^{4}$ (formally shown in Lemma
3.29).
$(ii)$ All candidates in a cell can be treated as identical, causing only a
loss of $2/h$ in the score. This implies that for any $T_{i,j}$, to
approximately compute the $f$-tolerant score of $T_{i,j}$, we _only_ need to
consider the failing sets where either all or none of the candidates in a cell
fail. Note that the number of such failing sets is at most $2^{O(h^{4})}$
(formally shown in Lemma 3.31).

Using these two observations, at a high level, our algorithm goes through all
committees of size at most $h^{4}$ (there are $h^{\mathcal{O}(h^{4})}$ of
these as we can assume that each cell has at most $h^{4}$ candidates),
approximately computes the $f$-tolerant score of each of these committees in
time $2^{O(h^{4})}$, and returns the smallest one with the desired score.

Figure 4: The figure shows a cell in the shifted grid. The solid lines around
the sides are the grid lines (and the region inside them is a cell). The
shaded (green) region is the boundary region. Inside the boundary region, we
divide the cell into $1/h\times 1/h$ smaller cells. The distance between any
two points in a smaller cell is $<2/h$. All candidates in smaller cells are
identical (i.e., candidates in blue regions). In this example, since only five
cells are nonempty, we have at most $2^{5}$ distinct failing sets.

######  Lemma 3.29.

Let $T,T^{*}\subseteq C$ be fault-tolerant committees for $V_{i,j}$. If
$|T^{*}\cap l_{a}|=1$ for all $a\in[h^{4}]$ such that $C\cap
l_{a}\neq\emptyset$, then $\sigma_{f}(T^{*})-\sigma_{f}(T)\leq 2/h$.

######  Proof 3.30.

Consider a failing set $J\subseteq C$. Since $T$ is a fault-tolerant
committee, there exists a valid replacement set $R$ such that $|(T\backslash
J)\cup R|\leq|T|$ and $\sigma_{0}((T\backslash J)\cup R)\leq\sigma_{f}(T)$.
Let $L^{\prime}=\\{l_{a}\in L:l_{a}\cap((T\backslash J)\cup
R)\neq\emptyset\\}$. Moreover, let $J^{*}=J\cap T^{*}$. Then we will show that
there exists a replacement set $R^{*}$ for $J^{*}$ such that
$|R^{*}|\leq|J^{*}|$ and $\sigma_{0}((T^{*}\setminus J^{*})\cup
R^{*})-\sigma_{0}((T\setminus J)\cup R)\leq 2/h$.

We construct the set $R^{*}$ as follows: Consider a cell $l_{a}\in
L^{\prime}$. Since $l_{a}\cap((T\setminus J)\cup R)\neq\emptyset$, $l_{a}$ is
nonempty. This implies $T^{*}\cap l_{a}\neq\emptyset$ from the way we
construct $T^{*}$. Let $c_{a}$ be the only candidate in $T^{*}\cap l_{a}$. If
$c_{a}\in J$, then we replace $c_{a}$ with an arbitrary $c_{a}^{\prime}\in
l_{a}\setminus J$ (i.e., we add $c_{a}^{\prime}$ to $R^{*}$). We know that
such a candidate $c_{a}^{\prime}$ exists because $l_{a}\cap((T\backslash
J)\cup R)\neq\emptyset$. Since we only add a candidate to $R^{*}$ from $l_{a}$
such that $J^{*}\cap l_{a}\neq\emptyset$, we have $|R^{*}|\leq|J^{*}|$.

We will now show that $\sigma_{0}((T^{*}\setminus J^{*})\cup
R^{*})-\sigma_{0}((T\setminus J)\cup R)\leq 2/h$. Observe that for a pair of
candidates $c_{1},c_{2}\in l_{a}$, $d(c_{1},c_{2})\leq 2/h$ (see Figure 4).
Let $C_{a}=l_{a}\cap((T\setminus J)\cup R)$. Moreover, let $V_{a}\subseteq V$
be the set of voters which have a candidate in $C_{a}$ as their closest
candidate in the committee $(T\setminus J)\cup R$. Using the triangle
inequality, we know that $d(V_{a},c_{a}^{\prime})\leq d(V_{a},C_{a})+2/h$. The
above statement holds for all cells $l_{a}\in L^{\prime}$. Therefore,
$\sigma_{0}((T^{*}\setminus J^{*})\cup R^{*})-\sigma_{0}((T\setminus J)\cup
R)\leq 2/h$.

Note that our proof works for an arbitrary failing set $J$ including
$J=\emptyset$. This completes the proof of Lemma 3.29.

Based on the above observation, we solve the problem as follows. We enumerate
all maps $\chi\colon L\rightarrow\\{0,1,\dots,h^{4}\\}$ where $\chi(l_{a})$ is
the number of candidates from $l_{a}$ in the committee. The total number of
such maps is $h^{O(h^{4})}$. For each feasible map, i.e., $\chi$ satisfying
$\chi(l_{a})\leq|C\cap l_{a}|$ for all $a\in[h^{4}]$, we construct a fault-
tolerant committee $T_{\chi}^{*}$ for $V_{i,j}$ by picking (arbitrarily)
$\chi(l_{a})$ candidates in $C\cap l_{a}$ for all $a\in[h^{4}]$ and including
them in $T_{\chi}^{*}$. For each constructed $T_{\chi}^{*}$, we compute a
number $\widetilde{\sigma_{f}}(T_{\chi}^{*})$ that approximates
$\sigma_{f}(T_{\chi}^{*})$ using the following lemma.

######  Lemma 3.31.

Given $T_{\chi}^{*}$, one can compute a number
$\widetilde{\sigma_{f}}(T_{\chi}^{*})$ in $2^{O(h^{4})}n^{O(1)}$ time such
that $|\widetilde{\sigma_{f}}(T_{\chi}^{*})-\sigma_{f}(T_{\chi}^{*})|\leq
2/h$.

######  Proof 3.32.

For a pair of candidates $c_{i},c_{j}$ in a cell $l_{i}\in L$, we know
$d(c_{i},c_{j})\leq 2/h$. Since we want to compute the number
$\tilde{\sigma_{f}}(T_{\chi}^{*})$ within an absolute error of $2/h$ compared
to the actual value, it is sufficient to only consider the failing sets for
which either all or none of the candidates from a cell fail. The total number
of cells is $h^{4}$; therefore, we only need to consider at most
$2^{O(h^{4})}$ distinct failing cells (see Figure 4). For each of these
failing sets (say $J\subseteq C$), we can compute a best replacement committee
$R$ in time $2^{O(h^{4})}$ by either choosing one or zero candidates from each
cell. For each replacement, $\sigma_{0}(T_{\chi}^{*}\setminus J\cup R)$ can be
computed in $O(nh^{4})$ time. Therefore, we can compute
$\tilde{\sigma_{f}(T_{\chi}^{*})}$ in time $2^{O(h^{4})}n^{O(1)}$.

Finally, we let $T_{i,j}$ be the smallest among all committees $T_{\chi}^{*}$
satisfying $\widetilde{\sigma_{f}}(T_{\chi}^{*})\leq 1+4/h$, and we return it
as our solution. The running time of our algorithm is clearly
$h^{O(h^{4})}n^{O(1)}$. The following lemma shows that our algorithm is
correct.

######  Lemma 3.33.

We have $\sigma_{f}(T_{i,j})\leq 1+6/h$. Furthermore, $|T_{i,j}|\leq|T|$ for
any fault-tolerant committee $T$ for $V_{i,j}$ with $\sigma_{f}(T)\leq 1$.

######  Proof 3.34.

The fact that $\sigma_{f}(T_{i,j})\leq 1+6/h$ follows directly from our
construction and Lemma 3.31. Let $T$ be a fault-tolerant committee for
$V_{i,j}$ with $\sigma_{f}(T)\leq 1$. We consider two cases: $|T|>h^{4}$ and
$|T|\leq h^{4}$. First, assume $|T|>h^{4}$. Define $\chi\colon
L\rightarrow\\{0,1,\dots,h^{4}\\}$ by setting $\chi(l_{a})=1$ for all
$a\in[h^{4}]$ with $C\cap l_{a}\neq\emptyset$, and $\chi(l_{a})=0$ whenever
$C\cap l_{a}=\emptyset$. Clearly, $|T_{\chi}^{*}|\leq h^{4}<|T|$. By Lemma
3.29, $\sigma(T_{\chi}^{*})\leq 1+2/h$. Thus,
$\widetilde{\sigma_{f}}(T_{\chi}^{*})\leq 1+4/h$ by Lemma 3.31. This further
implies that $|T_{i,j}|\leq|T_{\chi}^{*}|<|T|$.

Now assume $|T|\leq h^{4}$. Define $\chi\colon
L\rightarrow\\{0,1,\dots,h^{4}\\}$ by setting $\chi(l_{a})=|T\cap l_{a}|$ for
all $a\in[h^{4}]$. Clearly, $|T_{\chi}^{*}|=|T|$ and $|T_{\chi}^{*}\cap
l_{a}|=|T\cap l_{a}|$ for all $a\in[h^{4}]$. We show that
$\sigma(T_{\chi}^{*})\leq 1+2/h$. Since $|T_{\chi}^{*}\cap l_{a}|=|T\cap
l_{a}|$, for each $a$ pick a bijection $\pi_{a}\colon C\cap l_{a}\rightarrow
C\cap l_{a}$ such that for all $x\in C\cap l_{a}$, $x\in T_{\chi}^{*}$ if and
only if $\pi_{a}(x)\in T$. Observe that the distance between $x$ and
$\pi_{a}(x)$ is at most $2/h$ for all $x\in C\cap l_{a}$. Combining all
bijections $\pi_{a}$, we obtain a bijection $\pi\colon C_{i,j}\rightarrow
C_{i,j}$ with the property that for all $x\in C_{i,j}$, the distance between
$x$ and $\pi(x)$ is at most $2/h$, and $x\in T_{\chi}^{*}$ if and only if
$\pi(x)\in T$. Because of this bijection, it is obvious that
$|\sigma_{f}(T_{\chi}^{*})-\sigma_{f}(T)|\leq 2/h$ and in particular
$\sigma_{f}(T_{\chi}^{*})\leq 1+2/h$. Thus,
$\widetilde{\sigma_{f}}(T_{\chi}^{*})\leq 1+4/h$ by Lemma 3.31. This further
implies that $|T_{i,j}|\leq|T_{\chi}^{*}|=|T|$.

## References

  * [1] Kenneth Arrow.  Advances in the spatial theory of voting.  Cambridge University Press, 1990.
  * [2] Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann.  On the computation of fully proportional representation.  Journal of Artificial Intelligence Research, 47:475–519, 2013.
  * [3] Robert Bredereck, Andrzej Kaczmarczyk, and Rolf Niedermeier.  On coalitional manipulation for multiwinner elections: Shortlisting.  Autonomous Agents and Multi-Agent Systems, 35(2):38, 2021.
  * [4] John R Chamberlin and Paul N Courant.  Representative deliberations and representative decisions: Proportional representation and the borda rule.  American Political Science Review, 77(3):718–733, 1983.
  * [5] Shiva Chaudhuri, Naveen Garg, and Ramamoorthi Ravi.  The p-neighbor k-center problem.  Information Processing Letters, 65(3):131–134, 1998.
  * [6] Otto A Davis, Melvin J Hinich, and Peter C Ordeshook.  An expository development of a mathematical model of the electoral process.  American political science review, 64(2):426–448, 1970.
  * [7] Mark de Berg and Amirali Khosravi.  Optimal binary space partitions in the plane.  In International Computing and Combinatorics Conference, pages 216–225. Springer, 2010.
  * [8] Edith Elkind, Piotr Faliszewski, Jean-François Laslier, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon.  What do multiwinner voting rules do? an experiment over the two-dimensional euclidean domain.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31 of AAAI’17, pages 494–501, 2017.
  * [9] Edith Elkind, Piotr Faliszewski, Piotr Skowron, and Arkadii Slinko.  Properties of multiwinner voting rules.  Social Choice and Welfare, 48(3):599–632, 2017.
  * [10] Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe.  Llull and copeland voting computationally resist bribery and constructive control.  J. Artif. Intell. Res., 35:275–341, 2009.  doi:10.1613/jair.2697.
  * [11] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon.  Multiwinner voting: A new challenge for social choice theory.  Trends in computational social choice, 74(2017):27–47, 2017.
  * [12] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon.  Committee scoring rules: Axiomatic characterization and hierarchy.  ACM Transactions on Economics and Computation (TEAC), 7(1):1–39, 2019.
  * [13] Eric J Friedman, Vasilis Gkatzelis, Christos-Alexandros Psomas, and Scott Shenker.  Fair and efficient memory sharing: Confronting free riders.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1965–1972, 7 2019.
  * [14] Ashish Goel, Anilesh K Krishnaswamy, Sukolsak Sakshuwong, and Tanja Aitamurto.  Knapsack voting for participatory budgeting.  ACM Transactions on Economics and Computation (TEAC), 7:1–27, 2019\.
  * [15] Teofilo F Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical computer science, 38:293–306, 1985.
  * [16] Arnaud Grivet Sébert, Nicolas Maudet, Patrice Perny, and Paolo Viappiani.  Preference aggregation in the generalised unavailable candidate model.  In International Conference on Algorithmic Decision Theory, pages 35–50. Springer, 2021.
  * [17] Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, and Barna Saha.  A constant factor approximation algorithm for fault-tolerant k-median.  ACM Transactions on Algorithms (TALG), 12(3):1–19, 2016.
  * [18] Edith Hemaspaandra, Lane A Hemaspaandra, and Jörg Rothe.  Anyone but him: The complexity of precluding an alternative.  Artificial Intelligence, 171(5-6):255–285, 2007.
  * [19] Dorit S Hochbaum and Wolfgang Maass.  Approximation schemes for covering and packing problems in image processing and VLSI.  Journal of the ACM (JACM), pages 130–136, 1985.
  * [20] Dorit S Hochbaum and David B Shmoys.  A unified approach to approximation algorithms for bottleneck problems.  Journal of the ACM (JACM), 33(3):533–550, 1986.
  * [21] Samir Khuller, Robert Pless, and Yoram J Sussmann.  Fault tolerant k-center problems.  Theoretical Computer Science, 242(1-2):237–245, 2000.
  * [22] Sven Oliver Krumke.  On a generalization of the p-center problem.  Information processing letters, 56(2):67–71, 1995.
  * [23] Tyler Lu and Craig Boutilier.  Budgeted social choice: From consensus to personalized decision making.  In Twenty-Second International Joint Conference on Artificial Intelligence, pages 280–286, 2011.
  * [24] Tyler Lu and Craig E Boutilier.  The unavailable candidate model: a decision-theoretic view of social choice.  In Proceedings of the 11th ACM conference on Electronic commerce, pages 263–274, 2010.
  * [25] Sujaya Maiyya, Victor Zakhary, Divyakant Agrawal, and Amr El Abbadi.  Database and distributed computing fundamentals for scalable, fault-tolerant, and consistent maintenance of blockchains.  Proceedings of the VLDB Endowment, 11(12), 2018.
  * [26] Neeldhara Misra and Chinmay Sonar.  Robustness radius for chamberlin-courant on restricted domains.  In International Conference on Current Trends in Theory and Practice of Informatics, pages 341–353. Springer, 2019.
  * [27] Kamesh Munagala, Zeyu Shen, and Kangning Wang.  Optimal algorithms for multiwinner elections and the chamberlin-courant rule.  EC ’21: Proceedings of the 22nd ACM Conference on Economics and Computation, pages 697–717, 2021.
  * [28] Viswanath Nagarajan, Baruch Schieber, and Hadas Shachnai.  The euclidean k-supplier problem.  In Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013\. Proceedings 16, pages 290–301. Springer, 2013.
  * [29] Piotr Skowron, Piotr Faliszewski, and Jérôme Lang.  Finding a collective set of items: From proportional multirepresentation to group recommendation.  Artificial Intelligence, 241:191–216, 2016.
  * [30] Piotr Skowron, Piotr Faliszewski, and Arkadii Slinko.  Achieving fully proportional representation: Approximability results.  Artificial Intelligence, 222:67–103, 2015.
  * [31] Chinmay Sonar, Palash Dey, and Neeldhara Misra.  On the complexity of winner verification and candidate winner for multiwinner voting rules.  In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 89–95, 2021\.
  * [32] Chinmay Sonar, Subhash Suri, and Jie Xue.  Multiwinner elections under minimax chamberlin-courant rule in euclidean space.  In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 475–481. International Joint Conferences on Artificial Intelligence Organization, 7 2022.
  * [33] Chinmay Sonar, Subhash Suri, and Jie Xue.  Multiwinner elections under minimax chamberlin-courant rule in euclidean space, 2022.  arXiv:2205.13598.
  * [34] Chaitanya Swamy and David B Shmoys.  Fault-tolerant facility location.  ACM Transactions on Algorithms (TALG), 4(4):1–27, 2008.