| paper | d4-conf-ecai-2023-0446 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 6 is a clear computational result, and the proposed mass-Penrose question is precisely stated over a population of types. But its random turnout propensities do not arise from the paper’s independent uniform-subset lottery, and deleting a type edge removes a bloc-wide channel rather than one individual edge. A bloc-level version remains plausible, so the case does not settle whether this is a question the authors would recognize.
fails bit b-changes — the continuum limit changes the question
The paper’s independent coin-flip coalition lottery concentrates each type’s selected fraction near one half at high multiplicity, whereas the proposal uses order-one random propensities; its type-edge deletion also removes a whole bloc-to-bloc channel instead of one edge.
fatal: False
It is undecided whether the authors would recognize the proposed bloc-level problem as their edge-control question: it replaces the paper’s coalition lottery and single-edge action with random type-level turnout and channel removal. Author acceptance of those co-modifications would settle whether the mirror survives.
The proposal covers only the Penrose–Banzhaf edge-deletion increase and decrease results in Theorem 6; it leaves the Shapley–Shubik results, edge additions, and maintenance results aside.
The strongest case is a type-level version of control by deleting edges for Penrose–Banzhaf power. The paper’s anchor is Theorem 6, proved here: in graph-restricted weighted voting games, deleting edges to increase or to decrease a distinguished player’s Penrose–Banzhaf index is PP-hard; the same is true for the Shapley–Shubik index. The reductions already work with a deletion limit of one edge. I would mirror the Penrose–Banzhaf cases. The theorem establishes hardness for the finite game; it does not establish that the hardness survives this continuous model.
Take a large federated voting body with many members but relatively few complete agent types. A type \(t\) specifies a member’s per-capita voting weight and communication profile. Members of the same type are indistinguishable for the game. Let \(\mu_t\) be the fraction of the population of type \(t\), with \(\sum_t\mu_t=1\), and let \(\tau\) be the number of types. A graph \(H\) on the types records communication compatibility: members of a type can communicate among themselves, and an edge between two types means their members can communicate across those classes. Deleting a type edge models removing that channel between blocs. The population can be large while \(\tau\) remains modest; the target is an individual representative of a type, whose per-capita influence we measure.
Here is one precise question to hand a prover:
Mass-Penrose edge-deletion control. An instance consists of the finite type set \(T\), positive binary-rational masses \((\mu_t)_{t\in T}\), nonnegative rational per-capita weights \((w_t)_{t\in T}\), a rational quota \(q\), a type graph \(H=(T,E)\), a distinguished type \(p\), and a direction, increase or decrease. For a coalition mass vector \(x\), define \(v_H(x)=1\) exactly when some connected set \(K\) of types with \(x_t>0\) for every \(t\in K\) satisfies \(\sum_{t\in K}w_tx_t\ge q\). Otherwise define \(v_H(x)=0\).
To make coalition uncertainty explicit, draw the other coalition’s mass of each type independently and uniformly from its available mass interval. A distinguished individual has vanishing mass in the continuum, so use the first-order pivotality density
\[
b_H(p)=\lim_{\epsilon\downarrow0}\frac{1}{\epsilon}
\Pr\!\left[v_H(X^{(\epsilon)}+\epsilon e_p)>v_H(X^{(\epsilon)})\right],
\]
where \(X^{(\epsilon)}_t=\mu_tU_t\) for \(t\ne p\), \(X^{(\epsilon)}_p=(\mu_p-\epsilon)U_p\), and the \(U_t\) are independent uniform random variables on \([0,1]\). The question is whether there is an edge \(e\in E\) such that deleting it strictly changes \(b_H(p)\) in the specified direction. A yes-instance has a witnessing edge.
This keeps the paper’s underlying question: does restricting communication change a particular player’s pivotal influence in a graph-restricted weighted voting game? The index is a continuum form of probabilistic pivotality: the unscaled probability that an infinitesimal player is decisive vanishes, so the question uses its first-order density. Type-level edges are a natural co-modification for a high-multiplicity setting: the changed channel applies across two homogeneous classes. One finite approximation samples turnout through a shared random propensity for each type; as the number of members per type grows, the selected fractions approach the random masses above.
I would expect the variable-\(\tau\) problem to be continuum-specifically hard (Class C), while its fixed-\(\tau\) slice should be tractable. For each type graph, the winning and pivotal regions are described by finitely many linear inequalities over a rational box; \(b_H(p)\) is a boundary-volume derivative. With fixed \(\tau\), one can enumerate the relevant connected type sets and compute these fixed-dimensional volumes and derivatives. When \(\tau\) grows, exact volume comparisons and the edge choice may become hard. That is a reason to investigate the question, not a hardness proof. In particular, Theorem 6’s comparison of discrete subset counts does not itself prove PP-hardness here: fractional coalition masses replace those counts with geometric volume calculations.
The mirror covers only Theorem 6’s edge-deletion results for Penrose–Banzhaf influence. It does not claim a continuous Shapley–Shubik analogue or cover edge additions and maintenance. Further questions include whether the mass problem is PP-hard, whether it is fixed-parameter tractable in \(\tau\), and how its answer changes under other explicit coalition-mass distributions.
The weak point is that the paper’s Penrose–Banzhaf index samples every discrete coalition uniformly. The mass model uses random participation fractions, and its influence measure is a normalized limit; neither is the paper’s exact finite index. A referee might reject that as too large a change. The case for it is that it retains the same player-level pivotality question and communication-control operation while making uncertainty over population-scale coalition mass part of the model. The authors would have to accept that as their analogue.
Theorem 6 is a real anchor: deleting one edge can change a player’s Penrose–Banzhaf power, and deciding whether a helpful or harmful deletion exists is PP-hard. The difficulty is finding a continuous population model that still asks that question.
The proposed mass-Penrose index changes the coalition lottery. In the finite Penrose–Banzhaf index, each other player joins independently with probability \(1/2\). If type \(t\) has \(n_t\) members, its selected fraction is \(K_t/n_t\), where \(K_t\sim\mathrm{Bin}(n_t,1/2)\); as \(n_t\) grows, that fraction concentrates at \(1/2\). The proposal instead assigns each type an independent \(U_t\sim\mathrm{Unif}[0,1]\), producing order-one variation in its coalition mass. That is a coherent alternative uncertainty model, but it does not arise as the high-multiplicity limit of the paper’s index. Shapley–Shubik has yet another natural limit: the fractions of each type preceding a player in a random ordering approach a common random rank fraction, rather than independent uniforms.
The target player also has vanishing mass. Under independent turnout, with fixed per-capita weights and quota proportional to population, that player can be pivotal only when coalition weight lies in a narrow window near quota. The probability of that event is typically of order \(N^{-1/2}\) when quota is centered near expected weight, and can be exponentially smaller away from it. A nonzero limiting influence therefore needs a choice of normalization and quota scaling. The proposed derivative \(b_H(p)\) supplies one, but it is a modeling choice; it does not follow from the paper’s index. Its finite approximation with shared type propensities confirms that choice rather than recovering the standard Penrose–Banzhaf lottery.
The graph operation creates a separate mismatch. A type graph with an edge between two types naturally represents a block of links between their members. Deleting that type edge removes the whole block. Theorem 6 allows deletion of one individual edge. In large, densely connected type classes, a single edge is usually redundant: for example, deleting one edge from a clique changes connectivity only for coalitions containing its endpoints and no other clique member, an exponentially rare event under uniform coalition sampling. Where sparse individual links remain consequential, the neighborhood and position of each player matter; a type distribution alone does not record that topology. A single bridge between two large groups illustrates the problem: its endpoints can have zero population mass while their edge still changes which coalitions are connected.
The strongest repaired version would retain finitely many voter blocs, give each bloc a random participation propensity, and allow interventions on bloc-to-bloc communication channels. That could define an interesting computational problem. It would, however, pair a new influence measure with a macro-scale channel-removal operation. Whether the authors recognize that as their problem is the decisive uncertainty; its PP-hardness or tractability would be a result to investigate, not an objection.
So the negative case is that Theorem 6’s named problem has no canonical continuous counterpart preserving both its coalition lottery and its single-edge intervention. The mass-Penrose proposal chooses a different lottery and a different scale of control, while more faithful individual-level limits need extra topology and normalization. This makes the anchor substantially weaker than it first appears. It does not establish the requested universal claim: the bloc-level version could still be a worthwhile mirror if the authors accept those co-modifications.
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.