Best of Both Worlds Fairness under Entitlements -- probablistic allocation of indivisible items -- already probabilistic

The strongest positive case is for a high-multiplicity version of the paper’s Weighted Maximum Nash Welfare Lottery Algorithm. I would anchor it on Theorem 6.2, proved in this paper: a strongly polynomial-time algorithm returns an outcome that is ex-ante WEF, ex-post WPROP1, ex-ante Pareto optimal, and ex-post Pareto optimal. (Its decomposition ingredient, Lemma 6.1, is attributed to Freeman et al.; the theorem applying it to weighted entitlements is proved here.) This is a better anchor than the paper’s two-agent impossibility: the latter has no population to continuize.

Call the continuous problem HM-WMNW Best-of-Both-Worlds Allocation\(_\infty\). There is a finite set \(G\) of item categories. Category \(g\) has \(q_g\) indistinguishable indivisible copies per unit of population; in a finite \(N\)-person realization this means \(Nq_g\) physical copies. There is a finite set of agent types \(T\). Type \(t\) has population mass \(\mu_t\), additive per-person values \(v_t(g)\), and a per-person entitlement parameter \(a_t>0\), normalized so that \(\sum_t\mu_t a_t=1\). A type is complete: it fixes the entitlement band and the valuation vector, or the ordinal ranking in the ordinal variant.

The high-multiplicity dictionary is direct. In the \(N\)-agent discrete replica there are \(N\mu_t\) agents of type \(t\), each with paper-weight \(a_t/N\). Thus the paper’s weighted envy comparison between two individual agents becomes, after cancelling the common \(1/N\), comparison of per-person utilities divided by \(a_t\). The continuous society is \(\mu\), not a fractional outcome.

The ex-ante decision variable is \(F_{tg}\), the expected number of copies of category \(g\) received by one member of type \(t\), subject to
\[ \sum_t \mu_tF_{tg}=q_g. \]
Let \(U_t(F_t)=\sum_gv_t(g)F_{tg}\). The continuous WMNW allocation is a maximizer of
\[ \sum_t\mu_ta_t\log U_t(F_t), \]
equivalently the limit of the paper’s weighted Nash product in the finite replicas. It must satisfy continuous weighted envy-freeness:
\[ \frac{U_t(F_t)}{a_t}\geq \frac{\sum_gv_t(g)F_{sg}}{a_s} \quad\text{for all }t,s. \]

The “both worlds” part must not be erased by aggregation. A solution must also output a finite lottery over feasible continuum allocation patterns. A pattern assigns each individual member a finite bundle of actual indivisible copies, using exactly \(q_g\) mass of category \(g\). Its type-level bundle frequencies implement \(F\) in expectation. Every individual bundle \(B\) assigned to a type-\(t\) member must be WPROP1 in the scaled sense:
\[ v_t(B)+\max_{g}v_t(g)\ \geq\ a_t\sum_g q_gv_t(g). \]
And every pattern must be Pareto optimal: no reassignment of the same physical-copy mass can weakly improve every member and strictly improve a positive-mass set. Thus this is not the already-familiar move of making the goods divisible: goods remain indivisible to each recipient, and WPROP1 remains a one-item, ex-post condition. Continuity lies in the population and in recording the society by type masses.

The intended regime is large-scale allocation with standardized supply and a small institutional taxonomy: for example, a national or city-wide allocation of course seats, public-housing unit categories, work-placement slots, or benefit packages. People belong to a limited number of priority/entitlement bands and have one of a limited number of valuation profiles over standardized categories. There may be millions of recipients and many physical copies of each category, while the number of types is modest by comparison. This is quite unlike a one-off estate division, but it is close to the public-housing and group-entitlement motivations the paper itself discusses.

I expect this to be Class A. The ex-ante WMNW program collapses from one variable family per named person to one per type–category pair, and is a finite Fisher/convex program with aggregate budgets \(\mu_ta_t\). The substantive algorithmic question is the implementation: can one produce the required lottery of indivisible allocation patterns from the compressed type description without expanding to \(N\) people and \(Nq_g\) copies? Theorem 6.2 makes this an especially credible question, rather than a cosmetic relaxation: its Birkhoff/bihierarchical decomposition is precisely the finite-population mechanism whose high-multiplicity analogue should be sought through configuration LPs, flow decompositions, or block-structured IP. A useful further question is whether support can be generated in time polynomial in \((|T|,|G|)\) and the binary encoding lengths, rather than in the expanded population.

I believe the authors would recognize this as their problem. It retains asymmetric per-person entitlements, additive valuations, ex-ante WEF, ex-post WPROP1, and Pareto guarantees; it merely replaces repeated named agents and repeated physical item copies by their type masses. It does not claim that every fair-division instance has this structure.

The soft spot is real: the mirror needs replicated, reasonably standardized item categories. If every object is genuinely unique, or if every person has an idiosyncratic priority and valuation vector, then the type set grows with the population and there is no useful continuization. Also, one must retain bundle-level implementation rather than stop at the aggregate flow, because otherwise “up to one item” becomes meaningless. Those limitations delimit the regime, but they do not undermine the large public-allocation regime above—where Theorem 6.2 has a natural and technically promising continuous counterpart.