| paper | d4-conf-ijcai-2017-0854 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a candidate set \(C\), a finite support \(T\) of complete score vectors \(x_t\in\mathbb{Q}_{\ge 0}^{C}\), and rational masses \(\mu_t>0\) summing to \(1\), find a direction \(e\in\mathbb{R}^{T}\) with \(\sum_{t\in T}\mu_t e_t^2=1\) minimizing \(\sum_{c\in C}\sum_{t\in T}\mu_t\bigl(x_{ct}-a_c(e)e_t\bigr)^2\), where \(a_c(e)=\sum_{t\in T}\mu_t x_{ct}e_t\); return a minimizing direction and its induced aggregate scores.
Treat each complete score vector as a type carrying mass \(\mu_t\). Choose a unit direction in the mass-weighted inner product; each candidate’s aggregate score is its projection coefficient, and the objective is total mass-weighted squared projection error. A weighted leading-eigenvector computation gives the optimizer.
The spectral optimization has close prior art in functional principal component analysis, which limits the mirror’s novelty but does not undermine its population-mass formulation.
fatal: False
The mirror covers Theorem 2’s optimal projection direction and induced aggregate scores; it leaves Theorem 3’s signal-to-noise identity, the consistency discussion, and the empirical application claims aside.
The strongest anchor is Theorem 2, proved in this paper. It says that for a score matrix \(X\), the eigenvector of \(Z=X^{T}X\) corresponding to its largest eigenvalue gives the direction whose projections minimize the total squared distance between the candidates’ original score vectors and their projections. The paper does not state a standard complexity classification such as “in P,” and it has no named hardness result; Theorem 2 is its clearest named computational result.
A natural mirror is \(\textsc{Spectral Score Aggregation}_{\infty}\). An instance has a candidate set \(C\), and a society supported on \(\tau\) types. Type \(t\) is an agent’s complete score vector \(x_t=(x_{ct})_{c\in C}\), with scores on the common scale assumed by the paper. Its mass \(\mu_t\) is a nonnegative binary rational, and \(\sum_t\mu_t=1\). The question is to find a unit direction \(e\), with \(\sum_t\mu_t e_t^2=1\), and the resulting aggregate scores
\[
a_c(e)=\sum_t\mu_t x_{ct}e_t
\]
that minimize
\[
\sum_{c\in C}\sum_t\mu_t\bigl(x_{ct}-a_c(e)e_t\bigr)^2.
\]
A solution is any minimizing direction and its induced candidate scores; the direction may be chosen nonnegative. This is the paper’s projection objective over a society whose agents have been grouped by identical score vectors.
The mirror has a plausible high-multiplicity setting: a very large panel rating the same small slate of candidates on a discrete scale, such as a fixed set of products rated in half-star increments. Agents with the same complete rating vector are one type. With the slate and rating scale fixed, the number of possible types is bounded while the number of panelists can grow; the paper’s own rating example makes this interpretation particularly natural. The assumption that agents’ scores are commensurable is inherited directly from the paper.
The continuous problem reduces to a \(\tau\times\tau\) eigenproblem. Form
\[
B_{tt'}=\sqrt{\mu_t\mu_{t'}}\sum_{c\in C}x_{ct}x_{ct'}.
\]
A leading eigenvector \(u\) yields \(e_t=u_t/\sqrt{\mu_t}\), and hence the optimal aggregate scores. Thus I expect this mirror to be tractable: the optimization is solved by a leading eigenpair, with computation depending on \(m\), \(\tau\), and the input bit lengths. For an empirical society with \(n\) agents and proportions \(\mu_t\), this recovers the finite problem’s optimal direction after grouping identical columns; the aggregate scores differ only by a positive normalization factor. In that regime, the continuum is a high-multiplicity relaxation of the same computational question.
This case covers Theorem 2 and the spectral aggregation problem it certifies. It does not claim a continuous mirror for every discussion or application in the paper, or use Theorem 3’s separate consistency-indicator formula as another anchor. The mirror also prompts questions about how stable the resulting candidate ranking is under small changes in type masses, how tied leading eigenvalues affect that ranking, and whether the paper’s signal-to-noise indicator extends directly to this weighted setting.
The soft spot is that this is not a case where discrete hardness disappears: the paper already gives a spectral method for the finite-agent problem. The gain is the natural mass-based formulation and a computation parameterized by support size \(\tau\), rather than by a list of all \(n\) agents. That makes this a credible, narrow mirror of the authors’ actual objective, though a less dramatic example for a programme centered on where continuization changes the complexity landscape.
The strongest negative case is that the proposed mirror is weighted principal component analysis in population notation. Writing each candidate’s scores as a function \(f_c(t)=x_{ct}\) over types, the objective is
\[
\min_{\|e\|_{L^2(\mu)}=1}\sum_{c\in C}\|f_c-\langle f_c,e\rangle e\|_{L^2(\mu)}^2.
\]
Its covariance operator has rank at most \(m\), and the leading eigenfunction gives the solution. Functional PCA has already formulated rank-one approximation this way and given computational methods for it.[Huang, Shen, and Buja](https://arxiv.org/abs/0807.4862) That makes the mirror look like a direct translation of familiar spectral machinery, rather than a new complexity problem.
But that does not defeat the anchor under ChoCo’s rules: an answer from outside the literature does not make a well-posed mirror unworthwhile. Nor is the paper itself already a continuous-population model. Theorem 2 and Algorithm SPECTRAL provide a named optimization task and a constructive solution; the proposed distribution over complete score vectors is coherent, and a large panel rating a fixed slate is a plausible high-multiplicity setting. The objection that “agents are coordinates” also fails here: the score vector is a complete type, and the objective does not track individual identities.
So my honest case against is weak. The mirror may offer little algorithmic novelty, but I cannot turn that into a fundamental reason to reject it without relying on an objection the programme explicitly rules out. Theorem 2’s 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.