| paper | Fair and Efficient Resource Allocation with Partial Information |
| authors | Daniel Halpern, Nisarg Shah |
| venue | IJCAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a finite set \(T\) of top-\(k\) ranking types with mass distribution \(\mu\), finite good classes \(G\) with \(\rho_g\) indivisible copies per unit population, and class-symmetric rankings \(\sigma_t\), decide whether there exist masses \(x_{t,A}\ge0\) over integral bundles \(A\) such that \(\sum_A x_{t,A}=\mu_t\), \(\sum_{t,A}A_gx_{t,A}=\rho_g\) for every \(g\), and whenever \(x_{t,A}>0\) and \(x_{s,B}>0\), every additive unit-sum valuation \(v\succeq\sigma_t\) satisfies \(v(A)\ge v(B)\) or \(v(A)\ge v(B\setminus\{g\})\) for some \(g\in B\).
A finite-configuration feasibility model for a high-multiplicity indivisible-goods market: \(T\) carries agent mass \(\mu\), \(x_{t,A}\) assigns that mass to integral bundle configurations, \(\rho\) supplies the goods, and the objective is robust EF1 feasibility.
The paper's top-\(k\) rankings are over named goods, so the finite-type limit still needs an explicit rule for treating replicated copies as a class; otherwise \(T\) and the population limit are not canonical.
fatal: False
It covers Theorem 3's robust EF1 feasibility and threshold question over \(m\)-by-\(n\) allocation instances, but does not securely cover Theorem 4's distortion optimum or the MMS results.
The strongest honest positive case is conditional: the paper has a credible continuous-population mirror, but it does not contain a named complexity-class result of the kind your anchor rule requests. Its numbered theorems establish feasibility thresholds and distortion bounds, while the claims about “efficient algorithms” are not themselves stated as \(P\)-membership theorems. Thus this cannot honestly be presented as a full ChoCo complexity anchor. If exact algorithmic/performance theorems are admitted, the following is the best case.
The natural regime is large course-registration or housing-allocation markets. There are many agents, but only finitely many repeated preference and valuation cohorts. Goods are replicated seats or units: for each good class \(g\), \(\rho_g\) copies are available per unit population. Let \(T\) be the finite set of observed top-\(k\) ranking types, with mass distribution \(\mu\). A latent complete type additionally contains an additive valuation consistent with its observed ranking. Agents of the same latent type are genuinely interchangeable; the mechanism sees only the aggregate top-\(k\) distribution.
An allocation assigns every individual an integral bundle, but is represented in the continuum by \(x_{t,A}\), the mass of observed type \(t\) receiving integral bundle \(A\). Thus
\[ \sum_A x_{t,A}=\mu_t \]
and
\[ \sum_{t,A} A_gx_{t,A}=\rho_g \]
for every good class \(g\). The fractional object is population mass, not a fractional bundle received by an individual.
My lead candidate is Continuous Robust-EF1 Top-\(k\) Feasibility, mirroring Theorem 3. Its instance consists of \((T,\mu,G,\rho,k)\), where each \(t\in T\) supplies a top-\(k\) ranking \(\sigma_t\). The question is whether there exists an allocation \(x\), using only these rankings, such that every positive-mass agent is EF1 against every other allocated bundle for every additive valuation consistent with that agent’s observed ranking. Formally, whenever \(x_{t,A},x_{s,B}>0\), every \(v\) consistent with \(\sigma_t\) must satisfy
\[ v(A)\ge v(B) \]
or
\[ \exists g\in B:\quad v(A)\ge v(B\setminus\{g\}). \]
A solution is the mass assignment \(x\), or, in the rule version, an ordinal rule mapping \(\mu\) to such an assignment.
The anchor is Theorem 3, proved in the paper. It states that with \(n\) agents and \(m\) goods, EF1 can be guaranteed from top-\(k\) rankings if and only if
\[ k\ge \begin{cases} m-n,&m\bmod n=0,\\ m-2,&m\bmod n=1,\\ m-(m\bmod n),&m\bmod n>1. \end{cases} \]
The proof gives modified round-robin rules, assigning the unranked remainder so that it only permutes goods from the final round.
I would expect the continuous version to be Class A. The round-robin construction becomes a mass schedule, while the allocation layer is a transportation or column-generation problem over integral bundles. The genuinely new questions are whether the modular threshold has a clean per-capita limit, whether robust EF1 can be separated efficiently over the valuation polytope, and whether every feasible mass solution decomposes into integral individual bundles without losing the guarantee.
A second, supporting mirror is Continuous Ordinal-EF1 Distortion, based on Theorem 4. Given \((T,\mu,G,\rho,k)\), the mechanism must choose an allocation using only the observed ranking distribution. An adversary chooses latent additive valuations consistent with those rankings. The distortion is
\[ \sup_v \frac{\operatorname{OPT}(v)} {\mathbb E[\operatorname{SW}(F(\mu),v)]}, \]
where every allocation in the support of \(F(\mu)\) must be EF1 for the realized valuations. The problem is to find the smallest achievable distortion, separately for deterministic and randomized ordinal rules.
Theorem 4, proved by the authors with the proof deferred to the full version, states that deterministic EF1 rules have unbounded distortion on the \(k=0\) feasible family; with \(k\ge1\), the optimal deterministic distortion is \(\Theta(n^2)\); and the optimal randomized distortion over the whole EF1-feasible family is \(\Theta(n)\).
This mirror tests whether those bounds are caused by named-agent multiplicity or by the number of distinct preference/valuation roles and scarce good classes. Replicating every role into a large cohort should preserve the adversarial welfare construction, so my expectation is a Class B-style transfer of the lower-bound obstruction, although not a complexity-hardness result. The continuum may improve the deterministic bound if mass-splitting within an observed type effectively supplies randomization; determining whether that happens is itself a worthwhile question.
The authors would recognize both mirrors: they retain additive valuations, top-\(k\) information, indivisible individual bundles, EF1, and welfare distortion. The required co-modification—replicated goods with per-capita supply—is the natural high-multiplicity version of their allocation problem, not a switch to outcome-space fractional allocation.
The weakest point is serious. Theorem 3 and Theorem 4 are not NP-hardness, \(P\), FPT, or other explicit complexity classifications. Under the literal anchor requirement, the paper therefore has no qualifying computational anchor, and these mirrors should be labelled conditional rather than presented as a compliant positive case. Substantively, the modular \(m\bmod n\) phenomenon may also disappear or change once agents and goods are represented by masses, so the continuous problem is credible but its exact relationship to the printed theorem remains an open modelling result rather than something established by the paper.
The decisive objection is that neither proposed anchor is a computational-complexity result. Theorem 3 is an information-threshold characterization, and Theorem 4 is an optimal-distortion bound. The paper proves no \(P\)-membership, hardness, approximation, or parameterized-complexity theorem for a computational problem. Under ChoCo’s stated anchor rule, the paper therefore supplies no qualifying result to continuize. Any serious continuous fair-division project would be new work rather than a mirror of a named computational contribution.
Theorem 3 also has no stable population limit. If the number of indivisible goods \(m\) stays fixed while the population becomes atomless, the goods can be assigned only to a measure-zero set; almost every agent receives the empty bundle, and EF1 becomes vacuous. The proponent’s repair—scaling goods with population—is natural, but it exposes a deeper problem. Let the per-capita supply converge to an integer \(q\). The sequence \(m_N=qN\) requires \(k_N\ge(q-1)N\), whereas \(m_N=qN+1\), with exactly the same limiting per-capita supply, requires \(k_N\ge m_N-2\), hence \(k_N/N\to q\). A single globally negligible extra good changes the limiting threshold by one full good per agent. The theorem is therefore driven by finite indivisibility and the \(m\bmod n\) final-round effect, not by a well-defined continuous population object.
Moreover, with finitely many replicated good classes and unit-sum valuations, the value of one individual good is typically \(O(1/N)\). The “up to one good” exemption then disappears asymptotically and EF1 collapses toward ordinary envy-freeness. Replacing it by a positive-mass exemption would be a sensible new fairness notion, but it would no longer be the paper’s EF1 problem. Treating copies as distinct instead makes the number of goods and the top-\(k\) input grow with the population, so the proposed finite-type model no longer has a stable object. The mass assignment \(x_{t,A}\) is mathematically possible, but it is a new configuration-allocation problem, not a continuous form of Theorem 3.
Theorem 4 is even less compatible with high multiplicity. Its \(\Omega(n^2)\) construction obtains welfare from many agent-specific valuation roles and many corresponding goods: the pair-specific goods are precisely what make different agents valuable in different ways. Repeating a finite set of complete valuation types and replicating their goods forces the value of each copy down under unit-sum normalization, so the construction no longer produces the same population-sized welfare gap. Giving every repeated agent a separate high-value good preserves the lower bound only by creating a new complete type for every agent. That is the opposite of high multiplicity.
The proposed \(\mu\) over top-\(k\) rankings also does not determine the distortion objective. Social welfare and \(\operatorname{OPT}\) depend on the hidden cardinal valuation distribution and on its coupling with the assigned bundles. If the latent valuation is part of the type, its mass distribution must be supplied; if it is hidden and adversarial, the model is a robust incomplete-information problem over latent populations; if it is probabilistic, the continuous object is principally a prior or noise model. Each is defensible as new research, but none is the population-only mirror claimed here.
Finally, splitting a positive-mass ranking cohort across bundles effectively supplies ex ante randomization, erasing the deterministic/randomized distinction central to Theorem 4. Yet EF1 is imposed on individual integral bundles, while the adversary may correlate hidden valuations with the split. There is no canonical interpretation of this interaction in the paper. Restoring it requires latent individual types; forgetting it changes the distortion problem.
So the negative case is strong under ChoCo’s formal standard: no qualifying computational anchor survives, and both proposed continuizations either degenerate, depend on finite lattice artefacts, or require a materially new hidden-type model. The honest limitation is that a carefully designed high-multiplicity fair-allocation project could still be worthwhile in its own right. What fails is the claim that this paper already offers a worthwhile continuous computational mirror.
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.