Reducing Leximin Fairness to Utilitarian Optimization (aaai25-33521)

Given rational project costs, a budget, nonnegative additive valuations for a finite set of complete voter types, rational type masses summing to one, and an accuracy parameter ε, compute in time polynomial in the number of projects, types, input length, and 1/ε a sparse lottery over budget-feasible project subsets whose population utility quantile function is a (1−ε)-leximin approximation among all such lotteries.

Let \(P\) contain \(m\geq1\) projects, with binary rational costs \(c_p>0\) and budget \(B>0\). Feasible outcomes are \(\mathcal S=\{S\subseteq P:\sum_{p\in S}c_p\leq B\}\), including \(\varnothing\).
A society is given by its support: a list of \(\tau\geq1\) complete voter types, each specifying binary rational additive values \(v_{t,p}\geq0\) and a positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total binary input length.
For any lottery \(x\) over \(\mathcal S\), define \(U_t(x)=\sum_{S\in\mathcal S}x_S\sum_{p\in S}v_{t,p}\) and its population quantile \(Q_x(q)=\inf\{z:\sum_{t:U_t(x)\leq z}\mu_t\geq q\}\), for \(0<q<1\).
For finite step functions \(f,g\), write \(f\succeq_{\mathrm{lex}}g\) if they agree almost everywhere, or if, on the leftmost open interval of their common breakpoint partition where their values differ, the value of \(f\) is larger. Thus tied utilities pool their masses and isolated endpoints are ignored.
For rational \(0<\varepsilon<1\), a lottery \(x^A\) is a \((1-\varepsilon)\)-leximin approximation when \(Q_{x^A}\succeq_{\mathrm{lex}}(1-\varepsilon)Q_x\) for every lottery \(x\) over \(\mathcal S\). A sparse output lists feasible subsets and positive rational probabilities summing to one, with total encoding length polynomial in \(m,\tau,L,1/\varepsilon\).

Does this problem admit an FPTAS that computes such a sparse \((1-\varepsilon)\)-leximin approximation in time polynomial in \(m,\tau,L,1/\varepsilon\), or can such an approximation scheme be ruled out unless \(\mathrm{P}=\mathrm{NP}\)?

For an explicitly listed finite electorate with nonnegative additive utilities, an FPTAS for the corresponding expected-utility leximin approximation is established by [Hartman et al.](https://arxiv.org/html/2409.10395v4#S11.SS3).
No result settling exactly the rational-mass population-quantile formulation above was located in the literature search.

Result

An FPTAS exists. The rational masses need not be expanded into individual voters. The key is to remove types whose utility is identically zero and invoke the finite-electorate FPTAS with error \(\varepsilon/2\). This creates a strict advantage at the first quantile interval where a comparison can differ.

1. Identify types that can receive positive utility

Define
\[ A=\{t:\text{there exists }p\in P\text{ with }c_p\leq B\text{ and }v_{t,p}>0\}. \]
Here and below, displayed formulas use the same mathematical notation as inline formulas.

For every \(t\notin A\), every feasible outcome gives utility zero. Indeed, if \(p\in S\) for a feasible \(S\), positivity of costs implies \(c_p\leq B\), and the definition of \(A\) then gives \(v_{t,p}=0\). Consequently, \(U_t(x)=0\) for every lottery \(x\).

If \(A=\varnothing\), output the lottery concentrated on \(\varnothing\). Every quantile function is identically zero, so the required guarantee holds.

Henceforth assume \(n=|A|\geq1\). Define
\[ M=\max_{x\text{ over }\mathcal S}\min_{t\in A}U_t(x). \]

This maximum exists: \(\mathcal S\) is finite, its lottery simplex is compact, and the minimum of finitely many linear utility functions is continuous.

Moreover, \(M>0\). For each \(t\in A\), choose an affordable project \(p(t)\) with \(v_{t,p(t)}>0\). The lottery choosing each singleton \(\{p(t)\}\) with probability \(1/n\), combining repeated singletons, gives every \(t\in A\) utility at least \(v_{t,p(t)}/n>0\). Its minimum utility over \(A\) is therefore positive.

2. Apply the finite-electorate FPTAS

We use the finite-electorate result supplied in the question. In its notation, for any rational \(0<\delta<1\), it computes a sparse rational lottery \(y\) satisfying
\[ \bigl(U_t(y)\bigr)_{t\in A}^{\uparrow} \succeq_{\mathrm{lex}} (1-\delta)\bigl(U_t(x)\bigr)_{t\in A}^{\uparrow} \quad\text{for every lottery }x. \]
Here \({}^{\uparrow}\) means sorting in nondecreasing order, and the comparison is ordinary lexicographic comparison of vectors. The approximation definition and the budgeting FPTAS are given in [Hartman et al., Definition 3.2 and Corollary 11.5](https://arxiv.org/html/2409.10395v4#S11.SS3).

Construct this finite electorate by giving one voter to each type in \(A\), with its original additive values. The hypotheses hold: the electorate is explicitly listed, utilities are nonnegative and additive, outcomes are the original budget-feasible subsets, and \(\varnothing\) gives every voter utility zero.

Run its FPTAS with
\[ \delta=\varepsilon/2,\qquad \beta=1-\varepsilon/2,\qquad \alpha=1-\varepsilon. \]
Return its lottery \(y\).

The first coordinate of the vector guarantee implies
\[ \min_{t\in A}U_t(y)\geq \beta\min_{t\in A}U_t(x) \quad\text{for every }x. \]
Otherwise the output would already lose at the first coordinate. Applying this inequality to a maximizer defining \(M\), and writing \(d=\min_{t\in A}U_t(y)\), gives
\[ d\geq\beta M>\alpha M. \]
The strict inequality follows from \(M>0\) and \(\beta>\alpha\).

In particular, for every benchmark lottery \(x\), if \(b=\min_{t\in A}U_t(x)\), then
\[ d>\alpha M\geq\alpha b. \]

3. Verify the population-quantile guarantee

Fix any benchmark lottery \(x\). Let
\[ z=\sum_{t\notin A}\mu_t,\qquad h_y=\sum_{\substack{t\in A\\U_t(y)=d}}\mu_t,\qquad h_x=\sum_{\substack{t\in A\\U_t(x)=b}}\mu_t. \]

Since \(A\neq\varnothing\) and all masses are positive, \(z<1\), \(h_y>0\), and \(h_x>0\).

If \(z>0\), both \(Q_y\) and \(\alpha Q_x\) equal zero throughout \(0<q<z\): the types outside \(A\) have utility zero under both lotteries, and all utilities are nonnegative.

Now consider the nonempty open interval
\[ I=(z,\ z+\min\{h_y,h_x\}). \]
The definition of the quantile gives, throughout \(I\),
\[ Q_y(q)=d,\qquad Q_x(q)=b. \]

For the output, all types in \(A\) have utility at least \(d>0\), and mass \(h_y\) attains \(d\). For the benchmark, if \(b>0\), the same reasoning applies after the permanent zero mass \(z\). If \(b=0\), its zero-utility mass includes both \(z\) and \(h_x\), so its quantile is still \(b=0\) on \(I\).

Thus, throughout \(I\),
\[ Q_y(q)=d>\alpha b=\alpha Q_x(q). \]

The functions agree on every earlier open interval and the output is strictly larger immediately after \(z\). Therefore their leftmost differing interval in the common breakpoint partition favors the output. Isolated endpoints do not affect the comparison, exactly as required in the question. Hence
\[ Q_y\succeq_{\mathrm{lex}}(1-\varepsilon)Q_x. \]
Because \(x\) was arbitrary, \(y\) satisfies the requested approximation guarantee.

4. Running time and sparse encoding

Finding \(A\) requires checking at most \(m\tau\) rational cost and value conditions. The constructed finite electorate contains at most \(\tau\) voters and has encoding length polynomial in \(L\).

The finite-electorate FPTAS is called with \(1/\delta=2/\varepsilon\). Its running time and sparse rational output length are therefore polynomial in \(m,\tau,L,1/\varepsilon\). Its listed subsets remain feasible for the original instance, and its probabilities sum to one. Zero-probability entries, if present in the representation, can be discarded.

No voter replication or computation involving a common denominator of the masses is needed. The proof uses their positivity; their numerical sizes do not affect the algorithm.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated task. Its reduction is correct: after removing types whose utilities are always zero, the stronger approximation factor creates a strict advantage at the first quantile interval that can differ. Unequal rational masses do not invalidate this argument.

• Identifying permanently zero types is correct.

Every project in a feasible subset satisfies \(c_p\leq B\), because all costs are positive. Therefore, for \(t\notin A\), every project that can occur in a feasible outcome has \(v_{t,p}=0\). Hence \(U_t(x)=0\) for every lottery \(x\).

If \(A=\varnothing\), every population quantile is zero. The proposed lottery concentrated on \(\varnothing\) satisfies the guarantee and output requirements.

• Existence and positivity of \(M\) are established.

The feasible-outcome family is finite and nonempty, so its lottery simplex is compact. The function \(x\mapsto\min_{t\in A}U_t(x)\) is continuous, establishing attainment of \(M\).

The singleton lottery described in the output is feasible. Each active type receives its selected positive-valued project with probability at least \(1/n\); repeated singletons can be combined without changing this fact. Nonnegative utilities ensure that other singleton outcomes cannot reduce its expected utility. Thus every active type has strictly positive expected utility, and \(M>0\).

• The cited finite-electorate guarantee matches the invocation.

Definition 3.2 gives the universal multiplicative leximin comparison used by the prover, and Corollary 11.5 supplies the participatory-budgeting FPTAS. The paper also specifies sparse lottery representations and polynomial-support outputs. These are the relevant external guarantees, rather than an approximation under a different leximin definition. [Hartman et al., Sections 3 and 11.3](https://arxiv.org/html/2409.10395v4#S11.SS3).

The constructed electorate satisfies the stated hypotheses: it is explicitly listed, has nonnegative additive utilities, uses the original feasible outcomes, and includes the common zero-utility outcome \(\varnothing\). Giving each active type one voter is legitimate here: the subsequent argument uses only the resulting minimum-utility guarantee, not an identification of equal-weight and population-weighted leximin orders.

• The strict minimum-utility comparison follows.

Lexicographic dominance of the sorted vectors forces dominance at their first coordinates. Consequently, the returned lottery satisfies
\[ d\geq\beta M. \]
Since \(M>0\) and \(\beta>\alpha>0\), the prover correctly obtains
\[ d\geq\beta M>\alpha M\geq\alpha b \]
for every benchmark lottery, where \(b=\min_{t\in A}U_t(x)\). The final inequality uses \(b\leq M\).

The quantifiers are correct: one returned lottery satisfies this comparison simultaneously for every benchmark.

• The quantile argument handles unequal masses and ties correctly.

Positivity of all masses and nonemptiness of \(A\) give \(z<1\), \(h_y>0\), and \(h_x>0\). Moreover, both minimum-attaining masses are at most \(1-z\), so the interval
\[ I=(z,z+\min\{h_y,h_x\}) \]
is nonempty and lies in the quantile domain.

Before \(z\), both quantile functions are zero. Immediately after \(z\), the output quantile equals \(d\). If \(b>0\), the benchmark quantile equals \(b\) through its first active utility block. If \(b=0\), the additional active zero-utility mass keeps the benchmark quantile at zero throughout \(I\). Thus the claimed formulas on \(I\) hold in both cases.

Any additional breakpoints within earlier zero-valued regions leave the functions equal. The first differing open interval therefore favors the output. Pooling tied utilities and ignoring isolated endpoints are handled exactly as required. The cases \(z=0\), \(n=1\), and an interval ending at \(1\) cause no exception.

• The complexity and output claims follow from the invoked FPTAS.

Identifying \(A\) requires polynomially many rational comparisons. Restricting the listed utility table produces an instance of polynomial encoding length, with at most \(\tau\) voters. The accuracy parameter satisfies \(1/\delta=2/\varepsilon\).

The polynomial-time sparse-output guarantee therefore gives the required polynomial encoding length under the standard binary rational interpretation of the supplied FPTAS. The reduction preserves feasibility and normalization; deleting zero-probability entries preserves both. No population replication is performed.

No false statement, unjustified substantive step, or missing lemma was found. No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩