# Fault Tolerance in Euclidean Committee Selection

*Chinmay Sonar*,
*Subhash Suri* and
*Jie Xue*

Papers from arXiv.org

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

**Date:** 2023-08

**New Economics Papers:** this item is included in nep-mic

**References:** View references in EconPapers View complete reference list from CitEc

**Citations:** Track citations by RSS feed

**Downloads:** (external link)

http://arxiv.org/pdf/2308.07268 Latest version (application/pdf)

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** https://EconPapers.repec.org/RePEc:arx:papers:2308.07268

Access Statistics for this paper

More papers in Papers from arXiv.org

Bibliographic data for series maintained by arXiv administrators ().