| paper | Maximizing Nash Social Welfare under Two-Sided Preferences |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given finite worker types \(i\) with rational masses \(\mu_i\) and finite firm types \(j\) with rational masses \(\nu_j\), capacity 2, and two-sided valuation matrices (restricted to \(\{0,1,2\}\) and type-degree at most 3), choose masses \(y_{j,b}\) of firm type \(j\) receiving each integral worker-type bundle \(b\) with \(|b| \le 2\), satisfying \(\sum_b y_{j,b} = \nu_j\) and \(\sum_{j,b} b_i y_{j,b} = \mu_i\), to maximize the normalized sum of worker and firm log utilities, excluding zero-utility assignments.
A two-sided configuration LP: worker and firm types carry population mass; \(y_{j,b}\) assigns firm-type mass to integral bundles of worker types; the linear objective is the population-average log Nash welfare, with capacity and mass-conservation constraints.
The configuration LP's logarithmic coefficients do not by themselves establish an exact polynomial-time Turing-model algorithm, so the proponent overstates the exact computational conclusion.
fatal: False
Covers Theorem 1's constant-capacity, ternary-valuation, bounded-degree hardness setting through a high-multiplicity mass analogue; it leaves the other hardness, approximation, parameterized, restricted-domain, stability, and axiomatic results untreated.
My strongest case is positive but narrow. The lead anchor is Theorem 1, proved in this paper: computing a Nash-optimal matching is NP-complete even when every firm has capacity 2, valuations lie in \(\{0,1,2\}\), and every agent has degree at most 3. I would not add weaker anchors merely to lengthen the case.
The natural mirror is a repeated-cohort labour market. There are many workers and many two-seat teams or positions. A worker type is a complete valuation vector over the finitely many firm types; a firm type is a complete valuation vector over worker types, together with capacity 2. Thus agents of one type are genuinely interchangeable. For example, a large recruitment market may contain thousands of workers of each of a modest number of skill/location/preference profiles, and thousands of two-seat teams of each of a modest number of role types. The masses are rational fractions or counts, with the number of agents much larger than the number of types.
Call the problem Two-Sided Nash Mass Matching\(_\infty\). Let \(\mu_i\) be the mass of worker type \(i\), and \(\nu_j\) the mass of firm type \(j\). A feasible action assigns to each firm type \(j\) a distribution \(y_{j,b}\) over bundles \(b\) of worker types, where \(b_i\in\{0,1,2\}\) and \(\sum_i b_i\le2\). Here \(y_{j,b}\) is the mass of type-\(j\) firms receiving bundle \(b\). The constraints are
\[ \sum_b y_{j,b}=\nu_j \]
for every firm type \(j\), and
\[ \sum_{j,b} b_i y_{j,b}=\mu_i \]
for every worker type \(i\), in the paper’s positive-Nash-welfare regime. The second condition says that every worker is matched once; the first says that every firm receives at most two workers. A measurable matching realizes these masses: no individual worker is split between firms, and no individual firm receives a fractional worker. Only the population of identical agents is divided among bundle patterns.
If \(v^W_{ij}\) is worker \(i\)’s value for firm \(j\), and \(v^F_{ji}\) is firm \(j\)’s value for worker \(i\), then bundle \(b\) gives the firm utility
\[ U^F_{j,b}=\sum_i b_i v^F_{ji}. \]
The continuous objective is to maximize the geometric mean of all worker and firm utilities, equivalently
\[ \frac{1}{M_W+M_F} \sum_{j,b} y_{j,b} \left( \sum_i b_i\log v^W_{ij} + \log U^F_{j,b} \right), \]
where \(M_W=\sum_i\mu_i\) and \(M_F=\sum_j\nu_j\); invalid zero-utility bundles have value \(-\infty\), just as the paper discards zero-optimum instances.
This is a genuine population continuization of the paper’s problem. It preserves two-sided cardinal preferences, additive firm utilities, many-to-one matching, capacity 2, ternary valuations, bounded local degree, and Nash welfare over both sides. The configuration variable \(y_{j,b}\) is not divisible-resource allocation: it records what fraction of otherwise identical firms receives each integral bundle.
For capacity 2, the problem has only \(O(\tau_F\tau_W^2)\) bundle variables. The objective is linear in those variables because every bundle has a fixed worker utility contribution and a fixed firm utility contribution. Thus the mirror is a polynomial-size configuration LP, giving an exact rational optimizer in the linearized real-arithmetic model and an efficient \(\varepsilon\)-optimal algorithm under ordinary numerical encoding. I therefore expect this mirror to be Class A.
This also explains why Theorem 1’s hardness need not transfer. Its reduction selects individual workers and firms so as to realize a rainbow perfect matching. In the mass model, each worker type can be divided across several firm-type bundles, turning that selection problem into a fractional configuration flow. The discrete hardness is precisely the kind of population-level integrality obstruction that high multiplicity can remove.
The authors should recognise this as their question: it is not one-sided fair division, not probabilistic social choice, and not merely fractionalising a resource. It is the same two-sided matching market in a regime of repeated worker and firm types. The labour-market motivation in the paper makes recurring cohorts and standardized two-seat teams especially plausible.
The scope is deliberately limited to Theorem 1. It does not claim to mirror the paper’s parameterized algorithms, stability extensions, or axiomatic questions.
The weakest point is the realism of repeated firm types. Named firms often differ in location, reputation, salary, and working conditions, so treating many teams as exactly identical may be a strong assumption. The mirror is most convincing for standardized positions, school places, residency slots, or recurring project teams. If that regime is accepted, however, the configuration formulation is faithful and gives a concrete, nontrivial Class A continuation of the paper’s main hardness result. The natural follow-up is to quantify rounding from this mass optimum to a finite high-multiplicity market, and to determine whether unbounded capacities create a genuine pricing barrier.
The only serious anchor is Theorem 1, and the strongest negative case is that its proposed mirror is not really a new continuous social-choice problem. With capacity two, every firm can receive only a singleton or pair of worker types. Once workers and firms are grouped by type, the entire model becomes an immediate finite configuration LP. There is no nontrivial pricing problem, no subtle continuum geometry, and no computational phenomenon specific to the paper’s two-sided structure. The paper’s main contribution—encoding a rainbow perfect matching through individual edge identities—has simply been replaced by fractional flow among anonymous categories.
That criticism is strongest if “worthwhile” means generating a substantive ChoCo complexity landscape rather than recording another easy LP formulation. Theorem 1’s bounded-capacity restriction makes the proposed continuation almost mechanically tractable, and the paper itself gives no indication that its approximation or parameterized techniques lead to interesting mass variants. The natural extension to larger capacities is a different problem, with exponentially many bundles, and cannot be claimed as a mirror of the theorem without new modelling choices.
There are also technical overstatements in the positive case. The configuration LP has logarithmic, generally irrational objective coefficients. A rational optimal extreme point exists, but finding the exact optimum in the ordinary Turing model is not automatically a polynomial-time consequence of having a polynomial-size LP. An efficient ε-approximation is much more defensible. Likewise, the displayed formulation normalizes worker and firm masses separately, whereas the paper allows different numbers of workers and firms; that is repairable, but the mass scales must be part of the formal model.
Those points still do not defeat the mirror under ChoCo’s stated standard. The type construction is legitimate: a worker type can specify values for each firm type, and a firm type can specify values for each worker type. Standardized two-seat positions, school places, residency slots, or recurring project teams provide plausible repeated firm types. The fact that named firms often differ is not decisive, because the programme explicitly permits finding a different high-multiplicity scenario from the paper’s motivating story.
Nor does the configuration variable improperly fractionalize an individual agent. Each bundle remains integral for each firm; \(y_{j,b}\) only divides an atomless population of otherwise identical firms among bundle patterns. The resulting objective is exactly the limiting average of log utilities, which is the normalized log Nash product under replication. A rational solution can be implemented by a sufficiently large finite replication, subject to the usual denominator and rounding analysis. This is a genuine population continuation, not merely the Eisenberg–Gale divisible-resource model.
Most importantly, the loss of the rainbow-matching integrality obstruction cannot count against the proposal. If the discrete NP-hardness vanishes in the high-multiplicity regime, that is precisely the kind of Class A result the programme seeks. The theorem’s reduction relying on individual edge identities is not evidence that the mass question is meaningless; it is evidence that the mass question may separate population integrality from type-level optimization.
So the honest negative case is narrow: the proposed anchor may be too easy and too close to a routine bounded-capacity configuration LP to justify substantial programme investment, and its exact-computation claim needs tightening. But it does not establish that no worthwhile mirror exists. The repeated-cohort two-sided Nash problem is well-posed, preserves the paper’s essential objective and preferences, and produces a clean high-multiplicity question. On the stated criteria, Theorem 1 survives the attack; the negative case is therefore weak.
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.