| paper | d4-conf-aaai-2012-0213 |
| 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→P discrete result → its continuous mirror
Answer: Exactly solvable in polynomial time; the requested approximation holds with \(c=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.
statement extracted from the paper’s text layer
Given a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), and for each type a rational piecewise-constant density \(f_t\) with at most two positive segments, let \(F_t=\int_0^1 f_t(x)\,dx\). Choose measurable shares \(q_t(x)\in[0,1]\) with \(\sum_{t\in T}q_t(x)=1\) almost everywhere, and set \(W_t=\int_0^1q_t(x)f_t(x)\,dx\). Compute a welfare-maximizing allocation subject to \(W_t\geq\mu_tF_t\) for every type, with the type mass apportioned among its cake intervals so each infinitesimal resident receives one connected slice and at least \(F_t\) value per unit mass.
A high-multiplicity cake division model with type masses \(\mu_t\), at most two valuation segments per type, type-level shares \(q_t\), welfare \(\sum_t W_t\), and proportionality constraints \(W_t\geq\mu_tF_t\). Refining at all valuation endpoints yields a rational LP; atomless mass can be distributed across a type’s separate intervals while each resident receives a connected slice.
The shares-to-slices construction still needs a formal disintegration argument showing that each feasible endpoint-refinement allocation can be apportioned among connected slices while meeting the per-capita fairness floor.
fatal: False
The mirror covers Theorem 3 and includes Theorem 4’s normalized one-segment case. It leaves the linear-density PTAS, the fixed-order dynamic program, and the strategic-behavior discussion aside.
The lead mirror is a high-multiplicity cake division problem. The paper’s cake is already divisible; the continuous object here is the population. Think of a large community dividing a linear territory or shared corridor. Residents with the same valuation density are one type, and \(\mu_t\) is that type’s fraction of the population. A plausible regime has \(N\) residents and \(\tau\) distinct valuation types, with \(N\gg\tau\): many residents share each complete valuation profile.
Here is the continuous problem I would hand to a prover, Normalized One-Interval Cohort Welfare. Its input is a finite support \(T\), rational masses \(\mu_t>0\) summing to \(1\), and for each type a rational density \(f_t\) that is constant and positive on exactly one interval of \([0,1]\), zero elsewhere, and normalized so \(F_t=\int_0^1 f_t(x)\,dx=1\). Choose measurable shares \(q_t(x)\in[0,1]\), with \(\sum_t q_t(x)=1\) almost everywhere. The value assigned to type \(t\) is \(W_t=\int_0^1 q_t(x)f_t(x)\,dx\). Maximize \(\sum_t W_t\), subject to \(W_t\ge\mu_tF_t\) for every type. A solution is the allocation shares and their welfare.
The constraint is the population-scale form of proportionality: if \(n_t\) of \(N\) finite agents have type \(t\), summing their individual guarantees of \(F_t/N\) gives the cohort requirement \((n_t/N)F_t=\mu_tF_t\). The variables \(q_t\) describe how cake is divided among cohorts, not a lottery over outcomes. They also admit a connected-piece interpretation: refine the cake at all valuation endpoints, split each resulting interval into subintervals assigned to types, then divide each type’s assigned intervals among its atomless cohort. Since all members of a type have the same valuation, the cohort’s total value \(W_t\ge\mu_tF_t\) suffices to give each infinitesimal share at least \(F_t\) per unit of population mass, with each person receiving one connected interval. The finite \(N-1\) cut bound becomes the natural unbounded-cut limit as the population grows.
This mirrors Theorem 4, proved in this paper: with normalized piecewise-constant density functions, computing the optimum efficiency is NP-hard even when every function has exactly one segment. In the mirror, “one segment” becomes one preferred interval per type, but there may be many residents of each type. I expect this continuous problem to be tractable (Class A). Take the common refinement of all type endpoints. On each resulting interval every \(f_t\) is constant, so the allocation shares become variables in a rational linear program with constraints \(W_t\ge\mu_tF_t\) and objective \(\sum_t W_t\). Its size is polynomial in the support size, the number of endpoints, and the input bit length.
A second, broader anchor is Theorem 3, also proved here by a reduction from Partition: for piecewise-constant densities it is NP-hard to approximate optimum efficiency within a ratio of \(\Omega(1/\sqrt n)\), even when every function has at most two segments. Its corresponding question, Two-Segment Cohort Welfare, is exactly the problem above with each type’s density allowed at most two positive constant segments, without normalization. The same endpoint-refinement LP applies, so I again expect Class A. This asks whether the paper’s strong approximation barrier survives when residents are represented by type masses rather than as a finite ordered list.
I think the authors could recognize both as continuous analogues: they retain the common cake, the agents’ own valuation densities, proportionality, total welfare, and connected individual pieces. The type-level constraint is the summed proportionality requirement, and the atomless cohort can be divided into connected pieces to realize it. The mirror covers the paper’s piecewise-constant hardness results; it does not claim to mirror the linear-density PTAS or the paper’s strategic-behavior discussion.
The weakest point is the finite-to-continuous bridge. The paper’s hardness reductions use essentially distinct valuations across their agents, and the continuous LP permits type cohorts to be subdivided at arbitrary masses. It therefore does not establish that the discrete optima in Theorems 3 or 4 equal, or closely approximate, the continuous optimum. The crucial follow-up is to bound the rounding gap as a function of population size, support size, and endpoint count, and to determine when a finite cohort can realize the continuous allocation with exactly one connected piece per member. That gap limits the hardness claim, but it does not erase the mirror: a large population with repeated valuation profiles is a sensible instance regime, and its continuous welfare question is precisely stated and efficiently solvable.
The paper does have named computational results, so the strongest decisive objection is unavailable. Theorem 4 proves NP-hardness for normalized one-segment valuations; Theorem 3 proves an approximation hardness result for valuations with at most two segments. Both are legitimate anchors. But the proponent’s continuous model does not yet show that either theorem has a faithful population mirror.
In both proposed mirrors, \(W_t \ge \mu_t F_t\) guarantees enough *total* value for a type. It does not by itself specify how to give every member of that type a proportional share in one connected piece. The claim that the cohort can be divided among the allocated intervals needs a realization or limit argument: it must show that the interval pieces can be assigned to individuals, each meeting their own threshold, while preserving connectedness. Without that, the endpoint-refinement LP solves a multi-piece, type-level allocation problem. That is precisely the feature the paper sets aside when it imposes \(n-1\) cuts. The paper also notes that multi-piece proportional or envy-free welfare optimization already has an LP treatment, so these mirrors risk repackaging the tractable model while dropping the paper’s central constraint.
That objection applies separately to both anchors. For Theorem 4, the one-segment restriction makes the proposed LP especially simple, but does not fix the missing connection between aggregate type value and connected individual allocations. For Theorem 3, allowing two segments changes neither issue: the LP still gives each type fractional access to cake and does not encode the ordering of connected pieces. The hardness reductions use many different valuation profiles. Grouping exact duplicates into types may leave \(\tau\) close to \(n\) on those instances, though that limits what the reductions establish rather than ruling out a new repeated-type regime.
A stronger mirror could retain the ordering constraint directly. Label population mass by \(y\in[0,1]\), assign each label a type \(\theta(y)\) with distribution \(\mu\), and map labels monotonically to cake cuts \(x(y)\). Each infinitesimal agent then receives one interval, with proportionality expressed as a value-per-unit-mass condition. The objective is to choose the type order and cuts. This is a more faithful continuation of the paper’s problem than the cohort LP, but it needs a precise finite-to-continuous correspondence; it is an ordering or control problem, not the endpoint LP. A rule that puts each type in one contiguous block is another possible model, but that adds a coalition-contiguity restriction absent from the paper.
There is a sensible high-multiplicity scenario here: many residents with identical valuation profiles dividing a territory. The paper’s emphasis on connected pieces does not make that regime implausible. So the strongest case against is that the proponent has not justified the claimed connected-piece interpretation, and that the LP mirrors remove the paper’s distinctive computational constraint. I cannot honestly extend that into the universal claim that no worthwhile mirror exists: the connected, mass-indexed ordering problem remains a plausible mirror, and its value is unresolved.
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.