d4-conf-aaai-2021-0733 (d4-conf-aaai-2021-0733)

Given \(m\) and a finite rational encoding of a unit-mass population over types \(t=(z,v_1,\ldots,v_m)\), with \(z\in[0,1]\) and facility values represented by rational atoms or piecewise-constant spatial densities and value profiles, decide whether there exist pairwise-distinct facility locations \(x_1,\ldots,x_m\in[0,1]\) and a measurable assignment \(A_1,\ldots,A_m\) that assigns each unit of mass only to a nearest facility and satisfies \(\int_{A_i}v_i(t)\,d\mu(t)\geq \frac{1}{m}\int v_i(t)\,d\mu(t)\) for every facility \(i\).

Let \(m\geq2\). A society is given by its support: a list of \(\tau\) types \(t=(z_t,v_{1t},\ldots,v_{mt})\) with positive binary-rational masses \(p_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; locations \(z_t\in[0,1]\) are pairwise distinct rationals, values \(v_{it}\geq0\) are rational, and \(\max_i v_{it}>0\) for every type. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Each type represents divisible mass. An assignment specifies real masses \(a_{it}\geq0\) with \(\sum_i a_{it}=p_t\). Facility locations \(x_i\in[0,1]\) must be pairwise distinct, and \(a_{it}>0\) requires \(|z_t-x_i|=\min_j|z_t-x_j|\); mass may be split arbitrarily among tied nearest facilities. Facility \(i\)'s utility is \(\sum_t v_{it}a_{it}\); empty bundles are allowed and facility totals need not be normalized.
Is deciding whether such locations and an assignment exist satisfying \(\sum_t v_{it}a_{it}\geq\frac1m\sum_t p_tv_{it}\) for every \(i\) in P, or is it NP-hard?
For indivisible agents at distinct locations, existence of a proportional nearest-facility allocation is NP-complete ([Wang et al., 2021](https://cdn.aaai.org/ojs/16719/16719-13-20213-1-2-20210518.pdf)).
For spatially nonatomic demand, a polynomial-query algorithm guarantees half of each proportional share, and exact proportionality need not exist ([Wang and Zhang, 2021](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p1371.pdf)); these results do not classify the finite-support divisible-mass decision problem stated here.

Result. The decision problem is \(\mathrm{NP}\)-complete when \(m\) is part of the input. For every fixed \(m\), it is polynomial-time solvable.

The reduction below uses an exact-cover construction, with an endpoint atom and a separating atom that prevent divisibility from defeating the reduction. The exact-cover framework is motivated by [Wang et al. (2021)](https://cdn.aaai.org/ojs/16719/16719-13-20213-1-2-20210518.pdf); the divisible-mass argument is proved explicitly here.

1. Notation and geometry. Define the full-mass value of type \(t\) to facility \(i\) by \(W_{it}=p_tv_{it}\), and write \(q_{it}=a_{it}/p_t\). Thus \(q_{it}\geq0\), \(\sum_iq_{it}=1\), and facility \(i\)'s utility is \(\sum_tW_{it}q_{it}\). Its proportional threshold is \(\frac1m\sum_tW_{it}\).

Order the distinct facility locations as \(y_1<\cdots<y_m\), and define \(b_k=(y_k+y_{k+1})/2\) for \(1\leq k<m\). For \(u<v\),

\[ \]

The relevant comparison, written explicitly, is \(|z-u|\leq|z-v|\) if and only if \(z\leq(u+v)/2\), obtained by squaring both sides. Consequently, the nearest-facility region of rank \(k\) is the interval between its adjacent boundaries, intersected with \([0,1]\). Its interior has a unique nearest facility. Also, \(b_{k+1}-b_k=(y_{k+2}-y_k)/2>0\), so an atom can tie only between two adjacent facilities.

Two consequences will be used:

• At \(z=1\), the rightmost facility is uniquely nearest, because its distance is \(1-y_m\).
• If a facility receives positive mass at positions \(u<v\), then it is uniquely nearest at every position strictly between \(u\) and \(v\). Indeed, both positions belong to its nearest-facility interval, and every point strictly between them lies in that interval's interior.

2. Membership in \(\mathrm{NP}\). Guess a permutation specifying the spatial order of the facilities. For each type, guess either one facility rank or two adjacent ranks as the facilities permitted to receive its mass.

For a guessed singleton rank \(k\), impose \(b_{k-1}\leq z_t\leq b_k\), omitting the nonexistent boundary at either end. For a guessed adjacent pair \(k,k+1\), impose \(b_k=z_t\). Set all allocation fractions outside the guessed set to zero.

These constraints, the mass constraints, and the proportionality inequalities are linear. To enforce distinct facility locations, introduce \(\delta\), impose \(0\leq\delta\leq1\) and \(y_{k+1}-y_k\geq\delta\), and maximize \(\delta\), with all locations in \([0,1]\).

The guessed pattern is realizable precisely when this rational linear program has positive optimum. A positive optimum gives distinct locations and a valid assignment. Conversely, any valid solution supplies a guess whose linear program admits a positive \(\delta\), namely the minimum consecutive facility distance.

The program has \(O(m+\tau)\) variables and constraints after retaining only permitted allocation fractions. Its coefficients have bit length polynomial in \(L+\log m\). Exact rational linear programming therefore verifies a guess in \(\operatorname{poly}(m,\tau,L)\) time. This proves membership in \(\mathrm{NP}\).

3. Reduction construction. Reduce from the standard \(\mathrm{NP}\)-complete problem Exact Cover by 3-Sets. Let the universe be \(X\), with \(|X|=3s\), and let the family be \(T_1,\ldots,T_r\), where each set has three distinct elements. We may restrict to \(s,r\geq1\), since excluded cases are trivial.

Write \(T_j=\{e_{j1},e_{j2},e_{j3}\}\), choosing an arbitrary ordering within each set. Construct

\(m=r+3s+2,\qquad \tau=3r+s+2,\qquad D=5r+s+2.\)

The types are:

• Three occurrence types \(c_{j1},c_{j2},c_{j3}\) for each set \(T_j\), at \(z(c_{jk})=(5(j-1)+k)/D\).
• A separating type \(g\), at \(z(g)=(5r+1)/D\).
• Reserve types \(B_1,\ldots,B_s\), at \(z(B_\ell)=(5r+1+\ell)/D\).
• An endpoint type \(w\), at \(z(w)=1\).

These positions are pairwise distinct and ordered with all occurrence types before \(g\), and all reserve types between \(g\) and \(w\).

There are a set facility \(F_j\) for each \(T_j\), an element facility \(E_e\) for each \(e\in X\), a separating facility \(G\), and an endpoint facility \(H\).

Specify their full-mass values \(W\) as follows; every unspecified value is zero.

For each set facility \(F_j\),

\(W_{F_j,c_{jk}}=\frac13\quad(k=1,2,3),\qquad W_{F_j,B_\ell}=1\quad(1\leq\ell\leq s),\qquad W_{F_j,w}=m-s-1.\)

For an element \(e\), let \(f_e\) be the number of sets containing it. Set

\(W_{E_e,c_{jk}}=1\ \text{when }e=e_{jk},\qquad W_{E_e,w}=m-f_e.\)

Finally, set

\(W_{G,g}=1,\qquad W_{G,w}=m-1,\qquad W_{H,w}=m.\)

All these values are nonnegative: \(f_e\leq r<m\), and \(m-s-1=r+2s+1>0\). Every facility's total full-mass value is exactly \(m\), so every proportional threshold is exactly \(1\).

To obtain the required masses, let \(h=\lceil\log_2\tau\rceil\). Give every type other than \(w\) mass \(2^{-h}\), and give \(w\) mass \(1-(\tau-1)2^{-h}\). These are positive dyadic rationals summing to \(1\). Define the input values by \(v_{it}=W_{it}/p_t\).

Every type has positive value for some facility: occurrence types for their set facilities, reserve types for set facilities, \(g\) for \(G\), and \(w\) for \(H\). Thus the construction satisfies every input hypothesis.

4. Soundness: a proportional solution gives an exact cover. Suppose the constructed instance has a valid proportional solution.

Facility \(H\) values only \(w\). To reach threshold \(1\), it must receive positive mass there. Because \(w\) lies at \(1\), it has a unique nearest facility. Therefore \(H\) receives all of \(w\), and every other facility receives none of it.

Facility \(G\) can now obtain utility only from \(g\), whose full-mass value to \(G\) is \(1\). Its threshold forces \(q_{G,g}=1\).

No other facility can receive positive mass both at an occurrence type and at a reserve type. Otherwise, \(g\) lies strictly between two positions where that facility receives positive mass. By the geometric consequence proved above, that facility would be uniquely nearest at \(g\), contradicting \(q_{G,g}=1\).

Let \(C\) be the set of indices \(j\) for which \(F_j\) receives positive mass at some reserve type.

If \(j\in C\), facility \(F_j\) receives no occurrence mass and no endpoint mass. Its threshold therefore requires \(\sum_{\ell=1}^s q_{F_j,B_\ell}\geq1\). Summing over \(j\in C\) and using the mass constraints gives

\(|C|\leq\sum_{j\in C}\sum_{\ell=1}^s q_{F_j,B_\ell}\leq s.\)

If \(j\notin C\), facility \(F_j\) gets no reserve mass and no endpoint mass. Its threshold requires

\(\frac13\sum_{k=1}^3 q_{F_j,c_{jk}}\geq1.\)

Each fraction is at most \(1\), so all three equal \(1\). Thus \(F_j\) receives its entire occurrence triple.

Every element facility \(E_e\) must reach positive utility without receiving \(w\). It consequently receives positive mass at an occurrence representing \(e\). That occurrence cannot belong to a set with index outside \(C\), because such triples go entirely to their set facilities. Hence every element of \(X\) belongs to some \(T_j\) with \(j\in C\).

Therefore,

\(3s=|X|=\left|\bigcup_{j\in C}T_j\right|\leq3|C|\leq3s.\)

Equality throughout implies \(|C|=s\), and these \(s\) three-element sets are pairwise disjoint and cover \(X\). They form an exact cover. This argument permits arbitrary real allocation fractions, including arbitrary splitting at ties.

5. Completeness: an exact cover gives a proportional solution. Suppose \(s\) sets form an exact cover.

For each selected set, assign its set facility a different reserve type and locate it at that type. For each unselected set \(T_j\), locate \(F_j\) at its middle occurrence \(c_{j2}\) and assign it its whole occurrence triple.

Each element occurs in exactly one selected set. Locate its element facility at the corresponding occurrence type in that set and assign it that entire type. Locate \(G\) at \(g\) and \(H\) at \(w\), assigning each its entire type.

All facility locations are distinct. At every type occupied by its assigned facility, that facility is uniquely nearest. The only remaining cases are the two outer occurrences of an unselected triple. Each is at distance \(1/D\) from its set facility, whereas every facility outside that triple is at distance at least \(3/D\): consecutive triples have a gap of \(3/D\), as does the last triple and \(g\). Thus these assignments also obey the nearest-facility rule.

Every set facility, element facility, and separating facility receives utility \(1\). Facility \(H\) receives utility \(m\). All proportional thresholds are satisfied.

The reduction is therefore an equivalence.

6. Running times and conclusion. The reduction produces \(m=r+3s+2\) facilities and \(\tau=3r+s+2\) types. Each coordinate, mass, and value has \(O(\log(r+s+2))\) bits, so its explicit output length is \(L=O(m\tau\log(r+s+2))\). Construction takes polynomial time in that output length. Together with membership in \(\mathrm{NP}\), this establishes \(\mathrm{NP}\)-completeness.

For completeness, a deterministic algorithm runs in

\(m!(2\tau+1)^{m-1}\operatorname{poly}(m,\tau,L).\)

Sort the support positions, enumerate the facility permutation, and specify each midpoint boundary as either equal to a support position or lying in one of the gaps before, between, or after support positions. There are \(2\tau+1\) choices per boundary.

Each specification prescribes the permitted allocation ranks. Check it by the linear program above, using equality for an atom boundary and weak interval constraints for a gap boundary. Weak gap endpoints cause no false positives: they may create an additional nearest facility, but every permitted assignment remains nearest. Every actual solution appears in the enumeration by choosing its actual boundary positions. Positive \(\delta\) enforces distinct locations.

Thus the problem is polynomial-time solvable for fixed \(m\), but \(\mathrm{NP}\)-complete for variable \(m\).

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output resolves the stated finite-support divisible-mass problem: it is \(\mathrm{NP}\)-complete when \(m\) varies and polynomial-time solvable for every fixed \(m\). I found no substantive mathematical gaps or false steps.

• Normalization and geometry are correct. Since every \(p_t>0\), the fractions \(q_{it}=a_{it}/p_t\) are well-defined and preserve both feasibility and utilities.

The midpoint comparison is valid. For distinct ordered facilities, the nearest-facility regions are intervals, and consecutive boundaries satisfy
\[ b_{k+1}-b_k=\frac{y_{k+2}-y_k}{2}>0. \]
Consequently, a support point can tie only between two adjacent facilities. The endpoint \(1\) has a unique nearest facility. The stated consequence concerning positive allocations at two positions is also correct: every strictly intermediate position lies in the interior of that facility’s nearest-facility region.

• Membership in \(\mathrm{NP}\) is established. The permutation and recipient guesses have polynomial encoding length. Singleton guesses use weak inequalities correctly: a facility may receive all mass even when another facility is tied. Adjacent-pair guesses impose precisely the required midpoint equality.

Maximizing \(\delta\) correctly handles strict distinctness. Every valid configuration has a positive minimum consecutive distance, and every feasible solution with \(\delta>0\) has distinct locations. The feasible region is bounded, so a positive supremum cannot introduce an unattained-optimum issue.

After eliminating forbidden allocation variables, there are at most \(2\tau\) allocation variables, together with \(m\) locations and \(\delta\). There are \(O(m+\tau)\) constraints. All coefficients are rational with polynomial bit length. The invoked polynomial-time solvability of rational linear programming applies, including exact comparison of the optimum with zero. Thus a deterministic polynomial-time verifier can check each guessed pattern.

• The reduction satisfies the input requirements. The source problem is the standard exact-cover problem with a universe of size \(3s\) and three-element subsets; the cited [Wang et al. paper](https://cdn.aaai.org/ojs/16719/16719-13-20213-1-2-20210518.pdf) uses this same source problem in Theorem 3.1. The supplied proof establishes its divisible-mass reduction independently.

The constructed coordinates are distinct and lie in \([0,1]\). In particular, the last reserve coordinate is \((5r+s+1)/D<1\). The number of types is correctly counted as \(3r+s+2\).

The full-mass value totals check out:
\[ \sum_tW_{F_j,t}=1+s+(m-s-1)=m,\qquad \sum_tW_{E_e,t}=f_e+(m-f_e)=m. \]
The totals for \(G\) and \(H\) are also \(m\), so every threshold is exactly \(1\). All specified values are nonnegative.

Since \(2^h\geq\tau\), the endpoint mass is at least \(2^{-h}>0\). The masses sum to \(1\), and dividing \(W_{it}\) by \(p_t\) gives permitted rational values. Every type has a positive value for at least one facility.

• Soundness holds despite arbitrary splitting. Facility \(H\) must receive positive endpoint mass. Endpoint uniqueness then forces all endpoint mass to \(H\). Facility \(G\), deprived of endpoint mass, must receive all of \(g\).

The separating argument is valid: any other facility receiving positive mass on both sides of \(g\) would be uniquely nearest at \(g\), contradicting its complete allocation to \(G\).

For each \(j\in C\), the threshold therefore requires at least one unit of total reserve fractions. Summing gives \(|C|\leq s\). For \(j\notin C\), the only possible positive utility comes from its own occurrence triple. Its threshold forces all three fractions to equal \(1\).

Every element facility must obtain positive utility from an occurrence belonging to a set indexed by \(C\). Hence those sets cover \(X\), and the displayed cardinality chain forces \(|C|=s\) and pairwise disjointness. No integrality assumption on allocations enters this argument.

Elements with \(f_e=0\) create no overlooked exception: their facilities cannot meet the threshold after losing access to the endpoint, so such an instance cannot yield a proportional solution.

• Completeness is correct. The construction places exactly one facility at each selected occurrence, each reserve, the separating type, and the endpoint; unselected set facilities occupy their own middle occurrences. All locations are distinct, and every type is assigned.

For an unselected triple, each outer occurrence is \(1/D\) from its assigned facility. Consecutive triples are separated by \(3/D\), and the last triple is likewise separated from \(g\) by \(3/D\). Thus every outside facility is farther away. All proposed allocations satisfy the nearest-facility rule.

The utilities are exactly as claimed: \(1\) for each set, element, and separating facility, and \(m\) for \(H\).

• The encoding and running-time claims are valid. Coordinates, masses, and values each have \(O(\log(r+s+2))\) bits, including the endpoint value divisions. The explicit construction consequently has polynomial size and takes polynomial time.

For the deterministic algorithm, there are \(\tau\) atom choices and \(\tau+1\) gap choices per boundary, giving \(2\tau+1\) possibilities. Weak gap endpoints preserve validity because they can introduce additional ties without invalidating the recipients already permitted by the specification. Incompatible boundary specifications are rejected by the location constraints and positive-\(\delta\) requirement.

Every feasible solution has an enumerated permutation and boundary specification. Therefore the stated running time
\[ m!(2\tau+1)^{m-1}\operatorname{poly}(m,\tau,L) \]
is justified and is polynomial for fixed \(m\).

Required feedback: No mathematical repair or additional clarification is needed. The fixed-\(m\) result is a parameter restriction, rather than a dependence on input representation; the appropriate continuous complexity classification is therefore “hardness.”

⟨structured verdict parsed — rendered above⟩