REVIEW 3 major objections 2 minor 55 references
The Multi-Stage Assignment Problem: A Fairness Perspective
T0 review · 3 major / 2 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read This submission claims envy-minimizing assignment on multi-stage graphs is NP-hard and gives a 2M envy bound, yet the body text is an unrelated quantum-optics paper.
desk verdict Abstract advertises a fair-assignment paper, but the body is an unrelated quantum-optics paper; none of the claimed results exist in this manuscript. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The stated machinery is the C-Balance algorithm: for two agents it supposedly equalizes assigned path costs so that envy—the maximum cost gap between agents—is at most 2M, with a matching lower-bound example; DC-Balance repeatedly invokes C-Balance to handle n agents and is claimed to converge to envy arbitrarily close to 2M. The underlying object is a multi-stage graph, a sequence of weighted bipartite graphs between adjacent layers in which each agent receives a node-disjoint path from the first stage to the last. None of this machinery is present in the submitted full text, which concerns beamsplitter replacements for parametric down-conversion.
What would settle it
Read the submitted full text in search of C-Balance, the NP-hardness reduction, and theorem statements; none appears. To test the mathematical bound directly, implement the algorithm described in the abstract on two-agent instances of 3 or more stages with maximum edge weight 1 and search for envy exceeding 2; the first such instance would refute the 2M guarantee even before the missing proofs are supplied.
Extended reading notes
Core claim
The abstract asserts that an assignment minimizing total path cost on a multi-stage graph—nodes partitioned into K stages with weighted bipartite edges between consecutive stages, agents routed along node-disjoint paths from first to last stage—can be highly envious, and that finding an envy-minimizing assignment is NP-hard. It further asserts C-Balance, a two-agent balancing algorithm, bounds pairwise envy by 2M where M is the maximum edge weight, that this bound is tight, that the cost of the fair assignment is at most twice the minimum-cost assignment, and that DC-Balance makes iterative calls to C-Balance to bring n-agent envy arbitrarily close to 2M. The body text provided with this sub
Load-bearing premise
The load-bearing premise is that a pairwise cost gap between two agents is controlled by the largest single edge weight M, even though each agent's cost is a sum over many edges; the even weaker premise, at submission level, is that the algorithms and proofs described in the abstract exist in this manuscript at all.
Editorial extensions
If this is right
- If the abstract's claims hold, fair assignment on multi-stage graphs becomes tractable in a practical sense: a polynomial algorithm with constant worst-case envy in the largest edge weight and a cost-of-fairness factor of 2.
- The NP-hardness result would justify the approximation approach, ruling out exact envy minimization in general.
- The tight 2M example would show the analysis cannot be improved within the same algorithmic strategy.
- The claimed orders-of-magnitude speedup over ILP would make the algorithm usable in large staged routing settings.
Reading between the lines
- The abstract–body mismatch reads as a packaging error in the submission rather than a deliberate mathematical claim; the assignment results should be evaluated only against a complete, corrected manuscript.
- If the 2M bound is later proven, the most natural stress test is whether it degrades with the number of stages K; a reader should look for a counterexample with many small edges whose sum creates envy beyond 2M.
- The quantum-optics body has its own standalone content, but it cannot be used as support for, or evidence about, the multi-stage assignment problem.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The submission has the title and abstract of a paper on fair assignment in multi-stage graphs: it claims NP-hardness of envy-minimizing assignment, a C-Balance algorithm with a tight 2M envy bound for two agents, cost-of-fairness bound 2, a DC-Balance extension, and experimental speedups over an ILP. The full text, however, is a quantum-optics paper titled 'Nonlinear-linear duality for multipath quantum interference' with its own author list, introduction, theory, appendices, and references, and it contains none of the assignment problem, algorithms, definitions, theorems, proofs, or experiments announced in the abstract. The abstract's central claims are therefore uncheckable in this manuscript.
Significance. If the claimed results were stated and proved, they would constitute a substantive contribution: a first approximation framework with worst-case envy and cost guarantees for fair path assignment on multi-stage graphs, including an NP-hardness result and an algorithmic comparison with ILP. However, the manuscript as submitted provides none of these results. The optics body may be a legitimate and internally coherent contribution, with proofs in appendices and an honest statement of its own limitations, but it is not the paper described by the abstract. Consequently, the significance of the claimed results cannot be evaluated, and the submission-level premise — that this manuscript contains the promised technical content — is false.
major comments (3)
- [Abstract vs. Full text] None of the central objects or results appear in the body. The abstract asserts: (1) NP-hardness of envy-minimizing assignment on multi-stage graphs; (2) C-Balance guarantees envy at most 2M for two agents, with tightness; (3) cost-of-fairness at most 2; (4) DC-Balance converges to envy arbitrarily close to 2M; (5) orders-of-magnitude speedup over a suitably formulated ILP. Sections I–IV and Appendices A–F contain no multi-stage graphs, no assignment problem, no envy measure, no C-Balance or DC-Balance algorithms, and no ILP. These are not presentation issues; they are the entire claimed content of the paper, and their absence makes the abstract's assertions impossible to audit.
- [Abstract (envy bound)] The two-agent envy bound is claimed to be 2M, with M the maximum edge weight, and no stated dependence on the number of stages K. Since an agent's path cost is a sum of edge weights over many stages, pairwise cost disparity could in principle grow with K even when M is fixed. The manuscript provides no definition of envy, no algorithm, and no proof, so this fragile premise cannot be assessed. No equation or theorem beyond the abstract can be cited to check whether the bound depends only on M.
- [Data Availability / Experiments] The abstract claims 'we experimentally show that our algorithm runs several orders of magnitude faster than a suitably formulated ILP.' The full text has no experimental section, no ILP formulation, no benchmarks, and no runtime comparisons. Moreover, the Data Availability statement in the body says 'No data were created or analyzed in this study.' This directly contradicts the abstract's empirical claim and makes the reported speedup unverifiable.
minor comments (2)
- [Title and metadata] The title of the submission, 'The Multi-Stage Assignment Problem: A Fairness Perspective,' does not match the body's title, 'Nonlinear-linear duality for multipath quantum interference.' The body's arXiv header shows 2508.13855v3, not 2508.13856. This mismatch must be resolved; as submitted, the document is not self-consistent.
- [References] The body's reference list is entirely on quantum optics and contains no citations to multi-stage assignment, fair division, envy minimization, or computational complexity related to the abstract's claims. This reinforces that the body is a different paper.
Circularity Check
No circularity can be established: the abstract's claims have no derivations in this manuscript, so there is no reduction to inputs to exhibit; this is a submission-integrity issue, not circularity.
full rationale
The submission presents an abstract that promises results on the Multi-Stage Assignment Problem (C-Balance, DC-Balance, envy bounds bounded by 2M, cost-of-fairness bounds, ILP speedup) followed by a full text titled "Nonlinear-linear duality for multipath quantum interference" by a different set of authors. None of the abstract's definitions, theorems, algorithms, proofs, or experiments appear in the body. Consequently, there is no derivation chain in this manuscript that can be walked, no equations to compare, no fitted parameter renamed as prediction, and no self-citation chain invoked to force a conclusion. The hard rules require that circularity be demonstrated by quotation and a specific reduction (e.g., Eq. X = Eq. Y by construction, or a fitted parameter renamed as prediction). Here the claimed results are absent entirely, so no such reduction can be exhibited. This is a completeness or submission-integrity concern rather than circularity. The quantum-optics body is internally coherent and even honestly states its own limitations ('A shortcoming is this duality cannot take single-mode squeezing or real optical cavities into account'), but those limitations are irrelevant to the assignment claims. Therefore, under the stated rules, the correct finding is no significant circularity, score 0, with no specific circular steps identified.
Assumptions & free parameters
assumptions (3)
- domain assumption The assignment problem is defined over a multi-stage graph with nodes partitioned into K stages, agent paths are node-disjoint and run from first to last stage, costs are sums of edge weights, and envy is the maximum pairwise cost disparity.
- domain assumption Body text domain model: nondegenerate parametric down-conversion and lossless linear optical systems, monochromatic signal and idler light, multimode Fock representation.
- standard math Standard quantum-optics mathematics: Fock-space operator algebra, partial transpose of operators, scattering and transfer matrices, Redheffer star product, Gaussian state/symplectic formalism.
invented entities (1)
-
Hypothetical wavelength-shifting beamsplitter (B)
Cite this review
Pith. "Pith review of The Multi-Stage Assignment Problem: A Fairness Perspective." pith.science (2026). https://pith.science/paper/35UOCU6K
@misc{pith2026250813856,
author = {Pith},
title = {Pith review of: The Multi-Stage Assignment Problem: A Fairness Perspective},
year = {2026},
howpublished = {\url{https://pith.science/paper/35UOCU6K}},
note = {Machine review of arXiv:2508.13856}
}
abstract
This paper explores the problem of fair assignment on Multi-Stage graphs. A multi-stage graph consists of nodes partitioned into $K$ disjoint sets (stages) structured as a sequence of weighted bipartite graphs formed across adjacent stages. The goal is to assign node-disjoint paths to $n$ agents starting from the first stage and ending in the last stage. We show that an efficient assignment that minimizes the overall sum of costs of all the agents' paths may be highly unfair and lead to significant cost disparities (envy) among the agents. We further show that finding an envy-minimizing assignment on a multi-stage graph is NP-hard. We propose the C-Balance algorithm, which guarantees envy that is bounded by $2M$ in the case of two agents, where $M$ is the maximum edge weight. We demonstrate the algorithm's tightness by presenting an instance where the envy is $2M$. We further show that the cost of fairness ($CoF$), defined as the ratio of the cost of the assignment given by the fair algorithm to that of the minimum cost assignment, is bounded by $2$ for C-Balance. We then extend this approach to $n$ agents by proposing the DC-Balance algorithm that makes iterative calls to C-Balance. We show the convergence of DC-Balance, resulting in envy that is arbitrarily close to $2M$. We derive $CoF$ bounds for DC-Balance and provide insights about its dependency on the instance-specific parameters and the desired degree of envy. We experimentally show that our algorithm runs several orders of magnitude faster than a suitably formulated ILP.
Reference graph
Works this paper leans on
-
[1]
Multipath transfer matrix In classical optics, when analyzing multilayer thin-film structures, the transfer matrix is used to connect the forward- and backward-propagating light amplitudes at one side of the interface to the other, while the scattering matrix connecting the output amplitudes to the input ones follows the causal- ity. The transfer matrix o...
-
[2]
Gaussian operation andQ-function relation A nonlinear system with nondegenerate PDCs and linear lossless systems performs a Gaussian operation to the quan- tum optical field. Such an operation can be described by a symplectic matrixFwhich determines the Bogoliubov trans- formation to the creation and annihilation operators. Using the α,α ∗ basis (there ar...
-
[3]
This method cannot determineargC U
Nonlinear-linear duality Letting theP-functions of four multipath pure states beP s0(α),P s(α),P i0(α), andP i(α)(for example, |ψs0⟩⟨ψs0|= R dαPs0(α)|α⟩⟨α|), because|ψ ∗ i ⟩⟨ψ∗ i |=R dαPi(α)|α∗⟩⟨α∗|, we have ⟨ψs;ψ i| ˆU|ψ s0;ψ i0⟩ 2 = Z dαsdαidβsdβiPs0(αs)Pi0(αi)Ps(βs)Pi(βi) × ⟨βs;β i| ˆU|α s;α i⟩⟨αs;α i| ˆU †|βs;β i⟩ =|C U |2 Z dαsdαidβsdβiPs0(αs)Pi0(αi)...
-
[4]
One can find thatT ii =T ∗ ss andT is =T ∗ si [50]
Discussion on the duality for single-mode squeezing For realistic linear systems with cavities, the forward- and backward-propagating lights have the same wavelength, so Li =L s for a single linear lossless system (in this subsection, sandionly stand for forward and backward directions). One can find thatT ii =T ∗ ss andT is =T ∗ si [50]. Then, with Eq. (...
-
[5]
F. Dell’Anno, S. De Siena, and F. Illuminati, Multiphoton quan- tum optics and quantum state engineering, Phys. Rep.428, 53 (2006)
work page 2006
-
[6]
Fabre and N
C. Fabre and N. Treps, Modes and states in quantum optics, Rev. Mod. Phys.92, 035005 (2020)
2020
-
[7]
N. Quesada, L. G. Helt, M. Menotti, M. Liscidini, and J. E. Sipe, Beyond photon pairs—nonlinear quantum photonics in the high-gain regime: a tutorial, Adv. Opt. Photon.14, 291 (2022)
work page 2022
- [8]
Show all 55 references
-
[9]
B. E. A. Saleh,Quantum Photonics(Springer, Cham, 2025)
2025
-
[10]
M. V . Chekhova and Z. Y . Ou, Nonlinear interferometers in quantum optics, Adv. Opt. Photon.8, 104 (2016)
2016
-
[11]
Jin, Z.-Q
R.-B. Jin, Z.-Q. Zeng, C. You, and C. Yuan, Quantum interfer- ometers: Principles and applications, Prog. Quantum Electron. 96, 100519 (2024)
2024
-
[12]
C. K. Hong, Z. Y . Ou, and L. Mandel, Measurement of subpi- cosecond time intervals between two photons by interference, Phys. Rev. Lett.59, 2044 (1987). 14
-
[13]
Bouchard, A
F. Bouchard, A. Sit, Y . Zhang, R. Fickler, F. M. Miatto, Y . Yao, F. Sciarrino, and E. Karimi, Two-photon interference: the Hong–Ou–Mandel effect, Rep. Prog. Phys.84, 012402 (2020)
2020
-
[14]
M. G. Jabbour and N. J. Cerf, Multiparticle quantum interfer- ence in Bogoliubov bosonic transformations, Phys. Rev. Res.3, 043065 (2021)
2021
-
[15]
J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Koltham- mer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley, Boson sampling on a photonic chip, Sci- ence339, 798 (2013)
2013
-
[16]
Tillmann, B
M. Tillmann, B. Daki ´c, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, Experimental boson sampling, Nat. Photon.7, 540 (2013)
2013
-
[17]
A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, Boson sampling from a Gaussian state, Phys. Rev. Lett.113, 100502 (2014)
2014
-
[18]
C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silber- horn, and I. Jex, Gaussian boson sampling, Phys. Rev. Lett.119, 170501 (2017)
2017
-
[19]
Kruse, C
R. Kruse, C. S. Hamilton, L. Sansoni, S. Barkhofen, C. Silber- horn, and I. Jex, Detailed study of Gaussian boson sampling, Phys. Rev. A100, 032326 (2019)
2019
-
[20]
X. Y . Zou, L. J. Wang, and L. Mandel, Induced coherence and indistinguishability in optical interference, Phys. Rev. Lett.67, 318 (1991)
1991
-
[21]
L. J. Wang, X. Y . Zou, and L. Mandel, Induced coherence with- out induced emission, Phys. Rev. A44, 4614 (1991)
1991
-
[22]
Krenn, X
M. Krenn, X. Gu, and A. Zeilinger, Quantum experiments and graphs: Multiparty states as coherent superpositions of perfect matchings, Phys. Rev. Lett.119, 240403 (2017)
2017
-
[23]
Hochrainer, M
A. Hochrainer, M. Lahiri, M. Erhard, M. Krenn, and A. Zeilinger, Quantum indistinguishability by path identity and with undetected photons, Rev. Mod. Phys.94, 025007 (2022)
2022
-
[24]
K. Qian, K. Wang, L. Chen, Z. Hou, M. Krenn, S. Zhu, and X.- s. Ma, Multiphoton non-local quantum interference controlled by an undetected photon, Nat. Commun.14, 1480 (2023)
2023
-
[25]
G. B. Lemos, V . Borish, G. D. Cole, S. Ramelow, R. Lap- kiewicz, and A. Zeilinger, Quantum imaging with undetected photons, Nature (London)512, 409 (2014)
2014
-
[26]
Lahiri, R
M. Lahiri, R. Lapkiewicz, G. B. Lemos, and A. Zeilinger, The- ory of quantum imaging with undetected photons, Phys. Rev. A 92, 013832 (2015)
2015
-
[27]
G. B. Lemos, M. Lahiri, S. Ramelow, R. Lapkiewicz, and W. N. Plick, Quantum imaging and metrology with undetected pho- tons: tutorial, J. Opt. Soc. Am. B39, 2200 (2022)
2022
-
[28]
Leonhardt, Quantum physics of simple optical instruments, Rep
U. Leonhardt, Quantum physics of simple optical instruments, Rep. Prog. Phys.66, 1207 (2003)
2003
-
[29]
N. J. Cerf and M. G. Jabbour, Two-boson quantum interference in time, Proc. Natl. Acad. Sci. USA117, 33107 (2020)
2020
-
[30]
J. R. Carson, A generalization of the reciprocal theorem, Bell Syst. Tech. J.3, 393 (1924)
1924
-
[31]
Zheng, J.-S
Y . Zheng, J.-S. Xu, C.-F. Li, and G.-C. Guo, Theory of the monochromatic advanced-wave picture and applications in biphoton optics, Phys. Rev. A110, 063710 (2024)
2024
-
[32]
W. E. Salazar, O. Calderón-Losada, and J. H. Reina, Linear- nonlinear duality for circuit design on quantum computing plat- forms, arXiv:2310.20416
-
[33]
It can also be a three-wave mixing process with a strong coher- ent light under the parametric approximation
-
[34]
Chen, S.-T
C. Chen, S.-T. Xue, Y .-P. Shi, J. Wang, Z.-M. Cheng, P. Wan, Z.-C. Ren, M. G. Jabbour, N. J. Cerf, X.-L. Wang, and H.- T. Wang, Two-particle quantum interference in a nonlinear optical medium: a witness of timelike indistinguishability, arXiv:2502.01480
-
[35]
D. N. Klyshko, A simple method of preparing pure states of an optical field, of implementing the Einstein–Podolsky–Rosen experiment, and of demonstrating the complementarity princi- ple, Sov. Phys. Usp.31, 74 (1988)
1988
-
[36]
D. N. Klyshko, Two-photon light: Influence of filtration and a new possible EPR experiment, Phys. Lett. A128, 133 (1988)
1988
-
[37]
T. B. Pittman, Y . H. Shih, D. V . Strekalov, and A. V . Sergienko, Optical imaging by means of two-photon quantum entangle- ment, Phys. Rev. A52, R3429 (1995)
1995
-
[38]
Walborn, C
S. Walborn, C. Monken, S. Pádua, and P. Souto Ribeiro, Spatial correlations in parametric down-conversion, Phys. Rep.495, 87 (2010)
2010
-
[39]
M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, Exper- imental realization of any discrete unitary operator, Phys. Rev. Lett.73, 58 (1994)
1994
-
[40]
Chakhmakhchyan and N
L. Chakhmakhchyan and N. J. Cerf, Simulating arbitrary Gaus- sian circuits with linear optics, Phys. Rev. A98, 062314 (2018)
2018
-
[41]
R. M. Redheffer, On a certain linear fractional transformation, J. Math. Phys.39, 269 (1960)
1960
-
[42]
Li, Formulation and comparison of two recursive matrix al- gorithms for modeling layered diffraction gratings, J
L. Li, Formulation and comparison of two recursive matrix al- gorithms for modeling layered diffraction gratings, J. Opt. Soc. Am. A13, 1024 (1996)
1996
-
[43]
If their product (the modulus of the determinant) is1, they are all1and the matrix is unitary
The singular values of a scattering matrix for a linear optical system cannot be greater than1. If their product (the modulus of the determinant) is1, they are all1and the matrix is unitary
-
[44]
Yurke, S
B. Yurke, S. L. McCall, and J. R. Klauder, SU(2) and SU(1,1) interferometers, Phys. Rev. A33, 4033 (1986)
1986
-
[45]
Z. Y . Ou and X. Li, Quantum SU(1,1) interferometers: Basic principles and applications, APL Photon.5, 080902 (2020)
2020
-
[46]
The two phase plates on thespaths have the phase(Φ s + argβ)/2and those on theipaths are(Φ i + argβ)/2
-
[47]
Weedbrook, S
C. Weedbrook, S. Pirandola, R. García-Patrón, N. J. Cerf, T. C. Ralph, J. H. Shapiro, and S. Lloyd, Gaussian quantum informa- tion, Rev. Mod. Phys.84, 621 (2012)
2012
-
[48]
C. N. Gagatsos and S. Guha, Efficient representation of Gaus- sian states for multimode non-Gaussian quantum state engi- neering via subtraction of arbitrary number of photons, Phys. Rev. A99, 053816 (2019)
2019
-
[49]
Nevertheless, this theory is suitable for a well-calibrated setup which performs the PDC with almost no other influences on the optical field
The optical cavity can be seen in an optical parametric oscil- lator or amplifier, where a nonlinear crystal is inserted into it. Nevertheless, this theory is suitable for a well-calibrated setup which performs the PDC with almost no other influences on the optical field
-
[50]
J. Wang, F. Sciarrino, A. Laing, and M. G. Thompson, Inte- grated photonic quantum technologies, Nat. Photon.14, 273 (2020)
2020
-
[51]
Bouwmeester, J.-W
D. Bouwmeester, J.-W. Pan, K. Mattle, M. Eibl, H. Weinfurter, and A. Zeilinger, Experimental quantum teleportation, Nature (London)390, 575 (1997)
1997
-
[52]
However, perfect interference filters can be placed to totally ab- sorb lights with unwanted frequencies which are isolated from our considered ones
In practice, there might be PDC processes outsideD s orD i. However, perfect interference filters can be placed to totally ab- sorb lights with unwanted frequencies which are isolated from our considered ones. If the pump beam is polychromatic, the filtering leads to undetecte...
-
[53]
Houde, W
M. Houde, W. McCutcheon, and N. Quesada, Matrix de- compositions in quantum optics: Takagi/Autonne, Bloch– Messiah/Euler, Iwasawa, and Williamson, Can. J. Phys.102, 497 (2024)
2024
-
[54]
These are proved by verifying them for the elementary cases, one BS and one linear system pair, and then proving if two transfer matrices do, their product also does
-
[55]
S. L. Braunstein, Squeezing as an irreducible resource, Phys. Rev. A71, 055801 (2005)
2005
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.