| paper | d4-conf-ijcai-2017-0348 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; the exact output problem belongs to \(\mathrm{FP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Corollary 10
statement extracted from the paper’s text layer
Given a finite rational catalogue \(A\subseteq\mathbb{Q}^d\) and a rational-mass distribution \(\mu\) over consistent comparison-profile types \(t\), each described by \(\Lambda_t\subseteq\mathbb{Q}^d\), compute for every \(a\in A\) the mass \(M(a)=\sum_{t:\,a\in P_t(A)}\mu_t\), and return a maximizer, where \(P_t(A)=\{a\in A:\exists u\in SI(\Lambda_t),\ u\cdot a\ge u\cdot b\ \forall b\in A\}\) and \(SI(\Lambda_t)=\operatorname{cone}(\Lambda_t)\cap\{u:u\cdot\lambda\ge1\ \forall\lambda\in\Lambda_t\}\).
A population with rational masses over complete, recurring comparison profiles and a shared finite product catalogue. For each profile and product, an LP tests whether some input-rescaling-invariant max-margin vector makes that product possibly optimal; summing the masses gives its possibility reach \(M(a)\).
The mirror covers the input-rescaling-invariant inference characterization and its possibly-optimal alternatives, aggregated over profile types. It leaves aside the feature-rescaling variants, undominated-set computations, experimental comparisons, and imprecise-probability discussion.
My strongest honest case is a Mass-POS Recommendation mirror, anchored on Corollary 10, with its geometric statement in Theorem 9. Both are proved in this paper. The paper has no named hardness result, and these results do not themselves state a complexity class; the authors use their characterizations to compute preference relations and optimal alternatives, and leave complexity analysis as future work.
Theorem 9 says that for any preference-input set \(\Lambda\), the vectors that can be minimum-norm max-margin solutions under some independent positive rescaling of the inputs are exactly \(SI(\Lambda)=co(\Lambda)\cap\Lambda^\ge\). Here \(co(\Lambda)\) is the positive cone generated by \(\Lambda\), and \(\Lambda^\ge=\{u:\ u\cdot\lambda\ge1\text{ for every }\lambda\in\Lambda\}\). Corollary 10 gives the computational form for finite \(\Lambda=\{\lambda_i:i\in I\}\): \(u\in SI(\Lambda)\) exactly when there are coefficients \(r_i\ge0\) such that \(u=\sum_{i\in I}r_i\lambda_i\) and \(u\cdot\lambda_i\ge1\) for every \(i\). The paper uses this characterization in its inference procedures and computes possibly optimal alternatives in its experiments.
The regime is a large product platform with a common finite catalogue \(A\) and a standardized preference questionnaire. A type \(t\) is the user’s complete set \(\Lambda_t\) of reported pairwise comparisons, represented by their feature-difference vectors. Users with the same comparison set are indistinguishable for the inference task. A platform may have \(N\) users but only \(\tau\ll N\) recurring response profiles. The society is the rational-mass distribution \(\mu_t\) over those profiles, with \(\sum_t\mu_t=1\).
The continuous problem is: for each product \(a\in A\), find the fraction of society for whom \(a\) cannot be ruled out as a top choice under the paper’s input-rescaling-invariant relation; then return a product with the largest such fraction. Precisely, define
\[
P_t(A)=\{a\in A:\exists u\in SI(\Lambda_t)\text{ such that }u\cdot a\ge u\cdot b\text{ for every }b\in A\}
\]
and \(M(a)=\sum_{t:\,a\in P_t(A)}\mu_t\). The instance gives the rational feature vectors in \(A\), the rational comparison vectors \(\Lambda_t\), and the binary-rational masses. A solution is the exact rational value \(M(a)\) for every \(a\), together with a maximizer of \(M\).
This is computable by the result the paper actually uses. For each type \(t\) and product \(a\), test feasibility of the linear system with variables \(u,r_i\):
\[
u=\sum_i r_i\lambda_i,\quad r_i\ge0,\quad
u\cdot\lambda_i\ge1\ \forall i,\quad
u\cdot(a-b)\ge0\ \forall b\in A.
\]
Corollary 10 makes this test equivalent to \(a\in P_t(A)\). Then sum the masses of the feasible types and maximize over \(A\). This takes \(O(\tau|A|)\) linear-program feasibility tests, with size polynomial in the feature dimension, the input description of the types and catalogue, and the rational bit lengths. I expect this mirror to be tractable, or Class A: high multiplicity lets the platform process each complete profile type once and weight its result by its population mass.
The connection to the paper is that it keeps the authors’ input-rescaling-invariant preference model and their possibly-optimality operator intact, then asks a plausible population-level recommendation question. It continuizes the users, not the products or the feature space. Its scope is the input-scaling characterization and the possibly-optimal alternatives built from it; it does not attempt to mirror the paper’s feature-rescaling variants, undominated-set computations, or imprecise-probability discussion.
The weakest point is that maximizing the mass for whom an item is *possibly* optimal is a new collective recommendation objective, not one the authors formulate. Those masses can overlap across products, so \(M(a)\) measures plausible recommendation reach, not predicted choice share. The case is strongest when a platform genuinely needs one common recommendation for many users: the individual inference and optimality notion come directly from the paper, while the population distribution makes the deployment question a continuous one.
The strongest objection is that the proposed score \(M(a)\) does not measure how many users would choose \(a\). It counts each type whenever \(a\) is *possibly* optimal, and those possibility sets can overlap heavily. A platform that wants one common recommendation might therefore rank products by an ad hoc notion of plausible reach, not by a collective preference represented in the paper. In the paper’s ridesharing setting, the available matches may also be user-specific, so a common catalogue cannot be assumed there.
That objection does not defeat the anchor. A standardized product catalogue and a finite questionnaire make repeated comparison profiles a plausible high-multiplicity regime; \(\Lambda_t\) is complete for the inference task the paper studies. Nor does the paper lack a computational anchor: Theorem 9 and Corollary 10 characterize the input-rescaling-invariant relation, and Section 5 uses that characterization for computation. This is not an existing continuous-population treatment.
The better versions of the mirror also survive the objection to \(M(a)\). A platform could measure the mass for whom a product is *guaranteed* to be optimal, or aggregate the types’ cautious pairwise comparisons to choose a common product. Those objectives are not stated in the paper, but each gives a coherent population-level recommendation question using its preference model. Calling them too easy, or saying they only batch independent computations, would not show that the questions are unworthy under this programme’s criteria.
So the negative case is weak. The proposed \(M(a)\) needs a clearer interpretation as a recommendation objective, but I cannot show that no plausible, author-recognizable continuous mirror exists. The mass-POS anchor survives.
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.