{"id":"5fa0cb78-18c1-46e6-b862-f176445c425c","arxiv_id":"2504.04349","paper_version":3,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Derives tight regret bounds of order T to the 2/3 for independent values and T to the 3/4 for correlated values in global budget balanced fixed-price bilateral trade.","lead":"This paper establishes tight regret bounds for fixed-price bilateral trade mechanisms under regret minimization, achieving near-optimal rates for both independent and correlated value settings with limited feedback. It completes prior work by improving lower bounds and introducing new techniques for handling budget balance and one-bit feedback.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly isolates the global budget balance constraint as the central modeling restriction that both the upper- and lower-bound arguments must navigate. Because the abstract already flags this constraint and the new technical ingredients are introduced precisely to handle it, the claim structure is internally consistent on its face. Full proof verification would be needed for higher , but no load-bearing flaw is visible in the given material.","tokens_in":1796,"tokens_out":296,"duration_ms":51467,"concrete_test":"Verify that the fractal-elimination algorithm in the independent-values upper bound (and the adversarial lower-bound construction) explicitly maintains global budget balance after every round under one-bit feedback; if any intermediate price sequence violates it, recompute the regret to check whether the T^{2/3} or T^{3/4} scaling still holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and high-level description present a coherent program: tight regret bounds for fixed-price bilateral trade under global budget balance, with the T^{2/3} result for independent values via fractal elimination and the improved T^{3/4} lower bound for correlated values. The global budget balance constraint is explicitly foregrounded as restricting allowable price sequences, which is consistent with the claimed tightness. No internal inconsistency, hidden assumption, or gap in the stated conditions is detectable from the provided summary.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript examines regret minimization for fixed-price bilateral trade mechanisms subject to the global budget balance constraint. For independent buyer and seller values, it establishes a near-optimal tight bound of order T^{2/3} (up to polylog factors) under one-bit or two-bit feedback, achieved via a new 'fractal elimination' algorithmic paradigm. For correlated or adversarial values, it proves an Omega(T^{3/4}) lower bound that improves the prior Omega(T^{5/7}) result from BCCF24 and nearly matches the known O(T^{3/4}) upper bound from the same work. The paper positions these results, together with prior literature, as providing an essentially complete characterization of the problem.","tokens_in":1858,"tokens_out":469,"duration_ms":22478,"significance":"If the stated bounds and constructions hold, the work substantially advances the understanding of constrained online learning in bilateral trade, closing the gap between upper and lower bounds in both the independent and correlated regimes. The fractal elimination technique for one-bit feedback and the new lower-bound construction tailored to global budget balance are explicitly noted as potentially reusable in other settings; the combination with CCCFL24mor, CCCFL24jmlr, AFF24, and BCCF24 yields a thorough resolution of the fixed-price case.","major_comments":[],"minor_comments":[{"comment":"The abstract and introduction refer to 'fractal elimination' and the 'new lower-bound construction' as key technical contributions, but the high-level description in §1 does not include even a brief pseudocode sketch or proof outline; adding a one-paragraph intuitive description of each would improve accessibility without lengthening the paper.","section":null},{"comment":"Notation for the feedback models (one-bit vs. two-bit) is introduced in the abstract but first formally defined only later; a consolidated definition table or paragraph in §2 would prevent readers from needing to cross-reference.","section":null},{"comment":"The claim that the results 'essentially' give a thorough understanding (abstract) would benefit from an explicit comparison table in the introduction that lists the new bounds alongside those from BCCF24, CCCFL24, etc., for each feedback and value-correlation regime.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive and accurate summary of our manuscript, which correctly identifies the main contributions on tight regret bounds for global budget balanced fixed-price bilateral trade. We appreciate the recommendation for minor revision and the recognition of the potential reusability of the fractal elimination paradigm and the new lower-bound construction.","responses":[],"tokens_in":1339,"tokens_out":79,"duration_ms":11914,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that the authors pin down near-tight regret rates for fixed-price bilateral trade when the mechanism must stay globally budget-balanced at every round. For independent values they establish a matching ~Theta(T^{2/3}) bound under one-bit or two-bit feedback; for correlated or adversarial values they raise the lower bound to Omega(T^{3/4}), improving the earlier Omega(T^{5/7}) from BCCF24 and nearly matching that paper's upper bound up to logs. Together with the prior works they cite, this essentially finishes the regret analysis for this setting. The two technical pieces that stand out are the fractal elimination algorithm, which handles the one-bit feedback restriction cleanly, and the new lower-bound construction that directly incorporates the global budget-balance constraint with correlated values. Both look like genuine additions rather than minor tweaks on existing ideas. The math appears consistent with the stated assumptions, and the global budget-balance requirement is treated as a hard restriction on allowable price sequences, which is the right way to frame it. The only soft spot worth noting is that the one-bit feedback analysis for independent values relies on a fairly intricate elimination schedule; a referee would want to check whether the polylog factors hide any looseness or whether the construction generalizes beyond the specific feedback model. Otherwise the derivations track the abstract claims without obvious circularity or unstated assumptions. This is for people already working on online mechanism design and regret in bilateral trade. Anyone tracking the sequence of papers on this topic will need to absorb these bounds. The paper shows clear engagement with the literature and the technical ingredients are reproducible in principle. I would send it to peer review.","headline":"This paper tightens the regret picture for fixed-price bilateral trade under global budget balance, with a new fractal elimination method delivering the T^{2/3} rate for independent values and a stronger lower-bound construction for the correlated case.","tokens_in":2355,"tokens_out":423,"would_cite":true,"duration_ms":21362,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"fractal elimination... recursive decomposition of GFT(p,q)=H([0,p],q)+V(p,[q,1]) using Bayes and independence"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/ArithmeticFromLogic.lean","rs_theorem":null,"paper_passage":"GBB constraint... global nonnegative total profit over T rounds"}],"headline":"Regret bounds via fractal elimination in bilateral trade; no RS cost or distinction structure","alignment":"orthogonal","rationale":"Paper centers on online mechanism design with GBB constraint, one-bit feedback, and elimination algorithms for regret (T^{2/3}, T^{3/4} bounds). Central machinery (fractal elimination, ratio decompositions of GFT via Bayes/independence) uses standard MAB-style estimation and lower-bound constructions; no recognition cost J, golden-ratio forcing, 8-tick periodicity, or distinction-to-spacetime chain appears. Domain (cs.GT) lies outside RS theorems on cost uniqueness or parameter-free constants.","tokens_in":66146,"confidence":"high","tokens_out":298,"duration_ms":13065,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Fixed-price bilateral trade mechanisms achieve near-optimal regret of order T to the two-thirds for independent values and three-fourths for correlated values under global budget balance.","keywords":["bilateral trade","regret minimization","fixed-price mechanisms","global budget balance","one-bit feedback","independent values","correlated values","online algorithms"],"falsifier":"Exhibiting any global-budget-balance fixed-price mechanism that achieves o(T^{2/3}) regret for independent values under one-bit feedback would disprove the upper bound.","tokens_in":2683,"feed_emoji":"","tokens_out":693,"duration_ms":26754,"temperature":0.7,"pith_summary":"The paper establishes tight regret bounds for fixed-price mechanisms in bilateral trade that must obey global budget balance while receiving only one or two bits of feedback per round. For independent buyer and seller values the regret scales as the order of T to the power two thirds, which is shown to be the best possible up to logarithmic factors. For correlated or adversarially chosen values the authors prove a lower bound of order T to the power three fourths that improves the previous best lower bound and nearly matches the known upper bound. These results rely on a new algorithmic approach called fractal elimination and a fresh lower-bound construction. Together with earlier studies the work essentially completes the picture of regret minimization for this class of mechanisms.","feed_headline":"Fixed-price trade achieves tight T to the 2/3 regret","feed_subtitle":"Independent values allow near-optimal scaling while correlated values force at least T to the 3/4 under budget balance and limited feedback.","key_machinery":"Global budget balance constraint on fixed-price sequences together with the fractal elimination paradigm for one-bit feedback and the new lower-bound construction for correlated values.","core_discovery":"For independent values, a near-optimal ~Theta(T^{2/3}) tight bound for Global Budget Balance fixed-price mechanisms with two-bit/one-bit feedback. For correlated/adversarial values, a near-optimal Omega(T^{3/4}) lower bound for Global Budget Balance fixed-price mechanisms with two-bit/one-bit feedback, improving the prior Omega(T^{5/7}).","pith_inferences":["The global budget balance requirement appears to force strictly worse regret than unconstrained fixed-price mechanisms.","The new lower-bound construction may transfer to other online mechanism-design settings that impose balance constraints.","Practical repeated pricing systems could use these scaling laws to anticipate long-term loss under limited market feedback.","Extensions to multi-unit or multi-buyer variants would be a natural next test of the fractal elimination method."],"forward_implications":["The minimax regret for independent values is characterized up to polylog factors as Theta(T^{2/3}).","The minimax regret for correlated or adversarial values is characterized up to polylog factors as Theta(T^{3/4}).","The fractal elimination technique solves the one-bit feedback case for independent values.","Combined with prior results the regret minimization problem for fixed-price bilateral trade is now essentially settled."],"fun_headline_variants":["Tight T^{2/3} regret for independent-value fixed-price bilateral trade","Omega(T^{3/4}) lower bound for correlated fixed-price trade under budget balance","Fixed-price mechanisms regret bound T^{3/4} for adversarial values","Improved Omega(T^{3/4}) bound in bilateral trade regret minimization"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The mechanism must satisfy global budget balance at every single step while operating with only one-bit or two-bit feedback per round.","fun_headline_variants_meta":{"raw":{"variants":["Tight T^{2/3} regret for independent-value fixed-price bilateral trade","Omega(T^{3/4}) lower bound for correlated fixed-price trade under budget balance","Fixed-price mechanisms regret bound T^{3/4} for adversarial values","Improved Omega(T^{3/4}) bound in bilateral trade regret minimization"]},"model":"grok-4.3","cost_usd":0.005238,"raw_usage":{"total_tokens":2475,"prompt_tokens":706,"num_sources_used":0,"completion_tokens":81,"cost_in_usd_ticks":52378000,"prompt_tokens_details":{"text_tokens":706,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1688,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":706,"tokens_out":81,"duration_ms":13921,"temperature":1.0,"reasoning_tokens":1688,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-22T21:17:32.431150+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Exhibiting any global-budget-balance fixed-price mechanism that achieves o(T^{2/3}) regret for independent values under one-bit feedback would disprove the upper bound.","supporting_citations":[],"review_version":1}