Improving Resource Allocations by Sharing in Pairs

The strongest positive case is a high-multiplicity version of the paper’s egalitarian sharing problem, anchored in Theorem 2. I would make this the lead mirror.

The named anchor is Theorem 2, proved in this paper. It states that, for every fixed constant \(b\ge2\), \(b\)-Bounded Egalitarian Welfare Sharing Allocation (\(b\)-EWSA) is NP-hard even when the sharing graph is a clique. In \(b\)-EWSA, the input is an initial complete allocation of indivisible resources to agents, additive nonnegative utility functions, a sharing graph, and a threshold \(k\). The question is whether there exists a \(b\)-bounded 2-sharing—each resource shared with at most one other agent and each agent participating in at most \(b\) sharings—such that every agent’s final utility is at least \(k\).

The theorem is proved by reduction from strongly NP-hard Numerical Three-Dimensional Matching. For each \(x_i\in X\), \(y_j\in Y\), and \(z_\ell\in Z\), the construction creates agents holding, respectively, a “big,” “middle,” or “small” resource. The target is \(k=(B^2+B+1)T\), where \(B=mT\). A \(z\)-agent can reach \(k\) exactly when it receives one big resource, one middle resource, and its own small resource whose numerical labels sum to \(T\). Thus a feasible sharing encodes the required three-dimensional matching. The sharing graph is nevertheless a clique, and the construction uses only two sharings per agent, so the hardness holds for every fixed \(b\ge2\).

Here is the continuous problem I would propose.

Call it \(b\)-EWSA\(_\infty\). An instance contains a finite set of agent types \(\Theta\), a society distribution \(\mu\in\mathbb{Q}_{\ge0}^{\Theta}\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), and a finite catalogue of indivisible resource classes \(\mathcal R\). A type \(\theta\) specifies its complete initial bundle \(B_\theta\), its additive utility vector \(u_\theta(r)\) for every \(r\in\mathcal R\), and hence its initial utility \(u_\theta(B_\theta)\). It also specifies all other relevant parameters; in this lead version the sharing graph is complete, exactly as in Theorem 2.

Resource supplies scale with the population. If each type-\(\theta\) agent initially owns \(b_{\theta r}\) tokens of class \(r\), then the total mass of \(r\)-tokens is \(q_r=\sum_\theta\mu_\theta b_{\theta r}\). These are still indivisible tokens at the level of an individual agent. Only their aggregate supply is a real number.

The decision variable is a measurable mass-sharing plan. Equivalently, \(x_{\theta,\theta',r}\) denotes the mass of shares in which a type-\(\theta\) agent shares an \(r\)-token with a type-\(\theta'\) agent. Every resource token may be shared at most once, every agent may participate in at most \(b\) sharings, and each received resource must come from a token initially owned by some donor. Since the sharing graph is a clique, there is no further adjacency restriction. The plan must admit a decomposition into individual configurations, each of which gives every infinitesimal agent an integral bundle and uses at most \(b\) sharing incidences.

The resulting egalitarian welfare is

\[ W_\infty(\sigma) = \operatorname{ess\,inf}_{a} u_a\bigl(B(a)\cup R_\sigma(a)\bigr), \]

where \(R_\sigma(a)\) is the set of resources shared to agent \(a\). The problem asks whether there is a feasible plan \(\sigma\) with \(W_\infty(\sigma)\ge k\); equivalently, one may maximize \(W_\infty(\sigma)\).

This is the same underlying question as the paper’s \(b\)-EWSA. The change is that the agents are a large population of repeated types: for example, a large company, university system, or public institution with many employees in recurring qualification profiles. Agents of one type have the same initial bundle, resource valuations, and sharing parameters. A realistic regime could have \(N\) agents and \(\tau=|\Theta|\) role-and-bundle types with \(N\gg\tau\): many workers may share the same qualification profile, while the catalogue of profiles remains moderate. The paper’s knowledge-sharing interpretation supports this directly.

I would expect \(b\)-EWSA\(_\infty\) to fall in Class A, at least for fixed \(b\) and a finite resource catalogue. For a fixed threshold \(k\), enumerate the possible local sharing configurations of a type-\(\theta\) agent: which at most \(b\) resources it lends, which it receives, and whether its final utility reaches \(k\). Let \(y_{\theta,q}\) be the mass of type-\(\theta\) agents using configuration \(q\). The constraints that all type mass is assigned, each resource class is shared at most once, and donor and recipient masses can be paired are linear. With a clique sharing graph, the pairing component is a transportation constraint rather than a graph-combinatorial obstacle. Thus threshold feasibility becomes a configuration LP, with column generation available if the configuration set is implicit.

This is precisely the kind of case where the discrete NP-hardness may dissolve: the N3DM reduction relies on selecting individual big, middle, and small resources and forming exact triples. In the continuous population, large cohorts of identical \(x\)-, \(y\)-, and \(z\)-types can be mixed by mass, while still giving each individual an integral bundle. The expected result is therefore not that Theorem 2’s hardness transfers, but that its high-multiplicity relaxation becomes a tractable packing or transportation problem. That would be a meaningful continuization result rather than a weakened welfare question.

The mirror is plausible to the authors because it preserves all of their substantive modelling choices: an initial complete allocation, indivisible resources, additive cardinal utilities, sharing without reallocation, one-use resource sharing, a bounded number of sharings per agent, full utility from shared resources, a clique sharing network, and the egalitarian objective. Only the population representation changes from named agents to masses of indistinguishable agents. The paper itself explicitly identifies high-multiplicity versions as an open direction, so this is not a novelty collision; it is an unfinished extension of their model.

My weakest point is that Theorem 2’s reduction uses many distinct numerical utility profiles. If every distinct profile is treated as a separate type, then the reduction may have \(\tau\) growing almost as quickly as the number of agents, weakening the claim that it represents a genuine high-multiplicity regime. I would not claim that the theorem’s NP-hardness automatically transfers, nor that every application has \(N\gg\tau\). The honest claim is narrower: the paper has a natural, faithful continuous-population problem in a plausible repeated-cohort setting, and its most interesting prediction is that the discrete hardness may disappear into a configuration LP.

The resulting programme of questions is concrete: prove the LP formulation and its complexity for fixed \(b\); establish rounding or high-multiplicity approximation guarantees back to finite populations; determine whether sparse type-level sharing graphs reintroduce hardness; and study whether sharing losses or sharing costs destroy the LP structure. This mirror covers Theorem 2 emphatically, without pretending to continuize the paper’s entire attention-graph theory.