| paper | Local Differential Privacy Meets Computational Social Choice - Resilience under Voter Deletion |
| authors | Liangde Tao, Lin Chen, Lei Xu, Weidong Shi |
| venue | IJCAI 2022 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given rational \(\mu\in\Delta_m\), a designated candidate \(c_1\), and a common channel \(P=(p_{ij})\), let \(\widehat{\tau}_j=\sum_i\mu_i p_{ij}\) and \(q_{ij}=\mu_i p_{ij}/\widehat{\tau}_j\). Under the theorem's posterior-sign promise, compute the minimum deleted mass \(d_\infty(\mu,P)=\min\{\sum_jx_j:0\le x_j\le\widehat{\tau}_j,\ \mu_1-\sum_jq_{1j}x_j\ge\mu_i-\sum_jq_{ij}x_j\ \forall i\ge2\}\), an optimal \(x\), and \(d_\infty(\mu,P)/d_0(\mu)\), where \(d_0(\mu)=\sum_{i=2}^m\max\{0,\mu_i-\mu_1\}\). A second question is to determine, for randomized response and \(\mu_i>\mu_1\), the largest \(\epsilon\) for which deleting all reported mass is the only feasible attack.
A plurality society has true type masses \(\mu_i\), a common LDP channel \(P\), observed report-class masses \(\widehat{\tau}_j\), and posterior hidden compositions \(q_{ij}\). The decision variable is report-measurable deleted mass \(x_j\), the objective is \(\sum_jx_j\), and feasibility requires the designated candidate to be a co-winner in residual true mass.
The proposed mirror largely repackages the paper's own asymptotic LP and removes its distinctive finite-\(n\) stochastic winning-probability analysis.
fatal: False
The mirror covers Theorems 1 and 2 as normalized mass-deletion optimization and a randomized-response privacy threshold; it leaves finite-\(n\) concentration bounds, numerical experiments, parameter estimation, and discussion outside.
The strongest positive case is that this paper is unusually close to a genuine population continuization already. Its \(S_{m,\lambda}(n)\) model fixes type proportions \(\lambda\) and studies \(n\to\infty\). The proposed mirror simply makes that high-multiplicity object primary rather than treating it as a limit of finite elections.
Take a large plurality electorate with candidates \(C=\{c_1,\ldots,c_m\}\). A true voter type is \(i\), meaning a vote for \(c_i\), and the true society is a rational mass vector \(\mu\in\Delta_m\). Every voter uses the same LDP channel \(P\), where \(p_{ij}=\Pr[r=j\mid t=i]\). The joint mass of true type \(i\) and reported type \(j\) is
\[ \pi_{ij}=\mu_i p_{ij}. \]
The publicly visible mass reporting \(j\) is
\[ \widehat{\tau}_j=\sum_i \pi_{ij}, \]
and the posterior hidden composition of that report class is
\[ q_{ij}=\Pr[t=i\mid r=j]=\frac{\pi_{ij}}{\widehat{\tau}_j}. \]
Thus the complete population types may be taken to be the at most \(m^2\) joint types \((i,j)\), while the attacker can act only on the observable report coordinate \(j\).
The action is a report-measurable deletion rule \(x=(x_1,\ldots,x_m)\), where \(x_j\) is the mass deleted from report class \(j\), with \(0\le x_j\le\widehat{\tau}_j\). Deletion within a report class is exchangeable, exactly as in the paper: the attacker cannot target hidden true types. The resulting expected residual true mass of candidate \(i\) is
\[ \rho_i(x)=\mu_i-\sum_{j=1}^m q_{ij}x_j. \]
The objective is to minimize deleted mass subject to \(c_1\) becoming a co-winner:
\[ d_\infty(\mu,P)= \min_x\left\{ \sum_{j=1}^m x_j: 0\le x_j\le\widehat{\tau}_j,\ \rho_1(x)\ge \rho_i(x)\ \forall i\ge2 \right\}. \]
For comparison, the no-LDP deletion mass is
\[ d_0(\mu)=\sum_{i=2}^m\max\{0,\mu_i-\mu_1\}. \]
Assume \(d_0(\mu)>0\), and define the continuous power of LDP as \(d_\infty(\mu,P)/d_0(\mu)\). This is a population problem: masses are fractions of the electorate, deletion costs are mass, and the objective is total deleted mass. It does not make the outcome space continuous; the outcome remains a plurality winner. The continuous object is the society and the attack on it.
A credible regime is a national or citywide election with millions of voters, a small candidate set, a common polling mechanism, and unit deletion cost. The number of agents is enormous compared with the number of relevant types: \(n\gg m^2\). This is not an invented story: the paper itself assumes \(n\lambda_i\) voters of each true type, knows \(\lambda\), and takes \(n\to\infty\).
My lead anchor is Theorem 1, proved in this paper rather than cited from elsewhere. It states that under the sign condition on the posterior differences \(q_{ij}-q_{1j}\), for every \(\xi\in(0,1)\),
\[ \operatorname{APoLDP}(S,R,\xi) = \frac{\operatorname{OPT}_{LP}(\widehat{\tau})} {\sum_{j=2}^m\max\{0,n\lambda_j-n\lambda_1\}}. \]
After dividing by \(n\), the LP in the theorem is precisely the continuous problem above, evaluated at \(\widehat{\tau}\). Thus the continuous question is:
Given rational \(\mu\), an LDP channel \(P\), a designated candidate \(c_1\), and the theorem’s posterior-sign promise, compute \(d_\infty(\mu,P)\), output an optimal report-measurable mass deletion vector \(x\), and compute \(d_\infty(\mu,P)/d_0(\mu)\).
This is a natural Class A problem. It is an LP with \(m\) variables and \(m-1\) winner constraints, hence polynomial in \(m\) and the encoding length of \(\mu\) and \(P\). The paper’s important point is that the finite-\(n\) chance constraint becomes asymptotically insensitive to the particular fixed \(\xi\): finite sampling fluctuations are lower-order, while the hidden composition of each report class remains essential. A finite implementation can round \(nx_j\) and add a vanishing safety margin.
The second anchor is Theorem 2, also proved in this paper. It gives a closed-form privacy threshold for randomized response when \(\mu_i>\mu_1\) for every \(i\ge2\). The corresponding continuous problem is:
Given \(\mu\) and the randomized-response family \(P^\epsilon\), compute the largest privacy parameter \(\epsilon^\star\) for which deleting the entire reported population is the only feasible continuous attack, and compute the resulting maximal LDP-resilience ratio.
The theorem gives
\[ \epsilon^\star=\ln\frac{\mu_{\max}}{\mu_1}, \qquad \mu_{\max}=\max_i\mu_i, \]
and the maximal ratio
\[ \frac{1}{1-\sum_{i=2}^m(\mu_i-\mu_1)} = \frac{1}{1-m\mu_1}. \]
This is again Class A, in fact closed form. It is a genuine design question about a continuous society: how much privacy can be relaxed before a positive mass of reported voters becomes sufficient to overturn the designated candidate’s disadvantage?
The mirror covers Theorems 1 and 2, not the paper’s numerical experiments or every discussion point. It also preserves the paper’s crucial information restriction. Giving the attacker arbitrary access to the joint types \((i,j)\) would destroy the problem; allowing only report-measurable deletion is what makes this the same manipulation question in the continuum.
There is no named NP-hardness, coNP-hardness, or parameterized-hardness result in the paper, so I would not manufacture a Class B claim. The positive case is therefore algorithmic: the paper supplies a proved LP characterization and a proved threshold theorem, and both become clean mass-optimization questions.
The weakest point is also clear: the paper almost already contains this continuization. Its APoLDP analysis is effectively a high-multiplicity computation, so the mirror may look like a repackaging rather than a new computational discovery. Moreover, in the exact atomless limit the finite-\(n\) winning-probability parameter \(\xi\) largely disappears, and plurality with only \(m\) observable types is not a demanding exponential-type problem. Still, that weakness supports rather than refutes the mirror’s legitimacy: the authors’ own asymptotic formulation is evidence that the continuous population regime is sensible, and Theorems 1 and 2 provide precise, computable continuous questions rather than merely an analogy.
The proposed mirror is already the asymptotic core of this paper. I would not use high multiplicity as an objection—\(n\lambda_i\) voters of each type are a perfectly credible national-election regime. The problem is that the paper itself has already taken that limit and solved the resulting population problem.
For Theorem 1, write
\[ \pi_{ij}=\mu_i p_{ij},\qquad \widehat{\tau}_j=\sum_i\pi_{ij},\qquad q_{ij}=\frac{\pi_{ij}}{\widehat{\tau}_j}. \]
If \(x_j\) mass is deleted from reported class \(j\), then the residual true mass of candidate \(i\) is
\[ \rho_i(x)=\mu_i-\sum_j q_{ij}x_j. \]
Thus the proposed continuous problem is exactly the finite-dimensional LP already implicit in Theorem 1. It has \(m\) deletion variables, \(m-1\) winner constraints, and report-class capacity constraints. The \(m^2\) latent joint types do not create a pricing problem: they merely provide the coefficients \(q_{ij}\). The theorem has therefore not identified a missing continuous computational question; it has already evaluated it.
The sign condition in Theorem 1 does not rescue the mirror. If it is retained, the proposed problem is a theorem already proved under a promise. If it is removed, the deterministic atomless formulation is still a plurality LP. The sign condition matters to the paper’s finite-\(n\) concentration argument, not to the basic continuous optimization problem.
More fundamentally, the limit removes the paper’s distinctive stochastic object. At finite \(n\), the hidden composition of a reported class fluctuates, so achieving winning probability \(\xi\) is meaningful. In an atomless report-measurable model, that composition is exactly \(q_{ij}\); the outcome is deterministic, and every \(\xi\in(0,1)\) gives the same constraint. Retaining a nontrivial confidence level requires finite-\(n\) fluctuations, central-limit corrections, or large-deviation rates. That is a finite-population statistical problem, not the population-mass mirror proposed by ChoCo. Conversely, if the attacker may exploit individual identities, then \((\mu,P)\) no longer specifies the admissible information structure, so the mirror is under-specified.
Theorem 2 is weaker still as an anchor. Its privacy threshold is already a closed-form consequence of the paper’s own analysis, not an unasked computational problem. There is also an arithmetic inconsistency in the proponent’s transcription: when every \(\mu_i>\mu_1\),
\[ \sum_{i=2}^m(\mu_i-\mu_1)=1-m\mu_1. \]
Hence \(1-\sum_{i=2}^m(\mu_i-\mu_1)=m\mu_1\), not \(1-m\mu_1\). The natural maximal ratio is \(1/(1-m\mu_1)\), consistent with the two-candidate formula \(1/\phi\), but not with the displayed expression \(1/[1-\sum_i(\mu_i-\mu_1)]\). Even after correcting this, the result remains an already-solved threshold calculation.
One can propose richer variants—type-dependent privacy parameters, arbitrary report channels, full rankings, or a large-deviation security objective. But those either become finite-dimensional LDP mechanism design for plurality, or import a different voting problem whose complexity comes from the newly added signal/type space. They are not continuous mirrors of the computational results in this paper.
The honest weakness of this negative case is that the national-election regime is genuinely sensible, and a carefully designed finite-size or large-deviation extension could be worthwhile. But the faithful atomless mirror is not merely easy; it is already the paper’s APoLDP LP with the probability aspect removed. There is therefore no missing ChoCo computational landscape here to investigate.
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.