This grew out of an exchange with Jessica Taylor during MIRI’s recent visit to the FHI. Still getting my feel for the fixed point approach; let me know of any errors.

People at MIRI have recently proved you can use reflective oracles so that agents can use them to reason about other agents (including other agents with oracles) and themselves, and consistently reach Nash equilibriums. But can we do better than that?

To recap, a reflective oracle is a machine O such that:

• P(A()=1)>p implies O(A,p)=1

• P(A()=0)>1-p implies O(A,p)=0

This works even if A() includes a call to the oracle within its code. Now, all the algorithms used here will be clearly terminating, so we’ll have the other two implications as well (eg (P(A()=0)>p implies O(A,p)=0). And given any δ, we can, with order log(1/δ) questions, establish the probability of A() to within δ. Thus we will write O(A()==a)=p to mean that O(A()==a,(n-1)δ/2)=1 and O(A()==a,(n+1)δ/2)=0, where (n-1)δ/2 < p < (n+1)δ/2.

Note also that O can be used to output a probabilistic output (to within δ), so outputting specific mixed strategies is possible.

Speaking of Scott Aaronson, his latest post at Shtetl-Optimized seems worthy of some linky love.

Why do native speakers of the language you’re studying talk too fast for you to understand them?  Because otherwise, they could talk faster and still understand each other.

...

Again and again, I’ve undergone the humbling experience of first lamenting how badly something sucks, then only much later having the crucial insight that its not sucking wouldn’t have been a Nash equilibrium.  Clearly, then, I haven’t yet gotten good enough at Malthusianizing my daily life—have you?