Answer: \(\mathrm{NP}\text{-complete}\), even when every supported type has mass \(w_t=1\).
Corollary 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-complete to decide if a given UFL game Γ has a strong equilibrium. In the Appendix we show how to extend this result to connection-restricted facility location games (CRFL games) from [18], in which access to a facility f can be obtained only by certain allowed coalitions Af ⊆2T . We consider the special case of closed games (CCRFL games), in which the set system Af of allowed coalitions is downward closed, i.e., each subset of an allowed coalition is also an allowed coalition. This simplifies the specific allocation of the cost shares to connections and facilities.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given facilities \(F\), supported terminal types \(T\), rational masses \(w_t=N\mu_t\), opening costs \(a_f\), and type-to-facility costs \(d_{tf}\), decide whether there are nonnegative per-unit prices \(\pi_t\) with \(\sum_t w_t\pi_t=c(w)\) and \(\sum_t q_t\pi_t\le c(q)\) for every \(q\) satisfying \(0\le q_t\le w_t\). Here \(c(q)\) is the minimum UFL cost to serve mass \(q\), with each individual assigned to one facility and type-level assignments allowed to be fractional.
Let \(F\) be a nonempty facility set, with \(m=|F|\), and let \(T\) be the nonempty support of terminal types. A society is given by its support: the list of its \(\tau=|T|\) types with positive masses \(w_t\), each encoded as a binary rational; \(\tau\) counts supported types, not all possible types.
Write \(N=\sum_{t\in T}w_t>0\) and \(\mu_t=w_t/N\), so \(\sum_t\mu_t=1\); the masses \(w_t\) need not sum to one. Opening costs \(a_f\) and per-unit connection costs \(d_{tf}\) are finite nonnegative binary rationals, with no metric assumption. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
For every real coalition vector \(q\) with \(0\le q_t\le w_t\), define \(c(q)=\min\{\sum_f a_fy_f+\sum_{t,f}d_{tf}x_{tf}:\sum_f x_{tf}=q_t,\ 0\le x_{tf}\le q_ty_f,\ y_f\in\{0,1\}\}\).
Thus facilities open wholly and have unlimited capacity; \(x_{tf}\) is assigned mass. Each individual uses one facility, but a type's mass may be divided among facilities. In particular, \(c(0)=0\).
The decision problem asks whether there exist real per-unit prices \(\pi_t\ge0\) satisfying \(\sum_t w_t\pi_t=c(w)\) and \(\sum_t q_t\pi_t\le c(q)\) for every such \(q\).
Is this continuous core-nonemptiness decision problem in \(\mathrm{P}\), or is it NP-hard?
For finitely many individual terminals, deciding strong-equilibrium existence is NP-complete, and existence is equivalent to core nonemptiness ([Hoefer](https://algo.rwth-aachen.de/team/hoefer/papers/Hoefer11CoreSNE.pdf)).
Discrete UFL core nonemptiness is NP-complete and is equivalent to equality of the integer optimum and the standard UFL LP optimum ([Goemans–Skutella](https://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2000-14.pdf)). No result settling the exact mass formulation above was identified in the literature search.
The continuous core-nonemptiness problem is \(\mathrm{NP}\)-complete, even when every supported type has mass \(w_t=1\).
The key fact is that allowing fractional coalitions adds no constraints beyond those imposed by coalitions containing either all or none of each type’s mass. I prove this first, then give the reduction and a polynomial-time verifier.
Write \(u_+=\max\{u,0\}\).
Lemma. A vector \(\pi\in\mathbb R^\tau_{\ge0}\) satisfies every coalition inequality if and only if, for every facility \(f\),
\[\displaystyle \sum_{t\in T}w_t(\pi_t-d_{tf})_+\le a_f. \tag{1}\]
Proof of necessity. Fix \(f\), and choose the permitted coalition
\(\displaystyle q_t=\begin{cases}w_t,&\pi_t>d_{tf},\\0,&\pi_t\le d_{tf}.\end{cases}\)
If this coalition is empty, the left side of (1) is zero, so (1) follows from \(a_f\ge0\). Otherwise, opening \(f\) and assigning all coalition mass to it is feasible. Consequently,
\(\displaystyle \sum_tq_t\pi_t\le c(q)\le a_f+\sum_tq_td_{tf}.\)
Subtracting connection costs gives (1).
Proof of sufficiency. Suppose (1) holds, and fix any permitted \(q\) and any feasible solution \((x,y)\) serving it. For every open facility \(f\), we have \(0\le x_{tf}\le q_t\le w_t\). Thus
\(\displaystyle \sum_tx_{tf}(\pi_t-d_{tf})\le\sum_tw_t(\pi_t-d_{tf})_+\le a_f.\)
Closed facilities receive no mass because \(x_{tf}\le q_ty_f\). Summing over open facilities and using \(\sum_fx_{tf}=q_t\), we obtain
\(\displaystyle \sum_tq_t\pi_t\le\sum_fa_fy_f+\sum_{t,f}d_{tf}x_{tf}.\)
This holds for every feasible solution, hence also for its minimum cost \(c(q)\). The empty coalition satisfies the inequality directly. This proves the lemma.
In particular, necessity used only coalitions whose coordinates belong to \(\{0,w_t\}\). Therefore checking all such coalitions is sufficient for stability against every real coalition.
Construct a discrete UFL instance with one customer for each supported type. Retain opening costs \(a_f\), and set its connection costs to
\(\displaystyle D_{tf}=w_td_{tf}.\)
For a subset \(S\subseteq T\), let \(C_D(S)\) denote its discrete minimum service cost, with \(C_D(\varnothing)=0\). Let \(w^S_t=w_t\) for \(t\in S\), and \(w^S_t=0\) otherwise.
Then
\[\displaystyle C_D(S)=c(w^S). \tag{2}\]
Indeed, for any fixed nonempty open facility set \(A\), the minimum connection cost in either formulation is
\(\displaystyle \sum_{t\in S}w_t\min_{f\in A}d_{tf}=\sum_{t\in S}\min_{f\in A}D_{tf}.\)
In the mass formulation this minimum is attained by assigning the whole mass of each type to a cheapest open facility. Dividing mass cannot improve a linear connection objective. Minimizing over \(A\) proves (2) for nonempty \(S\); the empty case follows from nonnegative costs.
A discrete core allocation is a vector \(v\) satisfying
\(\displaystyle \sum_tv_t=C_D(T),\qquad \sum_{t\in S}v_t\le C_D(S)\quad\text{for every }S\subseteq T.\)
Such an allocation is automatically nonnegative. To see this, first observe that \(C_D\) is monotone: deleting customers from a feasible solution cannot increase its cost. Applying the core inequality to \(T\setminus\{t\}\) gives
\(\displaystyle v_t=C_D(T)-\sum_{s\ne t}v_s\ge C_D(T)-C_D(T\setminus\{t\})\ge0.\)
Proposition. The continuous instance has a core price vector if and only if the constructed discrete instance has a core allocation. The correspondence is \(v_t=w_t\pi_t\).
Proof. A continuous core price vector gives a discrete core allocation by applying its inequalities to \(w^S\) and using (2).
Conversely, suppose \(v\) is a discrete core allocation and define \(\pi_t=v_t/w_t\). This is well-defined and nonnegative because \(w_t>0\). Equation (2) gives budget balance:
\(\displaystyle \sum_tw_t\pi_t=\sum_tv_t=C_D(T)=c(w).\)
For each facility \(f\), define \(S_f=\{t:v_t>D_{tf}\}\). If \(S_f\) is nonempty, its discrete core inequality and the feasible solution opening only \(f\) give
\(\displaystyle \sum_{t\in S_f}v_t\le C_D(S_f)\le a_f+\sum_{t\in S_f}D_{tf}.\)
Hence
\(\displaystyle \sum_tw_t(\pi_t-d_{tf})_+=\sum_{t\in S_f}(v_t-D_{tf})\le a_f.\)
If \(S_f\) is empty, the same inequality follows from \(a_f\ge0\). The lemma now establishes every real-coalition inequality.
This equivalence uses exactly \(\tau\) discrete customers. It does not expand rational masses into individual terminals.
Goemans–Skutella, Theorem 5.1, establishes that deciding discrete UFL core nonemptiness is \(\mathrm{NP}\)-complete. [Source](https://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2000-14.pdf)
Their hardness construction allows forbidden connections, represented by infinite costs. These can be replaced by finite integers without changing any discrete coalition cost. Specifically, let \(B\) be the cost of a feasible solution serving every customer through finite-cost connections. Every subset then has a feasible solution costing at most \(B\), obtained by deleting the other customers. Replace each forbidden connection cost by \(B+1\). Any discrete solution using a replaced connection costs at least \(B+1\), so it cannot be optimal for any subset. The construction in that theorem has integer costs and such a bound \(B\) with polynomial encoding length.
Now take a finite-cost discrete instance from this hard family. Create a supported type for each customer, set \(w_t=1\), and retain all opening and connection costs. Section 2 proves that its continuous core is nonempty exactly when its discrete core is nonempty.
The transformation copies the explicit cost table and adds \(\tau\) unit masses. It takes \(O(L+m\tau)\) bit operations and has polynomial output length. All masses are positive; both sets are nonempty; all costs are finite nonnegative binary rationals. Thus this is a polynomial many-one reduction satisfying the stated hypotheses.
Therefore the continuous problem is \(\mathrm{NP}\)-hard already with unit masses.
The characterization also gives a direct verifier, without assuming that real prices themselves can be supplied as certificates.
Let \(R\) be the maximum revenue attainable by a stable nonnegative price vector. It is the optimum of the following rational linear program:
\(\displaystyle \text{maximize }\sum_tw_t\pi_t,\)
subject to
\[\displaystyle \pi_t\ge0,\qquad b_{tf}\ge0,\qquad b_{tf}\ge\pi_t-d_{tf},\qquad \sum_tw_tb_{tf}\le a_f\quad(f\in F). \tag{3}\]
For fixed \(\pi\), these constraints admit \(b\) exactly when (1) holds: necessity follows from \(b_{tf}\ge(\pi_t-d_{tf})_+\), and sufficiency follows by choosing equality.
The program is feasible at \(\pi=b=0\). It is bounded: for any fixed facility \(f\), its constraints imply
\(\displaystyle b_{tf}\le\frac{a_f}{w_t},\qquad \pi_t\le d_{tf}+\frac{a_f}{w_t}.\)
It consequently attains a finite optimum. It has \(\tau+m\tau\) variables and \(O(m\tau+m+\tau)\) constraints, with rational encoding length polynomial in \(m,\tau,L\). Exact rational linear programming computes \(R\) in \(\operatorname{poly}(m,\tau,L)\) time.
Every feasible price vector is stable, so its grand-coalition inequality gives \(R\le c(w)\). Because the maximum is attained,
\[\displaystyle \text{the core is nonempty}\quad\Longleftrightarrow\quad R=c(w). \tag{4}\]
A certificate consists simply of a nonempty facility subset \(A\subseteq F\). Its minimum cost of serving the grand coalition is
\(\displaystyle K(A)=\sum_{f\in A}a_f+\sum_tw_t\min_{f\in A}d_{tf}.\)
The verifier computes \(R\), computes \(K(A)\), and accepts precisely when they are equal.
If it accepts, then \(R\le c(w)\le K(A)=R\), so (4) proves core nonemptiness. Conversely, if the core is nonempty, an optimal grand-coalition facility subset satisfies \(K(A)=c(w)=R\), and is accepted.
The certificate has \(m\) bits, and verification takes \(\operatorname{poly}(m,\tau,L)\) time. Thus the problem belongs to \(\mathrm{NP}\).
For completeness, an exact deterministic algorithm computes \(R\) and enumerates all nonempty facility subsets to compute \(c(w)\). Its running time is
\(\displaystyle \operatorname{poly}(m,\tau,L)+O\!\left(2^m m\tau\,\operatorname{poly}(L)\right).\)
Together with the reduction, this proves \(\mathrm{NP}\)-completeness. A polynomial-time algorithm for unrestricted inputs would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the argument establishes \(\mathrm{NP}\)-completeness for the stated continuous mass formulation, including hardness when every supported type has unit mass. I found no major or minor mathematical issues.
Necessity is valid. For a fixed facility \(f\), the chosen coalition includes exactly the types for which \(\pi_t-d_{tf}>0\), at their full supported masses. Its coordinates satisfy the permitted bounds. When the coalition is nonempty, opening \(f\) gives a feasible solution, so both inequalities in
\[
\sum_tq_t\pi_t\le c(q)\le a_f+\sum_tq_td_{tf}
\]
have the stated justification. Subtracting the connection costs produces precisely condition (1). The empty-coalition case is correctly handled by \(a_f\ge0\).
Sufficiency is valid. For every open facility, the estimate
\[
\sum_tx_{tf}(\pi_t-d_{tf})
\le \sum_tw_t(\pi_t-d_{tf})_+
\]
holds term by term. Negative terms on the left are at most zero; positive terms are bounded using \(x_{tf}\le w_t\). Closed facilities receive zero mass. Summing therefore counts each opened facility’s cost once and recovers the coalition’s total payment through the assignment equalities.
The argument applies to every feasible solution for every permitted real coalition. Taking the minimum is justified: there are finitely many opening patterns, and each feasible assignment region is compact. Finite costs and a nonempty facility set ensure feasibility.
Consequently, the assertion that full-type coalitions suffice is established. It does not assume that fractional coalitions have discrete assignments.
The coalition-cost identity (2) is correct. For a fixed nonempty open set, unlimited capacity and the linear connection objective allow each type’s entire mass to be assigned to a cheapest open facility. Splitting cannot reduce that minimum. Because \(w_t>0\), multiplication by \(w_t\) preserves the ordering of connection costs. Minimizing over opening patterns gives the claimed identity.
The empty coalition is treated correctly: opening no facilities costs zero, and nonnegative costs preclude a cheaper solution.
Nonnegativity of discrete core allocations is proved correctly. Deleting customers preserves feasibility and cannot increase cost. Applying the complement-coalition inequality together with budget balance gives the displayed lower bound on each allocation coordinate. This also covers a single supported type, whose complement is empty.
Both directions of the correspondence are valid.
The construction uses exactly \(\tau\) customers. No expansion by mass denominators is needed, and no assumption that the masses sum to one appears in the proof.
The cited theorem matches the required source problem. Goemans–Skutella’s Theorem 5.1 states \(\mathrm{NP}\)-completeness of core nonemptiness for general unconstrained facility-location instances. Its construction uses nonnegative integer finite costs together with forbidden connections represented by infinity. The construction also gives every customer a finite-cost service option. These facts are confirmed in [the cited paper, Section 5](https://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2000-14.pdf).
The finite-cost replacement is valid. A feasible grand-coalition solution of cost \(B\) yields a feasible solution of cost at most \(B\) for every subset by deleting customers. Any discrete solution using a replacement connection costs at least \(B+1\), because costs are nonnegative and a discrete connection incurs its entire connection cost. Hence replacement connections cannot occur in an optimal solution for any subset.
Preserving every discrete coalition cost preserves the discrete core. The subsequent equivalence from Section 2 transfers this conclusion to the continuous instance. The argument does not require the replacement to preserve the source LP optimum.
The source construction supports a polynomially computable feasible bound with polynomial encoding length. Thus replacing forbidden entries and writing the explicit finite cost table is polynomial time.
Setting every supported mass to one then preserves the discrete instance’s coalition costs and core status. All target hypotheses are met, and the reduction proves the claimed restricted hardness.
The auxiliary-variable formulation is exact. The two lower bounds on \(b_{tf}\) imply
\[
b_{tf}\ge(\pi_t-d_{tf})_+.
\]
Conversely, choosing equality satisfies those bounds whenever condition (1) holds. Positive weights preserve the required inequalities.
Feasibility, boundedness, and attainment are justified. The zero vector is feasible because connection and opening costs are nonnegative. Each facility constraint bounds every associated auxiliary variable, since its summands are nonnegative and \(w_t>0\). The displayed upper bound on prices follows. The feasible region is closed and bounded in all variables, so the optimum is attained. Zero opening costs cause no exception.
The polynomial-time LP claim has the required hypotheses. The program has polynomially many variables and constraints, rational coefficients, and polynomial encoding length. Exact rational linear programming therefore computes its optimum in polynomial bit complexity. Exact equality testing, rather than numerical approximation, is appropriate here.
The core criterion (4) follows. Stability supplies the grand-coalition bound \(R\le c(w)\). Attainment ensures that equality produces an actual budget-balanced stable price vector. Conversely, any core vector attains revenue \(c(w)\).
The certificate verifier is sound and complete. A nonempty facility subset has polynomial certificate length, and its cost \(K(A)\) is computable using rational arithmetic in polynomial time. Acceptance gives
\[
R\le c(w)\le K(A)=R,
\]
which forces core nonemptiness. On a yes-instance, an optimal grand-coalition opening pattern provides an accepting certificate. Such a nonempty optimal pattern exists because total demand is positive.
The polynomial verification bound and the stated enumeration bound are consistent with the explicit binary-rational input. Rational products, sums, comparisons, and minima have polynomial bit complexity in \(L\).
The proof covers arbitrary positive rational masses, unnormalized total mass, singleton sets, zero costs, ties in cheapest facilities, and the empty coalition. It uses no metric assumption.
No additional clarification is required to verify the conclusion.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.