On Fair Division under Heterogeneous Matroid Constraints

The strongest honest positive case is a high-multiplicity fair-allocation mirror, with Theorem 6 as the lead. The paper contains no named NP-hardness result, so the anchors are polynomial-time and impossibility results rather than hardness results.

Take a recurring roster of medical shifts. There are many doctors, perhaps \(N\) in a planning horizon, but only \(\tau\ll N\) complete doctor types: each type specifies the same binary preferences over shift slots, the same partition of slots into categories, and the same capacity for each category. Shift slots also recur with population size: a slot type \(g\) has per-capita supply \(\rho_g\). This is a legitimate high-multiplicity regime: the relevant distinction is between a few schedule/preference patterns and thousands of agents, not between named individuals.

Let \(G\) be the finite set of slot types, partitioned into categories \(C_1,\ldots,C_\ell\). Type \(t\) has binary additive valuation \(v_t(g)\in\{0,1\}\), capacities \(k_{t,h}\), and feasible bundles \(\mathcal B_t=\{B\subseteq G: |B\cap C_h|\le k_{t,h}\text{ for every }h\}\). The society is a distribution \(\mu\) over types.

The continuous allocation variable is \(y_{t,B}\ge 0\): the mass of type-\(t\) doctors receiving the integral bundle \(B\). Thus \(\sum_{B\in\mathcal B_t}y_{t,B}=\mu_t\), while completeness requires \(\sum_{t,B:g\in B}y_{t,B}=\rho_g\). No doctor receives a fractional shift; only the distribution over integral bundles is fractional.

For type \(t\), define \(e_t(B)=\min_{Y\subseteq B,\ |Y|\le1}\max_{S\subseteq B\setminus Y,\ S\in\mathcal B_t}v_t(S)\). The type’s average utility is \(U_t(y)=\mu_t^{-1}\sum_B y_{t,B}v_t(B)\). I would call \(y\) type-\(\mathrm{F\text{-}EF1}_\infty\) when, for every positive-mass pair \(t,u\), \(U_t(y)\ge\mu_u^{-1}\sum_B y_{u,B}e_t(B)\). This is the natural type-average lift of the paper’s feasible EF1 condition.

Lead mirror — HM-F-EF1 under heterogeneous partition matroids. Given rational \(\mu\), rational per-capita supplies \(\rho\), binary valuations, and heterogeneous capacities over a common category partition, find a complete type-\(\mathrm{F\text{-}EF1}_\infty\) allocation plan \(y\), or decide that none exists.

The anchor is Theorem 6, proved in this paper: for partition-matroid constraints with binary valuations, allowing heterogeneous capacities and heterogeneous valuations, an F-EF1 allocation exists and can be computed efficiently by the Iterated Priority Matching algorithm. The continuous question preserves every substantive ingredient—complete allocation, binary additive values, heterogeneous capacities, partition feasibility, and feasible EF1—while replacing a large list of repeated doctors by type masses.

I expect this lead mirror to be Class A. The paper’s priority matchings have an obvious mass analogue: matching becomes transportation or max-flow between type mass and desired slot supply, while the configuration variables \(y_{t,B}\) form a finite-support LP. The real research question is whether the EF1 constraints admit efficient separation in the type-mass formulation, and whether the algorithm’s acyclic-en­vy invariant survives aggregation. This is precisely the kind of pricing/separation question the continuization programme is meant to expose.

The high-multiplicity bridge is also concrete. A rational \(y\) can be multiplied by a common denominator to produce a discrete allocation with many copies of each type and slot; conversely, an \(N\)-agent allocation produces empirical masses. Thus the mirror gives exact answers for denominator-compatible instances and additive approximations otherwise.

A second, narrower mirror uses Theorem 10, proved here. The theorem states that with three agents, a common base-orderable matroid constraint, and heterogeneous binary valuations, Iterated Swaps finds an EF1 allocation in polynomial time; the resulting allocation is also social-welfare maximizing and therefore Pareto efficient.

HM-SWM-F-EF1 under a common BO matroid. There are three large cohorts \(t\in\{1,2,3\}\), with masses \(\mu_t\), a common base-orderable matroid over recurring indivisible slots, and binary valuations \(v_t\). Find a complete allocation plan \(y\) that maximizes \(W(y)=\sum_{t,B}y_{t,B}v_t(B)\) and is type-\(\mathrm{EF1}_\infty\).

This is plausible for the same reason the original theorem is plausible: the common matroid supplies exchange bijections, while the three-type restriction may keep the potential-function argument manageable after aggregation. I would expect a Class A result, though the mass-weighted exchange argument is not automatic. The further question is whether welfare-preserving exchanges can reduce aggregate type envy when each type is itself distributed over several integral bundles.

A useful boundary mirror comes from Proposition 1, also proved here. It says that if two agents have identical constraints represented by an arbitrary set system \(\mathcal I\), and \(x,y\) are complementary—every feasible partition into two bundles puts \(x\) and \(y\) together—then a complete EF1 allocation may fail to exist even with identical binary valuations, when both agents value \(x\) and \(y\) at \(1\) and all other items at \(0\).

HM-complementarity violation minimization. Given a finite set system, type masses, recurring item supplies, and homogeneous binary valuations, find a complete allocation plan minimizing the maximum type-level EF1 violation, and decide whether violation zero is achievable.

Here I expect the specific two-agent obstruction to become tractable and sometimes disappear under high multiplicity. With many repeated copies, the complementary pair can be distributed across a mass of agents, and average type utilities can equalize even though the two-agent, one-copy instance has no EF1 allocation. But this should not be overstated: arbitrary non-matroid constraints may retain genuine obstructions, and their configuration pricing problem could itself be hard. The point is to identify exactly which impossibilities are finite-supply artifacts and which survive continuization.

The weakest point is the fairness lift. The paper’s F-EF1 is pointwise between named agents, whereas my main mirror compares type averages. A referee could reasonably say that this is a relaxation. I think it is the correct high-multiplicity interpretation because the programme explicitly treats type-level averages as primary, but I would report the stronger companion question as well: require the EF1 inequality for almost every pair of bundles in the two type distributions. If that pointwise version fails while the average version succeeds, the distinction should be presented as a substantive result, not hidden.

This case therefore covers Section 6 emphatically, Section 8.3 as a BO-matroid extension, and Section 3.3 as a boundary test. It does not claim that every theorem in the paper has a useful mirror; it claims that the paper’s central fair-allocation problem has a precise, natural population-continuum form whose main difficulty is exactly the computational separation problem that ChoCo is designed to study.