{'fraction_non_alphanumeric': 0.06020066889632107, 'fraction_numerical': 0.0137123745819398, 'mean_word_length': 3.9753189129229063, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Game Theoretic Control of Multi-Agent Systems

Control of multi-agent systems via game theory is investigated. Assume a system level object is given, the utility functions for individual agents are designed to convert a multi-agent system into a potential game. First, for fixed topology, a necessary and sufficient condition is given to assure the existence of local information based utility functions. Then using local information the system can converge to a maximum point of the system object, which is a Nash equilibrium. It is also proved that a networked evolutionary potential game is a special case of this multi-agent system. Second, for time-varying topology, the state based potential game is utilized to design the optimal control. A strategy based Markov state transition process is proposed to assure the existence of state based potential function. As an extension of the fixed topology case, a necessary and sufficient condition for the existence of state depending utility functions using local information is also presented. It is also proved that using better reply with inertia strategy, the system converges to a maximum strategy of the state based system object, which is called the recurrent state equilibrium.


Introduction
In recent years the game based control has received extensive attention from control community. The game theory has been applied to various control problems, including control of hybrid systems [18], planning hybrid power systems and distributed power control [15], [11], analysis and control of networks [17], distributed coverage of mobile agents [20], [21], road congestion control [19], just to name few.
Particularly, the game theoretic control is a promising new approach to the distributed control of multi-agent systems. In [13] the consensus of multi-agent systems is investigated. [10] describes a solution framework for multi-agent control problem using game theory. Noncooperative dynamic game theory provides an environment for formulating multi-agent decision control problems using distributed optimization [2]. Learning is an important tool to realize a global goal for game theoretic approach of multi-agent systems [1]. An hourglass architecture was proposed in [10]  theoretic control using potential games as the interface (refer to Fig. 1).

Potential Games Utility Design
Learning Design Consider a multi-agent system. Assume a system level objective function is given. This paper considers whether the system designer is able to design local information based utility functions for individual agents, such that the multi-agent system becomes a networked potential game with the objective function as the potential function. Then as the agents using their local information to maximize their utility functions the overall system can maximize the (system level) objective function. The paper consists mainly of two parts: First, the fixed topology case is considered. A necessary and sufficient condition is obtained to assure the existence of local information based utility functions. Then we show that the networked evolutionary potential games are special case of this kind of multi-agent systems.
Second, the case of time-varying topology is investigated. The concepts and results about state based potential game proposed by J.R. Marden [14] have been used and combined with our previous results. Similar to fixed topology case, a necessary and sufficient condition is also obtained. Certain state transition process is proposed as strategy depending Markov process, which assures the non-decreasing requirement of the state based potential function. An illustrative example is presented, which shows that the game theoretic control makes the multi-agent system reach consensus with probability 1.
The rest of this paper is organized as follows: Section 2 provides some necessary preliminaries, including (i) semi-tensor product of matrices, which is a basic tool in our approach; (ii)the potential equation, which is a key result used in this paper; (iii) networked potential game, which is an important example of the multi-agent systems concerned in this paper. Section 3 considers the game theoretic control for fixed topology multi-agent systems. A necessary and sufficient condition is presented. It is also shown that networked potential games meet the requirement. The game theoretic control for time-varying topology is discussed in Section 4. State based potential game is reviewed first. A necessary and sufficient conditions is also obtained. An illustrative example is presented. Section 5 is a brief conclusion.

Semi-tensor Product of Matrices
This subsection gives a brief review for semi-tensor product (STP). We refer to [3], [4], [5] for details. For statement ease, we first introduce some notations: (1) M m×n : the set of m × n dimensional real matrices.
(2) Col(A) (Row(A)): the set of columns (rows) of A; (4) δ i n : the i-th column of the identity matrix I n ; The set of m × r logical matrices is denoted as L m×r ; (7) Let L be a logical matrix, i.e., L ∈ L m×r . Then L = [δ i1 m δ i2 m · · · δ ir m ]. For brevity, (8) Set of random vectors: (9) Set of random matrices: Definition 1 Let A ∈ M m×n , B ∈ M p×q , and t = lcm(n, p) be the least common multiple of n and p. Then the (left) STP of A and B, denoted by A⋉B, is defined as where the ⊗ is the Kronecker product.
Remark 2 (1) If n = p, the STP defined in Definition 1 degenerates to the conventional matrix product. Hence, STP is a generalization of the conventional matrix product. Hence, we adopt as the convention that AB := A ⋉ B.
(2) All the major properties of conventional matrix product, such as the associativity and the distributivity etc., remain available.
The following proposition shows that the STP has certain communicative property.
Proposition 3 Given A ∈ M m×n .
1. Let Z ∈ R t be a column vector. Then 2. Let Z ∈ R t be a row vector. Then To explore further communicating properties, we introduce the swap matrix.
The following proposition shows that the swap matrix is orthogonal.
Its fundamental function is to swap two factors.
Proposition 6 1. Let X ∈ R m , Y ∈ R n be two column vectors. Then 2. Let X ∈ R m , Y ∈ R n be two row vectors. Then

Potential Games
Definition 7 [9] A finite game is denoted by G = {N, S, c}, where (i) N = {1, · · · , n} is the set of players; (ii) S = n i=1 S i is the profile of strategies (or actions) S i , where S i = {1, · · · , k i } is the set of strategies of player i; (iii) c = (c 1 , · · · , c n ) and each c i : S → R is the utility (or payoff ) function of player i.
To use STP, the action a i ∈ S i is denoted as Then each utility function c i can be expressed as where The set of finite games with |N | = n, |S i | = k i is denoted by G [n;k1,··· ,kn] . G ∈ G [n;k1,··· ,kn] is completely determined by V G := (V c 1 , · · · , V c n ) ∈ R nk . Hence, G [n;k1,··· ,kn] has a vector space structure as R nk [8].
Definition 8 Consider a finite game G = {N, S, C}. G is a potential game if there exists a function P : S → R, called the potential function, such that for every i ∈ N and for every s −i ∈ S −i := j =i S j and ∀α, β ∈ S i Potential games have some nice properties, which make them helpful in control design. We listed some as follows: Theorem 9 [16] If G is a potential game, then the potential function P is unique up to a constant number. Precisely, if P 1 and P 2 are two potential functions of G, then P 1 − P 2 = c 0 ∈ R.
Theorem 10 [16] Every finite potential game possesses a pure Nash equilibrium. The myopic best response adjustment (MBRA) leads to a Nash equilibrium. (Please also refer to (18)- (19) for MBRA.) Consider a finite game G = {N, S, c}, where |N | = n, |S i | = k i , i = 1, · · · , n, and the payoff function of player i is denoted as (8). We need some new notations as: and Then we construct a linear equation, called the potential equation, as where ξ i ∈ R k/ki . Then we have the following result: Theorem 11 [6], [8] A finite game G ∈ G [n;k1,··· ,kn] is a potential game, if and only if the potential equation (12) has solution. Moreover, if ξ is a solution then the potential function can be expressed as where V P , the structure vector of the potential function, is

Networked Evolutionary Games
Definition 12 [7] A networked evolutionary game (NEG), denoted by Γ = {(N, E), G, Π}, consists of (i) a network graph (N, E); (ii) a fundamental network game (FNG), G, such that if (i, j) ∈ E, then i and j play FNG with strategies a i (t) and a j (t) respectively; (iii) a local information based strategy updating rule (SUR), Π.
Using vector form expression of the strategies, (15) can be expressed into its algebraic state space form as where a(t) = ⋉ n i=1 a i (t), and when only pure strategies are allowed then L ∈ L k×k ; if the mixed strategies are allowed then The f i in (15) is determined by the SUR. In the following, MBRA, as the only SUR used in this paper, is briefly introduced. Denote by U (i) the neighborhood of node i. As a convention, we assume i ∈ U (i).
Let c ij be the payoff of the player i in the FNG between i and j, then the overall payoff of player i is Assume the SUR used is MBRA, that is where the elements of BR i (t) are named as a i (t + 1) is precisely defined as follows: If only the local information is allowed to use, then (16) becomes and the rest determining process remains unchanged.

Remark 13
If only the local information is allowed to use, the convergence described in Theorem 10 is not assured, unless the utilities are themselves local information depending. That is why we need to design the local information depending utilities.

Utility Design
As pointed in [10] or [14], in general, a multi-agent system may not originally a networked evolutionary game. There is a system level objective function φ : S → R that a system designer seeks to maximize. Then we may design a set of suitable utility functions such that the system becomes a potential game with φ as its potential function. This is the first task in game theoretic approach, which is described in top part of Fig. 1. Second task is: since the information used is a local one, a learning SUR is necessarily to assure the system converges to the maximum object value. We start with a motivated example.

A Motivated Example
A B C

Fig. 2. A Network
Assume there are three players: A, B, C, connected as in Fig. 2. Assume each player has two strategies S i = {1, 2}, i = 1, 2, 3. The system level object is to guide players to a synchronized form a 1 (t) = a 2 (t) = a 3 (t) = 1. So a system level objective function can be described as The system designer wants to maximize φ, which leads the system to the synchronization.
The structure vector of φ is figured out as It is easy to calculate that Using (11), we have Then the potential equation (12) can be built, and a solution is obtained as ξ = [0, 1, 0, 1, 1, 3, 1, 0, −1, 0, 0, 1] T , and ξ 1 follows as According to Theorem 11 this game is potential. Moreover, using (14) we can calculate that Note that is also a potential function.
Observing that in this networked game the utility functions c i depends only on its neighborhood. Hence the local information MBRA, as defined in (19) is the same as the global information MBRA, as in (18). According to Theorem 10, the local information MBRA can lead the system to a Nash equilibrium, which maximizes the system objective function.
Motivated by this example, it is natural to seek a set of local information based utility functions, which then can lead the system to a maximum point.

Local Information Based Utility Functions
Consider a game G ∈ G [n;k1,··· ,kn] . Assume U ⊂ N , say U could be a neighborhood of a node. Then we try to "draw" the nodes of U from all the nodes in N . We construct a matrix, called the U -drawing matrix, to do this. Set where Then we have the following result.
Remark 15 (1) The proof of Lemma 14 is based on the fact that for two column vectors X, Y , Then a straightforward computation leads to the conclusion. (2) From the proof it is clear that formula (16) is also available for a i ∈ Υ ki , i = 1, · · · , n.
Consider G ∈ G [n;k1,··· ,kn] being a networked evolutionary game. Assume the utilities are adjustable. A natural question is: are we able to design a neighborhooddeterminant utilities such that G becomes a potential game and local information is enough to assure the convergence.
Theorem 16 Assume G ∈ G [n;k1,··· ,kn] is a utilityadjustable networked evolutionary game. The system objective function is Then there exists a set of neighborhood-determinant utilities, which turn G to be a potential game, if and only if Proof. By the requirement, we have where a = ⋉ n i=1 a i .
Using the same argument as in the proof of Theorem 11, one sees that G is a potential game, if and only if, where a −i ∈ S −i , which means d i is independent of a i .

Plugging (25) into (26) yields
which is equivalent to (24). ✷ For convenience in use, denote by B a basis of the vector space on the right hand side of (24). That is, Row(B) are linearly independent and

Networked Potential Games
Consider an evolutionary game G = { (N, E), G, Π}, assume the fundamental network game G is potential, then we call G a networked potential game (NPG). Assume the system objective function where P e is the potential function for G over the edge e. Using the natural utility function (17), it is clear that (24) is satisfied. This fact shows that pretty of multiagent systems verify the requirements of Theorem ??.
In the following we give an example.

Example 17
Consider an NEG G = { (N, E) , G, Π}, where the network graph is as in Fig. 3, and the FNG, G, is the Prisoner's Dilemma game with payoff matrix shown in Table 1.  Using potential equation, we can prove that Prisoner's Dilemma is a potential game and one of its potential function is P (a 1 , a 2 ) = [−2, 0, 0, 1]a 1 a 2 . Then the overall potential function φ is φ(a) = P (a 1 , a 2 ) + P (a 1 , a 3 ) + P (a 2 , a 4 ) + P (a 3 , s 4 ) According to (21) and (22), we have Additionally, It is easy to check that which is equivalent to (24).

A Brief Review
The state based potential game is proposed in [14]. This subsection briefly review some related basic concepts and results.
Definition 18 (1) A finite state based evolutionary game is a tuple G = {N, S, C, X, P }, where N = {1, 2, · · · , n} is the set of players; S = n i=1 S i is the strategy profile; C = {c 1 , · · · , c n } is the set of payoff (utility) functions, and c i : X × S → R; X is the state space; P : X × S → △(X) is the the probability distributions over the finite state space X.
(2) X = {x 1 , · · · , x r }, where r = |X|. Similar to a i ∈ ∆ ki , we can also to express states in vector form as (3) The state x(t) satisfies which can be expressed into its algebraic state space form as where a(t) = ⋉ n i=1 a i (t).
(4) The strategy dynamics of an evolutionary game is of the following form , a(t), c(t)) a 2 (t + 1) = f 2 (x(t + 1), a(t), c(t)) . . . a n (t + 1) = f n (x(t + 1), a(t), c(t)), where c(t) = (c 1 (t), c 2 (t), · · · , c n (t)). The dynamics is determined by an SUR. In this paper we assume f i is independent of c, hence it can be expressed in algebraic state space form as

Definition 19
The action state pair [a * , x * ] is a recurrent state equilibrium with respect to the state transition process P (·) if the following two conditions are satisfied: • The state x * satisfies x * ∈ X(a * |x) for every state x ∈ X(a * |x * ). • For every agent i ∈ N and every state x ∈ X(a * |x * ), Definition 20 A state based game G = {N, S, C, X, P } is a state based potential game if there exists a potential function φ : X × S → R that satisfies the following two properties for every action state pair [a, x] ∈ S × X: • For any agent i ∈ N and action a ′ i ∈ S i • For any state x ′ in the support of P (x, a) The "better reply with inertia" dynamics is important for state based games. Define an agent's strict better reply set for any action state pair [a, x] ∈ S × X as The better reply with inertia dynamics can be described as follows.
Theorem 21 Let G = {N, S, C, X, P } be a state based potential game with potential function φ : X × S → R. If all agents adhere to the better reply with inertia dynamics then the action state pair converges almost surely to an action invariant set of recurrent state equilibria.
The system objective function can be expressed as Split V φ into r equal blocks as where U i (j) is the neighborhood of player j under fixed state x = x i . Define Next, we need to design the state evolutionary process (SEP). We suggest the following two ways to construct it.
The system objective function is Then there exists a set of neighborhood-determinant state based utilities, which turn Γ to be a state based potential game, if and only if Remark 24 Using the SEP-1 determined by (39)-(40) or the SEP-2 determined by (41) and the system objective function satisfying (42), we can convert a multi-agent system to a state based potential game. Then using better reply with inertia dynamics, the system will converge almost surely to an action invariant set of recurrent state equilibria.
the system level objective function as the potential function. Then individual agents can use their local information to reach an equilibrium, which maximizes the objective function. Two cases have been investigated. (i) fixed topology, and (ii) time-varying topology. Necessary and sufficient conditions have been obtained for both cases. Some examples are presented to illustrate the theoretical results.
There are several problems remaining for further study. For example, (1) The state transition process used in this paper for time-varying topology is designable. A challenge problem for further investigation is to relax this. (2) When the necessary and sufficient condition fails, can we design a near-potential game [22] to reach the same goal?