| paper | The Complexity of Bribery and Control in Group Identification |
| authors | G. Erdélyi, Christian Reger, Yongjie Yang |
| venue | ATAL 2017 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.2
Given a finite role set \(J\), rational distribution \(\mu\) over types \(\theta=(j,r,z)\) with \(r:J\to\{0,1\}\), target flag \(z\), quotas \(q_1,q_0\in[0,1]\), and mass budget \(\lambda\), may one transfer at most \(\lambda\) mass of complete assessment rows \(r\) to rows \(r'\), preserving \(j,z\), so that every unit of target mass \(z=1\) is socially qualified under \(A_j(\mu')\ge q_1\) for self-approvers and \(1-A_j(\mu')<q_0\) for self-disapprovers?
Types are \(\theta=(j,r,z)\), where \(j\) is a candidate class, \(r:J\to\{0,1\}\) is a qualification row, and \(z\) marks the target group. A distribution \(\mu\) is transformed by mass variables \(x_{\theta,r'}\) satisfying \(\sum_{r'}x_{\theta,r'}=\mu_\theta\); minimize \(\sum_{\theta}\sum_{r'\ne r_\theta}x_{\theta,r'}\), subject to the consent inequalities using \(A_j(\mu')=\sum_\theta\mu'_\theta r_\theta(j)\).
The fixed constants \(s,t\) do not yield a nondegenerate normalized limit, and the RX3C incidence may remain encoded in the type matrix; consequently, results for the mirror would not automatically explain the source theorem's hardness.
fatal: False
The mirror covers constructive group bribery for consent rules, especially the hardness regime \(s\ge1,t\ge3\). It leaves the procedural rules, control problems, destructive variants, and the separate \(t=2\) open case untouched.
My strongest honest mirror is a continuous version of constructive group bribery under consent rules, anchored on the paper’s hardness result rather than on its easier procedural cases.
The anchor is Theorem 4.2, proved in this paper: \(f^{(s,t)}\)-CGB is NP-complete for every \(s\ge 1\) and \(t\ge 3\). Here an instance consists of individuals \(N\), a binary qualification profile \(\varphi\in\{0,1\}^{N\times N}\), a distinguished group \(S\subseteq N\), and a bribery budget \(\ell\). The briber may change at most \(\ell\) complete rows of \(\varphi\), and asks whether every member of \(S\) can thereby become socially qualified under the consent rule \(f^{(s,t)}\). If an individual qualifies himself, he needs at least \(s\) incoming qualifications; if he disqualifies himself, he is qualified only when fewer than \(t\) individuals disqualify him. The paper proves hardness by reduction from Restricted Exact Cover By 3-Sets: the elements \(b_j\) are target individuals, each \(S_i\) disqualifies exactly the three elements in its set, the bribery budget is \(2m\), and a successful bribery exists exactly when the \(S_i\) contain an exact cover. The \(s\ge2\) and \(t\ge4\) cases are obtained by adapting the same construction. The paper notes that membership in NP is immediate and proves the NP-hardness here; this is not merely a cited result.
I would call the continuous problem Consent-Quota Group Bribery\(_\infty\).
Take a finite set \(J\) of candidate or role classes. An individual type is
\[ \theta=(j,r,z), \]
where \(j\in J\) is the individual’s candidate class, \(r:J\to\{0,1\}\) is the individual’s qualification assessment of every candidate class, and \(z\in\{0,1\}\) records whether that individual belongs to the distinguished target group. Thus all individuals of the same type have the same role, the same assessment of every role class, the same self-assessment \(r(j)\), and the same bribery cost. A society is a distribution \(\mu\) over these types.
This is a natural high-multiplicity regime for a large professional or institutional qualification system: there may be millions of people, but only a moderate number of standardized roles, certification classes, or skill profiles. Agents evaluate people by their role or qualification class rather than by name. One can have \(n=M\tau\) individuals but only \(\tau\) distinct types, with \(M\) large.
For a post-bribery distribution \(\mu'\), let
\[ A_j(\mu')=\sum_{(j',r,z)}\mu'_{(j',r,z)}\,r(j) \]
be the mass of society qualifying candidates in class \(j\). Using per-capita quotas \(q_1,q_0\in[0,1]\), an individual of type \((j,r,z)\) is socially qualified exactly when
\[ \begin{cases} A_j(\mu')\ge q_1, &\text{if }r(j)=1,\\[2mm] 1-A_j(\mu')<q_0, &\text{if }r(j)=0. \end{cases} \]
For a finite population of size \(n\), the direct normalized correspondence is \(q_1=s/n\) and \(q_0=t/n\). Equivalently, one could use unnormalized mass and retain the paper’s absolute quotas \(s,t\).
The action is a mass transfer of rows. If \(x_{j,r,z,r'}\) is the mass of type \((j,r,z)\) whose entire assessment row is changed to \(r'\), then
\[ \sum_{r'}x_{j,r,z,r'}=\mu_{j,r,z}. \]
The cost is
\[ \sum_{j,r,z}\sum_{r'\neq r}x_{j,r,z,r'}, \]
and the optimization problem is to minimize this cost subject to every unit of target mass, \(z=1\), being socially qualified in the resulting society. Its decision version asks whether the cost is at most a given mass budget \(\lambda\).
This is recognizably the same problem as the paper’s CGB. The population is still the object being changed; the briber still changes individuals’ complete qualification reports; the target is still a group rather than a fixed-size committee; and the social rule still has the paper’s two-branch self-consent logic. The only substantive change is that repeated, indistinguishable rows are represented by mass, and the count quotas are expressed in population units.
I expect the continuous version to be tractable, at least in the explicit finite-type regime, and therefore to be a plausible Class A mirror. The paper’s RX3C reduction relies on selecting whole individuals or whole rows. In the mirror, the corresponding variables are fractional masses. The condition that each target class lose enough disqualifications becomes a system of linear coverage inequalities. The exact-cover requirement is replaced by a fractional-cover feasibility problem. In the reduction’s own structure, variables \(x_i\) represent the mass of agents of set type \(S_i\) who are bribed, and the constraints saying that every \(b_j\) receives enough remaining support are linear in the \(x_i\).
More generally, after fixing which consent branch each target type uses, the aggregate approval quantities \(A_j(\mu')\) are linear functions of the bribed masses. The possible replacement rows are binary vectors, so the associated pricing problem is itself a linear optimization over independent coordinates. This suggests an LP or a small collection of LPs rather than the integral exact-cover structure used in Theorem 4.2. If the unrestricted problem eventually proves hard because of the interaction among many target classes and consent branches, that would be a continuum-specific Class C result; it would not be hardness transferred from the RX3C argument.
The main further questions would be whether the full, unrestricted Consent-Quota Group Bribery\(_\infty\) admits a polynomial LP formulation; whether a finite solution can be rounded from a continuous one with additive loss depending only on the number of types; whether weighted or type-dependent bribery costs preserve tractability; and what happens at the paper’s open boundary \(t=2\).
The weak point is that this mirror imposes a strong block structure. The original paper permits arbitrary opinions about named individuals, whereas the mirror assumes that large groups evaluate people only through a finite role or qualification type. The change from fixed absolute quotas \(s,t\) to per-capita quotas is also a modelling choice. If the intended application genuinely depends on idiosyncratic interpersonal judgments, this is a weak mirror. But for a large institution with standardized qualification categories, the repeated-type regime is plausible, and it directly tests the programme’s central question: does the NP-hardness of constructive group bribery come from population multiplicity, or from a deeper combinatorial structure? For Theorem 4.2, the strongest positive case is that its exact-cover hardness is precisely the sort of integrality that a continuous population can dissolve.
The best negative case is that Theorem 4.2 does not naturally describe a high-multiplicity population. Its input is an arbitrary binary relation \(\varphi\in\{0,1\}^{N\times N}\), with voters and candidates being the same named individuals. The computational payload is the incidence pattern between particular people: in the RX3C reduction, each set-agent has a distinct row encoding one \(S_i\), and each element-agent \(b_j\) is a distinct target. Nothing in the theorem supplies repeated, interchangeable agents.
The proposed type \((j,r,z)\) therefore imposes a substantial new symmetry:
\[ \varphi(a,a')=r(j') \]
for every voter of class \(j\) and candidate of class \(j'\). Qualification becomes class-uniform: all members of a candidate class have the same incoming support and, if their self-bits agree, the same social status. The original problem asks which named individuals qualify; this version asks which role classes qualify. That is not merely replacing counts by masses. It restricts the admissible profiles and changes the object being identified.
There is also a genuine scaling problem. With the paper’s fixed quotas \(s,t\), normalizing a population of size \(n\) gives thresholds \(s/n\) and \(t/n\). As \(n\) grows, the rule degenerates: a self-approving candidate needs merely positive approval mass, while a self-disapproving candidate requires essentially unanimous approval. Keeping nonzero quotas \(q_1,q_0\) instead means replacing \(s,t\) by quantities proportional to \(n\). That may be a sensible new rule, but it is not the high-multiplicity limit of the theorem’s fixed-parameter consent rule.
The proposed LP intuition also depends on the strongest possible quotient. If the role set \(J\) is fixed, arbitrary RX3C-style incidence cannot be represented. If \(J\) grows and rows \(r:J\to\{0,1\}\) encode the set system, then the instance-specific combinatorial structure has simply been moved into the type/approval matrix; the population itself is no longer carrying the relevant information. The resulting fractional-cover problem may be interesting, but it is a new class-based quota-bribery problem rather than a faithful continuous mirror of group identification.
That said, this is not an airtight negative case. A large institution in which people assess standardized qualification classes, and the target is an entire class or positive-mass subgroup, is a plausible high-multiplicity scenario. Under that interpretation, the proposed mirror is legitimate and its fractionalization of exact cover is precisely a worthwhile computational question. I therefore cannot honestly defend the universal claim that no worthwhile mirror exists. The strongest defensible conclusion is narrower: the mirror should be presented as a new block-symmetric, per-capita consent model—not as a direct continuization of Theorem 4.2.
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.