| paper | PeerNomination: Relaxing Exactness for Increased Accuracy in Peer Selection |
| authors | Nicholas Mattei, P. Turrini, Stanislav Zhydkov |
| venue | IJCAI 2020 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's only numbered results are strategyproofness and monotonicity propositions, neither of which asserts an algorithm, complexity bound, formulation used computationally, or hardness result. A coherent finite-type population model can be proposed, but the quota-calibration task is an added performance-analysis problem rather than a continuous analogue of a named computational result. Thus the computational-character gate fails.
fails bit a — no named computational result to mirror
The candidate mirror covers the peer-nomination quota, majority rule, expected selected mass, recall, and type-level analogues of the two structural properties; it leaves the Mallows experiments, empirical comparisons, and individual finite-population behavior outside the mirror.
The strongest honest case is a real but modest one: this paper admits a continuous-population mirror for its peer-nomination mechanism, but it does not contain the kind of named complexity result that ChoCo ideally wants. In the supplied text there is no numbered theorem, lemma, proposition, or corollary asserting NP-hardness, membership in \(P\), fixed-parameter tractability, or similar. The only numbered results are Proposition 1 and Proposition 2, concerning strategyproofness and monotonicity. Thus this cannot be presented as a hardness-dissolution result.
A plausible regime is a large online course or reviewing platform with \(N\) agents, \(N\gg m\), where \(m\) is fixed and \(k=\kappa N\) for a fixed target fraction \(\kappa\). Agents fall into finitely many complete types \(T\). A type records the agent’s ground-truth quality class, review-error or reporting behaviour, and assignment behaviour. Agents of the same type are interchangeable for everything the mechanism uses. The population is a mass vector \(\mu\), with \(\mu_t\) the fraction of agents of type \(t\).
The \(m\)-regular review graph is represented by its type-level limiting law: for each target type \(t\), let \(P_t(y)\) be the probability that a randomly selected reviewer places that target in position \(y\in\{1,\ldots,m\}\). This law is induced by \(\mu\), the assignment process, and the type-conditioned reporting kernels. It is the natural high-multiplicity limit of the paper’s uniformly sampled \(m\)-regular assignments.
For quota \(q=\kappa m+\varepsilon\), define the probability that a type-\(t\) agent is nominated in one review pool by \(a_t(q)=\sum_{y=1}^{\lfloor q\rfloor}P_t(y)+(q-\lfloor q\rfloor)P_t(\lfloor q\rfloor+1)\). Under the paper’s independent-review approximation, the acceptance probability is \(p_t(q)=\sum_{i=\lceil m/2\rceil}^{m}{m\choose i}a_t(q)^i(1-a_t(q))^{m-i}\). The selected mass of type \(t\) is then \(\nu_t=\mu_t p_t(q)\).
Let \(G\subseteq T\) denote the true top-\(\kappa\) mass, with boundary randomisation if necessary. The expected selected mass and expected recall are respectively \(S(q)=\sum_t\nu_t\) and \(R(q)=\kappa^{-1}\sum_{t\in G}\nu_t\). Notice that individuals still receive integral outcomes—selected or not. The fractional quantities are population masses and type averages, not divisible awards.
My lead anchor is Proposition 2, proved in this paper:
“The mechanism is monotonic, i.e., if a reviewer increases their ranking of an agent, that agent’s probability of selection is not decreased.”
The paper proves this by considering the three possible movements of an agent in a reviewer’s ranking: remaining a certain nominee or non-nominee, moving from fractional to certain nomination, or moving from non-nomination to fractional nomination. In every case the nomination probability, and hence the final selection probability, does not decrease.
The corresponding continuous problem is Calibrated Continuous Peer Nomination.
An instance consists of a finite type set \(T\), mass vector \(\mu\), target fraction \(\kappa\), fixed review degree \(m\), type-level review laws \(P_t\), a true top-\(\kappa\) set \(G\), and a tolerance \(\delta\geq0\). The decision variable is an ex-ante quota \(q\in[0,m]\), equivalently a slack value \(\varepsilon=q-\kappa m\). The task is to choose \(q\) and return the selected-mass vector \(\nu\) maximizing expected recall \(R(q)\), subject to \(|S(q)-\kappa|\leq\delta\). For \(\delta=0\), the requirement is exact expected mass; if no such quota exists, the instance is infeasible.
This is recognisably the authors’ problem: it retains their nomination quota, fractional nominee, majority threshold, slack parameter, and recall objective. The continuous change is only that \(N\) agents with type frequencies approaching \(\mu\) are represented by masses. The finite hypergeometric calculations become the limiting type-level probabilities \(P_t\).
I would expect this problem to be Class A in the intended regime. With fixed \(m\) and explicitly represented finite type laws, the acceptance probabilities are computable by finite sums. Moreover, \(a_t(q)\), \(p_t(q)\), and \(S(q)\) are nondecreasing in \(q\), so quota calibration can be performed by monotone search to any desired precision. If \(m\) is variable and the review laws are given succinctly, enumerating local review configurations may instead cost \(|T|^m\); the precise parameterised complexity would be a worthwhile follow-up.
A secondary, weaker anchor is Proposition 1, also asserted in this paper:
“The mechanism is strategyproof, i.e., no agent can affect their chances of selection using any strategy.”
Its continuous counterpart is Impartial Continuous Peer Nomination. Given the same population data, find a quota \(q\) and induced acceptance kernel satisfying the expected-mass constraint while maximising recall, with the additional requirement that for every individual agent \(x\), changing \(x\)’s own submitted reviews leaves \(x\)’s selection probability unchanged. The continuous \(\mathrm{PeerNomination}\) rule satisfies this because an agent’s own report is not used to nominate that agent.
This second mirror must be stated carefully. If “deviation” means that a positive-mass block of one type jointly changes its reporting kernel, Proposition 1 no longer directly applies: such a block can alter the reviews received by other agents. The faithful analogue is an individual deviation inside a high-multiplicity population, with each agent still having a finite review panel. In an atomless model, this is not merely a mass perturbation; it is a micro-level report deviation whose selection probability remains well defined.
The continuous mirror therefore covers the paper’s core mechanism and its two named theoretical properties, but not its empirical comparisons, Mallows-model simulations, or cited results about other mechanisms. Its weakest point is also clear: Proposition 2 is a structural property, not a computational complexity theorem, and the resulting calibration problem may look like a continuous restatement of the paper’s own expectation calculations rather than a new computational challenge. Proposition 1 is weaker still because individual non-pivotality can become nearly vacuous in a continuum.
So the positive verdict is: a sensible high-multiplicity mirror exists, and it yields a natural tractable problem of quota calibration and type-mass selection. But this paper is not a strong ChoCo candidate for the programme’s central hardness question, because it supplies no named discrete hardness result whose fate under continuization can be studied.
The negative case begins with a serious absence: this paper contains no named computational result to continuize. Its only numbered results are Proposition 1, strategyproofness, and Proposition 2, monotonicity. Neither asserts a complexity bound, an algorithmic optimization theorem, or a hardness result. The paper studies a mechanism and its statistical accuracy, not a computational problem whose discrete-versus-continuous complexity could be compared.
Proposition 2 does not rescue the case. Its natural continuous translation is simply: for a tagged agent, moving that agent upward in one reviewer’s ranking cannot decrease its selection probability. The paper’s three-case proof applies unchanged. The proposed “Calibrated Continuous Peer Nomination” adds a new optimization problem—choose \(q\) to maximize recall subject to an expected-size constraint—that Proposition 2 neither states nor solves. The authors treat \(\varepsilon\) as an input parameter, not as a computational decision variable.
Even granting that new problem, it is not a substantive continuization. Once the type-level laws \(P_t\) are supplied, \(a_t(q)\), \(p_t(q)\), and \(S(q)\) are finite sums and quota calibration is a one-dimensional monotone search. The population has disappeared only from the notation: the calculation is an expected-performance formula for a finite local mechanism. It does not create a mass-transfer problem, a separation problem, or any other computational structure of the kind ChoCo is designed to expose. If the laws \(P_t\) are not supplied, then deriving them requires the reviewer graph, its correlations, and the report-generation process—the discrete combinatorial object has merely been hidden behind an oracle.
There is also a genuine high-multiplicity problem. In the paper, an agent is identified by a position in a total ground-truth ranking and by the named agents in their review pool. As \(n\) grows, preserving that object requires distinguishing essentially every rank and often every local relation; the number of complete types therefore grows with \(n\). A finite type space is possible only after replacing the paper’s strict individual ranking by a latent-quality model with tied quality classes, random tie-breaking, or type-conditioned ranking kernels. That may be a sensible new peer-review model, but it is no longer the paper’s ground-truth identification problem.
The strongest repair is the proponent’s: a large exchangeable platform with finitely many latent quality and reporting types, a random sparse review graph, and a limiting local law. But with \(m\) fixed, each agent still receives only \(m\) reviews. Continuization then gives a law-of-large-numbers average of independent finite-neighbourhood experiments; it does not make the peer-selection mechanism itself continuous in any algorithmically meaningful sense. If correlations in the review graph matter, the marginal \(P_t(y)\) is insufficient and one must retain a joint local-network law. That is a mean-field analysis of a random graph, not a continuous-population computational problem.
Proposition 1 is even less promising. Impartiality is an individual identity property: agent \(x\)'s report is not among the reports used to select \(x\). In a genuine mass-only model, one agent has measure zero, so the property becomes automatic and vacuous. If a positive-mass type changes its reporting kernel, that is a coalition deviation and can alter the reports received by members of the same type; Proposition 1 says nothing about it. One can restore a tagged individual through a Palm-style random-graph model, but then the relevant proof is again the original local graph argument, with the continuum supplying only background frequencies.
The proponent also replaces the paper’s random selected set and individual top-\(k\) accuracy by expected selected masses such as \(\nu_t=\mu_t p_t(q)\). That is a reasonable statistical performance model, but it changes the object being studied: fluctuations, correlations, exact-set behavior, and identity-level false positives are discarded. The resulting question may be useful for analysing a large reviewing platform, yet it is not a continuous computational mirror of either proposition.
This negative case is not a proof that no interesting mean-field peer-review model could ever be written. The finite-type stochastic model is coherent, and someone interested in asymptotic accuracy might reasonably study it. The stronger conclusion is narrower: this paper offers no computational theorem for ChoCo to continuize, and its two named propositions either survive verbatim as local facts or become vacuous when identities are removed. The proposed calibration problem is an invented, elementary performance-analysis problem rather than a worthwhile continuous-computational mirror of the paper.
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.