Greedy Selection for Gini-Fair Objectives Across Many Groups

Many selection problems have several stakeholders at once. Examples include picking $B$ seed users to spread information to six language communities, choosing products that serve several customer segments, or choosing a committee for many voters. Each stakeholder's benefit from the chosen set typically shows diminishing returns (it is submodular), and for such functions a simple greedy algorithm provably reaches about 63% of the best possible value. The trouble begins when we aggregate across stakeholders. Summing their benefits lets a majority crowd out minorities. Maximizing the benefit of the worst-off group is hostage to a single hopeless group, and it is provably inapproximable when the budget is small. The middle ground is ordered weighted averaging (OWA): sort the groups by how well they are served and give larger weights to the worse-off positions. This is the Generalized Gini welfare used in fair division. It has no scalable algorithm with a guarantee, because sorting destroys the diminishing-returns structure that greedy relies on.

This note proposes an algorithm for that middle ground and a matching guarantee. The key observation is that a Gini-fair OWA of $k$ group utilities equals the worst case of a weighted sum, where an adversary chooses the weights from the permutahedron (all reorderings of the OWA weight vector and their mixtures). The worst case over that set can be computed simply by sorting. This makes Gini-fair selection a robust submodular problem with a very structured adversary. The recent max-min method, LP Greedy, handles only the special case where the adversary may pick any single group. We extend it to the permutahedron. The central conjecture is that the budget needed for a near-$(1-1/e)$ guarantee shrinks smoothly as the OWA weights become less extreme. At one end it matches LP Greedy's requirement for pure max-min, and at the other it approaches no requirement for the plain average.

Core Claim

Let $f_1,\dots,f_k$ be monotone submodular utilities for $k$ groups over a ground set $V$. Let $w_1 \ge \dots \ge w_k \ge 0$ with $\sum_j w_j = 1$ be fairness weights, applied to the groups' utilities sorted from worst-off to best-off. Write $\mathcal{P}(w)$ for the permutahedron of $w$, the convex hull of all permutations of $w$. The objective and its robust form are

$$\text{GGF}_w(S) = \sum_{j=1}^k w_j\, f_{[j]}(S) = \min_{p \in \mathcal{P}(w)} \sum_{i=1}^k p_i f_i(S),$$

where $f_{[j]}(S)$ is the $j$-th smallest group utility. The identity holds because a linear function over the permutahedron is minimized by pairing the largest weight with the smallest utility, which is exactly what sorting does. The min over the simplex (LP Greedy's case) is recovered at $w=(1,0,\dots,0)$, and the plain average is recovered at $w=(1/k,\dots,1/k)$, where $\mathcal{P}(w)$ collapses to a single point.

We claim that a randomized greedy procedure achieves $\text{GGF}_w(S) \ge (1-1/e-\epsilon)\,\text{OPT}$ with high probability. At each step it solves a small concave program for a distribution over elements, with the adversary restricted to $\mathcal{P}(w)$, and then samples from that distribution. The budget condition is conjectured to scale with an effective number of groups, $k_{\text{eff}}(w)$, rather than with $k$ itself. Concretely, we conjecture $B = \Omega(k_{\text{eff}}(w)\log k/\epsilon^3)$ with $k_{\text{eff}}$ between 1 and $k$, and candidates are $k\,\|w\|_2^2$ or $k\,w_1$.

The intuition comes from where LP Greedy loses its guarantee. Sampling makes each group's realized gain noisy, and the min operator exposes the single unluckiest group. A Gini-fair OWA instead averages the noise over the worst-off block of groups, so deviations partly cancel.

Relation to Prior Work

The closest works fall into three groups: one supplies the method, one supplies the structure, and one motivates the gap.

The method comes from An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale. That paper maximizes $\min_i f_i(S)$ with LP Greedy, which finds a distribution over elements via multiplicative weights, samples from it, and uses martingale concentration. It proves $(1-1/e-\epsilon)$ when $B \ge \Omega(k\log k/\epsilon^3)$. It covers only the extreme OWA vector and says nothing about intermediate weights. We replace the simplex adversary with a permutahedron adversary and re-derive the concentration step under an OWA-weighted deviation.

Distributionally Robust Submodular Maximization also reweights submodular objectives adversarially. Its adversary lives in a $\chi^2$ ball, which it shows is equivalent to variance regularization, and it optimizes with momentum Frank-Wolfe on the multilinear extension. The weights are therefore divergence-based rather than rank-based, and it pays the cost of evaluating the continuous extension, which we avoid.

The structure comes from two sources. Coresets for Ordered Weighted Clustering shows that any non-increasing ordered objective is a nonnegative combination of "sum of the $p$ extreme values" objectives. It uses this for coresets, not for selection. We use the same decomposition to show that $\mathcal{P}(w)$ is an intersection of capped simplices, which gives a fast projection and a clean regret bound for the adversary.

Finding a collective set of items proves that OWA applied within each agent's view of the committee, followed by a sum across agents, is submodular and so greedy-friendly. We study the opposite nesting: OWA across agents, which is not submodular. That paper's hardness results for "finicky" weight vectors also constrain us. We restrict attention to non-increasing fairness weights and make no claims about arbitrary OWA vectors.

The gap is motivated by two papers that solve inter-agent Gini-fair OWA exactly or by LP proxies. OWA for Bipartite Assignments handles matching, places fair OWA in XP, and proves that single-interval proxies are at best logarithmic approximations. Active Preference Learning Based on Generalized Gini Functions uses branch-and-bound on knapsack instances of at most 10 agents and 100 items. Neither offers a scalable greedy guarantee for submodular utilities. The logarithmic lower bound in the matching paper concerns interval proxies specifically, so it does not contradict a constant factor here; our setting also has a cardinality constraint rather than a matching.

Research Program

The algorithm is built in three steps.

Step one: the per-step subproblem. Given the current set $S$ and a guess $\tau$ of the optimum, we seek a distribution $x$ over elements such that the expected gain vector $g(x)$ satisfies $\text{GGF}_w(f(S) + B\,g(x)) \ge \tau$. A feasible $x$ exists: the uniform distribution over the optimal set works by submodularity and concavity of $\text{GGF}_w$ in the utility vector. We solve this by a zero-sum game. The adversary runs follow-the-regularized-leader over $\mathcal{P}(w)$, where projection is isotonic regression and costs $O(k\log k)$. The selector best-responds by choosing the element with the largest $p$-weighted marginal gain. The two players' averaged play gives $x$. The guess $\tau$ is set by bisection, as in LP Greedy.

Step two: sampling and the guarantee. We sample an element from $x$ and repeat for $B$ steps. The analysis follows LP Greedy's Azuma argument but bounds the OWA of the deviation vector instead of its maximum entry. This is where $k_{\text{eff}}(w)$ should appear. Proving the tight form of $k_{\text{eff}}$ is the main theoretical deliverable. A lower bound showing the dependence cannot be removed would complete the picture.

Step three: small budgets. For budgets below the threshold we also study a deterministic variant, "sort-reweight greedy." At each step it takes the current adversarial $p$ and adds the element with the best $p$-weighted gain. We will try to prove a weaker but budget-free bound for it, expressed in terms of $w$. We also report where it empirically fails.

Baselines

Plain greedy on group average. The naive reference point is standard greedy on the sum of group utilities. This is the utilitarian choice, carries the classic $(1-1/e)$ guarantee from Maximizing the spread of influence through a social network, and is what practitioners run by default. On Twitch Gamers it is known to be badly skewed: Fair Submodular Cover reports "over 80% of the selected users being English speakers." Beating it means higher $\text{GGF}_w$ at equal $B$ while losing a stated, small fraction of total utility.

LP Greedy. The strongest existing method with a guarantee is LP Greedy from An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale. We run it in two ways. First, as its authors intend, it maximizes the minimum, and we then score its output under $\text{GGF}_w$. Second, it is applied to each $p$-extreme component of the decomposition, and we keep the best result. It uses the same oracle calls, the same bisection tolerance, the same random seeds, and a matched wall-clock budget. The file reports only that LP Greedy beats Saturate, Greedy Round Robin, and Frank-Wolfe on the synthetic coverage graphs, Amazon co-purchasing graphs, and Antelope Valley networks. No reported result was found on Lacuna for its numerical objective values, so we rerun it ourselves on every instance. Beating it means strictly higher $\text{GGF}_w$ for intermediate $w$ at every budget. The win should be largest at small $B$.

Naive greedy on the OWA objective. This greedily adds whichever element most increases $\text{GGF}_w$ itself. It has no guarantee because the objective is not submodular.

Continuous robust method. We adapt momentum Frank-Wolfe from Distributionally Robust Submodular Maximization, replacing its $\chi^2$ adversary with $\mathcal{P}(w)$. We give it the same total number of function evaluations.

Ground truth on small instances. On instances small enough, exact integer programming using Ogryczak's linear form for Gini welfare gives the true optimum. This lets us report approximation ratios rather than only relative rankings.

Ablation. The ablation that isolates our key ingredient replaces the permutahedron adversary with a simplex adversary while keeping the OWA scoring. If the permutahedron adds nothing, the two will match. The deterministic sort-reweight variant is a second ablation, testing whether randomization matters.

Why not just…?

Why not just fix group weights and run ordinary greedy on the weighted sum? A fixed weighted sum is submodular, so greedy is guaranteed. However, the right weights depend on which groups end up worst-off, and that is unknown until the set is chosen. Active Preference Learning Based on Generalized Gini Functions makes the same point about transfers to the currently worse-off. Our method is precisely a principled way to find those weights, so the comparison is fair. We will also run an oracle version that fixes the adversary's final equilibrium weights in hindsight. If that oracle nearly matches our method, the contribution is mainly the guarantee rather than the empirical gain, and we will say so.

Why not just run LP Greedy on the minimum and accept its fairness? Pure max-min lets one hard-to-serve group dictate the whole selection. It is also provably inapproximable at small budgets. The budget sweep, which compares both methods' $\text{GGF}_w$ as $B$ shrinks relative to $k$, settles this directly.

Why not just greedily maximize the OWA objective itself? This is the real threat. It is cheap and may perform well on natural graphs. We will construct adversarial instances where its myopia strands a group, for example when one element helps many groups slightly and another rescues a single group. We will also report honestly if it ties on real data. In that case the proposal's value is the guarantee and the explanation of when the naive method is safe.

Why not just use hard group quotas? Fair Submodular Cover shows that rigid quotas stall greedy and require relaxed constraints. Fair Representation in Submodular Subset Selection argues that single-constraint formulations miss the tradeoff between utility and representation. A Gini-fair objective expresses that tradeoff through $w$ without fixing counts in advance.

Proposed Experiments

We use four sets of benchmarks. The first three come from the LP Greedy paper: synthetic max-$k$-cover graphs (Kronecker, Barabási-Albert, Erdős-Rényi), Amazon co-purchasing graphs with product categories as groups, and the 500-node Antelope Valley networks with demographic groups. The fourth is Twitch Gamers with six language groups, plus Facebook, DBLP, and Pokec with community groups, following Fair Representation in Submodular Subset Selection. Weight families range from max-min to mean. We use geometric decay $w_j \propto r^{j}$ with $r$ swept, Gini weights $w_j \propto (2(k-j)+1)$, and "average of the worst $p$ groups." The number of groups $k$ ranges from 6 up to about 100, with synthetic groups created by splitting communities. Metrics are $\text{GGF}_w$, total utility, the minimum group utility, the ratio to exact optimum on small instances, and oracle calls.

The decisive empirical check is the budget sweep. For each $w$ we find the smallest $B$ at which our method reaches 95% of its large-budget ratio to the best known solution, and we plot that threshold against $k$. If the conjecture holds, the threshold should grow roughly like $k\log k$ for max-min, flatten as $w$ becomes more even, and follow $k\,\|w\|_2^2$ or $k\,w_1$ closely enough to discriminate between the two candidates. If the threshold does not move with $w$, the conjectured interpolation is false. The contribution would then reduce to an OWA-compatible LP Greedy, and we would report it as such.

A second check uses the adversarial instances against naive OWA greedy. It should show a constant-factor gap there and near-parity elsewhere.