2 Game Theory and Mixed-Motive Settings

As mentioned in the introductory section, cooperative AI uses many tools and concepts from game theory, a mathematical framework for modelling strategic interactions. In this section, we’ll introduce you to some of the most important tools and concepts, and use these to get a sense for the kind of problems, settings and systems that the field of cooperative AI tends to focus on, and why.

Cooperation and Competition

‍

In game theory, multi-agent settings can be classified into three categories:

‍

• Fully cooperative: all agents have shared objectives, where what is “good” for one agent is always equally good for another agent.
• Fully competitive: all agents have opposing objectives, where what is “good” for one agent is always bad for all the others (also referred to as zero-sum or constant-sum games).
• Mixed-motive: agents have some overlap in objectives but also some conflicting interests.

‍

Virtually all interactions you have with other human beings could be described as mixed-motive. In a family, a sports team, a classroom or a workplace you will have different people with different goals that are not perfectly aligned with each other, but neither perfectly opposed.

‍

Fully cooperative and fully competitive settings are popular research topics in AI (for example, some of the most talked about breakthroughs in recent AI history are to do with performance in zero-sum games like Go). There are many reasons for this, such as:

‍

• There is a clear, unambiguous sense of what counts as good performance, and they are simpler to analyse mathematically and build scalable algorithms for.
• Board games and video games are natural test environments for AI systems and are often zero-sum.
• Applications with a single AI deployer are often fully cooperative (e.g. teams of robots in a warehouse).

‍

However, it’s important to note that "fully cooperative" and "fully competitive" settings only really exist within the realm of game theory or idealised settings like board games and sandboxed industrial settings. For real-world interactions between human entities, it is better to think in terms of a "mostly competitive" to "mostly cooperative" scale.

‍

This brings us to the notion of preference alignment: the degree to which the goals of agents in a particular setting are similar. Other ways of saying this might be: the degree to which agents are on the same team, the degree to which agents want the same outcomes as each other, or the degree of similarity between all the agents' goals. Lewis Hammond touches on this concept in the first lecture of the previous section (during this part of the presentation).

Fully competitive settings are not of interest to the cooperative AI field. This is because there is no room for overall cooperation or mutual benefit (though subgroups of agents can of course cooperate at the expense of others). Conflict is inevitable. Fortunately, fully competitive settings are also quite rare. The rest of this section will therefore focus on the mixed-motive and fully cooperative end of the spectrum.

‍

The possible challenges and failures that agents in mixed-motive and fully cooperative settings face are different but there is some overlap. The following piece, “A Review of Cooperation in Multi-agent Learning”, introduces cooperation between learning agents and contrasts fully cooperative settings against mixed-motive settings with some real-world examples. The section we recommend reading presents the challenges that are faced by learning agents in cooperative and mixed-motive settings.

Section 5 on cooperation with mixed motivation goes into more technical detail and is optional reading. It more rigorously defines a social dilemma (which you will be introduced to later) and presents ways to solve them.

The following piece, section 2.2 of ‘Multi-Agent Risks from Advanced AI’, provides a more in-depth explanation of why mixed-motive interactions are such an important aspect of multi-agent AI safety.

Decomposing Games into a Cooperative and Competitive Component Optional

This section is a small optional walkthrough of how to decompose any two-player normal-form game into a fully cooperative component and a fully competitive component. It is based on the work of Adam Kalai and Ehud Kalai (here is an accessible link). This part is optional and quite technical. It is best for those with a solid background in game theory and solution concepts (you will need to understand the minimax concept to continue).

‍

Any two-player game G with payoff matrices (A, B) (one for each player) can be decomposed into two components:

‍

• The zero-sum game G_z where Player 1 receives D = (A − B) / 2 and Player 2 receives −D. This captures pure competition: whatever one player gains, the other loses.
• The team game G_t with payoffs C = (A + B) / 2 for both players. In this game, both players have identical payoffs, so their interests are perfectly aligned.

‍

You can verify that adding these two components recovers the original game: Player 1’s payoff is C + D = (A + B)/2 + (A − B)/2 = A, and Player 2’s payoff is C − D = (A + B)/2 − (A − B)/2 = B.

‍

The decomposition can help us to understand the structure of the game. One useful concept that utilises the decomposition is the coco value. Assuming the utility in the game is transferable (for example, the utility represents a cash payment) and the two players in the game can cooperate on playing the strategies which maximise sum-total welfare, then the coco value suggests a fair way to distribute this welfare among the two players (fair with respect to the player’s competitive advantage over each other). It is defined for each player i as follows:

‍

coco_i = maxmax(G_t) + minmax(G_z)_i

‍

where maxmax(G_t) is the maximum sum-total welfare (the largest value of (A + B)/2 across all strategy profiles), and minmax(G_z)_i is the i^th component of the minimax value of the zero-sum game G _z. Note that unless minmax(G_z) = maxmin(G_z) over pure strategies, finding minmax(G_z) will require the consideration of mixed strategies.

Basic Game Theory for Cooperative AI

This subsection provides a basic introduction to concepts from game theory that are relevant to cooperative AI. If you are familiar with game theory, feel free to skip the three suggested readings below, but not the more detailed discussions of coordination problems, bargaining problems and social dilemmas as these are important to understanding the priorities of the cooperative AI field.

‍

Game theory abstracts situations involving multiple agents by modelling them as games with players, strategies and payoffs. Each player could be an individual, group, or AI agent. Payoffs, also known as utilities or rewards, are a way of representing the preferences players have over all the different combinations of strategies that players could adopt. The following provide a quick and accessible overview of the core terms and concepts from game theory.

A particularly important concept for cooperative AI from game theory is Pareto efficiency, as it serves as a foundation for many formal definitions of cooperation.

The prisoner’s dilemma is the most famous example in game theory and is useful for understanding the basic concepts you’ve seen so far.

The following video also provides a basic introduction to game theory, but in the context of cooperative AI. Feel free to skip or play most of it at a higher speed as it covers a lot of what has been introduced above, but it can be useful to see the concepts contextualised within the cooperative AI field.

Now we’ll introduce three kinds of games: a coordination problem, bargaining problem and social dilemma. You may have already come across these terms in your reading so far. They are important types of multi-agent situations to comprehend for understanding the priorities of the cooperative AI field. We start with a technical definition of each kind of game, and then provide examples to help grasp the core ideas.

(You may come across many subtly different definitions for the terms below, but these are what we’ll be working with in the curriculum.)

‍

Coordination Problem

‍

• A coordination problem is a game involving at least two Pareto-optimal Nash equilibria, and to achieve one of them, the agents must coordinate (i.e. pick compatible strategies). Put another way, if the agents play strategies for different Pareto-optimal outcomes, they will reach a Pareto-dominated outcome.
• For a two-player game, this can be formalised as follows: a game is a coordination problem if there exists at least one pair of Pareto-optimal Nash equilibria (a, b) and (c, d), such that (a, d) or (c, b) are Pareto-dominated.

‍

Don’t worry if the above doesn’t make a lot of sense yet. There are two types of coordination problems that are most important for you to understand: a pure coordination problem and a bargaining problem.

‍

Pure Coordination Problem

‍

• A pure coordination problem is a coordination problem where agents have identical preferences over the Pareto-optimal outcomes. That is, they don’t care which Pareto-optimal Nash equilibrium is coordinated on, only that any one is coordinated on.

‍

The prototypical example of a pure coordination problem is two people walking down a narrow pavement. Here, the “Pareto-optimal Nash equilibria" are: both people walk on their left or both people walk on their right. If they miscoordinate and walk on the same side of the pavement they will collide. A higher-stakes class of pure coordination problems are establishing technology standards. For example, there are typically many different ways a connector or port could be designed that everyone would be roughly equally happy with, but it’s best if we all agree to use only one of them.

‍

In these cases, the only problem is agreeing on any compatible, Pareto-efficient set of actions. To do this, a communication protocol or shared convention might be set up (or evolve organically over time). For example, people in the UK typically gravitate to walking on the left side of the pavement in line with the side of the road that cars drive on. In coordination problems, improving the capabilities of individual agents (better communication, better perception, more knowledge and access to information) is often sufficient to solve the problem. Once agents can reliably observe each other or share a convention, the problem largely dissolves.

‍

Pure coordination problems are quite rare in the real-world. Even problems that might seem like pure coordination problems actually involve a lot of mixed motives. For example, after taking into account some practical considerations, choosing where the prime meridian is on earth is seemingly arbitrary, and having a universally agreed prime meridian is of course better than having none at all. But the choice of course does have geopolitical implications. In fact, at the International Meridian Conference held in October 1884 to determine a prime meridian for international use, France argued for a “neutral” line in somewhere such as Azores or the Bering Strait, abstained from the vote and continued to use the Paris meridian until 1911 (see here for more details).

‍

Bargaining Problem

‍

• A bargaining problem is a mixed-motive coordination problem where the agents have different preferences over the Pareto-optimal outcomes requiring coordination.
• For a two-player game, this can be formalised as follows: a game is a bargaining problem if there exist distinct Pareto-optimal Nash equilibria (a, b) and (a’, b’) such that (a, b’) or (a’, b) is Pareto-dominated and one player prefers (a, b) to (a’, b’).
• Chicken and Bach or Stravinsky (also known as Battle of the Sexes) are the classic bargaining problems from game theory.

‍

Take an intersection on the road as an example, and suppose two cars are approaching. Both want to avoid a crash, but each would prefer to be the one that goes first. In these reasonably low-stakes, repeated scenarios, the solution is to fairly distribute who is favoured over the long term. For example, traffic lights typically swap evenly between which lanes are allowed to move and which must wait at busy intersections.

For a higher-stakes example, consider two nations negotiating over which country will host a major international institution, such as the headquarters of a new regulatory body. Both nations benefit from the institution existing, but the hosting country gains disproportionate influence and economic benefits, and the headquarters can only be in one place. Both this and coordinating cars on the road are bargaining problems, but this new situation is much harder to solve in a way that keeps all agents happy.

Bargaining problems are more socially demanding than pure coordination problems. Raw capability improvements might not necessarily be enough. Typically what's needed is something like a fair coordination device: a traffic light, a convention, a compromise or long-term agreement. The complexity of this device, or the difficulty of setting it up and maintaining it, depends on a few factors. We’ve already seen in the exercises above how factors like time horizon and the magnitude of the difference in preferences between the Pareto-optimal outcomes can have a large effect on the difficulty of bargaining problems and the efficacy of a coordination device. The problems caused by mixed motivations are most acute in social dilemmas, the final class of games we will introduce.

‍

Social Dilemma

‍

• A social dilemma is where Pareto-optimal outcomes exist (known as mutual cooperation or cooperative outcomes), but players are individually incentivised to avoid them, even if they knew that the other agents would behave in accordance with them.
• A game-theoretic way of saying this is that the Nash equilibria of the game are not Pareto-optimal.
• The Prisoners’ Dilemma and the Public Goods Game are the prototypical examples of a social dilemma.

‍

Social dilemmas crop in the real-world frequently, from maintaining public spaces to arms races. In fact, there is a brilliant list of examples on the Wikipedia page for the ‘Tragedy of the Commons’.

Let’s walk through a particular example of a social dilemma and explain how it differs from the previous two types of game. Take a group of fishing communities sharing a lake, where each community benefits from fishing more, but if everyone fishes as much as they'd individually like to, the fish stock collapses and everyone is worse off. In this situation the problem is that each agent is individually incentivised to not restrain their catch, even if they know others are cooperating (in fact, especially if they know others are cooperating!). The cooperative outcome—where everyone fishes a modest amount—is not a Nash equilibrium, meaning there is always a temptation to defect by fishing more. This contrasts with a coordination problem where an agent would be individually incentivised to act compatibly if they knew which coordinated outcome all other agents planned to pursue.

‍

This distinction has an important consequence. Unlike coordination problems, providing agents with better information, better communication, or simply more intelligence isn’t enough to solve a social dilemma. The fishing communities already understand the situation perfectly. Giving them better forecasts of fish populations, or faster communication, does not remove the underlying incentive to overfish. In fact, improving the capabilities of individual agents may even make things worse if those capabilities are used to find more sophisticated ways to exploit others. What's needed instead is something that changes the incentive structure: monitoring and enforcement of catch limits, systems of reputation that punish over-fishers, binding agreements, or norms backed by sanctions. These are fundamentally more demanding to design, implement, and maintain, and hence more costly and fragile.

Those who are very familiar with the basics of game theory might find the following optional content interesting. It provides a more rigorous exploration of coordination problems, bargaining problems and (sequential) social dilemmas, and breaks bargaining problems down into two types: symmetric and asymmetric. It’s a good example of developing and evaluating solutions for the different types of settings an agent may find themselves in, focussing mainly on the idea of “norm-adaptiveness”.

Why Cooperative AI Focuses on Particular Mixed-motive Settings

Now let's summarise what we’ve read and present a general overview of why the field of cooperative AI tends to focus on what it does (at least as we see it at the Cooperative AI Foundation).

‍

1. Highly competitive or zero-sum settings are rare and there is no room for overall cooperation or mutual benefit. Improving outcomes in fully cooperative settings and pure coordination problems are likely a default outcome of general AI progress. Therefore, these settings are typically of little interest to the field.
2. Mixed-motive problems are common, and high-stakes bargaining problems and social dilemmas don’t simply disappear as agents become more generally capable.
3. If we imagine that advanced and influential AI agents will be somewhat aligned with subsets of humans (e.g. AI assistants for a company or AI delegates for a nation’s government) with different goals, then we should expect AI agent interactions to be mixed-motive too.
4. Not only this, but some of humanity's greatest problems, like climate change and international conflict, are because of a strong tension between individual incentives and the collective good, rather than problems of coordination alone.
5. This is why cooperative AI tends to focus on finding general and context-specific methods to solve the most challenging mixed-motive situations.

This section has mainly focussed on concepts from game theory, and how they can be useful for thinking about cooperative AI. While game theory provides important tools for cooperative AI research, it is by no means the only approach for studying multi-agent safety. The next section will focus on a different perspective that instead draws more on tools from complex systems theory.

‍

If you are interested in learning more about game theory for cooperative AI research specifically, we highly recommend working through the ‘Foundations of Cooperative AI’ course material by Vincent Conitzer.