| paper | d4-conf-wine-2014-0004 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 2 is a computational approximation result, but the proposed role-mass question keeps a finite population and exact individual deviations, making it a succinct finite-instance problem. In a mass-only limit, one person's report does not change the society distribution, so impartiality becomes vacuous and the theorem's defining strategic constraint does not transfer.
fails bit b-changes — the continuum limit changes the question
The masses only compress a finite blow-up: exact impartiality still depends on the identity-level finite mechanism, so the continuous society does not preserve the theorem's defining strategic condition.
fatal: True
The candidate covers only Theorem 2's slicing guarantee on role-template blow-ups; it leaves the permutation analysis and other graph instances outside that compressed model.
The best case is narrow: a high-multiplicity version of the paper’s single-winner impartial selection problem. Consider a large peer-recognition platform with a small number \(\tau\) of roles. Many agents share each role, and agents in a role nominate the same role classes in the baseline profile. The population is described by type masses \(\mu_t=n_t/N\), with \(N\gg\tau\). This is a plausible structured regime, though a narrow one.
My lead and sole anchor is Theorem 2, proved in this paper: for every \(\epsilon>0\), there is a constant \(M_\epsilon\), independent of the number of agents, such that if the largest in-degree \(\Delta^-\) is at least \(M_\epsilon\), the slicing mechanism is \((1-\epsilon)\)-optimal. The authors also state \(M_\epsilon=O(\epsilon^{-8})\). This is an approximation guarantee for a concrete randomized selection mechanism, not a complexity-classification theorem; the paper gives no named hardness result to anchor a hardness-transfer question. [Theorem 2 in the paper](https://perso.liris.cnrs.fr/nbousquet/impartialselection.pdf)
A precise mirror is Type-Mass Impartial Selection. An instance consists of a population scale \(N\), a finite type set \(T\), rational masses \(\mu_t>0\) summing to one with \(N\mu_t\in\mathbb{N}\), and a directed type template \(A\in\{0,1\}^{T\times T}\). There are \(N\mu_t\) agents of type \(t\); every type-\(s\) agent nominates every type-\(t\) agent when \(A_{st}=1\), except itself. A type-\(t\) agent then has in-degree \(d_t=N\sum_s\mu_sA_{st}-A_{tt}\), and \(\Delta=\max_t d_t\).
Given \(\epsilon\), the task is to construct one randomized selector on the full domain of \(N\)-agent nomination graphs. It must be exactly impartial: changing only agent \(i\)’s outgoing nominations cannot change the probability that \(i\) is selected. On the template instance, the same selector must admit a sampler that uses \((N,\mu,A)\) directly, without expanding the \(N\)-agent graph, and runs in time polynomial in \(\tau\), the input bit length \(L\), \(\log N\), and \(1/\epsilon\). Its expected winner in-degree must be at least \((1-\epsilon)\Delta\) whenever \(\Delta\ge M_\epsilon\). A solution gives the selector and sampler, plus proofs of impartiality and the guarantee. On a symmetric template instance, the output can be summarized by type probabilities \(q_t\), followed by a uniform draw among the \(N\mu_t\) agents of the chosen type; its expected degree is \(\sum_t q_t d_t\).
I expect the approximation part to be Class A: Theorem 2 already establishes the guarantee on every finite blow-up, and the slicing mechanism’s sampling and elimination steps look amenable to aggregation by type. The new computational question is whether that mechanism’s behavior can be sampled from the mass description in time polynomial in the support size and bit length, while retaining the exact impartiality condition for individual deviations. That compressed implementation is not proved by the paper. A positive answer would make the high-multiplicity input useful in its own right. For any template with positive incoming mass to some type, \(\Delta\) grows with \(N\), while the normalized popularity \(d_t/N\) approaches \(\sum_s\mu_s A_{st}\); the approximation ratio is unchanged by that rescaling.
The mirror covers only the paper’s near-optimal slicing result in a structured, many-agent regime. It does not claim that all arbitrary nomination graphs have a small type description, and it does not continuize outcomes or replace agents with anonymous mass points.
The weakest point is that type classes defined by role-level nomination patterns restrict the paper’s arbitrary directed graphs. More fundamentally, an atomless model makes one person’s report carry zero mass, which can make impartiality vacuous. This formulation keeps the population scale \(N\) and requires exact impartiality on the finite graph domain to preserve the strategic issue; for that reason, it is best understood as a type-mass high-multiplicity mirror, rather than a claim that the paper’s mechanism has a nontrivial atomless limit. The supporting case is that the population itself is represented by masses over a small set of complete roles, and the object being selected, the popularity objective, and the individual deviation condition remain the paper’s.
The slicing theorem is the strongest anchor, but its strategic condition is attached to an individual atom. The mechanism must select one named person, and impartiality compares that person’s selection probability before and after they change their own nominations. In a genuine continuum of anonymous role masses, one person’s report changes no mass. Any selector computed only from those masses therefore sees the same society after the deviation, and individual impartiality becomes automatic. The theorem’s distinctive constraint has disappeared.
The proposed repair retains a finite population scale \(N\) and exact deviations. That preserves the constraint, but it also preserves the \(1/N\) atom that the continuum was meant to remove. The input \((N,\mu,A)\) then describes a finite blow-up of a role graph: every member of one role nominates every member of certain other roles. Asking for a compressed sampler on those inputs is a coherent succinct-input problem, but the impartiality condition still belongs to the finite, identity-indexed mechanism. The type masses do not encode that condition; the requirement that the selector be defined on arbitrary graphs supplies it from outside the mass model.
A more ambitious mirror could use a directed graphon or richer types to represent arbitrary nomination patterns. That does not resolve the mismatch. If the representation identifies societies that differ on a measure-zero agent, it cannot preserve that agent’s deviation as a distinct event. If it retains pointwise identities and reports so that it can test every deviation, the input is no longer a finite-support population description; in general, it has returned to the individual-level graph. Treating a positive-mass role’s coordinated change as the strategic deviation would give a nontrivial mass-level question, but that is group strategyproofness, not the individual impartiality studied here.
The particular role-template scenario also suppresses much of the paper’s input structure: nominations are all-or-nothing between role classes, and members of each class have identical in-neighborhoods. That may describe a narrow platform, but the more faithful the type system becomes to arbitrary named nominations, the less it compresses. The proposed mirror can thus be made well-posed in either direction: keep the atom and ask for succinct execution, or remove it and obtain an atomless rule whose impartiality condition has lost its force. Neither gives a compelling continuous version of Theorem 2’s central problem.
This is not an airtight claim that compressed implementations of the slicing mechanism lack value. Such a project could be worthwhile on its own. The negative case is that its value would come from succinct representation of a finite strategic problem, while the continuous-population version that preserves the paper’s defining axiom either retains those finite atoms or makes the axiom vacuous.
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.