| paper | Fairly Allocating Contiguous Blocks of Indivisible Items |
| authors | Warut Suksompong |
| venue | SAGT 2017 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Threshold feasibility is in \(\mathrm P\). The exact minimum \(\varepsilon\) and an attaining rational mass assignment can be computed, or global infeasibility reported, in time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite set of complete types \(T\), masses \(\mu_t\), and a prescribed single-line high-multiplicity expansion with per-capita capacities \(q_j\) and utilities \(u_t(j)\), let \(B\) range over integral intervals of the common physical line. Find \(x_{t,B}\ge 0\) and minimum \(\varepsilon\) satisfying \(\sum_B x_{t,B}=\mu_t\), \(\sum_{t,B:j\in B}x_{t,B}=q_j\), and \(u_t(B)\ge p_t-\varepsilon h_t\) whenever \(x_{t,B}>0\), where \(p_t=\sum_j q_j u_t(j)\) and \(h_t=\max_j u_t(j)\). The finite realization has \(N\mu_t\) agents and \(Nq_j\) capacities on one common line; the task is to compute the mass assignment or approximate the optimum.
A common-line high-multiplicity mass-assignment LP with type masses \(\mu_t\), whole contiguous blocks \(B\), physical overlap constraints, and minimum normalized proportionality shortfall.
The stated catalogue LP does not by itself encode a single physical line: overlapping catalogue intervals can consume different copies without specifying their placement, so the claimed \(O(m^2)\) formulation and exact bridge require \(B\) to range over intervals of an explicitly expanded common line.
fatal: False
The mirror covers Theorem 1's constructive approximate-proportionality guarantee and its running-time result. It leaves Theorem 2, the envy-freeness results, and the price-of-fairness bounds unmirrored.
The strongest honest case is a qualified yes, led by Theorem 1. I would not claim that every result in the paper has a useful population limit, but Theorem 1 has a natural high-multiplicity interpretation.
The relevant anchor is Theorem 1, proved in this paper. It states that for every instance there is a contiguous allocation \(M\) such that, for every agent \(i\), \(u_i(M_i)\ge \frac{1}{n}u_i(M)-\frac{n-1}{n}u_{i,\max}\). Hence a contiguous \(u_{\max}\)-proportional allocation always exists. The proof gives a left-to-right allocation algorithm, and the paper states that it runs in \(\Theta(mn)\) time, which is optimal up to constants because the input itself has size \(\Theta(mn)\).
My mirror is Mass-Contiguous Approximate Proportionality\(_\infty\).
An instance contains an ordered catalogue of item positions \(J=\{1,\ldots,m\}\), a finite set of complete agent types \(T\), type masses \(\mu_t\) with \(\sum_t\mu_t=1\), nonnegative utilities \(u_t(j)\), and a per-capita supply \(q_j\) of item position \(j\). The supply modification is necessary: with a literal finite stock of \(m\) indivisible items, a continuum of agents would be degenerate. In a finite \(N\)-agent realization, \(N\mu_t\) agents have type \(t\), and \(Nq_j\) integral copies of position \(j\) are available. Each individual still receives an integral contiguous block; only the population counts are fractional in the limit.
Let \(\mathcal B\) be the set of integral intervals \(B=[a,b]\subseteq J\). The decision variable \(x_{t,B}\) is the mass of type \(t\) receiving block \(B\). It must satisfy \(\sum_Bx_{t,B}=\mu_t\) for every \(t\), and \(\sum_{t,B:j\in B}x_{t,B}=q_j\) for every item position \(j\). Thus \(x\) is a mass assignment to whole contiguous bundles, not a fractional allocation of an item.
The type-\(t\) proportional benchmark is \(p_t=\sum_jq_ju_t(j)\), since this is the proportional share in the corresponding finite realization. Put \(h_t=\max_j u_t(j)\). The problem is to find \(x\) minimizing the worst normalized shortfall
\[ \varepsilon(x)=\max_{t,B:x_{t,B}>0}\frac{(p_t-u_t(B))_+}{h_t}. \]
Equivalently, given \(\varepsilon\), decide whether every type’s mass can be assigned to integral contiguous blocks satisfying \(u_t(B)\ge p_t-\varepsilon h_t\). A solution is the mass assignment \(x\), together with its value \(\varepsilon\).
This is recognizably the authors’ problem: the utility vectors, indivisibility, additive valuation, contiguity, and proportional-share guarantee are unchanged. The only new ingredient is that agents with the same complete type are represented by mass and may be distributed over several integral blocks. That is exactly the high-multiplicity interpretation of their allocation problem, not a change to outcome-space continuity.
The natural regime is a very large collection of research teams, retailers, or office groups being assigned contiguous units along a long ordered site. There may be millions of groups but only a modest number \(\tau\) of valuation archetypes: for example, teams with the same preferences for proximity to laboratories, entrances, sunlight, or transport. Item supply grows with the population, while each office or retail unit remains indivisible. The paper’s examples of offices, retail units, and conference slots make this scenario plausible, even if the paper’s motivating stories themselves do not all have high multiplicity.
I expect this mirror to be Class A. For explicit \(m\), there are only \(O(m^2)\) contiguous blocks. For any fixed \(\varepsilon\), discard the type-block pairs violating \(u_t(B)\ge p_t-\varepsilon h_t\), then test the remaining linear feasibility system in the variables \(x_{t,B}\). The optimal \(\varepsilon\) can be found by testing the finitely many thresholds \((p_t-u_t(B))_+/h_t\). Thus the mass problem is polynomial in \(m\), \(\tau\), and the encoding length, and its dependence is on the number of types rather than on the number of agents. Theorem 1 suggests the substantive conjecture \(\varepsilon^\star\le 1\), while the continuous formulation gives a way to compute the best possible guarantee and to study when the theorem’s bound improves.
The bridge is exact for rational high-multiplicity instances: if \(x_{t,B}=k_{t,B}/N\), then \(k_{t,B}\) is the number of type-\(t\) agents receiving block \(B\). Conversely, scaling a rational mass solution produces a finite allocation. This gives both downward approximation information for large finite instances and an upward test of whether the continuous guarantee is genuinely stronger.
The paper’s Theorem 2 is also suggestive—it proves, here, that a contiguous \(u_{\max}\)-equitable allocation exists even for a prescribed agent order, with an \(O(n^2m^4)\) algorithm—but I would not use it as a second anchor. Prescribed individual order is awkward to continuize without adding another ordering variable, and the proportionality mirror already makes the positive case cleanly.
The weakest point is the per-capita supply modification. A referee could say that the paper studies one line containing one copy of each item, whereas my mirror uses a high-multiplicity supply of ordered slots. That objection is serious, but a literal continuum of agents with fixed finite item stock is not a meaningful limit: almost all agents would receive nothing. Scaling the item supply is therefore forced by the population continuization, and it is explicitly the kind of co-modification the programme permits. The mirror preserves the essential features—integral bundles, additive utilities, contiguity, and individual-level fairness for every mass unit—while making the high-multiplicity regime explicit.
The proponent’s mirror has a real defect, but it does not support the universal negative claim.
The strongest objection is that the proposed \(x_{t,B}\)-LP does not actually preserve the paper’s defining object: one fixed line whose items are partitioned into disjoint contiguous blocks. With \(Nq_j\) copies of position \(j\), the model specifies only how many copies of each label are used. It does not specify where those copies lie on a line. Consequently, two overlapping catalogue intervals may be assigned to different population masses without consuming the same physical item. That is feasible in the LP, but not necessarily in the paper’s model.
There is a sharp dichotomy. If the \(Nq_j\) copies are placed on independent lines, contiguity becomes local to separate lines and the paper’s single-line constraint has disappeared. If they are placed on one long line, a bundle must be an interval of that expanded line, so the variables must range over intervals of length \(\sum_j Nq_j\), not merely over the \(O(m^2)\) intervals of the original catalogue. The claimed exact rational bridge therefore holds only after adding a substantial placement convention, and that convention changes the problem.
Keeping the original finite line does not repair matters. With \(m\) fixed and \(N\to\infty\), only \(m\) agents can receive nonempty bundles. Normalized population mass receiving anything therefore tends to zero; if item supply is normalized per capita, the proportional benchmark also tends to zero. The limit is either infeasible at exact fairness or vacuous at approximate fairness. To avoid this, one must scale the number of item positions with the population, which introduces a second growing object—the line itself.
There is also a formal anchor problem. Theorem 1 is an existence theorem with a greedy procedure, not a theorem classifying a named decision or optimization problem. Its \(\Theta(mn)\) running-time statement describes that procedure; the paper’s cited NP-hardness results are not proved in this paper. The proposed continuous optimization additionally changes the objective: it minimizes a type-normalized best shortfall \(\varepsilon\), whereas Theorem 1 only guarantees the existence of an allocation with additive error bounded by \(u_{\max}\). Thus the LP is an interesting new fair-division problem, but it is not clearly a continuization of the theorem’s computational result.
The proponent’s appeal to per-capita supplies cannot simply be dismissed: the programme expressly permits that co-modification. Nor is repeated utility type an illegitimate assumption. The difficulty is narrower: per-capita supply alone does not say how indivisible copies retain the paper’s common-line geometry.
A determined author could rescue the idea by studying \(N\) agents, a single line of \(L_N=\Theta(N)\) indivisible positions, and finitely many periodic or otherwise repeated utility types. That would be a legitimate continuous-population problem, and I cannot honestly claim it has no value. But it is a new long-line/high-multiplicity model, not the proponent’s stated catalogue-capacity LP and not a faithful limit of the paper’s fixed-line theorem.
So the best negative verdict is qualified: reject the proposed mirror as currently formulated, and note that the paper has no strong named complexity anchor. But I cannot honestly defend the stronger claim that no worthwhile continuous mirror exists in any scenario. Under the programme’s permissive co-modification rule, a carefully designed growing-line model 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.