Buridan's ass in coordination games

post by jessicata (jessica.liu.taylor) · 2018-07-16T02:51:30.561Z · LW · GW · 26 comments

Contents

  Claim 1: impossibility of solving the game using independent randomness 
  Claim 2: solving the game using shared randomness 
  Conclusion and directions for further research
  Appendix: extension to arbitrary normal-form cooperative games 
    Players play according to ag(u,R) with high probability 
    ag(u,R) is near-optimal in expectation 
    Proving the result from these facts 
None
26 comments

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 $u_y$ utility for some $0\le u_y\le 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 $u_y$, but not after knowing $u_y$.

An optimal policy pair is for each to pick X if $u_y<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 $u_y$, but instead each receives an independent observation $V_i$ (player 1 sees $V_1$, player 2 sees $V_2$), each of which is drawn uniformly from the range $[u_y-ϵ,u_y+ϵ]$ for some small $ϵ>0$. If both players follow the policy of choosing X if and only if their observation of $u_y$ is less than 1, then if $u_y$ 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 actions independently given their observations can simultaneously guarantee an expected utility greater than $max(1,u_y)-0.5$ for all $u_y\in [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 $u_y$, each player also gets to observe a random number $R\sim Uniform\left(\right[0,1\left]\right)$. Then there is a pair of policies that achieves expected utility at least $max(1,u_y)-2\sqrt{ϵ}-ϵ$ regardless of $u_y$ .

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 ${\pi }_1,{\pi }_2:R\to [0,1]$ be Lesbegue measurable functions representing the two players' policies, which map $V_i$ to the player's probability of choosing action Y.

Define $q\left(u\right):=Uniform\left(\right[u-ϵ,u+ϵ\left]\right)$ to be the function mapping $u_y$ to the resulting $V_i$ distribution.

Define ${\tau }_i\left(u\right):=E_{v\sim q\left(u\right)}\left[{\pi }_i\right(v\left)\right]$. This is defined so that ${\tau }_i\left(u_y\right)$ equals player $i$'s overall probability of choosing action Y.

For $u_1,u_2\in [0,2]$, note that the total variation distance between $q\left(u_1\right)$ and $q\left(u_2\right)$ is at most $\frac{|u_1-u_2|}{ϵ}$. Thus, since ${\pi }_i$ is bounded between 0 and 1, ${\tau }_i$ is $\frac{1}{ϵ}$-Lipschitz and therefore continuous.

I will now show that, for some $u_y$, the players achieve expected utility at most $max(1,u_y)-0.5$ by case analysis on ${\tau }_1$:

• If ${\tau }_1\left(0\right)\ge 0.5$ then at most 0.5 expected utility is achieved when $u_y=0$ (since at most 1 utility is achieved when player 1 chooses action X, and no utility is achieved when player 1 chooses action Y).
• If ${\tau }_1\left(2\right)\le 0.5$, then at most 1.5 expected utility is achieved when $u_y=2$ (since at most 1 utility is achieved when player 1 chooses action X, and at most 2 utility is achieved when player 1 chooses action Y).
• If neither of the two above cases hold, then by continuity of ${\tau }_1$ and the intermediate value theorem, there exists some $u\in [0,2]$ with ${\tau }_1\left(u\right)=0.5$. When $u_y=u$, since the two players choose actions independently, there is a 0.5 probability that they select the same action, ensuring that they achieve at most $\frac{max(1,u_y)}{2}\le max(1,u_y)-0.5$ expected utility.

Thus, claim 1 is proven. This proof method bears resemblance to the problem faced by Buridan's ass: in the third case, some $u_y$ value is found so that the "policy" ${\tau }_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_{ϵ}\left(v\right)=\frac{v-(1-\sqrt{ϵ})}{2\sqrt{ϵ}}$. Consider a pair of policies in which player $i$ chooses Y if $R<f_{ϵ}\left(V_i\right)$, and otherwise chooses X, where $R\sim Uniform\left(\right[0,1\left]\right)$. Intuitively, each of these policies increases its chance of taking action Y as its observation of $u_y$ increases in a smooth fashion, 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 $u_y\ge 1+\sqrt{ϵ}+ϵ$, it is guaranteed that $V_i,V_j\ge 1+\sqrt{ϵ}$, so both players always take action Y.

2. Since $f_{ϵ}$ is $\frac{1}{2\sqrt{ϵ}}$-Lipschitz, and $|V_i-V_j|\le 2ϵ$, the probability of the players taking different actions is at most $\sqrt{ϵ}$.

I will now show that the players' expected utility is at least $max(1,u_y)-2\sqrt{ϵ}-ϵ$ by case analysis:

• Suppose $u_y\ge 1+\sqrt{ϵ}+ϵ$. Then by property 1, both players are guaranteed to take action Y, so they achieve expected utility $u_y\ge max(1,u_y)-2\sqrt{ϵ}-ϵ$.
• Suppose $u_y<1+\sqrt{ϵ}+ϵ$. By property 2, the players choose the same action with probability at least $1-\sqrt{ϵ}$, and taking the same action yields a utility of at least 1, so they achieve expected utility at least $1-\sqrt{ϵ}$. Due to the bound on $u_y$, this is at least $max(1,u_y)-2\sqrt{ϵ}-ϵ$.

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

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 $u_y$ values) that is impossible to solve with only independent randomness, but which can be solved using shared randomness. Some notes on this:

• The proof of claim 1 only used the fact that ${\tau }_1$ is continuous. So even without noise, if the players' policies are a continuous function of the utility $u_y$, the same problem occurs.
• A pair of Bayesians playing this coordination game who have a prior over $u_y$ have no need for randomization, independent or joint. The goal of achieving a high expected utility regardless of $u_y$ most clearly makes sense if $u_y$ is selected adversarially (to maximize regret). It also makes sense if the environment is hard to model in a way that makes selection of a policy with a low rate of "ties" difficult. The comparison between the shared randomness solution and the Bayesian solution is similar to the comparison between randomized Quicksort and a "Bayesian" variant of Quicksort that selects pivots based on some expected distribution of inputs. While the Bayesian solution works better than the randomized solution when the prior over the input distribution is accurate, the randomized solution is simpler, is amenable to proofs, and works well even under adversarial conditions.

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 globally optimal (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 discontinuous as 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\ge 1$ be the number of players, $A_i$ be player $i$'s set of actions, and $u:{\prod }_{i=1}^n{A}_i\to R$ be the shared unknown utility function over strategy profiles, whose minimum value is $u_{min}$ and whose maximum value is $u_{max}$.

Fix $0<ϵ\le u_{max}-u_{min}$. Let $V_i:{\prod }_{i=1}^n{A}_i\to R$ be a "perturbed" version of $u$ that player $i$ observes; it must satisfy the property that for any strategy profile $a$, $|V_i\left(a\right)-u\left(a\right)|\le ϵ$.

To define the policies, we will first number the strategy profiles arbitrarily $a^1,\dots ,a^m$ where $m={\prod }_{i=1}^n|A_i|$. Let $c>0$ be some number to be determined later. For $j\in \{1,\dots ,m\}$, define

$f_j\left(v\right):=\frac{\exp \left(cv\right(a^j\left)\right)}{{\sum }_{j^{\prime }=1}^m\exp \left(cv\right(a^{j^{\prime }}\left)\right)}$.

This defines, given any $v\in {\prod }_{i=1}^n{A}_i$, a probability distribution over strategy profiles, since ${\sum }_{j=1}^m{f}_j\left(v\right)=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\sim Uniform\left(\right[0,1\left]\right)$. Define

$g(v,r):=min\left\{j\in \{1,\dots ,m\}\mid r\le {\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(v\right)\right\}$

Now note that $P\left(g\right(v,R)=j)=f_j\left(v\right)$, i.e. $g(v,R)$ is distributed according to $f_j\left(v\right)$. Define policies ${\pi }_i(v,r):=a_i^{g(v,r)}$. That is, player $i$ will play their appropriate action for strategy profile number $g(V_i,R)$.

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

• With high probability, the players play according to $a^{g(u,R)}$, i.e. for all $i$, ${\pi }_i(V_i,R)=a_i^{g(u,R)}$.
• The strategy profile $a^{g(u,R)}$ is near-optimal in expectation, i.e. $E\left[u\right(a^{g(u,R)}\left)\right]$ is close to $u_{max}$.

Players play according to $a^{g(u,R)}$ with high probability

First, we will show that, for all $i$ and $j$, $f_j\left(V_i\right)$ is close to $f_j\left(u\right)$.

For all $j\in \{1,\dots ,m\}$, since $|V_i\left(a^j\right)-u\left(a^j\right)|\le ϵ$, we have

$\exp (-cϵ)\le \frac{\exp \left(c{V}_i\right(a^j\left)\right)}{\exp \left(cu\right(a^j\left)\right)}\le \exp \left(cϵ\right)$.

Therefore, for all $j\in \{1,\dots ,m\}$,

$\frac{f_j\left(V_i\right)}{f_j\left(u\right)}=\frac{\exp \left(c{V}_i\right(a^j\left)\right)}{\exp \left(cu\right(a^j\left)\right)}\frac{{\sum }_{j^{\prime }=1}^m\exp \left(cu\right(a^{j^{\prime }}\left)\right)}{{\sum }_{j^{\prime }=1}^m\exp \left(c{V}_i\right(a^{j^{\prime }}\left)\right)}\le \exp \left(2cϵ\right)$.

By identical logic,

$\frac{f_j\left(u\right)}{f_j\left(V_i\right)}\le \exp \left(2cϵ\right)$.

Now we will bound $\left|{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)-{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(u\right)\right|$.

$\left|{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)-{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(u\right)\right|$

$=\left|{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)\left(1-\frac{f_{j^{\prime }}\left(u\right)}{f_{j^{\prime }}\left(V_i\right)}\right)\right|$

$\le {\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)\left|1-\frac{f_{j^{\prime }}\left(u\right)}{f_{j^{\prime }}\left(V_i\right)}\right|$

$\le {\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)max\left\{\exp \right(2cϵ)-1,1-\exp (-2cϵ\left)\right\}$

$\le {\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)\left(\exp \right(2cϵ)-1)$

$=\exp \left(2cϵ\right)-1$

For it to be the case that $g(u,R)\ne g(V_i,R)$, it must be the case that for some $j$,

$R\le {\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(u\right)\nleftrightarrow R\le {\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)$

which implies

$R\in ConvexHull\left(\left\{{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(u\right),{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)\right\}\right)$

Due to the bound on $\left|{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(V_i\right)-{\sum }_{j^{\prime }=1}^j{f}_{j^{\prime }}\left(u\right)\right|$, the measure of this hull is at most $\exp \left(2cϵ\right)-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\left(\exp \right(2cϵ)-1)$.

So, player $i$ chooses action $a_i^{g(u,R)}$ with probability at least $1-m\left(\exp \right(2cϵ)-1)$. Thus, by the union bound, the players jointly choose the actions $a^{g(u,R)}$ with probability at least $1-nm\left(\exp \right(2cϵ)-1)$.

$a^{g(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$,

$\frac{{\sum }_{j=1}^m\exp \left(c{x}_j\right)x_j}{{\sum }_{j=1}^m\exp \left(c{x}_j\right)}\ge {max}_{j\in \{1,\dots ,m\}}{x}_j-\frac{m}{ec}$.

Proof:

Let $x^{\ast }$ be the maximum of $x$. Now:

$\frac{{\sum }_{j=1}^m\exp \left(c{x}_j\right)(x^{\ast }-x_j)}{{\sum }_{j=1}^m\exp \left(c{x}_j\right)}\le \frac{{\sum }_{j=1}^m\exp \left(c{x}_j\right)(x^{\ast }-x_j)}{\exp \left(c{x}^{\ast }\right)}={\sum }_{j=1}^m\exp (-c(x^{\ast }-x_j\left)\right)(x^{\ast }-x_j)$

For any $y$, we have $y\ge \log y+1$. Therefore for any $y$, $cy\ge \log \left(cy\right)+1=\log y+\log c+1\iff \log y-cy\le -\log c-1$. By exponentiating both sides, $y\exp (-cy)\le \frac{1}{ec}$.

Applying this to the term from the previous inequality:

${\sum }_{j=1}^m\exp (-c(x^{\ast }-x_j\left)\right)(x^{\ast }-x_j)\le {\sum }_{j=1}^m\frac{1}{ec}=\frac{m}{ec}$

At this point we have

$\frac{{\sum }_{j=1}^m\exp \left(c{x}_j\right)x_j}{{\sum }_{j=1}^m\exp \left(c{x}_j\right)}=x^{\ast }-\frac{{\sum }_{j=1}^m\exp \left(c{x}_j\right)(x^{\ast }-x_j)}{{\sum }_{j=1}^m\exp \left(c{x}_j\right)}\ge x^{\ast }-\frac{m}{ec}$.

$\square$

At this point the implication is straightforward. Since $g(u,R)$ is distributed according to $f_j\left(u\right)$, we have

$E\left[u\right(a^{g(u,R)}\left)\right]={\sum }_{j=1}^m{f}_j\left(u\right)u\left(a^j\right)=\frac{{\sum }_{j=1}^m\exp \left(cu\right(a^j\left)\right)u\left(a^j\right)}{{\sum }_{j=1}^m\exp \left(cu\right(a^j\left)\right)}\ge u_{max}-\frac{m}{ec}$ .

Proving the result from these facts

At this point we have:

• Players play according to $a^{g(u,R)}$ with probability at least $1-nm\left(\exp \right(2cϵ)-1)$.
• $E\left[u\right(a^{g(u,R)}\left)\right]\ge u_{max}-\frac{m}{ec}$.

The first fact lets us quantify the expected difference between $u\left(a^{g(u,R)}\right)$ and $u\left({\pi }_1\right(V_i,R),\dots ,{\pi }_n(V_n,R\left)\right)$. Since these random variables are equal with probability at least $1-nm\left(\exp \right(2cϵ)-1)$, and their difference is bounded by $u_{max}-u_{min}$, their expected difference is at most $nm\left(\exp \right(2cϵ)-1)(u_{max}-u_{min})$.

Combining this with the second inequality:

$E\left[u\right({\pi }_1(V_1,R),\dots ,{\pi }_n\left(V_n\right),R\left)\right]\ge u_{max}-\frac{m}{ec}-nm\left(\exp \right(2cϵ)-1)(u_{max}-u_{min})$

To minimize $\frac{m}{ec}+nm\left(\exp \right(2cϵ)-1)(u_{max}-u_{min})$, set

$c:=\frac{1}{2\sqrt{enϵ(u_{max}-u_{min})}}$

This yields:

$\frac{m}{ec}=2m\sqrt{\frac{nϵ(u_{max}-u_{min})}{e}}$

Now note that

$2cϵ=\sqrt{\frac{ϵ}{en(u_{max}-u_{min})}}$

Due to the fact that $ϵ\le u_{max}-u_{min}$ and $n\ge 0$,

$2cϵ\le 1$.

Because for any $0\le x\le 1$, $\exp \left(x\right)-1\le 2x$, we have

$nm\left(\exp \right(2cϵ)-1)(u_{max}-u_{min})\le 4nmcϵ(u_{max}-u_{min})=2m\sqrt{\frac{nϵ(u_{max}-u_{min})}{e}}$.

By combining inequalities and equalities so far:

$E\left[u\right({\pi }_1(V_1,R),\dots ,{\pi }_n(V_n,R)\left)\right]\ge u_{max}-4m\sqrt{\frac{nϵ(u_{max}-u_{min})}{e}}$.

The expected suboptimality goes to 0 as $ϵ$ approaches 0.

26 comments

Comments sorted by top scores.