Answer: —
Theorem 10 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateWith general utilities and 2 agents, the BALANCED LIKE mechanism is not c-competitive from an egalitarian or utilitarian perspective for any constant c.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational population distribution \(\mu\), utility and like data \(u_t(j), b_t(j)\), and an ordered stream of item blocks \((j_r,\lambda_r)\) with \(\lambda_r\) indivisible items per unit population, evolve fluid BALANCED LIKE using load distributions \(\nu_t(\ell)\), compute its egalitarian or utilitarian welfare and the offline optimum, and determine the exact ratio or whether it is bounded by a supplied constant \(c\).
An instance has a finite type set \(T\), rational masses \(\mu_t>0\) with \(\sum_t\mu_t=1\), sincere like indicators \(b_t(j)\in\{0,1\}\), rational utilities \(u_t(j)\geq0\), and ordered blocks \((j_r,\lambda_r)\) with rational copy densities \(\lambda_r\geq0\).
Let \(\nu_t(\ell)\) be the mass of type \(t\) currently holding \(\ell\) indivisible copies, initially \(\nu_t(0)=\mu_t\). In block \(r\), repeatedly allocate infinitesimal copy mass to the lowest-load persons with \(b_t(j_r)=1\), uniformly over that pool, moving each selected mass from load \(\ell\) to \(\ell+1\), until \(\lambda_r\) copies per unit population are allocated; discard a block if its like pool is empty.
Let \(V_t\) be the resulting expected utility mass of type \(t\). Define \(W_{\mathrm{util}}=\sum_tV_t\) and \(W_{\mathrm{egal}}=\min_t V_t/\mu_t\). The offline optimum \(W^*_{\star}\) maximizes the same objective over fractional allocations of every block's copy mass, for \(\star\in\{\mathrm{util},\mathrm{egal}\}\).
Define FLUID-BALANCED-LIKE-RATIO to ask, given rational \(c\) and an instance with positive mechanism welfare, whether \(W^*_{\star}/W_{\star}\leq c\).
Is FLUID-BALANCED-LIKE-RATIO solvable in polynomial time, or is it NP-hard, for utilitarian welfare or for egalitarian welfare?
For finite individual-agent instances with general utilities, BALANCED LIKE has no constant competitive ratio for either welfare objective, even with \(2\) agents.
For fixed-order discrete instances, exact-outcome computation for BALANCED LIKE is intractable in general but tractable with \(2\) agents; neither result treats type masses or copy densities.
I do not settle the classification for an unrestricted number of types. I prove the following partial results for both welfare objectives:
The distinction between polynomially many arithmetic operations and polynomial bit complexity is essential here.
Write \(n=|T|\), and let \(R\) be the number of blocks. Define the current load mass of type \(t\) by
\(m_t=\sum_{\ell\geq 0}\ell\,\nu_t(\ell).\)
Thus \(m_t/\mu_t\) is its average load. Load mass and utility mass are different quantities.
After every block, the load distribution of each type is supported on at most two consecutive integers.
Proof. Initially, every type is supported at load zero.
Consider a block and assume the assertion holds before it. During this block, the mechanism completely processes successive lowest occupied load levels of the liking population, until it stops, possibly partway through one level, say \(k\).
At this stopping point:
A liking type initially supported on two consecutive levels therefore has three possibilities. Its support is entirely at or below \(k\), in which case its final support is contained in \(\{k,k+1\}\); its support is contained in \(\{k,k+1\}\), in which case that remains true; or its support is entirely above \(k\), in which case it is unchanged. Nonliking types are unchanged.
This proves the induction. \(\square\)
In particular, \(m_t\) determines the entire distribution. If
\(h_t=\lfloor m_t/\mu_t\rfloor,\qquad d_t=m_t-h_t\mu_t,\)
then
\(\nu_t(h_t)=\mu_t-d_t,\qquad \nu_t(h_t+1)=d_t.\)
When \(d_t=0\), the distribution is concentrated at \(h_t\).
Consider a block with density \(\lambda>0\) and nonempty liking set \(S\). Blocks with zero density or empty liking set leave the state unchanged.
For a nonnegative integer \(k\), define
\(F(k)=\sum_{t\in S}(k\mu_t-m_t)_+,\)
where \(a_+=\max\{a,0\}\).
The copy mass needed to raise every liking person below load \(k\) to load \(k\) is exactly \(F(k)\).
Proof. For a type supported on consecutive integers, there are two cases.
If \(m_t\leq k\mu_t\), all its occupied loads are at most \(k\), so the required copy mass is \(k\mu_t-m_t\).
If \(m_t>k\mu_t\), its lowest occupied load is at least \(k\), so the required mass is zero.
Summing gives the assertion. \(\square\)
Choose the largest nonnegative integer \(k\) satisfying \(F(k)\leq\lambda\). This integer exists because \(F(0)=0\), and is finite because \(S\) is nonempty. It satisfies
\(F(k)\leq\lambda<F(k+1).\)
Define
\(q_t=\min\{\mu_t,\max\{0,(k+1)\mu_t-m_t\}\}\quad(t\in S),\)
\(M=\sum_{t\in S}q_t,\qquad \alpha=\dfrac{\lambda-F(k)}{M}.\)
After completing all levels below \(k\), the mass of type \(t\) at load \(k\) is exactly \(q_t\). Moreover,
\(M=F(k+1)-F(k)>0,\qquad 0\leq\alpha<1.\)
Uniform allocation within the load-\(k\) pool advances an \(\alpha\) fraction of every type’s mass in that pool. Indeed, while this pool is being depleted, each type loses mass in proportion to its current pool mass; hence all type proportions remain constant.
Consequently, the exact update is
\(m'_t=m_t+(k\mu_t-m_t)_++\alpha q_t\quad(t\in S),\)
and \(m'_t=m_t\) for \(t\notin S\).
Because each allocated copy increases load by one, its utility contribution is also determined:
\(V'_t=V_t+u_t(j_r)(m'_t-m_t).\)
These formulas simulate the specified fluid mechanism exactly.
Let \(C=\sum_t m_t\) before the block, and let \(\mu_{\min}=\min_t\mu_t\). For every nonnegative integer \(K\),
\(F(K)\geq K\sum_{t\in S}\mu_t-\sum_{t\in S}m_t\geq K\mu_{\min}-C.\)
Therefore the integer
\(U=\left\lfloor\dfrac{C+\lambda}{\mu_{\min}}\right\rfloor+2\)
satisfies \(F(U)>\lambda\). Binary search between zero and \(U\) finds \(k\).
Crucially, \(C\) is simply the sum of densities of preceding blocks with nonempty liking sets. Thus \(C\), \(U\), and every tested integer have polynomial binary encoding length in the original input length \(L\).
Each evaluation of \(F\) uses \(O(n)\) arithmetic operations and comparisons. The entire simulation therefore uses polynomially many exact rational arithmetic operations and comparisons. This statement alone does not bound the lengths of the rationals produced.
Under the stated definition, the offline allocation is unrestricted by the like indicators. Let \(x_{tr}\) be the mass of copies from block \(r\) assigned to type \(t\). Its constraints are
\(x_{tr}\geq0,\qquad \sum_t x_{tr}=\lambda_r.\)
There is no capacity constraint on a type’s total number of copies.
For utilitarian welfare, blocks optimize independently, giving
\(W^*_{\mathrm{util}}=\sum_r\lambda_r\max_{t\in T}u_t(j_r).\)
For egalitarian welfare, the optimum is the value of the rational linear program
\(\text{maximize }z,\)
subject to
\(x_{tr}\geq0,\qquad \sum_t x_{tr}=\lambda_r,\)
\(\sum_r u_t(j_r)x_{tr}\geq\mu_t z\quad(t\in T),\qquad z\geq0.\)
These constraints express exactly the requirement that every type have average utility at least \(z\).
This linear program has polynomial size and rational input coefficients. It is feasible by assigning every block arbitrarily and taking \(z=0\). Its objective is bounded: for any fixed type \(t\),
\(z\leq \dfrac{\sum_r u_t(j_r)\lambda_r}{\mu_t}.\)
Thus exact polynomial-time rational linear programming applies, and the optimum has polynomial encoding length. The exact-solvability theorem used here is standard; see also [Dadush, Natura, and Végh’s treatment of exact linear programming](https://arxiv.org/abs/2009.04942).
Since mechanism welfare is promised positive, the target comparison is equivalent to
\(W^*_\star\leq cW_\star.\)
It remains to compute or compare the mechanism welfare.
For instances with at most two types, both welfare-ratio problems are solvable in polynomial time in the binary input length.
Proof. One type is immediate: every nonempty liking block assigns its entire density to that type.
Now suppose there are two types, of masses
\(\mu_1=p,\qquad \mu_2=1-p,\qquad 0<p<1.\)
Before a block, write
\(m_1=x,\qquad m_2=y=C-x.\)
As established above, \(C\) is known directly from the input prefix and has polynomial encoding length.
A block liked by only type one sends \(x\) to \(x+\lambda\). A block liked by only type two leaves \(x\) unchanged. Empty liking sets have no effect.
Consider a block liked by both types, with \(\lambda>0\), and compute its stopping level \(k\) as in Section 2. We show that every possible update is fractional-linear in \(x\), with coefficients of polynomial encoding length.
Define \(q_1,q_2\) by the block formula.
If \(q_2=0\), then \(y\geq(k+1)(1-p)\). Type two has no population below or at the final processed level, and receives no copies during this block. Hence
\(x'=x+\lambda.\)
Similarly, \(q_1=0\) implies \(x'=x\).
Both cannot vanish because \(q_1+q_2>0\).
For the remaining cases, both final-pool masses are positive.
Here
\(x\leq kp,\qquad y\leq k(1-p).\)
Then
\(F(k)=k-C,\qquad q_1=p,\qquad q_2=1-p.\)
The block formula gives
\(x'=p(k+\lambda-F(k))=p(C+\lambda).\)
Here
\(kp<x<(k+1)p,\qquad k(1-p)<y<(k+1)(1-p).\)
Therefore
\(F(k)=0,\qquad q_1=(k+1)p-x,\qquad q_1+q_2=k+1-C.\)
It follows that
\(x'=x+\lambda\dfrac{(k+1)p-x}{k+1-C}.\)
This is affine in \(x\), since \(C\) is an input-prefix quantity.
Suppose first that
\(x\leq kp,\qquad k(1-p)<y<(k+1)(1-p).\)
Then
\(F(k)=kp-x,\qquad q_1=p,\qquad q_2=(k+1)(1-p)-C+x.\)
Consequently,
\(x'=p\left(k+\dfrac{\lambda-kp+x}{p+(k+1)(1-p)-C+x}\right).\)
This is fractional-linear in \(x\). Its denominator is \(q_1+q_2>0\).
If type two is the lower type, exchange the type labels, apply the same formula to \(y=C-x\), and recover
\(x'=C+\lambda-y'.\)
Substitution and subtraction preserve fractional-linearity.
These cases are exhaustive: when \(q_t>0\), either \(m_t\leq k\mu_t\) or \(k\mu_t<m_t<(k+1)\mu_t\).
Every update therefore has the form
\(x'=\dfrac{ax+b}{dx+e},\)
with a nonzero denominator at the current state. The rational coefficients depend only on \(p,C,\lambda,k\), so their encoding lengths are bounded by a polynomial in \(L\).
Clear the four coefficient denominators simultaneously. This gives integer coefficients \(a,b,d,e\), still of polynomial bit length.
If \(x=N/D\), we may represent the updated value by
\(N'=aN+bD,\qquad D'=dN+eD.\)
If \(N,D\) have at most \(B\) bits and the coefficients have at most \(H\) bits, then \(N',D'\) have at most \(B+H+O(1)\) bits. Reducing the fraction cannot increase these bounds.
Thus each block increases the necessary bit length by at most a polynomial in \(L\). There are at most \(L\) explicitly listed blocks, so every state value has polynomial bit length.
All binary searches and case comparisons consequently take polynomial time. Utility masses are sums of polynomially many products of polynomial-bit rationals, and therefore also have polynomial encoding length.
Finally, compute the appropriate offline optimum using Section 3 and compare it with \(cW_\star\). This proves the theorem. \(\square\)
Define \(\mathrm{PosSLP}\) as follows: the input is a directed acyclic arithmetic circuit with constants zero and one and operations addition, subtraction, and multiplication; the question is whether its integer output is strictly positive.
For an arbitrary number of types, both welfare-ratio problems belong to \(\mathrm{P}^{\mathrm{PosSLP}}\).
Proof. Run the simulation of Section 2, representing each rational by two integer circuits for its numerator and positive denominator.
Every rational arithmetic operation adds only constantly many integer-circuit gates. For example,
\(\dfrac{A}{B}+\dfrac{D}{E}=\dfrac{AE+BD}{BE}.\)
All divisions needed in the state update are by positive quantities, so positive denominators can be maintained.
A comparison is an integer-circuit sign question:
\(\dfrac{A}{B}>\dfrac{D}{E}\quad\Longleftrightarrow\quad AE-BD>0,\qquad B,E>0.\)
Thus \(\mathrm{PosSLP}\) queries implement every comparison, including those used for positive parts, minima, and binary search. Non-strict comparisons follow by negating the corresponding strict comparison.
Input integers of polynomial bit length can be constructed with polynomially many gates using binary expansion. Previously constructed circuit nodes are shared, rather than copied.
The simulation uses polynomially many arithmetic operations and comparisons, and all binary-search integers have polynomial bit length. Hence its circuits and oracle queries have polynomial size.
Accumulate utility masses by the same circuit operations. For egalitarian welfare, find the minimum of \(V_t/\mu_t\) using circuit comparisons. Compute the offline optimum in polynomial time as in Section 3, and perform the final comparison \(W^*_\star\leq cW_\star\) with the oracle. \(\square\)
The compact state representation removes the apparent difficulty caused by potentially enormous load levels. It does not establish polynomial bit complexity for arbitrary numbers of types.
For more than two types, the final-pool denominator
\(M=\sum_{t\in S}\min\{\mu_t,\max\{0,(k+1)\mu_t-m_t\}\}\)
can depend on several evolving state coordinates. The two-type fractional-linear argument does not supply a bit-length bound in that setting.
Accordingly, the unrestricted classification remains unsettled here for both objectives. A complete resolution would require a polynomial-time comparison method exploiting additional structure, or a valid hardness reduction. Neither follows from the discrete BALANCED LIKE results given in the question.
⟨structured verdict parsed — rendered above⟩
The correct adjudication is partial. The prover explicitly leaves the unrestricted classification open. Its state representation, exact update formulas, two-type polynomial-time algorithm, and general \(\mathrm{P}^{\mathrm{PosSLP}}\) upper bound are sound. None establishes polynomial-time solvability or NP-hardness for unrestricted type sets.
I found no false central assertion or substantive gap in the partial results.
Initially, each type occupies only load zero. Within a block, allocation exhausts the lowest occupied liking load before proceeding upward. Consequently, at a stopping level \(k\), initially lower liking persons occupy \(k\) or \(k+1\), while initially higher persons remain unchanged.
Given the inductive assumption of consecutive support, the listed cases cover every liking type. Nonliking types are unchanged. Exact completion of a level is included by allowing zero progress at the next occupied level; zero-density and empty-pool blocks preserve the invariant directly.
The reconstruction from \(m_t\) is correct: because each type has mass \(\mu_t>0\), consecutive support determines its distribution uniquely from its average load. The formulas also handle \(d_t=0\).
The compact state concerns load distributions. Computing welfare additionally requires the utility accumulators \(V_t\), which the subsequent algorithm correctly maintains.
Lemma 2 correctly uses both the consecutive-support invariant and the integrality of \(k\). If \(m_t\leq k\mu_t\), no occupied load exceeds \(k\); if \(m_t>k\mu_t\), no occupied load is below \(k\). Thus the positive-part expression gives the required leveling cost exactly.
The function \(F\) is nondecreasing and eventually unbounded for a nonempty liking set. Therefore the largest qualifying integer \(k\) exists and satisfies the stated strict upper inequality.
The expression for \(q_t\) correctly covers all three possibilities: the entire type has been raised to level \(k\), only its original lower-load portion occupies \(k\), or none of the type occupies \(k\). The identity \(M=F(k+1)-F(k)\) holds in each case. Maximality of \(k\) consequently gives \(M>0\) and \(0\leq\alpha<1\).
Uniform depletion preserves the proportions of the types in the current lowest-load pool. Hence the partial-level term \(\alpha q_t\), the update for \(m'_t\), and the utility increment \(u_t(j_r)(m'_t-m_t)\) are correct. Previously accumulated utility does not need to be tracked by load, since subsequent allocation depends only on loads and likes.
Both inequalities bounding \(F(K)\) are valid: the liking mass is at least \(\mu_{\min}\), and its load mass is at most \(C\). The stated \(U\) therefore satisfies \(F(U)>\lambda\).
The identification of \(C\) with the total density of previously allocated, nonempty-pool blocks is correct. No capacity constraint prevents those blocks from being completely allocated.
Sums of explicitly supplied rational densities have polynomial encoding length. Together with the rational positive masses, this justifies the polynomial bit length of \(U\) and the polynomial number of binary-search iterations.
The prover correctly limits this conclusion to polynomially many arithmetic operations and comparisons; it does not silently assume that all evolving rational values have polynomial bit length.
Under the task’s definition, offline allocations have no stated like restriction. The prover’s unrestricted offline feasible set therefore matches the supplied task.
The utilitarian formula is correct because blocks have independent allocation constraints and utilities are linear.
The egalitarian linear program correctly expresses the type-average utility objective. It has polynomially many variables and constraints, rational coefficients, a feasible point with \(z=0\), and a finite objective bound because \(\mu_t>0\). These are the needed hypotheses for exact polynomial-time rational linear programming. The invoked standard result is applicable; the linked paper indeed concerns exact LP algorithms and their computational bounds. [Dadush, Natura, and Végh](https://arxiv.org/abs/2009.04942)
The positive-mechanism-welfare promise justifies multiplying the ratio inequality by \(W_\star\). This remains valid for every rational \(c\), including negative values.
The one-type case and the empty or singleton liking-set cases are correct.
For a block liked by both types:
These cases exhaust all possibilities, including equality at the lower boundary. Equality at the upper boundary is covered by a vanishing pool mass.
The bit-length argument is valid. Each branch’s coefficients depend only on polynomial-bit input quantities and the polynomial-bit stopping level. Clearing a fixed number of coefficient denominators preserves polynomial coefficient length. Updating a numerator-denominator pair by the displayed integer linear expressions increases its bit length additively, rather than multiplicatively.
Polynomially many blocks therefore preserve polynomial state bit length. The intermediate update calculations, utility accumulation, and final welfare comparisons also have polynomial bit complexity. No unproved unrestricted-type bit bound is used.
The definition of \(\mathrm{PosSLP}\) is precise. Integer-circuit numerator and positive-denominator representations support the required rational operations, and every state-dependent division has a strictly positive divisor.
Cross multiplication correctly reduces rational comparison to circuit positivity. Adaptive oracle answers suffice to choose the branches implementing positive parts, minima, and binary search.
Circuit sharing is essential and is explicitly specified. Since the simulation uses polynomially many operations and comparisons, the shared circuits and the explicitly submitted oracle queries remain polynomial in size.
Utility accumulation, the egalitarian minimum, and comparison against the polynomial-bit offline optimum are therefore implementable in \(\mathrm{P}^{\mathrm{PosSLP}}\).
Major issue relative to the assigned target: neither unrestricted welfare-ratio problem is classified as polynomial-time solvable or NP-hard.
This is an acknowledged limitation, not a contradiction in the proof. The two-type argument establishes only a restricted case. The oracle upper bound supplies neither an ordinary polynomial-time algorithm nor a hardness reduction. The discussion of several evolving coordinates identifies where the existing bit-length argument stops; it does not prove that polynomial bit complexity is impossible.
Minimum actionable feedback: no substantive repair is needed for the partial results. To resolve the assigned task, provide the missing unrestricted classification for each objective, with a complete algorithm and bit-complexity justification or a valid hardness reduction. Additional explanation of the existing formulas alone would not settle that target.
⟨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.