| paper | d4-conf-ijcai-2019-0605 |
| 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: \(\mathrm{NP}\text{-complete}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite set \(T\) of complete ADCOP types with rational masses \(\mu_t>0\), \(\sum_{t\in T}\mu_t=1\), finite domains \(D_t\), nonnegative rational interaction intensities \(\rho_{tu}\), asymmetric rational costs \(c_{t\leftarrow u}(a,b)\), and a rational threshold \(B\), decide whether \(\min_q F(q)\le B\), where \(q_{ta}\ge0\), \(\sum_{a\in D_t}q_{ta}=1\), and \(F(q)=\sum_{t,u\in T}\mu_t\mu_u\rho_{tu}\sum_{a\in D_t,\,b\in D_u}q_{ta}q_{ub}c_{t\leftarrow u}(a,b)\).
A dense block ADCOP population with \(\tau=|T|\) complete agent types, rational masses \(\mu_t\), type-pair interaction intensities \(\rho_{tu}\), asymmetric costs \(c_{t\leftarrow u}\), and action fractions \(q_{ta}\); minimize the per-capita aggregate cost \(F(q)\).
Theorem 1 bounds a particular distributed algorithm’s messages, while the proposed question is centralized and changes arbitrary constraint graphs to uniform type-pair interactions, so the connection to that theorem is indirect.
fatal: False
The mirror covers exact aggregate cost minimization in dense block ADCOPs; it leaves the graph-dependent message bound, GNLE privacy properties, TSPS and MBES tradeoffs, and empirical comparisons unmirrored.
The strongest case is for Dense Type ADCOP\(_\infty\), a mirror of the exact optimization problem that AsymDPOP solves. My anchor is Theorem 1, proved in this paper. It states that an agent’s UTIL message is exponential in the number of its separators and interface descendants. The proof identifies the table’s retained dimensions as \(Sep(a_i)\cup ID(a_i)\cup\{a_i\}\); descendants outside \(ID(a_i)\) have already been eliminated. With domain size bounded by \(d\), that means \(d^{|Sep(a_i)|+|ID(a_i)|+1}\) entries. This is a named algorithmic space-complexity result, not a theorem that ADCOP is NP-hard or in P. The paper gives no named classification of the underlying optimization problem comparable to those.
Here is the mirror. There are finitely many types \(T\), each with positive rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). A type is a complete ADCOP description: its members share an action domain \(D_t\), the same interaction profile with every other type, and the same private payoff tables. Let \(\rho_{tu}\) be the rational interaction intensity between types \(t\) and \(u\), and \(c_{t\leftarrow u}(a,b)\geq 0\) the cost incurred by a type-\(t\) participant interacting with a type-\(u\) participant who chooses action \(b\), when the type-\(t\) participant chooses \(a\). The society is a large, dense block-structured network: members of two types interact uniformly at the specified intensity.
The decision variable is \(q_{ta}\), the fraction of type \(t\)’s mass choosing action \(a\), with \(q_{ta}\geq 0\) and \(\sum_{a\in D_t}q_{ta}=1\). The per-capita aggregate cost is
\[
F(q)=\sum_{t,u\in T}\mu_t\mu_u\rho_{tu}
\sum_{a\in D_t,\ b\in D_u}q_{ta}q_{ub}\,c_{t\leftarrow u}(a,b).
\]
The ordered type pairs account separately for each participant’s private cost, as in an ADCOP. Dense Type ADCOP\(_\infty\) asks, given these rational data and a rational threshold \(B\), whether \(\min_q F(q)\leq B\); its optimization form asks for a global minimizer and the minimum cost. A solution is the yes/no answer to the threshold version, or an optimal set of type-level action fractions for the optimization version.
The regime is many radio or spectrum devices in a relatively small number \(\tau=|T|\) of hardware and location classes. A member’s action domain and interference costs against each class are shared by all members of its type; in a finite approximation, each class can contain \(N\gg\tau\) devices, with the same pairwise cost applying uniformly across the corresponding blocks. The continuum makes fractional \(q_{ta}\) honest: every device still chooses an integral action, but an arbitrary fraction of a large class can choose each action. This preserves the paper’s finite action choices, pairwise constraints, asymmetric private costs, and global cost-minimization objective. The co-modification is the interaction structure needed to make type-level masses sufficient; this is not an outcome-space or time continuization.
I expect this problem to be Class B: hardness transfers. In fact, the mirror remains NP-hard in the number of types. Given a graph \(G=(V,E)\), make one type per vertex, each with actions \(\{0,1\}\). For each edge, set symmetric nonnegative private costs to \(1\) when its endpoints choose the same action and \(0\) otherwise; give nonedges zero interaction weight. The objective is the sum, up to a positive scale, of same-action penalties. It is multi-affine in each type’s action fraction, so a global minimum can be attained with every type choosing one action purely. Its value is then \(|E|\) minus the size of a maximum cut. Thus a threshold question decides whether \(G\) has a cut of a specified size. The hardness lives in the interaction pattern over types, so making each type contain arbitrarily many agents does not erase it. This reduction is my analysis of the proposed mirror, not a result claimed by the paper.
The authors would likely recognize this as a continuous-population version of their underlying ADCOP assignment problem: the asymmetric costs and optimization target remain, and any allocation of actions within a type that realizes \(q\) gives the same aggregate cost under the block-homogeneity assumption. The mirror speaks most directly to the structural burden quantified by Theorem 1: a finite representation may carry dimensions for many individual agents, while a type-level formulation has variables indexed by types and actions. It does not establish that Theorem 1’s message bound carries over, or that a continuous solver would outperform AsymDPOP.
That limitation is also the weakest point. The paper allows arbitrary constraint graphs; this mirror requires dense, uniform interactions between type classes, and its centralized aggregate formulation does not reproduce AsymDPOP’s privacy-preserving message protocol. So I would scope the case to exact ADCOP optimization in this credible high-multiplicity regime, not to GNLE’s privacy properties, the TSPS/MBES implementation tradeoffs, or the paper’s empirical comparisons.
The next questions are whether this problem has useful approximation or parameterized algorithms in \(\tau\), whether tractability follows from restrictions such as low type-interaction treewidth or special payoff structure, and whether the message-complexity story can be recovered while keeping the type-level privacy boundaries meaningful.
The strongest objection is that Theorem 1 bounds a particular algorithm’s message size; it does not classify the complexity of ADCOP optimization. Its bound depends on separators and interface descendants in a fixed pseudo-tree. Theorem 1 is a genuine named algorithmic result, so “there is no computational result to mirror” would be the wrong argument. But a continuous mirror of that theorem would need to preserve the distributed message-passing problem, not just ask for the minimum aggregate cost.
That is hard to do while keeping the population description small. In an arbitrary ADCOP, an agent’s relevant type includes its constraint incidences and the private functions on those constraints. Grouping agents by local payoff table alone loses which actions meet across which edges; the action fractions \(q_{ta}\) do not determine the total cost. To make those fractions sufficient, one must add structure to the interaction graph. The proposed complete block model does that with uniform type-pair interactions. It is mathematically coherent, but it replaces the paper’s arbitrary constraint graph with a well-mixed, multitype interaction model.
A stronger version could retain the type-pair interaction kernel and ask for a privacy-preserving inference algorithm over type-level messages. That is a sensible question, but it is no longer a direct continuation of the theorem’s pseudo-tree bound: the separators and interface descendants belong to the original graph, while the new algorithm would operate on a quotient or kernel model. Keep arbitrary incidence and the number of types can grow with the population, removing the compression. Collapse to a small type graph and the message dimensions and privacy boundaries have changed along with the model.
This makes the proposed Dense Type ADCOP\(_\infty\) a weak target for Theorem 1 specifically: it asks about centralized global optimization and expressly leaves out the paper’s privacy-preserving protocol. Still, the negative case does not defeat it outright. Its block model is a plausible high-multiplicity ADCOP regime, and a continuous complexity question about its type-level optimization could be worthwhile on its own. I can argue that it is an adjacent model rather than a mirror of AsymDPOP’s main algorithmic result; I cannot honestly rule out every scenario in which the authors would recognize it as their problem.
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.