Smooth markets: A basic mechanism for organizing gradient-based learners
Authors: David Balduzzi
Wojciech M. Czarnecki
Tom Anthony
Ian Gemp
Edward Hughes
Joel Leibo
Georgios Piliouras
Thore Graepel
Venue:  (2020)
Keywords: game theory
optimization
gradient descent
adversarial learning

Abstract: With the success of modern machine learning, it is becoming increasingly important to understand and control how learning algorithms interact. Unfortunately, negative results from game theory show there is little hope of understanding or controlling general n-player games. We therefore introduce smooth markets (SM-games), a class of n-player games with pairwise zero sum interactions. SM-games codify a common design pattern in machine learning that includes some GANs, adversarial training, and other recent algorithms. We show that SM-games are amenable to analysis and optimization using first-order methods.

Published as a conference paper at ICLR 2020
SMOOTH MARKETS: A BASIC MECHANISM FOR ORGANIZING GRADIENT-BASED LEARNERS
David Balduzzi', Wojciech M Czarnecki', Thomas W Anthony', Ian M Gemp', Edward Hughes', .Jel Z Leibo', Georgios Piliouras", Thore Graepel' 'DeepMind <google com>; 2Singapore University of Technology and Design <sutd. edu. sg> {dbalduzzi, 1e lejlot, twa, imgemp, edwarchughes, jzl, georgios, thore)
ABSTRACT
With the success of modern machine learning, it becoming increasingly important to understand and control how learning algorithms interact. Unfortunately, negative results from game theory show there is little hope of understanding or controlling general n-player games. We therefore introduce smooth markets (SM-games), class n-plaaer games with pairwise zero sum interactions. SM-games codify a common design pattern in machine learning that includes (some) GANs, adversarial training. and other recent algorithms. We show that SM-games are amenable to analysis and optimization using first-order methods.
"I began to see legibility central problem in modern statecraft. The premodern state was, in many respects, partially blind [...] It lacked anything like a detailed 'map' of its terrain and its people. lacked, for the most part, measure, metric that would allow it to 'translate' what it knew into common standard necessary for synoptic view. As a result, its interventions were often crude and self-defeating."
from Seeing like a State by Scott (1999
INTRODUCTION
As artificial agents proliferate, increasingly important analyze, predict and control their collective behavior (Parkes and Wellman 2015 Rahwan et al. 2019). Unfortunately. despite almost century of intense research since yon Neumann 1928), game theory provides little guidance outside
few special cases such as two-player zero sum, auctions, and potential games (Monderer and Shapley 1996 Nisan al.) 2007: Vickrey [961 von Neumann and Morgenstern 1944). Nash equilibria provide a general solution concept, but are intractable in almost all cases for many different reasons (Babichenko] 2016; Daskalakis et al. 2009; Hart and Mas-Colell] 2003). These and other negative results (Palaiopanos et al. 2017) suggest that understanding and controlling societies of artificial agents is near hopeless. Nevertheless, human societies billions agents manage to organize themselves reasonably well and mostly progress with time, suggesting game theory is missing some fundamental organizing principles.
In this paper, investigate how markets structure the behavior of agents. Market mechanisms have been studied extensively (Nisan et al., 2007). However, prior work has restricted to concrete examples, such auctions and prediction markets, and strong assumptions, such convexity. Our approach is more abstract and more directly suited to modern machine learning where the building blocks are neural nets. Markets, for us, encompass discriminators and generators trading errors in GANs (Goodfellow et al. 2014) and agents trading wins and losses in StarCraft (Vinyals et al. 2019).
1.1 OVERVIEW
The paper introduces class of games where optimization and aggregation make sense. The phrase requires unpacking. "Optimization" means gradient-baat based methods. Gradient descent (and friends) the workhorse of modern machine learning. Even when gradients not available, gradient estimates underpin many reinforcement learning and evolutionary algorithms. "Aggregation" means weighted sums. Sums and averages the workhorses for analyzing ensembles and populations

---

Published as a conference paper at ICLR 2020
across many fields. "Makes sense" means we can draw conclusions about the gradient- gradient-based dynamics of the collective by summing over properties of its members.
As motivation, we present some pathologies that arise in even the simplest smooth games. Examples in section 2 show that coupling strongly concave profit functions to form a game can lead to uncontrolled behavior, such spiraling to infinity and excessive sensitivity learning rates. Hence, one of our goals is to understand how to "glue together agents' such that their collective behavior is predictable.
Section introduces class of games where simultaneous gradient ascent behaves well and is amenable to analysis. In a smooth market (SM-game), each player's profit is composed of a personal objective and pairwise zero-sum interactions with other players. Zero-sum interactions analogous to monetary exchange (my expenditure is your revenue), double-entry bookkeeping (credits balance debits), and conservation of energy (actions cause equal and opposite reactions). SM-games explicitly account for externalities. Remarkably, building this simple bookkeeping mechanism into games has strong implications for the dynamics of gradient-base based learners. SM- 3M-games generalize adversarial games (Cai et al.) 2016) and codify common design pattern in machine learning, see section
Section 4 studies SM-gamms from two points of view. Firstly, from that of a rational, profit-maximizing agent that makes decisions based on first-order profit forecasts. Secondly, from that of the game as a whole. SM-games collective of profit-maximizing agents is not rational because they do not optimize a shared objective (Drexler 2019). We therefore introduce the notion of legibility, which quantifies how the dynamics of the collective relate to that of individual agents.
not potential games, the game does not optimize any single function. A
Finally, Spactionnaappiiee legibility to prove some basic theorems on the dynamics of SM-gamer under gradient-ascent. We show that (i) Nash equilibria are stable; (ii) that if profits are strictly concave then gradient ascent converges Nash equilibrium for all learning rates; and (iii) the dynamics bounded under reasonable assumptions.
The results are important for two reasons. Firstly, we identify a class of games whose dynamics are, at least in some respects, amenable to analysis and control. The kinds of pathologies described in section 2 cannot arise in SM SM-games. Secondly, we identify the specific quantities, forecasts, that are useful to track at the level of individual firms and can be meaningfully aggregated to draw conclusions about their global dynamics. It follows that forecasts should be useful lever for mechanism design.
1.2 RELATED WORK
A wide variety of machine learning markets and agent-based economies have been proposed and
studied: Abernethy and Frongillo (20TT: Balduzzi (2014); Barto al. (1983); Baum (1999); Hu
and Storkey (2014): Kakade et al. (2003 2005) : Keams et al. (2001): p K wee et al. (201 Lay and
Barbu 2010g Minsky (1986); Selfnigge 1958); Storkey (20r Storkey et al. (2012); Sutton et al.)
(2011) Wellman and Wurman (199). The goal of this paper is different. Rather than propose another
market mechanism, we abstract an existing design pattern and elucidate some of its consequences for interacting agents.
Our approach draws on work studying convergence in generative adversarial networks (Balduzzi et al. 2018 Gemp and Mahadevan 20188; Gidel et al.) 2019 Meschedrrr 2018 Mescheder et al. related minimax problems (Abernethy et al. 2019: Bailey and Piliouras] (2018). 8). and monotone
2017).
games (Gemp and Mahadevan 2017 Nemirovski al. 2010 Tatarenko and Kamgarpour 2019).
1.3 CAVEAT
We consider dynamics in continuous time dt <(w) in this paper. Discrete dynamics, W + W. + {(w) require more delicate analysis, e.g. Bailey et al. (2019). In particular, we do not claim that optimizing GANs and SM-games is easy in discrete time. Rather, our analyis shows that is relatively easy in continuous time, and therefore possible in discrete time, with some additional effort. The contrast is with smooth games in general, where gradient- based methods have essentially no hope of finding local Nash equilibria even in continuous time.
dw
2

---

Published as a conference paper at ICLR 2020
A
0.09
02
n1 np
000
+0. 00
0.00
n 8
0.38
0.34
Ω nu/8
0.03
00
-0.03
-0. 00
101 10
100 100
12*
Ttanation
game
minimal NZ
Figure 1: Effect learning rates in two games. Note: æ-axis is log-scale. Left: "half a game", e Right:
minimal SM-game, e.g. Top: Both players have same learning rate. Bottom: Second
player has & learning rate of first (which same as for top). Reducing the learning rate of the second player destabilizes the dynamics in "half game", whereas the SM-game is essentially unaffected.
1.4 NOTATION
Vectors are column- The notations and v > refer to a positive-definiee matrix and vector with all entries positive respectively. Rather than losses, we work with profits. Proofs are in appendix. use economic terminology (firms, profits, forecasts, and sentiment) even though the examples of SM-games, such as GANs and adversarial training, are taken from mainstream machine learning. We hope the economic terminology provides an invigorating change perspective. The underlying mathematies is more than first and second-order derivatives.
profit of firm gradient of profit profit forecast
Wy ((()) = V Ti (T(w)
fv. W == = [.(
aggregate forecast sentiment of firm i
iv. (W;)
ww, (w)
SMOOTH GAMES
Smooth games model interacting agents with differentiable objectives. They are the kind of games that are played by neural nets. In practice the differentiability assumption can be relaxed by replacing gradients with gradient estimates.
Definition 1. smooth game (Letcher et al. 2019) consists in players [n] (1.....n), equipped with twice continuously differentiable profit functions { R R) The parameters are
(WI..... Wn) Fd with w, Rdd where Σ dc d. Player controls the parameters w.
If players update their actions via simultaneous gradient ascent, then a smooth game yields dynamical system specified by the differential equation dw for)
E(w) =
where (,ww) V (w)) is vector. The Jacobian of game is the (d x d)-matrix of second- derivatives J(w) = (CC((w)
The setup can be recast in terms of minimizing losses by
Ows a.B=1
substituting & := for all i.
Smooth games are too general to be tractable since they encompass all dynamical systems. Every continuous dynamical system on IR,, for any d, arises as simultaneous gradient ascent on the profit functions of smooth game.
Lemma 1.
The next two sections illustrate some problems that arise in simple smooth games.
Definition 2. We recall some solution concepts from dynamical systems and game theory:
3

---

Published as a conference paper at ICLR 2020
A stable fixed point w" satisfies E(w") and v vT J(w") < 0 for all vectors v + O.
A local Nash equilibrium w has neighborhoods U3 of w; for all i, such that
Ty (w;, w";) < (w w".) all w, E U, {w]}.
A classical Nash equilibrium w' satisfies n; (; w";) S T:(w, wi.) for all w; and all players i.
Example beloo shows that stable fixed points and local Nash equilibria do not necessarily coincide. The notion of classical Nash equilibrium is ill-suited to nonconcave settings.
Intuitively, fixed point stable all trajectories sufficiently nearby flow into it. A joint strategy is a local Nash if each player is harmed if it makes small unilateral deviation. Local Nash differs from the classic definition two ways. is weaker, because only allows small unilateral deviations. This is necessary since players are neural networks and profits are not usually concave. It is also stronger, because unilateral deviations decrease (rather than not increase) profits.
2.1 PROBLEMS WITH POTENTIAL GAMES
A game is a potential game if & Ve for some function d. see Balduzzi et al. (2018) for details, Example 1 (potential game). Fix small > 0. Consider the two-player games with profit functions
क. (w) wo W2 2 wi and (r(ww) ) w/ W2
-2 W22
The game has unique local Nash equilibrium at w = (0, 0) with क (0,0) = 0= (0,00,)))
The game is chosen to be as nice as possible: Ti and T2 are strongly concave functions of wi and w2 respectively. The game is potential game since - (w2 ewi, wi - ew22 Vø for <(w)= = wi we [w] + wz)). Nevertheless, the game exhibits three related problems.
Firstly, the Nash equilibrium is unstable. Players at the Nash equilibrium via the joint update w + (0, 0) + 17 11, so Ti(w) (w) = 711 - ) T2(w) > 0. The existence of Nash equilibrium where players can improve their payoff's by coordinated action suggests the incentives are not well-designed.
increase their profits
Secondly, the dynamics can diverge to infinity. Starting at w(!) = (1, 1) and applying simultaneously gradient ascent causes the norm of vector [/w((0) ||2 to increase without limit as f - oc and at accelerating rate due to a positive feedback loop between the players' parameters and profits. Finally, players impose externalities on each other. The decisions of the first player affect the profits of the second, and vice versa. Obviously players must interact for game be interesting. However, positive feedback loops arise because the interactions are not properly accounted for.
In short, simultaneous gradient ascent does not converge to the Nash and can diverge infinity. is open to debate whether the fault lies with gradients, the concept of Nash, or the game structure. In this paper, take gradients and Nash equilibria as given and seek design better games.
2.2 PROBLEMS WITH LEARNING RATES
Gradient-based optimizers rarely follow the actual gradient. For example RMSProp and Adam use adaptive, parameter-depende learning rates. This is not a problem when optimizing function. Suppose f(w) is optimized with reweighted gradient (Vf),, == (m Vif...., Tm Vnf) where 17 > vector of learning rates. Even though (V)),, is not necessarily the gradient of any function, behaves like V because they have positive inner product when V + 0:
(V V = Σ Th (V+))² > O, since > 0 for all
Parameter-dependent learning rates thus behave well in potential games where the dynamics derive from an implicit potential function {(w) Vo((), Severe problems can arise in general games.
Berard al. 2019 use different notion of stable fixed point that requires J has positive eigenvalues.
4

---

Published as a conference paper at ICLR 2020
Example 2 ("half game"). Consider the following game, where the w2 wyyplayer is indifferent to wi
Ti (w) W2
2 2 wi and Th (w()
.2 - W22
The dynamics are clear by inspection: the W2-player converges to w2 = 0, and then the wi ii-player does the same. is hard to imagine that anything could go wrong. contrast, behavior in the next example should be worse because convergence is slowed down by cycling around the Nash:
Example 3 (minimal SM-game). A simple SM-game, definition 3 is
(w)
W2
2 and T2(W) WW W2
2 W
2
Figure 1 shows the dynamics of the games, in discrete time, with small learning rates and small gradient noise. In the top panel, both players have the same learning rate, Both games converge. Example Satmmppeeconveee converges faster expected without cycling around the Nash.
In the bottom panels, the learning rate of the second player is decreased by a factor eight. The SM-game's dynamics do not change significantly. In contrast, the dynamies of example become unstable: although player is attracted to the Nash, it extremely sensitive to noise and does not stay there for long. One goal of the paper is to explain why SM 3M-games more robust, in general, to differences in relative learning rates.
2.3
S STOP GRADIENT AND LEARNING RATES
Tools for automatic differentiation (AD) such as TensorFlow and PyTorch include st stop.gradient operators that stop gradients from being computed. For example, let f(w) w1 stop
2 (wf + wy)) The use of stop gradi ent means f not strictly speaking a function and Then
VAD to refer to its gradient under automatic differentiation.
VADS(w) = (w2 - EWI, -EW2)
which the simultaneous gradient from example 2 Any smooth vector field the gradient of function augmented with stop-grade ent operators, see appendix Stop stop-gradi ennt is often used in complex neural architectures (for example when one neural network is fed into another leading to multiplicative interactions), and is thought to be mostly harmless. Section 2.2 shows that stop gradients can interact in unexpected ways with purameter-depeneen learning rates.
2.4 SUMMARY
is natural to expect individually well-behaved agents to also behave well collectively. Unfortunately, this basic requirement fails in even the simplest examples.
Maximizing a strongly concave function is well-behaved: there is a unique, finite global maximum. However, example shows that coupling concave functions can cause simultaneous gradient ascent to diverge to infinity. The dynamics of the game differs in kind from the dynamics of the players in isolation. Example ssows shows that reducing the learning rate of well-behaved (strongly concave) player in simple game destabilizes the dynamics. How collectives behave is sensitive not only to profits, but also to relative learning rates. Off-the-shelf optimizers such Adam (Kingma and Ba 2015) modify learning rates under the hood, which may destabilize some games.
3 SMOOTH MARKETS (SM-GAMES)
Let us restrict to more structured games. Take an accountant's view of the world, where the only thing we track is the flow of money. Interactions are pairwise. Money neither created nor destroyed, so interactions are zero-sum. If we model the interactions between players by differentiable functions Giy (w,, W,) that depend on their respective strategies then we have an SM-game. All interactions explicitly tracked. There
externalities off the books. Positive interactions, Isj 0, are revenue, negative are costs, and the difference is profit. The model prescribes that all firms are profit maximizers. More formally:
5

---

Published as a conference paper at ICLR 2020
Definition 3 (SM-game). A smooth market is a smooth game where interactions between players are pairwise zero-sum. The profits have the form
Ty (w) fi(w:)
Σ j
gio Wy)
where Di5( (W,, W,) + Ijs 9ja( (w,, w.) = 0 for all i,
The functions fi can act as regularizers. Alternatively, they can be interpreted as natural resources or dummy players that react too slowly to model as players. Dummy players provide firms with easy (non-adversarial) sources of revenue.
Humans, unlike firms, are not profit- mofittmaximiizer; humans typically buy goods because they value them more than the money they spend on them. Appendix brieffl discusses extending the model.
3.1 EXAMPLES OF SM-GAMES
SM-games codify a common design pattern:
1. Optimizing function. near-trivial case is where there is a single player with profit Ti (1) = (ww).
2. Generative adversarial networks and related architectures like CycleGANs are zero or near zero sum (Goodfellow et al. 2014 Wu et al. 2019; Zhu et al. 2017).
3. Zero-sum polymatrix games are SM-games where f((w;) = and (w, wy)
w Aij W for some matrices Aij. Weights are constrained probability simplices. The games have nice properties including: Nash equilibria are computed via linear program and correlated equilibria marginalize onto Nash equilibria (Cai et al. 2016).
4. Intrènsic curiosity modules use games to drive exploration. One module is rewarded for pre- dicting the environment and an adversary is rewarded for choosing actions whose outcomes
are not predicted by the first module (Pathak et al. 2017). The modules share some weights, so the setup is nearly, but not exactly, an SM-game.
5. Adversarial training concerned with the minmax problem (Kurakin et al. et al. 2018)
2017 Madry
El max (fw(x; 5e). 6.). B.En
min WEW
Setting 90s (Wo, 6;) ((Swo (x; 8.), v:) obtains a star-shaped SM-game with the neural net (player 0) at the center and n adversaries one per datapoint (x,, y1) on the arms
6. Task-suites where a population of agents are trained on a population of tasks, form bipartite graph. If the tasks are parametrized and adversarially rewarded based their difficulty for agents, then the setup is an SM-game.
7. Homogeneous games arise when all the coupling functions are equal up to sign (recall
yi -i -9jx). An example is population self-play (Silver et al. 2016 Vinyals et al. 2019) which lives on a graph where 9:3 W;, w,) == P(w, beats W,) comes from the probability that policy w; beats wj.
Monetary exchanges in SM-games are quite general. The error signals traded between generators and discriminators and the wins and losses traded between agents in StarCraft are two very different special cases.
4 FROM MICRO TO MACRO
How to analyze the behavior of the market as a whole? Adam Smith claimed that grofi-mmxxmizzing leads firms to promote the interests of society, as if by an invisible hand (Smith 1776). More formally, we can ask: Is there a measure that firms collectively increase or decrease? It is easy to see that firms do not collectively maximize aggregate profit (AP) or aggregate revenue (AR):
AP(w) Σ Te (w)
Σ fi(w.)
AR (w) Σ max (95((w,w,)..)

---

Published as a conference paper at ICLR 2020
A
B
c
D
Figure 2: SM-game graph topologies. A: two-player (e.g. GANs). B: star-shaped (e.g. adversarial training). C: bipartite (e.g. task-suites). D: all-to-all.
Maximizing aggregate profit would require firms to ignore interactions with other firms. Maximizing aggregate revenue would require firms to ignore costs. In short, SM-games are not potential games; there is no function that they optimize in general. However, it turns out the dynamics of SM-games aggregates the dynamics of individual firms, sense made precise section
4.1 RATIONALITY: SEEING LIKE A FIRM
Give an objective function to agent. The agent is rational, relative the objective, if chooses actions because it forecasts they will lead to better outcomes as measured by the objective. In SM-games, agents are firms, the objective is profit, and forecasts computed using gradients.
Firms aim to increase their profit. Applying the first-order Taylor approximation obtains (w) {h.o.t),
Te(w + v.) (w()
change
profit forecast
where (h.o.1.) refers to higher-order terms. Firm i's forecast how profits will change modifies production by v, is (w) == (w): The Taylor expansion implies that fv. (w) as T. (((w + v.) T. (w) for small updates V,. Forecasts encode how individual firms expect profits to change ceteris paribus
4.2 PROFIT CHANGES DO NOT ADD UP
How does profit maximizing by individual firms look from the point of view of the market as a whole? Summing over all firms obtains
Σ ( +v.) (T(
= Σ fv. (w) + {h.o..}
(3)
Sngregute-ehhngeee in-pootit
aggregate Forecast
where (w(w) = E. (w) is the aggregate forecast. Unfortunately, the left-hand side of Eq. 3 is incoherent. sums the changes in profit that would be experienced by firms updating their production in isolation. However, firms change their production simultaneously. Updates are not ceteris paribus and profit is not meaningful macroeconomic concept. The following minimal example illustrates the problem:
wiws W2 and T2(W) w1 W2. Fix w (w1, W2) and let (w2,-wi). The sum of the changes in profit expected by the firms, reasoning in isolation, is
Example 4. Suppose TI (
( - क (w) + T2(W + V2) T2 =2(w) = w + w > 0
whereas the actual change in aggregate profit is zero because xx(x) + イх(x) for any x.
Tracking aggregate profits is therefore not useful. The next section shows forecasts are better behaved.
4.3 LEGIBILITY: SEEING LIKE AN ECONOMY
Give a target function to every agent in a collective. The collective is legible, relative to the targets, it increases decreases the aggregate target according whether its members forecast, aggregate,
All else heing equal i.c. without taking into account updates by other firms.
7

---

Published as a conference paper at ICLR 2020
they will increase decrease their targets. We show that SM-games are legible. The targets profit forecasts (note: not profits).
Let consider how forecasts change. Define the sentiment as the directional derivative of the forecast vv, fv. (w) = v Vi, (w). The first-order Taylor expansion of the forecast shows that the sentiment is forecast about the profit forecast:
iv; w v.) fv. (w)
Vi, (w) + (h.o.t.}.
(4)
change in profit forecast
sentiment
The perspective of firms can be summarized as:
1. Choose an update direction V; that forecast to increase profit.
2. The firm is then one two main regimes:
a. If sentiment is positive then forecasts increase as the firm modifies its production forecasts become more optimistic. The firm experiences increasing returns-to-scale
b. If sentiment is negative then forecasts decrease the firm modifies its production forecasts become more pessimistic. The firm experiences diminishing returns-to-scale
Our main result that sentiment additive, which means that forecasts are legible: Proposition 2 (forecasts are legible in SM-games). Sentiment is additive
(wf Σ Dv.fv.(w).
Thus, the aggregrate profit forecast iv increases decreases according whether individual forecasts iv; are expected to increase or decrease in aggregate.
Section 5.1 works through an example that not legible.
DYNAMICS OF SMOOTH MARKETS
Finally, we study the dynamics of gradient- based learners in SM -agee.s. Suppose firms use gradient ascent. Firm i's updates are, infinitesimally, in the direction v, (w) that dw: (w). Since updates are gradients, we can simplify our notation. Define firm i's forecast fi(w) = 2 V I1l, (w)) 31 and its sentiment, ceteris paribus, as V
dig
dt (w).
We allow firms choose their learning rates; firms with higher learning rates are more responsive. Define the 77- weighted dynamics (,(ww) = E1 17.E)....,7)e. (.) and 17- peeehittedd forecast as
i, (w) = _ [1, (w)ll2
Σ vh f.(w).
In this setting, proposition implies that Proposition 3 (legibility under gradient dynamics). Fix dynamics di = En( Sentiment decom- poses additively:
di
di.
Σ
7
di
dt
Thus, can read off the aggregate dynamics from the dynamics of forecasts of individual firms.
5.1 EXAMPLE A FAILURE OF LEGIBILITY
The pairwise zero-sum structure is crucial to legibility. It is instructive to take a closer look at example[] where the forecasts are not legible.
Suppose गj (w) = u and T2(w) = w w2
f w Then E(w) = (w2 ew1, ew2)
and the firms' sentiments di -e(w2 ex and dia -e(w) ewu2)² which always
8

---

Published as a conference paper at ICLR 2020
non-positive. However, the aggregate sentiment is
di (w) = c((0 - ewi )² c(w, - cw2)²² + (1 + c ) w2 - c(w) + wz)²
dt
which for small e dominated by w w1W2, and so can be either positive or negative.
When w = (1,1) we have at Each firm expects their forecasts to decrease, and yet the opposite happens due to positive feedback loop that ultimately causes the dynamics to diverge to infinity.
d - c(6 5e + 2c²) Rs 1 >> and di + dfa - 2e (1 - -)² < dr
dt
5.2 STABILITY, CONVERGENCE AND BOUNDEDNESS
We provide three fundamental results the dynamics of smooth markets. Firstly, show that stability, from dynamical systems, and local Nash equilibrium, from game theory, coincide in SM-games:
Theorem (stability). A fixed point in an SM-game is a local Nash equilibrium iff it is stable. Thus, every local Nash equilibrium is contained in an open set that forms its basin of attraction.
Secondly, we consider convergence. Lyapunov functions are tools for studying convergence. Given dynamical system dw {(w) with fixed point w', recall that V(w) is Lyapunov function if: (i) V(w") = (ii) V (ww) system has a Lyapunov function then the dynamics converge to the fixed point. Aggregate forecasts share properties (i) and (ii) with Lyapunov functions.
for all * w"; and (iii) (w) for all * w If a dynamical
ii) Shared global minima: (w) = iff (w)(w) = 0 for all n.n' > 0, which occurs iff w is stationary point, <(()) for all
(ii) Positivity: f,(w) (w) > 0 for all points that are not fixed points, for all > 0.
We therefore use forecasts study convergence and divergence across all learning rates: Theorem 5. In continuous time, for all positive learning rates > 0,
1. Convergence: w is stable fixed point (S < 0), then there is an open neighborhood U w" where din (w) 0 for all U \ [w"), so the dynamics converge to w" from anywhere U.
2. Divergence: w" w is an unstable fixed point (S > 0), there is an open neighborhood U 3 w" such that dig repelled by w".
dt (w) > foror all w E U {w"}, so the dynamics within U are
The theorem explains why SM-games are robust to relative differences learning rates in contrast the sensitivity exhibited by the game in example If fixed point stable, then for any dynamics dw dt E, (w), there is corresponding aggregate forecast i,, (w) that can be used to show convergence. The aggregate forecasts provide a family of Lyapunov-like functions.
Finally, we consider the setting where firms experience diminishing returns-to-scale for sufficiently large production vectors. The assumption is realistic for firms in a finite economy since revenues must eventually saturate whilst costs continue to increase with production.
Theorem (boundedness). Suppose all firms have negative sentiment for sufficiently large values of ||we]]. Then the dynamics are bounded for all n > 0.
The theorem implies that the kind of positive feedback loops that caused example 1 to diverge to infinity, cannot occur in SM-games.
5.3 LEGIBILITY AND THE LANDSCAPE
One of themes is that legibility allows read off the dynamics of games. We make the claim visually explicit in this section. Let us start with a concrete game. Example 5. Consider the SM-game with profits
1
Ty (w) = 6 [w]] 3 + w
w1 W22
and T2(w) = Wwy
3
+
2 + W W2-
6 2
9

---

Published as a conference paper at ICLR 2020
B
D
recaive
poulle suttiment
-4 -2
Figure 3: Legibile dynamics. Panels AB: Dynamics an SM-game with both positive and negative sentiment, under different learning rates. Panels CD: Cartoon maps of the dynamics.
Figure JAB plots the dynamics of the SM-game in example 5 under two different learning rates for player I. There is unstable fixed point at the origin and an ovoidal cycle. Dynamics converge to the cycle from both inside and outside the ovoid. Changing player I's learning rate, panel B, squashes the ovoid. Panels CD provide cartoon map of the dynamics. There are two regions, the interior and exterior of the ovoid and the boundary formed by the ovoid itself.
In general, the phase space of any SM-gam SM-game is carved into regions where sentiment dig (w) is di positive and negative, with boundaries where sentiment is zero. The dynamics can be visualized as operating landscape where height at each point corresponds to the value of the aggregate forecast fn (w). The dynamics does not always ascend or always descend the landscape. Rather, sentiment determines whether the dynamics ascends, descends, or remains a level-set. Since dt
sentiment is additive, dfn (w) Σ. t/ at (w), the decision ascend descend comes down to
4f
weighted sum of the sentiments of the firms Changing learning rates changes the emphasis given to different firms' opinions, and thus changes the shapes of the boundaries between regions in relatively straightforward manner.
SM-games can thus express richer dynamics than potential games (cycles will not occur when per- forming gradient ascent on fixed objective), which still admit a relatively simple visual description in terms of landscape and decisions about which direction to go (upwards or downwards). Computing the landscape for general SM-games, as for neural nets, is intractable.
DISCUSSION
Machine learning has got a lot of mileage out of treating differentiable modules like plug-and-play lego blocks. This works when the modules optimize single loss and the gradients chain together seamlessly. Unfortunately, agents with differing objectives are far from plug-and-play. Interacting agents form games, and games are intractable general. Worse, positive feedback loops can cause individually well-behaved agents to collectively spiral out of control.
therefore necessary find organizing principles constraints on how agents interact that ensure their collective behavior is amenable to analysis and control. The pairwise zero-sum condition that underpins SM- SM-games is one such organizing principle, which happens to admit an economic interpretation. Our main result is that 3M-games are legible: changes in aggregate forecasts are the sum of how individual firms expect their forecasts to change. follows that we can translate properties of the individual firms into guarantees collective convergence, stability and boundedness EMggames, see theorems
Legibility is local-to-global principle, whereby can draw qualitative conclusions about the behavior of collectives based on the nature of their individual members. Identifying and exploiting games that embed local-to-globe principles will become increasingly important artificial agents become more common.
REFERENCES
Abernethy, J. and Frongillo, R. (2011). A Collaborative Mechanism for Crowdsourcing Prediction Problems. In NeurIPS.
NNote the dynamics de not necessarily follow the gradient of +fm- Rather, they move in directions with positive negative inner product with Vi, according to sentiment.
10

---

Published as a conference paper at ICLR 2020
Abemnethy, J., Lai, K. A., and Wibisono, A. (2019). Last-iterate convergence rates for min-max optimization. In arXiv:1906.0202
Babichenko, Y. (2016). Query Complexity of Approximate Nash Equilibria. Journal ACM, 63(4).
Bailey, J. P., Gidel, G., and Piliouras, G. (2019). Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent, In arXiv:1907.04392.
Bailey, J. P. and Piliouras, G. (2018). Multiplicative Weights Update in Zero-Sum Games. In ACM EC.
Balduzzi, D. (2014). Cortical prediction markets. In AAMAS.
Balduzzi, D., Racanière, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, (2018). The mechanics of n-player differentiable games. In ICMI..
Barto, A. G., Sutton, and Anderson, C. W. (1983). Neuronlike Adapative Elements That Can Solve Difficult Learning Control Problems. IEEE Trans. Systems, Man, Cyb, 13(5):834846.
Baum, E. B. (1999). Toward Model of Intelligence an Economy of Agents. Machine Learning, 35(155-185).
Berard, H., Gidel, G., Almahairi, A., Vincent, P., and Lacoste-Julien, S. (2019). A Closer Look the Optimization Landscapes of Generative Adversarial Networks. In arXiv: 04848.
Cai, Y., Candogan, O., Daskalakis, C., and Papadimitrion, C. (2016). Zero-sum Polymatrix Games: Generalization of Minmax. Mathematics of Operutions Research, 41 41(2):648-655.
Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. (2009). The Complexity of Computing Nash Equilibrium. SIAM J. Computing. 39(1):195-259.
Drexler, K. E. (2019). Reframing Superintelligene: Comprehensive Al Services as General Intelli- gence. Future of Humanity Institute, University of Oxford, Technical Report #2019-1.
Gemp, I. and Mahadevan, S. (2017). Online Monotone Games. In arrivv:170.0077
Gemp. I. and Mahadevan, S. (2018). Global Convergence to the Equilibrium of GANs using Variational Inequalities. In arXiv:1808.0153:)
Gidel, G., Hemmat, R. A., Pezeshki, M., Lepriol, R., Huang, G., Lacoste-Julien, S., and Mitliagkas, I. (2019). Negative Momentum for Improved Game Dynamics. In AISTATS.
Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014). Generative Adversarial Nets. In NeurIPS.
Hart, and Mas-Colell. A. (2003). Uncoupled Dynamics Do Not Lead to Nash Equilibrium. American Economic Review, 130--1883
Hu, and Storkey, A. (2014). Multi-period Trading Prediction Markets with Connections to Machine Learning. In ICML.
Kakade, Kearns, M., and Ortiz, L. (2003). Graphical economics. In COLT.
Kakade, S., Kearns, M., Ortiz, L., Pemantle, R., and Suri, S. (2005). Economic properties of social networks. In NeurIPS.
Kearns, M., Littman, M., and Singh, S. (2001). Graphical models for game theory. In UAI
Kingma, D. P. and Ba, J. L. (2015). Adam: A method for stochastic optimization. In ICLR.
Kurakin, A., Goodfellow, and Bengio, S. (2017). Adversarial Machine Learning at Scale. In ICLR.
Kwee, I., Hutter, M., and Schmidhuber, J. (2001). Market-based reinforcement learning in partially observable worlds. In ICANN.
11

---

Published as a conference paper at ICLR 2020
Lay, N. and Barbu, A. (2010). Supervised aggregation of classifiers using artificial prediction markets. In ICML.
Letcher, A., Balduzzi, D., Racanière. S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T. (2019). Differentiable Game Mechanics. JMLR, 20:1-400
Madry. A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2018). Towards Deep Learning Models Resistant to Adversarial Attacks. In ICLR.
Mescheder, L. (2018). On the convergence properties of GAN training. In ArXiv11801:044
Mescheder, L., Nowozin, S., and Geiger, A. (2017). The Numeries of GANs. In NeurIPS.
Minsky, M. (1986). The society of mind. Simon and Schuster, New York NY.
Monderer, D. and Shapley, L. S. (1996). Potential Games. Games and Economic Behavior, 14:124- 143.
Nemirovski, A., Onn, S., and Rothblum, U. G. (2010). Accuracy certificates for computational problems with convex structure. Mathematics of Operations Research, 35(1).
Nisan, N., Roughgarden, T., Tardos, É., and Vazirani, V., editors (2007). Algorithmic Game Theory. Cambridge University Press, Cambridge.
Palaiopanos, G., Panageas, I., and Piliouras, G. (2017). Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos. In NewrIPS.
Parkes, D. C. and Wellman, M. P. (2015). Economic reasoning and artificial intelligence. Science, 349(6245):277-72..
Pathak, D., Agrawal, P.. Efros, A. A., and Darrell, T. (2017). Curiosity-driven Exploration by Self-supervised Prediction. In ICML.
Rahwan, I., Cebrian, M., Obradovich, N., Bongard, J., Bonnefon, J.-F., Breazeal, C., Crandall, J. W., Christakis, N. A., Couzin, I. D., Jackson, M. O., Jennings, N. R., Kamar, E., Kloumann, I. M., Larochelle, H., Lazer, D., Mcelreath, R., Mislove, A., Parkes, D. C., Pentland, A. S., Roberts, M. E., Shariff, A., Tenenbaum, B., and Wellman, M. (2019). Machine behaviour. Nature, 568:477-486
Scott, (1999). Seeing Like a State: How Certain Schemes to Improve the Human Condition Have Failed. Yale University Press.
Selfridge, O, G. (1958). Pandemonium: a paradigm for learning. In Mechanisation of Thought Processes: Proc Symposium Held at the National Physics Laboratory.
Silver, D., Huang, A., Maddison, J., Guez, A., Sifre, I.., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T. P., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):4844499
Smith, A. (1776). The Wealth of Nations. Strahan and Cadell, London.
Storkey, A. (2011). Machine Learning Markets. In AISTATS.
Storkey, A., Millin, J., and Geras, K. (2012). Isoelastic Agents and Wealth Udates in Machine Learning Markets. In ICML.
Sutton, R., Modayil, J., Delp, M., Degris, T., Pilarski, M., White, A., and Precup, D. (2011). Horde: A Scalable Real-time Architecture for Learning Knowledge from Unsupervised Motor Interaction. In AAMAS.
Tatarenko, T. and Kamgarpour, M. (2019). Learning Generalized Nash Equilibria a Class of Convex Games. IEEE Transactions on Automatic Control, 64(4): 1429-1439.
12

---

Published as a conference paper at ICLR 2020
Vickrey, W. (1961). Counterspeculation, Auctions and Competitive Sealed Tenders. Finance, 16:8-37.
Vinyals, O., Babuschkin, I., Chung, J., Mathieu, M., Jaderberg, M., Czarnecki, W. M., Dudzik, A., Huang, A., Georgiev, P., Powell, R., Ewalds, T., Horgan, D., Kroiss, M., Danihelka, I., Agapiou, J., Oh, J., Dalibard, V., Choi, D., Sifre, L., Sulsky, Y., Vezhnevets, S.. Molloy, J., Cai, T., Budden, D., Paine, Gulcehre, C., Wang, Z.. Pfaff. T., Pohlen, T., Wu, Y., Yogatama, D.. Cohen, J.. McKinney, K., Smith, O., Schaul, T., Lillicrap, T., Apps, C., Kavukcuoglu, K., Hassabis, D., and Silver, D. (2019). AlphaStar: Mastering the Real-Time Strategy Game StarCraft https:: /deppmiaaammmmm nd. com com/blog og/ tatppssttr-msstrraaae
-real -ime strategyy game starcraft-ii/
von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100(1):2 320.
Neumann, J. and Morgenstem, O. (1944). Theory of Games and Economic Behavior, Princeton University Press, Princeton NJ.
Wellman, M. P. and Wurman, P. R. (1998). Market-aware agents for a multiagent world. Robotics and Autonomous Systems, 14:115-125.
Wu, Y., Donahue, J., Balduzzi, D., Simonyan, K., and Lillicrap, (2019). LOGAN: Latent
Optimisation for Generative Adversarial Networks. In 1rXhv:1912.00953.
Zhu, J.-Y., Park, T., Isola, P., and Efros, A. A. (2017). Unpaired Image-to-lmage Translation using Cycle-Consistent Adversarial Networks. In CVPR.
APPENDIX
A MECHANICS OF SMOOTH MARKETS
This section provides a physics-inspired perspective on smooth markets. Consider a dynamical system with particles moving according the differential equations:
dw1
dl E (WI,..... Wn)
dwn = (WI....... w.).
di
The kinetic energy of partiele times velocity squared, moz or in
energy of 7t particle ni3 f.(w) nf ||
where interpret the learning rate squared n?, of particle i as its mass and &, as its velocity. The total energy of the system the sum over the kinetic energies of the particles:
total energy (w( Σ ni 11
For example, in Hamiltonian game we have that energy is conserved:
df
total energy = | constant or
(w) =
di
since <T V 2 = ET ATE 0, see Balduzzi al. 2018 Letcher al. 2019) for details.
Energy is measured in joules (kg m 2). The rate of change of energy with respect to time is power, measured in joules per second watts (kg
-3)). Conservation of energy means that (closed) Hamiltonian system, in aggregate, generates no power. The existence an invariant function makes Hamiltonian systems easy to reason about in many ways.
13

---

Published as a conference paper at ICLR 2020
Smooth markets more general than Hamiltonian games in that total energy is not necessarily conserved. Nevertheless, they are much more constrained than general dynamical systems. Legibility, proposition says that the total power (total rate of energy generation) in smooth markets is the sum of the power (rate energy generation) of the individual particles:
di dt (w)
Σ df:
(w).
Example where legibility fails. Once again, it is instructive look at concrete example where legibility fails. Recall the potential game in example [ with profits
E
T (w) W2
2 w
and T2(w) = w W2
2
and sentiments
di dt
di2 (w) = -e <w2) dt
(w) = - <(w2 ewi )² and
Physically, the negative sentiments di < 0 and or
diz dt
0 mean that that each "particle" in the system,
considered in isolation, is always dissipating energy. as whole has
Nevertheless as shown in section 5.1 the system
di
(w) - ((w2 ewr)² - c(wi Ew2)² (1 + + <(wi + w2)
dt
which is positive for some values of w. Thus, the system whole can generate energy through interaction effects between the (dissipative) particles.
B PROOFS
Proof of lemma
Lemma 1. Every continuous dynamical system on TRd,, for any arises as sinultaneous gradient ascent on the profit functions of smooth game.
Proof. Specifically, we mean that every dynamical system of the form dw = E(w) arises as simulta- neous gradient ascent on the profits of a smooth game.
de
Given continuous vector field & on Rd, we need to construct a smooth game with dynamics given by g. To that end, consider a d-player game where player controls coordinate w,. Set the profit of player i to
Ti (w): =
(wi, W;-1 Wi+1, wa)dr
==0
and observe that
BiT Ohee
(w) ((()) by the fundamental theorem of caleulus.
Proof of proposition 2
Before proving proposition 2, we first prove a lemma.
Lemma (generalized Helmholtz decomposition). The Jucobian decomposes into J(w) S(w) (ww) where S(w) and A A(w) are symmetric and antisymmetric, respectively, for all E Rdd
Proof. Follows immediately. See Letcher et al. (2019) for details and explanation.
Proposition 2. Sentiment is additive: Dvfv(w)= = E, Dv.fv, (w).
Proof. For any collection of updates (v.) we need to show that
Viv Vfv(w)
Σ V. (w).
Direct computation obtains V = vJJv= v A because A is antisymmetric and S is block-diagonal.
VT
V...vv..
14

---

Published as a conference paper at ICLR 2020
Proof of proposition 3
First prove lemma.
Lemma 8. (w) (in(w) Σ== ni (.).:.))
Proof. Observe by direct computation that
Vi. = JT E:
and so
V(n.fi) = =J
') E:
0
is then easy to see that Vin = E, ?/ Vi, = E, JTC: J' Thus,
< Vi E J E, E (S AT) En
where ST since S symmetric. By antisymmetry of A, we have that v A for all v. The expression thus simplifies to
< Vin = E, S E, = Σ n (ET Su E.)
Σ oi V
by the block-diagonal structure of S.
Proposition 3 (legibility under gradient dynamics). Fix dynamics poses additively:
dw di
En( Sentiment decom-
din
di.
di
dl
Proof.
Applying the chain rule obtains
that
dfn
dw
V
w
fyp
w Ex, (w)
dt
dt
where the second equality follows by construction of the dynamical system di shows that
dw = (w). Lemma
ET,JTE,
(S AT)En
Σ nh S.S.E
Σ of ( E.. Viw(w)).
Finally, since dwi dt
m) (w) by construction, we have
dw;
ns E.
Vh(w))
Vw. (T:i(())
dt
d(nrf))
df.
dt dt
for all as required.
Proof of theorem 4
Theorem 4. fixed point in SM- SM-game is local Nash equilibrium is stable.
15

---

Published as a conference paper at ICLR 2020
Proof. Suppose that w" is a fixed point of the game, that is suppose E(w*) 0.
Recall from lemma 7 that the Jacobian of decomposes uniquely into two components J(w) = S(w) + Aw) where S = ST is symmetric and A + AT = 0 is antisymmetric. It follows that vTJv = vTSv + vv vTSv since A is antisymmetric. Thus, w* is a stable fixed point iff S(w*) is negative definite.
In an SM-game, the antisymmetric component arbitrary and the symmetric component is block diagonal where blocks correspond players' parameters. That is, S 0 for i + because the interactions between players and j are pairwise zero-sum - and are therefore necessarily confined to the antisymmetric component of the Jacobian. Since is block block-diagonal, it follows that S is negative definite iff the submatrices Sy along the diagonal are negative definite for all players i.
Finally, ( a (w*) is negative definite iff profit m; (w") is strictly concave in the parame- ters controlled by player at w" The result follows.
Proof of theorem
Theorem 5. In continuous time, for all positive learning rates 0,
1. If w" is stable fixed point (S < 0), then there is open neighborhood U w" where dfg (w) < 0 for all E U {w") }, so the dynamics converge w" from anywhere in U.
2. If w is an unstable fixed point (S > 0), there is an open neighborhood U в w" such that dig
de (w) > for all w E U ( J, so the dynamics within U are repelled by w".
Proof. We prove the first part. The second follows by symmetric argument. First, strict concavity implies S = Vi, is negative definite for all Second, since block -digonaa with zeros in all blocks Súj for pairs of players # it follows that S is also negative definite. Observe that
$ Vn En JT = ET (S + AT),, = E,, S E, <0
for all E, * 0 since S is negative definite. Thus, simultaneous gradient ascent the profits acts to infinitesimally reduce the function i, (w).
Since E,, reduces fn. it will converge to stationary point satisfying Vi, = 0. Observe that Vi, iff E, = 0 since Vf,, = JTC, and the symmetric component S of the Jacobian is negative definite. Finally, observe that all stationary points of fn. and hence E,, are stable fixed points of E., because negative definite, which implies that the fixed point is Nash equilibrium.
Proof of theorem
dig (w) f. sufficiently large values of Theorem 6. Suppose all firms have negative sentiment, de |[we]]. Then the dynamics are bounded for any learning rates n 0.
Proof. Fix v > 0 and also fix 0 such that di (w) < for all w satisfying ||wall2 > d. Let
(d) = [w ||wsll2 > d for all i} and suppose > is sufficienlly large such that fy (g) = {w
(n(w) = g} c (d). We show that
fn(w(0) (0)) < implies (n) < for all t > 0,
for the dynamical system defined by dw E,, Since we are operating in continuous time, all that is required is to show that f (w(()) = g' < g implies that fr, (w((++)) < <g' for all sufficiently small
dt
e > 0.
Recall that # (w) De,, (3 (211,,11)) - other words, the dynamics
E ViLT &, De. GIE. It follows immediately that dis (w) < 0 for all w a sufficiently small ball centered at w(t), In di
dw
E,, reduce fn and the result follows.
n
16

---

Published as a conference paper at ICLR 2020
C NEAR SM-GAMES: EXPERIENTIAL VALUE AND THE EXCHANGE OF GOODS
Definition proposes a model of monetary exchange smooth markets. It ignores some major aspects of actual markets. For example, SM-games do model inventories, investment, borrowing or interest rates. Moreover, in practice money is typically exchanged in return for goods or services- which are ignored by the model.
In this section, we sketch one way to extend SM-games to model the exchange of both money and goods although still without accounting for inventories, which would more significantly complicate the model. The proposed extension is extremely simplistic. It is provided to indicate how the model's expressive power can be increased, and complications that results.
Suppose
T: (:(w) = fi(w) + Σ (assassyyw (w;, wj) - Piyl (w,, w,). jit-
The functions wij measure the amount of goods (say, widgets) that are exchanged between firms i and j. We assume that wij + W/s = since widgets are physically passed between the firms and therefore one firms increase must be the others decrease. For firms enter into exchange must be that they subjectively value the widgets differently, hence we introduce the parameters a.j. Note that if oij for all íj then the model is equivalent to SM-game.
The transaction between firms and j is net beneficial to both firms and j if
agj Wiy (Wa, w;) > Gi (Ws, W;)
and, simultaneously
az (W,, wy) > (W,, Wj).
We can interpret the inequalities as follows. First suppose that Waj and giy always have the same sign. The assumption reasonable so long as firms do not pay give away widgets. Further assume without loss of generality that Wij and Júj are both greater than zero in other words, firm is buying then be rewritten
widgets from firm The above inequalities
Okij Way (Wi, wj)
Pig (Wi,
firm values widgets
firm pays
and
Ogii Wiy (W;, Wj)
Fig (W1, wj)
amount widgets
amount j paid
It follows that both firms benefit from the transaction.
Implications for dynamics. The off-block-diagonal terms of the symmetric and anti-symmetric components of the game Jacobian are
Sy
Oij O'ji
Vijuey ( w,)
2
and
Aij aij Ozi
Wig (W;; w,)
where it is easy to check that S.y = Sy and Aij + Afi = 0. The off-block-diagona terms of S has consequences for how forecasts behave:
E Vin
Σ D (ET Vi E,)
(5)
sentiment
Σ V
(ay ai (ET Vigli Ej)
correction
When near SM-games well-behaved? If agy ajs for all i, then the correction is zero; if Onj ~ Ojj then the corrections due to different valuations of goods will be negligible, and the game should be correspondingly well-behaved.
17

---

Published as a conference paper at ICLR 2020
What go wrong? Eq (5) implies that the dynamics of near SM-games specifically whether the dynamics are increasing or decreasing the aggregate forecast cannot be explained in terms of the sum of sentiments of individual terms. The correction terms involve interactions between dynamics of different firms and the (second-order) quantities goods exchanged. In principle, these terms could be arbitrarily large positive negative numbers.
Concretely, the correction terms involving couplings between dynamics different firms can lead to positive feedback loops, in example [ where the dynamics spiral off to infinity even though both players have strongly concave profit functions.
D THE STOP GRADDIEN OPERATOR
Lemma 9, Any smooth vector field can be constructed as the gradient of a function augmented with stop.gradiens operators.
Proof.
Suppose & =
(B] Own
(f((w) Owa
).
Define
d
g(w)= Σ
/ ( Wi, stop gradient
1=1
follows that
VAD [[]]]]]] = =((w)
as required.
18


Reviews:
[{"review_id": "SJepamwKYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces smooth market games (SM-games), a class of smooth games characterized by pairwise zero sum interactions, and show SM-games possess a number of appealing properties:\n- A fixed point is a local Nash equilibrium iff it is stable\n- Local convergence to stable fixed points\n- Unstable fixed points are repellent\n- Dynamics are bounded, assuming diminishing returns-to-scale for sufficiently large vectors.\nThe need for a class of games with such properties is motivated by a discussion of the pathologies of smooth games under simultaneous gradient ascent. \n\nThe paper has an extensive literature review, addresses an important problem, and has informative discussions. It is well written and there are nice examples to illustrate the central ideas. However, I do have some criticisms:\n\n1. The writing in this paper is sometimes pompous. Quoting James Scott has no added value to this work. Reference to Adam Smith’s invisible hand not only has no added value but is also confusing and detracts from the paper — SM-games are not purporting to be real economic models.\n2. Throughout the paper there is a confusing mix between ideas from economics and ideas from accounting. For example, it is not correct to say that aggregate revenue is the same as GDP. Revenue is an accounting term to show how much benefit you record in a year. GDP measures the value of production. It would be more accurate to write that aggregate output and GDP are the same. But if SM-games are reflecting the perspective of an accountant, as is stated, why is GDP being discussed at all? Similarly, the idea of a dummy player with off the book costs is not consistent with an accounting perspective. I think that the paper would be clearest if it did not attempt to use terminology from other fields. But if it is going to do so, it should make a more substantial effort to do so consistently.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "H1gVKATRFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper draws from concepts and patterns of game theory and economics to re-interpret common machine learning algorithms, and introduces a paradigm of n-player games such that there exists a simple way to study such games where each player is individually optimized by machine learning algorithms. \n\nOverall, this is a very interesting and inspiring paper with its interdisciplinary touch, but at the same time doesn’t lose readability for audience with mostly machine learning background. The paper is clear, concise, and well-written, and hence I do not have any overarching comments. There are several suggestions and questions, though, that I’d like to propose.\n\n1. Since many concepts are not from the machine learning domain, further and more detailed touch on related work are very beneficial. The current section of related work (Section 1.2) is more succinct than laying the right background information. Authors could consider giving some examples of “market mechanism”, and similarly for “design pattern”. This can give readers some ideas on how this present work’s use of “existing design pattern” is different from prior works’ proposals of “market mechanism”. Again for the second paragraph, although these concepts are more familiar to the audience, a short description for each mentioned concept is good to include (e.g. monotone games, etc)\n\n2. Move Lemma 1 before Definition 2? Since Lemma 1 is most related to Definition 1 and not related to Definition 2.\n\n3. For Definition 2, authors could consider adding “the classic definition [of Nash equilibrium]” to the list to clarify the difference. This classic Nash equilibrium definition will be referred to again in later sections. \n\n4. In Section 2.1, consider giving a formal definition of “potential game”.\n\n5. In Section 2.3, it is not immediately clear after the text why stop_gradient becomes a problem.\n\n6. In Section 3.1, could we elucidate a bit on what is “near zero sum”?\n\n7. In Section 5, why the equation following the text “firm i’s forecast” is always positive? Since by definition, forecast is meant to represent the change of profit, which can be negative?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper discusses smooth market games and demonstrate the merit of the approach.    The reviewers agree on the quality of the paper, and the comments have been addressed well by the authors.

Decision: Accept (Poster)