| paper | d4-conf-atal-2015-0136 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even with \(\tau=K=1\) and an initially equilibrium target. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given finitely many module types \(T\) with rational masses \(\mu_t\), Boolean action spaces \(A_t\) encoded by private local variables, goal formulas \(\gamma_t\), action costs \(c_t\), and initial endowments \(e_t^0\), together with a rational target action-mass profile \(x_{t,a}\) satisfying \(\sum_{a\in A_t}x_{t,a}=\mu_t\) and \(c_t(a)\le e_t^0\) whenever \(x_{t,a}>0\), let \(E=\sum_t\mu_t e_t^0\). Does there exist a measurable redistribution \(b\) over the unit-mass population, with \(\int b=E\), that keeps the assigned target action affordable almost everywhere and lets a positive mass of agents whose target action falsifies \(\gamma_t\) afford some action \(a'\in A_t\) satisfying \(\gamma_t\)? Each agent has private module variables, so a unilateral change does not affect another agent’s goal.
An atomless population of resource-bounded Boolean modules, grouped by type and private goal/action-cost template. The planner reallocates a fixed per-capita supply \(E\) through measurable individual budgets \(b\), preserving target affordability while enabling a positive mass of target-failing modules to afford goal-satisfying actions.
Covers the FEASIBLE ELIMINATION half of Proposition 7 for repeated modules with private goals; leaves out arbitrary cross-agent goal dependencies, the other elimination and construction results, and the dynamic result.
The strongest anchor is Proposition 7, proved in this paper: ELIMINATION and FEASIBLE ELIMINATION are both NP-complete. ELIMINATION asks, given an electric Boolean game and a feasible outcome, whether some redistribution of the total endowment makes that outcome cease to be a Nash equilibrium. FEASIBLE ELIMINATION asks the same while requiring the outcome to remain feasible after redistribution. The paper proves hardness by reducing the complement of pure Nash equilibrium recognition in Boolean games, which it cites as coNP-complete [6]. For membership in NP, it uses a polynomially representable redistribution and checks for infeasibility or a profitable feasible deviation.
I would mirror the FEASIBLE ELIMINATION half. Consider a large deployment of resource-limited automated modules: many agents run the same software, with a small number of hardware or policy types. Each type \(t\) has mass \(\mu_t\), a fixed set of local Boolean variables, an action set \(A_t\), an action cost \(c_t(a)\), and a dichotomous goal formula. Agents may also respond to shared Boolean signals determined by population rates—for example, whether the fraction in a particular operating mode exceeds a threshold. This preserves strategic goals and resource-limited choices while giving the cross-agent interaction a natural form for a repeated population. The regime is one with many modules and relatively few types, \(\tau\).
Here is a decision problem that could be handed to a prover. Call it Continuous Feasible Elimination. An instance gives the finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), the local actions, costs and goals, a rational total resource supply \(E\) per capita, and a target profile \(x\), where \(x_{t,a}\ge 0\) is the mass of type \(t\) assigned action \(a\) and \(\sum_{a\in A_t}x_{t,a}=\mu_t\). Shared signals are defined by rational threshold tests on these masses. The question is whether there is a measurable allocation of endowment \(b\) across agents, with total \(\sum_t\int b_t(s)\,ds=E\), such that the target action is affordable almost everywhere and a positive mass of agents can afford a unilateral action that changes their goal from false to true. A unilateral change leaves the shared signals fixed, since an individual has zero mass. The target is therefore feasible but not a Nash equilibrium in the continuum sense. Because the types have finitely many actions and costs, an allocation witness need only distinguish the finitely many relevant affordability thresholds.
The authors would, I think, recognize this as their problem in a high-multiplicity regime: agents still control Boolean choices, seek goal satisfaction, face action costs and endowment constraints, and a central planner redistributes resources to change equilibrium status. The scenario makes agents interchangeable precisely in the respects the model uses. It also retains meaningful strategic interaction through the shared signals.
There is a direct reason to expect hardness to transfer. Take one type of mass \(1\), with zero costs and total endowment \(E=0\), and no shared signals. Give each agent local variables for a Boolean formula \(\psi\), and make \(\psi\) its goal. Put the target at a valuation where the goal is false; a fresh conjunct \(z\), set false in the target, ensures this if needed. A positive mass can profitably deviate exactly when \(\psi\) is satisfiable. Thus the hardness source in Proposition 7 survives even when the whole population is one type: the hard combinatorics lie in the Boolean action and goal, not in the number of distinct agents. I would expect this mirror to be Class B, with hardness transferring from the discrete problem.
The scope is deliberately just the one-shot feasible-elimination result in Proposition 7. It does not claim a mirror for the paper’s construction or dynamic results. Further questions include whether the mirror remains hard when each type controls only a bounded number of variables, and how aggregate interaction signals affect its complexity.
The weakest point is that the paper allows goals to refer to individually named variables, while this mirror uses local variables and shared aggregate signals; moreover, an infinitesimal deviation cannot change those signals. That is a real restriction on the paper’s general model. The case still holds for the proposed regime because the matching hardness result already has a one-type, no-interaction subcase, while aggregate signals provide a plausible way to add system-level interaction among many repeated agents.
Proposition 7 is a real computational anchor, so the strongest objection is about whether its strategic problem survives aggregation. In the paper, an outcome is a complete assignment to individually controlled variables, and a player’s goal may refer to variables controlled by other named players. The feasibility of a unilateral deviation therefore depends on the *joint* assignment in that particular game. A distribution over type-action masses generally loses those within-game correlations.
The proposed shared-signal model does not restore them. It changes formulas over jointly assigned Boolean variables into goals evaluated against aggregate thresholds. In an atomless population, one agent cannot change such a threshold; that is a coherent mean-field game, but it changes the deviation semantics that Proposition 7 studies. A more faithful mirror would replicate whole finite games and keep each player’s role and opponents’ target choices as context. That can preserve the equilibrium question, but the object being distributed is then a population of game copies, with resource allocation inside each copy. It is a substantially different model from a society described just by masses of agent types.
The one-type SAT construction survives this objection as a formal possibility: repeat agents with the same local goal formula, give each its own renamed local variables, and ask whether a positive mass can deviate from a target where the goal is false. But its hardness comes entirely from whether that one local formula has a satisfying assignment. Redistribution, interaction among agents, and population mass do no work. That makes it weak evidence for a useful continuous *population* version of Proposition 7, even though it is a legitimate high-multiplicity instance if repeated local modules count as the authors’ problem.
So the best negative case is that the paper’s main strategic structure—equilibrium in a game of named agents—does not pass to type-action masses without either losing within-game information or adopting a richer population-of-games model. The proponent’s model changes the interaction structure; the more faithful local-goal mirror collapses to formula satisfiability. Still, I cannot honestly rule out the replicated-copy mirror: many identical resource-bounded modules are a plausible regime, and Proposition 7 gives a computational question for it. The case against “no worthwhile mirror in any scenario” is therefore weak at its universal point.
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.