Better Collective Decisions via Uncertainty Reduction

My strongest honest case uses one anchor: the CLD part of Theorem 1, which states that EAP, DAP, and CLD are NP-complete even for a one-dimensional proposal space. This is a result proved in the paper; the displayed proof is for CLD, by reduction from Vertex Cover on Cubic Graphs, while the EAP and DAP proofs are omitted. I use CLD because its proof and its delegation semantics are explicit.

A plausible high-multiplicity setting is a large public consultation over a fixed ordered set of policy proposals: several tax rates, energy sites, or regulatory thresholds. Millions of residents may be distributed among a much smaller number of belief-and-knowledge profiles. A type \(t\) records the complete pair \((P_t^+,P_t^!)\): the proposals that are genuinely beneficial to that type, and the proposals about which it is certain. Types can repeat because residents share policy positions and information sources. Thus \(\mu_t\) is the fraction of the electorate of type \(t\), with \(n\gg\tau\). The proposal space remains finite and discrete; only the population is continuized.

I would call the mirror Mass-CLD\(_\infty\). Its input is a finite ordered proposal space \(P=\{p_1,\ldots,p_m\}\), a finite explicit type set \(T\), rational masses \(\mu_t\ge0\) summing to \(1\), and an integer threshold \(\lambda\). Each type satisfies exactly the paper’s one-dimensional restrictions: \(P_t^+\) is an interval, and \(P_t^?\) consists of uncertainty intervals adjacent to the endpoints of that positive interval.

For each proposal \(p\), the correct outcomes are determined from the hidden preferences of the population: \(1\) is correct if \(\sum_{t:p\in P_t^+}\mu_t\ge 1/2\), while \(0\) is correct if \(\sum_{t:p\notin P_t^+}\mu_t\ge1/2\). Hence ties correctly produce \(\operatorname{corr}_\mu(p)=\{0,1\}\), just as in the paper.

Define a type-level delegation arc \(t\to u\) precisely when \(P_t^{+!}\cap P_u^-=\varnothing\), \(P_t^{-!}\cap P_u^+=\varnothing\), and \(|P_t^!|<|P_u^!|\). Let \(R(t)\) be the reachable types, including \(t\) itself. A solution is a nonnegative mass delegation plan \(y=(y_{t,g})\) satisfying \(\sum_{g\in R(t)}y_{t,g}=\mu_t\) for every \(t\). Here \(y_{t,g}\) is the mass initially of type \(t\) whose final guru has type \(g\). The resulting guru-mass distribution is \(\nu_g=\sum_t y_{t,g}\).

The possible outcomes after delegation are then exactly \(\operatorname{poss}_\nu(p)=\{1:\sum_{g:p\in P_g^{+!}\cup P_g^?}\nu_g\ge1/2\}\cup\{0:\sum_{g:p\in P_g^{-!}\cup P_g^?}\nu_g\ge1/2\}\). A proposal is safe when \(\operatorname{poss}_\nu(p)\subseteq\operatorname{corr}_\mu(p)\). Mass-CLD\(_\infty\) asks whether there is a plan \(y\) making at least \(\lambda\) proposals safe; equivalently, its optimization version maximizes the number of safe proposals.

This is recognizably the authors’ problem. It retains hidden preferences, uncertainty, majority correctness, willingness constraints, transitive delegation, gurus, and the objective of maximizing guaranteed-good issues. The only change is that the electorate is represented by masses. Splitting one type across several gurus is not an arbitrary weakening: in a large repeated electorate, different individuals of the same type may choose different permissible delegates. Rational \(y\) can be implemented by taking a sufficiently large replicated electorate and realizing each mass as a count.

My prediction is a split in complexity. The exact at-least-\(\lambda\) Mass-CLD\(_\infty\) problem is a good candidate for Class C, continuum-specific hardness. The published Vertex Cover reduction does not automatically transfer: once delegation mass is divisible, choosing a vertex can become assigning fractional mass to that vertex, and the gadget may collapse to a fractional-cover problem. Thus I would not honestly claim Class B.

However, the all-proposals subcase, \(\lambda=m\), looks like Class A. Once the correct outcome of each proposal is fixed, safety imposes linear inequalities on \(\nu\), and \(\nu\) is linear in \(y\). The resulting feasibility problem is an LP with strict majority inequalities, or an equivalent rational-margin formulation. The full objective introduces a cardinality choice over which proposal constraints to satisfy, naturally producing a mixed-integer layer. That issue-selection layer is where continuum-specific hardness could survive even though the all-safe discrete hardness dissolves.

This generates several useful questions: does Mass-CLD\(_\infty\) remain NP-hard for intermediate \(\lambda\) in the one-dimensional domain; is it polynomial for \(\lambda=m\); can one obtain rounding bounds from a continuous plan to a finite electorate; and what happens when parameterized by \(m\), \(\tau\), or the number of uncertain types? Proposition 2 also suggests studying whether the paper’s radical one-dimensional polynomial case remains polynomial after continuization.

The weakest point is the realism of repeated *complete* belief types. Exact agreement on both preferences and issue-specific certainty is more plausible in a segmented public consultation than in an arbitrary electorate, and less plausible when every person has idiosyncratic information. But that is a weakness of the scenario’s empirical reach, not of the mathematical mirror: the paper’s CLD model is already defined by complete belief profiles, and a large consultation with a finite profile taxonomy is a credible high-multiplicity regime. This mirror therefore covers CLD emphatically, while deliberately leaving EAP and DAP for separate analyses.