d4-conf-aaai-2020-0365

The strongest mirror is a population version of the paper’s F-DCOP optimization problem. Its continuous object is the society: many sensors are grouped into a small number of complete types, such as hardware-and-location classes with the same action domain, costs, and interaction profile. A network with hundreds of thousands of sensors but tens or hundreds of such types is plausible when many sensors are deployed in repeated coverage cells. Each sensor still chooses an individual continuous setting, such as orientation or duty cycle; type-level distributions record what fraction choose each setting.

My anchor is Proposition 1, proved in this paper: *PFD is an anytime algorithm*. In the authors’ sense, the best solution found so far improves monotonically as iterations increase—in a minimization problem, its cost never rises. This is a result about PFD’s incumbent solutions, not a guarantee of global optimality, a polynomial running time, or convergence to an \(\varepsilon\)-optimum. The paper has no named NP-hardness or complexity-class result to use as a stronger anchor.

Here is a precise problem to put to a prover. Call it Population F-DCOP \(\varepsilon\)-Optimization. An instance has a finite set of types \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), compact rational action intervals \(D_t\), rational interaction weights \(w_{ts}\), and rational polynomial unary and pairwise costs \(u_t\) and \(f_{ts}\). A feasible solution gives each type a probability distribution \(\pi_t\) over its actions: a fraction of the type’s mass chooses each setting. Minimize the per-capita cost

\[ J(\pi)= \sum_{t\in T}\mu_t\int_{D_t}u_t(x)\,d\pi_t(x) +\sum_{t,s\in T}\mu_t w_{ts} \int_{D_t}\int_{D_s}f_{ts}(x,y)\,d\pi_t(x)\,d\pi_s(y). \]

The task is to output finite-support distributions \((\pi_t)_{t\in T}\) with rational weights and action values such that \(J(\pi)\le \inf_{\pi'}J(\pi')+\varepsilon\), for a supplied rational \(\varepsilon>0\). Complexity should be measured in \(|T|\), the input bit length, and \(\log(1/\varepsilon)\). The direct anytime analogue of Proposition 1 would have a solver emit feasible population policies whose incumbent cost never rises. The optimization question above asks the more consequential question: how hard is it to find a globally \(\varepsilon\)-optimal policy?

I expect the unrestricted problem to be Class B: hardness transfers. The population limit removes duplicate agents; it need not remove combinatorics in the type-interaction structure. For example, set \(\mu_t=1/|T|\), \(D_t=[0,1]\), and use linear unary costs and bilinear pair costs so that the objective becomes
\[ \sum_t a_t p_t+\sum_{t<s}b_{ts}p_tp_s,\qquad p_t=\int x\,d\pi_t(x). \]
This is a binary quadratic optimization objective relaxed to \(p\in[0,1]^{|T|}\). It is affine in each coordinate separately, so a minimum occurs at a Boolean vertex; the continuous population problem therefore retains the discrete optimization value. That suggests NP-hardness even when every type has arbitrarily many agents. This is a reduction to prove for the stated encoding, rather than a result claimed by the paper. It also points to useful follow-up questions: whether fixed type-graph structure or convex cost restrictions give tractable cases, and whether a type-level distributed solver can pair PFD-style anytime incumbents with a global approximation guarantee.

The case is narrow: it mirrors the F-DCOP optimization that PFD is designed to solve, not every result or benchmark in the paper. The main weakness is the anonymous, type-block interaction model: it replaces an arbitrary named-agent graph with aggregate interactions between classes. The authors could reasonably accept it as an F-DCOP regime for large repeated sensor deployments, but Proposition 1 itself says nothing about whether PFD’s guarantee survives that change.