The set of Logical Inductors is not Convex

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, ${P_{n}}$ , and ${P_{n}^{'}}$ .

Let ${P_{n}}$ be any logical inductor over PA.

We consider an infinite sequence of sentences $ϕ_{n} :\Leftrightarrow" P_{n} (ϕ_{n}) < 1 / 2 "$ .

Let $P_{n} (ϕ_{n})$ be computable in $f (n)$ time.

We construct ${P_{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, ${P_{n}^{'}}$ is a logical inductor.

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

$P_{n} (ϕ_{n}) ≂_{n} 1 / 2,$

and

$P_{n}^{'} (ϕ_{n}) ≂_{n} T h m_{P A} (ϕ_{n}) .$

Now, consider the market

${P_{n}^{''} = \frac{P_{n} + P_{n}^{'}}{2}} .$

Observe that

$P_{n}^{''} (ϕ_{n}) ≂_{n} \frac{1 + 2 \cdot T h m_{P A} (ϕ_{n})}{4},$

$| P_{n}^{''} (ϕ_{n}) - 1 / 2 | ≂_{n} 1 / 4.$

Now, consider the trader who exploits ${P_{n}^{''}}$ by repeatedly either buying a share of $ϕ_{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 ${P_{n}^{''}}$ is not a logical inductor.

3 comments, sorted by

top scoring

Click to highlight new comments since: Today at 7:01 AM

New Comment

[-]Sam Eisenstat6y 1

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" ${{liminf}_{n \to \infty} P_{n} (ϕ_{n})}_{¯ ¯ ¯ ϕ efficiently computable}$ is convex, though that question is a bit less nice than the other).

[-]Abram Demski4y 0

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 $P_{n}$ have access to $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?

[-]Vanessa Kosoy4y 0

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 $Δ O^{ω}$ .)