| paper | Eliminating Majority Illusion Is Easy |
| authors | Jack Dippel, Max Dupré la Tour, April Niu, Sanjukta Roy, Adrian Vetta |
| venue | AAAI 2025 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Corollary 22
statement extracted from the paper’s text layer
Given rational type masses \(\mu\), a blue/red partition with blue mass greater than \(1/2\), and a symmetric rational matrix \(a\) of link densities between finitely many exchangeable types, choose a symmetric post-edit density matrix \(z\) in \([0,1]\) to minimize one-half times the sum over \(t,u\) of \(\mu_t \mu_u |z_{tu}-a_{tu}|\), subject to sum over blue \(u\) of \(\mu_u z_{tu}\) being at least the sum over red \(u\) of \(\mu_u z_{tu}\) for every type \(t\); addition-only and removal-only variants impose \(z \ge a\) or \(z \le a\).
A finite-step dense block-regular network with type masses, type colours, and type-pair link densities; decision variables are post-edit link densities and absolute-value slack variables, with normalized edited edge mass minimized under type-wise blue-neighbour-majority constraints.
The proposal lacks an exact finite-n rounding or convergence theorem and replaces arbitrary vertex-level edits with divisible block capacities, so its relationship to general MIE remains unproved.
fatal: False
It covers the p=1/2 MIE, MIAE, and MIRE polynomial-time results, but not the p not equal to 1/2 hardness theorems or the unresolved p=1/3 and p=2/3 cases.
My strongest case is for a mirror of Corollary 22, proved in this paper: “MIE and the \(1/2\)-ILLUSION problem can be solved in polynomial time.” The paper’s supporting Corollaries 14 and 18 establish the analogous addition-only and removal-only results, also proved here. I would not use Theorems 24–27 as anchors: their discrete NP-hardness may rely precisely on indivisible, individually specified edges, so claiming that hardness transfers continuously would be weak.
The mirror I would propose is Block-Regular Majority-Illusion Elimination\(_\infty\).
Take a very large social network whose agents belong to finitely many social types \(T\), with \(|T|=q\ll n\). A type records everything relevant to the problem: whether the agent is blue or red, its community or demographic role, its permitted connection partners, and its edit costs. Let \(\mu_t\) be the fraction of agents of type \(t\), with \(\sum_t\mu_t=1\) and \(\sum_{t\in B}\mu_t>1/2\).
The network is represented by a symmetric rational matrix \(a\), where \(a_{tu}\in[0,1]\) is the fraction of possible links present between types \(t\) and \(u\). This is a finite-step graphon, or equivalently the limit of large block-regular graphs. Every agent of type \(t\) has the same mass of neighbours in every type block.
A solution is another symmetric matrix \(z\), \(0\le z_{tu}\le1\), representing the post-edit link densities. For each type \(t\), define
\[ b_t(z)=\sum_{u\in B}\mu_u z_{tu}, \qquad r_t(z)=\sum_{u\in R}\mu_u z_{tu}. \]
The requirement is
\[ b_t(z)\ge r_t(z) \quad\text{for every type }t. \]
Thus every agent—not merely the population as a whole—has at least half of its neighbourhood in the global majority colour. For the unrestricted version, \(z\) may lie above or below \(a\); for addition-only, \(z\ge a\); and for removal-only, \(z\le a\). The objective is the normalized number of altered links,
\[ \frac12\sum_{t,u}\mu_t\mu_u\,|z_{tu}-a_{tu}|, \]
or, in decision form, whether this quantity is at most \(K\).
This is genuinely a continuous population model. The mass \(\mu_t\) is the fraction of society of each type, while \(\mu_t\mu_u z_{tu}\) is the mass of social connections between two types. The action variable is connection mass, not a fractional election outcome. The local neighbourhood condition from the paper is retained exactly at type level, including homophily and type-specific connectivity; this is not just replacing the network by the global blue/red fraction.
The high-multiplicity regime is plausible for a large platform, electoral network, or recommendation system with millions of users divided into a modest number of recurring communities, regions, age cohorts, or occupation groups. Within a type, users are interchangeable for the intervention: the platform does not target named individuals but changes an exchangeable fraction of links between cohorts. A finite instance with \(n\mu_t\) agents per type and regular inter-block degrees realizes the same model. Rational values of \(z\) can be implemented by regular bipartite or within-block graphs, with normalized edit cost converging to the displayed objective; rounding errors vanish as \(n\) grows.
The authors should recognise this as their problem’s continuous analogue. It preserves the two defining ingredients of MIE: altering edges, and enforcing a local majority condition at every node. It also reflects the proof architecture of the paper. Theorem 19 decomposes unrestricted MIE into an addition problem and a removal problem; Corollaries 14 and 18 solve those pieces in polynomial time; Corollary 22 combines them. In the block-regular limit, that decomposition becomes a pair of continuous capacity problems.
The expected classification is Class A. The constraints are linear in \(z\), and the objective can be linearized with auxiliary variables. Hence the continuous problem is a rational linear program with \(O(q^2)\) variables and constraints, solvable in time polynomial in \(q\) and the input encoding length. The paper’s TDI and \(b\)-matching machinery explains why this is not an arbitrary simplification: its polynomial algorithm already identifies the relevant structure as a capacitated matching problem with a tractable relaxation. Continuization makes the edge capacities divisible and removes irrelevant vertex labels.
This mirror covers the paper’s full \(p=1/2\) MIE result, including its addition-only and removal-only restrictions. It does not claim to mirror every arbitrary graph instance in the paper, nor does it claim that Theorems 24–27 transfer. Indeed, under this continuous edge-mass model, the \(p\)-variants also become linear programs, so the paper’s NP-hardness for other \(p\)-values may disappear. That would be a useful boundary result rather than a defect: it would identify the integrality of individual edge choices as the source of the discrete hardness.
The weakest point is that the model is dense and block-regular. It excludes sparse networks with many rare, structurally unique vertices, and fractional edge densities may be viewed as a relaxation of exact finite graph editing. If the authors regard those individual topological details as essential, they may reject this as too coarse. The answer is that the programme only needs one credible high-multiplicity regime, and large exchangeable social-network blocks are a natural one. The right follow-up questions are whether the normalized optimum has an exact finite-\(n\) rounding theorem, whether the mirror survives in sparse bounded-degree limits, and for which \(p\)-values or weighted edit costs the continuous problem remains tractable.
The strongest attack is that the proposed object is not actually a high-multiplicity version of MIE; it is a new dense graphon network-design problem.
MIE’s constraint is pointwise: every named vertex must have enough blue neighbours after editing. The pair \((\mu,a)\) records only type masses and aggregate edge densities. Those data do not determine the distribution of individual neighbourhoods. For example, with \(N\) red and \(2N\) blue vertices, one graph may give every red vertex \(N/4\) red and \(N/4\) blue neighbours, while another gives half the red vertices \(N/2\) red and no blue neighbours and the other half no red and \(N/2\) blue neighbours. The colour-level edge densities are identical, but the first instance already satisfies the condition and the second requires many additions.
The proponent can repair this by splitting the populations into sufficiently detailed neighbourhood-profile types and then imposing block regularity. But that is an additional exchangeability assumption, not a consequence of high multiplicity. In a generic social network, an agent’s relevant type includes its incidence pattern, not merely its colour, community, or permitted partner classes. Preserving those patterns can require \(\Theta(n)\) types, eliminating the multiplicity gain. If instead one assumes finitely many perfectly regular blocks, the problem has been re-modelled: individual edge edits have become divisible type-pair capacities, and the paper’s b-matching structure is replaced by an immediate small LP.
The proposed finite-\(n\) justification is only asymptotic. A density matrix need not encode the graphical or availability constraints of a particular finite network, and the discrepancy matters most in the sparse bounded-degree regime where social networks normally live. Under dense normalization, the model changes the intervention scale from editing \(O(n)\) links to editing \(O(n^2)\) possible links; under sparse normalization, ordinary graphon edge masses collapse. A faithful arbitrary-network limit would need a graphing or rooted-network model, not the finite type distribution used by ChoCo. An arbitrary graphon also lacks a finite computational input unless it is restricted back to finite-step graphs.
The same objection applies to Corollaries 14 and 18: the addition-only and removal-only mirrors preserve the theorem only after replacing vertex-level editing by exchangeable block-capacity editing. That is an interesting new extension, but it does not establish a continuous mirror of the paper’s result.
This negative case has a real limitation. A repeated, dense, block-regular platform network is a plausible high-multiplicity regime, and its LP is a legitimate Class-A boundary problem. Therefore I cannot honestly defend the universal claim that no worthwhile scenario exists. The strongest defensible verdict is narrower: the proponent has not supplied a direct mirror; they have supplied a graphon-style re-modelling. If ChoCo accepts author-recognisable extensions, this anchor survives and the negative case loses.
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.