Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio.
This is: Markets are Universal for Logical Induction, published by johnswentworth on the AI Alignment Forum.
Background
Logical Induction is the best framework currently available for thinking about logical uncertainty - i.e. the “probability” that the twin primes conjecture is true, or that the
10
10
10
10
t
h
digit of pi is 3. This is important for lots of reasons, and you should read the introduction of the paper (or the abridged version) for a much more detailed background.
The general idea of logical induction is to assign probability-like numbers to logical statements like “the
10
10
10
10
t
h
digit of pi is 3”, and to refine these “probabilities” over time as the system thinks more. To create these “probabilities”, each statement is associated with an asset in a prediction market, which eventually pays $1 if the statement is proven true, or $0 if it is proven false. The “probabilities” are then the prices of these assets.
(It’s also possible that a statement is never proven or disproven, and one of the many interesting results of the paper is that logical inductors assign useful prices in that case too.)
The logical induction paper has two main pieces. First, it introduces the logical induction criterion: a system which assigns prices to statements over time is called a “logical inductor” if the prices cannot be exploited by any polynomial-time trading algorithm. The paper then shows that this criterion implies that the prices have a whole slew of useful, intuitive, probability-like properties.
The second main piece of the paper proves that at least one logical inductor is computable: the paper constructs an (extremely slow) algorithm to compute inexploitable prices for logical statements. The algorithm works by running a prediction market in which every possible polynomial-time trader is a participant. Naturally, the prices in this market turn out to be inexploitable by any polynomial-time trader - so, this giant simulated prediction market is a logical inductor.
Our Goal
An analogy: one could imagine a decision theorist making a list of cool properties they want their decision theory to have, then saying “well, here’s one possible decision algorithm which satisfies these properties: maximize expected utility”. That would be cool and useful, but what we really want is a theorem saying that any possible decision algorithm which satisfies the cool properties can be represented as maximizing expected utility.
This is analogous to the situation in the logical induction paper: there’s this cool criterion for handling logical uncertainty, and it implies a bunch of cool properties. The paper then says “well, here’s one possible algorithm which satisfies these properties: simulate a prediction market containing every possible polynomial-time trader”. That’s super cool and useful, but what we really want is a theorem saying that any possible algorithm which satisfies the cool properties can represented as a prediction market containing every possible polynomial-time trader.
That’s our goal. We want to show that any possible logical inductor can be represented by a market of traders - i.e. there is some market of traders which produces exactly the same prices.
The Proof
We’ll start with a slightly weaker theorem: any prices which are inexploitable by a particular trader T can be represented by a market in which T is a participant.
Conceptually, we can sketch out the proof as:
The “trader” T is a function which takes in prices P, and returns a portfolio T(P) specifying how much of each asset it wants to hold.
The rest of the market is represented by an aggregate trader M (for “market”), which takes in prices P and returns a portfolio M(P) specifying how much of each asset the rest of the market wants to hold.
The “market maker” mechanism chooses prices so that the total portfoli...
view more