Markets are Universal for Logical Induction

post by johnswentworth · 2019-08-22T06:44:56.532Z · LW · GW · 2 comments

Contents

  Background
  Our Goal
  The Proof
  The Bigger Picture
None
2 comments

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}}}{)}^{th}$ 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}}}{)}^{th}$ 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 portfolio held by everyone is zero - i.e. T(P) + M(P) = 0. This means that any long position held by T must be balanced by a short position held by M, and vice versa, at the market prices.
• We know the trader’s function T, and we know the prices P which we want to represent, so we solve for M: M(P) = -T(P)

… so the market containing M and T reproduces the prices P, as desired. One problem: this conceptual “proof” works even if the prices are exploitable. What gives?

The main trick here is budgeting: the real setup gives the traders limited budget, and they can’t keep trading if they go broke. Since M is doing exactly the opposite of T, M will go broke when T has unbounded gains - i.e. when T exploits the prices (this is basically the definition of exploitation used in the paper). But if the prices are inexploitable, then T’s possible gains are bounded, therefore M’s possible losses are bounded, and M can keep counterbalancing T’s trades indefinitely.

Let’s formalize that a bit. I’ll re-use notation from the logical induction paper without redefining everything, so check the paper for full definitions.

First, let’s write out the correct version of “T(P) + M(P) = 0”. The missing piece is budgeting: rather than letting traders trade directly, the logical induction algorithm builds “budgeted” traders $B_{b_T}\left(T\right)$ and $B_{b_M}\left(M\right)$, where $b_T$ and $b_M$ are the two traders’ starting budgets. At each time t, the market maker mechanism then finds prices P_t for which

$B_{b_T}\left(T\right)(P_t,t)+B_{b_M}\left(M\right)(P_t,t)=0$

The budgeting function is a bit involved; see the paper for more. The important points are that:

• $B_{b_T}\left(T\right)$ will exploit the prices as long as T does
• Budgeting doesn’t change anything at all as long as the traders don’t put more money on the line than they have available; otherwise it scales down the trader’s investments to match their budget.

Enforcing the second piece involves finding the worst-possible world for each trader’s portfolio. M’s worst-possible world is $B_{b_T}\left(T\right)$’s best-possible world, so we reason:

• Since T cannot exploit the prices, neither can $B_{b_T}\left(T\right)$
• Since $B_{b_T}\left(T\right)$ cannot exploit the prices, its best-case gain is bounded
• Since $B_{b_T}\left(T\right)$’s best-case gain is bounded, the opposite strategy $-B_{b_T}\left(T\right)$’s maximum loss is bounded
• We can set M’s budget $b_M$ higher than this maximum loss, and set $M=-B_{b_T}\left(T\right)$, so that $B_{b_M}\left(M\right)=-B_{b_T}\left(T\right)$, as desired.

To recap: given a series of prices over time $P_t$ inexploitable by trader T, we constructed a market containing T which reproduces the prices $P_t$.

The proof approach generalizes easily to more traders: simply replace “$B_{b_T}\left(T\right)$” with ${\sum }_i{B}_{b_{T_i}}\left(T_i\right)$ to sum over the contribution of each individual trader, then select M to balance them out, as before. Since the prices are inexploitable by every trader, the traders’ aggregate best-case gains are bounded above, so M’s worst-case loss is bounded below. This works even with infinite traders, as long as the total budget of all traders remains finite.

In particular, if we consider all polynomial-time traders (with budgeting and other details handled as in the paper), we find that any prices satisfying the logical induction criterion can be represented by a market containing all of the polynomial-time traders.

The Bigger Picture

Why does this matter?

First and foremost, it neatly characterizes the class of logical inductors: there are degrees of freedom in budgeting, and a huge degree of freedom in choosing the trader M which shares the market with our polynomial-time traders, but that’s it - that’s all we need to represent all possible logical inductors. (Note that this does not mean that simulating a prediction market containing all possible polynomial-time traders is the only way to implement a logical inductor - just that there is always a prediction market which produces the same prices as the logical inductor.)

Second, the proof is short and simple enough to generalize well. We should expect a similar technique to work under other notions of exploitability, and in scenarios beyond logical induction. This ties in to a general research path I’ve been playing with: many conditions of “inexploitability” or “efficiency” which we typically associate with utility functions instead produce markets when we relax the assumptions somewhat. Since markets are strictly more general than utility functions, and typically satisfy the same inexploitability/inefficiency criteria under more general assumptions, these kinds of results suggest that we should use markets of subagents in many models where we currently use utilities - see “Why Subagents? [LW · GW]” for more along these lines.

2 comments

Comments sorted by top scores.