| paper | d4-conf-ijcai-2016-0669 |
| 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 · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 1
Given a finite support \(T\) of learner types, rational masses \(\mu_t\) summing to \(1\), and for each type \(t\) a nonempty feasible polyhedron \(G_t=\{w\in\mathbb{R}^n: w\cdot\lambda\ge 1\ \forall\lambda\in\Lambda_t,\; w\cdot\theta\ge 0\ \forall\theta\in\Theta_t\}\), where the complete inputs \(\Lambda_t,\Theta_t\) have rational coordinates, determine which types have exactly one rescale-optimal vector, return that vector for each such type, and compute their total mass \(\rho\). Here \(u\) is rescale-optimal in \(G_t\) if some \(\sigma\in\mathbb{R}_{++}^n\) makes \(u\) minimize \(\|\sigma\odot w\|_2\) over \(w\in G_t\).
The society is a distribution \(\mu\) over complete preference-input profiles. For each supported type \(t\), compute an indicator \(z_t\) for whether \(G_t\) has a unique rescale-optimal vector and return that vector when it exists; output \(\rho=\sum_{t\in T}\mu_t z_t\). Applying Corollary 1 takes at most \(O(\tau(n+1))\) linear-program calls, with polynomial dependence on the profile encoding lengths.
The computation runs independently on each profile, so the population affects only the final prevalence tally; the paper offers little evidence that complete profiles recur at scale or that this tally informs a product decision.
fatal: False
The mirror covers Corollary 1's uniqueness test and the vector it returns, aggregated across supported types. It leaves the paper's general preference-inference computation, other characterizations, and benchmark results outside the claim.
The strongest positive case is narrow: make the users of a preference learner the continuous population, and ask how much of that population has a preference model that is unchanged by feature rescaling.
My anchor is Corollary 1, proved in this paper; the authors refer readers to their 2016 extended version for some proof details. For \(G=G(\Lambda,\Theta)\), choose any \(z\in G\), and construct \(y\) coordinate by coordinate: if \(z(j)=0\), set \(y(j)=0\); if \(z(j)>0\), set \(y(j)=\inf\{w(j):w\in G,\ w(j)\ge0\}\); and if \(z(j)<0\), set \(y(j)=\sup\{w(j):w\in G,\ w(j)\le0\}\). The corollary says that if \(y\in G\), then \(y\) is the unique rescale-optimal element of \(G\), and that \(G\) has a unique rescale-optimal element if and only if \(y\in G\). The paper explains that this gives an algorithm using at most \(n+1\) linear-programming calls, hence polynomial time. When the unique vector is \(u\), it determines the user’s preference relation across every rescaling: \(a\) is preferred to \(b\) exactly when \(u\cdot(a-b)>0\).
Here is the continuous problem I would hand to a prover: Unique-Rescale Mass. There is a common \(n\)-feature space and a finite support \(T\) of learner types. A type \(t\) consists of the learner’s complete finite set of pairwise preference inputs \(\Lambda_t\) and feature constraints \(\Theta_t\); take their coordinates to be binary rationals. Its feasible polyhedron is \(G_t=\{w\in\mathbb R^n: w\cdot\lambda\ge1\ \forall\lambda\in\Lambda_t,\ w\cdot\theta\ge0\ \forall\theta\in\Theta_t\}\), assumed nonempty. The society is given by rational masses \(\mu_t\ge0\) summing to \(1\). A vector \(u\) is rescale-optimal for type \(t\) if some strictly positive coordinatewise scaling \(\sigma\in\mathbb R_{++}^n\) makes \(u\) a minimum-\(\|\sigma\odot w\|_2\) point of \(G_t\).
The task is to return the set \(S\) of types whose polyhedron has exactly one rescale-optimal vector, that vector \(u_t\) for each \(t\in S\), and the total mass \(\rho=\sum_{t\in S}\mu_t\). This reports what fraction of the society has a weight vector—and therefore an inferred preference relation—that survives every choice of feature scaling. It is a classification and aggregation task, not an optimization over the population.
A plausible regime is a large recommender or ride-sharing service with a shared feature schema and standardized comparison menus. Many users may submit the same complete set of comparisons and constraints, while the service has millions of users but comparatively few distinct profiles. A type here is that full learner input, not an individual comparison; its mass is the fraction of users with that input. This is a sensible high-multiplicity regime when feedback patterns recur. The paper’s ride-sharing experiments, which process multiple users’ preference profiles, make cohort reporting a recognizable extension of its application.
I expect this mirror to be tractable: run Corollary 1’s algorithm for each supported type, then sum the masses for the types with a unique vector. That takes at most \(O(\tau(n+1))\) LP calls, polynomial in the support size, feature dimension, profile encoding lengths, and mass bit lengths. The finite election analogue with \(N\) users has \(\mu_t=n_t/N\); the continuous version asks for the corresponding exact cohort share without one-person granularity. This case covers Corollary 1’s uniqueness question. It does not claim that the paper’s full preference-inference computation or its benchmark results have the same population algorithm. The supplied paper has no named hardness result to anchor a transfer question.
The natural follow-on is to compute, for a pair \(a,b\), what mass robustly prefers \(a\) to \(b\) even when a type has several rescale-optimal vectors. That goes beyond this anchor. The soft spot in the present case is the shift from inferring one user’s relation to reporting a population statistic, together with the possibility that complete feedback profiles are rarely repeated. The mirror is strongest where the platform’s interaction format creates genuinely recurring profiles; it is a narrow cohort extension, not a claim that the paper itself studies a continuous society.
Corollary 1 is a real computational anchor: it gives a polynomial-time LP procedure for deciding whether one learner’s feasible polyhedron has a unique rescale-optimal vector. So the negative case cannot rest on the paper lacking a computational result.
The difficulty is making that result a population problem without changing what it computes. A type would have to include the learner’s complete input, \((\Lambda_t,\Theta_t)\). That is a faithful high-multiplicity grouping: learners with identical inputs are indistinguishable for this algorithm. But the paper’s objects are individual feedback sets, with sizes and contents that vary by user. Its 13 ride-sharing benchmarks show several such users, not recurring cohorts of identical profiles. A platform with a fixed, restricted feedback menu could create repeated profiles, but that is a narrow regime, and the paper gives little evidence that full feedback profiles recur at the scale the proposal needs.
Even granting that regime, “Unique-Rescale Mass” runs Corollary 1 independently on each supported profile, then adds the corresponding masses. Its computational work is just \(\tau\) single-profile calls plus a weighted sum. Duplicating a learner leaves that learner’s vector unchanged; population size does not enter the feasible region or create a shared decision. The mass records the prevalence of an existing per-user property. That may be useful platform reporting, but it does not expose a population-dependent computational question of the sort the programme is designed to chart.
A stronger version would ask what fraction of users robustly prefer \(a\) to \(b\), including users whose polyhedra have several rescale-optimal vectors. That is a more useful cohort statistic than counting only uniquely determined users. Yet it still applies the per-user inference test to each profile and totals the qualifying masses. If instead the proposal pools everyone’s comparison inputs to infer one collective preference relation, it changes the target: conflicting users can make the pooled input inconsistent, while the paper’s method assumes consistent inputs and infers each user’s utility separately. Designing a rule for resolving that disagreement would be a new collective-preference problem, not a continuous mirror of Corollary 1.
This is not an airtight case that no application could make cohort reporting valuable. Repeated profiles and a product decision driven by their prevalence are plausible. The negative case is that, on the paper’s own model, the population supplies weights for reporting results rather than a new computational object; making it substantive appears to require adding a collective decision rule that the paper does not study.
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.