| paper | Group Fairness in Set Packing Problems |
| authors | Sharmila Duppala, Juan Luque, John Dickerson, Aravind Srinivasan |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite set \(T\) of interchangeable patient–donor types with masses \(\mu_t\), a typed compatibility system generating admissible cycle or set patterns \(\mathcal P\), pattern incidences \(a_{Pt}\), weights \(w_P\), color contents \(v_{P\ell}\), proportionality vector \(\vec p\), and \(\gamma\ge1\), compute a nonzero mass packing \(x_P\ge0\) maximizing \(W(x)=\sum_{P\in\mathcal P}w_Px_P\), subject to \(\sum_Pa_{Pt}x_P\le\mu_t\) and \(N_\ell(x)\le\gamma(p_\ell/p_q)N_q(x)\) for all colors with \(p_\ell,p_q>0\), where \(N_\ell(x)=\sum_Pv_{P\ell}x_P\) and \(N(x)=\sum_\ell N_\ell(x)>0\).
A high-multiplicity kidney-exchange or \(k\)-set-packing market with a finite type set \(T\), population mass \(\mu\), fixed typed compatibility patterns \(\mathcal P\), decision variables \(x_P\) representing packed mass, capacity constraints by type, and proportional group-fairness constraints on selected mass.
The proponent does not establish that the bounded finite compatibility-type regime is empirically substantial in the paper's realistic kidney-exchange instances, so practical relevance remains uncertain.
fatal: False
The mirror covers Theorem 1's RF approximation and packing objective, with Theorem 4 supporting the LP bridge. It does not directly cover Theorems 2 and 3's SRF concentration guarantees, finite-instance integrality-gap motivation, or arbitrary individual-specific compatibility graphs.
There is a credible continuous mirror here, strongest for the paper’s kidney-exchange interpretation rather than for arbitrary set-packing instances. My lead anchor is Theorem 1.
The population should be the population of patient–donor pairs, not the collection of cycles. Let \(T\) be a finite set of complete exchange types. A type includes the pair’s blood and sensitization attributes, compatibility signature, eligibility constraints, and every other feature that affects which cycles it can enter or what utility it contributes. Two pairs have the same type only if they are interchangeable for the entire optimization problem.
The society is a mass distribution \(\mu=(\mu_t)_{t\in T}\), with \(\sum_t\mu_t=1\). A feasible cycle or packing pattern \(P\) has incidence \(a_{Pt}\), meaning that it consumes \(a_{Pt}\) units of type \(t\), with \(\sum_t a_{Pt}\le k\), and has weight \(w_P\). Its color-\(\ell\) content is
\[ v_{P\ell}=\sum_{t:\,C(t)=\ell}a_{Pt}. \]
A continuous packing is a vector \(x=(x_P)_{P\in\mathcal P}\) satisfying
\[ \sum_{P\in\mathcal P}a_{Pt}x_P\le \mu_t \qquad\text{for every }t\in T. \]
Here \(x_P\) is the mass of exchange cycles of type-pattern \(P\). Its total utility and selected color masses are
\[ W(x)=\sum_P w_Px_P,\qquad N_\ell(x)=\sum_Pv_{P\ell}x_P,\qquad N(x)=\sum_\ell N_\ell(x). \]
This is genuinely a population continuization. If \(\mu_t=r_t/M\), form a discrete instance with \(r_t\) interchangeable copies of each type. A type-level vector \(x\) is the normalized limit of packings of those copies as \(M\) grows. The set-pattern structure, cycle length bound, weights, colors, and proportionality vector are all retained.
The plausible regime is a large national or regional exchange pool, or repeated clearing runs aggregated over time, with many pairs sharing a bounded number of clinical and compatibility profiles. Thus \(M\) is very large while \(\tau=|T|\) is comparatively small. This is not a claim that every real kidney-exchange graph has this property; rare biological attributes and idiosyncratic edges can destroy it. But a recurring cohort model with standardized compatibility classes is a sensible high-multiplicity version of exactly the application the paper presents.
The lead problem is Continuous RF-FAIRSP:
Given \(T,\mu,\mathcal P,a,w,C,\vec p\), and \(\gamma\ge1\), output a feasible mass packing, or a randomized policy \(X\) over feasible mass packings, with \(\mathbb E[N(X)]>0\), maximizing \(\mathbb E[W(X)]\) subject to
\[ \frac{\mathbb E[N_\ell(X)]}{\mathbb E[N_q(X)]} \le \gamma\frac{p_\ell}{p_q} \qquad\text{for all active colors }\ell,q. \]
When \(\gamma=1\), this is exact proportionality in expectation. A solution can be represented by the expected mass vector \(x_P=\mathbb E[X_P]\), together with a finite-support decomposition if an operational randomized policy is required.
The natural exact continuous optimization problem is the linear program
\[ \begin{array}{ll} \max & \displaystyle\sum_Pw_Px_P\[2mm] \text{s.t.} & \displaystyle\sum_Pa_{Pt}x_P\le\mu_t \quad(t\in T),\[2mm] & \displaystyle N_\ell(x)=p_\ell N(x)\quad(\ell\in[c]),\\ & x_P\ge0. \end{array} \]
If the type-pattern family is explicit, this is an ordinary polynomial-size LP. If patterns are generated from compatibility types, it remains polynomial for fixed \(k\), since there are at most \(O(\tau^k)\) type patterns. For variable \(k\), the relevant unresolved issue is precisely the pricing/separation problem, which is the kind of boundary the ChoCo programme is meant to expose.
The named anchor is Theorem 1, proved in this paper rather than cited from elsewhere. It states that FAIRSAMPLE is randomized polynomial time, achieves approximation factor \(k+\epsilon_k\), and, with probability \(1-\epsilon_L\), satisfies RF with \(\gamma=1+\epsilon_L\). In the high-multiplicity interpretation, the paper’s LP variables become expected masses of type-pattern cycles. Its rounding algorithm is then an implementation theorem: solve the continuous policy problem, and realize it on a large finite cohort with controlled loss in utility and proportionality.
The paper’s Theorem 4 supports this bridge: it proves that the optimum of LP (3) upper-bounds the randomized FAIRSP objective. In the nonatomic limit, that LP is not merely an upper bound; divisibility lets the mass solution itself be implemented by splitting the population among patterns. Thus the continuous mirror is not obtained by making the outcome “fractional” in an unrelated sense. The population of exchange pairs is the continuous object, and the paper’s own fairness accounting survives unchanged.
I would not use Theorems 2 and 3 as separate anchors. They offer a natural follow-up mirror for strong randomized fairness, but their hypotheses involve the finite-instance frequency \(f\), and that parameter need not behave well when every type is replicated into many concrete cycle instances. Theorem 1 gives the cleaner and stronger positive case.
The expected classification is Class A in the bounded-\(k\), bounded-type-pattern regime: the continuous problem is an LP, and the finite randomized algorithm supplies an approximation-preserving implementation. Further questions include whether implicit pattern pricing remains polynomial when \(k\) is part of the input, whether exact proportionality can be implemented with bounded support, how the price of fairness varies with \(\vec p\), and whether strong ex-post fairness survives under more realistic sparse compatibility models.
The weakest point is real: once the population is nonatomic, the integrality obstruction motivating the paper’s randomized fairness can largely disappear. Exact proportionality may become easy whenever the continuous LP is feasible, so this mirror does not preserve every difficulty of finite FAIRSP. Moreover, many actual exchange pools may have too many idiosyncratic types. But those are limitations of the regime, not a failure of the mirror. The paper’s KEP formulation, its color accounting, its proportionality constraints, and its LP-rounding result all survive in a large repeated-cohort population. That is a respectable continuous analogue of Theorem 1, even though continuization deliberately removes some finite-population hardness.
The negative case has to concede one point at once: Theorem 1 is a genuine named computational result, so “there is nothing computational here” is unavailable. The objection is instead that its computational content cannot survive as a population continuization without either losing the kidney-exchange instance or changing the problem into an ordinary fractional relaxation.
The relevant population would have to be patient–donor pairs, not cycles. But in FAIRSP, an element’s complete type is essentially its incidence vector across all sets, together with every feature affecting set weights and eligibility. In kidney exchange, that means its complete compatibility signature: which other pairs it can form cycles with, in which directions, with what weights. These signatures are generally individual-specific. As the pool grows, new pairs introduce new coordinates in the compatibility matrix, so the number of types grows with the population. Then \(\mu\) is only a compressed notation for the original graph, not a high-multiplicity society with a fixed or comparatively small type space.
Coarsening types to blood group, sensitization, or other clinical attributes does not repair this. Two pairs with the same such attributes may have completely different compatibility edges and cycle opportunities. The proposed incidence numbers \(a_{Pt}\) are therefore not defined by the type distribution. To recover them, one must provide an additional compatibility hypergraph or kernel. At that point the population distribution is insufficient to specify the instance: the computational object is the relational structure between agents, not their masses.
A stronger proposal would use a finite compatibility-type system in which all pairs of a given type are interchangeable and compatibility depends only on types. That is coherent, but it is a very restrictive blow-up of a fixed finite hypergraph. Every cycle pattern can then be enumerated from the type system, and the continuous problem is simply
\[ \max \sum_P w_Px_P \]
subject to
\[ \sum_P a_{Pt}x_P\le \mu_t \]
and the proportionality equations. This is exactly the fractional packing LP already present in the paper, with the right-hand sides rescaled from counts to masses. Randomization is unnecessary: nonatomic mass can be split directly among patterns, so the fairness equalities hold exactly.
That observation defeats the claimed connection to Theorem 1. The theorem’s content is the randomized rounding of an integral packing, together with approximate fairness after rounding. In the continuous blow-up, the integrality obstruction disappears by construction; Theorem 4’s LP upper bound becomes the answer because the model has replaced individual selection by divisible mass allocation. This is a legitimate high-multiplicity relaxation, but its computational content comes from fractionalizing the packing outcome, while \(\mu\) merely supplies capacities. It is therefore much closer to an LP relaxation of FAIRSP than to a new continuous-population problem.
The alternatives do not help. Treating cycles as population types retains the same problem: a cycle’s type includes its complete incidence pattern, and those patterns proliferate with the underlying graph. Aggregating repeated clearing runs either leaves the runs as separate finite instances, in which case no population compression occurs, or permits cross-run interchangeability, in which case it again produces the fixed-hypergraph blow-up above. A graphon- or compatibility-kernel formulation is possible, but then one is continuizing the relational network as well as the population; exact cycle feasibility is no longer determined by \(\mu\), and a computational input model would have to be supplied from outside the paper.
Theorem 4 does not provide an independent anchor. It only certifies that the finite randomized optimum is bounded by the natural LP. In the proposed mirror, that LP is made feasible as a direct mass allocation. This is precisely why the paper’s motivating phenomenon—deterministic fair packings being infeasible and randomized packings restoring fairness—has no population-level analogue unless one reintroduces finite indivisibilities.
The negative case is not airtight against a deliberately engineered market with a small number of genuinely interchangeable compatibility classes. Such a model is mathematically sensible, and the proponent is right that it has a formal high-multiplicity limit. But it is either a stylized fixed hypergraph whose solution is the paper’s fractional LP, or a realistic exchange model whose compatibility data remain individual-specific. On the evidence of this paper, there is no worthwhile continuous mirror that preserves both the KEP/set-packing population and the computational substance of Theorem 1.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.