| paper | d4-conf-ecai-2020-0320 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 5 is a clear computational result, but the proposed mirror does not make population mass affect its decision: the graph uses support roles and the factor \(\mu_i\) cancels. Treating a positive-mass type as jointly controlling fake accounts changes the theorem’s unilateral manipulation question. No stated continuous question survives for this anchor.
fails bit b-changes — the continuum limit changes the question
The proposed mirror attempted to cover Theorem 5; it leaves the paper’s other results unmirrored.
The only anchor I would use is Theorem 5, proved in this paper. It says BENEFICIAL-SPLIT is NP-complete: given an MCST problem with a monotonic weight function, a partition \(S\) of the nonparticipating nodes among agents, and a designated agent \(i\), decide whether some subset \(S'_i\subseteq S_i\) makes the Bird cost of \(i\) before manipulation greater than the sum of the Bird costs of \(i\) and those added accounts afterward. The paper proves membership in NP and gives a reduction from 3-SAT. I would not add the paper’s price-of-anarchy or rule-existence results as computational anchors.
My lead mirror is COHORT-BENEFICIAL-SPLIT\(_\infty\). The regime is a large service population grouped into a relatively small number \(\tau\) of account-role types: members of a type share the same true terminal role, edge-cost profile, and eligibility to use fake-account roles. A type’s mass \(\mu_t\) is its fraction of the population. This could describe repeated service users represented by standardized connection classes, with a large association or other massful cohort controlling accounts on its members’ behalf. The paper itself motivates MCST agents as groups of accounts, which makes that cohort interpretation plausible. Here the number of represented users can be much larger than \(\tau\); the 3-SAT gadget still needs \(\tau\) to grow with the formula.
Precisely, an instance consists of a finite complete graph of account roles and a source, rational nonnegative edge weights \(w\), a rational distribution \(\mu\) over true roles, a designated role \(i\) with \(\mu_i>0\), and a set \(A_i\) of currently inactive fake-account roles available to that cohort. Require the MCST cost to be monotone as participating roles are added. Let \(P=\operatorname{supp}(\mu)\), and let \(b_r(Q)\) be role \(r\)’s Bird charge in the MCST on active roles \(Q\), using the paper’s averaging convention when there are multiple MCSTs. The decision is whether there is some \(B\subseteq A_i\) such that
\(C_i^\mu(B)=\mu_i\sum_{r\in\{i\}\cup B} b_r(P\cup B)<\mu_i b_i(P)=C_i^\mu(\varnothing).\)
A solution is the chosen subset \(B\), with the Bird charges on the before-and-after graphs establishing the strict inequality. The mass factor makes this the cohort’s total bill; the per-capita cost comparison has the same sign. This covers only Theorem 5’s search for a beneficial Bird-rule split.
I expect hardness to transfer in this mirror. The paper’s reduction encodes Boolean choices in the available fake-account roles and their cost relationships. Those choices remain discrete, and their number grows with the role graph; distributing the users across massful types does not erase them. In the mirror’s finite-support domain, the paper’s instances embed by making each reduction role a positive-mass type. That makes this a Class B style case: hardness comes from the account-role structure, not from population multiplicity. Natural follow-up questions include whether the problem is tractable under structural restrictions on the role graph, and whether useful approximation guarantees exist for the best achievable reduction in cohort cost.
The weak point is substantial: this is a type-quotient, cohort mirror. The paper gives each participating account its own vertex, while this model aggregates interchangeable users into roles and treats the cohort’s added aliases at the role level. Mass aggregates the bill, but it does not continuously change which roles are present; the Bird rule depends on active nodes. An author might reject the quotient as changing the semantics of split manipulation. I still think it is the strongest honest positive case because the type roles retain the MCST, Bird rule, monotonicity condition, and fake-account choice that Theorem 5 studies.
Theorem 5 is a genuine computational anchor: it proves BENEFICIAL-SPLIT NP-complete. So the negative case cannot rest on the paper lacking a complexity result, or on the hardness surviving.
The proposed mirror’s problem is that its mass does no computational work. The active graph is built from \(P=\operatorname{supp}(\mu)\), and the deviation is still a subset \(B\) of finitely many fake-account roles. The factor \(\mu_i\) multiplies both sides of the comparison and cancels; the other type masses do not enter it. This is the paper’s finite search with a continuous label attached. If mass is meant to represent many actual account holders, each holder contributes a node to the spanning tree. Collapsing them to one role node can change both the tree and its Bird charges, so the proposed role quotient does not preserve the original cost-sharing problem.
Trying to preserve individual ownership exposes the deeper mismatch. In an atomless population, one person’s split has zero mass, while the paper’s action adds discrete vertices that can change the tree. Giving an entire positive-mass type one shared split decision preserves an effect, but turns unilateral manipulation into cohort coordination and requires a new definition of a mass-valued MCST and Bird allocation. A hybrid with a focal individual and a continuous background is conceivable, but it also needs a mixed discrete/continuum tree model; the paper supplies no such bridge, and its hardness gadget remains a finite account-choice problem.
That is a strong objection to the mirror as stated, but it does not establish that no worthwhile mirror exists. The paper itself motivates agents as groups of accounts, so a carefully defined cohort model could be recognizable to the authors and could make mass affect the network cost. I would reject the proposed formulation as a continuous-population mirror; I would not claim the universal negative is settled without first testing that mass-valued MCST model.
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.