| paper | d4-conf-aaai-2024-0599 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given finitely many types \(T\), rational masses \(\mu_t\) summing to \(1\), per-capita supplies \(q_j\), and SPLC valuations \(u_t(b)=\sum_j\sum_{r=1}^{b_j}v_{tjr}\) on integral bundles \(b\in\mathbb{Z}_{\ge 0}^{J}\), define \(\sigma_t(q)\) as the supremum of \(z\) for which a distribution over integral bundles has expected use of each good \(j\) at most \(q_j\) and gives every bundle in its support value at least \(z\). Find finite bundle masses \(\lambda_{t,b}\ge 0\) such that \(\sum_b\lambda_{t,b}=\mu_t\), \(\sum_{t,b}\lambda_{t,b}b_j\le q_j\) for each good, and every bundle with positive mass satisfies \(u_t(b)\ge \sigma_t(q)/2\).
A population of mass \(1\) with type distribution \(\mu\), per-capita supply \(q\), type-specific SPLC valuations, and integral bundles for individuals. The decision variables are masses \(\lambda_{t,b}\) assigned to bundles; the goal is to meet each type’s mass, respect aggregate supply, and give each type at least half its distributional MMS benchmark \(\sigma_t(q)\).
The paper does not specify a finite encoding for SPLC valuation curves as per-capita supplies scale, so the precise compressed input size and running-time target remain unsettled.
fatal: False
The mirror covers Theorem 4.1’s [0m\(\frac{1}{2}\)-MMS guarantee for SPLC valuations; it leaves the submodular [0m\(\frac{1}{3}\)-APS result and other results unaddressed.
My lead, and only anchor, is Theorem 4.1, proved in the paper. It says that for every SPLC fair-division instance, the stated algorithm gives each agent an integral bundle worth at least half that agent’s MMS. The paper also describes a polynomial-time implementation using computable share upper bounds, an LP, and rounding. This is an algorithmic anchor, not a hardness result. The text says that computing MMS values is NP-hard, but gives no numbered hardness theorem for that claim, so it cannot serve as a separate anchor under your rule.
A plausible regime is a large allocation system distributing many copies of standardized goods—relief supplies, for example—to residents in a modest number of standardized need cohorts. A type is the resident’s complete SPLC valuation: for each good category \(j\), a nonincreasing sequence of marginal values \(v_{tjr}\). Let \(\mu_t\) be the fraction of residents of type \(t\), with \(\sum_t\mu_t=1\), and let \(q_j\) be the supply of good \(j\) per resident. The regime is \(N\) residents and \(Nq_j\) copies of each good, with \(N\mu_t\) residents of each type: \(N\) grows while the number of types \(\tau\) stays relatively small.
Here is the continuous problem I would hand to a prover: SPLC Half-MMS Allocation\(_\infty\). An instance gives finite types \(T\), rational masses \((\mu_t)_{t\in T}\), per-capita supplies \((q_j)_{j\in J}\), and the SPLC valuations. A bundle \(b\in\mathbb Z_{\ge0}^{J}\) is still integral for each resident, with value \(u_t(b)=\sum_{j\in J}\sum_{r=1}^{b_j}v_{tjr}\). Define type \(t\)’s continuous MMS benchmark \(\sigma_t(q)\) as the supremum of \(z\) for which there is a probability distribution \(\pi\) over integral bundles such that every bundle in its support has value at least \(z\), and its expected use of each good \(j\) is at most \(q_j\). This is the mass-one version of the type’s cut-and-choose benchmark against the per-capita stock.
The task is to output a finite list of bundle masses \(\lambda_{t,b}\ge0\) such that \(\sum_b\lambda_{t,b}=\mu_t\) for every type, \(\sum_{t,b}\lambda_{t,b}b_j\le q_j\) for every good, and every listed bundle with \(\lambda_{t,b}>0\) satisfies \(u_t(b)\ge\sigma_t(q)/2\). The mass \(\lambda_{t,b}\) means that fraction of society of type \(t\) receives the integral bundle \(b\). Thus the aggregate allocation can have fractional average holdings while no resident receives a fractional good.
This is a credible mirror of Theorem 4.1 because a finite partition into \(N\) bundles is exactly an empirical distribution over integral bundles, and its per-capita resource use is \(q\). The proposed benchmark is the corresponding mass limit of that partition-based MMS. The paper’s finite algorithm and LP-rounding argument make Class A my expectation: the proof already exploits a fractional assignment followed by integral allocation. But it does not establish an algorithm polynomial in \(\tau\) and the bit length of the mass and supply data. A configuration formulation has potentially many bundle columns, so its pricing or separation problem is the central new question.
The authors should recognize the underlying problem: it remains SPLC fair allocation with integral bundles, equal treatment of agents, and an MMS guarantee. Scaling supplies with population is the co-modification needed to make the high-multiplicity regime meaningful. The mirror covers Theorem 4.1’s half-MMS result; it does not claim to cover the paper’s submodular APS result.
My weakest point is the type regime. Exact SPLC valuation identity within each type is a strong requirement, and a setting where the number of distinct complete valuations grows nearly as fast as the population would not support this mirror. Standardized cohorts make the regime plausible, but the paper itself does not supply that scenario. A second open issue is whether its finite polynomial-time algorithm yields a genuinely compressed continuous algorithm, rather than one whose running time depends on a large realizing population \(N\). Those are real limitations of the tractability case; they do not erase the well-posed population-limit question.
Theorem 4.1 is a genuine computational anchor: it gives a polynomial-time algorithm for a half-MMS allocation, and the appendix supplies the implementable version. I can’t dismiss it on the ground that there is no computational result to mirror.
The strongest negative case is about what remains new after scaling. For rational type masses and per-capita supplies, choose a common denominator \(N\). The resulting finite instance has \(N\) agents and \(Nq_j\) copies of each good. Its partitions correspond to empirical distributions over integral bundles. Thus the finite theorem carries the half-MMS guarantee to these scaled instances. The continuous question’s real computational content is whether one can avoid expanding \(N\) and solve from the binary description of the masses and supplies. That could be a substantial high-multiplicity problem, but it makes the mirror’s novelty depend on the input encoding for SPLC valuations: explicitly listing marginal values can grow with supply, while a compact curve representation needs to be specified.
That objection does not survive the stronger mirror. Standardized cohorts with identical diminishing-value curves for a fixed set of resource categories are plausible. With integral bundles for residents and masses over bundles for each cohort, the benchmark in the proposal is the continuum counterpart of an MMS partition: a finite partition gives an empirical bundle distribution, and the continuum permits arbitrary distributions. Identity carries no apparent information needed for the guarantee. Per-capita supplies are the natural co-modification for a growing population, and a configuration formulation gives a concrete pricing problem to study.
So the negative case is weak. The encoding issue is real, and it narrows what is genuinely new to compressed computation, but it does not show that the continuous question is ill-posed or uninteresting. I cannot honestly defeat this anchor across plausible scenarios; the proponent’s mirror survives.
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.