Reducing collective rationality to individual optimization in common-payoff games using MCMC

[jessicata]

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 ¹⁄₃ probability and “low” with ²⁄₃ 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.

[Rohin Shah]

I like this, it’s an explicit construction that demonstrates how you can play with the explore-exploit tradeoff in multiagent settings. Note that when α is set to be very high (the condition in which we get near-optimal outcomes in the limit), there is very little exploration, and so it will take a long time before we actually find the optimal outcome in the first place. It seems like this would make it hard to use in practice. Are you planning to use reflective oracles to replace the exploration here with reasoning about other agents? Or perhaps you think the slow exploration is not a problem for some reason?

[jessicata]

The approach most similar to this that is actually practical is MCMC optimization, which is practical for, among other things, program synthesis. I did not use that for this post since it would require agents to compute counterfactuals, but it is significantly more efficient in practice.

I’m currently trying to solve the theoretical decision theory problem rather than create usable algorithms. It would be pretty great to have a mathematical formalization of the correct decision theory even if it takes exponential time to run.

The problem with using reflective oracles is that this means the agents’ actions are independent, but, based on this post, the agents’ actions need to be correlated with each other to get a high score, if each policy is a continuous functions of the utility function. Correlated reflective oracles seem like they might help, but they are essentially a superset of ordinary reflective oracles, so using them can’t ensure that actions are correlated.

There might be some variant of reflective oracles that does work; a problem with this is that the algorithm in this post is “sticky”, which seems like an obstacle to deriving an agent’s policy based on their beliefs about others.

[cousin_it]

You could generalize to games where all players can achieve their best possible utilities by coordinating, and these utilities don’t have to be symmetric. For example, a coordination game with (5,5) and (10,20). Maybe your proof already works for this case.

Then you could try generalizing to games where some subset of players can jointly enforce their best possible utilities regardless of what other players do, but unfortunately that fails. For example, imagine three people, one of whom must be sacrificed to Cthulhu so the other two may live. The person to be killed is chosen by majority vote, and in case of tie they all die. Then any two people can ensure maximum utility for themselves by voting to kill the third, but the solution isn’t unique.

[jessicata]

I believe the same proof method works when players share the same ordering on outcomes; the important thing is that it’s more likely to jump from a bad state to a good state than vice versa.

I think the main issue with the Cthulhu example is that, if person A is voting for person B and person B is voting for person A, then person C is indifferent between voting for person A or person B. But I expect that the same proof method from the post shows that, if any subset can ensure their strict maximum utility by coordinating, then they will.

[cousin_it]

What does “strict maximum utility” mean—achieving the unique outcome that maximizes utility? That seems too restrictive, e.g. in a coordination game with (10,10) and (10,10) I want the players to find an optimal outcome even though it’s not unique. Can you make it precise?

Edit: your condition “all players share the same ordering on outcomes” also seems too restrictive. My condition “all players can achieve their best possible utilities by coordinating” is more lenient, because it doesn’t care about ordering of non-optimal outcomes. So maybe you could push in that direction as well.

[jessicata]

Yes, that is what I meant by strict maximum utility. Agree this is too restrictive. I don’t know what similar criterion would be both good to have and achievable, given the Cthulhu example.

Regarding all players achieving their best possible utilities by coordinating: what about a case where player A’s utility is always 0, and player B’s utility is 1 if player A takes action 1 and 0 if player A takes action 2? They can both achieve their best possible utilities by coordinating but I don’t think that means player A should necessarily take action 1.

[cousin_it]

Great example, I didn’t think of that. Maybe the right criterion is that some achievable utility vector must be strictly superior to all other achievable utility vectors on all coordinates. But it shouldn’t have to correspond to a unique outcome, so the (10,10) (10,10) example could still work. Would that be possible with your approach?

[jessicata]

Yes, I think that will work.

[Rohin Shah]

Two typos in the proof that confused me:

Since in general x/​1+x≤1−1/​x for positive x

Sign should be flipped.

A non-optimal state has probability at least umin

Should be “A non-optimal state has utility at least umin”.

[jessicata]

Thanks, fixed.

[Shmi]

Do I understand it correctly that the approach is to adjust the decision probabilities in a way that penalizes in some way low-utility outcome and rewards high-utility outcomes? If so, do you recommend a specific way of doing so? How hard would it be to do what you propose constructively, say in the iterated Prisoner’s dilemma with a bunch of bots following this strategy, and see if they converge to a Nash equilibrium, hopefully the best one?

[jessicata]

Do I understand it correctly that the approach is to adjust the decision probabilities in a way that penalizes in some way low-utility outcome and rewards high-utility outcomes?

Yes, the idea is that you switch actions more often when utility is low.

If so, do you recommend a specific way of doing so?

Yes, the decision rule is in the post.

How hard would it be to do what you propose constructively, say in the iterated Prisoner’s dilemma with a bunch of bots following this strategy, and see if they converge to a Nash equilibrium, hopefully the best one?

This doesn’t guarantee a Pareto efficient outcome in games where players have different utility functions (see “Extension to non-common-payoff games”). Running these strategies in iterated games is difficult given that there is an infinite number of “actions” (policies). It’s plausible that this approach yields something like $ϵ$-approximate correlated equilibria but I haven’t worked out the details, and anyway I’d rather try to find something that gets Pareto efficient outcomes.