All of János Kramár's Comments + Replies

Ah, I think I can stymy $M$ with 2 nonconstant advisors. Namely, let $A_1\left(n\right)=\frac{1}{2}-\frac{1}{n+3}$ and $A_2\left(n\right)=\frac{1}{2}+\frac{1}{n+3}$. We (setting up an adversarial $E$) precommit to setting $E\left(n\right)=0$ if $p\left(n\right)\ge A_2\left(n\right)$ and $E\left(n\right)=1$ if $p\left(n\right)\le A_1\left(n\right)$; now we can assume that $M$ always chooses $p\left(n\right)\in \left[A_1\right(n),A_2(n\left)\right]$, since this is better for $M$.

Now define $b_i^{\prime }\left(j\right)=\left|A_i\right(j)+E(j)-1|-\left|p\right(j)+E(j)-1|$ and $b_i\left(n\right)={\sum }_{j<n}{b}_i^{\prime }\left(j\right)$. Note that if we also define ${\mathrm{bad}}_i\left(n\right)={\sum }_{j<n}(\log \left|A_i\right(j)+E(j)-1|-\log \left|p\right(j)+E(j)-1|)$ then ${\sum }_{j<n}\left|2b_i\right(j)-{\mathrm{bad}}_i(j\left)\right|\le {\sum }_{j<n}\left(2A_1\right(j)-1-\log (2A_1\left(j\right)\left)\right))={\sum }_{j<n}O\left({(\frac{1}{2}-A_1(j\left)\right)}^2\right)$ is bounded; therefore if we can force $b_1$

I don't yet know whether I can extend it to two nonconstant advisors, but I do know I can extend it to a countably infinite number of constant-prediction advisors. Let $(P_i{)}_{i=0,\dots }$ be an enumeration of their predictions that contains each one an infinite number of times. Then:

def M(p, E, P):
    prev, this, next = 0, 0, 1
    def bad(i):
        return sum(log(abs((E[k] + P[i] - 1) /
                           (E[k] + p[k] - 1)))
                   for k in xrange(prev))
    for k in xrange(this, next): p[k] = 0.5
    prev, this, next = this, next, floor(exp

def M(p, E):
    p1, p2 = 1./3, 2./3
    prev, this, next = 0, 0, 1

bad1 and bad2 compute log-badnesses of M relative to p1 and p2, on E[:prev]; the goal of M is to ensure neither one goes to $\infty$. prev, this, next are set in such a way that M is permitted access to this when computing p[this:next].

    def bad(advisor):
        return lambda:
            sum(log(abs((E[i] + advisor(i) - 1) /
                        (E[i] + p[i] - 1)))
                for i in xrange(prev))
    bad1, bad2 = bad(lambda i: p1), bad(lambda i: p2)
    for i in xrange(this, next)

These results are still a bit unsatisfying.

The first half constructs an invariant measure which is then shown to be unsatisfactory because UTMs can rank arbitrarily high while only being good at encoding variations of themselves. This is mostly the case because the chain is transient; if it was positive recurrent then the measure would be finite, and UTMs ranking high would have to be good at encoding (and being encoded by) the average UTM rather than just a select family of UTMs.

The second half looks at whether we can get better results (ie a probability

There is a lot more to say about the perspective that isn't relaxed to continuous random variables. In particular, the problem of finding the maximum entropy joint distribution that agrees with particular pairwise distributions is closely related to Markov Random Fields and the Ising model. (The relaxation to continuous random variables is a Gaussian Markov Random Field.) It is easily seen that this maximum entropy joint distribution must have the form $\log Pr(1_{{\phi }_1},\dots ,1_{{\phi }_n})={\sum }_{i<j}{\theta }_{ij}{1}_{{\phi }_i\wedge {\phi }_j}+{\sum }_i{\theta }_i{1}_{{\phi }_i}-\log Z$ where $\log Z$ is the normalizing constant, or partition funct

In order to understand what the measure $\mu$ that was constructed from $d$ will reward, here's the sort of machine that comes close to ${sup}_M\mu \left(M\right)=3$:

Let $M_0$ be an arbitrary UTM. Now consider the function $r\left(n\right)=n-2^{\lfloor \lg n\rfloor }$ (or, really, any function $r:N^{+}\to N^0$ with $r\left(n\right)<n$ that visits every nonnegative integer infinitely many times), and let $L=\{x\in \{0,1{\}}^{\ast }:|x|>2,x_{|x|-1}=x_{r(|x|-1)},x_{|x|-2}=x_{r(|x|-2)}\}$. (The indices here are zero-based.) Choose $x_0\in L$ such that $x_0$ has no proper prefix in $L$. Then, construct the UTM $M$ that does:

rep

Consider the function $a(M_1,M_2)=2^{-d(M_1,M_2)-d(M_2,M_1)}$ where $d(M_1,M_2)=min\left(|x|\right|x\in \{0,1{\}}^{\ast }:\forall y\in \{0,1{\}}^{\ast }:M_1\left(xy\right)=M_2\left(y\right)\text{unless neither of these halts})$. The reversible Markov chain with transition probabilities $p(M_1,M_2)=\frac{a(M_1,M_2)}{{\sum }_{M_2^{\prime }}a(M_1,M_2^{\prime })}$ has a bounded positive invariant measure $\mu \left(M\right)={\sum }_{M^{\prime }}a(M,M^{\prime })$. Of course, as the post showed, the total measure is infinite. Also, because the chain is reversible and transient, the invariant measure is far from unique - indeed, for any machine $M_0$, the measure $\mu \left(M\right)=p^{\left(0\right)}(M,M_0)+2{\sum }_{n=1}^{\infty }{p}^{\left(n\right)}(M,M_0)$ will be a bounded positive invariant meas

Actually, on further thought, I think the best thing to use here is a log-bilinear distribution over the space of truth-assignments. For these, it is easy to efficiently compute exact normalizing constants, conditional distributions, marginal distributions, and KL divergences; there is no impedance mismatch. KL divergence minimization here is still a convex minimization (in the natural parametrization of the exponential family).

The only shortcoming is that 0 is not a probability, so it won't let you eg say that $Pr({\phi }_1\to {\phi }_2)=1$; but this can be remedied using a

An easy way to get rid of the probabilities-outside-[0,1] problem in the continuous relaxation is to constrain the "conditional"/updated distribution to have $\mathrm{Var}\left(1_{{\phi }_i}\right|\dots )\le E\left(1_{{\phi }_i}\right|\dots )(1-E\left(1_{{\phi }_i}\right|\dots ))$ (which is a convex constraint; it's equivalent to $\mathrm{Var}\left(1_{{\phi }_i}\right|\dots )+{(E\left(1_{{\phi }_i}\right|\dots )-\frac{1}{2})}^2$), and then minimize KL-divergence accordingly.

The two obvious flaws are that the result of updating becomes ordering-dependent (though this may not be a problem in practice), and that the updated distribution will sometimes have $\mathrm{Var}\left(1_{{\phi }_i}\right|\dots )<E\left(1_{{\phi }_i}\right|\dots )(1-E\left(1_{{\phi }_i}\right|\dots ))$, and it's not clear how

It may still be possible to get a unique (up to scaling) invariant measure (with infinite sum) over the UTMs by invoking something like the Krein-Rutman theorem and applying it to the transition operator. I haven't yet verified that all the conditions hold.

This measure would then be an encoding-invariant way to compare UTMs' "intrinsic complexity" in the sense of "number of bits needed to simulate".

This is interesting! I would dispute, though, that a good logical conditional probability must be able to condition on arbitrary, likely-non-r.e. sets of sentences.

What's the harm in requiring prior coordination, considering there's already a prior agreement to follow a particular protocol involving $A_i$s? (And something earlier on in the context about a shared source of randomness to ensure convexity of the feasible set.)

If the fairness constraints are all pairwise (ie each player has fairness curves for each opponent), then the scheme generalizes directly. Slightly more generally, if each player's fairness set is weakly convex and closed under componentwise max, the scheme still generalizes directly (in effect the componentwise max creates a fairness curve which can be intersected with the $xyz=A_i$ surfaces to get the $(x_i,y_i,z_i)$ points.

In order to generalize fully, the agents should each precommunicate their fairness sets. In fact, after doing this, the algorithm is very si

You did miss something: namely from PA+2 X wants to show feasibility of $(\frac{m}{2}{x}_{i_0},y)$, not $(\frac{m}{2},y)$. In your example, $x_{i_0}=3$, so the Löbian circle you describe will fail.

I'll walk through what will happen in the example.

The $A_i$ are just areas (ie $x_i{y}_i$), not rectangles. In this example, $A_1=6$ is enough to contain $(2,3)$ and $(3,2)$. For conciseness let's have $A_1=6$, $A_2=4$, and $m=3$ (so $A_3=0$).

Both X and Y have $i_0=1$. According to X, $(x_1,y_1)=(3,2)$, $(x_2,y_2)=(2,2)$, and $(x_3,y_3)=(0,0)$.

First the speculative phase will happen:

X will try to prove in PA+1 that $y\le 2$ and that $(\frac{3}{1}\cdot 3,y)$

How about a gridless scheme like:

The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.

Now discretize the possible "rectangle areas": let them be $A_1>...>A_m=0$. (This requires a way to agree on that, but this seems easier than agreeing on grid points; the finer the better, basically. Perhaps the most obvious way to do it is to have these be evenly spaced from $A_m=0$ to $A_1$; then only $A_1$ and $m$ need to be agreed upon.)

X will do the following:

let $A_{i_0}$ be the first area

How about a gridless scheme like:

The agents agree that they will each output how much utility they will get, and if they fail to choose a feasible point they both get 0.

Now discretize the possible "rectangle areas": let them be $A_1>...>A_m=0$. (This requires a way to agree on that, but this seems easier than agreeing on grid points; the finer the better, basically. Perhaps the most obvious way to do it is to have these be evenly spaced from $A_m=0$ to $A_1$; then only $A_1$ and $m$ need to be agreed upon.)

X will do the following:

let $A_{i_0}$ be the first area