Metric Distortion Under Group-Fair Objectives

The honest qualification comes first: this paper contains no named theorem establishing NP-hardness, membership in \( \mathrm{P} \), W[1]-hardness, FPT, or any comparable complexity classification. Its numbered results are distortion theorems. Thus, under ChoCo’s strict anchor rule, it has no admissible complexity anchor and cannot by itself support a Class A/B/C verdict.

If named approximation theorems count as a broader algorithmic anchor, the strongest positive case is its Max-of-Avg result.

Theorem 4.3, proved in this paper, says: for Max-of-Avg, an ordinal-information group-oblivious mechanism that returns an alternative whose domination graph has a perfect matching has distortion at most \(5\). The groups are unknown to the mechanism; it sees only ordinal preferences. The supporting Lemma 4.2, also proved here, states that if \(x\)'s domination graph has a perfect matching, then for every alternative \(y\),
\[ d(x,y)\le \frac{4}{n}\sum_{i\in N}d(i,y). \]
Theorem 4.1, likewise proved here, gives the matching lower bound: every ordinal-information group-oblivious mechanism for Max-of-Avg has distortion at least \(5-\varepsilon\), for every \(\varepsilon>0\), even with two alternatives and symmetric groups.

My proposed mirror is:

\[ \textit{Continuous Group-Fair Max-of-Avg Voting}. \]

An instance has a finite alternative set \(A\), \(k\) hidden groups, and a finite set of complete ground types \(\Theta\). A type \(\theta\) records its group \(g(\theta)\), ordinal ranking \(r(\theta)\), and its cardinal metric profile \(d_\theta(a)\) over alternatives. Its mass is \(\mu_\theta\in\mathbb{Q}_{\ge0}\), with \(\sum_\theta\mu_\theta=1\). The full type includes the group and cardinal profile, so agents of one type are genuinely interchangeable. The mechanism observes only the ranking distribution
\[ \bar\mu_r=\sum_{\theta:r(\theta)=r}\mu_\theta, \]
not the group labels or cardinal distances.

For a group \(g\), let \(M_g=\sum_{\theta:g(\theta)=g}\mu_\theta\). The continuous objective is
\[ \operatorname{MaxAvg}_\mu(a) = \max_{g\in[k]} \frac{1}{M_g} \sum_{\theta:g(\theta)=g}\mu_\theta d_\theta(a). \]

The mechanism must output an alternative \(x\). To mirror the paper’s perfect-matching rule, it may also output a mass coupling \(z_{r,s}\) between left-hand ranking mass and right-hand ranking mass, satisfying
\[ \sum_s z_{r,s}=\bar\mu_r, \qquad \sum_r z_{r,s}=\bar\mu_s, \]
with \(z_{r,s}>0\) only when ranking \(r\) ranks \(x\) at least as highly as the top alternative of ranking \(s\). This is the continuous domination-graph condition: a fractional perfect matching, or equivalently a transportation-feasibility certificate.

The question is to design a mechanism \(M\) mapping the visible distribution \(\bar\mu\) to such an \(x\), minimizing
\[ \sup_I \frac{\operatorname{MaxAvg}_{\mu^I}(M(\bar\mu^I))} {\min_{a\in A}\operatorname{MaxAvg}_{\mu^I}(a)}, \]
where the supremum ranges over all hidden group assignments and metric realizations consistent with the observed rankings. A solution is an alternative together with its feasible mass coupling, and globally a mechanism with the smallest worst-case ratio.

This is a convincing population mirror in a high-multiplicity regime: many residents belong to a bounded number of districts or communities, and within each district many residents share one of finitely many standardized preference-and-location profiles. Thus \(n\) is large while the number of distinct complete types is moderate. Rational masses expand exactly into finite populations, while finite populations aggregate back to rational masses. The group objective is unchanged: finite group averages become conditional expectations, not a different fairness criterion.

The paper’s proof transfers cleanly. A finite profile with \(n_{g,t}\) agents corresponds to \(\mu_{g,t}=n_{g,t}/n\), and
\[ \frac{\sum_t n_{g,t}d_t(a)}{\sum_t n_{g,t}} = \frac{\sum_t\mu_{g,t}d_t(a)}{M_g}. \]
The domination graph becomes a mass-transport polytope. The triangle-inequality argument in Theorem 4.3 then becomes an integral argument, yielding the same upper bound \(5\). Normalizing the constructions of Theorem 4.1 supplies the corresponding \(5-\varepsilon\) lower-bound family. I would therefore expect this mirror to retain the paper’s sharp \(5\) distortion threshold, with the matching certificate computable by transportation or max-flow methods.

This is not a weakened problem: it preserves the groups, the Max-of-Avg objective, ordinal information, metric uncertainty, and group-obliviousness. It merely replaces a repeated finite population by its empirical distribution.

The scope is deliberately limited to Section 4.1: ordinal-information, group-oblivious Max-of-Avg voting. I would not automatically extend it to Avg-of-Max, where a vanishing-mass outlier can still determine a group maximum, or to group-aware mechanisms without specifying whether maxima mean support maxima or essential suprema.

The weakest point is also decisive for the formal programme: Theorem 4.3 is an approximation guarantee, not a complexity theorem. The continuous matching subproblem is algorithmically tractable, but the paper does not establish a ChoCo-style complexity classification, nor does it show that any discrete NP-hardness dissolves. So this is a strong, natural continuous mirror of the paper’s problem, but only a candidate starting point for a later complexity study—not evidence that this paper itself fills the computational gap.