Xintong Wang, Rutgers University

Abstract

Designing automated market makers (AMMs) for prediction markets on combinatorial securities over large outcome spaces presents significant computational challenges. Prior research has studied combinatorial prediction markets on specific set systems (e.g., intervals, permutations), characterizing and addressing the design challenges by exploiting their respective security or outcome structures. A general framework for AMM design across arbitrary set systems remains undeveloped. Through establishing a connection between the design of AMMs for combinatorial prediction markets and the range query problem in computational geometry, we present a unified framework for both analyzing the computational complexity and designing efficient AMMs for combinatorial prediction/DeFi markets. The talk will be based on results from SODA'25 jointly with Fang-Yi Yu and AAMAS'21 together with Miro Dudik, David Pennock, and David Rothschild.

See: https://theory.cs.rutgers.edu/theory_seminar