{"id":"f6714509-7afb-4504-90f0-ba5816f05582","arxiv_id":"2507.23047","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"An online retailer buying and selling bundles with inventory caps can guarantee profit within O((1/epsilon) log(dv)) of the offline optimum, with matching lower bounds.","lead":"This paper gives an online algorithm for a retailer who buys and sells bundles of goods with storage limits, guaranteeing profit within a logarithmic factor of the best offline strategy. It also proves this ratio is essentially the best any online strategy can achieve, and extends the method to an incentive-compatible pricing scheme.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.8's final equivalence is not established: the cited bounds P≤v_cust and P≥(1+ε)v_supp do not imply bracket = O(net profit); a repeatable sale-buy cycle makes the ratio grow as 1/ε.","rationale":"I read the paper in good faith. The algorithmic idea is coherent: exponential-weight prices, LIFO accounting, and a dual-fitting skeleton are all plausible, and the lower bounds are mostly consistent with the claimed logarithmic rate. However, the proof of the main theorem has a real soft spot at the final step of Lemma 3.8, where the bracket is asserted to be O(ALG) using only P≤v_cust and P≥(1+ε)v_supp. Directionally these bounds leave an excess proportional to total customer revenue, and a constructed repeatable cycle shows bracket/profit ∼1/ε, so the chain of inequalities as written does not hold. This is a proof gap rather than a demonstrated falsity of the theorem: the actual dual value in the example is still O((η/ε)·ALG), so a sharper argument may repair it. The reader's weakest_assumption was the large-inventory condition; I agree that assumption is necessary, but I see the Lemma 3.8 final step as the more immediate obstacle to verifying the central claim. Since the reader already set CONDITIONAL and explicitly listed this inequality as an issue, my stress test does not change the verdict; it gives the concern a concrete, checkable form. No formal verification or reproducible code is present, so this proof step cannot be checked mechanically from the paper.","tokens_in":26363,"tokens_out":50945,"duration_ms":652937,"concrete_test":"Implement the single-item cycle: set ε=0.01, η=ln(3) (so d=1, v=2, μ=1), w=ceil(8η/ε), and choose initial inventory r so that P=e^{η(1−r/w)}−1=1. Feed one customer with value 1 buying one item, then one supplier selling one item at value v_s=(2e^{η/w}−1)/(1+ε), and repeat M times. Compute Algorithm 1's profit per cycle and the bracket ((1−ε/4)P + εv/η + 1/μ) − P_after/(1+ε). If bracket/profit is unbounded as ε→0, the final equality of Lemma 3.8 is false and the proof of Theorem 3.1 requires an additional argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The core of Theorem 3.1 rests on Lemma 3.8, whose last step claims\n  D ≤ O(η/ε)[Σ_cust((1−ε/4)P + εv/η + 1/μ) − Σ_supp P/(1+ε)] = O(η/ε)[Σ_cust v − Σ_supp v].\nThe second equality is load-bearing and not justified by the two inequalities cited there. Those give only\n  bracket ≤ Σ_cust((1−ε/4)v_cust + εv_cust/η + 1/μ) − Σ_supp v_supp,\nwhich is larger than Σ_cust v_cust − Σ_supp v_supp by roughly Σ_cust(v_cust + 1/μ). To absorb this excess one would need a lower bound on net profit in terms of total customer revenue; no such bound is stated or proved in the paper.\n\nThis is not a cosmetic gap. Take one item type, μ=1, v=2, ε small, and w=8η/ε (the boundary of Assumption 3.2). Set the inventory so that e^{η(1−r/w)}=2, i.e. the price is P=1. A customer buys one unit of value 1; the price becomes P_after=2e^{η/w}−1≈1+ε/4. A supplier then offers the same unit at v_s=P_after/(1+ε); the algorithm buys at zero utility and the price returns to P=1. Per cycle, ALG = 1 − v_s ≈ 3ε/4, while the bracket in Lemma 3.8 is (2 − ε/4 + ε/η) − v_s ≈ 1 + O(ε). Hence bracket/ALG ≈ 4/(3ε), so the displayed equality fails as ε→0 with the claimed O(η/ε) factor unchanged. The theorem may still be salvageable — in this example the raw dual value is only O(η/ε)·ALG — but the proof as written does not establish the central comparison, and the role of nonnegative profit / zero-value benchmarks is not addressed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies an online trading problem in which a retailer buys bundles of goods from arriving suppliers and sells bundles to arriving customers, subject to per-item inventory capacities, with the goal of maximizing profit. The authors consider both a known-valuation setting and an unknown-valuation, incentive-compatible setting. They propose exponential-weight-update dynamic pricing algorithms and analyze them via a primal-dual framework: an LP upper bounds the optimal offline fractional profit (with supplier values inflated by 1+epsilon), and the analysis constructs a feasible dual solution whose value is charged to the algorithm's profit. The claimed results are O((1/epsilon) log(dv))-competitiveness in the known case and O((1/epsilon) log(dv/epsilon))-competitiveness in the unknown case, subject to a large-inventory assumption, plus almost matching lower bounds and an inventory-size threshold below which no deterministic algorithm has finite competitive ratio.","tokens_in":26782,"tokens_out":17832,"duration_ms":184493,"significance":"If the main theorem is correct, this is a substantial contribution: it appears to be the first competitive online algorithm for two-sided bundle trading with inventory constraints, extending the classical sell-only line of work to a profit objective with both buying and selling. The dual-fitting approach is a natural and potentially influential generalization of earlier customer-only analyses, and the lower bounds (including the necessity of resource augmentation and the large-inventory threshold) are valuable. The paper is also commendable for giving explicit, checkable claims (Observation 3.5, Claim 3.9, Claim 3.10) and for constructing the dual solution explicitly. However, as detailed below, a load-bearing step in the proof of the main upper bound is not justified, so the central claim is not currently established.","major_comments":[{"comment":"The final displayed equality in Lemma 3.8 is not established. The step claims that O(eta/epsilon) * [sum over T'_cust of ((1-epsilon/4)P^t + epsilon v^t/eta + 1/mu) - sum over T'_supp of P^t/(1+epsilon)] equals O(eta/epsilon) * [sum v^t - sum v^t]. The proof justifies this only by P^t <= v^t for customers and P^t >= (1+epsilon)v^t for suppliers, but those inequalities do not control the extra positive terms epsilon v^t/eta + 1/mu - epsilon P^t/4. With the known-valuation choice mu=1, the term 1/mu = 1 per customer trade is not charged to any revenue. For example, take a single item with v=2, mu=1, small epsilon, and inventory on the boundary of Assumption 3.2. A customer buys one unit at price 1, raising the price to roughly 1+epsilon/4; a supplier then sells one unit back at P/(1+epsilon), restoring the price. The algorithm's profit per such cycle is about 3epsilon/4, while the bracket in Lemma 3.8 is about 1 + O(epsilon). Hence bracket/profit = Omega(1/epsilon), contradicting the claimed equality with the same O(eta/epsilon) factor. Because Theorem 3.3 and the known-valuation part of Theorem 3.1 rely on this equality, the main upper bound is not proven as written.","section":"Lemma 3.8 (final displayed equality)"},{"comment":"The incentive-compatible result inherits the gap in Lemma 3.8. The upper bound on OPT used in Section 3.2 is precisely Theorem 3.3, whose proof contains the unjustified final step. For the specific parameters chosen in Algorithm 2 (mu = 32/epsilon * (1+log v) and the corresponding eta), the problematic inequality 1/mu <= epsilon/4 - epsilon/eta might hold, so the final step may be repairable in that parameter regime. But the paper currently states and proves Theorem 3.3 for all mu >= 1 and eta >= 1+log(1+vdmu), and it does not verify the needed inequality for the parameters actually used in Section 3.2. Thus the unknown-valuation result is also not rigorously established as written.","section":"Section 3.2 (application of Theorem 3.3 to Algorithm 2)"}],"minor_comments":[{"comment":"In the proof of Lemma 3.14, the text reads \"max{1,P^t} <= v^t <= max{1,P^t} + 20 = 1 + max{1,P^t}\"; the \"20\" appears to be a typo and should be \"1\".","section":"Lemma 3.14 proof"},{"comment":"Observation 3.4 states that item prices are \"always positive,\" but the formula for x^t_i gives 0 when inventory is full; the statement should say \"nonnegative.\"","section":"Observation 3.4"},{"comment":"In Lemmas 4.2 and 4.3, each time step is described as having w suppliers arrive and the algorithm \"may purchase some fraction of items from the suppliers,\" which appears to allow buying more than one bundle per time step. This is a relaxation to a stronger fractional algorithm and is acceptable as a lower bound, but the text should explicitly state that this is a relaxation; otherwise it conflicts with the model's one-bundle-per-step constraint.","section":"Section 4.1 (lower bound construction)"},{"comment":"The theorem statement says the inventory must be at least (c/epsilon) log(2vd) times the bundle size for \"some large enough constant c,\" while Assumption 3.2 uses 8eta/epsilon with eta = 1+log(1+vd). The paper should state the explicit implied constant or clarify how c relates to eta, to make the quantitative threshold reproducible.","section":"Theorem 3.1 / Assumption 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper presents a promising framework and the lower-bound section is convincing, but the proof of the main upper bound has a genuine gap in the final step of Lemma 3.8. The authors should be asked to either repair that step or revise the theorem statement. If the fix requires an extra log(1/epsilon) factor in the known-valuation bound, the claimed tightness relative to the lower bound would need to be re-evaluated. The paper is otherwise within the scope of the journal and deserves a careful revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The problem is genuinely new: adversarial two-sided trading with bundles and inventory caps. Previous work is sell-only or stochastic prophet trading. The paper's deterministic exponential-weight pricing algorithm and its incentive-compatible variant are natural and plausible, and the dual-fitting framework is a nice extension of the sell-only primal-dual approach to a profit objective. The feasibility lemma and the KL-divergence claims check out. If the main theorem is correct, it's a solid within-field contribution.\n\nThe soft spots are in the upper-bound proof and the randomized lower bound. Lemma 3.8's final step does not follow from the inequalities it cites. The stress-test example—one item, small epsilon, a repeatable buy/sell cycle—shows the intermediate bracket can be roughly 1 while the algorithm's net profit per cycle is about 3epsilon/4, so the bracket is a factor of 1/epsilon larger. That invalidates the claimed equality and the proof as written only yields a competitive ratio like O(eta/epsilon^2), not the stated O(eta/epsilon). This is not a cosmetic typo; it needs a genuine repair. The theorem may still be true—in the stress-test instance the algorithm actually beats the augmented offline benchmark—but the current proof does not establish the main claim.\n\nThe randomized lower bound also has a problem. The construction is adaptive to the algorithm's inventory, which is fine for deterministic algorithms but not for randomized algorithms against an oblivious adversary. The observation that a randomized algorithm induces a fractional solution doesn't fix the adaptivity. The Omega((1/epsilon) log(dv)) lower bound should be stated for deterministic algorithms only unless a Yao-style argument is supplied.\n\nOverall, the paper deserves serious refereeing. The model is new, the algorithms are interesting, and the deterministic lower bounds look solid. But the main theorem as stated is not proven. I'd ask the authors to fix Lemma 3.8 and clarify the randomized lower bound, or scale down the claims. A careful referee could push this to a publishable state, but it needs work first.","headline":"New two-sided bundle trading model with a promising algorithm, but the proof of the main competitive-ratio theorem has a real gap in Lemma 3.8 and the randomized lower bound is not established.","tokens_in":27351,"tokens_out":17251,"would_cite":true,"duration_ms":192026,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W40","91B26"],"pacs":[],"model":"deepseek-v4-flash","headline":"An online retailer who must both buy and sell bundles of goods can guarantee profit within a logarithmic factor of a hindsight-optimal plan, as long as the comparison pays suppliers (1+ε) more and storage is large enough.","keywords":["online algorithms","competitive analysis","bundle trading","dynamic pricing","primal-dual methods","incentive compatibility","inventory constraints","lower bounds"],"falsifier":"Run Algorithm 1 on a single-item-type instance satisfying the large-inventory assumption with exponentially decreasing supplier values followed by one high-value customer; if the algorithm's profit divided by the benchmark profit ever exceeds C(1/ε) log(2dv) for the claimed constant C, the theorem's bound is false. Conversely, on the same family with inventory w below c/ε log v, the paper predicts every deterministic algorithm has unbounded competitive ratio, so any deterministic algorithm with finite competitive ratio on that family would refute the threshold.","tokens_in":26112,"feed_emoji":"📦","tokens_out":5797,"duration_ms":67496,"temperature":0.7,"pith_summary":"An online retailer who must both buy and sell bundles of goods only as suppliers and customers arrive previously had no general competitive algorithm beyond the sell-only case. This paper establishes that with modest resource augmentation, comparing against an offline plan that pays (1+ε) more to suppliers, the full buy-and-sell bundle trading problem admits logarithmic competitive ratios: O((1/ε) log(2dv)) deterministically when valuations are known, and O((1/ε) log(2dv/ε)) in expectation by a randomized incentive-compatible mechanism when valuations are private. Both guarantees require the inventory of each item type to be at least a constant times (1/ε) log(2dv), or log(2dv/ε), times the number of items of that type appearing in any bundle. The paper also proves nearly matching lower bounds showing the logarithmic ratio is tight up to constants and that both resource augmentation and the large-inventory condition are necessary.","feed_headline":"Online bundle trading now has a logarithmic guarantee","feed_subtitle":"New algorithms match any hindsight-optimal plan within a logarithmic factor, even when buyers and sellers keep valuations private.","key_machinery":"The central object is the inventory-dependent price update\n$$x_t^i = \\frac{1}{d\\mu}\\left(\\exp\\!\\left(\\frac{1-r_t^i}{w_i}\\,\\eta\\right)-1\\right),$$\nwhere $r_t^i$ is current inventory of item $i$, $w_i$ is its capacity, $d$ is the largest customer bundle size, and $\\mu, \\eta$ are parameters. As inventory of item $i$ drops, its base price per unit rises exponentially, and prices fall when suppliers restock the item. The proof machinery is dual fitting: the paper builds a feasible solution to the dual of an LP relaxation of offline profit using exactly these prices, then uses a weighted KL-divergence telescoping sum and the large-inventory assumption to show the dual value is at most $O(\\eta/\\epsilon)$ times the algorithm's profit.","core_discovery":"The paper constructs two algorithms, Algorithm 1 for known valuations and Algorithm 2 for unknown valuations, and proves they are competitive against an optimal offline fractional solution whose supplier values are inflated by (1+ε). The algorithms maintain an inventory-dependent base price per unit for each item type: the price is zero when inventory is full and grows exponentially as inventory empties, and the price of a bundle is the sum of its item prices. Customer willingness to pay is compared to this bundle price, while supplier offers are accepted at a (1+ε)-discounted price. In the unknown-valuation setting, a randomly sampled additive threshold is added to customer prices; the inventory update occurs even when the threshold prevents an actual sale, which makes the mechanism incentive compatible without being a pure posted-price mechanism. The correctness argument dual-fits the algorithm's profit to a linear program whose dual is feasible by the algorithm's own price sequence, and weak duality then bounds the optimal offline profit by O(η/ε) times the algorithm's profit.","pith_inferences":["Beyond the paper's scope, the random-additive-threshold device could be repurposed as a generic tool for converting profit-maximizing online algorithms into incentive-compatible ones with only an O(log v) penalty in parameters.","The open question the paper flags, whether randomization can beat the deterministic inventory threshold, is testable by trying to extend the randomized mechanism to small inventories; the sell-only analogue has resisted this for thirty years.","The LIFO accounting used in the lower bounds suggests a general template for proving impossibility in profit-maximizing online inventory problems: charge each unit with its acquisition cost and show sales below that cost cannot profit.","One could test the dual-fitting framework on richer constraints, such as matroid or multi-warehouse inventory constraints, by checking whether an analogous KL-divergence telescoping identity still bounds the dual value."],"forward_implications":["A retailer can operate a two-sided online bundle market and still earn within the stated logarithmic factor of a hindsight-optimal plan, provided storage is proportionally large.","The incentive-compatible version means self-interested customers and suppliers cannot profit by misreporting valuations, and the expected-profit guarantee survives strategic behavior.","The lower bounds imply the (1+ε) supplier-cost advantage is not a technical convenience: without it, no algorithm has finite competitive ratio, even for a single item type.","The inventory threshold is sharp in the deterministic case: below a constant factor of (1/ε) log(dv) times bundle size, no deterministic algorithm has bounded competitive ratio, so the theorem's assumption is essentially necessary."],"supporting_citations":[{"why":"Defines the sell-only online routing problem with initial inventory and the large-inventory assumption that this paper generalizes to two-sided trading.","marker":"[2]"},{"why":"Supplies the primal-dual dual-fitting technique for the customer-only online packing problem that the paper extends.","marker":"[11]"},{"why":"Provides the primal-dual incentive-compatible auction template that the unknown-valuation mechanism builds on.","marker":"[10]"},{"why":"Underlies the bidding-phase device that lets Algorithm 2 update prices even when the sampled threshold prevents a sale.","marker":"[1]"},{"why":"Introduces the positive-body-chasing LP dual formulation that this paper extends to integral, incentive-compatible solutions.","marker":"[7]"},{"why":"Gives the closest stochastic single-item trading model and the adversarial-order example that motivates the resource-augmentation and large-inventory assumptions.","marker":"[14]"}],"fun_headline_variants":["Bundle trading gets logarithmic online guarantee","Online bundle trading: logarithmic competitive ratio","Log-competitive algorithms for online bundle trading","Two-sided online bundle trading matches offline within log"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that each item type has enough storage: its inventory cap must be at least a constant times (1/ε) log(2dv), or (1/ε) log(2dv/ε), times the number of such items appearing in any bundle; if storage is comparable to bundle sizes, the logarithmic guarantee no longer applies and the paper shows no deterministic algorithm has finite competitive ratio.","fun_headline_variants_meta":{"raw":{"variants":["Bundle trading gets logarithmic online guarantee","Online bundle trading: logarithmic competitive ratio","Log-competitive algorithms for online bundle trading","Two-sided online bundle trading matches offline within log"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000501,"raw_usage":{"total_tokens":2432,"prompt_tokens":907,"completion_tokens":1525,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":1472}},"tokens_in":523,"tokens_out":1525,"duration_ms":13037,"temperature":1.0,"reasoning_tokens":1472,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T11:10:31.367757+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a single-item-type instance satisfying the large-inventory assumption with exponentially decreasing supplier values followed by one high-value customer; if the algorithm's profit divided by the benchmark profit ever exceeds C(1/ε) log(2dv) for the claimed constant C, the theorem's bound is false. Conversely, on the same family with inventory w below c/ε log v, the paper predicts every deterministic algorithm has unbounded competitive ratio, so any deterministic algorithm with finite competitive ratio on that family would refute the threshold.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the sell-only online routing problem with initial inventory and the large-inventory assumption that this paper generalizes to two-sided trading."},{"cited_title":"Improved bounds for online routing and packing via a primal-dual approach","cited_arxiv_id":null,"evidence_quote":"Supplies the primal-dual dual-fitting technique for the customer-only online packing problem that the paper extends."},{"cited_title":"Incentive compatible mulit-unit combinatorial auctions: A primal dual approach","cited_arxiv_id":null,"evidence_quote":"Provides the primal-dual incentive-compatible auction template that the unknown-valuation mechanism builds on."},{"cited_title":"Reducing truth-telling online mechanisms to online optimization","cited_arxiv_id":null,"evidence_quote":"Underlies the bidding-phase device that lets Algorithm 2 update prices even when the sampled threshold prevents a sale."},{"cited_title":"Chasing positive bodies","cited_arxiv_id":null,"evidence_quote":"Introduces the positive-body-chasing LP dual formulation that this paper extends to integral, incentive-compatible solutions."},{"cited_title":"Trading prophets","cited_arxiv_id":null,"evidence_quote":"Gives the closest stochastic single-item trading model and the adversarial-order example that motivates the resource-augmentation and large-inventory assumptions."}],"review_version":1}