| paper | d4-conf-aaai-2017-0239 |
| 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 in \(O(L)\) bit operations. Feasible distributions with \(K\leq B\) exist exactly when \(B\geq1\); the optimum is always \(K=1\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a population scale \(N\), a finite support \(T\) of piecewise-constant valuation types on \([0,1]\), and rational masses \(\mu_t\) summing to \(1\), with the types satisfying the intersection property, choose finite-support distributions \(q_t\) over bundles that are finite unions of intervals. Require that every mass unit receives a whole bundle, that \(\sum_{t\in T}\mu_t q_t(\{P:x\in P\})=1/N\) almost everywhere, and that every type weakly prefers every bundle in its distribution’s support to every bundle in any type’s support. Find distributions minimizing \(K=\sum_{t\in T}\mu_t\sum_P q_t(P)k(P)\), where \(k(P)\) is the number of intervals in \(P\).
A mass society over piecewise-constant valuation types, with within-type distributions over whole bundles. The resource constraint assigns mass \(1/N\) to each cake point, envy is compared across supported bundles, and the objective is the average number of intervals per person.
An explicit finite-support \(q_t\) may require \(\Omega(N)\) bundle atoms, so a runtime polynomial in \(\log N\) needs a succinct output format; this limits compression but does not invalidate the cut-density question.
fatal: False
The mirror covers Theorem 6’s envy-free allocation result for piecewise-constant valuations satisfying the intersection property; lifting its clone allocation gives \(K<2m\), but does not minimize \(K\). It leaves the other allocation results and the paper’s truthfulness results unmirrored.
The strongest positive case is a narrow one: the paper’s result for piecewise-constant valuations under the intersection property, in a large market of advertisers whose preferences follow a small number of standard templates. A type is the advertiser’s complete value-density function over the schedule. The mass \(\mu_t\) is the fraction of advertisers with type \(t\). A plausible regime has \(N\) campaigns but only \(\tau\) templates, with \(N\gg\tau\); for example, many campaigns may value the same standard dayparts, with different weights.
My anchor is Theorem 6, proved in this paper: for \(n\) players with piecewise-constant valuations having \(m\) steps, if the intersection property holds, there is a polynomial-time algorithm that finds an envy-free allocation using \(O(nm)\) cuts. The intersection property says that each valuation interval of a player intersects exactly one valuation interval of every other player. The paper’s proof applies EFGISM to \(nm\) interval-valued players, giving a cut bound linear in both \(n\) and \(m\), then combines each original player’s pieces.
Here is a continuous version I would hand to a prover. Call it minimum cut density for a mass society. An instance gives a population scale \(N\), a finite support \(T\) of piecewise-constant valuation types on \(C=[0,1]\), and rational masses \(\mu_t\geq0\) summing to \(1\). Each type has \(m\) value intervals, and the type supports satisfy the intersection property. An allocation is a finite-support distribution \(q_t\) over bundles \(P\subseteq C\), each bundle a finite union of intervals. It means that fractions of type \(t\)’s mass receive different bundles; every individual still receives one integral bundle. Write \(k(P)\) for the number of intervals in \(P\), and \(V_t(P)=\int_P\nu_t(x)\,dx\).
Require that, for almost every cake point \(x\),
\[
\sum_{t\in T}\mu_t\,q_t\bigl(\{P:x\in P\}\bigr)=\frac1N.
\]
This is the normalized resource constraint: in an \(N\)-person finite allocation, each cake point belongs to one person, so it is assigned to a fraction \(1/N\) of the population. Require envy-freeness as well: for every type \(t\), every bundle \(P\) in the support of \(q_t\), and every bundle \(Q\) in the support of any \(q_s\),
\[
V_t(P)\geq V_t(Q).
\]
The question is to find such an allocation minimizing
\[
K(q)=\sum_{t\in T}\mu_t\sum_P q_t(P)\,k(P).
\]
A solution is the distributions \(q_t\) and their bundles. \(K\) is the average number of allocated intervals per campaign; for a finite partition, the number of cuts is the total number of allocated intervals minus one. This makes \(K\) the natural per-campaign cut rate as \(N\) grows. The theorem’s \(O(nm)\) bound corresponds to an \(O(m)\) rate on finite clone instances, though it does not itself establish an algorithm for the mass problem.
I expect this restricted problem to be tractable (Class A). The mass variables let the algorithm split a type across bundle choices while keeping each person’s bundle integral. Once a menu of bundles is fixed, the mass and resource constraints are linear; the central open algorithmic question is whether bundle pricing can be done efficiently under the intersection property. A high-multiplicity algorithm should aim to run in \(\operatorname{poly}(\tau,m,L,\log N)\), rather than enumerate all \(N\) clones. This is a conjecture for the mirror, not a consequence of Theorem 6.
This case covers only Theorem 6’s envy-free small-cut allocation result under its structural assumption. It does not extend the paper’s strategyproof results: truthfulness in a nonatomic population needs its own direct-mechanism definition. The introduction cites Deng, Qi, and Saberi’s PPAD-completeness result for the general minimum-cut problem, but that is not a numbered result proved here and cannot serve as an anchor under the stated rule.
The weak point is the normalization. With a fixed cake and an unbounded population, each person’s share shrinks and the total cut count grows, so the mirror asks about cut density rather than a finite minimum number of cuts. I think the authors could recognize the mass allocation as their problem’s high-multiplicity form: the resource is still one schedule, envy compares actual bundles, and only the distribution of bundles within a type is fractional. But the cut-density objective is a deliberate asymptotic formulation, and Theorem 6’s polynomial dependence on \(n\) does not show that it compresses to dependence on \(\tau\) and \(L\). That compression—and whether the intersection property is necessary for it—is the main further question.
Theorem 6 is a real computational result, so “there is nothing computational to mirror” cannot carry the negative case. The best objection is that minimum cuts depends on a population scale that a type distribution \(\mu\) does not contain. The proponent adds \(N\), the number of people, and normalizes the objective to average intervals. That is sensible as a proposed asymptotic problem, but it creates a dilemma for the mirror.
For any positive length bundle \(P\) in the proposed model, the resource constraint implies \(\mu_t q_t(P)\leq 1/N\): at an interior point of \(P\), the mass receiving it cannot exceed the total \(1/N\) assigned that point. Thus a type of positive mass needs at least \(N\mu_t\) bundle atoms. If those atoms must correspond to whole people, their masses must also be quantized in units of \(1/N\), and the model is a finite clone instance whose explicit allocation grows with \(N\). If quantization is dropped, some atoms represent less than one person. And if \(N\) tends to infinity, the right side of the resource constraint tends to zero; the finite cut count becomes infinite, while \(K\) is a newly defined rate that needs its own limiting model and output representation. That makes the proposed mirror a substantial asymptotic partition problem, rather than a direct continuization of Theorem 6.
There is a narrower version closer to the theorem: replicate each type into \(N\mu_t\) finite players, apply Theorem 6, and divide its \(O(Nm)\) cut bound by \(N\). This gives an \(O(m)\) rate, but it uses the paper’s algorithm on all the clones. To ask for a better algorithm depending on support size and bit length, or to minimize the rate \(K\), is a new and stronger question. The theorem establishes a feasible allocation with a bound; it does not optimize \(K\). The proposed schedule scenario also strains the paper’s motivation: if each of many advertisers receives a vanishingly short slot, those slots may be unusable—the very problem the paper gives for excessive fragmentation.
The paper’s truthfulness theorems are even less promising as continuous anchors: a single infinitesimal agent cannot affect the aggregate, so individual strategyproofness risks becoming vacuous. But that does not defeat the envy-free allocation anchor. High multiplicity among repeated task or preference types is plausible, and an asymptotic cut-rate problem could be worth studying if its authors accept the new objective and representation. So the negative case is weak at its central point: the scale and output issues make the proposed mirror under-specified and more ambitious than Theorem 6, but they do not show that no worthwhile continuous mirror exists.
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.