| paper | d4-conf-aaai-2021-1896 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 0.20
statement extracted from the paper’s text layer
Given a population scale \(N\), a target set \(T_N\) whose size grows proportionally to \(N\), rational payoff data, and \(\epsilon>0\), let defender types \(\Theta\) have rational shares \(\mu_\theta\) summing to one and per-defender resource rates \(\rho_\theta\). The input includes a finite candidate coalition structure \((q^j,x^j)_{j=1}^r\), with rational type-mass vectors satisfying \(\sum_j q^j=\mu\), coverage vectors \(x^j\in[0,1]^{T_N}\), and \(\sum_{t\in T_N}x_t^j\le N\sum_\theta\rho_\theta q_\theta^j\). Its overall coverage is \(c_t=1-\prod_j(1-x_t^j)\), which gives each type its baseline utility \(u_\theta\) under the paper's attacker response and pessimistic tie-breaking. Decide whether there is no nonzero deviating mass vector \(d\le\mu\) and feasible deviation coverage \(x\), with \(\sum_t x_t\le N\sum_\theta\rho_\theta d_\theta\), such that every type with \(d_\theta>0\) gains at least \(\epsilon\) for every feasible revenger coverage \(y\), where \(\sum_t y_t\le N\sum_\theta\rho_\theta(\mu_\theta-d_\theta)\) and the resulting coverage is \(c'_t=1-(1-x_t)(1-y_t)\).
A continuum of defender mass over types that specify payoff data and resource rates. A described coalition receives type mass \(q^j\), pools its \(N\)-scaled resources, and chooses coverage \(x^j\); the attacker and each type's payoff and tie-breaking rule remain those of the paper.
The stated budget uses \(\sum_\theta \rho_\theta q_\theta\) for unit mass, omitting the population-scale factor needed to represent \(N\) defenders with those per-defender resource rates.
fatal: False
The mirror covers Theorem 0.20's \(\epsilon\)-core membership test for a given coalition structure. It leaves Theorem 0.11's grand-coalition construction, Theorem 0.12's hardness for non-grand core structures, and the other efficiency and deviation results outside its scope.
The strongest mirror I trust is a continuous defender-population version of core-membership testing, anchored in Theorem 0.20, proved in this paper. The theorem says that deciding whether a given coalition structure is in the \(\epsilon\)-core takes time \(O(2^\lambda\operatorname{poly}(m,n))\), where \(\lambda\) is the number of defender types. In the paper, defenders have the same type when their reward and penalty values agree on every target. The result works by reducing the search over possible deviating coalitions to combinations of types. This is the paper’s clearest computational result that already treats many interchangeable defenders as a meaningful regime.
A plausible setting is a growing network of public facilities protected by many standardized patrol units. Units share a small number of profiles: each profile specifies their rewards and penalties for attacks on every target and their resource endowment. The number of units is large compared with the number \(\lambda\) of profiles. To avoid the total resources overwhelming a fixed target set as the population grows, the number of targets and the resource supply should grow together. The paper already uses continuous randomized coverage; the proposed continuity is specifically in the population of defenders.
Here is the problem I would hand to a prover. Let \(\Theta=\{1,\ldots,\lambda\}\) be defender types, with rational masses \(\mu_\theta\geq 0\) summing to \(1\). Type \(\theta\) has the paper’s target-dependent payoff data and resource density \(\rho_\theta\); mass \(q_\theta\) therefore supplies \(\rho_\theta q_\theta\) resources. A candidate coalition structure is a finite list \((q^j,x^j)_{j=1}^r\), where \(q^j\in\mathbb{Q}_{\geq0}^{\lambda}\), \(\sum_j q^j=\mu\), and coalition \(j\)’s coverage satisfies \(x^j\in[0,1]^m\) and \(\sum_t x^j_t\leq\sum_\theta \rho_\theta q^j_\theta\). Its overall coverage is \(c_t=1-\prod_j(1-x^j_t)\). Payoffs and the attacker’s best response, including the paper’s pessimistic defender-specific tie-breaking, determine each type’s baseline utility \(u_\theta\).
Ask whether this structure is in the \(\epsilon\)-core. A deviation chooses nonzero mass \(d\) with \(0\leq d\leq\mu\) and coverage \(x\) feasible with resource budget \(\sum_\theta\rho_\theta d_\theta\). The remaining mass forms the revengers’ coalition, which can choose any feasible coverage \(y\) using budget \(\sum_\theta\rho_\theta(\mu_\theta-d_\theta)\). The deviation is \(\epsilon\)-successful if, for every type with \(d_\theta>0\) and every feasible \(y\), the utility at combined coverage \(c'_t=1-(1-x_t)(1-y_t)\) is at least \(u_\theta+\epsilon\). The question is whether no such \(d,x\) exists. The instance consists of the rational game data, \(\mu,\rho,\epsilon\), and the finite description of the candidate structure; a successful deviation witnesses a no-answer.
I expect this mirror to be Class A for fixed \(\lambda\). The source theorem’s type-subset enumeration has a natural counterpart here: enumerate the types with positive deviating mass, then handle the amount of mass through its aggregate resource capacity. The paper’s target-sorted safety optimization suggests a route to a polynomial algorithm in \(m,r,L\) for fixed \(\lambda\). That is a research target, not a consequence already proved by Theorem 0.20. The question for variable \(\lambda\), the analogous \(0^+\)-core membership problem, and whether continuous mass can support a non-grand stable structure are further natural problems.
This is an extension, not an exact clone of the theorem: fractional type mass can split in ways that no finite defender subset can. The paper’s explicit small-type result makes the population regime especially plausible, but the continuous algorithm still needs proof. Theorem 0.12’s NP-hardness result on non-grand coalition structures, even with two defenders, is tempting as a harder anchor; I would not claim that hardness transfers, because fractional deviations can split those defenders and change the stability question. The mirror covers Theorem 0.20’s stability-testing result, not the paper’s whole core-computation landscape.
The best case against the proposed mirror is a scaling objection. In the paper, each defender contributes an integer resource budget. With a fixed target set of size \(m\), a population of \(N\) defenders with positive per-defender budgets eventually has more resources than the targets can use: total coverage is capped by \(m\), so the tank-filling problem saturates. A nontrivial large-population regime therefore needs the number of targets to grow with the population as well.
The proponent recognizes that need in prose, but their formal model has \(\sum_\theta\mu_\theta=1\) and coalition budget \(\sum_\theta\rho_\theta q_\theta\). With fixed resource densities, that budget stays bounded as the population grows. To represent \(N\) discrete defenders, the budget needs a population-scale factor such as \(N\sum_\theta\rho_\theta q_\theta\). Then the mirror is a family of games whose target sets and payoff data must also scale with \(N\), rather than a fixed-target population limit. That is a real modeling cost, though it can be repaired and the programme permits such co-modifications.
After that repair, I do not see a strong objection to Theorem 0.20 as an anchor. Defender types are a natural complete description here: the paper already groups defenders by payoff data, and resource endowment can be included in the type. A mass of such defenders can plausibly represent many interchangeable patrol units or local security teams. Their coalition and deviation choices can be expressed in type masses, preserving the core-membership question.
The remaining skeptical argument is about marginal value. For a fixed set of types, once the active deviating types are chosen, the mass vector seems to affect feasibility mainly through aggregate resource capacity. That suggests a close extension of the paper’s type enumeration and target-sorted optimization. But the continuous input could also provide genuine high-multiplicity compression, and whether the resulting parametric problem is straightforward is itself a question to prove. The paper’s theorem is evidence that the regime is sensible, not a collision.
So the negative case is weak: the scale factor is missing from the proposed formulation, and a nontrivial limit needs a deliberate target-growth regime. Those points demand a better specification; they do not defeat the repaired mirror.
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.