Auditing for Core Stability in Participatory Budgeting (d4-conf-wine-2022-0028)

Given a finite candidate set \(C\) of unit-cost projects, budget \(k\), audited committee \(W\subseteq C\), and finite approval-type support \(T\) with rational masses \(\mu_t\ge0\) summing to \(1\), where type \(t\) approves \(A_t\subseteq C\), define \(u_t(D)=|A_t\cap D|\) and \(M_\mu(D;W)=\sum_{t:u_t(D)>u_t(W)}\mu_t\). Ask for the exact value, or an \(\alpha\)-approximation, of \(\theta_c^\infty(W)=\inf_{D\subseteq C:M_\mu(D;W)>0}|D|/(kM_\mu(D;W))\); equivalently, decide or approximate whether some integral committee \(D\) satisfies \(|D|\le\theta kM_\mu(D;W)\).

Let \(C\) contain \(m\ge1\) unit-cost projects, let \(k>0\) be a binary rational budget, and let the audited committee \(W\subseteq C\) satisfy \(|W|\le k\).
A society is given by its support: the list of \(\tau\) approval types with positive binary rational masses \(\mu_t\) summing to \(1\), each specified by \(A_t\subseteq C\). Empty approval sets are allowed. Here \(\tau\) is the support size, not the number of possible approval sets; \(L\) is the total input bit length.
Types have approval utilities \(u_t\). Coalitions may take any fraction of each type's mass; a coalition of mass \(s\) has entitlement \(ks\). Projects remain indivisible.
For an integral committee \(D\subseteq C\), define \(M_\mu(D;W)=\sum_{t:u_t(D)>u_t(W)}\mu_t\) and \(\theta_c^\infty(W)=\inf_{D\subseteq C:M_\mu(D;W)>0}|D|/(kM_\mu(D;W))\). No separate constraint \(|D|\le k\) is imposed, and the infimum of the empty set is \(+\infty\).
For finite optimum, a multiplicative \(\alpha\)-approximation returns an integral \(D\) with positive improving mass and ratio at most \(\alpha\theta_c^\infty(W)\); instances with infinite optimum must be identified.

For each fixed \(0<\gamma<1/e\), is approximating \(\theta_c^\infty(W)\) within \(1+1/e-\gamma\) possible in time polynomial in \(m,\tau,L\), or is this approximation problem NP-hard?

For explicitly listed discrete voters, approximation within \(1+1/e-\gamma\) is NP-hard, while a polynomial-time \(O(\min(\log m,\log n))\)-approximation is known, where \(n\) is the voter count ([Munagala, Shen and Wang](https://arxiv.org/pdf/2209.14468)). No result explicitly treating the rational-support mass formulation was located.

Result

For every fixed \(0<\gamma<1/e\), approximating \(\theta_c^\infty(W)\) within \(1+1/e-\gamma\) is NP-hard. The discrete-voter hardness transfers through a polynomial-time reduction that preserves every committee’s objective value exactly.

Throughout, approval utility means \(u_t(D)=|A_t\cap D|\).

1. Fractional coalitions do not change the objective

Fix an integral committee \(D\subseteq C\), and define its improving types by
\[ I(D)=\{t:u_t(D)>u_t(W)\}. \]

A coalition whose members all strictly improve with \(D\) can select masses \(x_t\) satisfying
\[ 0\le x_t\le\mu_t\quad(t\in I(D)),\qquad x_t=0\quad(t\notin I(D)). \]
Consequently, its mass \(s=\sum_t x_t\) satisfies
\[ s\le\sum_{t\in I(D)}\mu_t=M_\mu(D;W). \]
Equality is attained by taking the entire mass of every improving type.

If \(M_\mu(D;W)>0\), then \(D\ne\varnothing\), because the empty committee gives every type utility zero. Thus, for every such coalition of positive mass,
\[ \frac{|D|}{ks}\ge \frac{|D|}{kM_\mu(D;W)}. \]
The right-hand side is attained by the coalition consisting of all improving types. Hence allowing arbitrary fractions of types does not yield a smaller ratio for any fixed committee.

2. The discrete hardness theorem applies to this ratio

Consider an explicitly listed discrete election with voters \(i\in\{1,\ldots,n\}\), approval sets \(B_i\subseteq C\), budget \(k>0\), and audited committee \(|W|\le k\). Write
\[ H(D)=\{i:|B_i\cap D|>|B_i\cap W|\}. \]

The discrete core-auditing objective is
\[ \theta_{\mathrm{disc}}(W)= \min_{\substack{D\subseteq C\\H(D)\ne\varnothing}} \frac{n|D|}{k|H(D)|}, \]
with value \(+\infty\) when no committee improves any voter.

Indeed, for a fixed \(D\), the admissible discrete coalitions are the nonempty subsets of \(H(D)\); taking all of \(H(D)\) minimizes the ratio.

Section 2 of Munagala, Shen and Wang gives precisely this optimization program, without an additional constraint \(|D|\le k\). Their Theorem 3.2 states that, for every constant \(\gamma>0\), approximating its value within \(1+1/e-\gamma\) is NP-hard, already for unit-cost projects and approval utilities. These hypotheses match the discrete instances used here. [Source: *Auditing for Core Stability in Participatory Budgeting*, Section 2 and Theorem 3.2](https://arxiv.org/pdf/2209.14468).

3. An objective-preserving reduction to rational support

Given such a discrete instance, retain \(C\), \(k\), and \(W\). Group voters having identical approval sets. For each distinct approval set \(A_t\), let
\[ f_t=|\{i:B_i=A_t\}|,\qquad \mu_t=\frac{f_t}{n}. \]

This is a valid support instance: each \(f_t\) is positive, each \(\mu_t\) is a positive rational, and
\[ \sum_{t=1}^{\tau}\mu_t =\frac{\sum_{t=1}^{\tau}f_t}{n} =1. \]
Empty approval sets are retained when present. Project costs and audited-committee feasibility are unchanged.

The construction is polynomial-time. Identical approval sets can be grouped by sorting their encodings. There are at most \(n\) resulting types; each mass has numerator and denominator requiring \(O(\log n)\) bits. Copying each distinct approval set once and adding these masses therefore produces an instance of polynomial bit length in the explicitly listed input.

For every \(D\subseteq C\), all voters grouped into one type have the same improvement status. Therefore
\[ M_\mu(D;W) =\sum_{t:|A_t\cap D|>|A_t\cap W|}\frac{f_t}{n} =\frac{|H(D)|}{n}. \]
In particular, positive improving mass is equivalent to \(H(D)\ne\varnothing\). Whenever these conditions hold,
\[ \frac{|D|}{kM_\mu(D;W)} =\frac{n|D|}{k|H(D)|}. \]

Thus the feasible committees and their objective values coincide exactly:
\[ \theta_c^\infty(W)=\theta_{\mathrm{disc}}(W). \]
This also preserves infinite optimum.

4. Approximation transfer and infinite instances

Fix \(0<\gamma<1/e\), and put \(\alpha=1+1/e-\gamma\). Suppose a polynomial-time \(\alpha\)-approximation existed for the rational-support problem.

Apply the reduction above to any discrete instance and run that algorithm. On a finite instance, its returned committee \(D\) would satisfy
\[ \frac{n|D|}{k|H(D)|} =\frac{|D|}{kM_\mu(D;W)} \le\alpha\theta_c^\infty(W) =\alpha\theta_{\mathrm{disc}}(W). \]
If a discrete coalition is required, return \(H(D)\). Its members all strictly improve. On an infinite instance, the algorithm’s identification of infinity is also correct for the discrete instance. Its running time remains polynomial in the discrete input length.

This would give the approximation ruled out by Theorem 3.2. Hence the rational-support approximation problem is NP-hard.

For completeness, infinite optimum itself is easy to recognize:
\[ \theta_c^\infty(W)=+\infty \quad\Longleftrightarrow\quad A_t\subseteq W\text{ for every }t. \]
If every \(A_t\subseteq W\), then \(u_t(D)\le |A_t|=u_t(W)\) for every committee. Conversely, if some \(A_t\not\subseteq W\), then \(D=C\) strictly improves that positive-mass type, giving a finite ratio. Checking these inclusions takes polynomial time.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned question: the rational-support approximation problem is NP-hard for every fixed \(0<\gamma<1/e\). The reduction preserves every integral committee’s objective value, and the cited theorem applies to the source problem. I found no major or minor mathematical issues.

1. Definitions and scope

The prover explicitly specifies approval utility as \(u_t(D)=|A_t\cap D|\), matching the intended approval model.

The argument keeps projects indivisible and allows every \(D\subseteq C\), without imposing \(|D|\le k\). It therefore addresses the objective in USER_TASK, including deviations whose size exceeds the original budget.

2. Fractional coalitions

For a fixed committee \(D\), the stated constraints on \(x_t\) correctly describe a coalition consisting entirely of strictly improving types.

Summing \(x_t\le\mu_t\) over improving types gives \(s\le M_\mu(D;W)\). Equality is attainable because taking each improving type’s entire mass is permitted.

The assertion that positive improving mass implies \(D\ne\varnothing\) is correct: approval utilities are nonnegative, whereas the empty committee gives utility zero. For positive coalition mass, both denominators in the displayed ratio comparison are positive because \(k>0\). Increasing coalition mass decreases that ratio, so taking all improving mass minimizes it.

This establishes precisely the claimed equivalence for each fixed committee. Fractional participation introduces no discrepancy between the two objectives.

3. Cited discrete hardness theorem

I checked the cited paper. Section 2 minimizes the committee-size-to-coalition-size ratio multiplied by \(n/k\), with binary project and voter variables and strict improvement encoded by the approval threshold. It imposes no additional committee-size constraint. Section 3 explicitly restricts its hardness results to unit-cost projects and approval utilities; Theorem 3.2 states the claimed approximation hardness. These match the source instances used by the prover. [Munagala, Shen and Wang, Sections 2–3](https://arxiv.org/pdf/2209.14468)

For fixed \(D\), admissible nonempty discrete coalitions are exactly the nonempty subsets of \(H(D)\). Taking \(H(D)\) itself minimizes the ratio. Thus the prover’s formulation of \(\theta_{\mathrm{disc}}(W)\) correctly represents the cited optimization problem.

The target range \(0<\gamma<1/e\) lies within the stated theorem’s range and gives a meaningful approximation factor greater than one. No theorem hypothesis is left unverified.

4. Validity and size of the reduction

Grouping identical approval sets is valid because those voters have identical utility on every committee, including \(W\).

Every resulting frequency \(f_t\) is a positive integer, so \(\mu_t=f_t/n\) is a positive rational. The groups partition the electorate, giving total mass one. Empty approval sets remain legitimate types. Retaining \(C\), \(k\), and \(W\) preserves unit costs, positive budget, and audited-committee feasibility.

The polynomial-size claim is correct for explicitly listed voters:

• There are at most \(n\) groups.
• Each numerator and denominator has \(O(\log n)\) bits.
• Grouping explicitly encoded approval sets takes polynomial time.
• Copying each distinct approval set once produces polynomial total output length.

Consequently, a running time polynomial in the target parameters \(m,\tau,L\) becomes polynomial in the source input size. The argument does not require expanding arbitrary rational masses into discrete voters.

5. Exact preservation of objectives

For every \(D\subseteq C\), improvement is constant within each group. Therefore the displayed equality
\[ M_\mu(D;W)=\frac{|H(D)|}{n} \]
is correct.

It follows that positive improving mass and a nonempty improving voter set are equivalent. Substitution then yields
\[ \frac{|D|}{kM_\mu(D;W)} =\frac{n|D|}{k|H(D)|}. \]

Both objectives range over the same finite family of integral committees with positive improvement. Their finite optima therefore coincide exactly; if that family is empty, both values are \(+\infty\). There is no unattained-infimum issue.

6. Approximation transfer

The approximation inequality follows directly from the established objective equality. The returned committee is a valid discrete witness, and returning \(H(D)\) gives a coalition whose members all strictly improve.

The running-time transfer follows from the polynomial reduction. Thus a polynomial-time approximation for the rational-support formulation would provide the approximation excluded by the cited discrete hardness theorem.

7. Infinite optimum

The stated characterization is correct in both directions.

If every \(A_t\subseteq W\), each type already receives its maximum approval utility, so no committee strictly improves any type.

If some \(A_t\not\subseteq W\), the permitted committee \(D=C\) strictly improves that type. Its mass is positive, and its ratio is finite because \(k>0\).

Checking the inclusions takes polynomial time. This also verifies the task’s requirement concerning infinite instances.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩