| paper | d4-journals-geb-2020-0100 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given a finite set of household types \(T\) with rational masses \(\mu_t\), each type’s institution and complete ranking of apartment classes \(A\), per-capita class supplies \(s_a\), institutional quotas \(q_i\), apartment priorities over institutions, and responsive institutional rankings over class-type pairs, compute a rational allocation \(x_{t,a,i}\). Require \(x_{t,a,i}=0\) for unacceptable pairs or institutions outside type \(t\)’s attachment; \(\sum_{a,i}x_{t,a,i}\leq\mu_t\), \(\sum_{t,i}x_{t,a,i}\leq s_a\), and \(\sum_{t,a}x_{t,a,i}=q_i\). Under feasible quota filling and an over-demand promise that, for every \(i,a\), more than \(q_i\) mass of types attached to \(i\) accepts \(a\) and is acceptable to \(i\), find an individually rational allocation with no positive-mass waste or justified-envy block that is Pareto-undominated among such allocations. Compare allocations by first-order dominance for each type’s distribution over its ranked classes, with unmatched agents ranked last.
Use a nonatomic population of complete household types \(t\), with mass \(\mu_t\), and apartment classes with supplies \(s_a\) and institutional quotas \(q_i\). The decision variables \(x_{t,a,i}\) are masses of type \(t\) assigned to class \(a\) through institution \(i\); seek an allocation satisfying the mass versions of the paper’s fairness conditions and Pareto-undominated by those conditions. Apartment units remain indivisible for each household, while a type’s mass can be split across classes.
Covers Theorem 5.1’s quota-respecting fairness and Pareto-undominated assignment guarantee. It leaves that theorem’s strategy-proofness claim aside and does not mirror Theorem 5.2’s multiple-institution case or Theorem 6.1’s regional-preference extension.
There is no honest \(P\), NP-hardness, or parameterized-complexity anchor in this paper. Its strongest computationally relevant anchor is Theorem 5.1, proved in the paper’s appendix. For markets where each household belongs to one institution and the over-demand condition holds, it says the NDAI algorithm returns an individually rational, non-wasteful assignment that meets the institutional quotas and has no justified envy—that is, a fair assignment. It also says no fair assignment Pareto-dominates its output, and that NDAI is strategy-proof for households. This is an algorithmic mechanism result, but it does not classify a problem’s running time.
A plausible mirror is Over-demanded Institutional Mass Fair Assignment. Consider a large recurring social-housing allocation. A household type \(t\) records its institution, its complete ranking of apartment classes, and every characteristic that affects acceptability or how an institution ranks it. The society is given by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Apartment classes have per-capita supplies \(s_a\); institution \(i\) has a per-capita quota \(q_i\). Apartment priorities over institutions and institutions’ responsive preferences over apartment-class/type pairs are part of the input. Assume total supply covers the quotas and an individually rational quota-filling allocation is feasible.
The over-demand promise should be made strong enough to survive aggregation. One precise version is that, for every institution \(i\) and apartment class \(a\), more than \(q_i\) mass belongs to types attached to \(i\) that accept \(a\), and that institution \(i\) accepts the corresponding pair. This strengthens the paper’s condition, which is stated for individual households, but ensures eligible mass cannot all be used up while filling \(i\)’s quota.
A solution is a rational allocation \(x_{t,a,i}\geq 0\), where \(x_{t,a,i}\) is the mass of type \(t\) receiving one unit from class \(a\) through institution \(i\). It must satisfy \(\sum_{a,i}x_{t,a,i}\leq\mu_t\), \(\sum_{t,i}x_{t,a,i}\leq s_a\), and \(\sum_{t,a}x_{t,a,i}=q_i\), with assignments restricted to acceptable pairs and the household’s institution. Require the mass version of the paper’s fairness conditions: individual rationality, no positive-mass wasteful assignment, and no positive-mass justified-envy block under the apartment priorities and institutional choice rules. Among such allocations, return one not Pareto-dominated by another fair mass allocation, comparing each type’s distribution over apartments by its ranking. The units remain indivisible for each household; \(x\) records how a nonatomic cohort is divided among whole units.
This is a credible mirror because a large, standardized housing programme can have many applicants but relatively few recurring combinations of eligibility, institution, and apartment-class rankings. In that regime the support size \(\tau\) can be much smaller than the population. Scaling apartment supplies and quotas with the population is a necessary co-modification: leaving a fixed number of apartments while the population grows would make almost everyone unmatched. The types are meant to capture the complete distinctions the mechanism uses, so grouping applicants with genuinely different priorities or costs would change the problem.
I would expect this mass-assignment question to be tractable, perhaps by adapting a type-level deferred-acceptance procedure or a flow formulation. That is a research conjecture, not a consequence of Theorem 5.1. The theorem’s Pareto claim has a natural aggregate counterpart in the solution definition; its strategy-proofness claim does not transfer directly, since one infinitesimal household’s unilateral report changes no mass. Whether truthful reporting can be given a meaningful type-level formulation is a further question.
The scope is deliberately limited to the fair, quota-respecting assignment result of Theorem 5.1. It does not mirror the paper’s multiple-institution variant or its regional-preference extension. The weakest point is that Theorem 5.1 proves properties of a finite-agent mechanism, not a complexity bound for computing assignments. Also, mass fairness must be defined through positive-mass blocks, whereas the paper’s fairness test concerns individual households. Those gaps mean this is a promising algorithmic mirror, not a continuization of a proved complexity result.
The strongest case against this anchor is that Theorem 5.1 is a mechanism-design result, not a computational-complexity result. It proves that NDAI has fairness, Pareto, and incentive properties; the paper does not pose a search or decision problem, analyze input size, or bound the algorithm’s running time. A continuous version would therefore require ChoCo to introduce a new computational target: compute a fair, quota-respecting assignment from type masses. That target may be reasonable, but it is not a complexity question the paper itself develops.
The proposed mass-assignment mirror also needs several choices beyond replacing households with masses: apartment classes with supplies scaled to population, proportional quotas, a positive-mass notion of justified envy, and an aggregate Pareto comparison. The strongest version makes these choices sensibly, with types recording every relevant preference and characteristic. Still, the mirror’s central computational question comes from this redesigned model, while the theorem’s headline strategy-proofness does not transfer in a substantive way. An individual report has zero effect in a nonatomic society; treating a whole type’s report as a deviation changes the problem into one about coordinated misreports.
Those objections do not dispose of the fair-assignment question. A large standardized housing programme could plausibly have recurring types and supplies that scale with its applicant population. Individual households could still receive indivisible units, and fairness could be defined against positive-mass blocks. The paper’s own Paris example is less convincing as a limit regime: its apartments are differentiated objects, and its quotas reflect available stock. Aggregating those units into classes could erase distinctions the mechanism uses. But another standardized setting could avoid that problem, so the objection is about how much modelling work the mirror needs, not whether such a setting exists.
I would resist prioritizing this paper as a ChoCo mirror because its proved contribution is chiefly normative and the most natural incentive claim degenerates under nonatomicity. I cannot honestly make the universal negative case. The fair mass-assignment problem remains a coherent computational question under a plausible high-multiplicity regime, and the objections above do not defeat it.
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.