The Price of Connectivity in Fair Division

The strongest honest positive case is a high-multiplicity mirror of the paper’s Theorem 3.16, proved in this paper. It states that for a star with \(m\) goods and \(n\ge2\) agents,
\[ \operatorname{PoC}(G,n)= \begin{cases} m-n+1,&m\ge n,\\ 1,&m<n, \end{cases} \]
and, when \(m\ge n\), gives a polynomial-time algorithm computing a connected allocation in which every agent receives at least \(1/(m-n+1)\) of her MMS. The theorem’s proof is constructive: choose the \(n-1\) most valuable leaves as singleton bundles and give the remaining goods to the last agent.

I would not use the paper’s concluding remarks about NP-hard envy-free allocation as anchors: those are literature summaries, not numbered hardness results proved here.

The natural regime is a large collection of nearly identical households or research teams receiving connected bundles of offices arranged in a hub-and-spoke building. There are \(Nr\) agents, \(N\) indistinguishable copies of every graph location, and only finitely many utility types. A type \(t\) is a complete additive valuation vector \(u_t(v)\) over the \(m\) locations. A type distribution is \(\mu\), where \(Nr\mu_t\) agents have type \(t\). Thus the population grows with \(N\), while the number of types remains fixed. Each household receives an integral bundle whose occupied locations form a connected set of the star.

The per-capita supply of every location is \(q_v=1/r\): there are \(N\) copies of \(v\) for \(Nr\) agents. This scaling is forced by the high-multiplicity regime. The goods remain indivisible; only the population assignment becomes continuous.

Let \(\mathcal C(G)\) be the connected subsets of \(G\). A continuous allocation is a collection of masses \(x_{t,B}\ge0\), where \(x_{t,B}\) is the fraction of the population of type \(t\) receiving the integral connected bundle \(B\). It satisfies
\[ \sum_{B\in\mathcal C(G)}x_{t,B}=\mu_t \]
for every type \(t\), and
\[ \sum_{t}\sum_{B\ni v}x_{t,B}=q_v \]
for every location \(v\). Rational \(x\) can be implemented exactly by taking \(N\) large enough to clear denominators; conversely, finite replicated allocations converge to such an \(x\).

For a type \(t\), define its high-multiplicity MMS by
\[ \operatorname{MMS}^{\infty}_t(q) = \max_{y} \min_{B:y_B>0}u_t(B), \]
where \(y\) ranges over distributions on arbitrary integral bundles satisfying
\[ \sum_B y_B=1, \qquad \sum_{B\ni v}y_B=q_v. \]
The connected version restricts \(y\) to \(\mathcal C(G)\).

The continuous problem I would hand to a prover is:

\[ \textsc{Star-MMS}_{\infty} \]

Given a star \(S_m\), an integer \(r\), a finite type distribution \(\mu\), and additive valuations \(u_t\), compute the largest \(\alpha\) for which there exists a connected continuous allocation \(x\) satisfying
\[ u_t(B)\ge \alpha\,\operatorname{MMS}^{\infty}_t(q) \]
for every type \(t\) and every bundle \(B\) with \(x_{t,B}>0\), where \(q_v=1/r\). A solution is the mass allocation \(x\) and the optimal value \(\alpha\).

The lead subcase is homogeneous, \(\mu=(1)\), because the paper’s price-of-connectivity quantity itself is defined using one utility function. Its worst-case version asks whether
\[ \operatorname{PoC}^{\infty}(S_m,r) = \sup_u \frac{\operatorname{MMS}^{\infty}(u;q)} {\operatorname{G\text{-}MMS}^{\infty}_{S_m}(u;q)} \]
equals
\[ \begin{cases} m-r+1,&m\ge r,\\ 1,&m<r. \end{cases} \]

I expect the homogeneous additive-star problem to be tractable, hence Class A. The star has a very simple configuration structure: a connected bundle is either a singleton leaf or a bundle containing the centre. The proof of Theorem 3.16 already supplies the natural continuous candidate allocation, and its counting argument survives the mass formulation. The interesting question is whether mixing many integral configurations in the continuum improves the finite factor. My expectation is that it does not: the paper’s sparse valuation witnessing the factor \(m-r+1\) should remain extremal, while the constructive upper bound should lift to the mass allocation.

This is not merely restating the theorem. At \(N=1\), the paper permits one partition of \(m\) goods among \(r\) agents. In the mirror, \(N\) grows, configurations may be mixed across the population, and the relevant feasibility object is a distribution over connected integral bundles. If the continuous price turns out to equal the finite price, that equality would itself be a genuine discrete-to-continuous result.

The mirror covers Theorem 3.16 and deliberately does not claim to cover the paper’s envy-freeness results. Further questions include whether Theorem 3.19’s path formula survives the same limit, whether fixed \(\tau>1\) introduces new coupling phenomena, and whether arbitrary graphs yield a continuum-specific hardness boundary.

My weakest point is that the scenario requires copying each graph location as the population grows and imposing connectivity on the support of those copies. A referee who insists on a fixed finite inventory may reject that co-modification. It is nevertheless exactly the kind of per-capita supply scaling that a genuine high-multiplicity mirror requires, and the individual bundles remain integral throughout.