User:IssaRice/Logical inductor construction - Revision history

IssaRice: /* Definition/Proposition 5.1.2 (MarketMaker) */

2019-08-01T05:35:59Z

Definition/Proposition 5.1.2 (MarketMaker)

← Older revision		Revision as of 05:35, 1 August 2019
Line 68:		Line 68:

	Let's see what <math>f</math> does to <math>\mathbb V^\text{fix}</math>. By the Fixed Point Lemma, for any <math>\mathbb W</math> we have <math>\mathbb W'(T_n(\mathbb P_{\leq n-1}, \mathbb V^\text{fix})) \leq 0</math>. This means that as we max over these worlds, we will never exceed 0. So <math>f(\mathbb V^\text{fix}) \leq 0</math>. Or in other words <math>f(\mathbb V^\text{fix}) \in (-\infty, 0] \subset (-\infty, 2^{-n})</math>. (I had two confusions here: first, for some reason I mistakenly thought <math>2^{-n}</math> was negative for a while, so got confused about why <math>f(\mathbb V^\text{fix})</math> 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.)		Let's see what <math>f</math> does to <math>\mathbb V^\text{fix}</math>. By the Fixed Point Lemma, for any <math>\mathbb W</math> we have <math>\mathbb W'(T_n(\mathbb P_{\leq n-1}, \mathbb V^\text{fix})) \leq 0</math>. This means that as we max over these worlds, we will never exceed 0. So <math>f(\mathbb V^\text{fix}) \leq 0</math>. Or in other words <math>f(\mathbb V^\text{fix}) \in (-\infty, 0] \subset (-\infty, 2^{-n})</math>. (I had two confusions here: first, for some reason I mistakenly thought <math>2^{-n}</math> was negative for a while, so got confused about why <math>f(\mathbb V^\text{fix})</math> 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.)

			What I'm not sure about is why we need to do this <math>\max_{\mathbb W' \in \mathcal W'}</math> thing. Couldn't we fix some <math>\mathbb W</math> at the start, and consider the map <math>\mathbb V \mapsto \mathbb W(T_n(\mathbb P_{\leq n-1}, \mathbb V))</math>? Then by the same reasoning, for <math>\mathbb V^{\text{fix}}</math> maps into <math>(-\infty, 2^{-n})</math> so we have a neighborhood in <math>\mathcal V'</math> that maps into this open set. It seems like we didn't need to form the max over all the worlds. Of course, doing this <math>\mathbb W'</math> stuff becomes important when doing the brute force search later in the proof, but if we're merely trying to verify the pricing exists, it doesn't seem like we need to do this finite support stuff.

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

IssaRice: /* Lemma 5.1.1 (Fixed Point Lemma) */

2019-07-29T02:01:52Z

Lemma 5.1.1 (Fixed Point Lemma)

← Older revision		Revision as of 02:01, 29 July 2019
Line 7:		Line 7:
	Definition of fix: I found it helpful to look at the [https://www.wolframalpha.com/input/?i=plot+f(x)+%3D+max(0,+min(1,+x)) graph] of <math>f(x) = \max(0, \min(1, x))</math>; this looks like the identity function in the interval <math>[0,1]</math>, 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 <math>f(x) = \mathrm{Ind}_1(x > 0)</math>.		Definition of fix: I found it helpful to look at the [https://www.wolframalpha.com/input/?i=plot+f(x)+%3D+max(0,+min(1,+x)) graph] of <math>f(x) = \max(0, \min(1, x))</math>; this looks like the identity function in the interval <math>[0,1]</math>, 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 <math>f(x) = \mathrm{Ind}_1(x > 0)</math>.

	"the compact, convex space <math>\mathcal V'</math>" -- this intuitively makes sense, since <math>\mathcal V'</math> basically "looks like" a cube. But I'm not sure how to verify this.		"the compact, convex space <math>\mathcal V'</math>" -- this intuitively makes sense, since <math>\mathcal V'</math> basically "looks like" a cube. But I'm not sure how to verify this. -- Here's what I eventually came up with: in order to talk about a set being "compact" or "convex", we need some kind of structured space. But what kind of structured space? we can have metric spaces, normed spaces, inner product spaces, vector spaces, topological spaces, and on and on. The paper doesn't tell us what kind of space, so we have to figure it out on our own. Ok. But knowing the words "compact" and "convex", we can restrict what kind of space it can be. In particular, one way to go about this is to take the most general kind of structured space that each adjective ("compact" or "convex") can apply to, and then take the less general of the two, which gives us the most general kind of space that can take both adjectives. Now, theoretically, there can be a problem here, where when we do that, we get two spaces that are not comparable (formally: we have a partial order of structured spaces, and we are finding subsets of this partial order that can take each adjective, and then finding the maximum of the union, but because we're working on a partial order, a maximum might not exist -- we might just have a bunch of maximal elements). Luckily, in this case we don't need to worry about this problem... Anyway, compactness makes sense for topological spaces, which are very general. And convexity requires us to be able to add elements and scale them (since we need to form the expression <math>(1-t)v + tw</math> for <math>t\in [0,1]</math>). So maybe it's a topological vector space, but actually we don't need to be so general. I think we can just think of our space as being the subset <math>[0,1]^n</math> of the Euclidean space <math>\mathbf R^n</math>. I'm not entirely confident though; the paper talks about "the space of all valuations <math>\mathcal V = [0,1]^{\mathcal S}</math>", so maybe that's supposed to be the ambient space.

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

IssaRice: /* Lemma 5.1.1 (Fixed Point Lemma) */

2019-07-29T01:43:17Z

Lemma 5.1.1 (Fixed Point Lemma)

← Older revision		Revision as of 01:43, 29 July 2019
Line 3:		Line 3:
	==Lemma 5.1.1 (Fixed Point Lemma)==		==Lemma 5.1.1 (Fixed Point Lemma)==

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

	Definition of fix: I found it helpful to look at the [https://www.wolframalpha.com/input/?i=plot+f(x)+%3D+max(0,+min(1,+x)) graph] of <math>f(x) = \max(0, \min(1, x))</math>; this looks like the identity function in the interval <math>[0,1]</math>, 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 <math>f(x) = \mathrm{Ind}_1(x > 0)</math>.		Definition of fix: I found it helpful to look at the [https://www.wolframalpha.com/input/?i=plot+f(x)+%3D+max(0,+min(1,+x)) graph] of <math>f(x) = \max(0, \min(1, x))</math>; this looks like the identity function in the interval <math>[0,1]</math>, 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 <math>f(x) = \mathrm{Ind}_1(x > 0)</math>.

IssaRice: /* Lemma 5.1.1 (Fixed Point Lemma) */

2019-07-22T06:40:46Z

Lemma 5.1.1 (Fixed Point Lemma)

← Older revision		Revision as of 06:40, 22 July 2019
Line 60:		Line 60:

	But <math>\phi_j^{*n}(\mathbb P_{\leq n-1}, \mathbb V) = \mathbb V(\phi_j)</math> so the two sums cancel to obtain <math>0</math>.		But <math>\phi_j^{*n}(\mathbb P_{\leq n-1}, \mathbb V) = \mathbb V(\phi_j)</math> so the two sums cancel to obtain <math>0</math>.

			I think here is a simpler way to do the summation at the end: Write <math>T_n(\mathbb P_{\leq n-1}, \mathbb V)[\phi]</math> as <math>\xi_\phi</math>. Then we have <math display="block">\begin{align}\sum_{\phi \in \mathcal S}(\mathbb W(\phi) - \mathbb V^\text{fix}(\phi)) \cdot \xi_\phi &= \mathbb W\left(\sum_{\phi\in\mathcal S} (\phi - \mathbb V^\text{fix}(\phi))\xi_\phi\right) \\ &= \mathbb W\left(\sum_{\phi\in\mathcal S} (\phi-\phi^{n}(\mathbb P_{\leq n-1}, \mathbb V^\text{fix})) \xi_\phi\right) \\ &= \mathbb W(T_n(\mathbb P_{\leq n-1}, \mathbb V^\text{fix}))\end{align}</math> where the first equality follows from the linearity of <math>\mathbb W</math>, the second because <math>\phi^{n}(\mathbb P_{\leq n-1},\mathbb V^\text{fix}) = \mathbb V^\text{fix}(\phi)</math>, and the third because we can change the summation from <math>\phi\in\mathcal S</math> to <math>\phi \in \mathcal S'</math> and by the definition of <math>T_n</math>.

	==Definition/Proposition 5.1.2 (MarketMaker)==		==Definition/Proposition 5.1.2 (MarketMaker)==

IssaRice: /* Definition/Proposition 5.2.1 (Budgeter) */

2019-06-30T21:38:24Z

Definition/Proposition 5.2.1 (Budgeter)

← Older revision		Revision as of 21:38, 30 June 2019
Line 81:		Line 81:
	Why does Budgeter get all of <math>\overline D</math>? It seems to use only <math>D_m</math> up to <math>m \leq n</math>.		Why does Budgeter get all of <math>\overline D</math>? It seems to use only <math>D_m</math> up to <math>m \leq n</math>.

	What's up with the then-clause? Does it even trigger?		What's up with the then-clause? Does it even trigger? I think it's just there to make sure Budgeter is defined in all cases. The else-clause doesn't make sense for some values of <math display="inline">\mathbb W(\sum_{i \leq n-1} T_i(\mathbb P_{\leq i}))</math>.

			Another question I had was why the budget <math>b</math> is a positive integer, rather than a positive rational. After all, our markets run on rational prices. I think this is because in the way TradingFirm is constructed, all we care about is that we can increase the budget as much as we want, to let the good traders do what they want. The key property is Lemma 5.2.2.3. So basically we just need a subset of the rationals that is not bounded above. I think <math>\mathbb N^+</math> also works well because it's very easy to enumerate (maybe also it's important that it's easy to enumerate in increasing order).

	For the inf expression in the else-clause: the fact that we're in the else-clause means that the "if" part is false, so for <math>n-1</math> (which is less than <math>n</math>) in particular, the sum <math display="inline">\mathbb W(\sum_{i \leq n-1} T_i(\mathbb P_{\leq i})) > -b</math>. So the denominator <math display="inline">\mathbb W(\sum_{i \leq n-1} T_i(\mathbb P_{\leq i})) + b > 0</math>. Now suppose that according to <math>\mathbb W</math>, the trader wins money on day n. Then <math>-\mathbb W(T_n)</math> is negative, so that the whole fraction is negative. Thus the output of max is 1, so that Budgeter returns <math>T_n</math>. In other words, if the trader is going to win money anyway, then Budgeter does not interfere with what the trader is doing.		For the inf expression in the else-clause: the fact that we're in the else-clause means that the "if" part is false, so for <math>n-1</math> (which is less than <math>n</math>) in particular, the sum <math display="inline">\mathbb W(\sum_{i \leq n-1} T_i(\mathbb P_{\leq i})) > -b</math>. So the denominator <math display="inline">\mathbb W(\sum_{i \leq n-1} T_i(\mathbb P_{\leq i})) + b > 0</math>. Now suppose that according to <math>\mathbb W</math>, the trader wins money on day n. Then <math>-\mathbb W(T_n)</math> is negative, so that the whole fraction is negative. Thus the output of max is 1, so that Budgeter returns <math>T_n</math>. In other words, if the trader is going to win money anyway, then Budgeter does not interfere with what the trader is doing.

IssaRice: /* Proposition 5.3.1 (Redundant Enumeration of e.c. Traders) */

2019-06-30T21:30:08Z

Proposition 5.3.1 (Redundant Enumeration of e.c. Traders)

← Older revision		Revision as of 21:30, 30 June 2019
Line 110:		Line 110:

	Suppose we tried skipping the enumeration of the polynomials. Given <math>n</math>, we could decode it into a pair of integers <math>i,j</math>, and run <math>M(i)</math> for <math>j</math> steps. This would find all e.c. traders, but it would also find traders who aren't e.c., because the runtime isn't connected to the input to <math>M</math>.		Suppose we tried skipping the enumeration of the polynomials. Given <math>n</math>, we could decode it into a pair of integers <math>i,j</math>, and run <math>M(i)</math> for <math>j</math> steps. This would find all e.c. traders, but it would also find traders who aren't e.c., because the runtime isn't connected to the input to <math>M</math>.

			But given an <math>n</math>-strategy, shouldn't we be able to tell whether it is e.c. or not?

	==Definition/Proposition 5.3.2 (TradingFirm)==		==Definition/Proposition 5.3.2 (TradingFirm)==

IssaRice: /* Proposition 5.3.1 (Redundant Enumeration of e.c. Traders) */

2019-06-30T21:28:02Z

Proposition 5.3.1 (Redundant Enumeration of e.c. Traders)

← Older revision		Revision as of 21:28, 30 June 2019
Line 108:		Line 108:

	I think the key point of this proof is that the <math>n</math> in <math>M(n)</math> is the same as the <math>n</math> in <math>f(n)</math>, so that the input to the trader computation (which says what day it is) controls how long the computation can run.		I think the key point of this proof is that the <math>n</math> in <math>M(n)</math> is the same as the <math>n</math> in <math>f(n)</math>, so that the input to the trader computation (which says what day it is) controls how long the computation can run.

			Suppose we tried skipping the enumeration of the polynomials. Given <math>n</math>, we could decode it into a pair of integers <math>i,j</math>, and run <math>M(i)</math> for <math>j</math> steps. This would find all e.c. traders, but it would also find traders who aren't e.c., because the runtime isn't connected to the input to <math>M</math>.

	==Definition/Proposition 5.3.2 (TradingFirm)==		==Definition/Proposition 5.3.2 (TradingFirm)==

IssaRice: /* Proposition 5.3.1 (Redundant Enumeration of e.c. Traders) */

2019-06-30T21:21:22Z

Proposition 5.3.1 (Redundant Enumeration of e.c. Traders)

← Older revision		Revision as of 21:21, 30 June 2019
Line 106:		Line 106:

	==Proposition 5.3.1 (Redundant Enumeration of e.c. Traders)==		==Proposition 5.3.1 (Redundant Enumeration of e.c. Traders)==

			I think the key point of this proof is that the <math>n</math> in <math>M(n)</math> is the same as the <math>n</math> in <math>f(n)</math>, so that the input to the trader computation (which says what day it is) controls how long the computation can run.

	==Definition/Proposition 5.3.2 (TradingFirm)==		==Definition/Proposition 5.3.2 (TradingFirm)==

IssaRice: /* Definition/Proposition 5.3.2 (TradingFirm) */

2019-06-30T02:02:24Z

Definition/Proposition 5.3.2 (TradingFirm)

← Older revision		Revision as of 02:02, 30 June 2019
Line 109:		Line 109:
	==Definition/Proposition 5.3.2 (TradingFirm)==		==Definition/Proposition 5.3.2 (TradingFirm)==

	Why do we want to blank out the traders by defining <math>S^k_n</math>? shouldn't giving the later traders less weight be sufficient? This assumption is used to make the sum <math>\sum_{k \in \mathbb N^+}</math> into <math>\sum_{k \leq n}</math>.		Why do we want to blank out the traders by defining <math>S^k_n</math>? shouldn't giving the later traders less weight be sufficient? This assumption is used to make the sum <math>\sum_{k \in \mathbb N^+}</math> into <math>\sum_{k \leq n}</math>. In other words, on any day we are only dealing with a finite number of traders.

	==Lemma 5.3.3 (Trading Firm Dominance)==		==Lemma 5.3.3 (Trading Firm Dominance)==

IssaRice: /* Definition/Proposition 5.3.2 (TradingFirm) */

2019-06-30T01:54:25Z

Definition/Proposition 5.3.2 (TradingFirm)

← Older revision		Revision as of 01:54, 30 June 2019
Line 109:		Line 109:
	==Definition/Proposition 5.3.2 (TradingFirm)==		==Definition/Proposition 5.3.2 (TradingFirm)==

	Why do we want to blank out the traders by defining <math>S^k_n</math>? shouldn't giving the later traders less weight be sufficient?		Why do we want to blank out the traders by defining <math>S^k_n</math>? shouldn't giving the later traders less weight be sufficient? This assumption is used to make the sum <math>\sum_{k \in \mathbb N^+}</math> into <math>\sum_{k \leq n}</math>.

	==Lemma 5.3.3 (Trading Firm Dominance)==		==Lemma 5.3.3 (Trading Firm Dominance)==