A Note on Type-Symmetries in Finite Games

Abstract

In two-action generalized polymatrix games, Nash equilibria are support-type-symmetric, i.e., determined by supports for each type of player. We show that such a property does not generalize straightforwardly for games with at least three actions or where interaction weights have different signs (neither all positive nor negative). A non-trivial condition on interaction weights must be satisfied, which may go unnoticed as it is trivially satisfied for: (i) two-action games, (ii) conformity games, and (iii) congestion games. We derive this condition and the corresponding simplified analytic equation for mixed strategies.

1. Introduction

In finite games, understanding the structure and complexity of the set of equilibria is a longstanding problem, both from a practical and theoretical standpoint. Identifying invariances in the game structure, for example, by looking at permutations of players that induce the same payoff structure, allows distinguishing between diversity and multiplicity of equilibria. Say we consider a partition of players into same-type blocks of indistinguishable players. Given an equilibrium, any other strategy based on a permutation of players within same-type blocks is also an equilibrium. As the complexity of equilibria may depend on the number of same-type blocks, it becomes relevant to study the relationship between the type space and the equilibrium set. The importance of this notion of symmetry in games, known since the foundational work of von Neumann, Morgenstern, Nash, or Gale, continues to be explored to study how symmetries translate from game structure to equilibria ([1,2,3,4,5,6,7,8]).

We can take the question further: does the existence and size of same-type blocks in a given game induce any other structural property on its equilibrium set? In particular, when can same-type players play different strategies in equilibrium? How different can these strategies be?

For general two-action games of pairwise interaction, the authors of [9] show that same-type blocks of players can split into at most three groups in equilibrium: two in pure strategies and one in the same nondegenerate mixed strategy. Equilibria are support-type symmetric: for each type, supports determine strategies; hence, same-type blocks can play at most three because that is the number of possible supports. Each allocation of players to pure and mixed strategies determines the associated equilibrium and considering all possibilities characterizes the equilibrium set.

Our goal is to extend the result from two-action to n-action games, for $n\in \mathbb{N}$. We consider a generalized version of the class of polymatrix games with a presence-based assumption on interactions. Polymatrix games are a natural extension from standard bimatrix games which have drawn considerable attention, particularly in applications, for being succinctly representable, amenable to computational and algorithmic approaches, and the natural ground for studying games of network interactions ([10,11,12,13,14,15,16,17,18]). These are finite games where the utility stems from pairwise or dyadic interactions. The sum of weights in some given interaction matrix (possibly weighted, directed, and state-dependent) determines payoffs. Hence, utility functions are multilinear in the strategy profile. The generalized version allows for affine transformations of the utility function, which can accommodate, for example, endowments, costs, or preferences, as seen in many applications.

Presence-based is a common and convenient assumption, with a long history under different names, and most commonly known as Independence of Irrelevant Alternatives (IIA), dating back to Arrow’s work. For example, in the context of social choice theory, it means, broadly speaking, that given two alternatives, a and b, changes in other options will not change how players rank a relative to b. However, early in the field, [19] noted the problematic nature of using the same name in different contexts. Here the assumption is made on interactions and not on a preference relation. In presence-based games, it only matters if players choose the same action or a different one (i.e., are present or not). The assumption only impacts games with at least three possible actions, where it could matter what action is the different one. It is a commonly used assumption, but here we choose a new name to avoid misinterpretations.

In this class of games, the expected utility from a mixed strategy becomes additively separable, and the pure strategy payoff dependence on other players is linear. Furthermore, the impact players of the same type have on one another sets a limit for the difference in their expected payoffs in equilibrium. When we associate this with the fact that payoffs must be the same for every action in a mixed strategy, we find a limitation to asymmetries in equilibria involving same-type players. We call Nash equilibria support-type-symmetric if all players of the same type using the same support choose the same strategy. Knowing who plays what support determines support-type symmetric equilibria. We derive a condition for support-type symmetry: a restriction on interaction weights relative to the supports used. The condition comes from guaranteeing a non-zero determinant for a linear system in terms of the mixed strategies of same-type players using the same support. We observe that this condition is trivially satisfied for two-action games and games with interaction matrices where all entries have the same sign (all positive or all negative). The latter may cause it to go unnoticed and erroneously assumed as a general property of the class of games studied here, polymatrix or even of finite games in general.

In the next section, we formally setup the class of games treated. Section 3 contains the main results. We then provide consequences and corollaries and illustrate the results with examples before concluding.

2. Setup

Consider standard n-person games with a set $\mathcal{I}\equiv \{1,\dots ,n_{\mathcal{I}}\}$ of players, or individuals (we will refer to players and individuals interchangeably). Each player has to choose, independently and simultaneously, an element from its finite action set ${\mathcal{A}}_i$. Let us denote a pure strategy profile by $\mathbf{s}=(s_1,\dots ,s_{n_{\mathcal{I}}})\in {\mathcal{A}}_1\times \cdots \times {\mathcal{A}}_{n_{\mathcal{I}}}\equiv \mathcal{S}$. A generalized polymatrix game is defined by an utility function $u:\mathcal{I}\times \mathcal{S}\to \mathbb{R}$, which determines the payoff of a pure strategy profile $\mathbf{s}$ for player $i\in \mathcal{I}$, denoted $u(i;\mathbf{s})$, and given by

$$u(i;\mathbf{s})={\omega }_{s_i}^i+\sum _{j\in \mathcal{I}\backslash \left\{i\right\}}{\alpha }^{ij}(s_i,s_j),$$

where ${\alpha }^{ij}(s_i,s_j)\in \mathbb{R}$ represents how j impacts the payoff of i in strategy profile $\mathbf{s}$, and ${\omega }_a^i\in \mathbb{R}$ represents a personal payoff/cost for player i of choosing a. We can also call generalized polymatrix games the general class of finite games of pairwise interaction.

In the case that for all $i\in \mathcal{I}$, ${\omega }_a^i=0$, for all $a\in {\mathcal{A}}_i$, the above reduces to the class of polymatrix games. We consider the possibility of ${\omega }_a^i\ne 0$, not only to obtain a more general result, but also because most applications include such a component. For example, it could represent prices if each action is a product or service; a toll to control resource use (if actions are resources) or traffic (web or otherwise) if actions are routes; or it could also represent the players’ valuation of alternatives if it stems from the distribution of preferences. Note also that we may consider a common action set for all players, $\mathcal{A}=\bigcup {\mathcal{A}}_i$, and let ${\omega }_a^i=-\infty$ whenever $a\notin {\mathcal{A}}_i$. It produces the same set of Nash equilibria as when players have different action sets. Thus, for notation simplicity, and without loss of generality, we will assume all players have the same action set $\mathcal{A}\equiv \{1,\dots ,n_{\mathcal{A}}\}$, which leads to the pure strategy set $\mathcal{S}\equiv {\mathcal{A}}^{n_{\mathcal{I}}}$.

A mixed strategy for player i is represented by a vector ${\overrightarrow{\sigma }}_i=({\sigma }_1^i,\dots ,{\sigma }_{n_{\mathcal{A}}}^i)$ in the simplex ${\Delta }^{n_{\mathcal{A}}}$, where ${\overrightarrow{\sigma }}_i\left(a\right)\equiv {\sigma }_a^i$ is the probability that ${\overrightarrow{\sigma }}_i$ assigns to $a\in \mathcal{A}$ and naturally ${\sum }_{a\in \mathcal{A}}{\sigma }_a^i=1$. The support of a mixed strategy, $supp\left({\overrightarrow{\sigma }}_i\right)$, is the subset of pure strategies to which ${\overrightarrow{\sigma }}_i$ assigns positive probability. A mixed-strategy profile of the game is an element of $\Delta \equiv {\left({\Delta }^{n_{\mathcal{A}}}\right)}^{n_{\mathcal{I}}}$ with its coordinates being the mixed strategies of every individual $i\in \mathcal{I}$, denoted $\sigma =({\overrightarrow{\sigma }}_1,\dots ,{\overrightarrow{\sigma }}_{n_{\mathcal{I}}})$.

2.1. Presence Based Games

We will study the class of generalized presence-based polymatrix games. In presence-based games, an action’s payoff depends only on what is relative to that action, namely, the players who also choose that action (hence the word presence). Many applications, if not most, have this assumption, for example, congestion or conformity games (congestion depends on the use of some resource but not (directly) on the use of other resources).

Presence-based  (PB).

A generalized polymatrix game is presence-based if for all $i,j\in \mathcal{I}$ and $a\in \mathcal{A}$, we have ${\alpha }^{ij}(a,b)=0$ for all $b\in \mathcal{A}\backslash \left\{a\right\}$.

The assumption is a common and convenient one, with a long history, in the spirit of what is most commonly known as Independence of Irrelevant Alternatives, dating back to Arrow’s work. For example, in the context of social choice theory, it means, broadly speaking, that given two alternatives, a and b, changes in other alternatives will not change how players rank a relative to b. However, since early in the field, it was noted the problematic nature of using this same name for similar ideas in different contexts, as they may refer to different assumptions (see, for example, [19] for an early discussion). To avoid a misinterpretation, we choose a different name and call this a presence-based influence. Here the assumption is made on interactions and not on a preference relation directly (players influence each other dichotomically, i.e., whether they make the same or a different decision), similar to Independence of Irrelevant Choices as in [20] or No Spillovers as in [21]. Observe that, instead of 0, we could have chosen any constant in the definition. In particular, that means the equilibrium set of a two-action game is isomorphic to that of a two-action PB game, as satisfying the assumption requires only a shift-variable transformation (see for example [9] or [10]).

For PB generalized polymatrix games, the utility function can be rewritten in reduced notation using ${\alpha }_a^{ij}\equiv {\alpha }^{ij}(a,a)$. Given a strategy profile $\mathbf{s}$, let us denote the set of individuals who choose $a\in \mathcal{A}$ by $s^{-1}\left(a\right)\subset \mathcal{I}$. Then, we have,

$$u(i;\mathbf{s})={\omega }_{s_i}^i+\sum _{j\in s^{-1}\left(s_i\right)\backslash \left\{i\right\}}{\alpha }_{s_i}^{ij}.$$

The expected utility function determining the payoff to individual i of the mixed-strategy profile $\mathbf{\sigma }$, is (with the standard slight abuse of notation) $u(i;\mathbf{\sigma })\equiv \sum {\prod }_{j=1}^{n_{\mathcal{I}}}{\sigma }_{s_j}^{j}u(i;\mathbf{s})$, which leads to

$$u(i;\mathbf{\sigma })=\sum _{a\in \mathcal{A}}{\sigma }_a^i\left({\omega }_a^i+\sum _{j\ne i}{\alpha }_a^{ij}{\sigma }_a^j\right).$$

(To understand how to get the above expression, observe that the payoff impact when i and j interact is the same whatever the strategies of other individuals. By linearity of the expected value, one can keep the strategies of i and j fixed and separate the product of other players’ strategies, one by one, into a sum of all the possibilities for the remaining players, which equates to 1 since they are a probability distribution. See for example [22].)

2.2. Types

It is useful to partition the set of players into subsets of indistinguishable players. We will do this through a type map, in some general type space T, which induces a natural equivalence relation in the strategy space, in terms of the equilibrium set. (The type map is known a priori and reveals symmetries of the utility profile. Given any equilibrium, a permutation of strategies for players of the same type is also an equilibrium.) Let ${\overrightarrow{\omega }}_i\equiv ({\omega }_1^i,\dots ,{\omega }_{n_{\mathcal{A}}}^i)\in {\mathbb{R}}^{n_{\mathcal{A}}}$ be the vector of action coordinates. Types are defined as follows: if two individuals $j_1,j_2\in \mathcal{I}$ have the same type $t_{j_1}=t_{j_2}=t\in T$, then,

(1)

${\overrightarrow{\omega }}_{j_1}={\overrightarrow{\omega }}_{j_2}$;

(2)

For all $i\in \mathcal{I}$ and $a\in \mathcal{A}$ we have ${\alpha }_a^{i{j}_1}={\alpha }_a^{i{j}_2}\equiv {\alpha }_a^{it}$, and ${\alpha }_a^{j_{1}i}={\alpha }_a^{j_{2}i}\equiv {\alpha }_a^{ti}$.

We denote the set of individuals of type t by ${\mathcal{I}}_t$ and the profile ${\overrightarrow{\omega }}_t$ through coordinates ${\omega }_a^t$. With this, we can characterize a game by a reduced representation through $\mathbf{\omega }\equiv ({\overrightarrow{\omega }}_1,\dots ,{\overrightarrow{\omega }}_{n_T})$ and a set of matrices $\mathcal{N}\equiv \{N_1,\dots ,N_{n_{\mathcal{A}}}\}$ where for each $a\in \mathcal{A}$, $N_a$ is a $n_T\times n_T$ matrix with entries ${\alpha }_a^{tt}$.

2.3. Class of Games Analyzed

In this work, whenever we say games, we will mean PB generalized polymatrix games, and we refer to different games by two distinguishing features: $\left(i\right)$ the number of types $n_T$; and $\left(ii\right)$ the number of decisions $n_{\mathcal{A}}$. We denote the corresponding class of games by ${\Gamma }_{n_T,n_{\mathcal{A}}}$ and a particular game in such a class by ${\Gamma }_{n_T,n_{\mathcal{A}}}(\mathbf{\omega };\mathcal{N})$. Changing $n_T$ or $n_{\mathcal{A}}$ has different impacts and produces different challenges. Our focus is on the impact of the interaction structure $\mathcal{N}$. In particular, how properties that are known for $n_{\mathcal{A}}=2$ hold when $n_{\mathcal{A}}$ (the number of decisions) increases.

Note that ${\Gamma }_{n_T,n_{\mathcal{A}}}$ includes games based on networks given a priori. Namely, networks that may be directed (if ${\alpha }^{rt}\ne {\alpha }^{tr}$), weighted (if ${\alpha }^{rt}$ are not only 0 or 1), and state-dependent (because ${\alpha }_a^{rt}$ can depend on a). We can, of course, consider that $n_T=n_{\mathcal{I}}$, that is, each player has different connections (or a different utility function).

3. Main Result: Support Type-Symmetries in Nash Equilibria

Let ${\sigma }_{-\{i,j\}}$ denote the strategies of all other players except i and j. Consider the value of a given pure strategy a for an individual i of type t, not taking into account another given player j,

$$V_a^t\left({\mathbf{\sigma }}_{-\{i,j\}}\right)\equiv {\omega }_a^t+\sum _{j^{\prime }\ne i,j}{\alpha }_a^{t{j}^{\prime }}{\sigma }_a^{j^{\prime }}.$$

Let $\mathbf{\sigma }\in \Delta$ be a mixed-strategy Nash equilibrium and $i,j\in {\mathcal{I}}_t$ two players of the same type t. Observe that the payoff for i is $u(i;\mathbf{\sigma })=V_a^t\left({\mathbf{\sigma }}_{-\{i,j\}}\right)+{\alpha }_a^{tt}{\sigma }_a^j$ for all $a\in supp\left({\overrightarrow{\sigma }}_i\right)$, thus for any action $a\in supp\left({\overrightarrow{\sigma }}_i\right)\cap supp\left({\overrightarrow{\sigma }}_j\right)$,

$$u(i;\mathbf{\sigma })-u(j;\mathbf{\sigma })={\alpha }_a^{tt}\left({\sigma }_a^j-{\sigma }_a^i\right).$$

That is, the impact that players of the same type have on each other creates a bound for the difference in equilibrium payoffs for strategies with intersecting supports. Consider now, for each type t, the following partition of the action set according to the influence that individuals of type t have on each other,

$${\mathcal{A}}_t^{-}\equiv \{a\in \mathcal{A}:{\alpha }_a^{tt}<0\};{\mathcal{A}}_t^0\equiv \{a\in \mathcal{A}:{\alpha }_a^{tt}=0\};{\mathcal{A}}_t^{+}\equiv \{a\in \mathcal{A}:{\alpha }_a^{tt}>0\}.$$

The set ${\mathcal{A}}_t^{-}$ is the subset of actions that individuals of type t do not like to do together. The subsets ${\mathcal{A}}_t^0$ and ${\mathcal{A}}_t^{+}$ are, respectively, those actions that individuals of type t are indifferent or like to do together. Now partition the support of a mixed strategy ${\overrightarrow{\sigma }}_i$ of individual $i\in {\mathcal{I}}_t$ according to these subsets. Define $supp{\left({\overrightarrow{\sigma }}_i\right)}^{-}\equiv supp\left({\overrightarrow{\sigma }}_i\right)\cap {\mathcal{A}}_t^{-}$, and analogously, define $supp{\left({\overrightarrow{\sigma }}_i\right)}^0$ and $supp{\left({\overrightarrow{\sigma }}_i\right)}^{+}$.

Remark 1

(Type utility ordering). Let $\mathbf{\sigma }\in \Delta$ be a mixed strategy Nash equilibrium and consider a player $i\in {\mathcal{I}}_t$. The following holds for all $j\in {\mathcal{I}}_t$,

• given $a\in supp{\left({\overrightarrow{\sigma }}_i\right)}^{+}$, if ${\sigma }_a^i<{\sigma }_a^j$, then $u(i;\mathbf{\sigma })>u(j;\mathbf{\sigma })$;
• given $a\in supp{\left({\overrightarrow{\sigma }}_i\right)}^{-}$, if ${\sigma }_a^i>{\sigma }_a^j$, then $u(i;\mathbf{\sigma })>u(j;\mathbf{\sigma })$;
• given $a\in supp\left({\overrightarrow{\sigma }}_i\right)\cap supp\left({\overrightarrow{\sigma }}_j\right)\backslash {\mathcal{A}}_t^0$, ${\sigma }_a^i={\sigma }_a^j\iff u(i;\mathbf{\sigma })=u(j;\mathbf{\sigma })$.

Points 1–3 in Remark 1 lead to the following Lemma regarding the support of strategies that yield different equilibrium payoffs for players of the same type.

Lemma 1

(Type-asymmetry obstructions). Let $\mathbf{\sigma }\in \Delta$ be a non-degenerated mixed-strategy profile that is a Nash equilibrium. Consider two individuals of the same type $i,j\in {\mathcal{I}}_t$ such that ${\overrightarrow{\sigma }}_i\ne {\overrightarrow{\sigma }}_j$ and $u(i;\mathbf{\sigma })>u(j;\mathbf{\sigma })$. The following holds

• $supp{\left({\overrightarrow{\sigma }}_i\right)}^{+}\subseteq supp{\left({\overrightarrow{\sigma }}_j\right)}^{+}$;
• $supp{\left({\overrightarrow{\sigma }}_i\right)}^0=\varnothing$;
• $supp{\left({\overrightarrow{\sigma }}_i\right)}^{-}\ne \varnothing$.

Furthermore, if $supp\left({\overrightarrow{\sigma }}_i\right)=supp\left({\overrightarrow{\sigma }}_j\right)\equiv \underline{a}$, then

$$\sum _{a\in \underline{a}}{\displaystyle \frac{1}{{\alpha }_a^{tt}}}=0.$$

(1)

A consequence of the above Lemma for any given Nash equilibrium $\mathbf{\sigma }$, is that given some type t, for any $i,j\in {\mathcal{I}}_t$ such that ${\overrightarrow{\sigma }}_i\ne {\overrightarrow{\sigma }}_j$, if $supp{\left({\overrightarrow{\sigma }}_i\right)}^0\ne \varnothing$, then $u(i;\mathbf{\sigma })\le u(j;\mathbf{\sigma })$. Furthermore, if it also holds that $sup{p}^0\left({\overrightarrow{\sigma }}_j\right)\ne \varnothing$ then $u(i;\mathbf{\sigma })=u(j;\mathbf{\sigma })$. The choice of support limits the difference in individual strategies. In particular, when for some game, the condition of Equation (1) never holds, then individuals choosing the same support will have to play the same strategy. Based on this idea, we will build the next definition and results. The proof of Lemma 1 is in the Appendix A.

Definition 1

(Mixed Type-Symmetry condition MTS). A subset $A\subseteq \mathcal{A}$ satisfies the mixed type-symmetry condition $(MTS)$ for a given type t if

$$\sum _{a^{\prime }\in A}\prod _{a\in A\backslash \left\{a^{\prime }\right\}}{\alpha }_a^{tt}\ne 0.$$

Note that the MTS is incompatible with Equation (1) of Lemma 1. The formulas are the same for any support $\underline{a}$ such that $\underline{a}\cap {\mathcal{A}}_t^0$ is empty. However, the MTS allows $\underline{a}\cap {\mathcal{A}}_t^0$ to be a singleton. These are the only two possibilities if $\underline{a}$ satisfies the MTS condition.

Let us define, for two players $i,j\in {\mathcal{I}}_t$ and two actions $a_1,a_2\in \mathcal{A}$, the following difference

$$\Delta V^t(a_1,a_2;{\mathbf{\sigma }}_{-\{i,j\}})\equiv V_{a_1}^t\left({\mathbf{\sigma }}_{-\{i,j\}}\right)-V_{a_2}^t\left({\mathbf{\sigma }}_{-\{i,j\}}\right).$$

Note that this does not depend on the order of i and j. Using Lemma 1 we will prove that the MTS condition will force these players to play the same, unique, strategy.

Theorem 1

(Support type-symmetry). In a Nash equilibrium, if two individuals of the same type $i,j\in {\mathcal{I}}_t$ choose the same support, $\underline{a}\subset \mathcal{A}$, and the support satisfies the MTS condition for type t, then ${\overrightarrow{\sigma }}_i={\overrightarrow{\sigma }}_j$. Furthermore, the support $\underline{a}$ uniquely determines their (equilibrium) strategy in terms of the strategies of the other individuals ${\mathbf{\sigma }}_{-\{i,j\}}$. In the case of non-singleton supports it is given by the solution to

$${\sigma }_{a^{\ast }}={\displaystyle \frac{{\prod }_{a\in \underline{a}\backslash \left\{a^{\ast }\right\}}{\alpha }_a^{tt}+{\sum }_a\left(\Delta V^t(a,a^{\ast };{\mathbf{\sigma }}_{-\{i,j\}}){\prod }_{a^{\prime }\in \underline{a}\backslash \{a^{\ast },a\}}{\alpha }_{a^{\prime }}^{tt}\right)}{{\sum }_{a\in \underline{a}}{\prod }_{a^{\prime }\in \underline{a}\backslash \left\{a\right\}}{\alpha }_{a^{\prime }}^{tt}}},$$

for all $a^{\ast }\in \underline{a}$.

Note that the strategy characterized above is an intersection of best responses, not the unique best response. That is why in the theorem, we mention it as an equilibrium strategy and not the best response to ${\mathbf{\sigma }}_{-\{i,j\}}$. Observe also that because of the MTS condition, the denominator is not zero, and the strategy is well-defined. Naturally, it must satisfy being a probability, in particular $\Delta V^t(a,a^{\ast };{\mathbf{\sigma }}_{-\{i,j\}})$ contains $\Delta {\omega }^t(a_1,a_2)\equiv {\omega }_{a_1}^t-{\omega }_{a_2}^t$, which means there is a set of action coordinates for which the expression is in $(0,1)$ and such an equilibrium is possible. When $\underline{a}\cap {\mathcal{A}}_t^0=\varnothing$, i.e., when there are no zeros among ${\alpha }_a^{tt}$ for all $a\in \underline{a}$, the expression reduces to

$${\sigma }_{a^{\ast }}={\displaystyle \frac{1+{\sum }_a(\Delta V^t(a,a^{\ast };{\mathbf{\sigma }}_{-\{i,j\}})/{\alpha }_a^{tt})}{1+{\sum }_{a\ne a^{\ast }}({\alpha }_{a^{\ast }}^{tt}/{\alpha }_a^{tt})}},\mathrm{for}a,a^{\ast }\in \underline{a}.$$

The determining point for a strategy involving some $a^{\ast }\in \underline{a}$ is the relation between $\Delta V^t(a,a^{\ast };{\mathbf{\sigma }}_{-\{i,j\}})$ and ${\alpha }_{a^{\ast }}^{tt}$.

4. Consequences and Corollaries

In this section, we briefly discuss the consequences of Theorem 1 for some typical games: (i) the case where the weights in the network are all non-negative (conformity games); (ii) the case where interaction matrices are the same for every action, that is, the set $\mathcal{N}$ is a singleton; and (iii) the case where there are only two possible actions, i.e., the action space $\mathcal{A}$ has only two elements. We abusively called this section consequences and corollaries because the results here are a consequence of Theorem 1, but some would require small computations or reasoning relating more than one of the previous remarks or results.

Proposition 1

(Conformity games). If for a given type t, ${\mathcal{A}}_t$ satisfies the MTS and ${\mathcal{A}}_t^{-}=\varnothing$, then all equilibria involve a unique strategy for type t.

Proof. 

Follows from putting together Lemma 1 and Remark 1. □

Consider now the class of games ${\Gamma }_{n_T,n_{\mathcal{A}}}(\mathbf{\omega };\left\{N\right\})$, where N is the $n_T\times n_T$ network, with entries ${\alpha }^{t{t}^{\prime }}$. (It is possible to consider the extended $n_{\mathcal{I}}\times n_{\mathcal{I}}$ network, but there is no relevant information added, except for the number of players of each type.) These are games with a constant network (does not depend on the strategies chosen). In this case, the mixed type-symmetry condition $(MTS)$ for a given type t is ${\alpha }^{tt}\ne 0$, and it is independent of the support choice.

Corollary 1

(Constant network). Consider a game with a constant network. Given a type t, if ${\alpha }^{tt}>0$, all strategies are type-symmetric. If ${\alpha }^{tt}<0$, all strategies with the same support are type-symmetric. Furthermore, given some non-singleton support $\underline{a}$, and two individuals $i_1,i_2\in {\mathcal{I}}_t$, the strategy is

$${\sigma }_{a^{\ast }}={\displaystyle \frac{1+\frac{1}{{\alpha }^{tt}}{\sum }_a\Delta {\omega }^t(a,a^{\ast })+{\displaystyle \sum _{j\ne i_1,i_2}}{\sigma }_a^j-{\displaystyle \sum _{j\ne i_1,i_2}}{\sigma }_{a^{\ast }}^j}{n_{\underline{a}}}},$$

where $n_{\underline{a}}$ is the cardinal of the support $\underline{a}$.

In the class of games with only two possible actions, that is ${\Gamma }_{n_T,2}$, there are only three possibilities of supports (including singletons). If the action set (i.e., the two possible actions) satisfy the MTS condition, then players of the same type can either play a pure strategy or the same nondegenerate mixed strategy, i.e., nondegenerate mixed strategies are type-symmetric in equilibrium.

Corollary 2

(Heterogeneous two-action games). Consider the class ${\Gamma }_{n_T,2}$ where $\mathcal{A}=\{a_1,a_2\}$. If for some type t we have ${\alpha }_1^{tt}+{\alpha }_2^{tt}\ne 0$, then all individuals of type t either play a pure strategy or the same strictly mixed strategy.

In the particular case of ${\Gamma }_{1,2}$, i.e., state-dependent network games with only one type of individuals and two possible actions, we have $\mathcal{N}=\{{\alpha }_1,{\alpha }_2\}$. Let us define aggregate indicators, for a given strategy $\mathbf{\sigma }$, indicating the number of players using, respectively, a mixed or pure strategy,

$$m\left(\mathbf{\sigma }\right)\equiv \#\{i\in {\mathcal{I}}_t:0<{\sigma }_a^i<1,a\in \mathcal{A}\},\mathrm{and},l_1\left(\mathbf{\sigma }\right)\equiv \#\{i\in {\mathcal{I}}_t:{\sigma }_{a_1}^i=1\}.$$

Let us define the decision threshold $T\left(l_1\right)\equiv -({\alpha }_1+{\alpha }_2)l_1+{\alpha }_2(n-1)$.

Corollary 3

(Homogeneous two-action games). Consider the class ${\Gamma }_{1,2}$, with only one type of individuals and two possible actions $\mathcal{A}=\{a_1,a_2\}$. Let σ be a Nash equilibrium. If ${\alpha }_1+{\alpha }_2\ne 0$, then σ induces a partition of $\mathcal{I}$ in at most three groups: two subsets using pure strategies and one subset with the following mixed strategy,

$${\sigma }_{a_1}={\displaystyle \frac{T\left(l_1\right)-\Delta \omega (a_1,a_2)}{({\alpha }_2+{\alpha }_1)(m-1)}},$$

and ${\sigma }_{a_2}=1-{\sigma }_{a_1}$.

5. Illustrative Examples (Numeric)

Let us go through some numerical examples which can help illustrate the work. As the results are for each type of player, it is sufficient to consider one type. However, we need at least three actions to clarify the richness of the equilibrium structure in a given game. Consider then the class ${\Gamma }_{1,3}$, with $\mathcal{I}=\{1,2,\dots ,8\}$ (eight) players of the same type, and three actions $\mathcal{A}=\{a,b,c\}$. The possible supports for nondegenerate mixed strategies in this class are $\{a,b\},\{a,c\},\{b,c\}$ and $\{a,b,c\}$.

A member of ${\Gamma }_{1,3}$ (a game) is completely defined by action coordinates $\mathbf{\omega }$ and interaction structure $\mathcal{N}$. For clarity we will omit the type superscripts, as there is only one type. Suppose $\mathcal{N}=\{r+1,r,r-1\}$ for some constant $r\in \mathbb{R}$ (note that the three matrices $N_a={\alpha }_a$ for $a\in \mathcal{A}$ are $1\times 1$ because there is only one type). We can check the MTS condition for each of the possible supports:

• for $\{a,b\}$ it is $r+(1+r)=2r+1$;
• for $\{a,c\}$ it is $(r-1)+(1+r)=2r$;
• for $\{b,c\}$ it is $(r-1)+r=2r-1$;
• for $\{a,b,c\}$ it is $r(r-1)+(r+1)(r-1)+(r+1)r=3r^2-1$.

The condition depends on the value of r, and we will now consider the different cases (note that the above values are also the denominators for the strategy defined in Theorem 1 for each support). Let us also define $l_{\underline{a}}$ as the number of players who choose a given support $\underline{a}\subseteq \mathcal{A}$ in an equilibrium.

5.1. $r=2$ (Conformity)

For every $\mathbf{\omega }$ the game ${\Gamma }_{1,3}(\mathbf{\omega };\{3,2,1\})$ is a conformity game. Thus, by Proposition 1, in equilibrium, we must have, for all supports, $l_{\underline{a}}=8$ (i.e., all players (8) must use the same mixed strategy in equilibrium). Furthermore, all possible supports satisfy the MTS condition. Therefore, Theorem 1 gives us the strategies associated with each support.

Suppose, for example, we take the game with $\mathbf{\omega }=(1,-2,{\omega }_c)$ for some constant ${\omega }_c\in \mathbb{R}$. Let us denote $\mathbf{q}=(q,1-q)$ the strategy associated with $\{a,b\}$. Then, for all $i,j$,

$$\Delta V(b,a;{\mathbf{q}}_{-\{i,j\}})=-2+6·2(1-q)-1-6·3q=9-30q,$$

which allows us to compute q using Theorem 1. We obtain $q=\frac{2+9-30q}{5}$, therefore we obtain $\mathbf{q}=(11/35,24/35)$. The strategy produces payoff $u(i,\mathbf{q})=336/35$, so $\mathbf{q}$ is an equilibrium if players do not want to change to c, thus if ${\omega }_c\le 336/35$.

We can proceed analogously for the rest of the two-action supports, finding $(\frac{{\omega }_c+6}{28},\frac{22-{\omega }_c}{28})$ for $\{a,c\}$, which is an equilibrium if $-6<{\omega }_c<22$; and $(1-\frac{{\omega }_c}{9},\frac{{\omega }_c}{9})$ for $\{b,c\}$ with $0<{\omega }_c<9$.

For the strategy associated with $\{a,b,c\}$, let $\mathbf{p}=(p_a,p_b,1-p_a-p_b)$. Then, for all $i,j$, we obtain

$$\Delta V(b,a;{\mathbf{p}}_{-\{i,j\}})=-2+12p_b-1-18p_a=-3+12p_b-18p_a,$$

$$\Delta V(c,a;{\mathbf{p}}_{-\{i,j\}})={\omega }_c+6(1-p_a-p_b)-1-6·3p_a={\omega }_c+5-24p_a-6p_b,$$

thus

$$p_a=\frac{2·1+(-3+12p_b-18p_a)·1+({\omega }_c+5-24p_a-6p_b)·2}{11},$$

hence, $p_a=\frac{9+2{\omega }_c}{77}$. If we proceed similarly to find $p_b$, we obtain $\mathbf{p}=(\frac{9+2{\omega }_c}{77},\frac{30+3{\omega }_c}{77},\frac{38-5{\omega }_c}{77})$, with the restriction $-9/2<{\omega }_c<38/5$.

Note that the set of equilibria can only contain the above strategies and, eventually, pure strategies. It may happen they all coexist in the equilibrium set if $0<{\omega }_c<38/5$, but for some other games (values of ${\omega }_c$), just some of the strategies are equilibrium or none. For example, if ${\omega }_c=20$, there is a unique nondegenerate mixed strategy: the one associated with $\{a,c\}$.

5.2. $r=-2$ (Congestion)

In this case, we obtain ${\Gamma }_{1,3}(\mathbf{\omega };\{-1,-2,-3\})$, a congestion game for all $\mathbf{\omega }$. That means that equilibria of the type found in the previous case may exist. However, there may also be equilibria where players choose different supports. Namely, that means each support may have more than one associated strategy, i.e., where $l_{\underline{a}}<8$. However, if the MTS condition is satisfied, all players using the same support must play the same strategy. For $r=-2$ all possible supports satisfy the MTS. Thus, we can use Theorem 1 to find the respective strategy.

For example, suppose we take $\mathbf{\omega }=(1,6,7)$, and let us look for an equilibrium where $l_{\{a,b\}}=3$ and $l_{\{a,c\}}=5$. (Not all possibilities exist always. Here, $\mathbf{\omega }$ was chosen carefully so that this possibility exists.) Theorem 1 applies, but now strategies are interconnected. Suppose $\mathbf{p}=(p,1-p)$ and $\mathbf{q}=(q,1-q)$ are strategies such that $supp\left(\mathbf{p}\right)=\{a,b\}$ and $supp\left(\mathbf{q}\right)=\{b,c\}$. Proceeding analogously as before, to find p and q, we find for $i,j$ playing $\mathbf{p}$,

$$\Delta V(b,a;{\mathbf{p}}_{-\{i,j\}})=6+(l_{\{a,b\}}-2)·(-2)(1-p)+l_{\{b,c\}}·(-2)q-1-(l_{\{a,b\}}-2)(-1)p,$$

so $\Delta V(b,a;{\mathbf{p}}_{-\{i,j\}})=3-10q+3p$. Using the equation in Theorem 1, we obtain

$$p={\displaystyle \frac{-2+3-10q+3p}{-3}},$$

which is $p=\frac{1-10q}{-6}$. (The expression given in Theorem 1 still carries p because it gives the strategy of 2 players written in terms of the other players, and here there are 3 who use p.) We proceed similarly to find q, and then solving for both we obtain $\mathbf{p}=(\frac{1}{2},\frac{1}{2})$ and $\mathbf{q}=(\frac{2}{5},\frac{3}{5})$. We observe that Theorem 1 only guarantees the same payoff in all actions in the support. However, these strategies are, in fact, an equilibrium of the game, as players using $\mathbf{p}$ do not have an incentive to change to c because $u(i,\mathbf{p})=0>7+5(-3)(3/5)=-2$, and analogously for $\mathbf{q}$ because $u(i,\mathbf{q})=-1/5>1-3/2=-1/2$.

Note that the equilibrium we found here is $\sigma =(\mathbf{p},\mathbf{p},\mathbf{p},\mathbf{q},\mathbf{q},\mathbf{q},\mathbf{q},\mathbf{q})$ or any permutation, as players are indistinguishable.

5.3. $r=0$

In the case of games ${\Gamma }_{1,3}(\mathbf{\omega };\{1,0,-1\})$, besides all the possibilities presented in the previous examples, we have one support, $\{a,c\}$, which does not satisfy the MTS condition. Therefore, there may be equilibria in which players of the same type use different strategies with the same support, if that support is $\{a,c\}$. If a given strategy with support $\{a,c\}$ is part of an equilibrium, then all choices of a probability distribution over $\{a,c\}$ for the same players are also an equilibrium. However, we note that these are rare or frontier cases.

For example, suppose we take $\mathbf{\omega }=(1,-2,{\omega }_c)$ as in the first example, and let $L_{\{a,c\}}\subseteq \mathcal{I}$ be the set of players i such that $supp\left({\overrightarrow{\sigma }}_i\right)=\{a,c\}$ in some strategy profile $\mathbf{\sigma }$. Note that $\#L_{\{a,c\}}=l_{\{a,c\}}$. For $\sigma$ to be an equilibrium, it would be necessary that for all $i\in L_{\{a,c\}}$ the following (payoffs for a and c) holds

$$1+\sum _{j\in \mathcal{I}\backslash L_{\{a,c\}}}{\sigma }_a^j+\sum _{i\in L_{\{a,c\}}}{\sigma }_a^i={\omega }_c+(-1)\sum _{j\in \mathcal{I}\backslash L_{\{a,c\}}}{\sigma }_c^j+(-1)\sum _{i\in L_{\{a,c\}}}(1-{\sigma }_a^i),$$

which leads to

$${\omega }_c=-1-l_{\{a,c\}}-\sum _{j\in \mathcal{I}\backslash L_{\{a,c\}}}{\sigma }_c^j-\sum _{j\in \mathcal{I}\backslash L_{\{a,c\}}}{\sigma }_a^j.$$

As such, there is only one value of ${\omega }_c$ (one game) for which the given strategy can be part of an equilibrium. Furthermore, ${\omega }_c$ must also satisfy the interval restriction imposed by the strategies of remaining players, which sometimes is unfeasible. It is in opposition to what we saw in the first example ($r=2$), where there was an interval associated with each ${\omega }_c$.

6. Concluding Remarks

The main idea of this paper can be summarized following an approach analogous to [2] or [1]: given a type t and a vector $\overrightarrow{\sigma }\in {\Delta }^{n_{\mathcal{A}}}$, let us call a group to the maximal subset of individuals of the same type that choose the exact same strategy, $G(t,\overrightarrow{\sigma })\equiv \{i\in {\mathcal{I}}_t:{\overrightarrow{\sigma }}_i=\overrightarrow{\sigma }\}\subseteq \mathcal{I}$. A strategy profile $\mathbf{\sigma }$ naturally induces a partition of $\mathcal{I}$ into groups. Let $\#\mathcal{P}\left(\mathcal{A}\right)$ be the cardinal of the power set of $\mathcal{A}$.

Remark 2

(Groups). For every game ${\Gamma }_{n_T,n_{\mathcal{A}}}$ if every $A\subseteq \mathcal{A}$ satisfies the MTS condition for every type t, then, in a Nash equilibrium, the number of groups is bounded by $(\#\mathcal{P}\left(\mathcal{A}\right)-1)n_T$. If there exists $A\subseteq \mathcal{A}$ such that A does not satisfy the MTS condition, then the number of groups may be $n_{\mathcal{I}}$.

Verifying if every element in $\mathcal{P}\left(\mathcal{A}\right)$ satisfies the MTS condition naturally grows in complexity, but that is one of the points in this note: the generalization of support-type-symmetries from the class of two action games is not straightforward, nor is its complexity. Nevertheless, it is trivially satisfied in games where all weights in the interaction matrix are non-zero and have the same sign.

Remark 3

(Groups in conformity and congestion games). For congestion games, the number of groups in a Nash equilibrium is bounded by $(\#\mathcal{P}\left(\mathcal{A}\right)-1)n_T$. For conformity games, it is bounded by $n_T$.

We have focused the analysis on strategies with the same support. Nevertheless, for different supports the MTS condition still implicitly carries the idea that, for same type players, different strategies force the intersection of supports to some null externality set. We concretize this in the following remark, which relates to Remark 1.

Remark 4.

Let σ be a Nash equilibrium of some game Γ. Let ${\underline{A}}^{\ast }\subseteq \mathcal{A}$ be a maximal subset ${\underline{A}}^{\ast }\subseteq supp\left({\overrightarrow{\sigma }}_i\right)\cap supp\left({\overrightarrow{\sigma }}_j\right)$ for which the MTS condition holds. If $u(i;\mathbf{\sigma })=u(j;\mathbf{\sigma })$, then for all $a\in {\underline{A}}^{\ast }$ players must use the same probability, that is ${\sigma }_a^i={\sigma }_a^j$.