Truthful and Near-Optimal Mechanisms for Welfare Maximization in Multi-Winner Elections (d4-conf-aaai-2018-0444)

Given \(m\) indivisible projects with costs \(c_x\), budget \(1\), unit-sum utility types \(u_t\), and rational masses \(\mu_t\), partition each type mass into \(m\) candidate-query strata, apply independent thresholds \(T\sim U[0,1]\), observe the exact positive-report mass \(a_x=\sum_t\mu_tu_t(x)\) for each project, and output a feasible set \(S\) maximizing \(\sum_{x\in S}a_x\); determine its welfare guarantee and computational complexity.

A society is given by its support: the list of \(\tau\) utility types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) indivisible projects, binary-rational costs \(0\leq c_x\leq1\), and budget \(1\). Each type has binary-rational utilities \(u_t(x)\geq0\), with \(\sum_xu_t(x)=1\) and pairwise distinct utilities within each type. Let \(L\) be the total input bit length.
Split each type equally among the \(m\) project-query strata. In each stratum, thresholds have exactly the uniform distribution on \([0,1]\); a truthful report is positive precisely when \(u_t(x)\geq T\). The exact positive mass for project \(x\) is \(a_x/m\), and the observed score is its rescaling \(a_x=\sum_t\mu_tu_t(x)\).
The exact rule returns a set \(S\subseteq C\) maximizing \(\sum_{x\in S}a_x\) subject to \(\sum_{x\in S}c_x\leq1\), with lexicographic tie-breaking using project labels.
Define \(W(S)=\sum_t\mu_t\sum_{x\in S}u_t(x)\), \(\mathrm{OPT}=\max_{S:\sum_{x\in S}c_x\leq1}W(S)\), and distortion as \(\sup\mathrm{OPT}/\mathbb E[W(S)]\), taking the ratio as infinite when the denominator is zero.

What is the sharp worst-case distortion of this exact rule?
For rational \(0<\varepsilon<1\), can a mechanism using only the observed scores and costs guarantee \(\mathbb E[W(S)]\geq(1-\varepsilon)\mathrm{OPT}\) in time polynomial in \(m,\tau,L,1/\varepsilon\), or is attaining this approximation NP-hard?

For a finite population of \(n\) voters, independent binary threshold queries with a uniformly balanced random project assignment yield \(W(S)\geq(1-\delta)\mathrm{OPT}\) with probability at least \(1-1/n\), where \(\delta=m^{5/2}\sqrt{72\log(4mn)/n}\), assuming exact maximization of the reported scores. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/11480/11339)
Discrete welfare maximization with fully elicited utilities is reported NP-hard even for one voter and admits an FPTAS; these are results for cardinal-input optimization. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/11480/11339)

Result. The sharp worst-case distortion is \(1\). Moreover, a deterministic mechanism using only the observed scores and costs achieves \(W(S)\geq(1-\varepsilon)\mathrm{OPT}\) by a fully polynomial-time approximation scheme.

1. The scores determine welfare exactly

Nonnegativity and normalization imply \(u_t(x)\in[0,1]\). Thus a uniform threshold satisfies
\(\Pr[T\leq u_t(x)]=u_t(x)\), including at the endpoints.

Type \(t\) has mass \(\mu_t/m\) in the stratum querying project \(x\). Consequently, that stratum’s positive mass is
\(\sum_{t=1}^{\tau}(\mu_t/m)u_t(x)=a_x/m\).

For every project set \(S\), interchanging the finite sums gives
\[ W(S)=\sum_{t=1}^{\tau}\mu_t\sum_{x\in S}u_t(x) =\sum_{x\in S}\sum_{t=1}^{\tau}\mu_tu_t(x) =\sum_{x\in S}a_x. \]
Therefore, the observed scores specify the welfare of every set exactly. Pairwise distinct utilities within each type are compatible with this identity and impose no additional requirement on the algorithm.

2. Sharp distortion of the exact rule

Let \(S_{\mathrm{ex}}\) be the exact rule’s output. Its objective equals welfare, and its feasibility constraint is the one defining \(\mathrm{OPT}\). Hence
\(W(S_{\mathrm{ex}})=\mathrm{OPT}\).
Lexicographic tie-breaking only chooses between sets with identical optimal welfare.

The denominator in the distortion ratio is positive. Indeed,
\(\sum_{x\in C}a_x=\sum_t\mu_t\sum_xu_t(x)=1\).
Writing \(M=\max_x a_x\), we therefore have \(M\geq1/m>0\). Since every individual project costs at most \(1\), every singleton is feasible, so \(\mathrm{OPT}\geq M\).

Thus every admissible instance has
\(\mathrm{OPT}/\mathbb E[W(S_{\mathrm{ex}})]=1\).
Taking the supremum proves that the sharp worst-case distortion is \(1\).

3. A mechanism using only scores and costs

Fix rational \(0<\varepsilon<1\), and label the projects \(1,\ldots,m\). Define
\(K=\varepsilon M/m\) and \(q_i=\lfloor a_i/K\rfloor\).
These are well-defined because \(M>0\). Each \(q_i\) is a nonnegative integer, and
\(q_i\leq m/\varepsilon\).
Consequently, \(Q=\sum_{i=1}^{m}q_i\leq m^2/\varepsilon\).

The mechanism chooses a feasible set maximizing the rounded objective
\(q(S)=\sum_{i\in S}q_i\).
It computes this set by the following dynamic program.

For \(i\in\{0,\ldots,m\}\) and \(q\in\{0,\ldots,Q\}\), let \(D_i(q)\) be the minimum cost of a subset of \(\{1,\ldots,i\}\) whose rounded objective is exactly \(q\). Use \(+\infty\) when no such subset exists. Initialize \(D_0(0)=0\) and \(D_0(q)=+\infty\) for \(q>0\). The recurrence is
\(D_i(q)=\min\{D_{i-1}(q),\,c_i+D_{i-1}(q-q_i)\}\),
where a negative index has value \(+\infty\).

To justify the recurrence, any subset either excludes project \(i\), giving the first term, or includes it, leaving a subset with rounded objective \(q-q_i\), giving the second term. Conversely, either finite term is realized by a subset with the required objective. This establishes the meaning of every state by induction.

Choose the largest \(q\) with \(D_m(q)\leq1\), and reconstruct its realizing subset \(S\). This maximizes the rounded objective among feasible sets. The recurrence remains valid for zero costs and zero rounded scores because both alternatives reference the previous layer.

4. Approximation guarantee

Let \(S^\star\) be a welfare-optimal feasible set. The floor definition gives, for every project,
\(Kq_i\leq a_i\) and \(Kq_i\geq a_i-K\).
Since the mechanism maximizes the rounded objective,
\(q(S)\geq q(S^\star)\).

Combining these facts yields
\(W(S)\geq Kq(S)\geq Kq(S^\star)\geq W(S^\star)-|S^\star|K\).

Now \(|S^\star|\leq m\), \(mK=\varepsilon M\), and \(M\leq\mathrm{OPT}\). Therefore,
\(W(S)\geq\mathrm{OPT}-\varepsilon M\geq(1-\varepsilon)\mathrm{OPT}\).

The mechanism is deterministic, so the same guarantee holds for \(\mathbb E[W(S)]\).

5. Bit complexity and the supplied results

The dynamic program has at most \((m+1)(Q+1)\) states and uses \(O(m^3/\varepsilon)\) arithmetic operations.

Exact rational arithmetic also has polynomial bit complexity. For example, the product of the input denominators of all masses and utilities is a common denominator for every score and has bit length \(O(L)\). Since \(0\leq a_x\leq1\), the corresponding score numerators also have bit length \(O(L)\). Similarly, a common denominator for the costs has bit length \(O(L)\); any subset-cost numerator has bit length \(O(L+\log m)\). Thus all dynamic-programming additions and comparisons have polynomial bit cost. Computing the scores from the supplied support, if necessary, uses \(m\tau\) products and sums and never enumerates possible utility types.

Including the supplied accuracy parameter’s encoding in total input length, the running time is polynomial in \(m,\tau,L,1/\varepsilon\). This proves the requested FPTAS directly under the stated restrictions.

The cited finite-population theorem controls sampling error, whereas the stipulated exact strata here give the welfare coefficients without sampling error. The paper also identifies cardinal welfare maximization with knapsack and reports an FPTAS. The construction above verifies explicitly why such an approximation is available from the observed scores alone. [Bhaskar, Dani, and Ghosh, Sections 1 and 3](https://ojs.aaai.org/index.php/AAAI/article/download/11480/11339).

⟨structured verdict parsed — rendered above⟩

The argument resolves both questions: the exact rule has sharp worst-case distortion \(1\), and the proposed mechanism is a deterministic FPTAS. No substantive mathematical gaps or false steps were found.

1. Scores and welfare

The normalization and nonnegativity assumptions imply \(0\leq u_t(x)\leq1\). Therefore, for a threshold uniformly distributed on \([0,1]\), the probability of a positive report is exactly \(u_t(x)\). This holds at both endpoints: the event \(T=0\) has probability zero, and \(T\leq1\) has probability one.

The positive mass calculation correctly uses the stipulated mass \(\mu_t/m\) in each project-query stratum. Rescaling gives precisely \(a_x\).

The equality
\[ W(S)=\sum_{x\in S}a_x \]
follows by interchanging finite sums. It applies to every subset \(S\), so it establishes that the observed scores contain all information needed for this welfare objective. Distinct utilities within each type neither invalidate the identity nor require additional algorithmic assumptions.

Assessment: Correct.

2. Exact optimization and distortion

The exact rule and the definition of \(\mathrm{OPT}\) use identical objectives and feasibility constraints. Consequently, every output selected by the exact rule has welfare \(\mathrm{OPT}\). Lexicographic tie-breaking does not affect this conclusion.

The proof also correctly excludes the zero-denominator case. Since the scores sum to \(1\), their maximum satisfies \(M\geq1/m>0\). Every singleton is feasible because every project has cost at most \(1\), giving \(\mathrm{OPT}\geq M\).

Thus the rule’s welfare is positive and equals \(\mathrm{OPT}\) on every admissible instance. Its distortion ratio is always \(1\), which establishes both the bound and sharpness.

Assessment: Correct; the denominator convention is fully addressed.

3. Scaling and dynamic programming

The scaling parameter \(K=\varepsilon M/m\) is positive. For every project,
\[ 0\leq q_i=\lfloor a_i/K\rfloor\leq m/\varepsilon, \]
because \(a_i\leq M\). Summing establishes \(Q\leq m^2/\varepsilon\).

The dynamic-programming state is defined precisely: it stores the minimum cost of a subset with exactly the specified rounded objective. The initialization handles both the empty subset and unreachable objectives correctly.

The recurrence correctly partitions subsets according to whether they contain project \(i\). Both branches refer to the preceding layer, so each project can appear at most once. This remains true when \(q_i=0\) or \(c_i=0\).

At least one final state is feasible, since the empty subset realizes objective zero at cost zero. Selecting the largest feasible objective and reconstructing a realizing subset therefore produces a feasible rounded-objective maximizer. Standard predecessor bookkeeping suffices for the stated reconstruction; no additional mathematical lemma is needed.

Assessment: Correct, including zero costs and zero rounded scores.

4. Approximation guarantee

The floor inequalities are valid:
\[ Kq_i\leq a_i,\qquad Kq_i\geq a_i-K. \]

Rounded optimality gives \(q(S)\geq q(S^\star)\). Applying the inequalities to the returned set and the optimal set yields the claimed chain:
\[ W(S)\geq Kq(S)\geq Kq(S^\star) \geq \mathrm{OPT}-|S^\star|K. \]

The final bounds have the correct directions. Specifically, \(|S^\star|\leq m\), \(mK=\varepsilon M\), and \(M\leq\mathrm{OPT}\), so
\[ W(S)\geq\mathrm{OPT}-\varepsilon M \geq(1-\varepsilon)\mathrm{OPT}. \]

Determinism makes the expectation guarantee immediate.

Assessment: Correct, with the stated constants and full range \(0<\varepsilon<1\).

5. Bit complexity and information access

The state count is at most \((m+1)(Q+1)\), giving \(O(m^3/\varepsilon)\) dynamic-programming operations.

The common-denominator argument is sound. The product of all input mass and utility denominators is divisible by the denominator of each mass–utility product. Its bit length is \(O(L)\), and each score lies in \([0,1]\), so its numerator under that common denominator also has polynomial bit length.

The analogous cost denominator has bit length \(O(L)\). Any subset cost is at most \(m\), yielding the stated \(O(L+\log m)\) numerator bound. Dynamic-programming additions and comparisons consequently have polynomial bit cost.

Scaling and computing floors also involve rational numbers of polynomial bit length when the accuracy parameter’s encoding is included, as the prover explicitly specifies. This is the standard FPTAS input convention; the original instance length \(L\) and the encoding length of \(\varepsilon\) should be understood separately when tracking input sizes literally.

The mechanism itself uses only scores, costs, and the accuracy parameter. Computing scores from the support is optional preprocessing, not additional information required by the mechanism. No enumeration of unlisted utility types occurs.

Assessment: Correct under the explicitly stated accuracy-encoding convention.

6. Cited results and scope

The source does describe cardinal welfare maximization as knapsack, reports NP-hardness even for one agent, and states the availability of fully polynomial-time approximation schemes. Its binary-query mechanism and Theorem 2 concern finite-population sampling. The prover’s distinction between those sampled reports and the stipulated exact scores is accurate. [Bhaskar, Dani, and Ghosh, Sections 1 and 3](https://ojs.aaai.org/index.php/AAAI/article/download/11480/11339)

The proof does not rely on transferring the finite-population theorem to the continuous setting or on importing an FPTAS without checking its applicability: it supplies the algorithm and its guarantee directly.

The result establishes polynomial-time approximation with dependence on \(1/\varepsilon\). It makes no unsupported claim that exact maximization is polynomial-time.

Required repair or clarification: None.

⟨structured verdict parsed — rendered above⟩