A hierarchical multi-modal hybrid Nash-Stackelberg GA for a leader with multiple followers game

A hierarchical multi-modal hybrid Nash-Stackelberg GA for a leader with multiple followers game

Egidio D'Amato^?, Elia Daniele ^†, Lina Mallozzi ^‡, Giovanni Petrone^† and Simone Tancredi^†

? Dipartimento di Scienze Applicate, Università degli Studi di Napoli Parthenope"

Centro Direzionale di Napoli, Isola C 4 - 80143 Napoli (Italy) [email protected]

† Dipartimento di Ingegneria Aerospaziale, Università degli Studi di Napoli Federico II"

Via Claudio 21 - 80125 Napoli (Italy) [email protected], [email protected], [email protected]

‡ Dipartimento di Matematica e Applicazioni, Università degli Studi di Napoli Federico II"

Via Claudio, 21 - 80125 Napoli (Italy) [email protected]

Abstract. In this paper we propose a computational methodology to reach a Stackelberg solution for a hierarchical n+1-person game via genetic algorithm evolution process. There is only one player (the leader) making a decision that the rest of players (followers) know before they could make their own choices, so there is a two- level game between the leader and the followers. The idea of the Stackelberg-GA is to bring together genetic algorithms and Stackelberg strategy in order to process a genetic algorithm to build the Stackelberg strategy. The follower players make their decisions simultaneously at each step of the evolutionary process, playing a so called Nash game between themselves. The use of a multi-modal genetic algorithm allows to

nd multiple Stackelberg strategies at the upper level. In this model the uniqueness of the Nash equilibrium at the lower level problem has been supposed. The algorithm convergence is illustrated by means of several test cases.

Key Words: Genetic algorithm, Hierarchical game, Nash equilibrium, Stackelberg strategy.

1 Introduction

In this paper we consider a two-stage n+1 player game: in the rst stage one of the players, called the leader, chooses an optimal strategy knowing that, at the second stage, the other players react by playing a non-cooperative game which admits one Nash equilibrium, while a multiple Stackelberg solution may be managed at upper level. A step by step procedure for optimization based on genetic algorithms (GA) has been implemented starting from a simple Nash equilibrium, through a Stackelberg solution, up to a hierarchical Nash-Stackelberg game, validated by numerous test cases, even in comparison with other researchers proposals ([11], [10]).

A GA is presented for a Nash equilibrium problem in Section 2 and for a Nash-Stackelberg problem in Section 3, together with dierent test cases. Then some applications of the real life are indicated in the concluding Section 4.

1.1 The Nash-Stackelberg model

We deal with a n+1 player game, where one player is the leader and the rest of them are followers in a two-level Stackelberg game. Any player is assumed to minimize his own payo function called cost function. The followers act in a noncooperative way and play a Nash equilibrium game. The leader takes into account the followers Nash equilibrium, that we assume to be unique, and solve a Nash equilibrium problem in a backward induction scheme. Let X, Y1, ..., Yn be compact subsets of metric spaces that are the leader's and the followers' strategy sets, respectively. Let l, f1, ..., fn

be real valued functions dened on X × Y1× .... × Yⁿ representing the leader's and the followers' cost functions.

For each x ∈ X, that is the leader's decisions, the followers solve the following lower level Nash equilibrium problem N (x)























find (¯y1, ..., ¯yn)∈ Y¹× .... × Yⁿ such that f1(x, ¯y1, ...., ¯yn) = inf

y1∈Y1

f1(x, y1, ¯y2, ..., ¯yn) ....

fn(x, ¯y1, ...., ¯yn) = inf

yn∈Yn

fn(x, ¯y1, ..., ¯yn−1, yn) .

Let (˜y1(x), ...., ˜yn(x))∈ Y¹× .... × Yⁿ be the unique solution of the problem N (x). The leader has to compute a solution of the following upper level problem:







find ¯x∈ X such that l(¯x, ˜y1(¯x), ...., ˜yn(¯x)) = inf

x∈Xl(x, ˜y1(x), ...., ˜yn(x)).

Any solution ¯x ∈ X to this problem is called a Nash-Stackelberg strategy, while any vector (¯x, ˜y1(¯x), ...., ˜yn(¯x))∈ X × Y¹× .... × Yⁿ is called a Nash-Stackelberg equilibrium.

This model has been intensively studied and used in dierent applicative contexts, as in [4], [5], [6], [9].

1.2 Surviving of the ttest and GA

Genetic Algorithms (or GAs) are adaptive heuristic search algoritms based on darwinian natural evolution processes. In analogy to living organisms in nature, individuals of a population can be managed by computers as a digital - binary or oating point - DNA with the diversity associated to design variables optimization problem ([1]).

A genetic algorithm consists of a nite population of individuals of assigned size, each of them usually encoded as a string of bits named genotype, an adaptive function, called tness, which provides a measure of the individual to adapt to the environment, that is an estimate of the goodness of the solution and an indication on the individuals most likely to reproduce, semi- random genetic operators such as selection, crossover and mutation that operate on the genotype expression of individuals, changing their associated tness.

Because of the large dimension of global optimization problems and access to low cost dis- tributed parallel environments - such as clusters of PCs - it would be very useful replacing a global optimization by sharing it in local sub-optimizations by using Games Theory tools.

1.3 Multi-Modal Optimization

In this paper a common procedure of GAs has been intruduced in the algorithm to compute a Nash-Stackelberg strategy in line with [2]. Our approach considers also the case of multiple Nash- Stackelberg strategies for the leader, while for follower's choice the hypothesis of uniqueness still holds ([2], [6], [9]).

The multi-modal optimization is a technique used when is needed the research of all relative maxima or minima of an objective function. For such analysis a GA is easily implementable, since it is possible to introduce a so-called sharing function", i.e. a penalty function that grows as well as increases the density of points close to relative maximum or minimum for the objective function.

For each individual of the population we compute a relative distance based e.g. on chromosome s = x, y for a simple case of two design variables

di,j= v u u t

r

X

k=1

(si,k− s^j,k)², ∀i, j = 1, . . . , n

where r is the design variables number (or genes number, at least one for each player as written for s above), n the population size and di,j the distance between individual i and j. The sharing function" is dened as follows

pi,j= 1 + log( di,j

dmin

),

(pi,j≥ 1 ⇒ p = 1 pi,j≤ 0.01 ⇒ p = 0.01

where dmin is the minimum distance allowed between dierent individual in the same population and is based usually on domain extent. At this point a multi-modal tness function for each individual i in population can be evaluated from previous tness function as

f itness^mm_i =f itnessi·

n

Y

j=1

pi,j

We will use this function to approach the multi-modal case and compute multiple Nash- Stackelberg strategies.

2 Nash Genetic Algorithm

2.1 Algorithm description

We present here the algorithm for a two player Nash equilibrium game. Let Y1, Y2 be compact subsets of metric spaces that are the players' strategy sets. Let f1, f2be two real valued functions dened on Y1× Y²representing the players' cost functions. A Nash equilibrium problem is solved by the two players.

Let s = u, v be the string (or individual, or chromosome) representing the potential solution for a dual objective optimization problem, at least in the simplest case. Then u denotes the subset of variables handled by player 1, belonging to a metric space denoted by Y1, and optimized under an objective function always denoted by 1. Similarly v indicates the subset of variables handled by player 2, belonging to metric space called Y2, and optimized along another objective function denoted by 2. Thus, as advocated by Nash theory ([7]), player 1 optimizes the chromosome with respect to the rst objective function by modifying u while v is xed by player 2. Symmetrically,

Initialize populations

Beginning of era k

Binary Tournament

P1 Crossover Mutation Recasting

P2 Crossover Mutation Recasting

P1 Co- Evolution

ui, v^k₁ ...,...

un, v^k₁

P2 Co- Evolution

u^k₁, vi

...,...

u^k₁, vn

Iteration

P1 Evaluation u^k+1_i , v^k₁

...,...

u^k+1n , v^k1

P2 Evaluation u^k₁, v^k+1_i

...,...

u^k1, v^k+1n

Generation limit

or Tolerance

limit reached?

y₁^N, y^N₂ yes

no increment k

1

Figure 1: Nash-GAs algorithm structure

player 2 optimizes the chromosome with respect to the second criterion by modifying v , while uis xed by player 1. The next step consists of creating two dierent populations, one for each player. Player 1's optimization task is performed by population 1 and vice versa. Let u^k−1 be the best value found by player 1 at era k − 1 and v^k−1 be the best value found by player 2 at era k − 1 . At era k, player 1 optimizes u^k using v^k−1 in order to evaluate the chromosome (now s = u^k, v^k−1). At the same time player 2 optimizes v^k using u^k−1 to evaluate his chromosome (in this case s = u^k−l, v^k). This kind of classication is made on the basis of the evaluation of a tness function, typical of GAs, that counts the results of matches between each individual of population 1 with all individuals of population 2, scoring 1 or -1 for a win or loss, and 0 for a draw.

Parameter Value

Population size [-] 50

Crossover fraction [-] 0.90

Mutation fraction [-] 0.10

Parent sorting Tournament between couple

Mating Pool [%] 50

Elitism no

Crossover mode Simulated Binary Crossover (SBX)

Mutation mode Polynomial

dmin for multi-modal 0.2

Table 1: GA details

In this way a simple sorting criteria could be established. For equal tness value individual are sorted on objective function 1 for population 1 (player 1) and on objective function 2 for player 2. At the end of k − th era optimization procedure player 1 communicates his own best value u^k to player 2 who will use it at era k + 1 to generate its entire chromosome with a unique value for its rst part, i.e. the one depending on player 1, while on the second part it will be used a common GAs crossover and mutation procedure. Conversely, player 2 communicates its own best value v^k to player 1 who will use it at era k + 1, generating a population with a unique value for the second part of chromosome, i.e. the one depending on player 2. A Nash equilibrium is reached when neither player 1 nor player 2 can further improve their objective function, or a generation number limit is reached. This kind of structure for the algorithm is similar to those used by other researchers, with a major emphasis on tness function consistency ([11]).

2.2 Test case

In this test case and also in all the subsequent ones the characteristics of GAs algorithm could be summarized in table 1.

For the algorithm validation we consider the following example presented in [11]: the strategy sets are Y1=Y2= [−5, 5] and

f1(y1, y2) = (y1− 1)²+ (y1− y²)²

f2(y1, y2) = (y2− 3)²+ (y1− y²)² for which the analytical solution is

y1N = 5

3, y2N =7 3

Initialize Leader population

Beginning of L era kL

∀ L individual Follower Best Reply

L Tournament

CrossoverL Mutation Recasting

∀ L individual Follower Best Reply

L Evaluation

Generation limit

or Tolerance

limit reached?

L iteration on kL

x^S, y^S₁, y^S₂ yes no

iteration on kL

1

Figure 2: Stackelberg-GAs algorithm structure

By using the proposed algorithm a very closed results as been reached:

yˆ₁^N = 1.6665, ˆy^N₂ = 2.3332

3 Hierarchical Nash-Stackelberg Genetic Algorithm

3.1 Stackelberg Genetic Algorithm

Here the algorithm is presented for a two player leader-follower game or Stackelberg game. Let X, Y be compact subsets of metric spaces that are the players' strategy sets. Let l, f be two real valued functions dened on X × Y representing the players' cost functions. For any x ∈ X leader's

∀ L individual Beginning of F era kF

Initialize F population

F Tournament

CrossoverF Mutation Recasting

F Evaluation u^k_i^L, v^k_i^F

...,...

u^ki^L, v^kn^F

Generation limit Toleranceor

limit reached?

F Iteration

Follower Best Reply

no iteration on kF

yes

1

Figure 3: Stackelberg-GAs algorithm structure - follower detail

strategy, the follower solves the problem







find ¯y∈ Y such that f (x, ¯y) = inf

x∈Vf (x, y) .

If there is a unique solution to this problem, say ˜y(x) for any x ∈ X, the leader's problem is







find ¯x∈ X such that l(¯x, ˜y(¯x)) = inf

x∈Xl(x, ˜y(x)).

Any ¯x ∈ X solution of the leader's problem is called a Stackelberg strategy; any pair (¯x, ˜y(¯x)) ∈ X× Y is called Stackelberg equilibrium.

The initial population is provided with a random seeding in the subset of a metric space, X, i.e. that of the leader. For each individual (or chromosome) of the leader population, say ui, a random population for the follower player is generated, i.e. providing vi. At this step a typical best reply search for the follower player is made until is reached a limit in generation number or an exit criterium in case of same tness function value for the rst two best individual in population (i.e.

follower player). The result of this rst step is to determine the follower player best reply, that is

ready to be passed to the leader player in order to evaluate his own best strategy by sorting the population under objective function criterium, and by generating a mating pool in which normal genetic evolutionary strategy has to be performed. Now a second step begins. After a common crossover and mutation operation on the leader population, the part of chromosome depending on the follower player is determined in the same way described above (reminding the previous syntax for a chromosome we could say that in this case the individual is made of a string s = u, v). This is the kernel procedure of the algorithm that is repeated until a generation limit for leader player population is reached or an exit criterium is met, similarly for the follower player.

3.2 Test case

For the algorithm validation a test case is considered: the strategy sets are X = Y = [0, 1] and

l(x, y) = x²− y²− y

f (x, y) = xy + (y− x)² for which ˜y(x) = ^x₂ and the analytical solution is

x^S = 1

3, y^S= 1 6 while the numerical solution is

xˆ^S = 0.3315, ˆy^S= 0.1672

3.3 Hierarchical algorithm description

The initial population for the players is provided with a random seeding in X, the leader's strategy space. For each individual (or chromosome) of the leader population, say ui, a random population for each of the follower players is generated, i.e. providing v1,i and v2,i. The only dierence from the simple Stackelberg one-leader/one-follower is that now a typical Nash game is played between follower players until they reach a limit in generation number or an exit criterium. An approach similar to that described before for simple Stackelberg is used also in this case, by considering the algorithm described in Subsection 2.1 for the followers problem and the one described in Subsection 3.1 for the two-level problem.

Initialize Leader population

Beginning of L era kL

∀ L individual v^N1, v2^N for F1, F2

L Tournament

CrossoverL Mutation Recasting

∀ L individual v^N1, v2^N for F1, F2

L Evaluation

Generation limit

or Tolerance

limit reached?

L iteration on kL

x^{N S}, y^{N S}₁ , y^{N S}₂ yes no

iteration on kL

1

Figure 4: Hierarchical Nash-Stackelberg-GAs algorithm structure

3.4 Test case

For the algorithm validation a test case with a one leader two followers Stackelberg game: the strategy sets are X = Y1=Y2= [0, 1]and

l(x, y1, y2) =y2(x− y¹−1 2)² f1(x, y1, y2) = (y2− y¹)²+ (2y1− x)² f2(x, y1, y2) = (y1− y²)²+(2y2− x)²

2

Figure 5: Objective functions for hierarchical Nash-Stackelberg-GAs test case (1,¹₂,¹₂)

Figure 6: Objective functions for hierarchical Nash-Stackelberg-GAs test case (0, 0, 0)

Figure 7: Design variables for hierarchical Nash-Stackelberg-GAs test case (1,¹₂,¹₂)

Figure 8: Design variables for hierarchical Nash-Stackelberg-GAs test case (0, 0, 0)

for which ˜y1(x) = ˜y2(x) = ^x₂ and the analytical solutions are

x^{N S} = 1, y^{N S}₁ =1

2, y^{N S}₂ =1 2 x^{N S}_∗ = 0, y^{N S}_1∗ = 0, y^{N S}_2∗ = 0 while the numerical procedure has lead us to

xˆ^{N S}= 1.000, ˆy^{N S}₁ = 0.5000, ˆy^{N S}₂ = 0.4998

ˆx^{N S}_∗ = 0, ˆy^{N S}_1∗ = 0, ˆy^{N S}_2∗ = 2.243∗ 10⁻¹⁸

The history of objective functions and design variables are shown in gures 5, 6, 7, 8.

4 Final remarks

4.1 Applications to real life problems

Some of the major applications of the methodology and computational algorithm developed here could be very useful in many engineering problems, like optimization tool alternative to classical gradient or GAs methods (see also [3], [8], [11]). In particular the hierarchical Nash-Stackelberg model would be very attractive for real engineering problems like the optimization of the position of a multi element airfoil (or wing) subjected to equally important target for fore and aft movable surface (like slats and aps). This kind of methodology would skip the traditional troubles faced in multi-objective optimization problem where a scalarization approach is needed to weight every request (objective function) to form a new scalar function to optimize. Among the others, it would be also very useful in a classic aircraft preliminary design where some specications appear to be dominant (leader) respect to others (followers) in determine aircraft shape and dimensions.

Applications in other contexts must be mentioned too: for example, the hierarchical Nash- Stackelberg model has been used for oligopolies as in [9] and in [5], in Transportation problems as in [6].

4.2 Conclusions and future works

All the procedure implemented in the algorithm presented in this paper has given very reliable results, also compared with studies of previous literature ([11]). An extension to multiple n leaders seems to be a great challenge and need further develops and tests, even from a mathematical point of view. When a priori the uniqueness of a Nash equilibrium for the lower level problem cannot

be established, a more robust strategy should be implemented. In this case inside the algorithm a penalty function must be applied on a certain chromosome (or individual) when is reached an equilibrium in order to exclude this last one from the subsequent eorts of catching the others possible Nash equilibria, forcing the search pattern to explore other regions by means of increasing population size and mutation fraction. All these aspects will be investigated in a future paper.

References

[1] Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T. (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II, IEEE Transaction on Evolutionary Computation, 6(2), pp. 181-197

[2] Liu, B. (1998) Stackelberg-Nash equilibrium for multilevel programming with multiple followers using genetic algorithms, Computers Math. Applic., vol. 36, no. 7, pp. 79-89.

[3] Liu, W. and Chawla, S. (2009) A game theoretical model for adversarial learning, 2009 IEEE International Conference on Data Mining Workshops, pp. 25-30.

[4] Luo, Z.-Q., Pang, J.-S., Ralph, D. (1996) Mathematical programs with equilibrium constraints, Cam- bridge University Press, Cambridge.

[5] Mallozzi, L. and Morgan, J. (2005) On equilibria for oligopolistic markets with leadership and demand curve having possible gaps and discontinuities, Journal of Optimization Theory and Applications vol.

125, n.2, pp. 393-407.

[6] Marcotte, P. and Blain, M. (1991) A Stackelberg-Nash model for the design of deregulated transit system, Dynamic Games in Economic Analysis, Ed. by R.H. Hamalainen and H.K. Ethamo, Lecture Notes in Control and Information Sciences, Springer Verlag, Berlin, vol. 157, pp. 21-28.

[7] Nash, J. (1951) Non-cooperative games, Annals of Mathematics vol. 54, pp. 286-295.

[8] Periaux, J., Chen, H.Q., Mantel, B., Sefrioui, M. and Sui, H.T. (2001) Combining game theory and genetic algorithms with application to DDM-nozzle optimization problems, Finite Elements in Analysis and Design vol. 37, pp. 417-429.

[9] Sheraly, H.D., Soyster, A.L. and Murphy, F.H. (1983) Stackelberg-Nash-Cournot Equilibria: charac- terizations and computations, Operation Research vol. 31, pp. 253-276.

[10] Vallée, T. and Ba³ar, T. (2001) O-Line computation of Stackelberg solutions with the genetic algo- rithm Computational Economics, vol. 13, pp. 201-209.

[11] Wang, J. F. and Periaux, J. (2001) Multi-Point optimization using GAS and Nash/Stackelberg games for high lift multi-airfoil design in aerodynamics, in Proceedings of the 2001 Congress on Evolutionary Computation CEC2001 (May 2001), pp. 552-559.