Extensive–form games with heterogeneous populations: solution concepts,equilibria characterization,learning dynamics

2.1 Game definition and strategies

A perfect–information extensive–form game [8] is a tuple (N, A, V, T, ι, ρ, χ, u), where: N is the set of agents (i ∈ N denotes a generic agent), A is the set of actions (A _i  ⊆ A denotes the set of actions of agent i and a ∈ A denotes a generic action), V is the set of decision nodes (V _i  ⊆ V denotes the set of decision nodes of i), T is the set of terminal nodes (w ∈ V ∪ T denotes a generic node and w₀ is root node), ι : V → N returns the agent that acts at a given decision node, ρ : V → ℘ (A) returns the actions available to agent ι (w) at w, χ : V × A → V ∪ T assigns the next (decision or terminal) node to each pair 〈w, a〉 where a is available at w, and u = (u₁, …, u_|N|) is the set of agents’ utility functions u i : T → ℝ. Games with imperfect information extend those with perfect information, allowing one to capture situations in which some agents cannot observe some actions undertaken by other agents. We denote by V_i,h the h–th information set of agent i. An information set is a set of decision nodes such that when an agent plays at one of its nodes she cannot distinguish the node in which she is playing. For the sake of simplicity, we assume that every information set has a different index h, thus we can univocally identify an information set by h. Furthermore, since the available actions at all nodes w belonging to the same information set h are the same, with abuse of notation, we write ρ (h) in place of ρ (w) with w ∈ V_i,h. An imperfect–information game is a tuple (N, A, V, T, ι, ρ, χ, u, H) where (N, A, V, T, ι, ρ, χ, u) is a perfect–information game and H = (H₁, …, H_|N|) induces a partition V _i  = ⋃ _{h∈H i} V_i,h such that for all w, w′ ∈ V_i,h we have ρ (w) = ρ (w′). We focus on games with perfect recall where each agent recalls all the own previous actions and the ones of the opponents [8].

A behavioral strategy σ _i is represented as a probability distribution σ_i,a over the actions a ∈ A _i available at each information set h. Working with behavioral strategies is computationally hard, requiring highly non–linear optimization tools. With two agents the sequence form [12] allows one not to resort to non–linear programming. A sequence q ∈ Q _i is a set of consecutive actions a ∈ A _i , where Q _i  ⊆ Q is the set of sequences of agent i and Q is the set of all the sequences. A sequence can be terminal, if, combined with some opponents’ sequence, it leads to a terminal node (Q ¯ denotes the subset of terminal sequences), or non–terminal, if it cannot lead to any terminal node for every opponents’ sequence. The initial sequence of every agent, denoted by q₀, is said empty sequence and, given sequence q ∈ Q _i leading to some information set h ∈ H _i , we say that q′ extends q (denoted by q′ = q|a′) if the last action of q′ (denoted by a (q′) = a′) is some action a′ ∈ ρ (w) with w ∈ V_i,h. We denote a sequence–form strategy profile by a vector x = [x₁, …, x_|N|] where x _i is the strategy of agent i and we denote by x _i  (q) the probability associated with sequence q ∈ Q _i . Well–defined sequence–form strategies are such that, for every information set h ∈ H _i , the probability x _i  (q) assigned to the sequence q leading to h is equal to the sum of the probabilities x _i  (q′), for all the sequences q′ that extend q at h. The agent i’s utility is represented as a sparse matrix U _i .

2.2 Solution concepts and computation

It is well known that the NE concept is not satisfactory for extensive–form games, allowing agents to play non–credible threats. The concept of SPE refines the concept of NE, constraining a strategy profile to be an NE in every subgame [8], where a subgame is a portion of the game tree defined as follows: it has a root and for every node w ∈ V_i,h belonging to thesubgame the whole information set V_i,h belongs to the subgame. An SPE can be easily found by applying backward induction [8]. The concept of SPE is not satisfactory with imperfect information. In this case, SE [13] is used. An SE is a pair ( σ , σ ˆ ), where σ are the agents’ strategies and σ ˆ are the agents’ beliefs over the opponents’ strategies, such that σ are sequentially rational to σ ˆ and σ ˆ are consistent to σ.

The concept of SCE relaxes NE, capturing settings where opponents’ utilities and types are unknown. Similarly to an SE, an SCE is a pair ( σ , σ ˆ ) where σ are best responses to σ ˆ. Differently, σ ˆ can be wrong off the equilibrium path (instead they must be correct/confirmed on). Thus, every NE is an SCE, while an SCE may be not an NE.

Now, we briefly survey the main computational results. Finding an NE is PPAD–complete [5]. The problem to search for an NE is formulated as a linear–complementarity problem (LCP) and solved by employing the Lemke algorithm [14], a generalization of the algorithm presented in [15]. Other algorithms are based on support enumeration [18] and MILP [19]. The problem to verify whether a strategy profile, both in sequence form and agent form, is an NE can be easily solved in polynomial time by checking whether or not the constraints are satisfied. Finding an SE in PPAD and can be achieved by a variation of the Lemke’s algorithm [16]. Verifying whether or not a given solution is an SE is in P [9]. The unique result on the computation of SCEs shows that finding a basic SCE can be formulated as an MILP [10].

3.1 Game model

We focus on two–agent extensive–form games that are repeatedly played by different individuals as described in [7]. More precisely, for each agent (representing a role), there is a population of individuals and, at each repetition of the game, one individual is drawn from each population and the two drawn individuals are matched and then play the game. At each repetition, we may have individuals different from those of the previous repetitions. A common example is a market in which bilateral negotiations are carried out: there are two agents/roles (i.e., buyer and seller), but different buyers and different sellers can match. Other economic examples are given by auctions.

The game model proposed in [7] presents the following two main limitations that we remove in this paper.

Infinite populations: the number of individuals of all the populations is infinite. While this model can be a fine approximation with large populations, it is not when the populations contain few individuals.

In our model, we allow populations to be finite or infinite and to be heterogeneous including individuals of different types, where types differentiate for their preferences. We denote by Θ = (Θ₁, …, Θ_|N|) the set of all the types (θ denotes a generic type), where Θ _i is the set of types of agent i. We assume that the number of types is finite. We denote by Θ_–i = × _j≠i Θ _j the set of all the possible profiles of types of all the agents except agent i. Utility functions are defined also over types (in addition to the strategies of the agents). When types are non–interdependent, we have u _i  = u _i  (θ, σ _i , σ_–i) where θ ∈ Θ _i ; instead when types are interdependent we have u _i  = u _i  (θ, θ′, σ _i , σ_–i) where θ ∈ Θ _i and θ′ ∈ Θ_–i. For each type θ ∈ Θ _i , there is a (possibly infinite) population of individuals Λ _θ (we denote by λ a generic individual and by Λ _i the set of all the individuals of agent i). Each type θ ∈ Θ _i is associated with a probability ω_i,θ with which an individual of the pertinent population is drawn. Obviously, ∑_{θ∈Θ i} ω_i,θ = 1.Similarly, each individual λ ∈ Λ _θ is associated with a probability ω_i,θ,λ with which the individual is drawn such that ∑_{λ∈Λ θ} ω_i,θ,λ = ω_i,θ. For the sake of presentation, we assume that each individual has a different index λ and therefore we can refer to an individual λ ∈ Λ _θ by using λ in place of 〈i, θ, λ〉. Similarly, we assume each type has a different θ, therefore we can refer to a type θ ∈ Θ _i by using θ in place of 〈i, θ〉.

Different individuals may adopt different strategies. σ _λ denotes the strategy of individual λ. The aggregate strategy of the individuals of type θ ∈ Θ _i is σ _θ  = ∑_{λ∈Λ θ} σ _λ  · ω _λ , and the one of agent i is σ _i  = ∑_{θ∈Θ i} σ _θ  · ω _θ .

As in [7], we assume that agents have no information about the opponents. Specifically, we assume:

each individual has no information about the utility functions of the other agents;

Customarily, a game with types is said Bayesian. Each individual forms a belief over the opponents and adjusts it during the play. More precisely, when utilities are not interdependent, each individual λ of agent i has a (potentially different) belief σ ˆ λ j over the aggregate strategy of agent j for every j ≠ i. This is because each individual λ does not know the types and the individuals of the opponents and therefore she cannot form any belief over the single individual or type of the opponents. When utilities are interdependent, each individual λ of agent i has a (potentially different) belief σ ˆ λ θ over the aggregate strategy of type θ ∈ Θ _j for every j ≠ i and a (potentially different) belief ω ˆ λ θ over the pertinent probability ω _θ (also in this case individuals have not beliefs over the single individuals of the opponents).

Example 3.1. Agent 1 is of three types θ_1.1, θ_1.2, θ_1.3, each with probability ω_1.1, ω_1.2, ω_1.3. Two individuals λ_1.1.1, λ_1.1.2 are of type θ_1.1 (with ω_1.1.1 + ω_1.1.2 = ω_1.1), while only one individual λ_1.2.1 is of type θ_1.2 (with ω_1.2.1 = ω_1.2) and only one individual λ_1.3.1 is of type θ_1.3 (with ω_1.3.1 = ω_1.3). Notice that without interdependency the separation between types and individuals is not necessary and all the information can be coded by individuals (and not by types as discussed in Section 4), whereas with interdependency the separation is necessary, utilities being defined on types.

3.2 Solution concepts

Different solution concepts extending the SCE can be provided according to each specific situation, see Tab. 1.

The basic solution concept, introduced in [7], is the unitary SCE (USCE) that captures situations with a unique type per agent and a unique individual per type. A USCE constrains the agent’s strategy to be best response to the belief over opponent’s strategy and constrains beliefs to be correct (w.r.t. the strategies) on the equilibrium path.

Definition 3.2. A USCE is a pair ( σ , σ ˆ ) such that:

each agent i has single type θ and single individual λ;

Upon the USCE concept, we build the solution concepts for other (more complex) situations. We consider the situation with one type per agent and multiple finite individuals: the solution concept is finite heterogeneous SCE (FHSCE).

Definition 3.3. An FHSCE is a pair ( σ , σ ˆ ) such that:

each agent i has a single type θ and a finite number of individuals λ;

Notice that the constraints over the beliefs of an individual λ and the equilibrium path she observes depend on σ _λ . Thus, different individuals may have different strategies, each supported by different beliefs.

When there is an infinite number of individuals, the above definition is not operative, requiring one to specify an infinite number of strategies and beliefs. In this case, according to [7], we can work at the level of the single action a and we can state that a ∈ A _i could be played by agent i if there is a belief (confirmed on the equilibrium path) such that this action is a best response. As a result, for every action a ∈ A _i we need to define a belief σ ˆ i , a - i. As done above, we use σ ˆ a - i in place of σ ˆ i , a - i, under the assumption that each action a has a different label. The solution concept is the infinite heterogeneous SCE (IHSCE).

Definition 3.4. An IHSCE is a pair ( σ , σ ˆ ) such that:

each agent i has a single type θ and an infinite number of individuals λ;

We focus on Bayesian games. We report only the definition of the Bayesian USCE concept (BUSCE) because the redefinitions of FHSCE and IHSCE with Bayesian games (BFHSCE and BIHSCE, respectively) are similar.

Definition 3.5. A BUSCE is a pair ( σ , σ ˆ ) such that:

each agent i has a finite number of types θ and a single individual λ per type;

Finally, we remark that every game admits at least one SCE per extension, since the SCE concept relaxes the NE concept and every game admits at least an NE.

3.3 Computational results

We study both the problem to compute an equilibrium according to the solution concepts defined above and to verify whether a given solution is one of such solution concepts.

We initially consider the equilibrium computation problem. The solution concept definitions provided in the previous section are based on behavioral strategies, but it is known that behavioral strategies pose severe computational problems [20]. However, since those constraints are defined exclusively on the equilibrium path, it is possible to redefine them in terms of sequence–form strategies without perturbations (as instead it is needed for SEs to capture the off–the–equilibrium–path behavior). As a result, we have x _λ , x ˆ λ - i, x ˆ λ θ ′ for SCEs with finite populations, and x _θ , x_θ,q, x ˆ θ , q - i, x ˆ θ , q θ ′ for SCEs with infinite populations.

A specific sample of SCE extensions can be computed by searching for an NE and thus it can be solved by using the Lemke algorithm applied to the sequence form (in the case all the individuals have correct beliefs, all the individuals of the same type behave in the same way and therefore the game is essentially a Bayesian two–agent game). Hence, the problem to compute an SCE extension with two agents is PPAD–complete. However, the computation of a specific sample is not interesting when dealing with learning agents that can potentially achieve any equilibrium, while the aim is the derivation of the equilibrium conditions and the enumeration of all the equilibria. Indeed, knowing all the equilibria and their stability properties in terms of attractors, saddle points, and repellers, we can have a complete picture about all the possible learning dynamics of the agents.

The constraint expressing that a belief is confirmed on the equilibrium path is not linear and neither expressible as a linear complementarity constraint problem (LCP). Instead, it can be formulate as a non–linear complementary constraint problem (NLCP). Indeed, the constraint over the belief on a sequence (or an action indifferently) must be active only if such sequence (or action) is on the equilibrium path. More precisely, sequence q|a ∈ Q_–i is on the equilibrium path if both q|a is played with strictly positive probability and there is at least a sequence q′ ∈ Q _i leading to h ∈ H_–i, where a ∈ ρ (h), that is played with strictly positive probability. Given sequence q|a ∈ Q_–i, we denote by f (q|a) ⊆ Q _i the set of sequences leading to h ∈ H_–i such that a ∈ ρ (h). A possible way to code the above constraint with USCEs is: x λ ( q ′ ) · x λ ′ ( q | a ) · ( x ˆ λ - i ( q | a ) - x λ ′ ( q | a ) ) = 0 for every q′ ∈ f (q|a), where λ is an individual of agent i and λ′ is an individual of agent –i (notice that this constraint is not expressed as a NLCP, but it can be easily cast to such form). These non–linear constraints can be linearized by using binary variables.

We define the binary variables as s _λ  (q) such that s _λ  (q) =1 when q ∈ Q _i is played with positive probability by λ. Similarly, we use binary variables s _θ  (q) such that s _θ  (q) =1 when q is played with positive probability by at least one individual of θ, and we use binary variables s _i  (q) such that s _i  (q) =1 when q is played with positive probability by at least one individual of i. The previous non–linear constraint can be formulated as a pair of constraints: x ˆ λ - i ( q | a ) - x λ ′ ( q | a ) ≤ M · ( 2 - s λ ( q ′ ) - s λ ′ ( q | a ) ) and x λ ′ ( q | a ) - x ˆ λ - i ( q | a ) ≤ M · ( 2 - s λ ( q ′ ) - s λ ′ ( q | a ) ) for every q′ ∈ f (q|a), where M is an arbitrarily large constant. The problem to compute a BFHSCE when types are not interdependent can be formulated as the MILP (1)–(12), while the program for an FHSCE is a trivial simplification obtained by setting |Θ _i |=1 for every i.

Here, constraints (1) and (2) force v _λ  (h) at each h of individual λ to be equal to the expected (w.r.t. the individual’s beliefs x ˆ λ - i) utility of the best sequence available at h (similar constraints are used in MILP Nash formulation [19]); constraints (3) and (4) force the belief x ˆ λ - i ( q ) of individual λ over the aggregate opponent’s strategy x_–i to be correct on the equilibrium path (notice that, when 2 – s _λ  (f (q)) – s_–i (q) =0, q is on the equilibrium path); constraints (5) and (6) assure that x _λ is a well defined strategy; constraints (7) and (8) assure that x ˆ λ - i is a well–defined belief; constraints (9) assure that s _λ  (q) =1 if q are played with positive probability by individual λ; constraints (10) assure that s _i  (q) are strictly positive if at least one individual of i plays q with positive probability; constraints (11) and (12) define the domains of the variables. Differently from the case of NE or its refinements, both strategies and beliefs are variables.

Notice that the above program (1)–(12) is mixed–integer linear independently of the number of individuals per type. This is because each individual plays the best response to her beliefs, her beliefs are equal to the aggregate opponent’s strategy on the equilibrium path, and each agent aggregate strategy is given by the sum of the single individual strategies. In this perspective, the number of individuals behaves as the number of types. However, as we show in the next section, types and individuals have radically different effects on the set of equilibria.

The MILP for computing a BIHSCE is more involved. For each pair θ, q, we need a strategy x_θ,q (·) defined over the whole game and the corresponding values v_θ,q (·) per information set, and we need a belief x ˆ θ , q - i ( · ) over the aggregate opponent’s strategy. The MILP for computing a BIHSCE with non–interdependent types is program (13)–(26), while the program for IHSCE can be obtained with |Θ _i |=1 for every i.

Here, constraints (13) and (14) force v_θ,q (h) at each h of type θ related to q to be equal to the expected utility of the best sequence available at h; constraints (15) and (16) ensure that x ˆ θ , q - i ( · ) are correct on the equilibrium path identified by x_θ,q (·) and x_–i (·); constraints (17) and (18) guarantee that x_θ,q (·) is well defined and not played with a probability larger than ω _θ ; constraints (19) and (20) make the same with strategy x _θ  (·); constraints (21) and (22) ensure that x ˆ θ , q - i ( · ) are well defined; constraints (23) force s _θ  (q) =1 if there is a belief of type θ such that q is a best response; constraints (24) force s _i  (q) =1 if at least a type of i plays q with positive probability; constraints (25) and (26) define the domain of the variables.

We focus on the problem to verify whether a given solution is an SCE extension.

Proposition 3.6 The problem to verify whether or not a solution ( σ , σ ˆ ) (even expressed in sequence form) is one of the above SCE extensions is in P.

v λ ( h ) ≥ ∑ h ′ ∈ H i ( q | a ) v λ ( h ′ ) + ∑ q ′ ∈ Q - i u i ( θ , q | a , q ′ ) · x ˆ λ - i ( q ′ ) ∀ i ∈ N , q ∈ Q i , h ∈ H i ( q ) , a ∈ ρ ( h ) , θ ∈ Θ i , λ ∈ Λ θ(1) v λ ( h ) ≤ ∑ h ′ ∈ H i ( q | a ) v λ ( h ′ ) + ∑ q ′ ∈ Q - i u i ( θ , q | a , q ′ ) · x ˆ λ - i ( q ′ ) + M ( 1 - s λ ( q | a ) ) ∀ i ∈ N , q ∈ Q i , h ∈ H i ( q ) , a ∈ ρ ( h ) , θ ∈ Θ i , λ ∈ Λ θ(2) x ˆ λ - i ( q | a ) ≥ ∑ λ ′ ∈ Λ θ ′ , θ ′ ∈ Θ - i x λ ′ ( q | a ) - M · ( 2 - s λ ( q ′ ) - s - i ( q | a ) ) ∀ i ∈ N , q ∈ Q - i , q ′ ∈ f ( q | a ) , λ ∈ Λ θ , θ ∈ Θ i(3) x ˆ λ - i ( q | a ) ≤ ∑ λ ′ ∈ Λ θ ′ , θ ′ ∈ Θ - i x λ ′ ( q | a ) + M · ( 2 - s λ ( q ′ ) - s - i ( q | a ) ) ∀ i ∈ N , q ∈ Q - i , q ′ ∈ f ( q | a ) , λ ∈ Λ θ , θ ∈ Θ i(4) x λ ( q 0 ) = ω λ ∀ i ∈ N , λ ∈ Λ θ , θ ∈ Θ i(5) x λ ( q ) = ∑ a ∈ ρ ( h ) x λ ( q | a ) ∀ i ∈ N , λ ∈ Λ θ , q ∈ Q , h ∈ H i , q , θ ∈ Θ i(6) x ˆ λ - i ( q 0 ) = 1 ∀ i ∈ N , λ ∈ Λ θ , θ ∈ Θ i(7) x ˆ λ - i ( q ) = ∑ a ∈ ρ ( h ) x ˆ λ - i ( q | a ) ∀ i ∈ N , λ ∈ Λ θ , q ∈ Q , h ∈ H i , q , θ ∈ Θ i(8) s λ ( q ) ≥ x λ ( q ) ∀ i ∈ N , λ ∈ Λ θ , θ ∈ Θ i , q , ∈ Q i(9) s i ( q ) ≥ s λ ( q ) ∀ i ∈ N , λ ∈ Λ θ , q ∈ Q i , θ ∈ Θ i(10) s i ( q ) , s λ ( q ) ∈ { 0 , 1 } ∀ i ∈ N , q ∈ Q i , θ ∈ Θ i , λ ∈ Λ θ(11) x λ ( q ) , x ˆ λ - i ( q ) ≥ 0 ∀ i ∈ N , q ∈ Q i , θ ∈ Θ i , λ ∈ Λ θ(12) v θ , q | a ( h ) ≥ ∑ h ′ ∈ H i ( q | a ) v θ , q | a ( h ′ ) + ∑ q ′ ∈ Q - i u i ( θ , q | a , q ′ ) · x ˆ θ , q | a - i ( q ′ ) ∀ i ∈ N , q ∈ Q i , h ∈ H i ( q ) , θ ∈ Θ i , a ∈ ρ ( h )(13) v θ , q | a ( h ) ≤ ∑ h ′ ∈ H i ( q | a ) v θ , q | a ( h ′ ) + ∑ q ′ ∈ Q - i u i ( θ , q | a , q ′ ) · x ˆ θ , q | a - i ( q ′ ) + ∀ i ∈ N , q ∈ Q i , h ∈ H i ( q ) , θ ∈ Θ i , a ∈ ρ ( h ) M ( 1 - s θ , q | a ( q | a ) )(14) x ˆ θ , q - i ( q ′ | a ) ≥ ∑ θ ′ ∈ Θ - i x θ ′ ( q ′ | a ) - M · ( 2 - s θ , q ( q ″ ) - s - i ( q ′ | a ) ) ∀ i ∈ N , q ∈ Q i , q ″ ∈ f ( q ′ | a ) , q ′ ∈ Q - i , θ ∈ Θ i(15) x ˆ θ , q - i ( q ′ | a ) ≤ ∑ θ ′ ∈ Θ - i x θ ′ ( q ′ | a ) + M · ( 2 - s θ , q ( q ″ ) - s - i ( q ′ | a ) ) ∀ i ∈ N , q ∈ Q i , q ″ ∈ f ( q ′ | a ) , q ′ ∈ Q - i , θ ∈ Θ i(16) x θ , q ′ ( q 0 ) = ω θ ∀ i ∈ N , θ ∈ Θ i , q ′ ∈ Q i(17) x θ , q ′ ( q ) = ∑ a ∈ ρ ( h ) x θ , q ′ ( q | a ) ∀ i ∈ N , θ ∈ Θ i , q , q ′ ∈ Q i , h ∈ H i , q(18) x θ ( q 0 ) = ω θ ∀ i ∈ N , θ ∈ Θ i(19) x θ ( q ) = ∑ a ∈ ρ ( h ) x θ ( q | a ) ∀ i ∈ N , θ ∈ Θ i , q ∈ Q i , h ∈ H i , q(20) x ˆ θ , q ′ - i ( q 0 ) = 1 ∀ i ∈ N , θ ∈ Θ i(21) x ˆ θ , q ′ - i ( q ) = ∑ a ∈ ρ ( h ) x ˆ θ , q ′ - i ( q | a ) ∀ i ∈ N , θ ∈ Θ i , q ∈ Q i , h ∈ H i , q(22) s θ , q ′ ( q ) ≥ x θ , q ′ ( q ) ∀ i ∈ N , θ ∈ Θ i , q , q ′ ∈ Q i(23) s i ( q ) ≥ s θ , q ′ ( q ) ∀ i ∈ N , θ ∈ Θ i , q , q ′ ∈ Q i(24) s i ( q ) , s θ , q ′ ( q ) ∈ { 0 , 1 } ∀ i ∈ N , q , q ′ ∈ Q i , θ ∈ Θ i(25) x θ ( q ) , x θ , q ′ ( q ) , x ˆ θ , q ′ - i ( q ) ≥ 0 ∀ i ∈ N , q , q ′ ∈ Q i , θ ∈ Θ i(26)

Proof. Trivially, the verification problem requires one to check whether or not the pertinent above constraints are satisfied. Being the number of those constraints polynomial in the size of the game, the verification problem can be solved in polynomial time.□

More interesting is the verification problem when the input solution is partially specified, the beliefs being omitted. This problem is common when we question whether learning dynamics, e.g. approaching some attractor, are converging to some solution concepts.

Theorem 3.7. The problem to verify whether or not there is a solution ( σ , σ ˆ ) with a given strategy profile σ (even expressed in sequence form) that is one of the above SCE extensions is in P.

Proof. We focus on FHSCE (the proof for the other SCE extensions is similar). The verification problem when the input specifies only the strategies is equivalent to the problem, for each individual λ, to search for a belief confirmed on the equilibrium path such that the strategy of λ is best response. This problem is an overconstrained version (with a linear number of additional constraints) of the problem to verify whether or not a strategy is a never–best response, where the additional constraints are linear constraints. Since the problem to verify whether a strategy is a never–best response can be formulated as a linear mathematical programming problem and the additional constraints are linear, the resulting program is linear and therefore solvable with polynomial time.□

Summarily, these results show that finding an SCE extension is (in the worst case) as hard as finding an SE [16] and that verifying an SCE extension is easier than an SE [9].

We characterize the relationships between different SCE extensions. For clarity, we use the following example.

Example 3.8. In the game in Fig. 1, there are two agents, each with two types. Fig. 2.a and Fig.2.b report the equilibria in the space of the agents’ utilities when types are only θ_1.1, θ_2.1: A, B, C, D, and all the points between B and C are USCEs, while A is the unique SPE. Fig. 2.c and Fig. 2.d report the equilibria when types are only θ_1.2, θ_2.1: A, B, C, and all the points between B and C are USCEs, while A and all the points between D and C are SPEs.

While it is known that with two agents USCEs and NEs are the same in terms of expected utility, see [9], the presence of individuals makes HSCEs (both FHSCEs and IHSCEs) and NEs dramatically different. We state the following, whose proof is given as counterexample below.

Proposition 3.9 Types and individuals have a different expressivity.

Example 3.10 Different types can act in different ways only if their utilities are different, instead different individuals can act in different ways even with the same utility leading to new equilibria as shown as follows. In Fig. 2 the light gray polytopes contain all the IHSCEs. In Fig. 2.b and in Fig. 2.d, we report the FHSCEs with different combination of individuals per agent (in this case U₁ and U₂ are the aggregate expected utilities of agent 1 and 2, respectively). With ■ we mark FHSCEs (non–USCE) when agent 1 has two individuals (with ω _λ  = .5) and agent 2 has one individual. With ▴ we mark FHSCEs (non–USCE) when agent 1 has one individual and agent 2 has two individuals (with ω _λ  = .5). When both agents have two individuals (with ω _λ  = .5) new FHSCEs arise marked by ♦.

Thus, the presence of individuals introduces new equilibria and in some case a continuum of equilibria. Now, we derive some interesting properties among the solution concepts that we use below for the equilibrium enumeration problem. We initially provide the following definition.

Definition 3.11. The convex combination of two USCEs (σ₁, σ₂), ( σ 1 ′ , σ 2 ′ ) is defined as ( α · σ 1 + ( 1 - α ) · σ 1 ′ , α · σ 2 + ( 1 - α ) · σ 2 ′ ) with α ∈ [0, 1].

We can show that FHSCEs and IHSCEs are convex combinations of different USCEs. We state the following theorem for the IHSCE concept, the same result can be derived for the FHSCE concept.

Theorem 3.12. Every IHSCE is equivalent to a probability distribution over a set of USCEs, and vice–versa.

Proof. Given an IHSCE (x₁, x₂), we partition the set of terminal sequences q ∈ Q ¯ i such that x _i  (q) >0 by using the following equivalent relation: [ q ] = { q ′ ∈ Q ¯ i | x ˆ q ′ - i = x ˆ q - i }. For each equivalent class, we normalize the probability x _i such that x i * ( q 0 ) = 1 where x i * is the normalized probability and q₀ is the empty sequence. We obtain: x i * ( q ) = x i ( q ) ∑ q ′ ∈ [ q ] x i ( q ′ ) for every q ∈ [q]. Each equivalent class is a USCE because: (a) each q ∈ [q] is best–response given x ˆ q - i (by IHSCE definition) and (b) there exists a unique x ˆ q - i , ∀ q ∈ [ q ] (by partition rule). We define a probability distribution over the set of [q] such that: Pr ([q]) = ∑_q′∈[q]x _i  (q′). Notice that x i ( q ) = x i * ( q ) · Pr ( [ q ] ) for every q ∈ Q ¯ i.□

With infinite populations we can obtain every strategy profile (∑ _k α_1,k · σ_1,k, ∑ _k α_2,k · σ_2,k) with ∑ _k α_i,k = 1 and α_i,k ≥ 0, and where σ_i,k is the strategy of agent i in the k–th USCE. Therefore, once we have all the USCEs, we can derive all the IHSCEs simply as convex combinations of USCEs. In the finite case, the set of possible FHSCEs is limited to a finite set of strategies, that are obtained by constraining the coefficients of the convex combination as follows: α_i,k = ∑_{σ λ =σi,k}ω _λ .

We state the following theorem for the FHSCE concept, whose proof is given as counterexample below.

Theorem 3.13. Given a finite set of individuals, a convex combination of USCEs feasible w.r.t. probabilities ω _λ may be not an FHSCE.

Example 3.14. In Fig. 2.b, some possible convex combinations, e.g., the ones between A and C, do not correspond to any FHSCE. In Fig. 2.d, the unique two convex combinations that correspond to FHSCEs are between A and C and between B and D.

Therefore, the derivation of the FHSCEs cannot be performed on the basis of only the USCEs.

We use the above results for the equilibrium enumeration problem. The enumeration of the USCEs can be performed by enumerating all the basic solutions of the corresponding mathematical program. This can be performed by exhaustively visiting the branch–and–bound tree generated by the MILP solver. The size of the tree is O (2^{|Q₁|+|Q₂|}). The problem is # P and, in the case of degeneracy, the same approach adopted in [1] can be employed here. By the enumeration of the USCEs, we are enumerating all the IHSCEs, given that these can be derived as convex combinations of USCEs. The enumeration of FHSCEs can be accomplished similarly: enumerating all the USCEs, computing all the possible finite (with the given ω) convex combinations, and then verifying whether each convex combination is an FHSCE. Denoting with # USCEs the number of USCEs, this approach has a complexity O (2^{|Q₁|+|Q₂|} + 2^{log₂(#USCEs)·(|Λ₁|+|Λ₂|)}) much faster than enumerating the basic solutions of the mathematical program for FHSCE when log ₂ (# USCEs) is smaller than |Q₁| and |Q₂|, this last problem having complexity O (2^{|Q₁|·|Λ₁|+|Q₂|·|Λ₂|}).