This brief designs a distributed stochastic annealing algorithm for nonconvex cooperative aggregative games, whose players' cost functions not only depend on players' own decision variables but also rely on the sum of players' decision variables. To seek the social optimum of cooperative aggregative games, a distributed stochastic annealing algorithm is proposed, where the local cost functions are nonconvex and the communication topology between players is time-varying. The weak convergence to the social optimum of the algorithm is further analyzed. A numerical example is finally given to illustrate the effectiveness of the proposed algorithm.

Many machine learning problems can be formulated as non-convex multi-player games. Due to non-convexity, it is challenging to obtain the existence condition of the global Nash equilibrium (NE) and design theoretically guaranteed algorithms. This paper studies a class of non-convex multi-player games, where players' payoff functions consist of canonical functions and quadratic operators. We leverage conjugate properties to transform the complementary problem into a variational inequality (VI) problem using a continuous pseudo-gradient mapping. We prove the existence condition of the global NE as the solution to the VI problem satisfies a duality relation. We then design an ordinary differential equation to approach the global NE with an exponential convergence rate. For practical implementation, we derive a discretized algorithm and apply it to two scenarios: multi-player games with generalized monotonicity and multi-player potential games. In the two settings, step sizes are required to be O(1/k) and O(1/√k) to yield the convergence rates of O(1/ k) and O(1/√k), respectively. Extensive experiments on robust neural network training and sensor network localization validate our theory. Our code is available at https://github.com/GuanpuChen/Global-NE.

This paper considers Stackelberg equilibrium (SE) and Nash equilibrium (NE) computation in a class of non-convex network aggregative games with one leader and multiple followers. The cost function of each follower is influenced by its strategy, the leader’s strategy, and its neighbors’ aggregative strategies. Also, the structured non-convex cost function of the leader is the composition of a canonical function and a vector-valued geometrical operator that relies on its strategy and followers’ strategies. In the leader-follower scheme, when the leader has knowledge of the best responses of the followers in a closed form, the SE strategy will be the optimal choice due to its relatively low cost. When the leader does not know the exact expression of followers’ best responses or the leader’s dominance is threatened, NE will be what all players are committed to achieving. The widespread existence of nonconvexity creates a significant challenge for computing the above equilibria in different circumstances. The results in existing convex games are not directly applicable to such a non-convex case, as they get trapped in local equilibria or stationary points rather than global equilibria. Here, we adopt the canonical transformation to reformulate the non-convex games and present the existence condition based on the canonical duality theory. Then two projection gradient algorithms are designed to pursue the SE and the NE, followed by proving the convergence of the algorithms.

We consider solving distributed constrained optimization in this article. To avoid projection operations due to constraints in the scenario with large-scale variable dimensions, we propose distributed projection-free dynamics by employing the Frank-Wolfe method, also known as the conditional gradient. Technically, we find a feasible descent direction by solving an alternative linear suboptimization. To make the approach available over multiagent networks with weight-balanced digraphs, we design dynamics to simultaneously achieve both the consensus of local decision variables and the global gradient tracking of auxiliary variables. Then, we present the rigorous convergence analysis of the continuous-time dynamical systems. Also, we derive its discrete-time scheme with an accordingly proved convergence rate of O(1/k) . Furthermore, to clarify the advantage of our proposed distributed projection-free dynamics, we make detailed discussions and comparisons with both existing distributed projection-based dynamics and other distributed Frank-Wolfe algorithms.

There has been significant recent interest in a class of three-player leader-follower game models in many important cybersecurity scenarios. In such a tri-level hierarchical structure, a defender usually serves as a leader, dominating the decision process by the Stackelberg equilibrium (SE) strategy. However, such a leader-follower scheme may not always work, and the Nash equilibrium (NE) strategy may provide an alternative choice. Thus, we need to reveal the consistency between SE and NE in the three-player model to help the leader evaluate its strategy impact and avoid a choice dilemma. To this end, we first provide a necessary and sufficient condition such that each SE is an NE, which not only provides access to seek a satisfactory SE but also makes a criterion for an obtained SE. Then, we apply the results for case studies with a unique SE or with at least one SE being an NE. Moreover, when the consistency condition falls short, we give an upper bound of the deviation between SE and NE to help the leader tolerably adopt an SE strategy. Finally, we apply our consistency analysis to practical scenarios, including secure wireless transmission and advanced persistent threat defense.

In this article, we aim to design a distributed approximate algorithm for seeking Nash equilibria (NE) of an aggregative game. Due to the local set constraints of each player, projection-based algorithms have been widely employed for solving such problems actually. Since it may be quite hard to get the exact projection in practice, we utilize inscribed polyhedrons to approximate local set constraints, which yields a related approximate game model. We first prove that the NE of the approximate game is the ϵ -NE of the original game and then propose a distributed algorithm to seek the ϵ -NE, where the projection is then of a standard form in quadratic optimization with linear constraints. With the help of the existing developed methods for solving quadratic optimization, we show the convergence of the proposed algorithm and also discuss the computational cost issue related to the approximation. Furthermore, based on the exponential convergence of the algorithm, we estimate the approximation accuracy related to ϵ . In addition, we investigate the computational cost saved by approximation in numerical simulation.

In this paper, we employ a hypergame framework to analyze the single-leader-multiple-followers (SLMF) Stackelberg security game with two typical misinformed situations: misperception and deception. We provide a stability criterion with the help of hyper Nash equilibrium (HNE) to investigate both strategic stability and cognitive stability of equilibria in SLMF games with misinformation. In fact, we find mild stable conditions such that the equilibria with misperception and deception can become HNE. Moreover, we discuss the robustness of the equilibria to reveal whether players have the ability to keep their profits under the influence of some misinformation.