Oracle Induction Proofs

post by Diffractor · 2018-11-28T08:12:38.306Z · score: 6 (2 votes) · LW · GW · None comments


    Runtime Analysis:
No comments


and are the sets of all bitstrings of length and the set of all finite bitstrings, respectively. Elements of these sets are denoted by . The length prefix of is denoted by .

is the set of all satisfiable booleans with all variables having an index , and is the set of all satisfiable booleans. Similarly, and are the set of all booleans with all variables having an index , and the set of all booleans. Elements of these sets are denoted by . is also a boolean. Bitstrings may be interpreted as boolean constraints saying that the prefix of the bitstring must equal .

is a function that is time-constructible, monotonically increasing, and , which gives the runtime bound for traders.

is some function upper-bounded by that is time-constructible, monotonically increasing, and . It gives the most distant bit the oracle inductor thins about on turn .

is the function given by , giving the number of iterations of binary-search deployed on turn .

is the function given by . It gives the proportion of the inductor distribution that is made up by the uniform distribution.

The operations and take unit time to execute in our model of computation, though the input still has to be written down in the usual amount of time.

Given some arbitrary distribution over , and a , is the probability mass assigned to bitstrings that fulfill . Given a , is the conditional distribution given by . is the distribution induced by . There is an implicit dependence on which will be suppressed in the notation.

Lemma 1 (n-Lemma): Let . Given some distribution over for which , then


To begin with, if is incompatible with , by the construction of , and the inequality is trivial. So we can consider the case where is compatible with . Given as a strict prefix of , abbreviate as .

Because we're using a binary-search depth of on each bit, and taking the average of the interval, the probabilities are approximated to within .

Taking the midle three terms and subtracting from all of them, which flips the sign of the inequality, and rewriting as and rewriting as , we get

Now, because , using the previous inequalities, we can establish

For an individual term in the product of the lower/upper bound ( and will be used, the upper sign is used for the lower bound, the lower sign is used for the upper bound, and will be abused to mean for the lower bound and for the upper bound), we can get the following equality.

Because, by assumption, all bitstrings with nonzero probability and therefore prefixes of them have probability bounded below by , we get


which can be applied to conclude

Therefore, since we have lower-bounded or upper-bounded every term in the product, and , we can show

The n-Lemma is thus proven.

Lemma 2: The distribution induced by has the probability of all bitstrings bounded above by .

Identify with . Identify with . Identify with .

Because , . Due to of the distribution being composed of the uniform distribution, the probability of all is bounded below by

And Lemma 2 is proved.

From here on, we will frequently be going from the approximation of a conditional distribution to a conditional distribution via the n-Lemma and Lemma 2, so let , and , and . and will be used to refer to the probability distribution and conditional probability distribution over bitstrings that produces, and and refer to the approximation of that probability distribution with .

Lemma 3: The assessed value at time in world of a trader with a runtime and oracle-call filter attached is lower-bounded by

and upper-bounded by


To begin, the assessed value at time in world of a trader by is .

has rounds of binary search run on it, which yields an interval with a width of , and an upper-bound estimate is taken, so . Similarly, the net value of a trade has a lower-bound estimate run on it, so

Further, by the n-Lemma and Lemma 2 (probability of x is either or over ), we can replace by or respectively, which are then upper and lower-bounded by and , which, because the fraction doesn't depend on , can be pulled out of the sum, yielding the stated bounds.

In the next theorem, we will be abbreviating as and abbreviating as , so the value of a trader at timestep in world against the sequence of distributions is .

Theorem 1: If a trader exploits the market, there is a budgeted version that trader that exploits the market.

As before, the net value of a trader at timestep in world against the sequence of distributions is . Because the trader exploits the market, for all and all plausible at , the net value for some integer constant , we get that for all t and all plausible at , . Call this quantity the gain of the trader. Separate the sum into "good" days where , and "bad" days where this is false, and use Lemma 2 to get

Abbreviate as , and abbreviate as . Using Lemma 3, the worst-case assessed gain of the trader is . Focusing on an individual day, and using the fact that , and it's a good day so , we get

Substituting this into the sum and pulling out terms that don't depend on , we get

The last step was done by and ignoring some positive terms. Now we will bound .

Multiplying both sides by , which flips the upper and lower bounds of integration, we get

By putting both sides in an exponent, this inequality is equivalent to . Multiplying both sides by and using the definition of , we get .

Using the previous inequalities, we get that the worst-case assessed gain of the trader is greater than . Therefore, the worst-case assessed value of the trader is greater than , so when the budget is , will at worst evaluate the value as , so it will never return and interfere with the trade, so the budgeted trader makes the same trades as the original trader and exploits the market.

Lemma 4: The worst-case value of a trader with a budget of is .

Assume the value of a trader equals for some on some turn . Then the gain of the trader, is . By Lemma 3, the assessed gain is less than

Now we will bound the last term.

By putting both sides in an exponent, we get the equivalent inequality and multiplying both sides by yields , so the assessed gain is less than and the assessed value is .

Then, if the trader has a budget of (an integer), the worst-case scenario is that on some turn t it has a true value of and it is assessed to have a value of (maximum possible), so it barely passes the budgeting filter, and then loses dollar on the next turn, getting a final value of (after which it only outputs which has a value of ).

Theorem 2: If a budgeted trader exploits the market, the supertrader exploits the market.

is the probability of the supertrader drawing a bitstring which encodes the algorithm and budget on timestep . is the probability of with a runtime and oracle call filter and a budget filter of outputting the boolean . is the probability of a randomly selected infinite string encoding , and . For sufficiently large , and .

A useful thing to note is that, because the bitstring that is chosen is of length , and it is only run on the UTM for steps, its behavior is identical to that of all algorithms that are encoded by a bitstring that has as a prefix. Therefore, even though the probability of some being drawn may be on a timestep, there is some amount of probability mass in the supertrader that might as well have come from , in the sense that its behavior is indistinguishable from after the runtime and oracle call filter is applied.

Similarly, because the maximum selectable budget is , and a trader can lose at most dollar each turn, for all and positive integers , has the same exact behavior as , so we can pretend we are dealing with the full distribution over all budgets.

Therefore, for all , the distribution over satisfiable booleans given by equals the distribution over satisfiable booleans given by , and because of this,

Also, let be the value of 's trade on day according to some fixed . is the value that accumulates over all days up to .

The value of the supertrader at time according to a world that is plausible at that time is

Now the worst-case value of is by Lemma 4, so we get that the value of the supertrader is bounded below by


Also, if our exploiting trader and the budget which ensures its trade is never altered are and , we get that the value of the supertrader equals

Because is unbounded above for appropriate choices of and by assumption, it continues to be unbounded above when multiplied by and has subtracted from it. Therefore, the supertrader has plausible value unbounded above as well.

Theorem 3: The supertrader doesn't exploit .

Now, we will show that the maximum value that the supertrader can possibly get in worlds plausible at some turn is upper-bounded by , so the value of the supertrader is upper-bounded by .

To begin with, the probability mass the supertrader places on world at timestep is . This sum can be rewritten as , and for brevity, from here on, we will abbreviate as . With this abbreviation, we can express the value of the supertrader's trade on day and world as . Note that the numerator of the fraction is the supertrader, which uses the true conditional distribution, while the denominator is what the actual distribution is composed of, a small fragment of a uniform distribution with the rest is composed of a mixture of approximations to the appropriate conditional distribution. To begin the bounding argument, apply the n-Lemma to yield


By putting both sides in an exponent, this inequality is equivalent to , so , so the value of the supertrader gained on any given day is bounded above by , so the total value of the supertrader at any time is bounded above by .

Runtime Analysis:

The strength of the bounded reflective oracle needed is controlled by the longest runtime of the algorithms that the oracle is queried about. The relevant oracle calls are the invocations of SAT in , in the binary search portion of , , the SAT call in , the calls that the trader may make, and the oracle calls in the binary search portion of .

To begin with, the runtime of is the time needed to flip enough coins to get to the most distant variable index in (call it ), and then the time to run the boolean circuit on the padded itself, which would be be , to check each bit of the padded and do a pass over the boolean to substitute or for that variable, and then evaluating the resulting boolean with variables filled in.

Similarly, the runtime of SAT is the time to write down and the binary string corresponding to the probability bound, which has a length of approximately , for a runtime of .

Now we can look at the runtime of . It is always called with and there are that many iterations of writing down (which, everywhere it's invoked, takes less than bits) and the average of the two bounds, which, by a suitable binary encoding, takes at most about bits, so we get a runtime of about , which is .

As for the runtime of , the length of the boolean at the start is at most (the first part is because was returned by an algorithm that ran for at most steps, and the second part is the bound on the length of ). A boolean of this length is written down 3 times, and SAT is invoked twice, and is run twice, for a runtime of . Adding in the time to write in/read and from the input just adds another term which doesn't affect runtime that much.

Now for . There are at most iterations of , and we already accounted for the time to write the input to , so the runtime is .

reads the input, which takes time, emulates steps of a turing machine, which takes time, clips the input which takes time (the latter is an upper bound on the time to compute because is time-constructible), calls SAT on a boolean of length at most with a maximum index of , and writes the boolean, for a runtime of .

reads the input and writes parts of it into the query, which takes time, writes down the probability bound in time, and runs , for a runtime of .

either writes down in time and generates a string in time, or computes , , and in time, generates the trader and budget string in time, and invokes and for a runtime of .

Now we can address the runtime of all the algorithms fed into an oracle query but one. The SAT calls in ask about with a runtime of , which is sufficiently low. The queries about in have running in time (for the evaluation) plus time (to calculate ), so the runtime is which is sufficiently low. The SAT call in asks about with a runtime of which is sufficiently low. The SAT call the trader makes about isn't about a longer-running algorithm than the algorithm invoked in , so we're good there as well. Finally, the oracle queries in the binary search portion of take time (for the evaluation), plus the runtime of and the runtime of (in the numerator) or the runtime of (in the denominator), for a runtime of in both cases, which is sufficiently low.

This just leaves establishing the runtime of to ensure that the oracle is strong enough for our needs.

Generating takes time. Generating the world takes time. Running the deductive process takes time, and so does writing down the resulting boolean, and the maximum index is so the SAT invocation takes time as well, for a runtime so far of . That leaves the sum (computing the < isn't harder than computing the sum in the first place). We are carrying out at most fraction-additions. Each fraction-addition involves three multiplications, one addition, and two iterations of binary search. The length of the numbers is , but with each multiplication, they get longer by , so the maximum length of the numbers is . Using the standard inefficient multiplication algorithm for runtime per multiplication, and with addition being faster than multiplication, we get for the whole sum, to get a runtime of , which again is sufficiently low to permit oracle calls.

Thus, an oracle strength of suffices to make all oracle calls directed to algorithms with permissibly low runtime.

None comments

Comments sorted by top scores.