| paper | Random Assignment of Indivisible Goods under Constraints |
| authors | Yasushi Kawase, Hanna Sumita, Yu Yokoi |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given finite slot labels \(E\), rational normalized capacities \(b_e\), a finite set of complete types \(T\) with rational masses \(\mu_t\) summing to \(1\), one common strict ranking \(\succ\), and a matroid \(\mathcal F_t\) on \(E\) for each type, choose conditional bundle lotteries \(\lambda_t\in\Delta(\mathcal F_t)\). Require \(\sum_{t\in T}\mu_t\sum_{A\in\mathcal F_t}\lambda_t(A)\mathbf 1[e\in A]\le b_e\) for every \(e\), define \(U(e)=\{e'\in E:e'\succeq e\}\) and \(R_t^\lambda(e)=\sum_A\lambda_t(A)|A\cap U(e)|\), and require no feasible \(\lambda'\) to weakly improve every \(R_t^\lambda(e)\) with one strict improvement, together with \(R_t^\lambda(e)\ge\sum_{B\in\mathcal F_u}\lambda_u(B)\max_{Y\subseteq B,\,Y\in\mathcal F_t}|Y\cap U(e)|\) for all types \(t,u\) and thresholds \(e\). Output such a family or report that none exists.
A high-multiplicity capacitated random-assignment model with \(K\mu_t\) agents of type \(t\) and \(Kb_e\) indivisible copies of slot \(e\), compressed to type-level lotteries \(\lambda_t\), matroid-feasible bundles, aggregate capacity constraints, and the paper's SD-efficiency and SD-envy-freeness conditions.
The capacity-scaled construction is an extension of the paper's literal one-copy market, and a formal treatment is still needed to establish equivalence between conditional type lotteries, duplicated-slot tie conventions, and globally feasible finite lotteries.
fatal: False
The mirror covers the common-preference, heterogeneous-matroid tractability regime of Theorem 2 and can formulate Theorem 5's three-type obstruction; it leaves Theorems 1, 3, and 4, the full-version NP-hardness result, and the other fairness properties untreated.
I would make a strong case for a mirror, with Theorem 2 as the lead anchor. This paper is unusually well suited to continuization because its own proof already separates agents into preference/constraint profiles and works through fractional assignment polytopes.
The continuous model is the following. Let \(E\) be the finite set of good labels and \(\mathcal T\) a finite set of complete agent types. Type \(t\) consists of an ordinal ranking \(\succ_t\) and a hereditary feasible-family \(\mathcal F_t\), or a matroid when required. The society is a rational distribution \(\mu\), where \(\mu_t\) is the fraction of agents of type \(t\). Let \(b_e\) be the normalized supply of good \(e\). This represents repeated discrete copies of each good: in a sufficiently large finite realization, there are \(K b_e\) indivisible copies of \(e\), while there are \(K\mu_t\) agents of type \(t\). The goods are still indivisible in every finite realization; only the population is represented by mass.
The decision variable is a type-level lottery \(\lambda_t\in\Delta(\mathcal F_t)\), giving the bundle distribution of a random agent of type \(t\). It must satisfy the supply constraints \(\sum_t\mu_t\sum_{A\in\mathcal F_t}\lambda_t(A)\mathbf 1[e\in A]\le b_e\) for every \(e\). Write \(U_t(e)=\{e'\in E:e'\succeq_t e\}\), and let \(R_t^\lambda(e)=\sum_A\lambda_t(A)|A\cap U_t(e)|\). The lottery is sd-efficient if there is no feasible \(\lambda'\) with \(R_t^{\lambda'}(e)\ge R_t^\lambda(e)\) for every positive-mass type \(t\) and every \(e\), with one strict inequality. It is sd-envy-free if, for every pair of types \(t,u\) and every \(e\),
\[ R_t^\lambda(e)\ge \sum_{B\in\mathcal F_u}\lambda_u(B) \max_{\substack{Y\subseteq B\\Y\in\mathcal F_t}} |Y\cap U_t(e)|. \]
This preserves the paper’s crucial constrained definition of envy; it is not merely a fractional assignment problem. The objective is to find such a lottery, or decide that none exists.
The high-multiplicity regime is quite credible in course placement or shift assignment. Imagine a very large intake of students sharing a common ranking of courses but belonging to a small number of programmes with different eligibility or workload matroids. Alternatively, imagine many employees in each availability/contract class, with the same shift ranking within a class. The number of agents can be hundreds of thousands while the number of distinct complete types is modest. This is exactly the regime in which grouping agents by type is informative rather than artificial.
My lead problem is Continuous SD-Efficient and SD-Envy-Free Assignment under Common Preferences and Matroid Constraints. Its instances are the model above with all \(\succ_t\) identical and every \(\mathcal F_t\) a matroid. The question is to output a type-level lottery \(\lambda\) satisfying supply feasibility, sd-efficiency, and sd-envy-freeness.
The anchor is Theorem 2 of the paper, proved here: “An sd-efficient and sd-envy-free lottery assignment always exists and can be computed in polynomial time if the constraints are matroids, and the preferences are identical.” I expect the continuous problem to be Class A.
The reason is not simply that the finite theorem says “polynomial.” Algorithm 1 is already a population-compressed process. Process the common ranking \(e_1,\ldots,e_m\) in order, increasing the conditional allocation of every currently feasible type at the same per-agent rate. A type stops when its matroid constraint becomes tight; an item stops when its weighted aggregate consumption reaches \(b_e\). The stopping rate is determined by the \(\mu_t\)'s, so the algorithm depends on the number of types and the encoding length of their masses, not on the number of replicated agents. Matroid convex-hull descriptions, greedy choice functions, and the decomposition step then provide a finite-support lottery.
This is recognisably the authors’ problem rather than a softened substitute. Preferences remain ordinal, bundles remain constrained by the same matroids, and envy is still evaluated through the best feasible subbundle of another agent’s bundle. The only change is that equal agents are represented once with mass \(\mu_t\). In fact, a rational instance is exactly the normalized limit of repeated finite instances, so the mirror is the high-multiplicity version of their theorem rather than a new welfare criterion.
A second, deliberately negative anchor is Theorem 5, also proved here. The theorem states that an sd-efficient and sd-envy-free lottery assignment may not exist even with three agents and identical matroid constraints. Its explicit instance has \(E=\{a,b,c,d,e\}\), common matroid \(\mathcal F_i=\{X\subseteq E:|X\cap\{a,b,c\}|\le1\}\), and rankings
\[ d\succ_1 a\succ_1 b\succ_1 c\succ_1 e, \]
\[ d\succ_2 b\succ_2 e\succ_2 a\succ_2 c, \]
\[ a\succ_3 d\succ_3 e\succ_3 b\succ_3 c. \]
The corresponding continuous problem, Continuous Three-Type Matroid Assignment, has three types with \(\mu_1=\mu_2=\mu_3=1/3\), normalized supply \(b_e=1/3\) for every good, the common matroid above, and those three rankings. The question is whether a type-level lottery satisfying both properties exists. It does not.
This is a transferred impossibility, not continuum-specific hardness. If such a continuous lottery existed, its three type-conditional marginal assignments would give the fractional assignment \(\pi\) ruled out in the proof of Theorem 5. Equivalently, one may replicate each type and each item supply by a factor \(K\); the normalized feasibility and envy inequalities remain exactly the same, so increasing multiplicity does not repair the obstruction. This is useful evidence for the mirror: continuization preserves the paper’s genuine matroid incompatibility instead of automatically washing it away.
The two anchors therefore give a coherent boundary. The common-preference matroid regime should be tractable in the continuous, type-compressed representation; the three-type heterogeneous-preference regime can remain infeasible even at arbitrarily high multiplicity. The natural follow-up questions are whether a bounded number of preference types still permits a Class A algorithm, whether general hereditary constraints admit approximation, and whether one can characterize the mass-and-type patterns for which sd-efficiency and sd-envy-freeness coexist.
The weakest point is the supply normalization. If one insists on keeping literally the same finite set of one-copy goods while the population grows, most agents eventually receive nothing and the mirror becomes degenerate. My construction therefore uses repeated indivisible seats or shift slots, represented by normalized capacities \(b_e\). That adds a high-multiplicity supply regime, but it does not fractionalize the goods or replace the paper’s question by cardinal welfare maximization. It is the natural repeated-cohort interpretation of the assignment problem, and Theorem 5 shows that even under this interpretation the paper’s core impossibility survives.
The strongest negative case is that the paper’s literal market does not have a nondegenerate population limit. There is one copy of each \(e\in E\), so if the number of agents grows while \(E\) stays fixed, per-agent allocations converge to zero. Efficiency and envy-freeness then lose the assignment content that motivates them. Replicating every item \(K\) times avoids this collapse, but it also changes the model: goods now have capacities, identical copies require a weak-order or parallel-item treatment, and the limit is a capacitated allocation problem rather than the paper’s one-copy random assignment problem.
That objection does defeat the literal mirror, but not the better mirror. Repeated seats, course places, or shift slots are entirely credible high-multiplicity instances, and the goods remain indivisible in every finite realization. The paper’s strict rankings can be replaced by common rankings over item labels, or by a harmless consistent tie-breaking over copies. This is a recognizable high-multiplicity version, not merely fractionalizing goods.
Theorem 2 is therefore difficult to defeat. With common preferences and matroid constraints, a type consists precisely of a matroid constraint, and the paper’s Algorithm 1 aggregates naturally by type. If type \(t\) has mass \(\mu_t\), the item constraint becomes
\[ \sum_t \mu_t x_{t,e}\le b_e. \]
The stopping events are matroid constraints becoming tight or item capacity being exhausted; their number is governed by the number of types and items, not by the number of replicated agents. The choice functions and lottery decomposition already used in the proof extend to this setting. This gives a legitimate Class A question, plausibly solvable in time polynomial in the type description, \(m\), and the encoding length of the masses.
Theorem 5 also survives the same repair. Taking three types of masses \(1/3\), capacities \(b_e=1/3\), and the paper’s three rankings yields, after multiplying the capacity inequalities by \(3\), exactly the fractional assignment system ruled out by the theorem. Replicating the agents and goods does not remove the incompatibility. Thus the proposed continuous version is a valid high-multiplicity transfer of the impossibility result, even if it is not continuum-specific.
One can object that Theorem 5 supplies only a fixed obstruction, not a complexity classification. That limits its value as a computational anchor, but it does not invalidate the mirror: the natural broader problem is deciding existence, or characterizing existence, for distributions over matroid-and-preference types. Nor can one object that the continuous version is “just the same algorithm”; the programme explicitly permits such a transferred Class A result.
So the honest negative case is weak. The one-copy formulation degenerates, and the nondegenerate formulation scales item capacities as well as population. But course placement and shift assignment provide convincing scenarios for that scaling, and both anchors remain mathematically meaningful after it. I cannot defend the universal claim that no worthwhile continuous mirror exists.
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.