Oracle Induction Proofs

No­ta­tion:

and are the sets of all bit­strings of length and the set of all finite bit­strings, re­spec­tively. Ele­ments of these sets are de­noted by . The length pre­fix of is de­noted by .

is the set of all satis­fi­able booleans with all vari­ables hav­ing an in­dex , and is the set of all satis­fi­able booleans. Similarly, and are the set of all booleans with all vari­ables hav­ing an in­dex , and the set of all booleans. Ele­ments of these sets are de­noted by . is also a boolean. Bit­strings may be in­ter­preted as boolean con­straints say­ing that the pre­fix of the bit­string must equal .

is a func­tion that is time-con­structible, mono­ton­i­cally in­creas­ing, and , which gives the run­time bound for traders.

is some func­tion up­per-bounded by that is time-con­structible, mono­ton­i­cally in­creas­ing, and . It gives the most dis­tant bit the or­a­cle in­duc­tor thins about on turn .

is the func­tion given by , giv­ing the num­ber of iter­a­tions of bi­nary-search de­ployed on turn .

is the func­tion given by . It gives the pro­por­tion of the in­duc­tor dis­tri­bu­tion that is made up by the uniform dis­tri­bu­tion.

The op­er­a­tions and take unit time to ex­e­cute in our model of com­pu­ta­tion, though the in­put still has to be writ­ten down in the usual amount of time.

Given some ar­bi­trary dis­tri­bu­tion over , and a , is the prob­a­bil­ity mass as­signed to bit­strings that fulfill . Given a , is the con­di­tional dis­tri­bu­tion given by . is the dis­tri­bu­tion in­duced by . There is an im­plicit de­pen­dence on which will be sup­pressed in the no­ta­tion.

Lemma 1 (n-Lemma): Let . Given some dis­tri­bu­tion over for which , then

.

To be­gin with, if is in­com­pat­i­ble with , by the con­struc­tion of , and the in­equal­ity is triv­ial. So we can con­sider the case where is com­pat­i­ble with . Given as a strict pre­fix of , ab­bre­vi­ate as .

Be­cause we’re us­ing a bi­nary-search depth of on each bit, and tak­ing the av­er­age of the in­ter­val, the prob­a­bil­ities are ap­prox­i­mated to within .

Tak­ing the mi­dle three terms and sub­tract­ing from all of them, which flips the sign of the in­equal­ity, and rewrit­ing as and rewrit­ing as , we get

Now, be­cause , us­ing the pre­vi­ous in­equal­ities, we can establish

For an in­di­vi­d­ual term in the product of the lower/​up­per bound ( and will be used, the up­per sign is used for the lower bound, the lower sign is used for the up­per bound, and will be abused to mean for the lower bound and for the up­per bound), we can get the fol­low­ing equal­ity.

Be­cause, by as­sump­tion, all bit­strings with nonzero prob­a­bil­ity and there­fore pre­fixes of them have prob­a­bil­ity bounded be­low by , we get

and

which can be ap­plied to conclude

There­fore, since we have lower-bounded or up­per-bounded ev­ery term in the product, and , we can show

The n-Lemma is thus proven.

Lemma 2: The dis­tri­bu­tion in­duced by has the prob­a­bil­ity of all bit­strings bounded above by .

Iden­tify with . Iden­tify with . Iden­tify with .

Be­cause , . Due to of the dis­tri­bu­tion be­ing com­posed of the uniform dis­tri­bu­tion, the prob­a­bil­ity of all is bounded be­low by

And Lemma 2 is proved.

From here on, we will fre­quently be go­ing from the ap­prox­i­ma­tion of a con­di­tional dis­tri­bu­tion to a con­di­tional dis­tri­bu­tion via the n-Lemma and Lemma 2, so let , and , and . and will be used to re­fer to the prob­a­bil­ity dis­tri­bu­tion and con­di­tional prob­a­bil­ity dis­tri­bu­tion over bit­strings that pro­duces, and and re­fer to the ap­prox­i­ma­tion of that prob­a­bil­ity dis­tri­bu­tion with .

Lemma 3: The as­sessed value at time in world of a trader with a run­time and or­a­cle-call filter at­tached is lower-bounded by

and up­per-bounded by

.

To be­gin, the as­sessed value at time in world of a trader by is .

has rounds of bi­nary search run on it, which yields an in­ter­val with a width of , and an up­per-bound es­ti­mate is taken, so . Similarly, the net value of a trade has a lower-bound es­ti­mate run on it, so

Fur­ther, by the n-Lemma and Lemma 2 (prob­a­bil­ity of x is ei­ther or over ), we can re­place by or re­spec­tively, which are then up­per and lower-bounded by and , which, be­cause the frac­tion doesn’t de­pend on , can be pul­led out of the sum, yield­ing the stated bounds.

In the next the­o­rem, we will be ab­bre­vi­at­ing as and ab­bre­vi­at­ing as , so the value of a trader at timestep in world against the se­quence of dis­tri­bu­tions is .

The­o­rem 1: If a trader ex­ploits the mar­ket, there is a bud­geted ver­sion that trader that ex­ploits the mar­ket.

As be­fore, the net value of a trader at timestep in world against the se­quence of dis­tri­bu­tions is . Be­cause the trader ex­ploits the mar­ket, for all and all plau­si­ble at , the net value for some in­te­ger con­stant , we get that for all t and all plau­si­ble at , . Call this quan­tity 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

Ab­bre­vi­ate as , and ab­bre­vi­ate as . Us­ing Lemma 3, the worst-case as­sessed gain of the trader is . Fo­cus­ing on an in­di­vi­d­ual day, and us­ing the fact that , and it’s a good day so , we get

Sub­sti­tut­ing this into the sum and pul­ling out terms that don’t de­pend on , we get

The last step was done by and ig­nor­ing some pos­i­tive terms. Now we will bound .

Mul­ti­ply­ing both sides by , which flips the up­per and lower bounds of in­te­gra­tion, we get

By putting both sides in an ex­po­nent, this in­equal­ity is equiv­a­lent to . Mul­ti­ply­ing both sides by and us­ing the defi­ni­tion of , we get .

Us­ing the pre­vi­ous in­equal­ities, we get that the worst-case as­sessed gain of the trader is greater than . There­fore, the worst-case as­sessed value of the trader is greater than , so when the bud­get is , will at worst eval­u­ate the value as , so it will never re­turn and in­terfere with the trade, so the bud­geted trader makes the same trades as the origi­nal trader and ex­ploits the mar­ket.

Lemma 4: The worst-case value of a trader with a bud­get of is .

As­sume the value of a trader equals for some on some turn . Then the gain of the trader, is . By Lemma 3, the as­sessed gain is less than

Now we will bound the last term.

By putting both sides in an ex­po­nent, we get the equiv­a­lent in­equal­ity and mul­ti­ply­ing both sides by yields , so the as­sessed gain is less than and the as­sessed value is .

Then, if the trader has a bud­get of (an in­te­ger), the worst-case sce­nario is that on some turn t it has a true value of and it is as­sessed to have a value of (max­i­mum pos­si­ble), so it barely passes the bud­get­ing filter, and then loses dol­lar on the next turn, get­ting a fi­nal value of (af­ter which it only out­puts which has a value of ).

The­o­rem 2: If a bud­geted trader ex­ploits the mar­ket, the su­per­trader ex­ploits the mar­ket.

is the prob­a­bil­ity of the su­per­trader draw­ing a bit­string which en­codes the al­gorithm and bud­get on timestep . is the prob­a­bil­ity of with a run­time and or­a­cle call filter and a bud­get filter of out­putting the boolean . is the prob­a­bil­ity of a ran­domly se­lected in­finite string en­cod­ing , and . For suffi­ciently large , and .

A use­ful thing to note is that, be­cause the bit­string that is cho­sen is of length , and it is only run on the UTM for steps, its be­hav­ior is iden­ti­cal to that of all al­gorithms that are en­coded by a bit­string that has as a pre­fix. There­fore, even though the prob­a­bil­ity of some be­ing drawn may be on a timestep, there is some amount of prob­a­bil­ity mass in the su­per­trader that might as well have come from , in the sense that its be­hav­ior is in­dis­t­in­guish­able from af­ter the run­time and or­a­cle call filter is ap­plied.

Similarly, be­cause the max­i­mum se­lectable bud­get is , and a trader can lose at most dol­lar each turn, for all and pos­i­tive in­te­gers , has the same ex­act be­hav­ior as , so we can pre­tend we are deal­ing with the full dis­tri­bu­tion over all bud­gets.

There­fore, for all , the dis­tri­bu­tion over satis­fi­able booleans given by equals the dis­tri­bu­tion over satis­fi­able booleans given by , and be­cause of this,

Also, let be the value of ’s trade on day ac­cord­ing to some fixed . is the value that ac­cu­mu­lates over all days up to .

The value of the su­per­trader at time ac­cord­ing to a world that is plau­si­ble at that time is

Now the worst-case value of is by Lemma 4, so we get that the value of the su­per­trader is bounded be­low by

.

Also, if our ex­ploit­ing trader and the bud­get which en­sures its trade is never al­tered are and , we get that the value of the su­per­trader equals

Be­cause is un­bounded above for ap­pro­pri­ate choices of and by as­sump­tion, it con­tinues to be un­bounded above when mul­ti­plied by and has sub­tracted from it. There­fore, the su­per­trader has plau­si­ble value un­bounded above as well.

The­o­rem 3: The su­per­trader doesn’t ex­ploit .

Now, we will show that the max­i­mum value that the su­per­trader can pos­si­bly get in wor­lds plau­si­ble at some turn is up­per-bounded by , so the value of the su­per­trader is up­per-bounded by .

To be­gin with, the prob­a­bil­ity mass the su­per­trader places on world at timestep is . This sum can be rewrit­ten as , and for brevity, from here on, we will ab­bre­vi­ate as . With this ab­bre­vi­a­tion, we can ex­press the value of the su­per­trader’s trade on day and world as . Note that the nu­mer­a­tor of the frac­tion is the su­per­trader, which uses the true con­di­tional dis­tri­bu­tion, while the de­nom­i­na­tor is what the ac­tual dis­tri­bu­tion is com­posed of, a small frag­ment of a uniform dis­tri­bu­tion with the rest is com­posed of a mix­ture of ap­prox­i­ma­tions to the ap­pro­pri­ate con­di­tional dis­tri­bu­tion. To be­gin the bound­ing ar­gu­ment, ap­ply the n-Lemma to yield

Also,

By putting both sides in an ex­po­nent, this in­equal­ity is equiv­a­lent to , so , so the value of the su­per­trader gained on any given day is bounded above by , so the to­tal value of the su­per­trader at any time is bounded above by .

Run­time Anal­y­sis:

The strength of the bounded re­flec­tive or­a­cle needed is con­trol­led by the longest run­time of the al­gorithms that the or­a­cle is queried about. The rele­vant or­a­cle calls are the in­vo­ca­tions of SAT in , in the bi­nary search por­tion of , , the SAT call in , the calls that the trader may make, and the or­a­cle calls in the bi­nary search por­tion of .

To be­gin with, the run­time of is the time needed to flip enough coins to get to the most dis­tant vari­able in­dex in (call it ), and then the time to run the boolean cir­cuit on the padded it­self, which would be be , to check each bit of the padded and do a pass over the boolean to sub­sti­tute or for that vari­able, and then eval­u­at­ing the re­sult­ing boolean with vari­ables filled in.

Similarly, the run­time of SAT is the time to write down and the bi­nary string cor­re­spond­ing to the prob­a­bil­ity bound, which has a length of ap­prox­i­mately , for a run­time of .

Now we can look at the run­time of . It is always called with and there are that many iter­a­tions of writ­ing down (which, ev­ery­where it’s in­voked, takes less than bits) and the av­er­age of the two bounds, which, by a suit­able bi­nary en­cod­ing, takes at most about bits, so we get a run­time of about , which is .

As for the run­time of , the length of the boolean at the start is at most (the first part is be­cause was re­turned by an al­gorithm that ran for at most steps, and the sec­ond part is the bound on the length of ). A boolean of this length is writ­ten down 3 times, and SAT is in­voked twice, and is run twice, for a run­time of . Ad­ding in the time to write in/​read and from the in­put just adds an­other term which doesn’t af­fect run­time that much.

Now for . There are at most iter­a­tions of , and we already ac­counted for the time to write the in­put to , so the run­time is .

reads the in­put, which takes time, em­u­lates steps of a tur­ing ma­chine, which takes time, clips the in­put which takes time (the lat­ter is an up­per bound on the time to com­pute be­cause is time-con­structible), calls SAT on a boolean of length at most with a max­i­mum in­dex of , and writes the boolean, for a run­time of .

reads the in­put and writes parts of it into the query, which takes time, writes down the prob­a­bil­ity bound in time, and runs , for a run­time of .

ei­ther writes down in time and gen­er­ates a string in time, or com­putes , , and in time, gen­er­ates the trader and bud­get string in time, and in­vokes and for a run­time of .

Now we can ad­dress the run­time of all the al­gorithms fed into an or­a­cle query but one. The SAT calls in ask about with a run­time of , which is suffi­ciently low. The queries about in have run­ning in time (for the eval­u­a­tion) plus time (to calcu­late ), so the run­time is which is suffi­ciently low. The SAT call in asks about with a run­time of which is suffi­ciently low. The SAT call the trader makes about isn’t about a longer-run­ning al­gorithm than the al­gorithm in­voked in , so we’re good there as well. Fi­nally, the or­a­cle queries in the bi­nary search por­tion of take time (for the eval­u­a­tion), plus the run­time of and the run­time of (in the nu­mer­a­tor) or the run­time of (in the de­nom­i­na­tor), for a run­time of in both cases, which is suffi­ciently low.

This just leaves es­tab­lish­ing the run­time of to en­sure that the or­a­cle is strong enough for our needs.

Gen­er­at­ing takes time. Gen­er­at­ing the world takes time. Run­ning the de­duc­tive pro­cess takes time, and so does writ­ing down the re­sult­ing boolean, and the max­i­mum in­dex is so the SAT in­vo­ca­tion takes time as well, for a run­time so far of . That leaves the sum (com­put­ing the < isn’t harder than com­put­ing the sum in the first place). We are car­ry­ing out at most frac­tion-ad­di­tions. Each frac­tion-ad­di­tion in­volves three mul­ti­pli­ca­tions, one ad­di­tion, and two iter­a­tions of bi­nary search. The length of the num­bers is , but with each mul­ti­pli­ca­tion, they get longer by , so the max­i­mum length of the num­bers is . Us­ing the stan­dard in­effi­cient mul­ti­pli­ca­tion al­gorithm for run­time per mul­ti­pli­ca­tion, and with ad­di­tion be­ing faster than mul­ti­pli­ca­tion, we get for the whole sum, to get a run­time of , which again is suffi­ciently low to per­mit or­a­cle calls.

Thus, an or­a­cle strength of suffices to make all or­a­cle calls di­rected to al­gorithms with per­mis­si­bly low run­time.