| paper | Fairness Under Equal-Sized Bundles: Impossibility Results and Approximation Guarantees |
| authors | Alviona Mancho, E. Markakis, Nicos Protopapas |
| venue | SAGT 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: The sharp universal lower bound is \(1/2\). For each fixed \(k\ge2\), the sharp infimum is \(k/(2k-2)\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given finite agent types \(T\), item types \(G\), masses \(\mu\), per-capita supplies \(q\) with \(\sum_t\mu_t=1\) and \(\sum_gq_g=k\), and additive values \(v_t(g)\), compute a mass allocation \(x_{t,B}\) over integral \(k\)-item bundles \(B\) satisfying \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B}B_gx_{t,B}=q_g\), that is lexicographically MNW-optimal, and determine its largest \(\gamma\) for support-wise \(\gamma\)-EFF1: for every oriented pair of supported states \((t,B),(u,D)\), any envy \(v_t(B)<v_t(D)\) must admit a rational flip \(g\in B,h\in D\) with \(v_t(h)>v_t(g)\) and \(v_t(B-\mathbf e_g+\mathbf e_h)\ge\gamma v_t(D-\mathbf e_h+\mathbf e_g)\).
Use a high-multiplicity configuration model in which each unit of type-\(t\) mass receives an integral bundle \(B\), while \(x_{t,B}\) is divisible cohort mass. Maximize first \(\sum_{t,B:v_t(B)>0}x_{t,B}\), then \(\sum_{t,B:v_t(B)>0}x_{t,B}\log v_t(B)\), subject to per-capita item supplies; evaluate fairness on every oriented pair of supported bundle states.
Theorem 5.2 has no explicit runtime or complexity bound, so treating exact MNW optimization as an algorithmic anchor depends on accepting the stated welfare rule as a computational method.
fatal: False
The mirror covers Theorems 5.2 and 5.4, including the \(1/2\)-EFF1 guarantee and its tightness, but leaves the Round-Robin, envy-cycle, leximin, social-welfare, and exact EFFX results untreated.
This paper does admit a credible continuous mirror, but narrowly: the strongest case is Section 5, where maximum Nash welfare is combined with flip-based fairness. The paper contains no named NP-hardness result, so I would not manufacture a hardness anchor. My lead is Theorem 5.2, supported by its tightness result, Theorem 5.4.
A natural regime is a large hospital or workforce assigning each worker exactly \(k\) shifts. There may be millions of workers but only finitely many preference or skill profiles, and only finitely many shift categories. Workers of the same type have the same additive valuation over shift types. Each shift remains indivisible for an individual worker; only the population and the supply of each shift category are represented by mass.
Formally, let \(T\) be a finite set of worker types, \(G\) a finite set of item types, \(\mu_t\) the mass of workers of type \(t\), and \(q_g\) the per-capita supply of item type \(g\), with \(\sum_t\mu_t=1\) and \(\sum_gq_g=k\). A bundle is an integral vector \(B\in\mathbb Z_{\ge0}^{G}\) with \(\sum_g B_g=k\), and \(v_t(B)=\sum_gB_gv_t(g)\).
The allocation variable is \(x_{t,B}\), the mass of type-\(t\) workers receiving bundle \(B\). Thus
\[ \sum_Bx_{t,B}=\mu_t \quad\text{and}\quad \sum_{t,B}B_gx_{t,B}=q_g. \]
This is not fractional allocation of an individual bundle: every unit of mass receives an integral bundle. It is fractional only at the cohort level.
The continuous analogue of the paper’s MNW rule is to lexicographically maximize first the mass receiving positive value,
\[ \sum_{t,B:v_t(B)>0}x_{t,B}, \]
and then maximize
\[ \Phi(x)=\sum_{t,B:v_t(B)>0}x_{t,B}\log v_t(B). \]
This is the geometric-mean form of Nash welfare: for a finite replication of the population, \(\exp(\Phi(x))\) is the normalized Nash welfare.
The fairness condition is also ex post. For every pair of supported states \((t,B)\) and \((u,D)\), if \(v_t(B)<v_t(D)\), then a \(1/2\)-EFF1 requirement demands an item type \(g\) in \(B\) and \(h\) in \(D\), with \(v_t(h)>v_t(g)\), such that
\[ v_t(B-\mathbf e_g+\mathbf e_h) \ge \frac12\,v_t(D-\mathbf e_h+\mathbf e_g). \]
Thus the condition applies to every positive-mass pair of bundle states, not merely to average bundle values.
My lead problem is Continuous \(k\)-Bundle MNW–EFF1:
Given \((T,G,\mu,q,v)\), compute a continuous MNW-optimal allocation \(x\), together with the largest \(\gamma\) for which \(x\) is \(\gamma\)-EFF1. The central question is whether every continuous MNW optimum is \(1/2\)-EFF1.
The anchor is Theorem 5.2, proved in this paper: “Any \(k\)-bundle MNW-optimal allocation is \(1/2\)-EFF1.” The theorem includes the paper’s lexicographic treatment of zero-valued agents: it first maximizes the number of agents with positive value and then the Nash product over them.
This theorem is particularly mirrorable because its proof is an exchange argument. If two positive-mass bundle states violated \(1/2\)-EFF1, one could exchange an arbitrarily small mass of those two bundles. The same multiplicative inequality used in the paper would strictly increase \(\Phi(x)\), contradicting continuous MNW optimality. Nothing essential in that argument depends on named individuals or on there being only finitely many agents. I therefore expect this mirror to be tractable in the structural sense of Class A. With fixed \(k\), the bundle configurations form a finite configuration LP; with variable \(k\), the interesting remaining issue is the pricing problem over bundle configurations.
The second, independent problem is Continuous MNW–EFF1 Gap. Given the same input, compute an MNW-optimal \(x\) and its worst supported pairwise EFF1 ratio; then determine the worst case over all such continuous instances. Equivalently, ask whether
\[ \inf_I\ \inf_{x\in\operatorname{MNW}(I)}\gamma(x) \]
is \(1/2\), where \(\gamma(x)\) is the largest \(\gamma\) for which \(x\) is \(\gamma\)-EFF1.
The anchor is Theorem 5.4, proved in this paper: there are instances where a \(k\)-bundle MNW-optimal allocation is no better than \(1/2\)-EFF1. The paper gives a two-agent, \(2k\)-item construction, and the obstruction survives genuine continuization. Take two worker types of masses \(1/2\), two item types \(a,b\), and supplies \(q_a=q_b=k/2\). Let
\[ v_1(a)=c,\quad v_1(b)=0, \qquad v_2(a)=2,\quad v_2(b)=1. \]
The continuous MNW optimum gives type \(1\) the bundle \(a^k\) and type \(2\) the bundle \(b^k\). Type \(2\) envies type \(1\). After any rational flip, type \(2\)'s value is \(k+1\), while the value of the other bundle from type \(2\)'s perspective is \(2k-1\). Hence the ratio is
\[ \frac{k+1}{2k-1}\longrightarrow\frac12. \]
The construction uses only two positive-mass agent types and two item types, so this is not merely a finite two-agent instance disguised as a continuum. It also inherits the paper’s common-ranking feature; with suitable \(c\), it satisfies the paper’s normalized and few-value restrictions. Combined with the continuous extension of Theorem 5.2, I would expect the exact worst-case continuous MNW guarantee to remain \(1/2\). This is persistence of a finite obstruction, rather than continuum-specific hardness.
The high-multiplicity dictionary is clean here. Rational \(x\) can be multiplied by a common denominator to obtain a finite replicated instance, while every finite allocation induces an empirical \(x\). The paper is therefore not already studying the continuous-population model: its \(n\) agents and \(kn\) items are named and finite. The mirror adds a population limit and per-capita item supplies while preserving integral bundles and the original EFF1 thought experiment.
I would not stretch this mirror to Theorems 3.1–4.7. Round-Robin and envy-cycle elimination depend on sequential choices, agent order, and discrete item ownership; a continuum version would require additional design choices. The two MNW theorems are enough.
The weakest point is that “continuous MNW” and pairwise EFF1 admit more than one extension. If one instead evaluates only type-average bundles, the problem becomes outcome-space fractionalization and is no longer the paper’s fairness question. The proposed support-wise definition avoids that objection, but a referee could still argue that assigning a mass of identical workers to several integral bundles changes the intended notion of an allocation. The case survives because this is exactly what high multiplicity means in a recurring-shift or recurring-team regime, and the lower-bound construction remains valid even with positive mass for every type.
The strongest negative case is that the proposed mirror changes the paper’s model in two coupled ways. The paper has named, indivisible items with arbitrary identities; the proposed model replaces them by item types with per-capita supplies. That is not merely continuizing the population. If item identities matter, there is no bounded item-type space; if they do not, the problem has become a repeated-shift or repeated-team problem with additional symmetry assumptions. The paper’s EFF1 notion concerns exchanging actual items, while the mirror concerns exchanging copies of an item category. One could therefore argue that the resulting problem is a new high-multiplicity fair-division problem, not a continuous version of this paper.
This objection is not enough, however. The paper itself motivates equal-sized bundles by shifts and teams, and the programme expressly permits per-capita supplies when population continuization forces them. Identical shift copies can be complete item types, and additive valuations make their identities irrelevant. The authors would recognise that model. Thus the alleged model change is a legitimate co-modification, not a fatal distortion.
Theorem 5.2 is also a weak anchor if one insists that a mirror must transfer a computational result: it is a structural welfare–fairness theorem, not a complexity classification. But that does not defeat the proposed question. With finitely many agent and item types, the variables \(x_{t,B}\) describe a finite configuration space, and continuous MNW is a concave optimization problem over a transportation polytope. The paper’s exchange proof genuinely lifts: exchanging an arbitrarily small positive mass between two supported bundle states is the continuum analogue of exchanging two agents’ bundles. Disallowing such splitting would abandon high multiplicity; replacing it by average bundles would change EFF1. The proponent’s support-wise definition is therefore the natural one.
Theorem 5.4 survives even more cleanly. Two types of mass \(1/2\), with \(q_a=q_b=k/2\), are not a disguised single-agent example: every unit of mass still receives an integral \(k\)-item bundle, and both types have positive measure. The supply constraints force the same \(a^k\) and \(b^k\) allocation as in the finite construction, preserving the ratio
\[ \frac{k+1}{2k-1}\longrightarrow \frac12. \]
The finite-replication dictionary is exact for rational masses and supplies. Calling this “only a finite obstruction” would be precisely the wrong objection: persistence under high multiplicity is evidence that the mirror is meaningful.
The proposed MNW–EFF1 gap is likewise well-defined on the finite configuration space. It is not already answered continuously by the paper, and replacing supported bundle states by type-average bundles would indeed be an invalid fractional-outcome reformulation. The remaining reservation is only that the paper does not itself establish a complexity theorem for MNW optimization; the continuous problem would be a new computational study attached to a structural theorem.
So the honest negative case is weak. The best criticism is that the anchor results are not themselves complexity results and that the mirror requires a repeated-item interpretation. But the programme permits exactly that interpretation, and neither Theorem 5.2 nor Theorem 5.4 can be defeated without rejecting the high-multiplicity model itself. At least one worthwhile continuous mirror therefore survives.
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.