Diffractor

In­frafunc­tions Proofs

In­frafunc­tions and Ro­bust Optimization

• Diffractor 26 Mar 2023 6:12 UTC

  2 points

  0

  in reply to: Sonata Green’s comment on: Unify­ing Bar­gain­ing No­tions (2/​2)

  I’d strongly agree with that, mainly because, while points with this property exist, they are not necessarily unique. The non-uniqueness is a big issue.

• Diffractor 26 Mar 2023 6:09 UTC

  2 points

  0

  in reply to: Chris van Merwijk’s comment on: Unify­ing Bar­gain­ing No­tions (2/​2)

  It was a typo! And it has been fixed.

• Diffractor 26 Mar 2023 6:04 UTC

  2 points

  0

  in reply to: MondSemmel’s comment on: Unify­ing Bar­gain­ing No­tions (1/​2)

  It is because beach/​beach is the surplus-maximizing result. Any Pareto-optimal bargaining solution where money is involved will involve the surplus-maximizing result being played, and a side payment occuring.

• Diffractor 6 Nov 2022 2:38 UTC

  4 points

  2

  on: Open Prob­lem in Vot­ing Theory

  I have a reduction of this problem to a (hopefully) simpler problem. First up, establish the notation used.

  [n] refers to the set $\left\{\mathrm{1...}n\right\}$. $n$ is the number of candidates. Use $C$ as an abbreviation for the space $\Delta \left[n\right]$, it’s the space of probability distributions over the candidates. View $C$ as embedded in $R^{n-1}$, and set the origin at the center of $C$.

  At this point, we can note that we can biject the following:
  1: Functions of type $\left[n\right]\to [0,1]$
  2: Affine functions of type $C\to [0,1]$
  3: Functions of the form $\lambda x.⟨a,x⟩+c$, where $x,a\in R^{n-1}$, and and $c\in R$, and everything’s suitably set so that these functions are bounded in $[0,1]$ over $C$. (basically, we extend our affine function to the entire space with the Hahn-Banach theorem, and use that every affine function can be written as a linear function plus a constant) We can reexpress our distribution $V$ over utility functions as a distribution over these normal vectors $a$.

  Now, we can reexpress the conjecture as follows. Is it the case that there exists a $\mu :\Delta C$ s.t. for all $\nu :\Delta C$, we have

  $$E_{x,y,a\sim \mu \times \nu \times V}\left[\text{sgn}\right(⟨a,x-y⟩\left)\right]\ge 0$$

  Where $\text{sgn}$ is the function that’s −1 if the quantity is negative, 0 if 0, and 1 if the quantity is positive. To see the equivalence to the original formulation, we can rewrite things as

  $$E_{x,y,a\sim \mu \times \nu \times V}[{\text{1}}_{⟨a,x⟩>⟨a,y⟩}-{\text{1}}_{⟨a,y⟩>⟨a,x⟩}]\ge 0$$

  Where the bold 1 is an indicator function. And split up the expectation and realize that this is a probability, so we get

  $$P_{x,y,a\sim \mu \times \nu \times V}[⟨a,x⟩>⟨a,y⟩]-P_{x,y,a\sim \mu \times \nu \times V}[⟨a,y⟩>⟨a,x⟩]\ge 0$$$$P_{x,y,a\sim \mu \times \nu \times V}[⟨a,x⟩>⟨a,y⟩]\ge P_{x,y,a\sim \mu \times \nu \times V}[⟨a,y⟩>⟨a,x⟩]$$

  And this then rephrases as

  $$P_{x,y,U\sim \mu \times \nu \times V}\left[U\right(x)>U(y\left)\right]\ge P_{x,y,U\sim \mu \times \nu \times V}\left[U\right(y)>U(x\left)\right]$$

  Which was the original formulation of the problem.

  Abbreviating the function $E_{x,y,a\sim \mu \times \nu \times V}\left[\text{sgn}\right(⟨a,x-y⟩\left)\right]$ as $f(\mu ,\nu )$, then a necessary condition to have a $\mu :\Delta C$ that dominates everything is that

  $$\underset{\mu \in \Delta C}{sup}\underset{\nu \in \Delta C}{inf}f(\mu ,\nu )\ge 0$$

  If you have this property, then you might not necessarily have an optimal $\mu$ that dominates everything, but there are $\mu$ that get a worst-case expectation arbitrarily close to 0. Namely, even if the worst possible $\nu$ is selected, then the violation of the defining domination inequality happens with arbitrarily small magnitude. There might not be an optimal lottery-lottery, but there are lottery-lotteries arbitrarily close to optimal where this closeness-to-optimality is uniform over every foe. Which seems good enough to me. So I’ll be focused on proving this slightly easier statement and glossing over the subtle distinction between that, and the existence of truly optimal lottery-lotteries.

  As it turns out, this slightly easier statement (that sup inf is 0 or higher) can be outright proven assuming the following conjecture.

  Stably-Good-Response Conjecture: For every $\nu :\Delta C$, and $ϵ>0$, there exists a $\mu :\Delta C$ and a $\delta >0$ s.t.

  $$\underset{{\nu }^{\prime }:d(\nu ,{\nu }^{\prime })<\delta }{inf}f(\mu ,{\nu }^{\prime })>-ϵ$$

  Pretty much, for any desired level of suckage and any foe $\nu$, there’s a probability distribution $\mu$ you can pick which isn’t just a good response (this always exists, just pick $\nu$ itself), but a stably good response, in the sense that there’s some nonzero level of perturbation to the foe where $\mu$ remains a good response no matter how the foe is perturbed.

  Theorem 1 Assuming the Stably-Good-Response Conjecture, ${sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )\ge 0$.

  I’ll derive a contradiction from the assumption that $0>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$. Accordingly, assume the strict inequality.

  In such a case, there is some $ϵ$ s.t. $0>-ϵ>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$. Let the set $A_{\mu }:=\left\{\nu |f\right(\mu ,\nu )>-ϵ\}$. Now, every $\nu$ lies in the interior of $A_{\mu }$ for some $\mu$, by the Stably-Good-Response Conjecture. Since $\Delta C$ is a compact set, we can isolate a finite subcover and get some finite set $M$ of probability distributions $\mu$ s.t. $\forall \nu \exists \mu \in M:f(\mu ,\nu )>-ϵ$.

  Now, let the set $B_{\nu }:=\{\mu \in c.h(M\left)|f\right(\mu ,\nu )<-ϵ\}$. Since $-ϵ>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$, this family of sets manages to cover all of $c.h\left(M\right)$ (convex hull of our finite set.) Further, for any fixed $\nu$, $f(\mu ,\nu )$ is a continuous function $c.h\left(M\right)\to R$ (a bit nonobvious, but true nontheless because there’s only finitely many vertices to worry about). Due to continuity, all the sets $B_{\nu }$ will be open. Since we have an open cover of $c.h\left(M\right)$, which is a finite simplex (and thus compact), we can isolate a finite subcover, to get a finite set $N$ of $\nu$ s.t. $\forall \mu \in c.h\left(M\right)\exists \nu \in N:f(\mu ,\nu )<-ϵ$. And now we can go

  $$-ϵ>\underset{\mu \in c.h\left(M\right)}{max}\underset{\nu \in N}{min}f(\mu ,\nu )\ge \underset{\mu \in c.h\left(M\right)}{max}\underset{\nu \in c.h\left(N\right)}{min}f(\mu ,\nu )=\underset{\nu \in c.h\left(N\right)}{min}\underset{\mu \in c.h\left(M\right)}{max}f(\mu ,\nu )\ge \underset{\nu \in c.h\left(N\right)}{min}\underset{\mu \in M}{max}f(\mu ,\nu )>-ϵ$$

  The first strict inequality was from how all $\mu \in c.h\left(M\right)$ had some $\nu \in N$ which made $f(\mu ,\nu )$ get a bad score. The $\ge$ was from expanding the set of options. The $=$ was from how $f$ is a continuous linear function when restricted to $c.h\left(M\right)\times c.h\left(N\right)$, both of which are compact convex sets, so the minimax theorem can be applied. Then the next $\ge$ was from restricting the set of options, and the $>$ was from how every $\nu \in \Delta C$ had some $\mu \in M$ that’d make $f(\mu ,\nu )$ get a good score, by construction of $M$ (and compactness to make the inequality a strict one).

  But wait, we just showed $-ϵ>-ϵ$, that’s a contradiction. Therefore, our original assumption must have been wrong. Said original assumption was that $0>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$, so negating it, we’ve proved that

  $$\underset{\mu }{sup}\underset{\nu }{inf}f(\mu ,\nu )\ge 0$$

  As desired.

• Diffractor 1 Oct 2022 16:28 UTC

  2 points

  0

  in reply to: M. Y. Zuo’s comment on: Threat-Re­sis­tant Bar­gain­ing Me­ga­post: In­tro­duc­ing the ROSE Value

  With this.

• Diffractor 1 Oct 2022 2:24 UTC

  2 points

  0

  in reply to: M. Y. Zuo’s comment on: Threat-Re­sis­tant Bar­gain­ing Me­ga­post: In­tro­duc­ing the ROSE Value

  What I mean is, the players hit each other up, are like “yo, let’s decide on which ROSE point in the object-level game we’re heading towards”
  Of course, they don’t manage to settle on what equilibrium to go for in the resulting bargaining game, because, again, multiple ROSE points might show up in the bargaining game.
  But, the ROSE points in the bargaining game are in a restricted enough zone (what with that whole “must be better than the random-dictator point” thing) to seriously constrain the possibilities in the object-level game. “Worst ROSE point for Alice in the object-level-game” is a whole lot worse for her than “Worst ROSE point for Alice in the bargaining game about what to do in the object-level-game”.
  
  So, the players should be able to ratchet up their disagreement point and go “even if the next round of bargaining fails, at least we can promise that everyone does this well, right? Sure, everyone’s going for their own idea of fairness, but even if Alice ends up with her worst ROSE point in the bargaining game, her utility is going to be at least this high, and similar for everyone else.”
  
  And so, each step of bargaining that successfully happens ratchets up the disagreement point closer to the Pareto frontier, in a way that should quickly converge. If someone disagrees on step 3, then the step-3 disagreement point gets played, which isn’t that short of the Pareto frontier. And if someone doesn’t have time for all this bargaining, they can just break things off at step 10 or something, that’s just about as good as going all the way to infinity.
  
  Or at least, it should work like this. I haven’t proved that it does, and it depends on things like “what does ROSE bargaining look like for n players” and “does the random-dictator-point-dominance thing still hold in the n-player case” and “what’s the analogue of that strategy where you block your foe from getting more than X utility, when there are multiple foes?”. But this disagreement-point ratcheting is a strategy that address your worries with “ever-smaller pieces of the problem live on higher meta-levels, so the process of adding layers of meta actually converges to solving the problem, and breaking it off early solves most of the problem”
  
  Regarding your last comment, yes, you could always just have a foe that’s a jerk, but you can at least act so they don’t gain from being an jerk, in a way robust against you and a foe having slightly different definitions of “jerk”.

• Diffractor 30 Sep 2022 3:50 UTC

  LW: 10 AF: 7

  0

  AF

  on: Threat-Re­sis­tant Bar­gain­ing Me­ga­post: In­tro­duc­ing the ROSE Value

  I think I have a contender for something which evades the conditional-threat issue stated at the end, as well as obvious variants and strengthenings of it, and which would be threat-resistant in a dramatically stronger sense than ROSE.

  There’s still a lot of things to check about it that I haven’t done yet. And I’m unsure how to generalize to the n-player case. And it still feels unpleasantly hacky, according to my mathematical taste.

  But the task at least feels possible, now.

  EDIT: it turns out it was still susceptible to the conditional-threat issue, but then I thought for a while and came up with a different contender that feels a lot less hacky, and that provably evades the conditional-threat issue. Still lots of work left to be done on it, though.

• Diffractor 28 Sep 2022 21:08 UTC

  LW: 4 AF: 3

  0

  AF

  in reply to: Daniel Kokotajlo’s comment on: Threat-Re­sis­tant Bar­gain­ing Me­ga­post: In­tro­duc­ing the ROSE Value

  For 1, it’s just intrinsically mathematically appealing (continuity is always really nice when you can get it), and also because of an intution that if your foe experiences a tiny preference perturbation, you should be able to use small conditional payments to replicate their original preferences/​incentive structure and start negotiating with that, instead.

  I should also note that nowhere in the visual proof of the ROSE value for the toy case, is continuity used. Continuity just happens to appear.

  For 2, yes, it’s part of game setup. The buttons are of whatever intensity you want (but they have to be intensity-capped somewhere for technical reasons regarding compactness). Looking at the setup, for each player pair i,j, $D_{i,j}$ is the cap for how much of j’s utility that i can destroy. These can vary, as long as they’re nonnegative and not infinite. From this, it’s clear “Alice has a powerful button, Bob has a weak one” is one of the possibilities, that would just mean $D_{a,b}>>D_{b,a}$. There isn’t an assumption that everyone has an equally powerful button, because then you could argue that everyone just has an equal strength threat and then it wouldn’t be much of a threat-resistance desideratum, now would it? Heck, you can even give one player a powerful button and the other a zero-strength button that has no effect, that fits in the formalism.
  
  So the theorem is actually saying “for all members of the family of destruction games with the button caps set wherever the heck you want, the payoffs are the same as the original game”.

• Diffractor 28 Sep 2022 6:49 UTC

  LW: 7 AF: 4

  0

  AF

  in reply to: DaemonicSigil’s comment on: Threat-Re­sis­tant Bar­gain­ing Me­ga­post: In­tro­duc­ing the ROSE Value

  My preferred way of resolving it is treating the process of “arguing over which equilibrium to move to” as a bargaining game, and just find a ROSE point from that bargaining game. If there’s multiple ROSE points, well, fire up another round of bargaining. This repeated process should very rapidly have the disagreement points close in on the Pareto frontier, until everyone is just arguing over very tiny slices of utility.

  This is imperfectly specified, though, because I’m not entirely sure what the disagreement points would be, because I’m not sure how the “don’t let foes get more than what you think is fair” strategy generalizes to >2 players. Maaaybe disagreement-point-invariance comes in clutch here? If everyone agrees that an outcome as bad or worse than their least-preferred ROSE point would happen if they disagreed, then disagreement-point-invariance should come in to have everyone agree that it doesn’t really matter exactly where that disagreement point is.

  Or maybe there’s some nice principled property that some equilibria have, which others don’t, that lets us winnow down the field of equilibria somewhat. Maybe that could happen.

  I’m still pretty unsure, but “iterate the bargaining process to argue over which equilibria to go to, you don’t get an infinite regress because you rapidly home in on the Pareto frontier with each extra round you add” is my best bad idea for it.

  EDIT: John Harsanyi had the same idea. He apparently had some example where there were multiple CoCo equilibria and his suggestion was that a second round of bargaining could be initiated over which equilibria to pick, but that in general, it’d be so hard to compute the n-person Pareto frontier for large n, that an equilibria might be stable because nobody can find a different equilibria nearby to aim for.

  So this problem isn’t unique to ROSE points in full generality (CoCo equilibria have the exact same issue), it’s just that ROSE is the only one that produces multiple solutions for bargaining games, while CoCo only returns a single solution for bargaining games. (bargaining games are a subset of games in general)

Threat-Re­sis­tant Bar­gain­ing Me­ga­post: In­tro­duc­ing the ROSE Value

• Diffractor 17 Sep 2022 21:30 UTC

  2 points

  0

  in reply to: lexing’s comment on: Unify­ing Bar­gain­ing No­tions (1/​2)

  So, if you are limited to only pure strategies, for some reason, then yes, Chinese would be on the Pareto frontier.
  But if you can implement randomization, then Chinese is not on the Pareto frontier, because both sides agree that “flip a coin, Heads for Sushi, Tails for Italian” is just strictly better than Chinese.
  
  The convex shape consists of all the payoff pairs you can get if you allow randomization.

• Diffractor 16 Sep 2022 5:09 UTC

  17 points

  0

  on: What’s the longest a sen­tient ob­server could sur­vive in the Dark Era?

  Alright, this is kind of a Special Interest, so here’s your relevant thought dump.
  
  First up, the image is kind of misleading, in the sense that you can always tack on extra orders of magnitude. You could tack on another thousand orders of magnitude and make it look even longer, or just go “this is 900 OOM’s of literally nothing happening, lets clip that off and focus on the interesting part”
  
  Assuming proton decay is a thing (that free protons decay with a ridiculously long half-life)....
  
  ok, I was planning on going “as a ludicrous upper bound, here’s the number”, but, uh, the completely ludicrous upper bound wound up being a WHOLE LOT longer than I thought. I… I didn’t even think it was possible to stall till the evaporation of even a small black hole. But this calculation indicates that if you’re aiming solely at living ludicrously long, you can stall about a googol years, enough for even the largest black holes to evaporate, and to get to the end of the black hole era. I’m gonna need to rethink some stuff.
  
  EDIT: rethought some stuff, realized it doesn’t change my conclusions from when I last looked into this. The fundamental problem is that, for any remotely realistic numbers, if you’re trying to catch the final evaporation of a black hole to harvest its mass-energy, you’ll blow a lot more than the amount of mass-energy that you could gain, in order to wait that long.
  
  Final conclusion: If proton decay is a thing, it’s definitely not worth waiting to the end of a black hole, you’ll want to have things wrapped up far earlier. If proton decay isn’t a thing, you’ll want to wait till the black hole evaporates to catch that final party and last ${10}^{19}$ kg of mass-energy. If proton decay is a thing and you’re willing to blow completely ridiculous cosmic amounts of resources on it, you can last till the late parts of the black hole era.
  
  The rough rationale is as follows. Start with 10x the mass of the largest black holes in the universe, around ${10}^{12}$ solar masses stockpiled. If they’re spinning fast enough, you can extract energy from them, assume you can extract all of it (it’s over 10 percent, so let’s round it up to 100 percent). Assume that proton decay is ${10}^{40}$ years (a high estimate), and that we use the energy at 100 percent efficiency to make matter (also high estimate), you can take out one proton, wait for around a proton decay time, take out the next proton, and so on. Then you can take out around ${10}^{69}$ protons, and each one lasts you around ${10}^{40}$ years, getting around ${10}^{109}$ years (high uncertainty). And, coincidentally, natural Hawing radiation finishes off the black hole of that size in ${10}^{103}$ years, leaving a small margin left over for silly considerations like “maybe the intelligence needs more than one proton to physically implement”.
  
  So, not remotely practical, but maybe something like ${10}^{80}$ years would actually be doable? That extra 29 OOM’s of wiggle room patches over a lot of sins in this calculation.
  
  But, in terms of what would actually be practical for the far future of humanity, it’d be the strat of “dump as much mass into a fast-spinning black hole as possible. Like, eat the entire Laniakea supercluster complex. Wait a trillion years for the cosmic microwave background radiation to cool to its floor temperature. You’d be in the late Stelliferous era at this point, with a few red dwarfs around, if you didn’t dump all the stars in the mega-black-hole already. Set up some infrastructure around the mega-hole, and use the Blandford-Znajek mechanism to convert the mega-hole spin into electrical power. You should be able to get about a gigawatt of power for the next ${10}^{45}$ years to run a whole lotta computation and a little bit of maintanence, and if proton decay is messing with things, chop however many OOM’s you need off the time and add those OOM’s to the power output. Party for a trillion trillion trillion eons with your super-optimized low-temperature computing infrastructure”

In­fra-Ex­er­cises, Part 1

• Diffractor 20 Aug 2022 3:21 UTC

  LW: 6 AF: 3

  0

  AF

  in reply to: johnswentworth’s comment on: Unify­ing Bar­gain­ing No­tions (1/​2)

  Yeah, “transferrable utility games” are those where there is a resource, and the utilities of all players are linear in that resource (in order to redenominate everyone’s utilities as being denominated in that resource modulo a shift factor). I believe the post mentioned this.

Less Threat-Depen­dent Bar­gain­ing Solu­tions?? (3/​2)

• Diffractor 27 Jul 2022 20:13 UTC

  5 points

  0

  in reply to: mtaran’s comment on: Unify­ing Bar­gain­ing No­tions (2/​2)

  Task completed.

• Diffractor 27 Jul 2022 20:07 UTC

  LW: 12 AF: 2

  2

  AF

  in reply to: Dagon’s comment on: Unify­ing Bar­gain­ing No­tions (1/​2)

  Agreed. The bargaining solution for the entire game can be very different from adding up the bargaining solutions for the subgames. If there’s a subgame where Alice cares very much about victory in that subgame (interior decorating choices) and Bob doesn’t care much, and another subgame where Bob cares very much about it (food choice) and Alice doesn’t care much, then the bargaining solution of the entire relationship game will end up being something like “Alice and Bob get some relative weights on how important their preferences are, and in all the subgames, the weighted sum of their utilities is maximized. Thus, Alice will be given Alice-favoring outcomes in the subgames where she cares the most about winning, and Bob will be given Bob-favoring outcomes in the subgames where he cares the most about winning”

  And in particular, since it’s a sequential game, Alice can notice if Bob isn’t being fair, and enforce the bargaining solution by going “if you’re not aiming for something sorta like this, I’ll break off the relationship”. So, from Bob’s point of view, aiming for any outcome that’s too Bob-favoring has really low utility since Alice will inevitably catch on. (this is the time-extended version of “give up on achieving any outcome that drives the opponent below their BATNA”) Basically, in terms of raw utility, it’s still a bargaining game deep down, but once both sides take into account how the other will react, the payoff matrix for the restaurant game (taking the future interactions into account) will look like “it’s a really bad idea to aim for an outcome the other party would regard as unfair”

• Diffractor 27 Jul 2022 19:42 UTC

  LW: 2 AF: 1

  0

  AF

  in reply to: philip_b’s comment on: Unify­ing Bar­gain­ing No­tions (1/​2)

  Actually, they apply anyways in all circumstances, not just after the rescaling and shifting is done! Scale-and-shift invariance means that no matter how you stretch and shift the two axes, the bargaining solution always hits the same probability-distribution over outcomes, so monotonicity means “if you increase the payoff numbers you assign for some or all of the outcomes, the Pareto frontier point you hit will give you an increased number for your utility score over what it’d be otherwise” (no matter how you scale-and-shift). And independence of irrelevant alternatives says “you can remove any option that you have 0 probability of taking and you’ll still get the same probability-distribution over outcomes as you would in the original game” (no matter how you scale-and-shift)