Answer: All optimal grand-coalition dual vectors induce the same per-unit allocation, which is the unique core vector and is exactly computable in time polynomial in \(m,\tau,L\).
Theorem 5.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet (N, D, H, B, P) be a PI-situation with D being an integer matrix. Then, Owen(N, D, H, B, P) = {(o1, ..., on)} where, for each i ∈N, oi = X t∈H1(N) pN t di t + X t∈H2(N) di t pN kh + hN kht + X t∈H3(N) di t pN kb + bN tkb .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of types \(t\), masses \(\mu_t\ge 0\) summing to \(1\), integer demand vectors \(d_t\in\mathbb Z_{\ge 0}^K\), and nonnegative rational cost vectors \(p_t,h_t,b_t\), define any coalition by a mass vector \(0\le\nu\le\mu\). Its demand in period \(s\) is \(D_s(\nu)=\sum_t\nu_t d_{t,s}\); its production, inventory, and backlogging costs in each period are the coordinatewise minima among types with \(\nu_t>0\). Let \(c(\nu)\) be its minimum operation cost under the paper’s flow constraints, with \(c(0)=0\). Compute the per-unit type allocation \(o_t\) induced by optimal dual prices of the grand coalition, and establish that it is independent of the chosen optimal dual solution and satisfies \(\sum_t\mu_t o_t=c(\mu)\) and \(\sum_t\nu_t o_t\le c(\nu)\) for every \(0\le\nu\le\mu\). In particular, the paper’s formula is \(o_t=\sum_s d_{t,s}\lambda_s(\mu)\), where \(\lambda_s(\mu)=\min\{p_s^\mu,\min_{k<s}(p_k^\mu+\sum_{r=k}^{s-1}h_r^\mu),\min_{k>s}(p_k^\mu+\sum_{r=s}^{k-1}b_r^\mu)\}\), with empty minima omitted.
A society is given by its support: the list of \(\tau\ge1\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=K\ge1\) periods. Each type has demand \(d_t\in\mathbb Z_{\ge0}^{K}\) and unit production, inventory, and backlogging costs \(p_t,h_t,b_t\in\mathbb Q_{\ge0}^{K}\). Let \(L\) be the total input bit length.
A coalition is any real mass vector \(0\le\nu\le\mu\), with \(D_s(\nu)=\sum_t\nu_t d_{t,s}\). For \(\nu\ne0\), define \(a_s^\nu=\min_{t:\nu_t>0}a_{t,s}\) for \(a\in\{p,h,b\}\).
Its cost \(c(\nu)\) is the minimum of \(\sum_{s=1}^{K}(p_s^\nu q_s+h_s^\nu I_s+b_s^\nu E_s)\) over nonnegative real production, inventory, and backlog variables, subject to \(I_0=I_K=E_0=E_K=0\) and \(I_s-E_s=I_{s-1}-E_{s-1}+q_s-D_s(\nu)\) for every period; set \(c(0)=0\).
Grand-coalition dual prices are unrestricted real \(y_s\) maximizing \(\sum_sD_s(\mu)y_s\), subject to \(y_s\le p_s^\mu\), \(y_{s+1}-y_s\le h_s^\mu\), and \(y_s-y_{s+1}\le b_s^\mu\), with adjacent-period constraints for \(1\le s<K\). Each optimal dual vector induces \(o_t(y)=\sum_s d_{t,s}y_s\).
Do all optimal grand-coalition dual vectors induce the same per-unit allocation \(o\), satisfying \(\sum_t\mu_to_t=c(\mu)\) and \(\sum_t\nu_to_t\le c(\nu)\) for every real \(0\le\nu\le\mu\)?
Is computing a dual-induced allocation polynomial-time in \(m,\tau,L\), or is it NP-hard?
For finite agents with nonnegative integer demands, the dual-induced allocation is unique, has an explicit polynomial-time formula, and belongs to the core ([source](https://arxiv.org/abs/2402.04328)).
Subsequent work gives axiomatic characterizations for finite-agent production-inventory games ([source](https://grupo.us.es/gpb97/articles/Characterizations%20of%20the%20Owen%20point%20of%20production-inventory%20games.pdf)); no result for this exact mass-coalition formulation was located.
Yes. All optimal grand-coalition dual vectors induce the same per-unit allocation. This allocation satisfies efficiency and every real-coalition core inequality, and it can be computed exactly in time polynomial in \(m,\tau,L\). In fact, the core defined in the question is a singleton.
The finite-agent uniqueness result appears in [Guardiola, Meca, and Puerto, Theorem 5.1](https://arxiv.org/html/2402.04328v1). Below is a direct proof for the stated mass-coalition formulation, including irrational coalition masses.
First fix arbitrary nonnegative costs \(P_s,H_s,B_s\), and let
\( \displaystyle F(P,H,B)=\{y\in\mathbb R^K: y_s\le P_s,\quad y_{s+1}-y_s\le H_s,\quad y_s-y_{s+1}\le B_s\}. \)
The adjacent constraints apply for \(1\le s<K\).
Define the cost of producing in period \(r\) to meet one unit of demand in period \(s\) by
\( \displaystyle C_{rs}= \begin{cases} P_r+\sum_{\ell=r}^{s-1}H_\ell,&r\le s,\\ P_r+\sum_{\ell=s}^{r-1}B_\ell,&r>s. \end{cases} \)
Empty sums equal zero. Set
\( \displaystyle u_s=\min_{1\le r\le K}C_{rs}. \)
Lemma 1. The vector \(u\) belongs to \(F(P,H,B)\), and every \(y\in F(P,H,B)\) satisfies \(y_s\le u_s\) for every \(s\).
Proof. Consider a directed graph with vertices \(0,1,\ldots,K\), and arcs:
All arc costs are nonnegative. Removing a cycle from a walk cannot increase its cost, so a shortest walk can be chosen to be a simple path. After its first arc \(0\to r\), such a path must follow the unique simple path along the period line from \(r\) to its destination \(s\). Its cost is \(C_{rs}\). Thus \(u_s\) is the shortest-path distance from \(0\) to \(s\).
Appending an arc to a shortest path gives
\( \displaystyle u_s\le P_s,\qquad u_{s+1}\le u_s+H_s,\qquad u_s\le u_{s+1}+B_s. \)
Therefore \(u\in F(P,H,B)\).
For any feasible \(y\), telescoping the adjacent inequalities along the path from \(r\) to \(s\), starting with \(y_r\le P_r\), gives \(y_s\le C_{rs}\). Taking the minimum over \(r\) yields \(y_s\le u_s\). \(\square\)
Let \(D\in\mathbb R_{\ge0}^K\). Write \(c_{P,H,B}(D)\) for the production-inventory minimum with these fixed costs and demand vector \(D\).
Lemma 2. For every such real demand vector,
\( \displaystyle c_{P,H,B}(D)=\sum_{s=1}^K D_su_s. \)
Moreover, a feasible dual vector \(y\) is optimal exactly when
\( \displaystyle y_s=u_s\quad\text{for every }s\text{ with }D_s>0. \)
Proof. Rearranging the balance equations and using the zero endpoint variables gives, for every feasible production plan,
\( \displaystyle \sum_{s=1}^K D_sy_s = \sum_{s=1}^K q_sy_s +\sum_{\ell=1}^{K-1}I_\ell(y_{\ell+1}-y_\ell) +\sum_{\ell=1}^{K-1}E_\ell(y_\ell-y_{\ell+1}). \)
Consequently, if \(y\in F(P,H,B)\), its dual value is at most the plan’s cost: each coefficient on the right is bounded above by the corresponding production, holding, or backlog cost, and every plan variable is nonnegative. Applying this to \(u\) proves
\( \displaystyle c_{P,H,B}(D)\ge\sum_sD_su_s. \)
For the reverse inequality, choose, for each \(s\), a period \(r(s)\) attaining \(u_s=C_{r(s),s}\). Produce \(D_s\) units in period \(r(s)\). If \(r(s)<s\), hold those units through periods \(r(s),\ldots,s-1\); if \(r(s)>s\), backlog them through periods \(s,\ldots,r(s)-1\).
Explicitly, the superposed plan is
\( \displaystyle q_j=\sum_{\{s:r(s)=j\}}D_s, \)
\( \displaystyle I_\ell=\sum_{\{s:r(s)\le\ell<s\}}D_s,\qquad E_\ell=\sum_{\{s:s\le\ell<r(s)\}}D_s \quad(1\le\ell<K), \)
with all endpoint inventory and backlog variables zero. Each individual demand contribution satisfies the balance equations, so their sum does too. Its cost is
\( \displaystyle \sum_{s=1}^K D_sC_{r(s),s} =\sum_{s=1}^K D_su_s. \)
This proves the cost formula and attainment of both optima.
Finally, Lemma 1 gives \(u_s-y_s\ge0\) for every feasible \(y\). Its gap from the optimal dual value is
\( \displaystyle \sum_{s=1}^K D_s(u_s-y_s). \)
Every summand is nonnegative. The gap vanishes exactly when \(y_s=u_s\) at every period having positive demand. \(\square\)
This argument uses no demand integrality or rationality.
For the grand coalition, set
\( \displaystyle P_s=p_s^\mu,\qquad H_s=h_s^\mu,\qquad B_s=b_s^\mu, \)
and construct \(u\) as above. Define
\( \displaystyle o_t=\sum_{s=1}^K d_{t,s}u_s. \)
Let \(y\) be any optimal grand-coalition dual vector. Lemma 2 shows that \(y_s=u_s\) whenever \(D_s(\mu)>0\).
Because every listed mass is positive and every demand is nonnegative,
\( \displaystyle D_s(\mu)=0 \quad\Longleftrightarrow\quad d_{t,s}=0\text{ for every listed type }t. \)
Indeed, a positive demand \(d_{t,s}\) contributes the strictly positive quantity \(\mu_td_{t,s}\). Therefore any coordinate where optimal prices might differ contributes zero to every type’s allocation. Hence
\( \displaystyle o_t(y)=\sum_s d_{t,s}y_s =\sum_s d_{t,s}u_s=o_t \)
for every type \(t\).
Efficiency follows from Lemma 2:
\( \displaystyle \sum_{t=1}^{\tau}\mu_to_t =\sum_{s=1}^K D_s(\mu)u_s =c(\mu). \)
The dual vector itself need not be unique. For example, with one type, mass \(1\), demand \((1,0)\), and all costs equal to \(1\), every vector \((1,z)\) with \(0\le z\le1\) is optimal. Each induces allocation \(1\).
Fix any nonzero coalition \(0\le\nu\le\mu\). Its positive-mass types form a subset of the grand coalition’s support. Thus
\( \displaystyle p_s^\mu\le p_s^\nu,\qquad h_s^\mu\le h_s^\nu,\qquad b_s^\mu\le b_s^\nu. \)
It follows directly that every grand-coalition feasible dual vector is feasible for the coalition’s dual: all its upper bounds are relaxed.
In particular, applying the weak-duality identity from Lemma 2 to \(u\), the coalition costs, and the real demand vector \(D(\nu)\), gives
\( \displaystyle \sum_{t=1}^{\tau}\nu_to_t =\sum_{s=1}^K D_s(\nu)u_s \le c(\nu). \)
For \(\nu=0\), both sides are zero. This proves all required inequalities, including those for irrational masses.
Define the per-unit core as the set of vectors \(x\in\mathbb R^\tau\) satisfying the efficiency and coalition inequalities in the question.
We have proved that \(o\) belongs to it. Let \(x\) be any other core vector, and fix a type \(t\). Let \(e_t\) denote the \(t\)-th coordinate vector and choose \(0<\varepsilon<\mu_t\). The coalition
\( \displaystyle \nu=\mu-\varepsilon e_t \)
still contains every listed type with positive mass, so its cost coefficients equal the grand coalition’s. Lemma 2 therefore gives
\( \displaystyle c(\nu)=c(\mu)-\varepsilon o_t. \)
Efficiency of \(x\) and its inequality for this coalition imply
\( \displaystyle c(\mu)-\varepsilon x_t =\sum_j\nu_jx_j \le c(\mu)-\varepsilon o_t. \)
Thus \(x_t\ge o_t\). This holds for every type. But efficiency also gives
\( \displaystyle \sum_t\mu_t(x_t-o_t)=0. \)
All summands are nonnegative, and every \(\mu_t\) is positive. Hence \(x_t=o_t\) for every type, proving that the core is exactly \(\{o\}\).
Compute the grand-coalition cost minima by scanning the listed support. This takes \(O(K\tau)\) rational comparisons.
The prices \(u\) require only two passes. Define
\( \displaystyle F_1=P_1,\qquad F_s=\min\{P_s,F_{s-1}+H_{s-1}\} \quad(2\le s\le K), \)
and
\( \displaystyle G_K=P_K,\qquad G_s=\min\{P_s,G_{s+1}+B_s\} \quad(1\le s<K). \)
Induction on the recurrences gives
\( \displaystyle F_s=\min_{r\le s}\left(P_r+\sum_{\ell=r}^{s-1}H_\ell\right),\qquad G_s=\min_{r\ge s}\left(P_r+\sum_{\ell=s}^{r-1}B_\ell\right). \)
Consequently \(u_s=\min\{F_s,G_s\}\). Finally compute \(o_t=\sum_s d_{t,s}u_s\).
The total is \(O(K\tau+K)\) exact arithmetic operations and comparisons.
To verify the bit bound, take a common denominator \(Q\) equal to the product of all input cost denominators. Its binary length is \(O(L)\). After scaling costs by \(Q\), the recurrences use integer additions and comparisons. Every recurrence value represents a sum of at most \(K\) input costs, so its scaled binary length is \(O(L+\log K)\). Multiplication by input demands and summation over periods preserve a polynomial bit bound for the allocations. Thus all operations, and the entire algorithm, take polynomial bit time in \(K,\tau,L\).
Since \(m=K\), computing a dual-induced allocation is polynomial-time solvable in the requested parameters.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves both questions in USER_TASK: all optimal grand-coalition dual vectors induce the same per-unit allocation, that allocation satisfies efficiency and every real-coalition inequality, and it is exactly computable in polynomial bit time. The additional singleton-core claim is also proved.
No major or minor mathematical issues were found.
Lemma 1 is correct.
This also covers zero costs and \(K=1\). No lower bound on dual coordinates is assumed or needed.
Lemma 2 is correct.
The displayed weak-duality identity has the correct signs. Rearranging the balance equations yields inventory coefficients \(y_{\ell+1}-y_\ell\) and backlog coefficients \(y_\ell-y_{\ell+1}\); the endpoint conditions eliminate boundary terms. Dual feasibility bounds each coefficient by its corresponding cost.
The constructed production plan is feasible:
Simultaneously positive inventory and backlog are permitted by the stated model, so superposition causes no feasibility issue. The plan’s cost is exactly the claimed sum, establishing attainment and equality.
Finally, each term \(D_s(u_s-y_s)\) is nonnegative. Thus the objective gap vanishes exactly when \(y_s=u_s\) at every positive-demand coordinate. This remains valid when all demands vanish: the coordinate condition is vacuous, and every feasible dual vector is optimal.
The argument applies to arbitrary nonnegative real demands, including irrational demands.
The argument is correct and uses the support assumption essentially.
Because every listed \(\mu_t\) is strictly positive and all demands are nonnegative, \(D_s(\mu)=0\) holds exactly when every listed type has zero demand in period \(s\). Consequently, coordinates where optimal dual vectors may differ contribute nothing to any type’s allocation.
The efficiency calculation correctly exchanges finite sums and applies Lemma 2.
The nonunique-dual example is valid: every displayed vector satisfies the constraints and has optimal objective value \(1\). The example does not claim to enumerate all optimal vectors.
The proof is correct.
For every nonzero coalition, its positive-mass support is a nonempty subset of the grand-coalition support. Taking minima over this subset can only increase each cost coefficient. Hence every grand-coalition feasible dual vector remains feasible for that coalition.
Applying the already-proved weak-duality identity establishes the inequality for every real coalition mass vector. No rationality assumption, limiting argument, or finite-agent reduction is used.
The zero coalition is handled explicitly and correctly.
The stronger claim is proved.
Choosing \(0<\varepsilon<\mu_t\) keeps every type’s mass positive in the reduced coalition. Its cost coefficients therefore remain exactly those of the grand coalition, permitting application of the fixed-cost formula.
The resulting coalition inequality correctly gives \(x_t\ge o_t\). Efficiency then forces equality in every coordinate because all masses are positive.
This argument covers \(\tau=1\), zero-demand types, and an entirely zero-demand society. It concerns exactly the per-unit core defined in the output.
The recurrences and complexity analysis are correct.
The bit bound is sufficient. The product of all input cost denominators has binary length \(O(L)\). After scaling, every recurrence value represents a sum of at most \(K\) input costs, so its bit length is \(O(L+\log K)\). Multiplication by binary-encoded demands and summation preserve polynomial bit length. Constructing the common denominator and performing the exact operations also take polynomial bit time.
The algorithm depends on the listed support size, without expanding rational masses into agents or enumerating coalitions.
The historical attribution is accurate: [Theorem 5.1 of the cited paper](https://arxiv.org/html/2402.04328v1#S5) states singleton Owen-set uniqueness for finite-agent production-inventory situations with integer demand matrices. The output uses this as background, not as a theorem applied to the mass model; its proof is self-contained.
Required repairs: none.
⟨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.