Fair Division with Binary Valuations: One Rule to Rule Them All

I would make a positive case, but I would keep it focused on the paper’s randomized MNW result. The strongest anchor is Corollary 1, proved in this paper (using Theorems 3 and 4, with the bihierarchy algorithm of BCKM13 as an external subroutine):

Under binary additive valuations, the fractional maximum Nash welfare rule is ex ante envy-free, ex ante Pareto optimal, ex ante group strategyproof, ex post envy-free up to one good, and polynomial-time computable.

The paper does not contain a named hardness result, so there is no honest hardness anchor to prefer.

My lead mirror would be Continuous-MNW Implementation.

There are \(m\) good categories \(G\), and a finite explicit set \(T\subseteq 2^G\) of binary valuation types. A type \(t\in T\) likes exactly the goods in \(t\). The society is a rational distribution \(\mu\), where \(\mu_t\) is the mass of type \(t\), \(\sum_t\mu_t=1\). Goods are supplied at per-capita rates \(\rho_g\): in a finite population of \(N\) agents, there would be \(N\rho_g\) indivisible copies of good \(g\). Assume \(0\le \rho_g\le\sum_{t:g\in t}\mu_t\), so every supplied copy can be given to someone who likes it.

Each individual receives an integral bundle \(B\subseteq G\). Thus the outcome is not fractional at the individual level. A mass allocation can be represented by \(\lambda_{t,B}\), the mass of type \(t\) receiving bundle \(B\), with \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}\lambda_{t,B}=\rho_g\). The aggregate incidence \(x_{t,g}=\sum_{B:g\in B}\lambda_{t,B}\) is fractional only because different members of one type receive different integral bundles.

For \(\mu_t>0\), type \(t\)’s expected utility is \(u_t=\mu_t^{-1}\sum_{g\in t}x_{t,g}\). The continuous MNW allocation is an aggregate \(x\) maximizing \(\sum_{t:\mu_t>0}\mu_t\log u_t\), subject to the supply and feasibility constraints, with all supplied goods assigned to agents who like them. Equivalently, it maximizes the continuum analogue of the product of individual utilities.

The computational question is:

Given rational \((G,T,\mu,\rho)\), compute a population-MNW allocation \(x\), together with a finite compressed distribution \(\mathcal D\) over integral mass assignments implementing \(x\), such that:

• \(x\) is ex ante envy-free: for all positive-mass types \(t,s\), \(u_t\ge\sum_{g\in t}x_{s,g}/\mu_s\);
• \(x\) is ex ante Pareto optimal among feasible mass allocations;
• no positive-mass coalition can misreport its types so that every coalition member obtains strictly higher expected utility;
• every integral assignment in the support of \(\mathcal D\) is EF1 for every pair of types and bundles occurring with positive mass; and
• the output is computable in time polynomial in \(m\), \(\tau=|T|\), and the rational input length \(L\), without expanding a denominator-sized population.

I expect this to be Class A: tractable, although the compressed implementation theorem is the substantive new part. The MNW objective itself is a finite-dimensional convex-optimization problem over the \(\tau m\) marginal variables \(x_{t,g}\). The difficult step is to decompose the resulting aggregate allocation into integral bundles while preserving EF1 in every realization. The paper’s bihierarchy argument gives a highly credible template for that step: goods-marginal constraints and floor/ceiling utility constraints are precisely the sort of structured constraints that can support a polynomial decomposition. The incentive argument should likewise have a population version because shifting and optimal-utilization arguments depend on types and aggregate feasibility, not on the names of individual agents.

The high-multiplicity regime is natural. Consider millions of households receiving tickets, aid items, or school supplies, with perhaps \(m=20\) item categories but only \(\tau=30\) or \(50\) recurring need profiles. Every household of a given type likes the same categories and has no idiosyncratic prices or budgets. Here \(N\gg\tau\), and \(\mu\) is the operative object: it determines both how much demand each type contributes and how the available copies must be distributed. This is not merely replacing a finite list by a probability distribution.

The per-capita supply \(\rho_g\) is a necessary co-modification. With a continuum of agents and only one physical copy of each good, every good would reach a null set of agents and the welfare problem would collapse. Scaling the inventory with population preserves indivisibility for every individual while making the aggregate problem nondegenerate. For rational \(\mu\) and \(\rho\), the finite approximation has \(N\mu_t\) agents of type \(t\) and \(N\rho_g\) copies of good \(g\); normalizing that instance gives exactly the mass formulation. This is therefore a genuine high-multiplicity mirror, not an outcome-space relaxation disguised as one.

The authors should recognize this as their problem. The valuation language is unchanged, MNW is unchanged after normalization, and the guarantees are translated directly: fractional utilities become averages across many identical agents, while EF1 remains a statement about integral bundles in each realized assignment. The paper’s fractional allocation is not itself a novelty collision: it makes an individual’s outcome divisible or probabilistic, whereas this mirror makes the population continuous and derives fractional marginals from different agents receiving whole goods.

The weakest point is the ex post requirement. The paper’s proof uses named agents, finite lexicographic tie-breaking, and a bihierarchy over an explicitly finite allocation matrix. It does not automatically imply a polynomial-size decomposition when \(\mu\) and \(\rho\) have large denominators, nor does finite-agent group strategyproofness automatically become strategyproofness against atomless coalitions. Those are genuine proof obligations. I would still judge the mirror positively because the population regime is natural, the active optimization variables are masses rather than passive coefficients, and the paper’s own MNW/bihierarchy machinery gives a concrete route to solving rather than merely naming the problem.

The main follow-up questions are whether the EF1 implementation can be compressed to \(\operatorname{poly}(m,\tau,L)\), whether ex ante GSP survives arbitrary positive-mass type coalitions, and where the result fails if one reintroduces type-specific prices, budgets, or only a fixed finite stock of goods.