| paper | d4-conf-ijcai-2017-0661 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Proposition 1 is a computational result, but its proposed analogue samples a finite panel from a pool rather than making population mass act in the elimination process. The paper’s rule still operates on individual voters in ordered roles, so the proposal changes the problem instead of giving it a continuous-population mirror.
fails bit b-changes — the continuum limit changes the question
The pool supplies only a finite panel; the elimination remains over individual roles, and positive-probability reachability uses only the support of μ.
fatal: True
The proposal addresses only the positive-probability question in Proposition 1 as a sampled-panel extension; it leaves the communication bounds, axiomatic results, and Borda-optimal sequence analysis untouched.
The strongest mirror I see is for the randomized rule’s winner-support problem. It treats a very large pool of potential participants as a distribution over rankings, then asks whether the paper’s randomized sequential elimination rule can elect a specified candidate with positive probability.
Concretely, let \(C\) be a finite candidate set with \(m\) candidates, and let \(T\subseteq\mathcal{L}(C)\) be the listed support of a population distribution \(\mu\), with each \(\mu_t>0\) rational and \(\sum_{t\in T}\mu_t=1\). Interpret the society as a nonatomic pool in which fraction \(\mu_t\) has ranking \(t\). For \(n<m\), draw \(n\) distinct participants from that pool, assign them uniformly to the \(n\) placeholders, and run the paper’s pattern \(\pi=(1,2,\ldots,n,n,\ldots,n)\), of length \(m-1\).
Call the resulting decision problem Population-SER Support: given \(C,T,\mu,n\), and target \(w\), is the probability that \(w\) wins positive? A yes-solution can be given as a sampled type profile \((t_1,\ldots,t_n)\in T^n\) and a permutation of the placeholders for which \(w\) wins. Equivalently, the probability being tested is
\[ P_w(\mu)= \sum_{(t_1,\ldots,t_n)\in T^n} \left(\prod_{i=1}^{n}\mu_{t_i}\right) \frac{\left|\left\{\sigma\in S_n: F_{\sigma\circ\pi}(t_1,\ldots,t_n)=w\right\}\right|}{n!}. \]
The input masses define how likely each profile is; the decision asks whether \(P_w(\mu)>0\).
This has a plausible regime: a large public platform or civic process draws a relatively small panel from a much larger pool of participants, and the panel uses a low-communication elimination rule to choose among many options. The panelists may share a modest number \(\tau=|T|\) of complete preference types, even when the pool itself is enormous. The type is the entire ranking relevant to this rule; mass is the fraction of the pool holding it. The decision variable is the assignment of sampled types to roles, and the objective is winner reachability under the sampling and role randomization. The paper already studies a randomized, ex-ante anonymous rule and explicitly has low-stakes app-based choice in view, so this keeps its mechanism and computational question recognizable.
My anchor is Proposition 1, proved in this paper by a reduction from 3SAT. It states that, when \(m>n\) and \(\pi=(1,2,\ldots,n,n,\ldots)\), deciding whether a candidate \(w\) has nonzero probability of winning under \(\hat F_\pi\) is NP-complete. In the paper, the probability is over uniformly assigning the fixed finite electorate to the placeholders. Population-SER Support asks the corresponding reachability question when the panel’s rankings come from a continuous population distribution.
I would provisionally expect Population-SER Support to be hard for continuum-specific reasons, rather than claim that Proposition 1’s hardness transfers. The finite-profile problem and the population-sampling problem differ: repeated type draws are possible, and the original theorem does not establish hardness for that distributional input. A reduction for the new problem is needed. Further questions include whether the support problem is NP-complete, whether it is tractable or fixed-parameter tractable when \(\tau\) is small, and the complexity of computing \(P_w(\mu)\) exactly.
The scope here is deliberately narrow: it mirrors Proposition 1’s randomized SER support question, not the paper’s axiomatic results, deterministic communication bounds, or Borda-optimal sequence analysis. The mirror is not a claim that the paper’s original electorate was already a continuum.
The weak point is that the proposed population is sampled to form the panel; the rule does not operate directly on all the population’s mass. That makes this a credible extension of the paper’s randomized mechanism, but a less direct high-multiplicity version of its fixed-electorate theorem. Also, the positive-probability decision depends only on which types have positive mass, not on their precise proportions. Those limits are why I would treat this as a promising, qualified mirror rather than a clean hardness transfer.
Proposition 1 is a genuine computational anchor, so I would not dismiss it for lack of a result. The difficulty is that the problem it studies has no aggregate operation: a fixed set of voters occupies a finite sequence of roles, and each turn uses one person’s ranking to eliminate one candidate. Randomizing the assignment of those voters to placeholders makes the rule anonymous ex ante, but it does not make the voters a mass.
In the proposed mirror, \(\mu\) supplies a distribution for drawing a finite panel. For the positive-probability question, every nonzero term in \(P_w(\mu)\) is positive, so
\[ P_w(\mu)>0 \quad\Longleftrightarrow\quad \exists (t_1,\ldots,t_n)\in T^n,\ \exists \sigma\in S_n: F_{\sigma\circ\pi}(t_1,\ldots,t_n)=w. \]
The exact proportions disappear; only the support matters. This is a reachability problem over possible finite panels. It changes Proposition 1’s input, since repeated types are now allowed, but it does not gain a computational object from treating voters as mass.
The strongest repair is to ask for the exact probability \(P_w(\mu)\), or to optimize expected Borda score under \(\mu\). That would use the proportions and could be a useful question about selecting a panel from a large pool. But the pool still does not participate in the rule: a finite panel does. That makes the continuous distribution a sampling model around the election, rather than a continuous electorate whose mass acts in it. A plausible citywide platform scenario is therefore a new delegated-panel model, not a high-multiplicity version of the paper’s small group choosing together.
A direct mass version has a more basic problem. SER needs an ordered sequence of individual vetoes. Type frequencies do not say which type acts at each turn; choosing a type randomly at each turn returns to finite sampling. Treating all members of a type as acting together requires a new aggregation rule, since a fractional amount of a voter cannot eliminate a fractional candidate. If the voter and candidate counts both grow, the outcome still depends on the type at each single turn; replacing the roster by frequencies loses that order. Preserving the turn-by-turn roster keeps the discrete instance rather than producing a continuous mirror.
So the negative case is strongest as a scope argument: the paper’s defining computation is over finite roles and indivisible eliminations, and its natural large-pool adaptation puts the continuum upstream of a finite electorate. It is not airtight. Exact probability computation for sampled panels could be worth studying, and the authors might recognize that extension. I do not see, however, a natural population-mass version of the paper’s sequential rule that retains its defining operation.
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.