| paper | Locally Fair Partitioning |
| authors | Pankaj K. Agarwal, Shao-Heng Ko, Kamesh Munagala, Erin Taylor |
| venue | AAAI 2022 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 10
Given \(\tau\) ordered run-types on \([0,1]\), each with rational party label \(p_j\in\{R,B\}\), support interval \(I_j\), and mass \(\mu_j\) with \(\sum_j\mu_j=1\), together with \(k,\varepsilon,\beta\), decide whether there is a consecutive partition \(\Pi\) into intervals of mass in \([(1-\varepsilon)/k,(1+\varepsilon)/k]\) such that no allowable interval \(D\) has unhappy mass \(u_p(D,\Pi)>\max\{|D|/2,\beta/k\}\) for either party \(p\), and construct \(\Pi\) when one exists.
A piecewise-constant spatial population measure whose finite type table stores \(p_j\), ordered support \(I_j\), and mass \(\mu_j\); decision variables are district boundaries, and the objective is feasibility under majority labels, tie-to-blue convention, population balance, and local deviation constraints.
The mirror requires spatial support and order to be part of the run-type representation, and the polynomial-size representation of continuous dynamic-programming states is entirely unproved.
fatal: False
The mirror covers Theorem 10's feasibility and construction problem, while leaving the existence thresholds and clustered-instance results in Theorems 3–8 unmirrored.
My strongest case is narrow: the paper has one qualifying computational anchor, Theorem 10, proved in this paper. It states that, given \(X\), \(\sigma\), \(\varepsilon\), and \(\beta\), one can compute an \((\varepsilon,\beta)\)-locally fair partition or report that none exists in time \(O(n\sigma^3)\) for \(\varepsilon<1/3\) and \(O(n\sigma^4)\) for \(\varepsilon\in[1/3,1/2]\). Theorems 3–8 are important existence results, but they are not hardness or complexity classifications, so I would not count them as additional anchors.
The mirror I would propose is Run-Type Continuous Local-Fair Partition, written \(\mathrm{CLFP}_{\infty}\). Consider a one-dimensional jurisdiction represented by \([0,1]\), in cumulative population order. The population consists of \(\tau\) ordered spatial run-types \(t_1,\ldots,t_\tau\). Type \(t_j\) has party \(p_j\in\{R,B\}\), occupies a consecutive interval \(I_j\), and has mass \(\mu_j=|I_j|\), with \(\sum_j\mu_j=1\). All endpoints and masses are rational. A type includes its party and its ordered spatial block; agents inside one block have no further attributes used by the problem and their mass may be divided fractionally by a district boundary.
The intended regime is a large population of \(N\) voters formed by multiplying these masses: block \(j\) contains approximately \(N\mu_j\) voters. Think of a long corridor, chain of precincts, or geographically ordered set of large neighbourhoods, where each neighbourhood is politically homogeneous or nearly so. There may be millions of voters but only \(\tau\) relevant run-types, with \(\tau\) perhaps in the tens or hundreds. This is not an arbitrary reinterpretation of the paper: its clustered-input section already treats long monochromatic runs as a meaningful beyond-worst-case regime. The high-multiplicity claim is that the individuals inside a run are interchangeable for the paper’s own model.
Given \(k\), put \(\rho=1/k\). A solution is a finite partition \(\Pi=(\pi_1,\ldots,\pi_q)\) of \([0,1]\) into consecutive intervals such that every district has mass in \([(1-\varepsilon)\rho,(1+\varepsilon)\rho]\). The number \(q\) is allowed to vary exactly as in the paper’s relaxed model. A district’s party is its strict majority party, with ties assigned to blue. A point of mass is happy when its party agrees with the majority party of its district.
For any interval \(D\subseteq[0,1]\), let \(u_R(D,\Pi)\) and \(u_B(D,\Pi)\) be the red and blue mass in \(D\) whose assigned district has the opposite majority. The interval \(D\) is a \(\beta\)-deviating group if
\[ |D|\in[(1-\varepsilon)\rho,(1+\varepsilon)\rho] \]
and, for at least one party \(p\),
\[ u_p(D,\Pi)>\max\left\{\frac{|D|}{2},\beta\rho\right\}. \]
The decision problem is: output such a partition \(\Pi\), or certify that none exists. This is exactly the paper’s local-core notion with integer voter counts replaced by divisible population mass. The computational target would be polynomial time in \(\tau+k\) and the rational encoding length \(L\), with \(k\) explicitly bounded or the output represented succinctly.
I expect \(\mathrm{CLFP}_{\infty}\) to be Class A, although this is a conjectural direction rather than a theorem already proved by the paper. The reason is the structural one behind Theorem 10. An allowable deviating interval has mass at most \((1+\varepsilon)\rho\), while each district has mass at least \((1-\varepsilon)\rho\). Consequently, a deviating interval can intersect only constantly many consecutive districts: at most three when \(\varepsilon<1/3\), and at most four in the paper’s larger-\(\varepsilon\) range. Thus the dynamic-programming state need only remember a constant number of recent district boundaries.
In the continuum, once the run-crossing pattern is fixed, red and blue masses are affine functions of the boundary coordinates. The local “no deviating group” test therefore becomes a finite collection of linear or piecewise-linear inequalities. The natural continuization of the paper’s dynamic program is consequently a reachability computation over rational polyhedral regions of boundary space, rather than enumeration over \(n\) individual voters. The main algorithmic question is whether those reachable regions remain polynomially representable in \(\tau\), \(k\), and \(L\). If they do, the population multiplicity disappears exactly in the way the ChoCo programme seeks.
This mirror covers only Theorem 10. It does not claim to continuize every existential threshold or clustered-instance theorem, and I would not present Theorem 4 as an NP-hardness anchor: its statement is nonexistence of a fair partition on selected instances, not computational hardness. The continuous problem generates several useful follow-up questions: whether the polyhedral dynamic program is genuinely polynomial; whether \(k\) can be compressed when it is much larger than \(\tau\); how much slack is needed to round a continuous solution back to an \(N\)-voter solution; and whether allowing two-dimensional regions turns this into a Class C problem.
The weakest point is that Theorem 10’s stated algorithm is polynomial in \(n\) and \(\sigma\), not in the number of run-types \(\tau\). Replacing integer boundary indices by continuous reachable sets could introduce exponentially many pieces, and nothing in the paper proves that this does not happen. Moreover, if every individual location is treated as a distinct type, then \(\tau\) grows with \(N\) and the high-multiplicity gain disappears. The positive case therefore depends essentially on the clustered run-type regime. I believe that is defensible because it is a regime the paper itself identifies as meaningful, and because the mirror preserves its central objects—population balance, contiguous districts, majority winners, unhappy mass, and justified deviation—rather than simplifying the problem into an unrelated tractable one.
The paper has one genuine anchor: Theorem 10. It is a numbered computational result, so the negative case cannot dismiss the paper for lacking an algorithmic question.
The strongest objection is that the proposed \(\mathrm{CLFP}_{\infty}\) is not actually Theorem 10’s high-multiplicity version. The theorem runs in \(O(n\sigma^3)\) or \(O(n\sigma^4)\) on an explicitly listed binary sequence. The proposed problem asks for time polynomial in \(\tau+k+L\), where the input is a run-length encoding with rational masses. Clearing denominators gives a discrete instance, but it gives no algorithmic correspondence: the paper’s DP enumerates individual boundary indices, whereas the continuous DP must manipulate reachable regions in real boundary space, potentially with exponentially many pieces. Thus “the DP survives with real variables” is a conjecture, not an inherited result.
There is also a fidelity concern. In the original problem, location is part of what determines which deviations are feasible. If a voter type is only “red in run \(j\),” the type mass does not by itself encode adjacency; the proposed model repairs this by giving each type an ordered interval of support. That is no longer an ordinary distribution over finite voter types, but a piecewise-constant spatial population measure. If exact position is instead included in the type, then the number of types grows with the population and the high-multiplicity gain disappears. The best repair is therefore an author-recognisable extension, not a direct mirror.
The paper’s own clustered regime also weakens the motivation. When runs are sufficiently long, Theorem 6 and Corollary 7 already give constructive fair partitions. In the normalized model, those are precisely instances with run masses bounded below by a constant multiple of \(1/k\). To retain a genuinely difficult decision problem, one needs many alternating runs; then \(\tau\) is essentially the number of meaningful spatial events, and the proposed gain is compressed run-length encoding rather than continuization of the population.
Those objections do not, however, defeat the repaired mirror. The objective is aggregate rather than identity-sensitive; deviations retain positive mass because of the \(\beta/k\) threshold; and rational scaling gives a credible finite-population correspondence. A piecewise-constant spatial population is a sensible high-multiplicity regime, even if it is an extension of the paper’s formal model.
So the honest negative verdict is weak. I can reject the proponent’s claim that Theorem 10 directly yields a polynomial continuous algorithm, and I can insist that the proposed problem be labelled a compressed spatial extension. I cannot defend the universal claim that no worthwhile mirror exists: the repaired \(\mathrm{CLFP}_{\infty}\) is a legitimate open computational question, and Theorem 10’s anchor survives.
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.