| paper | d4-conf-ecai-2012-0140 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The proposed cohort time-sharing LP is a statable population extension, but it does not supply the required computational result from this paper. Proposition 8 gives a bound used in branch-and-bound, while the paper's algorithms have no numbered guarantee and its complexity claim remains open. The LP also averages independent risk within each type, changing the paper's individual ex-post objective into type-average ex-ante welfare.
fails bit a — no named computational result to mirror
Independent slot failures average out within each type, so the proposed max-min objective becomes type-average ex-ante welfare, rather than the paper's individual ex-post objective.
fatal: True
The proposed model covers cohort time-sharing under a type-average fairness criterion; it leaves the paper's individual ex-post objective and Proposition 8's computational role unmirrored.
The strict anchor test leaves this paper with no fully eligible result. Its numbered Propositions 1–8 establish welfare identities and inequalities, but none classifies a problem as tractable or hard. The paper says computing ex-post egalitarian utility is *suspected* to be #P-complete and leaves the question open; its branch-and-bound and Monte Carlo methods are described in Section 4 without a numbered computational theorem.
The closest anchor is Proposition 8, asserted here with its proof omitted for space. For a concave collective utility function \(G\), allocation \(\pi\), and subset \(O_{\rm ea}\) of objects evaluated ex ante, it states
\[
\operatorname{pcu}(\pi)\leq \operatorname{mcu}(\pi,O_{\rm ea})\leq \operatorname{acu}(\pi).
\]
Here \(\operatorname{mcu}\) takes expected utility for objects in \(O_{\rm ea}\) and realized utility for the remaining objects. When \(G=\min\), it also bounds the gap above \(\operatorname{pcu}\) by \(\sum_{j\in O_{\rm ea}}p_j(1-p_j)w_{a(j),j}\), where \(a(j)\) receives object \(j\). The paper uses this bound to prune its exact search. It is a named, computationally used result, but it does not establish a complexity or algorithmic guarantee of the kind the anchor requirement asks for.
A plausible positive-side question around the allocator is Cohort Time-sharing under Risk. Consider many recipients grouped into \(\tau\) types, where each type has a common additive value vector \(w_{tj}\). Let \(\mu_t\) be each type’s population fraction, and let \(q_j\) be the per-person supply of recurring time-slot class \(j\). Each person still receives an integral bundle. Write \(x_{tB}\) for the mass of type \(t\) receiving bundle \(B\), with
\[
\sum_B x_{tB}=\mu_t,\qquad
\sum_{t,B:j\in B}x_{tB}\leq q_j.
\]
Copies of each slot class have independent good-condition probability \(p_j\). Ask for a feasible assignment maximizing the minimum, over types, of their average realized utility per person. In the large-population limit, independent conditions average out within each type. The problem reduces to an LP: with \(y_{tj}\) the mass of type \(t\) receiving class \(j\), maximize \(z\) subject to
\[
z\leq \frac{1}{\mu_t}\sum_j p_jw_{tj}y_{tj},\quad
0\leq y_{tj}\leq\mu_t,\quad
\sum_t y_{tj}\leq q_j.
\]
Any such marginals can be realized by distributing integral bundles across the type’s members. I would expect this version to be tractable.
The regime is plausible for recurring time-sharing among many municipalities or organizations with a bounded number of shared valuation profiles. The paper itself names time-sharing, satellite use, and telescope scheduling, though its experiments involve only 2–5 agents. This candidate continuizes the population and scales supplies per capita; it does not make the individual bundles divisible.
The weakness is substantial: the LP uses type-average welfare. The paper’s ex-post egalitarian objective takes the minimum utility across individuals before averaging over risk. Under independent risk, that individual minimum can become degenerate at large population sizes; replacing it with type averages changes the fairness criterion. Some authors might accept that as the natural cohort limit, but others may reject it as no longer their problem. And because Proposition 8 is only a computational bound, this is a plausible mirror, not a strong anchor-based case.
The strongest case against this mirror is that the proposed anchor is not a computational result of the kind ChoCo is meant to continuize. Proposition 8 bounds the welfare of a *fixed allocation* and the paper uses that bound to prune a search. But it gives no complexity classification or algorithmic guarantee. Section 4 has exact and heuristic algorithms, while the paper explicitly leaves its suspected \(\#\mathrm P\)-completeness result open. There is therefore no established computational result here for Proposition 8’s continuous counterpart to mirror.
The cohort time-sharing LP is a coherent model, but it changes the paper’s objective. The paper’s ex-post egalitarian welfare is \(\mathbb E[\min_i u_i]\); the proposed LP maximizes the minimum *type-average* expected utility. With per-capita supplies of independent copies, the average realized utility within each type converges to its expectation, so the risk that distinguishes the paper’s ex-post criterion washes out. The LP then captures an ex-ante objective, which Proposition 1 already reduces to a risk-free instance with expected weights. If instead one retains the minimum over individuals, a continuum of independent risky allocations typically makes it depend on worst-case outcomes—or collapse to zero—rather than on the paper’s probability-weighted ex-post welfare.
A stronger repair would preserve risk through common shocks to slot classes. The paper does mention dependent conditions as a possible extension, so that is not an absurd model. But it requires both persistent cross-copy correlation and group-average fairness to avoid the two problems above. Those choices may define a worthwhile new problem; they do not follow from Proposition 8 or preserve the paper’s individual ex-post objective.
That defeats the stated anchor and the particular LP as a mirror of it. The universal claim is less secure: the paper’s time-sharing examples make large cohorts plausible, and its authors might accept type-average welfare as a natural variant. The honest negative case is strong on the missing computational anchor, but it cannot establish that no worthwhile continuous problem could be built from the paper’s setting.
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.