The study of multi-agent systems (MAS) is gaining increasing significance, particularly in engineering fields such as smart grids, robotics, and machine learning.
Game theory offers a robust framework for analyzing the strategic interactions between rational decision-makers in such systems. H owever, traditional gametheoretic concepts, such as Nash equilibrium [11], may need to be revisited in scenarios where agents have access to privileged i nformation. In the context of learning in games [23], such asymmetry of information can be exploited to manipulate the system's long-term behavior, leading to outcomes that benefit some agents while disadvantaging others. For instance, in the context of Nash equilibrium seeking in non-cooperative games [1,5], privileged agents can exploit knowledge of other agents' exploration policies to interfere with their learning processes, without altering their own learning capabilities. When this interference maintains the overall system's stability, it can cause the naive agents to converge to incorrect steady-state models or beliefs . This phenomenon, known as deception in games, has received significant attention during the last years due to its potential implications in the context of cyber-security and resilient decision making in socio-technical systems. Algorithmic deception has been studied across various domains, including robotics and aerospace control [3,4,6]. Similarly, studies such as [17] propose algorithms for robots to decide when to deceive, as illustrated in hide-and-seek experiments. While deception can aid robots in achieving particular goals in non-competitive e nvironments, it has also been explored in competitive scenarios, such as signaling games [8]. These concepts are further explored in works investigating deception in multi-agent systems, offering strategies to counter deceptive signals and attacks [14]. Deception has also been studied in the context of biological systems [15] and societal systems [10].
In this paper, we focus on studying deception in Nash equilibrium-seeking (NES) problems within non-cooperative games. In these scenarios, a finite number of agents, or players, seek to maximize their individual profits, which depend not o nly on their own actions but also on the actions of others. Given the challenge associated with computation of Nash equilibria [11] in noncooperative games, the study of NES algorithms has become a very hot researc h topic. Various algorithms have been designed, including distributed [20][21][22], semi-decentralized [2,24] and hybrid [18,19] algorithms. However, in some cases, the agents do not have precise knowledge of their cost functions, and hence they must rely on adaptive seeking dynamics that i ncorporate exploration and exploitation strategies. To address this, extremum-seeking based NES dynamics were introduced in [5] and have been extended to stochastic settings [9], systems with delays [12], nonsmooth algorithms [13], etc. In this setting, agents with privileged knowledge of the exploration policy used by others can manipulate their own exploration policy to induce false beliefs in the other agents, making them take actions that are detrimental for them. Such type of deception was recently introduced and studied in [16] for a general class of games, establishing conditions that preserve stability in the overall system. In particular, it was shown that when players i n a non-cooperative game implement the model-free Nash equilibrium seeking (NES) scheme from [5], a player who gains insight into another player's exploration policy can manipulate the Nash equilibrium to their advantage. The proposed deception mechanism involves an additive and dynamic modification to the deceiver's action update, incorporating the victim's exploration frequency. This modification is adjusted using first or second-order dynamics. In the context of duopoly games, deceptive players have been shown to manipulate the victim's perception of their sales function. Using an averaging and singular perturbation approach, it was further shown that the proposed deception mechanisms preserve stability in non-cooperative games with general nonlinear payoffs, including strongly monotone games. While the results in [16] were the first to establish dynamic deception through model-free NES dynamics, their general applicability is constrained b y certain assumptions. For example, the "stability-preserving set" described in [16], a key element in the singular perturbation analysis, is only guaranteed to cover a small neighborhood around a specific point. Additionally, although the work in [16] relaxes the diagonal dominance condition from [5], it does so at the cost of requiring all players to use identical gains and amplitudes in their NES dynamics.
In this paper, we introduce several new results that relax some of the previous assumptions considered in the literature [16], and, additionally, we introduce new results and computations in the context of general N -player N -player oligopoly markets, such as those studied in [5]. Furthermore, we exploit the structure of the oligopoly market to derive sharper stability results and characterizations that quantify the influence of deception in this context. We also provide a broader estimate for the stability-preserving set in the nominal average dynamics and offer results that determine when the new equilibrium point under deception is truly a Nash equilibrium, rather than just an equilibrium, for the deceptive game. T his framework further allows us to consider a more general class of NES dynamics, where players are permitted to use different gains and amplitudes in their update laws. The effectiveness of these results are also demonstrated through numerical simulations.
In this section, we describe the types of games considered in this pape r, as well as the model-free deception dynamics.
Consider an N -player noncooperative game, where player i implements action x i ∈ R and aims to unilaterally minimize their cost function J i : R N → R. We use [N ] := {1, 2, ..., N } to denote the set of players, and we let x = [x 1 , ..., x N ] denote the vector of players' actions. Similarly we use x -i ∈ R N -1 to denote the vector of all players' actions except for the action of player i. Given real-valued cost functions J i (x i , x -i ) : R N → R, for all i, a policy x * ∈ R N is called a Nash equilibrium if it satisfies
We define the pseudogradient of the game to be G(x
where
to denote the diagonal matrix with i-th diagonal element given by v i . Since we focus on oligopoly games where each player i controls the price x i of their own product, the cost functions of interest take the form [5]:
where m i is the marginal cost of the product generated by the i th player, and s i is their sales function, which is given by
Here, S d is the total consumer demand and R i represents the resistance" that consumers have towards buying the product offered by firm i. In other words, the desirability of product i is inversely proportional to R i . The quantities R and R i are given by
As in [5], the sales function is motivated by an electrical circuit analogy, illustrated in Fig. 1.
Fig. 1. Market-circuit analogy borrowed from [5], which models the sales s1, s2, s3 of a three-player oligopoly a s currents in a 3-resistor parallel circuit.
In Fig. 1, the total demand S d can be thought of as a current generator, the prices x i are voltage sources, and R i is the resistance towards product i. It is also important to note that s i (x)(x im i ) represents the profit of firm i, but we define J i as (2) since, without loss of generality, we see J i as a cost to b e minimized by the i th player.
To converge to a neighborhood of a "standard" Nash equilibrium by only using measurements of their cost J i , players can implemen t the following modelfree NES dynamics introduced in [5]:
where the gains a i , k i > 0 are positive tunable parameters, and the frequencies ω i ∈ R >0 are selected to satisfy the following assumption:
Assumption 1. The frequencies satisfy ω i = ω j for i = j, and
It is easy to verify that the costs J i can be represented in the quadratic form
where
Here, [Q i ] jk and [b i ] k denote the (j, k) entry of Q i and k-th entry of b i respectively. It follows immediately that the pseudogradient of the oligopoly can be represented in the form
Here, [E] i: denotes row i of matrix E.
To incorporate deception into the NES dynamics (5), in this paper we consider the following m odified model-free NES algorithm:
\ {i} if its actions are updated via the following rule:
where δ i (t) is a tuning deceptive gain that satisfies sup t≥0 |δ i (t)| > 0.
In addition to knowing the frequency ω i , any player who wants to deceive player i must also know the amplitude a i . While this seem more restrictive than the deception considered in [16], which only required knowledge of ω i , it is in fact less restrictive since the NES strategy in [16] assumed a k = a for all k ∈ [N ].
In our setting, we assume there are n deceptive players, and the set of deceptive player is given by D = {z 1 , ..., z n }. We say player i ∈ D is deceiving
where
is player i's desired reference cost. For non-deceptive players, we have that δ i := 0. The full model-free NES dynamics can thus be stated as follows for all players i ∈ [N ]:
Now that the overall game dynamics have been established, w e will present our main results.
Let K j represent the set of players who are deceptive to player j, i.e.
These quantities essentially represent the "perturbed" pseudogradient that results from deception, which will become more intuitive when we obtain the averaged system in the stability proof. Before we proceed to the stability analysis, we define the stability-preserving set:
where K = diag([k 1 , ..., k N ] ). We can then present our first result, which p rovides a somewhat useful "lower bound" on Δ:
Proof. By (7a) we already know [Q i ] kj = 0 for k ∈ K i and j = i, thus for fixed i we have
and
The result then follows by the G ershgorin Circle Theorem.
This estimate is a significant improvement compared to the results of [16], which only guarantee that Δ contains a neighborhood of the origin. By exploiting the structure of the duopoly, we are now able to say that this neighborhood at least contains the unit ball. To characterize when the deceptive players are able to properly achieve their desired payoffs via deception, we introduce the notion of attainability as was presented in [16]:
We let Ω ⊂ R n denote the set of all attainable vectors
With this definition at hand, we can now state the main result of this paper. The following theorem c haracterizes the stability properties of the NES dynamics with deception: Theorem 1. Consider the NES seeking dynamics ( 9) and (10) with J ref ∈ Ω, J i of the form (2) and ω i satisfying Assumption 1 for all i ∈ [N ]. Then there exists ε * > 0 such that for all ε ∈ (0, ε * ), there exists a * > 0 such that for a 1 , ..., a N ∈ (0, a * ) there exists ω * > 0 such that for all ω > ω * the state
Proof. To analyze the system, let μ(t) = xu, where x, u are given in (10). In other words, μ(t) is the vector of sinusoids. We apply the time scale transformation τ = ωt, and denote μ(τ ) = μ(τ /ω) and T = 2π ×lcm{1/ω 1 , 1/ω 2 , ..., 1/ω N }. With standard averaging theory [7], we can compute the average dynamics of system (10), whose state we denote as ũ ∈ R N :
By combining all u i 's, we obtain the average system
We can apply the same technique on (10) for i ∈ D:
where P i : R N → R is a quadratic function satisfying P i (a) = 0, and can thus be treated as an O(a) perturbation on compact sets, where a = [a 1 , ..., a N ] . We recall that D = {z 1 , ..., z n }. By setting τ * = ετ and J * (ũ) = [J z1 (ũ), ..., J zn (ũ)] , the entire system can be represented as
If we disregard the perturbation in (20), the resulting system is a singularly perturbed system with quasi steady state h( δ) = -Q( δ) -1 B( δ) and reduced dynamics given by
Since J ref ∈ Ω, it follows that ( 21) has an exponentially stable equilibrium point δ * ∈ Δ. Moreover, by denoting y = ũh( δ), we obtain the boundary layer system ∂y ∂τ = -KQ( δ)y (22) where the origin is exponentially stable uniformly in any compact set contained in Δ. Hence the unperturbed system (20) has an exponentially stable equilibrium point ζ * = [u * δ * ] where u * = -Q(δ * ) -1 B(δ * ). By standard robustness results for systems with small additive perturbations, we can find a * > 0 such that for max i a i ∈ (0, a * ), ζ converges exponentially to a O(max i a i ) neighborhood of ζ * provided |ζ(0)ζ * | sufficiently small. Then, by standard averaging results for ODEs [7, Thm 10.4] we prove the claim for ω sufficiently large.
Even though this proof is similar to that of the main result in [16], we include it here to account for the generalization of allowing distinct k i and a i . While this result is quite useful, one main concern is computing the set Ω. A relatively straightforward method for computing Ω when |D| = |D z1 | = 1 is presented in [16], but in general it is a challenging problem. One promising approach is to use Lemma 1 to evaluate a "lower bound" for J i (-Q(δ) -1 B(δ)) and then use numerical methods to appro ximate Λ(δ) for |δ| < 1.
In [16], it was shown that deception via (10) essentially transforms the duopoly into a deceptive game with deceptive costs that manipulate the victim's seeking dynamics into misinterpreting their sales function s i (x), so it is of interest to generalize t his intuition to the N -player oligopoly. We first recall the definition of a deceptive game from [16]:
In other words, this definition captures the effect of deception by framing the emerging behavior of the system as a standard Nash equilibrium-seeking problem parameterized by costs { Ji } i∈ [ N ] . That is, the game with costs {J i } i∈[N ] under the deceptive NES dynamics (10) will exhibit the same asymptotic behavior as a standard non-cooperative game with costs { Ji } i∈[N ] and players implementing the deception-free NES dynamics (5). We can then use (23) to compute a deceptive game for the oligopoly market scenario:
If we set
we finally obtain
When comparing (28) with (2), we can observe that player i now has a δ-inflated sales function, which is highly reminiscent of the duopoly analysis from [16]. If we reasonably assume that
R k > 0 implies that player i's NES dynamics behave as if their sales are greater than they really are. This will result in player i increasing their price x i to increase their payoff, even though in reality it might harm their profits. Similarly, if
R k < 0, player i's strategy will behave as if their sales are lower than their true value. This will result in player i decreasing their price x i , which could potentially harm their profits.
R k , which indicates that a firm with a more desirable product will wield more influence as a deceiver.
Although the "deceptive game" view adds some intuition behind how deception affects the players' behavior, one of the main drawbacks is that the variability of σ i may lead to conflicting interpretations. Hence, we present an alternate and somewhat consistent viewpoint that captures the effect of deception on player i's estimate of their gradient ∇ i J i . From (23) we have:
and we also have
and
Both cases seem to indicate that when player i is being attacked, their NES dynamics "learn" that the total desirability of the other players' products is given by 1
Ri . This means that whenever k∈Ki δ k R k > 0 holds, player i believes the other player's products to be less desirable than they really are, which would lead to player i increasing their price x i . Similarly, when k∈Ki δ k R k < 0, player i's NES dynamics will overestimate the desirability of the other players' products, leading to player i lowering their price. Alternatively , one can also make the following observation:
1
which suggests something slightly more intricate. In particular, although (29) and (30) provide some insight into how the players in K i collectively alter the beliefs of player i, equation (31) indicates the degree to which each deceptive player affects player i's estimate of the desirability of that deceptive player's product. Just as we have seen before, the term 1 R k implies that the desirability of a firm's product can amplify their ability to deceive.
So far, we have observed that when firms in an oligop oly implement the deceptive NES strategy (10), the asymptotic behavior aligns with that of a game parameterized by costs { Ji } i∈ [ N ] with firms implementing the deceptionfree NES dynamics (5), but it is also of interest to ask if the new "deceptive" equilibrium point is actually a Nash equilibrium of the deceptive game { Ji } i∈ [N ] .
The following result provides some sufficient conditions to answer this question. We present the proof for completeness: Theorem 2. Consider the N -player oligopoly with costs J i of the form (2)
Proof. Since the pseudogradient of the deceptive game satisfies G(x) = Q(δ)x + B(δ), it is easy to verify that if Q(δ) is invertible, the first order condition [1] for u * to be a Nash equilibrium is satisfied. We also have
since |δ| < 2. Thus, the second order condition [1] is satisfied, which implies u * is a Nash equilibrium of the deceptive game { Ji } i∈ [N ] .
To further illustrate our theoretical results, we present a three-firm oligopoly example with parameters R 1 = 0. = -1200 (recall that for our algorithm, we treat J i as a cost to be minimized ). Moreover, we have ∈ Ω. For a more intuitive illustration, we will only plot the profits P i = -J i . As we see in the plots, player 1 is able to force the dynamics to converge to a neighborhood of a point x δ that achieves J 1 (x δ ) = J ref 1 . Moreover, we notice that the deception mechanism causes player 3 to increase their price x 3 significantly, which is consistent with our observations from (28), ( 29) and (30) since δ * 1 > 0.
In this work, we performed a comprehensive study that applied the deception mechanism from [16] to an N -player oligopoly market. By leveraging the structure of the basic two-market duopoly, we establish stability for our proposed deception mechanism in which N players have different gains and exploration amplitudes for their NES dynamics. Moreover, the diagonal dominance property of the duopoly game allows us to derive an improved estimate on the "stabilitypreserving set" and quantify when the deceptive Nash equilibrium is actually a NE for the corresponding oligopoly class of deceptive games. It was also shown that the deception mechanism can be economically interpreted as an artificial inflation (or deflation) of the desirability of the deceivers' product learned by the victim. F uture research directions will characterize how the structure of the interaction graph between players (encoded on how the cost function J i depends on the actions of the other players) affects the emerging deceptive Nash equilibrium and its stability properties. It is also of interest to study stochastic and hybrid (involving continuous-time and discrete-time dynamics) deception mechanisms.