We compare level-k utility maximization and level-k regret minimization in evolutionary competition based on averages of one-shot plays over many randomly generated strategic games. Under the assumption that Theory-of-Mind-reasoning of depth k incurs a cost monotonically increasing with k, our results show that mixed states with low levels of reasoning depth k can be evolutionary stable with substantial basins of attraction under the replicator dynamics and that regret minimization can outperform utility maximization.
de Weerd, Verbrugge, and Verheij (2013) address a part of this question by looking at agent-based simulations of utility maximizers with di erent ToM reasoning capabilities when playing repeatedly selected zero-sum games against each other. The simulations of de Weerd, Verbrugge, and Verheij suggest that there is a bene t to deeper ToM reasoning only up to a fairly limited depth of reasoning.
Extending and generalizing this line of investigation, we use numerical
simulations to approximate the expected payo of agents with a xed choice
principle who play many arbitrary 2-player one-shot strategic games, not just a small
hand-picked selection. This way we try to assess the general evolutionary
benet of a choice principle across an unbiased sample of games, not just for those
games that are of particular technical, philosophical or historical importance.
Additionally, we compare not only di erent ToM reasoning capability of utility
maximizers, but also variation in the underlying method of choice. Concretely,
we look at level-k utility maximization and level-k iterated regret minimization
(IRM)
The choice principles we compare are de ned as follows. Look at level-k
utility maximizers rst. L-0 utility maximizers have an arbitrary probabilistic
belief about the opponent's behavior and are indi erent between any act that
maximizes expected utility under this belief. L-k + 1 utility maximizers have
an arbitrary probabilistic belief with support only on acts that an L-k
opponent might choose, and are indi erent between any act that maximizes expected
utility under this belief. Notice that this construction is di erent from that of
de Weerd, Verbrugge, and Verheij (2013) in several respects. Firstly, we look
at level-k reasoning models
Let's turn next to the de nition of level-k regret minimizers. Formally, if
U is a matrix of utilities for the row player, regret minimization is equivalent
to playing MaxiMin on the derived matrix U 0, where Ui0j = Uij maxkUkj is
the negative regret of choosing act i when the opponent chooses j. L-0 regret
minimizers are indi erent between any act that minimizes regret in this sense.
An L-k + 1 regret minimizer chooses like an L-0 regret minimizer in the reduced
game in which only acts remain that row and column players would choose that
are L-k regret minimizers
We randomly generate arbitrary strategic games and record the payo earned by each choice principle when playing against any other, including itself. In general, the details of generating arbitrary games are important to this approach. Some choice principles might be better in certain classes of games, but not others. For that reason, we used several algorithms for creating games that are as unbiased and neutral as possible. We choose neutrality in the selection of games, because we have at present no better answer to the main empirical question that is relevant here, namely which kinds of interactive decision-making situations were most frequent during the critical stages of cognitive development. For illustration, this abstract focuses on the results of a simple generic algorithm for constructing arbitrary asymmetric strategic games with 2 players. The procedure starts by rst picking a random number between 2 and 10 as the number of acts for each player, say n and m. Then, we determine each entry in the n m and m n utility matrices of each player as an integer between 0 and 10, all independently and uniformly at random.
Table 1 gives the accumulated payo averaged over 10.000 games sampled in this way, for 0 k 4. The table lists the average payo for the row principle when playing against the column principle and can be regarded as a symmetric \meta-game" that captures the evolutionary competition between choice principles. The only evolutionarily stable strategy (ESS) of this meta-game is EU-L4, but it is clear (from more extensive simulations) that this is just because we chose an arbitrary cuto for depth of reasoning. Generally, it appears that pure populations of EU-Lk players can always be invaded by EU-Lk + 1 players. But, interestingly, some pure populations of EU-Lk players can also be invaded by EU-Ll players, with l < k (see Table 1). On the other hand, if k 2, then RM-Lk is a neutrally stable strategy (NSS): regret minimizers of a di erent level l 2 would not be driven to extinction, but would also not take over the population (because they are behaviorally equivalent in all games from our random sample).
The results from this example generalize to other game-sampling routines, as long as they are general and encompassing enough. While there is usually no k at which EU-Lk is an ESS, there is a small k (almost always k 3) for which IRM has reached its xed point in all sampled games and RM-Lk0 is an NSS for all k0 k. This is a noteworthy result: on randomly sampled games, it is always bene cial for utility maximizers to outsmart the opponent by ideally one level of ToM reasoning, but too much ToM outsmarting is harmful. For IRM, levels of ToM reasoning higher than a few steps are evolutionarily pointless.
More ne-grained results obtain when we look at the predictions of the replicator dynamics on the simulated \meta-games" together with the natural hypothesis that ToM reasoning incurs a cost c(k) 2 R, which is monotonically increasing with k. For concreteness, we look at a parameterized cost function c(k ; s; a) = Pk
i=0 ai s where s is the initial step of growth, and a is a parameter that controls for superlinear and sublinear growth. For at least linear growth (a 1), there is a threshold :391 such that if s > , the only attractor is EU-L0. With s smaller or not too much bigger than and sublinear growth (e.g., a = 0:25), RM-L1 is a strong attractor, as well as mixed states of low level EUmaximizers. For step s < and a 1 results are more varied. If :313 < s < , the only attracting state is a mix of EU-L0 and EU-L1. If :011 < s < :313, RM-L1 is a strict symmetric Nash equilibrium and therefore an attractor, but also, depending on s, mixed states of low-level EU-maximizers are attracting. If 0 < s :011 RM-L2 is an attractor, together with mixed states of low level EU-maximizers.
In sum, our simulation data show that shallow depth of reasoning is
plausibly evolutionarily dominant in long run competition with \deep ToM" strategies.
Regret minimization often outperforms utility maximization in this
evolutionary competition, especially when reasoning costs are added. Although already
insightful, our results are only partial, because many interesting questions have
not yet been addressed. We mention just three obvious extensions for future
work. Firstly, sequential games might yield di erent results, because they would
induce more ties in strategic form, and hence more reasons to apply deeper
ToM reasoning. Secondly, the payo of utility maximization heavily depends
on the type of belief about the opponent's choice. Here we used arbitrary
beliefs compatible with the opponent's assumed type, but certain restrictions on
belief formation, e.g., using maximum-entropy beliefs, might give utility
maximizers a better payo on average. Finally, it would be interesting to extend our
comparison to more choice principles, e.g., ones including learning from repeated
interactions with the same players