d4-conf-atal-2018-0077 (d4-conf-atal-2018-0077)

Given a finite locality set \(L\), a finite support \(T\) of family types with strict rankings and one-dimensional demands, a population distribution \(\mu\) over \(T\), per-capita locality capacities \(c_\ell\), and a feasible incumbent allocation \(x_{t,a}\) with \(\sum_a x_{t,a}=\mu_t\), does there exist a feasible reassignment in which every unit of mass strictly improves? Equivalently, do there exist \(z_{t,a,b}\geq 0\) such that \(\sum_b z_{t,a,b}=x_{t,a}\), \(z_{t,a,b}>0\) only if \(b\succ_t a\), and \(\sum_{t,a}d_t z_{t,a,\ell}\leq c_\ell\) for every \(\ell\in L\)?

Let \(\mathcal L\) be a nonempty locality set of size \(m\), and let \(A=\mathcal L\cup\{\varnothing\}\), where \(\varnothing\) means unmatched and consumes no capacity.
A society is given by its support: the list of \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; normalize \(\sum_{t\in T}\mu_t=1\).
Each type \(t\) has a strict ranking \(\succ_t\) over \(A\) and one-dimensional demand \(d_t\in\mathbb Q_{>0}\). Every locality accepts every type; locality priorities play no role.
Locality capacities \(c_\ell\in\mathbb Q_{\geq0}\) are per unit total population. The incumbent \(x\) is a nonnegative binary-rational array satisfying \(\sum_{a\in A}x_{t,a}=\mu_t\) and \(\sum_t d_t x_{t,\ell}\leq c_\ell\).
Mass is divisible. A strict improvement of every unit of incumbent mass is an array \(z_{t,a,b}\in\mathbb R_{\geq0}\), indexed by \(t\in T\) and \(a,b\in A\), satisfying \(\sum_{b\in A}z_{t,a,b}=x_{t,a}\), \(z_{t,a,b}=0\) whenever \(b\not\succ_t a\), and \(\sum_{t\in T}\sum_{a\in A}d_tz_{t,a,\ell}\leq c_\ell\) for every locality.
Feasibility imposes only mass conservation and capacities; individual rationality is not an additional requirement. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).

Is deciding whether such a strict improvement exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

For indivisible families, testing weak Pareto optimality is strongly \(\mathrm{coNP}\)-complete under strict locality preferences, universal locality acceptance, and one-dimensional demands and capacities; thus existence of an improvement strictly benefiting every family is strongly \(\mathrm{NP}\)-complete. [Source](https://www.cse.unsw.edu.au/~haziz/refugee.pdf)
No result settling exactly the divisible-mass decision problem above was located in the literature search.

1. Result

The decision problem is in \(\mathrm P\). A strict improvement exists exactly when a polynomial-size flow network admits a flow saturating all source edges. A conservative running-time bound is \(\mathrm O(L^3+\tau^3m^4L^2)\) bit operations.

The construction uses the explicitly listed \(\tau\) types and permits splitting each incumbent row among several strictly preferred destinations.

2. Integer-capacity network

Write each input rational using its given integer numerator and positive integer denominator. Let \(Q\) be the product of all denominators appearing in the demands \(d_t\), incumbent entries \(x_{t,a}\), and capacities \(c_\ell\). Define

\(w_{t,a}=Qd_tx_{t,a}\), and \(H=\sum_{t\in T}\sum_{a\in A}w_{t,a}\).

These are nonnegative integers: the denominator of \(d_tx_{t,a}\) divides the product of the corresponding two denominator occurrences in \(Q\). Also \(Qc_\ell\) is an integer. Since every demand is positive and total incumbent mass is one, \(H>0\).

Construct a directed network with source \(s\), sink \(r\), a row vertex \(u_{t,a}\) for every pair \((t,a)\), and a destination vertex \(v_b\) for every \(b\in A\). Its edges and capacities are:

• \(s\to u_{t,a}\), with capacity \(w_{t,a}\).
• \(u_{t,a}\to v_b\), with capacity \(w_{t,a}\), precisely when \(b\succ_t a\).
• \(v_\ell\to r\), with capacity \(Qc_\ell\), for each locality \(\ell\).
• \(v_{\varnothing}\to r\), with capacity \(H\).

There are no other edges. The unmatched edge imposes no effective restriction, since total source capacity is \(H\).

The algorithm answers yes precisely when the maximum-flow value equals \(H\).

3. Equivalence proof

*An improvement yields a flow of value \(H\).*

Suppose \(z\) satisfies the improvement constraints. Set

\(f(s,u_{t,a})=w_{t,a}\), and \(f(u_{t,a},v_b)=Qd_tz_{t,a,b}\)

on the edges present in the network. Send each destination vertex’s total incoming flow to the sink.

The preference condition ensures that every positive transfer uses an existing edge. At each row vertex, conservation follows from

\(\sum_{b\in A}Qd_tz_{t,a,b}=Qd_tx_{t,a}=w_{t,a}\).

Nonnegativity and row conservation imply \(z_{t,a,b}\leq x_{t,a}\), so every row-to-destination edge respects its capacity. For each locality,

\(f(v_\ell,r)=Q\sum_{t,a}d_tz_{t,a,\ell}\leq Qc_\ell\).

The unmatched destination receives at most the total flow \(H\). Thus the constructed flow is feasible and has value \(H\).

*A flow of value \(H\) yields an improvement.*

Conversely, suppose \(f\) is a feasible flow of value \(H\). The source’s outgoing capacities sum to \(H\), and it has no incoming edges. Therefore every source edge is saturated: otherwise their total flow would be strictly less than \(H\).

For each existing row-to-destination edge define

\(z_{t,a,b}=\frac{f(u_{t,a},v_b)}{Qd_t}\),

and set all other entries to zero. This division is valid because \(Qd_t>0\).

Conservation at each row vertex gives

\(\sum_{b\in A}z_{t,a,b}=\frac{f(s,u_{t,a})}{Qd_t}=\frac{w_{t,a}}{Qd_t}=x_{t,a}\).

Every positive entry satisfies \(b\succ_t a\), by the edge construction. Finally, conservation at each locality destination gives

\(\sum_{t,a}d_tz_{t,a,\ell}=\frac{f(v_\ell,r)}{Q}\leq c_\ell\).

Consequently \(z\) satisfies every required constraint.

This proves the equivalence, including for improvements originally allowed to have arbitrary real entries. In fact, an integer maximum flow supplies a rational improvement whenever one exists.

4. Running time and bit complexity

The network has

\(V=\tau(m+1)+m+3=\mathrm O(\tau m)\)

vertices and at most

\(E=\tau(m+1)+\frac{\tau m(m+1)}2+m+1=\mathrm O(\tau m^2)\)

edges. The middle term counts the strictly ordered pairs in each type’s ranking.

Dinic’s algorithm computes a maximum flow in \(\mathrm O(V^2E)\) arithmetic and graph operations, independently of capacity magnitudes; see these [Charles University lecture notes](https://kam.mff.cuni.cz/~hubicka/2020/adsII-3.pdf). Here its hypotheses hold: the network is finite and directed, and all capacities are nonnegative integers. The resulting operation count is \(\mathrm O(\tau^3m^4)\).

The sum of the binary lengths of the input denominators is at most \(L\), so \(Q\) has \(\mathrm O(L)\) bits. Every scaled capacity also has \(\mathrm O(L)\) bits. Summing the \(\tau(m+1)\) row supplies adds at most \(\mathrm O(\log(\tau(m+1)))=\mathrm O(L)\) bits, so \(H\) has \(\mathrm O(L)\) bits as well. Integer flows, residual capacities, and intermediate flow values therefore remain of polynomial bit length.

Using elementary integer arithmetic, denominator clearing and network construction take at most \(\mathrm O(L^3+\tau m^2L^2)\) bit operations. Charging conservatively \(\mathrm O(L^2)\) per flow-algorithm operation yields the stated total bound

\(\mathrm O(L^3+\tau^3m^4L^2)\).

5. Why indivisible hardness does not transfer

The [cited paper](https://www.cse.unsw.edu.au/~haziz/refugee.pdf) concerns indivisible families. An integer flow here represents integer units of *scaled demand*, and a single incumbent row may send such units to several destinations. Recovering mass by division by \(Qd_t\) preserves that splitting. Thus flow integrality does not impose indivisibility of families.

The divisible decision problem is therefore polynomial-time solvable; an \(\mathrm{NP}\)-hardness result for this same problem would imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem correctly: deciding whether a strict improvement exists is in \(\mathrm P\). The flow equivalence and the stated bit-complexity bound are valid. No major or minor mathematical issues were found.

• Denominator clearing is valid. The product \(Q\) includes every denominator occurrence in the demands, incumbent entries, and capacities. Consequently, the denominator of each product \(d_tx_{t,a}\) divides \(Q\), even when the two factors have common denominator factors. Thus all \(w_{t,a}\) and \(Qc_\ell\) are nonnegative integers. Positive demands and normalized incumbent mass imply \(H>0\).

• The network represents the required constraints exactly. Each incumbent row has its own supply vertex, and its outgoing edges represent precisely its strictly preferred destinations. This preserves the requirement that every unit of every positive incumbent row strictly improves. Scaling mass by its type’s demand makes locality inflows measure capacity consumption. The unmatched destination’s capacity \(H\) imposes no restriction because total source supply is \(H\). Its incoming edges still enforce strict preference; unmatched is not assumed to be worst.

• An improvement produces a feasible saturating flow. The proposed assignment satisfies row conservation. Nonnegative transfers summing to \(x_{t,a}\) individually cannot exceed \(x_{t,a}\), so the row-edge capacities are respected. Locality capacities follow directly after multiplication by \(Q\). The argument applies to arbitrary real improvements and does not assume rationality.

• A saturating flow produces an improvement. Since the source has no incoming edges and its outgoing capacities sum to \(H\), a flow of value \(H\) saturates every source edge. Division by \(Qd_t\) is valid for every type. Row conservation then recovers exactly \(x_{t,a}\); the edge set enforces strict improvement; and destination conservation recovers the locality capacity inequalities. No additional individual-rationality restriction is introduced.

• The construction handles the relevant edge cases. Zero incumbent rows have zero supply and yield zero transfers. A positive row already at its type’s highest-ranked alternative has no outgoing preference edge and prevents saturation, as required. Zero locality capacities prohibit positive transfers into those localities. These cases require no separate modification of the proof.

• Network size and the max-flow theorem are correct. The vertex count is exact. A strict ranking on \(m+1\) alternatives has \(m(m+1)/2\) strictly ordered pairs, giving the stated edge count. Since \(m,\tau\geq1\), the bounds \(V=\mathrm O(\tau m)\) and \(E=\mathrm O(\tau m^2)\) hold. The cited theorem guarantees a maximum flow in \(\mathrm O(V^2E)\) operations; its finite directed-network and nonnegative-capacity hypotheses hold here. The cited algorithm also preserves integer flows when started from zero with integer capacities. [Charles University lecture notes](https://kam.mff.cuni.cz/~hubicka/2020/adsII-3.pdf)

• The bit-complexity accounting is valid. Although \(Q\) can have large numerical magnitude, its binary length is \(\mathrm O(L)\). Each scaled capacity likewise has \(\mathrm O(L)\) bits, and summing the explicitly represented row supplies preserves that bound. The elementary-arithmetic construction bound is conservative. Substituting the network sizes into the max-flow bound and charging \(\mathrm O(L^2)\) per operation gives the claimed

\[ \mathrm O(L^3+\tau^3m^4L^2) \]
bit operations, polynomial in the explicit input size.

• The indivisible-hardness discussion is consistent. Integer flow units represent scaled demand, and a row may split those units across destinations. Flow integrality therefore does not enforce indivisible families. The cited paper’s hardness statement concerns the indivisible setting and does not contradict this algorithm. [Refugee allocation paper, Proposition 7.2](https://www.cse.unsw.edu.au/~haziz/refugee.pdf)

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩