A well-known issue in game theory is that of multiple Nash equilibria in coordination games.

For example, consider the following game. Players 1 and 2 both choose either "high" or "low". If both choose "high", they both get 10 utility; if both choose "low", they both get 5 utility; if they choose different actions, then they get no utility. There are 3 Nash equilibria: one where both always play "high", one where both always play "low", and one where each plays "high" with 1/3 probability and "low" with 2/3 probability. While (high, high) is obviously the best Nash equilibrium, unilaterally switching to high when the current equilibrium is (low, low) is probably unwise.

You could imagine TDT arguments based on symmetry between the different players to argue that "high" is the only rational choice, but it is easy to imagine asymmetric variants of this problem where the symmetry arguments are much less clear.

The presence of suboptimal Nash equilibria looks like a serious problem for reconciling individual and collective rationality, even when players have common payoffs. If everyone is going to play "low", then playing "low" is individually rational (at least according to CDT); however, the collective of agents fails to act rationally due to a coordination failure.

What I hoped to do before coming up with the idea in this post is to somehow reduce collective rationality to individual rationality. Can we prescribe individual rationality conditions to each player, such that if each player follows these conditions, then a near-optimal outcome for everyone is attained?

Somewhat surprisingly, the answer is "kind of." It certainly seems like solving coordination problems requires global optimization instead of just local optimization, but under appropriate conditions, local optimization is actually sufficient.

Problem setup

We will consider the setting of normal-form common-payoff games. Let $n$ be the number of players. Let $A$ be some finite set of actions; each player $i$ will select the action $A_i$. Let $U:A^n\to R$ be the shared utility function. Each player receives the same utility $U(a_1,\dots ,a_n)$.

I will now assume that the players play some number of practice rounds before the "real" round. These practice rounds are very similar to those in the fictitious play algorithm. Ontologically, what are these practice rounds? One interpretation is that they are actual rounds of the game that have been played in the past; another interpretation is that they are a sequence of analogous one-shot rounds played by agents who have more and more compute and are thus able to simulate previous rounds. (The second interpretation might seem strange, but this is essentially how logical inductors achieve generalization bounds in decision theory problems)

Let $T$ be the number of practice rounds. Let $A_i^t$ be the action selected by player $i$ in practice round $t$. I will assume $A_i=A_i^T$, i.e. the last practice round is the "real" round.

We will assume that, in each round $t$, some shared random number $R_t\sim Uniform\left(\right\{1,\dots ,n\left\}\right)$ is generated, and that players' policies in round $t$ may depend on this number.

How are players' policies represented? We will assume that each player has only black-box access to each others' actions in previous practice rounds. Let ${\pi }_i:List\left(A^n\right)\times \{1,\dots ,n\}\to \Delta A$ be player $i$'s policy, which selects an action distribution for player $i$ in round $t$ given knowledge of the actions in all previous rounds and of the current shared random number.

The generative model is now obvious: For each $t$ in sequence, sample $R_t\sim Uniform\left(\right\{1,\dots ,n\left\}\right)$ and then sample each $A_i^t\sim {\pi }_i(A_{1:n}^{1:t-1},R_t)$ independently, where the notation $A_{1:n}^{1:t-1}$ refers to the list $(A_{1:n}^1,\dots ,A_{1:n}^{t-1})$.

Given a set of policies, it is possible to compute, for each $t$, expected utilities at each time step (which are the expected utilities attained if $T=t$):

$$v_t\left({\pi }_{1:n}\right):=E\left[U\right(A_{1:n}^t\left)|{\pi }_{1:n}\right]$$

The limit ${lim}_{t\to \infty }{v}_t\left({\pi }_{1:n}\right)$ and corresponding $liminf$ and $limsup$ are interesting; they indicate how well a set of policies does in expectation after a large number of practice rounds.

Policies that solve the game

The policies we will consider are ones that usually stick with the same action they played in the last round, but sometimes switch to a different action, and are more likely to switch the worse the utility in the last round was.

Let $u_{min}$ be a lower bound on $U$. Let $\alpha >0$ be some "rationality parameter". Consider the following set of policies:

$${\pi }_i^{\alpha }(A_{1:n}^{1:t-1},R_t)=Uniform\left(A\right)\text{if}t=1$$ $${\pi }_i^{\alpha }(A_{1:n}^{1:t-1},R_t)=\delta \left(A_i^{t-1}\right)\text{if}t>1,R_t\ne i$$ $${\pi }_i^{\alpha }(A_{1:n}^{1:t-1},R_t)=e^{\alpha \cdot (u_{min}-U(A_{1:n}^{t-1}\left)\right)}\cdot Uniform\left(A\right)+(1-e^{\alpha \cdot (u_{min}-U(A_{1:n}^{t-1}\left)\right)})\cdot \delta \left(A_i^{t-1}\right)\text{otherwise}$$

where $\delta \left(a\right)$ is a delta distribution on $a$, and probability distributions are taken to be vectors.

These policies start out with each player selecting a random action. In each round, a random player is selected (according to $R_t$); this player switches their action to some uniformly random action with a probability that is lower the higher the utility in the previous round was, and otherwise sticks with the same action. Players other than the randomly selected player always stick with the same action.

An important aspect of these policies is that each player only does local optimization. That is, each player shifts their own action depending on the utility in the last round, such that over the course of many iterations they are more likely to take an action that attains a high utility given the other players' actions. Naively, one would expect a local optimization algorithm like this one to get stuck in traps such as the (low, low) Nash equilibrium, but this turns out not to be the case.

We will prove the following theorem:

Theorem 1: For all $ϵ>0$ there exists $\alpha$ such that ${lim}_{t\to \infty }{v}_t\left({\pi }_{1:n}^{\alpha }\right)\ge {max}_{a_{1:n}\in A^n}U\left(a_{1:n}\right)-ϵ$.

i.e. by setting $\alpha$ high enough, these policies achieve an arbitrarily-close-to-optimal expected utility in the limit.

Analyzing the process as a Markov chain

To prove this theorem, we can analyze the multi-round process with these policies as a Markov chain where the state is the action vector $A_{1:n}^t$. The transition function (giving the distribution of $A_{1:n}^{t+1}$ given $A_{1:n}^t$) is:

$$t^{\alpha }\left(a_{1:n}\right)(a_{1:i-1},a_i^{\prime },a_{i+1:n}):=\frac{e^{\alpha \cdot (u_{min}-U(a_{1:n}\left)\right)}}{n|A|}\text{if}{a}_i^{\prime }\ne a_i$$

$$t^{\alpha }\left(a_{1:n}\right)\left(a_{1:n}\right):=1-\sum _{a_i^{\prime }\ne a_i}t\left(a_{1:n}\right)(a_{1:i-1},a_i^{\prime },a_{i+1:n})$$

$$t^{\alpha }\left(a_{1:n}\right)\left(a_{1:n}^{\prime }\right):=0\text{if}{a}_{1:n}\text{and}{a}_{1:n}^{\prime }\text{differ on at least two elements}$$

Consider the following distribution over states:

$$p^{\alpha }\left(a_{1:n}\right):=\frac{e^{\alpha U\left(a_{1:n}\right)}}{{\sum }_{a^{\prime }\in A^n}{e}^{\alpha U\left(a_{1:n}^{\prime }\right)}}$$

i.e. it is a softmax that is more likely to select states with higher utilities.

We will show:

Lemma 1: $p$ is the unique stationary distribution of the Markov chain defined by $t$.

Proof:

It is well-known (e.g. see this Wikipedia article) that an ergodic Markov chain satisfying detailed balance (a condition defined later) with respect to a probability distribution over states has this distribution of states as the unique stationary distribution.

The Markov chain is aperiodic, since every state has a nonzero probability of transitioning to itself. Additionally, it is irreducible (i.e. it is possible to get from any state to any other state), since any action in the state can change to any other action with nonzero probability while leaving the other actions fixed. Therefore, the Markov chain is ergodic.

This Markov chain satisfies a detailed balance condition relative to the state distribution $p$. Specifically, for any states $a_{1:n}$ and $a_{1:n}^{\prime }$:

$$p^{\alpha }\left(a_{1:n}\right)t^{\alpha }\left(a_{1:n}\right)\left(a_{1:n}^{\prime }\right)=p^{\alpha }\left(a_{1:n}^{\prime }\right)t^{\alpha }\left(a_{1:n}^{\prime }\right)\left(a_{1:n}\right)$$

i.e. if a state is sampled from $p$ then transitioned once, the probability of a transition from $a_{1:n}$ to $a_{1:n}^{\prime }$ equals the probability of a transition from $a_{1:n}^{\prime }$ to $a_{1:n}$.

The proof of this detailed balance property proceeds by case analysis on $a_{1:n}$ and $a_{1:n}^{\prime }$.

1. If $a_{1:n}=a_{1:n}^{\prime }$, then the condition is trivial.
2. If $a_{1:n}$ and $a_{1:n}^{\prime }$ differ on more than one element, then both transition probabilities are 0, so the condition is trivial.
3. If they differ on a single element $i$, then:

$$p^{\alpha }\left(a_{1:n}\right)t^{\alpha }\left(a_{1:n}\right)\left(a_{1:n}^{\prime }\right)=\frac{e^{\alpha U\left(a_{1:n}\right)}}{{\sum }_{b_{1:n}\in A^n}{e}^{\alpha U\left(b_{1:n}\right)}}\frac{e^{\alpha \cdot (u_{min}-U(a_{1:n}\left)\right)}}{n|A|}$$ $$=\frac{e^{\alpha u_{min}}}{n|A|{\sum }_{b_{1:n}\in A^n}{e}^{\alpha U\left(b_{1:n}\right)}}$$

and similarly

$$p^{\alpha }\left(a_{1:n}^{\prime }\right)t^{\alpha }\left(a_{1:n}^{\prime }\right)\left(a_{1:n}\right)=\frac{e^{\alpha U\left(a_{1:n}^{\prime }\right)}}{{\sum }_{b_{1:n}\in A^n}{e}^{\alpha U\left(b_{1:n}\right)}}\frac{e^{\alpha \cdot (u_{min}-U(a_{1:n}^{\prime }\left)\right)}}{n|A|}$$ $$=\frac{e^{\alpha u_{min}}}{n|A|{\sum }_{b_{1:n}\in A^n}{e}^{\alpha U\left(b_{1:n}\right)}}.$$

Since the Markov chain is ergodic and satisfies detailed balance with respect to $p^{\alpha }$, it follows that $p^{\alpha }$ is the unique stationary distribution of the Markov chain.

$\square$

Now we will prove Theorem 1.

Theorem 1: For all $ϵ>0$ there exists $\alpha$ such that ${lim}_{t\to \infty }{v}_t\left({\pi }_{1:n}^{\alpha }\right)\ge {max}_{a_{1:n}\in A^n}U\left(a_{1:n}\right)-ϵ$.

Proof:

Clearly, ${lim}_{t\to \infty }{v}_t\left({\pi }_{1:n}^{\alpha }\right)=E_{a_{1:n}\sim p^{\alpha }}\left[U\right(a_{1:n}\left)\right]$, since $p^{\alpha }$ is the unique stationary distribution of $A_{1:n}^t$ considered as a Markov chain.

Define $u^{\ast }:={max}_{a_{1:n}\in A^n}U\left(a_{1:n}\right)$, i.e. the highest achievable utility. Define $u^{\prime }$ to be the second-highest achievable utility.

At this point, we need only set $\alpha$ to be large enough that the $p^{\alpha }$ assigns almost all of its probability mass to optimal states. The argument that this is possible to do follows.

Fix $ϵ>0$. Set $\alpha :=\frac{n\log |A|+\log (u^{\ast }-u_{min})-\log ϵ}{u^{\ast }-u^{\prime }}$.

Let $a_{1:n}^{\ast }$ be an optimal action profile, and let $a_{1:n}^{\prime }$ be a non-optimal action profile. We have

$$\frac{p^{\alpha }\left(a_{1:n}^{\ast }\right)}{p^{\alpha }\left(a_{1:n}^{\prime }\right)}=e^{\alpha \left(U\right(a_{1:n}^{\ast })-U(a_{1:n}^{\prime }\left)\right)}\ge e^{\alpha (u^{\ast }-u^{\prime })}=\frac{|A{|}^n(u^{\ast }-u_{min})}{ϵ}$$

Since there is at least one optimal state and fewer than $|A{|}^n$ non-optimal states, the ratio between the probability (under $p^{\alpha }$) of a state being optimal and the probability of a state being non-optimal is at least $\frac{u^{\ast }-u_{min}}{ϵ}$. Since in general $\frac{x}{1+x}\ge 1-\frac{1}{x}$ for positive $x$, this means that the probability of a state being optimal is at least $1-\frac{ϵ}{u^{\ast }-u_{min}}$. A non-optimal state has utility at least $u_{min}$, so the overall expected suboptimality (i.e. difference between $u^{\ast }$ and $u\left(a_{1:n}\right)$) is at most $ϵ$, as desired.

$\square$

Extension to non-common-payoff games

The policies defined above can be extended to play non-common-payoff games. Specifically, each agent can have a higher likelihood of switching action in each round if their own utility is lower. Unfortunately, this results in mutual defection in a prisoner's dilemma; while I won't present a detailed analysis here, the gist of the argument is that (C, C) is much more likely to switch into (C, D) or (D, C), than (C, D) or (D, C) is to switch into (C, C). So a different approach than this one will be needed for achieving Pareto optimal outcomes in non-common-payoff games.

Conclusion

In this post I have shown that, in common-payoff games under a multi-round structure, there is a set of policies that only does local optimization but which, together, yield a globally near-optimal outcome. This is important because getting global optimality from local optimization is required for decision theory (i.e. each agent taking an action based on its own expected utility) to produce Pareto optimal outcomes in common-payoff games.

In a previous post on coordination games, I presented a plan for solving formal decision theory:

1. Solve Cartesian common-payoff 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.

This post has done something pretty close to solving 1, with the multi-round structure taking the place of reflective oracles. Unfortunately, step 2 fails since the solution method does not extend to non-common-payoff games. So it appears that, for my plan to work, 1 must be solved in a different way that can be extended to also solve non-common-payoff games.

Alternatively, the problem of non-common-payoff games may be attacked directly, though this seems difficult given that non-common-payoff games are more complex than common-payoff games, and include all the dynamics present in common-payoff games. But perhaps restricted subsets of general games, other than the set of common-payoff games, can be found and solved.