Single-agent Poisoning Attacks Suffice to Ruin Multi-Agent Learning
Authors: Fan Yao
Yuwei Cheng
Ermin Wei
Haifeng Xu
Venue: ICLR 2025 Poster (2025)
Keywords: Multi-agent learning
reward poisoning attack
Nash equilibrium
monotone game
convergence
robustness
Primary area: learning on time series and dynamical systems
TL;DR: Characterize efficiency and robustness trade-off for multi-agent learning algorithms

Abstract: We investigate the robustness of multi-agent learning in strongly monotone games with bandit feedback. While previous research has developed learning algorithms that achieve last-iterate convergence to the unique Nash equilibrium (NE) at a polynomial rate, we demonstrate that all such algorithms are vulnerable to adversaries capable of poisoning even a single agent's utility observations. Specifically, we propose an attacking strategy such that for any given time horizon $T$, the adversary can mislead any multi-agent learning algorithm to converge to a point other than the unique NE with a corruption budget that grows sublinearly in $T$. To further understand the inherent robustness of these algorithms, we characterize the fundamental trade-off between convergence speed and the maximum tolerable total utility corruptions for two example algorithms, including the state-of-the-art one. Our theoretical and empirical results reveal an intrinsic efficiency-robustness trade-off: the faster an algorithm converges, the more vulnerable it becomes to utility poisoning attacks. To the best of our knowledge, this is the first work to identify and characterize such a trade-off in the context of multi-agent learning.

Published as a conference paper at ICLR 2025
SINGLE-AGENT POISONING ATTACKS SUFFICE TO RUIN MULTI-AGENT LEARNING
Fan Yao
Yuwei Cheng Department of Statistics University of Chicago Chicago, IL 60637, USA
Department of Computer Science University of Virginia. Charlottesville, VA 22904, USA
fy4bcevirginia, edu
ywweicheng@uchhicaggooo edu
Ermin Wei
Haifeng Xu
Electrical and Computer Engineering Industrial Engineering and Management Sciences Northwestern University
Department of Computer Science University of Chicago haif saffenxxuuuchicago.com edu
ermin. wei www.weeeeoooooi wwwooooeetteerncc..
ABSTRACT
We investigate the robustness of multi-agent learning in strongly monotone games with bandit feedback. While previous research has developed learn- ing algorithms that achieve last-iterale convergence to the unique Nash equilibrium (NE) at a polynomial rale, we demonstrate that all such al- gorithms are vulnerable to adversaries capable of poisoning even single agent's utility observations. Specifically, we propose an attacking strat- egy such that for any given time horizon T, the adversary can mislead any multi-agent learning algorithm to converge a point other than the unique NE with a corruption budget that grows sublinearly in P. To further un- derstand the inherent robustness of these algorithms, we characterize the fundamental trade-off between convergence speed and the maximum tol- erable total utility corruptions for two example algorithms, including the stato-offthe of-thc-artt- one. Our thcoretical and empirical results reveal an intrin- sic robbustess tradc-off:: the faster algorithm converges, the more vulnerable becomes to utility poisoning attacks. the best of our knowledge, this is the first work to identify and characterize such trade-off in the context of multi-agent learning.
INTRODUCTION
In recent years, multi-agent learning (MAL) systems have become increasingly prevalent, finding applications in diverse fields such autonomous systems, distributed optimization, and economic markets Leo et al. 2014 Shalev-Shwarts et al. 2016 Jin et al. 2018 Qiu
let al. 2021 Zhou et al. 2021 Wu et al. 2022 These systems, characterized by agents act- ing independently to maximize their own utilities a non-cooperative environment, offer significant potential but also introduce unique vulnerabilities to potential adversarial at- tacks. Consider, for example, autonomous vehicles that communicate coordinate traffic flow or financial trading algorithms that interact to optimize individual profits (Sharif & Marijan 2022: Ataicfard & Hemmati] 2023 Shah al., 2024). In both cascs, cach agent (vehicle or trader) aims to maximize its own utility without direct collaboration. However, a single compromised licious agent can significantly influence the overall outcome. While it may be difficult for an adversary to directly allack or control multiple agents, targeting single vulnerable or insider agent can be more feasible (Lin et al., 2020). This raises an intriguing question of whether adversary still create disruptive outcome by simply poisoning the utility of one agent.
these systems
be highly susceptible
manipulation,
ma-
"Equal contribution.

---

Published as a conference paper at ICLR 2025
This scenario-wil a single agent in MAL system is targeted for utility poisoning attack presents a new and critical challenge. Prior research has primarily focused on two related but distinct areas: ad adversarial attacks on individual agents in online learning
environments (Bogunovic et al.)
2021a Jun et al.
2018:
Garcelon et al. 2020), and many-
agent attacks on MAL systems McMahan et al.
Guo et al. 2021 [Wu et al. 2023 2023 Liu & Laij 2023). However, the impact of single-agent
2024
Ma et al. 2021; Zhang et al.
attacks specifically in the multi-agent learning context remains underexplored. Tn this work, we address this gap by investigating the robustness of MAL dynamics against single-agent utility poisoning attacks. We show that even when one agent is compromised, the system can be disrupted, revealing stark vulnerability that has been overlooked in prior studies.
To study the effect of single-agent poisoning in multi-agent systems, we use NE-finding dynamics in monotone games
benchmark. Monotone games (Rosen 1965], which include well-known models like Cournot competition (Cournot 1838) Kelly auctions (Kelly
et al. 1998), , and Tullock contests [Tullock] 2008), represent broad class of multi-agent
strategic systems. In these games, agents' utility functions are concave, and many well-
established MAL dynamics converge to their unique NE (Even-Dar et al. 2009 Farina
al. 2022 Bravo al. 2018 Ba et al., 2024 (Tatarenko Kamgarpour 2020
Cai & Zheng
2023 making them ideal benchmarks ks for studying the effects of single-agent poisoning
system-wide behavior.
Our theorctical results demonstrate that single-agent poisoning attacks can drive the dy- namics away from the original NE, using an imperceptible, sublinear budget with respect to the time horizon. This holds for all MAL algorithms in this setting. We also investi- gale the robustness of two representatives of such MAL algorithms (Ba et al. 2024 Bravo let al. 2018) and show that by sacrificing convergence speed, one can increase the system's tolerance corruption, revealing a fundamental trade-off between efficiency and robust
Our contributions can be summarized as follows: (1) We propose a utility poisoning strategy that can mislead any MAL dynamics in strongly monotone games to converge to new NE with a sublinear corruption budget, even when only targeting a single agent. (2) We analyze the robustness of MAL algorithms against general utility poisoning attacks, showing that adjusting the learning rate introduces inherent robustness. (3) Our findings uncover an riobinccyroouutness trade-off in MAL dynamics, where faster-converging dynamics are more vulncrable utility poisoning. To the best of our knowledge, this the first work to reveal this tradc-off in multi-agent lcarning systems.
Related Work. Adversarial altacks on multi-agent learning oflen termed "steering" or "policy teaching" have been extensively studied under various assumptions about the attacker's 's knowledge, objectives, and stateggess. For instance, Liu & Lai (2023) show that in certain Markov games, neither action poisoning nor reward poisoning alone can be both efficient and successful, even with complete knowledge of the environment. ("white-box" setting), highlighting challenges in designing effective attacks. Similarly, Wu et al. (2023) investigate reward poisoning attacks on offline multi-agent reinforcement learners, demon- strating how adversaries can manipulate outcomes in offline settings.
Another line of research focuses on designing incentives to guide multi-agent dynamics to- ward a desirable equilibrium, known as "equilibrium steering" (Zhang el al.] 2023 Canyak- maz et al.) 2024 Huang et al. 2024). Ma et al. (2021) consider game redesign where a designer, operating in whitte-bxx setting, aims to induce players choose targeted actions in a normal-foor form game using sublinear cost, assuming the players employ no-regret learn- ing. The most relevant work to ours is /hang et al. (2023), which shows that a sublinear total incentive can induce a predetermined equilibrium against no-regret agents. However, their approach can only steer the game to an existing equilibrium and cannot achieve a non-equilibrium outcome without incurring a cost of I(T).
PRELIMINARIES
Our study focuses on strategic games with a finite number of agents |m| = f1....,............. .n) and continuous action sets ( associated with agents i E [n]. During play, each agent i chooses an action (i.e., a pure strategy) æ; E X C Rdd, where d, is the dimension of action space of agent i, and forms the joint action profile
(æz;rr;) (#1,'.. v.)) We
2

---

Published as a conference paper at ICLR 2025
denote d maXig[n] de- Let X' = IT:= N; be the game's strategy space, and each agent's reward is determined by a utility function WN XX' + R. Without loss of generality we assume the range of each uy is a bounded region [o, 1]. We do not require agents know their utility functions and only assumies that they can observe the point-wise leedback uz(m), also known as bandil feedback in online learning literature. Such a game is denoted by tuple = ((n, Jnn,& X, {ur]==) I==). The commonly adopted solution concept for such strategic games is Nash equilibrium (NE), an action profile where no agent can deviate unilaterally to improve her utility. The formal definition of NE is given by the following:
Definition 1. A joint strategy profile x' = (zi...., xrt)) forms a Nash equilibrium (NE) of game 9, if for every agent i, ai 18 best response to the opponents' stralegies a",; formally,
uz(ot,, x=1))= 2 ui( for every na X.
2.1 MONOTONE GAMES
Much of this paper's theoretical development focuses on an important class games called strictly monotone games (strictly MG). This focus is due to at least two reasons. First, from computational perspective, strictly monotone games are one of the most general classes of continuous games that admit efficient algorithms for NE; it includes most popular continuous games such as Cournot competition (Cournot 1838), Tullock contest (Tullock 2008 He
et al. 2024 and its variants that model content crcation competitions Yaao et al. 2024a b
Additionally, our framework encompasses all strictly convex-concavs zero-sum games and any game with strictly concave potential. Second, strictly monotone games turn out to admit fast converging (to NE) multi-agent learning algorithms (Bravo et al., 2018 Both conditions are important for our theoretical analysis. The concept of "monotomicty"" first introduced by Rosen (1965), refers games where each agent has a concave utility function, along with global condition known as diagonal strict concavity (DSC). A stronger version of the DSC condition defines a sub-class known as strongly monotone games. Formal definitions of these are provided below.
Definition 2 (Strictly/strn /strongly monotone games). A continuous malti-agent game
(nn, (X,,; (u:); )-1) is strictly monotone if for any x = (æ1,-.. ,nn, (x', ' r²)) E
X, it satisfies the diagonal strict concavity (DSC) property:
(aa (a())):)T(cc: ".;((((('), x';1) - vi( x-i)) < 0,
(2)
where (x(x)= = Vv, (xx is the first-order derivative of u; with respect to xt. In addition, the game G is 3-strongly monolone if Ei=( x.) (v:(1) (' -' v. x =)) < -B| 10
When discussing strongly monotone game in this paper, we treat | as a small constant and sometimes omit it in bounds unless there is need to emphasize the dependence on 3. Notably, the DSC property readily implies the strict concavity of uj with respect to ay for
any fixed x- This can be observed by taking x' = (œ), 1I--,, 2/, TR+1, x.,) in Eq. As result, the following best response mapping for each agent-k is well-defined"
Best response mapping:
(x & arg max xxEAx
(3)
Morcover, the following notion of game Hossian matrix will be useful throughout the paper:
Game Hessiam: Hig (
(4)
The following smoothness property of agents' utility functions will be useful for our analysis. Definition 3 (Second-order I-smooth utilities). Given any game 9, we say an agent k's utility function us srcond-order L-smooth if there erists a feasible set F S ldd such that for any å E F, the following function ( 8) 1dnd + Rd defined as
UR (K + ò, x
ux(x x.
ha (x:; 8)
(5)
||
is I--iipschitz continuous; that is, for any x. xx E X, it holds that
[1; (a' 5)]l < L| x' Because the maximizer of a strictly concave function always exists and is unique.
(6)
3

---

Published as a conference paper at ICLR 2025
Second-order smoothness requires that, for given agent k, while holding other agents' strategies fixed, the marginal change in k's utility with respect to her own strategy ay is Lipschitz continuous with respect to the joint stralegies æ of all agents. This is relatively mild assumption, as it. essentially demands the smoothness of the second-order derivatives of the agent's 's utility. To see this connection, by letting 6 + O, we have h4 (2; 6) + d'u 6 Hence, in this case Condition Eq. ( becomes the Lipschitz contimuity on the Hessian matrix d'us of ha, which is why it is called second-order smoothness. dzz
day T
A lew remarks are worth mentioning. First, our attack poison's only a single agent and its success is guaranteed so long as this single agent's 's utility is second-order smooth. Second, the smooth parameter in Definition 3 turns out to affect how "controllable" the attack outcome is. Our results will show that clever adversaries would tend to poison an agent with small L parameter. Third, many well-known strongly monotone games exhibit this smoothness property. For example, the n-agent Cournot competition is second-order 0- smooth, where n-agent Tullock contest is second-order O( ((yn)-smooth (see Appendix A for full descriptions of these games and proofs of these claims in Proposition 2 and 3
2.2 THE (cL))-MULTIAGENT LEARNING DYNAMICS UNDER BANDIT FREDBACK
Monotone games are known to have a unique Nash equilibrium, hence a substantial body of recent. work develops equilbrrim-conveerinng dynamics, including (Bravo et al. 2018 Tatarenko & Kangarpour] 2020 Cai & Zheng, 2023 Ba et al. 2024). These studies demon- strate that in a strictly monotone game cach agent independently follows such an algo- rithm, the joint strategies of all agents converge in last iterate to the NE at a polynomial rate. Among these, we are particularly interested in algorithms that operate in bandit feedback environment, where agents do not have access to their utility functions neither utility gradients, and can only observe the utilities (possibly noisy) resultant from the ac- tions they (ake at that round. This leedback setting is challenging yet realistic, as it reflects un-coupled learning situations where agents are unaware of their opponents' existence and simply optimize their own utilities selfishly. The following notion is crucial to our analysis.
Definition ((a, MAL Dynamics). We say a (possibly randomized) multi- multi-agent learning (MAL) dynamics A = (A1,... An) for n-agent game G with bandit feedback is an (a.p)- MAL dynamics if when each agent uses algorithem A, to determine her strategy x² at time t, then their joint strategy sequence {- converges to a Nash Equilibrium x² in the following sense: there exists positive constants C,To such that for any t To we have
El[(x - x x11 < CP. Po
(7)
In other words, an (a, MAL dynamics leads to last iterate convergence to some NE of the game G in the sense that the p-th power of the strategy profile difference, evaluated under the L2 norm, has a polynomial convergence rate a > 0. In the following section, shall see that the a,p parameter in (a, P)- algorithms fundamentally affects the algorithm's robustness to adversarial corruptions. In the literature of multi-agent learning for monotone games, various (a, -MLL dynamics have been developed. For instance, the Multi-Agent Mirror Descent with Bandit Feedback (MAMD) proposed by [Bravo et al. (2018) leads to ( 2)-MAL algorithm, while the Multi-Agent Mirror Descent with Self- Concordant Barrier Bandit Learning (MD-SCB) introduced in Ba et al. (2024) leads to (1. 2AL dynamies. Notably, while these designs often let every agent use the same learning algorithm, neither our definition of the (MAA) dynamics nor our designed attack later require this restriction
all we assume is that the learning dynamics converge.
3 VUINERABILITY OF MAL TO UTILITY POISONING IN MG
In this section, we examine the vulnerability of multi-agent learning (MAL) dynamics. Our main result is the design of single-agent utility poisoning attack, which is provably successful to any (a,P)-MAL algorithm for 8-strongly monotone games. Our results also quantitatively characterive how the attack costs and outcome depend on parameters 8 a, The risk of having a poisoned agent within a community is very realistic, hence our attack raises serious concerns regarding naively applying MAL dynamics to setting with potential
4

---

Published as a conference paper at ICLR 2025
adversaries. We conchude this section by showing how the attack can lead to worse outcomes when the adversary can poison even more agents.
3.1 POISONING A SINGLE AGENT SUFFICES TO STEER THE EQUILIBRIUM AWAY
We design an explicit implementation of such a utility poisoning attack, referred to the Single-agent Utility Shifting Attack (SUSA). SUSA first selects a victim agent & to poison, and computes corrupted utility function üy for this agent. Then during MAL process, at each round SUSA simply shift the realized utility agent h from uy to the üy with [ux- unl (hence the name "utility shifting"). The formal definition of SUSA is provided below.
attacking cost
Definition 5 (Single-agent Utility Shifting Attack). A Single-agent Utility Shifting At- tack (SUSA) against a strategic game instance G is specified by a tuple (k, S,), which implemented by the following two stages:
1. (Preparation Stage] Pre-compute a corrupted utility function for "victim agent" k: nR (ak, = (x + 5, xx + (ax
where A + R is a function depending on the joinl stralegy Ø- and ö E X
2. [Attacking Stage] During the execution of an MAL algorithm at round t, add a corruption
(0) (9) a = un (a a _k) ux =k)
to agent-k's 's ulilily observation.
In addition, we denole the corrupled game inslance as (kk 6, A), in which the k-th agent's s ulility funclion is replaced with üg.
A few remarks are worth clarifying. First, et is introduced after observing the current round action. This lype of corruption is often referred as "strong" corruption in the literature (Liu & Shroff 2019: Jun et al. 2018 Bogunovic et al. 2021b). Second, SUSA is applicable to any MAL learning dynamics in any games with continuous utility functions, though below we only show that the success of such attacks can be guaranteed for strongly monotone games under certain conditions. Third, SUSA only poisons agent k's utility observations and does not interfere with her actions, though the poisoning amount depends on an action shifting term d. Essentially, it makes & believe her utilities are drawn from a modified function ūj.
Notably, SUSA does not attack any other agents, but will nevertheless steer their equilibrium behaviors through influencing the victim k's behaviors. Since agents do not know their true utility functions but only observe the bandit feedback about utilitics, this form of corruption not only disrupts the sequential strategy updates of the victim agent k; but also influences the dynamical behaviors of all other agents involved.
The following Lemma reveals a nice property of SUSA. That is, if the larget game G is strongly monotone, SUSA preserves the strongly monotone property as long as the Iz-norm of the deviation ||ō0|2 upper bounded by a constant depending on the game parameters.
Lemma 1. Consider any 3-strongly monotone game (n, (M {u, H>>) uf is second- order I.- smothh,th then under SUSA the corrupted game G(k, 8, A) with ||51| < B/T. remains strongly monotone.
Lemma I indicates that the corrupted game preserves strong monotonicity as long as the norm of the shifting offset 8 is reasonably bounded. This is useful because MAL dynamics retains convergence in the corrupted game (still strongly monotone). As mentioned in Section 2.1, Cournot competition is O(1)-strongy monotone and 0-smooth, so SUSA using any preserves its monotonicity. In contrast, the Tullock contest is (())-strongy monotone but ((V7)-smooth, hence the adversary is limited to using ||0 < O(1/vR). This means that as the number of agents increases, it becomes more difficult for SUSA to preserve the monotone property. The proof of Lemma [ can be found in Appendix B.1
Our following main thoorem of this section, which formally characterizes SUSA's 's capability.
Higorously, we need extend the domain X ensure us (æx + 8, xx) is well-defined. In fact, any concave extension would suffice, and does not affect the validity of our theoretical results.
5

---

Published as a conference paper at ICLR 2025
Theorem 1. Let ((n, {K,}?-)- fuili=)) be any B-strongly monotone game (with unique NE x²) and A be any (o.p)-MAL dynamicss. Suppose viclim agent-k ulility function ug is second-order L-smooth. Consider SUSA(K, 6, A) constructed as
A(x_k. -u(BBR((-)))))
(BR -,
(9)
where ō is any vector satisfying |ö|12 < 3/L and (xx & max EX,, uy ug (1), xxk is the best response mapping of agent-k. Then the resulting dynamics induced by and SUSA(K, 5, A) converges to some x', such that
1. [Attack Success] The deviation to the original NE satisfies
- 2 /uppll//spppppple swpppspppppHaaa
[x",""],,
(10)
where pl (()())) represents the spectral norm of the game's Hessian Hg al æ, and
[x" denotes the segment (with a slight abuse of notation) Xē +1-A(11))x" [0,
2. [Sublinear Attack Costs] The expected total budget satisfies
T
ctl
S Co T
PTT,
(11)
where the constant Co CL1 +5) +2, L1 is the Lipschitz constant of all w.r.t. æ; and L2 the Lipschitz constant of victim agent k's k's best response BRg w.r.t. æ-k-
As described in Eq. (10 and Eq. [11 the success of a SUSA relies achieving two goals simultaneously: (1) steering the convergence to a joint strategy profile that is at least a constant distance away from the original NE, and (2) ensuring that the total budget required
(T). Theorem guarantees both even when the adversary only targets a single agent.
One might wonder, beyond the NE shifting distance guarantee Eq. (10) whether an adver- sary can have any control over the shifting direction, espocially if it aims to influence specific agents' strategies. Our answer is affirmative: although rigorously characterizing the direc- tion xx x² challenging, we can approximate it as Hg [ {][VRauu)) (see Appendix B.3 where H6 [:, k] is the k-th block column of the inverse of Hg, and Vasu is the Hessian of Un w.r.t. Tk. This suggests that if an adversary possesses some additional global knowledge about the game's Hessian Hg, it can further steer the NE deviation in a desired direction.
To get better sense of the attack success guarantee, we derive constants in Thcorem for and 3 Appendix
two examples as follows. The proof can be found in Proposition 2
Remark 1. For n-person Cournot competition, the corvesponding parameters Lo, L1, L and Hg specified Theorem satisfy
Lo -, = 0(1), L2 = O(vn), =(1), sup - O()),
=Ex
therefore, for an arbitrary 6, SUSA can induce an NE shift || x=112 2 O(n For n-person Tullock contest, we have
Lu = O -, 0 nn), sup {pl Hg (x))) O(n).
=
and thus for |,8|| < O(n SUSA can induce 1| - x 2 O(n 9). Both results are obtained within a total budget E EL= & 50(vTT'
pa
We observe that while some of the constants in the bounds are ((), some them inevitably depend on n and the specific guarantecs vary across different game structures. In our two examples, Cournot games are elearly more vulnerable One might also wonder the induced deviation from the original NE may be too small when gets large. As we will discuss in Scction 3.2 the adversary can improve the deviation in Eq. 11p by removing the factor sup p( H and may even force the NE deviation to an arbitrary direction if allowed poison multiple agents.
attacks compared Tullock games.
Next, we discuss the implications ions the necessary requirements in Theorem D which provide insight into why SUSA be successful. The first condition demands that the norm of

---

Published as a conference paper at ICLR 2025
the deviation ||ö]|, must be bounded by constant. This is to ensure that the corrupted game remains strongly monotone and thus allows A to converge to #", the unique NE of the corrupted game, as indicaled by Lemmn D The second condition provides an explicit construction of the offset function, which essential ial for maintaining a sub-linear total budget. In fact, the rationale behind the design of A is to satisfy that for the target agent-k xx)) = un (MRRRR (x= x.), where (2x(x=)) is the best response function for agent-k under the corrupted utility ug- In other words, regardless of the opponents' strategies, the best response of any agent under their corrupted utility ūy aligns with the intersection of ūg and the original utility ug. This means that as an agent gradually learns the best response to their opponents" stralegies particularly when converging to x* -he adversary's 's budget decreases to zero, ultimately resulting in a total budget that is sub-linear in T. The proof for Eq. (10) requires establishing a connection between the Jacobian of best response mapping and the game's s Hessian and applying Lagrange mean-value theorem for vector-valued functions (Hall & Newell 1979). The proof for Eq. (II) follows from careful analysis of the expected budget Bleell at each round. In fact, we can show that the same convergence rate applies to the corrupted game G and as the joint strategy approaches á at rate t"a Bi|c/[] decreases at rate t PFi. For detailed proof, please refer to Appendix B.2
and any æ-k E X-.. maxa,EM, arg maX (2, x+k) (2
3.2 POTENTIAL POWER OF POISONING MANY AGENTS
Theorem 1 demonstrates the significant impact of attacking even a single agent. A natural follow-up question is whether an adversary can gain additional power by poisoning multiple agents. While this is not the primary focus of our work-since it is unclear how realistic or feasible would be for an adversary to poison many agents- we provide preliminary evidence that such an adversary would indeed have significantly more influence. We illustrate this through an example in the Cournot competition, as detailed below.
Proposition 1. Under the same assumptions stated in Theorem 1 consider an adversary performing SUSA(K, 8k, Au) against all agents k E [n] in n-person Cournot competition. Then, the required attacking budget for each agent still bounded as Eq. (1I), and the shifted NE under allack salisfies x= - x= = H D8, where Hg is the game Hessian desined in Eq. 4 and D is diagonal block matria with the i-th diagonal block being the Hession of us w.r.t. It. As a result,
1. picking 5 = H-y can induce an arbitrary NE deviation direction v,
2. picking ô aligning with the direction associated with the largest eigenvalue of H. induces the largest possible NE deviation distance | x [l, which is at least | ||-
Although limited to Cournot games, Proposition 1 offers preview of the additional advan- tages of attacking multiple agents, namely more refined control over both the magnitude and direction of NE deviation. Compared to Remark [] allacking multiple agents increases the magnitude of the NE deviation from (1//n) to (I),, and allows for arbitrary directional deviation. We are able to derive a closed-form solution of ø* x² thanks to the quadratic utility function in Cournot games which yields a constant game Hessian and linear best response mapping. For more general game structures, we can show that similar results hold, albeit in an approximate sense, as a strongly convex function can always be approximated by a quadratic form, and the best response mapping can be linearized near x.. However, a. rigorous exploration of this is beyond the scope of our current work.
4 INTRINSIC TRADE-OFF BETWEEN EFFICIENCY AND ROBUSTNESS
Our main result in previous sections (i.c. Theorem 1 reveals an intriguing tradc-off between the officiency and robustness of MAL dynamics: the faster an algorithm converges (i.c., a larger a), the smaller corruption needed for inducing an NE shift. For simplicity, we name such outcome as NE Shifting Attack (NSA). While such trade-off is well-documented in single-agent online learning (Cheng el al., 2024), we are the first to identify it in the multi-agent context. In this section, we explore whether sacrificing the convergence rate of specific MAL dynamics can improve robustness against utility poisoning attacks. We focus on two dynamics: MD-SCB [Ba et. al. 2024), the fastest-converging state-of-hhe-ar. MAL
7

---

Published as a conference paper at ICLR 2025
algorithm, and MAMD (Bravo al. 2018 the foundational MAL algorithm for strongly concave gaies with bandit leedback.
Essentially, our key insight is that the robustness of these dynamics can be improved (i.e., become more resilient to NSA) by simply adjusting the learning rate. Theorem 2 shows how the learning rate of MD-SCB (see Appendix C.1 for details) influences its robustness against general utility poisoning attacks. Originally proposed by Ba et al. (2024), MD-SCB achieves an optimal convergence rate of O(d/VT) without adversarial attacks, choosing the learning rate ?)t x ビ- At each round t, we consider a general adversary who selects a set of agents Σ, to attack: any agent ï Σ, will receive an altered utility observation n(")) + (x,, c (z,) Theorem 2 highlights how the algorithm's 's convergence under such generic utility poisoning attack depends on both the learning rate d and the total attack budget p.
Theorem 2. Consider an adversury that allacks a set of agents i, at round with a total budget salisfying Ej=1 Eiez, l0g,8 S (1P) for all and some p E [0, By choosing learning rote sequence T7. rale of MD-SCB salisfies
2d t for sufficiently large T the last- convergence
E [||TT xx" ==1 I max
()
Specifically, EE || x 11 S O
ddT 26g ") can be achieved by choosing Φ 3 5)
Theorem 2 delivers a strong message: for a given sublinear total budget O even as + 1, we can always adjust the learning rate decay to recover last-iterate convergence, making MD-SCB absolutely resilient to NSA although at the cost of potentially slower convergence speed. The proof of Theorem _
quantifics the bias introduced by attacks the utility observations of the gradient estimator 6.0, and tracks the propagation of this bias throughout the convergence analysis (sce Appendix C.. We will later use similar approach to establish an analogous result for Algorithm 3 as well.
Theorem provides a potential defense strategy for an algorithm designer, assuming they can estimate the upper bound of the total corruption. To clarify the inherent trade-off between elficiency and robustness in MAL dynamics, we compare this result with our findings in Section
3 from a unified perspective. For this comparison, let ADV represent all possible utility poisoning strategies, and define the following quantily:
p(C, = inf {p E [0, 1][C with budget ((T)) always achieve NSA against A.),, sup(p E [0, 1|IC with budget O(T)) cannot achieve NSA against A.),
where C E ADV represents a generic utility poisoning adversary. Now, a fundamental question from both the attacker and defender's perspectives is to quantify the following two functions (with p = 2 fixed):
(a = inf
sup A), p+(a)= sup inf AEMAL( CEADV A).
(12)
CEADV AEMAM(..2)
Function (a) represents the optimal strategy of a utility poisoning adversary: for any MAL dynamics known to enjoy convergence rate a, (a) denotes the minimum budget level P required for NSA. In contrast, e+ (ax) describes the optimal defense from the perspective of the algorithm designer: given required convergence rate a, (a) identifies the most robust algorithun that can withstand NSA of level p from any utility poisoning adversary. The well-known max-min inequality also implies the following basic fact.
Fact 1. (a) 2 (a) for any a E 104].
Note that we restrict a E [0, 1l because a = 1/2 is proven to be the optimal convergence rate under p p= 2 in the non-corrupted setting [Ba et al. 2024). In general, one should expect strict incquality in this context (i.c., (a(a) > P+ (a)), unless p(C,A) has particular special properties. For instance, if p(C,.) is convex in C and concave in A, the equality must hold, as seen in the well-known minimax theorem from v. Neumann (1928); ; Sion (1958). In our problem, however, both C, A represent algorithms and it unclear how p changes w.r.t.
As NSA necessarily leads divergence, last-iterate convergence must imply resilience to NSA.
8

---

Published as a conference paper at ICLR 2025
C. and A. Thus, an intriguing open question remains: does the equality hold in Fact I In other words, does the adversary gain a strict advantage (i.e., P pa(a)) p+ (a)) by first observing the dynamics A and then designing the allack C?
To better understand the strength of the adversary, our main results in Theorems and 2 provide insights by establishing upper and lower bounds of P+)),, respectively, as summarized in Corollary [
Corollary 1. Given the definitions of (a) and p+(a) in Eq. 12 for some particular MAL algorithm Ao and adversary Co ADV, further define p(Ao(a)) = inf CEADV p(c,A Cl
Co),Co)= Ao(a)),
sup p = Ao, 2
where Ao(a) denotes algorithum Ao with set of hoper-parrmeetrs that guarantees M AL(a, 2) convergence. Then for ony a E [0, t). it holds that
20
1 a (.MD s p+(a)= p-(a) (4; 1
(13)
We defer the proof of Corollary to Appendix D.1 as it is straightforward: the three middle incqualitics follow directly from the definitions of p_, p_. and Fact [ The two outer incqualitics are derived from a restatement of Theorem 1 and 2 In fact. Theorem I quantifies the capability of a particular adversary (i.c., SUSA) and thus establish the upper bounds of p(a;; SUSA). Theorem 2 on the other hand, characterizes the robustness of a particular algorithm (i.e. MD-SCB), thus gives the lower bounds of p(MDDSCB(()).
Although the bounds in Corollary | are not light, they highlight intrinsic trade-off between efficiency and ro- bustness: MAL dynamics with higher convergence rates become more vulnerable- thee ruption, and adversaries need a smaller budget to at- tack them. Figure [ illustrates this trade-off. The yel- low dashed line represents p- (a); above it, a budget of O(T²) suffices for powerful adversary to induce NSA in any M ML((a, 2) dynamics. The red region, subset of this area, corresponds to the actual budget required for NSA using our specific attack strategy, SUSA. Con- versely, the blue dashed line represents (a); below it, the most robust M (AL 2) dynamics can withstand cor- ruption of O(T9) against any adversary. For a specific MAL dynamies like MD-SCB, the green region shows the budget within which it remains resilient to NSA. We only present p E [0.75, because the MAL. dynamics with the best convergence rate in such a setting (a = 0.25) (Ba) ct al. 2024) can withstand corruption level of p 0.75 (see Theorem 2). The three gaps in Figure correspond to three open problems: OP1. what is the most budget- adversary for any MAL dynamics; OP2. does an adversary have strict advantage by ob- serving the dynamics first and then design the attack C; and OP3. what is the most robust MAL dynamics resilient to any adversary? We left these for future research.
Rfliciency-oobusteess Trade-off
0.69
Vuleerall
they can withstand less cor-
0.85
MIMI
MAA
0.50
J.le
Redllent
OPS
0.75
Figure 1: Mustraaaionn of the four
quantities in Corollary 1 re- vealing the intrinsic efficiency- robustness trade-off under NSA.
Such an rofuutaesy trade-off extends to more general contexts. For example, the MAL algorithm MAMD (detailed in Algorithm 3 in Appendix C.4) exhibits a similar phenomenon. We establish a corresponding result in analogous to Theorem 2 in Proposition in Appendix C.4, showing how to adjust MAMD's learning rate to enhance its robustness. Moreover, this trade-off applies to a broader notion of robustness beyond just resilience to NSA attacks. In Appendix D we present similar results for stronger form of robustness that not only ensures resilience to NE shifting but also prevents any possible dampening of the convergence speed.
EXPERIMENTS
In this section, we validate our theoretical results from Theorem and Theorem by implementing SUSA against MD-SCB on n-person Cournot, games, w whose formal definition is given in Appendix A Additional results for Algorithm 3 are provided in Appendix
9

---

Published as a conference paper at ICLR 2025
Experimental Sctup: For the n-person Cournot game instance, we set 10, 0.05,
and the cost c, = for all agents i E [n]. The action space is set to X; = [0,50] and the unique NE of such games can be verified as क = 180 i x+I,
[n]. We let each agent run MD-
SCB with tha game size n E {10, 50, 1003. The learning rate schedule of MD-SCB is set to (m) x t == 8.0 = 0.5, 0.7,0.9), corresponding to convergence rates a 0.25, 0.15, 0.05, p when no attack is present. We implement SUSA against agent 1, with fixed 8 = 10.0. For each game instance specified by n and the attacked algorithm specified by the convergence rate a, we compare the dynamics' behavior both without attack and under SUSA, and report the actual total budget used.
The left panel of Figure plots the convergence curve of the L2 square error for n= 10, serving a sanity check to confirm that different learning rate schodules induce different convergence rates for MD-SCB in absence of an adversary. The middle panel shows the outcome of SUSA against MD-SCB with L2 distance between 3e and NE, The dashed lines display the convergence curve without the adversary, while the solid lines represent the dynamics under SUSA, with different colors indicating results for various game sizes n. As shown, for different values of n, the attacked dynamics exhibit divergence, as the solid lines saturate and stop decreasing, indicating that the dynamics are being steered to converge the induced NE deviation decreases with respect to n, which aligns with our theoretical predictions in Theoreu[] and Remark [] The right panel shows the cumulative attack budget C. = Er |cr| at each time step t against MD-SCB with different values of As the results indicate, although all exhibit a sublinear trend, a faster-converging dynamics (a 0.25) requires a smaller attack budget, corroborating our findings in Theorem 1 and Results for additional parameter settings are provided in Appendix
Result:
0.25, with the y-axis representing
a new point. Additionally, we observe that
Convergence with --10
Hé Manipu Power with 6.25
Comulative Atteck Budget with n=10
3000
1-1.5
190090
5000
2208
2000
730e 2200K 11500 1380e 27503
2300 2000
ri0e usee 12006 17590
Iteration
Figure 2: Left: square error of MD-SCB with varying convergence rates. Middle: square error of MD-SCB on different sizes of game instances against SUSA. Right: cumulative attack budget used by SUSA against MD-SCB with varying convergence rates. Error bars represent the 1-o region from 20 independent simulations.
DISCUSSION
In addition to the three open problems regarding the fundamental limits of attack efficiency and defense robustness raised in Section [ we discuss more potential limitations and future directions here. One limitation of our setting is that, although SUSA does not require the adversary to have full knowledge of the entire game (such as knowing every agent's utility function, as assumed in some prior literature (Ma et al. (002)), it does rely on the assumption that the adversary has complete knowledge of the victim agent's utility function. We believe this assumption can be further relaxed. A promising direction for future work is to enhance the applicability and practicality of SUSA by developing methods that assume the adversary has no prior knowledge of the victim agent's 's utility function and must instead learn it from observed trajectorios. Another key question we did not address the socictal impact of utility poisoning attacks, particularly its potential for "stocring for social good": : as although SUSA could be used by adversaries to induce a harmful NE, it also opens up opportunitics for a benevolent social planner to guide the system toward a better social outcome, simply by incentivizing a single agent. These intriguing open problems offer valuable avenues for future exploration.
A Acknowled lenowwedgmmet. This work is supported by Army Research Office Award W911 1-0030, ONR Award 400014-23-1-2002 and NSF Awards CCF-2303372, CNS-2030251,
10

---

Published as a conference paper at ICLR 2025
ECCS-2216970, CMMI-2024774, IIS-2128019. Fan Yao conducted this research while he visiting the University Chicago.
REFERENCES
Foozhan Ataicfard and Hadi Hemmati. Gray-box adversarial attack of deep reinforcement lcarning- based trading agents. In 2023 International Conference on Machine Learning and Applications (ICMLA), pp. 675-682. IEEE, 2023.
Wenjia Ba, Tianyi Lin, Jiawei Zhang, and Zhengyuan Zhou. Doubly optimal no-regret online learning in strongly monotone games with bandit feedback, 2024. URL https:
//arxiv.orgg www.oorg//bbbbaaeeeeeee abw/ 02856
Iiija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelli- gence and Statistics, pp. 991-999 PMTR, 2021a.
Iija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust. to adversarial allacks. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intellggncce and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 991 999. PMLR, 13- 15 Apr mlr wttpppeee//1///ooooooocc..... html
2021b. URL https::/proceeddi//
Mario Bravo, David Leslie, and Panayotis Mertikopoulos. Bandit learning in concave n- person games. Advances in Neural Information Processing Systems, 31, 2018.
Yang Cai and Weiqiang Zheng. Doubly optimal no-regret learning in monotone games. arxiv preprint 2xiiv23001131120, 2023.
Ilayda Canyakmaz, Josif Sakos, Wayne Lin, Antonios Varvitsiotis, and Georgios Piliouras. Steering game dynamics towards desired outcomes. orXie preprint ar arXiv:2404.000 2024.
Yuwei Cheng, Fan Yao, Xuefeng Liu, and Haifeng Xu. Learning from imperfect human feedback: tale from corruption-robust dueling, 2024. URL https://aaxiv wwwpiiv.rrrbbbb. 2405. 11204
Antoine Augustin Cournot. Recherches sur les Principes Mathématiques de la Théorie des Richesses. L. Hachette, Paris, 1838. URL https://gaalica. bnf fr/ ark: ark:
bpt6k8804262
Eyal Even-Dar Yishay Mansour, and Uri Nadav, On the convergence of regret minimization dynamics in concave games. In Proceedings of the forty-first annual ACM symposium Theory of computing, pp. 523 532, 2009.
Gabriele Farina, Toannis Anagnostides, Haipeng Luo, Chung- Wei Lee, Christian Kroer, and
Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games.
Advances in Neural Information Processing Systems, 0-330766-30080 2022.
Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks on linear contextual bandits.
Advances in Neural Information Processing Systems, 18:14362-14373, 2020.
Wenbo Guo, Xian WU, Sui Huang, and Xinyu Xing- Adversarial policy learning in two-player competitive games. In Marina Meila and Tong Zhang (eds.). Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine
Learning Research, pp. 3910 3919. PMLR, 18 24 Jul 2021. URL httpp://prooeedings. mlr. wttpppeee//////o///// html
William Hall and Martin Newell. The mean value theorem for vector valued functions: simple proof. Mathematics Magazine, 52(3):157 158, 1979.
Yu He, Fan Yao, Yang Yu, Xiaoyun Qiu, Minming Li, and Haifeng Xu. The complexity of tullock contests. ar Xix preprint or 25w:2412.06444 2024.
11

---

Published as a conference paper at ICLR 2025
Jiawei Huang, Vinzenz Thoma, Zebang Shen, Heinrich H Nax, and Niao He. Learning to sleer markovian agents under model uncertainty. ar preprial urXiv:2007. 10207, 2024.
Junqi Jin, Chengru Song, Han Li, Kun Gai, Jun Wang, and Weinan Zhang. Real-time bidding with multi-agent reinforcement learning in display advertising. In Proceedings of the 27th ACM international conference on information and knowledge management, pp. 2193 2201, 2018.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks stochastic bandits. Advances in neural information processing systems, 31, 2018
Frank Kelly, Aman K Maulloo, and David Kim Hong Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational 1998.
Research society, 49:237-255
R Leo, RS Milton, and A Kaviya. Multi agent reinforcement learning based distributed optimization of solar microgrid. In 2014 IEEE International Conference on Compulational Intelligence and Compuling Research, pp. 1 1-7. IEEE, 2014.
Jieyu Lin, Kristina Dzeparoska, Sai Qian Zhang, Alberto Larnaaa and Nicolas Paper- not. On the robustness of cooperative multi-agent reinforcement learning. In 2020 IEEE Security and Privacy Workshops (SPW), pp. 62 68. IEEE, 2020.
Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, pp. 4042 4050. PMLR, 2019.
Guanlin Liu and Lifeng Lai. Efficient adversarial attacks online multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 36:24401 2442443--2443,, 2023.
Yuzhe Ma, Young Wu, and Xiaojin Zhu. Game redesign in no-regret game playing, 2021.
URL httts:///rrii org/ aaaaaa//111 2210. 11763
Jeremy McMahan, Young Wu, Xiaojin Zhu, and Qiaomin Xie. Optimal attack and defense for reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence. 38(13):14332 14340, Mar. 2024. doi: 10.1609 vaaii.33Si33.29344 URL ntttp://ojss
Dawei Qiu, Jianhong Wang, Junkai Wang, and Goran Strbac. Multi-agent reinforcement learning for automated peer-to-peer energy trading in double-side auction market. In IJCAI, pp. 2913 2920, 2021.
J Ben Rosen. Existence and uniqueness equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society, pp. 520-534, 1965.
Mian Ibad Ali Shah, Abdul Wahid, Enda Barrett, and Karl Mason. Multi-agent systems in peer-to-peer energy trading: A comprehensive survey. Engineering Applications of Artificial Intelligence, 132:107847, 2024.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforce- ment learning for autonomous driving. Xr preprint or drXiv:1610.03220 2016.
Aizaz Sharif and Dusica Marijan. Adversarial deep reinforcement learning for improving the robustness of multi-agent autonomous driving policies. In 2022 29th Asia-Pacije Software Engineering Conference (APSEC), pp. 61 70. JEEE, 2022.
Maurice Sion. On general minimax theorems. 1958.
Tatiana Tatarenko and Maryam Kamgarpour. Bandit learning in convex non-strictly mono- tone games. arXiv preprint arXi::2099. vrXxv:2009.4225, 2020.
Gordon Tullock. Efficient rent sccking. In 40 Years of Research on Rent Seeking 1, pp- 105-120. Springer, 2008.
J v. Neumann. Zur theorie der geseelschaftsspiele. Mathemalische annalen, 100(1):295 -20, 1928.
12

---

Published as a conference paper at ICLR 2025
Jibang Wu, Haifeng Xu, and Fan Yao. Multi-agent learning for iterative dominance climi- nation: Formal barriers and new algorithms. In COLT, pp. 543, 2022.
Young Wu, Jeremy McMahan, Xiaojin Zhu, and Qiaomin Xie. Reward poisoning attacks on offline multi-agent reinforcement learning, 2023. URL https://arxiv. www.aaiwww..rog/oooa//o/ee arg/abs/2206 01888
Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. Human vs.
generative ai in content creation competition: Symbiosis or conflict? In International Conference on Machine Learning. PMLR, 2024a.
Fan Yao, Yiming Liao, Jingzhou Liu, Shaoliang Nie, Qifan Wang, Haifeng Xu, and Hongning
Wang. Unveiling user satisfaction and creator productivity trade-offs in recommendation platforms. Advances in Neural Information Processing Systems, 2024b.
Fan Yao, Yiming Liso, Mingzhe Wu, Chuanhao Li, Yan Zhu, James Yang, Qifan Wang, Haifeng Xu, and Hongning Wang. User welfare optimization in recommender systems with competing content creators. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Dala Mining, 2024c.
Brian Hu Zhang, Gabriele Farina, loannis Anagnostides, Federico Cacciamani, Stephen Mar- cus McAleer, Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Steering no-regret learners to desired equilibrium. arXiv preprint arXiv:2306. 05221, 2023.
Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, Iman Fadakar, Zheng Chen, et al. Smarts: An open-source scalable multi-agent training school for autonomous driving. In Conference on robot learning, pp. 264-285. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2025
Appendix to Single-Agent Poisoning Attacks Suffice to Ruin Multi-Agent Learning
A EXAMPLES OF SECOND-ORDER SMOOTH MONOTONE GAMES
In this section, we provide two explicit examples of second-order L-smooth and 3-strongly monotone games introduced in Definition These examples offer a concrete sense of what we can expect regarding the outcome of a utility poisoning attack in such games. The two cases we will discuss are the n-person Cournot Competition Cournot (1838) and the Tullock contest Tuullock (2008) (a.k.a. resource allocation auctions with costs).
Cournot competition is economic model describing number of firms independently competing on the amount of output they will produce. Each agent-r's pure strategy 2, is the quantity of product, and the payoff is determined by the marginal return of unit of product which decreases w.r.t, the opponents' total production (a Ei=,, and a marginal cost C.. The utility of agent-i is given by
u( Ij
6
Σ
zzj
CTT
(14)
Tullock contest involves agents competing for unit amount of prize in "winner-takes. all" framework. Each agent i's pure strategy is to choose an effort level 2, E [0, 1]. and the winning probability proportional to each agent's 's effort level. The prize is awarded to the contestant with the highest relative effort, and the payoff of each agent is the expected reward minus cost given by some function of the invested effort. Specifically, the payoff functions of agent-i is given by
Fg a
Uy (1
cx(x;);
(15)
1== 33j
where a models the exogenous factor that affects the outcome of the contest, and G R2o + Ry0 is an increasing cost function.
According to Rosen 1965), sufficient condition to verify whether game is 8-strongly monotone (a.k.a. 3-diggonal strict concavity, ie., 3-DSC) can be summarized in the follow- ing Lemma 2
Lemma 2. sufficient condilion for a game (m,, (X.,, (u;}) to 3-DSC is that
1. Each X; is compact and convex, and u,( is concave in and conver in x-i-
2. G's negative symmetric game Hessian defined as -1 - (Mob() (x)) is negative definite and its smallest eigenvalue is at least B.
And to verify the socond-order L-smooth condition, only need to directly apply Definition The following two propositions formalize our claims.
3
Proposition 2. An n-person Cournot competition with payoff functions defined by satisfies:
Eq. 14
1. each agent's ulilily function uy is (a + b + - Lipschillz in a4;
2. is -n-I - -ipschitz in æ-
3. G is 2b-strongly monotone;
4. the spectral norm of the G's Hessian (defined in Eg. satisfies p(Hg) S (n+ 1)b;
5. all agents' utility functions are second-orde order 0-smooth;
Proof. Bocause u;
continuous
Fis an Lipschitz constant can be
max 22,44(2;, x-)l < |a b b Tj - bz; - C.. Since a bΣ Zy 2 0 and
br; > 0, c; 0, have la b b - Ty br, oal a G.
14

---

Published as a conference paper at ICLR 2025
e-b a-b -ini =ohk
The best response mapping has a closed form BRx (x-
and we can verify
26
vn
xx) - -BB((= =
b
(alg
zz))
x x x'
2b
Jzk
Therefore, is /n-1 Lipschitt in a a-
For strongly monotonicity, simple calculation shows the Hessian of n-person Cournot game has the following form
(x) b(1 + 64))
(16)
where dig IIii = 51. We can casily verify that H = b(I +(I+11T) and the smallest and largest cigenvalues of H are 2b and (n 1)b. Therefore, the game is 26-strongly monotone, and p(Hg) = HH (n + 1)b.
To verify second-order smoothness, directly compute function 14(2;; o) for agent-i from Eq. which gives
Us (1 x-1) - 2;(2; + S5, xi)
5
(a- - b ΣØ ii= Ti Gi bz,) - (a - ba- 2j b5 bz, b5) 2h,
which means for any æ E X and 8 * 0, h;(2;; 8) is constant function. Therefore, the game second-order smooth for any L 2
Proposition 3. Consider an n-person Tullock contest G with payoff functions defined by Eq. (15) in which each agent's 's cost function C2 is Ba-strongly convex with its r-th order derivatiee bounded in [-M,, M,), S r $ 3. Then G satisfies:
1. each agent's ulility function is (1 + M1) Lipschilzz in 845
2. up is vn
2 me
+ a=
Lipschitz in x æ-ki
3. G (minie (3,} + (afngy)) -strongl monolone;
4. the spectral norm of the G's Hessian (defined in Eg. ma (B:);
A satisfies p(Ho) s nt +
5. all agents' utility functions are second-order
(4v x
6. a
+
2 as + Ma)) -smooth;
Proof. We prove these claims one by one.
Because u, continuous in F4, an Lipschitz constant can
a + Σ jops It
max meX
V n. U: (z,,
max zex
Vc
(a+ + -y= xz2)²
1
1
Vc,
- + Mi.
プソ xzg
From the implicit function theorem,
θ Barg max, uh (1, x))
(8uul ( x-x) Oxk
Puilan xt
Vn BRR (x: xx)
dr_k
(17)
15

---

Published as a conference paper at ICLR 2025
From Lagrange mean value theorem for multi-variable functions, there exists y-k X_ such that
(x- (2' V 2 (z x'_R).
As a result. a Lipschitz constant for function (R can be naX- V (y-(l Direct calculation shows that for any i,
Vauu(a))= = -
Jjj
va(sz))
(18)
i=1
V))(((>)
Σ
2
2jj
a
+
(19)
iyi
1=1
Since un is By-strongly concave, we have (u x--)]
2
and V V.u(())] Bis
S
2 + J. Substitute them into Eq. 17 we obtain
2 a 03
V (R S
3. To see why is (minge[n) (8.)
a (a+n)>) -strongly monotone, we need to show -Hg
positive definite and then pin down its smallest eigenvalue. From Eq. 18 and Eq. 19 we can derive
2aa + Eit1 13) a Eig ti Eitg 1.)
a + Σ (12) T2 2(a Σ
Vec((12)
-g =
a +
Ft
+
i=1
-3
n
A
a
+
M(a, x) diag( diagi (a)))))).. (een(
(20)
i=1
For any y (y1, .. Hn) E R", we have
n
y M(a
Σ Us
a
Σ Ij
+ Σ
Killi
a+ Σ IK
t=1
1
i<j
A
))
33
32
Σ
yj
+
Σ
y +
Σ
(21)
1=1
8
i=1
1=1
1=1
2 al1y/12-
Therefore, Amin (- (MM (a,a.))) x)) 2 and
Amin ( HHg) >
+ +.80 2
+ 3,.
(22)
(a
(a
n2)
where Bn = (1)
4. 9 second-order (+ +
3 a² -smooth:
Direct calculation shows that h,(2;)) 6) (3 x),)) :) ci( + x.
8
Vela; + +0) Ves(x;)
8A+ A(A+8)
A(A+ 8)2
AP +
8
16

---

Published as a conference paper at ICLR 2025
where A 4= -= == Ta. From the mean value theorem for vector-valued functions Hall Newell (1999) there exists y = x' A(x x') such that
[/:(2;; 8) - (x - [y)لl || - 2'112.
where J(y) the Jacobian matrix of b4 at y, and || || denotes the spectral norm of matrix, defined as
M|| = sup ||Mx||2 = o (M).
(23)
[ 1==1
Therefore, the smallest constant L such that 9 second-order smooth is
[ S || + || + || + || + ||
(24)
where Jo, J2 J3. J4 are the Jacobian matrices of functions f(x) 1
(A+a)a, f(x) =
A(A+8): f(x) M x( Ves(a:+0))
For single-valued
functions f, J(f = f and thus || = V f V fll- From straightforward calculation
we obtain
2
2/
Noll
(A + 8/3 ||||||
<
a
24 + 5
2/n
|
|2]|| -
A2 + 8)2
a
3.1² + 4A6 + 28
3
1
||
24
A2 8)4
x +
A(A 8)2
a²
a3
3A2² + 2A8
1
3 n
1
||ss||
24 *A -)22
5
A2 + 8)
a
2
|| S V M3.
Hence, the game is second order (4ve (+/2
6v2 a
+ 3/ Ms
-mooth..
5. Upperbound of p (Hg)-
From Eq. 21 holds that
M (a, x)y
I
+
Σ
24
Σ Vj
+ a
yi
V/
1=1
<
(n
1
1
+
a(n
1
1=1
(n
1)
a Σ
11
i=1
therefore, by Eq.
20
we have
1
1y Hoy 5
11112 + m
(a + Σm= x;
n + 1
+ max
max 11.112.
a²
<E(m)
Hence, upperbound of p(Hgg) is n+1 maxie (8.).
17

---

Published as a conference paper at ICLR 2025
B PROOFS IN SECTION 3
In this section, we present the missing proofs from Section 8 including the proofs of Lemma [nd Thcorem I which fully characterize the thcorctical guarantees of SUSA, and the proof of Proposition along with an extended argument regarding an additional attack success guarantee of SUSA.
Notably, we establish these results under a broader setting where the adversary can attack multiple agents, rather than being restricted to single agent. Specifically, we consider an adversary targeting a subset of agents C [n], and for each victim agent-k E V, the adversary performs SUSA(k, ōk, A&) on agent-k. We specify such an utility poisoning at- tack as the tuple (V. LEV, (AE) and we denote the corresponding adversary as SUSA(V, {6x JRE, (4
The proofs provided in this section apply to any SUSA(V, {ōx JEEV (A+)KE)) and thus also apply to the special case when V {k}, which is the setting considered in the main paper. For simplicity
notations, we denote the vector == (.1,.... 5n) E Rnd where d = o; i V, and 8, 0 if Φ V. In the following, we restate the generalized versions of our results in Section under SUSA(V, (V,A(V,(O&)eev) (As)eev) and then present their proofs.
B.1 PROOF OF LEMMA
We prove the following generalized version of Lemma
1 follows:
Lemma 3. For any B-strongly monotone and second-order L-smooth game G(n, (K) (w:))) under SUSA(V, (USA(V,(&<)re) (ōk)uev (AR]Nev), the corrupted game C(V, (8x)av (ARteev) with ||ō|| B/L remains strongly monotone.
Proof. By the definition of strongly monotonicity, for any x (æ), '. ,,,), x¹ ("',,". 2(,) E X, it holds that
Σ ( (vi(x(,, us u1 x).) S -B1lao 2012
(25)
where (x(x) Va, (x). Without loss of generality let's assume the SUSA targets at all agents (for agent V, simply let 8; 0 and A; 0). Then for agent-1's corrupted utility function ūn it holds that (xx = Va, (z(x) u (x) + ō1, x-1). By the definition of strictly monotonicity, what need to show is that there exists a 8o > 0 such that
Σ (c) 2;) ),, v,(x, + d, x x))) < -Bollæ' x11..
(26)
According to the second-order L-smooth condition, for any i E [n]] and ô; E RR, the function ha(x): Rnn + Rd defined as
h₂(x)) (2, - 22( + 8,, x.
(27)
||ō:||
is T--iiscciizz in As result, we have
18

---

Published as a conference paper at ICLR 2025
LHS of Eq. (55 LHS of Eq. 26
(a)) - 2;)) (uz (ack, x=';) (2a(,r + 6,, x' + 1,(2 + o,, x. Us (2,;
Σ ||::|| 11ock - x.)) (ha(x') - (x(())))
|| - ||ac| 2. [|ss(a')) (x))))
|| - -|ac -;|| L||x' x:1
=L||a'
x|
| |I
||a|
xill
$
<LI1e' - x=|
11
Σ 1=1
x;11?
i==
<LI|a' - x=|3.
|| 11?
Since (Ei 11 < Ly there must cxist a Bu E (0, such that (Ei [|o:112) S 9-30
As result, the difference between the LHS of Eq- (25) and the LHS of Eq. (26 Joes not exceed (3 - Bo)l(= xl... Hence, Eq. (26 holds and the corrupted game G remains Bo-strongly monotone.
B.2 PROOF THEOREM
We prove the following generalized version of Theorem
Theorem 3 (Vulnerabilityy of MAL algorithms for strongly monotone games under SUSA(V, {ōx (Ax)kev), Consider a SUSA(V, (ōx (Ac)vv)))) to 8-strongly monolone game ((n, (X, 12 (u,)==)) (with unique NE x²). ). Suppose the victim agent-k 's utility function Un is second-order Lm-sthh for all k E V. All agents run an (AAL algorithm A for T rounds. If the following conditions are satisfied:
| < <B/Lo,
2. A(--k: 8) uu (B)) + un (BR - 8, VK: E V, where (x - arg ma up (Ik, xb) is the best response mapping of agent-k,
3. u, is Lipischhitz æ. Vi [m] and BRg Li-Lisschitz in æ œ Vk e V.
Then, the resulting dynamics induced by A converges to some x", such that
1. The deviation to the original NE satisfies
| xx 1l 2 /
sup {p(Hg(z))) = .a)
(28)
where p(Hg(x)) represents the spectral norm of the game's Hession Hg at æ.
2. The expected total budget satisfies
ca
< Co -
(29)
19

---

Published as a conference paper at ICLR 2025
where the constant Cu (4 + -
Proof. From Lemma we know that the corrupted game G strongly monotone and thus also has unique NE x². We first give an estimation of the distance between x' and ø².
Define the best response mapping fa( -i) arg max, ue(1, m=)) for any [n]. Then by the definition of NE, x" = (x ... xr is the unique stationary point of the system
(i F3. Dn);
22 f2(21, "....... )n),
(30)
on = (21, 22, 1n-
while x= = .. .,,) the unique stationary point of the system
Φ = f1(022 x3. .n ô1.
32 fa 03,1 .3.""" .n.) d2.
(31)
3n fu (x 02,
xn-1) 1) dns V.
where 6,
0 if i
If we
let
F(x)
(fi F3, ...
",,...,,nn)) ,R),, (2 33
1 22, xn-1))
n-valued func-
tion and G(x) = F(x) - æz Eq.
(30 and Eq.
(31
can be further expressed as
G(x") 0,
G(ø") = (61, 52, ... 5.).
When G is twice differentiable, from the mean value theorem for vector valued functions Hall & Newell 1979), there exists X E [0, 1] such that
IG(x") G( S max p(J(A#* + (1 -| #*1l, xc(0.1]
(32)
where [xx is the Jacobian of G at æ, and p(J) s4p Julle is the spectral norm of J. Let Ptnax(J) e (axx + (1 A)x²)) ))), we immodiately obtain
- - x" 2 (J)
(33)
Next we estimate the upper bound of p(J). In fact, from implicit function theorem, we can derive the (i.))-th element of J as
Jr, = 1, i
Jr (x(()=:) ô arg max, (1 x. dx,
(Jux ( dx?
82 (2 a:))
Ox,
dx,üx,
8 (00 Om;
Note that the n-by-n matrix H = the diagonal matrix D diag( Hg). Thus, the Jacobian J can be represented as
is exactly the Hessian of g (i.e., Hg), and
J= Hg.
(34)
Since G B-strongly monotone, each diagonal element of D lower bounded by 3 > 0. Hence, the spectral norm of J can be upper bounded by
Pmax (J) < Pmax (Hg)
(35)
3
and
x -
-5"
11,,810 3/1111 Pmax (Hg),
where Pmnxx (Hg) A (P \)x= )))
20

---

Published as a conference paper at ICLR 2025
Next, we derive upper bound of the total corruption budget needed by an SUSA adver- sary. Since A is an (a,P)-MAT. algorithm and 9 is strictly monotone, the resulting playing sequence { converges to the unique NE of 9 with polynomial rate specified by
E|| - x' || S tp
Let y be any number such that << ? < pa. From Chebyshev's inoquality, with probability
at least 1 - p-tt,, ||0, x0 1/ I CP: 1 7, and the following bounds also hold:
[ 1 I C t ViE (n], [2].
(36)
Denote the attacking cost round for agent V as cr, which is given by Ct [ū,( (e, (t,,,. By the choice A., holds that
max (x; (BBR (x-:), x-1,, Va_ X-i. æ,EA,
(37)
Hence, we can estimate an upper bounded of Cta as the following:
Cr (Tr,,, Li,-i) u, uz =i)l
Ju i Dt. u. (BR. (xt, -i) at. (ū (Zr,i, (r, u. (BR. (2t (x), xr,-
(2),,, us (B (1) (1), x),, x(,-,)1 + jú [z,,, Di,-1) -1)- max ūn (0 -1)- (38)
m.
Since uy is Li-ipschitzz in a,, and BR.() ) BR(()) 8; is L2-Lipschitz, the first part of of RHS of Eq. (38) can be upper bounded by
lu, (Zt,i. Ct, un (B: Lt, xr,--)) :) < L1 [/||az at.. (R.(
41 L1||=a 0t,i - a |l + L (R),) (00
L1 || D1,s zi|l + L1 x==.. Z2,-oll
S CL1(1 + T2)
(39)
For the second part, we have
(zt, (t,,1) max ü, (3t, Lt,
a.Ed:
Eli4( 2t._i) - ūz (zx;, x x + (2) x1,) - max ūn (3 x(,-
(40)
2.EAt
Because (z( (-;, = us (x; + 8,, x. u.
8, x) and
Wi, BR, are L1, Li-iischitzz continuous, ū; is (7) + (1 L2)) 11 (2L2 + Lipsscchiit
continuous. Therefore, the first part of the RHS of Eq. (40) can be upper bounded by
(1,, ū, xi.) S CL2 (2L2 7/p
(41)
To upper bound the second term of the RHS of Eq. 40 just observe that
max (.(2,,==)) = max ui + 8;. x) B (x_;), x m.e.
(B - 8,, xi
..E.
-6;) x x.))
= .., (BR i:)
(42)
Using Eq.
we can obtain
0 (x) x²
max ū, ii) m.x..
max Ts úo(00, xt-))= - max (2 22, =xe,
|u:(BR - uz (BR, -5; 8; x))
<1, (11 -B, || + || - x1,-,ll)
<CL, (I2 + 1)/-7/P.
(43)
21

---

Published as a conference paper at ICLR 2025
Assembling Eq. 39
Eq. 41
Eq. 40
and Eq. 413 it holds that
together, from Eq. 38
conclude
that with probability least
pet
Cr - CL1(1+ + L2)t
CL₁ (2L2 + 33 + CL1 + 1)t
= +4
(44)
On the other hand, in the event (with a probability at most p-ttt that Eq. Eq. (36 do not hold, we can use the fact that E [0, M] to give trivial upper bound of a, as follows:
Ce,a [ū (are, Tt,- un (1 -i)-
= (4((x,,; + 8y, x1) - u/ (,RR, (1 (z),- x + + u, (1,)) u,(2111 xz,-
< (1r, + o1, ui (R. (It, (i), xi) (BRR (xt,,i)) 8; xi, ui ( Dt.
$ 2.M.
(45)
Putting Eq. 44 and Eq. 45 together, the expected corruption on agent-í the adversary needs at round t can be thus upper bounded by
E(ca & (1 PP) CT. 5) 11 patt 2M < [ + +2 2M] F+1,
# As result, the total expected corruption and the optimal order is achieved when is upper bounded by
T
E
Cz,b
(ICL + 2MJ -T-- #+1,
(46)
1=1
L
B.3 A GENERAL ARGUMENT OF ATTACKING ABILITY AND PROOF OF PROPOSITION
We first provide an argument regarding the relationship between and ø" x² gen- eral games, and then present the proof of Proposition D which rigorously establishes the corresponding results for the case of Cournot competition.
As pointed out in the proof of Theorem [ the converged point ã = (æi 2 under SUSA(V, (kij) {Ak) can be described by the solution the following system:
an = (1 33. ... Fn) δ1,
x2 = f2(01, Fz. ... xn,) 62.
(47)
In fn F2, xn Sn where the function fe(x-1) arg max, uz(t, x. is the best response mapping for agent i.
And x= (mi xx is the solution to
fi "..... In)) Ø2 f2(21, 03. ................................ Rn):
(48)
Cn = fn(11, (211, .. (nn1)).
Let F(x) (Ni
xx,), ), f2 (x1 ....... Rn)) S In 22,, ",,))))) an n-
valued function and G(ær) = F(x) - x,, we have
G(x") 0,
G(#*) = (8), 82, ... 8n).
For a small perturbation Az, we can approximate the system G around x" with a linearized version:
22

---

Published as a conference paper at ICLR 2025
G( + A,) = G(x") + ((G()"))) + +(1| (01Iam1?) 11
(49)
we view the target point to steer x" as x" + Aa: holds that
G( = G(x*)) G(a"))+
+ A2 12] = J(G + -x") 13)
(50)
From Eq. 34 we know that J(G(x")) = D (z') where Hg(æ*) the game Hessian at I = x", and D (x") is the block diagonal matrix with each block element being the inverse Hessian of u, w.r.t. z/. Therefore, we argue the following in the sense of approximation:
1. if the adversary wants to induce a particular deviation direction v, can simply pick 8 to be D="("")
2. if the goal is to induce largest deviation as possible, it can pick 8 to align with the direction corresponding the smallest eigenvalues of D D-1 (g(x))
And for the special case when SUSA only has victim agent k, it need to pick dz (iag(([V
is ui]l Hg kljo
(51)
in order to induce an NE shift v x² x,, and for any 8, it will cause an NE shifting characterized by
g [ k) [
(52)
which echoes our argument after Theorem 1 In addition, since ß-strongly monotonicity implies that each diagonal element of D lower bounded by B > O, we know the smallest eigenvalue of can be upper bounded by
Panin (J) S Pmiia (Hg)
B
1
(53)
minse(n) A6 min A4
where Pmiin (Hg) because is B-strongly monotone, and 88 is constant such that ue 8u-strongly concave, meaning Br 2 3. As a result, we have
- - x = Pmin ( ()) > ||ō|].
(54)
We note that such an argument is not rigorous and only holds in the sense of approximation, as we omit the high-order term O(]| l1²) in Eq. 449 However, this argument becomes
rigorous proof for Cournot competition, as the Jacobian of system G becomes constant matrix and the high-order term O(I Az IP2) in Eq. (49h disappears.
Proof. For Cournot competition, since the Jacobian of G is constant matrix and we do not have the high-order term O(IAA= in Eq. (9)). Hence, from Eq. (49) we have
G(æ: Ax) G(x*) DD Hg
(55)
which means that for any particular 8, it will induce
t --x x 11-=1,-100 D8.
D8.
(56)
As result, to induce particular NE deviation direction we only need to pick
D- Hgg. To induce the largest possible deviation distance - =x'l it need to pick
such that d aligns with the direction corresponding to the largest eigenvalues of Hz'D. D,
which is also the direction correspouding to the smallest eigenvalues of D-1
C TECHNICAL DETAILS FOR SECTION
In this section, we provide the technical details related to Section 4 that do not have space to include in the main paper. These include essential details for Algorithm and as well the proofs of Theorem 2 Proposition 4 and Corollary
23

---

Published as a conference paper at ICLR 2025
C.1 ESSENTIAL DETAILS FOR ALGORITHM
In this subsection, we outline all the necessary details for Algorithm The algorithm requires selecting self-concoddant barrier R2 (see Definition G and using specific prox- mapping, PR, (<) o6 Th, A, B) (see Definition 7 to update the action for the subsequent round.
Algorithm 1: MD-SCB under Utility Poisoning Attack (Ba et al. 2024
Input: step-size 1/2 2 weight A; >> game's strongly concave parameter 3 > and self-concordant barrier R, (x,) + R
1 Initialize: Let x; arg min (x, for all E [n]
for t [T] do for do
3
Set A!t) + (z) + m((++1) Ia,)
Draw direction (t) uniformly from unit sphere gd
zi
Play action &! t x; + A (t)
Receive 2. + m1((,) + (,,( for ie e A + pi(tt) for [n]
for i E [n] do
8
Compute gradient 6 dii (A (A!1))
Update action x; (t+1) &- PR, (a) 0ú 11,, \i,
10
Definition 6 (Self-concordancc). A function R int(A) - R is self-concordont if it satisfies
1. is three times continuously differentiable, convez, and approaches infinity along any sequence of points approaching the boundary of int(A).
2. For every E Rd and x inl(A), (² h MI S 2(h ((TV))))))) * holds, where [V*R())(, = J,ooo (x +4h 12h (zh) (:
FR
In addition to these beo conditions, if for every h E TRd and x E inl(A), (R(x) s và (h (*R(x) for posilive real number v, R is Definition 7 (Specific Prox-mapping). The prox-mapping exploited in Algorithm is de- fined as
PR( = arg rrngminn(f.a x') ) m1(1+ + - DR(a', r'Ex
2
where (x( the Bregman divergence that measures the difference between the values of convex R at two points, and x', combined with the local linear approrimation of R around x, described by the following equation
= x))
-()))
C.2 PROOF THEOREM 2
Theorem (Theorem restated). Consider an adversary that attacks set of agents
i, al round with lotal budgel. sulisfying Ej Eiet, lG,al S O(19) for all I. and some p E [0.1]. By choosing learning rate sequence 17p = 2d t, for sufficiently
large T the last-iterate convergence rate of Algorithm satisfies E [|]ēr x
Specifically, E [ x x0 [3] S O dT 260-1
max
can be achieved by choosing 3 2).
Proof. The proof outlined below motivated by the observation that we can quantify the bias caused by adversarial attack in utility observation in the Simultaneous Perturbation
24

---

Published as a conference paper at ICLR 2025
Stochastic Approximation (SPSA) estimator, which shares similar spirit to the gradient estimation under corruption lemma in Cheng el al. (2024). In particular, we can exlend Lemma 3.5 in Ba et al. (2024) to incorporate adversarial attacks as follows.
Lemma 4 (Extended Lemma 3.5 in (Ba ct al., 2024)): Suppose that μu is concave function and A; E Rd,xd, is converlible malrix for each E [n], define the smoothed version of Pa with respect to A, by (x(x)) = Bu,nB4 R,,,,,,,, B__ - 84, (ui + A,w;; 2-1] where Sd: is dj dimensional unit sphere, IBd. is di-dimensional unit ball and i; + A,z; for all i [n]. Then, the following statement hold true
( (+((( + b, ()))
where b, (2, 2
Remark 2. The key differennce between utility shifting attack and random noise is b, # 0.
This is because the corruption ((0,; depends on the randomly sampled vector z; through Rú which makes
(,, (A) #
Thus, we need to control the cumsulative impact of the bias in gradient coused by adversarial allack.
We then carry this bias b, throughout the analysis, closely following the original proof developed by Ba et al. (2024). Finally, we derive a result demonstrating how the decreasing speed of the learning rate allects convergence and its associated robustness adversarial atlacks.
To prepare for the proof, we first extend the Lemma 2.12 and Lemma 3.10 in Ba et al. 2024 to incorporate adversarial attacks.
Lemma (Extended Lemma 2.12 in (Ba et al. 2024 Suppose that the ilerate (x!1)) J121 is generated by Algorithm 2 and let each corrupted uhility value jit satisfy that jit (x:) S for all x X and < TJ S 2d we have
Dp(p, x++1)+ 31.(t 1) || (1+1)) -ll² < DR xx)+
mr8(t mn
+2 60 2 +nt x0) -p),
2
where p E and the sequence (113211 assumed to be non-increasing.
Algorithm 2: Single Agent Mirror Descent Colf-Concordant Barrier with Bandit Feed- back under Utility Shifting Attack
Input: step size π) 0, module 3 0, and barrier R int(X) I Initialize (1) arg minaex R(x))
for e [T'] do
3 set (() + (V" +
draw z1) ~ Sd
play a(() (())
receive ( (*(1)) + (ā(1))
set (+t) - (00) + de, ( -1 22))) 8r (=(0((()))))))))----
update x (++1) + Pn (1), i(0)
The proof Lemma 3 is similar to the proof in Appendiz A of the paper et al. (2024), with a simple modification for (t) g) = ((( l,,,,, drj (( ||
Remark 3. Algorithm
x is the single agent version of Algorithm
1
& dn S 2, which still holds.
Lemma (Extended Lemma 3.10 in Ba et al. (2024)). Suppose that the iterate (x2) is generated by Algorithm and let each corrupted utility value it satisfy that 1 (1) (a:) S
25

---

Published as a conference paper at ICLR 2025
for all x X and 0 1/1 S 1 2d we have
a ( + 17.(( + 1)
Σ
|
(1+1)
-Pal?
- Σ
(Pts
KE(N]
IEN
+ nr
+1
Σ iE(n
||
pill?
+ 2
Σ sE/n]
1114
of001 +
2x, 2 -0/0 -pi)
2
where pi E 24 and the sequence (mehe11 is assumed to be non-increasing.
Now, we will prove Theorem Taking the expectation of both sides for equation proved in Lemma 6
conditioned (x!!) have
E
Σ iE(m)
(p, (+11) 1a4
11 1)
E
Σ
||0
(1+1)
-pil 20 S
2
(E(M)
x ) + mm((+11)
Σ
|1= (1)
pil12
2
iE(n!
kE(M)
+ 2T
Σ AellA!00 1
n.E
(t)
pt) ar
iE(m]
iE(M)
By the definition of o and using Lemma 3.5 in Ba et al. 2024). we have
B(I [<;;)) S df.
In addition, using Lemma 3.5 in Ba et al. 2024 again and the Young's inequality, we have
(6, (1) xx p.)l s (V..u((r)... a - -pi) + 2/3
Xdl
Σ (amax (omax(A4!)) (4)
B 2
||o, (1) -pil
+ (0 (a))
+
- -p;),
im(m)
where have 6/0 equals the following 6,0) n, c,, ) (A4
* 0, this
is because (0) is function of z (2)
Since (x) is positive definite for all x E X and
A (o
xi x
(1)
-Pillx
d (VV - -pa) -pa)+ + 21
Σ A
Σ
iE(m)
TE(m)
iE(n)
iE(m]
B
||0
(1)
pill))
+ Σ (T
(x) ( -p.) pi)
vE(m)
3 (1/2))) pull2) + Σ
A
Σ x?1?
1, (m) ps) Σ
AVVanii))))) -p.).
32
2
1E(m]
(E(n)
sE(n]
iE(m)
In this way, we have
(p.
11 1)
E
|
((+1) - -pil12
I 7
Σ
Nv AvV.uu(p), (1) pi)
2
iE(m)
(E(n)
iE(m)
A,DR, (pn, (1))
31 E
[ (t)
211
+2n
Σ df
iE(m)
NE(m)
iE(m)
1
Σ di
X
+ m.E
(t)
(sc(")
pi)
2/2 1)
ic|m]
iE(m)
26

---

Published as a conference paper at ICLR 2025
Summing up the above inequality over = 1,2...., T 1, we have
- T-1
3T
A.R.. (Dr,
E
Σ
|
(0)
pill?
Me
Σ
pi)
2
[E(M)
KE(N
Σ iE[m]
DR, (pi, (p (1)) +
7113
Σ
|
pill2)
+2
Σ
de
Σ %1
JEN
iE(m)
T-1 +
1 2B2
A
Age? 1E(m]
Σ
Σ
Σ 7E
Σ
1, (t)T (xc (1)
p.))
6EIn]
We should notice that for each round, there is freedom for the adversary choose who to attack. To be consistent with the lower bound, in this upper bound, we assumee that the adversary consistently choose i := i to attack. Before procoeding afterwards, now let's analyze the cumulative impact of bias on the convergence of action profile. Notice that for i * i, by
0. Therefore we can use Cauchy Schwartz to bound the following inequality
T-1
1, (1) (z) -pi)
T-1
Σ
E
S
3
3/2 T
Vt + I (c,,) E" = CdB max Vx.,
(E(m)
(E(m)
where B = maXie[m] B,, B, is the radius of Rg In particular, Ö is the constant such that for (2R;(E0 (1)) + 1(((t))) Ia.)
all t, Fmax
Therefore, we have
d;
BT
T Σ
E
D.D,R (Pis
+
E
Σ (E(N)
|
- pill?
S
E
Σ
Ao
(V (0)
pi)
2
PE(m)
1=1
(EiN)
+
Σ
MrDx, (pi, x0) (1) )
)1+++ 7113
pill3
+2
Σ
de
T-11 Σ n
2
iE(n]
iE(m)
iE(n)
T-1 V3
+ 2,32
Ao
Σ x2e2
Σ
+
Σ
th
3/2
vl +
1
(..(
1+1
dE(m)
kElmi
Since
E
Eve(n) di DE (p:s (ris (0))
>
0, we have the following equation
T-1
E
1 (t)
p:l12
2
Σ
A
x() (9)
-p:)
BT
11T
t=1
ic(m)
X,D (pt, (1)
m7 +
Σ
||00 (1) pill2
+ BT
4
Σ
L.
Σ n
1/T BT
T
VE|n)
(E(M)
iE(m)
2 Tr
Ai
Σ cE|a|
Σ (++))
+
T-1
1/1
3/2
Vt+
B3T
NTVBT
BT
1=1
(57)
By the initialization x; (1) = arg min R₂(x), we have VR( = 0 which implics that DR. (pr. ()) = (p,) (mm(")) Then, let us inspect each coordinate of a unique Nash
equilibrium xt and set p coordinate by coordinate in 57 indeed, we consider the following two cases:
A point of E X; satisfies that Tea (xx)) < 1 - + By Lemma 2.4 (Ba et al. 2024
we have DR. (2f (xf (1) = Rx())) - - (R(( (2) & u2 log)(()) In this case, we set pt
27

---

Published as a conference paper at ICLR 2025
A point i E Xr satisfies that (x)();) that || - x || = O 1 vT) and n.a (2;) $ - VT.
1 Thus, can find T, 2, such By Lemma 2,4 (Ba et al. 2024).
vT'
1
we have DR. (3), x; (1)) (w,) (w) S us log(T). In this case, we set Pt B.
Therefore, we have the following equation. By choosing n 24 20, we have
E
|ل x; ||||
(58)
I
4d
T
E
Σ [m(m)
>pli
(1)
a211]
Σ (E(m]/z
||00
2ill
+ +
A
(0) EAnzelll - 3:1l] =
BT
1=1
iE|n]
(59)
+ T1
Σ
B
(60)
iE/m]
2
Σ
di
Σ
22
(61)
d371-6 0
VEIN
4d log'
Σ A
Σ
x3
(62)
3T1-6
iE|m
ic(m)
2C"
+ 11 (c:))
(63)
d/3T'-
2C"
c,, ((x))
(64)
d/BTI-0
4d
Σ vi
T
(65)
3T
KE(M)
We will analyze the convergence of E of the right-hand size one by one. By Lemma 2.4 (Ba et al. 2024), we have Eqq (58) and
EM ||=)
by bounding the convergence
Eq. 59h are upper bounded by O d is upper bounded by ((7)) Eq. (62 and Eq. 665 are upper bounded by Ö( Now
Eq. (60) is upper bounded by ( Eq. 661
vT
it remains to analyze the convergence rate for Eq. (63) which we regard as the impact
of observation error. Note that Eq. (65) can never be the dominant term, therefore, we
drop it from the analysis. Since tー (t 1)- < (x++1 for integer and >> 0 and if
Σj= (,,(( S 1' holds for all l, then we can bound
20'
T-1
Σ
#
- 3
(0(0)))
S 2 O(TP-)(0+1))
d/BTI-
d
E=1
Noticing that
2d Die d
E
Σ iE[m
a: 101
S E
Σ
(maxx (A(
S
iE ml]
-8
FE m]]m]
We have the following
E
Σ
|
< max (0(2TT-1),0(1T-))) 0 }.
|E|n]
which completes the proof.
28

---

Published as a conference paper at ICLR 2025
C.3 ESSENTIAL DETAILS FOR MAMD BRAVO ET AL. 2018
At the beginning of this section, we provide necessary details for Muti-Agent Mirror Descent (MAMD), initially developed by Bravo et al. (2018) for mulli-agent learning (see Algorithm
31- We altempt to evaluate the robust.nsss ol Algorithm 3 under utility shifting attack,
highlighted by the red line (Line 7 of Algorithm
A Algorithm 3: MAMD (Bravo et al. 2018) under Utility Shifting Attack
Input: step-size M/,1 = "t "t= query radius 7a2 = 8t safety ball By, (p:) C X; for all agents
(0) E X; for each agent [n]
Initialize action a; for i. E [7) do for E [n] do
Draw direction 2; uniformly from gd.
Set w + 2(() - r; (a p.)
play 0;
(1) (t)
t æi + 22
(8)
Receive n + (2((t) + c (t,) for i Ir, a/ + pi(at) for i [n] Iz
for i E [n] do
Set (1,/)1 (1) 2(1)
10
Update x.
(1+1) t- Pa(") nt,1 11
"The proximal mapping Px = argz/ex minfy" T (s x') + D(x', where DR .x) is the -x), for some strongly convex function R. Additionally, Algorithm creates safety ball Br, (p.), with d/r, 1, and generate (t)
Bregman divergence, where Dx R(r') R(x) VR(2)
bases on adjusted randomly sampled direction 2 to ensure feasibility.
C.4 PROOF OF PROPOSITION
Proposition 4. Consider an adversary that attacks a set of agents Ia at round with a total budget satisfying Ej Liet, G & O(t)) for all and some E [0, 1]. By choosing parameters 11.1 30-30 and 11, 81- for constants 7 and > 0, <
3 runming Algorithm 3 sufficiently large T, the last-ilerate convergence rale salisfies: E (1 1²) < (d ma TTD-20)).
Proof. Similar the proof structure in Appendix C. at core of the proof of Proposition 4 is to quantify the bias, b, caused by utility shifting attack in gradient estimation for SPSA estimator developed by Bravo et al. (2018). resulting the following lemma.
Lemma (Extended Lemma C.1 in Bravo al. 2018)). Consider o50) (defined in Line 9 of Algorithm 3) and Let (x(x) == Eug E -----1,, s4, [M, + n,,20,; x =)], then we have
[(o,(=)) = v.ūx(w) + b,.
where b, d (z) n1.2
Using Lemma by choosing Tt.1 = Pt- 71.2 n,2
86-9, we can extend Equation D.13 (see
Eq. (66) in Bravo et al. (2018) to incorporate bias (see term C in Eq. (67)), where we use D. to denote the average Bergman divergence E(D,) between x" and 2, induced by some K-strongly convex function R, and V2 = Σ, d?, we have
Det1 $ (1
By D +
7
+
V2 7282
(66)
t
2K
(2
29

---

Published as a conference paper at ICLR 2025
D41 S 5
BY 1
D
+
7 tp
8
1,,11
6.00 iE(n]
Σ
V2 7282
(67)
19
2K (2(p-9)
To analyze the convergence rate of Di+1: we need further extend the convergence lemma. (Lemma D.2 in Bravo et al. (2018) from smooth decaying by ~ (++) to only a sublinear summation bound (scc Eq. 688) to incorporate utility shifting attack.
Lemma 8 (Extended Lemma D.2 in Bravo al. satisfying that
2018
Let on be non-negative sequence
Q #²
0++1 S at
1
+
b
tp
Σ
< T VT > 0.
(68)
where P.Q > 0,p (0, E 12,1,, be [0, 1]. Then, there erists constant C > 0 such that for sufficiently large t, we have
1. there ecisls posilive constants C, To such that for any t> To,
C
0, S #
2. if the sequence {br)-= non-increasing starting from to, there erists positive constants C,To such that for any >> To.
a < f1-a
Proof. For the first situation, it holds that
P
0++1 S 0t
+
b
1
P
Q
(1
P
Q
1:-1
1
bt-
+
b
(1
1)p
(1-
1)p
b k
II
1 (1-
P
(69)
k)p i=1
(1-i i+
k
P
<Q.7 Σ
II
1
(70)
(t k) i=l
[t
K=0
<Q.
k)
< -P
{ (-- I (1
where Eq.
77 holds because the sequence
[-1++
is non-
k=0
increasing when p (0, Therefore, the maximum possible value of the RHS of Eq. is achieved when b. = ... = b4-1+11 = 1. When (bt) is non-increasing, the RHS of Eq. achieves its maximum possible value when b _..._ = by = 1o-1 Therefore, it holds that.
69
30

---

Published as a conference paper at ICLR 2025
b k)p i=1
P
4 SQ
Σ
1
(t i--i+ 1)p
k=0
1-1
k
P
-10-1Q Q
1
(8-i+1) (0-+11p))
(1 k)
(1 -
k=0
==1
$ $0(1)))
Armed with Lemma 8 we can analyze the convergence of Eq. 667 Firstly, we note that M1.1 (Eiejn) b(t) s (ddTe-)) Second, we need to choose p. g > 0 such that the cumulative sum with respect to the term A, C converge to constant. To satisfy this constraint, we need & < g S and we choose to make the order of term B and equal, we get p = 3q. In this way, the convergence rate is determined by Odd max (0-29)), completing the proof.
D ADDITIONAL DISCUSSION ABOUT ABSOLUTE ROBUSTNESS
In Section we explored the efficieacy-robustuess trade-off based on a specific concept of robustness whether utility poisoning adversary can induce NSA. However, this is not the only measure of robustness. In this section, we introduce a new concept called absolute robustness and establish formal efficiency-rouuste robustness trade-off, analogous to our results in Section [ under this broader notion of robustness.
To introduce the notion of absolute robustness, we need to first define generalized con- cept of utility poisoning attack outcome, named y-Successful Attack (a-SA), as shown in Definition g. Intuitively, 7-SA depicts broader and milder goal (i.e., slowing down the convergence rate or causing non-convergencee) compared to NSA.
Definition 8 (7-Successful Attack and Absolute Robustness). We say an adversary suc- cessfully implements a --Successful Attack (y-SA) for some y E [0, 1] to an (AL dynamics running a game if it induces joint strategy sequence (x) such that for any sufficiently large T, the cumulative error
x: 111 = Ω (TI-pa(1-n)).
(71)
In addition, we say an MAL dynamics A absolutely robust to a utility poisoning adversary with budget ((T)) if with budget O(TP) cannot induce 7-SA for any 7 > 0.
Naturally, NSA is a form of 1-SA, as shifting the NE inevitably results in a linearly growing cumulative error. Therefore, 7-SA is a weaker concept in terms of the attack's impact, while absolute robustness represents a stronger defensive notion, since it implics that not only can a new convergence point not be imposed, but the original convergence rate remains unaffected. Our next result shown in Corollary 2 indicates that if an adversary aims to achiove 7-SA for some y (0, 1), it requires smaller total budget, expected. To accomplish this, the adversary can divide the time horizon into different phases, altornating between performing SUSA and doing nothing. By adjusting the lengths of these phases, the adversary can balance the attack budget and the desired level of regret.
Corollary 2. Under the same conditions as stated in Theorem an adversary can imple- ment SASA within total budget
T
cel = =0(1(1-Aiti #1) -00(11))))))
E
(72)
31

---

Published as a conference paper at ICLR 2025
Proof. Define the p-th moment regret Regy (T) = =E== Ei=EBlla Bil ==1])] Then from Theorem
I we know that for any sufficiently large To, the adversary can use an expected total
budget of O (To' pa
to incur regret (T(T)). Consequently, for any given T, setting )
To = = 7--ppp11-1 ()), the adversary can use O (T (T-->1)) (1 ((11--((1-)))) ) total budget in expectation
to incur a regret of the order ((T1)=pa(1>)) by performing SUSA for the initial To rounds. For the remaining rounds, the adversary can refrain from injecting corruptions and allow the agents to run their MAL algorithm without interference. In this way, the adversary can incur at least ((T1-1)()))) regret while using at most O (T ( total expected budget.
Theorem | and Corollary 2 together highlight an intriguing trade-off between the efficiency and robustness of MAL learning dynamics. That is, the faster an MAL algorithm converges (i.e., a larger a), the smaller the total corruption budget required to implement a successful attack (either NSA or 7-SA). Next, we establish an analogous result to Corollary [ under a new (and stronger) robustness concept, that is, whether an MAL dynamics is absolutely robust to a utility poisoning adversary with certain budget, as defined below:
-(c,A)=inffe = inf E [o, 1]je with budget O(TP) can achieve 7-SA against A.}; = =sup( E A]IA is absolutely robust to C with budget O(T").), where C E ADV represents a generic utility poisoning adversary. Similarly, we fix p 2 and define the following quantities:
(a)
inf sup A), p+(a)=
sup inf AL CEADY AlC
(73)
CEADV AEMAL(o.2)
Here, the function p_(a) defined in Eq. 73 represents the optimal strategy of utility poisoning adversary. Specifically, for any MAL algorithm known to enjoy convergence rale a, (a))) denotes the minimum budget level p required for successful 7-SA by the adversary. In contrast, the function P+ (+(a) characterizes the optimal defense from the perspective of the algorithm designer. Given required convergence rate a, (a) identifies the most robust algorithm that can withstand a-SA of level p from any utility poisoning adversary. From minimax theorem dv. Neumann 1928 Sion 1958) we still have p_(a) 2 (+)),, Va E 4)- Furthermore, Corollary 2 and Theorem lead to the following result
73 for some particular MAL algorithm Ao and adversary Co ADV, we further define
Corollary 3. Given the definitions of p_(a) and (+(a) in Eq.
p(A((a))= inf plC, Ao(a)), p(a,Co)= CEADV
sup 2
p(C Co,
where Ao(a) denotes algorithm Ao with set of hyper-parameters that guarantees M MLL(a,2 2) convergence. Then for any a E [0, 1., it holds that
< (1
2a
1- S ((MD-SCB(a) s (a) S p- (a) S p(a; SUSA)
(1 (1-2a). 2a). (74)
3
The proof of Corollary 3 follows exactly from the idea of Corollary I and thus we put them together in Appendix D.1
Figure 3 illustrates this trade-off. The yellow dashed line represents p_(a): above it, a bud- get of (TT) suffices for a powerful adversary to induce 7-SA in any M AL dynamics. The red region, subset of this area, corresponds to the actual budget required for 7-SA for the specific attacking strategy outlined in Corollary 2 Conversely, the blue dashed line represents #+ (a): below it, the most robust MAL(a, 2) dynamics is absolutely robust to any adversary with a total corruption of O(T²). For specific MAL dynamics like MD-SCB, the green region shows the budget within which it remains absolutely robust. We only present E [0.25, 1] because the MAL dynamics with the best achievable convergence rate in such setting (alpha- 0.25) (Ba et al.)
2024) can withstand a corruption level of p p= 0.25 (see Theorem 2). The three gaps in Figure correspond to three open problems similar to those proposed in Figure
32

---

Published as a conference paper at ICLR 2025
D.1 PROOF OF COROLLARY AND COROLLARY X
Proof. By the definitions of p- (a), (+ and minimax theorem, it holds that p-
D(MD-SCB(a)) S (+ - (a) S SUSA),
P(MD-SCB(a)) s (+) S p- (a) - p SUSA).
Taking p = 2 in Thcorem we have (o;SUSA
and taking p = in Corollary 2
have p(;; SUSA) < (1 2xx
20).
Next, show that p(MD-SCBB()) 2 11-a and ((MD-SCB(()) > -1-3a 3a. By Theorem 2 we know that for MD-SCB, in order to incorporate a corruption ((T*) with > O, we have to slow down the learning rate by increase Φ. Therefore, for any particular choice of 6, the resultant convergence rate choice does not affect the convergence rate, and we obtain p 2 2 2 - 0, this = 1- 3a, meaning
I-Ø Hence, only when -p + @+1
2.
((MD-SCB(a)) 2 - 3a. On the other hand, if p 2 3a, as long as p -+1 < 0 (i.e., 1)) NSA impossible induce as MD-SCB will still converge although at a slower speed. This implies that p(MD-SCB(a)) 2 1- a.
Notably, the effciency-robuusuues trade off also exists in Algorithm 3 for 7-SA. Eq. (67 suggest that as long as
1 1- 1-p-g 4 potn will be the dominant order in decid- ing the convergence E(1æT- x 1l2). This implies that (MMMD(()) 2 1 4a, which also shows as long as < 1-4 the convergence rate of Algorithm 3 will not be affected robust to 7-SA. However, since g restricted to i < to ensure the convergence of Dr, when > 2' the dominant order will be 10-29 and we can see optimal choice of q - 3. implying p(MAMD(a)) 2 2 which we do not observe such a efficiency-robee nobustness trade-off of Algorithm for SUSA, theoretically.
3.0
Srfidency-Robusttne Trade-off
Vulnerabie
0.8
0.6
SUSA
0.4
A.Gat
2200
Attack
0.00
0.55
0.10
0.35
6.20
0.25
E ADDITIONAL EXPERIMENTS
Figure 3: Illustaation of the four quantities in Corollary 3 re- vealing the intrinsic effictency- robustness trade-off under 7- SA.
E.1 EXPERIMENT RESULT FOR MAMD
In this section, consider the same experimental setup as of Section 5 and evaluate the performance of Algorithm 3 We let each agent run MAMD with the game size [10, 50, 100). The learning rale schedule of MAMD is set to 1h,1 X 36 and T7,2 x & Ø = 0.33, 0.30, 0.25, corre- sponding to convergence rates a 0.165, 0.15, 0.125, p 2 when no attack is present. We implement SUSA against agent 1, with fixed 8 = 10.0. For each game instance specified by and the attacked algo- rithm specified by the convergence rate a, we compare the dynamics' behavior both without attack and under SUSA, and report the actual total budget used.
In the upper row of Figure 4 the left panel plots the convergence curve of the L2 square error for n = 10, serving schedules induce different convergence rates for MAMD in absence of an adversary. The middle panel shows the outcome of SUSA against MAMD with a = 0.165, with the y-axis representing T2 distance between 2; and NE. The dashed lines display the convergence curve without the adversary, while the solid lines represent the dynamics under SUSA, with different colors indicating results for various game sizes As shown, for different values of n, the attacked dynamics exhibit divergence, as the solid lines saturate and stop decreasing, indicating that the dynamics are being stcered to converge to new point. However, the trend betweon induced NE deviation magnitude with respect to n is unclear for MAMD, possibly because the lower bound proved in Eq. (10) of Theorem is not tight. The right panel shows the cumulative attack budget C. Σ [rr each time step against MAMD)
Result:
sanity check to confirm that different learning rate
33

---

Published as a conference paper at ICLR 2025
with different values of a. As the results indicate, although all exhibit sublinear trend, a faster-converging dynamics (ax = 0.165) requires a smaller attack budgel, corroborating our findings in Theorem |
and 2 The boltom row of Figure I evaluates the performance of MAMD under a different sets parameters nevertheless conveys a similar message.
Consergence with sx30
Nariialation Power with 0.15
Conuuative Atlock Buddet with no
10.10 ataic
2004
Lice
1380
2509
2509
756 1988
Beration
Heratioon
Reration
10 2315
00000
20000
10000
2500
7500 10689
12ies
10P
Btrstton
Iteration
Iteration
Figure 4: Left: square error of MAMD with varying convergence rates. Middle: square error of MAMD on different sizes of game instances against SUSA. Right: cunulative attack budget used by SUSA against MAMD with varying convergence rates. Error bars represent the 1-0 region from 20 independent simulations.
E.2 ADDITIONAL RESULTS FOR MD-SCB
Figure evaluates the performance MD-SCB under a different sets of parameters never- theless conveys similar message as of Figure 6
Cosvergance with 100
NE Man puletoe Power with -00
Orresistive Arrick Budgut n-100
40000
3800
1860
7000
100es
1986e
5hice
27813
1P
2000 1050
1969
30300 19850
1186 1980
Figure 5: Left: square error of MD-SCB with varying convergence rates when Middle: square error of MD-SCB on different sizes of game instances against SUSA with = 0.15. Right: cumulative attack budget used by SUSA against MD-SCB with varying convergence rates when = 100. Error bars represent the 1-o region from 20 independent simulations.
100.
F EXPERIMENTS
In this section, we validate our theoretical results from Theorem and Theorem by implementing SUSA against MD-SCB n-person Cournot games, which each player-i has a utility function ( x; a 1a-b-n - zi C. The formal definition is given
E for additional results for attacks We run simulations on two types of Cournot. game instances. In the first. type (homogeneous), all players share the same marginal cost 6, resulting in a symmetric game. In the second type (helerogeneous), players have varying costs. The results for the homogeneous
in Appendix A We also direct readers to Appendix against another algorithm MAMD (see Algorithm
presented in the main paper,
34

---

Published as a conference paper at ICLR 2025
while those for the heterogeneous case are included in Appendix E.2 as they basically convey the same message.
Homogeneous n-person Cournot Game Experimental Setup: We set = 10, b 0.05, and we consider the cost G2 for all agents E [n]. The action space is set
180 to X; = |0, [0,50] and the unique NE of such games can be verified as x; -+I i E [n]. We let each agent run MD-SCB with the game size n {10, 50, 100). The learning rate schedule of MD-SCB is set to (7) t-, = 0.5, 0.7,0.9). corresponding to convergence rates a = 0.25, 0.15, p = 2 when no attack is present. We implement SUSA against agent with fixed 8 10.0. For each game instance specified by and the attacked algorithm specified by the convergence rate a, we compare the dynamics' behavior both without attack and under SUSA, and report the actual total budget used.
Convergance with n-10
NE Manipulation Power with a 0.25
6000
100, attack
-0.35
50, attack
5000
a -0.05
+
10, no atlack
3000
10a
2000
10a
Iteration
Iteration
Cumulative Attack Budget with n-10
Comparative Welfare Analysis: With V5 with without Attacks
400000
- 2
0.05
300000
W(x))
120
100
100000
60
WiX")
5000
15000
Iteration
Iteration
Figure 6: This figure displays results for Homogeneous n-person Cournot Game. Top left: square eгror of MD-SCB with varying convergence rates. Top right: square error of MD- SCB on different sizes of game instances against SUSA. Bottom left: cumulative attack budget used by SUSA against MD-SCB with varying convergence rates. Bottom right: social welfare W (xx) under SUSA and without attack for
10. The red dashed line denote the social welfare under NE without attack, W(x"), while the red solid line denote the social welfare under manipulated NE under SUSA, W(*).. We plot 0.1-a region from 20 independent simulations for social welfare (the bottom right figure) and 0.5-a region for the rest figures.
Result: The top left panel of Figure 0 plots the convergence curve of the Le square error for n 10, serving as sanity check to confirm that different learning rate schedules induce different convergence rates for MD-SCB in absence of an adversary. The top right panel shows the outcome of SUSA against MD-SCB with L2 distance between 2; and NE. The dashed lines display the convergence curve without the adversary, while the solid lines represent the dynamics under SUSA, with different colors indicating results for varions game sizes n. As shown, for different values of n, the attacked dynamics exhibit divergence, as the solid lines saturate and stop decreasing, indicating that the dynamics are being steered to converge to a new point. Additionally, we observe that the induced NE deviation decreases with respect to n, which aligns with our theoretical predictions in Theorem and Remark The bottom left panel shows the cumulative attack
0.25, with the y-axis representing
35

---

Published as a conference paper at ICLR 2025
budget c== C==E== |c>| at each time step t against MD-SCB with different values of As the results indicate, although all exhibit a sublinear trend, a faster-convergingg dynamics (a = 0.25) requires smaller attack budget, corroborating our findings in Theorem | and 2 The bottom right, panel plots the social welfare ((x)) without attack (indicated by the dashed line) and under SUSA (indicated by the solid line). The panel shows that SUSA with 5 -10 can lead the learning dynamic
new NE with a lower social welfare, aligning with our theoretical results. These observations also hold for Cournot games with heterogeneous costs, and the corresponding results are presented Appendix E.2
Heterogeneous n-person Cournot Game Experimental Setup: Similar to the ho- mogeneous n-person Cournot game, we set = 10,6 0.05, n E [10, 50, 100], a [0.25, 0.15, 0.05], and X; E [0, 50), vi E [n]. However, in the hetcrogencous sctting, we the value of n. For
consider different configurations of G based assigned as follows: C1 = 0.5, G = 0.6 for i E [2, 7]. and C; = 0.7 for i E [8, 10]. For larger values of n, specifically dividing the sequence into groups when n = and into 10 groups when n = 100. Each group follows the same pattern of costs assignments in the 10 case. We implement SUSA against agent with 155
10, the costs
50 and n 100, replicate the structure of the
10 case,
Result: Figure 7 suggests that all results hold in the heterogencous setting just as they do in the homogencous sctting.
Convergence with n=10
NE Manipulation Power with a 0.25
100
5000
n 10, attack
10'
4000
2000
16a
10a
Iteration
Iteration
Cumulative Attack Budget with n=10
Comparative Welfare Analysis: With VS without Attacks
700000
Wyx
600000
+
500000
400000
W(x
120
100
2500
5000
15000
2500
5000
10000
12500 15000
Iteration
Iteration
Figure 7: This figure displays results for Heterogeneous n-person Cournot Game.
36


Reviews:
[{"review_id": "H2HlRy5UWC", "reviewer": "Reviewer_mptu", "summary": "This paper studies the robustness of multi-agent learning (MAL) algorithms in strongly monotone games with bandit feedback. The authors propose the Single-agent Utility Shifting Attack (SUSA) method to shift the Nash Equilibrium of monotone games by corrupting a single agent's utility feedback, using a sublinear corruption budget relative to the time horizon. Their analysis uncovers a trade-off between efficiency and robustness, showing that faster-converging MAL algorithms are more vulnerable to such attacks. They also validate their theoretical findings via numerical experiments.", "questions": "1) Given that the attack model assumes full knowledge of the victim agent’s utility function, do the authors believe that SUSA could still be effective in a limited-information setting? Are there alternative attack strategies that might be feasible with only partial information?\n\n2) The attack model relies on \"strong\" corruption, where the attacker observes the current round action. It would be valuable to investigate whether the results extend to scenarios where the attacker lacks this observational ability, as well as whether it becomes easier to design robust algorithms against such \"weaker\" attackers.\n\n3) To what extent might the findings on NE shifting and efficiency-robustness trade-offs apply to non-monotone games or games with multiple NEs? Could the authors envision scenarios where the attack objective is to guide agents toward a low-utility NE?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper highlights a significant and underexplored vulnerability in multi-agent learning (MAL), specifically through single-agent utility poisoning attacks. It may stimulate further research into designing MAL algorithms that are robust to adversarial attacks.\n\n2) The authors provide a rigorous theoretical analysis of the Single-agent Utility Shifting Attack (SUSA), clearly outlining the conditions under which SUSA can effectively alter the Nash Equilibrium (NE). The exploration of the efficiency-robustness trade-off is valuable, highlighting the increased vulnerability of faster-converging algorithms.\n\n3) The authors conduct extensive empirical simulations, showcasing the practical impact and effectiveness of their proposed method", "weaknesses": "1) The current attack objective is focused on shifting the Nash Equilibrium (NE) with specific distance guarantees. While the paper briefly discusses steering the NE deviation in a desired direction (lines 295-300), it remains unclear if it is feasible to mislead agents toward specific, predefined strategies.\n2) The study is primarily focused on monotone games, illustrated through Cournot competition and Tullock contests. It would be valuable to examine whether these insights hold in other game-theoretic contexts. For instance, in non-monotone games with multiple NEs, it would be interesting to explore alternative attack objectives, such as guiding agents toward an NE with low utility outcomes.\n3) The paper evaluates the effectiveness of attacks based on NE shift and cumulative budget. Expanding the evaluation to include additional robustness metrics, such as stability and utility outcomes, would provide a more comprehensive understanding of the impact of attacks on MAL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6BQi9jrqWz", "reviewer": "Reviewer_vqqA", "summary": "This paper designs the attack policy for multi-agent learning in monotone games. It shows that attacking a single agent is enough to diverge the convergence away from NE. The paper also studies the robustness of the MAL algorithm, presenting several interesting open problems and numerical simulations.", "questions": "Minor comments:\n\n1. Line 147, “will useful” → “will be useful”.\n2. Line 242 is a “strong” attack, [Lykouris et al., 2018] is a “medium” attack before observing the action. For strong attack, the related literature has: \n    1. Jun, Kwang-Sung, et al. \"Adversarial attacks on stochastic bandits.\" *Advances in neural information processing systems* 31 (2018).\n    2. Liu, Fang, and Ness Shroff. \"Data poisoning attacks on stochastic bandits.\" *International Conference on Machine Learning*. PMLR, 2019", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper's writing is clear and easy to follow. The figures (especially Figure 1) and remarks help readers understand the paper. \n2. The contributions of the attack policy to a single agent and proving a sublinear attack is theoretically enough (Theorem 1) are novel in the literature. \n3. The discussion of the robustness and efficiency trade-off is very insightful and opens the door for more interesting future works.", "weaknesses": "1. As the authors mentioned that the trade-off had been studied in a single agent, it would be helpful to discuss whether or not the three raised open problems are also present in the single-agent setting. If so, can we extend the single-agent results? If not, why?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fxItU0aE2U", "reviewer": "Reviewer_3kAq", "summary": "This paper investigates the vulnerability of multi-agent learning (MAL) systems in strongly monotone games with bandit feedback. Specifically, the authors propose an attack strategy called Single-agent Utility Shifting Attack (SUSA), which can steer the learning dynamics away from the Nash equilibrium with a sublinear (w.r.t. T) budget. The authors also provide theoretical and empirical results to validate their points.", "questions": "Can the authors discuss the attack strategy if the adversary only observes noisy rewards, e.g.,  sub-gaussian rewards?\n\nIs there any lower bound on the budget that misleads the convergence?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel type of poisoning attack that focuses on a single agent in multi-agent systems, a context underexplored in prior work. The proposed poisoning strategy can mislead any MAL dynamics in strongly monotone games away from the original NE, with a sublinear corruption budget.  \n\n2. The authors show a trade-off between convergence speed and the robustness to attacks.\n\n3. The authors provide a thorough theoretical analysis to validate theoretical results.", "weaknesses": "In the attack model, the authors assume full knowledge of the victim agent’s utility function, which may not always be practical in real-world applications. Moreover, since the agent is unaware of their utilities and the adversary has such knowledge which further allows to compute more information such as gradient, misleading the system not to converge the original NE looks not surprising due to the information asymmetry. It could be more interesting to restrict the adversary. For example, the adversary only observes the noisy rewards.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9rp6VKHBA4", "reviewer": "Reviewer_oyqK", "summary": "This paper considers the poisoning attacks in multi-agent learning, targeting a single agent. The authors first propose the attack strategy which steers the game from the NE with sublinear attack cost. They then explore the robustness of learning algorithms, analyzing how the convergence rate can affect the algorithms' robustness. Finally, the experiments verify the theories by showing the derivative and the cost under different parameters.", "questions": "Please try to solve the problems in weaknesses. Besides, there are some extra questions:\n\n* The trade-off between robustness and efficiency is very intriguing. I suggest authors further highlight this part in the next version.\n* In Line 169-170, is the parameter $L$ known to the adversary? How can the adversary select the target agent “smartly”?\n* In Line 295-301, the authors want to show that more information will lead to the ability to control the attack direction. However, without more knowledge (which means more assumptions), this is not addressed. Similarly, in Line 319-322, the same issue arises for the derivative distance.\n* In Proposition 1, what will happen if the target agents are a subset of all agents? I.e., for example, if the attacker can manipulate the utilities of two agents, is there any related result?\n* Minor typo: There is a missing \".\" in Line 390.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper considers an interesting topic: Attacking a single agent in multi-agent learning. The two main contributions are both noteworthy:\n\n* The first main result indicates that to shift the global equilibrium, an attacker only needs to target one agent with sublinear cost. This practical finding provides valuable insights into the potential risks of multi-agent learning. \n\n* Second, the trade-off between efficiency and robustness is very interesting. I believe this will provide some heuristic for the design of robust algorithms.\n\nMoreover, this paper is well-written.", "weaknesses": "I have several concerns about this paper:\n\n1. The assumptions underlying the proposed attack are quite strong. (1) As the author admits,the adversary is assumed to have complete knowledge of the victim agent's utility function. This assumption, while useful for theoretical analysis, may not hold in practical scenarios, potentially limiting the contribution. (2) The agent is assumed to be unaware of the attacker's presence. If the agents do know, will the attack still work?\n\n2. There’s no knowledge regarding the difficulty of the problem. In other words, can the authors show any lower bound on the cost, which will further indicate the efficiency of the attack? It is worth noting that in a similar topic which is also mentioned by this paper, $[1]$ has already closed such a gap. Furthermore, Figure 2 illustrates the significance of this concern, as in the last sub-figure, the cost increases at an almost linear rate. What’s more, this $\\alpha$ is determined by the dynamic itself, therefore it cannot be well controlled. Thus, the cumulative cost is quite large to some degree. After all, both $\\log(\\log(T))$ and $T^{1-\\alpha}$ are sublinear, but their outcomes are totally different.\n\n3. The authors may have partially overstated their work. The problem they considered is a specific attack problem in monotone games, however, the title and introduction demonstrate greater ambition (in general games). Whether the results can be generalized remains unknown.\n\n[1] Zuo, S. (2024, April). Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses. In International Conference on Artificial Intelligence and Statistics (pp. 2098-2106). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)