Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

There is a defensible positive mirror, but it depends on choosing a genuine high-multiplicity regime rather than simply declaring a finite item set fractional. My strongest anchor is Theorem 4.4, proved in this paper. It says that for objective mixtures of goods and chores, one can compute in polynomial time a PROP1 allocation whose proportional outcome has total subsidy at most \(\alpha(n)\), where \(\alpha(n)=n/4\) for even \(n\) and \(\alpha(n)=(n^2-1)/(4n)\) for odd \(n\). Theorem 3.1 is its chores-only special case, also proved here.

The appropriate regime is a large allocation system with many repeated item copies. Let \(T\) be a finite set of complete agent types, with population distribution \(\mu\in\Delta_T\). A type contains the entire additive utility vector, including whether each item class is a good or a chore. Let \(E=\{e_1,\ldots,e_q\}\) be a finite catalogue of item classes, and let \(\rho_e\in\mathbb{Q}_{\ge 0}\) be the number of copies of class \(e\) per agent. At replication scale \(N\), there are \(N\mu_t\) agents of type \(t\) and \(N\rho_e\) indivisible copies of item class \(e\).

This is plausible for a national or platform-scale allocation system: millions of households, workers, or service recipients, but only a few dozen valuation templates and a modest catalogue of repeated tasks, slots, benefits, and burdens. The relevant comparison is \(N\gg |T|,q\), not merely “fair division has many agents.” A named agent with an idiosyncratic utility vector is a separate type; high multiplicity is precisely the assumption that many agents share the whole vector.

For a bundle \(b\in\mathbb{Z}_{\ge0}^q\), write \(U_t(b)=\sum_e b_eu_t(e)\). The proportional benchmark for type \(t\) is

\[ p_t=\sum_e \rho_eu_t(e), \]

because this is the proportional share of an agent in the \(N\)-agent realization.

The continuous allocation is a finite-support mass distribution \(\lambda_{t,b}\). Here \(\lambda_{t,b}\) is the fraction of type \(t\) receiving the entire indivisible bundle \(b\), not a fractional bundle received by one person. It must satisfy

\[ \sum_b\lambda_{t,b}=\mu_t \]

for every type \(t\), and

\[ \sum_{t,b}b_e\lambda_{t,b}=\rho_e \]

for every item class \(e\). Thus \(\lambda\) is the empirical distribution of whole-bundle assignments in the high-multiplicity limit.

Let \(z_{t,b}\) be the total subsidy mass assigned to the agents in cell \((t,b)\). The proportionality requirement is

\[ z_{t,b}\ge \lambda_{t,b}\bigl(p_t-U_t(b)\bigr),\qquad z_{t,b}\ge0, \]

with average subsidy

\[ \Sigma=\sum_{t,b}z_{t,b}. \]

If the paper’s normalization \(s_i\in[0,1]\) is retained, add \(z_{t,b}\le\lambda_{t,b}\). A continuous PROP1 condition requires every used cell \((t,b)\) to satisfy one of the following: \(U_t(b)\ge p_t\); removing one item copy reaches \(p_t\); or adding an available good copy reaches \(p_t\).

The finite-\(N\) theorem translates exactly in scale:

\[ \frac{\tau(s)}{N}\le\frac{\alpha(N)}{N} = \begin{cases} 1/4,&N\text{ even},\[2mm] (N^2-1)/(4N^2),&N\text{ odd}. \end{cases} \]

Thus the natural continuous target is average subsidy at most \(1/4\). Whole item copies remain indivisible in every finite realization; only their population histogram is continuous.

I would call the first problem Objective-Mixed-High-Multiplicity PROP1 Subsidy:

Given \((T,\mu,E,\rho,u)\), where every item class is a good for all types or a chore for all types, output a finite-support \((\lambda,z)\) satisfying the allocation, PROP1, and proportionality constraints above, with \(\Sigma\le1/4\). The optimization strengthening is to minimize \(\Sigma\).

This is a credible Class A candidate in the common-ranking regime used directly by the paper’s proof: assume \(u_t(e_1)\ge\cdots\ge u_t(e_q)\) for every type \(t\). The paper’s double round-robin construction becomes a continuum of nearly even bundle configurations, followed by a mass-assignment problem over types. The resulting formulation is a configuration LP, and the important question is whether the ordered structure makes its pricing problem polynomial. That is exactly the kind of continuous-optimization question ChoCo is intended to expose. The unrestricted version may retain item-packing hardness, but such hardness would live in the item catalogue \(E\), not in population multiplicity; I would expect Class B rather than a genuinely continuum-specific Class C phenomenon.

My second anchor is Theorem 4.8, also proved here. It extends the same polynomial guarantee to subjective mixtures, where an item can be a good for one agent and a chore for another. The corresponding problem is Subjective-Mixed-High-Multiplicity PROP1 Subsidy: use the identical \((\mu,\rho,\lambda,z)\) formulation, but allow the sign of \(u_t(e)\) to depend on \(t\). In the most convincing version, types share an ordinal ranking of the repeated item classes while their positive/negative threshold and utility magnitudes differ.

This is still recognisably the authors’ problem: additive utilities, indivisible item copies, proportional shares, PROP1, and nonnegative subsidies all remain intact. The paper’s subjective-to-objective reduction suggests a Class A route in this common-ranking regime: choose a type with the largest positive prefix, zero the relevant negative utilities for other types, solve the objective-mixed mass problem, and move the affected item mass back to the selected type. Whether that reduction survives arbitrary shared-item correlations is a genuine follow-up question, not something I would assume for free. In the unrestricted version, I would expect either Class A after a new lifting argument or Class B from item-level configuration complexity.

The authors should recognise these as continuous analogues because the transformation is only from named agents to population proportions and from repeated item copies to per-capita supply. The subsidy is not being made type-dependent in an artificial way: a type is the complete utility description, and agents of the same type may still receive different bundles and hence different subsidies. The paper’s own proof already separates the problem into “make bundles approximately even” and “assign bundles to subsidy-efficient recipients”; the mirror replaces the finite assignment by a mass assignment.

The weakest point is important. If the item set \(M\) is held fixed while the number of agents tends to infinity, this is a bad mirror: almost everyone receives no item, and the subsidy problem degenerates. The positive case therefore requires a repeated-item regime in which item copies scale with the population. That does not make items divisible—the finite realizations still allocate whole copies—but it is a stronger modelling choice than the paper’s basic finite-instance statement. A second weakness is that the paper’s IDO relabelling argument is straightforward for named finite agents but may not preserve shared item identities in an unrestricted type distribution. For that reason, Theorem 4.4 in the common-ranked objective-mixed regime is my strongest case; Theorem 4.8 is a plausible extension, but not one I would oversell as automatic.

The paper contains no named NP-hardness or parameterized-hardness result of its own. Its named computational anchors are positive polynomial-time theorems, with the lower bound on \(\alpha(n)\) recalled from Wu et al. (2023). That makes the appropriate positive claim modest: this paper supplies a particularly clean Class A candidate for population continuization, and the main unresolved issue is whether its balancing-and-assignment structure yields a polynomial configuration algorithm independent of the enormous replication scale \(N\).