d4-conf-atal-2016-0025

The strongest honest case is a narrow mirror of Theorem 2. The paper states: “Alg. 1 is sound, i.e. the strategy profile obtained by this protocol is socially optimal.” Proved here, with a sketched proof, this means that any profile the protocol returns is acceptable, every chosen action is feasible for its agent in that agent’s perfect-view argumentation framework, and there is no other acceptable, feasible profile in which every agent strictly prefers their replacement action. Feasibility means the action’s practical argument belongs to at least one admissible set. The paper separately proves termination, but does not prove completeness: it gives an instance where the protocol returns no profile although one exists. Nor does it establish a polynomial-time bound. So this is an anchor for a computational *outcome property*, not a tractability result.

A plausible high-multiplicity setting is a large sensor network. Many nodes may share the same firmware, local observation class, argumentation structure, and action priorities; the network can then have millions of nodes but relatively few distinct types. Each node still chooses one indivisible action, such as a channel or operating mode. The continuous model describes what fraction of each type takes each action. The type must include the full information the paper uses: preferences, private and disclosable arguments, and the internal attack structure. Nodes with different relevant information belong to different types.

Here is the problem I would hand to a prover: Continuous Socially Optimal Coordination. The instance consists of a finite action set \(A\), a finite support \(T\) of types with positive rational masses \(\mu_t\) summing to \(1\), each type’s preference order and internal argumentation framework, the agreed attacks between disclosable arguments, and rational per-action share bounds \([\ell_a,u_a]\). For each type \(t\), combine its own framework with the disclosable arguments of the other supported types to form its perfect-view framework. Let \(E_t\) be the actions whose practical arguments are admissible there.

A solution is a rational allocation \(x_{t,a}\geq 0\) such that \(\sum_a x_{t,a}=\mu_t\), \(x_{t,a}=0\) for \(a\notin E_t\), and \(\ell_a\leq\sum_t x_{t,a}\leq u_a\). It must also be socially optimal in the paper’s sense. Precisely, there must be no other feasible allocation \(y\) and, for each type \(t\), a coupling \(\pi_{t,a,b}\) with marginals \(x_{t,a}\) and \(y_{t,b}\), supported only on pairs where type \(t\) strictly prefers \(b\) to \(a\). Such a coupling means that, up to a measure-zero set, every member of the population could receive a strictly preferred action. The answer is an allocation or a report that none exists. The bounds on shares are the natural per-capita scaling of the paper’s permitted action counts; each person still receives one action, while averages within a type can be fractional.

With the feasible-action sets \(E_t\) already known, this allocation problem has a clean continuous-optimization core: maximize \(\sum_{t,a}x_{t,a}r_t(a)\), where \(r_t\) increases with type \(t\)’s preference order. The constraints are linear, and an optimum is socially optimal under the paper’s strict-all-agent criterion: a coupling that strictly improves everyone would strictly increase the objective. This gives a polynomial-time LP for the allocation stage.

The unrestricted problem should remain hard, however. Admissibility testing is already computationally difficult: credulous acceptance under admissible semantics is NP-complete ([IJCAI paper on argumentation complexity](https://www.ijcai.org/Proceedings/11/Papers/177.pdf)). The paper’s restrictions on argument types do not remove this obstacle. Given an argumentation framework \(F\) and query \(q\), make a target type with a disclosable argument \(d\), a private argument \(p\), and practical argument \(A\), with attacks \(d\to p\to A\). Locally, \(A\) is feasible. A second type supplies the disclosable arguments of \(F\), plus \(z\), with attacks \(q\to z\to d\) and the original attacks of \(F\). In the target type’s perfect view, \(A\) is feasible exactly when \(q\) is credulously accepted in \(F\). With one action required for the whole population, a solution exists exactly in that case. The local-feasibility assumption is respected, and the same construction works with two discrete agents. This is a derived hardness argument, not a result claimed by the paper; it suggests that the full mirror lies on the hardness-transfer side of the trichotomy, while its allocation stage is tractable once action feasibility is settled.

The weakest point is that this mirrors the theorem’s allocation guarantee, not the paper’s full privacy-preserving protocol. Per-capita share bounds replace exact finite count sets, and a mass allocation replaces the protocol’s individually ordered token passing. That is a real co-modification, but it leaves the population as the continuous object and preserves the theorem’s feasibility and social-optimality requirements. The authors might still say the privacy guarantee is too central to leave outside the question; a type-level version of their entropy-based security claim would be a natural follow-up. Another is whether parameterizing the argumentation checks can yield an efficient end-to-end algorithm when the number of types is moderate.