Answer: Yes: report-independent uniform assignment succeeds above a sufficient threshold of \(O(g\log(\tau g/\varepsilon)/(\mu_{\min}(1-\alpha)^2))\). With unrestricted support size, admissible societies with arbitrarily many items can have no successful assignment.
Theorem 4 — class: algorithmic
Given \(g\) equal-mass groups, \(m\) indivisible items, \(\alpha\in[0,1)\), \(\varepsilon>0\), and a finite-support society \(\mu\) over complete types \(t=(k,v)\), where \(k\in\{1,\ldots,g\}\), \(v\in[0,1]^m\), \(\sum_v\mu_{k,v}=1/g\), and \(\sum_{j=1}^m v_j\ge m\mu_{\min}\) for every \(t\in\operatorname{supp}(\mu)\), construct a report-independent randomized assignment \(a:\{1,\ldots,m\}\to\{1,\ldots,g\}\) such that, with probability at least \(1-\varepsilon\), every supported type satisfies \(\sum_{j:a(j)=k}v_j\ge\alpha\sum_{j:a(j)=\ell}v_j\) for every \(\ell\), and determine the sufficient threshold in \(m\) and implementation complexity as functions of \(g,\tau,\alpha,\mu_{\min},\varepsilon\).
Let \(g\ge2\) and \(m\ge1\) be integers, with rational parameters \(\alpha\in[0,1)\), \(\mu_{\min}\in(0,1]\), and \(\varepsilon\in(0,1)\).
A society is given by its support: a list of \(\tau\) complete types \(t=(k,v)\), each with positive binary-rational mass \(\mu_{k,v}\), where \(k\in\{1,\ldots,g\}\) and \(v\in([0,1]\cap\mathbb Q)^m\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Require \(\sum_v\mu_{k,v}=1/g\) for every group and \(\sum_{j=1}^m v_j\ge m\mu_{\min}\) for every supported type. Valuations are additive, and all members of a group share its entire bundle.
An assignment \(a:\{1,\ldots,m\}\to\{1,\ldots,g\}\) allocates each indivisible item exactly once; empty bundles are allowed. It is \(\alpha\)-approximately envy-free when \(\sum_{j:a(j)=k}v_j\ge\alpha\sum_{j:a(j)=\ell}v_j\) for every supported \((k,v)\) and every \(\ell\), with equality accepted.
A randomized mechanism is report-independent if its output law depends only on the public parameters \(m,g,\tau,\alpha,\mu_{\min},\varepsilon\), and not on reported valuation vectors or type masses. The society is fixed, and probability refers only to mechanism randomness.
Can a report-independent randomized mechanism guarantee simultaneous \(\alpha\)-approximate envy-freeness with probability at least \(1-\varepsilon\) for every such society once \(m\) is sufficiently large, or can this guarantee fail? What sufficient threshold and implementation complexity are attainable in \(m,g,\tau,L,\alpha,\mu_{\min},\varepsilon\)?
For finite societies of \(n\) agents in equal-sized groups, independent random item values in \([0,1]\) with each mean at least \(\mu_{\min}>0\) permit report-independent uniform random assignment to achieve \(\alpha\)-approximate envy-freeness with high probability when \(m>Cg\log n\), where \(C\) depends only on \(\alpha,\mu_{\min}\). [Verified result](https://arxiv.org/pdf/1706.08219).
No result settling the stated fixed, finite-support society model was located in the literature search.
For every fixed admissible society, independent uniform assignment succeeds with probability at least \(1-\varepsilon\) whenever
\[
m\ge
\frac{g}{\mu_{\min}(1-\sqrt{\alpha})^2}
\log\frac{\tau(g-1)}{\varepsilon},
\qquad 0<\alpha<1.
\]
In particular, the simpler sufficient threshold
\[
m\ge
\frac{4g}{\mu_{\min}(1-\alpha)^2}
\log\frac{\tau(g-1)}{\varepsilon}
\]
is valid.
Thus the fixed finite-support model admits a guarantee without any randomness assumptions on valuations. However, a threshold based on the number of items alone can fail when support size is unrestricted: there are admissible societies with arbitrarily many items and no approximately envy-free assignment.
When \(\alpha=0\), every assignment satisfies the requirement, so no threshold is needed.
Assign each item independently and uniformly to one of the \(g\) groups. This mechanism depends only on \(m\) and \(g\), and hence is report-independent.
Fix a supported type \(t=(k,v)\), and write
\[
S_t=\sum_{j=1}^{m}v_j\ge m\mu_{\min}.
\]
For another group \(\ell\ne k\), define
\[
D_{t,\ell}
=
\sum_{j=1}^{m}
v_j\bigl(\mathbf 1_{\{a(j)=k\}}
-\alpha\mathbf 1_{\{a(j)=\ell\}}\bigr).
\]
The envy constraint against \(\ell\) fails exactly when \(D_{t,\ell}<0\). Equality therefore counts as success, as required.
We will prove
\[
\Pr(D_{t,\ell}<0)
\le
\exp\left(
-\frac{(1-\sqrt{\alpha})^2S_t}{g}
\right).
\]
Taking a union bound over the \(\tau(g-1)\) relevant constraints then gives
\[
\Pr(\text{some envy constraint fails})
\le
\tau(g-1)
\exp\left(
-\frac{m\mu_{\min}(1-\sqrt{\alpha})^2}{g}
\right).
\]
This establishes the first threshold. The second follows from
\[
(1-\sqrt{\alpha})^2
=
\frac{(1-\alpha)^2}{(1+\sqrt{\alpha})^2}
\ge \frac{(1-\alpha)^2}{4}.
\]
The probability statement holds for each fixed society, uniformly over all admissible valuation vectors and masses. It does not assert that one random assignment simultaneously works for every possible society.
Assume \(0<\alpha<1\), and set
\[
s=\frac12\log\frac1\alpha>0,
\qquad
q=(1-\sqrt{\alpha})^2.
\]
For the contribution of item \(j\), independence and uniform assignment give
\[
\mathbb E\!\left[
e^{-sv_j(\mathbf 1_{\{a(j)=k\}}
-\alpha\mathbf 1_{\{a(j)=\ell\}})}
\right]
=
1+\frac{e^{-sv_j}+e^{\alpha sv_j}-2}{g}.
\]
Consider the function
\[
h(x)=e^{-sx}+e^{\alpha sx}-2.
\]
It is convex because
\[
h''(x)=s^2e^{-sx}+\alpha^2s^2e^{\alpha sx}\ge0,
\]
and \(h(0)=0\). Consequently, for \(0\le x\le1\), the chord inequality gives
\[
h(x)\le xh(1).
\]
Convexity of the exponential function also gives
\[
e^{\alpha s}
=
e^{(1-\alpha)0+\alpha s}
\le (1-\alpha)+\alpha e^s.
\]
Since \(e^{-s}=\sqrt{\alpha}\) and \(\alpha e^s=\sqrt{\alpha}\), we obtain
\[
h(1)
\le
e^{-s}+\alpha e^s-1-\alpha
=
2\sqrt{\alpha}-1-\alpha
=
-q.
\]
Thus
\[
\mathbb E\!\left[
e^{-sv_j(\mathbf 1_{\{a(j)=k\}}
-\alpha\mathbf 1_{\{a(j)=\ell\}})}
\right]
\le
1-\frac{qv_j}{g}
\le
e^{-qv_j/g}.
\]
The assignment labels of different items are independent. Multiplying these bounds yields
\[
\mathbb E[e^{-sD_{t,\ell}}]
\le
\prod_{j=1}^{m}e^{-qv_j/g}
=
e^{-qS_t/g}.
\]
Finally, \(D_{t,\ell}<0\) implies \(e^{-sD_{t,\ell}}>1\). Markov’s inequality therefore gives
\[
\Pr(D_{t,\ell}<0)
\le
\mathbb E[e^{-sD_{t,\ell}}]
\le e^{-qS_t/g},
\]
as claimed.
No independence between different types or different envy constraints was used. The type masses play no role because success is required for every supported type.
Let \(b=\lceil\log_2 g\rceil\). For each item, generate a uniform \(b\)-bit integer; accept it if it is less than \(g\), otherwise repeat. An accepted integer specifies the recipient group.
The acceptance probability is \(g/2^b>1/2\), unless \(g\) is a power of two, in which case it is one. Thus exact sampling uses
Its running time is finite almost surely but has no deterministic upper bound.
The mechanism need not inspect the valuation vectors or masses. If the input representation requires scanning the complete society, that adds \(O(L)\) input-processing time.
A deterministic running-time bound is also attainable, using part of the error budget.
For each item, allow at most
\[
R=\left\lceil\log_2\frac{2m}{\varepsilon}\right\rceil
\]
sampling attempts. If all attempts reject, assign that item to group \(1\).
Couple this implementation with exact rejection sampling using the same random bits. For any item, the probability that all \(R\) attempts reject is at most \(2^{-R}\). Hence
\[
\Pr(\text{the two assignments differ})
\le m2^{-R}\le\frac{\varepsilon}{2}.
\]
Applying the earlier probability bound with error budget \(\varepsilon/2\), the bounded-time mechanism succeeds with probability at least \(1-\varepsilon\) whenever
\[
m\ge
\frac{g}{\mu_{\min}(1-\sqrt{\alpha})^2}
\log\frac{2\tau(g-1)}{\varepsilon}.
\]
Its worst-case sampling complexity is
\[
O\!\left(m\log g\log\frac{m}{\varepsilon}\right)
\]
bit operations and random bits. Its output law remains report-independent.
If desired, an assignment can separately be verified by calculating all bundle values for each supported type. This takes \(O(\tau(m+g))\) rational arithmetic operations and polynomial time in \(L\): denominators and numerators of the required sums have polynomially bounded bit length. Verification is not needed by the mechanism.
We now show why unrestricted support prevents a general item-count-only guarantee.
Fix
\[
g=2,\qquad 0<\alpha<1,\qquad
0<\mu_{\min}<\frac{1+\alpha}{2}.
\]
For every sufficiently large \(m\), let
\[
r=\lceil m\mu_{\min}\rceil.
\]
Because the inequality on \(\mu_{\min}\) is strict, sufficiently large \(m\) satisfies
\[
r<\frac{1+\alpha}{2}m.
\]
In each group, include the valuation vector \(\mathbf 1_S\) for every subset \(S\subseteq\{1,\ldots,m\}\) of cardinality \(r\). Here \(\mathbf 1_S\) values an item at one precisely when it belongs to \(S\). Every supported type satisfies
\[
\sum_j(\mathbf 1_S)_j=r\ge m\mu_{\min}.
\]
The support size is
\[
\tau=2\binom mr.
\]
These types can receive positive dyadic masses summing to \(1/2\) in each group. Explicitly, put \(N=\binom mr\) and choose
\[
d=\lceil\log_2N\rceil+2.
\]
Give the first \(N-1\) types mass \(2^{-d}\), and the last type mass
\[
\frac12-(N-1)2^{-d}>0.
\]
Thus the construction satisfies even the interpretation of binary-rational masses as dyadic rationals.
Consider any assignment. Choose a group with the smaller bundle, of cardinality \(b\le m/2\). The other bundle has cardinality
\[
c=m-b\ge m/2.
\]
There are two cases.
\[
0<\alpha r,
\]
so its envy constraint fails.
\[
r<\frac{1+\alpha}{2}m\le(1+\alpha)c,
\]
implying
\[
r-c<\alpha c.
\]
Its envy constraint again fails.
Every assignment therefore fails for this fixed society. Consequently, every randomized mechanism has success probability zero, regardless of report independence.
For a particularly transparent subfamily, take \(\mu_{\min}=1/2\) and even \(m\). Then \(r=m/2\), and the support is exponential:
\[
\tau=2\binom m{m/2}\ge\frac{2^{m+1}}{m+1}.
\]
The inequality follows because the central binomial coefficient is the largest of the \(m+1\) coefficients whose sum is \(2^m\).
This does not contradict the sufficient threshold: these societies have support growing with the number of items.
Large support does not always obstruct a guarantee.
Assign items deterministically so that bundle sizes differ by at most one. Put
\[
b_-=\left\lfloor\frac mg\right\rfloor,
\qquad
b_+=\left\lceil\frac mg\right\rceil.
\]
For every supported type, the value of its own bundle is at least
\[
m\mu_{\min}-(m-b_-),
\]
because each item outside that bundle has value at most one. Every other bundle has value at most \(b_+\).
Thus this report-independent assignment succeeds for every admissible society whenever
\[
m\mu_{\min}-m+b_-\ge\alpha b_+.
\]
In particular, if
\[
\eta=\mu_{\min}-1+\frac{1-\alpha}{g}>0,
\]
it suffices that
\[
m\eta\ge1+\alpha.
\]
Indeed, \(b_-\ge m/g-1\) and \(b_+\le m/g+1\) imply the preceding condition. At the boundary \(\eta=0\), it also holds whenever \(g\) divides \(m\).
[Theorem 4 of Manurangsi and Suksompong](https://arxiv.org/pdf/1706.08219) analyzes uniform random assignment under independent random valuations. The proof above instead fixes every valuation vector and uses independence only in the assignment labels.
The stated deterministic lower bound on each type’s total value is sufficient. No sampling of agents, probabilistic assumptions on preferences, or dependence on the smallest positive type mass is required.
⟨structured verdict parsed — rendered above⟩
The output resolves the task as stated. The probability bound, both sampling implementations, the nonexistence construction, and the dense-regime guarantee are correct. I found no major or minor mathematical issues.
The mechanism assigns every item exactly once, independently and uniformly among the \(g\) groups. Its law depends only on \(m\) and \(g\), so it satisfies the stated definition of report independence.
The guarantee concerns simultaneous satisfaction of all constraints within each fixed admissible society. The output explicitly distinguishes this from one assignment working simultaneously for every possible society. This is the correct quantifier order.
The support size \(\tau\) is used as the number of supported complete types. The masses need not enter the probability calculation because the requirement applies to every supported type regardless of its mass.
The case \(\alpha=0\) is correctly separated: nonnegative valuations make every required inequality hold for every assignment.
Fix a supported type \(t=(k,v)\) and another group \(\ell\ne k\).
All hypotheses of the elementary inequalities used here are satisfied.
There are exactly \(\tau(g-1)\) potentially nontrivial constraints. Comparisons with the type’s own group hold automatically because \(\alpha<1\) and bundle values are nonnegative.
The union bound and \(S_t\ge m\mu_{\min}\) give the stated total failure bound. Solving that bound for failure probability at most \(\varepsilon\) yields the first threshold, with the stated constant.
The identity involving \(1-\sqrt{\alpha}\), and the bound \((1+\sqrt{\alpha})^2\le4\), correctly establish the simpler threshold. Both bounds remain valid at equality in the threshold.
The exact rejection sampler is correct: conditional on acceptance, each integer below \(g\) is equally likely. Acceptance probability exceeds one half, so the expected number of attempts per item is bounded by a constant. The stated expected sampling, random-bit, and storage costs follow under the usual word-operation model.
For the bounded-time implementation:
The worst-case sampling cost is correctly bounded and polynomial in the indicated quantities. The optional input scan and verification costs are also consistent: exact rational sums and comparisons have polynomially bounded bit lengths in the explicit input length \(L\).
These are sampling costs; the output does not claim that checking the logarithmic threshold is part of the mechanism.
The construction establishes failure for the explicitly stated parameter regime.
The strict assumption \(\mu_{\min}<(1+\alpha)/2\) ensures that, for sufficiently large \(m\), the ceiling \(r=\lceil m\mu_{\min}\rceil\) satisfies the required strict inequality. Every indicator valuation lies in the permitted domain and meets the total-value lower bound.
The support count is correct. The proposed dyadic masses are positive and sum to one half in each group, including when \(N=1\).
For any assignment, choosing a smaller bundle gives \(b\le m/2\) and \(c\ge m/2\). Both cases are valid:
Thus every assignment fails. Success probability is zero for every randomized mechanism, including mechanisms that inspect reports.
The central-binomial-coefficient bound is correct. This construction refutes a general support-independent item threshold in the stated regime; it does not claim impossibility for every parameter choice.
The own-bundle lower bound follows from the total-value assumption and the upper bound of one on each outside item. The other-bundle upper bound follows from its cardinality. The floor and ceiling estimates correctly imply sufficiency of \(m\eta\ge1+\alpha\). At \(\eta=0\), divisibility by \(g\) makes the stated condition hold exactly.
The description of the supplied literature result agrees with [Theorem 4 of Manurangsi and Suksompong](https://arxiv.org/pdf/1706.08219). That theorem is contextual rather than an invoked premise of this proof; the new guarantee is established independently.
No repair or additional lemma is needed. The polynomial classification below concerns the explicit randomized mechanism under its sufficient threshold, not an unrestricted feasibility decision algorithm.
⟨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.