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 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 \leq u_y \leq 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 - \epsilon, u_y + \epsilon] for some small \epsilon > 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 \mathrm{Uniform}([0, 1]). Then there is a pair of policies that achieves expected utility at least \max(1, u_y) - 2\sqrt{\epsilon} - \epsilon 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 \epsilon > 0. Let \pi_1, \pi_2 : \mathbb{R} \rightarrow [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(u) := \mathrm{Uniform}([u-\epsilon,u+\epsilon]) to be the function mapping u_y to the resulting V_i distribution. Define \tau_i(u) := \mathbb{E}_{v \sim q(u)}[\pi_i(v)]. This is defined so that \tau_i(u_y) 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(u_1) and q(u_2) is at most \frac{|u_1 - u_2|}{\epsilon}. Thus, since \pi_i is bounded between 0 and 1, \tau_i is \frac{1}{\epsilon}-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(0) \geq 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(2) \leq 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(u) = 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} \leq \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_\epsilon(v) = \frac{v - (1 - \sqrt{\epsilon})}{2\sqrt{\epsilon}}. Consider a pair of policies in which player i chooses Y if R < f_\epsilon(V_i), and otherwise chooses X, where R \sim \mathrm{Uniform}([0, 1]). 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 \geq 1 + \sqrt{\epsilon} + \epsilon, it is guaranteed that V_i, V_j \geq 1 + \sqrt{\epsilon}, so both players always take action Y.
2. Since f_\epsilon is \frac{1}{2\sqrt{\epsilon}}-Lipschitz, and |V_i - V_j| \leq 2 \epsilon, the probability of the players taking different actions is at most \sqrt{\epsilon}. I will now show that the players’ expected utility is at least \max(1, u_y) - 2\sqrt{\epsilon} - \epsilon by case analysis:

• Suppose u_y \geq 1 + \sqrt{\epsilon} + \epsilon. Then by property 1, both players are guaranteed to take action Y, so they achieve expected utility u_y \geq \max(1, u_y) - 2\sqrt{\epsilon} - \epsilon.

• Suppose u_y < 1 + \sqrt{\epsilon} + \epsilon. By property 2, the players choose the same action with probability at least 1 - \sqrt{\epsilon}, and taking the same action yields a utility of at least 1, so they achieve expected utility at least 1 - \sqrt{\epsilon}. Due to the bound on u_y, this is at least \max(1, u_y) - 2\sqrt{\epsilon} - \epsilon. Thus, the claim is proven. By setting \epsilon 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 \geq 1 be the number of players, \mathcal{A}i be player i’s set of actions, and u : \prod{i=1}^n \mathcal{A}i \rightarrow \mathbb{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 < \epsilon \leq u_{\max}-u_{\min}. Let V_i : \prod_{i=1}^n \mathcal{A}i \rightarrow \mathbb{R} be a "perturbed" version of u that player i observes; it must satisfy the property that for any strategy profile \mathbf{a}, |V_i(\mathbf{a}) - u(\mathbf{a})| \leq \epsilon. To define the policies, we will first number the strategy profiles arbitrarily \mathbf{a}^1, \ldots, \mathbf{a}^m where m = \prod{i=1}^n |\mathcal{A}i|. Let c > 0 be some number to be determined later. For j \in {1, \ldots, m}, define f_j(v) := \frac{\exp(cv(\mathbf{a}^j))}{\sum{j'=1}^m \exp(cv(\mathbf{a}^{j'}))}. This defines, given any v \in \prod_{i=1}^n \mathcal{A}i, a probability distribution over strategy profiles, since \sum{j=1}^m f_j(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 \sim \mathrm{Uniform}([0, 1]). Define g(v, r) := \min\left{j \in {1, \ldots, m} \mid r \leq \sum_{j'=1}^j f_{j'}(v)\right} Now note that P(g(v, R) = j) = f_j(v), i.e.g(v, R) is distributed according to f_j(v). Define policies \pi_i(v, r) := \mathbf{a}^{g(v,r)}_i. 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 \mathbf{a}^{g(u, R)}, i.e. for all i, \pi_i(V_i, R) = \mathbf{a}_i^{g(u, R)}.

• The strategy profile \mathbf{a}^{g(u, R)} is near-optimal in expectation, i.e.\mathbb{E}[u(\mathbf{a}^{g(u, R)})] is close to u_{\max}.

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

First, we will show that, for all i and j, f_j(V_i) is close to f_j(u). For all j \in {1, \ldots, m}, since |V_i(\mathbf{a}^j) - u(\mathbf{a}^j)| \leq \epsilon, we have \exp(-c\epsilon) \leq \frac{\exp(cV_i(\mathbf{a}^{j}))}{\exp(cu(\mathbf{a}^{j}))} \leq \exp(c\epsilon). Therefore, for all j \in {1, \ldots, m}, \frac{f_j(V_i)}{f_j(u)} = \frac{\exp(cV_i(\mathbf{a}^j))}{\exp(cu(\mathbf{a}^j))} \frac{\sum_{j'=1}^m \exp(cu(\mathbf{a}^{j'}))}{\sum_{j'=1}^m \exp(cV_i(\mathbf{a}^{j'}))} \leq \exp(2c\epsilon). By identical logic, \frac{f_j(u)}{f_j(V_i)} \leq \exp(2c\epsilon). Now we will bound \left|\sum_{j'=1}^jf_{j'}(V_i)-\sum_{j'=1}^jf_{j'}(u)\right|. \left|\sum_{j'=1}^jf_{j'}(V_i)-\sum_{j'=1}^jf_{j'}(u)\right| = \left|\sum_{j'=1}^j f_{j'}(V_i)\left(1 - \frac{f_{j'}(u)}{f_{j'}(V_i)}\right)\right| \leq \sum_{j'=1}^j f_{j'}(V_i)\left|1 - \frac{f_{j'}(u)}{f_{j'}(V_i)}\right| \leq \sum_{j'=1}^j f_{j'}(V_i) \max{\exp(2c\epsilon)-1,1-\exp(-2c\epsilon)} \leq \sum_{j'=1}^j f_{j'}(V_i) (\exp(2c\epsilon)-1) = \exp(2c\epsilon)-1 For it to be the case that g(u, R) \neq g(V_i, R), it must be the case that for some j, R \leq \sum_{j'=1}^j f_{j'}(u) \not\leftrightarrow R \leq \sum_{j'=1}^j f_{j'}(V_i) which implies R \in \mathrm{ConvexHull}\left(\left{\sum_{j'=1}^j f_{j'}(u), \sum_{j'=1}^j f_{j'}(V_i)\right}\right) Due to the bound on \left|\sum_{j'=1}^jf_{j'}(V_i)-\sum_{j'=1}^jf_{j'}(u)\right|, the measure of this hull is at most \exp(2c\epsilon)-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\epsilon)-1). So, player i chooses action \mathbf{a}^{g(u, R)}_i with probability at least 1-m(\exp(2c\epsilon)-1). Thus, by the union bound, the players jointly choose the actions \mathbf{a}^{g(u, R)} with probability at least 1-nm(\exp(2c\epsilon)-1).

\mathbf{a}^{g(u, R)} is near-optimal in expectation

First we will prove a lemma.
Softmax lemma: For any c > 0 and vector \mathbf{x} of length m, \frac{\sum_{j=1}^m \exp(cx_j)x_j}{\sum_{j=1}^m \exp(cx_j)} \geq \max_{j \in {1, \ldots, m}} x_j - \frac{m}{ec}. Proof: Let x^* be the maximum of \mathbf{x}. Now: \frac{\sum_{j=1}^m \exp(cx_j)(x^-x_j)}{\sum_{j=1}^m \exp(cx_j)} \leq \frac{\sum_{j=1}^m \exp(cx_j)(x^-x_j)}{\exp(cx^)} = \sum_{j=1}^m \exp(-c(x^-x_j))(x^-x_j) For any y, we have y \geq \log y + 1. Therefore for any y, cy \geq \log (cy) + 1 = \log y + \log c + 1 \Leftrightarrow \log y - cy \leq -\log c -1. By exponentiating both sides, y\exp(-cy) \leq \frac{1}{ec}. Applying this to the term from the previous inequality: \sum_{j=1}^m \exp(-c(x^-x_j))(x^-x_j) \leq \sum_{j=1}^m \frac{1}{ec} = \frac{m}{ec} At this point we have \frac{\sum_{j=1}^m \exp(cx_j)x_j}{\sum_{j=1}^m \exp(cx_j)} = x^ - \frac{\sum_{j=1}^m \exp(cx_j)(x^-x_j)}{\sum_{j=1}^m \exp(cx_j)} \geq x^-\frac{m}{ec}. \square At this point the implication is straightforward. Since g(u, R) is distributed according to f_j(u), we have \mathbb{E}[u(\mathbf{a}^{g(u,R)})] = \sum_{j=1}^m f_j(u) u(\mathbf{a}^j) = \frac{\sum_{j=1}^m \exp(cu(\mathbf{a}^j))u(\mathbf{a}^j)}{\sum_{j=1}^m \exp(cu(\mathbf{a}^j))} \geq u_{\max}-\frac{m}{ec} .

Proving the result from these facts

At this point we have:

• Players play according to \mathbf{a}^{g(u, R)} with probability at least 1 - nm(\exp(2c\epsilon)-1).

• \mathbb{E}[u(\mathbf{a}^{g(u, R)})] \geq u_{\max} - \frac{m}{ec}. The first fact lets us quantify the expected difference between u(\mathbf{a}^{g(u, R)}) and u(\pi_1(V_i, R), \ldots, \pi_n(V_n, R)). Since these random variables are equal with probability at least 1 - nm(\exp(2c\epsilon)-1), and their difference is bounded by u_{\max} - u_{\min}, their expected difference is at most nm(\exp(2c\epsilon)-1)(u_{\max}-u_{\min}). Combining this with the second inequality: \mathbb{E}[u(\pi_1(V_1, R), \ldots, \pi_n(V_n), R)] \geq u_{\max} - \frac{m}{ec} - nm(\exp(2c\epsilon)-1)(u_{\max}-u_{\min}) To minimize \frac{m}{ec} + nm(\exp(2c\epsilon)-1)(u_{\max}-u_{\min}), set c := \frac{1}{2\sqrt{en\epsilon (u_{\max}-u_{\min})}} This yields: \frac{m}{ec} = 2m\sqrt{\frac{n\epsilon(u_{\max}-u_{\min})}{e}} Now note that 2c\epsilon = \sqrt{\frac{\epsilon}{en(u_{\max}-u_{\min})}} Due to the fact that \epsilon \leq u_{\max} - u_{\min} and n \geq 0, 2c\epsilon \leq 1. Because for any 0 \leq x \leq 1, \exp(x) - 1 \leq 2x, we have nm(\exp(2c\epsilon)-1)(u_{\max}-u_{\min}) \leq 4nmc\epsilon(u_{\max}-u_{\min}) = 2m\sqrt{\frac{n\epsilon(u_{\max}-u_{\min})}{e}}. By combining inequalities and equalities so far: \mathbb{E}[u(\pi_1(V_1, R), \ldots, \pi_n(V_n, R))] \geq u_{\max} - 4m\sqrt{\frac{n\epsilon(u_{\max}-u_{\min})}{e}}. The expected suboptimality goes to 0 as \epsilon approaches 0.