Unbeatable imitation of a friend

Masahiko Ueda

physics.soc-phJul 22, 2025

Unbeatable imitation of a friend

Authors: Masahiko Ueda

Organizations: Graduate School of Sciences and Technology for Innovation, Yamaguchi University, 1677-1, Yoshida, Yamaguchi, 753-8511, Japan.

Abstract

Imitation sometimes achieves success in multi-agent situations even though it is very simple. In repeated games, success of imitation has been characterized by unbeatability against other agents. Previous studies specified conditions under which imitation is unbeatable against co-players in repeated symmetric games, and clarified that the existence of unbeatable imitation is strongly related to the existence of payoff-controlling strategies, called zero-determinant strategies. However, these results were on the situations in which one repeated game is played by one group of players. It was pointed out that imitation of other players in the same group and imitation of other players in the same role in other groups generally result in different outcomes. Here, we investigate the existence condition of unbeatable imitation in the latter situations, described by two concurrent repeated games played by two different groups of players. We find that the existence condition of unbeatable imitation is stronger than the existence condition of unbeatable zero-determinant strategies, whereas both are very limited. Furthermore, we also find that adding exploration can make an imitation strategy unbeatable even in games where imitation without exploration can be beaten. Our findings suggest a strong relation between unbeatable imitation and payoff control even in the two concurrent repeated game situations.

Figures & tables

Figure 1: Schematic pictures of two situations of imitation. (a) “Imitation of opponents” (imitation of other players in the same group). (b) “Imitation of friends” (imitation of other players in the same role in other groups).

	$d_{1}$	$d_{2}$
$b_{1}$	$1$	$1$
$b_{2}$	$1$	$-1$
$b_{3}$	$-1$	$1$
$b_{4}$	$-1$	$-1$

Table 1: Payoff

s_{1}

in a weakly payoff-monotonic game for player

(\mu,1)

Figure 2: The time-averaged payoffs of the focal player $(1,1)$ and a friend $(2,1)$ for the weakly payoff-monotonic game in Table 1 . Players $(1,2)$ , $(2,1)$ , and $(2,2)$ take fixed actions $a_{(1,2)}=d_{2}$ , $a_{(2,1)}=b_{2}$ , and $a_{(2,2)}=d_{1}$ . Player $(1,1)$ adopts three strategies: a fair ZD strategy [ 22 ] , IIB ( 5 ), and $\epsilon$ -IIB ( 15 ) with $\epsilon=0.01$ . The initial conditions are (a) $a_{(1,1)}=b_{1}$ , (b) $a_{(1,1)}=b_{2}$ , (c) $a_{(1,1)}=b_{3}$ , and (d) $a_{(1,1)}=b_{4}$ . The time-averaged payoffs are calculated by one sample. In panels (a) and (c), all curves overlap.

	$d_{1}$	$d_{2}$
$b_{1}$	$1$	$1$
$b_{2}$	$0$	$0$
$b_{3}$	$-1$	$-1$

Table 2: Payoff

s_{1}

in a strongly payoff-monotonic game for player

(\mu,1)

Figure 3: The time-averaged payoffs of the focal player $(1,1)$ and a friend $(2,1)$ for the strongly payoff-monotonic game in Table 2 . Players $(1,2)$ , $(2,1)$ , and $(2,2)$ take random actions in each round. Player $(1,1)$ adopts two strategies: TFT ( 4 ) and IIB ( 5 ). The initial condition of the focal player is (a) $a_{(1,1)}=b_{1}$ , (b) $a_{(1,1)}=b_{2}$ , and (c) $a_{(1,1)}=b_{3}$ . The initial condition of the other players is $a_{(1,2)}=d_{1}$ , $a_{(2,1)}=b_{3}$ , and $a_{(2,2)}=d_{1}$ . The time-averaged payoffs are calculated by one sample.

	$d_{1}$	$d_{2}$
$b_{1}$	$1$	$1$
$b_{2}$	$1$	$-1$
$b_{3}$	$-1$	$1$

Table 3: Payoff

s_{1}

in a game with an autocratic action.

Figure 4: The time-averaged payoffs of the focal player $(1,1)$ and a friend $(2,1)$ for the game with an autocratic action in Table 3 . Players $(1,2)$ , $(2,1)$ , and $(2,2)$ take fixed actions $a_{(1,2)}=d_{2}$ , $a_{(2,1)}=b_{2}$ , and $a_{(2,2)}=d_{1}$ . Player $(1,1)$ adopts $\epsilon$ -IIB ( 15 ) with $\epsilon=0.01$ . The initial conditions are (a) $a_{(1,1)}=b_{1}$ , (b) $a_{(1,1)}=b_{2}$ , and (c) $a_{(1,1)}=b_{3}$ . The time-averaged payoffs are calculated by one sample. In panels (a) and (c), all curves overlap.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

	$d_{1}$	$d_{2}$	$d_{3}$
$b_{1}$	$1$	$1$	$1$
$b_{2}$	$1$	$1$	$0$
$b_{3}$	$1$	$1$	$-1$
$b_{4}$	$1$	$0$	$1$
$b_{5}$	$1$	$0$	$0$
$b_{6}$	$1$	$0$	$-1$

Appendix

Table 4: Payoff

s_{1}

in a bandit-like weakly payoff-monotonic game.

Figure 5: The time-averaged payoffs of the focal player $(1,1)$ and a friend $(2,1)$ for the bandit-like weakly payoff-monotonic in Table 4 . Players $(1,2)$ and $(2,2)$ take random actions in each round. Player $(2,1)$ adopts the reinforcement learning in Algorithm 1 with $\eta=0.01$ and $\alpha=0.1$ . Player $(1,1)$ adopts three imitation strategies: TFT ( 4 ), IIB ( 5 ), and $\epsilon$ -IIB ( 15 ) with $\epsilon=0.01$ . The initial condition is $a_{(1,1)}=b_{27}$ , $a_{(1,2)}=d_{1}$ , $a_{(2,1)}=b_{27}$ , and $a_{(2,2)}=d_{1}$ . The time-averaged payoffs are calculated by one sample. The payoff of IIB almost overlaps with that of $\epsilon$ -IIB.

Figure 6: The time-averaged payoffs of the focal player $(1,1)$ and a friend $(2,1)$ for the bandit-like weakly payoff-monotonic in Table 4 . Player $(1,2)$ is a myopic adversarial opponent taking the action ( 38 ) and player $(2,2)$ takes a random action in each round. Player $(2,1)$ adopts the reinforcement learning in Algorithm 1 with $\eta=0.01$ and $\alpha=0.1$ . Player $(1,1)$ adopts three imitation strategies: TFT ( 4 ), IIB ( 5 ), and $\epsilon$ -IIB ( 15 ) with $\epsilon=0.01$ . The initial condition is $a_{(1,1)}=b_{27}$ , $a_{(1,2)}=d_{1}$ , $a_{(2,1)}=b_{27}$ , and $a_{(2,2)}=d_{1}$ . The time-averaged payoffs are calculated by one sample. The payoff of IIB almost overlaps with that of $\epsilon$ -IIB.

Explore similar work

Multi-agent imitation learning with function approximation: Linear Markov games and beyond
Feb 26, 2026Luca Viano, Till Freihaut, Emanuele Nevali +3Mean Field Games Multi-Agent Reinforcement Learning
1EPFL · University of Zurich · 3Earth Species Project
Copying explains the collective behavior of AI agents in the wild
Sep 8, 2026Giordano De Marzo, Nicola Alboré, David GarciaCollective Behaviors Strategic Agents
University of Konstanz, Konstanz, Germany · Centro Ricerche Enrico Fermi, Rome, Italy · Intesa Sanpaolo, Data & Artificial Intelligence Office, Turin, Italy +1
Population-Aware Imitation Learning in Mean-field Games with Common Noise
May 5, 2026Grégoire Lambrecht, Mathieu LaurièreMean Field Games Imitation Learning
Center for Data Science, New York University and NYU Shanghai, New York, United States of America · Shanghai Center for Data Science; NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai; NYU Shanghai, Shanghai, People’s Republic of China.

Feb 26, 2026, cs.LGJ/K move · Enter open · S save

Multi-agent imitation learning with function approximation: Linear Markov games and beyond

Luca Viano, Till Freihaut, Emanuele Nevali, Volkan Cevher+2

1EPFL · University of Zurich · 3Earth Species Project

Mean Field Games Multi-Agent Reinforcement Learning Approximation

Open paper AskPDF arXiv

In this work, we present the first theoretical analysis of multi-agent imitation learning (MAIL) in linear Markov games where both the transition dynamics and each agent's reward function are linear in some given features. We demonstrate that by leveraging this structure, it is possible to replace the state-action level "all policy deviation concentrability coefficient" (Freihaut et al., arXiv:2510.09325) with a concentrability coefficient defined at the feature level which can be much smaller than the state-action analog when the features are informative about states' similarity. Furthermore, to circumvent the need for any concentrability coefficient, we turn to the interactive setting. We provide the first, computationally efficient, interactive MAIL algorithm for linear Markov games and show that its sample complexity depends only on the dimension of the feature map

d

. Building on these theoretical findings, we propose a deep MAIL interactive algorithm which clearly outperforms BC on games such as Tic-Tac-Toe and Connect4.

Abstract

Explore similar work

Multi-agent imitation learning with function approximation: Linear Markov games and beyond

Copying explains the collective behavior of AI agents in the wild

Population-Aware Imitation Learning in Mean-field Games with Common Noise