| paper | d4-conf-ecai-2024-0358 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given \(p\) types with rational masses \(\mu_t>0\) summing to \(1\), utility vectors \(u_t\in\mathbb{Q}_{\ge 0}^{7}\), and rational per-capita supplies \(b_j\ge 0\), decide whether there is a finite-support assignment \(x_{t,z}\ge 0\) to integral bundles \(z\in\mathbb{Z}_{\ge 0}^{7}\) such that \(\sum_z x_{t,z}=\mu_t\), \(\sum_{t,z}z_jx_{t,z}\le b_j\) for each item type \(j\), and Nash welfare \(\exp(\sum_{t,z}x_{t,z}\log(u_t\cdot z))\) is at least a given threshold \(R>0\), with welfare zero if positive mass receives zero utility?
A continuous population with \(p\) utility types, rational masses \(\mu_t\), and seven item types with rational per-capita supplies \(b_j\). The decision variables \(x_{t,z}\) give the mass of type \(t\) receiving integral bundle \(z\); maximize \(\exp(\sum_{t,z}x_{t,z}\log(u_t\cdot z))\) subject to type-mass and supply constraints.
The mirrors address Theorem 1's seven-item-type MNSW hardness, Theorem 6's seven-item-type MESW hardness, and Theorem 10's MNSW PTAS for a fixed number of agent types. They leave Theorem 7's two-item-type MESW PTAS and the paper's other results unmirrored.
I would mirror the population while keeping each person’s bundle indivisible. Take \(p\) agent types, with type \(t\) having mass \(\mu_t\in\mathbb{Q}_{>0}\), \(\sum_t\mu_t=1\), and an additive utility vector \(u_t\in\mathbb{Q}_{\ge0}^q\) over \(q\) item types. Let \(b_j\in\mathbb{Q}_{\ge0}\) be the supply of item type \(j\) per unit of population. A bundle is still an integer vector \(z\in\mathbb{Z}_{\ge0}^q\). The decision variable \(x_{t,z}\) is the mass of type \(t\) receiving bundle \(z\), subject to
\[
\sum_z x_{t,z}=\mu_t
\quad\text{and}\quad
\sum_{t,z}z_jx_{t,z}\le b_j \ \text{for every }j.
\]
A solution is a finite list of bundles and assigned masses. It describes a deterministic allocation across a continuum of people, not a lottery for each person: each person receives an integral bundle. For a finite population of size \(N\), the corresponding counts are \(N\mu_t\) and \(Nb_j\), when these are integers; finite allocations are the special case where every \(x_{t,z}\) is a multiple of \(1/N\).
The first anchor, and my lead hardness anchor, is Theorem 1, proved in the paper. It says that the decision variant of MNSW is NP-hard even with exactly seven item types. MNSW maximizes the geometric mean of agents’ utilities. Its continuous counterpart, C-MNSW-7, takes the rational masses, seven-dimensional utility vectors, and per-capita supplies above, and asks for a feasible mass allocation maximizing
\[
\exp\!\left(\sum_{t,z}x_{t,z}\log(u_t\cdot z)\right),
\]
with welfare zero if positive mass receives zero utility. The computational question is to find an optimal allocation; the threshold decision version asks whether one exists with welfare at least a given rational target.
I expect the fixed-seven-item-type continuous problem to be Class A, at least for approximation. The discrete reduction’s bin assignment has to choose whole agents; in this mirror, mass of a type can be split across integral bundles. That is a substantive relaxation, while the seven-dimensional bundle choices remain intact. The natural route is an LP over bundle configurations, with pricing over integral bundles in fixed dimension. Whether that pricing can be done efficiently for the Nash objective is a central question, not a result I am claiming.
The second hardness anchor is Theorem 6. The paper states that the decision variant of MESW is NP-hard even with seven item types; it says this follows from a slight modification of Theorem 1, with the proof omitted from this article. MESW maximizes the minimum utility. Its mirror, C-MESW-7, has the same instance and feasible allocations, and asks for an allocation maximizing
\[
\operatorname*{ess\,inf}_{(t,z):\,x_{t,z}>0} u_t\cdot z.
\]
Equivalently, for a rational threshold \(\lambda\), ask whether all positive mass can be assigned integral bundles with utility at least \(\lambda\), within the item supplies. I also expect Class A here. For a fixed threshold, the mass-allocation feasibility question has an LP formulation over bundles meeting that threshold; its pricing question is an integer optimization in seven dimensions. This makes the continuum version a plausible place for the discrete hardness to dissolve.
The regime that makes the population interpretation most convincing is captured by Theorem 10, proved in the paper: MNSW has a PTAS when the number of agent types is any fixed constant, with no corresponding restriction on the number of item types. Its mirror, C-MNSW-FEW-TYPES, takes a constant number \(p\) of rational utility types, rational masses summing to one, and any number \(q\) of item types with rational per-capita supplies. It asks for a feasible mass allocation whose Nash welfare is at least \(1-\varepsilon\) times optimal, for each fixed \(\varepsilon>0\). I expect this to admit a PTAS, and possibly an exact LP-based approach in some regimes: the cohorts may be large, while the number of recurring utility profiles stays small. This is the most persuasive regime match, though it is an algorithmic rather than hardness anchor. The paper’s PTAS does not itself establish a result for rational masses.
The scenario is a large allocation program serving many households with a small set of recurring utility profiles, where supplies of each item category grow with the population. The type is the household’s full utility vector for these goods; mass is its share of the population; the decision is how much mass of each type receives each integral bundle. Both egalitarian and Nash welfare retain their original meanings. The per-capita supply is a necessary co-modification when population size is removed, and fits the programme’s scope: the people become continuous, while goods do not.
The strongest support for the mirror is that the paper already treats multiplicities of agents and items as central, and explicitly studies few-type regimes. That makes a rational-mass version a natural next mathematical question for these authors. The weakness is that Theorems 1 and 6 do not establish hardness in a repeated-type population regime: Theorem 1’s construction has one agent for each input number \(a_i\), and its utility depends on \(a_i\). Thus the hardness may encode a growing number of distinct types rather than multiplicity within types. I would not claim those reductions survive the mirror; I would ask whether they do. Theorem 10 supplies the firmer scenario anchor, while the two hardness mirrors test whether continuous mass removes the partition structure.
This case covers the paper’s MNSW and MESW results on item-type hardness and the fixed-agent-type MNSW PTAS. It leaves the paper’s other algorithmic results outside scope. The further questions are whether the fixed-\(q\) mirrors have polynomial-time pricing, whether their exact optima are tractable or only approximable, and how closely rational-mass optima track large finite allocations.
The strongest negative case is that Theorems 1 and 6 are weak anchors for a continuum of repeated agent types. In the BECP reduction, each input number \(a_i\) appears in agent \(i\)’s utility for goods of type \(\gamma\). The seven item types stay fixed, but the agent type support can grow with \(n\). Restricting to a fixed number of agent types removes that feature; retaining it makes the hardness instance depend on a growing collection of distinct utilities. Theorem 6 inherits the same issue. That weakens the case that these hardness results reveal something about continuous cohorts, though it does not make their mirrors unworthy questions: whether the hardness survives is itself a valid result.
Theorem 10 is much harder to dismiss. A large allocation program with recurring utility profiles and supplies that scale with its population gives a coherent scenario. Its continuous MNSW mirror also has a clear formulation: taking logarithms makes the objective \(\sum_{t,z}x_{t,z}\log(u_t\cdot z)\), linear in the mass assigned to each integral bundle. The resulting configuration LP is familiar, which raises a reasonable concern that the mirror could be a modest reformulation of high-multiplicity optimization. But pricing over integral bundles, especially with an unbounded number of item types, remains a computational question. The paper’s PTAS for integer multiplicities does not settle it.
For rational masses and supplies, clearing denominators turns a feasible mass allocation into a finite allocation at a larger population scale. That makes the mirror closely tied to replication in the paper’s own high-multiplicity setting. This is the best concern about its distinctiveness, but the programme explicitly treats that connection as part of the bridge, and existing high-multiplicity work supports the population regime.
So the negative case can downgrade Theorems 1 and 6 as evidence and question how much new theory the Theorem 10 mirror will require. It cannot honestly rule out every worthwhile mirror. The Theorem 10 question survives, leaving the requested universal claim 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.