How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents
Authors: Yoav Kolumbus
Noam Nisan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Regret minimization
Meta games
User incentives
Parameter manipulation
Learning agents
Algorithmic game theory
Multi-agent systems

Abstract: The usage of automated learning agents is becoming increasingly prevalent in many online economic applications such as online auctions and automated trading. Motivated by such applications, this paper is dedicated to fundamental modeling and analysis of the strategic situations that the users of automated learning agents are facing. We consider strategic settings where several users engage in a repeated online interaction, assisted by regret-minimizing learning agents that repeatedly play a "game" on their behalf. We propose to view the outcomes of the agents' dynamics as inducing a "meta-game" between the users. Our main focus is on whether users can benefit in this meta-game from "manipulating" their own agents by misreporting their parameters to them. We define a general framework to model and analyze these strategic interactions between users of learning agents for general games and analyze the equilibria induced between the users in three classes of games. We show that, generally, users have incentives to misreport their parameters to their own agents, and that such strategic user behavior can lead to very different outcomes than those anticipated by standard analysis. 

How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents
Yoav Kolumbus
Noam Nisan The Hebrew University of Jerusalem noamêcs. Saan@cs.hujia a.c.. il
The Hebrew University of Jerusalem yoav. kolumbus@maal. wwwji.ac..
Abstract
The usage of automated learning agents is becoming increasingly prevalent in many online economic applications such as online auctions and automated trading. Motivated by such applications, this paper is dedicated fundamental modeling and analysis of the strategic situations that the users of automated learning agents are facing. We consider strategic settings where several users engage in repeated online interaction, assisted by regret- segretiminmmizing learning agents that repeatedly play "game" on their behalf. We propose view the outcomes of the agents' dynamics as inducing "meta-game whether users can benefit in this meta-game from "manipulating" their own agents by misreporting their parameters to them. We define general framework to model and analyze these strategic interactions between users of learning agents for general games and analyze the equilibria induced between the users in three classes of games. We show that, generally, users have incentives to misreport their parameters to their own agents, and that such strategic user behavior can lead very different outcomes than those anticipated by standard analysis.
between the users. Our main focus is on
1 Introduction
This paper deals with the following common type of scenario: several users engage in some strategic online interaction, where each of them is assisted by learning agent. A typical example is advertisers that compete for advertising slots over some platform. Typically, each of these advertisers enters his key parameters into some favertiser-facing website, and then this website's 's "agent" participates the advertiser's s behalf in a sequence of auctions for slots. Often, the platform designer provides this agent its advertiser-facing user interface. In cases where the platform's 's agent does not optimize sufficiently well for the advertiser (but rather, say, for the auctioneer), one would expect some other company to provide better (for the advertiser) agent.
The basic model for such scenarios is as follows. There is an underlying n-person game that n "software learning agents" will play repeatedly. Some of the parameters of this game, typically the players' utilities, are private to the n "human users," and each of these users enters his key parameters into his own software agent. From this point on, these software agents repeatedly play the game on behalf of their users, where each agent aims to optimize the utility of its owner according to the parameters reported to it by using some learning algorithm. A typical learning algorithm of this type will have at its core some regret-minimization algorithm [15,47), such as "multiplicative weights" "
[1, "online gradient descent" (94] perturbed leader" 45 51.
variant of fictitious play [8 79
such "follow the
On intuitive level, these agents, playing between themselves, each aiming to maximize its owner's utility, will reach some kind of a game-theoretic equilibrium of the underlying game, and the average utilities of the agents over time will converge to the utilities of this equilibrium. Specifically, while it known that the dynamics of rregre--miimizzatin algorithms may fail to converge to any equilibrium
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

6 48 76.. it is also known that the empirical play statistics of no-regret dynamics do approach what sometimes called coarse correlated equilibrium [ 47 92 (CCE). The notion of coarse comelated equilibrium is a generalized weaker notion than the Nash equilibrium!" formalization of the no-regret property for each agent. For formal definitions and further discussion and analysis of regre--minimization dynamics, see Appendix A in the Supplementary Material.
T and is essentially a
While the dynamics of learning agents in repeated games and their convergence properties have been 18
the focus of extensive studies since the early days of game theory 13 14]
45
79 33 and in later
88 our focus is on different question of analyzing the incentives of the users of such agents. In our scenario where (human) users report some of their parameters to their (software) agents, the learning process of the agents depends on the parameters that the users report to them. This motivates the following question: Given a game and a set of learning agents (one for each user), what parameters should the users report to their own learning agents?
works, e.g., L5 26 36 37
Since in the reached equilibrium every agent is best-replying to the others' behavior, it would seem obvious that each user would maximize his utility by indeed reporting his true parameters his own agent, thus indeed allowing the agent to optimize for the true utilities. However, as we show, on closer inspection, this is not necessarily true: while user guaranteed that his agent best-replies to the others' empirical play (in the sense of having low regret), this empirical play itself of the other agents and the outcome of the joint dynamics are dependent on the behavior of our user's own agent. Thus, the interactions between the agents induce a "meta-game actions are the parameters that they report to their own agents, and the users' utilities are determined by the long-term empirical average of the agents' joint dynamics.
between the users, in which the users'
This is somewhat similar to the situation in classic repeated games: since agents respond to the previous actions of the other players, the "dynamics" do not necessarily give an equilibrium of the underlying single-shot game. In fact, the folk theorem characterizes a wide set of equilibria of the repeated game that can be reached using the correct combination of punishments and rewards that
each player uses affect the others' behavior (see, e.g.. [ [22 75 81) ). In some sense, the critical aspect here is a "theory of mind" that players have about each other, which enables them to understand how punishments and rewards affect the other players' play in the equilibrium of the repeated game.
By contrast, in our case, regret-minimizing agents have no "theory of mind" since they are each blindly following their own regret-minimizztion strategy. In particular, user's agent never aims to punish or reward another agent. A user that aims to influence the outcome of the repeated play between regret- ggrret-minmmzzig agents must in some sense have "theory of mind" of regret-minimizing agents, both of his own agent as well as of the other agents.
In this paper we establish the first steps in the theoretical modeling and analysis of the incentives of users of such automated learning agents in online strategic systems. We analyze three classes of games: dominance-solvabbee games, Cournot competition games, and opposing-interre interests games, and demonstrate how in all these different settings, users generally have incentives to manipulate their own learning agents by misreporting their parameters to them, and how equilibria of the users' game can have different properties and outcomes than those of the original underlying game.
Our results underline the importance of considering and analyzing user incentives: when a strategic system is accessible to its users through learning agents, its original properties are not necessarily preserved, and even strong notions like strict domination may no longer hold, and so meta-game analysis is required in order to understand or anticipate the actual outcomes. Our results focus on demonstrating the types of phenomena that can happen due to strategic behavior of users of learning algorithms and on showcasing them in games that are as transparent for analysis and as simple as possible. The framework that we propose is general for any learning dynamics and can be studied
in any game- either analytically or by using simulations. In a companion paper [53] we use the model that we propose here analyze repeated auctions with regret-minimizing agents, and show that these phenomena indeed occur also in the auction setting. That is, counterintuitively. in the first-price auction users prefer submit truthful reports to their agents, while in the dlominant-stratege truthful) second-price auction users have incentives to manipulate their own agents by submitting non-truthful reports of their valuations.
I For games in which there are at most two actions for each player this notion is equivalent to Aumann's correlated equilibrium 2 B). but for general games it is weaker and more general notion.

---

2 The Meta-Game Model
We define the "meta-game" between "users" ("players") in terms of the outcomes of the repeated games that their agents play on their behalf. In our definition, all that we formally need from these agents is that they repeatedly interact with each other, where at each point in time each agent's algorithm has observed the past play of all agents in all previous time steps, and then needs to determine its own next action based on this information (and the parameters given by its user). Intuitively, however, specificallly, meggeiimin agents.
are thinking of agents that aim maximize some utility for their user,
Definition 1. A user-agent meta-game has the following ingredients.
Users and Agents: We have "human" users, each with his fixed "software" learning agent.
Agent Strategy Spaces An: The agents "play" against each other for a period of time steps, where each step t = 1..., T each agent i plays an action oe E AA and then gets as feedback the actual play of all the agents a' = =.ai...,, d,,).
User Parameter Spaces PI....,Prr Each user i inputs "declaration" " P.EP, into his agent.
Agent Utility Functions Ui, Un: The utility function of agent is u; P.x x...XX An + R. At each time step each agent gets a utility of u. a'), where Ps are the parameters given to it by its user. Our agents aim to maximize this utility.
User True Types $1, Sni Each user has "true" type 9; E P: that describes the true utility of the user. The utility of user when his true type 8,, and when each user j declares Pj P3 to his agent, is U2(Si, pi..... .....-...)> = (E wi(si, aa) ())T))TTTT where for each 1 -.., T, a is the vector of actions played by the agents at time step I, as defined above. If the agents are randomized, then this expression is actually a random variable, and we define Ug to be its expectation.
The User Meta-Game: Fixing the true parameters (81, 8n). we get an n-person game between the users, where user i's strategy space is P: and his utility is U:(ss,)) )).
This model is formally defined for any game, fixed tuple of learning algorithms, and fixed "horizon" T, and for any such the ensuing meta-game be directly studied by simulations. In order to proceed and thcoretically study this meta-gant as the horizon T' goes to infinity, we would require a setting where it is possible to theoretically analyze the utilities of the resulting dynamics both for the true types (parameters) 8; and for possible deviations P; * 8;- The theoretical analysis in the following sections concerns all regret-minimize miniiziiiniii algorithms, in the "limit" T co, where the agents' game converges to a known CCE. For further discussion on the convergence of eegret-minmmzzing agents, see Appendix A. We note that while our focus on regret-minimization dynamics, all our results hold also under an alternative interpretation of our model in which the agents reach a CCE of the game with the declared parameters via an arbitrary black-box device.
will study cases
For the games studied, we will start with basic questions like what is the best reply of a player to another player in the meta-game and then proceed to more advanced questions, specifically, in which cases is the truth p. = 8; a best reply in the meta neta-game, and when this is not the case, what is the Nash equilibrium of the meta- gamt. All proofs in this paper deferred to the appendix.
Definition 2. A user-agent meta-game is called manipulation-fer free if the truth- rruth-telling declaration profile, iee, all users declaring p; = 8ú, is a Nash equilibrium of the meta meeaa-gam!??
3 Dominance-Solvable Games
The first class of games that we consider are dominance-solvable games. A main interest in the literature in studying these types of games has been as design objectives due to their stable strategic structure, e.g., for voting mechanisms [31 [66] and contract design [5] 44 80). Formally, games of this class have a unique pure Nash equilibrium that is also the single CCE, and thus we know that the
This definition is for a fixed game that is defined by the true parameters 81, .... Sn. (but in the context of given parameter spaces Pr.... P.). One may also naturally look at the family of games for all possible $1, s,, and discuss truthfulness in the sense used in mechanism design (71). but we leave this for further follow-up up work.
3

---

1, 3
3, 4
C, d
3, 4
2, 2
2, 2
4,
An example of parameter manipulation in a dominance-solvable game. Left: the payoff' matrix of the true game. Right: the manipulated payoff's that the players provide their learning agents, The row player selects the parameter and the column player selects the parameter d.
Figure I:
empirical play statistics of any regret-minimization dynamics will provide, the limit, the utilities of this equilibrium. For completeness, give here the definition of a seciiianne-sslvvblle game.
Definition 3. A game called dominance solvable if there exists an order of iterated elimination of strictly dominated strategies that leads single strategy profile (the unique Nash equilibrium).
We show that even in these strategically simple games, users of learning agents face non- con-trivial strategic considerations, and, specifically, even users who have a dominant strategy in the game may obtain further gains (beyond their dominant-stratee strategy outcome) by manipulating their own agents.
We begin by demonstrating our agenda on a simple 2x2 2 two-person game where one of the players has dominant strategy. The other player then has strict best reply, and so the game is dominance- solvable. It is not difficult to see that any dynamics of regret-mininizing learning agents playing such game will converge the pure equilibrium, since the agent with the dominant strategy will learn to play only its dominating strategy, regardless of the actions of the second agent, and then the second agent will learn to best-reply that. Formally, the time average of regret-minimization dynamics must converge to the (unique) Nash equilibrium as it is also the unique CCE. For further details, see Appendix B.
This simple analysis also shows that the other player has no profitable manipulation: since the agent of the player with the dominant strategy can indeed learn to play it whatever the other player does, the other player can do no better than to best-reply to the dominant strategy.
It may also seem intuitive that the player with the dominant strategy have profitable manipula- tion either, but this turns out to be false. Consider the game depicted in Figure I (left), in which the row player has dominant strategy to play the bottom row. The unique pure Nash equilibrium of this game gives the row player utility U1 2. We now get to our point where the utility of each player private him (at least partially). In our example, suppose that the constants 1 and 3 in the game description are private to the two users, respectively, and that each learning agent gets the value of the parameter (c and d, respectively) from their users. After each agent gets its own parameter, the two agents then engage in repeated play. In this play, each agent minimizes regret for its owner in the game with the parameters that were given il (rather than the true parameters that known only to the user), as shown in Figure (right). the row player declares instead of the true = 1 a value of, say, e 5. then the (declared) game has a unique mixed Nash equilibrium, which is also its unique CCE (20 667,, where the row player plays the top row with probability = 1/2, and the column player plays the left column with probability g = 1/4, giving the row player a utility of #ı 3. Declaring an even higher value e + oo will decrease q - 0, leading to higher utility of u2 - 3.5.
Once the row player has manipulated his input, the column player may also beneficially do The meta meta-game does not literally have a Nash equilibrium (as the strategy spaces of the players are a continuum and no continuity of utility is guaranteed), but it has e-equilibrium for any 0: as c + oo and d = 4 - ā with >> 0 and 5 - O. In this case, p > and - 0, leading to an c-equilibrium with utilities u1 3, 122 -> 4.
Notice that the outcome in this e-equilibrium of the meta-game strictly Pareto-dominates the Nash equilibrium of the original game, and thus we may say that the players managed to reach cooperative outcome. The logic behind this cooperation is that the player with the dominant strategy is given the opportunity take the point of view of Stackelberg game where he goes first and the other player best-replies to his strategy. If the dominated strategy is the preferable strategy in the Stackelberg game, it is in example, then a manipulation approach it.
In e-equilibrium no player can gain than by deviating.

---

This example demonstrates how even in very simple games, users may have incentives to misreport their parameters to their agents, and that even a strong notion like strict domination does not guarantee the stability of truthful declarations. This phenomenon is in fact general for a large class of games:
Theorem 1.
In any n x m game where one of the players has a dominant strategy, if the Stackelberg outcome of the game is different from the truthful Nash equilibrium outcome, then, for a sufficiently wide user parameter space, the game is not manipulation- free, and, specificully, the player with the dominant strategy has an incentive to manipulate his declaration.
For the special case of 22x games this result holds even when users can manipulate only a single one of their parameters, and for specific subclasses of games it is possible to characterize the equilibria of the meta-game, as in our example above. Additionally, Theorem T is in fact even more general and applies not only to games with a dominant strategy, but to any dominance-solvvan some player has a Stackelberg value that higher than his utility in the truthful Nash equilibrium.
n x m game where
4 Cournot Competition Games
The second class of games that we consider are the classic Cournot competition games 25 34 63
with linear demand functions and linear production costs. These games are contained in a class of games called "socially concave" that were identified by [34]. who showed that for games of this class the time-average distribution of any regret-minimizs minimization dynamics converges to the unique Nash equilibrium of the game, and so we can confidently analyze the utilities obtained in the meta -ama-e
We consider a game between two firms that are competing for buyers by controlling the quantity that each of them produces. There is demand function that specifies the market price for any given total quantity produced. In our case we assume that the demand function is linear; i.e., if the two firms produce quantities qi and q2 respectively then the market price will be aa-b- b. (gi + q2). where a and b are commonly known positive constants. The private parameter that each firm will have is its production costs, which we also assume are linear; i.e., firm i's cost produce quantity qi is exactly 4: where 0 S c S a is privately known to firm i. The utility of firm 1 is given by un (91, 92) q1 (a b- (q1 + 92) - cı); similarly, u2 ug(g1, 92) q2 (a b (g1 + 92) -2)).
The Nash equilibrium of the game depends on the parameters as follows. If a + C2 2c1 > 0 and + 0 202 0, then the Nash equilibrium is q: 35 (a + 02 2m)) and qa = 35 (a + c 202)). If + c- - 20g > 0 and C1 < a, the Nash equilibrium is qı = a-m and ø2 = 0, and symmetrically,
22
a + C2 - 22,, > and C2 < a, the equilibrium is q = 0 and d = 26 Otherwise, in the Nash
equilibrium both players produce zero
Thus, there are four parameter regions of interest associated with the four possible types of unique Nash equiliiriaa of the game, illustrated in Figure 2 The parameter region A {c1, cyla-
22 22c > 0, a + c1 - 202- > 0, e1 > 0, C2 > 0F is the region where both agents produce positive quantities (the shaded areas in region A in the figure relate to equilibria of the meta-game, as explained below). The parameter regions B- = /ci,0gle + C1 20g > 0, 0 < c1 < a, C2 > 0} and
C = fci, C2 C2 2c1= > 0, 0 < C2 < a, C1 > 0} are regions where only one player produces positive quantity. In the remaining region, region D = {cr, 02/c1, C2 2 a}, both agents produce zero.
As running example, we will consider the case where a = b = 1 and e₁ = C2 = 1/2, for which the standard analysis yields that in equilibrium each player produces the quantity 4: = 1/6, the price is thus 2/3, and the utility of each player is 1/36.
We now turn to look at the meta-game in which each player reports his production cost to his own agent, and then the agents repeatedly play the declared game. That is, each player i reports a declared cost S x; S a in the parameter space and then the agents reach the equilibria with the declared costs. It turns out that in our example, firm I's best reply to firm 2's true cost is 21 = 3/8, rather than the truth e 1/2, which increases its utility (calculated, of course, according to the true costs) to 1/32 > 1/36. That is, the firm under-represents its production costs to its own agent, causing the agent to over-prdduce. While this ovor-pronnttion by itself hurts our user (the firm), the benefit is that our user as opposed to its automated learning agent- understands that this aggressive declaration will lead to a reduction in the production of the other firm's 's agent, making up, and more, for the revenue loss from its own over- over-produss productouit.on.
5

---

Figure 2: Parameter declaration regions in Cournot competition games.
Analyzing the equilibrium of the mneta-game between the users, one obtains that the equilibrium is the declaration profile 21 Z2 = 2/5, rather than the truthful declarations = 1/2. That is, the two players under-represent their production costs their agents, causing them to over-vvedeeeeoooo over-produce. where each of them produces a quantity 9; = 1/5, which is strictly higher than the production of 1/6 obtained in the equilibrium of the truthful game. In the equilibrium of the meta-game the utility of each of the two players drops to 1/50,, which is significantly less than the original utility of 1 1/66. We see that the players are locked here in sort of prisoners' dilemma where each of them benefits from unilateral deviation from the truth, but when they both deviate, they both suffer losses.
Our analysis shows that these comparative staties generalize long as both players keep producing non-zero quantity in the meta- game equilibrium. In some cases, which we explicitly describe below, the player with lower costs can under-represent his costs in sufficiently extreme way so as to drive the other player completely out of the market. In such cases the quantity produced by the player who remains in the market still larger than the total quantity produced by both players when they play the truth in the meta- meta-game, but his utility increases. We also completely characterize the rather limited set of cases where the game manipulation-free
Theorem 2. (1) In any two-player linear Cournot competition with linear production costs, the total quantity produced in the equilibrium of the meta- game is greater than or equal the total quantity produced when the players play the truth in the meta-game, and the price is thus lower. (2) If both players continue to produce a non-zero quantity the meta- gamee equilibrium, then their utilities are less than or equal to their utilities when both play the truth in the meta- meta-game game. If. on the other hand, one of the players produces zero in the meta nema- equilibrium, then the utility of the producing player is greater than or equal to his utility when both play the truth in the meta- meta-game game.
Theorem 3. In two-player linear Cournot competition with linear production costs, the meta- gala-gamme is manipulation-free if and only if either (at least) one of the players produces zero when both play the truth in the meta-game, both players have zero production costs, C2 O.
Figure 2 illustrates the parameter ranges in which the different types of equilibria of the game exist. The dark-shaded areas show the parameter ranges where in the equilibrium of the meta-gan game the player with the low production cost drives the other competitor out of the market, and the light- shaded area shows the parameter range where both players declare costs lower than their true costs and produce positive quantities in the equilibrium of the meta- neta-game. The regions denoted in the figure by 21 = 0 and agents in equilibrium, and the region denoted by 0, 0 the range where both players declare zero in equilibrium. In the remaining kite-shaped region in region A, both players declare positive costs that are less than their true costs. Finally, in regions B, C, and D, there is no competition and the equilibrium declarations are truthful. For further details, Appendix C.
0 show where players 1 and 2, respectively, declare a cost of zero to their

---

2,
-1,
c-1
-, 1
-1,
1,-1
-1,d
1,11
Figure 3: An example of parameter manipulation in an opposing-interests game. Left: the payoff' matrix of the true game. Right: the manipulated payoff's that the players provide their learning agents, The row player selects the parameter and the column player selects the parameter d.
5 Opposing-Interest Games
The next class of games that we analyze are games in which there is a single mixed Nash equilibrium and no pure equilibrium. The prototypical example is matching pennies. In these games, often called fully mixed games, the unique Nash equilibrium is also the unique coarse correlated equilibrium 20 67,, and thus the dynamics of regret-minimizing agents will approach this equilibrium. We focus on subclass called opposing- eoposing-interests interests games, where the first player gets higher utilities along the main diagonal than he gets along the other diagonal, and the opposite is true for the second player. This subclass of fully mixed games includes many games that are similar to matching pennies, and specifically includes all constant-sum games that are fully mixed.
We begin with an example of the following variant of matching pennies, where one of the utilities for each player is changed from the standard value of I to another value, as shown in Figure (left).
standard analysis shows that the single mixed Nash equilibrium of this game is where the row player plays the top row with probability p= 2/3 (and plays the bottom row with probability 1-p and the column player plays the left column with probability g = 2/5 (and the right column with probability q 3/5). Calculating the utilities of the two players in this equilibrium gives us 21 = 1/5 for the row player, and Ui = 1/3 for the column player. Running a (typical) simulation of learning agents that repeatedly play this game against each other, we observe the dynamics shown in Figure 4a As is well known 77 48 76), and as we can clearly see, there is no convergence in the behavior of the agents. However, if write down the empirical probabilities of play of each of the four combinations of the players' strategies (as shown in Figure 4b) we get (close to) the Nash equilibrium probabilities, as theoretically expected 20
p = 1/3),,
multiplicative-weiie
In our example, suppose that the constants 2 and 3 in the game description are parameters that the two users, respectively, declare their agents, as shown in (right))))) Now we ask ourselves, what should the players do in order to maximize their utility? What parameter should, say, the row player report to his agent as maximize his expected utility over the whole run of the learning agents? It would seem natural to assume that entering the true value, in our case 2, should be the best possible: after all, the agent is optimizing for the value entered into it, and so the row player should give his agent the correct value to optimize for. However, as we have seen also in other types of games, this intuition is again false. Suppose that the row player reports, e.g., C learning agent (and suppose that the column player sticks to the truth, d = 3). When the two agents now repeatedly play against each other they reach (in the limit empirical distribution sense) the Nash equilibrium of the game with these values of the parameters, which, as one may calculate, is p = 2/3, q 1/2. The utility of the row player, whose true value is e = 2, in this resulting distribution is 211 = 1/3, which is greater than his "truth-telling" utility of 1/5, as we have seen above
his parameter his
*There are two reasons for not reaching exactly the Nash equilibrium. First, as our simulations are only for a finite number of steps and with a finite step size, the multiplicative-weighh algorithm does not fully minimize regret but only nearly so, and thus leads only to near-equilibrium. Second, as the algorithm is randomized there is an expected stochastic error. These error terms are theoretically of an order of magnitude of O(1/VT), where T' is the number of rounds, which fits the observed deviations in our simulation for T = 50,000 rounds.
'This improvement is even more puzzling when we take closer look: in the Nash equilibrium of the original game, the row player has mixed between his two pure strategies, implying that they both give him the same utility. Thus, the only way that our row agent can improve his utility is by first causing the column player's 's agent change its distribution of play, and only then it could take advantage of this change. The column player's agent's 's behavior, however, does not depend directly on the row player's utilities. The solution is that there an indirect dependence that goes through the actual play of the row agent. Taking advantage of this indirect dependence obviously requires understanding the "theory of mind" of the column agent's 's's algorithm. In our case. the row understands that the agents' dynamics will reach the Nash equilibrium of the declared game, he
7

---

Nash equilibrium distribution
4 0.4
9 0.6
p 0.667
0.267
0.133
Stratogy proflic
= 0.333
0.4
0.2
Empirical distribution
0.405
9 = 0.595
p 0.665
0.270
0.135
0.335
0.395
0.200
2500
5000
10000 12500 15600 17500 20000
Timee Igame
(a) Mixed strategy dynamics
(b) Empirical and Nash equilibrium action distributions
Figure 4: Dynamics and payoff' in the game shown Figure Left: dynamics of multiplicative- weights agents in the game with the true parameters 2, d 3. Right: the Nash equilibrium distribution and the empirical action distribution from simulations multiplicativ--eeigte agents.
Just the player gain by misreporting his utility to his agent, can the column player. Had the column player declared d = (now with the row player declaring the truth e = 2). his utility would have increased to u2 2/5. Had they both manipulated their "bids" and declared = 1, d = 1 to their respective agents, then both would have benefited relative to telling the truth, getting utilities of u1 1/4 and t2 = 1/2.
Next, let us look for an equilibrium the users' game. need to determine for which declarations dl will neither of the two players wishes to unilaterally change his declaration (where the true utilities are still set to c = 2. declarations in the meta-game, are 3, d 1/3. The equilibrium of the declared game that is played between the agents in this case is = 2/5 and = 1/3. The utilities of the two players (according to the true game parameters) in this distribution details, see Appendix D). Surprisingly, these are the same utilities that our players obtained when telling the truth. In fact, this result is not coincidence. The following theorem characterizes the equilibrium of the meta-game and the utilities obtained in While our example we fixed simple parameter space where was the single parameter of the first player and d the single parameter of the second player, the following results apply to a wide range of parameter spaces where any one of the utilities of each player in the game is a parameter that the player analysis is for the "limit" meta- game and holds for every pair of regret-minimizing agents.
in our example). Our analysis shows that the equilibrium
1/5 and U2 1/3 (for further
manipulate. As mentioned, this
Theorem 4. In aaposing-interesse 2x2 games, the utilities of the two players an equilibrium of the meta- game are the same as the utilities obtained when both play the truth in the mela mela-game game.
Thus, in these types of games the players have incentives to unilaterally manipulate their own agents, but in equilibrium they can neither cooperate in the sense of improving their utilities nor do they suffer losses. This is in contrast to what we saw in dominance-sob sollvabbeee games and in Cournot competition games. Additionally, we characterize the cases where these games manipulation -rree:
Theorem 5. An opposing interests 2x2 game is manipulation-fiee if and only if its Nash equilibrium symmetric under player permutations (i.e., the same equilibrium distribution is obtained when player indices are switched).
6 Further Related Work
Regret minimization in repeated strategic interactions and in online decision problems has been extensively studied in the literatures of game theory, machine learning, and optimization. Early regret-minimizztion algorithms were related to the notion of fictitious play [8] 79 (a.k.a. "follow the leader"), which in its basic form does not guarantee low regret, but its smoothed variants, such
as "follow the perturbed leader" (FTPL) 41 45 50 51 and "follow the regularized leader" (FTRL) 22 are known to guarantee an adversarial regret of O (vT) in T decision periods; for more recent
can manipulate the parameter that he gives to his agent to indirectly cause increase in g, the probability that the column agent plays the first column, action that the player finds favorable.

---

Other common approaches to regret- based learning are the "multiplicative-wegeee -eightss algorithm, which has been developed and studied in many variants (see [1] and references therein, and see [23 26 77 for results on more advanced variants of this algorithm), and the family of algorithms that are based on the regret-matching approach that has
advances along these lines see, e.g., 227 65 88
been well studied in several settings (see [4]] and references therein). For a broad discussion and for
further references on regret- mingmiiiniii dynamics, see [88] and [22].
Our work formalizes the meta-game faced by users of regret-minimizing learning algorithms, and asks whether and when users can benefit from manipulating their own agents. To our knowledge, there is no prior analysis or modeling of these strategic interactions between users of learning agents (which are induced by the dynamics of their agents). In a companion paper [53), we study an application of our meta -gaee model in auctions, where we analyze the dynamics and outcomes of repeated auctions played between regret-minimizing agents of a class that includes many natural algorithms such as multiplicative weights. We show in that paper that in the meta-game induced between the users of such auto- aito-bidding agents, the second- price auction loses its compaibllyy property, while the first-price auction becomes incentive compatible.
As discussed in the introduction, our work is related to the broad field of equilibria in repeated games [6]] [75] but the situation that the users of learning agents in our setting are facing differs from classic repeated games in significant aspects. Conceptually closer works are [66] that study equilibria between policies in the repeated game (i.e., strategies that are conditional on the history of play), and
works on program equilibria (55] 73 74 [9 in which each agent can read the commitments made by the other agents and condition its actions on these commitments. These models, however, are technically very different from our model, and in particular, the notions of equilibrium are different from a meta-game equilibrium.
In broader perspective, our work is related to a research area that can be called "strategic consider- ations in machine-learning systems," with a growing body of work at the intersection of machine learning, algorithmic game theory, and artificial intelligence that addresses this topic from different perspectives, including learning from strategic data [9 24 32
40
43
46
58 Stackelberg games
770 (84) and recommendation systems [10 90). More closely 30 62,, which deal with optimization against gegret-minimizing agents. The possibility of obtaining increased gains when playing against a no-regret algorithm that is studied in these works is conceptually close to our work. A basic difference, however, is that these works consider single optimizer facing a no-regret algorithm- setting that induces optimization problems, rather than games whereas we study games between the users that are induced by their learning agents' dynamics, and in which all users can act strategically and reason about the strategies their peers. Additionally, in the meta-game a user does not need to select the actual step-by-step actions in the repeated game, but instead chooses the declaration to input into the automated agent, whereas the direct optimization over the action space of the underlying game is performed only by the agents.
12 39], security games [8
42
69
related works are [17
Finally, the idea that inputting "wrong" reward function into a learning algorithm can in some cases improve actual outcomes has been long known in the context of reinforcement learning 9 54
85 86 87]. Specifically, and closer to our context, in Markov games (60) it has been shown that the dynamics of reinforcement learners with certain intrinsic reward functions can lead to improved actual utility to all the agents playing the game 4 33 49 57]. This literature, however, does not consider interactions between users of such agents and their incentives when entering their parameters into their learning agents. We view the analysis of our model for Markov games with reinforcement-eemming agents as natural and interesting extension, but we leave this for future work, and focus in the current paper on repeated games with
agents.
7 Conclusion
The present study deals with the modeling and analysis of scenarios in which human players use autonomous learning agents to perform strategic interactions with other players on their behalf. The usage of automated learning agents is becoming increasingly common and prominent in many real-
world economic systems and online interactions such as online auctions [8. 28
29
53 68 64 72),
(78) Understanding the impact of this transition to automated agents on strategic systems and on their outcomes is a challenge in itself, and a prerequisite for studying how to better design such inntraccttinntaaatiiino systems.
financial markets [56] 59 91 93 and other systems

---

The framework that we propose for analyzing the meta- games between the users, and the results of our analysis, highlight the fact that the strategic nature of interactions does not disappear and does not remain the same when direct human play is replaced by automated agents, but rather the introduction of these learning agents changes in specific ways the rules of the game that the human users (who are the actual stakeholders in the system) are facing. Every automated agent that operates in a system on behalf of its user needs to receive some input from the user (such as preferences, goals, or constraints); user faces non-trivial strategic decision in which he needs to consider also the decisions of the other users. The goal of our model is to describe these interactions and formalize them.
show that at this interaction point between user and his own learning agent, the
Our contributions in this paper include the basic definitions related these phenomena, demonstra- tions of how users of learning agents can profitably manipulate their own agents in several settings, as well as identification of cases where this cannot done. These results have implications both for users of learning agents in strategic settings and for platform designers who need to take into account these types of manipulations. We believe that the present paper, along with its companion paper [53] where we study these phenomena in online auctions, only scratch the surface of these types of questions, and much work remains to be done.
Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 Research and Innovation Programme (grant agreement no. 740282).
References
[1] Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing 8(1). 121-164 (2012)
[2] Aumann, R.J.: Subjectivity and correlation in randomized strategies. Journal of mathematical Economics 1(1), 67-96 (1974)
[3] Aumann, RJJ.: Correlated equilibrium as expression of bayesian rationality. Econometrica:
Journal of the Econometric Society pp. 1-18 (1987)
[4] Austerweil, J.L.,, Brawner, S., Greenwald, A., Hilliard, E.,, Ho, M., Littman, M.L.,, MacGlashan, J., Trimbach, C.: How other-regarding preferences can promote cooperation in non-zero-sum grid games. In: Proceedings of the AAAI Symposium on Challenges and Opportunities in Multiagent Learning for the Real World (2016)
[5] Babaioff, M., Kolumbus, Y., Winter, E.: Optimal collaterals in multi-enterprise investment networks. In: Proceedings of the ACM Web Conference 2022. pp. 79 9989 (2022), https:
//dl. wttp////////oooo/o//////oo//oo/t 1145/3485447 0001447355110 35522053
[6] Bailey, J.P., Nagarajan, S.G., Piliouras, G.: Stochastic multiplicative weights updates in zero- sum games. arXiv preprint wrXivv22110002 (2021)
[7] Bailey, J.P., Piliouras, G.: Multiplicative weights update in zero-sum games. In: Proceedings of the 2018 ACM Conference Economics and Computation. pp. 321-338 (2018)
[8] Balseiro, S., Deng, Y., Mao, J., Mirrokni, V., Zuo, S.: Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems 34 (2021)
[9] Barto, A.G.: Intrinsic motivation and reinforcement learning. In: Intrinsically motivated learning in natural and artificial systems, pp. 17-47. Springer (2013)
[10] Ben-Porat O., Tennenholtz, M.: A game-theoretic approach to recommendation systems with strategic content providers. In: Proceedings of the 32nd International Conference on Neural
Information Processing Systems. pp. 1118-1128 (2018)
[11] Benoit, J.P., Krishna. V., et al.: Finitely repeated games (1984)
[12] Birmpas, G., Gan, J., Hollender, A., Marmolejo, F., Rajgopal, N., Voudouris, A.: Optimally deceiving learning leader in stackelberg games. Advances in Neural Information Processing Systems (2020)
[13] Blackwell, D.: An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics 6(1), 1-8 (1956)
10

---

[14] Blackwell, D., et al.: Controlled random walks. In: Proceedings of the international congress of mathematicianss. vol. 3. pp. 336-338 (1954)
[15] Blum, A., Monsour, Y.: Learning, regret minimization, and equilibria (2007)
[16] Brafman, R., Tennenholtz, M.: Efficient learning equilibrium. Advances Neural Information
Processing Systems 15 (2002)
[17] Braverman, M., Mao, J., Schneider, J., Weinberg, M.: Sclling no-regret buyer. In: Proceed-
ings of the 2018 ACM Conference on Economics and Computation. pp. 523-538 (2018)
[18] Brown, G. W.: Iterative solution of games by fictitious play, Activity analysis of production and allocation 13(1), 374-376 (1951)
[19] Cai, Y., Daskalakis, C., Papadimitriou, C.: Optimum statistical estimation with strategic data sources. In: Conference Learning Theory. pp. 280-288099000 296. PMLR (2015)
[20]
Calvó-Armengol, A.: The of correlated equilibria of 2x2 games. Working paper (2006)
[21] Cesa-Bianchi, N., Gentile, C., Mansour, Y.: Regret minimization for reserve prices in second- price auctions. IEFE Transactions on Information Theory 61 549-564 (2014)
[22] Cesa-Bianchi, N., Lugosi, G.: Prediction, learning, and games. Cambridge university press (2006)
[23] Chen, X., Peng, B.: Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems 33 pre-proceedings (NeurIPS 2020) (2020)
[24] Chen, Y., Liu, Y., Podimata, C.: Learning strategy-aware linear classifiers. Advances in Neural Information Processing Systems 33, 15265-15276 (2020)
[25] Cournot, A.A.: Recherches sur les principes mathématiques de la théorie des richesses. L.
Hachette (1838)
[26] Daskalakis, C., Fishelson, M., Golowich, N.: Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems 34 (2021)
[27] Daskalakis, C., Panageas, I.: Last-iterate convergence: Zero-sum games and constrained min- max optimization. In: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl- Pagstuhl-Leeibniz-ZZee Leibiiz-Zetruum fuer Informatik (2018)
[28] Daskalakis, C., Syrgkamis, V.: Learning in auctions: Regret is hard, envy is easy. In: 2016 icce 57th annual symposium foundations of computer science (focs). pp. 219-228. IEEE (2016)
[29] Deng, Y., Mao, J., Mirrokni, V., Zuo, S.: Towards efficient auctions in auto-bidding world. In: Proceedings of the Web Conference 2021 (2021)
[30] Deng, Y., Schneider, J., Sivan, B.: Strategizing against no-regret learners. Advances in Neural Information Processing Systems 32, 1589-1587 (2019)
[31] Dhillon, A., Lockwood, B.: When are plurality rule voting games dominance-solvable? Games and Economic Behavior 46(1), 55-75 (2004)
[32] Dong, J., Roth, A., Schutzman, Z., Waggoner, B., Wu, Z.S.:
Strategic classification from revealed preferences. In: Proceedings of the 2018 ACM Conference on Economics and Compu- tation. pp. 55-70 (2018)
[33] Eccles, T., Hughes, E., Kramár, J., Wheelwright, S., Leibo, J.Z.: Learning reciprocity in complex sequential social dilemmas. arXiv preprint arXiv: 1et.:.00300099 (2019)
[34] Even-Dar, E., Mansour, Y., Nadav, U.:
On the convergence of regret minimization dynamics in concave games. In: Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 523-532 (2009)
[35] Foster, D.P., Vohra, V.V Calibrated learning and correlated equilibrium. Games and Economic Behavior (1-2),), 40 (1997)
[36] Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games and Economic Behavior (9(1..). 79-103 (1999)
[37] Fudenberg, D., Levine, D.K.: Conditional universal consistency, Games and Economic Behavior 29(1-2), 104-130 (1999)

---

[38] Gan, J., Guo, Q. Tran-Thanh, L., An, B., Wooldridge, M.: Manipulating a learning defender and ways to counteract. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems. pp. 8274-8283 (2019)
[39] Gan, J., Xu, H., Guo, Q. Tran-Thanh, L.., Rabinovich, Z., Wooldridge, M.: Imitative follower deception in stackelberg games. In: Proceedings of the 2019 ACM Conference on Economics and Computation. 639-657. EC 19, Association for Computing Machinery (2019)
[40] Ghalme, G., Nair, V., Filat, I., Talgam-Cohen, I,, Rosenfeld, N.: Strategic classificatton in the dark 139, 3672-3681
http:ppp/pppccccccnngg....... mlr wwwps//vvsss// Ime21a, .ttll
[41] Grigoriadis, M.D., Khachiyan, L.G.: A sublincar-time randomized approximation algorithm for matrix games. Operations Research Letters 18(2). 53-58 (1995)
[42] Haghtalab, N., Fang, F., Nguyen, T.H., Sinha, A., Procaccia, A.D., Tambe, M.: Three strategies to success: Learning adversary models in security games. In: IJCAI (2016)
[43] Haghtalab, N., Immorlica, N., Lucier, B., Wang. J.Z.: Maximizing welfare with incentive-aware
evaluation mechanisms. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 160-166 (2020)
[44] Halac, M., Kremer, I., Winter, E.: Raising capital from heterogeneous investors. American Economic Review 110(3), 889-921 (2020)
[45] Hannan, J.: Approximation to bayes risk in repeated play. In: Contributions to the Theory of
Games (AM-39), Volume III, pp. 97-139. Princeton University Press (1957)
[46] Hardt, M., Megiddo, N., Papadimitriou, C., Wootters, M.: Strategic classification. In: Proceed- ings of the 2016 ACM conference on innovations in theoretical computer science. pp. 111-122 (2016)
[47] Hart, S., Mas-Colell, A.: simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127-1150 (2000)
[48] Hart, S., Mas-Colell, A.: Simple adaptive strategies: from regret-matching to uncoupled dynamics, vol. 4. World Scientific (2013)
[49] Jaques, N., Lazaridou, A., Hughes, E., Gulcehre, C., Ortega, P., Strouse, D., Leibo, J.Z., De Freitas, N.: Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In: International Conference on Machine Learning, pp. 3040-3049, PMLR (2019)
[50] Kalai, A., Vempala, S.: Geometric algorithms for online optimization. In: Journal of Computer and System Sciences. Citeseer (2002)
[51] Kalai, A., Vempala, S.: Efficient algorithms for online decision problems. Journal of Computer and System Sciences 7 73)) 291-307 (2005)
[52] Kalai, A.T., Kalai, E., Lehrer, E., Samet, D.: A commitment folk theorem. Games and Economic Behavior 69(1), 127-137 (2010)
[53] Kolumbus, Y., Nisan, N.: Auctions between regret-minimizing agents. In: Proceedings of the ACM Web Conference 2022 (WWW '22). pp. 100-111 (2022), https://arxxvv.rgg////
.df
[54] Kulkarni, T.D., Narasimhan, K., Saeedi, A., Tenenbaum, J.: Hierarchical deep reinforcement
learning: Integrating temporal abstraction and intrinsic motivation. In: Advances in Neural Information Processing Systems. pp. 3675-3683 (2016)
[55] Vaiitorre, P., Fallenstein, B., Yudkowsky, E., Barasz, M.. Christiano, P., Herreshoff, M.: Program equilibrium in the prisoner's dilemma via löb's theorem. In: Workshops the twenty- eighth AAAI conference on artificial intelligence (2014)
[56] Lei, K., Zhang, B., Li, Y., Yang, M., Shen, Y.: Time-driven feature-aware jointly deep reinforce- ment learning for financial signal representation and algorithmic trading. Expert Systems with Applications 140, 1 112872 (2020)
[57] Leibo, J.Z., Zambaldi, V., Lanctot, M., Marecki, J., Graepel, T.: Multi-agent reinforcement learning in sequential social dilemmas. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. pp. 464-733 (2017)
[58] Levanon, S., Rosenfeld, N.: Strategic classification made practical. In: Proceedings of the 38th International Conference on Machine Learning. vol. 139, pp. 6243-6253. PMLR (2021)
12

---

[59] Li, Y., Zheng, W., Zheng, Z.: Deep robust reinforcement learning for practical algorithmic trading. IEEE Access 7, 108014-108022 (2019)
[60]
Littman, M.L.: Markov games framework for multi-agent reinforcement learning. In:
Machine learning proceedings 1994, pp. 157-163. Elsevier (1994)
[61]
Mailath, G.J., Samuelson, L., et al..: Repeated games reputations: long-run relationships.
Oxford university press (2006)
[62]
Mansour, Y., Mohri, M., Schneider, J., Sivan, B.: Strategizing against learners in bayesian
games. arXiv preprint arXiv:2205.0856. (2022)
[63] Mas-Colell, A., Whinston, M.D., Green, J.R., et al.: Microeconomic theory, vol. 1. Oxford university press New York (1995)
[64] Mehta, A.: Auction design in an auto-bidding setting: Randomization improves efficiency beyond veg. In: Proceedings of the ACM Web Conference 2022. pp. 173-181 (2022)
[65] Mertikopoulos, P., Papadimitriou, C.,, Piliouras, G.: Cycles in adversarial regularized learning. In: Proceedings of the Twenty-Ninte -Nith Annual ACM-SIAM Symposium Discrete Algorithms. pp. 2703-2717. SIAM (2018)
[66] Moulin, H.: Dominance solvable voting schemes. Econometrica: Journal of the Econometric
Society pp. 1337-1351 (1979)
[67] Moulin, H., Vial, J.P.: Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7(3-4),
201-221 (1978)
[68] Nekipelov, D., Syrgkanis, V., Tardos, E.: Econometrics for learning agents. In: Proceedings of the Sixteenth ACM Conference Economics and Computation, pp. 1-18 (2015)
[69] Nguyen, T., Xu, H.: Imitative attacker deception in stackelberg security games. In: IJCAL pp. 528-534 (2019)
[70] Nguyen, T.H.,, Wang, Y., Sinha, A., Wellman, M.P.: Deception in finitely repeated security
games. In: Proceedings of the AAAI Conference on Artificial Intelligence. pp. 2133-2140 (2019)
[71] Nisan, N., et al.: Introduction to mechanism design (for computer scientists). Algorithmic game theory 9, 209-242 (2007)
[72] Noti, G., Syrgkanis, V.: Bid prediction in repeated auctions with learning. In: Proceedings of the Web Conference 2021. pp. 3953-3964 (2021)
[73]
Oesterheld, C.: Robust program equilibrium. Theory and Decision 86(1), 143-159 (2019)
[74] Oesterheld, C., Conitzer, V.: Safe pareto improvements for delegated game playing. Autonomous Agents and Multi-Agent Systems 36(2), 1-47 (2022)
[75] Osborne, M.J., Rubinstein, A.: A course in game theory. MIT press (1994)
[76] Papadimitriou, C.,, Piliouras, G.: From nash equilibria to chain recurrent sets: algorithmic solution concept for game theory. Entropy 20(10), 782 (2018)
[77] Piliouras, G., Sim, R., Skoulakis, S.: Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. arXiv preprint arX.v:2111.14737 (2021)
[78] Rahwan, L. Cebrian, M., Obradovich, N., Bongard, J.. Bonnefon, J.F., Breazeal, C., Cran- dall, J.W., Christakis, N.A., Couzin, L.D., Jackson, M.O., et al.: Machine behaviour, Nature 568(7753), 477-486 (2019)
[79] Robinson, J.: An iterative method of solving game. Annals of mathematics pp. 296-301 (1951)
[80] Segal, I.: Contracting with externalities. The Quarterly Journal of Economics 1 114(2), 337-388 (1999)
[81] Segal, U., Sobel, J.: Tit for tat: Foundations of preferences for reciprocity strategic settings. Journal of Economic Theory 136(1), 197-216 (2007)
[82] Shalev-Shwartz, S., et al.: Online learning and online convex optimization. Foundations and trends in Machine Learning 4, 107-194 (2011)
[83] Shapley, L.: Some topics in two-person games. Advances in game theory 52, 1-29 (1964)
13

---

[84] Shi, Z.R.. Procaccia, A.D., Chan, K.S., Venkatesan, S., Ben-Asher, N., Leslie, N.O., Kamhoua, C., Fang, F.: Learning and planning in the feature deception problem. In: International Confer- ence on Decision and Game Theory for Security. pp. 23-44. Springer (2020)
[85] Şimşek, Ó., Barto, A.G.: An intrinsic reward mechanism for efficient exploration. In: Proceed- ings of the 23rd international conference on Machine learning. pp. 833- (2006)
[86] Singh, S., Barto, A.G., Chentanez, N.: Intrinsically motivated reinforcement learning. In: Proceedings of the 17th International Conference on Neural Information Processing Systems (2004)
[87] Singh, S., Lewis, R.L., Barto, A.G., Sorg, J.: Intrinsically motivated reinforcement learning: An evolutionary perspective. IEEE Transactions on Autonomous Mental Development 2(2), 70-82 (2010)
[88] Syrgkanis, V., Agarwal, A., Luo, H., Schapire, R.E.: Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems 28, 2989-2997 (2015)
[89]
Tennenholtz, M.: Program equilibrium. Games and Economic Behavior 49(2), 363-373 (2004)
[90] Tennenholtz, M., Kurland, O.: Rethinking search engines and recommendation systems: a game theoretic perspective. Communications of the ACM (2))), 66-75 (2019)
[91] Treleaven, Galas, M., Lalchand, V:: Algorithmic trading review. Commun, ACM 56(11),
76-85 (nov 2013), https:///oi..... org/ 10 1 1145/2500111
[92] Young, H.P.: Strategic learning and its limits. OUP Oxford (2004)
[93] Zhou, H., Kalev, P.S.: Algorithmic and high frequency trading in asia-pacific now and the future. Pacific-Basin Finance Journal 53, 186-207 (2019)
[94] Zinkevich. M.: Online convex programming and generalized infinitesimal gradient ascent. In:
Proceedings of the 20th international conference on machine learning. pp. 928-936 (2003)
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [Yes] As in every game theoretic study, outcomes that may be useful to one player may reduce the utility another, depending on the nature of the underlying game. We provide fundamental theoretical analysis for understanding the incentives that users of learning algorithms may have to manipulate their own agents and the potential outcomes of such manipulations.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Due to the space limitation, all proofs are deferred to the supplementary materials.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes] The code and
requirements for our simulations are provided as part of the supplementary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A] The number T of game repetitions in our simulations is purposely chosen such that the variance the time average of player payoff's between independent simulations is small and error bars were not informative.
14

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Our simulations do not require any special resources and can be run on a CPU in standard PC.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "ZvbEwuLdbkL", "reviewer": "Reviewer_Uqbg", "summary": "The authors consider a setting where human players play a game, but automated agents execute their decisions. This scenario arises in, e.g., online advertising, where an automated bidding agent makes real-time decisions intending to maximize the utility of the player it represents. The authors distinguish between the meta-game between human players and the game instantiation the agents play. The instantiation is induced by players specifying parameters like their utility for outcomes (valuations, costs, etc.). The authors claim that automated agents are regret-minimizing algorithms in many settings.\n\nThe authors identify a loophole in this modeling: Aiming to maximize their utility, the players might be incentivized to manipulate their agents. Namely, there are cases in which passing the wrong parameters to agents can actually lead to better player utility. \n\nThe authors analyze three classes of games and show when/how manipulation can help players. They provide elaborate examples along with the formal characterization of beneficial manipulations. ", "questions": "Overall, I'm positive about this paper but want to understand the author's stance about the weaknesses I raised. Please address my 1 and 2 concerns in the \"weaknesses\" part.", "limitations": "Null", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The topic is hot and relevant. Real-world applications that employ automated agents (like online advertising) are positioned in multi-billion industries. Even small advancements can be highly profitable, so reasoning about potential harms is highly impactful.\n\n2. The claims are non-intuitive. Regret-minimizing algorithms are used widely, and the authors prove they can become problematic in multi-agent settings. Furthermore, the authors provide deep insights like the connection between regret-minimizing to Stackelberg games and cooperation in Theorem 1.\n\n3. The paper is full of examples that assist in understanding the different classes of games, the deviations, and the theoretical results.\n\nWeaknesses:\n1. My main concern about this paper is the so-called companion paper (first presented in line 80). The authors, it seems, already initiated the study of \"incentives of users in automated learning agents in online strategic systems\" with that companion paper (assuming it was published). Hence, line 67 is misleading: only one of those papers could initiate this study. Further, I'm not familiar with treating previous literature as a \"companion paper\" --- how should I assess the contribution of this paper without knowledge about the other? I believe the authors should have addressed their previous \"companion\" paper as related work in this paper. I understand that addressing the companion paper risks anonymity, and yet the current situation where there's another paper on this topic, but it is not surveyed here is also unfortunate. \n\n2. If I understand correctly, the incentive misalignment follows from the automated agents being regret minimizers. Therefore, I was surprised to see that the authors don't formally define the notion of regret. Further, they discuss no-regret dynamics or other essential notions such as CCE without defining them. I believe that defining these technical notions is crucial for understanding the paper's contribution (and appreciating the paper's non-intuitive claims about the incentive mismatch). \n\n3. I did not consider the following comment in my score, but I believe the authors could significantly improve the write-up. Here are several examples:\n* The order of citations is incorrect (e.g., [75, 43, 5] in line 127, instead of [5, 43, 75])\n* Many sentences are unclear. For instance, line 143 says, \"this simple analysis also shows that the other player has...\" Who is the other player? The word \"this\" at the beginning of the sentence is a dangling modifier. Many other sentences were hard to follow.\n* Inconsistency of technical details, for instance, \"sub-family … [of] games\" vs. \"subclass of… games\" in lines 262 and 264. Such inconsistencies make reading harder.\n* Wordiness, for example, line 222: \"Analyzing the equilibrium of the meta-game, one obtains that the equilibrium of the meta-game.\" Why should we repeat \"equilibrium of the meta-game\" twice? I believe that the authors could be more articulate in this sentence. \n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PbheoaOq_9I", "reviewer": "Reviewer_WKoR", "summary": "This paper introduces the study of how users interact with game-solving agents - in particular, it explores the question of what happens if we allow a user to specify, or indeed *mis*specify, her own utility function to a learning agent that will then attempt to learn and play an equilibrium on behalf of the user. The paper then establishes, somewhat counterintuitively, several cases in which the user has incentive to misspecify her utility, despite the fact that the learning agent's objective is perfectly aligned with the user's, and carefully analyzes the Nash equilibria of the resulting \"meta-game\" for the users in these various cases.", "questions": "1. Is there anything special about regret-minimizing agents in the context of this paper? It seems as though all the results in the paper hold if the learning agents are replaced with arbitrary black-box CCE (or Nash) solvers. If this is the case, I think it'd be better to frame the result in this light, as it would be more general.\n2. To what extent is it possible to \"mechanism design\" around this problem? For example, can one program the learning agents in such a way that the users are incentivized to tell the truth? At what cost does this come? For example, such learning agents can't always converge to CCE, lest they be subject to the incentive problems raised by this paper, and therefore they cannot all be regret minimizers. Can we say anything positive?\n3. Thm 4 reminds me of the revenue equivalence principle in mechanism design. Is there any connection here?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is very intellectually stimulating and well written, and I think it brings to light an important and quite counterintuitive concept. For that, I think it is worthy of acceptance. \n\nIf I can point out any weakness, it is perhaps the specificity of the theoretical results: they are limited to special cases of dominance-solvable, Cournot, or 2x2 games. I do not think that this weakness is significant though--it simply leaves room for better future work!\n\nI also think that one of the points raised only in the appendix--namely, that regret minimization alone is never guaranteed to converge to any particular CCE in a game with multiple CCEs--is interesting in its own right, and perhaps deserves a mention in the main body.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IGmlClDEBS1", "reviewer": "Reviewer_zZ5S", "summary": "The paper suggests to view the strategic behaviour of _users_ of agent representatives, assuming those representatives are playing a repeated normal form game using regret-minimisation. As opposed to many papers that would present a limited set of specific examples, authors present analysis of game _classes_ where users are an incentive to mis-represent their actual preferences to manipulate the interaction between the automated representatives. ", "questions": "There are authors who study out-of-equilibrium behaviour and \"stable cycles\". Are there any indications of what happens if the automated agents are locked into cycle/dynamic-equilibrium patterns, rather than strongly converge to a (pure) equilibrium in beliefs/traces? \n\nAlong this same line of thinking. Since the model already admits separation of representative and user utility, what happens if the meta-game utility is even further removed. E.g., trading on \"futures\", deriving utility from the representative agent beliefs, rather than decisions that those beliefs produce in the underlying game at that moment?\n", "limitations": "none beyond the questions above\n", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: Analysis of manipulation of adaptive learning _systems_. Applicable (potentially) to multi-agent learning scenarios, especially hierarchical learning approaches. Game _class_ analysis.\n\nWeaknesses: Assumption of an equilibria seeking behaviour. Needs at least a mention of off-equilibria behaviour possibility (see works by ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GnJLgbMWLAS", "reviewer": "Reviewer_Nu2E", "summary": "This paper investigates equilibria of a class of competitive games where players do not take actions directly, but instead pick a configuration for an (automated) learning agent which then engages in a multi-round competition with agents configured by the other players. The configuration is assumed to only affect the “declared utility” a player derives from each round’s outcome. The agents are assumed to employ a no-regret learning algorithm which maximises the *declared* utility. Under the authors’ assumptions, the studied games always have a coarse correlated equilibrium (CCE), implying the statistics of the repeated game _between the agents_ converge to the CCE in the infinite horizon limit. The authors then study the “meta-game” *between the players*, and their incentives to declare utility different from their underlying true one (which is assumed private). \n\nThe authors study three classes of games played by the agents: (i) dominance-solvable; (ii) (linear) Cournot competition; and (iii) opposing-interests games. In terms of “stability”, they find that players often have an incentive to declare utility different from their true one (“deceiving their agent”). Whether players achieve greater/lower utility in the CCE then depends on which of the above three agent games is played. The authors provide rigorous characterization of both (and say that deeper investigation of repeated auction is in a complementary paper, presumably also submitted to NeurIPS).", "questions": "1. Can you please provide real-world examples for where the setup you study exists? (See the “Strengths and weaknesses” review section.) If you can do so convincingly, I will change my recommendation to accept.\n\n2. Can you please clarify why you are using the “single-shot” Nash equilibria as the baseline as opposed to some type of equilibria of the repeated game?\n\n3. Is there ever an incentive to hire more than one SW agent? (In other words, how is the assumption of one agent per player justified?)", "limitations": "The crucial limitation of this work is in its motivation/applicability to realistic scenarios, as already discussed in other parts of the review. If there are none, it is hard to see merits; if there are, it is a good paper.\n\nI did not look at the appendix which includes proofs.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n+ With an increasing number of algorithms deployed in the real-world, scenarios where agents interact with each other are likely to increase in frequency. Understanding the resulting dynamics is therefore useful.\n\n+ Breadth: The authors investigate a relatively large number of theoretical settings (dominance-solvable, Cournot, and opposing-interests games).\n\n+ The authors fruitfully connect a variety of concepts from machine learning and economics.\n\n\n**Weaknesses**\n- AFAICT the authors do not provide a single reference to where a setup like theirs appears in the *real world*. The authors mention, e.g., auctions, but I am not aware of any instances where the *auctioneer* provides a _fixed_ (adversarial bandit) agent, with which the customers interact solely by declaring outcome utilities. IIUC, the assumption of an external fixed agent and utility declaration are crucial for relevance of these results, as more direct control over the agent would result in a standard repeated game (unless other constraints are introduced ofc). (Repeated games have ofc been studies extensively.)\n\n- Relatedly, the paper explains technical definitions of the dominance-solvable/Cournot/opposing-interests games, but does not provide justification for why these particular games should be of interest (based on real-world applications).\n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept