| paper | Possible Fairness for Allocating Indivisible Resources |
| authors | — |
| venue | AAMAS 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given finite agent types \(T\), item categories \(G\), rational type masses \(\mu\), per-capita supply \(\sigma\in\mathbb Q_{\ge0}^{G}\), and weak ordinal rankings \(\succeq_t\), find finite-support masses \(x_{t,b}\ge0\) over integer bundles \(b\in\mathbb Z_{\ge0}^{G}\) and additive witnesses \(u_t\) consistent with \(\succeq_t\) such that \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b=\sigma\), every used bundle has size \(\lfloor\bar m\rfloor\) or \(\lceil\bar m\rceil\) for \(\bar m=\sum_{g\in G}\sigma_g\), every used bundle \(b\) of type \(t\) satisfies \(u_t\cdot b\ge u_t\cdot(b-e_g)\) for every item \(g\) appearing in any used bundle \(b'\), and \(u_t\cdot b\ge\lambda_t\), where \(\lambda_t=\sup\{\min_{b'':y_{b''}>0}u_t\cdot b'':y\ge0,\sum_{b''}y_{b''}=1,\sum_{b''}y_{b''}b''=\sigma,\ y\text{ has finite support}\}\).
A repeated-indivisible-goods high-multiplicity economy: finite ordinal agent types \(T\) have masses \(\mu\), categories \(G\) have per-capita supply \(\sigma\), and \(x_{t,b}\) assigns mass of type \(t\) to whole integer bundle configurations \(b\); feasibility requires balancedness, typewise possible-cardinal witnesses \(u_t\), \(p\)-EFX, and \(p\)-MMS.
The continuous formulation strengthens the paper's per-agent existential semantics by requiring one common \(u_t\) for all clones of type \(t\), and the cases do not establish equivalence or a polynomial batched implementation.
fatal: False
The mirror covers Theorem 2's simultaneous \(p\)-EFX, \(p\)-MMS, and balanced-allocation result in a repeated-resource high-multiplicity regime. It leaves the general individual-item setting, the Pareto-optimality guarantee, necessary fairness, Proposition 3, and the paper's structural lemmas unmirrored.
The strongest positive case is a qualified yes: this paper supports a genuine high-multiplicity extension mirror, with Theorem 2 as the lead anchor. I would not present it as a literal mirror of every arbitrary labelled-item instance; I would present it as the natural repeated-agent, repeated-resource regime that the paper’s treatment of indifferences and balancedness already motivates.
The anchor is Theorem 2, proved in this paper:
“For any instance with ordinal preferences, Algorithm 3 computes an allocation that is simultaneously p-EFX, p-MMS and balanced in polynomial time.”
The regime is a large population of exchangeable agents receiving repeated copies of a finite set of indivisible resource categories. Let \(T\) be the finite set of complete agent types, where a type \(t\) specifies a weak ordinal ranking \(\succeq_t\) over resource categories \(G=\{g_1,\ldots,g_\kappa\}\). The society is a rational mass vector \(\mu\), with \(\mu_t\) the fraction of agents of type \(t\). A natural example is a public distribution programme giving standardized indivisible kits to a very large number of households, where households fall into a modest number of preference or need types and the kits contain many repeated copies of a few item categories.
Resource supply must scale with population. Let \(\sigma_g\) be the number of copies of category \(g\) per unit population. This is not fractional allocation: every copy remains indivisible. It is a normalized census of repeated copies. If all masses have denominator \(q\), then \(q\mu_t\) agents of type \(t\), \(q\sigma_g\) copies of \(g\), and \(qx_{t,b}\) agents assigned to bundle \(b\) recover an ordinary finite instance exactly.
The continuous decision variable is \(x_{t,b}\), the mass of type-\(t\) agents receiving the whole integer bundle \(b\in\mathbb{Z}_{\ge0}^{\kappa}\). It must satisfy \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=\sigma_g\) for every \(g\). If \(\bar m=\sum_g\sigma_g\), balancedness requires every used bundle to have size \(\lfloor\bar m\rfloor\) or \(\lceil\bar m\rceil\), with exactly the appropriate mass receiving the larger size. The objective is a feasibility/search objective: output one such allocation, just as Theorem 2 outputs one finite allocation.
To preserve possible fairness, the solution also supplies one additive cardinal witness \(u_t\) per agent type, consistent with \(\succeq_t\). Requiring the witness to be typewise is appropriate for high multiplicity, and it is compatible with the paper’s construction \(u_i(g)=W_i+v_i(g)\): clones of the same ordinal type can use the same lexicographic valuation.
The continuous p-EFX condition is the following. For every \(t\), every bundle \(b\) with \(x_{t,b}>0\), every used bundle \(b'\), and every category \(g\) with \(b'_g>0\), require \(u_t\cdot b\ge u_t\cdot(b-e_g)\). Thus a positive-mass agent must not envy any other positive-mass bundle after deletion of any one indivisible item.
For p-MMS, define the continuum maximin share of type \(t\) as the supremum, over finite-support distributions \(y\) on whole integer bundles satisfying \(\sum_b y_b b=\sigma\), of the minimum \(u_t\)-value of a bundle in the support. Every bundle assigned positive mass to type \(t\) must have value at least this threshold. This is the high-multiplicity limit of partitioning \(q\sigma\) indivisible copies into \(q\) bundles: \(y_b\) is the fraction of bundles of configuration \(b\).
Call this problem \(\mathrm{pFairAlloc}_\infty\): given \((T,\mu,G,\sigma,\succeq)\), find \(x\) and a common typewise valuation profile \(u\) satisfying supply conservation, balancedness, p-EFX, and p-MMS simultaneously. It is recognizably the paper’s question: ordinal agents, indivisible goods, possible cardinal fairness, and balanced allocation remain exactly the central objects. Only the population and repeated-resource regime has been compressed.
I expect the bounded-category, bounded-bundle version to be Class A. When \(\kappa\) and the number of items per agent are fixed, there are finitely many bundle configurations, the maximin thresholds have a finite configuration formulation, and Algorithm 3’s picking process should admit a batched implementation over type masses. The interesting open question is whether this can be made polynomial in \(\tau\), \(\kappa\), and the encoding length \(L\), rather than merely fixed-parameter tractable in the number of bundle configurations. If \(\kappa\) or bundle size is unrestricted, configuration pricing may itself become hard; that would be a possible Class C boundary, not something established by this paper.
I am deliberately not claiming hardness transfer: the paper contains no named NP-hardness theorem. Nor am I extending the claim to necessary EFX/MMS, Proposition 3, or the paper’s Pareto-optimality statement. Pareto comparisons among continuum allocations would require an additional identity-preserving semantics.
The weakest point is that the mirror replaces individually labelled items by repeated resource categories and replaces an \(n\)-way finite MMS partition by its asymptotic configuration-distribution form. A sceptic can therefore call it an extension rather than a direct mirror. The reply is that this is precisely a legitimate high-multiplicity regime: rational denominator clearing gives exact finite clone instances, whole bundles remain indivisible, and the paper itself identifies similar items and balanced allocations as motivating cases. The claim should remain modest—Theorem 2 has a credible continuous high-multiplicity analogue in this regime—not that every instance or every theorem in the paper has been continuized.
Theorem 2 is the only serious anchor, and the strongest objection is that its proposed mirror has no nondegenerate population-only limit.
Keep the paper’s finite item set \(M\) while letting the agent population grow. Once \(n>|M|\), every \(n\)-partition has an empty bundle, so \(\operatorname{MMS}_n=0\). With at most one item per recipient, EFX is also automatic: deleting the other recipient’s only item leaves the empty bundle. Balancedness is automatic as well. Thus the continuum gives a vacuous fairness problem.
The proponent avoids this by scaling the item supply with the population. But that is no longer merely continuizing the population. It introduces a repeated-resource economy and replaces the paper’s allocation of labelled items by a census of bundle configurations. That can be a sensible new model, but it is not a limit of the paper’s general problem. If item identities are retained, the resource description grows with the clone population and there is no meaningful finite-type compression. If items are collapsed into genuinely identical categories, the paper’s item-level allocation structure has been removed.
Indeed, when the per-capita supply is integral, \(\sigma\in\mathbb Z_{\ge0}^{\kappa}\), the proposed problem collapses completely: give every agent the same bundle \(\sigma\). Then, for every additive valuation \(u_t\),
\[ u_t(\sigma)\ge u_t(\sigma-e_g) \]
so EFX holds, while the average-value bound and the partition into identical bundles give
\[ \operatorname{MMS}_{\infty}(u_t)=u_t(\sigma). \]
Balancedness is exact. Preferences are irrelevant. Nonintegral supply leaves only a remainder/configuration problem, not the paper’s substantive possible-fairness problem.
There is also a quantifier mismatch. In the paper, p-EFX and p-MMS permit each named agent to choose a separate cardinal completion of her ordinal ranking. The proposed mirror instead requires one valuation \(u_t\) for every mass of type \(t\), including agents of that type who receive different bundles. That is a new clone-consistency restriction. If the original existential semantics is preserved, the formulation needs variables for the distribution of cardinal completions \(u\), so the finite ordinal type space no longer captures complete agent types. The paper’s “same valuation profile” observation does not fix this: its profile is indexed by named agents and is an output witness, not a typewise input assumption.
Finally, Theorem 2’s algorithm does not automatically batch. Its exchange graph and removal rules operate on individual item ownership and individual agents. Allowing a type’s mass to split across bundles produces a support-wise configuration problem. With fixed category count and fixed bundle size, one can enumerate configurations and obtain a finite flow formulation, but that is a heavily bounded new problem. Once those parameters are part of the input, the configuration catalogue can be exponential, and the proposed polynomial algorithm is only conjectured.
So the negative case is: fixed supply makes the mirror vacuous; scalable supply changes the resource model; identical repeated supply often trivializes possible fairness; and preserving the original existential semantics destroys finite-type compression. I would therefore reject the claimed universal mirror under a strict population-only standard. I would not call the case airtight, however: if ChoCo accepts joint scaling of agents and repeated goods as a legitimate extension, Theorem 2 remains a credible but narrow high-multiplicity research problem rather than a clear “no.”
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.