d4-conf-aaai-2021-0733

The strongest mirror is a nearest-facility allocation problem over a population measure. A complete type is \(t=(z,v_1,\ldots,v_m)\): a resident’s location \(z\in[0,1]\) and the per-unit utilities \(v_i\) that each facility’s manager assigns to that resident. The society is a probability measure \(\mu\) over these types. For a finite input, \(\mu\) can be encoded by rational point masses or by rational piecewise-constant spatial densities and utility profiles; let \(\tau\) count the atoms or encoded cells, and \(L\) their bit length.

A decision is a profile of distinct facility locations \(x_1,\ldots,x_m\). Each resident is assigned to a closest facility, with arbitrary tie-breaking where needed. If \(A_i(x)\) is the mass assigned to facility \(i\), its utility is \(U_i(A_i)=\int_{A_i}v_i\,d\mu\). The scale is per capita: total population mass is one, and an allocation can give a facility a fractional share of a spatial region’s mass even though each resident goes to a single closest facility. This keeps the paper’s line, facilities, facility-specific additive values, and closest-assignment rule intact.

That model fits a plausible regime: many residents along a corridor, a small number of recreation centers, and managers whose values depend on residents’ group profiles. Residents attend the nearest center; the population is described by spatial distributions rather than a list of individuals. The exact coordinate must remain part of a resident’s type because it affects which center is closest. Thus a diffuse instance has a continuum of complete types, represented by a finite density description; I would not call spatial cells themselves complete types.

My lead anchor is Theorem 3.1, proved in this paper. It says that deciding whether a given finite instance has a proportional valid allocation is NP-complete. Here “valid” means induced by pairwise distinct facility locations with each item assigned to a closest facility, and proportional means every facility \(i\) receives utility at least \(u_i(N)/m\). The authors prove this by adapting an X3C reduction and incorporating distances and facility locations.

The corresponding continuous question is Proportional Nearest-Facility Mass: given \(m\) and a finite rational encoding of \(\mu\), decide whether there are distinct facility locations and a closest-facility assignment such that
\[ U_i(A_i)\geq \frac{1}{m}\int v_i\,d\mu \qquad\text{for every }i. \]
A solution is the location profile and its induced assignment. I expect Class B hardness for this measure problem as stated. For any paper instance with \(n\) items at positions \(z_j\) and utility vectors \(u(j)\), set
\[ \mu=\frac{1}{n}\sum_{j=1}^n\delta_{(z_j,u(j))}. \]
Then each facility’s measure utility is its paper utility scaled by \(1/n\); the proportionality inequalities and feasible nearest assignments are exactly preserved. The discrete problem therefore embeds in the measure problem. This gives NP-hardness of the mirror, without claiming NP-completeness for a model with real-valued location decisions.

A second worthwhile anchor is Theorem 4.1, also proved in this paper. It says that deciding whether a finite instance has an envy-free valid allocation is NP-complete: each facility must weakly prefer its own bundle to every other facility’s bundle according to its own additive valuation. The paper says this follows by a similar reduction; the proof is omitted from the supplied main-text excerpt. Its mirror, Envy-Free Nearest-Facility Mass, uses the same instance and solution format, replacing the proportionality constraints with
\[ U_i(A_i)\geq U_i(A_j) \qquad\text{for every pair }i,j. \]
The same empirical-measure mapping preserves every inequality, so I again expect Class B hardness for the full model.

These are distinct fairness questions, not a second claim that Theorem 3.1 alone establishes envy-freeness hardness. Both are plausible mirrors because the authors’ defining allocation constraint—the closest facility serves each resident—remains in force, and the fairness tests still compare the facilities’ utilities over their assigned population. The mirror covers the existence results in Theorems 3.1 and 4.1. It does not, by itself, continuize the paper’s price-of-fairness bounds or its Pareto-optimality algorithm.

The weakest point is the boundary of the hardness claim. The embedding uses atomic measures with \(\tau=n\), and the paper’s reduction lets the number of facilities grow. It establishes hardness for the general measure problem, but does not show hardness when the society is diffuse, \(m\) is fixed, or the encoded density has small \(\tau\). Those are natural further questions: does proportional or envy-free feasibility become tractable for atomless spatial populations, and how does complexity depend on \(m\) and the density representation? The fixed-type intuition is also less direct here than in voting, since location itself is a feature the assignment rule uses. Still, the continuous population model is natural for the paper’s geography and preserves its central decision problem; the two named hardness anchors survive exactly on its empirical-measure instances.