Truthful and Near-Optimal Mechanisms for Welfare Maximization in Multi-Winner Elections

The strongest honest case is that this paper has a natural continuous-population mirror, especially for its large-electorate threshold result. It does not provide a named NP-hardness theorem, so the case is algorithmic and approximation-theoretic rather than a hardness-transfer story.

The natural regime is participatory budgeting in a large municipality or organization. There are \(n\) residents, \(m\) recurring projects, and a fixed budget. Residents fall into a relatively small number \(\tau\) of complete utility types: a type includes the entire unit-sum utility vector \(u_t\), not merely a ranking. Thus the society is represented by masses \(\mu_t\), with \(\tau\ll n\). This is plausible when preferences are generated by recurring household, neighbourhood, or demographic templates. Projects remain indivisible: the continuous object is only the population.

My lead anchor is Theorem 2, proved in this paper. It concerns the mechanism I.I.D.-THRESHOLDS-AND-CANDIDATES. Agents are randomly partitioned among the \(m\) candidates; an agent assigned to \(x\) receives an independent threshold \(T_i\sim U[0,1]\) and reports the single bit \(b_i=1\) iff \(u_i(x)\ge T_i\). For every candidate, the mechanism estimates its welfare by the fraction of positive reports in its assigned group, then returns the budget-feasible set maximizing the sum of these estimates. The theorem states that, with \(\delta=m^{5/2}\sqrt{72\log(4mn)/n}\), the returned set \(S\) satisfies \(uw(S)\ge OPT(1-\delta)\) with probability at least \(1-1/n\).

The corresponding continuous problem is:

Continuum Binary-Threshold Budgeting. An instance consists of candidates \(C\), rational project costs \(c_x\), budget \(1\), a finite utility-type set \(T\), and masses \(\mu_t\). For each candidate \(x\), create a query stratum of mass \(1/m\) containing mass \(\mu_t/m\) of every type \(t\). Each unit of mass in that stratum receives an independent threshold and reports only whether \(u_t(x)\) exceeds it. From the resulting approval masses \(\bar V_x\), output a feasible set \(S\) maximizing \(\sum_{x\in S}\bar V_x\). The objective is to maximize \(W_\mu(S)=\sum_t\mu_t\sum_{x\in S}u_t(x)\).

In the continuum, \(\bar V_x\) is exactly \(W_\mu(\{x\})\), because \(\Pr[T\le u_t(x)]=u_t(x)\). Hence the statistical error in Theorem 2 disappears: the continuous mechanism achieves distortion \(1\), subject only to solving the resulting finite knapsack instance. Exact selection retains the usual knapsack difficulty, but an FPTAS is available; this is inherited finite-outcome computation, not continuum-specific hardness. The question is therefore Class A in its approximation version.

This is a particularly credible mirror because the paper itself motivates the mechanism by the phrase “when the number of agents is large.” The continuous version does not give the mechanism cardinal reports, fractional projects, or a different objective. It gives exactly the paper’s one-bit information protocol, with the finite sampling noise replaced by population mass.

A second, independent anchor is Theorem 5, proved here. The paper’s \(k\)-WINNER-SELECTION mechanism samples an agent uniformly, chooses a candidate \(z\) from that agent’s ranking with probability proportional to \(1/r_i(z)\), independently samples a uniformly random \(k\)-set \(Y\), and returns \(Z=\{z\}\) or \(Y\), each with probability \(1/2\). The mechanism is truthful because the \(Z\)-part is a point-voting mechanism and the \(Y\)-part is independent of reports. The theorem states that its expected social welfare is at least \(OPT/(4\sqrt m\log m)\), where \(OPT\) is the welfare of the best \(k\)-set.

The corresponding problem is:

Continuum Truthful Harmonic \(k\)-Selection. An instance consists of \(m\) candidates, \(k\), a finite set of unit-sum utility types \(T\), strict rankings \(r_t\), and masses \(\mu_t\). A mechanism may sample a unit of population according to \(\mu\), observe only its ordinal ranking, and output a set of \(k\) candidates. Its objective is expected per-capita welfare \(W_\mu(S)\), and truthfulness is required for a sampled agent: conditional on being sampled, reporting its true ranking must maximize its expected utility.

The paper’s mechanism is immediately well-defined: sample \(t\) with probability \(\mu_t\), choose \(z\) with probability \(1/(H_m r_t(z))\), independently sample \(Y\), and return \(Z\) or \(Y\). Its expected welfare is a finite sum over types, and the theorem’s guarantee remains \(OPT/(4\sqrt m\log m)\). Thus this is also an explicit Class A mirror for evaluating and implementing a truthful mechanism over a high-multiplicity society.

The continuum version needs one semantic safeguard: ordinary dominant-strategy truthfulness becomes vacuous if an individual has literally zero mass and cannot affect an aggregate outcome. The clean interpretation is the finite-replication semantics: the continuous rule must be the limit of truthful rules on every finite society containing \(q\mu_t\) agents of type \(t\). For the sampled-agent mechanism above, this condition is automatic, since the sampled agent can affect the outcome with positive probability.

The third anchor is Theorem 7, also proved here. It states that every truthful ordinal mechanism for one-winner selection has distortion at least \(\sqrt m\log m/8\). The proof constructs, for each rank \(r\), an instance in which a special candidate has rank \(r\) for a carefully chosen fraction of agents, while the remaining candidates are balanced across ranks. The theorem uses the characterization results in Theorems 3 and 4, which are cited from Gibbard, Barbera, and Filos-Ratsikas–Miltersen.

Its continuous counterpart is:

Continuum One-Winner Ordinal Distortion Frontier. An instance consists of \(m\) candidates, a finite ranking-type set, and ranking masses \(\rho_\pi\). A solution is a randomized ordinal rule, interpreted through truthful finite replications of the mass profile. Its distortion is the worst ratio, over all unit-sum cardinal utility assignments compatible with the ranking masses, between the best candidate’s welfare and the rule’s expected welfare. The task is to determine or approximate the minimum achievable worst-case distortion.

I expect Theorem 7’s lower bound to transfer essentially unchanged. The construction uses population fractions such as \(r\sqrt m\log m/(2m)\), and those fractions become ordinary masses in the continuum. Theorem 5 with \(k=1\) supplies the matching \(O(\sqrt m\log m)\) upper bound. Thus the continuous frontier should remain \(\Theta(\sqrt m\log m)\): infinite population eliminates sampling noise, but it does not eliminate the information-theoretic loss caused by ordinal reports. This is a transferred impossibility boundary, not continuum-specific hardness.

These mirrors cover Theorems 2, 5, and 7. They do not claim to continuize every result in the paper. Theorem 6 should admit a similar general-cost participatory-budgeting mirror, while Theorem 9’s two-candidate result is less valuable as an anchor because it already works directly with population fractions. The paper contains no numbered NP-hardness or parameterized-complexity theorem; the introductory knapsack remark is not a suitable hardness anchor.

My weakest point is the type regime. Exact repetition of cardinal utility vectors is stronger than repetition of rankings, and the threshold mirror assumes that such utility templates are meaningful. The ordinal mirror also requires care about truthfulness in a nonatomic population. I would therefore present finite replication as part of the formal definition, rather than pretending that standard continuum strategyproofness is automatically meaningful. Even if that objection weakened the truthful anchors, the threshold mirror remains strong: it is precisely the paper’s large-\(n\) mechanism, with the population estimator replaced by an exact mass integral while the projects, budget constraint, one-bit reports, and welfare objective all remain unchanged.