| paper | Fair Division with Bounded Sharing: Binary and Non-degenerate Valuations |
| authors | Samuel Bismuth, I. Bliznets, Erel Segal-Halevi |
| venue | SAGT 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem \(\ref{thm:hardness-fair-with-sharings}\)
Given two complete agent types of masses \(\mu_1=\mu_2=1/2\), \(m\) object classes each supplied with mass \(1/2\), and non-negative rational additive values \(v_{i,o}\), decide whether the object classes can be partitioned into integral bundles \(B_1,B_2\) such that \(u_i(B_i)\geq \frac{1}{2}\sum_o v_{i,o}\) for both types. Equivalently, decide whether a zero-aggregate-sharing high-multiplicity allocation exists, which for two bundles is also envy-free.
A high-multiplicity cohort allocation with type masses \(\mu_t\), integral bundles \(B\), and mass variables \(x_{t,B}\), subject to type-mass and object-supply constraints. For the anchored \(s=0\) problem, each type receives one bundle and every object class is assigned wholly to one type.
The mirror covers the \(s=0\) proportionality and envy-freeness hardness results and the binary proportionality flow result; it leaves positive-sharing regimes, generalized-binary valuations, non-degenerate valuations, truthfulness, and consensus largely untouched.
The strongest positive case is a high-multiplicity mirror in which population mass is continuous, but every individual still receives an integral bundle. I would lead with the zero-sharing regime, because it avoids any ambiguity about what “sharing” means.
Let \(T\) be a finite set of complete agent types, with mass distribution \(\mu\). In the balanced regime with \(|T|=\tau\), take \(\mu_t=1/\tau\) and \(1/\tau\) copies per capita of every object class. An allocation assigns integral bundles \(B\subseteq [m]\) to population mass \(x_{t,B}\), satisfying \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:o\in B}x_{t,B}=1/\tau\). Thus \(x_{t,B}\) is a population fraction, not a fractional bundle received by an individual.
For \(u_t(B)=\sum_{o\in B}v_{t,o}\), proportionality requires \(u_t(B)\geq \sum_o v_{t,o}/\tau\) for every bundle \(B\) receiving positive mass of type \(t\). Envy-freeness requires every such type-\(t\) bundle to be at least as valuable to \(t\) as every bundle assigned to any other type. At zero sharing, every object class is assigned to one type, so the allocation is simply a partition of object classes among the types.
This is a genuine high-multiplicity relaxation. Starting from an \(n\)-agent instance, make \(K\) identical copies of every agent and \(K\) copies of every object. The resulting population has \(N=nK\) agents but only \(n\) types. Normalizing by \(N\) gives \(\mu_t=1/n\) and object supply \(1/n\). Fairness and feasibility are preserved exactly. Conversely, a zero-sharing mass allocation yields the original partition. No lottery or fractional individual outcome is being introduced.
My lead anchor is Theorem \(\ref{thm:hardness-fair-with-sharings}\) in §7.2, proved in this paper. It states that \(\propwithsharing{n,s}\) and \(\efwithsharing{n,s}\) are generically NP-hard for every fixed \(n\geq2\) when \(s=0\), and for every fixed \(n\geq3\) when \(0\leq s\leq n-3\). The proof is a multi-reduction from \(k\)-way Partition, with the answer preserved throughout a super-polynomial-radius neighbourhood of the constructed valuation instance. I use its \(n=2,s=0\) case.
The corresponding continuous problem is:
\(\mathsf{HM\text{-}PROP}^{\mathrm{arb}}_0(2)\): given two types with masses \(1/2\), \(m\) object classes, and non-negative rational values \(v_{1,o},v_{2,o}\), decide whether there is a partition \(P\cup ([m]\setminus P)\) such that \(\sum_{o\in P}v_{1,o}\geq \frac12\sum_o v_{1,o}\) and \(\sum_{o\notin P}v_{2,o}\geq \frac12\sum_o v_{2,o}\). A solution is the partition \(P\), with all members of type \(1\) receiving \(P\) and all members of type \(2\) receiving its complement. With two complete bundles, this is also the exact envy-free condition.
This is a natural regime: two large homogeneous cohorts divide a catalogue of recurring assets, with each cohort having the same valuation vector internally. The population can be arbitrarily large while the number of types remains exactly two. The authors should recognise it as their problem under replication, not as a weakened surrogate.
I expect \(\mathsf{HM\text{-}PROP}^{\mathrm{arb}}_0(2)\) to be Class B. The reduction’s combinatorics live in selecting object classes for the two bundles, not in the number of named agents. Continuizing the population therefore does not dissolve the Partition structure. The theorem’s generic hardness also suggests robustness to small perturbations of the valuation data.
A second hardness anchor is Theorem \(\ref{thm:unbounded-binary-ef}\) in §5.1, proved here; its \(s=0\) base hardness is attributed to Aziz et al. and Hosseini et al. The theorem states that, for every fixed \(s\geq0\), binary additive valuations make both \(\efwithsharing{s}\) and \(\efwithshared{s}\) NP-complete, with the number of agents unbounded. The paper extends the \(s=0\) hardness by adding \(s\) forced-sharing agent pairs and objects.
Its continuous \(s=0\) mirror is:
\(\mathsf{HM\text{-}EF}^{\mathrm{bin}}_0\): given types \(T\subseteq\{0,1\}^m\), with \(\mu_t=1/|T|\), partition the object classes into bundles \(B_t\) and require \(u_t(B_t)\geq u_t(B_{t'})\) for every \(t,t'\). The solution is the partition itself; every individual receives an integral bundle. This models a large population of applicants or households sharing finitely many binary preference patterns over a common catalogue.
I again expect Class B when the number of types is part of the input. The exact-cover and equitable-colouring structure lies in the incidence pattern between types and object classes, while cloning each type merely increases multiplicity. For \(s>0\), the natural scale-invariant modification is to count object classes whose aggregate supply is assigned to more than one type; that is a co-modification forced by the continuum. I would not claim literal preservation of the paper’s count of individually split physical objects without further work.
The contrasting algorithmic anchor is Theorem \(\ref{thm:unbounded-binary-prop-no-sharings}\) in §5.1, proved here. It states that \(\propwithsharing{s=0}\) with binary additive valuations is solvable in polynomial time, even when the number of agents is unbounded. The proof uses an integral flow network: source-to-agent capacity \(\lceil V_i/n\rceil\), agent-to-liked-object arcs of infinite capacity, and object-to-sink capacity \(1\).
Its continuous mirror is:
\(\mathsf{HM\text{-}PROP}^{\mathrm{bin}}_0\): given binary type vectors \(v_t\in\{0,1\}^m\), assign every object class to exactly one type so that type \(t\) receives at least \(\left\lceil |\{o:v_{t,o}=1\}|/\tau\right\rceil\) desired classes. A solution is the type-to-object partition. The same bipartite flow solves it in polynomial time, now interpreting repeated agents as mass rather than as individually listed vertices.
Thus the mirror produces a meaningful landscape rather than a blanket claim: arbitrary valuations already give a Class B problem with only two types; binary proportionality gives a Class A problem even with many types; binary envy-freeness remains Class B when the type-incidence structure is unrestricted.
The main weakness is that the lead \(s=0\) mirror adds no new fractional action variable: it is primarily a mathematically exact high-multiplicity quotient of the discrete problem. That makes it less ambitious than a mirror allowing bounded aggregate sharing. But it is also why the case is hard to dismiss: the population is genuinely continuous, the number of agents can be arbitrarily larger than the number of types, every individual receives an integral bundle, and the paper’s fairness and computational questions survive unchanged.
The strongest negative case is semantic rather than complexity-theoretic. Fair division has two coupled indivisibilities: the objects are physical and indivisible, while each agent receives a bundle. A genuinely continuous population creates a dilemma.
If individuals must still receive integral bundles, then splitting an object across population types requires many physical copies. But assigning different copies of one object class to different types is not sharing an object in the paper’s sense. Counting such an aggregate split as one “shared object” is a new measure. If there is only one physical object, sharing it requires fractional individual bundles, which continuizes the outcome space rather than the population. Thus the bounded-sharing part of the paper does not survive cleanly.
The envy-freeness anchor is especially vulnerable. EF is a universal comparison: every positive-mass type must prefer its bundle to every other bundle. The numerical masses \(\mu_t\) do not enter those inequalities. With one bundle per type, the population distribution is merely a list of types with positive support; with multiple bundles per type, masses affect capacity but not the fairness condition. A mass-weighted or average-envy notion would make continuity substantive, but it would no longer be the paper’s EF problem.
The proportionality anchor has a related problem. The proponent’s threshold \(\lceil V_t/\tau\rceil\) assumes one integral bundle per type and equal type masses. In a genuine atomless population with fixed total inventory, each individual’s proportional entitlement tends to zero. To avoid that degeneration one must scale object supplies with population size. Then the ceiling and much of the paper’s indivisibility obstruction become capacity effects in a flow or configuration model. That may be a useful new problem, but it is not a direct continuous version of the stated theorem.
These objections do defeat the proponent’s particular formulations as complete mirrors. They do not, however, defeat the stronger universal claim.
The first anchor, Theorem \(\ref{thm:hardness-fair-with-sharings}\) at \(n=2,s=0\), survives. Take \(K\) copies of each agent type and \(K\) copies of each object, then let \(K\) grow. A type-homogeneous allocation gives one cohort \(P\) and the other its complement, with every individual receiving an integral bundle. The original proportionality or envy-freeness condition is reproduced exactly. This is a plausible high-multiplicity setting—two large homogeneous cohorts dividing recurring assets—and its computational core is a legitimate Class B mirror. Calling the population variable “only normalization” would conflict with the programme’s own high-multiplicity bridge.
The binary envy-freeness anchor also survives after correcting the proponent’s overly restrictive assumption that all members of a type receive the same bundle. The better model allows \(x_{t,B}\) mass of type \(t\) to receive each integral bundle \(B\), subject to
\[ \sum_B x_{t,B}=\mu_t \]
and the corresponding object-supply constraints. That is a genuine configuration or transportation problem over a continuous population, while every individual still receives an integral bundle. The binary incidence structure from the paper remains intact.
Finally, the binary proportionality theorem has an even clearer mirror: its bipartite flow formulation naturally becomes a mass-capacitated flow when agent and object multiplicities are scaled. The paper’s integral capacities become population capacities, and the resulting problem remains computationally meaningful and polynomial-time solvable. Correcting the proponent’s ceiling does not remove the mirror; it gives the right one.
So the negative case identifies a real modelling warning: bounded physical sharing, EF, and continuous population do not coexist naturally without carefully distinguishing object copies, aggregate splitting, and individual fractional allocation. But it cannot honestly defeat every anchor. The two-agent zero-sharing hardness result alone is a valid high-multiplicity mirror, and the binary proportionality result supplies a plausible Class A counterpart. I would therefore not sign the universal negative verdict.
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.