Facility Location With Approval Preferences: Strategyproofness and Fairness

There is a credible continuous mirror, and I consider Theorem 12 the strongest anchor. Its fairness question is almost asking for mass rather than headcount: a group of at least \(n/k\) agents becomes a group of population mass at least \(1/k\). Theorem 2 gives a second, independent anchor for coverage optimization.

The mirror keeps the paper’s facility-location problem intact and continuizes only the population. Let \(F\) be the facilities, let \(Y\) be a finite set of rational potential locations, and let \(k\) be the number of facilities to build. A type \(t\) is a complete profile
\[ t=\left(x_t,(r_{tf})_{f\in F}\right), \]
where \(x_t\) is the residents’ common location and \(r_{tf}\in\mathbb{Q}_{\ge 0}\cup\{-\infty\}\) is their approval radius for facility \(f\). A type approves \((f,y)\) precisely when \(r_{tf}\neq-\infty\) and \(|x_t-y|\le r_{tf}\). The society is a rational distribution \(\mu\) over a finite type set \(T\). Thus \(\mu_t\) is the fraction of residents of type \(t\).

A committee \(W\subseteq F\times Y\) has size \(k\) and must satisfy exactly the paper’s compatibility conditions: no facility is placed twice, and, in the no-co-location variant, no two facilities occupy the same location. Equivalently, the decision variable is a binary vector \(z_{f,y}\) selecting a compatible size-\(k\) committee. Nothing is fractional about the facilities or the committee; only the population is represented by mass.

This is a sensible regime for a municipality, university campus, or large residential development with millions of residents but perhaps hundreds or thousands of distinct profile types: location or neighbourhood, household needs, and facility-specific approval radii. A type may represent an entire cohort of residents with indistinguishable preferences and costs. If the denominator of \(\mu\) is \(D\), the instance can be realised by \(D\) residents, or by any multiple of \(D\); hence the number of named agents can be arbitrarily larger than \(|T|\). That is precisely the high-multiplicity interpretation, not an assumption that every person has an idiosyncratic profile.

My lead anchor is Theorem 12, proved in this paper. It states that deciding whether an instance admits a size-\(k\) committee providing justified representation is \(\mathrm{NP}\)-complete, even when every approval radius is either one common value \(r\) or \(-\infty\), in the discrete no-co-location model.

The corresponding continuous problem is:

Given \(F,Y,k\), a finite type set \(T\), and rational masses \(\mu\), does there exist a compatible size-\(k\) committee \(W\) such that, for every candidate \(c\in(F\times Y)\setminus W\),
\[ \sum_{\substack{t\in T:\ c\text{ is approved by }t\\ A_t\cap W=\varnothing}}\mu_t<\frac{1}{k}, \]
where \(A_t\) is the set of facility-location pairs approved by type \(t\)?

Call this problem Continuous High-Multiplicity JR for Facility Location. The sum is the mass of residents who unanimously approve \(c\) but receive no representation from \(W\). The condition says that no such unrepresented cohesive group has mass at least \(1/k\). This is exactly the paper’s definition of JR after replacing cardinality by mass. If a type has mass larger than the threshold, one may select a submass of that type as the complaining group; this is faithful to a finite realisation containing many identical residents.

The paper’s 3-SAT reduction lifts directly. Give every profile in the reduction its corresponding rational mass, normalised by the total number of agents. Then “at least \(n/k\) agents” becomes “mass at least \(1/k\),” with no change to the feasible committees or the geometric argument. Moreover, every type can be replicated \(Q\) times without changing \(\mu\), so the same hard instances describe populations with \(N\gg |T|\). The hardness is therefore driven by facility identities, locations, and incompatibilities—not by the inability to compress a long list of individual residents.

I would expect this mirror to be Class B: hardness transfers from the discrete problem. It is not continuum-specific hardness, because the continuum is merely storing multiplicities compactly. The continuous question is nevertheless valuable: it turns the paper’s fairness notion into a genuinely population-level object and asks whether proportional representation remains computationally feasible when the electorate is described by mass. It also creates a natural weighted version of the paper’s representation theory.

The second anchor is Theorem 2, also proved in the paper. It states that FL-Coverage is \(\mathrm{NP}\)-complete both with and without co-location. The paper proves this by reducing from approval-based Chamberlin–Courant coverage, or equivalently MaxCoverage.

The corresponding problem is Continuous High-Multiplicity FL-Coverage. Given \(F,Y,k,T,\mu\), a co-location regime, and a rational threshold \(\lambda\in[0,1]\), find a compatible size-\(k\) committee \(W\) maximising
\[ \operatorname{cov}_\mu(W) = \sum_{t\in T}\mu_t\,\mathbf{1}[A_t\cap W\neq\varnothing], \]
or decide whether some \(W\) satisfies \(\operatorname{cov}_\mu(W)\ge\lambda\).

This is not a softened version of the authors’ problem. It retains facility-specific approval radii, physical locations, the integrated choice of which facilities to build and where to place them, compatibility, and unit-demand utilities. The only change is
\[ \left|\{i:u_i(W)>0\}\right| \quad\longrightarrow\quad \sum_t\mu_t\,\mathbf{1}[A_t\cap W\neq\varnothing]. \]
The theorem’s reduction already uses a special case in which all residents are co-located and approval vectors encode arbitrary approval ballots. That gives an immediate hardness transfer to the mass version. The full location-dependent problem is at least as general.

This mirror is also expected to be Class B. The combinatorics live in the facilities, approval patterns, and committee size, so increasing the multiplicity of each profile does not dissolve the hardness. In the residential interpretation, the output is still an integral construction plan, while coverage is the fraction of residents served. That is a natural statement even when individual headcounts are politically or computationally irrelevant.

The paper’s Section 5, where \(Y=\mathbb{R}\), is useful supporting evidence but is not itself a novelty collision for ChoCo. The paper continuousizes the location space while retaining a discrete list of agents and sums over them. Proposition 11 shows that continuous locations can be discretised. Our mirror continuousizes the society instead, while deliberately keeping \(Y\) finite so that no outcome-space continuity is being smuggled in. The two constructions could later be combined, but they are conceptually separate.

This case does not claim to mirror every result in the paper. In particular, it does not yet provide a population-continuous formulation of the strategyproofness results for additive agents, nor does it assert that Theorem 6’s individual strategyproofness survives unchanged when a positive-mass type reports collectively. Those are further questions. One should distinguish manipulation by a single resident, by an entire cohort, and by an infinitesimal mass of residents.

The weakest point is that Theorem 2’s published hardness reduction makes facility locations largely irrelevant, so an opponent can argue that this particular anchor is really high-multiplicity approval voting with facility-location notation. Theorem 12 is stronger against that objection: its reduction genuinely uses incompatible facility placements and geometric approval regions. Even there, however, the proposed mirror is finite-support rather than a distribution with a density over continuously varying profiles. Under ChoCo’s stated model—finite \(T\), rational masses—that is not a defect, but it is the boundary of the claim.

The mirror therefore gives two precise computational questions: mass-based justified representation and mass-based coverage maximisation. Both are recognisable continuizations of named results in the paper, both admit natural high-multiplicity scenarios, and both are expected to retain discrete hardness rather than acquire a spurious continuum-specific one.