| paper | d4-conf-ijcai-2016-0136 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: NP-hard for every fixed \(k\in\{1,\ldots,6\}\), already with \(\tau=2\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given a finite-support rational distribution over initial belief types, a target formula φ, a controllable portion of the mass, and a common policy \(R^k_{Δ_{d_D,Σ}}\) for some \(k\in\{1,\ldots,6\}\), does there exist a mass transfer from controllable types \((B,e)\) to bases \(B'\) with \(B'\preceq_\varphi B\) such that, under complete interaction and mass-weighted merging, every resulting positive-mass cohort's cycle outcome entails φ?
Represent an atomless complete forum by a finite-support rational distribution μ over types \((B,e)\), where \(B\) is an initial belief base and \(e\) records control eligibility. A plan reallocates eligible mass only to bases \(B'≼_φ B\); each update uses mass-weighted Δ, scoring an interpretation by the mass of bases it satisfies.
The weighted Δ update and mass-transfer interventions need new semantics, so Propositions 7 and 12 do not establish strong monotonicity for the continuum; the proponent's budgeted minimum-cost objective also goes beyond those results.
fatal: False
The mirror covers control feasibility from Proposition 7, instantiated by Proposition 12's complete-graph policy class. It leaves the promotion-lattice results, failure examples, detailed outcome characterizations, and complexity classification unaddressed.
The strongest honest positive case is narrow: a large, nearly homogeneous population of people who all receive the same discussion, with a small number of distinct initial belief bases. But there is an anchor problem. The paper gives no named result about complexity—nothing classifies a problem as polynomial-time solvable, hard, fixed-parameter tractable, or similar. Its closest results are about control, but they do not establish such a classification.
The most relevant are Proposition 7 and Proposition 12, both proved in this paper. Proposition 7 says that in any BRG satisfying strong monotonicity, if replacing every controllable agent’s base by the target formula fails, then no control strategy succeeds. Proposition 12 says that every complete BRG using any one of the six revision policies \(R^k_{\Delta_{dD,\Sigma}}\), for \(k\in\{1,\ldots,6\}\), satisfies strong monotonicity. Together they give a useful shortcut for the paper’s control question in that restricted setting. They are the closest thing to an algorithmic anchor, but neither states a complexity result, so neither qualifies as an anchor under the stated requirement.
The natural continuous setting would be a large deliberative forum in which everyone receives the same discussion and applies the same revision policy. A type would specify an agent’s initial belief base, policy, and control eligibility and cost. Mass would be the fraction of participants of that type. This is plausible when the issue vocabulary is fixed and only a few belief bases occur, even though the number of participants is very large. The complete-network assumption is restrictive, but it matches the scope of Proposition 12.
A concrete follow-on problem—not a result established by the paper—would be Minimum-Mass Promotion Control. Its instance consists of a finite propositional vocabulary, a rational distribution \(\mu\) over types, a target formula \(\varphi\), a common policy \(R^k_{\Delta_{dD,\Sigma}}\), and a budget \(K\). A solution transfers controllable mass from each original base \(B\) to bases \(B'\) satisfying \(B\land\varphi\models B'\models B\lor\varphi\), with total intervention cost at most \(K\). Define the continuum’s merging operator by letting each interpretation receive the total mass of bases it satisfies, and use the corresponding weighted profile in the BRG update. The question is whether some such transfer makes every positive-mass cohort eventually accept \(\varphi\), meaning its cycle outcome entails \(\varphi\).
This preserves the paper’s central control question and its promotion notion while making population mass the object being controlled. It does not dumb down the goal to a one-step vote: agents still update through the BRG dynamics. Proposition 12 motivates asking whether strong monotonicity survives this weighted model; if it does, Proposition 7’s basic-strategy shortcut may survive too. I would expect the dynamics’ dependence on the propositional vocabulary to remain a likely source of hardness, rather than assume that making the population continuous makes the whole problem tractable. The paper itself does not settle that prediction. Follow-on questions include whether the weighted analogue of strong monotonicity holds and whether minimum-cost promotion control has an efficient algorithm.
The weakest point is that this is a new continuous extension of a control result, not a mirror of a named complexity result in the paper. Also, the passage from finite complete graphs to weighted masses needs proof: when a focal agent’s own vote disappears into the continuum, ties in the drastic-distance merging operator may behave differently. So the positive case supports a plausible research direction, but it cannot supply the requested anchor-led complexity case.
The strongest case against is that neither named anchor is a computational result of the kind ChoCo is meant to continuize. Proposition 7 says that, under strong monotonicity, the basic control strategy is sufficient. Proposition 12 identifies a class of finite BRGs with that property. They establish semantic facts about when a control strategy works; they do not classify the complexity of a decision or optimization problem. The paper gives no running-time, hardness, approximation, or parameterized result for control.
There is a plausible high-multiplicity setting here, so I would not argue that mass is meaningless. A large deliberative forum with a fixed vocabulary, a complete communication graph, and many people sharing initial beliefs and revision policies could have types described by those features, plus control eligibility and cost. Its population distribution would be a sensible object.
But the direct continuous questions raised by the two propositions are still semantic. A mass version of Proposition 7 would ask whether strong monotonicity makes the basic strategy sufficient when interventions change positive amounts of each type. A mass version of Proposition 12 would ask whether that property holds under a weighted \(\Delta_{d_D,\Sigma}\) update. Both may be worth proving. Neither is a complexity result, and moving from named agents to mass transfers changes the intervention being quantified over.
Minimum-Mass Promotion Control is the strongest attempt to turn those results into a computational anchor. It could be a worthwhile new problem, but it adds an objective and formal choices the propositions do not settle: intervention costs, permitted transfers, the weighted update, and the input representation. The paper mentions cost-sensitive control as a possibility; it does not state or analyze a minimum-cost control problem. A complexity theorem for that extension would be a new contribution, not a continuous mirror of Propositions 7 or 12. The same applies if one builds a decision version with a budget.
So I would reject the proponent’s *anchor-led* case: its named results motivate a mass-based extension but supply no computational classification to mirror. The negative case is weaker against the broader claim, though. The high-multiplicity forum scenario is credible, and a costed continuous control problem could be valuable to the programme. I cannot honestly rule out that research direction; I can only say that this paper’s named results do not establish its computational case.
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.