Individual Fairness under Group Fairness Constraints in Bipartite Matching - One Framework to Approximate Them All

The strongest case is a genuine Class-A mirror of the paper’s exact disjoint-group result, with Theorem 3.7 as the lead anchor. The paper’s named algorithmic results are not merely imported from related work: Theorem 3.7 and Theorem 4.1 are the authors’ results, with proofs supplied in the cited full version [Panda et al., 2024]. Theorem 4.1 is the formal version of Theorem 3.4.

The high-multiplicity regime is plausible in, for example, a national school, grant, or training-program allocation round. There may be \(N\) applicants, a fixed set \(P\) of perhaps \(20\)–\(100\) programmes, and only \(\tau\ll N\) applicant types. A type records the applicant’s eligibility set, ranking of programmes, group membership, and the entire vector of individual-fairness bounds \(L_{t,k},U_{t,k}\). In a disjoint-group instance, it also records one protected category \(g(t)\). These are genuine cohorts: applicants in the same administrative category receive the same ranking template, eligibility rules, and fairness policy. Platform quotas scale with the cohort size, so an integer quota \(u_{p,h}\) becomes a rational mass quota \(u_{p,h}/N\). The platforms remain finite, named resources; only the applicant population is continuized.

My lead problem is Continuous Strong-BoBW Matching.

An instance consists of a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), platforms \(P\), a disjoint group map \(g:T\to[\chi]\), eligible sets \(N_t\subseteq P\), rankings \(R_t\), top-\(k\) sets \(R_{t,k}\), rational strong group-fairness bounds \(\ell_{p,h},u_{p,h}\), and rational individual-fairness bounds \(L_{t,k},U_{t,k}\). A pure continuous matching assigns atomless mass of each type to eligible platforms. If \(y_{t,p}\) is the mass of type \(t\) assigned to \(p\), then \(\sum_{p\in N_t}y_{t,p}\le\mu_t\), and the group load is \(X_{p,h}=\sum_{t:g(t)=h}y_{t,p}\). Every pure matching in the support must satisfy \(\ell_{p,h}\le X_{p,h}\le u_{p,h}\).

The output is a finite lottery \(D=\{(\alpha_j,y^j)\}_j\) over such pure continuous matchings. Its type-level probability of reaching a top-\(k\) platform is \(q_{t,k}(D)=\sum_j\alpha_j\big(\sum_{p\in R_{t,k}}y^j_{t,p}\big)/\mu_t\). The constraints are \(L_{t,k}\le q_{t,k}(D)\le U_{t,k}\), and the objective is to maximize expected matched mass, \(\sum_j\alpha_j\sum_{t,p}y^j_{t,p}\). The solution is an optimal finite-support lottery, or a certificate of infeasibility.

This is recognizably the same question as Theorem 3.7: find a distribution over strong group-fair matchings satisfying probabilistic individual fairness, while maximizing matching size. The only change is that indistinguishable applicants are represented by mass. A rational instance can be cleared to denominators and expanded into \(N\mu_t\) clones. Conversely, any finite clone instance can be symmetrized over permutations of clones of the same type, producing exactly this type-level lottery. Thus this is not merely a fractional relaxation: atomless mass can be partitioned among platforms while every individual remains assigned integrally.

I expect this mirror to be tractable, Class A. With disjoint groups, the group constraints and top-\(k\) constraints are linear in the \(y_{t,p}\), giving a polynomial-size LP with \(O(\tau m)\) assignment variables. The integrality obstruction that motivates the paper’s decomposition machinery disappears at the population level: a mass of type \(t\) can be divided among platforms because it represents many applicants, not one fractional applicant. The main further questions are whether one can give a polynomial-size decomposition that preserves ex-post group fairness, whether the running time depends on \(\tau\) rather than \(N\), and whether the result remains true with platform copies or capacities.

The second anchor is Theorem 4.1, the formal version of Theorem 3.4. Its continuous mirror, Continuous Overlapping-Group Bicriteria Matching, uses the same input except that each type has an overlapping group set \(G_t\subseteq[\chi]\), with \(|G_t|\le\Delta\), and only upper bounds \(X_{p,h}\le u_{p,h}\). Given \(\epsilon>0\), the problem asks for a finite-support lottery over group-fair continuous matchings whose expected matched mass is at least \((\mathrm{OPT}_\infty+\epsilon)/f_\epsilon\), where the natural type-compressed target is \(f_\epsilon=O(\Delta\log(\tau/\epsilon))\), and whose type-level individual-fairness probabilities satisfy \( (L_{t,k}-\epsilon)/f_\epsilon\le q_{t,k}(D)\le (U_{t,k}+\epsilon)/f_\epsilon\).

I expect this one also to be Class A in the genuinely atomless regime, although the classification is less secure. The discrete difficulty in overlapping-group matching is largely the selection of indivisible items under multiple group constraints. At the type level, the population of each type can be split, so the corresponding selection problem becomes a linear mass-allocation problem. The paper’s LP formulation and its greedy decomposition then suggest an exact or improved bicriteria algorithm whose dependence is on \(\tau\), \(m\), and \(\Delta\), rather than on the number \(N\) of named applicants. The important open boundary is whether the overlap structure itself still carries hardness when \(\tau\) is small. If it does, that would be Class B hardness surviving in the type agenda; if not, the discrete NP-hardness dissolves specifically because population multiplicity has been removed.

This second mirror generates useful questions: does overlapping-group hardness require \(\tau\) distinct types, or can it persist with a fixed type catalogue and large masses? Can the \(O(\Delta\log N)\) guarantee in Theorem 4.1 be replaced by \(O(\Delta\log\tau)\)? And can one obtain exact continuous feasibility and optimization even when the discrete problem only admits bicriteria approximation?

These mirrors cover the paper’s central named algorithmic results, not its unnumbered “Known Hardness Results,” which are cited from other papers. They also do not pretend that every matching instance is high-multiplicity. A market with individualized rankings, eligibility, and bounds may have \(\tau\approx N\), in which case the mirror gives little compression. That is the weakest point. The additional semantic wrinkle is that the prose says items may receive multiple assignments, whereas LP 4.2 treats top-\(k\) probability as a sum of edge variables, which corresponds to one selected platform per item. If literal many-to-many assignments are intended, the mirror needs bundle variables and a configuration formulation; the exact polynomial claim then becomes an open obligation rather than an automatic consequence.

But in the cohort-based school, grant, or training-allocation regime, the authors should recognize the proposed problems as their own: same platforms, preferences, group quotas, probabilistic individual fairness, and matching-size objective, with only the applicant population replaced by rational type masses.