Fairly Allocating Contiguous Blocks of Indivisible Items (d4-conf-sagt-2017-0008)

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 society is given by its support: a list \(T\) of \(\tau\) complete utility types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input specifies one fixed ordered line \(M=\{1,\ldots,m\}\), with \(m\ge1\), nonnegative binary-rational per-capita capacities \(q_j\), and nonnegative binary-rational additive utilities \(u_t(j)\). No utility normalization or ordering of recipients is imposed.
Let \(\mathcal B=\{\varnothing\}\cup\{\{a,a+1,\ldots,b\}:1\le a\le b\le m\}\), \(u_t(B)=\sum_{j\in B}u_t(j)\), \(p_t=\sum_jq_ju_t(j)\), and \(h_t=\max_ju_t(j)\).
For \(\varepsilon\ge0\), a mass assignment consists of \(x_{t,B}\ge0\) satisfying \(\sum_{B\in\mathcal B}x_{t,B}=\mu_t\), \(\sum_{t,B:j\in B}x_{t,B}=q_j\), and \(x_{t,B}>0\Rightarrow u_t(B)\ge p_t-\varepsilon h_t\). These are the complete feasibility conditions; no additional finite-realization constraint is imposed.
The optimization problem minimizes \(\varepsilon\), reporting infeasibility when no assignment exists. Let \(L\) be the total binary input length, including any supplied threshold.

Is deciding whether a mass assignment exists for a supplied nonnegative rational threshold \(\varepsilon\) in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard? What is the corresponding complexity of computing the minimum \(\varepsilon\) and an attaining assignment?

For \(n\) discrete agents and \(m\) indivisible items, a contiguous partition giving every agent \(i\) utility at least \(u_i(M)/n-(n-1)\max_j u_i(j)/n\) can be found using \(\Theta(mn)\) arithmetic operations; this universal additive guarantee is tight ([Suksompong](https://arxiv.org/pdf/1707.00345)).
The literature search identified no result addressing exactly the mass-assignment problem defined above.

Result

Threshold feasibility is in \(\mathrm P\). The exact minimum \(\varepsilon\), together with an attaining rational mass assignment, can also be computed in time polynomial in \(m,\tau,L\), or infeasibility can be reported.

The proof uses precisely the stated mass-assignment conditions. In particular, it imposes no integrality or finite-realization requirement.

1. A polynomial-size linear program for a fixed threshold

The number of permitted bundles is

\(\displaystyle K:=|\mathcal B|=1+\frac{m(m+1)}2.\)

Fix the supplied rational threshold \(\varepsilon\ge0\). For each type \(t\), compute its admissible bundles

\(\displaystyle \mathcal A_t(\varepsilon):=\{B\in\mathcal B:u_t(B)\ge p_t-\varepsilon h_t\}.\)

Introduce a variable \(x_{t,B}\) only for \(B\in\mathcal A_t(\varepsilon)\), and consider the following rational linear feasibility problem:

\(\displaystyle \sum_{B\in\mathcal A_t(\varepsilon)}x_{t,B}=\mu_t\qquad(t\in T),\)

\(\displaystyle \sum_{t\in T}\ \sum_{\substack{B\in\mathcal A_t(\varepsilon)\\j\in B}}x_{t,B}=q_j\qquad(j\in M),\)

\(\displaystyle x_{t,B}\ge0\qquad(t\in T,\ B\in\mathcal A_t(\varepsilon)).\)

An empty sum is interpreted as zero, so a type with no admissible bundle makes this system infeasible because \(\mu_t>0\).

Equivalence. Given a feasible mass assignment, every inadmissible coordinate must be zero: otherwise the utility implication in the definition would fail. Its remaining coordinates therefore satisfy this linear program. Conversely, extend any feasible solution of the linear program by zero on every inadmissible pair. The resulting assignment satisfies both sets of equalities, nonnegativity, and the utility implication.

There are at most \(\tau K\) variables and \(\tau+m\) equality constraints, in addition to nonnegativity. The equality matrix has entries in \(\{0,1\}\), and its right-hand side consists of the input masses and capacities.

We use the standard exact rational linear-programming theorem: feasibility of an explicitly represented rational linear system is decidable in polynomial bit time, and a rational feasible point can be returned when one exists. The theorem allows equalities and lower-dimensional feasible sets; see the polynomial-time feasibility result in [MIT’s linear-programming lecture notes](https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/60dd52896e183e2c60bfe40e076d83d3_MIT15_083JF09_lec10.pdf). The required representation and bit-length bounds are verified in Section 3.

This proves polynomial-time threshold feasibility.

2. Exact optimization over finitely many breakpoints

First consider a type with \(h_t=0\). Nonnegativity of utilities implies \(u_t(j)=0\) for every item. Consequently, \(p_t=u_t(B)=0\), and every bundle is admissible at every nonnegative threshold.

For a type with \(h_t>0\), define, for every bundle,

\(\displaystyle c_{t,B}:=\max\left\{0,\frac{p_t-u_t(B)}{h_t}\right\}.\)

For every \(\varepsilon\ge0\), rearranging the utility inequality gives the exact equivalence

\(\displaystyle B\in\mathcal A_t(\varepsilon)\quad\Longleftrightarrow\quad\varepsilon\ge c_{t,B}.\)

Thus each type–bundle pair becomes admissible at one rational breakpoint, including the breakpoint itself.

Form the finite set

\(\displaystyle S:=\{0\}\cup\{c_{t,B}:t\in T,\ h_t>0,\ B\in\mathcal B\},\)

and sort its distinct elements as

\(\displaystyle 0=s_0<s_1<\cdots<s_r.\)

Its cardinality is at most \(1+\tau K\).

Detecting global infeasibility. At \(s_r\), every bundle is admissible for every type. Therefore, if the linear program at \(s_r\) is infeasible, no assignment can exist at any threshold: increasing the threshold cannot admit any further bundle.

Locating the optimum. Otherwise, let \(s_k\) be the smallest feasible element of \(S\). Feasibility is monotone in the threshold, because increasing it only adds admissible variables. Hence \(s_k\) can be found by binary search.

To prove that \(s_k\) is the minimum over all nonnegative real thresholds, take any \(\varepsilon<s_k\). Let \(s_i\) be the largest element of \(S\) with \(s_i\le\varepsilon\); it exists because \(0\in S\). For each type–bundle pair with positive \(h_t\), its breakpoint belongs to \(S\), so

\(\displaystyle c_{t,B}\le\varepsilon\quad\Longleftrightarrow\quad c_{t,B}\le s_i.\)

Types with zero \(h_t\) admit all bundles at both thresholds. Thus the linear programs at \(\varepsilon\) and \(s_i\) have exactly the same admissible coordinates. Since \(s_i<s_k\), the latter is infeasible by the choice of \(s_k\). Therefore \(\varepsilon\) is infeasible as well.

It follows that

\(\displaystyle \varepsilon^\star=s_k.\)

The linear program at \(s_k\) returns an attaining assignment. The inclusive utility inequality ensures attainment at the breakpoint itself.

3. Bit complexity and output size

All preprocessing uses exact rational arithmetic.

For each type, prefix sums compute every interval utility from

\(\displaystyle U_t(b):=\sum_{j=1}^{b}u_t(j),\qquad u_t(\{a,\ldots,b\})=U_t(b)-U_t(a-1),\)

with \(U_t(0)=0\). Computing \(p_t\), \(h_t\), all interval utilities, and all breakpoints requires polynomially many arithmetic operations.

These operations also have polynomial bit cost. A sum of at most \(m\) rationals can be represented using the product of their denominators as a common denominator. Its bit length is bounded by the sum of the operand bit lengths, together with a logarithmic allowance for addition. The products \(q_ju_t(j)\) have bit lengths bounded by the sum of their input bit lengths. Consequently, every \(p_t\), interval utility, and breakpoint has bit length polynomial in \(m,L\). Division occurs only when \(h_t>0\), and preserves polynomial bit length.

Admissibility tests and breakpoint comparisons are exact rational comparisons, computable by integer cross-multiplication. Sorting polynomially many breakpoints therefore takes polynomial bit time.

Each explicitly constructed linear program has at most \(\tau K\) variables, polynomially many matrix entries, and rational right-hand sides of input-bounded bit length. Thus its complete encoding length is polynomial in \(m,\tau,L\), satisfying the hypotheses of the rational linear-programming theorem.

Finally, every feasible coordinate satisfies \(0\le x_{t,B}\le\mu_t\), by nonnegativity and its type equality. The exact linear-programming algorithm returns a rational feasible solution of polynomial encoding length. Extending it by zeros produces at most \(\tau K\) output coordinates.

Optimization uses one feasibility test at the largest breakpoint, \(O(\log(2+\tau K))\) tests to locate the first feasible breakpoint, and a final solution-producing call if needed. Its total bit running time is polynomial in \(m,\tau,L\).

4. Complexity conclusion

The fixed line has only quadratically many intervals, and the input explicitly lists the \(\tau\) supported types. These facts give a polynomial-size formulation directly. The discrete contiguous-partition guarantee is not needed for this argument.

Threshold feasibility belongs to \(\mathrm P\); consequently, it cannot be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions unless \(\mathrm P=\mathrm{NP}\). Exact optimization and construction of an attaining assignment are polynomial-time function problems.

⟨structured verdict parsed — rendered above⟩

The argument establishes polynomial-time threshold feasibility and polynomial-time exact optimization with an attaining rational assignment. There is one minor quantifier omission in the optimality argument; no major mathematical issue was found.

• Bundle enumeration and LP formulation are correct.

The count \(\displaystyle K=1+\frac{m(m+1)}2\) includes the empty bundle and every nonempty interval exactly once. Hence there are at most \(\tau K\) type–bundle coordinates.

The stated LP is equivalent to the task’s feasibility conditions in both directions. An inadmissible coordinate must vanish in any feasible assignment, and extending an LP solution by zeros preserves the mass equalities, capacity equalities, nonnegativity, and utility implication. No additional constraint is introduced.

The empty-admissible-set case is correctly handled: its type equality becomes \(\displaystyle 0=\mu_t\), which is impossible because \(\mu_t>0\).

• The polynomial-time LP theorem applies.

The prover explicitly states the standard theorem for feasibility and construction of a rational feasible point for an explicitly represented rational linear system. Its application permits equalities and lower-dimensional feasible sets.

The cited [MIT lecture notes](https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/60dd52896e183e2c60bfe40e076d83d3_MIT15_083JF09_lec10.pdf) discuss arbitrary polyhedra and polynomial precision, beyond the preliminary full-dimensional formulation. Their integer-data formulation is compatible with the rational-data theorem stated by the prover.

The LP here has rational input data, polynomially many variables and constraints, and polynomial encoding length. No theorem hypothesis is left materially unverified.

• The breakpoint construction is correct, including zero utilities.

If \(h_t=0\), nonnegative utilities force every item utility to vanish. Thus \(p_t=u_t(B)=0\), and every bundle is admissible for every permitted threshold.

If \(h_t>0\), division by \(h_t\) is valid. For \(\varepsilon\ge0\), the stated equivalence
\[ \text{ } \]
is correctly expressed by the prover as \(\displaystyle B\in\mathcal A_t(\varepsilon)\Longleftrightarrow\varepsilon\ge c_{t,B}\). Clamping the breakpoint to zero handles bundles whose utility already meets or exceeds \(p_t\).

The set \(S\) is finite, rational, nonempty, and has the claimed cardinality bound.

• Global infeasibility detection and monotonicity are correct.

At the largest breakpoint, every positive-\(h_t\) pair is admissible; every zero-\(h_t\) pair was already admissible. Consequently, infeasibility there implies infeasibility at every threshold.

Adding admissible coordinates preserves previous feasible assignments by assigning zero to the new coordinates. This proves the monotonicity needed for binary search.

The singleton case \(S=\{0\}\), including the case where all utilities vanish, is covered by the same procedure.

• The optimum and attainment arguments are substantively correct.

For a nonnegative threshold below the first feasible breakpoint, the preceding breakpoint exists and has exactly the same admissible coordinates. Its infeasibility therefore establishes infeasibility of that threshold. Feasibility at the first feasible breakpoint establishes both optimality and attainment.

Minor issue: The sentence “take any \(\varepsilon<s_k\)” omits the restriction \(\varepsilon\ge0\). Taken literally, the following claim that a preceding element of \(S\) exists is false for negative \(\varepsilon\), since every element of \(S\) is nonnegative. This does not affect the intended optimization domain.

Minimum clarification: Restrict that sentence to \(\displaystyle 0\le\varepsilon<s_k\). When \(s_k=0\), there are no thresholds in this range.

• Bit complexity, output size, and the final classification are correct.

The arithmetic uses polynomially many operations on rationals of polynomial bit length. Products, finite sums, subtraction, and division by a nonzero rational have the claimed bounds. Exact comparisons and sorting therefore have polynomial bit cost.

The explicitly represented LPs have polynomial encoding length. The invoked exact LP theorem supplies a rational feasible point of polynomial encoding length; coordinate boundedness alone is not being used to establish that bit-length claim.

The stated number of LP calls is polynomial, and extending an assignment by zeros yields polynomially many output coordinates. The qualification concerning \(\mathrm{NP}\)-hardness unless \(\mathrm P=\mathrm{NP}\) is correct.

⟨structured verdict parsed — rendered above⟩