| paper | New Fairness Concepts for Allocating Indivisible Items |
| authors | Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, Giovanna Varricchio |
| 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 4
statement extracted from the paper’s text layer
Given rational type masses \(\mu\in\Delta_\tau\), rational per-capita supplies \(\rho\in\mathbb{Q}_{\ge0}^q\) of indivisible item classes, additive valuations \(v_\theta(g)\), and a finite bundle bound \(K\), does there exist a bundle census \(x_{\theta,b}\) satisfying type-mass and item-supply constraints such that every positive-support pair \((\theta,b)\) has a certificate census retaining some mass \(0<\varepsilon\le x_{\theta,b}\) of type \(\theta\) with bundle \(b\), while every certificate bundle \(b'\) satisfies \(v_\theta(b)\ge v_\theta(b')-v_\theta(g)\) for every positively valued item \(g\in b'\); compute such a census and certificates.
A high-multiplicity fair-division market with agent types \(\theta\) of mass \(\mu_\theta\), repeated indivisible item classes \(g\) with supply \(\rho_g\), integral bundle configurations \(b\), census variables \(x_{\theta,b}\), and focal-group EEFX certificate variables.
In the atomless limit, preserving one focal bundle has zero resource effect, while requiring positive \(\varepsilon\)-mass changes an individual EEFX certificate into a group certificate; moreover, the support-dependent certificate condition is not plainly an LP.
fatal: False
The mirror covers Theorem 4’s existence and polynomial computation of EEFX allocations, with possible implications for MXS feasibility. It leaves the NP-hardness of Theorem 5, the implication theorems, verification complexity, and the paper’s other fairness questions untreated.
My strongest case is a qualified Class A mirror of Theorem 4, proved in this paper: “In any fair division instance, an EEFX allocation exists and can be computed in polynomial time.” I would not use Theorem 5 as an anchor: its NP-hardness reduction has only two agents and relies on a finite collection of exceptional item values, so direct hardness transfer to a population limit would be unconvincing.
The natural regime is a large repeated allocation market: for example, a university assigning many copies of a fixed catalogue of course seats, or a public programme distributing standardized bundles to a very large cohort. There are \(N\) agents, but only \(\tau\) complete valuation types, with \(N\gg\tau\). There are also \(N\rho_g\) physically distinct copies of each item class \(g\), where \(g\in G=\{1,\ldots,q\}\). Copies remain indivisible; they merely have identical values for every agent type. A type includes the entire additive valuation vector, so agents with the same type are genuinely interchangeable.
The continuous problem I would call \(\mathsf{EEFX}_\infty\) is this. An instance consists of rational type masses \(\mu\in\Delta_\tau\), rational per-capita item supplies \(\rho\in\mathbb{Q}_{\ge 0}^{q}\), additive valuations \(v_\theta(g)\in\mathbb{Q}_{\ge0}\), and a finite maximum bundle size \(K\). Let \(\mathcal B=\{b\in\mathbb Z_{\ge0}^{q}:\sum_g b_g\le K\}\) be the set of integral bundle configurations.
The decision variable is a bundle census \(x_{\theta,b}\): the mass of type-\(\theta\) agents receiving the indivisible bundle \(b\). It must satisfy \(\sum_b x_{\theta,b}=\mu_\theta\) for every \(\theta\), and \(\sum_{\theta,b}x_{\theta,b}b_g=\rho_g\) for every item class \(g\). Thus \(x\) may split a type across several bundles, exactly as a large finite population may give different bundles to different clones. It does not split an individual item.
For every pair \((\theta,b)\) with \(x_{\theta,b}>0\), there must be an EEFX certificate. Formally, there must exist some \(0<\varepsilon\le x_{\theta,b}\) and a certificate census \(y^{\theta,b}_{\theta',b'}\) satisfying \(\sum_{b'}y^{\theta,b}_{\theta',b'}=\mu_{\theta'}-\varepsilon\mathbf 1_{\theta'=\theta}\) and \(\sum_{\theta',b'}y^{\theta,b}_{\theta',b'}b'_g=\rho_g-\varepsilon b_g\). The missing \(\varepsilon\)-mass is the group of focal type-\(\theta\) agents retained with bundle \(b\). Every bundle \(b'\) used by the certificate must obey \(v_\theta(b)\ge v_\theta(b')-v_\theta(g)\) for every \(g\) with \(b'_g>0\) and \(v_\theta(g)>0\).
The question is to output such an \(x\), together with certificates for every positive-support pair. The original theorem has no optimization objective beyond feasibility, so the objective here is simply to find a feasible census, equivalently to minimize \(0\). A secondary objective such as maximizing aggregate welfare could be added, but is not part of the anchor.
This is recognizable as the authors’ problem. The fairness notion is still EEFX, the valuations are still additive, and the certificate still means that the remaining indivisible items can be reshuffled while the focal agent keeps her bundle. The only change is that repeated agents and repeated item copies are represented by their census. If all masses and supplies are rational, denominator clearing produces a finite instance with cloned agents and indivisible item copies.
I expect \(\mathsf{EEFX}_\infty\) to be tractable in the natural bounded-catalogue regime. For fixed \(q\) and \(K\), the configuration set \(\mathcal B\) is polynomially bounded, each certificate is a linear feasibility problem, and the master allocation is another LP. More ambitiously, with an implicit configuration catalogue, the problem has exactly the shape the continuous programme is designed to expose: a configuration LP whose difficulty is the pricing/separation problem over integral bundles. The likely Class A result is an FPT or polynomial algorithm in structured catalogue parameters, with possible continuum-specific hardness when bundle pricing is completely unrestricted.
The paper’s proof gives useful guidance but not the continuous theorem itself. Algorithm 1 and Lemma 3 show that EEFX certificates arise from a structured reallocation, while the mass formulation asks whether that structure can be compressed into type-level flows and configuration columns. The main follow-up questions are whether certificates have polynomial-size support, whether implicit bundle pricing is polynomial, whether continuous solutions round to exact or approximate finite EEFX allocations, and whether the paper’s Corollary 1 has an analogous Pareto-optimal MXS version.
The weakest point is essential: with a fixed finite set of items and a continuum of agents, almost everyone receives the empty bundle, so the limit degenerates. The mirror therefore requires item supplies to scale with the population. That makes it an extension to a repeated-indivisible-item regime rather than a literal limit with the paper’s one-off item set. I think that is defensible because repeated copies are still exactly the paper’s indivisible-item model, and large course-seat or standardized-goods markets are genuine high-multiplicity settings. But if the authors insist that only the population may scale while the item inventory remains fixed, then this paper has no useful continuous mirror.
The only serious anchor is Theorem 4, so the negative case cannot rely on the absence of a computational result. The strongest objection is that its direct population mirror degenerates.
If the paper’s item set remains fixed while the number of agents tends to infinity, at most \(m\) agents can receive nonempty bundles. Almost all agents therefore receive the empty bundle. Indeed, assigning each item to a different agent gives an EEFX allocation: every other bundle becomes empty after removing its sole item. The continuous census puts essentially all mass on the empty bundle, so the population limit has discarded the fairness phenomenon Theorem 4 studies.
The proposed repair scales item supplies with the population. That is a reasonable large-market model, but it is no longer continuization of the population alone. It simultaneously replaces the finite item set by a continuum of repeated item copies, introduces per-capita supplies \(\rho\), and imposes a bounded bundle catalogue through \(K\). This is an author-recognizable extension of fair division, but it is a different two-sided configuration-allocation problem, not a continuous mirror of the theorem as stated.
There is also a semantic problem that scaling does not remove. EEFX is not merely a constraint on type masses. For each individual, it preserves that individual’s exact bundle and asks whether the remaining named items can be rearranged so that every other bundle passes the “remove any one item” test. In an atomless population, the focal agent has mass zero. Retaining her bundle consumes no mass of items or agents in the limit. Thus the exact finite certificate becomes either vacuous at the resource level or must be repaired by retaining a positive \(\varepsilon\)-mass of clones.
The latter repair is not innocuous. A fixed \(\varepsilon>0\) changes the predicate from an individual certificate to a positive-mass group certificate. Letting \(\varepsilon\) tend to zero restores the atomless limit but loses the finite resource effect of preserving one bundle. The genuinely faithful alternative is a continuum plus a marked finite agent, or a separate Palm-style certificate for every possible bundle. That is no longer a society represented solely by a type distribution; the decisive object is again an individual atom.
The proposed computational formulation also overstates its LP character. For a fixed support pair \((\theta,b)\), finding a certificate is a linear feasibility problem. But the global condition is
\[ x_{\theta,b}>0 \;\Longrightarrow\; \text{there exists a certificate for }(\theta,b), \]
which is support-dependent and generally disjunctive. Mixing two feasible censuses can introduce a bundle whose certificate is invalid in the mixture. Hence the master problem is not simply the LP described in the case for; it needs support enumeration, integer activation variables, or a new structural theorem. With fixed \(q\) and \(K\), exhaustive enumeration makes the model a small finite configuration problem. If \(q\) or \(K\) is part of the input, the configuration catalogue and its support structure are precisely new sources of complexity that Theorem 4 does not address.
So the negative case defeats a clean, population-only mirror: fixed supplies make the limit vacuous, while scalable supplies and marked certificates create a new repeated-agent/repeated-item model with altered semantics and an unproved configuration problem. I cannot honestly claim that no worthwhile extension exists at all. If joint scaling of agents and item copies is admitted as an acceptable extension, the proponent has a plausible research direction. But it should be labelled an extension or re-modelling, not a faithful continuous mirror of Theorem 4.
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.