| paper | d4-journals-jet-2013-0109 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Lemma 2
Given a finite resource set \(Q\) and a support \(\mathcal T\) of \(\tau\) types, where type \(t\) has mass \(\mu_t\in\mathbb Q_{>0}\), peak \(p_t\), and eligible sources \(N_t\subseteq Q\), and each source \(r\) has rational supply \(\omega_r\) per unit of normalized population, compute the unique weighted analogue of Lemma 2’s partition \((\mathcal T_+,\mathcal T_0,\mathcal T_-;Q_+,Q_0,Q_-)\) in time polynomial in the input size and rational bit length \(L\). Define \(P(S)=\sum_{t\in S}\mu_t p_t\), \(\Omega(R)=\sum_{r\in R}\omega_r\), \(f(S)=\bigcup_{t\in S}N_t\), and \(g(R)=\{t:N_t\cap R\ne\varnothing\}\). The partition must satisfy \(E(\mathcal T_-,Q_0\cup Q_-)=E(\mathcal T_0,Q_-)=\varnothing\), \(P(S)<\Omega(f(S)\cap Q_-)\) for each nonempty \(S\subseteq\mathcal T_+\), and \(\Omega(R)<P(g(R)\cap\mathcal T_-)\) for each nonempty \(R\subseteq Q_+\); the balanced component must admit flows \(y_{tr}\ge0\) on eligible edges in \(\mathcal T_0\times Q_0\) with \(\sum_r y_{tr}=\mu_t p_t\) and \(\sum_t y_{tr}=\omega_r\).
Types carry mass \(\mu_t\), peak \(p_t\), and source eligibility \(N_t\); source supplies are normalized to a unit-mass population. Partition labels are the decision variables, with eligible aggregate flows \(y_{tr}\) witnessing balance; there is no optimization objective.
The mirror covers computation of the canonical partition; it leaves the full Egalitarian allocation, Lorenz dominance, characterization, and incentive properties unmirrored.
The closest computational anchor is Lemma 2, proved in the paper. It states that for every connected bipartite compatibility graph \(G\), positive resource supplies \(\omega\), and nonnegative peak profile \(p\), there is a unique partition of agents and resources into \(M_+,M_0,M_-\) and \(Q_+,Q_0,Q_-\). There are no edges from \(M_-\) to \(Q_0\) or \(Q_-\), or from \(M_0\) to \(Q_-\); the restricted problem on \(M_+,Q_-\) is underdemanded, the one on \(M_0,Q_0\) is balanced, and the one on \(M_-,Q_+\) is overdemanded. The paragraph immediately after the lemma says this canonical partition can be computed in polynomial time in the number of nodes. That runtime claim is in the prose, not in the numbered lemma itself; if your anchor rule requires the numbered statement itself to assert membership in \(P\), the paper has no qualifying anchor. It has no named hardness result either.
A natural mirror is Weighted Canonical Decomposition. Consider a large water system with finitely many sources \(Q\). Households fall into \(\tau\) exact types: each type \(t\) has a single-peaked demand with peak \(p_t\) and can receive water from sources \(N_t\subseteq Q\). Let \(\mu_t\in\mathbb{Q}_{>0}\) be its population fraction, with \(\sum_t\mu_t=1\), and let \(\omega_r\in\mathbb{Q}_{>0}\) be source \(r\)’s supply per resident. In a plausible high-multiplicity regime, millions of households belong to dozens or hundreds of zone-by-demand types. The full type includes both demand and source access; \(\mu_t\) is a share of the population. Scaling supply per resident is part of making this population limit meaningful.
The problem is: given \(Q\), the type data, and the rational supplies, compute the unique weighted analogue of Lemma 2’s three-part partition. For \(S\subseteq\mathcal T\), write \(f(S)=\bigcup_{t\in S}N_t\) and \(P(S)=\sum_{t\in S}\mu_t p_t\); for \(R\subseteq Q\), write \(g(R)=\{t:N_t\cap R\ne\varnothing\}\) and \(\Omega(R)=\sum_{r\in R}\omega_r\). The underdemanded part must satisfy \(P(S)<\Omega(f(S)\cap Q_-)\) for every nonempty \(S\subseteq\mathcal T_+\); the balanced part must admit per-member allocations \(p_t\) using exactly the \(Q_0\) supplies; and the overdemanded part must satisfy \(\Omega(R)<P(g(R)\cap\mathcal T_-)\) for every nonempty \(R\subseteq Q_+\), along with the same no-edge conditions as Lemma 2. The output is the partition. The paper’s two surplus functions become \(P(S)-\Omega(f(S))\) and \(\Omega(R)-P(g(R))\). I would expect this mirror to be Class A, with a weighted cut or maximum-closure algorithm running in the explicit support size and rational bit length.
This is a plausible question for the authors because it preserves their central objects and distinctions: peaks, bilateral eligibility, and underdemanded, balanced, and overdemanded components. It continuizes the population; the fact that water is already divisible is not the point. The mirror covers the decomposition computation that supports the paper’s Pareto characterization and its egalitarian allocation. Proposition 2, proved in the paper, says that the Egalitarian solution is Lorenz dominant among all Pareto-optimal allocations; it makes the decomposition’s role in the mechanism especially clear, but it is not itself a complexity result.
The weak point is that the polynomial claim is stated for an explicit finite graph, not for rational type masses encoded in binary. The weighted algorithm and its bit-complexity bound are therefore new work, not a result established by this paper. And this is a narrow algorithmic positive case: it supports a tractable mirror, but not a claim that any discrete hardness in this paper dissolves in the continuum.
The strongest objection is that Lemma 2 is not a named computational result. It proves existence and uniqueness of the three-part decomposition; the polynomial-time computation appears in the prose after the lemma. The paper has no numbered result stating the complexity of a computational problem. So “Weighted Canonical Decomposition” is a new problem suggested by the paper’s structure, not a continuous mirror of one of its computational results.
The best repair is to ask for the full Egalitarian allocation on a society described by rational masses of types, where each type includes its peak and source access, and supplies scale per resident. That is a sensible high-multiplicity regime. But the paper already characterizes Pareto allocations and gives a threshold algorithm for the Egalitarian rule. With divisible resources and identical access within each type, type-level aggregate flows suffice; the new work would chiefly be establishing a bit-complexity bound and adapting the finite algorithm to weighted inputs. That could be useful, but it looks like a narrow algorithmic reformulation rather than a new complexity landscape.
I can’t make the universal negative convincingly. The paper’s lack of a qualifying computational result defeats the stated anchor, but the weighted full-allocation question remains coherent and plausibly worthwhile under the programme’s high-multiplicity aims. The negative case is strongest on the mismatch between the anchor and the requested kind of result, and weakest on the claim that no better mirror deserves attention.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.