{"id":"7396ab35-fbc7-4b04-b4f0-9a17bb8e2db5","arxiv_id":"2411.08972","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Combinatorial LMSR market making is shown equivalent to range query with range update, giving sublinear-time algorithms for bounded VC-dimension set systems and matching hardness results.","lead":"This paper connects automated market makers for combinatorial prediction markets to range query problems in computational geometry, yielding sublinear-time algorithms and new hardness results. It also extends the framework to quadratic and power scoring rules and to constant function market makers in decentralized finance.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Partition-tree sublinear guarantees assume constant-time node/range relation tests; without them, finite-VC sublinear LMSR is unestablished in the RAM model.","rationale":"The reader's weakest assumption identifies exactly the load-bearing concern: the sublinear-time guarantees for finite-VC set systems require constant-time node/range intersection and containment tests, which the paper does not provide for arbitrary set systems. The paper itself flags this in Section 3.2.1, so the concern is not hidden, but it does mean the abstract's unqualified 'sublinear time algorithms' claim overstates what is established. The LMSR-RQRU equivalence (Theorem 3.1) is a clean and valuable reduction, and for the geometric instantiations the partition-tree algorithms are standard and sound. The unbounded-VC lower bound is also plausible via the reduction to static range searching. Thus the paper merits acceptance only with the computational model made explicit and Corollary 3.8 qualified accordingly. Two further issues reinforce the conditional verdict but are not the primary attack. First, Lemma 4.7's closed form for the 3/2-power MSR is not valid for all states: for n=2, b=1, w=(10,0), the quantity M1^2 - n(M2 - 9b^2/4) is negative, so the formula is imaginary; the KKT solution is only interior when the variance of w is bounded, and boundary cases are omitted. Second, the Appendix D NP-hard cost function is not a valid convex, 1-invariant cost function: the indicator of a partition is not convex, and adding a constant to all coordinates changes the partition condition unless 2|S|=n. These are localized but should be fixed. Since the reader's conditional verdict already captures the central concern, no verdict adjustment is needed.","tokens_in":37678,"tokens_out":7284,"duration_ms":76871,"concrete_test":"Implement Corollary 3.8 on Example 2.6 (top-L securities) with K=10 and n=K!, using the Theorem 3.7 partition-tree construction and only a membership oracle. Instrument every node/range relation test in Algorithm 2, counting the actual RAM cost of deciding N(v) subset-of, disjoint-from, or crossing E. If a single price query costs more than O(n^(1-epsilon)) because the tests iterate over |N(v)| or require solving an intractable predicate, the sublinear claim fails in the standard model.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central algorithmic claim rests on Algorithms 1 and 2, whose query/update time is bounded by the partition tree's visiting number. That bound only counts nodes visited; each visit requires deciding whether the node-set N(v) is contained in, disjoint from, or crossing the query range E. The paper explicitly acknowledges in Section 3.2.1 that it 'sweeps the latter under the rug' and works in an arithmetic/decision-tree model. For the geometric examples in Corollaries 3.4-3.6, node-sets have succinct encodings (intervals, rectangles, halfspaces) and the three-way test is genuinely constant-time. But Corollary 3.8 claims sublinear LMSR for every finite-VC set system given only a membership oracle. The Chazelle-Welzl partition tree from Theorem 3.7 may produce node-sets with no succinct representation; deciding whether an arbitrary such node-set lies inside a query range can require scanning the node-set or solving a hard predicate. A membership oracle for point/range incidence does not supply constant-time node/range classification. Without an additional assumption, the stated O(n^(1-epsilon)) running time is not realized on a standard RAM, so the bounded-VC characterization is only conditional on unstated oracle and encoding assumptions. This is the single most load-bearing gap: if it fails, the equivalence to RQRU still holds but does not yield sublinear LMSR for general finite-VC set systems.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a unified geometric framework for combinatorial prediction-market AMMs. Its central result is an equivalence (Theorem 3.1) between LMSR price/cost/buy operations and the (+, ·)-range-query/range-update problem, followed by a lazy-propagation partition-tree algorithm whose running time is governed by the partition tree's visiting number (Theorem 3.3). The framework is applied to interval, orthogonal, and hyperplane securities; to finite-VC and infinite-VC set systems; to QMSR and 3/2-power MSR; to multi-resolution markets; and to CFMM swap operations in decentralized finance. The paper's main advertised achievement is an exact reduction of combinatorial LMSR market making to range searching, yielding sublinear-time algorithms for bounded-VC set systems and hardness results for unbounded VC dimension.","tokens_in":38006,"tokens_out":25011,"duration_ms":209983,"significance":"If the central equivalence holds, it is a valuable conceptual bridge between market design and computational geometry: it transfers a large body of range-searching results to combinatorial prediction markets and gives explicit sublinear algorithms for natural security families. The proof of the LMSR-RQRU equivalence is algebraic, self-contained, and appears correct; the lazy-propagation argument is careful and is a genuine contribution. The paper should also be credited for being explicit about the node-visiting model in footnote 3, even though, as discussed below, this caveat undermines one of the paper's headline claims. The significance is tempered by the model-dependence of the general finite-VC sublinear result and by several localized errors in the power-MSR, matrix-multiplication-hardness, and NP-hard cost-function arguments.","major_comments":[{"comment":"The O(n^{1-epsilon_D}) claim for arbitrary finite-VC set systems with only a membership oracle is not established in the RAM model. Algorithm 2's query time is bounded by the number of partition-tree nodes visited, but each visit requires deciding whether the node-set N(v) is contained in, disjoint from, or crossing the range E; the paper explicitly states that it 'sweeps the latter under the rug' in the footnote on pp. 10-11. A membership oracle that answers point/range incidence does not supply constant-time node/range classification, and for the abstract partition trees of Theorem 3.7 the node-sets may have no succinct representation. Thus the stated running time is a visiting-number bound in an arithmetic/decision-tree model, not a wall-clock RAM bound. The geometric Corollaries 3.4-3.6 are unaffected because their node-sets are intervals, rectangles, or halfspaces with constant-time tests. Corollary 3.8 should be restated in the appropriate model or augmented with an explicit oracle/encoding assumption that permits constant-time three-way tests. Additionally, Theorem 3.7's construction uses O(|F| n^{2/d} + n^{2+2/d}) membership calls, so the 'O(poly(n)) calls' in Corollary 3.8 requires an argument controlling |F|, which the paper does not supply.","section":"Sec. 3.2.1 / Cor. 3.8"},{"comment":"The closed forms in Lemma 4.7 are internally inconsistent. The stated cost uses the term M1^3 - 3 M1^2 mu + 2 mu^3, but the KKT derivation in the proof gives M1^3 - 3 M1 mu^2 + 2 mu^3. With the printed expression, the n=1, b=1 case gives C(t) = (2/3)t^2 - 1 instead of t - 1, so the printed cost violates 1-invariance and cannot be the 3/2-power MSR. The displayed price formula also drops the b^{-2} factor that appears in the proof, and with n=1, b=1 its derivative is not the derivative of the printed cost expression. Since Lemma 4.9 and Theorem 4.10 depend on Lemma 4.7, the Section 4.2 results must be corrected before they can be relied upon.","section":"Lemma 4.7"},{"comment":"The proof of Proposition 3.10 is not correct as written. For a fixed j, the loop 'update((:, j), B_i,j) for all i' scales the entire column j by the product of all B_i,j, so a subsequent row query returns sum_j A_{i,j} * prod_k B_{k,j}, not (AB)_{i,j}. The intended reduction can likely be repaired by updating each column k by B_{k,j} and then querying rows, but the printed loop and the stated O(m^2(T_P + T_B)) accounting need to be fixed. Since Proposition 3.10 is the main lower-bound evidence for the difficulty of 2D LMSR, this proof needs a substantive correction.","section":"Appendix A.2, Prop. 3.10"},{"comment":"The NP-hard cost function C_partition is not shown to be convex. The argument that the indicator term is bounded by 1 does not imply convexity: the set {w : exists S, 2 sum_{i in S} w_i = sum_j w_j} is a finite union of hyperplanes, and the indicator of such a nonconvex set is not convex even when added to a large quadratic term. For example, in one dimension the function 1_{x != 0} + M x^2 is not convex for any finite M. Thus the claim that there is a convex, differentiable, 1-invariant cost function whose computation is NP-hard is not established by this construction. The authors should either provide a valid construction or qualify/remove the claim.","section":"Appendix D"}],"minor_comments":[{"comment":"The theorem states a price operation time of 2T_Q(n)+1, but the proof uses one range query and one division; the constants should be reconciled. The proof's notation for the update multiplier (e^s versus e^{s/b} versus e^{bs}) is inconsistent where the liquidity parameter b appears and should be cleaned up.","section":"Theorem 3.1"},{"comment":"Definition 4.12 says 'C : X -> R' where the domain should be R^X. In Definition 4.19, 'N(v) in E' should presumably be 'N(v) subset of E', and Z(E) is used before being defined.","section":"Sec. 4.3"},{"comment":"The interval lower bound Omega(log n) in Corollary 3.9 is proved in the group arithmetic model of Patrascu-Demaine; the unconditional Theta(log n) entry in Table 1 should carry that model caveat.","section":"Table 1 / Cor. 3.9"},{"comment":"The sentence 'there does not exists a partition tree' contains a typo; also, the lower bound o(n^{1-1/d}) is stated without log factors, so it should be harmonized with the upper bound's poly-logarithmic terms.","section":"Theorem 3.7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a good fit for a theory/EC journal. The core LMSR-RQRU equivalence and the lazy partition-tree scheme are solid contributions, and the errors in Section 4.2, Appendix A.2, and Appendix D appear local and fixable. The main risk is the overclaim in Corollary 3.8 and the abstract: the general finite-VC sublinear result needs an explicit model statement or an additional oracle/encoding assumption. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core result here is real: Theorem 3.1's equivalence between LMSR market making and (+,·)-RQRU is proven cleanly and self-containedly, and it deserves to be the paper's centerpiece. The lazy propagation partition-tree scheme is a nice unification of interval, orthogonal, and hyperplane cases, and the reductions for QMSR and for logarithmic/linear CFMM swaps are sensible and correctly argued. The lower bounds for intervals and the unbounded-VC cases are also on solid ground (modulo the fix below). If the paper were only about the equivalence plus the geometric applications, I'd recommend accepting after minor revision.\n\nBut there are several soft spots that need real work. First, Lemma 4.7's closed forms for the 3/2-power MSR are simply wrong: the cost formula is not 1-invariant, and the price formula's derivative does not sum to 1 over x. This is not a stylistic complaint; it breaks the reduction in Lemma 4.9 and Theorem 4.10 unless corrected. The authors should either rederive the conjugate carefully or drop the 3/2-MS section.\n\nSecond, Proposition 3.10's matrix-multiplication reduction has an indexing error. The text says to update column j by B_{i,j}, but the correct reduction multiplies column i by B_{i,j} (and later column i by 1/B_{i,j}). This is easily fixable, but as written the reduction computes something else entirely.\n\nThird, Appendix D's NP-hard cost function is not convex as claimed: an indicator of a non-convex partition condition plus a convex quadratic is not necessarily convex, and the paper gives no construction of a convex differentiable extension. That claim should be removed or replaced with a real proof.\n\nFinally, the stress-test concern is on the nose. Corollary 3.8 claims sublinear LMSR for every finite-VC set system given only a membership oracle, but the running time bound counts only visited nodes, not the cost of the contain/disjoint/cross tests. The paper explicitly sweeps this under the rug in Section 3.2.1. For geometric examples with succinct node-sets those tests are constant-time, but for arbitrary finite-VC systems with only a membership oracle, the node-sets from Chazelle–Welzl may lack succinct encodings, and the classification tests could be expensive or undecidable. The theorem should be stated conditionally on constant-time node/range classification, or the claim restricted to set systems with succinctly representable node-sets. As it stands, the advertised sublinear result for arbitrary finite VC is not established in the standard RAM model.\n\nWho is this for? Computational geometry folks will appreciate the range-query lens; market design people will care about the equivalence. It deserves a serious referee, but the revision should address the points above, especially the 3/2-MS formulas and the oracle assumption. I'd send it to peer review with a clear request for major revision; the central equivalence is worth keeping.","headline":"The LMSR–RQRU equivalence is a genuine, carefully proven contribution, but the paper ships with broken 3/2-MS closed forms, a fixable indexing error in the matrix-multiplication reduction, a non-convex NP-hardness construction, and an oversold finite-VC sublinear claim.","tokens_in":38478,"tokens_out":3177,"would_cite":true,"duration_ms":33532,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B26","68P05","68U05","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Combinatorial prediction-market making is the same computational problem as range searching, and the paper proves the equivalence both ways.","keywords":["automated market makers","combinatorial prediction markets","LMSR","range query range update","VC dimension","partition trees","constant function market makers","scoring rules"],"falsifier":"Implement the partition-tree scheme on a finite-VC set system whose ranges are given as membership in an arbitrary polynomial-time language, and measure actual per-operation time. If each visited node requires a superconstant containment decision, the observed growth will exceed $O(n^{1-\\epsilon})$ despite finite VC dimension, showing the stated running times are decision-tree bounds rather than standard RAM bounds.","tokens_in":37503,"feed_emoji":"📈","tokens_out":5891,"duration_ms":56110,"temperature":0.7,"pith_summary":"The paper tries to show that designing fast automated market makers for combinatorial prediction markets is, at its core, a computational geometry problem. It proves an exact equivalence between the logarithmic market scoring rule (LMSR) and the range-query/range-update problem, so any speedup or lower bound in one transfers to the other. If this is right, the scattered collection of special-case market designs collapses into one theory, and a market is computationally tractable exactly when the family of securities has bounded VC dimension. The same reduction also gives a bridge from prediction-market making to constant-function market makers in decentralized finance.","feed_headline":"Betting markets are range-query problems in disguise","feed_subtitle":"New equivalence gives fast price and trade algorithms for low-complexity securities, and proves fundamental limits otherwise.","key_machinery":"The load-bearing object is the partition-tree scheme from range searching, augmented with lazy propagation. A partition tree recursively partitions the outcome set into canonical node-sets, and a query either adds a stored weight when a node-set is contained in the range, stops when it is disjoint, or recurses when the range crosses it. The paper's lazy update algorithm stops early whenever an update range contains a node-set, storing the pending multiplier at the node instead of pushing it to all descendants, which makes update time proportional to the same visiting number as a query. The visiting number is controlled by the dual shattering dimension, hence by VC dimension: bounded VC gives sublinear visiting numbers, unbounded VC forces linear ones. The equivalence theorem is what converts these geometric bounds into market-operation bounds, and the framework is generalized so that quadratic and power scoring rules fit as group-action range updates.","core_discovery":"The paper's central claim is that an LMSR market on any set system $(X,\\mathcal{F})$ is equivalent to the $(+, \\cdot)$ range-query-range-update problem: with only constant overhead, price operations become range queries, buy operations become range updates, and cost operations become two updates and two queries. The weight stored at each outcome is $e^{w_x/b}$, so a buy on an event rescales exactly the outcomes in that event, and the normalized query sum is the price. Because the reduction is bidirectional, known data structures and hardness results from range searching apply verbatim to market making: intervals get $O(\\log n)$ operations, $d$-dimensional orthogonal and hyperplane securities get $O(n^{1-1/d})$, and every finite-VC set system gets $O(n^{1-\\epsilon})$ for some $\\epsilon>0$; unbounded VC dimension forbids sublinear time with linear space. The same partition-tree machinery extends to quadratic scoring rules and $3/2$-power scoring rules, where the update operation becomes addition or a group action instead of multiplication, and to the combinatorial swap problem of constant-function market makers.","pith_inferences":["Going beyond the paper, the bidirectional reduction suggests that any future data structure for range queries with range updates automatically becomes a new market maker, and any market-design constraint can be imported into geometry.","The paper's Remark 4.11 conjecture can be tested directly: if the cost function for a general $\\gamma$-power scoring rule is polynomial of degree $\\gamma/(\\gamma-1)$ in the maintained power sums, the same partition tree should support all power scoring rules.","The constant-time membership-test assumption is the place where the stated RAM complexity could fail in practice; a concrete stress test would be to run the partition tree on a finite-VC set system whose ranges are given implicitly by hard membership predicates and measure actual wall-clock scaling.","In decentralized finance, the reduction to range updates implies that the same lazy partition-tree code should support combinatorial basket swaps for logarithmic and linear trading functions with guarantees matching the visiting number, which is a directly implementable extension."],"forward_implications":["Interval-securities LMSR markets can be run in $O(\\log n)$ time per price, buy, and cost operation with linear space, matching the prior log-time result and its $\\Omega(\\log n)$ lower bound.","For $d$-dimensional orthogonal and hyperplane securities, LMSR operations take $O(n^{1-1/d})$ time; a substantially faster two-dimensional algorithm would imply near-quadratic matrix multiplication, so sub-polynomial speed is unlikely.","Every set system with bounded VC dimension admits an LMSR market with sublinear per-operation time $O(n^{1-\\epsilon})$, while unbounded VC dimension rules out sublinear time with linear space, covering pairing securities and $1$-junta securities.","Quadratic and $3/2$-power scoring-rule markets inherit the same partition-tree scheme with different update types, and regular orthogonal QMSR markets can even run in polylogarithmic time, unlike LMSR.","Multi-resolution markets with LMSR or QMSR submarkets fit into the partition tree with local, closed-form arbitrage removal, preserving the same per-operation complexity."],"supporting_citations":[{"why":"Supplies the partition-tree visiting-number bounds, the finite-VC construction base, and the lower bound for unbounded complexity that the paper relies on.","marker":"[13]"},{"why":"Gives the prior log-time interval-securities market that the paper recovers and extends through the RQRU equivalence.","marker":"[26]"},{"why":"Provides the quadratic scoring rule cost function and the bounded-loss utility framework used for the QMSR reduction.","marker":"[15]"},{"why":"Frames the cost-function-based AMM model with convex, 1-invariant cost functions that all market designs in the paper use.","marker":"[1]"},{"why":"Gives the partial-sums lower bound that proves the $\\Omega(\\log n)$ optimality for interval LMSR.","marker":"[43]"},{"why":"Provides the optimal partition trees used for hyperplane securities with $O(n^{1-1/d})$ visiting number.","marker":"[12]"},{"why":"Supplies the randomized low-crossing-spanning-tree construction behind the finite-VC partition-tree algorithm.","marker":"[21]"},{"why":"Gives the multidimensional segment tree with polylogarithmic addition range updates used for the QMSR efficiency result.","marker":"[35]"},{"why":"Provides the current matrix-multiplication exponent used to argue that near-quadratic matrix multiplication would follow from a faster 2D LMSR.","marker":"[53]"}],"fun_headline_variants":["Range queries crack combinatorial betting markets","Market making meets computational geometry","Fast AMMs from range-query equivalence","VC dimension decides market speed","Combinatorial securities: a geometric shortcut"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sublinear-time guarantees assume that deciding whether a partition-tree node-set is contained in, disjoint from, or crossing a query range costs constant time; for arbitrary set systems these membership and intersection tests can themselves be expensive or undecidable, and the paper counts visited nodes rather than actual computation steps.","fun_headline_variants_meta":{"raw":{"variants":["Range queries crack combinatorial betting markets","Market making meets computational geometry","Fast AMMs from range-query equivalence","VC dimension decides market speed","Combinatorial securities: a geometric shortcut"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000321,"raw_usage":{"total_tokens":1821,"prompt_tokens":974,"completion_tokens":847,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":590,"completion_tokens_details":{"reasoning_tokens":788}},"tokens_in":590,"tokens_out":847,"duration_ms":8293,"temperature":1.0,"reasoning_tokens":788,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T21:14:49.047143+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the partition-tree scheme on a finite-VC set system whose ranges are given as membership in an arbitrary polynomial-time language, and measure actual per-operation time. If each visited node requires a superconstant containment decision, the observed growth will exceed $O(n^{1-\\epsilon})$ despite finite VC dimension, showing the stated running times are decision-tree bounds rather than standard RAM bounds.","supporting_citations":[{"cited_title":"A combinatorial prediction market for the us elections","cited_arxiv_id":null,"evidence_quote":"Gives the prior log-time interval-securities market that the paper recovers and extends through the RQRU equivalence."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the quadratic scoring rule cost function and the bounded-loss utility framework used for the QMSR reduction."},{"cited_title":"An optimization-based framework for automated market-making","cited_arxiv_id":null,"evidence_quote":"Frames the cost-function-based AMM model with convex, 1-invariant cost functions that all market designs in the paper use."},{"cited_title":"Tight bounds for the partial-sums problem","cited_arxiv_id":null,"evidence_quote":"Gives the partial-sums lower bound that proves the $\\Omega(\\log n)$ optimality for interval LMSR."},{"cited_title":"Optimal partition trees","cited_arxiv_id":null,"evidence_quote":"Provides the optimal partition trees used for hyperplane securities with $O(n^{1-1/d})$ visiting number."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the randomized low-crossing-spanning-tree construction behind the finite-VC partition-tree algorithm."},{"cited_title":"Epsilon-nets and simplex range queries","cited_arxiv_id":null,"evidence_quote":"Gives the multidimensional segment tree with polylogarithmic addition range updates used for the QMSR efficiency result."},{"cited_title":"New bounds for matrix multiplication: from alpha to omega, 2023","cited_arxiv_id":null,"evidence_quote":"Provides the current matrix-multiplication exponent used to argue that near-quadratic matrix multiplication would follow from a faster 2D LMSR."}],"review_version":1}