The set of Logical Inductors is not Convex

post by Scott Garrabrant · 2016-09-27T09:05:00.000Z · score: 3 (3 votes) · LW · GW · None 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, , and .

Let be any logical inductor over PA.

We consider an infinite sequence of sentences .

Let be computable in time.

We construct as in the paper, but instead of using all traders computable in time polynomial in , we use all traders computable in time polynomial in time. Since this also includes all polynomial time traders, is a logical inductor.

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

and

Now, consider the market

Observe that

so

Now, consider the trader who exploits by repeatedly either buying a share of 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 is not a logical inductor.

None comments

Comments sorted by top scores.

comment by SamEisenstat · 2016-09-27T16:20:37.000Z · score: 1 (1 votes) · LW(p) · GW(p)

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? (Your proof also makes me curious as to whether the set of "expanded limits" is convex, though that question is a bit less nice than the other).

comment by LawChan · 2017-08-13T00:26:43.000Z · score: 0 (0 votes) · LW(p) · GW(p)

From conversation with Scott and Michael Dennis: there aren't enough logical inductors to make the set of limits convex, since there are an uncountable number of convex combinations but only a countable number of inductors (and thus limits). The interesting question would be whether any rational/computable convex combination of limits of logical inductors is a logical inductor.

comment by abramdemski · 2018-01-11T22:41:51.000Z · score: 0 (0 votes) · LW(p) · GW(p)

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 have access to and vice versa. Or perhaps just assume that the markets cannot be arbitrarily exploited by such traders. Then, are linear combinations also logical inductors?

comment by Vanessa Kosoy (vanessa-kosoy) · 2018-01-12T15:56:58.000Z · score: 0 (0 votes) · LW(p) · GW(p)

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 .)