| paper | On Improving Resource Allocations by Sharing |
| authors | Robert Bredereck, Andrzej Kaczmarczyk, Junjie Luo, Rolf Niedermeier, Florian Sachse |
| venue | AAAI 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given finite agent types Θ with rational masses μ\(_\theta\), finite resource classes \(R\) with rational masses ρ\(_{\theta r}\) of repeated indivisible copies initially owned by type θ, additive utilities \(u_\theta(r)\), a typed relation ℐ specifying allowable owner-recipient pairs, fixed \(b\ge2\), and rational threshold \(q\), decide whether a mass distribution over legal sharing configurations exists in which initial ownership is preserved, each copy is shared with at most one neighbor while its owner keeps access, each agent has at most \(b\) sharing incidences, and \uoperatorname*{ess\,inf}\(_a\) \(u_{\operatorname{type}(a)}(B_a)\ge q\).
A high-multiplicity typed resource-sharing model: μ\(_\theta\) is mass of complete agent types, ρ\(_{\theta r}\) is mass of repeated indivisible resource copies initially owned by those types, and decision variables are masses of legal sharing configurations subject to resource-capacity and per-agent \(b\)-incidence constraints, maximizing minimum post-sharing additive utility.
It covers Theorem 2 directly and gives a second mirror for Theorem 3; it leaves Theorem 1, Lemma 1, Theorems 4–8, and Observation 3 without continuous formulations.
Yes. The strongest honest mirror is a high-multiplicity sharing economy: many agents belong to a small number of complete types, and many physical resource copies belong to a small number of resource classes. The resources remain indivisible; only their repeated population counts are normalized into mass.
A natural regime is a large employer, cloud platform, or knowledge-sharing system with \(N\) agents, \(\tau\ll N\) agent types, and \(\Theta(N)\) copies of each resource class. A type records an agent’s entire utility function, initial bundle, and sharing permissions. Agents of the same type are interchangeable for the problem. A mass \(\mu_\theta\) represents the fraction of agents of type \(\theta\), while \(\rho_{\theta r}\) represents the mass of copies of resource class \(r\) initially owned by that type. A mass of \(x\) shared copies means \(xN\) discrete copies before normalization; it does not mean that one indivisible item yields fractional utility.
My lead anchor is Theorem 2: “\(b\)-EWSA is NP-hard for any constant \(b\ge2\).” This is proved in the paper, by a reduction from N3DM. The result concerns egalitarian welfare, so its population version has an especially clean objective.
Call the continuous problem \(b\)-EWSA\(_\infty\). An instance consists of finite agent types \(\Theta\), rational masses \(\mu_\theta\), resource classes \(R\), initial bundles \(B_\theta\), additive utilities \(u_\theta(r)\), a typed sharing relation \(S\subseteq\Theta\times\Theta\), a fixed constant \(b\), and a rational target \(q\). A feasible solution is a mass matching of agents and resource copies. A sharing event takes one copy of \(r\) owned by an agent of type \(\theta\), gives access to it to an agent of type \(\theta'\) with \((\theta,\theta')\in S\), leaves the owner’s access unchanged, uses each resource copy at most once, and gives each agent at most \(b\) sharing incidences. The resulting bundle of each agent includes its initial bundle and every resource shared to it.
The question is whether there exists such a mass sharing \(\sigma\) satisfying
\[ \operatorname*{ess\,inf}_{a} u_{\operatorname{type}(a)}(B_\sigma(a))\ge q. \]
This is not a weakened welfare problem: it preserves the initial allocation, indivisible resource copies, additive utilities, the \(b\)-bounded sharing rule, and the paper’s egalitarian objective. It removes only the names of repeated agents and repeated resource copies.
The plausible expectation is Class A. For fixed \(b\), the continuum solution can be described by a configuration or flow LP over agent types, resource classes, and local sharing patterns. A local pattern contains only \(O(b)\) sharing incidences, and additive utilities make its value explicit. The discrete N3DM obstruction is the requirement that individual elements form integral exact triples; mass can split among compatible configurations. The main technical question is whether the resulting configuration LP has a polynomial-time separation oracle in \(\tau\), \(|R|\), \(b\), and the encoding length. If it does, Theorem 2 gives a clear example where discrete NP-hardness dissolves under high multiplicity. If separation becomes hard for a richer typed sharing relation, that would instead identify a continuum-specific boundary.
The paper’s authors should recognize this as their problem. The only substantive modelling choice is the scenario: the paper’s particular agents need not be repeated, but its resource-sharing model naturally applies to large cohorts of employees with repeated qualification profiles, or to large pools of clients and identical machines, servers, or training resources. The programme explicitly treats that as the relevant test.
A second, particularly clean anchor is Theorem 3 (\(\star\)): “ERSA is NP-hard even if the attention graph and the sharing graph are (bidirectional) cliques, and the goal is to reduce the number of envious agents by at least one.” This is proved in the paper, with the starred proof details deferred to the cited long version. It is valuable because no individual social-network structure is needed.
Define complete-network ERSA\(_\infty\) using the same typed mass instance, but with every agent able to share with and envy every other agent, and with simple \(2\)-sharing: each agent participates in at most one sharing. Let \(\nu_{\theta,B}(\sigma)\) be the mass of type-\(\theta\) agents whose post-sharing bundle is \(B\). Define the mass of envious agents by
\[ E_\infty(\sigma) = \sum_{\theta,B}\nu_{\theta,B}(\sigma) \mathbf{1}\!\left[ u_\theta(B) < \max_{\nu_{\theta',B'}(\sigma)>0}u_\theta(B') \right]. \]
Given a rational \(\Delta>0\), Complete-Graph ERSA\(_\infty\) asks whether there is a legal mass sharing \(\sigma\) such that
\[ E_\infty(\sigma)\le E_\infty(\sigma_0)-\Delta, \]
where \(\sigma_0\) is the initial allocation. Equivalently, one may give a rational threshold \(\kappa\) and ask whether \(E_\infty(\sigma)\le\kappa\).
This is the direct population form of the paper’s envy-reduction problem: same initial allocation, same full utility for shared resources, same no-reallocation rule, same one-share-per-agent restriction, and exactly the same definition of envy, with agent counts replaced by mass. The complete graph is not an artificial simplification introduced by the mirror; it is the graph restriction under which Theorem 3 already proves hardness.
I would tentatively expect this problem also to be Class A in the finite-type regime, though less confidently than \(b\)-EWSA\(_\infty\). Once the set of occupied post-sharing bundle types is fixed, the feasibility constraints are mass-matching constraints. The difficulty is that envy depends on which post-sharing bundle types have positive mass, so the objective is support-sensitive rather than a single plain LP. A natural programme is to enumerate or otherwise optimize over the relevant support and maximum-value patterns. Whether that can be done polynomially in \(\tau\), the number of resource classes, and the encoding length is itself a worthwhile open problem. If it cannot, this would be a plausible Class C phenomenon: hardness caused by the continuum’s support and threshold structure rather than by named individuals.
The exact phrase “reduce envy by one agent” does not survive normalization literally: one agent has mass \(1/N\), which vanishes as \(N\) grows. That is a genuine weakness, not something to conceal. The correct continuous question asks for a positive rational reduction \(\Delta\), or for a target envy mass. It is still the same optimization problem in the high-multiplicity regime, but not the literal one-agent decision threshold.
My other main reservation is that repeated resource copies are necessary. If resources remain a fixed finite set while only agents become nonatomic, the model degenerates: there cannot be \(N\gg\tau\) agents with a genuine initial allocation of individually owned resources. The mirror therefore assumes a large stock of repeated resource classes. That is a high-multiplicity assumption about the instance regime, not an outcome-space relaxation: each finite-\(N\) resource remains indivisible and shareable at most once.
This case deliberately covers Theorems 2 and 3, not the entire paper. Theorem 1 would give an additional polynomial matching baseline, but the two hardness anchors already establish the substantive ChoCo question: whether the paper’s discrete combinatorial difficulty survives when the agents and resource copies are represented by mass.
The strongest negative case is conditional: if ChoCo continuizes only the agent population while keeping the paper’s finite resource set fixed, both proposed mirrors degenerate. With \(N\) agents and \(|R|\) fixed, at most \(|R|\) agents own resources; as \(N\to\infty\), almost all mass has empty initial bundles. For any positive egalitarian target, \(b\)-EWSA becomes infeasible or trivial, while any envy reduction caused by sharing is at most \(O(|R|/N)\) and disappears in the limit. Thus neither Theorem 2 nor Theorem 3 has a meaningful population-only limit.
That objection does not defeat the proponent’s stronger formulation, however. Allowing \(\Theta(N)\) repeated resource copies produces a legitimate high-multiplicity regime: each finite-\(N\) copy remains indivisible, while identical agent and resource profiles occur many times. Initial ownership, utility vectors, and sharing permissions can all be included in the type. The N3DM construction can itself be replicated by taking many copies of each \(x_i\)-, \(y_i\)-, and \(z_i\)-profile. If the resulting mass problem admits fractional mixtures of triples, that is precisely the sort of population-induced hardness dissolution ChoCo is designed to investigate. For fixed \(b\), local sharing configurations contain only \(O(b)\) incidences, so a configuration or capacitated-flow formulation is entirely natural.
Theorem 3 is no stronger against continuization. “Reduce envy by one agent” vanishes under normalization, but replacing it by a positive mass reduction \(\Delta\), or by a fixed percentage of the population, is an entirely reasonable high-multiplicity question. In the complete graph, identity itself is unnecessary: a type together with its post-sharing bundle determines its envy status, and the mass of agents split across bundle configurations is enough to compute the objective. The discontinuity caused by the appearance of a positive-mass maximum bundle is a technical feature of the optimization problem, not a modelling failure.
So the best case against is that the literal paper instances have too few resources for a population limit, and the useful mirror must continuize the inventory as well as the agents. But that is a scope caveat, not a decisive objection: the repeated-resource model is plausible, preserves indivisibility at finite multiplicity, and gives both Theorem 2 and Theorem 3 meaningful computational questions. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists. Theorem 2, in particular, survives the negative case.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.