| paper | d4-journals-jet-2014-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the problem belongs to \(\mathrm P\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
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 finite-support population \(\mu\) of household types, each carrying its own finite budget-choice history and its own LP witness. The decision is whether every positive-mass type passes; the numerical masses affect feasibility only through which types are in the support.
The exact repeated histories required for a type make the population wrapper a support-wise batch of individual tests; the proponent acknowledges the restriction but does not establish how often such cohorts arise.
fatal: False
The mirror covers Proposition 1’s convex-rationalizability test for finite unions of polyhedral budgets. It does not cover the general co-convex-hull characterization in Theorem 3 or the separate results on GARP and non-convex rationalizations.
My strongest mirror is the paper’s test of convex rationalizability for consumers facing nonlinear budgets. The continuous object is the population: a fraction \(\mu_a\) of households belongs to each of a small number \(\tau\) of complete consumer types. A type records the household’s preference archetype, budget environments, and finite observed history of choices. For example, a large labor-supply or tax-benefit population could contain many households in each standardized profile, with nonlinear budget sets formed by tax brackets and guaranteed-income rules. Within a type, households share the preferences and other characteristics the test uses; their budget-and-choice history is the same. The population may be large even when the number of distinct types is modest.
For each type \(a\), the input is a finite dataset \(\mathcal D_a=\{(B_{a,r},x_{a,r})\}_{r\in R_a}\). Each \(x_{a,r}\in\mathbb R_+^n\) is an observed bundle, and each \(B_{a,r}\) is a closed, monotone budget set represented as an explicit finite union of polyhedral convex sets with rational data. The question is whether there is a locally non-satiated, quasi-concave utility \(u_a\) that makes every \(x_{a,r}\) maximize utility over \(B_{a,r}\). A solution is a yes/no answer, with a utility rationalization or a feasibility certificate. This is a recognition problem, so it has no optimization objective; its decision variables are the utility-witness parameters. If the model requires one common preference across several types, their observations can instead be pooled into one dataset.
The anchor is Proposition 1, proved in this paper. For finite unions of closed, monotone polyhedral budget sets with nonempty interiors, it gives four equivalent conditions: (i) the data are rationalizable by a locally non-satiated, quasi-concave utility; (ii) there are coefficients \(\alpha_t^{j,i}\ge 0\), summing to one for each budget piece, such that the co-convex hulls
\[
H_t=\left\{x\in\mathbb R_+^n:
\min_j\sum_i\alpha_t^{j,i}(q_t^{j,i})^\top x\le 1\right\}
\]
pass GARP; (iii) there are \(U_t\ge 0\), \(\lambda_t>0\), and such coefficients satisfying, for every pair \(t,v\) and every piece \(k\) of \(B_v\),
\[
U_t-U_v\le \lambda_v\left(\sum_i\alpha_v^{k,i}(q_v^{k,i})^\top x_t-1\right),
\]
together with \(\sum_i\alpha_t^{j,i}=1\) and \(\sum_i\alpha_t^{j,i}(q_t^{j,i})^\top x_t\ge1\) for every \(t,j\); and (iv) the data are rationalizable by an increasing, concave, continuous utility. Here each budget piece has an explicit finite description \(B_t^j=\{x\ge0:\max_i(q_t^{j,i})^\top x\le1\}\).
The paper then operationalizes the condition as a linear feasibility problem: set \(\tilde\alpha_t^{j,i}=\lambda_t\alpha_t^{j,i}\). The constraints become
\[
U_t-U_v\le \sum_i\tilde\alpha_v^{k,i}(q_v^{k,i})^\top x_t-\lambda_v,\qquad
\sum_i\tilde\alpha_t^{j,i}=\lambda_t,\qquad
\sum_i\tilde\alpha_t^{j,i}(q_t^{j,i})^\top x_t\ge\lambda_t,
\]
with nonnegative coefficients and positive \(\lambda_t\). Thus, for explicit rational inputs, the test is solvable in polynomial time in the number of goods, observations, budget pieces and facets, and their bit length. Applied per type, the total running time is polynomial in the explicit population-support input size.
I expect this mirror to be tractable. It is a Class A case in the programme’s sense: the authors’ characterization turns the underlying rationalizability question into a problem continuous-optimization methods can solve. The mass \(\mu_a\) is the share of society represented by a type. Each positive-mass type’s observations must pass the test; averaging bundles would change the question and is unnecessary. Since the paper contains no named hardness result, Proposition 1 is the honest lead even though the programme generally benefits most from hardness anchors.
The authors should recognize the underlying question: for each type, it is exactly their finite-data convex-rationalizability problem. The scope is narrow and deliberate. This mirrors Proposition 1’s polyhedral-budget case, not every nonlinear budget set covered by the more abstract Theorem 3. Nor does it count the paper’s continuous commodity space as continuization: the mirror’s continuous object is the population.
The weakest point is that the population wrapper adds little computational content. Once the positive-mass types and their histories are listed, the masses do not change the feasibility test; it is just a batch of the paper’s tests. The scenario also requires unusually repeated histories and shared preferences within each type, which fits standardized menus or administrative cohorts better than unrestricted household data. That leaves a real, but modest, mirror: a sensible high-multiplicity regime whose tractability comes from Proposition 1, rather than from population mass dissolving a discrete hardness barrier.
This formulation raises follow-up questions about pooling types under a common preference, extending the test to infinitely supported budget or choice distributions, and whether observed choice shares can be explained when the model imposes specific tie-breaking rules. Those are additional questions; Proposition 1 directly supports the finite-support mirror above.
Proposition 1 is the proponent’s strongest anchor: it turns convex rationalizability into a linear feasibility test. The problem is that its index \(t\) denotes a choice situation in a revealed-preference dataset, not a person in a population. The comparisons across those situations are essential. If each consumer type carries its full observed history, then repeated consumers of that type just repeat the same test. If each type gets its own unknown utility, the tests are independent. In neither version does mass enter the constraints.
The strongest alternative is to pool observations from a large cohort under a shared-preference assumption. That is a recognizable demand-analysis question, and Proposition 1 can test it. But the test depends on which budget-choice pairs occur, not how often they occur: duplicate pairs add redundant constraints, and changing their population shares does not change the answer. After removing duplicates, this is the paper’s finite-data problem again. A genuinely continuous distribution over budget-choice pairs would need an exact representation or additional structure; without that, the paper’s finite LP does not specify a computational problem for it.
One could make population shares matter by asking what fraction of consumers can be rationalized, or by imposing an aggregate demand condition. Those would be new questions, not mirrors of Proposition 1. They also move away from the paper’s individual choice model. More broadly, the paper studies whether one consumer’s choices fit a preference relation; it has no collective choice, allocation, or strategic interaction for a continuous society to change. So the proposed mirror does not expose a population-scale computational question for ChoCo.
This is not an airtight case against every possible use: a cohort with shared preferences and varied budgets is plausible, and the resulting test is useful in demand analysis. The negative case is strongest on fit and substance: that scenario adds a population interpretation, but population mass contributes no computational structure, and the underlying question remains individual revealed-preference testing.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.