I N MULTIAGENT systems with competitive decision- makers, the act of deception is typically defined as the systematic exploitation of privileged information to induce false beliefs in other agents, leading them to outcomes that are detrimental to their performance or advantageous to the deceiving entity [1]. In game theory, a player who employs deceptive strategies is termed a deceiver. Their aim is to enhance their own outcomes covertly, often without the other players' awareness, who are typically oblivious to such deceitful behavior. Deception in games has gained significant research attention in recent years, particularly due to concerns about safety and security in engineering systems [2]. Deception has been rigorously studied across various domains, including robotics and aerospace control [2], [3], and it has also been recognized as a key evolutionary feature observed in biological systems [4] and human societies [5].
In this article, we study model-free deception in N-player games, where each player aims to unilaterally minimize its own cost function. For such games, the traditional solution concept studied in the literature corresponds to the notion of a Nash equilibrium (NE) [6]. When their collective actions correspond to an NE, no player has any incentive to deviate from their current action, leading to an equilibrium state for the system that is of interest in many coordination and control problems [7], [8], [9], [10]. When the model of the cost function is unknown, and payoff-based strategies are required, various NE-seeking algorithms have been studied in the literature. For example, in N -person noncooperative games with individual real-valued cost functions J i (x), i ∈ {1, 2, . . . , N } and vector of actions x = [x 1 , . . . , x N ] , the work [11] introduced a class of model-free and adaptive NE seeking dynamics that implements exploration and exploitation actions in each player i via the following dynamics:
where a, k, and ω i are positive tunable parameters, u i is an auxiliary state implemented by every player i, and μ(ω i t) is a local continuous periodic probing signal characterizing the exploration policy implemented by the agent. As shown in [11], for a general class of games, the payoff based algorithm (1) can attain convergence to a neighborhood of the NE of the underlying game characterized by the cost functions J i . Such results opened the door to the development of a variety of NE-seeking algorithms in the context of systems with delays [12], games with constraints [13], dynamics with momentum [14], games over networks with mild coupling [15], nonsmooth algorithms [16], etc. Since system (1) can be seen as a continuous-time version of a discrete-time zeroth-order algorithm based on simultaneous perturbations [17], the results of [11] have also been connected and extended to discrete-time and stochastic settings using tools, such as discrete-time averaging [18], stochastic calculus [19], and stochastic approximations [20], [21], to name just a few. Regardless of the specific NE-seeking dynamics implemented by the players, the majority of works in the literature have primarily focused on studying decision-making problems with symmetric information, where all agents have access to the same type of signals to implement their algorithms. However, in many practical settings involving competitive and/or adversarial entities, a subset of agents has access to private information regarding the other players' algorithms. Such scenarios break the classic assumption of symmetric information, leading to games where players with privileged information can systematically use it to their advantage, sometimes called signaling games [22]. How to utilize such information in NE-seeking systems without causing instabilities, while consistently improving the outcomes of players with privileged information, is a question that has not been thoroughly explored in the literature. This question motivates this work. In particular, we study a class of stable deceptive NE-seeking algorithms that generalize (1) to games with asymmetric information, where two different types of players emerge: oblivious players, who implement the classic dynamics (1), and deceptive players who implement the following policies.Zeroth-order exploitation policy:
Dynamic state-dependent exploration policy:
ηi (t) = εF i (η i (t), J i (x(t)), u i (t)) , ε > 0 (2c)
where F i and h i are suitable smooth functions and ε > 0 is a small parameter designed to induce a time scale separation between the NES dynamics and the deception mechanism.
The key difference between the nominal and deceptive NEseeking dynamics lies in the dynamic, state-dependent exploration policy implemented by the deceivers. In general, the deceiver can tune δ i using only measurements of their action and their payoff. We show that this new policy, which leverages privileged knowledge of the probing signals μ(ω i j ) of a subset of oblivious players {i j } n j=1 , can systematically achieve closed-loop stable behaviors in the multiagent system, while simultaneously inducing false beliefs in the oblivious players, leading them to implement actions that converge to the NE of a different game than the one being played. This "deceptive Nash equilibrium (DNE)" may result in better outcomes for the privileged players. As seen in (2b), the proposed deception mechanism takes the form of an additive modification to the deceiver's action update that incorporates the victims' exploration signals and with amplitudes updated via dynamic feedback.
The following are the main contributions of this article. 1) We introduce the concept of "deception" within the context of the NE seeking schemes proposed in [11], which are based on algorithms that simultaneously implement exploration and exploitation policies, as in (1). We show that if a subset of the players has access to private information related to the exploration policies of other players, then they can use this information to their advantage by implementing the dynamics (2) to influence the behavior of the oblivious players that implement the nominal NE seeking dynamics (1). As a result, the actions of oblivious players converge to the reaction curves of a different game, which is parameterized by the deceiving player. Specifically, we show that if a nominal, model-based, pseudogradient flow dynamic exponentially stabilizes a "classic" NE in a noncooperative game, then the proposed model-free dynamics with deception will retain the exponential stability properties, but now with respect to a new DNE. We characterize the geometric properties of this DNE by studying how deception affects the reaction curves of the game learned by the oblivious players. We show that for quadratic games, deception can effectively rotate or translate the reaction curves of the oblivious players, while for aggregative games deception induces nonlinear transformations that can increase the number of equilibria. By using the duopoly game as an example, we discuss various microeconomic interpretations of deception in Nash-seeking dynamics within competitive markets.
2) To align DNEs with desired individual outcomes, we show that deceptive players can modify in real-time the underlying game played by the oblivious players until the value of the cost function of the deceiver aligns with a desired reference value. This is achieved through dynamic deceptive exploration signals, managed by an auxiliary payoff-based mechanism implemented by the deceiving agents. We rigorously characterize the conditions under which the deceptive player can improve their own objective function and provide a conservative estimate of the potential improvement while maintaining the stability of the game. We also study mutual deception when multiple deceivers have privileged information about each other's exploration policies.
3) By leveraging the geometric characterization of the DNE, we provide sufficient conditions on the game parameters that ensure "immunity" against deceptive players. These conditions offer valuable insights into designing counter-deception mechanisms for games and adaptive NE seeking algorithms. We also study deceptive dynamics with integral and approximate proportional action, which are able to improve transient performance to minimize potential deception detection via transient analysis. All our results are validated through simulations and numerical analysis. To the best of the authors' knowledge, this work is the first to study stable deception mechanisms in model-free NE seeking dynamics.
No portion of this article was published at a conference. The rest of this article is organized as follows. Section II presents the preliminaries. Section III introduces the problem of deceptive NE seeking. Section IV presents the main results for N-player quadratic games. Section V focuses on deception applied to N -player (strongly monotone) aggregative games. Finally, Section VI concludes this article.
We use a ij to denote the matrix A whose (i, j) entry is given by a ij . Given a matrix Q i and vector b i , we use (Q i ) jk to denote the (j, k)th entry of Q i , (Q i ) j: to denote the jth row of Q i , (Q i ) :j to denote the jth column of Q i , and (b i ) j to denote jth entry of b i . Furthermore, we let [Q] i,j denote the matrix formed by taking Q and removing the ith row and jth column. Having "∼" in the i (or j) entry means no row (or column) is removed. For instance, [Q] ∼,3 is the matrix formed by only removing the third column of Q (no row is removed). Given N ∈ N, we use [N ] to denote the set of positive integers no greater than N , i.e., [N ]
2) Game Theory: We consider N -player non-cooperative games, where the action of player i is a scalar x i ∈ R, and each player aims to unilaterally minimize its own cost J i , which also depends on the actions of the other players, and which is assumed to be continuously differentiable. We use [N ] = {1, 2, . . . , N } to denote the set of players, and x = [x 1 , . . ., x N ] to denote the vector of actions. Similarly, we let x -i ∈ R N -1 be the vector containing the actions of all players other than the ith player. Given real-valued cost functions J i (x i , x -i ) : R N → R, for all i, a NE [6] is a vector x * ∈ R N that satisfies
that is, if the other players implement x * -i , then no player has incentive to unilaterally deviate from x * i ∈ R to improve their cost. For a broad class of noncooperative games, NE can be characterized using the pseudogradient of the game, which is a mapping
In particular, an NE x * satisfies G(x * ) = 0, but the converse is in general not true without additional assumptions. For each x -i ∈ R N -1 , the reaction curve of player i is defined as the set-valued mapping RC i (x -i ) : R N -1 ⇒ R that satisfies ∇ i J i (RC i (x -i ), x -i ) = {0}. Since reaction curves are characterized by their graph, in this article, a "reaction curve" will refer to the set N (∇ i J i (x)). While we assume scalar actions to avoid cumbersome notation, our models and results extend to games with vector actions via Kronecker products.
For a general class of games with symmetric information, the model-free dynamics (1) have been show to attain local or semiglobal practical NE seeking [11], [15], [16]. The key enabler for the "learning" capabilities of system (1) are the probing signals μ that use frequencies ω i ∈ R >0 , which are selected to satisfy the following assumption.
Assumption 1: The frequencies satisfy ω i = ω j for i = j, and
Assumption 1 is instrumental for the analysis and generalizing the set of permissible exploration frequencies beyond Q >0 . Under Assumption 1, for sufficiently small values of a and sufficiently large values of ω, the trajectories of system (1) can be approximated (on compact sets) by a perturbed pseudogradient flow of the form u = -kG(ũ) + O(a).
Since nominal pseudogradient flows of the form u = -kG(ũ) converge to the NE in a variety of games [23], [24], suitable (practical) stability properties can be established for (1) under an appropriate tuning of its parameters. Note that, in system (4), the ith component of ũ is given by ui
which shows that, when the O(a) perturbation is neglected, the equilibria of (4) are precisely characterized by the intersection of the reaction curves for all i ∈ [N ]. Hence, to study deception in a general setting, we start by making the following assumption that pertains to the behavior of the unperturbed system (4) in a nominal game with symmetric information. Assumption 2: J i ∈ C 2 (R N , R), there exists a unique NE x * ∈ R N for the game {J i } N i=1 , and the dynamics ẋ = -kG(x) render x * uniformly globally exponentially stable.
Remark 1: The stability properties of Assumption 2 are satisfied in a variety of games, including strongly monotone, which are common in the literature of NE seeking [16]. However, we note that the assumption can be relaxed to local exponential stability, which holds for a larger class of games [11], and which can be studied via linearization methods.
The principles behind systems of the form (1) or (2), which simultaneously implement exploration and exploitation mechanisms, apply to other algorithms, including discrete-time and stochastic algorithms where players use random perturbations with zero expectation and identity correlation instead of periodic deterministic dither signals (see [20], [25], and [26]). In particular, many multiagent model-free equilibrium-seeking algorithms rely on two key principles: 1) modulation: each agent uses an exploration signal with a unique key feature to perturb their nominal action u i ; and 2) demodulation: each agent uses the same exploration signal to extract information from their cost function about their cost derivatives. This information is then used by a preselected exploitation policy to update u i to "seek" for the NE. and decryption (D) using private exploration policies. Top: Scheme proposed in [11] for games with symmetric information. Bottom: Schemes studied in this paper for games with asymmetric information and deceptive players. For this figure, we took a = 1 for illustration purposes.
The two principles mentioned above happen to be identical to those employed in symmetric-key algorithms used in cryptography for encryption and decryption of messages transmitted via communication channels in adversarial environments [27,Ch. 2]. Indeed, the stability properties of a large class of algorithms based on simultaneous perturbations usually rely on conditions similar to those in Assumption 1, where each player uses a different "key" to encode and decode information about their own current assessment of the game. The left plot of Fig. 1 illustrates this connection. This approach is reasonable in symmetric games. However, as shown in the right plot of Fig. 1, in asymmetric games where some players access others' "keys," the privileged player's new information opens the door to novel strategic adversarial behaviors and, specially, feedback schemes that can exploit this information and which have not been studied in NE seeking problems.
We consider noncooperative games with asymmetric information, where some of the players have access to private information about the exploration policy of other players' algorithms, and use this information to their advantage. We call such players "deceptive."
if its actions are updated via the following rule:
for all t ∈ dom(u d ), where δ is updated via the deceptive dynamics
where η d ∈ R m is an auxiliary state, ε > 0 is a parameter, and F d , h are suitable smooth functions.
To simplify notation, we remove the time dependency from the states of the system. When a player d is being deceptive toward some player d j , we say that player d j is oblivious under player d. The set of all oblivious players under player d is denoted as
and the set of all oblivious players in the game is denoted as
Similarly, the set of all deceptive players is denoted as
In the deceptive strategy ( 6), the parameter δ plays a crucial role. It will be used by the deceptive player to control the game that is learned in real time by the oblivious player.
Definition 2: Given a noncooperative game
In other words, Definition 2 introduces families of games { Ji } i∈[N ] for which only the oblivious players, characterized by the index set D, have cost functions of the form (8) instead of the nominal cost J i . Such functions depend also on the derivatives of the nominal costs J i with respect to the actions of the players k ∈ K i , i.e., the "externalities" that those players have on player i. The σ i (x -i ) term represents any C 0 function that depends on the actions of any set of players excluding that of player i, thus it has no effect on the pseudogradient. Note that, in general, both oblivious and nonoblivious players could be part of the sets K i for some i ∈ [N ]. However, Definition 2 rules out players who are "self-deceiving," although it leaves open the door to "mutual deception," which we will study in Section IV-C.
The following proposition computes the average dynamics of ( 1) and ( 6). The proof follows directly from the proof of Theorem 1 in Section III-D.
Proposition 1: Suppose that Assumption 1 holds, and consider an N-player noncooperative game {J i } i∈[N ] , where a nonempty set D * ⊂ [N ] of deceptive players implements (6), and the rest of the players implement (1). Then, the average dynamics of the players are given by
where
The role of Proposition 1 is to characterize the effect of the exploratory policy (6a) on the average dynamics of the Nashseeking system. That is, deceptive players modify the average dynamics of the oblivious players by injecting externalities into the vector fields, each externality being weighted by the controlled parameter δ j . By effectively inducing false beliefs (i.e., ∇ i J instead of ∇ i J i ) in the oblivious players' dynamics, deceptive players create a new pseudogradient flow (9) defined over the deceptive game Ji instead of the nominal game J i . If a deceptive player is not oblivious (i.e., no other player has access to his exploration policy), then his average dynamics remain unchanged and still approximate (5). In other words, deceptive nonoblivious players still learn their correct reaction curves, but they are able to control the reaction curves learned by the other players.
Given a deceptive N-player game
In general, a DNE might not be a true NE unless it also satisfies second order conditions [28] with respect to the deceptive game, i.e., with Ji instead of J i . Nevertheless, whether x δ is a true NE of the deceptive game is unimportant in the context of stable deception. Yet, in many cases, the DNE turns out to be an NE of the deceptive game. The following example illustrates these ideas using the well-known duopoly game, extensively studied in symmetric-information games [11], [16], [29].
Example 1 (The Duopoly Game With Deceptive Entities): Consider a duopoly market where the two players represent companies that set the prices of their products. Let x 1 (t) denote the price of company 1's product at time t, and let x 2 (t) denote the price of company 2's product at the same time t. As shown in [11], the negative of the profits of the companies in the market is given by
where, for each company i, s i is the number of sales, m i is the marginal cost, and x im i is the profit per unit. Using the model in [11], and assuming that the consumers have a preference for the product of the company 1, as long as its price is not too large compared to the price of the product of company 2, we can model the sales using the functions
, where p > 0 quantifies the preference for company 1, and S d is the total consumer demand, assumed to be constant for simplicity. As shown in [11, Sect. II], the unique NE of this game is
In [11,Thm. 1], the above game was studied under a symmetric-information assumption, and it was shown that if both players implement the NE seeking dynamics (1), then the prices x i will converge to a neighborhood of x * , provided that the parameters a and ω are appropriately tuned. Now, suppose that company 2 has obtained knowledge of the exploration policy μ(ω 1 t) used by player 1, thus breaking the symmetric-information assumption. Using this knowledge, company 2 revises its strategy and implements ( 6) with a sinusoidal probing function
Company 1 is unaware of this change, and continues implementing the vanilla NE-seeking dynamics (1). The resulting average dynamics of the companies are given by u1
Neglecting the O(a) perturbation, this dynamics correspond to the pseudogradient flow of a game with costs ( J1 , J 2 ), where J 2 is still given by ( 10), but J1 is now given by ( 8), i.e.,
Since ∂J 1 (y,x 2 )
, we have
. Thus, using (10), the structure of s 1 , and choosing
, we have that one possible expression for J1 is
which, compared to (10), now has a δ 2 -inflated sales function s1 (x). Thus, whenever the price x 1 is above the marginal cost m 1 , player 1 now has an incentive to increase his price further in order to increase his payoff (i.e., decrease his cost).
To compare the trajectories generated by both algorithms (with and without deception), we simulate the system using S d = 100, p = 0.2, and m 1 = m 2 = 30, and the exploration policies μ(ω i t) = sin(ω i t), for i ∈ {1, 2}. To control δ 2 , company 2 makes use of the following payoff-based deceptive dynamics (7) based on a simple integrator with state
where J ref 2 is a desired profit value for the company. The left plot in Fig. 2 shows the trajectories x i with (solid) and without (dashed) deception. As expected, when all companies implement the nominal NE-seeking dynamics (1), the prices x converge to a neighborhood of the NE x * . The resulting profit functions are also shown in the center plot, converging to J i (x * ), for i ∈ 1, 2. However, note that when company 2 is deceptive, the system's trajectories converge to a neighborhood of a different action x δ ∈ R 2 , namely, the DNE of the deceptive game ( J1 , J 2 ), which, additionally, satisfies J 2 (x δ ) = J ref , and which is given by
Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on December 05,2025 at 23:04:58 UTC from IEEE Xplore. Restrictions apply. The profit J ref is attained by company 2 using δ 2 = δ * = 0.7929, shown in the right plot of Fig. 2. In this way, by controlling δ 2 , company 2 is able to induce a different NE to attain its desired profits. In particular, company 2 deceives company 1 into overpricing relative to his Nash price, resulting in extra profit for the deceiver and reduced profit for company 1. The deception consists in making the oblivious player (i.e., company 1) believe that his sales are higher than they actually are, a belief that is reflected in (14). As we will show in the next sections (see Remark 4), this type of stable deception is possible for any J ref 2 > 0. The oscillatory transient behavior in the figure can be avoided with phase-lead compensation, as shown in Section IV-D. Note that the dynamics (1), (6), and ( 15) are all payoff-based and do not require knowledge of the mathematical form of J i . Moreover, in this case, it can be verified that x δ is also a true NE of the deceptive game ( J1 , J 2 ) when δ 2 = 0.7929.
Remark 2: An alternative interpretation of the deceptive mechanism can be formulated based on adaptive incentives and tolls [30], [31]. In this interpretation, we write the deceptive profit as J1 (x(t)) = J 1 (x(t)) + θ(t), where θ(t) = δ 2 (t)
dy is a state-dependent incentive (or tax). Company 2 uses the deceptive NE-seeking dynamics to "indirectly incentivize" company 1 to choose a different price that results in higher profits for company 2. While adaptive incentives have been studied in economics [29] and congestion problems [30], [32], [33], [34], we are not aware of model-free algorithms able to induce incentives/tolls via deception.
We now generalize the previous discussions to N -player games with multiple deceptive and oblivious players. Consider an N -player noncooperative game with n ≤ N deceptive players. Since we can always assign any reordering to the players, without loss of generality, we assume that the set of deceptive players is given by D * = {1, . . ., n} = [n], where each player i ∈ [n] deceives a subset of players D i := {d i,1 , . . ., d i,n i }, where n i ∈ [N -1]. To simplify our presentation, we focus on exploration policies that use sinusoidal functions, i.e., μ(•) = sin(•). However, other continuous periodic functions with suitable 0-average and orthogonality properties can be used in the exploration policies.
The NES dynamics can be written in a compact form as
where, for simplicity, we omit writing the explicit time dependence of x i and u i . To control the parameters δ i , we first focus on deceptive dynamics based on integral action δi = εε i J i (x) -
To study the stability properties of ( 17) and ( 18), we define the deceptive game operator
where δ = [δ 1 , . . ., δ n ] and
We define the set
where D ũγ is the Jacobian of γ with respect to its first argument. In words, the set Δ characterizes the values of δ for which the negative pseudogradient of a deceptive game has a unique DNE. The next lemma follows directly from the implicit function theorem [35, Thm. 9.28], and it states an important property on how the DNE u * depends on δ. Lemma 1: Under Assumption 2, the set Δ is nonempty and open, and there exists g ∈ C 1 (Δ, R N ) such that γ(g(δ), δ) = 0, for all δ ∈ Δ.
Not every possible value of J ref i may be attainable by a deceptive player under the dynamics (18). To characterize the set of values that can be attained, we introduce the following definition, which makes use of the set Δ in (21) and the function g from Lemma 1. Definition 3:
is said to be attainable if there exists δ * ∈ Δ such that the following holds.
1
2) The matrix ∇ j ξ i (δ * ) ∈ R n×n is Hurwitz, where ξ i :
R n → R is given by ξ i (δ) := ε i J i (g(δ)). We let Ω ⊂ R n denote the set of all attainable vectors
. Remark 3: Attainability is in general a difficult condition to verify a priori, which is why we typically employ numerical methods to verify it. Fortunately, as we will see in Section IV-B, the conditions are relatively simple to check for special cases of quadratic games.
The following general theorem is the first main result of this article. It characterizes the stability properties of the NE seeking dynamics with deception.
Theorem 1: Consider the NE seeking dynamics ( 17) and ( 18) with J ref ∈ Ω, namely, with J ref attainable, as defined in Definition 3. Suppose that Assumptions 1 and 2 hold. Then, there exists ε * such that for all ε ∈ (0, ε * ) there exists a * such that for all a ∈ (0, a * ) there exists ω * such that for all ω > ω * the state
is sufficiently small, where u * is the DNE.
Proof: To analyze the system, let μ(t) = 1 a (xu), where x and u are given in (17). Consider the time scale transformation τ = ωt, and denote μ(τ ) = μ(τ /ω). With standard averaging theory for Lipschitz ODEs [36], we can compute the average dynamics of system (17), whose state we denote as
= -2k ωT
where ℓ is a point on the line segment connecting the points ũ and ũ + aμ(τ ). The summation in the second equality uses multi-index notation, and we used Assumption 1 to evaluate the integrals. Let δ := [δ 1 , . . ., δ n ] , and note that the average dynamics in vector form in the original time scale are given by
with Λ(ũ) given by (19). Averaging also the dynamics of δ, we obtain the average system
and using a Taylor series approximation in (25), we get
where l is a point on the line segment connecting the points ũ and ũ + aμ(τ ). Thus, the overall average dynamics of ( 17) and (18) are
Denoting J * (ũ) = [J 1 (ũ), . . ., J n (ũ)] , we have
Using τ * = τ ε in (28), we get
) If we disregard the O(a) perturbation, the resulting system is in standard singular perturbation form, which, by Lemma 1, has a quasi-steady state ũ * = g( δ). The reduced system is given by ∂ δ
Since J ref ∈ Ω, (30) has an exponentially stable equilibrium δ * ∈ Δ. Furthermore, we can also let y := ũg( δ) and obtain the boundary layer system from ( 29)
where the origin is exponentially stable uniformly in δ ∈ B r * (δ * ) for some r * > 0. Thus, using a standard singular perturbation argument [36,Ch.11.4] (see [42] for details) and letting u * = g(δ * ), we can find ε * > 0 such that for ε ∈ (0, ε * ), [u * δ * ] := ζ * is an exponentially stable equilibrium of the unperturbed system (28). By standard robustness results for systems with small additive perturbations, we can find a * > 0 such that for a ∈ (0, a * ), ζ converges exponentially to a O(a)-neighborhood of ζ * provided that |ζ(0)ζ * | is sufficiently small. By averaging [36,Thm. 10.4], we prove the claim for ω sufficiently large. Remark 4: As in standard NE-seeking algorithms [11], the DNE-seeking dynamics can be enhanced by incorporating a phase φ i into the exploration dither of every player, such that sin(ω i t) in (17) becomes sin(ω i t + φ i ). In this case, if player d is deceiving player i, we let φ d,i denote player d's "estimate" of φ i (i.e., replace sin(d i,j t) in (17a) with sin(d i,j t + φ i,d i,j )). Thus, ∇ j J i (ũ) in ( 20) can be replaced with cos(φ j,iφ i )∇ j J i (ũ), and with this modification, all our results hold, i.e., as long as player d's knowledge of φ i is not off by an odd multiple of π 2 , the effect of deception persist.
While Theorem 1 is quite general and relies only on Assumptions 1 and 2, it does not characterize the set of attainable costs for deceptive players, or how this set relates to the stabilitypreserving set Δ in (21). We address these questions in the next sections by leveraging additional structures on some classes of common games studied in NE seeking problems.
In this section, we focus on games with costs of the form
with Q i ∈ R N ×N being symmetric ∀i, b i ∈ R N , and p i ∈ R. In this case, the pseudogradient of the game is
where Q ∈ R N ×N and B ∈ R N ×1 have the form
. . .
When -kQ is Hurwitz with a negative diagonal, Assumption 2 holds and the NE of the game can be directly computed as x * := -Q -1 B. In this case, we can obtain an exact characterization of the average dynamics using the expansion
In particular, note that under Assumption 1, we have 1
is the sum of terms that are odd and periodic in τ , which implies that O(a) = 0 in (27a).
To study deception in quadratic games, we introduce the matrices Q(i, j) ∈ R N ×N , B(i, j) ∈ R N given by
which allow us to write the average dynamics (24) as
where
Similarly, the average dynamics of δ can be computed as
where P i is now a quadratic function. Therefore, the set Δ in (21) can be equivalently written as Δ = {δ ∈ R n : -kQ δ is Hurwitz} and the δ-dependent equilibrium point of ( 35) is given by
and where g comes from Lemma 1. Note that, while the set Δ is nontrivial to compute, Theorem 1 guarantees that Δ contains a neighborhood of 0, and this neighborhood can be used to obtain a conservative estimate of Ω.
To better understand the effect of deception on quadratic games, we can study the expression in (35). Since for Nplayer quadratic games, each player's reaction curve is an N -dimensional affine hyperplane, and it can be seen that the deception mechanism in ( 17) and ( 18) effectively "adds" additional hyperplanes to the reaction curve of the deceived player. These hyperplanes are precisely the externalities that other players' actions have on the cost of the deceived player.
In particular, recall that the nominal reaction curve for player k is given by N
However, if player k is being deceived by player j, the reaction curve of player k in the deceptive game satisfies
However, since the set
does not depend on δ j whenever δ j = 0, we can deduce that ( 36) is a rotation of player k's reaction curve around the N -1 dimensional hyperplane
then the added hyperplane is parallel to the reaction curve of player k, and hence, (36) is a translation of player k's reaction curve. The following examples illustrate these ideas.
In the duopoly game of Example 1, the profits of the companies have the form (32) with
When company 2 implements the deceptive NE-seeking dynamics (17), we can use the preceding observations to verify that companies 1's perceived reaction curve is a rotated version of the original reaction curve around the point [30,10] . This rotation, for different values of δ 2 , is illustrated in the left plot of Fig. 3, where we also show the reaction curve of company 2 (in color black) and its isoprofit functions (in color gray).
Example 3 (Translation of reaction curves via deception): Consider now a quadratic game with matrices Q 1 = where player 2 is still deceiving and player 1 is still oblivious. In this game, Q 1 is singular and N (∇ 1 J 1 (x)) ∩ N (∇ 2 J 2 (x)) = ∅. Therefore, we can conclude that the "transformation" induced on player 1's reaction curve via deception by player 2 is in fact a translation. This is visualized in the right plot of Fig. 3.
We have observed cases where deception can rotate or translate the reaction curve of the oblivious player, but it is important to note that these two phenomena cannot occur simultaneously. An important implication of the previous discussion is that the reaction curve of player d i is unaffected by deception if
). This property, detailed in the following lemma, characterizes a class of games that are intrinsically "deception-immune" under (17) and Lemma 2 (Deceptive-immune games): Consider an N -player quadratic game, and suppose that only players in K i are deceptive to player i. If δ ∈ Δ, then the following condition:
implies
Proof: Following the computations in (36), condition (38) implies that the reaction curve for player i satisfies
where the last equality follows from the fact that δ ∈ Δ implies
Hence, we prove the result. Although condition (38) "immunizes" player i's reaction curve to deception, player i can still be indirectly affected if other players are deceived. However, if all deceived players' objective functions satisfy (38), the game is immune to deception. Indeed, a sufficient condition for a fully deception-immune game is that rank Therefore, this game is immune to deception under the DNEseeking dynamics (6). Note that for the duopoly game studied in Example 1, the matrices Q 1 and Q 2 are invertible for any p, and there are no choice of parameters that can immunize the companies to deception.
For games with one deceiver and one oblivious player, it is possible to provide a more detailed characterization of the deceiving properties of the DNE-seeking dynamics (17) and (18).
In N -player games with one deceiver and one oblivious player, we can precisely determine how J i (x δ ) changes with δ, and whether the deceptive dynamics (18) allow deceivers to achieve any desired value J ref i . The following lemma is a first step in this direction. Lemma 3: Consider an N -player game with quadratic costs of the form (32), and let
where J i is a quadratic polynomial and f : R \ {-
with q 1 , q 2 , q 3 ∈ R. If q 3 = 0, then f is a bijection. Proof: We will assume without loss of generality that player 1 is a deceiving player d, so
Solving for e δ,2: and plugging into e δ yield the following:
This formulation, of course, only makes sense if [Q] d,1 is invertible, which is another assumption we will make. Indeed, even if [Q] d,1 is singular, given that -kQ is Hurwitz (which implies invertibility), we can always find some i such that [Q] d,i is invertible. Then, we can select e δ,1 to be the ith entry of e δ and partition e δ appropriately. Without loss of generality, we will make the assumption that the entry i = 1 satisfies this property.
Inspecting the d row of (40) to solve for e δ,1 , we obtain
where
Using (43), we directly obtain 42) into this expression leads to
where
which establishes the result. By leveraging Lemma 3, we can now characterize the structure of the set of attainable costs Ω for SDSO quadratic games.
Theorem 2: Consider an N -player quadratic SDSO game with cost functions (32), D * = {1}, D 1 = {d}, and let J 1 be given by (44) and f be given by (39).
1) If ε 1 r 1,2 q 1 q 3 > 0, then
2) If ε 1 r 1,2 q 1 q 3 < 0, then
Proof: Since there is only one deceptive player, we have δ = δ 1 . Using the definition of ξ in Definition 3, and the result from Lemma 3, we obtain that
where r i,j is defined in (45). The result follows now directly from Definition 3. Remark 5: Using these results, we obtain that for the duopoly of Example 1, Δ = (-∞, 1.5) and Ω = (0, ∞). However, as J ref 2 → ∞, we have δ * → 1.5. So, as the deceiver gets greedier, the basin of attraction of the DNE shrinks.
Example 5 (On the geometry of attainable costs): Consider a two-player quadratic game with cost parameters We can use our previous theoretical results to compute the key properties of the emerging DNE. Specifically, using (34), we obtain Q = [1, 5; 0, 0] and B = [2; 0]. Similarly, Δ = (-7, 5 3 ), and using (42), we obtain e δ = e δ,1 Φ, where Φ = [1 -0.5] and e δ,1 = 4δ(-1.5δ + 2.5) -1 . It follows that player 2 can rotate the reaction curve of player 1 around the point -Q -1
1 b 1 = [-1.286; -0.143]. Lastly, we have J 2 (e δ,1 ) = 3e 2 δ,1 -8e δ,1 + 0.5, which achieves a minimum of -4.83 at e * δ,1 = 4 3 → δ = 5 9 . Using Theorem 2, we can compute the range of attainable J 2 values, which is Ω = (-4.83, 31.64).
In words, the result of Theorem 2 characterizes the level of profits that players can achieve via deception in quadratic games when there is only one deceiver and one oblivious player. Since, in practice, the parameters of the game are unknown, this characterization is only relevant to establish viability for deception. Note that if J ref is not moderate, one might have
∈ Ω, and then instability can emerge, i.e., greedy deception might lead to instability.
2) Benevolent Deception: In the duopoly example, it can be verified that setting J ref 2 = 1000 shifted the NE to a position more favorable for company 2 but less favorable for company 1. However, in some cases, deception can also benefit oblivious players. This setting is known in the literature as benevolent deception [37], and it can also emerge under the DNE-seeking dynamics ( 17) and ( 18) with an appropriate choice of J ref i in (18).
To study benevolent deception, note that the cost functions in the duopoly game, evaluated at the DNE, can be written as follows using (43)
δ,1 + 33.3e δ,1 + J 2 (x * ). To improve both payoff functions, δ must satisfy δ ∈ {δ : -2.5e 2 δ,1 + 33.3e δ,1 > 0, -1.25e 2 δ,1 + 33.3e δ,1 > 0} = 0, 0.75) which is consistent with the fact that in Example 1, the desired value J ref 2 = 1000 was achieved with δ = 0.7929 ∈ (0, 0.75). To characterize the values of J ref 2 that lead to benevolent deception, we can compute the set J 2 (g((0, 0.75))) = (222.2, 888.8), where g(δ) is the DNE (from Lemma 1). It follows that for any J ref 2 ∈ (222.2, 888.8), the seeking dynamics ( 17) and ( 18) will stabilize a DNE that leads to a better payoff for both players. These ideas can be generalized to an N -player setting. Using (44), let F i (e δ,1 ) := J i (e δ,1 ) -J i (x * ) = r i,2 e 2 δ,1 + r i,1 e δ,1 and note that F i (0) = r i,1 . The following theorem establishes benevolent DNE seeking whenever player 1 is the deceptive player and player d is the oblivious player.
Theorem 3: Consider an N-person noncooperative game with cost functions (32) and players implementing the DNE-seeking dynamics (17) and (18), where n = 1, n 1 = 1, and d 1,1 = d. Let M denote a subset of players with cost functions satisfying sgn (r 1,1 ) = sgn (r i,1 ) ∀i ∈ M.
Suppose ε 1 r 1,1 q 1 q 3 < 0. Then, Ω is nonempty and there is a nonempty subset Ω * ⊂ Ω such that for each
Proof: First, we assume that r 1,1 > 0, and the r 1,1 < 0 case is nearly identical. This means that F i (0) > 0 for each i ∈ M ∪ {1}, so we can find some R > 0 such that F i (e δ,1 ) < 0 whenever e δ,1 ∈ (-R, 0), ∀i ∈ M ∪ {1}. We also have
which is negative by our assumptions, so we can find R * > 0 such that ∂ξ 1 ∂δ < 0 for all δ ∈ B R * (0) ⊂ Δ. We can define the following set:
which is nonempty since f is continuous and strictly monotone in a neighborhood of 0. We can then let Ω * = J 1 (E), which completes the proof.
To provide more insight on our results and show their application in larger multiplayer games, we consider a three-player quadratic game with cost functions having parameters defined in the caption of Fig. 4. The pseudogradient parameters are given by
If player 1 is deceptive to player 3, we have
An application of the Routh-Hurwitz criteria yields Δ = (-3.315, ∞), and from the proof of Lemma 3, we also have Φ = [1; 1.55; 10.86] and f (δ) = -3.6δ(1.21δ + 4) -1 . We set ε 1 > 0, and with Proposition 2, we obtain Ω = J 1 ((-0.629, ∞)) = (1.04, ∞). Furthermore, we also have r 1,1 = 68.3, r 2,1 = 42.6 and r 3,1 = 15.8. When ε 1 > 0, the conditions of Theorem 3 are satisfied, which guarantees the possibility of benevolent deception. We also have J 1 (x * ) = 22.5, so if player 1 chooses J ref 1 = 5, which is achieved at δ = 0.454, it can be verified that each player's cost function improves when the NE is moved to the stable DNE. Moreover, it can also be verified that the DNE is a true NE of the deceptive game. The results are verified and illustrated in Fig. 4.
In this section, we study an important question that can emerge in systems with more than one deceiver and oblivious player: What happens when two players are deceptive to each other? This situation is refer to in the literature as mutual deception [38]. This is a special case of the generalized deception considered in Theorem 1, but it raises some interesting questions.
To study mutual deception in noncooperative games, we focus on two-player games with exploration policies given by
In this case, the average dynamics of the system are given by ( 35) with δ = [δ 1 δ 2 ] and
We let each player i update δ i via the first-order integrator dynamics δi = εε i J i (x) -J ref i where ε > 0. In this case, by direct computation, we can observe that the vector
for which the following three properties hold:
1) -kQ δ * is Hurwitz; 2)
3) The following matrix is Hurwitz:
To illustrate these ideas, we revisit the duopoly example when company 1 is also deceptive to company 2.
Example 7 (Duopoly Game With Mutual Deception): For the duopoly game studied in Example 1, we show that the effect of deception of company 2 on company 1 was reflected on a modified cost J1 with an inflated sales function. Using similar computations, it can be verified that if company 1 is also deceptive to company 2, the perceived cost of company 2
Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on December 05,2025 at 23:04:58 UTC from IEEE Xplore. Restrictions apply. Fig. 5. Left: Profit convergence in a duopoly game under mutual deception using first-order deceptive dynamics. Center: Profit convergence in a duopoly game under (mutual) deception using second-order deceptive dynamics. Right: trajectories of δ in a mutually deceptive duopoly with first and second order tuning dynamics on δ.
becomes
where
2p . In (49), company 2's perceived cost has now a distorted sales value s 2 that depends on deceiving prices x1 and x2 . Note that the resulting quadratic game can be written as (32) with
Suppose the companies implement (18) with J ref 1 = 1200 and J ref 2 = 1800, leading to δ * 1 = 0.459 and δ * 2 = 0.848. With ε = 0.001, ε 1 = 1, and ε 2 = 1 2 , the second condition of Definition 3 leads to
which is Hurwitz. It can also be verified that -kQ δ * is Hurwitz. Thus, the solutions of the closed-loop system converge to the DNE. This can be visualized in the left plot of Fig. 5, where the DNE-seeking dynamics used a = 0.05, k = -0.03, ω 1 = 7877.75, and ω 2 = 7436.5. This example also showcases the possibility of benevolent deception and mutual deception occurring simultaneously.
The first-order deceptive dynamics (18) are not the only dynamics of the form (7) that can be studied for the purpose of systematic deception. In particular, we now consider the following deceptive dynamics:
where G i,2 > G i,1 > 0 are tunable gains. Note that the choice G i,1 = G i,2 reduces (51) to the first-order dynamics (18). In essence, the second-order dynamics (51) incorporate a phaselead compensation mechanism that incorporates integral action plus an approximate proportional term to improve transient performance. This improvement can be observed in the center plot of Fig. 5, where we simulated the duopoly game with deception using (51) instead of the integral deception mechanism (18). The following theorem formalizes the stability properties of the deceptive NE-seeking dynamics (17) with second-order deceptive dynamics (51). Theorem 4: Suppose that Assumption 1 holds, and consider the DNE-seeking dynamics ( 17) and (51) with J ref ∈ Ω and J i satisfying Assumption 2 for all i ∈ [N ]. Then, there exists ε * such that for all ε ∈ (0, ε * ) there exists a * such that for all a ∈ (0, a * ) there exists ω * such that for all ω > ω Proof: After obtaining the average system with τ = ωt, we can apply the time scale transformation τ * = ετ to obtain
If J ref ∈ Ω, then (53) has an exponentially stable equilibrium point * ∈ Δ. Now, setting y = zz * , we obtain the boundary layer system
where Λ * is a n × n diagonal matrix with the (i, i) entry being 1 -G i,2/ G i,1 . We see that (54) is a cascade, and y 2 = 0 is an exponentially stable equilibrium for (54b). Substituting into (54a) gives
which is exponentially stable at y 1 = 0 uniformly in ˜ ∈ B R * ( * ) for some R * > 0. At this stage, the system reduces to the system in Theorem 1 but with ζ * = [g( * ), * , * ] .
We now study deception in games that admit non-quadratic cost functions J i . Specifically, we now consider games where each player's objective function is of the following form:
where c i : R → R is twice differentiable and strongly convex, and l i : R N -1 → R is linear. These types of games are often referred to as aggregative games, and they are also common in the literature of NE seeking problems in noncooperative games, e.g., [39], [40], and [41].
In aggregative games, the ith entry of the pseudogradient is given by
where l i can be written as
For convention, we will use α k,k = 0 for k ∈ [N ]. Under suitable conditions on l i , aggregative games are strongly monotone (i.e, G is a strongly monotone operator). To see this, let κ i > 0 denote the strong convexity parameter of c i . Setting z := xy, we obtain
, it is easy to see that the aggregative game is strongly monotone with κ ∈ (0, min j K j ) provided K j > 0∀j. Therefore, we make the following assumption on the game.
Assumption 3: The N-player aggregative game with cost functions (55) is κ-strongly monotone.
Let each player i ∈ [N ] choose its action according to the strategy (1), except for player d, who we assume is deceptive and therefore implements (6a) to deceive n d players in the set D = {d 1 , . . ., d n d }. Using the same steps as in Section IV, under Assumption 1, the average dynamics of u are given by u = -kG(ũ) -kδΨ(ũ) + O(a)
where Ψ(u) ∈ R N and where the d i th entry of Ψ(u) is now given by ∇
while all the other entries are equal to 0. As before, we first disregard the O(a) perturbation term in (58) to proceed with our analysis. We obtain the nominal dynamics u = -kγ(ũ, δ), where γ(ũ, δ) := G(ũ) + δΛũ, with Λ being a diagonal matrix with diagonal entries equal to zero, except for the (d i , d i ) entries, which are equal to α d i ,d . Note that the change that results from deception in the average dynamics corresponds to the added term -kδΛũ.
In particular, unlike the quadratic case, the effect of deception in the reaction curves of nonlinear aggregative games is not any more a rotation or translation, but rather a complex nonlinear transformation that can even induce multiple critical points for the pseudogradient of the deceptive game. This behavior is illustrated in Fig. 6 for a two-player aggregative game with cost functions
where player 1 is deceptive to player 2.
To study the monotonicity properties of the induced deceptive aggregative game, we first consider the case where δ is fixed. Using again z := xy, the mapping γ satisfies
Since, by Assumption 3, the nominal game is strongly monotone, to guarantee strong monotonicity of the deceptive game, we just need to guarantee the condition K i + δα i,d > 0 ∀i ∈ D. To study the set of points δ that satisfy this condition, which we now denote Δ, without loss of generality, we can assume that α i,d = 0∀ i ∈ D, since otherwise, the 0 cases will have no effect on such set. By direct computation, we obtain the following. Lemma 4: For an N -player strongly monotone aggregative game where D * = {d} and D = {d 1 , . . ., d n d }, the following estimate of Δ holds:
where δ -and δ + are given by
The conditions of Lemma 4 provide some (conservative) estimates on the values δ the deceiver can use to influence the game without loosing the strong monotonicity property.
2) When Can the Deceptive Player Benefit?: Since the main goal of deception is to obtain better profits (when possible), we now address the following question: When can a player in an aggregative game use deception to improve their own cost while maintaining closed-loop stability? To address this question, fix δ * ∈ Δ and pick x * such that γ(x * , δ * ) = 0. Computing the Jacobian of γ with respect to x, we obtain
where the matrix Ξ takes the form
Since γ(•, δ) is strongly monotone for all δ ∈ Δ, it follows that D x γ(x * , δ * ) is invertible. Then, using Lemma 1, we can obtain a function g ∈ C 1 (Δ, R N ) which, by the implicit function theorem, also satisfies
where g is understood to be componentwise differentiation with respect to its argument. Let x * denote the nominal NE of the averaged game dynamics (disregarding the O(a)-perturbations) without deception, i.e., when δ = 0, and let Ξ * := Ξ(x * ). By inspecting (62), we can derive the following result, which guarantees DNE seeking with the deceptive player d always improving its payoff. then there is a nonempty subset Ω * ⊂ Ω such that for each J ref d ∈ Ω * , it follows that J d (u * ) < J d (x * ), where ζ * = [u * δ * ] is the point generated by Theorem 1. Proof: We know that x * satisfies G d (x * ) = c d (x * d ) + l d (x * -d ) = 0 → l d (x * -d ) = -c d (x * d ). Then, using (55), we obtain J d (x * ) = c d (x * d ) + l d (x * -d )x * d = c d (x * d )c d (x * d )x * d =: Jd (x * d )
where Jd : R → R. We can differentiate to extract some information about the behavior of (63) In particular, this tells us that no matter the value of x * d , there is a "direction" such that J d decreases when x * d is moved in that "direction." Since player d seeks to minimize J d , it is most desirable to find δ ∈ Δ such that |x * d | is maximized. As we have demonstrated above, we can use the implicit function theorem to obtain g ∈ C 1 (Δ, R N ) such that ũ = g(δ) is the DNE of the unperturbed (58) for δ ∈ Δ and g (0) = -(Ξ * ) -1 Λx * . Since ε d ((Ξ * ) -1 Λx * ) d x * d > 0, we know that g d (0) = 0, so by observing (63) and (64), we know that there is some open interval E 1 ⊂ Δ such that J d (g(δ)) < J d (x * )∀δ ∈ E 1 , where E 1 is either of the form (-R, 0) or (0, R) for some R > 0. Furthermore, by continuity we can also find an open neighborhood E 2 of 0 such that g d (δ)g d (δ) > 0∀δ ∈ E 2 . Let E := E 1 ∩ E 2 , which is also an open interval. Then, we set Ω * := (inf δ∈E J d (g(δ)), J d (x * )), which completes the proof.
From the proof of Theorem 5, the expression in (64) can be used to establish the following Corollary for two player games.
Corollary 1: Consider a two-player strongly monotone aggregative game where player 1 is deceptive to player 2. Let (δ, δ) ⊂ Δ such that 0 ∈ (δ, δ), where δ, δ are given by (61). Furthermore, assume x * 2 = 0. Then, at least one of the following holds:
1) J 1 (g(δ)) is strictly decreasing on (0, δ);
2) J 1 (g(δ)) is strictly increasing on (δ, 0); where g(δ) = x δ is obtained from Lemma 1. Proof: In this setting, we have γ(x, δ) = c 1 (x 1 ) + α 1,2 x 2 c 2 (x 2 ) + α 2,1 x 1 + δα 2,1 x 2 .
(65)
It follows that g 2 (δ) is injective. Indeed, suppose there exists δ a , δ b ∈ Δ with δ a = δ b and g 2 (δ a ) = g 2 (δ b ). Then, the top entry of (65) implies g(δ a ) = g(δ b ), and the bottom entry gives (δ aδ b )α 2,1 g 2 (δ a ) = 0, which implies g 2 (δ a ) = 0. But this means g(δ a ) = x * is also an NE of the nondeceptive game, which contradicts the assumption that the NE is unique. Then, g 2 (δ) is strictly monotone on Δ, and since the top entry of ( 65) is a strictly monotone curve in the R 2 plane, we also conclude that g 1 (δ) is strictly monotone on Δ. By combining this with the observation from (64) (but replace x * with we the result. This result suggests that one viable strategy for the deceiver in a two-player aggregative game is to tune δ monotonically. In particular, if the conditions of Theorem 5 are satisfied and the deceiver is able to improve their cost by perturbing δ in some "direction" away from 0, then they can continue tuning δ ∈ Δ in that same "direction."
Consider a two-player aggregative game with cost given by (59).It is straightforward to verify that κ 1 = κ 2 = 2, α 1,2 = 2, and α 2,1 = 1.1. It can also be verified that this game is strongly monotone since κ j -|α 2,1 +α 1,2 | 2 = 2 -|3.1| 2 > 0. Suppose player 2 is deceptive to player 1. Then, we can compute G and γ as follows:
3 1 + 2x 1 + 2x 2 e x 2 + 2x 2 + 1.1x 1 , γ = 4x 3 1 + 2x 1 + 2x 2 + 2δx 1 e x 2 + 2x 2 + 1.1x 1
and we also have that Δ = (-0.225, ∞). Note that setting the second component of γ equal to 0 results in a monotonic curve in the R 2 plane. That is, as x 2 increases, we must have that x 1 decreases. This relationship would of course be reversed if α 2,1 were negative. Fig. 6 presents a visualization for how deception affects the reaction curve for player 1in this setting. An interesting observation is that, similar to quadratic games, all the reaction curves of the oblivious player intersect at a single point. However, in the aggregative game considered in this example, the "transformation" induced by dynamic deception on the reaction curves is not anymore a rotation. The shared point in this example is the point on player 1's reaction curve where x 1 = 0, which is 0. In this case, player 2 sets J ref 2 = 0.605, achieved at δ = -0.22 ∈ Δ. The convergence of i and J 2 are visualized in Fig. 7. Additional analytical and numerical examples can be found in [42].
We introduced the problem of model-free NE-seeking with deception for noncooperative games with finitely many players. The setting considered incorporates oblivious and deceiving players, and studies the stable behaviors that emerge under a class of model-free (or payoff-based) algorithms that rely on simultaneous exploration and exploitation policies implemented in games with asymmetric information. The geometrical and structural properties of the induced deceptive games and deceptive Nash equilibria were studied, as well as the stability properties of the dynamics under benevolent deception, mutual deception, and using high-order deceptive dynamics. Our results open the door to several new research questions at the intersection of adaptive and learning systems, and deception in game theory.
Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on December 05,2025 at 23:04:58 UTC from IEEE Xplore. Restrictions apply.