Buridan's ass in coordination games

16th Jul 2018

16gjm

9Paul Christiano

10Wei Dai

5Jessica Taylor

4Dagon

4Jessica Taylor

3Dagon

0Jessica Taylor

6Dagon

3Jessica Taylor

2Dagon

1Jessica Taylor

2Dagon

1Jessica Taylor

4Dagon

0Jessica Taylor

0Dagon

4Rohin Shah

1Laszlo Treszkai

1Jessica Taylor

1Donald Hobson

4avturchin

2Vladimir Slepnev

3Jessica Taylor

4Vladimir Slepnev

4Vladimir Slepnev

New Comment

26 comments, sorted by Click to highlight new comments since: Today at 8:17 PM

This doesn't (I think) really have much to do with randomness as such. The relevant thing about R is that it's *shared information that a hypothetical adversary doesn't get to see*.

If isn't chosen adversarially, then our players don't care about pessimizing over but about something like an average over , and then R isn't needed. Or, if they are ultra-cautious people who universally care about worst cases, then they don't care about expectation w.r.t. R but about the worst case as R varies, and then R doesn't help. R only helps them when is chosen adversarially and R isn't; or when they care about pessimizing w.r.t but not w.r.t. R.

So the real conclusion here is not "sometimes shared randomness helps", it's "if some people are trying to coordinate in the presence of an adversary, anything they share and the adversary has no access to helps".

Sometimes you want to prove a theorem like "The algorithm works well." You generally need randomness if you want to find algorithms that work without strong assumptions on the environment, whether or not there is really an adversary (who knows what kinds of correlations exist in the environment, whether or not you call them an "adversary").

A bayesian might not like this, because they'd prefer prove theorems like "The algorithm works well on average for a random environment drawn from the prior the agents use," for which randomness is never useful.

But specifying the true prior is generally hideously intractable. So a slightly more wise Bayesian might want to prove statements like "The algorithm well on average for a random environment drawn from the *real* prior" where the "real prior" is some object that we can talk about but have no explicit access to. And now the wiser Bayesian is back to needing randomness.

A bayesian might not like this, because they’d prefer prove theorems like “The algorithm works well on average for a random environment drawn from the prior the agents use,” for which randomness is never useful.

It seems like a bayesian can conclude that randomness is useful, if their prior puts significant weight on "the environment happens to contain something that iterates over my decision algorithm and returns its worst-case input, or something that's equivalent to or approximates this" (which they should, especially after updating on their own existence). I guess right now we don't know how to handle this in a naturalistic way (e.g., let both intentional and accidental adversaries fall out of some simplicity prior) and so are forced to explicitly assume the existence of adversaries (as in game theory and this post).

This seems basically right. As discussed in the conclusion, there are reasons to care about worst-case performance other than literal adversaries.

Sure, but non-adversarial cases (really, any cases where u is determined independently of strategies chosen) can just choose R as a fixed part of the strategy, rather than a random shared component determined later.

That's right, but getting the worst-case guarantee requires this initial choice to be random.

Nope. Random choice gives a specific value for R each game. The outcome for that iteration is IDENTICAL to the outcome if that R was chosen intentionally. Randomness only has game value as a mechanism to keep information from an adversarial actor.

To be clear, by "worst-case guarantee" I mean "the expected utility is guaranteed to be pretty good regardless of ", which is unattainable without shared randomness (claim 1).

I think you are either misunderstanding or disagreeing with a lot of the terminology on randomized algorithms and worst-case guarantees that are commonly used in CS and statistics. This article is a decent introduction to this topic.

I'm missing something (and I haven't digested the math, so maybe it's obvious but just missing from the narrative description). Is epsilon the same for both players, in that they see the same V, it just may not exactly match u? or is it different for each player, meaning for the same u, they have different V? From your analysis (risk of 0), it sounds like the latter.

In that case, I don't see how additional shared knowledge helps coordinate them, nor why it needs to be random rather than just a fixed value they agree on in advance. And certainly not why it matters if the additional random shared value is generated before or after the game starts.

If they don't have this additional source of shared randomness, can they just decide in their pre-game discussion to use R=0.5? Why or why not?

is the same for both players but and (the players' observations of ) are different, both sampled independently uniformly from .

If they decide on then there exists some value for which they get a bad expected utility (see Claim 1).

Sure, but that goes for a randomly-chosen R too. For every possible R, there is a u value for which they get bad outcomes. It doesn't get better by randomly choosing R.

The assumption is that is chosen after . So for every the pair of policies gets a good expected utility. See the point on Bayesian algorithms in the conclusion for more on why "get a high expected utility regardless of " might be a desirable goal.

R∼Uniform([0,1])

How can it possibly matter whether R is chosen before or after uy? R is completely independent of u, right? It's not a covert communication mechanism about the players' observations, it's a random value.

If is chosen after then it might be chosen to depend on in such a way that the algorithm gets bad performance, e.g. using the method in the proof of Claim 1.

Based on other comments, I realize I'm making an assumption for something you haven't specified. How is uy chosen? If it's random and independent, then my assertion holds, if it's selected by an adversary who knows the players' full strategies somehow, then R is just a way of keeping a secret from the adversary - sequence doesn't matter, but knowledge does.

Claim 1 says there exists some value for which the algorithm gets high regret, so we might as well assume it's chosen to maximize regret.

Claim 2 says the algorithm has low regret regrardless of , so we might as well assume it's chosen to maximize regret.

uy and R are independently chosen from well-defined distributions. Regardless of sequence, neither knows the other and CANNOT be chosen based on the other. I'll see if I can find time tonight to figure out whether I'm saying your claim 1 is wrong (it dropped epsilon too soon from the floor value, but I'm not sure if it's more fundamentally problematic than that) or that your claim 2 is misleading.

My current expectation is that I'll find that your claim 2 results are available in situation 1, by using your given function with a pre-agreed value rather than a random one.

The theorems are of the form "For all uy, you get good outcomes" or "There exists a uy that causes bad outcomes".

When you want to prove statements of this form, uy is chosen adversarially, so it matters whether it is chosen before or after R.

uy and R are independently chosen from well-defined distributions.

What distribution is uy chosen from? That's not specified anywhere in the post.

True, they will fail to cooperate for some R, but the values of such R have a low probability. (But yeah, it's also required that uy and R are chosen independently—otherwise an adversary could just choose either so that it results in the players choosing different actions.)

The smoothness comes in from marginalising a random R. The coordination comes from making R and ε common knowledge, so they cooperate using the correlation in their observations—an interesting phenomenon.

(How can I write LaTeX in the comments?)

If you assume a fixed probability distribution over possible $u_y$ that both players know when coordinating, then they can set up the rules they choose to make sure that they probably win. The extra random information is only useful because of the implicit "for all $u_y$". If some malicious person had overheard their strategy, and was allowed to choose $u_y$, but didn't have access to the random number source, then the random numbers are useful.

I expected that Lamport paper would be mentioned, as it describes a known catastrophic mode for autonomous systems, connected with Buridan ass problem and infinite recursion about predicting future time of the problem solving. I think that this problem is underexplored for AI Safety, despite previous attempt to present it on LessWrong.

Looks like I was wrong again and shame on me. Correlated equilibrium can't be useful in a purely cooperative game, it's only useful if we're trying to minimax over many cooperative games. You even spelled it out in the post, but my eyes skipped over it. Sorry again.

Yeah, sorry, I was hasty. Looks like you're making a more interesting point: correlated equilibrium can be useful even in purely cooperative games. I wonder what would be the simplest example game...

Consider a simple coordination game. In this game, two players (player 1 and player 2) each simultaneously choose an action, X or Y. If they both choose X, they both get 1 utility. If they both choose Y, they both get uy utility for some 0≤uy≤2 known to both players. If they choose different actions, they both get 0 utility. Which action should they each choose? Assume they get to communicate before knowing uy, but not after knowing uy.

An optimal policy pair is for each to pick X if uy<1, and Y otherwise. Unfortunately, this policy pair can break down in the presence of even a small amount of noise. Assume neither player observes uy, but instead each receives an independent observation Vi (player 1 sees V1, player 2 sees V2), each of which is drawn uniformly from the range [uy−ϵ,uy+ϵ] for some small ϵ>0. If both players follow the policy of choosing X if and only if their

observationof uy is less than 1, then if uy is very close to 1, there is a significant likelihood that one player will receive an observation less than 1, while the other will receive one greater than 1. Thus, they have a significant chance of choosing different actions and receiving 0 utility. This issue is essentially the same as the one faced by Buridan's ass: both options are equally good, so there is no way to effectively decide between them.In fact, as I will prove:

Claim 1: No pair of policies in which the players select their actionsindependentlygiven their observations can simultaneously guarantee an expected utility greater than max(1,uy)−0.5 for all uy∈[0,2].But things change when a shared source of randomness is allowed. Then, as I will also prove:

Claim 2: Suppose that, after observing their observation of uy, each player also gets to observe a random number R∼Uniform([0,1]). Then there is a pair of policies that achieves expected utility at least max(1,uy)−2√ϵ−ϵ regardless of uy .This solution method extends to arbitrary cooperative normal-form games where players observe a perturbed version of the true utility function. This is shown in the appendix.

Why is this important? I expect progress in decision theory to come from studying very simple decision problems like this one. If it is possible to show that any solution to some simple problem has certain properties, then this usefully constrains the design space of possible decision theories. In this case, the result suggests that something like shared randomness may be required for achieving provable near-optimality even in cooperative settings.

## Claim 1: impossibility of solving the game using independent randomness

Fix ϵ>0. Let π1,π2:R→[0,1] be Lesbegue measurable functions representing the two players' policies, which map Vi to the player's probability of choosing action Y.

Define q(u):=Uniform([u−ϵ,u+ϵ]) to be the function mapping uy to the resulting Vi distribution.

Define τi(u):=Ev∼q(u)[πi(v)]. This is defined so that τi(uy) equals player i's overall probability of choosing action Y.

For u1,u2∈[0,2], note that the total variation distance between q(u1) and q(u2) is at most |u1−u2|ϵ. Thus, since πi is bounded between 0 and 1, τi is 1ϵ-Lipschitz and therefore continuous.

I will now show that, for some uy, the players achieve expected utility at most max(1,uy)−0.5 by case analysis on τ1:

Thus, claim 1 is proven. This proof method bears resemblance to the problem faced by Buridan's ass: in the third case, some uy value is found so that the "policy" τ1 is equally compelled by both options, choosing between them with a 50/50 coin flip in a way that is disastrous for coordination.

## Claim 2: solving the game using shared randomness

Define fϵ(v)=v−(1−√ϵ)2√ϵ. Consider a pair of policies in which player i chooses Y if R<fϵ(Vi), and otherwise chooses X, where R∼Uniform([0,1]). Intuitively, each of these policies increases its chance of taking action Y as its observation of uy increases in a

smoothfashion, and they correlate their randomness so that they are likely to choose the same action. Now note a couple properties of this pair of policies:1. For uy≥1+√ϵ+ϵ, it is guaranteed that Vi,Vj≥1+√ϵ, so both players always take action Y.

2. Since fϵ is 12√ϵ-Lipschitz, and |Vi−Vj|≤2ϵ, the probability of the players taking different actions is at most √ϵ.

I will now show that the players' expected utility is at least max(1,uy)−2√ϵ−ϵ by case analysis:

Thus, the claim is proven. By setting ϵ sufficiently low, this pair of policies yields an expected utility arbitrarily close to max(1,uy) regardless of uy.

## Conclusion and directions for further research

Together, these claims show that there is a simple set of noisy coordination games (namely, the set of games described in the beginning of this post for all possible uy values) that is impossible to solve with only independent randomness, but which can be solved using shared randomness. Some notes on this:

Where to go from here? Roughly, my overall "plan" for formal decision theory consists of 3 steps:

1. Solve Cartesian cooperative decision theory problems where players reason about each other using something like reflective oracles.

2. Extend the solution in 1 to Cartesian multiplayer game theory problems where players have different utility functions and reason about each other using something like reflective oracles.

3. Extend the solution in 2 to a logically uncertain naturalized setting.

Step 1 has still not been solved. Previous writing on this includes this post which studies a setting with a single memoryless player (which is similar to a set of players who have the same utility function). The post shows (redundantly with the paper introducing the absent-minded driver problem as I later found out) that, if the player's policy is

globallyoptimal (i.e. it achieves the highest possible expected utility), then all actions that might be taken by that policy are CDT-optimal, assuming SIA probabilities. This second condition is a local optimality condition, so the post shows that global optimality implies local optimality.It would be highly desirable to find a similar but different local optimality property that implies a global optimality property. That would essentially be a way of deriving collective self-interest from individual self-interest when individuals have the same utility function and common priors.

As this current post shows, the globally optimal policy is

discontinuousas a function of the utilities involved, and no continuous approximation always yields a near-optimal expected utility. I expect this to hinder attempts to derive global optimality from local optimality, as it implies there is a valley of bad policies between decent policies and good ones.Introducing shared randomness here may help by preserving continuity. So a natural next step is to find useful local optimality properties in a cooperative setting where players have shared randomness.

## Appendix: extension to arbitrary normal-form cooperative games

The solution described in the section on claim 2 can be extended to arbitrary normal-form cooperative games where the players receive only noisy observations of the payoffs. Reading this appendix (which takes up the rest of this post) is unnecessary for understanding the main point of this post.

Let n≥1 be the number of players, Ai be player i's set of actions, and u:∏ni=1Ai→R be the shared unknown utility function over strategy profiles, whose minimum value is umin and whose maximum value is umax.

Fix 0<ϵ≤umax−umin. Let Vi:∏ni=1Ai→R be a "perturbed" version of u that player i observes; it must satisfy the property that for any strategy profile a, |Vi(a)−u(a)|≤ϵ.

To define the policies, we will first number the strategy profiles arbitrarily a1,…,am where m=∏ni=1|Ai|. Let c>0 be some number to be determined later. For j∈{1,…,m}, define

fj(v):=exp(cv(aj))∑mj′=1exp(cv(aj′)).

This defines, given any v∈∏ni=1Ai, a probability distribution over strategy profiles, since ∑mj=1fj(v)=1. Specifically, the distribution is a softmax. This distribution is more likely to select strategy profiles that v considers better, but has some chance of selecting every strategy profile.

Players will sample from this distribution using a source of shared randomness, R∼Uniform([0,1]). Define

g(v,r):=min{j∈{1,…,m}∣r≤∑jj′=1fj′(v)}

Now note that P(g(v,R)=j)=fj(v), i.e. g(v,R) is distributed according to fj(v). Define policies πi(v,r):=ag(v,r)i. That is, player i will play their appropriate action for strategy profile number g(Vi,R).

Roughly, we will now show 2 properties that are sufficient to establish that these policies are near-optimal:

## Players play according to ag(u,R) with high probability

First, we will show that, for all i and j, fj(Vi) is close to fj(u).

For all j∈{1,…,m}, since |Vi(aj)−u(aj)|≤ϵ, we have

exp(−cϵ)≤exp(cVi(aj))exp(cu(aj))≤exp(cϵ).

Therefore, for all j∈{1,…,m},

fj(Vi)fj(u)=exp(cVi(aj))exp(cu(aj))∑mj′=1exp(cu(aj′))∑mj′=1exp(cVi(aj′))≤exp(2cϵ).

By identical logic,

fj(u)fj(Vi)≤exp(2cϵ).

Now we will bound ∣∣∑jj′=1fj′(Vi)−∑jj′=1fj′(u)∣∣.

∣∣∑jj′=1fj′(Vi)−∑jj′=1fj′(u)∣∣

=∣∣∣∑jj′=1fj′(Vi)(1−fj′(u)fj′(Vi))∣∣∣

≤∑jj′=1fj′(Vi)∣∣∣1−fj′(u)fj′(Vi)∣∣∣

≤∑jj′=1fj′(Vi)max{exp(2cϵ)−1,1−exp(−2cϵ)}

≤∑jj′=1fj′(Vi)(exp(2cϵ)−1)

=exp(2cϵ)−1

For it to be the case that g(u,R)≠g(Vi,R), it must be the case that for some j,

R≤∑jj′=1fj′(u)↮R≤∑jj′=1fj′(Vi)

which implies

R∈ConvexHull({∑jj′=1fj′(u),∑jj′=1fj′(Vi)})

Due to the bound on ∣∣∑jj′=1fj′(Vi)−∑jj′=1fj′(u)∣∣, the measure of this hull is at most exp(2cϵ)−1. Furthermore, there are m hulls of this form (one for each j value), so the total measure of these hulls is at most m(exp(2cϵ)−1).

So, player i chooses action ag(u,R)i with probability at least 1−m(exp(2cϵ)−1). Thus, by the union bound, the players jointly choose the actions ag(u,R) with probability at least 1−nm(exp(2cϵ)−1).

## ag(u,R) is near-optimal in expectation

First we will prove a lemma.

Softmax lemma: For any c>0 and vector x of length m,∑mj=1exp(cxj)xj∑mj=1exp(cxj)≥maxj∈{1,…,m}xj−mec.

Proof:Let x∗ be the maximum of x. Now:

∑mj=1exp(cxj)(x∗−xj)∑mj=1exp(cxj)≤∑mj=1exp(cxj)(x∗−xj)exp(cx∗)=∑mj=1exp(−c(x∗−xj))(x∗−xj)

For any y, we have y≥logy+1. Therefore for any y, cy≥log(cy)+1=logy+logc+1⇔logy−cy≤−logc−1. By exponentiating both sides, yexp(−cy)≤1ec.

Applying this to the term from the previous inequality:

∑mj=1exp(−c(x∗−xj))(x∗−xj)≤∑mj=11ec=mec

At this point we have

∑mj=1exp(cxj)xj∑mj=1exp(cxj)=x∗−∑mj=1exp(cxj)(x∗−xj)∑mj=1exp(cxj)≥x∗−mec.

□

At this point the implication is straightforward. Since g(u,R) is distributed according to fj(u), we have

E[u(ag(u,R))]=∑mj=1fj(u)u(aj)=∑mj=1exp(cu(aj))u(aj)∑mj=1exp(cu(aj))≥umax−mec .

## Proving the result from these facts

At this point we have:

The first fact lets us quantify the expected difference between u(ag(u,R)) and u(π1(Vi,R),…,πn(Vn,R)). Since these random variables are equal with probability at least 1−nm(exp(2cϵ)−1), and their difference is bounded by umax−umin, their expected difference is at most nm(exp(2cϵ)−1)(umax−umin).

Combining this with the second inequality:

E[u(π1(V1,R),…,πn(Vn),R)]≥umax−mec−nm(exp(2cϵ)−1)(umax−umin)

To minimize mec+nm(exp(2cϵ)−1)(umax−umin), set

c:=12√enϵ(umax−umin)

This yields:

mec=2m√nϵ(umax−umin)e

Now note that

2cϵ=√ϵen(umax−umin)

Due to the fact that ϵ≤umax−umin and n≥0,

2cϵ≤1.

Because for any 0≤x≤1, exp(x)−1≤2x, we have

nm(exp(2cϵ)−1)(umax−umin)≤4nmcϵ(umax−umin)=2m√nϵ(umax−umin)e.

By combining inequalities and equalities so far:

E[u(π1(V1,R),…,πn(Vn,R))]≥umax−4m√nϵ(umax−umin)e.

The expected suboptimality goes to 0 as ϵ approaches 0.