| paper | d4-conf-wine-2018-0003 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: NP-hard, even for $\tau=1$ and $\epsilon=0$; deciding $D_0\le3$ is already NP-hard. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a fixed experiment protocol, a finite support of revealed-preference graph types \(G_t\) on its observation set, rational masses \(\mu_t\) summing to one, and rational \(0\le\epsilon<1\), determine the least integer \(d\ge1\) such that \(\sum_{t:\operatorname{RPDim}(G_t)\le d}\mu_t\ge1-\epsilon\).
Consumers are distributed over complete graph types \(t\), each with mass \(\mu_t\). Each type retains its own observed history and RP-dimension realization; the decision is the common goods dimension \(d\) needed to account for at least \(1-\epsilon\) of the population.
The mirror aggregates Theorem 1’s RP-dimension question across graph types. It leaves the poset results in Theorems 2 and 3 aside, and does not resolve the paper’s open complexity question for RevPrefDim.
The mirror I find defensible is a population audit of revealed-preference dimension. Imagine a large consumer panel run through standardized price experiments. Each consumer has a revealed-preference graph on their observed choices. Many consumers may share the same graph pattern, even if the panel has millions of people. Let a type \(t\) be one such graph \(G_t\), and let \(\mu_t\) be the fraction of consumers with that graph. The regime is credible when the number of consumers is large and the support size \(\tau\)—the number of distinct graph patterns—is much smaller.
I would call the resulting problem Population RP-Dimension Quantile. Given finite support \(T\), graphs \(G_t=(V_t,E_t)\), rational masses \(\mu_t\) summing to one, and an allowed exception fraction \(\epsilon\), find
\[
D_\epsilon(\mu)=\min\left\{d\ge1:\exists S\subseteq T,\
\sum_{t\in S}\mu_t\ge1-\epsilon,\
\operatorname{RPDim}(G_t)\le d\ \text{for every }t\in S\right\}.
\]
A solution gives \(d\), the included types \(S\), and, for each included type, vectors \(p_{t,i},x_{t,i}\in\mathbb R_{\ge0}^d\) satisfying
\[
(i,j)\in E_t\quad\Longleftrightarrow\quad
\langle p_{t,i},x_{t,i}\rangle>\langle p_{t,i},x_{t,j}\rangle
\]
for every \(i,j\in V_t\). Thus the question is: how many goods are needed to account for at least \(1-\epsilon\) of the population’s observed graph patterns? The mass is the fraction of consumers; \(\epsilon\) allows a specified fraction of the panel’s behavior types to remain unexplained.
My anchor is Theorem 1, proved in this paper. It states that for every directed graph \(G\),
\[
\operatorname{RPDim}(G)=\operatorname{RPDim}(G^+)
=\operatorname{SgnRnk}(M(G^+))-1.
\]
Here \(G^+\) adds a dominating vertex \(s\) with edges \(s\to v\), a dominated vertex \(t\) with edges \(v\to t\), and the edge \(s\to t\); \(M(H)\) has a zero on the diagonal, \(+\) for each edge of \(H\), and \(-\) for each non-edge. This is a characterization of the underlying dimension problem, not a theorem placing it in a complexity class. The paper uses it to discuss complexity, but explicitly leaves open whether \(\operatorname{RevPrefDim}\) is NP-hard. That is the only anchor I would rely on: the paper supplies no named result settling the complexity of this problem.
The mirror covers that dimension question, aggregated over a high-multiplicity population; it does not try to continuize the paper’s poset results or its matrix encoding. It is plausible as the authors’ problem because every type-level question is exactly their question about whether a revealed-preference graph admits a realization in \(d\) goods. The population version asks how much of a consumer panel has graphs with that property. For \(\epsilon=0\) and a single type, it is precisely their problem.
My expectation is hardness transfers if the base problem is hard, not continuum-specific hardness. A one-type society embeds any \(\operatorname{RevPrefDim}\) instance, so population mass cannot dissolve hardness in that case. With \(\tau\) types, the population problem amounts to solving the dimension question for each support graph and taking a weighted quantile; if the base problem is tractable, the aggregate version is tractable in \(\tau\) such computations. The crucial further question is whether the restricted sign-rank instances in Theorem 1 are themselves hard or admit an efficient algorithm.
The weak point is that this is an aggregate audit over consumers’ *whole graphs*, rather than a continuous relaxation of the graph realization itself. The paper’s graph vertices are observations within a consumer, not people. Also, when \(\epsilon=0\), the masses only identify which graph types occur; they do not affect realizability. So this is a narrow but plausible population mirror, not evidence that continuization changes the core sign-rank problem.
The paper’s only plausible anchor is Theorem 1, but it is an exact representation identity for one consumer’s graph, not a theorem about an algorithm or complexity class. The complexity consequences are discussed afterward, and deciding whether \(\operatorname{RevPrefDim}\) is NP-hard is left open. So the proposed population problem would extend an unresolved single-instance question; it would not continuize a complexity result the paper establishes.
The strongest version of the proposed mirror is still coherent: with a fixed experiment protocol, treat each consumer’s complete revealed-preference graph as their type, and ask what fraction of the population has RP dimension at most \(d\). That avoids a weak objection about the experiment histories differing. Repeated graph types could occur in a large panel, and the weighted quantile could be a useful descriptive audit.
The deeper problem is that the graph’s vertices are repeated observations of the same consumer. An edge \(i\to j\) compares that consumer’s choice at one price with another bundle from their own history. Pool observations across people and those comparisons cease to have the revealed-preference meaning used in the paper: different consumers may have different utilities. Keep each person’s history intact, and each graph is realized independently. A common goods dimension then gives exactly the quantile problem; it adds no coupling between types. A more ambitious mass-transfer or repair problem would need a new intervention and cost model that the paper does not supply. Continuizing the observation index instead would change the axis from population to observations.
That leaves the quantile as a population statistic over instances of the paper’s open problem. This is a reason to doubt that it opens a worthwhile continuous-computational landscape, but it is not a proof that the question is illegitimate: under a broad reading, authors could recognize it as a useful population-level audit. The negative case is therefore limited. I would not claim that no scenario can yield a sensible mirror; I would argue that the best candidate is a thin distributional wrapper, while the paper itself offers no proved complexity result for that wrapper to extend.
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.