| paper | d4-conf-atal-2014-0189 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Propositions 2 and 4 are genuine computational hardness results, but their proposed mirrors change both the stability concept and the effectivity measure. Stable allocations can have zero ambient volume, so the stated convention can make the attack ineffective even when it changes which stable outcomes satisfy the threshold. The large-community setting is plausible, but the anchors do not preserve the paper’s question as formulated.
fails bit b-changes — the continuum limit changes the question
The proposed measure is usually degenerate when stable allocations occupy lower-dimensional sets, and uniform sampling of finite partitions need not converge to uniform volume; repairing the measure would change the effectivity problem, while the nonatomic stability condition also changes the paper’s atomic deviation model.
fatal: True
The proposed anchors concern Propositions 2 and 4; they leave the characterizations in Propositions 1, 3, 5, 6, 7, 8, and 9, the empirical study, and the remaining analysis untouched.
There is a credible continuous mirror here, but it needs a specific regime. I would study a large population of users forming a modest number \(K\) of persistent online communities or guilds. Players care about the mix of play styles in a community, not the identity of each ordinary member. There are many users but relatively few complete preference types: \(\tau\) stays small compared with the population, and each type \(t\) has mass \(\mu_t\), with \(\sum_t\mu_t=1\). One tagged user \(m\) remains exceptional so the paper’s Sybil attack still has an actor. This is plausible for composition-based communities; it is a poor fit for a seven-person committee or a game where preferences hinge on named individuals.
A concrete model uses \(x_{t,k}\), the mass of type \(t\) assigned to community \(k\), as its allocation variable. Each type’s preferences are over the mass composition \(q_k=(x_{1,k},\ldots,x_{\tau,k})\) and whether a tagged identity is present. For a finite input description, I would use rational affine utilities over those profiles. Stability means no positive mass of a type prefers another community, and neither tagged identity wants to move. A single user can still deviate, but their move changes the mass composition by zero in the limit. The Sybil identities remain tagged individuals with their own preferences, rather than being treated as positive mass.
The paper’s objective also needs a continuous version. For a fixed set of \(K\) communities, aggregate allocations lie in a product of simplices. I would select uniformly by volume from the Nash-stable allocations and define \(r^\theta\) as the volume of satisfactory stable allocations divided by the volume of all stable allocations, with value zero when the stable set has zero volume. That parallels the paper’s uniform draw from stable partitions. It is a specified selection rule, not a canonical fact about continua; the paper itself allows other rules when the manipulator’s goal makes sense.
My lead is Continuum Constructive Sybil Effectivity, mirroring Proposition 2, proved in this paper. Proposition 2 states that it is NP-hard, given an RIRLC hedonic game \(G\), an agent \(m\), and a threshold coalition \(C_\theta\), to decide whether the paper’s constructive manipulation is effective for \(m\) relative to \(C_\theta\). That attack adds one Sybil \(s\), makes \(m\) indifferent among coalitions, and gives \(s\) \(m\)’s original preferences with \(m\) replaced by \(s\). “Effective” means the attack strictly increases \(r_G^\theta\), the fraction of Nash-stable partitions satisfactory to \(m\). The proposition is proved here by reduction from deciding whether a game has any Nash-stable partition, an NP-complete problem cited to Ballester [3].
In the continuous problem, the input is the rational mass vector \(\mu\), the \(K\) communities, the type utilities, \(m\)’s original utility and threshold profile \(\theta\), and the corresponding base and post-attack stable-allocation sets. The question is whether the constructive attack strictly raises the volume share \(r^\theta\). A solution is a yes/no answer; stable allocations witnessing a positive numerator can serve as certificates for the relevant feasibility subquestions. This preserves the attack and the “chance of reaching an acceptable outcome” objective, while replacing individual coalitions with community compositions. I would provisionally expect the exact problem to be Class C when \(\tau\) and \(K\) vary: it compares volumes of stability regions that are finite unions of rational polyhedra. That is a reason to investigate volume computation, not a hardness result established by Proposition 2. With \(\tau K\) fixed, I would expect a tractable geometric algorithm.
A second strong anchor is Continuum Destructive Sybil Effectivity, mirroring Proposition 4, also proved here. Proposition 4 states that it is NP-hard to decide whether the paper’s destructive manipulation is effective on an RIRLC game for a given \(m\) and \(C_\theta\). The attack leaves \(m\)’s preferences unchanged and adds one Sybil whose preferences veto coalitions containing \(m\) that fail the threshold. Proposition 3 shows why this attack works: it is effective exactly when the original game has at least one satisfactory stable partition and at least one stable but nonsatisfactory partition; after the attack, every stable partition is satisfactory. Proposition 4 proves the hardness by reduction from the same cited stable-partition existence problem.
The continuous version has the same mass-and-utility input, but applies that veto preference to the tagged Sybil. It asks whether the attack strictly raises \(r^\theta\) under the volume lottery. A solution is a yes/no answer; in particular, before the attack the satisfactory and nonsatisfactory stable regions must both have the volume needed for a strict probability increase. After the attack, all stable allocations are satisfactory, if any exist. I again provisionally expect Class C for the exact variable-dimension volume comparison, with a tractable fixed-dimension case. A useful follow-up is whether the volume test admits an approximation scheme, or whether the simpler question “does each region have positive volume?” is tractable.
The two propositions are worthwhile anchors on their own: Proposition 2 studies creating satisfactory outcomes, while Proposition 4 studies eliminating unsatisfactory ones. Proposition 2 is my lead because its reduction directly connects attack effectivity to the existence of stable outcomes. The paper’s NP-hardness does not by itself show that either continuous problem is hard. Its reduction can use many individually distinct preference lists, so the hard combinatorics may disappear when many users collapse into a few composition-based types. That is the central question for the mirror: can hardness be encoded with small \(\tau\), or does it depend on population multiplicity?
The soft spot is substantial. The paper ranks coalitions of named agents and counts stable partitions; this mirror ranks mass compositions and measures a region of stable allocations. The volume lottery is a deliberate, explicit continuation of its outcome-selection rule, but it need not be the limit of uniform sampling from finite-agent partitions. Nor does a single tagged attacker fit a model in which every agent must be represented only by a positive-mass type. I think the mirror is plausible for large composition-based communities, where one account can still act strategically against a population, but it is a regime-specific extension rather than a restatement of the paper’s unrestricted model.
I would not argue that the paper lacks computational results: Propositions 2 and 4 are genuine NP-hardness results, and the cited high-multiplicity literature is evidence for a continuous regime, not an objection to one. The stronger negative case is that both propositions depend on a feature the proposed continuum does not carry over cleanly: the *fraction of stable outcomes* that satisfies the attacker.
For Proposition 2, the paper counts finite Nash-stable partitions before and after the constructive attack. The proposed mirror replaces that count with volume over fractional allocations. But Nash stability for individuals in a nonatomic population should be expressed through infinitesimal deviations: each type uses only communities that maximize its utility at the current composition. With generic affine utilities, splitting a type across communities requires utility ties, so stable allocations will often lie on lower-dimensional sets and have zero volume in the allocation space. The proposed convention then assigns zero to the probability both before and after the attack, even if the attack creates satisfactory stable allocations. A measure on the stable set’s own dimension might avoid that problem, but components can have different dimensions and there is no canonical way to compare their measures.
Proposition 4 has the same problem. Its result is about an attack changing the *share* of stable partitions that satisfy the threshold. Saying that the attack makes every remaining stable allocation satisfactory does not establish a strict increase in volume share if the original or resulting stable set has zero volume. Replacing the ratio with “does a satisfactory stable allocation exist?” or “does the satisfactory region have positive volume?” gives a well-posed alternative, but it is no longer the paper’s effectivity question. A more faithful probability could come from limits of finite populations, but uniform sampling of finite partitions induces weights based on how many individual partitions produce each aggregate allocation. Those weights are generally entropy-shaped, not uniform volume. The result would depend on the chosen finite-population approximation and sampling rule.
There is also a mismatch in the attack itself. In a genuinely anonymous, composition-based population, one attacker and finitely many Sybils have zero mass, so they do not change community composition. If their presence changes ordinary agents’ utilities anyway, then the attack works through a named-identity switch affecting the whole population—a special tagged-player model, not an aggregate mass effect. Giving the attacker or Sybils positive mass avoids that degeneration, but turns the attack into manipulation by a bloc of society. That could be an interesting problem, though it changes the mechanism these propositions study.
These objections defeat both anchors as stated and show why the proposed volume version needs more modeling work before it supports the claimed complexity questions. They do not establish that no worthwhile mirror exists in any scenario. Large communities with composition-based preferences are plausible, and a carefully specified type-based hedonic model could be worth studying. The honest weakness in the negative case is that such a model may be a useful new problem even if Propositions 2 and 4 do not carry over as cleanly as the proponent suggests.
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.