| paper | d4-conf-ecai-2016-0099 |
| 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}\)-hard, already for \(\tau=1\) and \(K=2\), and also for \(\tau=2\) and \(K=3\) with no unconditional antecedents. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 9
statement extracted from the paper’s text layer
Given finitely many types \(T\) with rational masses \(\mu_t>0\) summing to \(1\), integral local Boolean strategies, and finite commitment menus whose antecedents are rational-threshold predicates over type-level action shares, does there exist a positive-mass coalition allocation and a stable selection of commitments that forms a confirmed deal? The selected consequents must guarantee their antecedents, and each coalition member’s strategy must honor every commitment that could be triggered under every feasible action profile of the outsiders.
Use mass variables \(z_{t,a,S}\) for type \(t\) assigned integral strategy \(a\) and selected commitment subset \(S\), with \(\sum_{a,S} z_{t,a,S}\leq\mu_t\) and positive total selected mass. The question is whether such an allocation satisfies stability and safety for threshold guards over type-level action shares, with safety quantified over all outsider mass allocations.
An atomless threshold guard cannot represent a deal whose success turns on one specifically named outsider’s action, so the mirror excludes that subcase.
fatal: False
The mirror covers Proposition 9’s confirmed-deal existence problem. It leaves the separate results on commitment consistency and possible deals, and the results on Nash equilibria and negotiation protocols, unmirrored.
My strongest mirror is the paper’s confirmed-deal existence problem, anchored in Proposition 9, which the authors prove here. The proposition states that, given a Boolean game and a set \(C=(C_i)_{i\in N}\) of commitments, deciding whether any confirmed deal exists is \(\Sigma_2^P\)-complete. In the paper, a confirmed deal is a coalition \(J\) and a stable subset \(C'\subseteq C\), with \(J=\operatorname{deb}(C')\), for which there is a playable coalition strategy that honors the selected commitments and is safe against every strategy of agents outside the coalition. Stability requires the commitments’ consequents to entail their antecedents and to have a playable strategy. Safety requires that, whatever outsiders do, if one of a coalition member’s commitments is triggered, that member’s chosen strategy honors it. The completeness result concerns deciding whether such a deal exists.
Here is the continuous question I would put to a prover:
Continuous Confirmed-Deal Existence. An instance has a finite set \(T\) of agent types and rational masses \(\mu_t>0\) summing to \(1\). A type specifies the full information relevant to this problem: its controlled Boolean action bits, permissible local strategies, and finite menu of commitments. Each commitment has a consequent formula over its debtor’s own bits and an antecedent formula over aggregate conditions for its creditor types. Aggregate conditions are rational-threshold predicates—for example, whether at least a specified fraction of a type chooses an action with bit \(1\).
Does there exist a positive-mass coalition and a mass allocation of its members to integral local strategies and selected subsets of their commitment menus that forms a confirmed deal? A solution must give that allocation. Every selected consequent must hold for its assigned strategy; the coalition’s selected consequences must guarantee the selected antecedents; and each assigned strategy must honor every commitment of its type that could be triggered under any feasible action profile of the outsiders.
More explicitly, let \(x_{t,a}\) be the total mass of type \(t\) playing local strategy \(a\), with \(\sum_a x_{t,a}=\mu_t\). A witness specifies nonnegative masses \(z_{t,a,S}\), where \(S\) is a selected subset of type \(t\)’s commitments, and \(\sum_{a,S}z_{t,a,S}\leq\mu_t\). The total selected mass must be positive. Let \(\mathcal E(z)\) be all complete population profiles consistent with the selected mass, so \(x_{t,a}\geq\sum_S z_{t,a,S}\). Each positive-mass block assigned \((t,a,S)\) must satisfy every consequent in \(S\); every profile in \(\mathcal E(z)\) must satisfy the antecedent of every selected commitment; and, for every other commitment of type \(t\), every profile in \(\mathcal E(z)\) that triggers it must have its consequent satisfied by \(a\). Thus the deal remains safe as the outsiders’ mass varies. Each person still chooses an integral Boolean strategy; only the population allocation among strategies is fractional.
A plausible regime is a large federation of households coordinating around a shared infrastructure decision. Types could capture the features that determine households’ action options, goals, and commitment menus—for example, ownership and heating-system classes—while commitments are triggered by participation rates among relevant groups. There might be hundreds of thousands of households and tens or hundreds of such types. The case depends on that actual grouping being credible: if costs, preferences, or commitments vary idiosyncratically, they must appear in the type description and the support may grow substantially.
This keeps the paper’s central question intact: can a coalition make conditional commitments that guarantee a safe agreement despite what outsiders do? It changes how conditions are evaluated—from formulas over named agents’ Boolean actions to formulas over aggregate participation—because the society itself is now continuous. That is a substantive, visible co-modification, but it is one the authors could plausibly recognize as the population version of their confirmed-deal problem. It asks a computational question about deals in a continuum-agent Boolean game, not an equilibrium or outcome-continuity question.
For the unrestricted continuous problem, I would expect hardness to persist when the number of distinct types and the Boolean commitment agenda can grow. The relevant combinatorics can live in the types’ roles, guards, and commitment menus, rather than in the number of repeated copies. That is a hypothesis, not a consequence of Proposition 9: its reduction does not by itself establish hardness for the fractional-mass semantics above. A useful next question is whether fixed support size and a restricted threshold-guard language yield a tractable LP-based case.
I would mirror Proposition 9 alone. This covers the paper’s result on confirmed-deal existence, not its separate results on consistency, possible deals, or the later claims about Nash equilibria and negotiation protocols.
The weakest point is the change in trigger semantics. The paper’s antecedents refer to particular agents’ variables; this mirror uses conditions on population shares. Although that is natural for large populations and preserves the paper’s safety requirement, it can change which commitments activate and which coalitions count as confirmed deals. The mirror is strongest in settings where commitments really are triggered by participation levels.
Proposition 9 is a genuine computational result: confirmed-deal existence is \(\Sigma_2^P\)-complete. So the decisive objection that there is no result to mirror is unavailable.
The strongest objection is that the paper’s commitments are built around named agents. Each agent controls its own Boolean variables; an antecedent can depend on particular creditors’ variables; and the deal’s safety condition quantifies over every strategy of every outsider. In the general model, an agent’s interaction pattern can distinguish it from every other agent. Treating agents as repeated types then gives no compression: the complete type must include that pattern, and the support can grow with the population.
The proponent’s best repair is also the point where the mirror changes character. To keep support small, it assumes interchangeable copies with local strategies and replaces named-agent antecedents by thresholds on type-level participation. That is a coherent model of anonymous population contracts, but its core question is whether bulk participation can support a safe agreement. In the paper, it is whether particular agents can honor particular conditional commitments despite the choices of other named agents. In the continuum, an individual outsider has measure zero and cannot affect a threshold; the safety condition therefore loses the individual-trigger behavior that motivates it in the paper. The authors might welcome this extension, but the paper gives little reason to treat it as the same problem.
There is a further mismatch in the existence question. The finite problem accepts any nonempty coalition, including a single agent. The proposed continuum version accepts any coalition of positive mass, however small. That excludes finite deals whose normalized mass vanishes, while allowing an arbitrarily small sliver to witness a deal. A minimum participation share would make the question more operational, but it adds a quorum condition absent from Proposition 9.
These points make the mirror less direct than the proponent’s framing suggests, but they do not establish that it is unworthy of study. A large federation with genuinely anonymous, threshold-triggered commitments is plausible, and a mass floor is a natural modelling choice. The negative case is weakest there: the best mirror is a real extension of the paper’s setting, even if its fit to this particular result is not compelling.
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.