| paper | d4-conf-atal-2016-0079 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: All limits exist, and exact computation is polynomial-time solvable: \(O(m+\tau)\) arithmetic operations and \(O((m+\tau)L^2)\) bit operations for a standard explicit input encoding. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite rooted connector tree \(H\), a map \(h\) from supported voter types \(t\) to connectors, and rational masses \(\mu_t>0\) summing to \(1\), form, for each denominator-compatible \(N\), a network by attaching \(N\mu_t\) voter leaves of type \(t\) to \(h(t)\), with the root as target. For each type \(t\), compute the exact limit \(q_t=\lim_{N\to\infty}Nw_v^{(N)}\), where \(w_v^{(N)}\) is the LEGIT+ weight of any type-\(t\) voter in that expansion; equivalently, compute each type’s total weight \(\alpha_t=\mu_tq_t\).
The society is the rational distribution \(\mu\) over voter types defined by network connector and, if relevant, reported rating; each type contributes repeated leaf voters on the fixed scaffold \(H\). The output is the limiting per-capita weight \(q_t\), or total type weight \(\alpha_t\), assigned by LEGIT+. There is no optimization objective: the task is to compute the mechanism’s limiting weights.
Covers Theorem 6 for voter cohorts on a fixed rooted connector tree. It leaves the false-name-proofness theorems, Theorems 1 and 2; the impossibility and small-network results, Theorems 4 and 5; and the experiments untreated.
The strongest honest anchor is the paper’s only named complexity result: Theorem 6, which states that, given a connected undirected graph \(G\), a voter set \(S\), and a target \(v^\star\), the weight vector returned by LEGIT+ can be computed in \(O(|V|+|E|)\) time. The authors prove this result for their paper; the supplied text defers the correctness and running-time details to its full version. The algorithm uses the graph’s biconnected-component structure. The paper gives no comparable hardness result, so this is an algorithmic lead.
A continuous version I would put to a prover is High-Multiplicity LEGIT+ Weight Computation. Its regime is a large recommendation platform with many raters but a small, recurring set of network roles: for example, users connected to one of a fixed number of community or institutional accounts. The target and these connectors form a fixed finite rooted tree \(H\), with the target at its root. A voter type \(t\) specifies its connector and, if the recommendation is also being computed, its reported rating. Voters of a type are otherwise interchangeable. The society is the rational distribution \(\mu\) over the \(\tau\) supported types, where \(\mu_t\) is their population fraction and \(\tau\ll N\), the number of raters.
To define the question precisely, expand each type \(t\) into \(N\mu_t\) degree-one voters attached to its connector, for \(N\) divisible by the masses’ common denominator. Let \(w_v^{(N)}\) be the weight LEGIT+ assigns to voter \(v\) in that finite network. The input is \(H\), the type-to-connector map, and the rational masses \(\mu\). The task is to return the exact limiting per-capita weight
\[
q_t=\lim_{N\to\infty}Nw_v^{(N)}
\]
for a voter \(v\) of type \(t\). Equivalently, return each type’s total weight \(\alpha_t=\mu_tq_t\), with \(\sum_t\alpha_t=1\). The output is the weight density chosen by the mechanism; this is a computation problem, not an optimization problem.
There is a direct recursive solution. At a connector \(h\), let \(\mu_h=\sum_{t:h(t)=h}\mu_t\), and let \(b\) be the weight share passed to it. If \(\mu_h>0\), assign \(\alpha_t=b\mu_t/\mu_h\) to each type there. In the finite expansion, its \(N\mu_h\) voters compete for LEGIT+’s share with only finitely many child connectors, so their cohort takes all of \(b\) in the limit. If \(\mu_h=0\), divide \(b\) equally among the active child connectors, those whose subtrees contain voters, and recurse. Start at the target with \(b=1\), then set \(q_t=\alpha_t/\mu_t\). This takes \(O(|H|+\tau)\) arithmetic steps, with polynomial bit complexity in the input length. I expect this mirror to be tractable in this stated regime.
This is population continuization: \(\mu_t\) measures the fraction of raters in a type, and the question computes how their mass receives the paper’s LEGIT+ weights. The finite target and connector tree supply the network structure that the weight rule uses. The construction keeps LEGIT+ itself unchanged on every finite expansion; the continuous output is the limit of its type-level weights. A weighted-median recommendation can then use those weights if ratings are included.
The mirror covers Theorem 6’s computation of LEGIT+ weights, in a structured high-multiplicity regime. It does not continuize the paper’s false-name-proofness theorems, impossibility result, small-network optimality result, or experiments. Further questions include whether the compression extends to richer block-cut structures, how sensitive the limit is to a small number of exceptional users, and whether a continuum model can preserve the paper’s individual false-name guarantees when an attacker can add a number of fake accounts proportional to \(N\).
My weakest point is that the paper’s key structure is individual vertex connectivity. The finite connector tree preserves that structure, but an unrestricted atomless network can lose it: individual cut vertices have zero mass, and the limiting weight computation need not capture the strategic effect of adding many fake identities. The scenario is also narrower than a general social network, and Theorem 6 already gives linear-time computation on an explicit graph. The case for the mirror is therefore a focused one: large cohorts over a fixed network scaffold yield a precise, compressed population computation of the paper’s mechanism.
The only strong anchor is Theorem 6: LEGIT+’s weights can be computed in \(O(|V|+|E|)\) time. That is a genuine computational result, and the proposed fixed scaffold with repeated voter leaves is a coherent high-multiplicity version of it.
The strongest objection is that the algorithm depends on deleting individual vertices. Its key objects—articulation points, lobes, and biconnectivity—are properties of named positions in the graph, not just of the distribution of voter types. In a usual atomless network limit, removing one agent removes zero mass, so it cannot express the disconnections LEGIT+ uses. A richer mass distribution over voter types does not by itself recover that topology.
The proposed scaffold preserves the topology by keeping every separator in the fixed finite tree and putting the growing population on leaves. A broader version could use voter cohorts attached to a finite block-cut structure, but then the structure that matters still has to be specified separately. If the population itself supplies more and more separators, that structure grows with it; if it does not, the mirror covers only populations whose network roles are already fixed. The same issue limits extensions to the paper’s manipulation guarantees: an individual has zero mass in an atomless model, so a continuum formulation would need a separate way to represent that individual’s effect. Those guarantees are not part of the proposed anchor, though, so this does not defeat it.
That leaves a real but narrow criticism: the mirror continuizes the multiplicities of users on a fixed network scaffold, while LEGIT+’s distinctive structure remains finite and discrete. I cannot honestly turn that into a decisive objection. The proposed limit is well-defined, the population is the continuous object, and it mirrors a named algorithmic result. A reader may judge this specialization too narrow for the programme, but the case that *no* worthwhile continuous mirror exists is weak; this anchor survives.
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.