Pith. sign in

REVIEW 4 major objections 4 minor 60 references

Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint

T0 review · 4 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Combinatorial prediction-market making is the same computational problem as range searching, and the paper proves the equivalence both ways.

desk verdict 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. read the letter →

arxiv 2411.08972 v1 pith:H55B2SNH submitted 2024-11-13 cs.GT cs.CGcs.DS

Prommy Sultana Hossain , Xintong Wang , Fang-Yi Yu This is my paper · ORCID
classification cs.GTcs.CGcs.DS MSC 91B2668P0568U0568Q17
keywords automatedmarketmakerscombinatorialpredictionmarketsLMSRrangequeryupdateVCdimensionpartitiontreesconstantfunctionscoringrules
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

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.

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 (4)
  1. [Sec. 3.2.1 / Cor. 3.8] 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.
  2. [Lemma 4.7] 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.
  3. [Appendix A.2, Prop. 3.10] 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.
  4. [Appendix D] 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.
minor comments (4)
  1. [Theorem 3.1] 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.
  2. [Sec. 4.3] 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.
  3. [Table 1 / Cor. 3.9] 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.
  4. [Theorem 3.7] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the LMSR/RQRU equivalence is a direct algebraic reduction and all nontrivial algorithmic and hardness inputs are external computational-geometry results.

full rationale

The paper's central reduction (Theorem 3.1) is derived explicitly: LMSR price is the normalized exponential range sum and buy updates multiply the stored weights, so the equivalence is by direct algebraic invariant, not by fitting or by defining the target result. The partition-tree algorithms (Theorem 3.3, Corollaries 3.4-3.8) inherit their query/update bounds from external results of Chazelle-Welzl, Chan, and Csikós-Mustafa; the finite-VC lower bound is likewise external (Chazelle-Welzl), and the interval lower bound uses Patrascu-Demaine. The QMSR, 3/2-power MSR, and CFMM reductions are algebraic and self-contained. The only self-citations (Dudík et al. 2021, Wang et al. 2021/2024) are contextual or provide prior interval/multi-resolution designs; none is load-bearing for the new claims. The acknowledged constant-time node/range classification assumption in Section 3.2.1 (footnote 3) is an explicit modeling limitation that affects RAM realizability of Corollary 3.8 for arbitrary finite-VC systems, but it is not circularity: it is an unstated oracle/decision-tree assumption, not an equivalence of outputs to inputs. No fitted parameter is renamed as a prediction, and no uniqueness claim is imported from the authors' own prior work. Overall score 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no fitted parameters and no new physical entities. It imports standard geometric data-structure theorems and market-design axioms as black boxes. The central LMSR-RQRU equivalence is derived cleanly. However, two ad hoc constructions are flawed: the 3/2-power MSR closed form and the Appendix D NP-hard cost function, both of which are introduced specifically to support the paper's claims of generality.

assumptions (7)
  • standard math Partition tree bounds for range searching (Chazelle-Welzl, Chan, k-d trees)
    The sublinear visiting-number bounds for intervals, orthogonal sets, and hyperplanes are imported from computational geometry literature and used as black boxes in Corollaries 3.4-3.8.
  • standard math VC dimension / dual shattering dimension equivalence (Assouad)
    Used to translate between finite VC dimension and finite dual shatter dimension in the characterization of sublinear algorithms.
  • standard math Matrix multiplication exponent lower-bound conjecture (current best O(m^{2.371552}))
    Proposition 3.10 is a conditional hardness result: if 2D LMSR had subpolynomial time, matrix multiplication would be near-quadratic, which is not currently ruled out but contradicts the best known algorithm. This is an assumption about an open problem.
  • standard math Cost functions are convex, differentiable, and 1-invariant (Abernethy et al.)
    The entire framework for prediction market AMMs inherits the cost-function axiomatization from prior work; the paper does not re-derive it.
  • domain assumption Membership and intersection tests for ranges can be decided in constant time
    The partition tree query/update time counts only visited nodes, not the cost of deciding whether N(v) ⊆ E or N(v) ∩ E = ∅, as noted in the Section 3.2.1 footnote.
  • ad hoc to paper The 3/2-power MSR closed form in Lemma 4.7
    The stated formula contains a typo (M1^2 μ should be M1 μ^2), and the price formula does not sum to 1, violating 1-invariance. The subsequent RQRU reduction in Lemma 4.9 depends on this formula, so the power-MSR section rests on an incorrect derivation as written.
  • ad hoc to paper The NP-hard cost function in Appendix D
    The construction C_partition uses an indicator that is discontinuous on a union of hyperplanes, so the function is not convex and cannot be a valid cost function; the claim that it is convex, differentiable, and 1-invariant is false.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint." pith.science (2026). https://pith.science/paper/H55B2SNH

@misc{pith2026241108972,
  author       = {Pith},
  title        = {Pith review of: Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H55B2SNH}},
  note         = {Machine review of arXiv:2411.08972}
}
read the original abstract

Designing automated market makers (AMMs) for prediction markets on combinatorial securities over large outcome spaces poses significant computational challenges. Prior research has primarily focused on combinatorial prediction markets within specific set systems (e.g., intervals, permutations). We introduce a framework for designing AMMs on arbitrary set systems by building a novel connection to the range query problem in computational geometry. This connection enables the analysis of computational complexity and the design of efficient AMMs. We first demonstrate the equivalence between price queries and trade updates under the popular combinatorial logarithmic market scoring rule market and the range query and range update problem. Building on this equivalence, we construct sublinear time algorithms when the VC dimension of the set system is bounded and show the non-existence of such algorithms for unbounded VC dimension cases. We then extend this approach to AMMs for combinatorial prediction markets with quadratic and power scoring rules. Finally, we show that the multi-resolution market design can be naturally integrated into the partition-tree scheme. Additionally, we introduce the combinatorial swap operation problem for automated market makers in decentralized finance and show that it can be efficiently reduced to range update problems.

Figures

Figures reproduced from arXiv: 2411.08972 by the authors.

Figure 1
Figure 1. A partition tree for Example 2.3 with n = 16. In the figure, we consider a range query with E5,13 = {5, 6, . . . , 13}, the squared nodes are visited by the query and blue ones has node set crossed by E(5,13). More generally, given n points X = {0, . . . , n − 1}, let K = ⌈log2 (n)⌉, the height of partition tree is K with node V = {vk,l : k = 0, . . . , ⌈log2 (n)⌉, l = 0, . . . , 2 k − 1} where vk,l is the l-th node… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 53 canonical work pages

  1. [1]

    An optimization-based framework for automated market-making

    Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan. An optimization-based framework for automated market-making. In Proceedings of the 12th ACM Conference on Electronic Commerce, 2011

    work page 2011

  2. [2]

    Uniswap v2 core

    Hayden Adams, Noah Zinsmeister, and Dan Robinson. Uniswap v2 core. Tech. rep., Uniswap, Tech. Rep., 2020

    work page 2020

  3. [3]

    Uniswap v3 core

    Hayden Adams, Noah Zinsmeister, Moody Salem, River Keefer, and Dan Robinson. Uniswap v3 core. Tech. rep., Uniswap, Tech. Rep., 2021

    2021

  4. [4]

    Range searching

    Pankaj K Agarwal. Range searching. In Handbook of discrete and computational geometry , pages 1057–1092. Chapman and Hall/CRC, 2017

    work page 2017

  5. [5]

    An analysis of uniswap markets

    Guillermo Angeris, Hsien-Tang Kao, Rei Chiang, Charlie Noyes, and Tarun Chitra. An analysis of uniswap markets. 2021

    work page 2021

  6. [6]

    Constant function market makers: Multi-asset trades via convex optimization

    Guillermo Angeris, Akshay Agrawal, Alex Evans, Tarun Chitra, and Stephen Boyd. Constant function market makers: Multi-asset trades via convex optimization. In Handbook on Blockchain, pages 415–444. Springer, 2022

    work page 2022

  7. [7]

    The geometry of constant function market makers

    Guillermo Angeris, Tarun Chitra, Theo Diamandis, Alex Evans, and Kshitij Kulkarni. The geometry of constant function market makers. arXiv preprint arXiv:2308.08066 , 2023

    arXiv 2023

  8. [8]

    Densit´ e et dimension

    Patrick Assouad. Densit´ e et dimension. In Annales de l’Institut Fourier , volume 33, pages 233–282, 1983

    work page 1983

Show all 60 references
  1. [9]

    Results from a dozen years of election futures markets research

    Joyce Berg, Robert Forsythe, Forrest Nelson, and Thomas Rietz. Results from a dozen years of election futures markets research. Handbook of experimental economics results , 1:742–751, 2008. 21

    2008

  2. [10]

    Convex optimization algorithms

    Dimitri Bertsekas. Convex optimization algorithms . Athena Scientific, 2015

    2015

  3. [11]

    In- structor rating markets

    Mithun Chakraborty, Sanmay Das, Allen Lavoie, Malik Magdon-Ismail, and Yonatan Naamad. In- structor rating markets. In Proceedings of the 27th AAAI Conference on Artificial Intelligence , pages 159–165, 2013

    2013

  4. [12]

    Optimal partition trees

    Timothy M Chan. Optimal partition trees. In Proceedings of the twenty-sixth annual symposium on Computational geometry, pages 1–10, 2010

    2010

  5. [13]

    Quasi-optimal range searching in spaces of finite vc-dimension

    Bernard Chazelle and Emo Welzl. Quasi-optimal range searching in spaces of finite vc-dimension. Discrete & Computational Geometry , 4, 1989. doi: 10.1007/BF02187743. URL https://doi.org/10. 1007/BF02187743

    1989 doi

  6. [14]

    Approximate range searching in higher dimension

    Bernard Chazelle, Ding Liu, and Avner Magen. Approximate range searching in higher dimension. Comput. Geom. Theory Appl. , 39(1):24–29, jan 2008. ISSN 0925-7721. doi: 10.1016/j.comgeo.2007.05

    2008 doi

  7. [15]

    URL https://doi.org/10.1016/j.comgeo.2007.05.008

    2007 doi

  8. [17]

    A utility framework for bounded-loss market makers

    Yiling Chen and David M Pennock. A utility framework for bounded-loss market makers. arXiv preprint arXiv:1206.5252, 2012

    2012 arXiv

  9. [18]

    Yiling Chen, Lance Fortnow, Evdokia Nikolova, and David M. Pennock. Combinatorial betting. SIGe- com Exch. , 7(1):61–64, dec 2007. doi: 10.1145/1345037.1345053. URL https://doi.org/10.1145/ 1345037.1345053

    2007

  10. [19]

    Betting on permutations

    Yiling Chen, Lance Fortnow, Evdokia Nikolova, and David M Pennock. Betting on permutations. In Proceedings of the 8th ACM Conference on Electronic Commerce , pages 326–335, 2007

    2007

  11. [20]

    Lambert, David M

    Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, and Jennifer Wortman. Complex- ity of combinatorial market makers. CoRR, abs/0802.1362, 2008. URL http://arxiv.org/abs/0802. 1362

    2008 arXiv

  12. [21]

    Yiling Chen, Sharad Goel, and David M. Pennock. Pricing combinatorial markets for tournaments. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008 , pages 305–314. ACM, 2008. doi: 10...

    2008

  13. [22]

    M´ onika Csik´ os and Nabil H. Mustafa. Escaping the curse of spatial partitioning: Matchings with low crossing numbers and their applications. In Kevin Buchin and ´Eric Colin de Verdi` ere, editors, 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11,...

    2021 doi

  14. [23]

    The geometry of proper scoring rules

    A Philip Dawid. The geometry of proper scoring rules. Annals of the Institute of Statistical Mathematics, 59:77–93, 2007

    2007

  15. [24]

    Computational geometry: algorithms and applications

    Mark de Berg. Computational geometry: algorithms and applications. Springer, 1997. ISBN 354061270X. URL https://www.worldcat.org/oclc/36800677

    1997

  16. [25]

    Miroslav Dud ´ ık, S´ ebastien Lahaie, and David M. Pennock. A tractable combinatorial market maker using constraint generation. In Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

    2012

  17. [26]

    A combinatorial prediction market for the us elections

    Miroslav Dud ´ ık, S´ ebastien Lahaie, David M Pennock, and David Rothschild. A combinatorial prediction market for the us elections. In Proceedings of the fourteenth acm conference on electronic commerce , pages 341–358, 2013. 22

    2013

  18. [27]

    Pennock, and David M

    Miroslav Dud ´ ık, Xintong Wang, David M. Pennock, and David M. Rothschild. Log-time prediction markets for interval securities. CoRR, abs/2102.07308, 2021. URL https://arxiv.org/abs/2102. 07308

    2021 arXiv

  19. [28]

    Stableswap-efficient mechanism for stablecoin liquidity

    Michael Egorov. Stableswap-efficient mechanism for stablecoin liquidity. Retrieved Feb, 24:2021, 2019

    2021

  20. [29]

    Frongillo, Maneesha Papireddygari, and Bo Waggoner

    Rafael M. Frongillo, Maneesha Papireddygari, and Bo Waggoner. An axiomatic characterization of cfmms and equivalence to prediction markets. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, ...

    2024 doi

  21. [30]

    Mingyu Guo and David M. Pennock. Combinatorial prediction markets for event hierarchies. In Pro- ceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1, AAMAS ’09, page 201–208, Richland, SC, 2009. International Foundation for Auton...

    2009

  22. [31]

    Robin D. Hanson. Decision markets. IEEE Intelligent Systems , 14(3):16–19, 1999

    1999

  23. [32]

    Robin D. Hanson. Combinatorial information market design. Information Systems Frontiers , 5(1): 107–119, 2003

    2003

  24. [33]

    Robin D. Hanson. Logarithmic market scoring rules for modular combinatorial information aggregation. Journal of Prediction Markets , 1(1):1–15, 2007

    2007

  25. [34]

    Geometric approximation algorithms

    Sariel Har-Peled. Geometric approximation algorithms . Number 173. American Mathematical Soc., 2011

    2011

  26. [35]

    Epsilon-nets and simplex range queries

    David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. In Proceedings of the second annual symposium on Computational geometry , pages 61–71, 1986

    1986

  27. [36]

    Kaykobad, and M

    Nabil Ibtehaz, M. Kaykobad, and M. Sohel Rahman. Multidimensional segment trees can do range updates in poly-logarithmic time. Theoretical Computer Science, 854:30–43, January 2021. ISSN 0304-

    2021

  28. [37]

    Arbitrage-free com- binatorial market making via integer programming

    Christian Kroer, Miroslav Dud ´ ık, S´ ebastien Lahaie, and Sivaraman Balakrishnan. Arbitrage-free com- binatorial market making via integer programming. In Proceedings of the 2016 ACM Conference on Economics and Computation , pages 161–178, 2016

    2016

  29. [38]

    Scoring rules, generalized entropy, and utility maximization

    Victor Richmond R Jose, Robert F Nau, and Robert L Winkler. Scoring rules, generalized entropy, and utility maximization. Operations research, 56(5):1146–1157, 2008

    2008

  30. [39]

    Algorithms and hardness for multidimensional range updates and queries

    Joshua Lau and Angus Ritossa. Algorithms and hardness for multidimensional range updates and queries. CoRR, abs/2101.02003, 2021. URL https://arxiv.org/abs/2101.02003

    2021 arXiv

  31. [40]

    Graphical model market maker for combinatorial prediction markets

    Kathryn Blackmond Laskey, Wei Sun, Robin Hanson, Charles Twardy, Shou Matsumoto, and Brandon Goldfedder. Graphical model market maker for combinatorial prediction markets. J. Artif. Intell. Res. , 63:421–460, 2018. doi: 10.1613/JAIR.1.11249. URL https://doi.org/10.1613/jair.1.11249

    2018 doi

  32. [41]

    A new algorithm for updating and querying sub-arrays of multidimensional arrays

    Pushkar Mishra. A new algorithm for updating and querying sub-arrays of multidimensional arrays. arXiv preprint arXiv:1311.6093 , 2013

    2013 arXiv

  33. [42]

    Balancer: A non-custodial portfolio manager, liquidity provider, and price sensor, 2019

    Fernando Martinelli and Nikolai Mushegian. Balancer: A non-custodial portfolio manager, liquidity provider, and price sensor, 2019

    2019

  34. [43]

    Tight bounds for the partial-sums problem

    Mihai Patrascu and Erik D Demaine. Tight bounds for the partial-sums problem. In SODA, volume 4, pages 20–29, 2004

    2004

  35. [44]

    Automated market-making in the large: The gates hillman prediction market

    Abraham Othman and Tuomas Sandholm. Automated market-making in the large: The gates hillman prediction market. In Proceedings of the 11th ACM Conference on Electronic Commerce, pages 367–376, 2010. 23

    2010

  36. [45]

    Plott and Kay-Yut Chen

    Charles R. Plott and Kay-Yut Chen. Information aggregation mechanisms: Concept, design and imple- mentation for a sales forecasting problem. Working paper No. 1131, California Institute of Technology, 2002

    2002

  37. [46]

    The real power of artificial markets

    David M Pennock, Steve Lawrence, C Lee Giles, Finn Arup Nielsen, et al. The real power of artificial markets. Science, 291(5506):987–988, 2001

    2001

  38. [47]

    Internet-based virtual stock markets for business forecasting

    Martin Spann and Bernd Skiera. Internet-based virtual stock markets for business forecasting. Manag. Sci., 49(10):1310–1326, 2003. doi: 10.1287/MNSC.49.10.1310.17314. URL https://doi.org/10.1287/ mnsc.49.10.1310.17314

    2003

  39. [48]

    Division of space by balls in rn

    pyrrhic (https://math.stackexchange.com/users/119748/pyrrhic). Division of space by balls in rn. Mathematics Stack Exchange. URL https://math.stackexchange.com/q/2832639

  40. [49]

    Handbook of discrete and computational geometry

    Csaba D Toth, Joseph O’Rourke, and Jacob E Goodman. Handbook of discrete and computational geometry. CRC press, 2017

    2017

  41. [50]

    An introduction to hyperplane arrangements

    Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13 (389-496):24, 2004

    2004

  42. [51]

    Pennock, David M

    Xintong Wang, David M. Pennock, David M. Rothschild, and Nikhil R. Devanur. Designing expres- sive and liquid financial options markets via linear programming and automated market making. In Proceedings of the 5th ACM International Conference on AI in Finance (ICAIF) , 2024

    2024

  43. [52]

    Pennock, Nikhil R

    Xintong Wang, David M. Pennock, Nikhil R. Devanur, David M. Rothschild, Biaoshuai Tao, and Michael P. Wellman. Designing a combinatorial financial options market. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC) , page 864–883, 2021

    2021

  44. [53]

    New bounds for matrix multiplication: from alpha to omega, 2023

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega, 2023

    2023

  45. [54]

    Polygon retrieval

    Dan E Willard. Polygon retrieval. SIAM Journal on Computing , 11(1):149–165, 1982

    1982

  46. [55]

    On updating and querying submatrices

    Jason Yang and Jun Wan. On updating and querying submatrices. arXiv preprint arXiv:2010.13180 , 2020

    2010 arXiv

  47. [56]

    Lirong Xia and David M. Pennock. An efficient monte-carlo algorithm for pricing combinato- rial prediction markets for tournaments. In Toby Walsh, editor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain...

    2011 doi

  48. [58]

    Formal specification of constant product (xy= k) market maker model and implementation

    Yi Zhang, Xiaohong Chen, and Daejun Park. Formal specification of constant product (xy= k) market maker model and implementation. White paper, 2018. 24 A Proofs in Section 3 A.1 Proofs in Section 3.2 Algorithm 1 Range update on partition trees Require: A range E ⊆ X, value to ...

    2018

  49. [59]

    update(k, ∆): modify W (k) ← ∆

  50. [60]

    Theorem A.4 (Theorem 4.1 in Patrascu and Demaine [43])

    sum(k): returns the partial sum P i≤k W (i). Theorem A.4 (Theorem 4.1 in Patrascu and Demaine [43]) . Any algorithm for the online partial sums problem in the group arithmetic model has a running time per operation of Ω(log n) in the worst case. Proof of Corollary 3.9. We will...

  51. [61]

    The first and the third ensure that Eq

    propagates the lazy value to each child u ∈ C(root) so that pend( root) ◦ pend(u) is unchanged, and 3) pend′(root) = 1S . The first and the third ensure that Eq. (28) holds for the root node because pend′(u) ⊗ val′(root) = 1S ⊗ val′(root) = val′(root) = pend(root) ⊗ val(root) ...

  52. [3975]

    URL http://dx.doi.org/10.1016/j.tcs.2020.11.034

    doi: 10.1016/j.tcs.2020.11.034. URL http://dx.doi.org/10.1016/j.tcs.2020.11.034

    2020 doi

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.