| paper | d4-conf-aaai-2014-0258 |
| 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: A deterministic online policy running in time polynomial in \(m,\tau,L\) exists and guarantees \(\mathrm{ALG}\ge\tfrac12\mathrm{OPT}\) for every admissible arrival sequence. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite horizon \(T\), a finite support \(\Theta\) of types \(\theta=(a_\theta,d_\theta,v_\theta)\) with rational masses \(\mu_\theta\), and shared discount functions \(F,D\), each arriving type mass is revealed at its arrival slot while future arrivals remain unknown. With per-capita capacity \(q\) per slot, does there exist an online allocation policy assigning mass \(x_{\theta,t}\) only for \(a_\theta\le t\le d_\theta\), with \(\sum_t x_{\theta,t}\le\mu_\theta\) and \(\sum_\theta x_{\theta,t}\le q\), whose welfare \(\sum_{\theta,t}x_{\theta,t}\max\{v_\theta F(t)+D(t),0\}\) is at least half the offline optimum for every arrival sequence?
A finite-support online welfare allocation problem: types carry mass \(\mu_\theta\), arrival and departure slots, and time-discounted values; each slot has capacity \(q\). The policy may split type mass at a value cutoff, corresponding to serving a subset of otherwise identical individuals, and is compared against an offline allocator that knows all arrivals.
The main mirror covers Theorem 1’s \(2\)-competitive welfare guarantee; Theorem 2 has a separate recognizable truthfulness mirror, while the numerical comparisons are outside these questions.
The strongest mirror is the paper’s online welfare allocation problem. There is no named NP-hardness, tractability-class, or parameterized-complexity theorem in the paper. Its two named results concern a mechanism’s competitive welfare guarantee and strategy-proofness; both are proved here. The introduction also gives polynomial running times for the allocation and payment algorithms, but those are not stated as numbered complexity results.
Theorem 1 states that the authors’ online auction mechanism for time-discounting values is \(2\)-competitive. In their model, each agent wants at most one unit, can receive it in a time slot between arrival and departure, and values it according to a discounted valuation curve. The auctioneer has \(g\) identical, reusable or reproducible items per slot. The proof is in the paper. The mechanism uses a greedy allocation rule; the introduction reports \(O(n\log n)\) time for allocation and \(O(n^2T\log n)\) for payment determination.
For its continuous mirror, consider a finite horizon \(T\) and a finite support \(\Theta\) of types \(\theta=(a_\theta,d_\theta,v_\theta)\). Each type specifies arrival, departure, and intrinsic value; all types share known discount functions \(F,D\), so \(v_\theta(t)=\max\{v_\theta F(t)+D(t),0\}\) while the type is present. The input gives each type’s rational mass \(\mu_\theta\), with total mass normalized to one. At each slot, the mass of newly arriving types is revealed, but future arrivals are unknown.
Let \(q\) be per-capita supply per slot: along a discrete sequence with \(n\) agents, supply scales as \(g_n/n\to q\). The decision variable \(x_{\theta,t}\) is the mass of type \(\theta\) served at time \(t\). It must be zero outside that type’s interval, satisfy \(\sum_t x_{\theta,t}\leq\mu_\theta\), and satisfy \(\sum_\theta x_{\theta,t}\leq q\) in each slot. Ask for an online allocation policy whose welfare \(\sum_{\theta,t}x_{\theta,t}v_\theta(t)\) is at least half the welfare of the offline optimum, which knows all arrivals in advance. A solution is the policy and its feasible allocations as each cohort arrives.
I expect this problem to be tractable (Class A). The natural mirror of the paper’s greedy rule sorts currently available type masses by their discounted value and allocates up to \(q\), splitting a cohort at the cutoff. The paper’s \(2\)-competitive argument appears to carry over by replacing sums over agents with integrals over mass. With finite support, the direct implementation would process at most \(\tau=|\Theta|\) types per slot, giving a natural target of \(O(T\tau\log\tau)\) arithmetic operations. Whether the exact guarantee survives all tie and fractional-allocation details is part of the question for a prover.
This is plausible in a large cloud-service or advertising market with many requests following a small set of standard templates: common arrival and departure windows, service value, and discount curve. There, \(n\) can be large while \(\tau\ll n\). A mass allocation means that a stated fraction of a cohort is served; each individual still receives either the full unit or no unit, with the fraction implemented as a per-person lottery. This matches the paper’s objective of allocating scarce time-sensitive service online for social welfare.
Theorem 2 states that the authors’ mechanism is strategy-proof for online auctions with time-discounting values. The result is proved in the paper using Lemma 1, which establishes truthful intrinsic-value reporting as a dominant strategy for any proposed presence interval, and Lemma 2, which establishes truthful arrival and departure reporting. The paper also asserts individual rationality. Lemma 2’s proof is omitted for space, but the theorem is presented as a result of this paper, not as a citation.
The corresponding continuous mechanism-design question uses the same mass input and capacity scaling. Reports arrive online; an agent may report a later arrival or earlier departure than their true times, as in the paper, and may misreport intrinsic value. The mechanism chooses feasible per-type, per-slot allocation probabilities and per-capita payments. For each infinitesimal participant, define utility from winning at \(t\) as \(v_\theta(t)-p_{\theta,t}\), and utility from losing as zero. Ask for an online direct-revelation mechanism that makes truthful reporting dominant, is individually rational under truthful participation, and retains the \(2\)-competitive welfare guarantee. A solution is the allocation-and-payment rule satisfying those properties. I expect this to be tractable as well, though less confidently than the allocation question: the paper’s candidate-winning-slot and payment calculations suggest a finite-support algorithm, but threshold payments at fractional cohort cutoffs and incentive constraints for arrival-time reports need to be proved carefully.
This is the weaker mirror. Individual truthfulness in a nonatomic population needs a precise per-person lottery and payment interpretation, and the paper’s finite-agent proof does not automatically supply it. The capacity scaling is also essential: keeping \(g\) fixed while population grows would make per-capita supply vanish. Still, scaling supply with demand is a natural large-market regime for these reusable services, and the paper’s mechanism is explicitly built around exactly the type features—arrival, departure, and discounting value—that the continuous types preserve. The mirror covers the online allocation and incentive guarantees, not the paper’s experimental comparisons.
The strongest case against is that these two anchors amount to one mechanism result: Theorem 1 analyzes the greedy allocation rule, and Theorem 2 supplies payments that make it strategy-proof. The proposed continuous questions alter the operating regime—capacity must scale with population, cohorts can be split, and individuals need lottery allocations—so they are not verbatim extensions of the paper’s mechanism.
That objection does not hold up under ChoCo’s scope. Scaling supply with population is an allowed co-modification, and a mass of agents with identical arrival, departure, and value is a credible large-market cohort. Fractional cohort allocation can be implemented as per-person lotteries. For Theorem 1, the online input can reveal cohort masses slot by slot, and the greedy rule and its competitive comparison have a natural mass analogue. I see no fundamental obstacle to asking whether the \(2\)-competitive guarantee survives.
Theorem 2 has a sharper modeling gap: aggregate masses alone do not specify the effect of one person’s deviation, since an individual has measure zero. A mirror would need to define pointwise allocation probabilities and payments for a tagged participant against the aggregate population. But the proponent explicitly supplies that interpretation through per-person lotteries and per-capita payments. It is a real proof obligation, not evidence that the question is ill-posed; truthful reporting in the continuum remains a meaningful property.
So the negative case is weak. The mirrors may turn out to be fluid versions of the paper’s existing arguments, and the proposed work may be narrower than a complexity classification of a new hard problem. That is a concern about what the answers will contribute, not a sound reason to reject the questions. I cannot honestly defeat either anchor, including its stronger cohort-based formulation.
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.