| paper | d4-conf-aaai-2024-0257 |
| 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: \(\text{Polynomial-time solvable}\) · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Fix a finite-support \(K\)-nary GBT root law and positive rational prior variance \(\sigma^2\). An instance gives \(m\) alternatives, a positive integer population scale \(N\), report types \(t=(a_t,b_t,r_t)\) with rational masses \(\mu_t\) summing to \(1\), and rational \(\varepsilon>0\). Output a rational vector within \(\ell_2\)-distance \(\varepsilon\) of the minimizer of \(J(\theta)=\frac{1}{2\sigma^2}\sum_{a=1}^m\theta_a^2+N\sum_{t\in T}\mu_t[\Phi_f(\theta_{a_t}-\theta_{b_t})-r_t(\theta_{a_t}-\theta_{b_t})]\).
A society of contributors represented by report types \(t=(a,b,r)\) and masses \(\mu_t\); compute the MAP score vector minimizing the prior penalty plus the mass-weighted GBT comparison loss, scaled by \(N\).
The paper formalizes at most one comparison per pair, while the mirror counts repeated user reports separately; the application makes that extension plausible, but the paper does not analyze it.
fatal: False
The mirror covers MAP score computation supported by Proposition 2; it leaves the monotonicity, resilience, and statistical results unmirrored.
The strongest honest case is narrow: this paper has no named NP-hardness, \(P\), or parameterized-complexity theorem. Its best anchor is an algorithmic one.
Lead anchor: Proposition 2, proved in this paper. For every comparison matrix \(R\), the negative log-posterior \(L(\cdot\mid R)\) is \(1/\sigma^2\)-strongly convex. Therefore it has a unique minimizer, the MAP score vector \(\Theta^*_{f,\sigma^2}(R)\). The paper says this makes the estimator fast to compute with strongly convex optimization methods. Proposition 2 does not establish a polynomial bit-complexity bound, so the continuous question below would test whether that computational claim can be made precise in a high-multiplicity regime.
GBT-Report-Population-MAP. Fix a finite-support GBT root law \(f\), such as the paper’s \(K\)-nary model with fixed \(K\), and a positive rational prior variance \(\sigma^2\). An instance gives \(m\) alternatives, a positive integer \(N\), and a finite support \(T\) of report types \(t=(a_t,b_t,r_t)\), where a type records one paired judgment and its outcome. Each type has binary-rational mass \(\mu_t\geq 0\), with \(\sum_{t\in T}\mu_t=1\). The mass is the fraction of the reporting population that supplied that judgment; \(N\mu_t\) is its effective count. Given rational \(\varepsilon>0\), output a vector \(\hat\theta\in\mathbb R^m\) within \(\ell_2\)-distance \(\varepsilon\) of the unique minimizer of
\[ J(\theta)=\frac{1}{2\sigma^2}\sum_{a=1}^{m}\theta_a^2 +N\sum_{t\in T}\mu_t\left[ \Phi_f(\theta_{a_t}-\theta_{b_t}) -r_t(\theta_{a_t}-\theta_{b_t}) \right]. \]
For the discrete case where every \(N\mu_t\) is an integer, this is exactly the paper’s MAP objective for that multiset of reports, up to terms independent of \(\theta\). Fractional counts give the continuous relaxation. For fixed \(K\), there are at most \(K\binom{m}{2}\) single-judgment types, so a large reporting population can have support \(\tau\) far smaller than \(N\).
The regime I believe in is a comparison platform that assigns many contributors one pair of videos, candidates, or teams to judge. A report’s type is the pair and rating; its mass is the population share producing that report. With a fixed rating menu, \(N\) can be millions while the number of possible types is bounded by the number of alternative pairs times the rating levels. This uses contributors as the population and retains the paper’s underlying task: infer scores for alternatives from paired comparisons. The GBT rating distribution may be discrete; continuity here comes from population mass.
I expect this problem to be Class A, at least for a fixed finite-support root law with an efficient evaluation procedure for \(\Phi_f\). Its objective is a finite weighted sum over \(\tau\) types, and Proposition 2 supplies strong convexity and uniqueness. A prover would still need to establish an appropriate bit-complexity or approximation bound, including its dependence on \(N\), \(\sigma^2\), and the requested precision. The paper itself supplies no such bound.
The scope is score estimation and computation of the MAP estimator, anchored by Proposition 2. It does not turn the paper’s monotonicity or resilience results into complexity results, and I would not claim that it covers the whole paper. Further questions include how runtime depends on population scale and conditioning, whether the aggregate report distribution is a sufficient representation for other GBT tasks, and how the same model supports active selection of comparison pairs.
The soft spot is that the paper’s formal input is a comparison matrix with one value per compared pair, while this mirror treats repeated reports as separate observations and weights them by population mass. That fits the paper’s crowdsourced motivation and preserves its likelihood and score-estimation objective, but it is an extension of its formal input model. Also, “strongly convex” is not itself a polynomial-time theorem for arbitrary root laws. Those are real limits on the positive case: this is a credible continuous mirror of the paper’s MAP computation, not evidence that the paper proves a complexity separation or that every version is efficiently computable.
Proposition 2 is the strongest objection to a mirror, but it does not establish a computational complexity result. It proves strong convexity and uniqueness of the MAP estimate. The claim that the estimate is “fastly computable” by a strongly convex optimizer is not a bound in the input size, precision, or bit complexity. So the paper has no named complexity theorem whose result can be continuized.
The proposed report-population version is still worth taking seriously. If many contributors each submit one judgment, a type can be the assigned pair and its rating; repeated reports can be grouped by type. For integer \(N\mu_t\), the weighted objective recovers the likelihood objective for repeated observations. That is a plausible high-multiplicity regime, and I would not dismiss it on the ground that people have distinct identities.
The difficulty is that this makes the question a new weighted-estimation problem around a changed data model. The paper’s formal input has at most one comparison per pair; the mirror introduces repeated observations and makes contributors, rather than comparisons, the population. Once aggregated, the masses are just coefficients in a finite sum. With fixed finite rating support, there are at most \(O(Km^2)\) report types, and the objective and its derivatives can be evaluated from those types directly. There is no exponentially large domain or pricing problem for continuous optimization to unlock. A complexity analysis could be useful, but the likely story is standard finite-dimensional convex estimation, not a new computational-social-choice landscape.
Making each contributor’s full response history their type does not improve the fit much: under the paper’s independent-comparison likelihood, the objective depends on the aggregate comparison counts, not on which judgments came from the same user. Modeling user reliability or correlated reports could make user types matter, but then the result being mirrored is no longer Proposition 2’s model.
So the negative case is strongest as a case for low priority: the paper has no formal complexity result, and the most plausible population version appears to reduce to weighted convex estimation with a small explicit support. It is not airtight. The one-report-per-contributor regime is coherent, and formalizing approximation complexity there could yield a worthwhile answer. I cannot honestly rule out every useful mirror; the objection is that this paper gives little reason to expect one that advances ChoCo’s central complexity programme.
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.