| paper | d4-conf-ecai-2023-0349 |
| 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; every valid instance is feasible, with an explicit rational realizable profile of welfare \(1\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given \(N\), a template of \(q\) ordered indivisible items, rational type masses \(\mu_t\), and type weights \(w_{t,j}\ge 0\) with \(\sum_{j=1}^{q}w_{t,j}=1\), form a path of \(N\) repeated templates where each copy of item \(j\) is worth \(w_{t,j}/N\) to type \(t\). Find a realizable mass profile \(x_{t,I}\) of contiguous integral intervals, with type mass \(\mu_t\), such that every assigned interval is MMS-fair for its type and \(\sum_{t,I}x_{t,I}N v_t(I)\ge 1/4\).
The population is a rational mass distribution \(\mu\) over complete valuation types. Each person receives a contiguous bundle of whole items on a shared path; \(x_{t,I}\) records aggregate type-and-bundle frequencies realizable by complete allocations. The objective is to find an MMS-fair profile with aggregate utilitarian welfare at least \(1/4\) in scaled units.
The repeated-template construction gives every type an MMS-fair cycle, so it also gives PROP and scaled welfare \(1\); this makes the proposed family trivial and removes the contrast that motivates the paper’s bounds.
fatal: False
The mirror covers the algorithmic MMS allocation guarantees of Theorems 4 and 10 on the repeated-template family. It does not capture their general price-of-fairness bounds or lower-bound examples, nor the paper’s PROP1 and two-agent results.
The strongest positive case is narrow: continuize the population in the paper’s MMS results while keeping the ordered items indivisible and every person’s bundle contiguous. A plausible regime is a large venue assigning consecutive time slots across a long calendar. There may be millions of users but relatively few complete, recurring valuation profiles; users with the same profile are one type. As the population grows, the supply of slots grows with it.
For a precise mirror, take a scale \(N\) and a path \(E_N\) made of \(N\) repetitions of an ordered template of \(q\) slot positions. A type \(t\) has nonnegative rational values \(w_{t,j}\) for the \(q\) positions, with \(\sum_j w_{t,j}=1\); each copy of position \(j\) is worth \(w_{t,j}/N\). Thus each agent values the whole path at \(1\), as in the paper. The society is a rational mass distribution \(\mu\) over a finite set \(T\) of such complete valuation types, with \(\sum_t\mu_t=1\).
Let \(x_{t,I}\) be the fraction of the population of type \(t\) assigned the integral interval \(I\) of the path. Require \(\sum_I x_{t,I}=\mu_t\), and admit only profiles realizable as limits of complete allocations of the path. In particular, every person represented by \(x\) receives a contiguous block of whole items; only the aggregate type and bundle frequencies are fractional. Keep \(N\) as a scale parameter because MMS depends on the number of agents. Write \(u_t(I)=N v_t(I)\) and \(\theta_t(N)=N\,\mathrm{MMS}_t(E_N,N)\). Then an assigned block is MMS-fair for type \(t\) exactly when \(u_t(I)\ge\theta_t(N)\). This co-scales population and supply, while preserving the paper’s individual fairness test.
My lead is Theorem 4, proved in this paper: for utilitarian welfare and MMS fairness, the price of fairness is at least \(\Omega(\sqrt n)\) and at most \(O(n)\). Its upper bound comes from a polynomial-time construction—Algorithm 3—which returns a contiguous MMS allocation with utilitarian welfare at least \(1/4\). The continuous problem I would hand to a prover is Continuous MMS Utilitarian Allocation: given \(N\), the template, type valuations, and masses \(\mu\), find a realizable profile \(x\) in which every assigned block meets its type’s MMS threshold and
\[
\sum_{t,I}x_{t,I}u_t(I)\ge \tfrac14.
\]
A stronger version maximizes this welfare and asks for the continuous price-of-fairness bound. I expect the construction question to be tractable—Class A—if interval assignments and single-path realizability admit an efficient flow or pricing formulation. The naïve type-by-interval capacity LP is not enough by itself: its profiles must actually be sequenceable on the shared path.
A second worthwhile anchor is Theorem 10, also proved here: for egalitarian welfare and MMS fairness, the price of fairness is \(\Theta(n)\). The paper’s polynomial-time upper-bound algorithm ensures every agent’s value is at least \(\max\{\mathrm{MMS}_i,\mathrm{OPT}_E/(2n)\}\). Its mirror is Continuous MMS Egalitarian Allocation: on the same type-mass instance, find a realizable MMS-fair profile maximizing
\[
\inf\{u_t(I):x_{t,I}>0\},
\]
and compare it with the unrestricted optimum. I again expect an algorithmic Class A result for an explicit path, perhaps by testing candidate utility thresholds with a flow or pricing oracle. The substantive open question is whether the \(\Theta(N)\) loss survives with small type support, or becomes a bound in \(\tau=|T|\).
These are constructive PoF results, not conventional NP-hardness theorems: the paper does not give a named complexity classification for either underlying optimization problem. Both anchors are proved in this paper; I would not present cited hardness about a different allocation setting as a result of these theorems. The mirror covers the paper’s connected-allocation MMS results for utilitarian and egalitarian welfare. It does not claim to cover PROP1, envy-freeness, or the paper’s two-agent result.
The authors should recognize this as their problem: agents still receive contiguous bundles of indivisible items, MMS still refers to partitioning the full path into \(N\) bundles, and the objectives are the same welfare measures. The weakest point is the high-multiplicity limit itself. The MMS threshold must retain its dependence on \(N\), and realizability of fractional type–bundle frequencies on one path is a genuine constraint. Also, the paper’s worst-case examples may rely on \(\tau\) growing with \(N\); they may not yield the same bounds when \(\tau\) is small. Those are questions for the mirror to answer, rather than reasons to replace it with divisible cake.
The “no computational result” objection does not fit this paper: Theorems 4 and 10 give price-of-fairness bounds through polynomial-time allocation algorithms. The stronger negative case is that the proposed high-multiplicity family removes the feature those anchors are meant to study.
In that family, each type values every repeated template cycle at \(1/N\). Since an agent’s MMS is at most \(1/N\), and the \(N\) cycles form a partition into \(N\) bundles each worth \(1/N\), \(\mathrm{MMS}_t=1/N\) for every type. Assigning one cycle to each agent is therefore both MMS-fair and proportional. In scaled units, every agent gets utility \(1\). So the Theorem 4 feasibility question—find an MMS allocation with utilitarian welfare at least \(1/4\)—already has a direct cycle-by-cycle construction. The mass formulation adds no pricing or sequenceability challenge in this regime.
The same construction weakens the Theorem 10 mirror. Here the distinction between guaranteed MMS and potentially nonexistent PROP disappears: PROP is attainable by the cycle allocation. The proposed max-min optimization can still be posed, but the paper’s central contrast—what happens on instances where PROP does not exist—has been designed out of the model. With fixed \(q\), the growing variety of valuable regions that drives the paper’s lower-bound examples is also absent.
A repair would let types have different valuation densities along the path. That may yield a meaningful continuous allocation problem. But if the item mesh becomes fine relative to each person’s share, indivisibility effects fade toward connected divisible cake cutting; if the mesh stays coarse through a fixed repeated template, the cycle argument returns. Avoiding both outcomes seems to require preserving substantial item-level structure, which makes the proposed population-only compression less compelling. This is the strongest negative case I can make against these particular anchors.
It does not establish the universal claim. A finite set of types with distinct spatial valuation densities is plausible, and its limiting allocation problem might retain both multiplicity and meaningful computation. I cannot honestly rule that out; the negative case is strongest against the proponent’s repeated-template mirror, and weaker against every possible 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.