9.25 The Market Maker's Impossibility: Speed Versus Accuracy, and Why Arbitrage Is Tolerated

Polymarket could eliminate structural arbitrage tomorrow. It chooses not to, and the choice is forced by a theorem, not by laziness. A combinatorial market maker faces a hard fork: price fast, or price coherently, and no mechanism does both unless one of the deepest open problems in computer science quietly turns out to be trivial. The platform picked speed. The bill for that choice is the entire structural half of this pillar, the roughly $40M that arbitrageurs extracted in a single election cycle. That is not a bug the exchange is racing to patch. It is a line item it has decided to pay.

The Dutch-book argument in "The Dutch Book Theorem, Plainly" showed that incoherent prices exist. This is the harder question behind it: why can a well-run, well-capitalized exchange not simply keep its prices coherent and shut the arbitrageurs out? The answer is computational, and once you see it, the permanence of structural edge stops looking like a temporary inefficiency and starts looking like a design constant.

The fork: fast or coherent, pick one

State the tradeoff as the proposition it is. For any cost-function market maker running combinatorial markets with logical dependencies between them, exactly one of two things holds.

Fast price updates, meaning constant-time per trade, imply arbitrage exists. Coherent prices, meaning the price vector always sits inside the arbitrage-free set, imply each update requires solving an NP-hard integer program. No mechanism achieves both at once.

The reason is membership testing. Keeping prices coherent after every trade means verifying, every time, that the new price vector lies inside the marginal polytope from "The Marginal Polytope: One Shape That Contains Every Fair Price." For general logical constraints of the integer-programming form, that verification is co-NP-hard, the complement of checking integer feasibility. A maker that enforces coherence in real time must therefore solve a co-NP-hard problem on every single trade, which is flatly incompatible with the sub-100-millisecond updates a live exchange needs, unless P equals NP. The same computational wall that "Frank-Wolfe: Solving a Quintillion-Vertex Problem in 100 Steps" climbs from the arbitrageur's side, approximating the projection with a hundred oracle calls, is the wall the exchange would have to climb exactly, on every order, for every user. The arbitrageur gets to be approximate and occasional. The maker would have to be exact and constant. That asymmetry is the whole game.

Polymarket chose speed, on purpose

Faced with the fork, Polymarket runs independent logarithmic-market-scoring-rule sub-markets, each pricing in under 100 milliseconds, with no real-time mechanism enforcing consistency across related markets. Fast, cheap, responsive, and permanently arbitrageable. The platform tolerates the arbitrage for three concrete reasons, and each one is a business decision, not an oversight.

Arbitrageurs supply volume and liquidity. Someone racing to close an incoherence is placing orders, tightening books, and moving prices toward fair, which is exactly the activity a young exchange wants more of. The maker's loss is bounded, at b times the log of the outcome count from "If You've Used a Softmax Layer, You Already Know the Price Formula," so the downside of running fast is capped by construction and known in advance. And removing the arbitrage would require the slow, coherent pricing on the other side of the fork, which would throttle trading volume and drive users away. The cure is worse than the disease.

Put a number on the disease. Benchmark the roughly $40M in estimated arbitrage profit over the cycle against public figures for Polymarket's gross fee revenue in the same window, and it lands on the order of a few tens of percent, around 20 percent in a back-of-the-envelope read. Significant, and evidently acceptable. The exchange is handing arbitrageurs a fifth of its gross fee take as the price of pricing fast, and the trade is worth it to them. This reframes the arbitrageur from parasite to paid liquidity provider, and it is why the edge is not a race the platform is trying to win. As long as the platform prices fast, the edge regenerates continuously, trade after trade, which is the permanence the article "The Term Structure of Prediction-Market Strategy and Crowding" relies on when it treats structural incoherence as a renewable resource rather than a one-time find.

Why this is not a market inefficiency that competition erases

Retail intuition says any free money gets competed away, so structural arbitrage must be a fluke that closes. That intuition, the one behind the old article "Random Walk and Efficient Markets Are Not the Same Thing," is right about informational edges and wrong here. Competition among arbitrageurs decides who captures a given incoherence and how fast, the crowding dynamics from the term-structure article, but it does not stop new incoherences from being born. Each new trade on a fast independent sub-market can push prices back outside the coherent set, and the maker, pricing in constant time, does nothing to pull them back. The generator of the edge is the exchange's own pricing mechanism, running on every order, forever. You are not front-running a mispricing that will correct. You are harvesting the exhaust of a machine that is designed to keep producing it.

Reflexivity: where the exchange's choice does bite the trader

One caveat separates the two halves of the pillar. Structural arbitrage needs no forecast, so it is immune to reflexivity, the feedback loop where the price itself changes the reality it is pricing. For informational trades on high-visibility events, that loop is a first-order effect. On a big election, the market price shifts campaign spending, media narratives, and turnout, which shifts the true probability, which shifts the price again, an oscillation.

$$ \text{no feedback:} \quad x_t = f(x_{t-1}) + w_t \qquad\qquad \text{reflexive:} \quad x_t = f(x_{t-1},\, y_{t-1}) + w_t $$

Read that as: the standard model evolves the hidden true probability x from its own past plus noise, while the reflexive model lets the past price y feed back into the true probability's evolution. The first is the clean world the structural arbitrageur lives in. The second is the messy world the informational trader from "Bayesian Edge in Log-Odds" actually trades, where the price is both a measurement of reality and a cause of it. The oscillation reflexivity creates is exploitable with mean reversion if you can estimate the feedback strength, but it also means an informational edge on a high-profile event is fighting a moving target it is helping to move. That is one more reason the pillar ranks structural edge above informational: the structural trader is exempt from the feedback the informational trader cannot escape.

KEY POINTS

• A combinatorial market maker faces a forced fork: fast updates imply arbitrage exists, coherent prices imply an NP-hard integer solve per trade. No mechanism does both unless P equals NP.
• The reason is membership testing. Keeping prices inside the marginal polytope after every trade is co-NP-hard, incompatible with sub-100-millisecond updates. The arbitrageur gets to be approximate and occasional; the maker would have to be exact and constant.
• Polymarket chose speed: independent LMSR sub-markets, no real-time cross-market consistency. Fast, cheap, and permanently arbitrageable.
• The platform tolerates arbitrage for three reasons: arbitrageurs supply volume and liquidity, the maker's loss is bounded at b times the log of the outcome count, and removing the arbitrage would require slow pricing that kills volume.
• The bill is roughly 20 percent of gross fees, around $40M in one election cycle. The exchange pays a fifth of its fee take to price fast, and finds the trade worth it. The arbitrageur is a paid liquidity provider, not a parasite.
• This is not an inefficiency competition erases. Competition decides who captures each incoherence, but the exchange's fast pricing keeps generating new ones on every trade. The edge is a renewable resource, not a closing window.
• Structural arbitrage is immune to reflexivity because it needs no forecast. Informational trading on high-visibility events fights a price-reality feedback loop, one more reason structural edge outranks informational.

References

• Arbitrage-Free Combinatorial Market Making via Integer Programming - Kroer et al. (2016)
• Combinatorial Information Market Design - Hanson (2003)
• A Tractable Combinatorial Market Maker Using Constraint Generation - Dudik et al. (2012)
• Prediction Markets - Wolfers and Zitzewitz (2004)
• The Promise of Prediction Markets - Arrow et al. (2008)
• Unravelling the Probabilistic Forest: Arbitrage in Prediction Markets - Saguillo et al. (2025)