Answer: Polynomial-time solvable: the problem belongs to \(\mathrm P\).
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateConsider a data set S = {Bt, xt}t∈T where each Bt is a finite union of closed, monotone polyhedral sets Bj t , with j = 1, . . . , ℓt, each having a non-empty interior. Then, the following statements are equivalent: (i) The data set S is rationalizable by a locally non–satiated and quasi–concave utility function. (ii) For all t ∈T and j = 1, . . . , ℓt, there exist numbers αj,i t ≥0, with i = 1, . . . , |Kj t |, such that • ∑|Kj t | i=1 αj,i t = 1; • minj ∑|Kj t | i=1 αj,i t qj,i t xt = 1; • {Ht, xt}t∈T satisfies garp, where, Ht = x ∈Rn + min j=1,...,ℓt |Kj t | ∑ i=1 αj,i t qj,i t x ≤1 .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support rational distribution \(\mu\) over consumer types \(a\), each specified by a finite history \(\{(B_{a,r},x_{a,r})\}_{r\in R_a}\) with explicit rational polyhedral-union budgets, decide whether every type with \(\mu_a>0\) has a locally non-satiated, quasi-concave utility rationalizing its history; equivalently, test Proposition 1’s linear feasibility system for each supported type.
A society is given by its support: a list of \(\tau\) consumer types with positive binary-rational masses \(\mu_a\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) goods. Each type \(a\) has a nonempty finite history \(\{(B_{a,r},x_{a,r})\}_{r\in R_a}\), with rational chosen bundles \(x_{a,r}\in B_{a,r}\subseteq\mathbb R_+^m\).
Each budget is explicitly represented as \(B_{a,r}=\bigcup_{j=1}^{\ell_{a,r}}B_{a,r}^j\), where \(\ell_{a,r}\geq1\) and \(B_{a,r}^j=\{x\in\mathbb R_+^m:q_{a,r}^{j,i}\cdot x\leq1\text{ for every }i\}\), using a nonempty finite list of rational vectors \(q_{a,r}^{j,i}\in\mathbb Q_+^m\). Components are closed, downward closed, and have nonempty interior; boundedness is not required.
A type is rationalizable if there exists a locally non-satiated, quasi-concave utility \(u_a:\mathbb R_+^m\to\mathbb R\) such that \(u_a(x_{a,r})\geq u_a(x)\) for every \(r\in R_a\) and \(x\in B_{a,r}\). Utilities may differ across types; no continuity or additional monotonicity is imposed.
Let \(N\), \(J\), and \(H\) be the total numbers of observations, polyhedral components, and listed inequalities, respectively, and let \(L\) be the total binary input length. State running times in \(m,\tau,N,J,H,L\).
Is deciding whether every supported type is rationalizable solvable in polynomial time in \(m,\tau,N,J,H,L\), or is it NP-hard?
For a single finite consumer history with these budgets, Cherchye, Demuynck, and De Rock establish an equivalent linear feasibility system and an efficient linear-programming test.
The supplied result does not separately formulate the distribution-over-types decision problem.
The decision problem is polynomial-time solvable in \(m,\tau,N,J,H,L\). The supplied single-history test can be applied independently to each explicitly listed supported type.
We use the supplied Cherchye–Demuynck–De Rock result in its stated algorithmic form: for a finite history with budgets represented as explicit finite unions of polyhedral components of the specified kind, existence of a locally non-satiated, quasi-concave rationalizing utility can be decided by an efficient linear-programming test. Their [paper](https://www.sciencedirect.com/science/article/abs/pii/S0022053114000684) gives the underlying linear-inequality characterization.
Write \(n,j,h,\lambda\) for the numbers of observations, components, listed inequalities, and input bits in one history. The algorithmic consequence of the supplied result is a running-time bound
\(p(m,n,j,h,\lambda)\), where \(p\) is a fixed polynomial, which we may take to be nondecreasing in each argument.
Here we use the efficient-test part of the supplied premise: equivalence to linear feasibility alone would not suffice without polynomial bounds on the formulation and its rational encoding.
For every supported type, the hypotheses match: its history is finite and nonempty, its observed bundles are rational and feasible, and its budgets have exactly the explicit polyhedral-union representation specified in the task. The required utility properties also coincide. We invoke the supplied result for these budgets, including the permitted unbounded components; we impose no additional continuity or monotonicity requirement.
For each \(a\in\{1,\ldots,\tau\}\), let \(\mathcal U_a\) be the set of locally non-satiated, quasi-concave utilities rationalizing all observations of type \(a\).
The society condition is precisely
\(\mathcal U_a\neq\varnothing\) for every \(a\in\{1,\ldots,\tau\}\).
Indeed, if the society satisfies the condition, each type has a rationalizing utility, so every \(\mathcal U_a\) is nonempty. Conversely, if every \(\mathcal U_a\) is nonempty, choose one \(u_a\in\mathcal U_a\) for each of the finitely many supported types. These utilities satisfy all required conditions. No constraint involves utilities belonging to different types.
The positive masses identify the listed types as supported. Their numerical magnitudes do not enter any rationalizability condition.
Apply the supplied single-history test to every listed type. Reject if any test rejects; otherwise accept.
If the algorithm accepts, the single-history equivalence gives \(\mathcal U_a\neq\varnothing\) for every supported type, so Section 2 proves that the society satisfies the requirement.
If the algorithm rejects, some type has \(\mathcal U_a=\varnothing\), again by that equivalence. Therefore the requirement that every supported type be rationalizable fails.
Thus the algorithm is correct in both directions.
Let \(N_a,J_a,H_a,L_a\) denote the corresponding input parameters for type \(a\). Then
\(\sum_a N_a=N\), \(\sum_a J_a=J\), and \(\sum_a H_a=H\), while each \(L_a\leq L\).
Including polynomial-time input parsing, the total running time is bounded by
\(\operatorname{poly}(L)+\sum_{a=1}^{\tau}p(m,N_a,J_a,H_a,L_a)\).
By the coordinatewise monotonicity of \(p\), this is at most
\(\operatorname{poly}(L)+\tau\,p(m,N,J,H,L)\),
which is polynomial in all six requested parameters.
Crucially, the algorithm processes only the explicitly listed support. It does not enumerate possible consumer types. Consequently, the absence of a separately formulated distribution-over-types theorem creates no additional computational obstacle.
The problem therefore belongs to \(\mathrm P\); an \(\mathrm{NP}\)-hardness result under polynomial-time many-one reductions would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument is correct under the supplied single-history premise. It establishes polynomial-time solvability of the society decision problem. No major or minor issues were found.
The prover accurately restates the supplied result: a finite history with the specified budget representation admits a locally non-satiated, quasi-concave rationalizing utility exactly when the supplied linear-programming test accepts.
The hypotheses match the input for each type: finite nonempty histories, rational feasible observations, and explicitly represented finite unions of the specified polyhedral components. The prover also expressly includes unbounded components and does not introduce continuity or additional monotonicity assumptions.
The polynomial-time conclusion relies on the supplied efficient test, rather than on linear-feasibility equivalence alone. The prover explicitly identifies this distinction. Against the premise granted by USER_TASK, it need not reproduce the underlying LP formulation or prove the cited theorem independently.
The definition of \(\mathcal U_a\) is appropriate: it contains exactly the utilities satisfying the rationalizability conditions for type \(a\).
The equivalence between society rationalizability and \(\mathcal U_a\neq\varnothing\) for every supported type is valid in both directions. In the reverse direction, selecting one utility from each of finitely many nonempty sets suffices. The task imposes no common utility or other constraint coupling different types.
The treatment of masses is correct. Their positivity makes every listed type supported; their magnitudes do not affect the individual rationalizability conditions.
The algorithm tests every listed type and accepts exactly when all tests accept.
Acceptance implies that each \(\mathcal U_a\) is nonempty by the supplied single-history equivalence. Rejection identifies a supported type whose history is not rationalizable. These are precisely the two outcomes required by the society decision problem.
The parameter identities
\(\sum_a N_a=N\), \(\sum_a J_a=J\), and \(\sum_a H_a=H\) correctly reflect the explicit support representation. Each individual history has input length at most \(L\).
Taking a coordinatewise nondecreasing polynomial upper bound \(p\) is legitimate. Consequently, the stated estimate
\[
\operatorname{poly}(L)+\sum_{a=1}^{\tau}p(m,N_a,J_a,H_a,L_a)
\leq
\operatorname{poly}(L)+\tau\,p(m,N,J,H,L)
\]
is valid and polynomial in all requested parameters. No enumeration of unlisted possible types occurs.
Membership in \(\mathrm P\) follows. The final qualification concerning NP-hardness is also correct: polynomial-time many-one NP-hardness together with this algorithm would imply \(\mathrm P=\mathrm{NP}\).
Repair feedback: None is required. The output resolves the assigned question using the supplied theorem.
⟨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.