| paper | Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap |
| authors | Shayan Chashm Jahan, Masoud Seddighin, Seyed-Mohammad Seyed-Javadi, Mohammad Sharifi |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 3 is a named existence and quality bound, but it does not formulate a computational problem or state an algorithm, running time, hardness result, or approximation algorithm. The proposed typed mass allocation is a coherent high-multiplicity extension of EFX, but that cannot repair the missing computational anchor. The opponent therefore wins on bit (a).
fails bit a — no named computational result to mirror
No anchor is greened; against the proposed Corollary 3 mirror, the strongest objection is that per-capita inventories create a repaired model and the finite \(O_\varepsilon(\sqrt{N}\log N)\) rate disappears after normalization, while the support-wise EFX problem has no algorithmic connection supplied by the paper.
fatal: False
The proposed mirror covers only the derived allocation consequence: \((1-\varepsilon)\)-EFX with \(O_\varepsilon(\sqrt{N}\log N)\) discarded goods. It leaves the extremal \(R(d)\) and \(H(\ell)\) bounds, the permutation variant \(R_p(d)\), and the conjectures outside the mirror.
The strongest positive case is real but qualified: this paper contains no named computational-complexity result. No theorem states that an allocation problem is in \(P\), NP-hard, W[1]-hard, FPT, or similar. Its named results are extremal bounds. Thus, under the strictest reading of the anchor requirement, there is no qualifying computational anchor. The best available anchor is nevertheless a natural algorithmic existence result.
I would lead with Section 4, Corollary 3, proved in this paper:
\[ \text{for every }\varepsilon\in(0,1/2],\text{ a }(1-\varepsilon)\text{-EFX allocation exists after discarding } O_\varepsilon(\sqrt n\log n)\text{ goods}. \]
The corollary is derived from the paper’s Section 4 Theorem 1, also proved here, which states \(H(\ell+1)\ge \ell^2/(20\ln \ell)\), and Corollary 2, which obtains \(R(d)\in O(d\log d)\). The separate introductory Theorem 1 giving the general \(R(d)\)-to-EFX implication is explicitly cited from Chaudhury et al. [2021a].
The corresponding continuous problem is:
\[ \mathrm{Mass\mbox{-}EFX\mbox{-}Discard}_\infty. \]
An instance consists of a finite set \(T\) of complete agent types, a rational distribution \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_{\theta\in T}\mu_\theta=1\), and additive valuations \(v_\theta\) for each type \(\theta\). It also contains finitely many good kinds \(G\), with \(\rho_g\) indivisible copies of good kind \(g\) per unit population. A bundle \(B\) is a finite multiset of good kinds, and
\[ v_\theta(B)=\sum_{g\in G}w_{\theta,g}a_g(B), \]
where \(a_g(B)\) is the number of copies of \(g\) in \(B\).
The decision variable is \(x_{\theta,B}\ge0\), the mass of type-\(\theta\) agents receiving exactly bundle \(B\), together with \(z_g\ge0\), the mass of discarded copies of good \(g\). They must satisfy
\[ \sum_B x_{\theta,B}=\mu_\theta \]
for every \(\theta\), and
\[ \sum_{\theta,B}a_g(B)x_{\theta,B}+z_g=\rho_g \]
for every \(g\). The objective is to minimize
\[ \sum_{g\in G}z_g. \]
The allocation is \((1-\varepsilon)\)-EFX if, whenever \(x_{\theta,B}>0\) and \(x_{\theta',B'}>0\), then for every good \(g\) occurring in \(B'\),
\[ v_\theta(B)\ge (1-\varepsilon)v_\theta(B'\setminus\{g\}). \]
This is deliberately a support-wise condition: it requires EFX for every pair of bundles that is actually used by positive mass. It is not an ex-ante or expected-value relaxation. Goods remain indivisible for every individual agent; only the number of agents receiving each whole bundle is represented continuously.
The natural regime is a large population of households, students, or applicants with a small number \(\tau=|T|\) of complete valuation profiles, together with \(O(N)\) copies of each standardized good kind. Thus \(N\gg\tau\). A rational solution with denominator \(N\) expands into \(N\) named agents and integer numbers of item copies, while any such finite allocation normalizes back to \(x\) and \(z\). This gives the required high-multiplicity bridge. The fact that all agents of one type share the same valuation is not an artificial restriction: it is exactly what “type” means in the programme.
The authors should recognize this as their problem. The allocation remains an allocation of indivisible goods under their exact EFX notion; the only change is replacing repeated, indistinguishable agents by their mass. The connection to their main theorem is also direct: Corollary 3 predicts that in an \(N\)-agent realization the discarded fraction is
\[ O_\varepsilon\!\left(\frac{\log N}{\sqrt N}\right). \]
Thus the continuous limit suggests zero discarded mass for fixed \(\varepsilon\), while the finite-\(N\) version asks for the sharp convergence rate or for an algorithm achieving the bound.
My prior is that the explicit-bundle version is tractable by finite-dimensional optimization, while the natural implicit version with all bundles \(B\subseteq G\) is a candidate Class C problem. Continuization removes assignment-rounding issues, but it does not remove the global combinatorial choice of a mutually EFX-compatible support of bundles. A configuration LP and a pricing oracle are the obvious first approach. The key questions are whether that pricing problem is polynomial, whether the rainbow-cycle argument yields a separation oracle, and whether hardness can already be obtained with \(\tau\) fixed. If hardness requires many distinct valuation types, it is likely discrete multiplicity hardness; if it persists with a bounded type set, it would be genuinely continuum-specific.
The weakest point is substantial: Corollary 3 is an existence bound, not a stated complexity classification, and the paper never formulates the mass allocation problem. Moreover, its proof controls finite graph cardinalities, so \(R(d)\in O(d\log d)\) does not automatically become an algorithm for \(\mathrm{Mass\mbox{-}EFX\mbox{-}Discard}_\infty\). A referee could therefore reasonably call this a promising continuous research question generated by the paper, rather than an already-established computational mirror. Still, it is a faithful mirror of the paper’s EFX result, and it covers the central allocation consequence without pretending that the entire rainbow-cycle theory has already been continuized.
The decisive objection is that this paper supplies no qualifying computational anchor. Its named results are extremal bounds on \(R(d)\) and \(H(\ell)\), plus the derived existence guarantee in Corollary 3. Nothing formulates an input-output allocation problem or proves a complexity, approximation, or parameterized-complexity result. “We can find” is an algorithmic-sounding consequence, but no running time or computational problem is stated. Under ChoCo’s anchoring rule, there is therefore no result here to continuize.
Even granting Corollary 3 as an informal anchor, the proposed \(\mathrm{Mass\mbox{-}EFX\mbox{-}Discard}_\infty\) is not its continuous limit in the informative sense. With the paper’s fixed finite set of goods and \(N\to\infty\), almost all agents receive nothing; allocating every good as a singleton already makes EFX essentially vacuous, with no discarded-good phenomenon left. Scaling goods proportionally with \(N\) avoids that collapse, but it introduces a repeated-inventory fair-division model absent from the paper. That may be sensible, but it is a new model rather than a population-only continuization.
Nor does proportional scaling preserve the paper’s quantitative result. Corollary 3 gives \(O(\sqrt N\log N)\) discarded goods. After normalization by a supply of \(\Theta(N)\), this becomes
\[ O\!\left(\frac{\log N}{\sqrt N}\right)\to 0. \]
Thus the continuous limit records only zero discarded mass; it loses the finite-size rate that the paper actually proves. Recovering that rate requires a second-order \(N\)-dependent analysis, not an atomless society. The proposed mass minimization is consequently a new question whose answer is not supplied by the corollary.
The bundle formulation also does not turn the problem into the kind of continuous optimization ChoCo targets. Support-wise EFX says that two bundles with positive mass must be mutually compatible. This is a disjunctive support condition, not a system of linear inequalities in the masses \(x_{\theta,B}\). With implicitly represented bundles, one needs a mixed-integer or clique/support-selection formulation; a configuration LP and a pricing oracle do not follow automatically. The paper’s rainbow-path argument is a cardinality proof, not a separation oracle, and supplies no algorithmic handle on this new support problem.
A better attempt would mirror the paper’s actual combinatorics directly by assigning masses to vertices of the multipartite graph. That fails to make multiplicity meaningful. Rainbow cycles depend on the existence and identity of particular vertices and edges. Duplicating a vertex type does not change whether a rainbow cycle exists: one representative suffices. Conversely, preserving each vertex’s incident-edge pattern as part of its type makes the types essentially vertex-specific, eliminating the high-multiplicity compression. A graphon or positive-mass cycle notion would be a new relational-continuum theory, outside the programme’s population-only scope.
So the proponent has shown a plausible independent research direction: typed repeated-goods allocation with indivisible bundles and mass-valued support. I cannot honestly claim that such a model could never be worthwhile. But it is not anchored by a computational result in this paper, its literal population limit degenerates, its nondegenerate repair changes the resource model, and its computational core must be invented from scratch. On the programme’s stated standard, this paper should not enter the continuous-mirror catalogue.
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.