Answer: The sharp universal lower bound is \(1/2\). For each fixed \(k\ge2\), the sharp infimum is \(k/(2k-2)\).
Theorem 5.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAny k-bundle MNW-optimal allocation is 1/2-EFF1. 3This is possible e.g., in the extreme case where vi(g) > 0 only of a single item g ∈[kn].
statement extracted from the paper’s text layer; consult the paper for the exact wording
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)\).
A society is given by its support: the list of \(\tau\) agent types \(T\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
There are \(m\ge1\) item types \(G\), nonnegative binary-rational supplies \(q_g\) with \(\sum_gq_g=k\), and nonnegative binary-rational additive values \(v_t(g)\), where \(k\ge2\) is an integer. Values may be zero or tied; no value normalization is imposed.
Bundles are multisets \(\mathcal B=\{B\in\mathbb Z_{\ge0}^{G}:\sum_gB_g=k\}\), allowing repeated item types, with \(v_t(B)=\sum_gB_gv_t(g)\). A feasible mass allocation has \(x_{t,B}\ge0\), \(\sum_Bx_{t,B}=\mu_t\), and \(\sum_{t,B}B_gx_{t,B}=q_g\).
A lexicographic MNW optimum maximizes first \(P(x)=\sum_{t,B:v_t(B)>0}x_{t,B}\), then \(H(x)=\sum_{t,B:v_t(B)>0}x_{t,B}\log v_t(B)\). Both objectives concern realized bundle utilities; all tied optima are included.
For \(\gamma\in[0,1]\), support-wise \(\gamma\)-EFF1 means that every oriented pair with \(x_{t,B}>0\), \(x_{u,D}>0\), and \(v_t(B)<v_t(D)\) admits \(g,h\in G\) with \(B_g>0\), \(D_h>0\), \(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)\); \(\mathbf e_g\) is the unit vector for type \(g\). Comparisons include different bundles held by the same agent type.
Let \(\Gamma(x)\) be the largest such \(\gamma\). For any algorithmic claims, state running times in \(m,\tau,k,L\), where \(L\) is the total binary input length.
What is the sharp universal lower bound on \(\Gamma(x)\) over all instances and all lexicographic MNW optima? Does the discrete \(1/2\)-EFF1 guarantee remain valid and sharp in this mass model, or is the sharp guarantee different?
For finite agents receiving equal-sized bundles, every lexicographic MNW optimum is \(1/2\)-EFF1, and this constant is asymptotically tight as \(k\) grows. [Verified discrete results](https://arxiv.org/html/2507.20899v1#S5).
No result settling this exact mass model was located in the literature search.
The sharp universal guarantee remains \(\boxed{1/2}\). More precisely, for every fixed \(k\ge2\),
\[ \inf_{\text{instances and lexicographic MNW optima }x}\Gamma(x) =\frac{k}{2k-2}. \]
Thus every individual instance has \(\Gamma(x)>1/2\), but no constant larger than \(1/2\) works uniformly over \(k\).
This agrees with the [discrete benchmark](https://arxiv.org/html/2507.20899v1#S5). The proof below establishes the mass-model result directly, including zero utilities, comparisons within one agent type, and optimality of the sharpness construction over all feasible mass allocations.
There are finitely many bundles. The feasible set is nonempty: assign mass \(\mu_tq_g/k\) of type \(t\) to the bundle \(k\mathbf e_g\). This satisfies both the type-mass and supply constraints.
The feasible set is compact, and both objectives are linear functions of the allocation coordinates, with finite coefficients. Consequently, lexicographic optima exist.
Fix any such optimum \(x\), and two supported coordinates \((t,B)\) and \((u,D)\) with
\[ a:=v_t(B)<b:=v_t(D). \]
These coordinates are distinct, even if \(t=u\).
For \(B_g>0\) and \(D_h>0\), define
\[ B'=B-\mathbf e_g+\mathbf e_h,\qquad D'=D-\mathbf e_h+\mathbf e_g. \]
Remove an equal mass \(\varepsilon>0\) from \((t,B)\) and \((u,D)\), and add it to \((t,B')\) and \((u,D')\). Choosing \(\varepsilon\) sufficiently small preserves nonnegativity. Type masses are preserved, and supplies are preserved because \(B'+D'=B+D\). This remains valid when \(t=u\) or some added coordinates coincide.
Suppose first that
\[ a>0,\qquad c:=v_u(D)>0. \]
Write the recipient’s gain and donor’s loss as
\[ r:=v_t(h)-v_t(g)>0,\qquad \delta:=v_u(h)-v_u(g). \]
Then optimality implies
\[ (a+r)(c-\delta)\le ac, \qquad\text{hence}\qquad \delta\ge\frac{cr}{a+r}. \tag{1} \]
Indeed, if \(c-\delta>0\), the exchange preserves \(P\), and its change in \(H\) is
\[ \varepsilon\log\frac{(a+r)(c-\delta)}{ac}, \]
which cannot be positive. If \(c-\delta=0\), the product inequality holds automatically. Nonnegative valuations ensure \(c-\delta\ge0\).
Continue with \(a,c>0\). Define the largest possible gain from a single flip:
\[ d:=\max_{\substack{B_g>0\\D_h>0}} \bigl(v_t(h)-v_t(g)\bigr). \]
Because \(b>a\) and both bundles have \(k\) items, \(d>0\).
Label the \(k\) occurrences in each multiset and pair them by any bijection. Let \(I\) contain the pairs \((g_i,h_i)\) having positive gain
\[ r_i:=v_t(h_i)-v_t(g_i)>0. \]
The sum over all paired differences equals \(b-a\). Discarding nonpositive differences therefore gives
\[ b-a\le\sum_{i\in I}r_i\le kd. \tag{2} \]
For each \(i\in I\), inequality (1) applies. Since the selected occurrences \(h_i\) are distinct and valuations are nonnegative,
\[ \sum_{i\in I}\bigl(v_u(h_i)-v_u(g_i)\bigr) \le\sum_{i\in I}v_u(h_i) \le c. \]
Combining this with (1) and dividing by \(c>0\) yields
\[ \sum_{i\in I}\frac{r_i}{a+r_i}\le1. \]
Because \(r_i\le d\), we consequently have
\[ \frac{b-a}{a+d} \le \frac{\sum_{i\in I}r_i}{a+d} \le \sum_{i\in I}\frac{r_i}{a+r_i} \le1. \]
Together with (2), this proves the two bounds
\[ b\le2a+d,\qquad b\le a+kd. \tag{3} \]
Choose a flip attaining \(d\). Its two post-flip values, both evaluated by type \(t\), are \(a+d\) and \(b-d\).
If \(b-d=0\), this flip establishes exact EFF1. Otherwise, put \(z=d/a>0\). From (3),
\[ \frac{a+d}{b-d} \ge \frac{1+z}{\min\{2,\;1+(k-1)z\}}. \]
This last expression is at least \(k/(2k-2)\):
\[ \frac{1+z}{1+(k-1)z}-\frac{k}{2k-2} = \frac{(k-2)\bigl(1-(k-1)z\bigr)} {2(k-1)\bigl(1+(k-1)z\bigr)} \ge0. \]
Thus the desired flip exists whenever both holders’ realized utilities are positive.
We now justify the cases excluded above.
Suppose \(c=v_u(D)=0\). Choose any rational flip, which exists because \(b>a\).
Every occurrence \(h\) in \(D\) has \(v_u(h)=0\), so the donor’s new utility is \(v_u(g)\ge0\).
If \(a=0\), the recipient becomes positive and no previously positive holder becomes zero, increasing \(P\). If \(a>0\) and \(v_u(g)>0\), \(P\) again increases. Finally, if \(a>0\) and \(v_u(g)=0\), \(P\) stays unchanged while the recipient’s log utility strictly increases.
Every possibility contradicts optimality. Hence an envied supported bundle cannot have zero utility for its own holder.
Suppose \(a=0<c\). Every occurrence \(g\) in \(B\) has \(v_t(g)=0\).
If \(D\) contained at least two occurrences positive for type \(t\), one such occurrence \(h\) would satisfy \(v_u(h)<c\). Otherwise, two distinct occurrences would already contribute at least \(2c\) to \(v_u(D)=c\).
Exchanging this \(h\) with any occurrence \(g\) in \(B\) gives the recipient positive utility and leaves the donor with utility
\[ c-v_u(h)+v_u(g)>0. \]
This increases \(P\), a contradiction.
Therefore \(D\) has exactly one occurrence positive for type \(t\). Exchanging that occurrence with any item in \(B\) makes the recipient positive and leaves the envied bundle with value zero for type \(t\). This establishes exact EFF1.
Combining all cases proves
\[ \boxed{\Gamma(x)\ge\frac{k}{2k-2}} \]
for every lexicographic MNW optimum, including every tied optimum.
Fix \(k\ge2\), and choose a positive binary-rational parameter \(s\) satisfying
\[ 0<s\le\frac{k}{k-1}. \]
Use two agent types and two item types, denoted \(A,Z\), with masses and supplies
\[ \mu_1=\mu_2=\frac12,\qquad q_A=q_Z=\frac{k}{2}. \]
Their values are
| Agent type | \(A\) | \(Z\) |
|---|---:|---:|
| \(1\) | \(1\) | \(0\) |
| \(2\) | \(1+s\) | \(1\) |
Consider the allocation \(x^*\) giving every type-\(1\) agent \(k\) copies of \(A\), and every type-\(2\) agent \(k\) copies of \(Z\). It is feasible, and
\[ P(x^*)=1,\qquad H(x^*)=\log k. \]
We next certify its optimality against all feasible mass allocations.
Let \(z\) denote the number of copies of \(A\) in a bundle, and set
\[ \lambda:=\log\frac{k}{k-1}. \]
For type \(1\), a positive bundle has utility \(z\), where \(1\le z\le k\). Since
\[ \log k-\log z = \sum_{j=z+1}^{k}\log\frac{j}{j-1} \ge(k-z)\lambda, \]
we obtain
\[ \log z\le\log k+\lambda(z-k). \tag{4} \]
For type \(2\), the utility is \(k+sz\). The binomial expansion gives \((1+s/k)^z\ge1+sz/k\), so
\[ \log(k+sz) \le\log k+z\log(1+s/k) \le\log k+\lambda z. \tag{5} \]
The final inequality uses \(s\le k/(k-1)\).
Any allocation with \(P=1\) assigns no positive mass to type-\(1\) bundles with \(z=0\). We may therefore sum (4) and (5) over that allocation. Its total consumption of \(A\) is \(k/2\), giving
\[ H(x) \le \log k+\lambda\left(\frac{k}{2}-k\mu_1\right) =\log k. \]
Thus \(x^*\) is a lexicographic MNW optimum.
Type \(1\) does not envy type \(2\). Type \(2\) values its own bundle at \(k\) and the other bundle at \(k(1+s)\).
Every possible rational flip exchanges one \(Z\) for one \(A\). Its post-flip values for type \(2\) are
\[ k+s,\qquad k+(k-1)s. \]
Consequently,
\[ \Gamma(x^*)=\frac{k+s}{k+(k-1)s}. \]
As \(s\) approaches \(k/(k-1)\) from below, this approaches
\[ \frac{k}{2k-2}. \]
The parameters can be chosen dyadic: for example,
\[ s_n=2^{-n}\left\lfloor 2^n\frac{k}{k-1}\right\rfloor. \]
Hence sharpness holds even if “binary-rational” requires finite binary expansions. If arbitrary rationals encoded in binary are allowed, choosing \(s=k/(k-1)\) attains the bound exactly.
For every fixed \(k\), the sharp infimum is \(k/(2k-2)\). Therefore
\[ \inf_{k\ge2}\frac{k}{2k-2}=\frac12. \]
The discrete \(1/2\)-EFF1 guarantee remains valid and asymptotically sharp in this mass model.
⟨structured verdict parsed — rendered above⟩
The argument resolves the target in substance. The fixed-\(k\) bound \(\Gamma(x)\ge k/(2k-2)\), the matching infimum construction, and the universal sharp constant \(1/2\) are correct. I found one minor terminology omission and no major mathematical gaps.
The proposed allocation assigns mass \(\mu_tq_g/k\) to \(k\mathbf e_g\). Summing over \(g\) gives type mass \(\mu_t\), and summing the resulting consumption over \(t\) gives supply \(q_g\). Zero supplies cause no difficulty.
There are finitely many bundles for every finite \(m,k\). The feasible set is closed and bounded, and the coefficients of both objectives are finite: zero-utility coordinates are excluded from the logarithmic objective. Maximizing \(P\), then maximizing \(H\) on the first objective’s maximizing face, therefore yields a lexicographic optimum. This step is valid without value normalization.
Strict envy ensures that the two source coordinates are distinct, including when \(t=u\). Removing sufficiently small equal mass from them and adding that mass to the exchanged bundles preserves nonnegativity, each type’s total mass, and aggregate supplies.
Coincidences among destination and source coordinates do not invalidate the argument: the updates and objective changes add linearly. Thus comparisons between distinct supported bundles of the same agent type are covered.
For \(a,c>0\) and an improving flip with \(r>0\), the recipient’s new utility is positive. When \(c-\delta>0\), the exchange preserves \(P\), and the stated logarithmic change in \(H\) is correct. Optimality consequently gives \((a+r)(c-\delta)\le ac\).
When \(c-\delta=0\), that product inequality is automatic; the proof does not incorrectly invoke preservation of \(P\) in this case. Nonnegative additive valuations ensure \(c-\delta\ge0\).
Rearrangement yields precisely \(\delta\ge cr/(a+r)\). All divisions have positive denominators.
Because both bundles have \(k\) occurrences and \(b>a\), at least one cross-bundle item difference is positive, so \(d>0\).
The occurrence pairing correctly handles repeated item types. The sum of all paired differences is \(b-a\), and discarding nonpositive differences gives \(b-a\le\sum_{i\in I}r_i\le kd\).
Applying the exchange inequality separately to each positive paired difference is legitimate; these exchanges need not occur simultaneously. The selected donor occurrences are distinct, so nonnegativity gives \(\sum_{i\in I}\delta_i\le c\). Consequently, \(\sum_{i\in I}r_i/(a+r_i)\le1\).
Since \(r_i\le d\), the denominator comparison has the correct direction. The resulting bounds \(b\le2a+d\) and \(b\le a+kd\) both follow.
A flip attaining \(d\) gives the two values \(a+d\) and \(b-d\), evaluated by the envious type. The second is nonnegative because it is the value of an actual bundle.
If \(b-d=0\), the fairness inequality holds even for \(\gamma=1\). Otherwise, the two preceding bounds imply the stated ratio estimate.
The split at \(z=1/(k-1)\) is correct. I rechecked the displayed subtraction: its numerator is \((k-2)(1-(k-1)z)\), with the stated positive denominator. Thus both branches yield \(k/(2k-2)\).
The edge case \(k=2\) is included: the factor is \(1\), and the subtraction in the second branch vanishes.
If \(c=0\), every occurrence in \(D\) has zero value for its own holder. For an improving flip, each of the three cases listed produces either a strict increase in \(P\) or preservation of \(P\) with a strict increase in \(H\). The contradiction is valid.
If \(a=0<c\), every occurrence in \(B\) has zero value for the envious type. If two occurrences in \(D\) were positive for that type, at least one would have donor value strictly below \(c\). The resulting exchange would make the recipient positive while keeping the donor positive, contradicting maximality of \(P\).
Hence \(D\) has exactly one occurrence positive for the envious type; existence follows from \(b>0\). Exchanging it leaves the comparison bundle with value zero for that type and establishes exact EFF1.
These arguments also remain valid for repeated occurrences and coincident allocation coordinates. Instances with no strict envy comparisons satisfy the definition vacuously.
The construction satisfies the required support, mass, supply, and valuation conditions. Its claimed values \(P(x^*)=1\) and \(H(x^*)=\log k\) are correct. Since total allocated mass is \(1\), no allocation can have \(P>1\).
Inequality (4) is valid for every integer \(1\le z\le k\): each term in its telescoping sum is at least \(\lambda\).
Inequality (5) is valid for every integer \(0\le z\le k\). The binomial bound uses nonnegative terms, and \(s\le k/(k-1)\) gives the stated comparison of logarithms.
For any allocation with \(P=1\), all supported type-\(1\) bundles have \(z\ge1\), so the two inequalities apply to every relevant coordinate. Summing them uses exactly the supplied quantity \(q_A=k/2\) and the fixed mass \(\mu_1=1/2\). The resulting bound \(H(x)\le\log k\) certifies optimality against all feasible mass allocations.
The construction has only one oriented strict-envy comparison: type \(2\) envies the type-\(1\) bundle. Its available improving exchanges all have the stated post-flip values. Thus \(\Gamma(x^*)=(k+s)/(k+(k-1)s)\); this ratio lies in \([0,1]\), including equality to \(1\) when \(k=2\).
The endpoint limit is \(k/(2k-2)\). The proposed dyadic sequence is positive, obeys the required upper bound, and converges to that endpoint. This establishes the infimum under finite binary expansions as well as under general binary-encoded rationals.
Finally, the infimum over integers \(k\ge2\) is \(1/2\). The comparison with the [cited discrete benchmark](https://arxiv.org/html/2507.20899v1#S5) is consistent, but the mass-model proof does not depend on importing that theorem.
The only repair needed is to define “rational flip”, used in Sections 3 and 4, as a supported exchange satisfying \(v_t(h)>v_t(g)\). The intended meaning is clear from context, and this requires no new mathematics.
No algorithmic running-time claim is made, so no complexity bound in \(m,\tau,k,L\) is missing. The established result is a sharp fairness guarantee, rather than a computational complexity classification.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.