| paper | Manipulation-Robust Selection of Citizens’ Assemblies |
| authors | — |
| venue | AAAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results are quantitative manipulation bounds and impossibilities, not named algorithmic or complexity results for computational problems, so bit (a) fails. A mass-relabelling mirror is nevertheless a plausible, recognisable high-multiplicity extension, and the scaling objection bounds its interpretation rather than eliminating the question. The absence of a qualifying computational anchor makes the grade red.
fails bit a — no named computational result to mirror
The proposed mirror covers the paper’s type-level selection probabilities, manipulation measures, and asymptotic pool-size results, while leaving randomized rounding, empirical experiments, and quota-based algorithms aside.
The strongest positive case is a narrow but genuine one: the paper’s manipulation problem has a natural high-multiplicity version in which volunteers are replaced by mass over feature-vector types. The lead anchor is Theorem 4.2, proved in this paper. I would not claim that the paper contains a numbered P-versus-NP result; its named anchors are quantitative algorithmic theorems. If “anchor” is restricted only to complexity-class statements, this paper has no qualifying anchor. Under the broader “and so on” reading, it is a good candidate.
Take a finite feature system \(F\), with value sets \(V_f\), and feature-vector types
\[ W=\prod_{f\in F}V_f. \]
A type \(w\) completely specifies the volunteer’s reported-feature possibilities and all attributes relevant to the paper’s selection rule. Let \(\mu_w\) be the fraction of the volunteer pool of type \(w\), and let \(M\) be the population scale, so type \(w\) has mass \(\lambda_w=M\mu_w\). The underlying constituency has feature rates \(\rho_{f,v}\), and the panel has \(K\) seats.
A selection profile is a type-level probability \(x_w\in[0,1]\): every unit of type-\(w\) mass is selected with probability \(x_w\). The representation polytope is
\[ \sum_{w:f(w)=v}\lambda_wx_w=K\rho_{f,v} \quad\text{for every }(f,v), \qquad \sum_w\lambda_wx_w=K. \]
For \(r>1\), the continuous \(\ell_r\) selector is
\[ x^{(r)}(\lambda) \in\arg\min_{x\in\mathcal R(\lambda)} \sum_w\lambda_w\left|x_w-\frac KM\right|^r. \]
This is exactly the paper’s \(\ell_p\) objective after aggregating equal feature vectors and replacing agent counts by masses.
A coalition’s manipulation is a mass relabelling. It chooses \(y_{u,w}\ge 0\), where \(y_{u,w}\) is mass whose true type is \(u\) but which reports \(w\), with
\[ \sum_w y_{u,w}\le \lambda_u, \qquad \sum_{u,w}y_{u,w}=a. \]
The reported pool becomes
\[ \lambda'_w=\lambda_w-\sum_z y_{w,z}+\sum_u y_{u,w}. \]
The coalition’s objective is to maximize one of the paper’s three gains:
Thus my lead problem would be:
Continuous \(\ell_r\)-Sortition Manipulation\(_\infty\). Given rational \((F,V_f,\rho,\lambda,M,K,r,a)\), compute, or \(\varepsilon\)-approximate, the maximum internal, external, and composition manipulation gains over all mass relabellings of total mass \(a\). A witness consists of a transfer matrix \(y\), the resulting reported distribution \(\lambda'\), and the two optimal selection profiles.
This is recognisably the paper’s problem. It retains the same population rates, volunteer-pool bias, feature vectors, representation constraints, \(\ell_r\) objective, and costless strategic reports. The only change is that \(n_w\) becomes \(\lambda_w\), and a coalition of \(c\) volunteers becomes mass \(a=c\). Randomized rounding is not being discarded arbitrarily: the paper explicitly says that rounding preserves the selection probabilities, and all three manipulation measures depend only on those probabilities.
The regime is highly plausible for national or city-wide citizens’ assemblies. The feature taxonomy is fixed and coarse—gender, age band, region, education, political concern, and so forth—while the volunteer pool can contain many thousands of people. Hence \(M\gg |W|\), or at least \(M\) grows while the number of effective feature types stays bounded. Volunteers sharing a feature vector are genuinely interchangeable under the paper’s model: they have the same relevant features, reporting options, and no individual-specific reporting costs. Missing intersections, such as a feature vector absent from the volunteer pool, are also plausible under self-selection bias and are central to the paper’s negative examples.
Theorem 4.2 then has a direct continuous reading. Under its Pool Richness assumption, if \(a\le \kappa M\), the expected bounds become
\[ \operatorname{MANIP}_{\mathrm{int}}, \operatorname{MANIP}_{\mathrm{ext}} \in O\!\left(\frac{K}{M^{1-1/r}}\right), \]
and
\[ \operatorname{MANIP}_{\mathrm{comp}} \in O\!\left(\frac{aK}{M^{1-1/r}}\right). \]
The theorem is proved here, not cited from elsewhere. Its proof already works with type-level masses: it preserves aggregate selection mass by feature vector, controls the maximum type probability, and then uses norm inequalities. This is unusually strong evidence that the proposed mirror is not an invented relaxation.
I expect the fixed-report selection problem to be Class A: for explicit \(W\), it is convex optimization, with leximin handled by sequential linear programs and Nash welfare by a concave program. The full worst-case problem over \(y\), however, is a plausible Class C candidate: it optimizes over a mass-transfer polytope while evaluating a parameter-dependent convex optimum, and activating a previously absent type can cause discontinuous changes in the relevant type profile. The paper does not settle this outer computational problem. That is precisely a worthwhile ChoCo question rather than a defect.
A second, independent anchor is Theorem 3.1, also proved here. Define the same continuous manipulation problem for the paper’s Leximin and Nash selectors. Nash welfare is the weighted high-multiplicity limit of the paper’s product objective,
\[ \max \prod_{w:\lambda_w>0} x_w^{\lambda_w}, \]
and continuous Leximin is obtained by clearing denominators in \(\lambda\), replicating each type accordingly, and applying the paper’s leximin rule.
The corresponding problem is:
Continuous Leximin/Nash Manipulation\(_\infty\). Given \((\rho,\lambda,M,K,a)\), compute the maximum internal or composition gain caused by relabelling mass \(a\), once the post-manipulation selection profile is chosen by Leximin or Nash welfare.
Theorem 3.1 predicts an especially sharp answer. With two binary features and
\[ \mu_{00}=\mu_{11}=\nu^*,\qquad \mu_{10}=1-2\nu^*,\qquad \mu_{01}=0, \]
a mass \(a=c<K/2\) of type \(10\) can report type \(01\). For arbitrarily large \(M\), the continuous analogue retains
\[ \operatorname{MANIP}_{\mathrm{int}}=1 \]
and composition gain \(c\) for both Leximin and Nash welfare. This is not a single-agent artefact: the same construction works with a positive mass \(c\) of strategic volunteers while the rest of the pool grows arbitrarily large.
For this second problem, the two-feature witness is Class A to analyse directly—it is an explicit convex/lexicographic calculation—but the general worst-case optimization is again a plausible continuum-specific hardness problem. The important computational conclusion already transfers: high multiplicity does not automatically make Leximin or Nash manipulation vanish.
Theorem 4.3, proved here, supplies a useful boundary condition rather than a separate anchor. It says that no rounding-based objective can beat an \(\Omega(K/M)\) individual manipulation rate, or an \(\Omega(aK/M)\) composition rate, on some pools. In the continuous setting this generates a further problem: design the best anonymous representation-feasible selection objective against mass relabelling. The paper’s \(\ell_\infty\) discussion suggests the optimal rate may be attained up to constants.
The mirror covers the paper’s theoretical results about Step 1 selection probabilities, manipulation, and asymptotic pool size. It does not claim to continuize the finite discrepancy-based rounding theorem, the empirical datasets, or the paper’s ex-post quota algorithms. Those are separate questions.
The weakest point is that the proposed outer manipulation optimization is a new problem, not a theorem already solved by the authors. Moreover, the paper already uses fractional selection probabilities, so an opponent can say that the mirror merely renames an existing convex relaxation. The answer is that the continuous object here is specifically the volunteer population: \(\lambda\) is a distribution over complete, interchangeable types, and \(y\) is a mass report-transfer. The paper’s own use of fractional pool composition, equal treatment within feature vectors, pool duplication, and asymptotics in \(n\) makes this the high-multiplicity version of its actual question—not continuity of the panel outcome.
The strongest negative case begins with a scope problem: none of the proposed anchors is a computational-complexity result in ChoCo’s sense. Theorem 3.1 is an impossibility result for two selection objectives; Theorem 4.2 is a stability bound; and Theorem 4.3 is a lower bound on unavoidable manipulation. None classifies an exact, approximate, or parameterized computational problem. The convex program used to define the selection probabilities is part of the model, not a theorem about its complexity. The proposed outer optimization over mass reports is a new problem, not a computational result of this paper.
Even granting the broader notion of “computational result,” the continuous limit has a serious scaling defect. Let \(M\) be the volunteer-pool size, \(K\) the panel size, and \(x_w\) the selection probability of a type. In normalized population masses,
\[ \sum_w \mu_w x_w=K/M. \]
For the citizens’ assembly regime actually studied in the paper, \(K\) is fixed while \(M\) grows. Thus every ordinary type has selection probability tending to zero. The paper’s asymptotic rates are then largely dilution rates caused by dividing a fixed number of seats among more volunteers.
This undermines each anchor.
Theorem 4.2 concerns coalitions of \(c\leq \kappa M\). If \(c\) is fixed, the coalition becomes zero mass in the continuum. If \(c=\alpha M\), its composition bound is generally vacuous when \(K\) is fixed, since the coalition cannot receive more than \(K\) seats anyway. The theorem therefore does not yield a nontrivial positive-mass manipulation problem with the same institutional meaning.
Theorem 3.1 is even more dependent on this singularity. Its unit-probability manipulation works by having one or a few agents report an otherwise absent feature vector. The reported type contains only the strategic defectors, allowing each of them to receive probability one. As \(M\) grows, those defectors have mass \(O(1/M)\). The phenomenon survives only as a finite marked exception sitting on top of a continuum, not as manipulation of a continuous society. Replacing the \(c\) agents by a positive fraction would require \(K\) to grow linearly as well, because the theorem assumes \(c<K/2\).
Theorem 4.3 has the same problem in reverse: its \(\Omega(K/M)\) lower bound tends to zero because individual selection probabilities tend to zero. In a genuine mass model, that is not a meaningful unavoidable manipulation rate. If probabilities are rescaled by \(M/K\), the lower bound becomes constant, but then the quantity being studied—and effectively the objective being optimized—is a new normalized selection-intensity problem.
The obvious repairs do not restore a mirror of the paper. Keeping \(K/M=\beta>0\) produces assemblies whose size grows linearly with the constituency, changing the institution and eliminating the paper’s finite-panel asymptotics. Rescaling probabilities produces a different utility notion. Measuring only aggregate seats gained by a positive-mass coalition abandons the paper’s central individual incentive. Retaining a few exceptional agents preserves the theorem but abandons the atomless high-multiplicity interpretation.
I would not rely on the weaker objection that agents have identities. The proponent is right that one can enrich a type with both a true feature vector and a reported feature vector, and represent manipulation by a mass-transfer matrix. Nor is existing high-multiplicity work an objection; the paper’s coarse feature vectors and pool-copying experiments actually make a high-multiplicity regime plausible.
That concession is also why the negative case is not airtight. A weighted Leximin/Nash model with a positive panel density could be a sensible new continuous mechanism-design problem. But it would be an adjacent problem, not a continuous version of any named computational theorem here. Under ChoCo’s stated standard, the paper supplies no qualifying complexity anchor, and its three strongest quantitative results collapse either into dilution, a vanishing exceptional coalition, or a redefined objective. The universal claim that no worthwhile variant exists is therefore overstated; the narrower claim that this paper does not motivate a worthwhile ChoCo mirror is defensible.
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.