Democratic Fair Allocation of Indivisible Goods

Yes—there is a credible mirror, with the strongest conclusion being Class B: the population can be continuized while the goods remain indivisible, and the paper’s hardness survives because the combinatorics live in the goods rather than in individual identities.

My lead anchor is Proposition 3.25(a), proved in this paper. It states that deciding whether a binary instance with two groups admits an allocation giving every agent positive utility is NP-complete. The paper proves membership in NP directly and proves hardness from Monotone SAT: variables become goods; positive clauses become agents in the first group; negative clauses become agents in the second group; assigning a good to the first group means setting its variable true, and assigning it to the second means false. Every agent receives positive utility exactly when the corresponding clause is satisfied.

The continuous mirror is:

\(\textsc{Unanimous-Positive-Utility}_{\infty}\).

An instance has a finite set of indivisible goods \(G\), two groups, and for each group \(i\) a finite-support distribution \(\mu_i\) over binary approval types \(S\subseteq G\). A type \(S\) consists of agents who approve exactly the goods in \(S\), and \(\mu_{i,S}\) is their fraction of group \(i\), with \(\sum_S\mu_{i,S}=1\). A solution is an integral partition \(G=X_1\dot\cup X_2\), where \(X_i\) is the public bundle given to group \(i\). The happy mass of group \(i\) is \(H_i(X_i)=\sum_{S:S\cap X_i\neq\varnothing}\mu_{i,S}\). The decision question is whether \(H_1(X_1)=H_2(X_2)=1\). More generally, one can maximize \(h^*=\max_{X_1\dot\cup X_2=G}\min\{H_1(X_1),H_2(X_2)\}\).

This is a genuine continuous-population question: the electorate is represented by a distribution over complete types, and the objective is a mass fraction. But the action remains faithful to the paper—goods are not divisible, and a group receives one common bundle.

The high-multiplicity regime is natural for two large municipalities, countries, departments, or civic constituencies jointly dividing a finite portfolio of indivisible public projects. Many residents share the same approval list because they belong to recurring demographic, professional, or neighbourhood constituencies. If the formula produces \(q_i\) clause types in group \(i\), replicate every type \(M\) times. The population then has \(Mq_i\) agents but only \(q_i\) distinct types, with \(M\) arbitrarily large. The continuous representation stores the same society as masses, without retaining irrelevant names.

The Monotone SAT reduction transfers exactly: give every clause type positive rational mass. An allocation with happy mass \(1\) in both groups exists precisely when the formula is satisfiable. The continuous problem is also in NP under explicit rational-support encoding, since a certificate is the \(m\)-bit partition of the goods and the two happy masses can be checked exactly. Thus I expect \(\textsc{Unanimous-Positive-Utility}_{\infty}\) to be NP-complete. This is a Class B result, not continuum-specific hardness: the reduction is driven by the allocation of goods, while population multiplicity merely supplies repeated type mass.

The continuous analogue is plausible because the paper itself identifies large groups such as cities and countries as its motivating setting, and its Section 3.6 explicitly discusses maximizing the fraction of happy agents. The mirror therefore makes the paper’s democratic quantity primary; it does not replace the paper’s problem by a different fractional-goods problem.

A second, algorithmic anchor is Theorem 5.9, also proved in this paper, though its construction adapts an earlier individual-allocation algorithm. The theorem states that, for \(k\) groups with additive valuations, one can efficiently compute a \(1/k\)-democratic \(\mathrm{PROP}(k-1)\) allocation. Here an agent regards \(X_i\) as \(\mathrm{PROP}(k-1)\) if there is a set \(C\) of at most \(k-1\) goods outside \(X_i\) such that \(u(X_i)\geq \frac1k u(G\setminus C)\).

Its continuous mirror is:

\(\textsc{Mass-PROP}_{\infty}\).

An instance has \(k\) groups, indivisible goods \(G\), and for each group \(i\) a rational distribution over finitely many additive valuation types \(v\in\mathbb{Q}_{\geq0}^{G}\). For a partition \(G=X_1\dot\cup\cdots\dot\cup X_k\), let \(P_i(X_i)\) be the mass of types \(v\) for which \(X_i\) satisfies \(\mathrm{PROP}(k-1)\). The task is to output a partition satisfying \(P_i(X_i)\geq 1/k\) for every group \(i\).

The paper’s line-sweep protocol extends directly. Process goods in a fixed order, maintaining a prefix \(X\). For each group, calculate the total mass of its types for which \(X\) is \(\mathrm{PROP}(k-1)\). Once some group reaches mass \(1/k\), give it the prefix and continue with the remaining groups and goods. The proof replaces agent counts by weighted masses; the key union-bound argument is unchanged. With explicit rational additive types, the protocol is polynomial in the number of goods, groups, support types, and valuation encoding length. I would therefore expect this mirror to remain in Class A.

This second anchor matters because it shows that the mirror is not being selected only to preserve hardness. The same population continuization supports a clean weighted version of one of the paper’s positive protocols, while retaining indivisible goods and the group-public-good structure.

The scope is deliberately narrow: these two mirrors cover Proposition 3.25(a) and Theorem 5.9. I would not claim that every RWAV, cake-cutting, MMS, or arbitrary-monotonicity result in the paper has an equally compelling continuous version. Natural follow-up questions include whether maximizing \(h^*\) admits approximation or parameterized algorithms, whether the hardness persists with bounded approval-type support, and whether the \(1/k\) guarantee in \(\textsc{Mass-PROP}_{\infty}\) can be improved for restricted type distributions.

The weakest point is that the lead mirror is still a weighted compression of an indivisible allocation problem: it does not produce an LP collapse, and its hardness reduction may use many distinct types—one per clause. If “high multiplicity” were required to mean a fixed number of types independent of the number of goods, the case would be much weaker. Under the programme’s stated standard, however, \(N\gg\tau\) is enough, and repeated constituency types are both mathematically legitimate and socially plausible.