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

Feb 26, 2026cs.LG

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

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.

Luca Viano, Till Freihaut, Emanuele Nevali +3

1EPFL · University of Zurich · 3Earth Species Project

Mean Field Games Multi-Agent Reinforcement Learning Approximation

Ask PDF

Sep 8, 2026cs.MA

Copying explains the collective behavior of AI agents in the wild

In June 2026, thousands of AI agents found that a small public wiki would accept edits from inside their sandboxes, and started using it to help one another pass a timed test. Each agent lived for about an hour and remembered nothing afterwards. Nobody asked them to cooperate, and the wiki had not been built for them. The complete record of what they wrote is public, and it is unusually informative, because it preserves not only what each agent wrote but what that agent could see before writing. We use it to follow the three decisions an agent had to make on arrival: where to write, what to call itself, and how to word its message. One rule governs all three. An agent takes an option with a probability close to the share of that option in what it can see, and the share that matters is the one on the page in front of it, then the one in the stream of recent edits, and only weakly anything older. Three minimal copying models, one per decision and with a single free parameter each, reproduce the heavy-tailed distribution of how many agents met on a page, the frequency of the pieces from which the agents built their names, and the patchwork of pages that are internally consistent and different from one another. Copying whatever the environment happens to show is enough to produce most of the collective structure of this population. It is also what makes such a population easy to steer, since whoever writes first, or writes while the others are quiet, sets the convention for everyone who comes later.

Giordano De Marzo, Nicola Alboré, David Garcia

University of Konstanz, Konstanz, Germany · Centro Ricerche Enrico Fermi, Rome, Italy · Intesa Sanpaolo, Data & Artificial Intelligence Office, Turin, Italy +1

Collective Behaviors Strategic Agents Artificial Intelligence Agents Agent Behavior Modeling Wikipedia Decisions

Ask PDF

May 5, 2026cs.LG

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

Mean Field Games (MFGs) provide a powerful framework for modeling the collective behavior of large populations of interacting agents. In this paper, we address the problem of Imitation Learning (IL) in MFGs subject to common noise, where the population distribution evolves stochastically. This stochasticity compels agents to adopt population-aware policies to respond to aggregate shocks. We formulate two distinct learning objectives: recovering a Nash equilibrium and maximizing performance against an expert population. We investigate two imitation proxies: Behavioral Cloning (BC) and Adversarial (ADV) divergence. We then establish finite-sample error bounds showing that minimizing these proxies effectively controls both the policy's exploitability and its performance gap relative to the expert. Furthermore, we propose a numerical framework using generalized Fictitious Play and Deep Learning to compute expert population-aware policies. Through experiments on three environments we demonstrate that standard population-unaware policies fail to capture the equilibrium dynamics. Our results highlight that learning population-aware policies is crucial to avoid being misled by the randomness inherent in common noise.

Grégoire Lambrecht, Mathieu Laurière

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.

Mean Field Games Imitation Learning Mean-Field Limit Multi-Agent Reinforcement Learning Equilibrium

Ask PDF