| paper | d4-conf-aaai-2026-3596 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite resource set \(M\), rational type masses \(\mu_t\) summing to \(1\), and rational piecewise-linear monotone nondecreasing utility curves \(u_t(j,z)\) for each type \(t\), resource \(j\), and population load \(z\in[0,1]\), let \(\theta_t=\max_{j\in M}u_t(j,1)\). Does there exist a mass assignment \(x_{t,j}\geq 0\) with \(\sum_j x_{t,j}=\mu_t\), loads \(y_j=\sum_t x_{t,j}\), and \(x_{t,j}>0\Rightarrow u_t(j,y_j)\geq\theta_t\) for every \(t,j\)?
A society is a distribution \(\mu\) over complete utility-curve types. Each type’s mass is split among indivisible shared resources through assignments \(x_{t,j}\); the resulting load is \(y_j\), and utility depends on that population fraction. The decision objective is whether every assigned mass receives at least its continuous MMS threshold \(\theta_t\).
The paper does not specify how utility scales as the population grows; with fixed co-user saturation, the MMS threshold may collapse to a simple type-to-resource assignment, so the proposed complexity question depends on the added fraction-based scaling regime.
fatal: False
The mirror covers only Theorem 3: MMS-allocation existence under monotone nondecreasing valuations. It leaves the paper’s other MMS, stability, envy-freeness, epistemic, and swap-stability results unaddressed.
The best mirror I see is Continuous Shared-Resource MMS Existence. Its anchor is Theorem 3, which says: under monotone nondecreasing valuations, deciding whether an instance admits an MMS allocation is NP-complete. The paper presents this as its own result, not as a result cited from elsewhere.
A plausible regime is a large population choosing among a fixed set of shared activities or services. For example, many users might choose among a handful of online group activities whose appeal rises with attendance. Users with the same utility curve for every activity and attendance level form a type. Then \(n\) can be very large while the number of distinct types \(\tau\) stays modest. A type is complete for this model: its members share the same per-resource utility curves. Mass \(\mu_t\) is the fraction of the population in type \(t\).
Here is the continuous problem. The input is a finite resource set \(M\), rational type masses \((\mu_t)_{t\in T}\) summing to \(1\), and rational piecewise-linear, monotone nondecreasing utility curves \(u_t(j,z)\), where \(z\in[0,1]\) is the fraction of the population assigned to resource \(j\). Choose mass assignments \(x_{t,j}\geq 0\), with \(\sum_j x_{t,j}=\mu_t\), and let \(y_j=\sum_t x_{t,j}\). Define the continuous MMS threshold for type \(t\) by \(\theta_t=\max_{j\in M}u_t(j,1)\). This is the continuation of the paper’s nondecreasing-valuation MMS value: its allocation-vector definition simplifies to the best utility at full load. The question is whether an assignment exists such that, for every \(t,j\), \(x_{t,j}>0\) implies \(u_t(j,y_j)\geq\theta_t\). A solution is such a mass-assignment matrix \(x\), or a “no” answer if none exists.
This keeps the paper’s central question intact: can everyone receive their own MMS guarantee when the utility of using a resource depends on how many others use it? Each infinitesimal person still uses one whole resource; splitting \(x_{t,j}\) means partitioning a cohort of people across resources, not giving anyone a fractional resource. For a finite population with \(n_t/n=\mu_t\), the discrete model embeds by assigning masses in multiples of \(1/n\) and sampling \(u_t(j,z)\) at loads \(z=k/n\). The continuous problem then relaxes that grid. Theorem 3’s hardness need not survive that relaxation—that is precisely the computational question.
My working expectation for unrestricted \(m\) and \(\tau\) is Class C, continuum-specific hardness, rather than hardness transfer. For each type-resource pair, there is a minimum load needed to reach \(\theta_t\); deciding which resources reach which thresholds and routing the masses among them creates a coupled support-selection problem. That could remain hard after fractional assignment, but the paper’s theorem alone does not establish it. Further questions include whether fixed \(\tau\) or fixed \(m\) makes the problem tractable, and whether fixing the active resource supports reduces it to a flow or LP.
The weakest point is the new utility-curve assumption. The paper specifies valuations at integer group sizes, whereas this mirror supplies piecewise-linear curves over normalized loads. Sampling those curves embeds finite, repeated-type instances, but the paper’s Theorem 3 does not, from the stated result, show that its hard instances have few repeated types or that their hardness survives fractional cohort splitting. Even so, the mirror seems recognizable to the authors: it preserves their indivisible resource choices, load-dependent utilities, monotonicity regime, and MMS allocation question. It covers Theorem 3 alone; I would not stretch it to claim a mirror for the paper’s other fairness and stability results.
The anchor is real: Theorem 3 is a named NP-completeness result, and the proposed question keeps its MMS existence problem. I can’t defeat it by saying the paper has nothing computational to mirror.
The strongest objection is the scaling step. The theorem gives valuations at integer group sizes for a particular finite population. It does not say how those valuations change as the population grows. For many shared activities, utility saturates after some fixed number \(K\) of co-users. If we hold that scale fixed while \(n\) grows, any resource receiving a positive fraction \(y_j\) of the population has about \(ny_j\) users and eventually reaches saturation. For monotone nondecreasing valuations, an agent’s MMS threshold is \(\max_j v_i(j,n)\). In that limit, assigning each type to a resource where its saturated utility is highest meets the threshold; the resource’s exact positive load no longer matters. The hard feasibility question can disappear.
The proposed mirror avoids that collapse by making utility depend on the *fraction* \(z\) of society using a resource. That is coherent for settings where market share or population share drives utility, and the assignment of nonatomic cohorts to whole resources respects the population-continuum scope. But it adds an asymptotic scaling law that the paper’s finite model and Theorem 3 do not supply. If the authors endorse that law, the resulting threshold-and-load feasibility problem is recognizable as a continuous MMS question. Its resource activation constraints may still be computationally interesting.
So the negative case is weak at its central point. The scaling objection shows that the mirror is not uniquely determined by the theorem, and that some natural fixed-scale limits degenerate. It does not rule out a plausible fraction-based population regime. I would not claim that no worthwhile mirror exists; under the programme’s stated test, the proponent’s anchor survives unless the authors reject that regime.
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.