Search

Pareto-based evolutionary multiobjective approaches are methods that use the Pareto dominance concept to guide the search of evolutionary algorithms towards the Pareto frontier of a problem. To address the challenge of providing an entire set of optimal solutions they use specially designed mechanisms for preserving search diversity and maintaining the non-dominated solutions set. The limitation of the Pareto dominance relation in high-dimensional spaces has rendered these methods inefficient for many-objective optimization. In this paper we aim to exploit existing Pareto-based methods to compute the generalized Nash equilibrium for multi-player games by replacing the Pareto dominance relation with an equilibrium generative relation. The generalized Nash equilibrium extends the Nash equilibrium concept by considering constraints over players’ strategies. Numerical experiments indicate that the selected methods can be employed for equilibria computation even for games with up to twenty players.

This paper explores the influence maximization problem for the weighted cascade model by considering an approach based on Shapley value and Extremal Optimization. The Shapley value is a solution concept in cooperative game theory that, given a total value of the game assigns to each player a value as part of it, computed as its marginal contribution to all possible coalitions of players. In the weighted cascade model we consider adding and updating nodes in the initial set during the extremal optimization search based on their Shapley value in an approach already tested for the independent cascade model. Comparisons with other methods by means of numerical experiments show that results reported by this approach are promising, prompting for further research in this direction.

The paper proposes a general game theoretical model, called capacity demand game, for treating simultaneous capacity requests in scarce-resource cognitive radio (CR) environments. The approach is that of non-cooperative games describing CR interactions in terms of radio resource access. Experiments reveal stable states (equilibria) that favour an equitable usage of radio resources to the benefit of all participants. Several equilibria are detected and discussed: Nash (NE), Pareto, joint Nash–Pareto, and Lorenz equilibrium.

The problem of Network Influence Maximization is approached by an Extremal Optimization algorithm called Shapley value Extremal Optimization (SvEO). The influence maximization problem for the independent cascade model is considered as a cooperative game. In this cooperative game players seek to choose seeder nodes to maximize the value of the game computed as the size of the influence set of their cascade model by maximizing their average marginal contribution to all possible player coalitions (i.e. subsets of the seeder set). SvEO is compared with other influence maximization algorithms by means of numerical experiments, with promising results. Possible implications of the use of the Shapley value are discussed using a network constructed from highly cited publication data in the field of computer science.

The Generalized Berge-Zhukovskii equilibrium extends the Berge-Zhukovskii equilibrium problem by introducing constraints over the set of strategy profiles. The new equilibrium is computed in a dynamic environment by using an evolutionary dynamic equilibrium tracking algorithm. Numerical experiments for the generalized Cournot duopoly illustrate the capability of the approach.

A Cournot oligopoly is used as a benchmark for Nash equilibria tracking and detection in a dynamic setting. Several dynamics that induce different trajectories for the equilibria are considered: random, linear, cosine, and spiral. A new Extremal Optimization based method is tested on the proposed dynamic setting.

Berge-Zhukovskii equilibrium is an alternate solution concept to Nash equilibrium that induces cooperation in non-cooperative games. A solution of a game is a Berge-Zhukovskii equilibrium if the payoff of each player cannot increase regardless of what the other players do. The Berge-Zhukovskii equilibrium has been found to be us useful in trust games. We propose a new method, based on evolutionary algorithms, to detect and track the Berge-Zhukovskii equilibrium of a game considering a discrete-time dynamic environment. To test our method we propose a new dynamic multiplayer game model, based on the Voluntary contribution mechanism. Numerical results show the potential of the proposed method.

Game theory models strategic and conflicting situations and offers several solution concepts that are known as game equilibria, among which the Nash equilibrium is probably the most popular one. A less known equilibrium, called the (k,t)-robust equilibrium, has recently been used in the context of distributed computing. The (k,t)-robust equilibrium combines the concepts of k-resiliency and t-immunity: a strategy profile is k-resilient if there is no coalition of k players that can benefit from improving their payoffs by collective deviation, and it is t-immune if any action of any t players does not decrease the payoffs of the others. A strategy profile is (k,t)-robust if it is both k-resilient and t-immune. In this paper an evolutionary approach of approximating (k,t)-robust equilibria is proposed. Numerical experiments are performed on a game that models node behavior in a distributed system.

The community structure detection problem in weighted networks is tackled with a new approach based on game theory and extremal optimization, called Weighted Nash Extremal Optimization. This method approximates the Nash equilibria of a game in which nodes, as players, chose their community by maximizing their payoffs. After performing numerical experiments on synthetic networks, the new method is used to analyze functional connectivity networks of the brain in order to reveal possible connections between different brain regions. Results show that the proposed approach may be used to find biomedically relevant knowledge about brain functionality.

The Berge-Zhukovskii optimal Nash equilibrium combines the properties of the popular Nash equilibrium with the ones of the less known Berge-Zhukovskii by proposing yet another Nash equilibrium refinement. Moreover, a computational approach for the detection of these newly proposed equilibria is presented with examples for two auction games.

The problem of equilibria detection of a discrete-time Generalized Cournot Dynamic Oligopoly is approached by using a Differential Evolution and a Particle Swarm Optimization algorithm adapted to compute and track the set of generalized Nash equilibria in a dynamic setting. Both challenges of this problem, i.e. to correctly compute the entire set of generalized Nash equilibria of the constrained (generalized) game, and also to cope with the dynamic character of the landscape, are dealt with by using a simple adaptive mechanism. Numerical experiments for settings up to 60 players are performed to illustrate the efficiency of the approach.

Discrete-time dynamic games capture changes within game parameters (payoffs), representing thus a more realistic real-world decision model. A new approach to equilibria detection and tracking in a dynamic game setting, called Dynamic Equilibrium Tracking Differential Evolution, is proposed. A discrete-time dynamic asymmetric Cournot oligopoly is introduced and used to evaluate the proposed method by means of numerical experiments for instances up to 70 players. Results indicate the effectiveness and the potential of the proposed method.

In a mixed strategy equilibrium players randomize between their actions according to a very specific probability distribution, even though with regard to the game payoff, they are indifferent between their actions. Currently, there is no compelling model explaining why and how agents may randomize their decisions is such a way, in real world scenarios. In this paper we experiment with a model for bimatrix games, where the goal of the players is to find robust strategies for which the uncertainty in the outcome of the opponent is reduced as much as possible. We show that in an evolutionary setting, the proposed model converges to mixed strategy profiles, if these exist. The result suggest that only local knowledge of the game is sufficient to attain the adaptive convergence.

The aim of this paper is to asses simultaneous spectrum access situations that may occur in Cognitive Radio (CR) environments. The approach is that of one-shot, non-cooperative games describing CR interactions. Open spectrum access scenarios are modelled based on continuous and discrete reformulations of the Cournot game theoretical model. CR interaction situations are described by Nash and Pareto equilibria. Also, the heterogeneity of players is captured by the new concept of joint Nash-Pareto equilibrium, allowing CRs to be biased toward different types of equilibrium. Numerical simulations reveal equilibrium situations that may be reached in simultaneous access scenarios of two and three users.

Nash equilibrium in many cases is not the best choice for human players. In case of trust games the Nash equilibrium is often mutual defection which is the worst possible outcome for all players. The Berge-Zhukovskii equilibrium models a more cooperative behavior, so in case of trust games, when players gain by cooperating, it is usually a better choice than Nash equilibrium. Real life results show that players rarely follow the theoretical predictions. Our aim is to find new equilibria types that offer a more realistic modeling of human players. The fuzzy Nash---Berge-Zhukovskii equilibrium is proposed which is a fuzzy combination of the Nash and Berge-Zhukovskii equilibrium. Several continuous trust games are investigated. Numerical results indicate that fuzzy Nash---Berge-Zhukovskii equilibrium is suitable to model real-life situations.

Nash equilibrium is an important solving concept in Game Theory. Playing in Nash sense means that no player can deviate from the equilibrium strategy in order to increase her/his payoff. Some games can have several Nash equilibria. Strong Berge and strong Berge Pareto equilibria are important refinements of the Nash equilibrium. An evolutionary technique based on non-domination is proposed in order to detect the strong Berge and strong Berge Pareto equilibria. Some numerical experiments are presented in order to illustrate the proposed method.

Nash equilibrium is an important solving concept in Game Theory. Playing in Nash sense means that no player (agent) wants to deviate from the equilibrium strategy in order to increase the payoff. Some games can have more Nash equilibria. Several refinements have been developed. Strong Berge Pareto equilibrium is an important refinement of the Nash equilibrium. An evolutionary technique based on non-domination is proposed in order to detect the strong Berge Pareto equilibria. Some numerical experiments are presented in order to illustrate the proposed method.

An evolutionary procedure based on nondomination with respect to the generative relation is proposed for detecting different new equilibria types. The notions of joint Pareto-Aumann, Aumann-Pareto, Nash-Aumann and Aumann-Nash equilibrium are introduced. These combinations (representing new solution concepts) may allow an approximation of how people play in real life situations. Some numerical experiments show the importance of this new equilibria types.

The problem of equilibria detection in many-player games is computationally untractable by standard techniques. Generative relations represent an useful tool for equilibria characterization and evolutionary equilibria detection. The generative relation for k-Berge-Zhukovskii equilibrium is introduced. An evolutionary technique based on differential evolution capable to cope with hundred players is proposed. Experimental results performed on a multi-player version of Prisoner’s Dilemma indicate the effectiveness of the approach.

Two important network system problems, the job scheduling, and the bin packing problem are presented from a game theoretical perspective. Solution concepts are related to Nash and Aumann equilibria. The concept of Aumann equilibrium is viewed from a different perspective. A generative relation of the Aumann equilibrium is considered. A generative relation is used for the evolutionary detection of the equilibrium. The numerical experiments demonstrate the effectiveness of the proposed method in addressing job scheduling and bin packing problems.