| paper | d4-conf-wine-2022-0017 |
| 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: \(\alpha(\kappa)=0\) for every \(\kappa\in(0,1]\), under the stated feasibility conditions. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given finitely many types \(t=(r,o)\), rational masses \(\mu_t>0\) summing to \(1\), nomination densities \(\rho_{st}\in[0,1]\), and a cap \(\kappa\in(0,1]\), define \(d_t=\sum_s\mu_s\rho_{st}\). Compute quotas \(q_t\in[0,1]\) with \(0<\sum_t\mu_tq_t\le\kappa\) that maximize \(\min_{t:q_t>0}d_t\), subject to equal quotas for types sharing incoming class \(r\); \(o\) records outgoing nomination patterns.
A finite-type mass-selection model with per-capita incoming-density scores and a quota cap. Selection probabilities depend on incoming class and remain unchanged when an agent changes only its outgoing-pattern coordinate.
In the proponent’s version, equal inclusion probabilities within each type do not ensure impartiality if changing an agent’s outgoing report moves it to a type with a different quota; the repaired mirror must make quotas invariant to the outgoing-pattern coordinate.
fatal: False
The mirror covers Theorem 4’s cap-versus-minimum-indegree objective. It leaves Theorems 1–3 and the finite additive bound’s tightness open.
The best positive mirror I see is for dense, cohort-structured peer nomination: a very large organization or professional platform where agents fall into a small number of recurring role and nomination-pattern types. Each person in a type nominates at similar rates across the same target types. The relevant regime has \(n\) agents but only \(\tau\) types, with \(\tau\ll n\). The output is a share of each type selected, and nomination scores are per-capita densities. This is a natural population continuization, with the change from counts to densities forced by the large-population limit.
My lead anchor is Theorem 4, proved in this paper. It says that for every \(n\) and every \(k\in\{2,\ldots,n\}\), there is an impartial \(k\)-selection mechanism on all \(n\)-vertex directed graphs that is \(\bigl(\lfloor(n-2)/(k-1)\rfloor+1\bigr)\)-min-additive. Here a \(k\)-selection mechanism selects at most \(k\) vertices, and min-additivity bounds the difference between the graph’s maximum indegree and the minimum indegree of a selected vertex. The paper gives the mechanism: delete specified edges according to a fixed vertex order, then apply asymmetric plurality with runners-up. It is a constructive guarantee, not a classical NP-hardness or P classification.
Here is the continuous problem I would hand to a prover, Block-Continuum Impartial Min-Selection. An instance consists of a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), rational nomination densities \(\rho_{st}\in[0,1]\), and a cap \(\kappa\in(0,1]\). A type completely specifies the relevant role and nomination pattern. The density \(\rho_{st}\) describes nominations from type \(s\) into type \(t\); type \(t\)’s per-capita indegree is
\[
d_t=\sum_{s\in T}\mu_s\rho_{st}.
\]
The decision is a quota vector \(q_t\in[0,1]\), where \(q_t\) is the fraction of type \(t\) selected, with \(0<\sum_t\mu_tq_t\le\kappa\). Find an impartial rule that maximizes the minimum \(d_t\) among selected mass. A solution is an algorithm returning such quotas for each instance. Individual selection can be implemented by an exchangeable lottery within each type.
In the atomless model, changing one named agent’s outgoing nominations changes no type mass or nomination density. A rule that assigns the same inclusion probability to every member of a type therefore satisfies individual impartiality. The problem is tractable: compute the \(d_t\), select positive mass from a type of maximum \(d_t\), and the minimum selected density equals the population maximum. This takes polynomial time in \(\tau\) and the input bit length. The paper’s finite guarantee points in the same direction: with \(k=\lfloor\kappa n\rfloor\), Theorem 4 gives an unnormalized loss of \(O(1/\kappa)\), so the loss after dividing indegrees by \(n\) tends to zero. That supports the density objective, though the theorem alone does not ensure a positive limiting share of selected agents.
A useful second anchor is Theorem 3, also proved here. For \(n\ge3\), \(k\in[n]\), and maximum outdegree \(d\in[n-1]\), it says that any impartial \(k\)-selection mechanism on \(G_n(d)\) that is \(\alpha_1\)-median-additive must have
\[
\alpha_1\ge \tfrac12(1+\mathbf{1}(d\ge3)),
\]
and any such mechanism that is \(\alpha_2\)-mean-additive must have
\[
\alpha_2\ge
\frac{\lfloor(d+1)/2\rfloor}{\lfloor(d+1)/2\rfloor+1}.
\]
These are impossibility bounds on quality, not complexity-class results. Their continuous counterpart, Block-Continuum Impartial Median/Mean Selection, uses the same instance and asks whether an impartial quota rule can achieve the best possible selected median or mean of indegree densities under the mass cap. It can: select positive mass only from maximum-indegree types, giving both objectives zero density gap. In dense high-multiplicity regimes, the finite lower bounds are \(O(1)\) in counts and hence vanish when divided by \(n\). The predicted answer is tractable, with the finite impossibility not transferring as a positive density loss.
The scope is deliberately narrow: these questions mirror the paper’s impartial selection guarantees and impossibility bounds. They do not claim to continuize every result in the paper or to establish that its finite-graph mechanisms have already solved these quota problems. The paper has no named NP-hardness result; its useful anchors are constructive and impossibility results about mechanisms.
The weakest point is the nomination model. Actual nominations often name particular people, and many peer-selection settings are sparse: each agent nominates a few individuals. A small set of role-based nomination densities may discard precisely the identity-level structure that makes impartiality difficult. In the atomless model, an individual’s report has zero aggregate effect, so impartiality becomes much easier. I would sell this as a credible mirror for dense, repeated cohort nominations, not as a universal continuous version of peer selection. A valuable follow-up is to find where the answer changes as agents retain nonzero atom size, or as nominations become sparse.
I would not argue that there is no named result to mirror: Theorems 3 and 4 are real results about impartial mechanisms. But they do not classify computational complexity. Their substance is the tension between an individual’s outgoing nominations and that individual’s chance of selection. That tension is exactly what a population continuum tends to erase.
In the proposed block model, changing one person’s nominations changes no type-level density: that person has zero mass. The same holds in the stronger graphon version. A person is a point \(x\), and indegree density at \(y\) is \(d(y)=\int W(z,y)\,dz\). Changing the outgoing row \(W(x,\cdot)\) leaves every \(d(y)\) unchanged, because a single point contributes zero to the integral. If the outcome is a quota vector or a selected set considered up to measure zero, the change also cannot alter the person’s mass of selection. Impartiality has become automatic at the level the model observes.
That defeats the proposed Theorem 4 mirror, and its best repair. If a fixed positive share \(\kappa\) is selected, the theorem’s bound is \(O(1/\kappa)\) in counts, hence vanishes after normalizing indegrees by \(n\). The continuum can select the highest-density types directly. If only \(o(n)\) people are selected, the selected share vanishes, so there is no positive-mass selection outcome to optimize. In a sparse regime with bounded outdegree, normalized indegrees themselves vanish; in a dense regime, an individual’s effect on normalized scores vanishes. Neither regime retains the theorem’s finite-agent impartiality trade-off.
Theorem 3 runs into the same problem. Its median and mean lower bounds concern changes of constant size in *counts*. A quota model with a positive selected mass can instead sort the finitely many type densities and take the required mass from the top types; the capped version in the proponent’s statement is even easier, since it allows an arbitrarily small positive quota from a maximum-density type. Requiring an exact quota would fix that loophole, but leaves a weighted quantile or top-mass calculation. Those are coherent allocation questions, yet the impossibility phenomenon in Theorem 3 has disappeared because no single agent can move the aggregate scores that drive it.
One could keep the agents’ point identities and ask for a finite number of winners from a continuum, but that selects a measure-zero set, so mass-based quality objectives no longer express what the finite theorem measures. Or one could treat an entire positive-mass cohort as the strategic unit and require its selection to be independent of the cohort’s own nominations. That may be worth studying, but it replaces individual impartiality with a bloc-level axiom; it is a different problem unless the authors explicitly adopt that change.
So the strongest negative case is that both anchors either lose their defining constraint in the population limit or require changing the unit of agency. The case is not airtight: a simple quota-selection problem could still be useful in its own right, and a cohort-level model might interest the authors. But neither supplies a convincing continuous mirror of these theorems’ central contribution.
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.