| paper | d4-conf-aaai-2021-2045 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Both objectives are polynomial-time solvable in \(m,\tau,L\). The specified greedy procedure always returns the unique optimal assignment for each objective. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given finite types \(T\) with rational masses \(\mu_t\), rational per-capita capacities \(q_1,\ldots,q_k\) summing to \(1\), and rational costs ordered by type as \(c_{t1}\le\cdots\le c_{tk}\), compute a feasible mass assignment \(x_{tj}\) that lexicographically minimizes the descending multiset of assigned costs, and separately of regrets \(d_{tj}=c_{tj}-\min_\ell c_{t\ell}\). Prove or refute that filling interventions \(k,k-1,\ldots,1\) with the lowest-cost remaining mass, splitting at a cutoff when needed, returns these optima.
Each type is a complete cost vector with population mass \(\mu_t\); \(q_j\) is intervention \(j\)'s per-capita capacity, and \(x_{tj}\) is the mass of type \(t\) assigned to it, with row sums \(\mu_t\) and column sums \(q_j\). Each unit of mass receives one discrete intervention, while a type's mass may split. Leximin minimizes mass at each distinct assigned-cost level in descending order; LoINC applies the same objective to regret levels.
The paper's household-specific data and continuous-support synthetic experiments have nearly \(n\) distinct full cost vectors, so the mirror concerns a separate repeated-profile regime.
fatal: False
The selected mirror covers Proposition 2's ordered-tier assignment structure; the case also proposes mass versions of Proposition 4's two-intervention identity and Proposition 3's capacity-share bounds. The empirical findings and the greedy claim for unsorted costs remain outside this mirror.
There is a credible continuous mirror here, but it is a mirror of the paper’s allocation results—not of a hardness result. The paper gives no named NP-hardness or complexity-class theorem. Its strongest anchors are the numbered propositions on LoINC’s efficiency, leximin’s structure, and the price of fairness.
Take a society with finitely many types \(T\), where a type \(t\) has the complete cost vector \((c_{t1},\ldots,c_{tk})\) used by the allocation problem. Its mass \(\mu_t\) is that type’s share of the population, with \(\sum_t\mu_t=1\). Let \(q_j\) be the per-capita capacity of intervention \(j\), with \(\sum_jq_j=1\). An assignment is a mass flow \(x_{tj}\geq0\) satisfying \(\sum_jx_{tj}=\mu_t\) and \(\sum_tx_{tj}=q_j\): each unit of mass receives one discrete intervention, while a type’s population may be divided across interventions. The total cost is \(C(x)=\sum_{t,j}c_{tj}x_{tj}\); the efficient assignment minimizes \(C\). For LoINC, use regrets \(d_{tj}=c_{tj}-\min_\ell c_{t\ell}\).
To define the fairness objectives, list the distinct assigned cost values in descending order and, for each value, count the mass receiving it. Leximin lexicographically minimizes this vector of masses; LoINC does the same for regret values. With finite types and rational inputs, these objectives can be optimized by sequential linear programs, one for each distinct cost or regret level. Thus the model has an explicit, polynomial-size mass-flow description, and its solutions can be given as rational assignment matrices.
My lead is Proposition 4, proved by the authors in the supplementary material: with \(k=2\), \(\mathrm{PoF}(\mathrm{LoINC})=1\), without assuming that cost rows are sorted. Its mirror, Two-Intervention LoINC Mass Assignment, takes the type masses, two intervention capacities, and arbitrary rational cost vectors as input. It asks for a LoINC-optimal mass assignment and its total cost, alongside the minimum total cost; a solution is a feasible mass-flow matrix and the two exact cost values. The continuous claim is that every LoINC optimum has the efficient cost, so the price is \(1\). I expect this to be tractable. With two interventions, capacity imbalance determines how much mass must be assigned away from its preferred intervention; both minimizing the worst regrets lexicographically and minimizing total cost select the smallest regret gaps first, splitting mass at a tied cutoff if needed. This anchor is especially persuasive because it does not require a common ranking of interventions across types.
A second mirror rests on Proposition 2, also proved in the supplementary material: on a row-sorted cost matrix, the \(u_k\) agents with the lowest costs in intervention \(k\) are assigned to it under leximin; for LoINC, use normalized costs instead. The continuous problem, Ordered-Tier Leximin Mass Assignment, has the same type-mass and capacity input, with \(c_{t1}\leq\cdots\leq c_{tk}\) for every type. It asks for the leximin and LoINC assignment matrices. The expected answer is the mass analogue of the paper’s descending greedy procedure: fill intervention \(k\) with the remaining mass having the lowest \(c_{tk}\) values (or lowest \(d_{tk}\) values), splitting a boundary type if necessary, then repeat for \(k-1,\ldots,1\). This is a tractable allocation problem; with finite support, types can be sorted and processed directly.
A third, distinct question mirrors Proposition 3, proved in the same supplementary material. In the paper, for row-sorted costs,
\[
\mathrm{PoF}(L)\leq 1+\frac{b_u}{b}\frac{n-u_k}{u_k},
\qquad
\mathrm{PoF}(\mathrm{LoINC})\leq 1+\frac{b_n}{b}\frac{n-u_k-u_1}{u_k},
\]
where \(b\) is the lowest cost in intervention \(k\), and \(b_u\) and \(b_n\) are the largest assigned cost under leximin and largest assigned normalized cost under LoINC. In Ordered-Tier Continuum Price of Fairness, the input is the same row-sorted mass-allocation instance, with \(b=\min_t c_{tk}>0\). The requested output is the optimal leximin, LoINC, and efficient mass assignments and their exact costs; the claim to establish for this family is
\[
\mathrm{PoF}(L)\leq 1+\frac{B_L}{b}\frac{1-q_k}{q_k},
\qquad
\mathrm{PoF}(\mathrm{LoINC})\leq 1+\frac{B_N}{b}\frac{1-q_k-q_1}{q_k},
\]
where \(B_L\) and \(B_N\) are the largest cost and regret, respectively, on positive-mass assignment arcs. These are the capacity-share versions of Proposition 3. For equal capacities, the factors become \(k-1\) and \(k-2\). I expect the bounds to carry over: the counts and capacities in the paper’s ratios become masses and capacity shares. The allocations themselves remain tractable by the previous greedy construction.
A plausible regime is a large regional service system assigning thousands of households to a small set of interventions, where many households share standardized profiles that give the same costs and eligibility across interventions. The type must contain that complete information; materially different response vectors are different types. Then the number of households can greatly exceed the number of types, and \(q_j\) expresses the agency’s per-capita supply. Repeating a discrete instance gives the usual bridge to high multiplicity, while mass assignments also allow fractional splits within a type. The outcome remains one intervention per unit of population; this is a continuous population model, not a divisible-resource or lottery model.
The mirror covers the unit-demand assignment problem and these three fairness results. Proposition 2 and Proposition 3 require a common intervention ordering across types. That is plausible for standardized intensity tiers, but the paper notes that its homelessness dataset is not row-sorted. Proposition 4 avoids that restriction but applies only to two interventions. Also, because the paper supplies no named hardness result, these mirrors do not show that discrete hardness dissolves in the continuum. Their value is narrower: they make the type-level, high-multiplicity versions of the paper’s allocation questions explicit and show how its structural and price-of-fairness claims may extend to population shares.
The strongest case against a useful mirror is about the instance regime. The paper’s input is an arbitrary household-specific cost matrix, and its synthetic experiments draw costs from distributions with continuous support. Since a type must include the full cost vector, those regimes have \(\tau=n\) almost surely: exact grouping gives no population compression. The real homelessness dataset is also presented as household-level outcome estimates, not as a small set of repeated profiles. So the paper’s central empirical story does not itself supply a high-multiplicity regime.
That objection has a limit, though. Repeated standardized profiles are plausible for some service systems, and the paper’s assignment model still applies to them. Under that regime, capacity shares and mass flows are a natural way to represent assigning each person one intervention. I cannot rule out a scenario the authors would recognize.
Proposition 4 is the hardest anchor to defeat. With two interventions, a mass version can be stated for arbitrary cost vectors: send the required excess mass away from its preferred intervention in order of increasing regret gap, splitting mass at a tie. This gives both a LoINC-optimal assignment and an efficient assignment. The paper’s result already makes this extension look immediate, but that is not a reason to reject the question under ChoCo’s rules. The mass model remains distinct, and the result that LoINC has price \(1\) would be a valid continuous answer.
Proposition 2 also survives its stronger formulation. For finite support and a common intervention ordering, the greedy rule extends by filling each intervention with the lowest-cost remaining mass, splitting a type at the cutoff. That is a precise, tractable continuous assignment problem. The fact that the paper already gives a fast discrete algorithm makes the computational gain modest, but does not make the mirror ill-posed.
Proposition 3 is the least compelling anchor as a computational question: its mass-share bounds appear to follow by rescaling capacities and counts, and the proposed version assumes \(b>0\). Still, that is a criticism of its likely contribution, not a fundamental obstruction to asking for the bound. The paper’s asymptotic assignment literature does not already settle continuous-population leximin or LoINC; it is not a continuous collision.
So the negative case rests on a mismatch between the paper’s household-specific, often atomless cost inputs and the repeated exact types needed for a meaningful high-multiplicity regime. That makes the mirror’s practical fit uncertain, especially for the experiments emphasized in the paper. It does not defeat the two-intervention LoINC mirror or the ordered-tier leximin mirror. I cannot honestly sustain 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.