Answer: The threshold decision problem is \(\mathrm{NP}\)-complete, even for fixed \(q=1/3\); exact computation of \(\operatorname{OPT}\) is \(\mathrm{NP}\)-hard.
Proposition 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateSet O obeys dominance axiom if and only if there exists a strictly in- creasing sequence {φm}m∈M and a strictly decreasing sequence {ϕt}t∈T of real numbers such that (m, t)R∗(n, s) implies φm + ϕt ≥φn + ϕs. This result is implied by Lemmas A.4 and A.5 in the Appendix, as well as the ne- cessity of the dominance axiom for rationalsiation by a discounted utility function.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a standardized finite experiment battery and a society represented by a finite support of response-record types \(r\), each with rational mass \(\mu_r\), compute the maximum mass \(\sum_{r\in S}\mu_r\) of types \(S\) for which there exist strictly increasing values \(\phi_m\) and strictly decreasing values \(\varphi_t\) satisfying \(\phi_m+\varphi_t\geq\phi_n+\varphi_s\) for every revealed comparison \((m,t)R^*(n,s)\) in that type’s record.
A battery consists of \(k\geq 1\) explicitly listed nonempty finite menus \(A_j\) of options \((a,t)\), with binary rational payments \(a\geq 0\) and binary integer delays \(t\geq 0\); repeated menus are allowed. Let \(m=|\bigcup_j A_j|\), and let \(M,T\) be the sets of observed payments and delays.
A response-record type \(r\) specifies exactly one choice \(x_j^r\in A_j\) for every trial. Define \(xR_r^*y\) whenever some trial chooses \(x\) while offering \(y\); these comparisons are weak, so tied options may be chosen without a fixed tie-breaking rule.
A society is given by its support: the list of the \(\tau\) response-record types with positive mass, each mass \(\mu_r\) a binary rational, with \(\sum_r\mu_r=1\). Here \(\tau\) is the support size, not the number of possible response records; \(L\) is the total input bit length.
A subset \(S\) of supported types is feasible if there is one shared pair of real-valued sequences \((\phi_a)_{a\in M}\), \((\varphi_t)_{t\in T}\), strictly increasing in payment and strictly decreasing in delay, such that \(\phi_a+\varphi_t\geq\phi_b+\varphi_s\) for every \((a,t)R_r^*(b,s)\) with \(r\in S\). Selection retains each type's entire record; \(S=\varnothing\) is allowed.
Define \(\operatorname{OPT}=\max_{S\text{ feasible}}\sum_{r\in S}\mu_r\). Its threshold decision problem takes an additional binary rational \(q\in[0,1]\) and asks whether \(\operatorname{OPT}\geq q\).
Is computing \(\operatorname{OPT}\) possible in time polynomial in \(m,\tau,k,L\), or is the threshold decision problem \(\mathrm{NP}\)-hard?
For finite choice data, discounted-utility rationalizability is equivalent to feasibility of the displayed monotone additive inequalities, with strictly increasing positive felicity and strictly decreasing positive discounting normalized at delay zero. [Finite-data characterization](https://mpra.ub.uni-muenchen.de/56596/1/MPRA_paper_56596.pdf).
A later treatment likewise characterizes rationalizability of finite preference comparisons over dated rewards. [Published characterization](https://www.sciencedirect.com/science/article/abs/pii/S0899825618301271). No result settling this exact support-weighted, shared-rationalization selection problem was located.
Result. The threshold decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when every menu has exactly two options, the observed delays are \(\{0,1,2\}\), all supported types have equal mass, every individual record is feasible, and the threshold is fixed at \(q=1/3\).
Consequently, computing \(\operatorname{OPT}\) exactly in time polynomial in \(m,\tau,k,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
1. Polynomial verification of a selected subset.
Fix a subset \(S\) of supported types. Order the observed payments and delays as
\(a_1<\cdots<a_p\) and \(t_1<\cdots<t_d\).
Consider the rational linear system consisting of all revealed-choice inequalities from \(S\), together with
\(\phi_{a_{i+1}}-\phi_{a_i}\geq 1\quad(1\leq i<p)\)
and
\(\varphi_{t_i}-\varphi_{t_{i+1}}\geq 1\quad(1\leq i<d).\)
This system is feasible exactly when \(S\) is feasible under the original strict monotonicity requirements:
There are at most \(2m\) variables and at most \(\tau km+2m\) constraints. Their coefficients and right-hand sides are integers of bounded magnitude, so the system has polynomial encoding length. Rational linear-program feasibility is decidable in polynomial time, by the [polynomial-time linear-programming theorem](https://www.mathnet.ru/eng/dan42319).
A verifier can therefore guess \(S\), check its feasibility, and compare the exact rational sum \(\sum_{r\in S}\mu_r\) with \(q\), all in polynomial time. Thus the threshold problem belongs to \(\mathrm{NP}\).
2. Encoding a graph by a common battery.
Let \(G=(V,E)\) be a finite simple graph with no isolated vertices. Write \(n=|V|\), enumerate its edges as \(e_1,\ldots,e_h\), and arbitrarily designate their endpoints by \(e_i=\{u_i,v_i\}\).
For each edge introduce three options:
\(P_i=(2i-1,0),\qquad Q_i=(2i,1),\qquad H_i=(2i,2).\)
The battery has two menus per edge:
\(A_{2i-1}=\{P_i,Q_i\},\qquad A_{2i}=\{P_i,H_i\}.\)
For each vertex \(w\in V\), define one complete response-record type \(r_w\). Its choices on the two menus for edge \(e_i\) are:
| Vertex | Choice from \(A_{2i-1}\) | Choice from \(A_{2i}\) |
|---|---|---|
| \(w=u_i\) | \(P_i\) | \(P_i\) |
| \(w=v_i\) | \(Q_i\) | \(H_i\) |
| \(w\notin\{u_i,v_i\}\) | \(Q_i\) | \(P_i\) |
Give every type mass \(\mu_{r_w}=1/n\).
These are distinct response-record types. Indeed, each vertex \(w\) has an incident edge. If \(w=u_i\), its choice \(P_i\) from the first menu differs from every other vertex’s choice there. If \(w=v_i\), its choice \(H_i\) from the second menu differs from every other vertex’s choice there.
The construction satisfies
\(\tau=n,\qquad k=2h,\qquad m=3h,\qquad T=\{0,1,2\}.\)
All payments are positive integers at most \(2h\), and all menus and records are explicitly listed.
3. Proven equivalence: feasible subsets are independent sets.
For \(W\subseteq V\), let \(S_W=\{r_w:w\in W\}\). We prove that \(S_W\) is feasible if and only if \(W\) is independent in \(G\).
*Necessity.*
Suppose that both endpoints \(u_i,v_i\) of an edge belong to \(W\). Define
\(\Delta_i=\phi_{2i}-\phi_{2i-1},\qquad D_1=\varphi_0-\varphi_1,\qquad D_2=\varphi_0-\varphi_2.\)
Strict decrease of the delay sequence implies \(D_2>D_1\).
Record \(r_{u_i}\) chooses \(P_i\) over \(Q_i\), so
\(\phi_{2i-1}+\varphi_0\geq\phi_{2i}+\varphi_1,\)
which gives \(\Delta_i\leq D_1\).
Record \(r_{v_i}\) chooses \(H_i\) over \(P_i\), so
\(\phi_{2i}+\varphi_2\geq\phi_{2i-1}+\varphi_0,\)
which gives \(\Delta_i\geq D_2\).
Together these imply \(D_2\leq\Delta_i\leq D_1\), contradicting \(D_2>D_1\). Therefore a feasible subset cannot contain both endpoints of any edge.
*Sufficiency.*
Suppose \(W\) is independent. Set
\(\varphi_0=0,\qquad\varphi_1=-1,\qquad\varphi_2=-2.\)
For each edge define a positive payment increment \(d_i\) by:
Independence ensures that the first two cases never overlap. Define
\(\phi_{2i-1}=4(i-1),\qquad \phi_{2i}=4(i-1)+d_i.\)
These payment values are strictly increasing. Within a pair the increment is positive, and between consecutive pairs,
\(\phi_{2i}\leq4(i-1)+2<4i=\phi_{2i+1}.\)
Let \(U(a,t)=\phi_a+\varphi_t\). The relevant utility differences are
\(U(Q_i)-U(P_i)=d_i-1,\qquad U(H_i)-U(P_i)=d_i-2.\)
We check every selected record’s choices.
This verifies all comparisons in all menus using one shared pair of sequences. The allowed freedom to choose either tied option is used explicitly.
Hence
\(S_W\text{ is feasible}\quad\Longleftrightarrow\quad W\text{ is independent in }G.\)
Writing \(\alpha(G)\) for the maximum independent-set cardinality, we obtain the exact identity
\(\operatorname{OPT}=\alpha(G)/n.\)
In particular, every individual supported record is feasible, because every singleton vertex set is independent.
4. Hardness at the fixed threshold \(q=1/3\).
We reduce from \(\mathrm{3SAT}\), whose \(\mathrm{NP}\)-completeness is a standard theorem; see [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Take a formula with \(c\geq1\) clauses, each having three literal occurrences. Clauses with fewer nonzero numbers of literals can be padded by repeating a literal without changing satisfiability.
Construct a graph with one vertex for each literal occurrence. Join the three vertices of each clause into a triangle. Also join any two distinct vertices whose literals are complementary. This graph has \(n=3c\) vertices and no isolated vertices.
Every independent set has size at most \(c\), because it contains at most one vertex from each clause triangle. Moreover:
Thus the formula is satisfiable exactly when \(\alpha(G)=c\).
Apply the battery construction above and use \(q=1/3\). Then
\(\operatorname{OPT}\geq1/3 \quad\Longleftrightarrow\quad \alpha(G)/(3c)\geq1/3 \quad\Longleftrightarrow\quad \alpha(G)\geq c \quad\Longleftrightarrow\quad \text{the formula is satisfiable}.\)
The graph has at most \(\binom{3c}{2}\) edges. The battery contains two menus per edge and \(3c\) explicitly listed records, each specifying every choice. Payments require \(O(\log(h+1))\) bits, and masses \(1/(3c)\) require \(O(\log(c+1))\) bits. Consequently the entire reduction has polynomial output length and runs in polynomial time.
This proves \(\mathrm{NP}\)-hardness under all the restrictions stated at the beginning. Together with polynomial verification, it proves \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed hardness and membership in \(\mathrm{NP}\). The reduction correctly preserves entire response records and uses one shared rationalization. I found one minor domain omission: Section 2 should explicitly exclude the empty graph. It does not affect the graphs produced in Section 4.
Normalization of strict monotonicity is correct. There are finitely many adjacent payment and delay gaps. If any exist, strict monotonicity makes their minimum \(\delta\) positive. Scaling both sequences by the same positive factor \(1/\delta\) preserves every homogeneous revealed-choice inequality and makes all adjacent gaps at least \(1\).
Conversely, adjacent gaps of at least \(1\) imply the required strict monotonicity throughout each ordered sequence. If neither sequence has an adjacent gap, both monotonicity requirements are vacuous; the prover explicitly handles this case.
The linear-system size bounds are correct. Every observed payment and delay occurs in an observed option, so \(|M|+|T|\leq 2m\). Each selected record contributes at most \(km\) comparisons, including harmless self-comparisons. There are at most \(\tau km\) revealed-choice constraints and fewer than \(2m\) adjacent monotonicity constraints.
The coefficients have bounded integer magnitude. The numerical payments and delays determine their ordering and variable labels; they do not become large coefficients in the system. Sorting their binary encodings and constructing the constraints take polynomial time.
The linear-programming theorem applies. The invoked result is that feasibility of a finite rational linear system can be decided in time polynomial in its binary encoding length. The constructed system meets these hypotheses. Neither boundedness nor strict feasibility is required. The cited reference is [Khachiyan’s polynomial-time linear-programming paper](https://www.mathnet.ru/eng/dan42319).
The \(\mathrm{NP}\) membership argument is correct. A subset of the explicitly listed support has a certificate of length \(\tau\). Feasibility can be checked deterministically in polynomial time. Summing the selected binary rational masses and comparing the sum with \(q\) also take polynomial time: the bit lengths of intermediate common denominators are bounded by the sum of the input denominator bit lengths.
This argument includes \(S=\varnothing\) and the threshold endpoints \(q=0\) and \(q=1\). No numerical utility certificate needs to be guessed.
For a nonempty simple graph without isolated vertices, the construction is valid.
Distinctness of records is correctly proved. At an incident edge, a vertex designated \(u_i\) is the only vertex choosing \(P_i\) from the first menu. A vertex designated \(v_i\) is the only vertex choosing \(H_i\) from the second menu. Consequently, no two vertices produce the same complete record, and \(\tau=n\).
Minor issue: the graph’s nonemptiness is unstated. A finite simple graph with no isolated vertices can be empty. For that graph, \(n=h=0\), the mass \(1/n\) is undefined, and the construction violates \(k\geq1\). The claimed observed delay set also fails.
The minimum clarification is to add \(n\geq1\) to Section 2’s graph assumptions. Together with the absence of isolated vertices, this ensures \(h\geq1\). Section 4 already produces graphs satisfying these conditions, so the omission does not undermine the reduction.
Necessity is correct. If both endpoints of an edge are selected, their records impose
\(\Delta_i\leq D_1\) and \(\Delta_i\geq D_2\). Strict decrease over delays \(0<1<2\) gives \(D_2>D_1\). These inequalities are incompatible.
The contradiction uses only weak revealed-choice comparisons and strict delay monotonicity, exactly as required by the task.
Sufficiency is correct, including all selected records. Independence makes the three cases defining \(d_i\) mutually exclusive and exhaustive. Each increment is positive and at most \(2\). The stated calculation correctly verifies strict payment monotonicity both within each pair and between consecutive pairs. The chosen delay values are strictly decreasing.
The utility differences are correctly computed:
\[
\]
\(U(Q_i)-U(P_i)=d_i-1\) and \(U(H_i)-U(P_i)=d_i-2\).
The three checks cover every possible selected record at every edge:
Independence excludes the opposite endpoint in the first two cases. Ties are permitted by the task, so the different choices at tied menus cause no inconsistency.
The same sequences serve every edge and every selected record. The empty subset is also covered: the displayed sequences remain strictly monotone, and no revealed-choice constraints need checking.
Thus the stated equivalence is established. Since the records are distinct and equally weighted, the identity \(\operatorname{OPT}=\alpha(G)/n\) follows. The claim that every individual record is feasible follows from the same equivalence.
The negative delay-sequence values introduce no issue: the task explicitly permits real-valued additive sequences.
The source problem and graph reduction are valid. The invoked standard theorem is the \(\mathrm{NP}\)-completeness of Boolean satisfiability for conjunctions of clauses with three literal occurrences. Karp’s cited treatment includes satisfiability with at most three literals per clause; repeating a literal preserves a nonempty clause’s truth value and supplies the stated three-occurrence representation. See [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Repeated literals cause no problem because graph vertices represent occurrences, not distinct literals. Each clause therefore contributes three distinct vertices forming a triangle. Adding complementary-literal edges preserves simplicity when edges are treated as a set.
The independent-set correspondence is correctly proved. The disjoint clause triangles bound every independent set’s size by \(c\). A satisfying assignment supplies one true occurrence per clause, with no complementary pair. Conversely, an independent set of size \(c\) contains exactly one occurrence per clause; absence of complementary pairs makes the prescribed variable values consistent.
The constructed graph has \(n=3c>0\), and every vertex has its two clause-triangle neighbors. Hence it meets the graph assumptions needed for the battery construction.
The threshold calculation is exact. Equal masses give \(\operatorname{OPT}=\alpha(G)/(3c)\). Consequently, the fixed threshold \(q=1/3\) is reached exactly when \(\alpha(G)\geq c\), which is equivalent to satisfiability.
The encoding bound is sufficient. There are \(O(c^2)\) edges and \(O(c^3)\) explicitly listed record choices. Payments, record references, and masses require only polynomially many bits. Thus both construction time and output length are polynomial in the source input length.
All claimed restrictions are attained. Combining the reduction with Section 1 proves \(\mathrm{NP}\)-completeness. An exact polynomial-time computation of \(\operatorname{OPT}\) would decide the threshold problem by exact comparison and therefore imply \(\mathrm{P}=\mathrm{NP}\).
Add an explicit nonemptiness assumption to Section 2. No new lemma, construction, or substantive argument is needed.
⟨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.