János Kramár(János Kramár)

• János Kramár 16 Dec 2015 21:27 UTC

  LW: 5 AF: 4

  AF

  on: Con­cise Open Prob­lem in Log­i­cal Uncertainty

  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): p[i] = 0.5
      prev, this, next = this, next, floor(exp(next - 1)) + 1
  
      while True:
          for i in xrange(this, next): p[i] = p1
          prev, this, next = this, next, floor(exp(next - 1)) + 1
  

  bad1() is now be up to date through E[:this], not just E[:prev]

          bound = 2 * bad1()
          while bad1() > 0:
              # won't let bad1() surpass bound
              eps = (bound - bad1()) / 2 / (1 - p1) / (next - this)
  

  This is just for early iterations; in the limit, eps should be just enough for bad1 to go halfway to bound:

              while eps >= 1 - p1 or
                bound <= bad1() + (next - this) *
                log((1 - p1) / (1 - p1 - eps)):
                  eps /= 2
              for i in xrange(this, next): p[i] = p1 + eps
              prev, this, next = this, next, floor(exp(next - 1)) + 1
  
              for i in xrange(this, next): p[i] = p1
              # this is where the p1 + eps affects bad1()
              prev, this, next = this, next, floor(exp(next - 1)) + 1
  

  Now every iteration (after the first few) where $\mathrm{mean}\left(E[prev:this]\right)\le \frac{2}{5}$ will decrease bad2() by roughly at least $(this-prev)\left(\log \right(1-p1)-\log (1-p2)+\frac{2}{5}(\log \left(p1\right)-\log \left(p2\right)-\log (1-p1)+\log (1-p2)\left)\right)=(this-prev)\frac{1}{5}\log \left(2\right)\gg prev$, which is large enough to turn bad2() negative. Therefore, if M is bad for E, there can be only finitely many such iterations until the loop exits. However, every iteration where $\mathrm{mean}\left(E[prev:this]\right)\ge \frac{2}{5}$ will cause bound - bad1() to grow exponentially (by a factor of $\frac{11}{10}=1+\frac{1}{2}(-1+\frac{2}{5}\frac{1}{p1})$), so the loop will terminate.

  Now we’ll perform the same procedure for bad2():

          for i in xrange(this, next): p[i] = p2
          prev, this, next = this, next, floor(exp(next - 1)) + 1
  
          bound = 2 * bad2()
          while bad2() > 0:
              # won't let bad2() surpass bound
              eps = (bound - bad2()) / 2 / p2 / (next - this)
              while eps >= p2 or
                bound <= bad2() + (next - this) *
                log( p2 / (p2 - eps)):
                  eps /= 2
              for i in xrange(this, next): p[i] = p2 - eps
              prev, this, next = this, next, floor(exp(next - 1)) + 1
  
              for i in xrange(this, next): p[i] = p2
              # this is where the p2 - eps affects bad2()
              prev, this, next = this, next, floor(exp(next - 1)) + 1
  

  For the same reasons as the previous loop, this loop either stops with bad2() < 0 or runs forever with bad2() bounded and bad1 repeatedly falling back below 0.

  Therefore, this algorithm either gets trapped in one of the inner while loops (and succeeds) or turns bad1() and bad2() negative, each an infinite number of times, and therefore succeeds.

• János Kramár 5 Mar 2018 22:13 UTC

  3 points

  in reply to: Raemon’s comment on: On Defense Mechanisms

  Seems also like the “playing dead” behaviour. If you’re under attack and aren’t going to summon/​indicate allies (via sadness) or enforce your boundary yourself (via anger) or appease the attacker (via submission), another option is to give up on active response and hope that if you play dead just right, they’ll lose interest for some reason. Many attackers’ goals are better served by a responsive opponent; and attacking someone dead is both potentially unhealthy and no fun.

• János Kramár 4 Jun 2015 16:31 UTC

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

• János Kramár 21 Jun 2015 22:56 UTC

  LW: 2 AF: 1

  AF

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

  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 measure) by restricting our attention to output-free “UTMs” (though I misspoke; these are not actually UTMs but rather universal semidecidable languages (we can call them USDLs)). It concludes that we can’t if the measure will be continuous on the given digraph—however, this is an awkward notion of continuity: a low-complexity USDL whose behavior is tweaked very slightly but in a complex way may be very close in the given topology, but should have measure much lower than the starting USDL. So I consider this question unanswered.

• János Kramár 20 Jun 2015 16:34 UTC

  LW: 2 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

  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 function. This is an appealing distribution to use, and easy to do conditioning on and to add new variables to. Computing relative entropy reduces to finding bivariate marginals and to computing $Z$, and computing marginals reduces to computing $Z$, which is intractable in general[^istrail], though easy if the Markov graph (ie the graph with edges $ij$ for ${\theta }_{i,j}\ne 0$) is a forest.

  There have been many approaches to this problem (Wainwright and Jordan[^wainwright] is a good survey), but the main ways to extend the applicability from forests have been:

  • decompose components of the graph as “junction trees”, ie trees whose nodes are overlapping clusters of nodes from the original graph; this permits exact computation with cost exponential in the cluster-sizes, ie in the treewidth[^pearl]

  • make use of clever combinatorial work coming out of statistical mechanics to do exact computation on “outerplanar” graphs, or on general graphs with cost exponential in the (outer-)graph genus[^schraudolph]

  • find nodes such that conditioning on those nodes greatly simplifies the graph (eg makes it singly connected), and sum over their possible values explicitly (this has cost exponential in the number of nodes being conditioned on)

  A newer class of models, called sum-product networks[^poon], generalizes these and other models by writing the total joint probability as a positive polynomial $1={\sum }_{x_1,\dots ,x_n=0}^{1}Pr(1_{{\phi }_1}=x_1,\dots ,1_{{\phi }_n}=x_n)1_{{\phi }_1}^{x_1}{1}_{{\overline{\phi }}_1}^{1-x_1}\dots 1_{{\phi }_n}^{x_n}{1}_{{\overline{\phi }}_n}^{1-x_n}$ in the variables $1_{{\phi }_1},1_{{\overline{\phi }}_1},\dots ,1_{{\phi }_n},1_{{\overline{\phi }}_n}$ and requiring only that this polynomial be simplifiable to an expression requiring a tractable number of additions and multiplications to evaluate. This allows easy computation of marginals, conditionals, and KL divergence, though it will likely be necessary to do some approximate simplification every so often (otherwise the complexity may accumulate, even with a fixed maximum number of sentences being considered at a time).

  However, if we want to stay close to the context of the Non-Omniscience paper, we can do approximate calculations of the partition function on the complete graph—in particular, the Bethe partition function[^weller] has been widely used in practice, and while it’s not logconvex like $Z$ is, it’s often a better approximation to the partition function than well-known convex approximations such as TRW.

  [^istrail]: Istrail, Sorin. “Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intractability for the partition function of the Ising model across non-planar surfaces.” In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 87-96. ACM, 2000.

  [^weller]: Weller, Adrian. “Bethe and Related Pairwise Entropy Approximations.”

  [^pearl]: Pearl, Judea. “Probabilistic reasoning in intelligent systems: Networks of plausible reasoning.” (1988).

  [^schraudolph]: Schraudolph, Nicol N., and Dmitry Kamenetsky. “Efficient Exact Inference in Planar Ising Models.” arXiv preprint arXiv:0810.4401 (2008).

  [^wainwright]: Wainwright, Martin J., and Michael I. Jordan. “Graphical models, exponential families, and variational inference.” Foundations and Trends® in Machine Learning 1, no. 1-2 (2008): 1-305.

  [^poon]: Poon, Hoifung, and Pedro Domingos. “Sum-product networks: A new deep architecture.” In Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on, pp. 689-690. IEEE, 2011.

• János Kramár 18 Jun 2015 18:16 UTC

  LW: 2 AF: 1

  AF

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

  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:

  repeat:
      s := ""
      while s not in L:
          # if there is no next character, halt
          s := s + readchar()
      if s == x0:
          break
  M0()
  

  This $M$ will have $\mu \left(M\right)>3-2^{-|x_0|}+d(M_0,M)2^{-|x_0|-d(M_0,M)}$.

  $M$ here is optimized for building up internal states (that are then UTMs that are efficiently encoded), while also being very easy to reset from these internal states; in other words being easy to “encode” from the UTMs it efficiently encodes, using at most 2 bits (an average of $\frac{1+\sqrt{5}}{2}$). This is somewhat interesting, but clearly doesn’t capture the kind of computational expressivity we’re primarily interested in.

• János Kramár 18 Jun 2015 18:07 UTC

  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ár 2 Jun 2015 0:36 UTC

  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ár 7 May 2015 2:04 UTC

  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ár 29 Apr 2015 22:46 UTC

  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ár 25 Apr 2015 0:57 UTC

  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.

• János Kramár 11 Jun 2015 17:31 UTC

  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ár 12 Jan 2016 21:08 UTC

  0 points

  AF

  in reply to: Scott Garrabrant’s comment on: Con­cise Open Prob­lem in Log­i­cal Uncertainty

  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\left(n\right)\to \infty$ or $b_2\left(n\right)\to \infty$ then we win.

  Let’s reparametrize by writing $\delta \left(n\right)=A_2\left(n\right)-A_1\left(n\right)=\frac{2}{n+3}$ and $q\left(n\right)=\frac{p\left(n\right)-A_1\left(n\right)}{\delta \left(n\right)}$, so that $b_i^{\prime }\left(j\right)=\delta \left(j\right)(|i-2+E(j\left)\right|-\left|q\right(j)-1+E(j\left)\right|)$.

  Now, similarly to how $M$ worked for constant advisors, let’s look at the problem in rounds: let $s_0=0$, and $s_n=\lfloor \exp (s_{n-1}-1)\rfloor +1$ for $n>0$. When determining $E\left(s_{n-1}\right),\dots ,E(s_n-1)$, we can look at $p\left(s_{n-1}\right),\dots ,p(s_n-1)$. Let $t_n=\lfloor b_2\left(s_n\right)-\frac{1}{n}\rfloor$. Let’s set $E\left(s_{n-1}\right),\dots ,E(s_n-1)$ to 1 if ${\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)\ge 1$; otherwise we’ll do something more complicated, but maintain the constraint that $b_2\left(s_n\right)\ge b_2\left(s_{n-1}\right)-\frac{1}{n(n-1)}\ge t_{n-1}+\frac{1}{n}$: this guarantees that $t_n$ is nondecreasing and that ${liminf}_{j\to \infty }{b}_2\left(j\right)\ge {lim}_{n\to \infty }{t}_n$.

  If $t_n\to \infty$ then $b_2\left(n\right)\to \infty$ and we win. Otherwise, let $t={lim}_{n\to \infty }{t}_n$, and consider $n$ such that $t_{n-1}=t$.

  We have ${\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)<1$. Let $J\subseteq \{s_{n-1},\dots ,s_n-1\}$ be a set of indices with $q\left(j\right)\ge q\left(j^{\prime }\right)$ for all $j\in J,j^{\prime }\notin J$, that is maximal under the constraint that ${\sum }_{j\in J}\delta \left(j\right)(1-q(j\left)\right)\le \frac{1}{n(n-1)}$; thus we will still have ${\sum }_{j\in J}\delta \left(j\right)(1-q(j\left)\right)\ge \frac{1}{n(n-1)}-\delta \left(s_{n-1}\right)$. We shall set $E\left(j\right)=0$ for all $j\in J$.

  By the definition of $J$: $$\begin{array}{cc}\sum _{j\in J}{b}_1^{\prime }\left(j\right)& =\sum _{j\in J}\delta \left(j\right)q\left(j\right)\\ & \ge \sum _{j\in J}\delta \left(j\right)(1-q(j\left)\right)\frac{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)q\left(j\right)}{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)}\\ & \ge (\frac{1}{n(n-1)}-\delta (s_{n-1}\left)\right)\frac{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)-1}{1}\\ & \ge (\frac{1}{n(n-1)}-\delta (s_{n-1}\left)\right)(2\log \left(\frac{s_n+3}{s_{n-1}+3}\right)-1)\\ & \ge 2\text{if}n\gg 0\end{array}$$

  For $j^{\prime }\notin J$, we’ll proceed iteratively, greedily minimizing $\left|{\sum }_{j^{\prime }=s_{n-1}}^j{1}_{j^{\prime }\notin J}\left(b_1^{\prime }\right(j^{\prime }),b_2^{\prime }(j^{\prime }\left)\right)\right|$. Then: $$\begin{array}{cc}\underset{s_{n-1}\le j<s_n}{min}\sum _{j^{\prime }=s_{n-1}}^j{1}_{j^{\prime }\notin J}{b}_1^{\prime }\left(j^{\prime }\right)& \ge -\sqrt{\sum _{j=s_{n-1}}^{s_n-1}\delta (j{)}^2}\\ & =-2\sqrt{\sum _{j=s_{n-1}+3}^{s_n-2}\frac{1}{j^2}}\\ & \ge -2\sqrt{\sum _{j=s_{n-1}+3}^{s_n-2}(\frac{1}{j-1}-\frac{1}{j})}\\ & \ge -\frac{2}{\sqrt{s_{n-1}+2}}\\ & \ge -1\text{if}n\gg 0\end{array}$$

  Keeping this constraint, we can flip (or not flip) all the $E\left(j^{\prime }\right)$s for $j^{\prime }\notin J$ so that ${\sum }_{j^{\prime }=s_{n-1}}^{s_n-1}{1}_{j^{\prime }\notin J}{b}_2^{\prime }\left(j^{\prime }\right)>0$. Then, we have $b_2\left(s_n\right)\ge b_2\left(s_{n-1}\right)-\frac{1}{n(n-1)}$, $b_1\left(s_n\right)-b_1\left(s_{n-1}\right)={\sum }_{j=s_{n-1}}^{s_n}(1_{j\in J}+1_{j\notin J})b_1^{\prime }\left(j\right)\ge 2-1=1$ if $n\gg 0$, and for $s_{n-1}\le j\le s_n$, $b_1\left(j\right)\ge b_1\left(s_{n-1}\right)+{\sum }_{j^{\prime }=s_{n-1}}^{j-1}{1}_{j^{\prime }\notin J}{b}_1^{\prime }\left(j^{\prime }\right)\ge b_1\left(s_{n-1}\right)-1$ if $n\gg 0$.

  Therefore, $b_1\left(j\right)\to \infty$, so we win.

• János Kramár 12 Jan 2016 20:45 UTC

  0 points

  AF

  in reply to: Scott Garrabrant’s comment on: Con­cise Open Prob­lem in Log­i­cal Uncertainty

  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(next - 1)) + 1
  
      for i in xrange(0, Inf):
          for k in xrange(this, next): p[k] = P[i]
          prev, this, next = this, next, floor(exp(next - 1)) + 1
  

  bad(i) is now up to date through E[:this], not just E[:prev]

          bound = 2 * bad(i)
          for j in xrange(0, Inf):
              if P[j] == P[i]: continue
              flip = P[j] < P[i]
              p1, p2 = abs(P[i] - flip), abs(P[j] - flip)
              for k in xrange(this, next): p[k] = abs(p1 - flip)
              prev, this, next = this, next, floor(exp(next - 1)) + 1
              
              if bad(i) <= 0: break
              while bad(i) > 0 and bad(j) > 0:
                  # won't let bad(i) surpass bound
                  eps = (bound - bad(i)) / 2 / abs(1 - p1 - flip) / (next - this)
  

  This is just for early iterations of the inner loop; in the limit, eps should be just enough for bad(i) to go halfway to bound if we let p = abs(p1 + eps - flip):

                  while eps >= 1 - p1 or
                        bound <= bad(i) + (next - this) *
                          log((1 - p1) / (1 - p1 - eps)):
                      eps /= 2
                  for k in xrange(this, next): p[k] = abs(p1 + eps - flip)
                  prev, this, next = this, next, floor(exp(next - 1)) + 1
  
                  for k in xrange(this, next): p[k] = abs(p1 - flip)
                  # this is where the P[i] + d * eps affects bad(i)
  

  Consider $q=\frac{\log (1-p1)-\log (1-p2)}{\log (1-p1)-\log (1-p2)+\log \left(p2\right)-\log \left(p1\right)}$. This $q$ is the probability between p1 and p2 such that if E[k] is chosen with probability $|q-flip|$ then that will have an equal impact on bad(i) and bad(j). Now consider some $q^{\prime }$ between p1 and $q$. Every iteration where $\mathrm{mean}\left(\left|E[prev:this]-flip\right|\right)\le q^{\prime }$ will decrease bad(j) by a positive quantity that’s at least linear in this-prev, so (at least after the first few such iterations) this will exceed $prev\cdot -\log ({max}_{k:P_k\text{has been reached}}max(P_k,1-P_k\left)\right)>bad\left(j\right)$, so it will turn bad(j) negative. If this happens for all j then M cannot be bad for E. If it doesn’t, then let’s look at the first j where it doesn’t. After a finite number of iterations, every iteration must have $\mathrm{mean}\left(\left|E[prev:this]-flip\right|\right)>q^{\prime }$. However, this will cause bad(i) to decrease by a positive quantity that’s at least proportional to bound - bad(i); therefore, after a finite number of such iterations, we must reach $bad\left(i\right)<0$. So if M is bad for E then for each value of i we will eventually make $bad\left(i\right)<0$ and then move on to the next value of i. This implies M is not bad for E.

  ---

  Emboldened by this, we can also consider the problem of building an $M$ that isn’t outperformed by any constant advisor. However, this cannot be done, according to the following handwavy argument:

  Let $q$ be some incompressible number, and let $E\left(i\right)\stackrel{iid}{\sim }\mathrm{Bern}\left(q\right)$. When computing $p\left(n\right)$, $M$ can’t do appreciably better than Laplace’s law of succession, which will give it standard error $\sqrt{\frac{q(1-q)}{\log \left(n\right)}}$, and relative badness $\sim \frac{q(1-q)}{\log \left(n\right)}(\frac{1}{q}+\frac{1}{1-q})=\frac{1}{\log \left(n\right)}$ (relative to the $q$-advisor) on average. For $i\le n$, and $n\gg 0$, the greatest deviation of the badness from the ${\sum }_{j=2}^i\frac{1}{\log \left(j\right)}\ge \frac{i-1}{\log \left(i\right)}$ trend is $\approx \sqrt{2n\log \log \left(n\right)q(1-q)}$ (according to the law of the iterated logarithm), which isn’t enough to counteract the expected badness; therefore the badness will converge to infinity.

• János Kramár 12 Jun 2015 1:49 UTC

  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ár 11 May 2015 2:35 UTC

  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ár 25 Apr 2015 21:53 UTC

  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ár 25 Apr 2015 21:09 UTC

  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.