d4-conf-ijcai-2021-0340

The strongest honest case is a single broad algorithmic anchor: Theorem 1, proved in this paper. It states that GDA-FD runs in polynomial time and returns a feasible, non-wasteful outcome, even when students can have multiple types. Here, non-wastefulness means that no assigned student can move to a strictly preferred contract while keeping the outcome feasible. The paper does not prove a numbered hardness result of its own; the NP-hardness it mentions for hard lower quotas is prior work on a different model.

I would mirror Theorem 1 with Flexible-Diversity Mass GDA\(_\infty\). An instance has a finite set of schools and seat classes, with each class supplied at a rational rate per unit of population. It also has a finite support \(\Theta\) of applicant types and rational masses \(\mu_\theta\) summing to \(1\). A type records everything the allocation uses: its acceptable school-seat contracts and their preference order, its priority at each school, and its memberships in the school’s diversity categories. Schools retain the paper’s flexible diversity policies, with their count intervals expressed as proportions of the population. Thus a type’s mass contributes to each category it belongs to, including when types overlap.

The question is to compute the terminal assignment of a mass version of GDA-FD. At each round, remaining applicant mass proposes to its most preferred contract not yet rejected. Each school selects from the proposed mass using the paper’s rule: dynamic precedence depends on the diversity-category masses it is currently selecting, and static priority orders applicants within the eligible precedence classes. In a type cohort, selected and rejected portions may differ, so the process can split its mass. A solution is the resulting rational flow \(x_{\theta,b,h}\) over contracts, with each type assigned at most \(\mu_\theta\) and each seat class using at most its per-capita supply. Each person in the underlying atomless cohort still receives one whole contract; the fractional quantities describe how much of a type gets each contract. The desired output is feasible and non-wasteful, in the same sense as Theorem 1. There is no additional welfare objective in the paper to preserve.

A plausible regime is a large district or public-housing authority assigning tens of thousands of applicants across a fixed collection of schools or developments and seat or unit classes. Many applicants can share complete profiles: the same ranked options, administrative priority band, eligibility, and diversity memberships. The support might then be hundreds of profiles rather than tens of thousands of individuals. If priorities or preferences are individually idiosyncratic, those differences must remain in the type, and the support may grow to nearly the population size; that regime offers little compression. The mirror’s more credible setting is a repeated intake with standardized options and priority bands.

This is a faithful change of scale, not a simpler allocation question: it keeps the paper’s contracts, overlapping categories, dynamic diversity rules, priorities, and matching procedure. It scales capacities and diversity thresholds with the population, which is a natural co-modification when moving from applicant counts to population shares. High-multiplicity matching work is supporting evidence that these repeated-profile markets are sensible objects.

I expect this mirror to be Class A, tractable, though that is a conjecture the prover must establish. The instance has finitely many type-contract choices and finitely many encoded policy thresholds. An event-driven simulation might process rational mass as it reaches those thresholds and as rejections send it to later choices. The relevant complexity target is polynomial in the number of schools and seat classes, support size \(\tau\), diversity categories, policy intervals, and input bit length \(L\).

The weakest point is that Theorem 1’s polynomial-time guarantee is for an explicitly represented finite market. It does not show that mass GDA-FD has a polynomial-size state description in \(\tau\), or that partial rejections and changing precedence generate only polynomially many events. That is the main question, not a detail already settled by the theorem. Further questions include whether the mass process always terminates with an exact rational output of polynomial bit length; how its output relates to finite high-multiplicity markets; and whether rounding preserves non-wastefulness when mass and capacities lie on a finite population grid.

My scope here is deliberately narrow: Theorem 1’s efficient computation of a feasible, non-wasteful allocation. I am not claiming continuous versions of the paper’s strategyproofness, stability, or impossibility results.