Reducing Leximin Fairness to Utilitarian Optimization

I would make a positive case, but a deliberately narrow one. The strongest mirror is the participatory-budgeting application, with the paper’s general reduction as a second anchor. The lottery over outcomes is not itself the continuization; that already exists in the paper. The new continuous object is the population of voters.

My lead anchor is Corollary 11.5, proved in this paper using Theorem 10.1 and the standard knapsack FPTAS:

“There is an FPTAS for leximin for participatory budgeting lotteries.”

A natural continuous version is the following.

Let \(P\) be a finite set of projects, with rational costs \(\operatorname{cost}(p)>0\), budget \(B\), and a finite set \(T\) of voter types. Type \(t\) has mass \(\mu_t\), where \(\sum_t\mu_t=1\), and an additive nonnegative valuation \(v_t(p)\) for each project. A type is complete: voters of the same type have the same valuation for every project and are otherwise indistinguishable to the problem.

The deterministic states remain genuinely discrete budget allocations,

\[ S=\{A\subseteq P:\sum_{p\in A}\operatorname{cost}(p)\le B\}. \]

A solution is a sparse lottery \(x\) over these states. If \(A\) is drawn, the selected projects are funded exactly as in the paper; no project is fractionally funded. The expected utility of type \(t\) is

\[ e_t(x)=\sum_{A\in S}x_A\sum_{p\in A}v_t(p). \]

To define fairness over the continuous society, give type \(t\) an interval of length \(\mu_t\) in the sorted population utility profile, with value \(e_t(x)\). Let \(Q_x(q)\) be the resulting lower-quantile step function. The required output is a sparse lottery \(x^\star\) whose quantile function is lexicographically maximal:

\[ Q_{x^\star}\succeq Q_x \]

for every feasible lottery \(x\). An \(\alpha\)-approximation satisfies \(Q_{x^\star}\succeq \alpha Q_x\) for every \(x\). For rational masses with a common denominator \(D\), this is exactly ordinary leximin applied to the finite profile containing \(D\mu_t\) copies of type \(t\), but the continuous algorithm must work on the compressed representation \((T,\mu)\), not expand \(D\) voters.

This is a faithful mirror of the paper’s problem. The projects, budget constraint, additive utilities, deterministic states, and ex-ante lottery are unchanged. Only the population representation changes from named voters to a distribution over complete valuation types. A plausible regime is a large participatory-budgeting electorate with millions of voters but a standardized catalogue of valuation profiles—say, repeated neighbourhood, demographic, institutional, or ballot-template types. One might have \(10^6\) voters and \(10^2\) or \(10^3\) distinct types. Individual targeting is deliberately absent, as it should be in a high-multiplicity model.

I expect the approximation version to be Class A. For any nonnegative type weights \(c_t\), the utilitarian pricing problem becomes

\[ \max_{A\in S}\sum_t c_t\mu_t\,v_t(A) = \max_{A\in S}\sum_{p\in A}\left(\sum_t c_t\mu_t v_t(p)\right), \]

which is still a knapsack instance. Thus the paper’s black-box mechanism has exactly the right continuous shape: population masses become coefficients, while the hard combinatorics remain in the state/pricing problem. The open technical step is a compressed, mass-weighted version of the paper’s leximin reduction whose running time depends polynomially on \(|P|\), \(|T|\), the encoding length, and \(1/\varepsilon\), rather than on the common denominator of the masses.

This mirror does not claim that exact optimization becomes easy. With just one voter type, population leximin is ordinary utilitarian optimization, hence exact 0–1 knapsack. That hardness is driven by the project set and budget, so it is a Class B boundary: continuity does not erase the underlying combinatorics. The FPTAS, however, is a genuine positive result for the continuous problem.

The broader anchor is Theorem 10.1, proved in this paper:

“Given an \(\alpha\)-approximate black-box for the utilitarian welfare, an \(\alpha\)-leximin-approximation can be computed in time polynomial in \(n\) and the running time of the black-box.”

Its continuous counterpart is the following general problem. The input is a finite type set \(T\), a mass vector \(\mu\), a succinctly represented deterministic state space \(S\), nonnegative type utilities \(u_t:S\to\mathbb{R}_{\ge0}\), and a zero-utility degenerate state. In addition, one is given a black box which, for every nonnegative coefficient vector \(c\), returns a state \(s\) satisfying

\[ \sum_t c_t\mu_tu_t(s) \ge \alpha\max_{s'\in S}\sum_t c_t\mu_tu_t(s'). \]

The task is to output a sparse lottery over \(S\) that is an \(\alpha\)-approximation to population leximin under the quantile definition above.

I expect this general problem also to be Class A relative to the pricing oracle. The paper’s proof already exposes the relevant structure: the exponential object is the state distribution, while separation reduces to a weighted utilitarian optimization. In the continuous version, the coefficients are simply \(c_t\mu_t\). The important caveat is that the theorem as printed is indexed by named agents and performs \(n\) leximin stages. Replacing that by a truly compressed weighted-quantile procedure is not automatic, especially when masses are binary-encoded and several types share the current bottleneck utility. That is a real research question, not a cosmetic change.

The mirror therefore covers the paper’s central reduction and its participatory-budgeting application, but not every application. I would not use giveaway lotteries as a primary anchor: once groups become infinitesimal, indivisibility of groups largely disappears and the mirror becomes less clean. Likewise, I would not lead with stochastic allocation of indivisible goods, because a continuum of recipients can make the aggregate allocation look fractionally divisible.

My weakest point is precisely the weighted leximin compression. The paper proves a result for \(n\) individual utilities; it does not prove that arbitrary population masses can be handled in time polynomial in the number of types and the bit-length of those masses. Also, exact identical valuation vectors across millions of voters are stylized. But these weaknesses do not undermine the mirror itself. The participatory-budgeting problem remains the authors’ problem, the deterministic outcomes remain discrete, the high-multiplicity regime is standard and plausible, and the computational boundary remains meaningful: approximation should inherit the knapsack FPTAS, while exact hardness survives through the projects rather than the population.

The main follow-up questions are whether Theorem 10.1 admits this weighted population compression, whether the resulting FPTAS has support polynomial in the number of types rather than the expanded electorate, and whether ex-ante population leximin can be combined with the paper’s desired ex-post fairness and truthfulness properties.