Source-linked AI summary
Finding Optimal Strategies in a Multi-Period Multi-Leader-Follower Stackelberg Game Using an Evolutionary Algorithm
Ankur Sinha, Pekka Malo, Anton Frantsev, Kalyanmoy Deb
TL;DR
The paper studies a multi-period multi-leader-follower Stackelberg problem whose nonlinearities and discrete production decisions challenge conventional bilevel methods. It uses a computationally intensive nested evolutionary framework to solve the model and test-suite problems. The approach handles the stated difficult bilevel problems, while efficiency and scalability remain future-work concerns.
Problem
Bilevel methods face difficult multi-period Stackelberg models with nonlinear cost and demand functions and discrete production variables.
Method
A computationally intensive nested evolutionary algorithm solves the multi-period multi-leader-follower model by optimizing both bilevel levels.
Results
The method successfully handles difficult bilevel problems and solves a concrete model with 2 leaders, 5 followers, and 5 time periods.
Takeaways & Limitations
The framework can solve the stated multi-period multi-leader-follower problem despite assumptions that conventional bilevel methodologies would not overcome.
Takeaways & Limitations
The computationally intensive method needs improved efficiency and faster convergence for more complex problems with more variables.
Abstract
from arXiv · showhide
Stackelberg games are a classic example of bilevel optimization problems, which are often encountered in game theory and economics. These are complex problems with a hierarchical structure, where one optimization task is nested within the other. Despite a number of studies on handling bilevel optimization problems, these problems still remain a challenging territory, and existing methodologies are able to handle only simple problems with few variables under assumptions of continuity and differentiability. In this paper, we consider a special case of a multi-period multi-leader-follower Stackelberg competition model with non-linear cost and demand functions and discrete production variables. The model has potential applications, for instance in aircraft manufacturing industry, which is an oligopoly where a few giant firms enjoy a tremendous commitment power over the other smaller players. We solve cases with different number of leaders and followers, and show how the entrance or exit of a player affects the profits of the other players. In the presence of various model complexities, we use a computationally intensive nested evolutionary strategy to find an optimal solution for the model. The strategy is evaluated on a test-suite of bilevel problems, and it has been shown that the method is successful in handling difficult bilevel problems.
1. Introduction
The paper addresses a difficult bilevel Stackelberg problem by modeling multi-period markets with multiple leaders and followers, nonlinearities, and discrete production. It proposes a nested evolutionary approach because existing approximate methods rely on simplifying assumptions and struggle with such complexity.
- Motivation: Bilevel optimization nests a lower-level optimization inside an upper-level problem, so upper-level feasibility depends on lower-level optimality.This nested requirement makes bilevel problems difficult to solve.
- Contribution: The paper models multiple leaders and followers interacting across multiple periods in an oligopolistic Stackelberg market.The formulation incorporates investment and marketing effects while keeping production discrete and investment and marketing continuous.
- Model complexity: Nonlinear demand and cost functions, discrete production, and cross-period investment and marketing interactions create substantial model complexity.Investment and marketing expenditures are also constrained by budgets for leaders and followers.
- Research gap: Prior approximate bilevel methods commonly use simplifying assumptions and are often unsuitable for problems with higher levels of complexity.The paper identifies nonlinearity and discreteness as inherent sources of difficulty in its oligopolistic model.
- Approach: The paper evaluates a nested bilevel evolutionary algorithm after formulating the market model and its aircraft-manufacturing application.The paper structure includes formulation, algorithm description, evaluation, and model results.
2. Generalized Stackelberg Competition Model
The generalized model combines simultaneous noncooperative competition within leader and follower groups with Stackelberg competition between those groups. Strategies are sequences of decisions over the game horizon, and optimal strategies are obtained by optimizing firms’ objectives under their constraints.
- Market structure: Stackelberg competition is especially suitable when firms have unequal market power, unlike Bertrand and Cournot settings that assume more symmetric competitors.The model targets oligopolies in which some firms possess greater market power than others.
- Strategies: A strategy is a sequence of decisions made by a player throughout the duration of the game.Leader and follower strategies are represented separately across their available alternatives.
- Optimization: The model obtains leaders’ and followers’ optimal strategies by optimizing the competing firms’ objectives.Leader and follower objective functions are constrained by their respective feasible strategies and constraints.
- Interaction structure: Each leader competes as a Stackelberg leader against followers but as a Cournot firm against other leaders.Followers similarly act as Stackelberg followers toward leaders and Cournot firms toward one another.
- Model extension: The concrete model adds investment and marketing variables, expenditure constraints, and discrete production variables for both leaders and followers.These additions extend the generalized competition framework toward a more realistic market model.
3. Multi-Leader-Follower Stackelberg Model
The paper instantiates the generalized game for multi-leader-follower markets with multiple periods, discrete production, and financially constrained investment and marketing. Aircraft manufacturing illustrates the intended setting, where a few large firms coexist with smaller followers.
- Market setting: A multi-leader-follower game extends the classic one-leader, one-follower, one-period Stackelberg setting to markets with multiple firms on both sides.The model assumes leaders and followers compete in Cournot fashion within their respective groups.
- Application: Aircraft manufacturing is a motivating example because high entry costs produce a small, stable market dominated by Boeing and Airbus alongside smaller suppliers.Discrete and comparatively small production quantities can make one additional unit materially affect profits.
- Model features: The model includes multiple time periods whose decisions are linked through investment and marketing expenditures.Production is discrete for both leaders and followers, while investment and marketing decisions are continuous.
- Decision variables: A leader’s or follower’s period decision consists of production, investment, and marketing choices.Production variables are discrete, whereas monetary investment and marketing expenditures are continuous.
- Constraints: Investment and marketing expenditures are limited by revenue-related constraints, and both are zero in the first period because no prior revenue exists.The formulation also assumes firms can satisfy the entire market demand for their products.
- Profit formulation: The model’s total objectives aggregate period-specific profits, with single-period profit subtracting production, investment, and marketing expenses from revenue.This structure applies to both leaders and followers.
4. Solution Methodology
The solution method is a nested evolutionary algorithm that optimizes upper- and lower-level decisions, reusing nearby lower-level solutions and applying tailored operators for continuous and discrete variables. Constraint handling, variance-based termination, and local search support the optimization process.
- Algorithm: The nested algorithm uses steady-state single-objective real-coded genetic algorithms at both levels, with Parent Centric Crossover as a core operator.The lower-level problem is solved for each upper-level decision vector, using the nearest known upper-level solution to initialize lower-level information.
- Upper-level procedure: Initialization evaluates lower-level optima for randomly generated upper-level populations and assigns fitness using upper-level objectives and constraints.This establishes feasible or ranked candidates before upper-level evolution begins.
- Upper-level procedure: Upper-level evolution selects parents, generates offspring with PCX and mutation operators, and supports different operators for real and discrete variables.Real variables use polynomial mutation, while discrete variables use binary crossover and mutation.
- Lower-level procedure: For each offspring, the lower-level procedure copies variables from the closest upper-level member, augments them with random candidates, and performs lower-level optimization.The resulting lower-level optima are combined with offspring upper-level variables for evaluation.
- Population management: Population updates retain the best candidates from pooled parents and offspring, followed by termination checks and further generations when required.The lower level uses a similar evolutionary procedure.
- Constraint handling: Constraint handling prioritizes lower violation, feasibility over infeasibility, and higher objective value among feasible candidates.The algorithm uses this rule at both optimization levels.
- Termination: The variance-based termination criterion stops optimization when η falls below η_stop, set to 10^-5 at both levels.A mutation-based local search is then used to check convergence.
5. Algorithm Evaluation
The nested bilevel evolutionary algorithm is evaluated on SMD test problems across variable sizes, function-evaluation requirements, and accuracy. Scalability runs converge successfully with high accuracy, while the multi-leader-follower problem requires many lower-level evaluations.
- Test-suite evaluation: The evaluation uses six SMD test problems with 10- and 20-variable instances, reporting upper- and lower-level function evaluations and accuracy.Table 1 covers 10-variable instances, while additional results address 20-variable instances.
- Scalability analysis: 10, 20, 30 and 40 variable instances of SMD1 and SMD2 were each solved in 31 runs for the scalability analysis.The required function evaluations are presented for both lower and upper levels.
- Scalability analysis: The algorithm converges successfully for each scalability run with high accuracy.Accuracy is calculated as the Euclidean distance between the obtained and actual optimal solutions.
6. Results for Multi-Leader-Follower Stackelberg Model
The paper models a multi-period multi-leader-follower Stackelberg problem with symmetric firms, nonlinear economic functions, cumulative investments and marketing, and solves it using a nested bilevel evolutionary algorithm. Results show convergence on test problems, first-mover advantages for leaders, and lower individual profits but higher total production as players enter.
- Model formulation: The model uses identical cost and inverse demand functions within leader and follower groups, while cumulative investment and marketing link decisions across time periods.These cross-period effects prevent solving each period independently because prior investments and marketing must be included.
- Model formulation: Demand-supply and symmetry simplifications reduce the individual-firm model to 13 variables, with eight constraints at each optimization level.Demand variables are eliminated because demand equals supply at the optimum, and first-period investment and marketing are fixed at zero.
- Algorithm and computational results: The nested evolutionary algorithm solves the lower-level optimization for every newly generated upper-level member, producing a high number of lower-level function evaluations.The reported computational expense is associated with repeatedly solving the follower problem inside the upper-level search.
- Results for two leaders and five followers: The best solutions from 31 runs show leaders producing more and earning higher profits than followers, consistent with a first-mover advantage, while investment and marketing constraints are active at the optima.Period profits are reported before deducting investment and marketing expenditures.
- Varying the number of leaders and followers: Adding a player at either level reduces profits for all players, with the largest reduction affecting the incumbents at the entrant’s level; individual production also falls with each entrant.Leaders and followers are symmetric within their respective groups, so players at the same level earn identical profits.
- Varying the number of leaders and followers: Increasing the number of players raises total production while reducing prices and aggregate player profits, creating a consumer advantage through greater market competition.The paper attributes the result to additional players increasing production enough to lower prices and overall profits.
7. Convergence Analysis
The nested bilevel evolutionary algorithm is evaluated on a simple two-period, single-leader single-follower problem, with grid search used to verify its solution and convergence examined over generations.
- Experimental setup: The convergence analysis uses a two-period single-leader single-follower problem so solutions can be represented graphically and checked with grid search.The problem contains two production variables for each player.
- Verification: A grid search around the evolutionary solution verifies the upper- and lower-level decisions and produces the contours shown for the production variables.Lower-level optimal solutions are computed for each upper-level decision vector.
- Problem structure: The leader’s objective surface is uneven because the lower-level problem has discrete decisions.The surface is evaluated with follower decision vectors set to their optima.
- Convergence behavior: The leader’s objective value continuously improves over generations, whereas the follower’s objective value need not improve monotonically.Figure 18 tracks both objective values for the elite individual.
8. Conclusions and Future Work
The paper formulates and solves a multi-period multi-leader-follower Stackelberg model with a nested bilevel evolutionary algorithm, including a concrete multi-player instance and analyses that vary player counts. The authors identify efficiency, convergence speed, realism, and multi-objective extensions as future directions.
- Contributions: The paper formulates a multi-period multi-leader-follower Stackelberg model with N leaders, M followers, and T time periods.The formulation is intended for oligopolistic markets.
- Contributions: A computationally intensive nested bilevel evolutionary framework solves a concrete instance with 2 leaders, 5 followers, and 5 time periods.The approach is described as easily parallelizable.
- Results: The method handles model assumptions that conventional bilevel methodologies would not overcome, and the analysis varies the numbers of leaders and followers.The paper also presents contour and convergence analyses of the model and algorithm.
- Future work: Future work targets greater efficiency for problems with more variables, faster convergence to optimal solutions, more realistic market formulations, and multi-objective extensions.These directions are presented as areas for further development.