Answer: NP-hard under polynomial-time Turing reductions. An exponential output-size lower bound also rules out polynomial time in the stated input parameters.
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm Pareto-PBS1(C, Z, ≺) always ter- minates. Each successful run returns a G-preferred solution of (C, X, Z, ≺) and each G-preferred solution is returned by exactly one successful run. Adding upper bounds thus helps to control the behaviour of PBS and to avoid that it jumps from one extreme solu- tion to the other. In figure 4, minimizing the quality refutes the cheapest price of 160, as it was required.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given τ customer types with rational masses μ_t, type-specific finite-domain CSPs with feasible configurations ℱ_t, and shared comparable criteria and preference orders, choose masses y_{tq} ≥ 0 with ∑_{q∈ℱ_t} y_{tq} = μ_t. Each individual receives an integral configuration q, while cohort criterion j is z_j(y) = ∑_t ∑_{q∈ℱ_t} y_{tq} f_{tj}(q). Determine the exact set of attainable aggregate criterion vectors that are G-preferred under the paper’s Definition 4, with a finite symbolic description and a feasible allocation witness for each represented outcome.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Normalize \(\sum_t\mu_t=1\).
Each type has a finite-domain CSP with at most \(m\) variables, explicitly listed domains and constraint relations, and feasible configurations \(\mathcal F_t\), which are not explicitly enumerated and may be empty. There are \(n\geq1\) shared criteria; Boolean circuits compute signed binary-rational values \(f_{tj}(q)\). All criterion values are already standardized and smaller values are preferred. An explicitly given strict partial order \(\prec_Z\) on criterion indices specifies importance.
An allocation assigns real masses \(y_{tq}\geq0\) satisfying \(\sum_{q\in\mathcal F_t}y_{tq}=\mu_t\); each individual receives an integral configuration. Its aggregate vector is \(z_j(y)=\sum_t\sum_{q\in\mathcal F_t}y_{tq}f_{tj}(q)\). Let \(A\subseteq\mathbb R^n\) be the attainable set.
An attainable vector \(a\) is G-preferred if there is no \(b\in A\), \(b\neq a\), such that every index \(i\) with \(a_i<b_i\) has an index \(j\prec_Z i\) with \(b_j<a_j\). Equal aggregate vectors represent one outcome.
The computational problem is to describe exactly all G-preferred vectors as a finite union of sets defined by rational linear equalities and strict or weak inequalities. Each set must carry a rational affine allocation map, using explicitly listed feasible configurations and assigning zero mass to all unlisted configurations, that realizes every vector in that set. The empty union represents no outcomes. Let \(L\) be the total input bit length.
Can this exact description and allocation representation be computed in time polynomial in \(m,\tau,n,L\), or is the computation NP-hard under polynomial-time Turing reductions?
For finite configurations, preference-based search is proved terminating, sound, complete, and duplicate-free; no polynomial running-time bound is asserted ([verified discrete result](https://cdn.aaai.org/AAAI/2002/AAAI02-006.pdf)). No result settling this exact mass-allocation problem was located.
The computation is NP-hard under polynomial-time Turing reductions, already with one type, one criterion, and an always-feasible CSP.
Moreover, the required explicit allocation representation can have exponential size. Consequently, polynomial running time in \(m,\tau,n,L\) is impossible for the full task, independently of whether \(\mathrm P=\mathrm{NP}\).
Write \(P(A)\) for the set of G-preferred attainable vectors.
If \(\prec_Z\) is empty, the domination condition in the question holds precisely when
\[
b_i\leq a_i\quad\text{for every }i,\qquad b\neq a.
\]
Indeed, any index with \(a_i<b_i\) would require a more important index, and none exists. Thus G-preference is ordinary Pareto minimality in this case.
In particular, with one criterion and nonempty attainable set \(A\), whenever its minimum exists,
\[
P(A)=\{\min A\}.
\]
Every larger attainable value is dominated by the minimum, while no attainable value dominates the minimum.
Let \(\varphi(x_1,\ldots,x_k)\) be a Boolean 3-CNF formula. Construct the following society:
\[
f(s,x)=1-s\varphi(x),
\]
where \(\varphi(x)\in\{0,1\}\) is the formula’s truth value.
Every configuration is feasible. The construction has \(m=k+1\), \(\tau=n=1\), and input length polynomial in the formula length. Its criterion values are the binary rationals \(0\) and \(1\).
If \(\varphi\) is unsatisfiable, every configuration has value \(1\). Since allocation masses sum to \(1\),
\[
A=\{1\},\qquad P(A)=\{1\}.
\]
If \(\varphi\) is satisfiable, choose a satisfying assignment \(x^\ast\). The configuration \((1,x^\ast)\) has value \(0\), while every configuration with \(s=0\) has value \(1\).
Every aggregate is a convex combination of \(0\) and \(1\), so it lies in \([0,1]\). Conversely, assigning masses \(1-\lambda\) and \(\lambda\) to these two configurations realizes aggregate \(\lambda\), for every \(\lambda\in[0,1]\). Hence
\[
A=[0,1],\qquad P(A)=\{0\}.
\]
Therefore,
\[
\varphi\text{ is satisfiable}\quad\Longleftrightarrow\quad 0\in P(A).
\]
Suppose a routine computes the requested description
\[
P(A)=\bigcup_{r=1}^{R}S_r,
\]
with each \(S_r\) given by rational linear equalities and strict or weak inequalities.
To test whether \(0\in P(A)\), substitute \(z=0\) into every defining system. A conjunction holds exactly when all its rational comparisons hold; the union contains \(0\) exactly when at least one conjunction holds. These exact comparisons take polynomial time in the returned description’s bit length.
Thus a single call to a polynomial-time description routine, followed by polynomial-time postprocessing, would decide 3-SAT. This is the explicit-output Turing reduction establishing NP-hardness.
This reduction does not depend on a large required answer. Every constructed instance admits a polynomial-size output:
Both maps are rational affine maps, list one feasible configuration, and assign zero mass to every other configuration.
We now construct polynomial-size inputs for which every valid output must explicitly list exponentially many different configurations.
Fix \(m\geq1\), and put
\[
D=2^m,\qquad N=D-1.
\]
Use one type of mass \(1\), with \(m\) unconstrained Boolean variables. Its configurations are uniquely indexed by the integers \(k\in\{0,\ldots,N\}\); denote the configuration encoding \(k\) by \(q_k\).
Use two criteria, with empty importance order, and define
\[
v_k=f(q_k)=
\left(\frac{k}{D},\frac{(N-k)^2}{D^2}\right).
\]
These values are dyadic rationals in \([0,1]\). The first circuit copies the configuration bits into a rational encoding. For the second, \(N-k\) is the bitwise complement of the \(m\)-bit encoding of \(k\); a Boolean multiplication circuit squares it. Such circuits have polynomial size, so the total input length \(L\) is polynomial in \(m\).
Since there is one type of mass \(1\),
\[
A=\operatorname{conv}\{v_0,\ldots,v_N\}.
\]
For each \(k\), consider the linear functional
\[
\ell_k(z)=
\frac{2(N-k)+\tfrac12}{D}\,z_1+z_2.
\]
Both coefficients are strictly positive.
For another index \(l\), let \(d=l-k\). Direct calculation gives
\[
\ell_k(v_l)-\ell_k(v_k)
=
\frac{d^2+\tfrac12d}{D^2}.
\]
If \(d\) is a nonzero integer, then
\[
d^2+\tfrac12d>0:
\]
for \(d\geq1\) both terms are positive, while for \(d=-h\), \(h\geq1\), the expression is \(h(h-\tfrac12)>0\).
Consequently, \(v_k\) uniquely minimizes \(\ell_k\) among all configuration vectors. For any allocation,
\[
\ell_k(z(y))-\ell_k(v_k)
=
\sum_{l=0}^{N}y_{q_l}
\bigl(\ell_k(v_l)-\ell_k(v_k)\bigr).
\]
Every summand is nonnegative, and each coefficient with \(l\neq k\) is strictly positive. Equality therefore holds exactly when
\[
y_{q_k}=1,\qquad y_{q_l}=0\quad(l\neq k).
\]
This proves two facts:
Any exact union describing all preferred vectors must contain every \(v_k\). Choose a set in that union containing \(v_k\), and evaluate its allocation map at \(v_k\).
The map must assign mass \(1\) to \(q_k\), by uniqueness of the realizing allocation. Because the task requires zero mass on every unlisted configuration, that map must explicitly list \(q_k\).
Thus all \(D=2^m\) distinct configurations must occur somewhere in the output. Its length is at least
\[
\Omega(2^m).
\]
Since \(\tau=1\), \(n=2\), and \(L\) is polynomial in \(m\), this exceeds every polynomial in the stated input parameters. Merely writing a valid output therefore rules out the proposed polynomial running-time bound.
The SAT reduction establishes computational hardness even on instances with a one-piece, polynomial-size answer. The separate construction proves that the mandatory explicit allocation maps can force exponential output.
Both arguments use always-feasible CSPs and an empty importance order. Thus neither empty feasible sets nor complicated importance relations are needed for either obstruction.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The SAT construction establishes NP-hardness in the stated explicit-output computational setting. The second construction independently establishes an exponential lower bound on the required output size. No major or minor mathematical issues were found.
With an empty importance order, an index satisfying \(a_i<b_i\) cannot have the required more-important witness. Thus the domination condition is equivalent to \(b_i\leq a_i\) for every index, together with \(b\neq a\).
The identification with Pareto minimality is correct. For one criterion, if a minimum exists, it is the unique preferred value. Both cases used in the reduction have an explicitly established minimum.
The constructed instance satisfies the input requirements:
The extra variable \(s\) guarantees a configuration of value \(1\), regardless of satisfiability.
If the formula is unsatisfiable, every configuration has value \(1\), so every normalized allocation has aggregate \(1\). Therefore \(A=\{1\}\) and \(P(A)=\{1\}\).
If the formula is satisfiable, the exhibited configurations have values \(0\) and \(1\). All aggregates lie in \([0,1]\). Assigning mass \(1-\lambda\) to the value-\(0\) configuration and mass \(\lambda\) to the value-\(1\) configuration gives aggregate \(\lambda\). Thus \(A=[0,1]\) and \(P(A)=\{0\}\).
Consequently, the equivalence between satisfiability and membership of \(0\) in the preferred set is correct.
For the required explicit union of linear systems, membership of the fixed vector \(0\) is checked by direct substitution. Rational equalities and strict or weak inequalities can all be evaluated exactly in polynomial time in the description length.
If the description routine runs in polynomial time in the original input length, its explicit output length is also polynomially bounded. The stated postprocessing therefore yields a polynomial-time SAT decision procedure using one call to that routine. Together with the standard NP-completeness of Boolean 3-SAT, this establishes the claimed computational hardness in the explicit-output setting.
The separately exhibited short outputs are valid:
Each map is rational affine, uses one feasible configuration, and assigns zero mass elsewhere. Their existence does not assume that a satisfying assignment can be found efficiently.
With \(m\geq1\), there are exactly \(D=2^m\) unconstrained Boolean configurations, indexed by \(0,\ldots,N\), where \(N=D-1\).
Both coordinates of \(v_k\) are dyadic rationals in \([0,1]\). Their binary representations require only polynomially many bits in \(m\). The complement operation computes \(N-k\), and Boolean squaring circuits have polynomial size. Thus the claim that the complete instance has \(L\) polynomial in \(m\) is justified.
Since the sole type has mass \(1\), its attainable set is precisely the convex hull of its configuration vectors.
The coefficients of \(\ell_k\) are strictly positive for every permitted \(k\), including \(k=N\).
The displayed difference calculation is correct: writing \(d=l-k\), it gives \((d^2+d/2)/D^2\). For every nonzero integer \(d\), this is strictly positive. The calculation therefore establishes that \(v_k\) uniquely minimizes \(\ell_k\) among the configuration vectors.
The extension to allocations correctly uses nonnegative masses summing to \(1\). Equality in the displayed weighted sum forces zero mass on every \(q_l\) with \(l\neq k\), and normalization then forces mass \(1\) on \(q_k\).
Accordingly:
The endpoint indices and the base case \(m=1\) satisfy the same calculations.
Every exact output must cover every \(v_k\). Any set covering \(v_k\) must carry an allocation map realizing that vector. Uniqueness forces that map to assign mass \(1\) to \(q_k\).
The requirement that unlisted configurations receive zero mass therefore forces \(q_k\) to be explicitly listed somewhere in the output. Applying this to all \(2^m\) distinct configurations proves the claimed output-length lower bound.
This argument does not depend on how the preferred vectors are divided among sets or on whether configuration lists are shared: all distinct configurations still require explicit representation somewhere.
Because \(\tau=1\), \(n=2\), and \(L\) is polynomial in \(m\), the exponential output length exceeds every polynomial in the stated parameters. The unconditional running-time obstruction follows in the explicit-output model.
The constructions lie within valid, always-feasible subclasses of the task. They need not handle empty feasible sets or nonempty importance orders to establish hardness and the output-size obstruction.
The prover does not rely on the linked discrete-search result or transfer its conclusions to mass allocations. Both arguments directly address the requested continuous allocation representation.
No repairs or additional mathematical clarification are required.
⟨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.