Answer: Polynomial-time solvable for \(\tau=2\); an exact rational maximizing allocation can be computed.
Theorem 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is a combinatorial strongly polynomial algorithm for solving ADNB2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two types with rational masses \(\mu_i>0\), \(\sum_i\mu_i=1\), linear per-person utilities \(u_{ij}\), disagreement utilities \(c_i\), and one unit of each good per unit of population, find a feasible per-type allocation \(q_{ij}\) maximizing \(\sum_{i=1}^2\mu_i\log(\sum_j u_{ij}q_{ij}-c_i)\), subject to \(\sum_i\mu_i q_{ij}\le1\).
A society is given by its support: the list of the \(\tau=2\) types with positive binary rational masses \(\mu_i\), where \(\mu_1+\mu_2=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) divisible goods, each with total supply one. Inputs are binary rational utilities \(u_{ij}\ge0\) and disagreement utilities \(c_i\ge0\); every type values some good positively, and every good is valued positively by some type. Let \(L\) be the total input bit length.
An allocation specifies a common per-person bundle \(q_i\) for each type, with \(q_{ij}\ge0\), \(\sum_{i=1}^{2}\mu_iq_{ij}\le1\) for every good, and per-person utility \(v_i(q)=\sum_{j=1}^{m}u_{ij}q_{ij}\).
Restrict to instances admitting an allocation with \(v_i(q)>c_i\) for both types. Compute any exact maximizing allocation for \(\sum_{i=1}^{2}\mu_i\log(v_i(q)-c_i)\), over allocations with strictly positive gains; no tie-breaking among maximizing allocations is prescribed.
Is this exact two-type allocation problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For two discrete players, nonsymmetric linear Arrow–Debreu Nash bargaining with positive integer clouts admits a combinatorial strongly polynomial algorithm; more generally, two-player bargaining with rational linear constraints admits an exact rational solution computable in polynomial time. [Vazirani](https://ics.uci.edu/~vazirani/LNB2.pdf)
No separate result for exactly the population-mass formulation above was identified in the literature search.
Theorem. On the promised instances with \(\tau=2\), an exact rational maximizing allocation can be computed in time polynomial in \(m\) and \(L\).
We prove this directly by enumerating at most \(2m+1\) rational candidates and checking their optimality using rational arithmetic.
Define aggregate allocations, aggregate utilities, and aggregate disagreement utilities by
\(x_{ij}=\mu_iq_{ij},\qquad U_i(x)=\sum_{j=1}^{m}u_{ij}x_{ij},\qquad d_i=\mu_ic_i.\)
Because each \(\mu_i>0\), this is an invertible transformation. The allocation constraints become
\(x_{ij}\ge0,\qquad x_{1j}+x_{2j}\le1\quad\text{for every }j.\)
Moreover,
\(v_i(q)-c_i=\dfrac{U_i(x)-d_i}{\mu_i}.\)
Consequently, the original objective equals
\(\sum_{i=1}^{2}\mu_i\log(U_i(x)-d_i)-\sum_{i=1}^{2}\mu_i\log\mu_i.\)
The second term is constant. Thus it suffices to maximize
\(F(x)=\mu_1\log(U_1(x)-d_1)+\mu_2\log(U_2(x)-d_2)\)
over aggregate allocations with \(U_i(x)>d_i\). The promise guarantees that such an allocation exists.
Let \(X\) be the aggregate allocation polytope, and define
\(K=\{x\in X:U_1(x)\ge d_1,\ U_2(x)\ge d_2\}.\)
The set \(X\) is compact: every coordinate lies in \([0,1]\), and its defining constraints are closed. Hence \(K\) is compact.
On \(K\), the function
\(H(x)=(U_1(x)-d_1)^{\mu_1}(U_2(x)-d_2)^{\mu_2}\)
is continuous, where a zero gain contributes a zero factor. By the promise, \(H\) is positive somewhere. Therefore its maximum exists and is positive. Every maximizer consequently has both gains strictly positive. Since \(F=\log H\) there, a maximizer of \(F\) exists.
For any allocation \(x\) with positive gains, define
\(p_i=\dfrac{\mu_i}{U_i(x)-d_i}>0,\qquad M_j=\max\{p_1u_{1j},p_2u_{2j}\}.\)
The following conditions certify optimality:
We prove both necessity and sufficiency.
Necessity. Let \(x^*\) maximize \(F\), and compute \(p_i\) at \(x^*\). For any \(y\in X\), the allocation
\(x(s)=(1-s)x^*+sy\)
has positive gains for all sufficiently small nonnegative \(s\). Optimality therefore implies
\(\left.\dfrac{d}{ds}F(x(s))\right|_{s=0} =\sum_{i=1}^{2}p_i\bigl(U_i(y)-U_i(x^*)\bigr)\le0.\)
Thus \(x^*\) maximizes the linear functional
\(\sum_{j=1}^{m}\sum_{i=1}^{2}p_iu_{ij}x_{ij}\)
over \(X\). This maximization separates across goods. Every good is positively valued by some type, so \(M_j>0\). For each good, a linear maximizer must use its entire supply and assign positive quantities only to types attaining \(M_j\). These are precisely the certificate conditions.
Sufficiency. Suppose \(x\) satisfies the certificate. For every \(y\in X\),
\(\sum_{i=1}^{2}p_iU_i(y) \le\sum_{j=1}^{m}M_j =\sum_{i=1}^{2}p_iU_i(x).\)
If \(y\) also has positive gains, the tangent inequality for the logarithm gives
\(F(y)-F(x) \le\sum_{i=1}^{2}p_i\bigl(U_i(y)-U_i(x)\bigr) \le0.\)
Therefore \(x\) is a global maximizer.
All quantities in this certificate are rational when \(x\) is rational. Checking it requires no logarithm evaluations.
Partition the goods into
\(I_1=\{j:u_{1j}>0,\ u_{2j}=0\},\qquad I_2=\{j:u_{1j}=0,\ u_{2j}>0\},\)
and
\(C=\{j:u_{1j}>0,\ u_{2j}>0\}.\)
These sets partition all goods by the assumption that every good is positively valued by some type.
Write \(C=\{j_1,\ldots,j_k\}\), ordered so that
\(\dfrac{u_{1j_1}}{u_{2j_1}}\ge\cdots\ge\dfrac{u_{1j_k}}{u_{2j_k}}.\)
Fix any order among equal ratios.
Let \(x^*\) be a maximizer and let \(p_i\) be its certificate coefficients. Goods in \(I_i\) go entirely to type \(i\). For a common good, the certificate implies:
The goods with equality form a contiguous block in the sorted order. We can rearrange allocations within this block without changing either utility.
Indeed, let their common ratio be \(r\), and write \(z_j=x^*_{1j}\). Their total allocation to type \(1\), measured using type \(2\)'s utility coefficients, is
\(T=\sum_{\text{block }j}u_{2j}z_j.\)
Their contributions to the two utilities are respectively
\(rT\qquad\text{and}\qquad\sum_{\text{block }j}u_{2j}-T.\)
Assign the block to type \(1\) in its fixed order until the quantity \(T\) is reached: fill successive goods completely, split the next good if necessary, and assign the remainder to type \(2\). Since every \(u_{2j}\) in the block is positive and
\(0\le T\le\sum_{\text{block }j}u_{2j},\)
this construction is possible and preserves both utilities.
Hence some maximizer has a prefix of common goods assigned to type \(1\), a suffix assigned to type \(2\), and at most one shared good.
Throughout, assign goods in \(I_i\) entirely to type \(i\).
For every \(\ell\in\{0,\ldots,k\}\), include the allocation assigning the first \(\ell\) common goods to type \(1\) and all remaining common goods to type \(2\).
There are \(k+1\) such candidates.
For each \(h\in\{1,\ldots,k\}\), consider allocations that assign:
Set
\(a=u_{1j_h}>0,\qquad b=u_{2j_h}>0,\)
\(P_h=\sum_{j\in I_1}u_{1j}+\sum_{\ell<h}u_{1j_\ell}-d_1,\)
and
\(Q_h=\sum_{j\in I_2}u_{2j}+\sum_{\ell\ge h}u_{2j_\ell}-d_2.\)
The gains along this segment are
\(U_1-d_1=P_h+at,\qquad U_2-d_2=Q_h-bt.\)
Where both gains are positive, the derivative of the objective is
\(\dfrac{dF}{dt} =\dfrac{\mu_1a}{P_h+at}-\dfrac{\mu_2b}{Q_h-bt}.\)
An optimum with \(0<t<1\) must have zero derivative, because sufficiently small changes in either direction remain feasible and preserve positive gains. Clearing the positive denominators gives
\(\mu_1aQ_h-\mu_2bP_h-ab(\mu_1+\mu_2)t=0.\)
Using \(\mu_1+\mu_2=1\), the only possible interior optimum is
\(t_h=\dfrac{\mu_1Q_h}{b}-\dfrac{\mu_2P_h}{a}.\)
This is rational. Include this candidate whenever \(0<t_h<1\).
There are at most \(k\) additional candidates.
Enumerate these at most \(2k+1\) candidates. Discard any candidate whose gains are not both strictly positive. Check the optimality certificate from Section 2 on every remaining candidate, and return any candidate that passes.
The algorithm always finds one:
Conversely, the certificate proves that every returned candidate is globally maximizing.
When \(k=0\), the enumeration contains just the allocation assigning each exclusive good to its valuing type. The same argument applies.
Finally, return the per-person allocation
\(q_{ij}=\dfrac{x_{ij}}{\mu_i}.\)
Sorting the common goods takes \(O(m\log m)\) rational comparisons. Ratios can be compared by cross multiplication because their denominators are positive.
There are at most \(2m+1\) candidates. Computing utilities and checking the certificate takes \(O(m)\) rational operations per candidate. Thus the algorithm uses
\(O(m^2+m\log m)\)
rational arithmetic operations and comparisons.
All intermediate rational numbers have polynomial encoding length:
For completeness, a sum of input rationals can be represented over the product of their denominators. The bit length of that denominator is at most the sum of their denominator bit lengths; the numerator also has polynomial bit length. The subsequent constant-depth operations preserve a polynomial bound. Standard exact rational arithmetic therefore gives polynomial total running time in \(m\) and \(L\), with \(\tau=2\).
The rescaling also places the problem within two-player nonsymmetric linear bargaining. Its feasible utility set is a compact rational polytope. The transformed disagreement point belongs to that set: starting from a strictly feasible allocation, scale each type's aggregate bundle by \(d_i/U_i\), which lies in \([0,1)\), to obtain utilities exactly \(d_i\).
To obtain positive integer clouts, multiply both rational masses by a common denominator. This only scales the objective by a positive constant, and the clouts have polynomial binary encoding length. Thus the hypotheses of [Vazirani’s Theorem 13](https://ics.uci.edu/~vazirani/LNB2.pdf) are satisfied. The direct algorithm above additionally supplies an explicit allocation and bit-complexity proof for this population formulation.
⟨structured verdict parsed — rendered above⟩
The direct algorithm correctly establishes polynomial-time solvability of the exact two-type allocation problem. Sections 1–5 contain a complete argument. The only issue is a minor omission in the presentation of the supplementary theorem citation in Section 6.
Since both masses are strictly positive, \(x_{ij}=\mu_iq_{ij}\) is invertible and preserves feasibility in both directions. The identities \(U_i(x)=\mu_iv_i(q)\) and \(d_i=\mu_ic_i\) give exactly the stated transformation of gains and objective.
The additive constant does not affect maximizers. Strict positivity of gains and the feasibility promise are preserved. The proof treats the two supported types directly; it does not confuse support size with the number of possible types.
Nonnegativity and the supply constraints imply every coordinate of \(X\) lies in \([0,1]\). Thus \(X\), and its closed subset \(K\), are compact.
Because \(\mu_i>0\), each power function defining \(H\) is continuous on nonnegative gains, including at zero. The promise makes its maximum strictly positive. A point with either gain zero has \(H=0\), so every maximizer of \(H\) has both gains strictly positive. The identity \(F=\log H\) on that domain then establishes existence of a maximizer of the required objective.
For necessity, fix any \(y\in X\). Each gain along the segment from \(x^*\) to \(y\) is affine in the segment parameter and strictly positive at zero. Consequently, it remains positive for a sufficiently small interval, even if \(y\) itself does not have positive gains. The one-sided derivative inequality is therefore justified.
The derivative establishes that \(x^*\) maximizes the stated linear functional over all of \(X\). Its constraints separate by good. Since \(M_j>0\), a maximizer must exhaust each good’s supply and allocate it only to types attaining \(M_j\). This proves both certificate conditions.
For sufficiency, the certificate establishes linear optimality over \(X\). The tangent inequality for the logarithm applies because both allocations being compared have positive gains. With coefficients \(p_i=\mu_i/(U_i(x)-d_i)\), it gives exactly the displayed upper bound on \(F(y)-F(x)\). Thus the certificate proves global optimality without evaluating logarithms.
An exclusive good must go entirely to its valuing type by the certificate. For common goods, comparing their positive utility ratios with \(p_2/p_1\) gives the stated prefix and suffix assignments.
All goods whose ratios equal \(p_2/p_1\) form one contiguous block, including under an arbitrary fixed ordering of equal ratios. Within this block, the two utility contributions depend only on \(T\), as written. Full supply usage is already established, so the type-2 contribution is indeed the total type-2 value of the block minus \(T\).
The proposed rearrangement preserves both utilities and hence the objective and positive gains. Positivity of the block’s type-2 coefficients ensures that reaching \(T\) requires at most one fractional good. The endpoints \(T=0\) and \(T\) equal to the entire block value produce no shared good. If the equality block is empty, the existing allocation already has the required form.
This step asserts existence of a suitable maximizer, which is sufficient because the task prescribes no tie-breaking.
The no-sharing candidates cover all prefix allocations, including the empty and full prefixes.
On a segment with shared good \(j_h\), the definitions of \(P_h\) and \(Q_h\) give the stated gains. In particular, \(Q_h\) includes the full type-2 value of \(j_h\), which is then reduced by \(bt\).
Rechecking the derivative equation gives \(\mu_1aQ_h-\mu_2bP_h-ab(\mu_1+\mu_2)t=0\). Since \(\mu_1+\mu_2=1\) and \(a,b>0\), its unique solution is exactly \(t_h=\mu_1Q_h/b-\mu_2P_h/a\).
A genuinely shared maximizing allocation lies strictly inside its segment. Its gains remain positive under sufficiently small changes in either direction, so zero derivative is necessary. It is therefore included among the enumerated candidates. Fractions equal to zero or one are already covered by no-sharing candidates.
Discarding nonpositive-gain candidates is valid. At least one maximizing candidate survives and passes the necessary certificate; every candidate returned is optimal by sufficiency. The case \(k=0\) is explicitly covered. Division by the positive masses produces an exact rational per-person allocation.
The candidate count is at most \(2k+1\le 2m+1\). Sorting and the stated per-candidate computations give the claimed polynomial number of rational operations.
The bit-length argument also suffices. Products of input denominators have bit length bounded by the sum of their bit lengths. The sums defining \(P_h\) and \(Q_h\), the constant number of subsequent products and divisions, and the candidate utility sums therefore have polynomial encoding length. Certificate divisions have nonzero denominators because gains are checked first; output divisions have nonzero denominators because masses are positive.
Exact comparisons and arithmetic on these rational numbers take polynomial bit time. The argument establishes the requested polynomial-time bound, without needing a strongly polynomial claim.
The transformed utility set is a compact convex rational polytope. The disagreement-point construction is valid: strict feasibility and \(d_i\ge0\) imply \(U_i>d_i\ge0\), so every scaling factor is defined and belongs to \([0,1)\). Scaling each bundle down preserves all supply constraints and gives utilities exactly \(d_i\), including when \(d_i=0\).
Clearing the rational masses’ denominators yields positive integer clouts of polynomial binary encoding length and multiplies the objective by a positive constant.
[Vazirani’s Theorem 13](https://ics.uci.edu/~vazirani/LNB2.pdf) does establish rationality and polynomial-time computation for games in the defined two-player linear bargaining class. Its hypotheses match this formulation.
Minor issue: Section 6 names the theorem and asserts applicability without explicitly stating its operative conclusion and class definition, as required by the verification discipline. This does not affect the independent proof in Sections 1–5.
Minimum clarification: State the relevant part of Theorem 13 and explicitly identify the transformed problem as a feasible two-player nonsymmetric bargaining game with rational linear constraints and positive integer clouts. No additional mathematical argument is needed.
⟨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.