d4-journals-geb-2009-0049

I would make one focused case around Theorem 5.1, proved in this paper. It says that for every PI-situation with integer demands, the Owen set is a singleton, and gives the unique Owen allocation explicitly. For a firm \(i\), its cost share is its demand in each period multiplied by that period’s minimum-cost production price: if demand in period \(s\) is cheapest to produce then, the price is \(p_s^N\); if it is cheaper to produce earlier and hold, it is \(p_k^N+\sum_{r=k}^{s-1}h_r^N\); if it is cheaper to produce later and backload, it is \(p_k^N+\sum_{r=s}^{k-1}b_r^N\). Here \(p^N,h^N,b^N\) are the componentwise cheapest costs available to the grand coalition, and \(k\) is the cheapest production period in the relevant direction. The theorem says these shares are the same whichever optimal dual solution is used. Its explicit formula gives a polynomial-time computation in the horizon and the input size; the paper also states that the Owen point is polynomially computable.

A plausible high-multiplicity setting is a large cooperative of independently operated production or distribution units—say, many standardized regional facilities pooling production and warehouse access over the same planning horizon. A type \(t\) is the full vector \((d_t,p_t,h_t,b_t)\): the unit’s demand by period and its production, inventory, and backlogging costs. Units with the same vector are interchangeable for this problem. There might be tens of thousands of units but only tens or hundreds of recurring demand-and-cost profiles. This fits the paper’s own firm-based model better than a story about individually targeted consumers.

Here is the continuous problem I would hand to a prover. Call it Mass-PI Owen Allocation. The input is a finite support of types \(t\), each with integer demand vector \(d_t\in\mathbb Z_{\ge0}^K\) and nonnegative rational cost vectors \(p_t,h_t,b_t\), together with rational masses \(\mu_t\ge0\) summing to \(1\). For any coalition mass vector \(0\le\nu\le\mu\), let \(A(\nu)=\{t:\nu_t>0\}\). The coalition’s demand in period \(s\) is \(\sum_t\nu_t d_{t,s}\); its unit costs are the cheapest costs among the types in \(A(\nu)\). Define its operation cost \(c(\nu)\) as the minimum of
\[ \sum_{s=1}^K (p_s^{A(\nu)}q_s+h_s^{A(\nu)}I_s+b_s^{A(\nu)}E_s) \]
over nonnegative aggregate production, inventory, and backlog satisfying the paper’s period-by-period flow equations and zero initial and final inventory and backlog. For \(\nu=0\), set \(c(0)=0\).

The task is to compute an exact cost share \(o_t\) per unit of type \(t\), such that the type’s total allocation is \(\mu_t o_t\), the allocation is efficient, and every coalition mass vector is protected:
\[ \sum_t\mu_t o_t=c(\mu), \qquad \sum_t\nu_t o_t\le c(\nu)\quad\text{for every }0\le\nu\le\mu. \]
A solution is the rational vector \((o_t)_t\) satisfying those conditions. Theorem 5.1 supplies it directly: compute the grand coalition’s period prices and set \(o_t=\sum_s d_{t,s}\lambda_s^\mu\), where
\[ \lambda_s^\mu= \min\left\{ p_s^\mu,\ \min_{k<s}\left(p_k^\mu+\sum_{r=k}^{s-1}h_r^\mu\right),\ \min_{k>s}\left(p_k^\mu+\sum_{r=s}^{k-1}b_r^\mu\right) \right\}. \]
Empty minima are omitted. This is tractable in \(\mathrm{poly}(K,\tau,L)\), where \(\tau\) is the support size and \(L\) the binary input length. The core guarantee extends to fractional coalition masses because the grand coalition’s dual prices remain feasible when a coalition has weakly higher minimum costs; duality then gives the coalition inequality.

This is a plausible mirror of the paper’s Owen-allocation result: the authors already model a finite set of firms with complete demand-and-cost profiles, and the continuous input replaces counts of identical firms with their population shares. For \(\mu_t=n_t/n\), the continuous aggregate costs and allocations are the discrete ones normalized by \(n\); the continuous model adds fractional coalition masses and allows average production quantities to be fractional. The planning horizon remains finite and discrete. The mirror covers the computation and stability of the Owen allocation, rather than every result in the paper.

I would expect this problem to be Class A, tractable: the explicit formula does the work, so no exponential-variable LP or difficult pricing problem is needed. Further questions include whether the paper’s singleton-core criterion in Theorem 5.4 has a clean support-based continuum version, how the full core changes when coalition masses become fractional, and how sensitive allocations are when a type’s mass approaches zero.

The soft spot is substantial: the paper is a cooperative operations-research game, not a voting or social-choice paper, and it contains no named hardness result whose complexity might dissolve under continuization. This is a case for the population-continuity method, not a claim that the paper fills a voting-complexity gap. There is also a modeling edge in the paper’s rule that any positive coalition mass of a type supplies its cheapest technology; an arbitrarily small mass can therefore unlock that technology for the whole coalition. The finite model has the same feature for a single member, but the continuum version makes it especially visible.