| paper | d4-conf-atal-2020-0182 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.2
statement extracted from the paper’s text layer
Given a finite target set \(T\), attacker utilities \(u^a\), a distribution over \(\tau\) defender types with rational masses \(\mu_\ell>0\) summing to \(1\), rational type utilities \(u_{\theta_\ell}\), normalized pooled capacity \(R\), and a supplied benchmark \((c^0,t_0)\), find \((c,t)\) maximizing \(\sum_{\ell=1}^{\tau}\mu_\ell u_{\theta_\ell}(c,t)\). Require \(t\in\arg\max_{j\in T}u^a(c,j)\), \(c\in[0,1]^T\), \(\sum_{j\in T}c_j\le R\), and \(u_{\theta_\ell}(c,t)\ge u_{\theta_\ell}(c^0,t_0)\) for every supported type; the stated mass-allocation model treats these coverage vectors as feasible.
A continuous population of defender types with masses \(\mu_\ell\), a fixed finite target set, pooled normalized capacity \(R\), and a common attacker. The decision is a feasible coverage vector \(c\) and an attacker best response \(t\); the objective is mass-weighted defender utility, subject to each type’s benchmark utility guarantee.
The mirror covers Theorem 4.2’s CSW-Max outcome selection after a benchmark is supplied. It leaves the benchmark’s computation, the impossibility results, and the special strategyproof mechanism of Theorem 4.3 outside scope.
The strongest positive case is narrow and algorithmic. Theorem 4.2, proved in this paper, states that CSW-Max outputs an outcome that is Pareto efficient and weakly utility preserving. Its construction computes a no-coordination NSE, solves an LP for each possible attacker target, and selects the best solution; the paper says this runs in polynomial time. The theorem is therefore a tractable mechanism-design anchor. The paper gives no NP-hardness or parameterized-complexity result, so this mirror would not test whether a known hardness result dissolves in the continuum.
I would mirror it with Mass-CSW-Max. Consider a large federation of port or coastal-security units facing one attacker at a fixed set \(T\) of targets. Units fall into \(\tau\) standardized types, each specifying defender payoff vectors and a normalized per-capita patrol endowment. The input gives each type’s population mass \(\mu_\ell\), with \(\sum_\ell\mu_\ell=1\), and the total normalized capacity \(R=\sum_\ell\mu_\ell\rho_\ell\). The regime is many units, relatively few types: the masses are binary rationals, and the payoff, attacker, and capacity data are rational. Resource endowments are public, as in the paper’s separation between private payoffs and resource profile.
The instance also supplies a certified no-coordination equilibrium with coverage \(c^0\) and attacker response \(t_0\). Write \(u_{\theta_\ell}(c,t)\) for type \(\ell\)’s defender utility and \(u^a(c,t)\) for the attacker’s utility. The task is to return a coordinated coverage vector and attacker response \((c,t)\) maximizing \(\sum_{\ell=1}^{\tau}\mu_\ell u_{\theta_\ell}(c,t)\), subject to \(t\in\arg\max_{j\in T}u^a(c,j)\), \(0\le c_j\le1\), \(\sum_j c_j\le R\), and \(u_{\theta_\ell}(c,t)\ge u_{\theta_\ell}(c^0,t_0)\) for every supported type. A solution is the maximizing pair \((c,t)\), together with a lottery over patrol allocations implementing \(c\). The per-type constraints give every member of that type the same utility guarantee.
This is a specific continuous population model of Theorem 4.2’s underlying coordination problem: pooled patrol resources, an attacker best response, Pareto efficiency, and guarantees against a decentralized equilibrium. Mass weights social welfare, and type-level constraints express utility preservation. For rational data, the proposed optimization is a linear program with \(m\) coverage variables and \(O(m+\tau)\) constraints, so I expect this restricted mirror to be in Class A, tractable in \(\mathrm{poly}(m,\tau,L)\). The paper’s theorem is proved here; its NSE computation relies on the algorithm cited from Gan et al. [10].
The main weakness is the resource normalization. With a fixed target set and each of an increasing number of agencies contributing a whole vessel, pooled capacity eventually makes the interior-coverage premise uninteresting. This mirror needs capacity and coverage measured in normalized units, so each unit of population contributes a diminishing share of a fixed total patrol capacity. That co-modification is permitted by ChoCo’s scope, but it is a real modeling choice the authors or a referee could reject. The mirror also assumes a supplied equilibrium benchmark; computing and characterizing continuum equilibria is a further problem.
The scope is just the CSW-Max result in Theorem 4.2. It does not claim a continuous analogue of the paper’s impossibility results. Further questions include whether the benchmark equilibrium can be computed from the type distribution, whether the result survives with unrestricted payoff types, and how finite high-multiplicity instances approximate the mass problem.
The strongest objection is that the proposed mirror conditions on the hardest part of Theorem 4.2’s mechanism: it is given a certified no-coordination equilibrium. In the paper, CSW-Max must obtain that benchmark from the defenders’ uncoordinated game. That game is defined through individual resource holdings, unilateral deviations, and the resulting coverage \(1-\prod_i(1-c_{it})\). A distribution over defender types does not by itself say how those deviations or their effects on coverage behave in a continuum. Supplying \((c^0,t_0)\) makes the proposed optimization well-defined, but turns it into a conditional welfare problem rather than a direct mirror of the full mechanism.
The resource scaling is another real modeling burden. With fixed targets and a positive integer resource endowment shared by a positive-mass type, the number of resources grows with the population; coordinated coverage can then saturate. Holding total capacity \(R\) fixed instead requires vanishing, divisible contributions. That is a plausible fluid security model, but it changes the paper’s resource and coverage semantics, and its lottery implementation needs to be specified carefully. Neither issue is fatal under ChoCo’s rules: resource scaling can be part of the mirror, and the benchmark can be defined as an input or derived from a chosen continuum equilibrium notion.
That leaves the best negative case short of its burden. The conditioned version is a small LP, but an answer that is already easy does not make a well-posed mirror unworthy. A fuller version could ask how to define and compute an appropriate uncoordinated benchmark for a high-multiplicity defender population, then apply the same coordination optimization. The paper’s result has a recognizable computational core, and defender types can plausibly aggregate preferences and contributions. I can identify a gap between the proposed LP and the full theorem, but I cannot honestly rule out every worthwhile continuous 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.