Similarity-based cooperative equilibrium

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.

Paper

References (63)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer ty7R8/10 · confidence 4/52023-06-11

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.

Strengths

- The paper builds on existing concepts like program equilibrium to propose a logical extension that is more practical and relevant for AI. - The paper presents a strong theory followed by limited but representative experiments. - The paper is well-written and well-structured. I appreciate the examples in the introduction and the explanations throughout the paper. - HDPD is a cool independent contribution. - 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.

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

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

- The theoretical analysis is restricted to a certain class of diff-based policies (lines 161-163). - As mentioned in section 6.4, the proposed empirical method may have limited applicability in more complex games.

Reviewer xnVF4/10 · confidence 3/52023-07-03

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).

Strengths

- The paper presents an interesting: difference meta games. These games are simpler than program meta games, and are in important ways more realistic. - The paper has a high-level or rigor and is, for the most part, easy to read and understand.

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. - 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.

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?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

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.

Reviewer EVhh6/10 · confidence 4/52023-07-05

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. This 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. The 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.

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. The 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.

Weaknesses

My 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.

Questions

From 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. Is 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. 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".

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Although 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. However, 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.

Reviewer 2ynN6/10 · confidence 3/52023-07-06

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). When 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.

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. This paper takes a step beyond proving the existence of equilibria, and demonstrates that plausible training procedures can actually find them. The 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. The procedure described still tends not to find fully cooperative equilibria, which seems like a shortcoming. #### Minor issues (did not affect rating) - 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? - p.2: "In particular, full transparency can make the problem of equilibrium selection harder": Isn't this also true of partial transparency?

Questions

Have you evaluated your approach on non-additively-decomposable games?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

n/a

Reviewer xnVF2023-08-12

Thanks for the clarifications and arguments. I remain dubious about the generality and practicality of the approach.

Reviewer EVhh2023-08-14

The devil is in the details...

Thank you for the response. When defining a diff function, I tend to think that "the devil is in the details." Certainly in human interactions, agents who profess to follow a moral code, but then violate that code when they think they can get away with it, is a very common occurrence. :-) However, basic theoretical work which shows that equilibria exist in simple settings is a first step towards solving that problem. Future work might also focus on how robust those equilibria are. For example, if the diff function is not entirely reliable, i.e. reflecting a judgment that "the other agent looks honest, but I can't be sure", do the equilibria still exist? How much noise or uncertainty can they tolerate before things fall apart?

Authorsrebuttal2023-08-21

(Optional) further thoughts on more realistic theoretical models and experiments

Thanks for this response! We agree with the reviewer’s comments. In particular, we agree that this is an important question and that future work should tackle it. We give some further thoughts on settings in which to investigate these things below. The reviewer and AC shouldn’t feel obligated to read these thoughts. It seems that an important question is whether _realistic_ ways of perceiving similarity are sufficient for establishing cooperative equilibrium. Both our theoretical results and our empirical results are about artificial ways of perceiving similarity. That being said, the reviewer's comment inspired us to consider the following slight extension of our model: Consider the Prisoner’s Dilemma, parameterized by G, as per Table 1 of our paper. Imagine that each player is only allowed to submit a threshold agent $(C,\theta_i,D)$. Now imagine that each player $i$’s diff function works as follows: With probability $p_i$: $\mathrm{diff}_i(\theta_1,\theta_2)=|\theta_1-\theta_2|+N$ with $N\sim \mathrm{Unif}([0,\epsilon])$ for some $\epsilon>0$. But with probability $1-p_i$: $\mathrm{diff}_i(\theta_1,\theta_2)=0$. (For $p_1,p_2=1$ this is exactly the setting in Example 1 and Proposition 1 of the paper.) Intuitively, this is supposed to model the case where each player can try to “manipulate” the diff value to be 0 and the manipulation succeeds with probability $1-p_i$. It is furthermore assumed (somewhat unrealistically) that if manipulation fails, the other player never learns of the attempt to manipulate. Instead, the diff value is observed normally if manipulation fails. That way we can assume that each player always attempts to manipulate. Then the following generalization of Proposition 1 holds: In the aforedescribed game, $((C,\theta_1,D),(C,\theta_2,D))$ is an equilibrium if and only if * $\theta_1,\theta_2 \leq 0$, or * $0\leq \theta_1=\theta_2 \leq \epsilon$ and $Gp_i\geq 2$ for $i=1,2$. The proof works just the same as the proof of the original Proposition 1. Intuitively, the idea (for the second part) is that if Player $i$ decreases $\theta_i$, their own probability of cooperation decreases by $2\delta/\epsilon$. Meanwhile, the opponent’s probability of cooperation decreases by $p_{-i} \delta/\epsilon$. Thus, the overall increase in Player $i$’s utility is $ 2\delta/\epsilon - G p_{-i} \delta/\epsilon$. For this to be nonnegative, we need to have $G*p_i\geq 2$. In terms of more realism, here is an ambitious setting that it would be exciting to study in future work. Say we have two complex base models. For concreteness, let’s say these are two potentially very different LLMs. Now, we get to train the LLMs to do SBC with each other. Call the resulting models the SBC base models. Now two players (principals) Alice and Bob play a game in which each chooses a fine-tuning scheme for one of the SBC base models. The LLMs then play a game against each other on the principals’ behalf. Let’s imagine that this game is a social dilemma. But let’s also imagine that this game has some player-specific aspects. In particular, imagine that Alice and Bob need to do some fine-tuning to achieve high utility and that this necessary fine-tuning is different between the two players. Finally, as our diff, we imagine that the two models make some observation about how they were fine-tuned. For example, we might imagine that they directly observe each other’s fine-tuning data sets. (At least for practical purposes this is still very far from full transparency.) But we might also imagine that they observe some abstract description of these data sets, such as a description of what kind of data they contain. For example, we might imagine descriptions such as, “The opponent model was trained on analyses of 18th century landscape paintings; it wasn’t trained on any strategic data” or “Alice’s and Bob’s fine-tuning data seems to have a very similar effect on strategic behavior”. We might use another language model to write a description of how the fine-tuning data sets relate. Now the challenge would be: Can we train the SBC base models in such a way that the game between Alice and Bob has cooperative (approximate) equilibria? We conjecture that the answer is yes. However, depending on various details of the setting, this is not at all obvious. For example, it may be possible for Alice or Bob to deploy “deceptive training data”, i.e., training data that looks innocuous but somehow still affects the strategic behavior. While this setting is still artificial (like most work on safety in social dilemmas between autonomous agents), we think it could elucidate the kind of worries shared by EVhh and the authors in a way that our numeric diff model cannot. Unfortunately, it is also vastly more complicated than training models with ~10k parameters and a handful of inputs and outputs. Nonetheless, we prospectively would like to investigate this kind of setting.

Reviewer 2ynN2023-08-14

Thanks for the clarifications!

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC