| paper | On maximum weighted Nash welfare for binary valuations |
| authors | Warut Suksompong, Nicholas J. Teh |
| venue | MSS 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.2
Given finitely many agent types \(T\), type masses \(\mu_t\), type weights \(w_t>0\), binary approval vectors \(a_t\in\{0,1\}^q\), and rational per-capita supplies \(\rho_j\) for \(q\) good classes, choose a finite-support mass assignment \(\pi_{t,B}\) of type \(t\) agents to integral bundles \(B\in\mathbb{Z}_{\ge 0}^q\), satisfying \(\sum_B\pi_{t,B}=\mu_t\) and \(\sum_{t,B}\pi_{t,B}B_j\le\rho_j\). Maximize first \(P(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}\), then \(\Phi(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}w_t\log u_t(B)\), where \(u_t(B)=a_t\cdot B\), with all positively valued supply assigned and an anonymous type-level refinement if a canonical tie-broken output is required.
A continuum of agents is represented by \(\mu\) over complete types; each individual receives an integral bundle of repeated good classes, while \(\pi_{t,B}\) assigns population mass to bundles. The objective is the high-multiplicity normalized weighted Nash welfare, preceded lexicographically by positive-utility mass, with per-capita supplies \(\rho\) and a type-level tie-break.
The mirror directly covers the polynomial-time computation of \(\mathrm{MWNW}^{\mathrm{tie}}\) under binary valuations in a high-multiplicity regime. It leaves the paper's resource- and population-monotonicity proofs, group-strategyproofness theorem, strong-group-strategyproofness counterexample, and comparisons with other rules as separate questions.
The strongest positive case is a narrow Class A mirror of the paper’s algorithmic result. I would not claim a hardness mirror: the paper contains no named NP-hardness result. Its direct computational anchor is Theorem 3.2.
Theorem 3.2, proved in this paper, states that under binary additive valuations, Algorithm 1 computes an \(\mathrm{MWNW}^{\mathrm{tie}}\) allocation in polynomial time, specifically in time \(\mathcal{O}(mn(m+n^2))\). The algorithm starts with the empty allocation and adds goods one at a time. For each new good it constructs a directed graph whose edge \(x\to y\) means that \(y\) values some good in \(x\)'s current bundle; it adds a dummy node holding the new good, examines reachable agents, and transfers the new good and a chain of already allocated goods along a path. It selects the path maximizing the weighted Nash welfare, with the paper’s lexicographic tie-breaking. The resulting allocation maximizes, in order, the number of agents with positive utility, the weighted product of their utilities, the lexicographic weighted-utility vector, and minimal completeness.
My lead mirror is:
Continuous MWNW Allocation, \(\mathrm{MWNW}^{\mathrm{tie}}_\infty\).
There are \(q\) good classes and finitely many agent types \(T=\{1,\ldots,\tau\}\). A type \(t\) consists of a weight \(w_t>0\) and a complete binary approval vector \(a_t\in\{0,1\}^q\). Thus agents of type \(t\) have identical entitlement and value exactly the same good classes. The society is a distribution \(\mu\), with \(\mu_t\) the mass of type \(t\). Good class \(j\) has supply \(\rho_j\) per unit mass of population.
An individual agent still receives an integral bundle \(B\in\mathbb{Z}_{\ge 0}^q\), with utility \(u_t(B)=\sum_j a_{tj}B_j\). The continuous decision variable is \(\pi_{t,B}\), the mass of type-\(t\) agents receiving bundle \(B\). Feasibility requires \(\sum_B\pi_{t,B}=\mu_t\) for every \(t\), and \(\sum_{t,B}\pi_{t,B}B_j\le\rho_j\) for every good class \(j\). Thus bundles remain indivisible; only the population mass assigned to each integral bundle is fractional.
The continuous analogue first maximizes the mass receiving positive utility, \(P(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}\). Subject to maximizing \(P\), it maximizes the normalized logarithm of weighted Nash welfare, \(\Phi(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}w_t\log u_t(B)\). This is exactly the high-multiplicity limit, since a finite lift with \(N\mu_t\) agents and \(N\pi_{t,B}\) agents receiving \(B\) has normalized log welfare \(N^{-1}\log\prod_i u_i^{w_i}=\Phi(\pi)\).
The problem is therefore: given rational \(\mu\), \(\rho\), weights, and binary approval vectors, output a finite-support feasible \(\pi\) maximizing \(P\) and then \(\Phi\), with all valued supply allocated and no universally unvalued supply allocated. If a single-valued rule is required, the paper’s agent-indexed lexicographic refinement can be replaced by an anonymous type-level refinement over utility distributions. The substantive mirror is the underlying MWNW optimization, not the arbitrary ordering of named agents.
This is a credible high-multiplicity regime. Think of millions of districts, libraries, schools, or organizations receiving large batches of standardized supplies. There may be only a few dozen entitlement-and-approval types, while the population and total supply are enormous. The type is complete: it includes the weight and the full approval pattern, so this is not erasing genuine individual heterogeneity. It is precisely the high-multiplicity assumption that many agents are interchangeable for the purposes of the problem.
The per-capita supply scaling is essential. With a fixed finite set of indivisible goods and a continuum of agents, every good would reach a null set of agents and the question would be vacuous. Scaling supplies with population is therefore a co-modification forced by continuizing the population, not a replacement of the population question by divisible-resource allocation. Each individual still receives an integral bundle; fractional quantities occur only as type-level masses.
I expect this mirror to be tractable, hence Class A. Once bundle columns are fixed, the continuous problem is a linear optimization problem over the variables \(\pi_{t,B}\). The challenge is column generation. For a given type and dual prices on goods, the pricing problem asks which integral bundle maximizes a term of the form \(w_t\log u_t(B)\) minus its resource price. Binary valuations make this unusually structured: only approved goods matter, and candidate bundles can be found by ordering approved goods by price and considering the attainable utility levels. This is exactly the sort of pricing/continuous-optimization question that the programme is meant to expose.
The prediction is not a consequence of Theorem 3.2 alone. Its algorithm is polynomial in the explicitly listed number of agents and goods, not automatically in the compressed encoding of \(\mu\) and \(\rho\). Proving polynomiality in the number of types and the bit-length of per-capita supplies would be the new ChoCo result. If binary-encoded supplies make that version hard, that hardness would be genuinely informative: it would show where the finite algorithm fails to survive high-multiplicity compression.
The paper’s other main results strengthen the plausibility of this mirror, although I would not use them as separate anchors. Theorem 3.1 proves resource-monotonicity, Corollary 1 says that adding one valued good increases exactly one agent’s utility by one, and Theorem 3.3 proves population-monotonicity. Their continuous counterparts generate natural follow-up questions: does adding supply mass leave every type’s mean utility nondecreasing, and does adding population mass of a new type leave existing types’ mean utilities nonincreasing? Theorem 4.1 similarly suggests a positive-mass group-strategyproofness question.
The weakest point is that the mirror changes more than the population: it requires goods to occur in per-capita supply, and the paper’s lexicographic tie-breaking over named agents has no literal anonymous-continuum analogue. A fixed finite set of unique goods would not support a meaningful continuum mirror. But the paper itself motivates applications involving supplies, districts, libraries, and organizations, and its mathematical problem allows arbitrary numbers of agents and goods. In those applications, repeated supply and repeated agent types are natural. The underlying weighted Nash-welfare question survives intact, and rational finite instances with \(N\mu_t\) agents and \(N\rho_j\) goods provide the exact high-multiplicity bridge back to the paper’s setting.
So my positive verdict is: one serious, author-recognizable continuous-population problem exists, anchored by Theorem 3.2, and it is plausibly a tractable Class A problem whose central contribution would be a compressed type-level algorithm rather than merely re-running the paper’s finite-agent algorithm.
The strongest negative case is that the proponent’s anchor is not really a continuization of Theorem 3.2. That theorem exploits a discrete successor operation: add one named good, increase exactly one agent’s integer utility by one, and repair the allocation along an alternating path. In the proposed model, a positive mass of goods is allocated simultaneously through \(\pi_{t,B}\). The one-good invariant, the path update, and the corollary that exactly one agent improves all disappear. The proposed optimization is therefore a new high-multiplicity allocation problem, not a continuous version of the paper’s algorithm.
With the paper’s original finite goods, the continuum genuinely degenerates. If there are \(m\) goods and population size tends to infinity, at most \(m\) agents obtain positive utility, so the positive-utility mass tends to zero. In the atomless model the primary MWNW objective is identically zero, and the remaining welfare criterion has no meaningful population-level content.
The proposed rescue—replicating goods into per-capita good classes—is legitimate under the programme’s permissive scope, but it changes both sides of the problem. A good is no longer an individual object with its own valuation column; it becomes a supply class, and agents can be split across bundles through a mass distribution. That may be an interesting new concave-cost-flow or column-generation problem, but its tractability would not explain the paper’s theorem, whose content lies precisely in indivisible one-good augmentation and named-agent tie-breaking.
The other results do not provide stronger anchors. Resource-monotonicity and population-monotonicity become vacuous when one good or one agent has zero mass; their nontrivial versions require adding positive supply or a positive-mass type and are new aggregate monotonicity questions. Group-strategyproofness fares worse: a finite coalition has measure zero and cannot affect an atomless allocation, while positive-mass coalitions define a different incentive notion.
That is the best negative case, but it is not decisive. The per-capita replicated-goods model is a sensible high-multiplicity regime, preserves integral bundles for every individual, has exact finite lifts, and retains the weighted Nash-welfare objective. The anonymous tie-breaking can be redefined at type level, as the programme explicitly permits. Consequently, I cannot honestly defend the universal claim that no worthwhile continuous mirror exists. The paper’s named algorithm does not transfer directly, but the proponent has identified a credible new Class A question anchored in its computational core.
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.