Object Allocation via Swaps along a Social Network

The strongest honest case is a typed, high-multiplicity version of the swap dynamics in which the social network becomes a finite network of large cohorts. This continuizes the population, not the objects: every individual still receives one indivisible object, while \(z_{a,x}\) records the fraction of agents of type \(a\) currently holding object \(x\).

Let \(H\) be a finite contact graph on cohort roles. A type \(a\) specifies its role \(v(a)\in V(H)\), strict preference order \(\succ_a\), and initial object \(e(a)\), together with mass \(\mu_a\). The number of named agents may be \(M\sum_a\mu_a\), with \(M\) very large, while the number of distinct types remains \(|A|\). This describes, for example, a large organization with repeated employee cohorts, repeated equipment or room types, and communication links between departments or sites.

A state is a nonnegative matrix \(z=(z_{a,x})\), where \(\sum_xz_{a,x}=\mu_a\), and the total mass of each object type is conserved. If \(a\) and \(b\) occupy adjacent roles and currently hold \(x\) and \(y\), then a mass \(\delta\) may swap whenever \(y\succ_a x\) and \(x\succ_b y\). The update is

\[ z_{a,x}\mathrel{-}=\delta,\qquad z_{b,y}\mathrel{-}=\delta,\qquad z_{a,y}\mathrel{+}=\delta,\qquad z_{b,x}\mathrel{+}=\delta. \]

Thus a mass transition is simply \(\delta M\) ordinary rational swaps in a finite \(M\)-copy realization. No individual receives a fractional object; fractional entries describe fractions of a repeated type. This is therefore a genuine high-multiplicity version of the paper’s model.

My lead anchor is Theorem 1. The paper proves, by a reduction from \(2\mathrm{P}1\mathrm{N}\)-SAT, that Reachable Object is NP-complete even when the network is a tree. In the constructed instance, an object \(t\) is reachable for a designated clause agent \(C_m\) exactly when the formula is satisfiable. The proof is entirely in this paper, not merely cited.

The corresponding continuous problem is:

Continuous Reachable Mass on a Tree. The instance consists of a tree \(H\), finitely many cohort types \(A\), rational masses \(\mu_a\), strict preferences \(\succ_a\), initial objects \(e(a)\), a target type \(a^\star\), a target object \(x^\star\), and a rational threshold \(\eta>0\). Starting from the initial state \(z^0\), is there a finite sequence of mutually beneficial aggregate swaps leading to a state \(z\) with

\[ z_{a^\star,x^\star}\ge \eta? \]

Taking \(\eta=\mu_{a^\star}\) asks whether the entire target cohort can obtain \(x^\star\); smaller thresholds ask whether a prescribed fraction can do so. A solution is the aggregate swap sequence, with rational mass transfers.

This is recognisably the authors’ problem: the object moves only through socially adjacent roles, every exchange is mutually improving, and reachability remains the question. The only substantive change is that many indistinguishable agents can make the same local exchange and the target is a positive mass rather than a named individual. That is precisely the change high multiplicity is meant to make.

I would provisionally expect this tree version to be Class A. The paper’s NP-hardness relies on all-or-nothing choices: once one literal object leaves a variable branch, another branch becomes blocked. With divisible population mass, a cohort can split its mass between the two branches. The \(2\mathrm{P}1\mathrm{N}\)-SAT consistency gadget therefore does not automatically survive. On a tree, unique paths and the paper’s own path-based observations suggest a flow or dynamic-programming formulation over object mass and preference ranks. Establishing whether this really yields a polynomial algorithm would be a worthwhile continuization result: it would show that the discrete NP-completeness is caused by population-level indivisibility rather than by the network structure itself.

The resulting follow-up questions are natural: compute the maximum reachable mass of \(x^\star\) for \(a^\star\); determine whether the problem is polynomial on paths, generalized stars, or bounded-degree trees; minimize the number of aggregate swap stages; and compare the continuous optimum with the best finite \(M\)-copy realization after rounding.

A second, perhaps more socially meaningful anchor is Proposition 4. The paper proves here that Pareto is NP-hard. Its Pareto problem asks for a Pareto-efficient allocation inside the reachable set \(R_A\), not merely any Pareto-efficient allocation in the unrestricted housing market. The proof reuses the construction from Theorem 2: the constructed instance has an allocation in which every agent receives her most preferred object exactly when the original Reachable Object instance is positive, and that allocation is the unique Pareto-efficient assignment. Hence an algorithm producing a Pareto-efficient reachable allocation would solve the NP-hard reachability problem.

The continuous counterpart is:

Continuous Pareto Swap Search. Given the same typed population and contact graph, output a reachable state \(z\) that is Pareto-efficient among all reachable states.

For precision, \(z'\) Pareto-dominates \(z\) if, for every type \(a\), there is a coupling \(q^a_{x,y}\) between the old and new object masses satisfying

\[ \sum_y q^a_{x,y}=z_{a,x},\qquad \sum_x q^a_{x,y}=z'_{a,y}, \]

with \(q^a_{x,y}>0\) only when \(y\succeq_a x\), and with positive mass making a strict improvement for at least one type. The required output is a reachable \(z\) for which no reachable \(z'\) satisfies these conditions.

This is a particularly plausible mirror because the paper itself motivates Pareto efficiency as the social-quality question for a distributed swap process. Large hospitals, universities, or firms can have many employees with the same preference ranking over equipment, rooms, shifts, or locations, while communication is constrained by a department or site network. The continuous Pareto notion is not an outcome-space relaxation: it compares welfare of a repeated population while preserving one indivisible object per person.

For unrestricted cohort networks, my forecast is Class C rather than an automatic hardness transfer. Fractional mass may destroy the specific reduction used for Proposition 4, so it would be wrong to claim that NP-hardness follows immediately. But coordination among local swaps can remain difficult even when mass is divisible: the hard structure may lie in precedence constraints induced by the network and preference orders, rather than in the number of named agents. A continuum-specific hardness theorem here would be interesting precisely because it would identify a boundary where high multiplicity stops helping. On paths and stars, I would instead expect Class A behavior, in line with Propositions 5 and 6.

I am deliberately not presenting Theorem 2 as a third anchor. Although it proves that Reachable Assignment is NP-complete in general, the two mirrors above already cover the paper’s central decision and welfare questions, and adding an exact target-state version would mostly repeat the same construction.

The weakest point is the network representation. A literal atomless population has no meaningful individual edge: one isolated pairwise swap has measure zero. The cohort graph \(H\), with aggregate swaps across its edges, is therefore a necessary co-modification of the social network. A referee could regard this as too far from an arbitrary finite graph unless the paper’s authors accept typed network roles as part of the model. The case is strongest when \(H\) represents repeated departments, campuses, wards, or neighbourhood roles, and when the continuous problem is explicitly defined as the limit of finite repeated copies.

The paper’s reductions also do not automatically establish either continuous hardness or continuous tractability. That is not a defect in the mirror; it is the research question. The paper supplies unusually good anchors because its computational content is exactly about reachable allocations, local mutually beneficial swaps, and Pareto quality. The proposed questions preserve all three, while asking what survives when a large repeated population is represented by mass.