János Kramár

• János KramárJun 18, 2015, 6:07 PM

  LW: 2 AF: 1

  AF

  in reply to: János Kramár’s comment on: Sta­tion­ary al­gorith­mic probability

  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 measure.

  It seems tempting (to me) to try to get a probability measure by modding out the output-permutations (that the post uses to show this isn’t possible for the full set of UTMs). To this end, consider the set of UTMs that have no output. (These will be unaffected by the output-permutations.) We can try to use the induced sub-digraph on these to build a probability measure $\mu$. The measure of each UTM should be a function of the rooted edge-labeled digraph $G_M$ rooted at that UTM.

  The most natural topology on rooted edge-labeled infinite digraphs is the one generated by the sets $\{G:G^{\prime }\text{is isomorphic to an induced rooted edge-labeled subgraph of G}\}$ where $G^{\prime }$ ranges over finite rooted edge-labeled digraphs—we could hope that $\mu$ is continuous according to this topology. Unfortunately, this can’t work: if $\mu \left(M\right)>0$ then ${\mu }^{-1}\left(\right(\frac{1}{2}\mu \left(M\right),\infty \left)\right)$ must be open, and so it must contain some finite intersection of the generating sets; however, every such intersection that’s nonempty (as this one is) contains infinitely many UTMs, so the total measure must be infinite as well.

• János KramárJun 12, 2015, 1:49 AM

  0 points

  AF

  on: A tractable, in­ter­pretable for­mu­la­tion of ap­prox­i­mate con­di­tion­ing for pair­wise-speci­fied prob­a­bil­ity dis­tri­bu­tions over truth values

  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 real or hyperreal approximation.

• János KramárJun 11, 2015, 5:31 PM

  LW: 1 AF: 1

  AF

  on: A tractable, in­ter­pretable for­mu­la­tion of ap­prox­i­mate con­di­tion­ing for pair­wise-speci­fied prob­a­bil­ity dis­tri­bu­tions over truth values

  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 to interpret that.

• János KramárJun 4, 2015, 4:31 PM

  LW: 3 AF: 2

  AF

  on: Sta­tion­ary al­gorith­mic probability

  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”.

A tractable, in­ter­pretable for­mu­la­tion of ap­prox­i­mate con­di­tion­ing for pair­wise-speci­fied prob­a­bil­ity dis­tri­bu­tions over truth values

• János KramárJun 2, 2015, 12:36 AM

  LW: 2 AF: 2

  AF

  on: No Good Log­i­cal Con­di­tional Probability

  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.

• János KramárMay 11, 2015, 2:35 AM

  0 points

  AF

  in reply to: orthonormal’s comment on: Mo­dal Bar­gain­ing Agents

  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.)

• János KramárMay 7, 2015, 2:04 AM

  LW: 2 AF: 1

  AF

  in reply to: orthonormal’s comment on: Mo­dal Bar­gain­ing Agents

  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 simple: player X can compute what it believes is the optimal-$xyz$ feasible-and-fair-according-to-everyone point $(x,y,z)$ (which is unique because these are all convex sets), and if PA proves the outcome will be fair-according-to-X, then output $x$; otherwise output 0.

• János KramárApr 29, 2015, 10:46 PM

  LW: 2 AF: 1

  AF

  in reply to: orthonormal’s comment on: Mo­dal Bar­gain­ing Agents

  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)$ is in the feasible set. The latter is immediately false, so this will fail.

  Next, X will try to prove in PA+2 that $y\le 2$ and that $(\frac{3}{2}\cdot 3,y)$ is in the feasible set. This too is immediately false.

  Next, X will try to prove in PA+3 that $y\le 2$ and that $(\frac{3}{3}\cdot 3,y)$ is feasible (in short, that $y=2$), and return 3 if so. This will fail to reach a cycle.

  Then the bargaining phase:

  Next, X will try to prove in PA+4 that $y\le 2$ and that $(3,y)$ is feasible, and return 3 if so. This will fail identically.

  Next, X will try to prove in PA+5 that $y\le 2$ and that $(2,y)$ is feasible, and return 2 if so. This will reach a Löbian circle, and X and Y will both return 2, which is what we want.

• János KramárApr 25, 2015, 9:53 PM

  0 points

  on: Mo­dal Bar­gain­ing Agents

  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 in this list that is achieved by a feasible point on X’s fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)

  for $i=i_0,\dots ,m-1$, let $(x_i,y_i)$ be the “fair” utility distribution that achieves area $A_i$; let $(x_m,y_m)=(0,0)$.

  let $y$ be Y’s output.

  # Speculative phase:

  $\text{else}$ if $PA+1$ proves $y\le y_{i_0}$ and $(\frac{m}{1}{x}_{i_0},y)$ is feasible, return $\frac{m}{1}{x}_{i_0}$.

  else if $PA+2$ proves $y\le y_{i_0}$ and $(\frac{m}{2}{x}_{i_0},y)$ is feasible, return $\frac{m}{2}{x}_{i_0}$.

  $\text{else}⋮$

  else if $PA+m$ proves $y\le y_{i_0}$ and $(\frac{m}{m}{x}_{i_0},y)$ is feasible, return $\frac{m}{m}{x}_{i_0}$.

  # Bargaining phase:

  else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0},y{)}_{+1}$ is feasible, return $x_{i_0}$.

  else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0+1},y)$ is feasible, return $x_{i_0+1}$.

  $\text{else}⋮$

  else if $PA+m+m-1$ proves $y\le y_{m-1}$ and $(x_{m-1},y)$ is feasible, return $x_{m-1}$.

  else return $x_{i_0}$.

  If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent’s fairness curve.

  Furthermore, if the intersection of the fairness curves is at a feasible point that produces rectangle area $\ge A_i$ for some $i$ and X and Y follow the protocol then on the $PA+m+i$ step, they will be able to agree on the coordinatewise min of their proposed feasible points with area $A_i$.

  If they’re both really generous and their fairness curves don’t intersect inside the feasible region, the given protocol will agree on approximately the highest feasible multiple of how much they thought they were fairly due, avoiding utility sacrifice.

• János KramárApr 25, 2015, 9:09 PM

  0 points

  AF

  on: Mo­dal Bar­gain­ing Agents

  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 in this list that is achieved by a feasible point on X’s fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)

  for $i=i_0,\dots ,m-1$, let $(x_i,y_i)$ be the “fair” utility distribution that achieves area $A_i$; let $(x_m,y_m)=(0,0)$.

  let $y$ be Y’s output.

  # Speculative phase:

  $\text{else}$ if $PA+1$ proves $y\le y_{i_0}$ and $(\frac{m}{1}{x}_{i_0},y)$ is feasible, return $\frac{m}{1}{x}_{i_0}$.

  else if $PA+2$ proves $y\le y_{i_0}$ and $(\frac{m}{2}{x}_{i_0},y)$ is feasible, return $\frac{m}{2}{x}_{i_0}$.

  $\text{else}⋮$

  else if $PA+m$ proves $y\le y_{i_0}$ and $(\frac{m}{m}{x}_{i_0},y)$ is feasible, return $\frac{m}{m}{x}_{i_0}$.

  # Bargaining phase:

  else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0},y{)}_{+1}$ is feasible, return $x_{i_0}$.

  else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0+1},y)$ is feasible, return $x_{i_0+1}$.

  $\text{else}⋮$

  else if $PA+m+m-1$ proves $y\le y_{m-1}$ and $(x_{m-1},y)$ is feasible, return $x_{m-1}$.

  else return $x_{i_0}$.

  If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent’s fairness curve.

  Furthermore, if the intersection of the fairness curves is at a feasible point that produces rectangle area $\ge A_i$ for some $i$ and X and Y follow the protocol then on the $PA+m+i$ step, they will be able to agree on the coordinatewise min of their proposed feasible points with area $A_i$.

  If they’re both really generous and their fairness curves don’t intersect inside the feasible region, the given protocol will agree on approximately the highest feasible multiple of how much they thought they were fairly due, avoiding utility sacrifice.

• János KramárApr 25, 2015, 12:57 AM

  LW: 2 AF: 1

  AF

  on: Mo­dal Bar­gain­ing Agents

  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 in this list that is achieved by a feasible point on X’s fairness curve. (We will assume the fairness curve is weakly convex and weakly increasing.)

  for $i=i_0,\dots ,m-1$, let $(x_i,y_i)$ be the “fair” utility distribution that achieves area $A_i$; let $(x_m,y_m)=(0,0)$.

  let $y$ be Y’s output.

  # Speculative phase:

  $\text{else}$ if $PA+1$ proves $y\le y_{i_0}$ and $(\frac{m}{1}{x}_{i_0},y)$ is feasible, return $\frac{m}{1}{x}_{i_0}$.

  else if $PA+2$ proves $y\le y_{i_0}$ and $(\frac{m}{2}{x}_{i_0},y)$ is feasible, return $\frac{m}{2}{x}_{i_0}$.

  $\text{else}⋮$

  else if $PA+m$ proves $y\le y_{i_0}$ and $(\frac{m}{m}{x}_{i_0},y)$ is feasible, return $\frac{m}{m}{x}_{i_0}$.

  # Bargaining phase:

  else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0},y{)}_{+1}$ is feasible, return $x_{i_0}$.

  else if $PA+m+i_0+1$ proves $y\le y_{i_0+1}$ and $(x_{i_0+1},y)$ is feasible, return $x_{i_0+1}$.

  $\text{else}⋮$

  else if $PA+m+m-1$ proves $y\le y_{m-1}$ and $(x_{m-1},y)$ is feasible, return $x_{m-1}$.

  else return $x_{i_0}$.

  If both agents follow protocol, the result is guaranteed to be feasible and to not be above either agent’s fairness curve.

  Furthermore, if the intersection of the fairness curves is at a feasible point that produces rectangle area $\ge A_i$ for some $i$ and X and Y follow the protocol then on the $PA+m+i$ step, they will be able to agree on the coordinatewise min of their proposed feasible points with area $A_i$.

  If they’re both really generous and their fairness curves don’t intersect inside the feasible region, the given protocol will agree on approximately the highest feasible multiple of how much they thought they were fairly due, avoiding utility sacrifice.