Answer: Polynomial-time solvable; for the stated formulation the sharp worst-case value is \(1/\theta^*=\tau\), independently of \(\mu\). A projective-plane family gives \(\Omega(\sqrt{\tau})\), but is not extremal.
Lemma 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any agent i, the value CCSi is the optimal solution to the following LP: max X k∈[m] vik · xk , (1) s.t. X k∈[m] vjk · xk ≤uj([m]) n , ∀j ∈([n] \ {i}) ; (2) 0 ≤xk ≤1 , ∀k ∈[m] . Similarly, the envy free share EFSi is the solution to the following linear program: max X k∈[m] vik · xik , (3) s.t. X k∈[m] vjk · xik ≤ X k∈[m] vjk · xjk , ∀j ∈([n] \ {i}) ; (4) X j∈[n] xjk ≤1 , ∀k ∈[m] ; xjk ≥0 , ∀j ∈[n], k ∈[m] .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) divisible resources, rational type masses \(\mu\) over valuation-vector types \(v_t\), and an integer population scale \(N\) with \(N\mu_t\) integral, compute each type's CCS \(\sigma_t\) using constraints from represented other agents, then maximize \(\theta\) over type-level bundles \(a_t\) satisfying \(v_t \cdot a_t \ge \theta \sigma_t\) for every positive-mass type, \(\sum_t \mu_t a_{t,k} \le 1/N\) for every resource, and \(0 \le a_{t,k} \le 1\).
Let \(T\) be a finite type set, \(\tau=|T|\), with rational masses \(\mu_t>0\) satisfying \(\sum_t\mu_t=1\), nonnegative valuation vectors \(v_t\), and per-capita supply vector \(b\). Define
\(E_t^{\infty}=\max\{v_t^\top z:z\ge0,\ y_s\ge0,\ \sum_s\mu_s y_{s,k}\le b_k\ \forall k,\ v_r^\top z\le v_r^\top y_r\ \forall r\in T\}\).
For a type-level allocation \(a\), let \(\theta^*\) be the maximum \(\theta\) such that \(\sum_t\mu_ta_{t,k}\le b_k\) for every \(k\), and \(v_t^\top a_t\ge\theta E_t^{\infty}\) for every \(t\in T\).
Is computing \(\theta^*\) for rational inputs polynomial-time solvable, or is it NP-hard? What is the sharp worst-case dependence of \(1/\theta^*\) on \(\tau\) and \(\mu\), including whether a projective-plane family yields \(\Omega(\sqrt{\tau})\)?
For the finite individual-agent model with linear valuations, Bai, Munagala, Shen, and Zhang prove a worst-case \(\Omega(\sqrt n)\) lower bound for simultaneously approximating cake-cutting shares, via a finite-projective-plane construction with \(n=q^2+q+1\) agents ([source](https://arxiv.org/abs/2411.10434)).
That result concerns equal-weight individual agents; the cited source does not state a result for the above distribution-over-types formulation.
Under the definition stated literally, computing \(\theta^*\) is polynomial-time solvable. Moreover, for every positive rational mass vector \(\mu\), the sharp worst-case value is
\(\displaystyle \sup \frac{1}{\theta^*}=\tau.\)
If zero supply coordinates are allowed, the value \(\tau\) is attained exactly. If every supply coordinate must be strictly positive, the supremum remains \(\tau\). A finite-projective-plane family does yield \(\Omega(\sqrt{\tau})\), but this is not worst-case sharp for the stated benchmark.
The reason the bound differs from the finite-agent cake-cutting result is crucial: the test bundle \(z\) is not charged against supply.
Assume \(b\geq 0\), and that \(a\) and \(\theta\) are optimized jointly.
For each \(t\), the definition of \(E_t^\infty\) is a rational linear program with \((\tau+1)m\) variables, where \(m\) is the number of goods, and \(m+\tau\) substantive constraints.
It is feasible because \(z=0\) and \(y_s=0\) are feasible. It is bounded because the constraint for \(r=t\) gives
\(\displaystyle v_t^\top z\leq v_t^\top y_t,\)
while supply feasibility and \(\mu_t>0\) imply, coordinatewise,
\(\displaystyle y_{t,k}\leq \frac{b_k}{\mu_t}.\)
Consequently,
\(\displaystyle E_t^\infty\leq \frac{v_t^\top b}{\mu_t}<\infty.\)
Conversely, \(z=b\) and \(y_s=b\) for every \(s\) are feasible because \(\sum_s\mu_s=1\). Hence \(E_t^\infty\geq v_t^\top b\). In particular,
\(\displaystyle E_t^\infty=0\quad\Longleftrightarrow\quad v_t^\top b=0.\)
After computing the rational numbers \(E_t^\infty\), compute \(\theta^*\) from the linear program
\(\displaystyle \max \theta\)
subject to \(a_{t,k}\geq0\),
\(\displaystyle \sum_t\mu_ta_{t,k}\leq b_k\)
for every \(k\), and
\(\displaystyle v_t^\top a_t\geq\theta E_t^\infty\)
for every \(t\).
This LP has \(\tau m+1\) variables and \(m+\tau\) substantive constraints. Rational linear programming is solvable exactly in polynomial time in the Turing model; the intermediate optimal values \(E_t^\infty\) have polynomially bounded encoding length by the standard determinant bounds for rational basic feasible solutions. Therefore the associated threshold decision problem and the exact computation of \(\theta^*\) are polynomial-time solvable.
If all \(E_t^\infty=0\), then \(\theta^*=+\infty\). Below, suppose at least one benchmark is positive.
Let
\(\displaystyle A=\{t\in T:E_t^\infty>0\},\qquad r=|A|.\)
For every \(t\in A\), choose an optimal witness \((z^{(t)},y^{(t)})\) for \(E_t^\infty\). Define
\(\displaystyle a_s=\frac1r\sum_{t\in A}y_s^{(t)}.\)
This allocation is feasible because, for every good \(k\),
\(\displaystyle \sum_s\mu_sa_{s,k}=\frac1r\sum_{t\in A}\sum_s\mu_sy_{s,k}^{(t)}\leq\frac1r\sum_{t\in A}b_k=b_k.\)
For \(s\in A\), the summand corresponding to \(t=s\) satisfies
\(\displaystyle v_s^\top y_s^{(s)}\geq v_s^\top z^{(s)}=E_s^\infty.\)
All other summands are nonnegative. Therefore
\(\displaystyle v_s^\top a_s\geq\frac{E_s^\infty}{r}.\)
For \(s\notin A\), the benchmark is zero and the fairness constraint is automatic. Thus
\(\displaystyle \theta^*\geq\frac1r,\qquad \frac1{\theta^*}\leq r\leq\tau.\)
This argument uses no lower bound on the masses.
Fix arbitrary positive rational masses \((\mu_t)_{t\in T}\). Introduce one common good \(c\) and one private good \(p_t\) for every type \(t\). Set
\(\displaystyle b_c=1,\qquad b_{p_t}=0.\)
Let type \(t\) value \(c\) and \(p_t\) at one, and all other private goods at zero.
For any witness for type \(t\), supply feasibility gives
\(\displaystyle y_{t,c}\leq\frac1{\mu_t},\qquad y_{t,p_t}=0.\)
Hence
\(\displaystyle v_t^\top z\leq v_t^\top y_t\leq\frac1{\mu_t}.\)
Equality is feasible: take \(z_{p_t}=1/\mu_t\), take \(y_{t,c}=1/\mu_t\), and set all other coordinates to zero. Every other type assigns value zero to \(z\). Therefore
\(\displaystyle E_t^\infty=\frac1{\mu_t}.\)
Because each private good has zero supply, every feasible allocation has \(a_{t,p_t}=0\). Thus type \(t\)'s utility is \(a_{t,c}\). If an allocation achieves factor \(\theta\), then
\(\displaystyle a_{t,c}\geq\frac{\theta}{\mu_t}.\)
Multiplying by \(\mu_t\), summing over all types, and using the common-good supply gives
\(\displaystyle 1\geq\sum_t\mu_ta_{t,c}\geq\sum_t\theta=\tau\theta.\)
Thus \(\theta^*\leq1/\tau\). Equality is achieved by
\(\displaystyle a_{t,c}=\frac1{\tau\mu_t}.\)
Consequently,
\(\displaystyle \theta^*=\frac1\tau,\qquad \frac1{\theta^*}=\tau.\)
Together with the universal bound, this proves exact worst-case sharpness for every mass vector \(\mu\).
If zero supplies are disallowed, set \(b_{p_t}=\varepsilon>0\). The same argument gives
\(\displaystyle E_t^\infty=\frac{1+\varepsilon}{\mu_t}\)
and
\(\displaystyle \theta^*=\frac{1/\tau+\varepsilon}{1+\varepsilon}.\)
Therefore
\(\displaystyle \frac1{\theta^*}=\frac{\tau(1+\varepsilon)}{1+\tau\varepsilon}.\)
Taking rational \(\varepsilon\) arbitrarily small makes this tend to \(\tau\). For example, \(\varepsilon=\tau^{-2}\) gives
\(\displaystyle \frac1{\theta^*}=\frac{\tau^2+1}{\tau+1}\geq\frac{\tau}{2}.\)
Hence the sharp asymptotic dependence remains \(\Theta(\tau)\) even with strictly positive supplies.
Although it is not extremal, the projective-plane construction does yield \(\Omega(\sqrt{\tau})\) in this formulation.
Let \(q\) be a prime power and let
\(\displaystyle n=q^2+q+1=\tau.\)
Take the types to be the lines of a projective plane of order \(q\). There are \(n\) projective-point goods and \(q^2=n-q-1\) universal goods. Every good has supply \(1/n\), and every type has mass \(1/n\). A line-type values every universal good and precisely the \(q+1\) points on its line.
Fix a line \(i\). Let \(z\) contain one unit of each point on \(i\). Then type \(i\) values \(z\) at \(q+1\), while every other line \(j\) values \(z\) at one because two distinct lines meet in exactly one point.
Set \(y_i=z\). For \(j\neq i\), give \(y_j\) an amount \(1/(n-1)\) of every universal good and of every point on \(j\) except the intersection of \(i\) and \(j\). There are
\(\displaystyle q^2+q=n-1\)
such valued goods, so \(v_j^\top y_j=1=v_j^\top z\).
For a point on \(i\), the total unweighted allocation among the \(y_j\)'s is one. For a point outside \(i\), it is \((q+1)/(n-1)\leq1\). For a universal good, it is one. Since every mass equals \(1/n\), the witness is supply-feasible. Thus
\(\displaystyle E_i^\infty\geq q+1\)
for every \(i\).
There are
\(\displaystyle m=n+q^2=2n-q-1\)
goods. For any feasible allocation, \(\sum_i a_{i,k}\leq1\) for every good, and binary valuations imply
\(\displaystyle \sum_i v_i^\top a_i\leq m.\)
If the allocation achieves factor \(\theta\), then
\(\displaystyle \sum_i v_i^\top a_i\geq n\theta(q+1).\)
Therefore
\(\displaystyle \frac1{\theta^*}\geq\frac{n(q+1)}{2n-q-1}>\frac{q+1}{2}>\frac{\sqrt n}{2}.\)
Hence this infinite family gives \(\Omega(\sqrt{\tau})\) directly. It is an adaptation of the incidence construction in [Bai, Munagala, Shen, and Zhang](https://arxiv.org/pdf/2411.10434), but the direct verification above is necessary because their finite-agent benchmark is not identical to \(E_t^\infty\).
For the literal definition:
⟨structured verdict parsed — rendered above⟩
The prover’s mathematical argument is correct under its explicitly stated interpretation that \(a\) and \(\theta\) are optimized jointly. It establishes polynomial-time solvability, the exact worst-case bound \(1/\theta^*=\tau\) when zero supplies are allowed, supremum \(\tau\) under strictly positive supplies, and a valid projective-plane family with \(\Omega(\sqrt{\tau})\) growth.
The only issue is a quantifier ambiguity inherited from the task but not fully resolved in the write-up: the displayed definition can be read as fixing \(a\), whereas the prover optimizes over \(a\). The intended simultaneous-allocation interpretation is strongly suggested by the target, but it should be stated in the formal definition.
The LP formulation of \(E_t^\infty\) is correctly counted and has rational input.
The boundedness argument is valid. From supply feasibility and nonnegativity,
\[ \mu_t y_{t,k}\leq \sum_s\mu_s y_{s,k}\leq b_k, \]
so \(y_{t,k}\leq b_k/\mu_t\). The constraint indexed by \(r=t\) then gives
\[ v_t^\top z\leq v_t^\top y_t\leq \frac{v_t^\top b}{\mu_t}. \]
The lower-bound witness \(z=b\), \(y_s=b\) is feasible because \(\sum_s\mu_s=1\), and it proves \(E_t^\infty\geq v_t^\top b\). Consequently, assuming the usual nonnegativity of the supply vector, the equivalence \(E_t^\infty=0\) if and only if \(v_t^\top b=0\) is correct.
Once the benchmarks are computed, the displayed joint LP in \(a\) and \(\theta\) exactly expresses the intended simultaneous optimization. The appeal to polynomial-time exact rational linear programming is appropriate, and the benchmark values have polynomial encoding length by standard rational LP bit-complexity bounds.
If every benchmark vanishes, the conclusion \(\theta^*=+\infty\) is correct under the literal absence of a restriction such as \(0\leq\theta\leq1\).
The averaging argument is correct. Each selected benchmark LP has an attained optimum because it is feasible and has finite optimal value.
Averaging the \(r\) witness allocations preserves supply feasibility. For each active type \(s\), its own witness contributes at least \(E_s^\infty/r\), while every other contribution is nonnegative. Hence
\[ \theta^*\geq \frac1r \]
and therefore \(1/\theta^*\leq r\leq\tau\). No assumption on a lower bound for the masses is used.
For the zero-private-supply construction, the benchmark calculation is valid:
Thus \(E_t^\infty=1/\mu_t\).
Zero supply and nonnegativity force every allocation on every private good to vanish. Summing the resulting common-good requirements yields \(\tau\theta\leq1\). The proposed allocation \(a_{t,c}=1/(\tau\mu_t)\) is feasible and attains equality. Therefore \(\theta^*=1/\tau\).
This proves exact sharpness for every fixed positive mass vector.
The formula
\[ E_t^\infty=\frac{1+\varepsilon}{\mu_t} \]
is correct: type \(t\)’s allocation can use at most \(1/\mu_t\) units of the common good and \(\varepsilon/\mu_t\) units of its private good, and the analogous witness attains their sum.
The asserted simultaneous optimum
\[ \theta^*=\frac{1/\tau+\varepsilon}{1+\varepsilon} \]
is also correct. The common good contributes total mass-weighted utility at most \(1\), while the \(\tau\) relevant private goods contribute at most \(\tau\varepsilon\). The stated allocation uses each private supply and divides the common supply equally in mass-weighted terms, attaining the bound.
The reciprocal and its limit as \(\varepsilon\to0\) are algebraically correct.
The witness is supply-feasible:
Because masses and supplies both equal \(1/n\), these unweighted load bounds are exactly the supply constraints.
Each nondistinguished line receives \(1/(n-1)\) on \(q^2+q=n-1\) valued goods, giving utility \(1\), equal to its value for \(z\). The distinguished type obtains \(q+1\). Hence \(E_i^\infty\geq q+1\).
For every good, feasibility gives \(\sum_i a_{i,k}\leq1\). Since valuations are binary,
\[ \sum_i v_i^\top a_i\leq m. \]
Combining this with the benchmark lower bounds yields
\[ \frac1{\theta^*}\geq \frac{n(q+1)}{2n-q-1}>\frac{q+1}{2}>\frac{\sqrt n}{2}. \]
All counts and inequalities are correct, so the claimed \(\Omega(\sqrt{\tau})\) family is established.
The task’s wording says “For a type-level allocation \(a\), let \(\theta^*\) be the maximum \(\theta\),” which can grammatically mean that \(a\) is fixed. The prover instead assumes that \(a\) and \(\theta\) are optimized jointly. Under a fixed-\(a\) interpretation, the displayed LP and the worst-case claims concern a different quantity. The minimum required clarification is an explicit quantifier stating that \(\theta^*\) is the maximum over both feasible allocations \(a\) and factors \(\theta\).
⟨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.