| paper | d4-conf-wine-2025-0038 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given recipient types \(t\in T\) with rational masses \(\mu_t\) summing to \(1\), \(d\) item classes with rational per-recipient supplies \(q_j\), and type-specific sizes \(s_{tj}\), clear denominators with \(D\). For each \(r\), form the finite instance with \(rD\mu_t\) recipients of type \(t\) and \(rDq_j\) items of class \(j\); let \(\kappa_t(r)\) be the paper’s bin-packing MMS and set \(\kappa_t^\infty=\sup_r\kappa_t(r)\). Determine the complexity of finding a finite-support mass allocation \(x_{t,b}\ge0\), where \(b\in\mathbb Z_{\ge0}^d\) is an integral bundle, satisfying \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}b_jx_{t,b}=q_j\), and \(c_t(b)\le\frac43\kappa_t^\infty+\frac43\) whenever \(x_{t,b}>0\).
A continuum of recipient groups carries type mass \(\mu_t\); each group receives a whole integral bundle \(b\), while item-class supplies scale with population. The decision variables are the masses \(x_{t,b}\), and the task is to find a feasible allocation meeting the per-type bin-cost bound.
The mirror covers Theorems 1–3: the bin-covering cardinal and ordinal guarantees and the bin-packing ordinal guarantee. It leaves the paper’s other discussion and results outside those three allocation guarantees aside.
The strongest honest case is a high-multiplicity mirror of the paper’s allocation algorithms. The paper has no numbered hardness result or explicit complexity-class theorem. Its numbered results are constructive approximation guarantees; the proofs and surrounding text give polynomial-time algorithms for them. So this mirror asks whether those algorithms can be compressed to work on a continuous population described compactly.
Consider a large population of recipient groups—such as delivery teams, cloud tenants, or hospital units—with standardized operating profiles. A type \(t\) is the complete vector of that group’s sizes for each item class, and \(\mu_t\) is its population share. There are \(d\) item classes, with \(q_j\) items of class \(j\) available per recipient. The stock of each class scales with the population. This is plausible in the paper’s own applications: shipment lots, computing jobs, or medical supplies recur as the number of teams grows. Let \(b\in\mathbb Z_{\ge0}^d\) denote an integral bundle. Each recipient still gets whole items and uses whole bins; only the recipient population is continuous.
For a precise high-multiplicity MMS, clear the denominators of \(\mu\) and \(q\) with \(D\). For each \(r\), form the finite instance with \(rD\) recipients, \(rD\mu_t\) of type \(t\), and \(rDq_j\) items of class \(j\). Let \(\kappa_t(r)\) be the paper’s MMS for a recipient of type \(t\) in that instance, and set \(\kappa_t^\infty=\sup_r\kappa_t(r)\). This is a well-defined integer: the MMS is bounded by the finite per-capita stock, and any replicated instance can itself be replicated further. It captures the best guarantee available as the population grows.
An allocation is a finite-support table \(x_{t,b}\ge0\), where \(x_{t,b}\) is the mass of type-\(t\) recipients who each receive the whole integral bundle \(b\). It must satisfy
\[
\sum_b x_{t,b}=\mu_t
\quad\text{and}\quad
\sum_{t,b} b_jx_{t,b}=q_j\quad\text{for every item class }j.
\]
The first mirror problem, Continuous Bin-Packing OMMS, asks for such an allocation with every bundle of positive mass satisfying
\[
c_t(b)\le \tfrac43\kappa_t^\infty+\tfrac43.
\]
This mirrors the paper’s main packing guarantee directly.
Theorem 3, proved in this paper, is my lead anchor. It says that every finite bin-packing instance has a \(4/3\)-OMMS allocation: each agent \(a_i\) can pack their allocated bundle into at most \(\tfrac43\kappa_i+\tfrac43\) unit-capacity bins. The paper supplies an algorithm and says it runs in polynomial time in \(n\) and \(m\). The continuous problem asks for the corresponding mass allocation above, measured against \(\kappa_t^\infty\). Its expected direction is Class A, through a compressed version of the paper’s structural algorithm or a configuration LP. The further questions are whether that computation is polynomial in \(d,\tau,L\), whether the MMS values can also be computed in that bound, and whether bundle pricing admits efficient separation.
A second mirror, Continuous Bin-Covering OMMS, uses the same allocation variables and asks that every bundle of positive mass satisfy
\[
v_t(b)\ge \tfrac34\kappa_t^\infty-\tfrac74.
\]
Theorem 2, also proved here, says that every bin-covering instance has a \(3/4\)-OMMS allocation: each agent can cover at least \(\tfrac34\kappa_i-\tfrac74\) bins. The paper proves this with its round-robin algorithm and states a polynomial running time in \(n,m\), without an MMS oracle. The expected direction is again Class A; the open computational question is whether the round-robin argument can be expressed directly over type masses and item-class supplies, with a compact output.
A third, more oracle-dependent mirror is Continuous Bin-Covering CMMS. It asks for an allocation in which each bundle of positive mass can be partitioned into \(\kappa_t^\infty\) bins, each with total size at least \(2/3\) for type \(t\). Theorem 1, proved here, establishes that every finite bin-covering instance has a \(2/3\)-CMMS allocation: each agent can partition their bundle into \(\kappa_i\) bins meeting that threshold. Its section gives a polynomial-time algorithm in \(n,m\) given valuation and MMS-partition oracles. I expect Class A conditional on those oracles; computing the continuous MMS and compressing the oracle-based algorithm are additional questions.
These are mirrors of population allocation, not of fractional bundles: \(x_{t,b}\) counts how much population receives each *integral* bundle. The paper itself gives a bridge to this interpretation by describing its agents as groups with shared valuations and bins as group members. The mirror takes recipient groups as the high-multiplicity population and assigns them by type. It covers the paper’s three named approximation guarantees, rather than attempting to continuize every result in fair division.
The weakest point is the computational compression. Applying a finite algorithm to a denominator-cleared instance establishes the route from finite allocations to mass allocations, but \(D\) can be exponential in the input bit length. Polynomial time in \(n,m\) therefore does not establish polynomial time in \(\tau,d,L\). Also, these anchors are positive approximation results, so they do not supply a discrete hardness result whose dissolution the continuous problem could test. The mirror is plausible and recognizable as the authors’ problem, but its compact-input complexity remains the real question.
The strongest case against is that the proposed mirrors leave the paper’s computational setting only after imposing two-sided repetition: many recipients must share an entire size profile, and many items must share a size profile across those recipient types. If item classes proliferate with the instance, or recipients have individualized profiles, the supposed compression disappears. If both stay small, the problem starts to look like aggregate inventory planning rather than the paper’s allocation among agents and individually valued items. That is a real limit on how broadly these mirrors speak for the paper.
It does not defeat the proposed cohort scenario, though. Standardized recipient groups and recurring item classes are plausible, and the paper itself motivates group fairness and assumes shared valuations within a group. Under that scenario, the type is complete and mass is meaningful. The programme also permits scaling supplies with population, so fixed inventory cannot rule it out.
For Theorem 3, the closest objection is that the theorem gives an allocation guarantee and an algorithm polynomial in explicit \(n,m\); it says nothing about a succinct type-and-supply encoding. The proposed \(\kappa_t^\infty\) benchmark makes a mirror’s guarantee precise, but the remaining question is whether an allocation can be found in time polynomial in \(d,\tau,L\). The finite theorem does not answer that. This weakens the claim that the paper’s result itself opens a new complexity landscape, but compact computation is a substantive high-multiplicity question. I cannot rule it out as worthwhile.
Theorem 2 has the same gap. Its round-robin algorithm is polynomial on an explicit item list, but that bound does not settle computation from item-class counts and type masses. A better mirror would specify those inputs and ask for a compact mass allocation. The finite guarantee alone does not settle that search problem. Again, I have no fundamental reason to reject it.
Theorem 1 is the weakest anchor: its algorithm is polynomial only given valuation and MMS-partition oracles. A mirror that assumes equivalent continuous oracles would hide much of the computational work. But an oracle-free version can define the benchmark from the type and supply data and ask for a compact allocation. That is harder to analyze, not incoherent.
So the strongest honest negative case is narrow: these mirrors require a particular regime of repeated recipient and item profiles, and the paper’s explicit-input running times do not establish efficient computation on that compressed input. It does not defeat the anchors under the proponents’ better formulations. I cannot honestly support the universal claim that no worthwhile continuous mirror exists in any scenario.
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.