Answer: \(\mathrm{NP}\text{-hard}\); a polynomial bound on total computation and oracle calls would imply \(\mathrm P=\mathrm{NP}\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf MMRε(gS, Ω) ≤(1 + ε)δ at the end of the search procedure, then MR(g(p∗), ND(X), Ω) ≤δ, for any solution path p∗∈arg min pℓ:ℓ∈S MR(gℓ, gS, Ω).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite directed path graph, nonnegative additive criteria, a finite support \(T\) of complete resident preference types, and a rational polytope \(\mathcal M\subseteq\Delta(T)\) of possible population shares, let \(F_\mu(p)=\sum_{t\in T}\mu_t\psi_t(g(p))\). With pairwise comparison answers determined by an unknown \(\mu^*\in\mathcal M\), can an interleaved search and elicitation procedure return a path \(p\) whose regret \(\max_{\mu\in\mathcal M}\bigl(F_\mu(p)-\min_{p'}F_\mu(p')\bigr)\) is at most a given tolerance \(\delta\), after refining \(\mathcal M\) from those answers?
Let \(G=(V,A)\) be an explicitly given finite directed graph, with source \(s\), goal set \(\Gamma\), and a nonempty set \(P\) of simple source-to-goal paths. Each arc has \(m\) nonnegative binary-rational costs; \(g(p)\) is their componentwise sum.
Known nondecreasing rational piecewise-linear functions \(v_i:\mathbb R_+\to[0,1]\) describe criterion disutilities. Each complete type \(t\) specifies either \(\psi_t(x)=\sum_{i=1}^m w_{ti}v_i(x_i)\), with positive rational weights summing to one, or the Choquet integral of \((v_i(x_i))_{i=1}^m\) with an explicitly tabulated rational normalized monotone capacity. Lower disutility is preferred.
A society is given by its support: the list \(T\) of \(\tau\) types with positive mass, each mass a binary rational, summing to one; \(\tau\) is the support size, not the number of possible types. In this elicitation problem, the masses are hidden and constrained by a given nonempty rational polytope \(\mathcal M\subseteq\Delta(T)\), described by linear inequalities and having only positive coordinates.
For \(\mu\in\mathcal M\), define \(F_\mu(p)=\sum_{t\in T}\mu_t\psi_t(g(p))\). A comparison oracle uses a fixed unknown rational \(\mu^*\in\mathcal M\): querying two feasible paths returns one with weakly smaller \(F_{\mu^*}\), choosing either in a tie. Retain the corresponding weak linear inequality in the current polytope \(\mathcal M'\).
Given rational \(0\le\delta<1\), an adaptive procedure must return a single path \(p\in P\) with \(\max_{\mu\in\mathcal M'}[F_\mu(p)-\min_{q\in P}F_\mu(q)]\le\delta\), for every admissible hidden society and every permitted tie answer. Queries may be interleaved with computation; there is no separate query budget.
Does this tolerance-regret elicitation problem admit an algorithm with total computation and number of oracle calls polynomial in \(|V|,|A|,m,\tau,L\), or is achieving the stated guarantee NP-hard? Here \(L\) is the total binary encoding length of the supplied numerical data and function descriptions, including \(\delta\).
The finite-graph, single-decision-maker analogue has a conditional \(\delta\)-regret correctness guarantee for search interleaved with elicitation, rather than a polynomial worst-case running-time theorem ([primary source](https://www.ijcai.org/Proceedings/15/Papers/048.pdf)).
No result settling this precise support-distribution comparison-oracle problem was located.
The problem is \(\mathrm{NP}\)-hard. A procedure whose total computation and number of oracle calls are polynomial in the stated parameters would imply \(\mathrm P=\mathrm{NP}\).
This holds already for two distinct additive types, two criteria, fixed tolerance \(\delta=1/4\), and a non-singleton interval of strictly positive society masses. Allowing Choquet types yields hardness for every fixed rational tolerance \(\delta<1\).
I use the intended implicit representation of feasible paths: in the constructed instances, \(P\) consists of all simple source-to-goal paths in the supplied graph.
Write the regret of a path as
\(R_{\mathcal M'}(p)=\max_{\mu\in\mathcal M'}\bigl[F_\mu(p)-\min_{q\in P}F_\mu(q)\bigr]\).
For any fixed admissible hidden society \(\mu^*\), every permitted oracle answer retains an inequality satisfied by \(\mu^*\). Inductively, therefore, \(\mu^*\in\mathcal M'\) throughout the procedure. In particular,
\(R_{\mathcal M'}(p)\ge F_{\mu^*}(p)-\min_{q\in P}F_{\mu^*}(q)\).
Consequently, comparisons cannot make a path with actual regret greater than \(\delta\) satisfy the required guarantee. This observation applies to adaptive queries and either permitted answer in a tie.
We use the standard \(\mathrm{NP}\)-complete problem \(\mathrm{PARTITION}\): given positive integers encoded in binary, decide whether some subset has half their total sum. Its classical completeness result appears in [Karp’s *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We may assume that the total is even. Indeed, doubling every input integer preserves the answer and makes the total even, with polynomial encoding size. Denote the resulting integers by \(a_1,\ldots,a_n\), and write \(\sum_{j=1}^n a_j=2B\).
Construct vertices \(u_0,\ldots,u_n\), together with two vertices \(r_j^0,r_j^1\) for each \(j\). For each item, add the following arcs:
| Arc | Cost vector |
|---|---|
| \(u_{j-1}\to r_j^0\) | \((a_j,0)\) |
| \(u_{j-1}\to r_j^1\) | \((0,a_j)\) |
| \(r_j^0\to u_j\) | \((0,0)\) |
| \(r_j^1\to u_j\) | \((0,0)\) |
Set \(s=u_0\) and \(\Gamma=\{u_n\}\). This is a directed acyclic graph with \(3n+1\) vertices and \(4n\) arcs. All its source-to-goal paths are simple.
Every feasible path corresponds uniquely to a subset \(S\subseteq\{1,\ldots,n\}\), with
\(g(p_S)=(z_S,2B-z_S)\), where \(z_S=\sum_{j\in S}a_j\).
Call a path balanced when \(z_S=B\). Thus a balanced path exists exactly when the Partition instance is a yes-instance.
For both criteria, use
\(v_1(x)=v_2(x)=\min\{1,\max\{0,x-B\}\}\).
These functions are nondecreasing, continuous, rational piecewise-linear functions into \([0,1]\). Each has three pieces, with breakpoints \(B\) and \(B+1\).
Because both coordinates of every path cost are integers and sum to \(2B\), the transformed cost vector is exactly
For example, if \(z_S>B\), integrality gives \(z_S\ge B+1\), while \(2B-z_S\le B-1\). The other unbalanced case follows symmetrically.
Use two distinct additive types:
\(\psi_1(x)=\tfrac14v_1(x_1)+\tfrac34v_2(x_2)\),
\(\psi_2(x)=\tfrac34v_1(x_1)+\tfrac14v_2(x_2)\).
Their weights are positive rationals summing to one. Let
\(\mathcal M=\{(\mu_1,\mu_2):\mu_1+\mu_2=1,\ \tfrac14\le\mu_1\le\tfrac34\}\),
and fix \(\delta=1/4\).
This is a nonempty rational polytope of positive dimension relative to the simplex. Both coordinates are at least \(1/4\), so every admissible society has support size exactly \(\tau=2\).
Balanced paths have \(F_\mu(p)=0\) for every \(\mu\in\mathcal M\). For an unbalanced path, the two possible social disutilities are
\(\tfrac34-\tfrac12\mu_1\quad\text{and}\quad\tfrac14+\tfrac12\mu_1\).
Both belong to \([3/8,5/8]\) throughout \(\mathcal M\).
Therefore, if a balanced path exists, every unbalanced path has regret at least \(3/8>\delta\) over every nonempty current polytope \(\mathcal M'\subseteq\mathcal M\). Any output satisfying the guarantee must then be balanced, regardless of the queries or tie answers.
The uncertainty is substantive: the ordering of paths with transformed vectors \((1,0)\) and \((0,1)\) reverses as \(\mu_1\) crosses \(1/2\).
Suppose a procedure achieving the requested guarantee had polynomial total computation and polynomially many oracle calls.
Run it on the constructed instance using the fixed hidden society
\(\mu^*=(1/2,1/2)\in\mathcal M\).
At this society, balanced paths have disutility zero and every unbalanced path has disutility \(1/2\). We can consequently simulate each comparison in polynomial time: compute the queried paths’ cost sums, determine whether each is balanced, and return one with smaller disutility. In a tie, return the first queried path.
These answers come from one fixed admissible rational society and obey the allowed tie rule. Hence they form a valid oracle interaction, including when the procedure chooses its queries adaptively.
Inspect the returned path:
Testing whether its first cost coordinate equals \(B\) therefore decides Partition.
All supplied data have polynomial encoding size. In particular, \(B\) has polynomial bit length, each disutility function has only three pieces, and the types, mass constraints, and tolerance use constant-size rational data. Each simulated comparison uses polynomial-time binary arithmetic.
Thus the hypothetical procedure would decide Partition in polynomial time. This proves the claimed \(\mathrm{NP}\)-hardness in the relevant algorithmic sense: even with a polynomially simulable valid comparison oracle, producing the guaranteed path is \(\mathrm{NP}\)-hard.
The same graph and criterion functions establish a stronger result when Choquet types are permitted.
Define two capacities on \(\{1,2\}\):
| Subset | Capacity of type \(1\) | Capacity of type \(2\) |
|---|---:|---:|
| \(\varnothing\) | \(0\) | \(0\) |
| \(\{1\}\) | \(1\) | \(0\) |
| \(\{2\}\) | \(1\) | \(0\) |
| \(\{1,2\}\) | \(1\) | \(1\) |
Both capacities are rational, normalized, monotone, and explicitly tabulated.
For sorted disutilities \(y_{(1)}\le y_{(2)}\), the two-dimensional Choquet formula is
\(C_\nu(y)=y_{(1)}\nu(\{1,2\})+(y_{(2)}-y_{(1)})\nu(\{(2)\})\).
Hence these types evaluate respectively as
\(\psi_1(x)=\max\{v_1(x_1),v_2(x_2)\}\),
\(\psi_2(x)=\min\{v_1(x_1),v_2(x_2)\}\).
Their scores on balanced paths are \((0,0)\), and their scores on every unbalanced path are \((1,0)\).
Given any rational \(0\le\delta<1\), choose a dyadic rational \(c\) satisfying \(\delta<c<1\), and set
\(\mathcal M_\delta=\{(\mu_1,\mu_2):\mu_1+\mu_2=1,\ c\le\mu_1\le(1+c)/2\}\).
This interval has positive length and strictly positive coordinates. Balanced paths have social disutility zero; unbalanced paths have social disutility \(\mu_1\ge c>\delta\). Whenever a balanced path exists, every valid output must therefore be balanced.
The construction remains polynomial in the encoding of \(\delta\). Indeed, write \(\delta=a/b\), with integers \(0\le a<b\). Taking \(c=1-2^{-k}\), where \(k=\lceil\log_2 b\rceil+1\), gives
\(2^{-k}<1/b\le1-\delta\),
so \(c>\delta\), with polynomial encoding length.
Choose the fixed hidden society to be the midpoint of \(\mathcal M_\delta\). Comparisons are again polynomially simulable, since all unbalanced paths have the same score and all balanced paths have score zero. The preceding reduction therefore applies for every fixed rational tolerance below one.
This lower bound is compatible with the cited paper. Its Proposition 3 gives a regret guarantee conditional on the state reached at the end of search; it does not establish a polynomial worst-case bound for this problem. [Benabbou and Perny, IJCAI 2015](https://www.ijcai.org/Proceedings/15/Papers/048.pdf).
The target question is settled: achieving the stated guarantee is \(\mathrm{NP}\)-hard, including with genuine support-distribution uncertainty and positive tolerance.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed hardness under the explicitly stated, intended representation of feasible paths. No major or minor mathematical gaps were found. A polynomial procedure satisfying the task’s guarantee would decide binary-encoded Partition in polynomial time.
The conclusion concerns producing a guaranteed path with an interactive comparison oracle. The prover correctly explains the reduction in that algorithmic sense; it does not claim membership in a complexity class or strong NP-hardness.
The task does not specify a separate encoding of \(P\). The prover explicitly uses the natural graph-based interpretation: \(P\) consists of all simple source-to-goal paths.
This is an appropriate interpretation of the intended problem, whose polynomial bound depends on graph size rather than an explicitly enumerated path list. The construction does not require representing an arbitrary additional restriction on feasible paths.
The conclusion should retain this interpretation. It does not establish hardness for a different problem whose input explicitly enumerates every feasible path.
Every retained weak comparison inequality is satisfied by the fixed hidden society \(\mu^*\), including when the oracle breaks a tie arbitrarily. Thus the induction establishing \(\mu^*\in\mathcal M'\) is valid.
Consequently,
\(R_{\mathcal M'}(p)\ge F_{\mu^*}(p)-\min_{q\in P}F_{\mu^*}(q)\)
is correct.
The minima and maxima are well-defined: the finite graph has finitely many simple paths, \(P\) is nonempty, and the current polytope is a nonempty closed subset of the initial compact polytope. The objective is continuous in the masses.
This observation applies to adaptive queries without assuming that their sequence is fixed in advance.
The cited source problem is correctly stated: deciding whether binary-encoded positive integers admit an equal-sum partition is NP-complete. The classical result is attributed to [Karp’s paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Doubling all integers preserves the answer and makes the total even. This remains correct when the original total is odd: the doubled entries are all even, whereas their proposed half-total is odd, so no partition is introduced.
The preprocessing has polynomial encoding size. Positivity gives \(B>0\), so the function breakpoints used later lie in their stated domain.
The vertex count \(3n+1\) and arc count \(4n\) are correct. Every source-to-goal path chooses exactly one branch at each item gadget. The graph is acyclic, so every such path is simple.
The asserted subset correspondence and cost vector
\(g(p_S)=(z_S,2B-z_S)\)
are correct, taking \(S\) to index the branches contributing to the first coordinate.
All costs are permitted nonnegative binary-rational numbers; integers are a special case. Feasible paths exist regardless of the Partition answer.
A path is balanced exactly when its subset sum equals \(B\). Hence balanced-path existence is equivalent to the original decision problem.
The proposed functions are nondecreasing, continuous, rational piecewise-linear functions from \(\mathbb R_+\) into \([0,1]\). Their breakpoints and slopes have polynomial encoding length.
The three transformed vectors are correct:
Integrality is essential to the asserted constant separation, and the construction supplies it explicitly.
Both additive types have strictly positive rational weights summing to one, and they are distinct.
The mass polytope is a nonempty interval of positive relative dimension. Both mass coordinates lie in \([1/4,3/4]\), so the support size is exactly two throughout.
The social-score computations are correct. On transformed vector \((1,0)\), the score is
\(\tfrac34-\tfrac12\mu_1\);
on \((0,1)\), it is
\(\tfrac14+\tfrac12\mu_1\).
Both range over \([3/8,5/8]\).
If a balanced path exists, its score is zero for every admissible society. Since all scores are nonnegative, the optimal score is then zero for every society. Every unbalanced path therefore has regret at least \(3/8\) over every nonempty current polytope.
The strict inequality \(3/8>1/4\) establishes that every valid output on a yes-instance must be balanced. This conclusion survives all permitted comparisons and tie answers.
The claimed reversal of the ordering at \(\mu_1=1/2\) also follows directly from the two displayed score formulas.
The society \(\mu^*=(1/2,1/2)\) is rational and admissible. Under it, balanced paths have score zero and every unbalanced path has score \(1/2\).
The simulator therefore implements the actual comparison rule in polynomial time. Returning the first queried path in a tie is permitted. All answers arise from one fixed society, so adaptivity causes no consistency problem.
The output test correctly distinguishes the cases:
A simple path has polynomial description length, and its cost sum can be computed with polynomial-time binary arithmetic. Together with the hypothesized polynomial computation and query bounds, this yields a polynomial Partition decision procedure.
The inference to hardness is valid. The proof does not need the simulator to solve Partition before answering a query; it only checks the explicitly queried paths.
Both capacity tables satisfy normalization and monotonicity. Zero singleton capacities are permitted by the task.
The displayed two-dimensional Choquet formula is correct. It gives the maximum for type one and the minimum for type two. Equal transformed coordinates cause no sorting ambiguity affecting the value, because the difference term vanishes.
Thus balanced paths have type-score vector \((0,0)\), and every unbalanced path has type-score vector \((1,0)\), exactly as claimed.
For every rational \(0\le\delta<1\), the chosen interval has positive length and strictly positive mass coordinates. Its lower bound \(c>\delta\) supplies the required strict regret separation.
The encoding calculation is correct:
\(k=\lceil\log_2 b\rceil+1\) implies
\(2^{-k}<1/b\le1-\delta\).
Consequently \(c=1-2^{-k}>\delta\), and the encoding length of \(c\) is polynomial in the encoding length of \(\delta\). This includes \(\delta=0\).
The midpoint is an admissible rational hidden society of polynomial encoding length. The comparison simulation and output test remain valid. The extension establishes hardness for every fixed rational tolerance below one.
The characterization of Proposition 3 is accurate: its regret conclusion is conditional on the final minimax-regret condition. It is not a polynomial worst-case running-time theorem. [Benabbou and Perny, Proposition 3](https://www.ijcai.org/Proceedings/15/Papers/048.pdf).
The reduction does not rely on applying that proposition, so no unverified hypotheses from the cited search procedure enter the hardness argument.
No repair or additional lemma is needed. The explicit graph-based interpretation of \(P\) should remain attached to the hardness statement.
⟨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.