d4-conf-atal-2015-0337

The strongest positive case is modest and algorithmic. The paper has no named hardness result to anchor a question about hardness dissolving; its suitable computational anchor is Proposition 7, proved here. It says that, given any explicit set of alternatives \(W\subseteq 2^{\Phi_0}\), an alternative \(w\in W\), and an RCL formula \(\varphi\), an algorithm decides whether \(W,w\models\varphi\) in time \(O(|W|\cdot\|\varphi\|)\), where \(\|\varphi\|\) is the number of symbols in the formula. The paper’s main Theorem 1 concerns axiomatic conditions, not computational complexity, so I would not use it as an anchor.

A plausible high-multiplicity regime is a large membership organization choosing from a shared, finite slate of policy packages. Members use a fixed response format to express priorities among package properties. A type is one complete RCL reason hierarchy in that format; mass is the fraction of members using it. There could be hundreds of thousands of members but only tens or hundreds of distinct formula types. Members with the same formula are indistinguishable for the collective rule, as high multiplicity requires.

That gives a precise mirror: Continuous Quota-RCL Model Checking. Let \(W\) be explicit, and let the society have support \(T_+\) of \(\tau\) types, with positive binary-rational masses \(\mu_t\) summing to one. Require each type \(t\) to have a complete, equal-depth formula \(\varphi_t=A^t_1\triangledown\cdots\triangledown A^t_d\), where \(W\models\bigvee_{j=1}^d A^t_j\). Given a rational quota \(\alpha\in(0,1]\), define
\[ h_t(w)=\min\{j:w\models A^t_j\},\qquad q_\alpha(w)=\min\left\{k:\sum_{t:h_t(w)\le k}\mu_t\ge\alpha\right\}. \]
The continuous collective choice set is
\[ C_\alpha=\{w\in W:q_\alpha(w)=\min_{v\in W}q_\alpha(v)\}. \]
The problem is to compute \(C_\alpha\), or decide whether a queried \(w\) belongs to it.

This is a direct mass version of the paper’s uniform quota rule \(F_\tau\). For a finite profile in which \(n_t\) agents have type \(t\), set \(\mu_t=n_t/n\) and \(\alpha=\tau/n\). With equal formula depth, the tier-\(k\) clause of \(F_\tau\) holds at \(w\) exactly when at least \(\tau\) agents have \(h_t(w)\le k\). Thus the continuous choice set agrees exactly with the finite rule on that profile.

I expect this mirror to be tractable. Evaluate each type’s tiers on every alternative, sum the corresponding binary-rational masses, and find the alternatives with minimum quota rank. The running time is polynomial in \(|W|\), \(\tau\), the total formula length \(S\), and the bit length \(L\) of the masses and quota. This stays close to Proposition 7’s explicit-alternative model checking, while representing repeated agents by their type masses instead of expanding them into a long profile. I think the authors would recognize it: their agents already submit RCL formulas, and their collective rules already include quotas.

The weak point is that this does not expose a hard discrete problem whose hardness might disappear. Proposition 7 is already a polynomial-time result, and the exact correspondence I give is for the equal-depth subcase of \(F_\tau\). The paper’s examples also involve small groups, so the large-template population is a plausible new regime, not one established by the paper. That limits the claim: this is a credible continuous mirror of its collective model-checking result, not evidence that the paper’s central contribution is about computational hardness or that its full range of formula profiles has already been continuized.