{"id":"3bbabc04-c8ac-4ce1-a565-d3f6861b02f7","arxiv_id":"2506.00909","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new algorithmic framework guarantees a fixed fraction (between 15% and 63%) of optimal online revenue for consecutive-stay seat and room allocation, with or without customer choice.","lead":"This paper designs fast algorithms for selling seats or rooms when each customer needs a block of consecutive seats or nights, and proves the algorithms earn at least a fixed percentage of the best possible online strategy. The results give the first constant-factor guarantees for this class of revenue management problems, where earlier bounds shrank as the stay length grew.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the constant-factor approximation results are internally consistent and the proof chain (LP upper bound, proposal-discarding independence, correlation-gap and coupling bounds) holds up under scrutiny.","rationale":"The central claim is that polynomial-time policies achieve constant-factor approximations against the online optimum. This rests on three pillars: the fluid relaxations upper-bound V(I); the virtual-status construction realizes the LP/SBLP marginals while preserving feasibility and independence; and the per-period revenue lower bounds convert those marginals into constant factors. I examined each pillar. The mapping from any feasible policy to an LP solution is valid, so the upper bounds hold. The independence of virtual statuses is the most delicate point, but the proposal-discarding mechanism is purpose-built to couple updates with independent Bernoulli coins (or the Random/General-Random coupling subroutines), and Propositions 2, 6, and 9 supply the needed inductive argument with regularity conditions verified. I could not construct a violation. The BAM analysis is intricate, but inequalities (14) and (15) are valid uses of Jensen/convexity and the layer-cake formula, and Lemma 5 is correct. The general-arrival extension uses attenuation correctly, and Lemma 9's hypotheses are satisfied. The hardness and integrality-gap sections are secondary and do not affect the positive guarantees. Minor presentation issues—such as the abstract's 0.156 versus the exact 0.158 and the terseness of some 'straightforward' appendix proofs—do not threaten correctness. Therefore the reader's ACCEPT verdict should stand unchanged.","tokens_in":35789,"tokens_out":50705,"duration_ms":504173,"concrete_test":"Run a brute-force verifier on small random instances (for example M,N,T≤4): compute V(I) by exact dynamic programming, solve the LP/SBLP, simulate Algorithms 1–3 many times to estimate expected revenue, and confirm that Vπ(I) is at least the claimed constant times LP(I)/SBLP(I) and that simulated virtual-status marginals match the LP x-variables and are independent across resources.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the load-bearing steps of the main theorems. Lemma 2/4/7 correctly show V(I)≤LP(I)/SBLP(I) by feasible-policy arguments. The virtual-status construction (Property 1) preserves feasibility, the LP/SBLP marginals via the Balance equations, and independence across resources, because proposals use independent coins and the discarding rules are coupled with arrival/choice through Random/General-Random; the regularity conditions (8) and (24) are verified by S⊆P and the definitions of q and q′. Theorem 1's application of the correlation gap is valid since max-weight is monotone submodular and total proposal probability is at most 1. Theorem 2's small/large attractiveness bounds are correctly derived, and Lemma 5 supplies the 1/4 constant. Lemma 8 follows Fleischer et al. and correctly yields the extra 1−1/e factor. I found no internal inconsistency. The consecutive-stays assumption is a modeling restriction rather than a hidden gap. The abstract's numerical value 0.156 is a slight rounding slip for 1/4·(1−1/e)≈0.158, and some appendix proofs are terse, but neither affects correctness.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies network revenue management with consecutive stays, where each request requires a contiguous interval of slots on a single resource. It considers two scenarios: accept-or-reject, and a BAM-based assortment setting with customer choice. For Bernoulli arrivals, it develops polynomial-time policies with approximation ratios of 1-1/e and 1/4 relative to the optimal online policy; for general arrivals, it obtains (1-1/e)^2 and (1/4)(1-1/e). The proofs are built on fluid relaxations (LP and SBLP), a decomposable state representation via maximal sequences, a proposal-discarding mechanism with virtual resource statuses, and coupling arguments. The paper also proves an offline NP-hardness bound of 0.95+epsilon and gives integrality-gap examples.","tokens_in":36079,"tokens_out":40340,"duration_ms":394423,"significance":"If correct, this is the first constant-factor approximation framework for this class of NRM problems when benchmarked against the online optimum, a meaningful advance over the prior nonconstant, L-dependent guarantees. The constants are explicit and parameter-free, the fluid relaxations are derived from necessary conditions of online policies rather than fitted, and the proof chain is largely self-contained. The consecutive-stays assumption is the key modeling restriction that makes the state-space compression and the decomposable property possible; the results do not extend to arbitrary slot subsets or multi-resource requests. The paper also contributes the first integration of a choice model into the proposal-discarding framework.","major_comments":[],"minor_comments":[{"comment":"The abstract reports 0.156 for the BAM-based scenario under general arrivals, but 1/4*(1-1/e) is approximately 0.158; please correct the rounding.","section":"Abstract"},{"comment":"Line 8 of Algorithm 5 can overwrite k_j with a later type when an earlier X for the same resource was already 1, contradicting the earliest-success rule stated in (EC.6) and the coupling described in the text; the pseudocode should add the guard 'if k_j=0' before assigning k_j.","section":"EC.4.2, Algorithm 5"},{"comment":"The assertion that an optimal solution 'must still assign each θ_i' is not immediate and needs a short justification; one can assign a skipped variable request to the literal resource that currently serves fewer clause requests, losing at most c_i/2 clause revenue while gaining c_i/2 variable revenue, so there is an optimal solution with all variable requests assigned.","section":"EC.2.2, Proof of Proposition 3"},{"comment":"The proposal probabilities divide by p_t (or p_t^(k)); for periods or types with zero arrival probability, the convention that the proposal probability is zero should be stated explicitly.","section":"Section 5, Algorithm 1 and Algorithms 2-3"},{"comment":"The derivation of the unconditional expected revenue from the conditional bounds (14)-(15) silently multiplies by p_t; please make this multiplication explicit so the reader can follow the transition from conditional revenue to E[revenue in period t].","section":"Section 6, Proof of Theorem 2"},{"comment":"The statement that at the minimum the two terms inside the maximum must be equal is correct but terse; a one-sentence justification (if one term were larger, shifting probability mass would reduce the maximum) would improve readability.","section":"EC.3.3, Proof of Lemma 5"},{"comment":"In line 6 of Algorithm 4, the expression (q_j-z_j)/(1-z_j) is undefined when z_j=1; this case is handled implicitly by the coupling, but the 0/0 convention should be stated.","section":"EC.3.2, Algorithm 4"}],"recommendation":"minor_revision","confidential_remarks":"This is a strong contribution with sound central proofs and only local issues to fix. I recommend minor revision. The most important fixes are the rounding slip in the abstract, the guard in Algorithm 5's pseudocode, and the short justification in the NP-hardness proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Take it seriously. This paper gives the first constant-factor approximation ratios against the online optimum for network revenue management with consecutive stays, and the central arguments hold up under checking. I verified the main chain: the fluid relaxations are valid upper bounds (Lemmas 2, 4, 7), the virtual-status construction preserves feasibility and independence (Property 1), and the correlation-gap and coupling steps in Theorems 1 and 2 are sound. The general-arrivals extension with attenuation is also correct.\n\nThe genuinely new content: it moves the proposal-discarding framework from online matching into NRM with a richer state space (maximal sequences), integrates customer choice into that framework for the first time, and adds a clean NP-hardness bound of 0.95+epsilon for the offline version. The 1/4 constant for BAM is not pulled from thin air; the small/large attractiveness partition and the technical lemma that yields 1/4 are solid.\n\nSoft spots are minor. The consecutive-stays assumption is the load-bearing modeling restriction; without it, the O(N^2) state representation and the decomposable property collapse. That is stated clearly, but readers should not expect the techniques to port to arbitrary resource requirements. The appendix, especially the General-Random subroutine, is terse; the correctness claims are believable but would benefit from more intuition and a worked example. The abstract says 0.156 for 1/4(1-1/e); the value is about 0.158. Cosmetic.\n\nOne substantive caveat: the benchmark is the online optimum, not the offline optimum. When measured against offline, the guarantees are nonconstant (as prior work shows). The authors are explicit about this, and the online-optimum benchmark is the right one for this research program, but it is worth keeping in mind when interpreting \"constant-factor.\"\n\nVerdict: this deserves a serious referee. The proofs are reparably terse in places, but the results are new, the analysis is non-circular, and the main theorems are correct. I would bring it to the reading group and I would cite it.","headline":"Solid paper that delivers the first constant-factor approximations against the online optimum for consecutive-stays revenue management; the proofs check out, with only minor presentation issues.","tokens_in":36557,"tokens_out":2477,"would_cite":true,"duration_ms":22594,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90B50"],"pacs":[],"model":"deepseek-v4-flash","headline":"Consecutive-stay revenue management admits polynomial-time policies with constant-factor guarantees against the optimal online algorithm: 1−1/e for accept-or-reject and 1/4 for customer choice under Bernoulli arrivals.","keywords":["network revenue management","consecutive stays","online optimum","philosopher inequality","proposal-discarding algorithm","basic attraction model","assortment optimization","approximation ratio"],"falsifier":"Compute the exact online optimum by dynamic programming on small exhaustive instances (for example, up to 3 resources, 4 slots, and 25 periods under Bernoulli arrivals) and simulate Algorithms 1 and 2 on the same instances; a single instance where Algorithm 1 earns less than (1−1/e)·V(I) or Algorithm 2 earns less than 0.25·V(I) would refute Theorems 1 and 2, and the same test on Algorithm 3 would test the general-arrival constants. Independently, recompute the paper's own integrality-gap constructions, which should yield V(I)/LP(I) ≈ 0.8134 in the L=2 example and V(I)/SBLP(I) ≈ 0.7941 in the BAM example; values far from these would signal an error in the examples.","tokens_in":35643,"feed_emoji":"🚄","tokens_out":13104,"duration_ms":116377,"temperature":0.7,"pith_summary":"This paper claims that network revenue management with consecutive stays — requests for contiguous blocks of slots on a single resource, as in railway seat sales and hotel room bookings — admits polynomial-time policies whose expected revenue is a constant fraction of the optimal online policy's revenue, with the constant independent of the maximum stay length L. Under Bernoulli arrivals, the fractions are 1−1/e ≈ 0.632 for the accept-or-reject scenario and 1/4 for the customer-choice (BAM) scenario; under general random request types both fractions lose an additional factor of 1−1/e, giving (1−1/e)² ≈ 0.399 and (1/4)(1−1/e) ≈ 0.158. These are the first constant-factor guarantees for these problems measured against the online optimum, in contrast to prior nonconstant ratios such as O(log log L/log L) or Ω(1/L) that were measured against the offline optimum — a benchmark so strong that constants are provably impossible even for a single resource. If the results stand, a booking platform can implement a simple polynomial-time rule and be guaranteed a fixed fraction of the revenue of a clairvoyant policy that knows the demand distribution but not its realizations, matching in the basic scenario the best known offline approximation ratio.","feed_headline":"Booking policies guarantee 63% of optimal online revenue","feed_subtitle":"Polynomial policies for consecutive stays hit 63% and 25% of the online optimum, independent of stay length.","key_machinery":"The argument runs on four interlocking pieces. First, the consecutive-stays assumption compresses each resource's state into its maximal sequences of available slots — at most O(N²) per resource — and the value function decomposes additively over these sequences, yielding a polynomial-time optimal dynamic program for a single resource and the state representation for all that follows. Second, a fluid relaxation (a linear program, or a sales-based linear program for the choice scenario) upper-bounds the online optimum through a constraint that allocation probabilities cannot exceed availability probability times arrival probability — a constraint online policies satisfy but the offline optimum does not. Third, the algorithms adapt the proposal-discarding framework: each resource independently proposes to serve the arriving request with probabilities read off the fluid solution, the platform selects the highest-revenue proposal (or the revenue-maximizing assortment of proposers), and unselected proposers are discarded through a virtual resource status that marks slots unavailable even when physically free, which preserves probabilistic independence across resources. Fourth, for general arrivals, attenuation factors — offering the assortment to a given customer type only with a prescribed probability — together with a two-dimensional coupling subroutine restore independence at the cost of an extra factor 1−1/e, converted into the final bounds by the correlation-gap lemma and the separable-assignment inequality.","core_discovery":"The paper establishes, through four theorems, that constant-factor approximation ratios against the optimal online algorithm are achievable in polynomial time for network revenue management with consecutive stays. In the accept-or-reject scenario under Bernoulli arrivals, the proposal-discarding policy achieves 1−1/e of the online optimum, and the paper complements this with a gap-preserving reduction from MAX-3SAT showing that even the offline version is NP-hard to approximate within 0.95+ε, while the 1−1/e bound is tight for the algorithm and matches the best known offline approximation for interval scheduling. In the BAM-based scenario, where the platform offers an assortment and the customer chooses under the basic attraction model, a sales-based fluid relaxation plus a randomized coupling subroutine yields a 1/4 guarantee. When request types are themselves random, the same machinery with attenuation factors yields (1/4)(1−1/e) for the BAM scenario and (1−1/e)² for the accept-or-reject scenario. The authors present these as the first constant-factor guarantees for the consecutive-stays structure, explicitly benchmarked against the online optimum because the offline optimum cannot sustain constants.","pith_inferences":["The enabling move is the benchmark choice itself — the online optimum is not a weaker consolation prize but the only benchmark on which constant-factor results for this problem class can live, because a single-resource lower bound rules out constants against the offline optimum; papers that insist on the offline benchmark should expect stay-length-dependent losses no matter the algorithm.","The machinery is not obviously tied to intervals — any resource-requirement structure whose state space consists of polynomially many 'maximal components' with an additive decomposition (laminar or path-shaped requests, for example) is a plausible candidate for the same proposal-discarding-plus-coupling argument, and testing that is a natural next step.","The attenuation mechanism puts a worst-case price on type heterogeneity — random stay lengths cost exactly a factor 1−1/e — suggesting that demand forecasting and stay-segmentation are worth roughly that factor of revenue in practice.","The coupling subroutines are reusable primitives — any platform that must translate intended choice probabilities into independent per-resource state transitions could adopt them without the rest of the revenue-management machinery."],"forward_implications":["A platform running the accept-or-reject policy is guaranteed at least 1−1/e ≈ 63.2% of the optimal online policy's expected revenue, the same ratio as the best known offline approximation for interval scheduling, so worst-case online uncertainty costs nothing at the level of the ratio.","The 1−1/e ratio is tight for the algorithm, and since the offline version is NP-hard to approximate within 0.95+ε, any further improvement would likely require a better offline approximation first.","With customer choice under BAM, the guaranteed fraction falls to 1/4 with fixed request types and to (1/4)(1−1/e) ≈ 15.8% with random request types, quantifying the revenue cost of choice and type uncertainty.","The fluid relaxations used for the upper bounds are not tight — integrality gaps of at most 0.8134 for the accept-or-reject LP and 0.7941 for the BAM SBLP — so the gap between the algorithms and their upper bounds is an explicit open target.","Under general arrivals the random type structure costs exactly one extra factor 1−1/e in both scenarios, giving (1−1/e)² ≈ 39.9% for accept-or-reject and 15.8% for BAM."],"supporting_citations":[{"why":"Supplies the proposal-discarding framework — virtual copies and discarding of unselected proposers — that Algorithms 1–3 generalize from online matching to resource states.","marker":"Braverman et al. (2025)"},{"why":"Supplies the independent-proposal stage and max-weight selection that Algorithm 1 inherits directly.","marker":"Braverman et al. (2022)"},{"why":"Initiates the online-optimum benchmark and the (Online) constraint used in the fluid relaxations, and provides the hardness and integrality-gap starting examples.","marker":"Papadimitriou et al. (2024)"},{"why":"Provides the sales-based linear program that models customer choice in the BAM scenario.","marker":"Gallego et al. (2015)"},{"why":"Provides the correlation-gap lemma that turns independent proposals into the 1−1/e revenue lower bound.","marker":"Agrawal et al. (2010)"},{"why":"Provides the inequality that converts the attenuation factors under general arrivals into the extra 1−1/e loss.","marker":"Fleischer et al. (2011)"},{"why":"Establishes the (1−1/e) offline approximation for interval scheduling that the online ratio matches and tightness is measured against.","marker":"Bhatia et al. (2007)"},{"why":"Gives the prior O(log log L/log L) competitive ratio against the offline optimum, the nonconstant benchmark the new constants supersede.","marker":"Chawla et al. (2019)"}],"fun_headline_variants":["Constant-factor revenue guarantees for consecutive stays","63% and 25% of online optimum guaranteed by policies","Polynomial policies secure constant online revenue share","First constant-factor algorithms for stay-based revenue","Booking revenue: guaranteed 63% of online optimum"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire construction rests on the consecutive-stays assumption: every request must want one contiguous block of slots on a single resource, and if a request could consume scattered slots or span several resources, the compact state representation and the decomposition property collapse, leaving the paper with no constant-factor claim.","fun_headline_variants_meta":{"raw":{"variants":["Constant-factor revenue guarantees for consecutive stays","63% and 25% of online optimum guaranteed by policies","Polynomial policies secure constant online revenue share","First constant-factor algorithms for stay-based revenue","Booking revenue: guaranteed 63% of online optimum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000939,"raw_usage":{"total_tokens":4059,"prompt_tokens":1034,"completion_tokens":3025,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":650,"completion_tokens_details":{"reasoning_tokens":2954}},"tokens_in":650,"tokens_out":3025,"duration_ms":26367,"temperature":1.0,"reasoning_tokens":2954,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:57:02.127617+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact online optimum by dynamic programming on small exhaustive instances (for example, up to 3 resources, 4 slots, and 25 periods under Bernoulli arrivals) and simulate Algorithms 1 and 2 on the same instances; a single instance where Algorithm 1 earns less than (1−1/e)·V(I) or Algorithm 2 earns less than 0.25·V(I) would refute Theorems 1 and 2, and the same test on Algorithm 3 would test the general-arrival constants. Independently, recompute the paper's own integrality-gap constructions, which should yield V(I)/LP(I) ≈ 0.8134 in the L=2 example and V(I)/SBLP(I) ≈ 0.7941 in the BAM example; values far from these would signal an error in the examples.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the proposal-discarding framework — virtual copies and discarding of unselected proposers — that Algorithms 1–3 generalize from online matching to resource states."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the independent-proposal stage and max-weight selection that Algorithm 1 inherits directly."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the sales-based linear program that models customer choice in the BAM scenario."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the inequality that converts the attenuation factors under general arrivals into the extra 1−1/e loss."}],"review_version":1}