Intelligent Agent Foundations Forumsign up / log in
The set of Logical Inductors is not Convex
post by Scott Garrabrant 1029 days ago | Sam Eisenstat, Abram Demski and Patrick LaVictoire like this | 3 comments

Sam Eisenstat asked the following interesting question: Given two logical inductors over the same deductive process, is every (rational) convex combination of them also a logical inductor? Surprisingly, the answer is no! Here is my counterexample.

We construct two logical inductors over PA, \(\{\mathbb{P}_n\}\), and \(\{\mathbb{P}^\prime_n\}\).

Let \(\{\mathbb{P}_n\}\) be any logical inductor over PA.

We consider an infinite sequence of sentences \(\phi_n:\Leftrightarrow"\mathbb{P}_n(\phi_n)<1/2"\).

Let \(\mathbb{P}_n(\phi_n)\) be computable in \(f(n)\) time.

We construct \(\{\mathbb{P}^\prime_n\}\) as in the paper, but instead of using all traders computable in time polynomial in \(n\), we use all traders computable in time polynomial in \(f(n)\) time. Since this also includes all polynomial time traders, \(\{\mathbb{P}^\prime_n\}\) is a logical inductor.

However, since the truth value of \(\phi_n\) is computable in \(f(n)\) time, if the difference between \(\mathbb{P}^\prime_n(\phi_n)\) and the indicator of \(\phi_n\) did not converge to 0, a trader running in time polynomial in f(n) can easily exploit \(\{\mathbb{P}^\prime_n\}\). Thus,

\[\mathbb{P}_n(\phi_n)\eqsim_n 1/2,\]

and

\[\mathbb{P}^\prime_n(\phi_n)\eqsim_n Thm_{PA}(\phi_n).\]

Now, consider the market

\[\left\{\mathbb{P}^{\prime\prime}_n=\frac{\mathbb{P}_n+\mathbb{P}^\prime_n}{2}\right\}.\]

Observe that

\[\mathbb{P}^{\prime\prime}_n(\phi_n)\eqsim_n \frac{1+2\cdot Thm_{PA}(\phi_n)}{4},\]

so

\[|\mathbb{P}^{\prime\prime}_n(\phi_n)-1/2|\eqsim_n 1/4.\]

Now, consider the trader who exploits \(\{\mathbb{P}^{\prime\prime}_n\}\) by repeatedly either buying a share of \(\phi_n\) when the price is near 3/4, or selling a share when the price is near 1/4, waiting for that sentence to be resolved, and then repeating. Eventually, in each cycle, this trader will make roughly 1/4 of a share, because eventually the price will always be close enough to either 1/4 or 3/4, and all shares that this trader buys will be true, and all shares that this trader sells will be false.

Thus \(\{\mathbb{P}^{\prime\prime}_n\}\) is not a logical inductor.



by Sam Eisenstat 1029 days ago | Scott Garrabrant likes this | link

Nicely done. I should have spent more time thinking about liar sentences; you really can do a lot with them.

Follow-up question - is the set of limits of logical inductors convex? (We can regard your proof as showing that the set of “expanded limits”, i.e. things of the form \((\liminf_{n \to \infty} \mathbb{P}_n(\phi_n))_{\overline{\phi}\textrm{ efficiently computable}}\) is not convex, but we have reason to expect limits in the usual sense to be nicer objects.)

reply

by Abram Demski 557 days ago | link

This uses logical inductors of distinctly different strengths. I wonder if there’s some kind of convexity result for logical inductors which can see each other? Suppose traders in \(\mathbb{P}_n\) have access to \(\mathbb{P}'_n\) and vice versa. Or perhaps just assume that the markets cannot be arbitrarily exploited by such traders. Then, are linear combinations also logical inductors?

reply

by Vanessa Kosoy 557 days ago | link

This is somewhat related to what I wrote about here. If you consider only what I call convex gamblers/traders and fix some weighting (“prior”) over the gamblers then there is a natural convex set of dominant forecasters (for each history, it is the set of minima of some convex function on \(\Delta\mathcal{O}^\omega\).)

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

[Note: This comment is three
by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

RSS

Privacy & Terms