User:IssaRice/Logical inductor construction

Notes from the Logical Induction paper as I walk through the construction of LIA in section 5.

Lemma 5.1.1 (Fixed Point Lemma)

"Observe that ${\mathcal {V}}'$ is equal to the natural inclusion of the finite-dimensional cube $[0,1]^{{\mathcal {S}}'}$ in the space of all valuations ${\mathcal {V}}=[0,1]^{\mathcal {S}}$." -- I think what this is saying is that since ${\mathcal {S}}'\subset {\mathcal {S}}$, we can think of $[0,1]^{{\mathcal {S}}'}$ as being sort of a subset of $[0,1]^{\mathcal {S}}$. Except it's not strictly speaking a subset, since the functions in $[0,1]^{{\mathcal {S}}'}$ and $[0,1]^{\mathcal {S}}$ have different domains. How can we make it a subset? The "natural" way to do this is to set everything outside of ${\mathcal {S}}'$ to zero. But that's exactly what ${\mathcal {V}}'=\{\mathbb {V} \in [0,1]^{\mathcal {S}}:\mathbb {V} (\phi )=0{\text{ whenever }}\phi \notin {\mathcal {S}}'\}$ is. One thing I'm still not sure about is the "finite-dimensional" part; doesn't having $[0,1]$ make the cube infinite-dimensional?

Definition of fix: I found it helpful to look at the graph of $f(x)=\max(0,\min(1,x))$; this looks like the identity function in the interval $[0,1]$, but then becomes constant once it hits either of the endpoints. If you've already thought about the definition of continuous threshold indicator (definition 4.3.2), then you will recognize that $f(x)=\mathrm {Ind} _{1}(x>0)$.

"the compact, convex space ${\mathcal {V}}'$" -- this intuitively makes sense, since ${\mathcal {V}}'$ basically "looks like" a cube. But I'm not sure how to verify this.

For the fixed point reasoning: we don't actually have a fixed point of $f$; instead, it's a fixed point of $g$, where $g(x)=f(x+\delta )$ and $\delta =T_{n}(\mathbb {P} _{\leq n-1},\mathbb {V} ^{\text{fix}})[\phi ]$. If $\delta >0$, then the graph of $g$ is just the graph of $f$ but shifted to the left. You will see that this intersects the graph of the identity function at $x=1$; this is the fixed point. On the other hand, if $\delta <0$, then we shift the graph of $f$ to the right, and now the fixed point is at $x=0$.

The key property of $\mathbb {V} ^{\text{fix}}$ that we use in the proof:

• If $T_{n}$ buys a share of $\phi$ on day $n$, then the price of $\phi$ on day $n$ is 1 (the maximum possible).
• If $T_{n}$ sells a share of $\phi$ on day $n$, then the price of $\phi$ on day $n$ is 0 (the minimum possible).

One question to ask is, couldn't we just avoid using Brouwer's fixed point theorem by just setting the prices to obey the above property? There are two problems with this. One is that the definition of the $n$th day prices would depend on $T_{n}$'s behavior, which depends on the $n$th day prices! So the definition would be circular. The other problem is that we can't guarantee that the map would be continuous if we just magically set it to obey some property.

Something else I got confused about: I was thinking that the above key property only talks about day $n$. Couldn't the trader make a lot of money on previous days, and then just make no money on day $n$, so that it would still be making lots of money? The answer is that we are only dealing with a trading strategy in this lemma, not a full trader. Later, in lemma 5.1.3, we recursively use this idea to deal with a full trader.

How do we come up with the definition of fix? Here's one way to think about it. Let $x$ be the market price (of some sentence on day $n$) and $\delta$ be the trading volume of that sentence on the same day. We want to return some quantity $f(x,\delta )$ that fixes up the price, after the fact, so that the trader would have earned less money. Why after the fact? Because doing it in real time is confusing! The trader depends on the prices for day n, which is what we want to decide. But we want to know what the trader does on day n in order to determine the prices. So there is a circular dependency. This sort of thing happens in game theory too, where everything does eventually take place in real time, but we can think iteratively by "pressing pause" and considering counterfactuals and going down different paths in the game tree. It's also a hint that fixed points are going to appear. Ideally we would like to say something like:

$f(x,\delta )={\begin{cases}1&{\text{if }}\delta >0\\x&{\text{if }}\delta =0\\0&{\text{if }}\delta <0\end{cases}}$

This will work, but it's after the fact. We eventually would like to fix the prices in real time. So one way to think about this is to adjust the prices a little at a time, querying the trading strategy each time to see if we should nudge the prices up or down. Here is one idea:

$f(x,\delta )={\begin{cases}x+\epsilon &{\text{if }}\delta >0\\x&{\text{if }}\delta =0\\x-\epsilon &{\text{if }}\delta <0\end{cases}}$

where $\epsilon >0$ is some small adjustment. In other words, if a trader buys at the current price, then nudge it up a little to make it a slightly worse deal for the trader. And if the trader sells at the current price, then nudge it down. Now, there are three problems with this map. As a function of $\delta$, it's still discontinuous (ugly). Also, we don't check whether the values we return stay within the allowed $[0,1]$ interval of valuations. But most importantly, if we only adjust the prices a little, that means the trader can still make money from us. So what can we do? Well, we can apply the map many times: $f(f(f(f(f(x,\delta ),\delta ),\delta ),\delta ),\delta )$ (actually, maybe we should allow the $\delta$s to change as well, to react in response). Now it's like a turn-based game: the trader says he's going to buy, so we adjust up; the trader still says he's buying, so we adjust up again; the trader now says he's going to sell, so we adjust down (oops, now we're in exactly the same spot, leading to an infinite loop...).

We can fix the second problem above with the following:

$f(x,\delta )={\begin{cases}\min(1,x+\epsilon )&{\text{if }}\delta >0\\x&{\text{if }}\delta =0\\\max(0,x-\epsilon )&{\text{if }}\delta <0\end{cases}}$

Now if the prices go out of bounds, they get adjusted back to the bound, but otherwise they are unaffected.

Let $t:[0,1]\to \mathbb {R}$ be a trading strategy that takes the price of a sentence and outputs how much it would trade at that price. So then we start with some price $x_{1}$, which gets fed into $t$ to get $\delta _{1}=t(x_{1})$. Then we have the next price $x_{2}=f(x_{1},\delta _{1})$. And the next trade volume is $\delta _{2}=t(x_{2})$ and so on. So we get $f(f(x_{1},t(x_{1})),t(f(x_{1},t(x_{1}))))$.

So what can we do to avoid the infinite loop? One idea might be to decrease the step size $\epsilon$ with time (the number of iterations). This sort of thing is reminiscent of some versions of gradient descent. Another idea is to make the step size a function of $\delta$: if the trader trades a lot, then we adjust a lot, but if the trader trades only a little, it signals that we're getting close to ... a fixed point!

$f(x,\delta )={\begin{cases}\min(1,x+|\delta |)&{\text{if }}\delta >0\\x&{\text{if }}\delta =0\\\max(0,x-|\delta |)&{\text{if }}\delta <0\end{cases}}$

The following is used in the Fixed Point Lemma (5.1.1):

Writing the $n$-strategy as

$T_{n}=\sum _{j=1}^{k}\xi _{j}\phi _{j}-\sum _{j=1}^{k}\xi _{j}\phi _{j}^{*n}$

we have

$\mathbb {V} (T_{n}(\mathbb {P} _{\leq n-1},\mathbb {V} ))=\sum _{j=1}^{k}\xi _{j}(\mathbb {P} _{\leq n-1},\mathbb {V} )\cdot \mathbb {V} (\phi _{j})-\sum _{j=1}^{k}\xi _{j}(\mathbb {P} _{\leq n-1},\mathbb {V} )\cdot \phi _{j}^{*n}(\mathbb {P} _{\leq n-1},\mathbb {V} )$

But $\phi _{j}^{*n}(\mathbb {P} _{\leq n-1},\mathbb {V} )=\mathbb {V} (\phi _{j})$ so the two sums cancel to obtain $0$.

See also

• https://machinelearning.subwiki.org/wiki/User:IssaRice/Logical_induction_notation