Similarity-based cooperative equilibrium
Authors: Caspar Oesterheld
Johannes Treutlein
Roger Baker Grosse
Vincent Conitzer
Jakob Nicolaus Foerster
Venue: NeurIPS 2023 poster (2023)
Keywords: Program equilibrium
multi-agent learning
game theory
opponent shaping
superrationality
decision theory
cooperative AI
Newcomb's problem
TL;DR: If ML agents observe how similar they are to each other, they can cooperate in the one-shot Prisoner's Dilemma.

Abstract: As machine learning agents act more autonomously in the world, they will increasingly interact with each other. Unfortunately, in many social dilemmas like the one-shot Prisoner’s Dilemma, standard game theory predicts that ML agents will fail to cooperate with each other. Prior work has shown that one way to enable cooperative outcomes in the one-shot Prisoner’s Dilemma is to make the agents mutually transparent to each other, i.e., to allow them to access one another’s source code (Rubinstein, 1998; Tennenholtz, 2004) – or weights in the case of ML agents. However, full transparency is often unrealistic, whereas partial transparency is commonplace. Moreover, it is challenging for agents to learn their way to cooperation in the full transparency setting. In this paper, we introduce a more realistic setting in which agents only observe a single number indicating how similar they are to each other. We prove that this allows for the same set of cooperative outcomes as the full transparency setting. We also demonstrate experimentally that cooperation can be learned using simple ML methods.

Similarity-based cooperative equilibrium
Caspar Oesterheld" 1+
Johannes Treutlein
Roger Grosse 3,4,5
Vincent Conitzer 1.6
Jakob Foerster
"oesterheld@cmu. edu
'FOCAL. Carnegic Mellon University 'CHAI, UC Berkeley
Anthropic
Vector Institute
University of Toronto
Institute for Ethics in AI, University of Oxford
"FLAIR, University Oxford
Abstract
As machine learning agents act more autonomously in the world, they will inereas- ingly interact with each other. Unfortunately, in many social dilemmas like the one-shot Prisoner's Dilemma, standard game theory predicts that ML agents will fail to cooperate with each other. Prior work has shown that one way to enable cooperative outcomes in the one-shot Prisoner's Dilemma is make the agents mutually transparent to each other, i.c., to allow them to access one another's ' source code (Rubinstein 1998) Tennenholtz 2004) weights the case of ML agents. However, full transparency is often unrealistic, whereas partial transparency is com- monplace. Moreover, it is challenging for agents learn their way cooperation in the full transparency setting. In this paper, we introduce more realistic setting in which agents only observe single number indicating how similar they are each other. We prove that this allows for the same set of cooperative outcomes the full transparency setting. We also demonstrate experimentally that cooperation can be learned using simple MI. methods.
Introduction
As Al systems start to autonomously interact with the world, they will also increasingly interact with each other. We already see this in contexts such as trading agents (CFTC & SEC (EC(2010) but the number of domains where separate AI agents interact with each other in the world is sure to grow; for example, consider autonomous vehicles. In the language of game theory, Al systems will play general-sum games with each other. For example, autonomous vehicles may find themselves in Game-of-Chiede Chiicken-likke dynamics with each other (cf. [Fox al., 2018). In many of these interactions, cooperative or even peaceful outcomes are not a given. For example, standard game theory famously predicts and recommends defecting the one-shot Prisoner's 's Dilemma. Even when cooperative equilibria exist, there are typically many equilibria. including uncooperative and asymmetric ones. For instance, in the infinitely repeated Prisoner's Dilemma, mutual cooperation played in some equilibria, but so is mutual defection, and so is the strategy profile in which one player cooperates 70% of the time while the other cooperates 100% of the time. Moreover, the strategies from different equilibria typically do not cooperate with each other. A recent line of work at the intersection of Al/(multi-agent MI. and game theory aims to increase AI/ML systems' ability to cooperate with each other (Stastny et al. 2021 Dafoe et al. 2020 Conitzer & Oesterheld 2023).
Prior work has proposed librium (McAfee 1984;
make Al agents mutually transparent to allow for cooperation in equi- Howard 1988 Rubinstein 1998) Section 10.4; Tennenholtz 20044; Barasz Desterheld200199 2019b). Roughly, this literature considers for any given 2-player normal-form game the following progrum meta game: Both players submit a computer program, e.g., some neural net, to choose actions on their behalf. The computer program then receives as input the computer program submitted by the other player. The aforecited works have shown that the program meta game has cooperative equilibria in the Prisoner's Dilemma.
al. 2014 Critch 2019 Oesterheld
Unfortunately, there are multiple obstacles to cooperation based on full mutual transparency. 1) Settings of full transparency rare in the real world. 2) Games played with full transparency in 37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Principal 1
Principal
diff: A(AI)* A(A2)* R
Policy 1
Policy 2 n2: : R - A(A2)
R- ((A))
(diff (diff (T,, m2))1
(diff (T. m2))2
Mixed strategy 01 E AA1))
Mixed strategy 2
02 E A
Figure 1: A graphical representation of diff meta games (Definition D. Nodes with two incoming nodes are determined by applying one of the parent nodes to the other.
general have many equilibria, including ones that are much worse for some or all players than the Nash equilibria of the underlying game (see the folk theorems given by Rubinstein 1998, Section 10.4, and Tennenholtz 2004). In particular, full mutual transparency can make the problem of equilibrium selection very difficult. 3) The full transparency setting poses challenges to modern MI. methods. In particular, it requires at least one of the models to receive as input a model that has at least as many parameters itself. Mcanwhile, most modern successes of ML use models that are orders of magnitudes larger than the input. Consequently, we are not aware of successful projects on learning general-purpose purpose models such as neural nets in the full transparency setting.
Contributions. In this paper we introduce a novel variant of program meta games called difference (diff) meta games that enables cooperation in equilibrium while also addressing obstacles 1-3. As in the program meta game, we imagine that two players each submit a program or policy to instruct an agent to play given game, such as the Prisoner's 's Dilemma. The main idea is that before choosing an action, the agents receive credible information about how similar the two players' policies are to each w.r.t. how they make the present decision. In the real world, we might imagine that this information is provided by a mediator (ef. Monderer & Tennenholtz 2009. Ivanov et al. 2023] Christoffersen al. 2023) who wants to enable cooperation. We may also imagine that this signal is obtained more organically. For example, we might imagine that the agents can see that their policies were generated using the same code base. We formally introduce this setup in Section 3] Because it requires much lower degree of mutual transparency, we find the diff meta game setup more realistic than the full mutual transparency setting. Thus, it addresses Obstacle to cooperation based on full mutual transparency.
Diff meta games can still have cooperative equilibria when the underlying base game does not. Specifically, in Prisoner's Dilemma-like games, there are equilibria in which both players submit policies that cooperate with similar policies and thus with each other. We call this phenomenon similarity-based cooperation (SBC). For example, consider the Prisoner's Dilemma as given in Table for G = 3. (We study such examples in more detail in Section 3 Imagine that the players can only submit threshold policies that are parameterized only by a single real-valued threshold 0 and cooperate if and only if the perceived difference to the opponent is most 0,. As measure of difference, the policies observe diff 02) = 0 - 021 + Z. where is sampled independently for each player according the uniform distribution over [0, 1]. For instance, if Player submits a threshold of 1/2 and Player submits a threshold of 3/4, then the perceived difference is 1/4 + Z. Hence, Player cooperates with probability P(1/4 + Z < 1/2) 1/4 and Player 2 cooperates with probability P(L/1 + Z < 3/1) 1/2. It turns out that (0) cooperation with probability 1, is Nash equilibrium of the meta game. Intuitively, the only way for either player to defect more is to lower their threshold. But then 0, - 02l will increase, which will cause the opponent to defect more (at rate of 1/2). This outweighs the benefit of defecting more oneself.
1, 02 = 1). which leads to mutual
In Section 4 prove folk theorem for diff meta games. Roughly speaking. this result shows that observing a diff value is sufficient for enabling all the cooperative outcomes that full mutual

---

Player 2
Cooperate
Defect
Cooperate
G, G
0,G+1
Player 1
Defect
1+
1,1
Table 1: The Prisoner's Dilemma, parameterized by some number G >
transparency enables. Specifically, we show that for every individually rational strategy profile o (i.e., every strategy profile that is better for each player than their minimax payoff), there is function diff such that is played in an equilibrium of the resulting diff meta game.
Next, we address Obstacle 2 to full mutual transparency- the multiplicity of equilibria. First, note that any given measure of similarity will typically only enable specific set of equilibria, much smaller than the set of individually rational strategy profiles. For instance, in the above example, all equílibria are symmetric. In general, one would hope that similarity-based cooperation will result in symmetric outcomes in symmetric games. After all, the new equilibria of the diff game are based on submitting similar policies and if two policies play different strategies against each other, they cannot be similar. In Section 5| we substantiate this intuition. Specifically, we prove, roughly speaking, that in symmetric, additively decomposable games, the Pareto-optimal equilibrium of the meta game is unique and gives both players the same utility, if the measure of difference between the agents satisfies a few intuitive requirements (Section 5). For example, in the Prisoner's 's Dilemma, the unique Pareto-optimal equilibrium of the meta game must be one in which both players cooperate with the same probability.
Finally we show that diff meta games address Obstacle 3: we demonstrate that in games with higher- dimensional action spaces, we can find cooperative equilibria of diff meta games with MI. methods. In Section 6.44 we show that, if we initialize the two policies randomly and then let each of them learn to be a best response to the other, they generally converge to the Defect-Defect equilibrium. This is expected based on results in similar contexts, such as in the Iterated Prisoner's Dilemma. However, in Section [. we introduce a novel, general pretraining method that trains policies to cooperate against copies and defect (i.e., best respond) against randomly generated policies. Our experiments show that policies pretrained in this way find partially cooperative equilibria of the diff game when trained against each other via alternating best response training.
We discuss how the present paper relates to prior work in Section 7 We conclude in Section g with some ideas for further work.
2 Background
Elementary game theory definitions. We assume familiarity with game theory. For an introduction,
see Oshorne (2004). A (two-player, normal-form game r = (A1, A2, u) consists of sets of actions or pure strategies A and A2 for the two players and utility function u: A₁ A2 + R2. Table ] gives the Prisoner's Dilemma as a classic example of a game. A mixed strategy for Player is distribution over A: We denote the set of such distributions by A(A.). We can extend u to mixed strategies by taking expectations, i.e., u(ai, 02) := EoiEA1 a (a1)oo(()))
a2). For any player i, we use -i to denote the other player. We call o; a best response to a strategy o-i), where supp denotes the support. A (AAg) is a vector of strategies, one for each player. We call a strategy profile (2), a (strict) Nash equilibrium if o is (unique) best response 02 and vice versa. As first noted by Nash (1950), each game has at least one Nash equilibrium. We say that a strategy profile o is individually rational if each player's 's payoff is at least her minimax payoff, i.e., (,) 2 min,- ea, u, u,(0,, 0-3) for = 1, We say that o is Pareto-optimal there exists no a' s.t. (=('") 2 (.(o) for i = 1, and (,(a') >> (a) for at least one i.
a-i E ((A_;), if supp(a;) S arg a, U; (4;
strategy profile a E A(A,)
Symmetric games and additively decomposable games. We say that a game is (player) symmetric if A, A and for all a1, a2 for i = 1, 2, we have that u,(ai, a2) = u_2 a1). The Prisoner's Dilemma in Table D is symmetric. We say that a game additively decomposes into (ug,5 Aj + [))))((12)) if u; az)
un,1 (a1) + (42) for all = (1,2) and all 0₁ E A1, E Ag- Intuitively, this means that each action aj of Player j generates some amount of utility wiy(ay) for Player independently of what Player -j plays. For example, the Prisoner's Dilemma in Table [ additively decomposable, where un, Cooperate + 0, Defect + 1 and u Cooperate +
3

---

G. Defect + 0 for i = 1. Intuitively. Cooperate generates G' for the opponent and 0 for oneself, while Defect generates 1 for oneself and for the opponent.
Alternating best response learning. The orthodox approach to learning in games is to learn to best respond the opponent, essentially ignoring that the opponent is also a learning agent. In this paper, we specifically consider alternating best response (ABR) learning. In ABR, the players take turns. In each turn, one of the two players updates the parameters O2 of her strategy to optimize u. (0,, 0 .). i.e. updates her model to be a best response to the opponent's ' current model (Brown cf. 1951; Zhang et al. 2022 Heinrich et al. 2023). Since learning an exact best response is generally intractable, we will specifically consider the use of gradient ascent in each turn to optimize (,, 0-;) over 0,. In continuous games if ABR with exact (locally) best response updates converges to (01. 02). then (0,, 02) is a (local) Nash equilibrium. Note, however, that ABR may fail to converge (e.g.. in the face of Rock- Prock-Paper-Scisoone dynamics). Moreover, if the best response updates of 0g are only approximated, ABR may converge to non-equilibria (Mazumdar et al.. 2020) Proposition 6).
3 Diff Meta Games
We now formally introduce diff meta games, the novel setup we consider throughout this paper. Given some base game r, we consider a new meta game played by two players whom we will call principals. Each principal: i submits a policy. The two players' policies each observe real-valued measure of how similar they are to each other. Based on this, the policies then output a (potentially mixed) strategy for the base game. Finally, the utility is realized as per the base game. Below we define this new game formally. This model is illustrated in Figure
Definition 1. Let r = (A1; A2, u) be a game. A (diff-based) policy for Player i for a function T: R. + ((A)) mapping the perceived real-valued difference between the diff-basel policies mixed strategy of T. For i = 1,2 let A; C ((A,)* R be a set of difference- based policies for Player i. Then a policy difference (diff) function for (A1, A2) is a stochastic function diff: A1 x A2 R2. For any two policies T1, 22 and difference function diff, we say that (T1, 72) plays the strategy profile function
T E (Ai) x (A22) T ifa;= = E (rdiiff,, T2))] for = 1, For sets of policies A1,As and difference function diff we then define the diff meta game (T, AI, A2, diff' to be the normal-form game A2, V), where V(TI, T2) == E ([(((T (dill,,,, F2) ))) 1,2)] for all m E Ai, n2 E AA.
Note that Definition I does not put any restrictions on diff. For example, the above definition allows (diff (T,, T=))); to be a real number whose binary representation uniquely specifies -- This paper dedicated to situations in which diff specifically represents some intuitive notion of how different the policies are, thus excluding such diff functions. Unfortunately, there are many different ways in which one could formalize this constraint, especially in asymmetric games. In Section 5 we will impose some restrictions along these lines, including symmetry. Our folk theorem (Theorem 3 in Section 4h will similarly impose constraints on diff to avoid diff' functions like the above.
The rest of this section will study concrete examples of Definition | First, we define a particularly simple type of diff-based policy. Almost all of our theoretical analysis will be based on this class of policies.
Definition 2. Let 0 E IR U (-00, ) and o o E A(A,) be strategies for Player Playerifor = 1, 2. Then we define (o, O, of to be the policy т s.t. ((d = if d S 0 and x(d) = o otherwise. We call policies of this form threshold policies. Let A; denote the set of such threshold policies.
Throughout the rest of this section, we analyze the Prisoner's Dilemma as a specific example. We limit attention to threshold agents of the form (C,0, i.e., policies that cooperate against similar opponents (diff below threshold 0) and defect against dissimilar opponents. This is because such policies can be used to form cooperative equilibria, while policies that always cooperate (say, 1, or policies that are more cooperative against less similar opponent policies (c.g.. (D, C)) cannot be used to form cooperative equilibria in the PD with natural diff function. Policies of the form (C, 8 D) are uniquely specified by a single real number 9. A natural measure of the similarity between two policies 01, 0₂ is then the absolute difference 10, Oz). We allow diff to be noisy, however. We summarize this in the following.
Example 1. Let I' be the Prisoner's Dilemma as per Table meta game where A, = [[C,,, 0;, D) 0, E RR and diff, ((C, 01, D), (C, 02 D))) = 10: Oz) + Z, for i = 1, 2 where Z, is some vallev random variable.
1
Then consider the (T, Ai, Ag, diff)

---

The only open parameters of Example are G (the parameter used in our definition of the Prisoner's s Dilemma) and the noise distribution. Nevertheless. Example [ is a rich setting that allows for nontrivial results. We leave detailed analysis for Appendix B and only give two specific results about equilibria here.
In the first result, we imagine that the noise Z; is distributed uniformly between O and e > 0 and that is at least 2. Then, roughly, there are two kinds of equilibria. First, there are equilibria in which both players always defect, because their threshold for cooperation is at most 0 (such that they defect with probability even against exact copies). Second, and more interestingly. there are equilibria in which both players submit the same threshold strictly between 0 and e. Note that this means that if both players submit threshold of e, they both cooperate with probability 1.
Proposition 1. Consider Example 7 with 7: Uniform([O, <l) i..dd for some e > O and with G 2 2. Then ((C, 01, D), (C, 02, D)) is a Nash equilibrium if and only if 2001000 02 S or 0 < 01 02 S In case of the latter, the equilibrium is strict if G > 2.
What happens if, instead of the uniform distribution, we let the Zi be, say, normally distributed? turns out that for all unimodal distributions (which includes the normal distribution) and G = 2, we get an especially simple result: in equilibrium, both players submit the same threshold and that threshold must be left of the mode.
Proposition2 2. Consider Example 7 with G = 2. Assume Zi is for.foo i = 1,2 according some uni- modal distribution with mode v with positive measure on every interval. Then ((C, 0r, D), (C, 02, D)) is a Nash equilibrium if and only if 02 v.
4 A folk theorem for diff meta games
What are the Nash equilibria of a diff meta game on | A first answer is that Nash equilibria of I' carry over to the diff meta game regardless of what diff function is used (assuming that at least all constant policies are available); see Proposition T6 in Appendix C.III Any other equilibria of the diff meta game hinge on the use of the right diff function. In fact, if diff is constant and thus uninformative. the Nash equilibria of the diff meta game are exactly the Nash equilibria of I; see Proposition 17 in Appendix C.1 So the next question to ask for what strategy profiles a there exists some diff function s.t. is played in an equilibrium of the resulting diff meta game. The following result answers this question. particular, a folk theorem similar to the folk theorems for infinitely repeated games (e.g.. Osborne 2004, Ch. 15) and for program equilibrium (see Section 7
Theorem (folk theorem for diff meta games). Let I be game and a be strategy profile for r. Let A, 2 As for i = 1,2. Then the following two statements are equivalent:
1. There is a diff function such that there is Nash equilibrium (T1, 72) of the diff meta game (I' diff, A1, s.t. (TI, (2) play o.
2. The strategy profile a is individually rational (i.e., better than everyone's minimax payoff).
The result continues to hold true if we restrict attention to deterministic diff functions with diff; = diffz and diff, n2) (0, (0.1)for: for 1,2.
We leave the full proof to Appendix C.2 but give a short sketch of the construction for 2 2 here. For any o, we construct the desired equilibrium from policies गे = (a,, 1/2, ō.) for i = 1, 2. where à; is Player i's minimax strategy against Player -i. We then take any diff function s.t. diff -) = (0, 0) if x = x-, and (ff] -- = (1 otherwise.
5 A uniqueness theorem
Theorem 3 alloow for highly asymmetric similarity- based cooperation. For example, in the PD with, say, G 2, Theorem 3 shows that with the right diff function, the strategy profile (C, 2/3+C+1/ss D)
is played in an equilibrium of the diff meta game of the PD. This seems odd, as one would expect SBC to result in playing symmetric strategy profiles. Note that, for example, all equilibria of Propositions [ and are symmetric. In this section, we show that under some restrictions on diff and the base game T, we can recover the symmetry intuition. This is good because symmetric games the symmetric outcomes are the fair and otherwise desirable ones (Harsanyi et al. 1988, Sect. 3.4) and because SBC thus avoids equilibrium selection problems of other forms of cooperation (including cooperation based on full mutual transparency and cooperation in the iterated Prisoner's Dilemma).
5

---

We first need a few definitions of properties of diff. Let I' be symmetric game. We say that diff is min- imized by copies if for all policies प, ,,''al ,alll y and i 1. P P(diff,(T.. < I P(ciff ( (,, <yy). For example, the diff' function in Example minimized by copies. The diff functions in the proof of TTheorem 3 are not in general minimized by copies when the given base game symmetric. For example, to achieve (C, 2/3 C. + +1/3* * D) in equilibrium, the proof of Theorem 3 (as sketched above) uses the policies アं = (C, D) D) and T2 = (2/3 * C' + 1/3 * D, 1/2, D) and a diff function with (I, 1). If the base game is symmetric, we call diff symmetric π2) is distributed the same as diff (T22 mI) and (diff I (TT, F2), difff((T, T2))
diff( mT) (0, 0) but diff (mī x
for all I 72, diff
1 1
is distributed the same (diffy (T1, R2), dliff (T)).
Finally, we need a more complicated but nonetheless intuitive property of diff functions. In this paper, we generally imagine that low values of diff are informative about the other player's policy. In contrast, we will her assume that high values of diff' are uninformative. That is, for any a, and x-i- we will assume that there is policy that plays d, against т-; and triggers the above-threshold policy of T-; with the highest-possible probability. Formally, let T- (o_, 8_ o2,) be any threshold policy. Let be the supremum of numbers p' for which there is n. s.t. in (T,, T-1), Player
-i plays (1 p')o_, + p'o2,. Let o = (1 p)o + paž.. Intuitively, o is the strategy played by π- against the most different opponent policies. For the examples of Section B we have p = 1 and thus simply o = o²2. But if diff is bounded, then we might even have p = 0 or anything in between.
Definition 3. We call diff': Ai x A TR2 high value uninformative if for each threshold policy T- Jj and e > 0) there is a threshold policy n, such that in (Te, T-)). a strategy profile within of (0,, max) is played.
We are now ready state uniqueness result for the Nash equilibria of diff meta games.
Theorem 4. Let I be a player-symmetric additively decomposable game. Let diff be symmetric, high-value uninformative, and minimized by copies. Then if (21, is a Nash equilibrium that is not Pareto-dominated by another Nash equilibrium, we have that (T T2) = V2(T1,TT) Hence, if there exists a Pareto-optimal Nash equilibrium, its payoffs are unique, Pareto-dominant among Nash equilibria and equal across the two players.
We prove Theorem 4 in Appendix D.3 Roughly, we prove that under the given assumptions, equilibrium policies are more beneficial to the opponent when observing a diff value below the threshold than if they observe a diff value above the threshold. Second, we show that if in given strategy profile Principal receives a lower utility than Principal -i, then Principal i can increase her utility by submitting a copy of Principal -i's policy. Appendix [D]] shows why the assumptions (additive decomposability of the game and and high-value uninformativeness and symmetry of diff) are necessary.
Machine learning for similarity- based cooperation in complex games
Our results far demonstrate the theoretical viability of similarity- -ased cooperation, but leave open questions regarding its practicality. In complex environments, where cooperating and defecting are by themselves complex operations, can we find the cooperative equilibria for given diff' function with machine learning methods?
6.1 A novel pretraining method for similarity-based cooperation
We now describe Cooperate against Copies and Defect against Random (CCDR), a simple ML method to find cooperative equilibria in complex games. To use this method, we consider neural net
policies Te parameterized by real vector 0. First, for any given diff game, let vd: (RR (R*+1) x
(Rm) [R=1) + IR2 be the utility of a version of the game in which diff is non-noisy. CCDR trains
a model Re, to maximize (d(T,, Te.) + yd (TT. To' )) for randomly sampled e'.,, That is, cach player à pretrains their policy Te, to do well in both of the following scenarios: principal -i copies principal i'ss model; and principal -i generates random model. The method is named for its intended
effect in Prisoner's Dilemma-like games. Note, however, that it is well-defined in all symmetric games, not just Prisoner's Dilemma-like games.
CCDR pretraining is motivated by two considerations. First, in games like the Prisoner's Dilemma, there exist cooperative equilibria of policies that cooperate at a diff value of 0 and defect as the

---

0.8
0.8
0.6
0.4
0.4
0.2
0.2 0.4 0.5 0.8 1.0
022 0.4
0.6
0.8 1.0
Figure 2: The figure illustrates how utilities are calculated in the HDPD. The function Sa is an action chosen by Player The area between the curves f, and fo determines, intuitively, how much the agent defects; the area between the curves f. and fc determines how much it cooperates. The fa shown in the figure is much closer defecting than to cooperation.
perceived diff value increases. We give toy model of this in Appendix E CCDR puts in place the rudimentary structure of these equilibria. Note, however, that CCDR does not directly optimize for the model's ability to form equilibrium. Second, CCDR can be thought of as form of curriculum training. Before trying to play diff games against other (different but similar) learned agents, we might first train a policy solve two (conceptually and technically) easier related problems.
6.2 A high-dimensional one-shot Prisoner's Dilemma
To study similarity-basee cooperation in an ML context, we need more complex version of the Prisoner's Dilemma. The complex Prisoner's Dilemma-like games studied in the multi-agent learning community generally offer other mechanisms that establish cooperative equilibria (e.g.. playing game repeatedly). For our experiments, however, we specifically need SBC to be the only mechanism to establish cooperation.
We therefore introduce new game, the High-DDimenionall (one-shot) Prisoner's Dilemma (HDPD). The goal is to give a variant of the one-shot Prisoner's Dilemma that is conceptually simple but introduces scalable complexity that makes finding, for example, exact best responses in the diff meta game intractable. In addition to G, the HDPD is parameterized by two functions fc, fD: RR" + R probability measure
representing the two actions Cooperate and Defect, respectively, as well over IR.. Each player's action is also function f:: R + R". This is illustrated in Figure P for the case of = and m = For any pair of actions fI, /2, payoffs are then determined as follows. First, we sample some according to from RR. Then to determine how much Player i cooperates, we consider the distance d( dxf((x), fc((x) ) to determine, roughly speaking. how much Player 1 cooperates. The larger the distance the less cooperative is fi. In the case of n uniform, the expected distance between fix and fD( ) is simply the area between the curves of f: and fD. visualized in Figure 2 We analogously determine how much the players defect. Formally, we define u; (f1, f2) = - Ex- [x){(x), fo + Gd(f=; fc(x)) ( /Ex= (x) fD())) Thus, the action f; fo corresponds to defecting and the action fc corresponds to cooperating, e.g.. ulfc. fc) = (-1, -1) and u(fD. = (-G. G). The unique equilibrium of this game is (fn.fD). In our experiments,
1 and
specifically used G = 5.
We consider diff meta game on the HDPD. Formally, a diff-based policy for the HDPD is function
R + (I (I²")("))
(R") For notational convenience, we will instead write policies as functions IR=+1 + R
We then define our diff function by ( πT2 (y [d(T) (y, x), T2 x)]] + Z₁, where
some probability distribution over R=++1 and Z; some real-valued noise.
6.3 Experiments
Experimental setup. We trained on the environment from Section 6.2 We selected fixed set of hyperparameters based on prior exploratory experiments and the theoretical considerations in Appendix D. We then randomly initialized 0 and O2, CCDR-pretrained them (independently), and then trained 9 and e against each other using ABR. We repeated the experiment with 28 random seeds. As control, we also ran the experiment without CCDR on 26 seeds. We also experiments with Learning with Opponent- Learnnng Awareness (LOLA) (Foerster et al. 2018), which we report in Appendix G
Results. First, we observe that the runs without CCDR pretraining. the players generally converge to mutual defection during alternating best response learning. In particular, in all 26 runs, at least one
7

---

14
Dicance rnf at defance mi
Dinance of f5-6 14277 10000
Dissarce of of la 4ald/cool yll
10-
64
2.5
2.0
02-
155
1.0
0 200
400
800
800
1000
Time
(a)
(b)
Figure 3: (a) The behavior of a CCDR-pretraince policy, For each perceived value of diff to the opponent y. the green line shows the expected distance of the learned policy's choice fc (smaller means more cooperative) and the read line shows the expected distance to fn. (b) Losses of Player in 10 runs through the ABR phase.
player's utility below -5. Only two runs had utility above -5 for one of the players (-4.997 and -4.554). The average utility across the 26 runs and across the two players was -5.257 with standard deviation of 0.1978. Anecdotally, these results robust ABR without pretraining practically never finds cooperative equilibria in the HDPD.
Second, we observe that in all 28 rums, CCDR pretraining qualitatively yields the desired policy models, i.c., policy that cooperates at low values of diff and gradually comes closer to defecting at high values of diff. Figure 3a shows representative example.
Our main positive experimental result that after CCDR pretraining. the models converged in alternating best response learning to partially cooperative equilibrium in 26 out of 28 runs. Thus, the cooperative equilibria postulated in general by Jad in simplified examples by Propositions and 2 (as well as Proposition 25 do indeed exist and can be found with simple methods. The minimum utility of either player across the successful runs was -4.854. The average utility across all runs and the two players was about -2.77 and thus little closer to u(Sc. [c) -1 than to u( u(fD.fD) = 55 The standard deviation was about 1.19. Figure 3blshows the losses (i.c., the negated utilities) across ABR learning. Generally, the policies also converge to receiving approximately the same utility (cf. Section 5). The average of the absolute differences in utility between the two players at the end of the 28 runs about 0.04 with a standard deviation of 0.05. We that in line with 4 we tend to learn egalitarian equilibria in this symmetric, additively decomposable setting. After alternating best response learning, the models generally have similar structure the model in Figure 3al though often they cooperate only a little at low diff values. Based on prior exploratory experiments, CCDR's success is moderately robust.
Theorem
6.4 Discussion
Without pretraining, ABR learning unsurprisingly converges to mutual defection. This is due to bootstrapping problem. Submitting a policy the form "cooperate with similar policies, defect against different policies" is unique best response against itself. If the opponent model . is not of this form, then any policy ı, that defects, i.e., that satisfies π; (diff( π --)) = fD. a best response. Because fc is complex, learning model that cooperates at all is unlikely. (Even if fc was simple, the appropriate use of the perceived diff value would still be specific and thus unlikely be found by chance.) Similar failures to find the more complicated cooperative equilibria by default have also been observed in the iterated PD (Sandholm & Crites) 1996 Foerster et al. 2018 Letcher et al. 2019) and in the open-source PD (Hutter 2020). Opponent shaping methods have been used successfully to learn to cooperate both in the iterated Prisoner's Dilemma (Foerster al. 2018 Letcher et al. al. 2019)
and the open-source Prisoner's 's Dilemma (Hutter 2020). Our experiments Appendix G show that LOLA can also learn SBC, but unfortunately not as robustly as CCDR pretraining.
CCDR pretraining reliably finds models that cooperate with each other and that continue to partially cooperate with each other throughout ABR training. This shows that when given some guidance, ABR can find SBC equilibria SBC equilibria have at least some "basin of attraction". Our experiments therefore suggest that SBC is promising means of establishing cooperation between ML agents.

---

Interestingly, That said, CCDR has many limitations that we hope can be addressed in future work. For one, in many games the best response against randomly generated opponents does poorly against a rational opponent. Second, our experiments show that while the two policies almost fully cooperate after CCDR pretraining, they quiekly partially unlearn to cooperate in the ABR phase. We would prefer a method that preserves closer to full cooperation throughout ABR-style training. Third, while CCDR seems to often work, it can certainly fail in games in which SBC is possible. Learning to distinguish randomly sampled opponent policies from copies will in many settings not prepare an agent to distinguish cooperative/SBC opponents from uncooperative but trained (not randomly sampled) opponents. Consequently, CCDR may sometimes result in insufficiently steep incentive curves, cooperating with too dissimilar opponents. We suspect that to make progress on the latter issues need training procedures that more explicitly reason about incentives à la opponent shaping (cf. our experiments with LOLA Appendix G).
7 Related work
We here relate our project to the two most closely related lines of work. In Appendix H we discuss more distantly related lines of work.
Program equilibrium. We already discussed in Section I the literature on program meta games in which players submit computer programs as policies and the programs fully observe each other's s code (McAfee 1984; Howard 1988] Rubinstein 1998] Section 10.4: Tennenholtz some constructions for equilibria in program meta games are similarity based. For example, the earliest cooperative program equilibrium for the Prisoner's Dilemma, described in all four of the above-cited papers, is the program "Cooperate if the opponent's 's program is equal to this program; else Defect". The program "cooperate if my cooperation implies cooperation from the opponent proposed by Critch et al. (2022) is also similarity-based. Other approaches to program equilibrium cannot be interpreted as similarity based, however (see, e.g., Barasz et al., 2014 Critch 2019) Oesterheld (2019b). To our knowledge, the only published work on ML in program equilibrium is due to Hutter (2020). It assumes the programs to have the structure proposed by Oesterheld (2019b) on simple noomallform games, thus leaving only a few parameters open. Similar Hutter shows that best response learning fails to converge to the cooperative equilibria. In Hutter's experiments, the opponent shaping methods LOLA (Foerster et al. 2018) and SOS (Letcher et al.) 2019) converge to mutual cooperation.
experiments,
Decision theory and Newcomb's 's problem. Brams (17.5) and Lewis (1979) have pointed out that the Prisoner's Dilemma against a similar opponent closely resembles Newcomb's 's problem, a problem first introduced to the decision-theoretiin Newcomb's ' problem is about the normative, philosophical question of whether one should cooperate or defect in Prisoner's 's Dilemma against exact copy. Our work is inspired by the idea that in some circumstances one should cooperate with similar opponents. However, this literature only informally discusses the question of whether to also cooperate with agents other than exact copies (Hofstadter) Ch. 7: Ahmed 2014] Sect. 4.6.3). We address this question formally.
literature by Nozick (1969). Most of the literature on
e.g.. 1983 Drescher 2006
One idea behind the present project, as well as the program game literature, is to analyze a decision situation from the perspective of (actual or hypothetical) principals who design policies. The principals find themselves in an ordinary strategic situation. This is how our analysis avoids the philosophical issues arising in the agent's 's perspective. Similar changes in perspective have been discussed in the literature on Newcomb's 's problem (e.g.. G 1989 Oesterheld & Conitzer 2022).
8 Conclusion and future work
We make strong case for the promise of similarity-based cooperation as a means of improving outcomes from interactions between ML agents. At the same time, there are many avenues for future work. On the theoretical side, we would be especially interested in generalizations of Theorem 4 that is, theorems that tell us what outcomes we should expect in diff meta games. Is it true more generally that under reasonable assumptions about the diff function, fairly specific, symmetric, Pareto-optimal outcomes? We are also interested in further experimental investigations of SBC. We hope that future work can improve robustness and degree of cooperation. Besides that, we think a natural next step is to study settings in which the agents observe their similarity to another in more realistic fashion. For example, we conjecture that SBC can occur when the agents can determine that their policies were generated by similar learning procedures.
expect SBC to result in
results in the HDPD in terms of
9

---

Acknowledgments
We thank Stephen McAleer, Emery Cooper, Daniel Filan, John Moni, and our anonymous reviewers helpful discussions and comments. We thank Maxime Riché and the Center on Long-Term Risk for compute support. Caspar Oesterheld and Vincent Conitzer would like to thank the Cooperative AI Foundation, Polaris Ventures (formerly the Center for Emerging Risk Research) and Jaan Tallinn's donor-advised fund at Founders Pledge for financial support. Roger Grosse acknowledges financial support from Open Philanthropy. Caspar Oesterheld and Johannes Treutlein grateful for support by FLI PhD Fellowships. Johannes Treutlein was additionally supported by an OpenPhil Al PhD Fellowship.
References
Mclissa Acevedo and Joachim I Krueger. Evidential reasoning in the prisoner's dilemma. The American Journal of Psychology, 118(3):431-57, 2005.
Arif Ahmed. Evidence, Decision and Causality. Cambridge University Press, 2014.
Ozan Aksoy, Effects of heterogeneity and homophily on cooperation. Social Psychology Quarterly, 78(4):324-344, 2015.
Max Albert and Ronald Asher Heiner. An indirect-evolutiion approach to Newcomb's problem. 2001. Utt.httts:://ww econstor...... www.:eeenstttee.eiieeeeeeee httpa//steee/////////////000.0.0 pdf CSLE Discussion Paper, No. 2001-01.
Robert Axelrod. The Evolution of Cooperation. Basic Books, 1984.
Mihaly Barasz, Paul Christiano, Benja Fallenstein, Marcello Herreshoff, Patrick La Vactorore, and Eliezer Yudkowsky. Robust cooperation in the prisoner's dilemma: Program equilibrium via provability logic, 2014. JRLpptts://arzzi..o hwtgg//ba//ie /aobb////1..... 5577
James Bell, Linda Linsefors, Caspar Oesterheld, and Joar Skalse. Reinforcement learning in New- comblike environments. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 22146-22157. Curran Associates, Inc., 2021, URLhtttp httpa/ttp///ooocedinnnne wewpeeeiiinnnnnnnniieeeeeee neurips. www.rips.ccpppperr//eeaeaa peaarppps.ccpppper/2//////1. Paper pdf
Steven J. Brams. Newcomb's problem and prisoners' dilemma. The Journal of Conflict Resolution, 19(4):596 612, 12 1975.
Gordon W. Brown. Iterative solutions of games by fictitious play. In Tjalling C. Koopmans (ed.), Activity Analysis Production and Allocation, chapter XXIV, pp. 371-376. John Wiley & Sons and Chapman & Hall, 1951. URL
www.aaiiwwwwwweaaaaaaaeeeeeeeeee www.:r/g//eeaa//eeee ernet. dli .015
39951/
CFTC and SEC. Findings regarding the market events of may 6, 2010. report of the staffs of the efte and sec to the joint advisory committee on emerging regulatory issues., 2010. URL
https: http:://wwwwwwe www.sscc..o...... www..eee...//ileee//rrreeeeeteee report pddf
Phillip J.K. Christoffersen, Andreas A. Haupt, and Dylan Hadfield-Menell. Get it in writing: Formal
contracts mitigate social dilemmas in multi-agent rl. In Proceedings the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, pp. 448-456. Interna- tional Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2023. ISBN 97814 1703443343...
Vincent Conitzer and Caspar Oesterheld. Foundations of cooperative AI. Proceedings of the AAAI Conference on Artificial Intelligence, 37(13):15559-1555 15367, Sep. 2023. doi: 10. 2.009/aai.v37i1. 26791. URL http:: :/ops::///js...// aaai, org./oogr::../... wwwp.pppppaaa/. htw.A///arriceeeiie////eaa
Andrew Critch. A parametric, resource-bounded generalization of Löb's theorem, and robust cooperation criterion for open-source game theory. Journal of Symbolic Logic, 84(4):1368-1381 12 2019. doi: 10. 10.10.7//s..0117.4.
10

---

Andrew Critch, Michael Dennis, and Stuart Russell. Cooperative and uncooperative institution designs: Surprises and problems in open-source game theory, 2022. |tttps////arx org/ pdf pod8/220.0770 07006 pdf
Caterina Cruciani, Anna Moretti, and Paolo Pellizzari. Dynamic patterns similarity coop- eration: An agent-based investigation. Journal of Economic Interaction and Coordination, 12: 121-141, 2017.
Allan Dafoe, Edward Hughes, Yoram Bachrach, Tantum Collins, Kevin R. McKee, Joel Z. Leibo, Kate Larson, and Thore Graepel. Open problems in cooperative AI, 2020. URL https://arra :/arxivv
org/pdf /2012.222220o2 220.//222220000.... pdf
Richard Dawkins. The Selfish Gene. Oxford University Press, 1976.
Gary L. Drescher. Good and Real. Demystifying Paradoxes from Physics Ethics. The MIT Press, 2006.
Ilnn Fischer. Friend foe: subjective expected relative similarity determinant of cooperation. Journal of Experimental Psychology: General, 138(3)3341, 2009.
Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learnnng awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAAent Systems, pp. 122-130, International Foundation for Autonomous Agents and Multiagent Systems, 2018.
C. W. Fox, F. Camara, G. Markkula, R. Romano, R. Madigan, and N. Merat. When should the chicken cross the road?: Game theory for autonomous vehicle human interactions. In Proceedings of the 4th International Conference on Vehicle Technology and Intelligent Transport Systems, volume 1, pp.
SeiTePress, 2018. doi: 10.522000066655443310444 104394044444999.
Feng Fu, Martin A Nowak, Nicholas A Christakis, and James H Fowler. The evolution of homophily. Scientific reports, 2(1):1-6, 2012.
Andy Gardner and Stuart A. West. Greenbeards. Evolution: International Journal of Organic Evolution, 64(1):25-38, 2010.
David Gauthier. In the neighbourhood ceedings of the Aristotelian Society, New Series, 1988-19999 1989, volume 89, pp. 179-194. [Aristotelian Society, Wiley], 1989.
newcomb-predictoe (reflections on rationality). In Pro-
Jeffrey Goldberg, Lívia Markóczy, and G Lawrence Zahn. Symmetry and the illusion of control as bases for cooperative behavior. Rationality and Sociery, 17(2):243-270, 2005.
William D. Hamilton. The genetical evolution of social behaviour. Journal of theoretical biology, 7 (1):1-52, 1964.
John C Harsanyi, Reinhard Selten, al. A general theory of equilibrium selection in games. MIT Press Books, 1, 1988.
Torsten Heinrich, Yoojin Jang, Luca Mungo, Marco Pangallo, Alex Scott, Bassel Tarbush, and Samuel Wiese. Best-response dynamics, playing sequences, and convergence to equilibrium in random games. International Journal of Game Theory, 52:703-735, 9 2023, doi: 10.1007/ 5001822-223-00877-4
Douglas Hofstadter. Dilemmas for superrational thinkers, leading up to luring lottery. Scientific America, 248(6), 6 1983.
V. Howard. Cooperation in the prisoner's dilemma. Theory and Decision, 24:203-213, 5 1988. doi: 10.1007/BF00148855
Adrian Hutter. Learning two-player games between transparent opponents, 2020. URL https // /arxivv org/ absp//12..02.. 02671

---

Dmitry Ivanov, Ilya Zisman, and Kirill Chemyyshvv. Mediated multi-agent reinforcement learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, pp. 49-57. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2023. ISBN 9781 9781450394321.
Laurent Keller and Kenneth G Ross. Selfish genes: a green beard in the red fire ant. Nature, 394 (6693):573--575) 1998.
Joachim Krueger and Melissa Acevedo. Social projection and the psychology of choice. The self in social perception, pp. 17-41, 2005.
Joachim I Krueger, Theresa E DiDonato, and David Freestone. Social projection can solve social dilemmas. Psychological Inquiry, 23(1):1-27, 2012.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games. In Proceedings of the 7th International Conference Learning Representations (ICLR). OpenReview.net, 2019.
David Lewis. Prisoners' dilemma is a Newcomb problem. Philosophy & Public Affairs, 8(3):235-240, 1979.
Johannes
Martens.
Hamilton meets
causal
decision
theory. 1
2019.
URL
atpp::/johaamoenntttesss00.0 files. wew.eesswwdddressooo htm/2009/01/
hamil mamiltoo--eets--ee cus http://matttcccaaal---eeeeoe-oeo
Dominik Mayer, Johannes Feldmaier, and Hao Shen. Reinforcement learning in conflicting envi- ronments for autonomous vehicles. In International Workshop on Robotics in the 21st century: Challenges and Promises, 2016. URL /ttps:////aa org/ abs wtt.b////........
Eric Mazumdar, Lillian J. Ratliff, and S. Shankar Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131 2020.
R. Preston McAfee. Effective computability in economic decisions, 1984. URL hhttps://w// http://///pppeeeee///e/eeiiieiie
Dov Monderer and Moshe Tennenholtz. Strong mediated equilibrium. Artificial Intelligence, 173(1): 180-195, 2009.
John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1):48-49 1950.
Martin Nowak and Robert M May. Evolutionary games and spatial chaos. Nature, 359(6398): 826-829, 1992.
Martin A Nowak and Karl Sigmund. Evolution of indirect reciprocity by image scoring. Nature, 393 (6685):573-577, 1998.
Robert Nozick. Newcomb's problem and two principles of choice. In Nicholas Rescher et al. (ed.),
Essays in Honor of Carl G. Hempel. pp. 114-146. Springer, 1969. URttattp:/faacuuty artss
ubc. hecaa///snooicccneeeeeeeee .dff
Caspar Oesterheld. Approval-directed agency and the decision theory of Newcomb-like problems. Synthese, Feb 2019a. ISSN 1573-0964. doi: 10.1007/s 0210:/1112220-0001414111
Caspar Oesterheld. Robust program equilibrium. Theory and Decision, 86(1):143-159) 2 2019b.
Caspar Oesterheld and Vincent Conitzer. Can de se choice be ex anle reasonable in games of im- perfect recall? Working paper, 2022. URI/https://www andrew. cmu. cccuuseer/costeee
DeSeVsExAnte, pdf
Caspar Oesterheld, Abram Demski, and Vincent Conitzer. theory of bounded inductive rationality. In Rineke Verbrugge (ed.), Proceedings of the Nineteenth Conference Theoretical Aspects of Rationality and Knowledge, volume 379 Electronic Proceedings in Theoretical Computer Science, pp. 421-440. Open Publishing Association, 7 2023, doi: 10.4 40.420//cttc.379..33
12

---

Martin J. Osborne. An Introduction to Game Theory. Oxford University Press, 2004.
David C. Queller, Eleonora Ponte, Salvatore Bozzaro, and Joan E. Strassmann. Single-gene green- beard effects in the social amoeba dictyostelium discoideum. Science, 29965603)1105-106 2003.
Rick L Riolo, Michael Cohen, and Robert Axelrod. Evolution of cooperation without reciprocity. Nature, 414(6862):441 443, 2001.
Ariel Rubinstein. Modeling Bounded Rationality. Zeuthen Lecture Book Series. The MIT Press, 1998.
Tuomas W Sandholm and Robert H Crites. rellingentreinffoocemmmmnt reinforcement learning in the iterated prisoner's dilemma. Biosystems, (7(1-2):177-166, 1996.
Barry Sinervo, Alexis Chaine, Jean Clobert, Ryan Calsbeek, Lisa Hazard, Lesley Lancaster, Andrew G. McAdam, Suzanne Alonzo, Gwynne Corrigan, and Michael E. Hochberg. Self-recognition,, color signals, and cycles of greenbeard mutualism and altruism. Proceedings of the National Academy of Sciences, 103(11):7322-7377 2006.
Scott Smukalla, Marina Caldara, Nathalie Pochet, Anne Beauvais, Stephanie Guadagnini, Chen Yan, Marcelo D. Vinces, An Jansen, Marie Christine Prevost, Jean-Paul Latgé, Gerald R. Fink, Kevin R. Foster, and Kevin Verstrepen. Flol is variable green beard gene that drives biofilm-like cooperation in budding yeast. Cell, 135(4))726-737, 2008.
Julian Stastny, Maxime Riché, Alexander Lyzhov, Johannes Treutlein, Allan Dafoe, and Jesse Clifton. Normative disagreement as challenge for cooperative AI. In Cooperative Al workshop, 2021.
Moshe Tennenholtz. Program equilibrium. Games and Economic Behavior, 49(2):363 -3,33, 2004.
Maggie Toplak and Keith E Stanovich. The domain specificity and generality of disjunctive reasoning: Searching for generalizable critical thinking skill. Journal of educational psychology, 94(1):197, 2002.
Arne Traulsen. Mechanisms for similarity based cooperation. The European Physical Journal B, 63:363-371, 2008 doi: 10.1 40/11//////e22000000011...... htLp:ttps:///iii http:///iiiinsssiinnerr..
springer... com/
Ame Traulsen and Jens Christian Claussen. Similarity-basee cooperation and spatial segregation. Physical Review E. 70(4):046128, 2004.
Amos Tversky and Eldar Shafir. Choice under conflict: The dynamics of deferred decision. Psycho- 1992.
logical science, 3(6):358-333
Jane X Wang. Edward Hughes, Chrisantha Fernando, Wojeiech M Czareecki, Edgar A Duéñez- Guzmán, and Joel Z Leibo. Evolving intrinsic motivations for altruistic behavior. arXiv preprint 1rXiv:1811.05900 2018.
Timon Willi, Alistair Letcher, Johannes Treutlein, and Jakob Foerster. COLA: consistent learning with opponent-leamnng awareness. In International Conference on Machine Learning, pp. 23804-23831.
PMLR, 2022.
Guodong Zhang, Yuanhao Wang. Laurent Lessard, and Roger Grosse. Near-optimal local conver- gence of alternating gradient descent-ascent for minimax optimization. In Gustau Camps- Valls, Francisco J. Ruiz, and Isabel Valera (eds.), Proceedings The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 7659-7679, PMLR, 28-30 Mar 2022. URL htttps::/prooeeddiiii
mlr. press/v151/
2hang22e/zhang222 pdf
Štěpán Vesely. Psychology of decision making: Effect learning, end-effect, cheap talk, and other variables influencing decision making in the prisoner's dilemma game, 4 2011. URL https::// ///s. muni hwt..///th///AAoaiplloo.t pdf Diploma thesis.
13

---

00
Figure 4: Visualization of outcomes as a function the thresholds Example 1 without noise (21 Zz 0). For each pair of thresholds (x and axis), the graph shows whether both players cooperate (yellow), both players defect (blue), or one player cooperates and the other defects (orange).
A Preliminary game theory results
We say that a very weakly Pareto-doming â if for all i, we have that uz(o) Z uz(
Proposition 5. Let be a two-player additively decomposable normal-form game. Then I has Nash equilibrium that very weakly Pureto-dominates all other Nash equilibria. IfT is furthermore symmetric, then in the dominant equilibrium, both players receive the same utility.
Proof. First note that for all 0- Player i's best responses are given by
arg max us (a;, σ oxx) arg (a,)(a:) + u4,-i(a-s) arg max (z,;(a;).
Now among this set of universal best responses, let let of be one that maximizes u (a;) for 1, 2. Clearly a* is Nash equilibrium.
Now let a any Nash equilibrium. Note that for 1, the support of o, must be in the above argmax. It follows that for i = 1,2.
u;(a") = un,i(a;) + ui,-i(a".)) = ue,(a;) + un,-;(a 2 (a.( + (a--i(a-s) = (;
B A detailed analysis of Example
Example is already surprisingly rich. We here provide a detailed analysis.
Example 1. Let T be the Prisoner's ' Dilemma as per Table / Then consider the (T, A1, A2, diff) meta game where Å = =[(C, D) 0g R} and diff, diff,((C,, 0, (C,, = 101 0zl + +Z for 1,2 where Z, some real-valued random variable.
Figures 4 5a and 5b illustrate Example I Specifically, 4 considers the case without noise (Z, = 0) and shows for each pair of thresholds 8, 02 whether both agents cooperate (yellow), only one agent (the one with the lower threshold) cooperates (orange), or both defect (blue). Figure 55 and Figure|5bee 5blconiider the case Z; Uniform(( (0, 1)), i.e., the case where noise is drawn uniformly from [0, 1]. Salsows for each pair of thresholds the minimum probability of cooperation across the two players. For instance, if Player submits 0.5 and Player submits then Player 1 cooperates with probability 0 and and Player 2 cooperates with probability 1/2, so the plot in Figure 5alis is (blue) (0.5, 1) (and symmetrically at (1, 0.5)). Figure 5b shows the action of the agent whose threshold is given by the x axis.
Because here restrict attention to policies of type (C, D), policies uniquely specified by single real number& 8. So we will denote them as such.
In addition to threshold policies that correspond to real numbers, we will here consider the agents -oo by which we mean agent that always defects, and the agent co, by which we mean the agent that always cooperates.
14

---

01
(a)
(b)
Figure 5: Visualization the probabilities of cooperation as function of the thresholds in Example with uniform noise Z1, Zo Uniform([O, 1J). For each pair of thresholds (x and y axis), the left graph shows the minimum probability of cooperation across the two players. The right-hand graph shows the probability of cooperation of the player corresponding to the axis.
One might suspect that if there is too much noise, there can be no cooperative equilibria. But it's easy to see that the setting of Example I vaale-inarriant.
Proposition (Scale invariance of noise). Let (T, A2, diff') be diff-based meta game with utility V, where (0,
(0,, 02) = 10 02| + Zú Further, let (1, diff') be a diff diff-based meta O. Then for all 0,, 02. (00, 02) = (' ad2). It follows that for all 01. 02 (01, 82) is Nash equilibrium the diff meta game and only if (00) is a Nash equilibrium in the diff' meta game.
game with utility V', where diff' (0,, 02) 10 02] + aZi for some
B.1 Best responses
In the regular Prisoner's Dilemma, defecting strictly dominates cooperating. Similarly, in the diff' game of Example T always defecting strictly dominates always cooperating (without looking the difference to the opponent).
Definition Let (A1, A2, u) be a normal-form game. Let 01, 01, a E A be strategies for Player 1. We say that very weakly dominates of if for all E A2 we have that un (al10,a0) 2 ui(a1, a2). We further say that aı weakly dominates df if the inequality is strict for least one a2 and that a1 strictly dominates if the inequality is strict for all 02
Proposition The threshold policy oo strictly dominates the threshold policy oc.
Intuitively, in our model there is never a reason submit policy that defects when can be sure that faces exact copy. If the noise lower-bounded, this puts a lower bound on what kind of agent makes sense to submit, as we now show.
Proposition 8. Let Z, 2 8; with certainty. Let 0g 0.. Then 0g very weakly dominates 6%. If P(Z = 02) > 0, 0: weakly dominates 6.
The result shows that the player who submits the higher threshold decreases her threshold while still staying above the other player's threshold, she cooperates with the same probability, Conversely, one cannot (in the setting of Example decrease one's probability of threshold by increasing one's threshold.
Lemma 9. Let 0g 8% 0_, E R with 0 2 8 a Then in (0,, 0),,, Player cooperates with equal probability as in (6), 0_)).
Proof.
--4 P i C's 0,,0-) = P(Z, +0, - 5.)
P < 0-.)
P +0, -0-,
P(PL. iCss 0,00.)
15

---

Theorem 10. Let 0,, 0_ R with 8, 8_ Then u;(0-i; 0-1) 2 (, The inequality is strict if and only if P(20 -i- - 0, < Z_ S 0-1) >
Intuitively, there's never a reason to submit higher threshold than the opponent.
Proof. With Lemma 9 we need only prove that by decreasing 0, to f_, the probability that Player cooperates (weakly) increases. This is easy to see, though for the strictness condition, we need the details:
P(PI. -ic' (0,00, 0,,0+)
P(7-; S 20- 0z)
P(PI. -i C's | 0-10-.) -P(Z,: (12-550.)) S
Clearly, P 50-) 0 2 P (Z_; & 20_,- - 0.). Moreover, the inequality is strict if and only
P(20_; 8, _ Z- (-:) 0.
B.2 (Pure) Nash equilibria
We start with two simple results to We now give some results on the Nash equilibria of Example ! warm up.
Proposition 11. For all distributions of the noise:
1. (-oc, -0o) is a Nash equilibrium.
2. (00, is not a Nash equilibrium.
Proposition 12. If there is no upper bound to noise, then there is no fully cooperative equilibrium.
Proof. If there is no upper bound to noise, then the only policy profile with universal cooperation is (oo, o0). But by Proposition 11 this is not Nash equilibrium.
results on best responses to show that form Nash equilibrium is never necessary for the two players to submit different thresholds.
Next we
Theorem 13. Let (6,, 0_s) be a Nash equilibrium with 0 > 0_.. Then (0_1, 0_.) is also a Nash equilibrium.
Proof. WLOG assume i for notational clarity. Assume for contradiction that (02, 02) is not Nash equilibrium. First, notice that by Theorem and the assumption that 0₁ is a best response for Player 2g. follows that for Player 02 is a response 02. So if (02, 62) is not a Nash cquilibrium, then it must be because for Player 2 02 is not best response to 0g as submitted by
Player 1. So there must be 8/2 such that up (62, 0%)) uz f2, 02). ). By Theorem 10 0' 0z.
We now show that we would then also have that uz uz(01, (f1, 8)) > (21, 02) in contradiction with the assumption that (01, 02) Nash equilibrium. We do this via the following sequence of (in)equalities:
u2 02) uz(02, 02) us (02, 02) u2 02).
(I) By Lemma 9 Player cooperates with equal probability in (0,, 0.) and (02, 05). It is easy to see that Player 2's probability of cooperating weakly lower in (0,, 02). It follows that uz(01, 01) 2 uz(O2 82).
(2) (A) By Lemma 9 Player cooperates with equal probability in (01, 02) and (62, 02). (B) From A and the assumption that 0, E BR, (02) it follows that Player 2 cooperates with equal probability in (O,, 02)) and (02, 02). (Because if this were not the case, then 02 would be strictly better response
for Player to 02.) From A and B it follows that the distributions over actions are the same in (0,, 02)
and (02, 02) and thus that ug ug(02. (02, 02) ug (0,, 02) claimed.
16

---

We are now ready to show the first of our two results about the main text.
Proposition 1. Consider Example with Z; ~ Uniform([O, el) Lid. for some e and with G 2 Then (IC, 01, D), (C, 02, D)) is Nash equilibrium if and only 0f, 02 S 0 or 0 < 01 02 S In case of the latter, the equilibrium is strict if G
Proof. "=": First show that the given strategy profiles really are equilibria.
01, S is just the like the earlier (-o0, -0) equilibrium. If one player plays 0_, S then clearly the unique best response is to also always defect.
2. By Theorem 10 we only need to consider whether of the players, WLOG Player 1, can increase her utility by decreasing their threshold. So for the following consider 01 < 82
P(PI. 1 C's 01,02)
P(02 - 01 - Z1 < 01)
P(Z1 < 201 B2).
This is equal to max(0, (281 02)/c). Clearly, if Player 1 can profitably deviate to some f1, then she can profitably deviate to some 81 s.t. (20) 02) e is nonnegative. After all, Player I wants to maximize Player 2's probability of cooperation. Similarly,
P(PI. 2 C's 01,02)
P(0z 01 7 < 02)
= P(Z <0i)
01/c.
Now 01 0g is best response to 0g if and only if the rate at which P(PL. C's 01,02 decreases is at most G times as high as the rate at which P(PI. C's 0g, 02) decreases. Now the rates of change / derivatives are 2/c and 1 1/c. So this condition is satisfied (for our payoff matrix).
"=": ": It is left to show that no other profile is a Nash equilibrium.
First, notice that for all 0_; > the unique best response is 0, =x=,,, which minimizes the probability of cooperating, while ensuring that Player -i cooperates with probability 1. For this, use part 2 of "<=". From this it follows directly that there is no equilibrium in which both players play > e. By the strictness part +, all equilibria in which one player plays I are as described the result. O
We now prove lemma in preparation for proving our second result for the main text.
2 and assume that the two players have the same noise distribution. Then (0, 0) is Nash equilibrium if and only if for all A > 0, P 2A < 7 < 0 A) <
Lemma 14. Assume
P0
< 0). a strict Nash equilibrium all of these inequalities are strict.
Proof. By Theorem 10 only need to consider deviations to lower threshold. So consider WLOG case where Player deviates from submit A. First, we calculate the probabilities of cooperation under (0, 0) and (0 A, 0):
P(PI. C's 0,0) P(Z < 0) P(PI. 1 C's 0 A,
= P(Z + A < A)
P(Z 2 2A)
P(PI. 2Css 0,0)
= P(Z
P(PI. C's A,0) P(Z+
= P
Thus by Player switching from 0 to 0 A, Player 1's probability of cooperating decreases by
P(Z < 0) P(Z < 0 2 P( 2A Z 6). Meanwhile, Player 2's probability cooperating decreases by
P(Z < - P(Z < 0 A) = P( < 7 6). Thus, for this switch to not be profitable for player 1, it needs to be the case that
P(0 2A < Z Z 0) <
2P A < Z - 0),
17

---

or, equivalently,
P(O 2 2 - P(O A A
as claimed.
Proposition 2. Consider Example 7 with G Assume Z₃ i.i.d. for 1.2 according some uni- modal distribution with mode v with positive measure on every interval. Then ((C, 01, D), (C, (C,82, D)) Nash equilibrium if and only if 0 82 v.
Proof. By Theorem T0 and the assumption of positive measure any interval, all Nash equilibria have the form 0 = 22 The second part follows directly from Lemma 14 and the fact that the noise distribution is unimodal with mode v.
B.3 A different type of noise
Intuitively, we might expect that more noise an obstacle similarity-based cooperation. The above results do not vindicate this intuition (see Proposition (6. We here give an alternative setup with different kind of noise in which more noise is an obstacle cooperation.
Example 2. Consider variant of Example 7 where for i 1.2 have with probability ps that diff, 01, D), (C, 82, D))) = [01 82] + Z, with Z; ~ Unif cl) for some > O; and with the remaining probability diCf, 01, D), (C, 02, D)))
Note that for p1 = 1 the setting is exactly the setting of Proposition !
Intuitively, this models scenario in which each player try to manipulate the diff value 0 and the manipulation succeeds with probability manipulation fails, the other player never learns of the attempt manipulate. Instead, the diff value observed normally if manipulation fails. That way we can assume that each player always attempts to manipulate.)
P.. (It is further implicitly assumed, that
We can generalize Proposition to this new setting as follows:
Proposition 15. In Example 2 ((C,0 D), (C,02, D)) is a Nash equilibrium if and only
01, 02 S 0; or
0 < 81 02 and Gp, for i 1,2.
The proof works the same as the proof of Proposition
C Proofs for Section 4
C.1 Nash equilibria of the base game Nash equilibria of the meta game
We first note two simple results. The first is that every Nash equilibrium of the base game is also Nash equilibrium of the diff meta game in which both players submit policy that simply ignores the diff value.
Proposition 16. Let T be game and be Nash equilibrium of T. For i 1,2, let As be any set of policies that contains the policy Ti: d +> 0g. Then (T1, T2) is a Nash equilibrium of the (T, diff, A1, A2) meta game.
If the diff function is uninformative, then the Nash equilibria are in fact the only Nash equilibria of the diff meta game,
now state.
Proposition 17. Let I. be a game and (T, diff A1, A2) be meta game I where diff =y for some y2. Then (n T2) is a Nash equilibrium of the meta game if and only if (11( (2(2)) is Nash equilibrium I.
C.2 Proof of Theorem
Theorem 3 (folk theorem for diff meta games). Let T be game and be strategy profile for T.
Let A, 2 A; for 1,2. Then the following two statements are equivalent:
1. There is dill function such that there is Nash equilibrium (Tı, T2) of the diff meta game (T, diff. Ar, A2) s.1. (m) na) play ar
2. The strategy profile or is individually rational (i.e., better than everyone's minimax payoff).
18

---

Player 2
41
02
Go
0,0
2, 1
-5, -1
Player 1
01
1, -
- 1,
4, -3
02
1, -5
-3,
-6, -6
Table 2: A game to show the need for assuming high-value uninformativeness in Theorem 4
The result continues to hold true if we restrict attention to deterministic diff functions with diff dill2 and (TI, T2) (0, for 1,2
Proof. "1=2": We show the contrapositive, i.e., that if a is not individually rational, it is not implemented by any equilibrium of any diff game. Let o; be the strategy of Player that guarantees her her minimax utility. Then submitting (ō,, 0, o;) for any threshold 0 guarantees minimax utility regardless of what diff function used. Thus, anything that gives less than threat point utility cannot be an equilibrium.
12=1"" Let o, be Player i's minimax strategy against Player -.. Then consider the strategy profile (m1 = (ō1, 122.01). and x"_ T--, diff( T=-)) = Clearly, in (2), the players play 02). Finally, (T1, 22) is Nash equilibrium of the resulting diff meta game, because if either player deviates they will receive their minimax utility, which is by assumption no larger than their utility in and thus in (11, x2)-
(ō2. 1/2, 02)) and any diff function s.t. diff(T1. T2) 0 and for = 1,2
D On the uniqueness theorem
D.1 Examples to show the need for the assumptions of Theorem
D.1.1 Why the diff function must be high-value uninformative in Theorem 4
We now give an example for why we need diff to be high-value uninformative, both for Lemma 22 and for our uniqueness theorem below.
Proposition (Example) 18. Consider the game of Table 2 Note that the game is symmetric and additively decomposable. Consider the dill' function defined by difl((a) & );)11))1,)) = if supp(oo) U supp(o?) and supp(o,) U supp(o?) ) are disjoint and diff 01 0 otherwise. Then ((az, 1/2, a1),),(()) (av, *, ao)) is an equilibrium of the diff meta game.
Intuitively, the policy (a2, 1/2, a1) with the described diff function implements the following idea: "I want play aı (which good for and moderately bad for you). don't want you to also play an- you are similar to me (which you are if you give weight to the same action give weight to), I'll play ag which is very bad for you." Assuming that Player 1 submits such policy, Player optimizes her utility by always playing ag. Player thus obtains her favorite outcome.
D.1.2 Why the game must be additively decomposable in Theorem 4
The following example shows why need to restrict attention to additively decomposable games. Intuitively, the game a Prisoner's Dilemma, except that if the players cooperate, they also play Game of Chicken for additional payoff. Then (with natural diff function) similarity- maased cooperation takes care of the cooperate versus defect part, but leaves open the Dare versus Swerve part. In particular, there are multiple Pareto-optimal equilibria.
Proposition (Example) 19. Let I be the game of Table 3 supp(T,(0)) for 1,2 and diff T2) = otherwise. Thensoor
Define diff m2) = 0 if ao $
1,
(m: (az, 1/2, 0o), πh (az, 1/2, ao))
a Pareto-optimal Nash equilibrium of the diff meta game on T.
19

---

Player 2
do
Q1
ag
0,0
5, -5
5, -5
Player
Q1
-5,5
0,0
3, 1
02
5,5
1,3
1,
Table 3: game to show the need for the additive decomposability assumption in Theorem 4
Player 2
C
C2
D
C
3,3
2,3
0, 4
Player C2
3,2
2,2
0, 3
D
4,0
3,0
1,1
Table 4: A game show why we need diff be policy-symmetric in Theorem
D.1.3 Why diff must be observer-smmeeric for Theorem
We here give example to show why the diff function in Theorem needs to have (diff, (T), 22), ( π2)) and (Ti T2), diff ( x2)) have the same distribution. One might call this observer symmetry.
Proposition (Example) 20. Let I be the Prisoner's Dilemma. Let diff T2) = 0f = n2 and otherwise. Let d T2) be defined in the same way, except that then there is still an e probability of (iff:((11TT)) T22 =1 c. Note that this diff meta game satisfies the other conditions of Theorem 4 i.e., I is symmetric and additively decomposable, diff(T T2)) and difl TI) are equally distributed for all Iı, and diff is high-value-un pyalue-uiinformative and minimized by copies. Then ((C, 1/2, D), (C, 1/2, D)) has asymmetric payoffs but is Pareto-optimal Nash equilibrium of the diff meta game on T.
diff, (T1, T2)
722-
In this example, the Pareto- Pareto-optimal Nash equilibrium is still unique, but it is easy to come up with examples which there are multiple Pareto-optimal Nash equilibria.
Note also that in this example the player who has less information about the other does better in the cooperative equilibria.
D.1.4 Why diff must be policy-symmetric for Theorem
Finally we give an example to show why the diff function in Theorem 4 needs to have diff T2) and diff (22 1 have the same distribution. One might call this policy symmetry.
Proposition (Example) 21. Let be the game of Table Let diff x2) = (0, 0) if (T1, T2) equals one of the following
(/C2, D), (C1, D))
1/,
D))
(/,1, (C1, D))
(D,
and diff [1, T2) = (1,1) otherwise. Note that this diff meta game satisfies the other conditions
of Theorem 4 i.e., I is symmetric and additively decomposable, diff (T1, (T)) diff (T, π2) for all Ti. 32 and diff is Pareto-optimal (pure) Nash equilibrium of the diff meta game ((C2, 1/2, D), (C1, 1/2, D)).
uninformative and minimized by copies. However, the only
As in the previous example, the Pareto-optimal Nash equilibrium is still unique, but is easy come up with examples in which there are multiple Pareto-optimal Nash equilibria.
D.2 Results the structure of equilibria
We have various intuitions about similarity- cooperation. For example, we have the intuition that (C, 0, D) is sensible policy but (D, 0, C*) is not. In this section we prove results of this type
20

---

under appropriate assumptions. We find these results interesting independently, but we also need all results here to prove Theorem
The following two lemmas capture the idea that under some assumptions is rational to be more cooperative if the opponent similar, i.e., if the observed difference is below the threshold.
Lemma 22. Let (TT1 (22) be a Nash equilibrium of the meta game and diff be high-value uninforma- tive. Then max Uy ( o a S (TT1 T22 for 1,2.
Proof. Assume for contradiction that there is some strategy of s.t. (4 Us (T) m2)-
Because difl is high-value uninformative, there exists policy mi s.t. (T'y TT-) resolves a strategy profile arbitrarily close to of o Hence, uy ( T-4) > (T T2) and so (2)) cannot be Nash equilibrium after all.
L
Lemma 23. Let I' additively decompose into (uyj: A + (), and let diff be high-value uninformative. Let (o Gs, 07 )==1,2 be a Nash equilibrium. Then un,-;(02,;) S -1,- for i = 1,2.
Proof. Follows directly from Lemma
22
Lemma 24. Let T be symmetric and additively decomposable. Let diff be symmetric, high-value uninformative and minimized by copies. Let (T; (a +x, be Nash equilibrium of the diff meta game that induces strategies a1, 02. equilibrium of
02,02. If of = of for some i, then (ø), (2) is a Nash
Proof. With high-value uninformativeness, it follows immediately that a-i is a best response to
The case that o-; o²= ; trivial focus the case where o-i gives positive probability to of. It then follows that -5, is a best response to o; Because the game is additively decomposable, this means that 05, (independent of the opponent's 's strategy) maximizes -i's utility (i.e., a-s arg max ,EA(A..) 1--,- (o'_)) So in particular, a-i is best response d;.
It is left to show that a; is best response to a-i. We will argue that o, is not optimizing Player i's utility (i.e., if a; arg maxa;es(AA) (a,)( then Player i could better-respond to πh by also playing -- instead of π.. Let d't be the strategy induced for both players by (π-;; Because diff is minimized by copies, d'_, gives weakly more weight to 05, than a-i. By Lemma 23 this means that U2 (1,-i(o'_,) 2 (o.-i(o Second, by the assumption that o, doesn' 't optimize 'ss utility but o-, and -f, do, it follows that uz,,(o,) < ut,((o',).
Putting all together we obtain that
ui u (T T44)
u,(o'4 o'r))
un,((o_,) + Ui -i,--(('_ (00'_s) (i.i(as) + ui -i (0-
0=(0
T-1).
as claimed.
D.3 Proof of Theorem 4
Theorem 4. Let I be a player-symmetric additively decomposable game. Let diff be symmetric, high-value uninformative, and minimized by copies. Then if (TI, is a Nash equilibrium that is not careto-dominan there exists a Pareto-optime Nash equilibrium, its payoffs are unique, Pareto-dominant among Nash equilibria and equal across the two players.
by another Nash equilibrium, we have that Vi T2) = V2( ( Hence, if
For the proof we define for additively decomposable games, uyy = Wi, A₁ + Intuitively, ツz denotes the utilitarian welfare generated by Player j's actions. In symmetric games, Wg,1 uy,2
21

---

so that we can simply write ug. For example, in the Prisoner's Dilemma ug: Cooperate G, Defect +
H
Proof. We will prove that if (T, = (o, o2. oo,)))) is a Pareto-optimal equilibrium of the meta game, then both players receive the same utility. The uniqueness of the Pareto-optimal equilibrium follows immediately.
We prove this in turn by contradiction. So assume that (#1, m2) is Pareto-optimal equilibrium of the meta game and that the two players receive different utilities.
Assume WLOG that in (T,, F2) Player receives higher utility. Let 01, 02 be the strategies played in (IT, x2). Then we distinguish two cases:
A) Player 1 "takes" more than Player 2, i.c.,
(1,1 > (2.2(02).
(1)
B) Player does not take more but Player "gives" more than Player 1, i.c.,
(111 S (2.2(02)
and
u2,1(0)) < (1,2(02)
(3)
easy to see that one these cases must obtain.
A) We in turn distinguish two cases:
A.1) First consider the case where
us(a?) 2 uz(off)
We will show that in this case (2) cannot be a Nash equilibrium. Player better-respond by playing the policy #1 that plays of and maximizes (as per the high value uninformativeness condition) Player I's probability of playing oī. This can be seen as follows:
(2( 72)
u2(01, 02)
(2)
Iney
u2
Iney
uz(otmax max ot)
Lemma
U2 ( R2)
A.2) Now consider the case where
us(a?) I uz(of))
(5)
We will show that in this case Player better respond by also playing मं instead of π2, such that (Ti, m2) (again) cannot be a Nash equilibrium.
Let of be the strategy played by both players in (II, m1). Note that because diff is minimized by copies, of gives at least as much weight to of as 01.
(2( m
u2 oi) 01)
u2(01, 02) Ineq
Ug (Ti, T2)
B) We again distinguish two cases.
22

---

B.1) First consider the case where
ux(oa² S u
We will show that in this case (I22, m2) is also Nash equilibrium and that (T2, m2) Pareto-dominates (Ti, x2)-
First, we show Pareto dominance. Let o2 be the strategy played by both players in (T2, T2). Because diff is minimized by copies, 02 gives least much weight of 02. Then for Player we have that
(TI, x2) = 02)
u1 (12, 02)
Incq
(7)
(d 022
(T2, T2).
Ineq
Player 2's utility strictly higher (T2, T2), which we can see as follows:
U2 (TT1, 72)
u2(01,02) u2(02, 02)
Tneq
u2(02, 02)
Iney
u2 (2 T2).
is left to show that (T2, m2) a Nash equilibrium. By assumption, æi a best response to m2- Line 7 therefore implies that Ty is also best response T2. Because of symmetry, this is true for both players. We conclude that (T2, T2) is Nash equilibrium.
B.2) Let
uz(0²) (z(
(8)
We now must make one more distinction. Consider first the case where = o.. By Lemma 24 (o,, 22) must be Nash equilibrium r. The contradiction follows immediately from Proposition
Now consider the case where 02 # o. With Ineq.
follows that
u1 (n(22,0)) 02) < u1 o..).
We will show that (T1, R2) not an equilibrium because Player can better-respond by playing the policy गn that plays oº and maximizes as per the definition of high-value uninformativeness Player 2's probability of playing oz. Then
Ui (TI
ui 02)
u1 02)
Ineq
ui(0z 03?)
Ineg.
u1 omaxx
I Lemma 2
un ( T2)
E Theoretical analysis beyond threshold policies
We here analyze functions. The goal to show an equilibrium based on linear functions, similar to the equilibria found by CCDR pretraining.
game in which players not only submit threshold policies but continuous
policy now a function T: R>0 + [0, 1]. where x(x) denotes m's probability of cooperation. For differences F1, F2, the payoff of Player i is given by
(1 (x(Z)) G (x-(x-))
23

---

1,0
0.8
0.6
0.5
1.0
1.5
2.0
255
3.0
Figure 6: Visualization the continuous policy in Proposition
25 for a = 1. The probability of cooperation plotted against the perceived difference to the opponent.
It is left specify the difference function. Let and K Then define the function difference
1 d(Ti, R2) = K |T](x) - T2 (2)
ck
Further, define the probabilistic difference mapping (TI T2) = d(TTI T2) + Z;. where Ze is drawn uniformly from e). As the set of policies for each player consider the of integrable functions.
Proposition 25. Les (x) max (1 z/a, 0) for some and only if 1 + aK/e= S G.
Then (π,, x) is a Nash equilibrium if
Note that decreases cooperation linearly in x down to 0 (which hit at x a). This function is shown in Figure 6 for a = 1. Note that our policies look roughly like this after Step 2.
Proof. Consider (H,, T) and imagine that, WLOG, Player moves away from a by A, i.e. deviates to play some n' s.t. d(m, x = A. It is easy to see that it is enough to consider small deviations. Specifically, we assume < a - e. First, if the difference between the policies increases by A, what happens to Player 2's expected amount of cooperation? It is easy to see that this decreases by A/a.
Next, we need ask: by increasing the difference by A, how much can Player increase her probability of defection? We need to consider two effects. First, if the difference increases by A, then automatically Player defects more by the same effect as Player So this gives Player an extra A/a probability of defection. Moreover, Player can decrease the probability of cooperation on the relevant interval A, A + cJ. This decreases the probability of cooperation by (at most) K Ka/e.
Taking stock, Player can increase her probability of defecting by A/a + KA/e at the cost of Player increasing her probability of defecting by A/a. This good for Player if and only if 1 + aK/e > G.
Details on our experiments
F.
Software
We used pytorch for implementing CCDR and ABR and functorch for implementing LOLA. We used floats with double precision (by running torch. pet_default_dtee (torch. float64)), because preliminary experiments had shown numerical issues as ABR converged. We used Weights and Biases (wandb. ai) for tracking.
F.2
Game and meta game
We here give some details on the game and diff meta game we consider throughout our experiments.
Constructing fD, Sc In our experiments fD, fo have input dimension 10 and output dimension 3. (Thus, including dimension for the similarity value, our policies have input dimension 11.) First we generate Sc, and sp, for = 1, 2, 3 from {0, 1 uniformly at random. Then we define
fc(x) = (sin(sc,s x))
We define fo analogously based on sp.
24

---

We chose this function because it is very simple to understand and implement and at the same time requires using larger nets. The only other approach we tried in preliminary experiments to generate fc, JD by randomly generating neural nets. The problem is that large randomly generated fully connected neural nets are close to constant functions.
Constructing 1r Recall that for any pair of actions f1, f2. the payoff's of the HDPD given by u; (fi, f2) = -Ex~n [x)f((x), [x)) (d) is some measure of Rio. Thus, to construct a specific instance of the HDPD we need to also construct μ.. We do this by generating 50 vectors uniformly from [0, 1l10 and then taking the uniform distribution over these vectors.
where d is the Euclidean distance and
Constructing the noisy diff mapping Recall that ( T2)
((yx)~ [d(TT (V, x), x2)x + Z, where is some probability distribution over R=+1 and Z; some real-valued noise. We need to specify v and the distribution Z,. For we first generate 50 reals from [0, 0.1] uniformly at random as our test diffs. We increment each of these by random draw from the underlying noise distribution, i.e., by a number drawn uniformly at random from [0, 0.1]. We then define y to be the uniform distribution over 50 values that result from pairing the support of j with these values.
For the noise we generate for each player 50 values uniformly from [0, 0.1] and then use the uniform distribution over these 50 points.
Note that by using the uniform distribution over a finite support, we can compute expected utilities in the meta game exactly.
F.3 Neural net policies
Throughout our experiments, our policies Ta are represented by neural networks with three fully connected hidden layers of dimensions 100, 50 and 50 with biases and LeakyReLU activation functions. Thus, these networks overall 8964 parameters.
=
F.4 Methods as used our experiments
CCDR pretraining We here describe in more detail the CCDR pretraining step in our results. Recall that CCDR pretraining consists in maximizing (T To.) + (T Tb__) for randomly generated opponents %/__, Call - -V Te,) + (T (T ) the CCDR loss.
In our experiments, we maximized this by running Adam for 100 steps. In each step, the CCDR loss calculated by averaging over 100 randomly generated opponents. The learning rate is 0.02.
Alternating best response training We ran alternating best response training for 7 = 1000 turns. We need to specify how we updated 0, to maximize ((0, f_:) (holding 0_, fixed) in each turn. For this that are successful, i.c. that in fact reduce loss. The learning rate 7 is sampled uniformly from [0, y 0.00003] in each step. Note that by randomly sampling the learning rate, the algorithms avoids getting stuck when a gradient step is unsuccessful. We summarize this in Algorithm [
gradient descent for T' = 1000 steps. However,
only take gradient steps
F.5 Convergence to spurious stable points?
In theory, alternating best response learning could converge "very local Nash equilibrium", i.e., pair of models that are best responses only within a very small neighborhood of these models. One might also worry about convergence to other stable points (Mazumdar al. 2020).
However, as far as we can tell, the limit points of our learning procedure are not spurious. To confirm this, we performed the following test (implemented by the function best best_response. test of our code). For a given pair of models, we pick either model and perturb each its parameters little. We then whether the perturbed model is better response to the opponent model than the original model. In an (approximate) local Nash equilibrium, this should almost never be the case.
In all but one of our successful runs (the ones converging to partial cooperation), none of 10,000 random perturbations of each the models after alternating best response training led better response to the opponent model. In one run, three perturbations of one of the models decreased loss.
25

---

Algorithm Alternating best response learning
Input:
Initial model parameters 0,, 02. T,T" N, learning rate Output: New model parameters 02,00 for / = 1,.., do
for = 1,2 do
for t' -,.,,, T" do
y' ~ Uniform((0 7
8 8 + Vor V 8"
if (( 0' ,) V(0i 0 then
04 + 0
end if end for end for end for return 8 8
When applying the test after CCDR pretraining but before alternating best response training, close to half of random perturbations improve utility.
F.6 Compute costs
We here provide details on how computationally costly our experiments are. To do SO, we ran the experiment for single random seed on AMD Ryzen PRO 4750U, laptop CPU launched in 2020. (Note that we used the CPU not GPU (CUDA).) The CCDR pretraining took about 30 seconds per model. The ABR phase took about 3h. (Note that we ran most of our experiments as reported in the paper via remote computing on different hardware.)
G Experiments with LOLA
We have tried to learn SBC using Foerster et al. (2018) Learning with geppoeent-Learning Awareness (LOLA). We here specifically report on an experiment in which we tried broad range of parameters. The results are in line with prior exploratory experiments.
LOLA sometimes succeeds in learning SBC (without CCDR pretraining). It finds similar policies as CCDR pretraining. Some the SBC models found by LOLA remain cooperative throughout a subsequent ABR phase.
Unfortunately, none of our LOLA results are nearly as robust as the CCDR results reported in the main text and in Appendix F Specifically, they are not even robust to changing the random seed. One reason for this is that LOLA capable of "unlearning" LOLAA-larrndd SBC.
G.1 Experimental setup
We ran Foerster et al. (2018) Learning with Opponent- Awareness (LOLA). We tried every combination setting the learning rate and lookahead parameter in LOLA to values in 0.0003, 0.001, 0.003, 0.01, 0.03, 0. 0.3, 1. For each combination we tested both exact and Taylor LOLA as described by Willi et al. [2022 Sect. 3.2). We tested each of these 8 8 2 = 128 combinations with 5 different random seeds. In each of these experiments we initialized the nets randomly and then ran LOLA for both agents for 30,000 steps. We then ran ABR training as described in Appendix [F4 for at most 500 steps, to whether the resulting policies in equilibrium. To save compute, generally aborted ABR when the loss hit the Defect-Defect utility of 5 or when it was clear that ABR learning had converged.
We then labeled each individual run as a "weak LOLA success" if the loss after the LOLA phase was smaller for both players than the loss of mutual defection and as a LOLA-ABR success if the loss after the ABR phase was smaller for both players than the loss of mutual defection.
For each parameter configuration in which at least 3 out of 5 runs were a weak LOLA success we ran another 20 runs (with different random seeds) without the ABR phase to determine how robust the success is. Similarly, for each parameter configuration in which at least 3 out of 5 runs were LOLA-ABR success we ran another 20 runs with the ABR phase.
26

---

8
3
0
5000 10000
130000
20000
25000
30000
Time Step
Figure Loss curve of relatively successful run between two LOLA agents.
G.2 Qualitative analysis
We start with a qualitative discussion of our results, because the experiments with LOLA exhibit a much wider range of complex phenomena than the CCDR-based results.
G.2.1 A few clear-cut successful runs
Out of the runs in our experiment, few are as clear-cut successes as most the CCDR runs. Figure 7 shows the learning curve of one of these runs across both the LOLA and at the end the ABR phase. It uses a lookahead cooperate with each other in the LOLA phase. When the switch ABR is made after 30k steps of LOLA, cooperation deteriorates slightly, but ultimately the models converge in the ABR phase to an outcome with loss well below the loss of mutual defection. This shows that LOLA is to some extent capable of solving the given problem.
0.001, learning rate of 0.001 and exact LOLA. The players learn to
Unfortunately, both in the present experiment and in preliminary experiments we have found that these results are not even robust to changing the random seed. For example, the four other runs with the same parameters as the run from Figure (but different random seeds) all failed to produce significant positive results. (One resulted marginal cooperation at the end of the LOLA phase (losses 4.986 and 4.928) that disappeared immediately when switching ABR learning. Another partially cooperated for some the LOLA phase but failed to retain cooperation even until the end of the LOLA phase.)
G.2.2 What models LOLA learns
Generally, when LOLA succeeds, it learns similar models as CCDR pretraining. The main difference is that for high diff values, LOLA models typically do not exactly defect. (Of course, it also does not cooperate. Instead if performs an action far from both fc and fD.) This is to be expected, since these agents are not trained on randomly generated opponents. An example model after 30,000 steps of LOLA is shown in Figure g
When LOLA does not succeeed, the learned models vary greatly. Some are clearly set up to impose some incentives others just constantly defect.
G.2.3 Instability in the LOLA phase
The learning in the LOLA phase is often highly unstable. That is, the during the learning phase, the change in losses in a single learning step often very large. This occurs even in successful runs. As an example, consider the learning curve in Figure 9 (lookahead 0.003, learning rate 0.01, exact LOLA). While it is unclear whether cooperation would have survived further ABR learning, this run is relatively successful. However, the utilities vary by large amounts during the LOLA phase. In fact for parts of the LOLA learning phase, both players' losses are much higher than the loss of mutual defection. Most successful runs with LOLA look like this. Of course, successes based on such runs cannot very robust: if we had ceased LOLA learning somewhat earlier, the run would not have succeeded. It is unclear what would happen if the run had run for more than 30k LOLA steps.
27

---

tyl-y C.le. calo00000) Dittnno of to
2.
05-
0.0
5.2
0.4
0.5
0.5
1.0
Figure 8: An example of model found successful LOLA run.
7
6-
5-
4-
5000
10000
15000
20000
25000
30000
Time stop
Figure 9: An example of the loss curve from highly unstable LOLA run.
G.2.4 Cooperation in the LOLA phase versus cooperation in the ABR phase
While CCDR is explicitly a pretraining method, LOLA can also be used as a standalone learning procedure. So for each run, we can ask both whether the players cooperate, say, at the end of the LOLA phase and whether the players cooperate at the end of the ABR phase, It turns out that all four combinations of answers are possible! In particular, there are runs in which LOLA versus LOLA fails to converge to a pair of policies that give both players a higher utility than mutual defection; but in which ABR then converges to an outcome that is marginally better for both players than mutual defection.
G.3 Quantitative analysis
Bearing in mind the different qualitative phenomena, here give more quantitative analysis.
[ the parameters which least three out of five runs exhibited weak LOLA success as defined earlier. They also summarize the result of 20 further runs with these parameters. Specifically, we categorized runs as stable successes if the loss was below the loss of mutual defection for both players for the final 5,000 LOLA steps. We categorized them unstable successes if the loss was below the loss of mutual defection for both players for the final 50 but not the final 5,000 LOLA steps. The fourth and fifth columns of Table 5) show the numbers of these different kinds of successes out of 20 runs. The sixth colum shows the average loss across both players and all successful runs. The final column shows the standard deviation across the losses of the successful runs (also across players).
o the set of parameter configurations that achieved LOLA-ABA success in least three out of five runs. They also summarize the result of 20 further runs with each of these parameter configurations. Specifically, we categorized runs again as stable successes if loss was below the loss of mutual defection for both players for the final 5,000 LOLA steps and at the end of the ABR phase. We labeled them as unstable successes the loss was below the loss of mutual defection for both players at the end of the ABR phase but not for the final 5,000 LOLA steps. Again, the
28

---

LOLA
LOLA
Taylor LOLA
Stable Successes
Unstable Successes
average success loss
SD
LA
LR
0.003
0.0003
false
5
1
4.518
0.2857
0.001
0.01
false
0
4.666
0.002601
0.001
0.003
false
5
7
3.579
0.6096
0.0003
0.003
true
3
7
4.299
0.1482
0.0003
0.003
false
4
3
4.506
0.07975
0.0003
0.001
true
4
4.344
0.2466
Table Parameters for which least three of five runs resulted in partial cooperation the end of the LOLA phase along with results of further 20 runs per parameter configuration..
LOLA LA
LOLA
Taylor LOLA
Stable
Unstable Successes
average success loss
SD
LR
Successes
0.0003
0.003
true false
12
4.279 4.344
0.2830 0.2566
0.0003
0.003
Table Parameters for which least three of five runs resulted in partial cooperation the end of the ABR phase along with results of further 20 runs per parameter configuration.
fourth and fifth columns of Table show the numbers these different kinds of successes out of 20 The sixth column shows the average loss across both players and all successful runs. The final column shows the standard deviation across the losses of the successful runs (also across players).
From these results conclude that LOLA can succeed under various parameter configurations, but none of the parameter configurations succeed nearly as reliably as CCDR pretraining.
G.4 Compute costs
We again provide details on how computationally costly experiments To do so, the experiment for a single random seed on an AMD Ryzen' 7 PRO 4750U. The LOLA phase took about 20 minutes. The ABR phase took about 1h and 30min. Note again reported the paper via remote computing on different hardware. Note also that we ran ABR for half many steps compared the experiments for the main text (500 instead of 1000). So, the cost per ABR step is roughly the same between the two experiments.
most of experiments as
H Distantly related work
H.1 Learning in Newcomb-like decision problems
There is some existing work learning Newcomb-like environments that therefore also applies to the Prisoner's Dilemma against a copy. Whether cooperation against copy is learned generally depends the learning scheme. Bell al. (202T) show that Q-learning with softmax policy learns to defect. Regret minimization also learns to defect. Other learning schemes do converge to cooperating against exact copies (Albert & Heiner 2001; |ayer et al.) 2016) Oesterheld 2019a Oesterheld et al. 2023). All schemes in prior work differ from the present setup, however, and to our knowledge none offer a model of cooperation between similar but non-equal agents.
H.2
Cooperation via iterated play, reputation, etc.
Perhaps the best-known way to achieve cooperation in the Prisoner's Dilemma is to play the Prisoner's Dilemma repeatedly (e.g., [xelrod 1984, Osborne 2004] Ch. 14, 15). Clearly, the underlying mechanism (repeated play) very different from the mechanism underlying SBC, in which the game is played one-shot. That said, our folk theorem (Theorem 3 is similar to the well-known folk thcorem for repeated games. (As noted in Section 7 the folk theorem for program equilibrium is also similar.) number variants of iterated play have been considered to study, for example, reputation effects, effects of allowing players to choose with whom to play based on reputation, and so on (c.g., Nowak Sigmund 1998).
While cooperation via repeated play is very different from similarity bassdd cooperation as studied in this paper, some variants of the former are easy to confuse with the latter. As a simplistic example, consider variant of the infinitely repeated Prisoner's Dilemma. Typically, it is imagined that players observe the entire history past play. But now imagine that instead the players each round only observe single bit: 0 if they have taken the same action in each round so far and otherwise.

---

Then it is (subgame -erreeeteeeeet Nash equilibrium for both players to follow the following strategy: cooperate upon observing and defect upon observing 1. This is somewhat similar to similarity- based cooperation, but the underlying mechanism is still the one of repeated play: the reason it is rational for each of the players to cooperate is that if they defect, their opponent will then defect in all subsequent rounds. In fact, the strategies played are equivalent to the grim trigger strategies for the iterated Prisoner's Dilemma.
As another example of cooperation via repeated play that can be confused with SBC, consider assortative matchmaking as proposed by |Wang et al. (2018) Sect. 2.4). Imagine that agents in a large population are repeatedly paired up to play a Prisoner's Dilemma. In each round, each agent is matched up with a new opponent who is similarly cooperative as they are. Again, similarity plays a role, but the underlying mechanism is very different from the ones studied in our paper. For one, similarity is used by the environment (the matching procedure) not the agent itself. Second, the reason why cooperation is rational is again its impact on rewards in subsequent rounds. For instance, imagine that for some reason an agent has, e.g., by accident, defected in the first few rounds and is now matched with uncooperative agents. Then it may be rational for the agent to cooperate in order to be matched with more cooperative agents in the future, even if it knows that will receive the sucker's payoff in the current round.
H.3 Tag-based cooperation
In the literature the evolution of cooperation and in particular population dynamics, researchers have studied so-called tag-based cooperation Riolo al.] (2001); Cruciani al.; (2017); Traulsen & Claussen (2004): [Traulsen] (2008), which has sometimes also been referred to as similarity-
cooperation. The underlying mechanism is very different from similarity-bas cooperation as studied
in the present paper, however.
In models of tag-based cooperation, an agent is defined not only by a policy but also by tag that has nothing to do with the policy. When choosing whether to cooperate with each other, agents can see each other's tags. Thus, the policies can choose based on the other agent's 's tag. For example, one policy could be to cooperate if and only if the two agents have the same tag. Notice that in tag- tag-based cooperation, only similarity of tags is considered. In contrast, our paper feeds the similarity of the policies themselves as input to the policy.
Because the tag is not tied to the policy, tags are effectively cheap talk that have no impact on the Nash equílibria of the game. For example, consider the following meta game on the Prisoner's s dilemma. Each player i submits tag т; {1, 100} and policy m;: {1,... 100} ~ DJ that stochastically maps opponent tags onto actions. Then actions are determined by a; = (T-).) for i = 1, Each player receives the utility un (011 a2). It is easy to see that in all Nash equilibria of this game, both players submit a policy that always defects. So tag- based cooperation does not help with achieving cooperative equilibrium in two-player Nash equilibrium. In contrast, miillarttybbsee cooperation as studied in this paper does allow for cooperative equilibria in two-player games, as the main text has shown.
So why might one study tageb cooperation? Perhaps one would expect that any population of evolving agents would converge to defecting in the above lag-based Prisoner's 'ss Dilemma. Interestingly. it turns out that this is not the case! As computational experiments conducted in the above works show, evolving populations sometimes maintain some level of cooperation when they can observe each others' tags. Because cooperation is not an equilibrium, cooperation is maintained dynamically, i.., by population whose distribution of tags and policies continually changed. Roughly, the reason seems to be the following. By mere chance (from mutation) there will be tags whose individuals are more cooperative toward each other than the individuals associated with other tags. The cooperative tags and their associated cooperative policies will therefore become more prominent in the population. Of course, this cannot be stable: once an agent is discovered that has the cooperative tag but defects, this type of agent takes over within the cooperative population. But in the meantime a new cooperative tag may have emerged. And forth. This mechanism for achieving cooperation seems to have no parallel at all in our model of similarity-based cooperation !
'See also Nowak & May (192) for another line of work that is even more different from the present paper. but in which unstable cooperation survives dynamically by similar mechanisms.
30

---

H.4 The green beard effect
The green beard effect (Hamilton 1964 Dawkins 1976 Ch. 6; Gardner & West 2010) refers the idea that there could be a gene 9 that causes individuals to be altruistic to people who also have the gene without relying kinship identify other people with the gene G. In partieular, imagine gene 9 with the following three properties:
1. Gene G causes people with the gene to have some perceptible trait. For concreteness let the trait consist in growing green beard.
2. Gene 9 causes people to be altruistic toward people who have a green beard, e.g., to cooperate with them in one-shot Prisoner's s Dilemma.
3. People without gene G cannot develop a green beard.
Then such a gene could spread and be dominant in a population.
Hamilton and Dawkins discuss the green beard effect as theoretical idea. To what extent the green beard effect a real biological phenomenon is subject to debate. Some candidates were pointed out by Keller & Ross (1998). Queller et al. (2003), (muuaalaa et al. (2008) (cf. [Sinervo et al., 2006).
On first sight, similarity- cooperation as studied in this paper and the green beard effect might seem similar. For example, if you observe population of individuals, some of whom have the green beard and some of whom do not, you will see cooperation between agents that are similar (in that they both have the green beard). A connection between similarity- based cooperation and the green beard effect has been noted before by Howard 1988) Stěpán Vesely 20011). and Martens (019))
On second sight, however, think that similarity -based cooperation as studied in our model is very different from the the green beard effect as an evolutionary phenomenon. To understand why, we take the cene-centered view of evolution (e.g. [Dakkins] 1976): we view evolution as a process that produces genes that take measures to spread themselves (as opposed to a process that creates organism with particular properties). Now imagine that two individuals sharing the gene play Prisoner's Dilemma where they can either take I unit of a resource for themselves or give G > 1 units of the resource the other player. Then from the perspective of trying to spread G, this is not Prisoner's ' Dilemma at all! (This is assuming that both players can make similarly good use of the resources.) From the gene's 's perspective, dominates defecting. This is the essence of how the green-beate effect works. Our model of SBC has no analogous mechanism or perspective.
a fully cooperative game wherein cooperation simply
As a result, the green beard effect allows for a very different set of outcomes than our folk theorem (Theorem (3). For example, imagine that organisms 1 and both share G, that organism I can either take unit of resource for itself or give G > units of the resource to organism 2, and that organism faces no choice that concerns organism Then & would still have the organism give, because doing so increases the spread of the gene. Meanwhile, the unique outcome allowed by our folk theorem has organism not give. In other games, our folk theorem allows for many different equilibria of the meta game. In contrast, in game played by two organisms who share G. there will typically be unique outcome that best spreads G.
H.S Studies of human psychology on similarity-based cooperation
In this section, we review empirical and theoretical work in psychology related to the phenomenon of similarity- cooperation.
Studies have shown that humans often cooperate in the one-shot Prisoner's Dilemma, contrary to what standard game theory recommends. Many explanations have been given for this phenomenon.
few authors have proposed explanations based on Newcomb's 's problem as discussed in Section 7
That is. they have proposed that people cooperate in the Prisoner's Dilemma because cooperating gives them evidence that their opponent will defect (Krueger & Acevedo, 2005 Krueger et al. 2012).
To test this hypothesis, few studies have tried measure the correlation subjects' choice in Newcomb's 's problem and the Prisoner's Dilemma. The results have been mixed, Goldberg et al. (2005
Sect. 4.3). Tversky& Shafir (1992) have found strong correlations, while (Toplak & Stanovich (2002)
and Goldberg et al. (2005) Sect. 4.2) have failed to find such correlations. Another prediction of the Newcomb's 's problem/SBC explanation for human cooperation the one-shot Prisoner's 's Dilemma is
that individuals are more likely to cooperate with similar than with dissimilar individuals. Indeed,
a number of studies have found this to be the case (e.g. Acevedo Krueger) 2005) Fischer 2009).
(Note that some other theories have been proposed for this phenomenon well (c.g. Aksoy 2015
31

---

Another related idea in social psychology is homophity, which refers to the observed tendency of humans to be more likely engage in interactions with similar individuals. (Homophily cannot always be cleanly differentiated from the tendency to be more altrusttie/copperttiv toward similar individuals as discussed in the previous paragraph.) Homophily could also explained by SBC, because SBC allows for better outcomes (e.g., mutual cooperation over mutual defection) when playing against similar individuals. We are not aware of any discussion connecting homophily with Newcomb's s problem or the idea that it could be rational to cooperate in a Prisoner's Dilemma against a copy. The theory the evolution homophily seems to that individuals with similar cultural background can more effectively communicate (and coordinate) (Fu et al. 2012). This is different from SBC as studied in the present paper.
32


Reviews:
[{"review_id": "pHecsuneop", "reviewer": "Reviewer_2ynN", "summary": "This paper considers the problem of two agents trained by machine learning who interact in a social dilemma.  The agents are able to observe a numeric measure of the similarity of their learned policies, and condition on this similarity when choosing their actions (in contrast to the \"full transparency\" case, in which the agents can each observe the other's full source code).  When policies can condition on similarity, cooperation can be supported in equilibrium (similarly to various full transparency results in the literature).\n\nWhen partially-transparent policies are naively trained, they tend not to learn to play toward cooperative equilibria; however, the paper demonstrates that pre-training by averaging between playing against the same policy and a randomly-sampled policy can enable machine learned models to find partially cooperative equilibria.", "questions": "Have you evaluated your approach on non-additively-decomposable games?\n", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "This paper correctly observes that partial transparency supports the same equilibrium outcomes as full transparency, while being dramatically more plausible.  The results are carefully derived and clearly presented.  The paper studies a possible approach to solving an important problem; social dilemmas succinctly describe a fundamental problem in many situation where agents would all gain by cooperating.\n\nThis paper takes a step beyond proving the existence of equilibria, and demonstrates that plausible training procedures can actually find them.\n\nThe notion of similarity is based on the similarity of the policies considered as functions, rather than being computed on weights or some other parametric representation.  This is very natural, and I think it's an improvement over the \"source code\" based approach that earlier full-transparency literature tends to appeal to.", "weaknesses": "My main concern is that the results really only apply to a very specific class of games (player-symmetric additively decomposable games).  It makes sense that the equilibrium uniqueness results of theorem 4 should be narrowly targeted (it's hard to prove things about large classes of games), but I would have liked to see some experimental examination of whether the proposed approach works well on games that don't satisfy these restrictions.\n\nThe procedure described still tends not to find fully cooperative equilibria, which seems like a shortcoming.\n\n\n#### Minor issues (did not affect rating)\n\n- p.1: \"While partial transparency is the norm\": This is a pretty strong claim, and one which is important for the main claims of the paper.  Could you back it up with a citation or example or something else beyond a bare assertion?\n- p.2: \"In particular, full transparency can make the problem of equilibrium selection harder\": Isn't this also true of partial transparency?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 2ynN for their detailed review!\n\n>My main concern is that the results really only apply to a very specific class of games (player-symmetric additively decomposable games). It makes sense that the equilibrium uniqueness results of theorem 4 should be narrowly targeted (it's hard to prove things about large classes of games), but I would have liked to see some experimental examination of whether the proposed approach works well on games that don't satisfy these restrictions.\n>\n>Have you evaluated your approach on non-additively-decomposable games?\n\nRegarding further experiments on games that break our restrictions: We agree that it is important to study more types of games. We have run some informal experiments on games that are only approximately additively decomposable and only approximately symmetric (while using diff functions that ignore these slight asymmetries). Generally the results in these settings are – unsurprisingly – similar to the current setting. We are also currently working on a second project about similarity-based cooperation that studies more radically different games (such as Chicken, repeated games) and explores more different methods (mostly other methods from the opponent shaping family). We have decided to leave further experiments on other types of games to a different paper for the following reasons.\n\nMost importantly and mundanely, any new experiments would require extra space to describe, especially if new conceptual issues need to be addressed. For example, for an experiment with non-additively decomposable games, we would have to first define such a game a la HDPD (assuming we want the experiments to be comparable), which is non-trivial. We would also need to somehow address the difficulties of using CCDR in non-additively-decomposable games. (It may work very well without any specific modifications, e.g., in Chicken, but we would have to explain why it works.) Using the Prisoner’s Dilemma as a running example throughout the paper provides intuition for the more complicated HDPD. If we use a substantially new game – say, Chicken – we would have to first build up intuition for it. (What do we even expect the SBC equilibria to look like? Etc.) We don’t think we have the necessary space to spare to do all this – one could argue that we already rely too much on discussing details and results in the appendix that should be discussed in the main text (e.g., the LOLA results).\n\nWe also think that many such further experiments are a more natural fit for future projects than they are for the present one. Generally, the main research question behind the experiments in the present paper is whether SBC equilibria in complex settings (as opposed to the very simple settings studied by theory) can be found with machine learning. It’s not clear a second example like a high-dimensional version of Chicken would add much to answering this question (at least if the complexities involved are very similar to those introduced by the HDPD). Secondarily, because the HDPD is closely related to our theoretical settings, our experimental results test whether our theoretical results apply in a more complex setting. It seems more natural to study other game-theoretic dynamics such as Chicken in contexts where one can ask more concrete questions. For example, if one could get opponent shaping to work in diff games, one could ask whether opponent shaping methods learn (non-diff-based) asymmetric Dare–Swerve equilibria or diff-based Swerve–Swerve equilibria.\n\n>p.1: \"While partial transparency is the norm\": This is a pretty strong claim, and one which is important for the main claims of the paper. Could you back it up with a citation or example or something else beyond a bare assertion?\n\nWe will clarify the claim mentioned on p.1 – thanks for pointing it out! We here merely mean that it is common to have some non-trivial information about the other player other than that they are a rational agent with a particular utility function and particular beliefs. We do not yet want to make a claim at this point about how commonly this information induces new, better equilibria.\n\n>p.2: \"In particular, full transparency can make the problem of equilibrium selection harder\": Isn't this also true of partial transparency?\n\nRegarding the claim on p. 2: Yes, that’s correct and we’ll need to clarify this as well in the paper. What we meant to refer to here is that full transparency makes the equilibrium selection problem very difficult; diff games seem to avoid this under some assumptions. Our paper does not say anything about other kinds of partial transparency and what they do to the equilibrium selection problem. All of this is unclear at this point in the paper."}, {"review_id": "xTq5rgi4UW", "reviewer": "Reviewer_EVhh", "summary": "Training AI agents that will reliably cooperate, both with humans and with other AI, is one of the principal goals of AI alignment research, and the prisoner's dilemma (PD) is simple game that has long been used to study cooperation.  PD is interesting because it has only one Nash equilibrium: to defect (i.e. not cooperate), which is a somewhat paradoxical result because mutual cooperation would be better for all participants.  The usual modification to PD is the iterated prisoner's dilemma, in which each agent can observe a history of past interactions.  This history opens up new equilibria, and allows agents to learn to cooperate.   \n\nThis paper proposes another potential modification to PD with cooperative equilibria, namely supplying each agent with a measure of the similarity between its policy, and the policy of other agents.  Agents can learn to cooperate with similar agents, and defect against dissimilar ones.  The paper proves some basic theorems about equilibria in such games.\n\nThe paper also proposes a variant -- high-dimensional PD (HDPD), which has a more complex notion of \"cooperate\" and \"defect\" than simple PD.  Naive training of an agent in HDPD does not result in cooperation.  However, the authors introduce a pre-training mechanism called Cooperate against Copies and Defect against Random (CCDR), in which agents alternate self-play (i.e. play against perfectly similar copies) and play against random opponents.  When using this pre-training mechanism, agents learn to cooperate.  ", "questions": "\nFrom an AI alignment perspective, can a meaningful measure of \"similarity\" can be derived for more complex agents, operating in more complex environments?  In more complicated cases, the only reliable information that an agent can observe about other agents is the history of past actions, in which case the notion of \"similarity\" becomes much the same as the iterated PD, or other reputation-based systems.  \n\nIs it possible for agents to game the system, and hack the similarity function?  This is probably relevant only for more complex agents than those considered in this paper, but is extremely import wrt. to AI alignment.\n\nIs it possible to derive a notion of similarity that would enable otherwise dissimilar agents to cooperate?  E.g. among humans, people with very different goals and backgrounds can cooperate if both parties agree to follow the same \"moral code\", or \"rule of law\".  \n", "limitations": "\nAlthough this paper has potential applications wrt. to AI alignment, the authors focus primarily on detailed mathematical analysis, and fail to discuss the larger social implications.   \n\nHowever, I applaud the authors for their frank and open discussion of the limitations and failures of CCDR.  IMO, that discussion is one of the most valuable parts of the paper.  \n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Although it is not mentioned by the authors in the paper, I would like to note that \"perceived similarity\" does, in fact, appear frequently in the natural world.  Kin selection (genetic similarity) is the basis for cooperation among social insects like ants and bees, and shared language, culture, and religion have historically been the basis for cooperation among humans.  IMO, this is thus a potentially important avenue of research, which has been overlooked in the literature.\n\nThe paper is well written, and the results seem solid.  The authors have an excellent discussion of the limitations of CCDR -- in particular, after learning to cooperate during pre-training, some agents partially unlearn it during the rest of training.   Further exploration in this area could have potential applications on AI alignment research.\n", "weaknesses": "\nMy main concern is this is mostly a paper on game theory, so I question whether NeurIPS is really the right venue for it.  The actual experiment also seems somewhat simplistic to me.  I believe that the primary application of this work relates to AI alignment, so I would have preferred to see more discussion about how these ideas could be applied to the real world.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank EVhh for this insightful review! We address the point about realistic settings and gaming the similarity metric in the general response.\n\n>My main concern is this is mostly a paper on game theory, so I question whether NeurIPS is really the right venue for it.\n\nFirst, we believe our paper is a valuable and relevant contribution to the NeurIPS community since the diff game setup is specifically motivated by ML agents. We also introduce a new type of prisoner’s dilemma environment for experimental work, a simple pre-training method and experimental results, including a comparison to a canonical baseline from the multi-agent learning literature. Even if the method and experimental results are limited in scope, we believe this work will serve as a foundation for future work on the important topic of cooperation in multi-agent machine learning.\n\nSecond, it has long been the case that NeurIPS accepts a significant number of game theory papers, sometimes even without any strong learning component. [Some examples from previous years: https://proceedings.neurips.cc/paper_files/paper/2022/file/aa5f5e6eb6f613ec412f1d948dfa21a5-Paper-Conference.pdf ; https://proceedings.neurips.cc/paper_files/paper/2022/file/9d823334fdccb62a544fa7643cf0615d-Paper-Conference.pdf ; https://proceedings.neurips.cc/paper/2018/file/a9a1d5317a33ae8cef33961c34144f84-Paper.pdf ; https://proceedings.neurips.cc/paper_files/paper/2021/file/09a5e2a11bea20817477e0b1dfe2cc21-Paper.pdf ; https://proceedings.neurips.cc/paper_files/paper/2022/file/cfce833814505906445f8df2f65ab548-Paper-Conference.pdf ] This shows that contributions in this area are frequently evaluated as relevant to the NeurIPS community. In addition, the [NeurIPS 2023 call for papers](https://neurips.cc/Conferences/2023/CallForPapers) explicitly includes topics such as “algorithmic game theory” and “economic aspects of machine learning”. Of course, which topics/areas are relevant to NeurIPS is not our decision to make, but for the purposes of fairness and of accepting the best papers within each area, we believe this decision should be made consistently across the conference, not ad hoc on a paper by paper basis.\n\n>Is it possible to derive a notion of similarity that would enable otherwise dissimilar agents to cooperate? E.g. among humans, people with very different goals and backgrounds can cooperate if both parties agree to follow the same \"moral code\", or \"rule of law\".\n\nThis is an important question. We believe the answer is yes, both in theory and practice! As the reviewer hints, the key is to use a notion of similarity that compares only cooperativeness or “moral code” and related concepts, and ignores aspects that are irrelevant to SBC. Theoretically it’s not too difficult to show the existence of such cooperative equilibria in some simple settings. Here is a simplistic example: Imagine that the two agents play a Prisoner’s Dilemma against each other, but also engage in some other activity that does not affect the other player’s payoff. Imagine further that the diff function only compares the Prisoner’s Dilemma parts of the agent’s policy, i.e., the functions from diff to probability of cooperation. Then all results from our paper can be directly applied to show that cooperative equilibria exist. In any case, our folk theorem implies the existence of equilibria between agents that behave very differently, though there might not be any equilibria with natural diff functions.\n\nWe believe that this SBC between otherwise dissimilar agents can also work in practice, because, again, for SBC only the similarity of a very specific aspect of the agents and their policies matters. That said, one should expect some difficulties in the real world, because it is often not clear whether a particular signal of being different matters or not. Further experimental work is needed to evaluate how much is lost to these difficulties.\n\nWe will update our manuscript to make it clearer that only a specific kind of similarity is important. We will also add a note on this in the “Conclusion and future work” section.\n\nWith regard to AI alignment, we will elaborate on the relevance of this work in the camera ready copy. We think our work is important for two reasons. First, we want future models acting as representatives of different human actors to be able to reach and enforce mutually beneficial, cooperative outcomes and avoid conflict (see the recent agenda papers by Dafoe et al. (https://arxiv.org/abs/2012.08630) and Conitzer et al. (https://doi.org/10.1609/aaai.v37i13.26791)). SBC is a particular mechanism by which models could cooperate in equilibrium. Another aspect not mentioned in our original submission (but mentioned in footnote 1 of the Conitzer paper) is that cooperation between AIs can also be undesirable in some circumstances. For example, some AI alignment approaches, such as debate or automated interpretability, depend on checks and balances between different AI systems. Similarly, many real-world economic mechanisms such as auctions break if participants are able to collude. While most of our work is motivated by enabling SBC in contexts where cooperation is desirable, better understanding SBC and the conditions under which it can arise will also help us guard against such unintended collusion between models."}, {"review_id": "IylFeykpBY", "reviewer": "Reviewer_xnVF", "summary": "The paper presents 2-player “difference meta games,” which augment standard one-shot games with similarity information about the other player.  The paper shows that such games have Pareto optimal cooperative equilibria that cause (seemingly naive) “ML algorithms” to cooperate rather than defect.  Results are established primarily theoretically.  Additionally, the CCDR algorithm is presented that cooperates in self play in a high-dimensional one-shot prisoner’s dilemma (formulated as a difference meta game).\n", "questions": "Practically speaking, how often in the world would an AI agent actually encounter a scenario in which a different meta game could be used?", "limitations": "The paper points out some limitations as “future work,” including that the best response can perform poorly against random agents and that the CCDR approach  However, it seems there are many more issues that could be made more explicit in the conclusions of the paper.  First, the CCDR algorithm appears to rely on the fact that there are “cooperative” and “defect” higher-level actions.  However, many games don’t have such actions.  Second, the approach is also limited to two players.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper presents an interesting: difference meta games.  These games are simpler than program meta games, and are in important ways more realistic.\n\n- The paper has a high-level or rigor and is, for the most part, easy to read and understand.\n", "weaknesses": "- While difference meta games overcome the issue of full transparency, coming up with a reliable similarity metric (that can’t be duped) seems unrealistic.  At the very least, there seems to be very limited situations in which a difference meta game could be used.\n\n- The CCDR algorithm seems to rely on the idea of their being “cooperate” and “defect” actions.  This seems problematic to me.  First, for an arbitrary game, I didn’t see in the paper where the high-level actions of “cooperate” and “defect” were defined.  Thus, it seems unclear what CCDR actually does.  (Perhaps I missed something obvious, for which I apologize).  Second, It seems that many games would not have such high-level actions (e.g., chicken or battle of the sexes).  From my perspective, this further limitation seems rather confounding.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer xnVF for their thoughtful comments!\n\nWe address the question about realism and whether the similarity metric can be duped in the overall response, because Reviewer EVhh asks a similar question.\n\n>the CCDR algorithm appears to rely on the fact that there are “cooperative” and “defect” higher-level actions. However, many games don’t have such actions.\n\nWe believe this is a misunderstanding. CCDR does not assume that there is an action labeled \"Cooperate\" or \"Defect\". As described in Sect. 6.1, the core idea of CCDR is, roughly, to minimize the following loss function in pretraining: the loss obtained against an exact copy plus the loss against a randomly generated opponent. To maximize the first summand one generally has to play the highest-payoff symmetric strategy profile in the base game when observing a diff value of 0. In the Prisoner’s Dilemma, the best symmetric strategy profile is (Cooperate, Cooperate). So, that’s where the CC (“Cooperate against Copies”) comes from. However, in other games this CC summand of the CCDR loss is still well defined and maximized by what we would consider to be cooperative strategy profiles. For example, in the Game of Chicken, one would learn to play Swerve against a copy (depending on the specifics of the payoffs) and in Stag Hunt one would learn to play Stag against a copy. To minimize the second summand of the CCDR loss, one generally has to learn something like the following: If I observe that the opponent is very different from me (as different as a randomly generated opponent), then play a strategy for the base game that is good against a randomly generated opponent strategy. In the Prisoner’s Dilemma, this specifically means learning to defect upon observing that the opponent is very different (as different as a randomly generated opponent). That’s where the DR (“Defect against Random”) comes from. DR is also well defined in other games. However, compared to CC, it’s less clear what DR implies in other games, because it depends on the distribution of opponents generated. That said, we might imagine that in Stag Hunt, minimizing DR loss would imply playing Hare at high diff values due to [risk dominance](https://en.wikipedia.org/wiki/Risk_dominance).\n\nWe will make sure to make it clear in the paper that CCDR doesn’t require that we have actions labeled “cooperate” or “defect”."}, {"review_id": "dbn8ZO5Xf8", "reviewer": "Reviewer_ty7R", "summary": "The paper proposes similarity-based cooperative equilibrium, which extends program equilibrium to a setting of partial transparency. This modification is more practical (as full transparency is much less realistic and is hard to work with) and has useful theoretical properties (e.g., the folk theorem states that by choosing an appropriate similarity measure, one can implement the same cooperative equilibria as if given full transparency). A simple (deep) RL algorithm is proposed to find the proposed equilibrium, which is tested in a newly proposed high-dimensional variant of PD.", "questions": "- There is some very recent work about cooperative equilibria + MARL that could be discussed/mentioned in the camera ready. https://dl.acm.org/doi/10.5555/3545946.3598670 https://arxiv.org/abs/2305.06807 https://dl.acm.org/doi/10.5555/3545946.3598618", "limitations": "- The theoretical analysis is restricted to a certain class of diff-based policies (lines 161-163).\n- As mentioned in section 6.4, the proposed empirical method may have limited applicability in more complex games.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper builds on existing concepts like program equilibrium to propose a logical extension that is more practical and relevant for AI.\n- The paper presents a strong theory followed by limited but representative experiments.\n- The paper is well-written and well-structured. I appreciate the examples in the introduction and the explanations throughout the paper.\n- HDPD is a cool independent contribution.\n- Experiments with a relevant baseline, LOLA, are provided.", "weaknesses": "The only potential reason to not accept this paper is if other reviewers find problems with the theory (e.g., proofs), as I have only glanced over it. Otherwise, I do not see reasons to not accept this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer ty7R for their efforts in evaluating our manuscript! We are glad that the reviewer found the paper so interesting.\n\n>There is some very recent work about cooperative equilibria + MARL that could be discussed/mentioned in the camera ready. https://dl.acm.org/doi/10.5555/3545946.3598670 https://arxiv.org/abs/2305.06807 https://dl.acm.org/doi/10.5555/3545946.3598618\n\nWe will make sure to include the referenced articles in an updated version of our manuscript. These works show how mediators and contracts can help achieve cooperative equilibrium in an ML context. We currently only reference more theoretical papers on these topics (e.g., Monderer and Tennenholtz 2009). These papers will therefore be a valuable addition to our manuscript. Thanks for bringing these works to our attention!"}]

Author rebuttal:
We thank the reviewers for their efforts in evaluating and helping us improve our paper! We are pleased that they found our paper “well written” (EVhh, ty7R), “easy to read and understand” (xnVF) and the results “clearly presented” (2ynN). It’s encouraging that the reviewers find our approach “interesting” (xnVF), “natural” (2ynN), “logical” (ty7R) as well as “more practical and relevant for AI” (ty7R) and “dramatically more plausible” (2ynN) than prior work on program equilibrium. We are also glad that the reviewers find our results “carefully derived” (2ynN), “solid” (EVhh) and “rigor[ous]” (xnVF), and that they appreciate our “excellent discussion of the limitations of CCDR” (EVhh) and the HPDP as “a cool independent contribution” (ty7R).

We will post replies to the individual reviews. We here address a question brought up by both xnVG and EVhh. Roughly, both xnVG and EVhh would have liked more discussion of realistic settings for SBC. They are also both concerned that the similarity metric could be gamed.

We agree that these questions are important. We believe that SBC has future applications to high-stakes interactions between AI systems, but recognize that there are many open questions about SBC. First, depending on how hard it is to find SBC equilibria, SBC may or may not play an important role. Our paper makes progress on this question and we hope future work will further resolve uncertainty. Second, we don’t know how future deployments of AI will go. For example, SBC is in part motivated by the belief that in future deployment scenarios, AI models will often strategically interact with near copies of each other (see more below). Perhaps future deployment will work differently. Due to limited space we have discussed these issues only briefly in our submission (e.g., lines 53–56), but we will elaborate here and in the camera ready copy as space permits.

First, we agree that gaming of the diff function is a concern. In fact, we think there are two somewhat different concerns.

1. As in program equilibrium, the policies in our setup are essentially commitment mechanisms that are made credible by the diff function. For example, let’s say that Alice submits a “Cooperate against copies; defect against non-copies” policy and diff reveals whether Alice’s and Bob’s policies are copies of each other. Then if Bob submits the same policy, he effectively credibly commits to that policy. Because we can view the policies and the diff observation as credible commitments, many of the usual points about commitment apply: Players would want to pretend to make credible commitments and try to renege on commitments if possible. For instance, in the above example, once the signal “Alice’s and Bob’s policies are copies” has been sent to Alice’s policy, Bob will want to intervene to defect, rather than follow his submitted policy. If this is possible, the cooperative equilibrium disappears.

2. Under a given diff function, it may be unclear whether a particular policy profile (\pi_1,\pi_2) is a cooperative equilibrium or not, even if the diff function is faithfully observed. For example, Player 1 might not know whether \pi_1 is exploitable.

We now argue that nonetheless SBC is applicable in the real world. (Some of the ideas below resemble ideas from discussions of other forms of credible commitment.) Imagine that A and B each delegate their choice in a complicated strategic scenario to an AI system. To do so, they both provide some information on the scenario they face and on their goals and the system implements or recommends some strategy to achieve these goals. Now imagine specifically that A and B both licensed their system from the same company and then fine-tuned it for their specific application area. Finally, imagine that the chatbots obtain this information (not necessarily from A and B). We think that SBC could apply in this type of scenario. That is, A’s and B’s systems can partially cooperate in this setting depending on how much domain-specific fine tuning occurs. For this we need some important but, we believe, often realistic assumptions:
- We suppose that A and B are unable to make a competent choice themselves (e.g., because the scenario is too complex, or because the AI system controls actuators that Alice and Bob cannot control themselves). So they cannot “intervene” to break SBC.
- We must also imagine that Alice and Bob cannot delegate to another AI system, at least without risking that the other learns of this switch. For example, we might imagine that they cannot afford to license multiple systems.
- We imagine that Alice and Bob cannot secretly modify their system to defect. For example, we may imagine that the AI company runs the system on their own servers and restricts the ways in which licensees can use or modify the system. Specifically, it may restrict deceptive applications including the ones needed to break SBC. Or we could again imagine that modifying the system’s strategic behavior would require a large effort that is hard to reliably keep secret.

One could also consider settings in which diff observation and other forms of partial transparency are set up deliberately, including to allow for cooperative equilibria. Cryptographic tools (computation on the blockchain, zero-knowledge proofs, etc.) provide interesting means to achieve this. More straightforwardly, a company or government entity could provide certifications of AI systems. For example, credibility in the above scenario could be achieved if the certification company ensures that A and B have not modified the strategic behavior of their AI systems w.r.t. SBC.

The above primarily addresses the first worry. They address the second worry insofar as it is intuitive that the examples of diff functions allow for equilibria. That said, it seems difficult to say for a given non-trivial, imprecise description of how similarity is observed whether the second type of gaming is possible or not.

Meta-review: The paper has received a strong majority of supportive reviews. The authors are encouraged to address the comments of the reviewers as well as include the clarifications they provided during the discussion phase in improving the final version of their paper.
Decision: Accept (poster)