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. Here is another way to think about it. We get an infinite number of "retries". We first set the price to something arbitrary. Then we get to see what the trader would do in that situation. Ah, it buys some shares, making money in expectation. We want to prevent that, so we pretend that wasn't the real market price, and see what the trader does in the new, adjusted price. 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}}$

This turns out to be equivalent to $\max(0,\min(1,x+\delta ))$, which is the form of fix given in the paper. To see this, just split into cases based on $\delta >0$, $\delta =0$, or $\delta <0$. The version in the paper makes it obvious that the function is continuous, but it is more difficult to see what is going on.

We want some $x$ such that $x=f(x,t(x))$, i.e. we are satisfied with the price so that we don't try to change it. Thanks to $f,t$ both being continuous, this is guaranteed by Brouwer's fixed point theorem.

We imagined that we were working with just one sentence, but it turns out that (for some reason) basically the same thing works when dealing with all sentences.

Another thing to wonder is that the rate of adjustment is just $1\cdot \delta$. What if we did $2\cdot \delta$ instead? or $\delta /2$? or $\delta ^{2}$? It seems like these would change the slope of the graph of $f(x,t(x))$, which means we might introduce more fixed points (just graph the identity function with the new functions); one of the nice things about slope=1 is that it is parallel to the identity function, so we get exactly one fixed point, or infinitely many. Actually, the scalar on x is still 1, so this probably doesn't matter.

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

Definition/Proposition 5.1.2 (MarketMaker)

Define $f:[0,1]^{\mathcal {S}}\to \mathbb {R}$ by $f(\mathbb {V} )=\max _{\mathbb {W} '\in {\mathcal {W}}'}\mathbb {W} '(T_{n}(\mathbb {P} _{\leq n-1},\mathbb {V} ))$ (this is the same map given in the proof).

Let's see what $f$ does to $\mathbb {V} ^{\text{fix}}$. By the Fixed Point Lemma, for any $\mathbb {W}$ we have $\mathbb {W} '(T_{n}(\mathbb {P} _{\leq n-1},\mathbb {V} ^{\text{fix}}))\leq 0$. This means that as we max over these worlds, we will never exceed 0. So $f(\mathbb {V} ^{\text{fix}})\leq 0$. Or in other words $f(\mathbb {V} ^{\text{fix}})\in (-\infty ,0]\subset (-\infty ,2^{-n})$. (I had two confusions here: first, for some reason I mistakenly thought $2^{-n}$ was negative for a while, so got confused about why $f(\mathbb {V} ^{\text{fix}})$ was always contained in the interval. Second, I wondered why the left endpoint was minus infinity; couldn't any negative number also work? it couldn't, because we don't know how negative the trader could be; in other words, the trader could perform arbitrarily badly and we don't have a lower bound on that.)

"Hence there is some neighborhood in ${\mathcal {V}}'$ around $\mathbb {V} ^{\text{fix}}$ with image in $(-\infty ,2^{-n})\subset \mathbb {R}$." -- This uses one of the equivalent definitions of continuity (often called the topological definition of continuity), namely, $f:X\to Y$ is continuous iff for every open set $V\subset Y$ such that $f(x_{0})\in V$, there exists an open set $U\subset X$ such that $x_{0}\in U$ and $f(U)\subset V$. Here we know that $(-\infty ,2^{-n})$ is open and $f(\mathbb {V} ^{\text{fix}})\in (-\infty ,2^{-n})$. So there exists an open set $U\subset {\mathcal {V}}'$ such that $f(\mathbb {V} ^{\text{fix}})\in U$ and $f(U)\subset (-\infty ,2^{-n})$.

One thing I'm unclear on is, are we using a metric on ${\mathcal {V}}'$? If so, what is the metric?

Lemma 5.1.3 (MarketMaker Inexploitability)

This proof is pretty simple.

We use the geometric series $\sum _{i=0}^{\infty }2^{-i}={\frac {1}{1-1/2}}=2$. (Then subtract $2^{0}=1$ since index starts at 1 rather than 0.)

Definition/Proposition 5.2.1 (Budgeter)

Why does Budgeter get all of ${\overline {D}}$? It seems to use only $D_{m}$ up to $m\leq n$.

What's up with the then-clause? Does it even trigger?

For the inf expression in the else-clause: the fact that we're in the else-clause means that for $n-1$ in particular, the sum ${\textstyle \mathbb {W} (\sum _{i\leq n-1}T_{i}(\mathbb {P} _{\leq i}))>-b}$. So the denominator ${\textstyle \mathbb {W} (\sum _{i\leq n-1}T_{i}(\mathbb {P} _{\leq i}))+b>0}$.

Lemma 5.2.2 (Properties of Budgeter)

Part 1

If the trader never overspends, then budgeter does nothing.

Part 2

If we inductively alter the trader on every single day, then we never overspend.

Part 3

If the trader can exploit the market, then we can give it the budget it needs so that it can do its thing.

See also

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