Journals and large conferences do not assign reviewers from one flat pool. A submission first goes to an intermediate editor (an Associate Editor or Area Chair), and that editor then recruits reviewers from the people they know and are allowed to use. Every published fair-assignment algorithm ignores this. Some solve the paper-to-reviewer step as if any reviewer were reachable. Others rank editors for the editor-in-chief and never look at which reviewers those editors can reach. The predictable failure is that a niche paper lands with an editor whose reviewer pool contains nobody qualified to judge it, even though a different editor could have served it well. This proposal treats the paper → editor → reviewers chain as one combinatorial problem. It uses parameterized complexity, the branch of algorithms that confines exponential cost to a small, explicitly named quantity, to explain when the cheap tier-by-tier pipeline is already optimal and to repair it exactly when it is not.
The central bet is that hardness in real editorial boards is concentrated in a few contested papers: those whose natural editor cannot serve them, so they must be rerouted. We define the parameter $k$ as the number of papers that must leave their pipeline-chosen editor for the instance to reach the best achievable worst-case reviewer expertise. We then aim for an exact algorithm whose exponential cost depends only on $k$. If $k$ is small on realistic boards, three things follow. Editors get a fast exact solver. They get a certificate that the pipeline is optimal whenever $k=0$. And they get a measured "price of hierarchy", meaning the reviewer quality lost by routing through editors instead of a flat pool.
Core Claim
Define a hierarchical assignment instance as follows. Papers $P$ are routed to editors $E$, and editor $e$ can handle at most $c_e$ papers, with capacities that may differ across editors. Each editor $e$ has a reviewer pool $R_e$, and pools may overlap. Each paper needs $\lambda$ reviewers, all drawn from the pool of the editor that handles it. Reviewer $r$ reviews at most $\ell_r$ papers. $s(p,r)$ is the expertise score between paper $p$ and reviewer $r$. Following the max-min objective of PeerReview4All, the decision question is whether there is a routing $\sigma: P \to E$ and a reviewer assignment $A$ with
$$\min_{p \in P} \; \min_{r \in A(p)} s(p,r) \;\ge\; t, \qquad A(p) \subseteq R_{\sigma(p)},\ |A(p)| = \lambda,$$
subject to all capacities. Here $t$ is a quality threshold, and the optimum is found by searching over $t$. The difficulty comes from one requirement: all $\lambda$ reviewers of a paper must come from the same pool. That requirement breaks the network-flow structure that makes the flat problem polynomial.
We claim three things. First, the joint problem is NP-hard even with $\lambda = 2$, while each tier taken alone is polynomial. Second, the canonical pipeline is exactly optimal whenever $k=0$. That pipeline is a capacitated editor matching on paper–editor fit, followed by a per-pool max-flow at threshold $t$. Third, the joint problem is solvable in time $f(k)\cdot\text{poly}(|P|,|R|)$. This is a "distance from triviality" parameterization in the spirit of Yeo et al.'s above-lower-bound analysis of minimum profile, which measures how far an instance sits from a guaranteed baseline. We borrow that style of parameter. We do not borrow its problem.
Relation to Prior Work
Three single-tier lines of work motivate the gap. PeerReview4All maximizes the worst-off paper's expertise with incremental max-flow over a flat reviewer pool. Greedy Reviewer Round Robin and recursively balanced picking sequences (Fair Allocation Problems in Reviewer Assignment) enforce envy-freeness up to one reviewer, also over one flat queue. The last of these also frames reviewers as bearing chores. None of the three models an editor who restricts which reviewers a paper may use. We keep PR4A's objective and add the routing tier. At the editor tier, Charlin, Zemel and Boutilier solve a capacitated integer program for papers to Area Chairs on NIPS 2009 and 2010 data. The IEEE TMI feasibility study ranks Associate Editors by embedding and keyword similarity, reaching 53.67% Top-10 accuracy, but with no capacities and no view of reviewer pools. Both treat the editor tier in isolation, which is exactly the decoupling we test.
On the method side, Boehmer and Koana show that fair many-to-one matching with topic "colors" is NP-hard once there are three or more colors. They also show it is fixed-parameter tractable (FPT: exponential cost confined to the parameter) in the number of right-side vertices, using integer programs with few variables. They explicitly leave heterogeneous capacities open. Their hardness result constrains us: editorial boards have dozens of topics, so polynomial exact algorithms are not expected. Their few-variable integer program supplies a secondary result we will pursue. When the number of senior editors is small, as with a handful of area editors at an IEEE Transactions journal, we will treat editors as right-side vertices and papers grouped by eligibility signature as high-multiplicity types. Arbitrary capacities then enter as ordinary linear constraints. This would partly settle their open capacity question in the editorial setting. The bounded-search-tree technique for the main result follows the branching-with-polynomial-residual pattern of Bergren et al., who branch a bounded number of times and hand the remainder to a polynomial solver.
Research Program
The theory has three pieces. The first is a reduction showing NP-hardness of the joint problem from a partition-type problem, with paper-pool compatibility encoding the elements and reviewer loads encoding bin sizes. The second is a lemma showing that when the pipeline fails, some failing paper has a witness: a short alternating chain of editor and reviewer capacity conflicts. The third uses that witness to build a search tree. Each branch reroutes one paper along a witness chain, the depth is bounded by $k$, and the branching factor is bounded by the chain length, which we expect to bound in terms of $k$ and $\lambda$. Every leaf is checked with the polynomial pipeline.
The honest risk is that the branching factor depends on $|E|$. In that case the result becomes FPT only in the combined parameter $k + |E|$, or XP in $k$ (polynomial time for each fixed $k$, with an exponent that grows with $k$). We will report whichever bound we can actually prove. In parallel, we will implement the solver so that it returns, for any instance, either an optimal solution or a proof that $k$ exceeds a budget.
Baselines
The naive reference point is the decoupled pipeline as practiced. Each paper goes to its top-similarity editor, as in the TMI recommender. Reviewers are then assigned within each pool by PR4A. This is what a journal would deploy tomorrow. We will also run a stronger decoupled variant: capacitated editor matching in the style of Charlin et al., followed by per-pool PR4A. If our method beats the naive version but not this one, then the gain comes from editor capacities, not from joint optimization.
The strongest competitor is a monolithic mixed-integer program for the full joint problem, solved by a commercial solver with the same threshold search. It is exact, and on many real instances it may simply be fast. No reported result was found on Lacuna for a joint two-tier integer program. The closest reported numbers concern flat PR4A on ICLR 2018 (911 papers, 2,435 reviewers). There, Stelmakh et al. report that PR4A increased the fairness metric by 25% over TPMS while total similarity dropped by only 2%, and that it takes about 3 hours for 5,000 papers. Flat PR4A, which ignores pools entirely, serves as an upper bound on achievable quality, not as a competitor.
All methods share the same instances and scores. The solver gets the same wall-clock budget as our method and is tuned with default plus one presolve-aggressive setting. Beating the integer program means matching its optimum and either solving the instances it fails to close within budget, or returning optimality certificates in a small fraction of its time, on instances where $k$ is small. The key ablation keeps our search tree but picks rerouted papers at random instead of along witness chains. This isolates whether the structural lemma, rather than generic branching, does the work.
Why not just…?
Why not just run the pipeline and let the editor-in-chief fix bad cases by hand? This is what happens now, and when $k=0$ our theory says it is optimal. The question is how often $k>0$ and how much the worst-off paper loses when it is. The TMI study reports that managing editors still inspect submissions manually, which suggests failures are common, but it gives no measurement. Our experiments supply the gap between pipeline and joint optimum per instance. If that gap is negligible on realistic boards, that is itself the finding, and we will report it as such.
Why not just hand the joint problem to Gurobi? This is the real threat. Assignment programs are often easy in practice, and if the solver closes every realistic instance quickly, the algorithmic contribution shrinks. Two things would remain: the hardness boundary, and the structural explanation of when instances are easy. We will report solve times stratified by measured $k$. The claim survives only if solver time grows with $k$ while our method's time grows more slowly, or if the certificate is useful as a deployable check. We will not count instances built directly from our own reduction as evidence of practical advantage.
Why not just assign reviewers flat with PR4A and then pick the editor whose pool covers the chosen reviewers? This post-hoc routing works when pools overlap heavily, because almost any reviewer set is then covered by some editor. It fails when pools are near-disjoint and editor capacities bind. We will vary pool overlap and report where post-hoc routing violates editor capacity or cannot place a paper's reviewers in a single pool. The same experiment determines which regime real boards occupy.
Proposed Experiments
No public dataset contains both tiers, so instances are semi-synthetic and anchored to real scores. For the editor tier we use paper–Area Chair scores from the NIPS 2009 and 2010 data (1,079 papers × 30 chairs and 1,250 × 48). For the reviewer tier we use ICLR 2018 similarity matrices from PeerReview4All and the CVPR, CVPR'18 and MIDL affinities used by Payan and Zick. We will build editor pools in two ways: by thresholding reviewer similarity to each editor's paper centroid, and by clustering reviewers. Both are swept over overlap levels and editor capacity tightness. The gold-standard expertise dataset shows that similarity models err 36–43% of the time on hard pairs. We will therefore perturb scores at that noise level and check whether the joint optimum's advantage survives score error.
The metrics are worst-off-paper expertise (the max-min objective), the fraction of papers left with fewer than $\lambda$ reviewers above threshold, editor load spread, the price of hierarchy relative to flat PR4A, wall-clock time, and the measured $k$.
The decisive checks are three. The first is the distribution of $k$ on realistic instances. If $k$ is routinely in the hundreds, the parameterization is the wrong lens and we will say so. The second is whether joint optimization raises the worst-off paper's expertise over the capacitated pipeline at moderate pool overlap, the regime where we predict the gap is largest. The third is whether our solver's runtime advantage over the integer program grows with $k$. Together these show whether the editorial hierarchy carries a hidden cost that a small structural quantity both predicts and removes.
References
- PeerReview4All: Fair and Accurate Reviewer Assignment in Peer Review
- Fixed-Parameter Complexity of Minimum Profile Problems
- I Will Have Order! Optimizing Orders for Fair Reviewer Assignment
- Fair Allocation Problems in Reviewer Assignment
- A Framework for Optimizing Paper Matching
- Artificial intelligence-aided assignment of journal submissions to associate editors—a feasibility study on IEEE transactions on medical imaging
- The Complexity of Finding Fair Many-to-One Matchings
- On Covering Segments with Unit Intervals
- A Gold Standard Dataset for the Reviewer Assignment Problem