Multiagent Reinforcement Learning in Games with an Iterated Dominance Solution
Authors: Yoram Bachrach
Tor Lattimore
Marta Garnelo
Julien Perolat
David Balduzzi
Thomas Anthony
Satinder Singh
Thore Graepel
Venue:  (2020)
Keywords: multiagent
reinforcement learning
iterated dominance
mechanism design
Nash equilibrium

Abstract: Multiagent reinforcement learning (MARL) attempts to optimize policies of intelligent agents interacting in the same environment. However, it may fail to converge to a Nash equilibrium in some games.  We study independent MARL under the more demanding solution concept of iterated elimination of strictly dominated strategies.  In dominance solvable games, if players iteratively eliminate strictly dominated strategies until no further strategies can be eliminated, we obtain a single strategy profile. We show that convergence to the iterated dominance solution is guaranteed for several reinforcement learning algorithms (for multiple independent learners). We illustrate an application of our results by studying mechanism design for principal-agent problems, where a principal wishes to incentivize agents to exert costly effort in a joint project when it can only observe whether the project succeeded, but not whether agents actually exerted effort. We show that MARL converges to the desired outcome if the rewards are designed so that exerting effort is the iterated dominance solution, but fails if it is merely a Nash equilibrium.

Under review as a conference paper at ICLR 2020
MULTIAGENT REINFORCEMENT LEARNING IN GAMES WITH AN ITERATED DOMINANCE SOLUTION
Anonymous authors Paper under double-blind review
ABSTRACT
Multiagent reinforcement learning (MARL) attempts to optimize policies of intelli- gent agents interacting in the same environment. However, it may fail to converge to Nash equilibrium in some games. We study independent MARL under the more demanding solution concept of iterated elimination of strictly dominated strategies. In dominance solvable games, if players iteratively eliminate strictly dominated strategies until no further strategies can be climinated, we obtain a single strategy profile. We show that convergence to the iterated dominance solution is guaranteed for several reinforcement learning algorithms (for multiple independent learners). We illustrate an application of our results by studying mechanism design for principal-agent problems, where a principal wishes to incentivize agents to exert costly effort in a joint project when it can only observe whether the project succeeded, but not whether agents actually exerted effort. We show that MARL converges the desired outcome if the rewards are designed so that exerting effort is the iterated dominance solution, but fails if it is merely a Nash equilibrium.
INTRODUCTION
Intelligent agents sharing a common environment are affected by the actions taken by their peers. Using reinforcement learning (RL) to derive agent policies becomes challenging since the environment becomes non- non-stationary for each agent when its peers adapt their behaviour through their learning process. One simple form of multiagent reinforcement learning (MARL) is independent learning. where each agent simply treats its experience as part of the non-stationary environment. Unfortunately, independent MARI. fails to converge to Nash equilibrium in many settings (Bowling. 2000 Shoham
et al., 2003). To guarantee convergence to a Nash equilibrium, one must either examine restricted
classes of games such as fully cooperative games (Claus & Boutilier 1998 Bu et al. 2008 Panait al. 2006 Matignon al. 2007), or devise specialized algorithms that guarantee convergence (Hu & Wellman 2003) Wang & Sandholm 2003). We investigate independent MARL in games that are solvable by iterated elimination of dominated strategies (Moulin 1979). We say that action by an agent is dominated by another the first action offers the agent strictly lower reward than taking the second action, matter which actions taken by the other agents. In iterated elimination of dominated strategy we iteratively examine the actions of every agent, and remove strictly dominated actions, until no further actions can be removed. A game dominance solvable only one action profile survives the process of iteratively eliminating strictly dominated strategies.
We examine implications of the relation between iterated dominance and RL through applications in mechanism design, field in economics that studies how to set incentives for rational agents, so as to achieve desired objectives. One key line of work in mechanism design deals with principal-agen problems (Holmstrom et al. 1979) holmstrom 1982moaalgoossmmm 1ans2aanassssllffonn2///o relating to principal charge of joint project, whose success depends on the exertion of effort by multiple agents; the principal wishes to incentivize agents maximally exert costly effort, but cannot observe how much effort any individual agent exerted.
We show that for dominance solvable games, multiagent reinforcement learners converge to the iterated dominance solution for simple and reasonable algorithms; in games with two actions per agent, REINFORCE (Williams) 1992) converges to the solution, and in games with more than two actions Moonee-Carlo Policy Improvement (Sutton & Barto 2018) converges when using importance weighted action value estimators. In contrast Nash equílibrium, which exists in
Our contribution:

---

Under review as a conference paper at ICLR 2020
any game with finite action set, not every game is dominance solvable. However, in mechanism design settings we engineer the game in order to achieve certain desired agent behaviors, and can thus construct games that are dominance solvable. We examine mechanism design to illustrate the applications of our work, empirically investigating a principal-agent problem. We show that an incentive scheme based on iterated dominance guarantees that independent reinforcement learners converge to the optimal solution for the principal, whereas under a scheme where exerting effort is only a Nash equilibrium, independent RL typically does not converge to an optimal solution.
1.1 PRELIMINARIES
An n-player normal form game is given by a set of players = {ai..... ant. and for each player a, a (finite) set of pure strategies S,, and a utility function u, : Si x S2 x... Sn + R. where u4(81,...,,., 8p) denotes a, 's utility when each player aj plays strategy 8j. For brevity, we denote the set of full strategy profiles S = S1 S2 x ... x Sn, and denote items in S as s E S (s = (s),..., 8n), where 8; E S:). We also denote S_, = S x X Si X S x x Sn. and given partial strategy profile 8_, = (81,....; 8,-1 8 .......)))))).......... E S_; we denote (8-1, ($1,...,&$ 84-1, 86, S1411...8,, ..) >) E S. Given a normal form game G. we say agent aj strategy 82 E S, strongly dominates Sy E St if a, 's utility is higher when using s, than when using Sy. no matter what strategies the other agents use, i.e.: agent a, 's strategy Se E S, strictly dominates sy E S if for any partial strategy profile s-, E S_; we have ui ui((s_ 82)) > u;((s-i, 8y)). We say player a,'s strategy 8, is a, 's dominant strategy if it dominates all other strategies 8; E S.
Game-theorete solutions specify which outcomes are reasonable, under various assumptions of rationality and knowledge. We focus on a prominent procedure called iterated elimination of dominated strategies, and identify conditions under which learning agents converge to this solution. In cases where every agent has a dominant strategy, it seems reasonable to predict that each player would play their dominant strategy. Given a game G, we say a strategy profile = ($1...., sn E S is dominant strategy equilibrium if for any agent a,, strategy 8; is dominant strategy for a;- However, in many games a player may not have a dominant strategy. A less demanding concept is that of Nash equilibrium, which merely seeks strategy profile where player can improve their utility by unilaterally deviating. Given game G a strategy profile = (S1,..., 8n) is a Nash equilibrium if for any player a, and any alternative strategy 82 E ES, we have u;(s) 2 u,(s 8x) (i.e. (s......... S St. si+l:.... sn)) 2 usss)..... -;_1. Sp. $1+1...., Sn))). )). A mixed Nash equilibrium exists in games with finite strategy sets (Nash al.] 1950, Morgenstern
Von Neumann [953), but many games have multiple Nash equilibria, resulting in an equilibrium selection problem.
Another prominent concept is that of iterated dominance (Osborne Rubinstein 1994), where we iteratively remove dominated strategies, with eliminated strategies no longer having effect on future dominance relations. Given a game G with players I fa!..... a,, strategy sets S,...., S,, and utilities ,.,..., Un. a (strict) domination elimination step dl is a triplet d = (i E L, E S, 84 E S.), where the strategy 8) strictly dominates 81 for player i. The elimination step d indicates that 81 is eliminated from G as it is dominated by Sh. Following the elimination step we get the game Ga. which is identical to G except the strategy 8 is removed from strategy set S, of player i (i.c. the strategy set for i in Ga is S, \ (st)), and the range of the utility function is restricted to this reduced strategy set). A dominance elimination sequence is a sequence (G, d1, Gd, d2, Gd2
Gd. dz-1. Ga.) where G is an initial game and each de is an elimination step from the game G, resulting in the game Gi+1. If no more dominance elimination steps can be taken from Gj. we say that the strategy profiles in G3 survive iterated elimination of (strictly) dominated strategies. Further, if no more dominance elimination steps can be taken from G2 and there is only one strategy remaining for each player, the game called (strict) dominance-solvable Iteratively eliminating dominated strategies is known to reserve Nash equilibria, and further when removing only strictly dominated strategies the procedure is inaepiindeeen,ntt", yielding the same final strategy sets regardless of the order in which the dominated strategies were removed (Osborne & Rubinstein 1994).
Our discussion focuses on normal-fort game, but out results extend to temporally extended settings (games with multiple timesteps). We consider MARL in Markov games (Shapley 1953 Littman 1994), where in each state agents take actions (possibly given only partial observations of the true world state), with each agent obtaining individual reward. We consider independent MARL, where agents each learn a behavior policy through their individual experiences interacting with one another in the environment. We discuss MARL in Markov games in Appendix 6.3 along experimental results.
2

---

Under review as a conference paper at ICLR 2020
One motivation for work comes from mechanism design, field of economics investigating how incentives should be set up so as to achieve desired outcomes strategic settings where multiple agents interact. This was studied in settings ranging from government policy and social choice to
auctions (Börgers, 2015 Nisan & Ronen 2001; Krishnal 2009; Abdulkadiroolu & Sönmez, 2003
Parkes & Singh| 2004). We focus on principal-agent problems, where agents take actions behalf
of another entity called the principal, but agents' interests may not align with the principal's (Holm-
strom et al. 1979: Grossman & Hart 1992, Laffont & Martimorl 2009). A key example efforts
in a joint project consisting of multiple tasks, each handled by an agent (Holmstrom et al. 1979
Holmstrom
1982
Winter 2004 Babaioff al., 2006). We discuss this model in Section
2 MULTI-AGENT RL AND
GAMES
We consider training multiple independent reinforcement learners in a game G which is strict dominance-solvable. Each agent i takes the role of player in the game G and its possible actions are the strategies in S, Given the actions (strategy choices) of all agents we obtain full strategy profile E S1 X ... S,, and the reward each agent obtains is the respective payoff (s(s) in the game. As we consider training general RL agents in a domain that is normal form game, we intermix game theoretic terminology (strategies and payoffs) and RL terminology (actions and rewards).
2.1 LEARNING DYNAMICS IN NORMAL FORM GAMES
Given the strategies s E S-, of all players except i, agent faces a single run of a game denoted as b (reflecting the setting induced by the choices 8-; E S-; of other players). The possible actions for agent are S, and any action a E S; results in a reward r = (s(8-5,)) a) as given by player i's payoff in the game. However, agent i simply selects action and receives its obtained reward; it plays without ever gaining knowledge of which strategies were used by the other agents.
2.1.1 REINFORCE AGENTS IN NORMAL FORM GAMES
We consider REINFORCE (Williams 1992) agent which maintains score (logit) per each ac- tion, x = 31. Ty, and applies a softmax operation to transform these scores to the respective probabilities of choosing each action: (a) = Σøn exp(x,) Each agent starts with initial logits for
exp(xa)
I1. .l...... Zn. Fixing the choice b of the other agents (relating to their chosen actions in S-i), denote by Jo the expected reward of the target agent, so Σ. Pr (a)r The exact REINFORCE update Σ. V.VVVaa
is: In+1 Fn + ab
As agents only take a single action each episode, this is typically estimated by substituting V = E. ra (a) = Σ. raP..(a) (a) V Po Ea-p,r r V log (a)),, then selecting a single action a sampled from the distribution ps (parame- terized by x). Given the softmax rule above for setting the action probability distribution Pz. and denoting Kronecker delta as dij we have: @p.(t)
(i) pÿ)-
azz
We examine MARL. dynamics dominance-solvabie games, identifying conditions under which learning converges on the (strict) iterated dominance solution. Given the dominance climination sequence (G, d1. Gd. d2, Gd...... Gd 1, Ga.) (where the d,s are elimination steps), one may hope the learning dynamics would "follow" the strategy elimination steps in the sequence, first lowering the probability on the dominated strategy of d1 to (almost) zero, then lowering the probability dominated strategy of d2 and on, until remain with agents only playing the strategies of Ga.- We show that this is indeed the case for MARL using REINFORCE when each agent has at most two strategies. For settings with arbitrary number of actions per agents, provide a similar proof for a variant of Monte-Carlo policy iteration given in Section 2.1.2
2.1.2 IMPORTANCE WEIGHTED MONTE-CARLO AGENTS IN NORMAL FORM GAMES
Monte-Carlo policy iteration (MCPI) is one of the simplest methods for control. It maintains an estimate of the expected reward for each strategy, updating the estimate after observing the outcome of every run of the game, and follows an e-greedy policy based these estimates to guarantee exploration. To achieve convergence dominance dominance-solvable games, we use the specific estimator of A At every step it maintains a score x; for every possible action E S.. The scores
3

---

Under review as a conference paper at ICLR 2020
softmaxed derive policy distribution P over actions. We denote by P. the probability of choosing action i E S,. Every step, the agent selects an action 8; from the current policy P. and depending on the actions b S_, taken by other agents, it receives reward rh We denote the probability of selecting action under the policy P at time as Pt,; and the action taken by the agent at time as
Ag. As estimator for the reward when selecting action i, use Re, 1(A,=()r' (in contrast to standard MCPI whose estimator is the average past rewards when selecting action i). The score dy; increased by the estimator Re,,, and the scores x are softmaxed to obtain an improved policy. As with MCPI, to maintain exploration we use e-greedy version of this improved policy in addition to the exploration due to the softmax), Algorithm iis thus a variant of MCPI with an importance weighted reward estimator, which study in the context of MARL in dominance-solvable games.
Pt.:
Algorithm I: Importance Weighted Monte Carlo Policy Improvement (IW-MCPI), for agent /
1: procedure IMPORTANCE WEIGHTED MCPI
2: I3 + (for all 8, E Si)
3: for t = 1,2, do
4:
For each i let Qi Σソ=1 exp(x,) // Compute softmax of x =,Q,
exp(x;)
5:
For each i let P. = ( + e/k Compute e--gredy policy derived from Q
6:
Sample action A, ~
7:
Other agents select (unknown and unobserved) strategies E S-1
8:
Play A, in the game, obtaining reward r
9:
Ri, -
1(A
P:
24 1 Ix: + RI,i
11: end for
12: end procedure
CONVERGENCE OF RL TO AN ITERATED DOMINANCE SOLUTION
We show that MARL in dominance-solvable games converges to the iterated dominance solution using the above MCPI (Algorithm [ or under REINFORCE in the two action case. One may consider two training modes. In the serial mode, cycle through the agents, each time performing RL updates for the policy of the current agent while holding the policies of other agents fixed for many iterations (enough for the policy to converge and eliminating strategy). As we fix the strategies of others when training each agent, the process "follows" the domination elimination sequence. Another training mode is parallel mode, where we update the policies of all agents following the experience gained in each episode (Littman 1994). Our convergence results hold for both modes, but handling the parallel mode requires the more intricate conditional expectation analysis of Theorem 3.4
3.1 BINARY ACTION CASE
Consider a dominance-solvable game and MARL using REINFORCE. As discussed in Section 2 given the strategic choices of other agents 6 s S... agent i faces a run of the game, with reward r = ( i.. a) depending on i'ss action and the strategies b of the other agents. Each agent i performs the REINFORCE updates of Section 2.1.T based only on its action a and obtained reward rh without ever becoming aware of the strategies b = s taken by others. A dominance elimination step d = (i, 81, 5n) includes a dominated strategy 81 and dominating strategy 8n for agent i, where 8,, strictly dominates greater utility from 8y than 51; Thus for any 8-1, (1h 8-4) > u11,, s-1). or in other words, for any setting b S_, that agent may be playing, action 3h. has higher payoff than st, so r r Lemma 3.1. Let B be a set of settings with two actions si and Sh. where for any setting B the respective rewards for sn, is strictly higher than for St, so rb > rrh The REINFORCE update eventually places a mass as close to zero as desired on the dominated action St-
so no matter what strategies 8-; other players choose, player obtains strictly
Proof. We consider applying the update for setting b, and baseline of the lower reward r.. Denote
the minimal gap between the rewards of the actions as g minse m rb 0. We have:
4

---

Under review as a conference paper at ICLR 2020
-. = = (sp=(sh)+ tr V Vs))(s)). The baseline argument for policy gradient
updates states that for any constant we have: v. (. (a)ra) = V. Pa (a) - c)). Using the baseline argument with c = r', we get: v = (ra, -
- V.Pa(s)) (ra, -r VV.P(rr))
(r., - v.Pr(ss) 2 (s). Thus, regardless of the setting b used, the update increases the probability of the dominating action, at least as much as the update for the minimal gap setting does. Repeatedly applying the update for the minimal gap setting eventually places negligible probability on the dominated action, so this is also the case for any update sequence (of any of the settings). C
Theorem 3.2. Let G be a dloinance-solvabbl game which has a single stralegy profile 8 Si x X Sn, surviving iterated elimination of strictly dominated strategies, and where every player has at most 2 strategies, and consider agents trained independently using the REINFORCE update. Then the agents converge to the iterated elimination solution 8.
Proof. Consider an iterated elimination sequence (G, d1. Gd d2. Gdg....,Gaur dx-1, G. The first climination d1 (i. ( st,) relates to agent i who faces different settings due to other agents playing different strategies, but whose payoff under some 8h S: strictly dominates Lemma 3.T shows it eventually places negligible mass 61 on the dominated action (for as low c as desired). We examine the second elimination step d2 = [j, s..) While in the original game has faced some settings E S_j where of E Sj got a higher reward than & E Sj. these settings are encountered less and less frequently. Consider target probability é2 for agent j to select the dominated strategy sf. By Lemma 3.1 there is a number & of steps where if we train agent j for k steps only on settings where of is dominated by sh places mass of at most E2 s7. By the union bound, the probability of encountering a "wrong" setting (with of not dominated by * is at most k as 61 is as small as desired, the probability of agent j not reaching the target (a mass of at most 22 on sf)) is also as small as desired. Applying this argument over the elimination sequence, we conclude that agents converge on the single strategy profile s surviving iterated elimination.
E S
Our proof of Theorem 3.1 iteratively applies Lemma 3.1 which holds when players have at most two strategies. Section 3.2 provides similar results to Theorem 3.2 for more than two actions, but under the MCPI variant of Algorithm [ Section backs the theory up through experiments.
3.2 CONVERGENCE IN DOMINANCE-SOLLARRE GAMES FOR IMPORTANCE WEIGHTED MC
We consider agents using Algorithm I (IW-MCPI), and show that when an action dominates action j. IW-MCPI eventually stops choosing the dominated action. We assume rewards are normalized to the range [0. 1]. Denote the IW-MCPI estimator for the reward of action i in time t as Ra,i,
where Re, 1(Ar=()r', (r'),, depends on the agent's action A,, and the actions b taken by others). Pt.s
The reward estimators R, = =Re,,, ... Re,,)
are then converted to scores per action where Sr,; = =E R2... and the scores are converted to a distribution Q. = (Qt,,, Qt.,..... Qx,x) by taking the softmax: Q+ Softmar(SS) Q encodes "greedy" policy, which is then converted to an c, e--rredyy policy P,: Pt, = & + (1 (i). We anneal the value of e, towards zero over time. Note that over time I, the scores St,; are sequence of random variables Si, S2.,..... Sr, where each St, dependent on the earlier variables ..,,,,.,,,,,1.. We denote the conditional expectation
of St,; given the previous variables as: E, (S.,)) e E[S... |S,,, .2. St_1,s] In other words, E, denotes the conditional expectation with respect to the observations by player i at the start of round I.
Theorem 3.3. Assume that en is non-increasing and lim en = 0 and lim
log(n) n2
ΣT 1
O. Fix an agent and let Re be the expected reward for the agent when playing action in round t.
1 Then the following holds with probability one: lim ñ Σi= RR, Ru.3 =0.
Proof. E, [R, = Re,s and E., [R2,] =
R2,
Pr. F.- Let Xx Re,i Re.:- Freedman's inequal-
ity (Freedman et al., 1975) states that for a sequence of random variables .I..... X, (each depending on the previous ones in the sequence), with high probability of least 1 5 the following holds:
5

---

Under review as a conference paper at ICLR 2020
IX (Xe - -x(Xx)
& soy
[ari[Xi] log 3.- Applying Freedman's 's inequality we obtain:
2
3k
2 (
P
Σ
X
2k
log
+
log
S S.
26
[ml
Then by union bound it follows that with probability at least
the following holds for all m:
n
2n(n+ + 1)
3k
2n(n + )
X S
2k
log
log
(I)
Et
5
2en
The assumptions that Cn is nonincreasing and lim,- login)
0 imply that
lim,-100 log(n) < lim, log(n)
21=1 = 0. Combining this with 1
2n
1 shows that with probability
Nen
one we have: limn-
Theorem 3.4. Lef G be dominance-solvable game which has a single strategy profile 8 S
x Sn surviving iterated elimination of strictly dominated strategies. Consider agents trained independently using Algorithm | the iterated elimination solution
Provided that lim n22 _t=l = 0, the agents converge to
log(n)
13
Proof. By setting E 1/t², for any p E (0, 1), the assumptions on e, ensure that we can apply Theorem 3.3 (for all i, with probability 1). We show players' strategies converges to the iterated dominant profile. Suppose there exists a round тi after which action dominated by action j. which means there exists ag O such that for all / Ti it holds that Re, S Rej 9. Then:
Res
RI,i =
Σ
[Ra.-
Re,5)
1
Σ
Ra.: Re,,)
Σ 1=1
[Re.) - Re,:)
1=1
t=1
1=1
Σ
Ra. Rr.s) Σ
n
R Ri,,)
T1
g(n - T1)
n
n
n
n
Taking the limit tends to infinity shows there exists time T2 such that for all 2 12 have Σi=1 Ras Ri, ng/2. Therefore for any n 2 T2 have:
exp
EE RE,
exp
Re,
Qn =
S exp (-ng/2).
(3)
Σ exp
E1 Rc.))
n- Ri.j)
exp
Hence, PR.s = (x) t cn/k S + exp (-ng))2. Since lim = 0 by assumption,
follows that lim, PR.i 0 almost surely. The previous part shows that if action is dominated after some round Ti, then for any > 0 there exists a round 73 such that Pa.i < e. Choosing sufficiently small and iterating the argument completes the proof in the same way as Theorem 3.2
EMPIRICAL ANALYSIS OF PRINCIPAL-AGENT GAMES
Our environment is simulation of a prominent problem studied by economists, called the principal agent problem (Holmstrom et al.) 1979; Holmstrom 1982, Winter 2004 Babaioff et al. (006). through which we show how our results can be used to design mechanisms for reinforcement learners. It considers a project which requires completing multiple tasks, each handled by an agent. Normally each task succeeds with a low (but non-zero) probability, which increases when the handling agent exerts additional effort. The project succeeds only if all its tasks succeed, in which case the principal stands to gain large monetary amount (A (Appendix 1..21..cosse considers model where some task failures allowed). The principal thus wants to make sure as many agents possible exert effort. A dilemma arises when exerting effort is costly for the agents (i.e. incurs an immediate negative reward); A natural way compensate for that is for the principal to offer agents reward based on the effort they exerted. However, in principal- the entire project succeeded, and is incapable of observing whether any individual agent exerted
settings, the principal only knows whether

---

Under review as a conference paper at ICLR 2020
effort (note tasks succeed with non-zero probability even without effort). Thus, it can only promise each agent a reward r, offered only when the entire project is successful. We refer to the promised rewards r = (ri...... :?n) as a reward scheme. Each such reward scheme induces game played by the agents, and the principal gets to design the game, by selecting the reward scheme. On the one hand, the higher the rewards, the more incentive agents have to exert effort. On the other hand, the rewards are costly to the principal, so they want to minimize them. One possible reward scheme is Nash equilibrium implementation, where the principal sets rewards so that the profile where all agents exert effort is a Nash equilibrium (Babaioff et al. 2006). A Nash scheme may seem tempting to the principal as it offers low rewards. However, independent MARL may not converge a Nash equilibrium (Lanctot et al. 2017). and there may be multiple equilibria, so agents may converge on an undesired equilibrium. A scheme at the other end of the scale a dominant strategy scheme, where the principal promises each agent a reward high enough to make exerting effort dominant strategy, so each agent would rather exert effort no matter what others do. Under this scheme MARL converges on exerting effort, but it is expensive to the principal. We show that an iterated dominance scheme is a good middle ground, guaranteeing convergence to the desired equilibrium at a far cheaper cost.
Environment parameters: we simulate a project which depends on five tasks T = {t, ) cost c = 10 for exerting effort, and where any task &, succeeds with probability h = 0.8 if agent exerts effort and with probability 1 = 0.1 if they do not. Every episode, each agent takes one of two actions, either exert effort or not. We sample the success of each task I, as a Bernoulli variable, with a success probability of either h or I, depending on agent i's action. The entire project is successful only if all tasks {t are successful. The rewards r = (ri...., rn) are the parameters of our environment; an agent who exerts effort incurs negative reward -c, and if the project is successful they also receive reward r, Table shows the possible reward schemes for these settings. We briefly discuss how these were computed, with full details in the appendix.
Reward scheme
Rewards r (71, (T,,
Nash scheme
+35 + + 35 c,35 c) (142, 857 + 142, 857 + 142, 857 + 142, 857 + e, 142, 857 +e) 142,
Dominant Scheme
Iterated dominance scheme
(142, 857 +7, 858 +,, 233 + e, 280 + 3, +c)
Table I: Reward schemes in our joint project principal-agent environment.
Consider agent i who is promised a reward r; and who knows that exactly m of the other agents would exert effort (so the remaining
m - 1 will not exert effort). If exerts effort, the project succeeds with probability hm*11 1 1 so their expected reward is h 1- p=-m--.. r; - c. If i does not exert effort, the project succeeds with probability hm pn-m and their expected reward 1n-m-1 h T4 >> h"d -n-- -ú, or equivalently if r; > c/hh=+1 pa-m-1 h 1" -n=-).. Observe that the minimal reward to induce i to exert effort decreases in m, and when assumes no other agents would exert effort (m = 0), the required reward ri is ri > c/(h- 1--1 Int). Thus setting r; to P3 c/(h- 1n-1 - 1 +
is ft 1"-m_ Ts. Agent would thus exert effort if::
for all agents makes exerting effort a dominant strategy for all agents. In contrast, when i assumes all other agents exert effort (m n - 1), the required reward r; is ri > c/(h" n--1 I), so setting r; = c/(h" - h=-1, I) + e for all agents makes exerting effort a Nash equilibrium. Setting r. = =/(h=+11 pn-m-1 hm (n-m) + e results in an iterated dominance scheme: the dominant strategy for the first agent is exerting effort; once not exerting effort has been eliminated as a strategy for player i 1, player i assumes players to 1 would exert effort, and thus they also exert effort.
As Table shows, even with only five agents, there are huge differences in the principal's 's expenditure when the project succeeds. We simulate the environment with all three reward schemes, setting e <= 160 so the reward is just above the minimum threshold (e = 160 is negligible compared to the high reward 142, 857), and use both REINFORCE learners, and Advantage Actor-Critic agents (Mnih) et al. (0166) agents. Our results show that under the cheap Nash scheme MARL does not converge to exerting effort (rather, all agents end up not exerting effort). However, MARL does converge on exerting effort for the iterated dominance scheme, which is far cheaper than the dominant scheme.
Figure T shows the proportion of times where agents select the high effort action over training time under the Nash scheme, indicating that agents do not converge on the Nash equilibrium of all exerting effort. Figure [ shows the results under the dominant strategy scheme, showing all agents converge on exerting effort. Figure 3 shows the results for the iterated dominance reward scheme, for different
7

---

Under review as a conference paper at ICLR 2020
Potton of fand wark acions
3.-
9.5
9.-
Eption: 180
Bpsile:: 150
busitmn: 200
Spsien: 220
0.5
30
Thrnig Iention230
310
213
30
Thining amd
320
200
250
50
Training Iteration x200
100
150
200
250
Figure I: Nash scheme
Figure 2: Dominant scheme
Figure 3: Iterated Dominance scheme
1.0
10000
300
0.8
10000
tpsiions 200
Spalion: 160
of hard
0.7
0000
Agent
0.5
2010
Agent Agent 4
0.3
130
15a
200
2000
200
255
Trairing itoration x100
Training iteraiio
Figure 4: Individual agent effort (Iterated Dominance)
Figure 5: Rewards (Iterated Dominance)
values of c. It shows that agents indeed learn to all exert effort, at much lower cost to the principal than in the dominant strategy scheme (roughly 20% of the cost under the dominant strategy scheme).
Figure D shows the effort level of individual agents over training in the iterated dominance scheme (measured by the proportion of times where each agent selected the high effort action). It shows that first the highest reward agent learns to exert effort, then the next agent and so on. Interestingly, given the initial effort levels of the other agents, the last agent (with smallest promised reward) initially learns not to exert effort. Only after the other agents exert more effort, this agents learns to exert more effort. Figure 5) shows the mean agent reward over time the iterated dominance scheme (similarly to Figure 3). It shows that agents exert more effort, they improve their overall reward (reaching the reward under the scheme when all agents exert effort). The above figures are for REINFORCE agents, but our experiments with Advantage Actor Critic agents (Mnih et al. (016)) yield very similar results.
These results highlight the importance of the iterated dominance concept for multiagent systems comprised of independent reinforcement learners: such systems may converge the desired Nash cquilibrium, but do converge to an iterated dominance solution. Thus, when designing mechanisms for multiple reinforcement learners, one should strive for an implementation that based on the stronger iterated dominance solution, rather than on the less demanding Nash equilibrium.
We note that our theoretical results hold for REINFORCE only when agents have two actions, however, in the appendix we consider simulation with three actions (effort levels), and we show that empirically agents do converge to the desired outcome in this case as well.
CONCLUSION
We have provided convergence results for MARL in iterated dominance solvable games, and discussed their implications to mechanism design for RL agents. Our results show that reward schemes based on iterated dominance are desirable, as MARL with reasonable learning methods is guaranteed to converge to such solution, in contrast to schemes based on Nash equilibrium. Several directions are open for future research. First, while we only proved convergence for specific RL algorithms or under some restrictions the underlying game, we conjecture convergence occurs in wider settings. Could our results be extended to cover other RL algorithms or fewer restrictions on the game? In particular, can prove convergence for REINFORCE with three more actions? Second, we have focused on strict dominance what can one say about weak iterated dominance? Finally, could we theoretically bound the required time convergence an iterated dominance solution?
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Atila Abdulkadiroglu and Tayfun Sönmez. School choice: A mechanism design approach. American economic review, 93(3):729 747, 2003.
Moshe Babaioff, Michal Feldman, and Noam Nisan. Combinatorial agency. In Proceedings of the 7th ACM conference on Electronic commerce, pp. 18-28. ACM, 2006.
Tilman Börgers. An introduction to the theory of mechanism design. Oxford University Press, USA, 2015.
Michael Bowling. Convergence problems of general-sum multiagent reinforcement learning, In ICML, pp. 89 09-9,,2 2000.
George W Brown, Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
Lucian Bu, Robert Babu, Bart De Schutter, et al. A comprchensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172, 2008.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. AAAI/IAA,, 1998(746-752)2, 1998.
Vincent Conitzer and Tuomas Sandholm. Complexity of (iterated) dominance. Proceedings of the 6th ACM conference on Electronic commerce, pp. 88-97. ACM, 2005.
David A Freedman al. On tail probabilities for martingales. the Annals of Probability. 3(1): 100-118, 1975.
Drew Fudenberg, Fudenberg Drew, David K Levine, and David K Levine. The theory of learning in games, volume 2. MIT press, 1998.
Sanford J Grossman and Oliver D Hart. An analysis of the principal-agent problem. In Foundations of Insurance Economics, pp. 302-340. Springer, 1992.
Bengt Holmstrom. Moral hazard in teams. The Bell Journal of Economics, pp. 324-340, 1982.
Bengt Holmstrom et al. Moral hazard and observability. Bell journal of Economics, 10(1):74-91, 1979.
Junling Hu and Michael Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 1(N0v):1039-1069, 2003.
Vijay Krishna. Auction theory. Academic press, 2009.
Jean-Jacques Laffont and David Martimort. The theory of incentives: the principal-agent model. Princeton university press, 2009.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 4190 4203, 2017.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Laëtitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Hysteretic q-learning an algorithm for decentralized reinforcement learning in cooperative multi agent teams. In 2007 IEEE/RSI International Conference on Intelligent Robots and Systems, pp. 64-69. IEEE, 2007.
Panayotis Mertikopoulos. Christos Papadimitrion, and Georgios Piliouras. Cycles in adversarial regularized learning. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2703-2717 SIAM, 2018

---

Under review as a conference paper at ICLR 2020
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference machine learning, pp. 1928-1937, 2016.
Oskar Morgenstern and John Von Neumann. Theory of games and economic behavior. Princeton university press, 1953.
Hervé Moulin.
Dominance solvable voting schemes. Econometrica: Journal of the Econometric Society, pp. 1337-1351, 1979.
John H Nachbar. Evolutionary selection dynamics in games: Convergence and limit properties. International journal of game theory, 19(1):59-88) 1990.
John Nash et al. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48 49, 1950.
Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic behavior, 35 (1-2):166-196, 2001.
Shayegan Omidshafiei, Daniel Hennes, Dustin Morrill, Remi Munos, Julien Perolat, Mare Lanctot, Audrunas Gruslys, Jean-Ba San-Baptistt Lespiau, and Karl Tuyls. Neural replicator dynamics. arXiv preprint arXiv: 1ttp::990000000000 2019.
Martin Osborne and Ariel Rubinstein. course in game theory. MIT press, 1994.
Liviu Panait, Keith Sullivan, and Sean Luke. Lenient learners cooperative multiagent systems. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pp. 801-803. ACM, 2006.
David C Parkes and Satinder P Singh. An mnd-based approach to online mechanism design, In Advances in neural information processing systems, pp. 791-798. 2004.
Julia Robinson. An iterative method solving game. Annals of mathematics, pp. 296-301, 1951.
Peter Schuster and Karl Sigmund. Replicator dynamics. Journal of theoretical biology, 100(3): 533-538, 1983.
Shapley. Stochastic games. Proceedings of the National Academy of Sciences of the United States of America, 39(10):0055-111 1953.
Yoav Shoham, Rob Powers, and Trond Grenager. Multi-agent reinforcement learning: critical survey. Web manuscript, 2003,
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Peter D Taylor and Leo B Jonker. Evolutionary stable strategies and game dynamics. Mathematical biosciences,
1978.
Xiaofeng Wang and Tuomas Sandholm. Reinforcement learning to play an optimal nash equilibrium in team markov games. In Advances in neural information processing systems, pp. 1603-1610, 2003.
Jörgen W Weibull. Evolutionary game theory. MIT press, 1997.
Ronald J Williams. Simple statistical fradient- algorithms for connectionist reinforcement learning, Machine learning, 8(3-4):229-256, 1992.
Eyal Winter, Incentives and discrimination. American Economic Review, 94(3):664-77 2004.
10

---

Under review as a conference paper at ICLR 2020
6 APPENDIX: RL IN THE PRINCIPAL-AGENT JOINT PROJECT DOMAIN
Our empirical results regarding the joint project domain show how our theoretical results regarding MARL in iterated dominance solvable games can be used for mechanism design for reinforcement learners. We make the point that while many games are not iterated dominance solvable, in various domains we may design the game the agents play. We demonstrated how iterated dominance design is preferable to a design based on the less demanding Nash equilibrium using the the principal-agent domain. A principal trying cut costs (promised rewards) may settle on a Nash reward scheme, where it is a Nash equilibrium for all agents to exert effort. On the other hand, principal who is extremely cautious may try and guarantee that all agents exert effort, by using dominant strategy scheme, which promises extremely high rewards, sufficient to make it dominant strategy for every agent to exert effort. Our empirical results show that when agents are "reasonable" reinforcement learners, neither extreme is recommended. For RL agents, the principal could promise an iterated dominance reward scheme, which on the one hand achieves convergence to the desired outcome of exerting effort, and on the other hand does so at far lower cost than the dominant reward scheme.
The empirical results in the main paper consider a setting where agents have two effort levels (exerting high effort or exerting effort) and where the joint project only succeeds when all tasks succeed. In this appendix we provide more detailed experimental results:
1. We provide a more detailed derivation of the reward schemes: the Nash scheme, the dominant strategy scheme, and the iterated dominance scheme.
2. We consider a richer model with three effort levels: effort, medium effort and high effort (each resulting in a different task success probability). We show that REINFORCE agents converge to the desired outcome of exerting effort. Our theoretical results for REINFORCE only hold for the two action case, so this gives some indication that convergence occurs even in settings where is not guaranteed by our theoretical results.
3. We discuss more general combinatorial joint project model, where the entire project may succeed even when some tasks fail. In this case, we have a list of task subsets which result in the successful completion of the project. We provide simulation results for the case where the project succeeds if all tasks are successful, or if at most one task fails. Our results show that in this case as well, agents converge to the desired outcome of exerting effort under an iterated dominance reward scheme.
We begin by presenting the more general model of the joint project problem, and discuss how the three reward schemes are derived. Finally, we provide the additional empirical results discussed above.
The joint project principal-agent domain relates to a project comprised of a set of tasks T = (t.) In the main paper we considered the case where the project successful only when all tasks are successful. In the more general model, the joint project is successful when certain subsets of tasks are successful. We consider technology funnttion V : IP(T) + {0, 1} which maps a subset of tasks to a Boolean value indicating whether completing them results in successfully completing the project. We generally assume the technology function is monotone so if t1 S tz S T and v(t2) = 1 then v((2) = 1. We refer to subset of tasks T' such that v(T') = 1 as set of tasks fulfilling the project. The set of all task subsets fulfilling the project is denoted as Tw = (TT.. S (TWw(T..) = 1).
A set of agents 1 = {a: are in charge of the tasks, with agent a; in charge of task 4,- Task & has a base probability 4 > 0 of succeeding, and agent i has two strategies S, = {e, d} where e stands for exerting high effort, and d stands for not exerting effort. If a; exerts effort, the probability of task t; succeeding rises from its base probability of I, to higher level h2 S 1. The additional effort is costly, incurring negative reward c; < 0 to the agent. We assume the tasks succeed or fail independently of one another.
For subset of players C' J. we denote the tasks owned by these players T(C) {4; Tia C) Suppose agents in C' exert effort, and agents in / )) C' do not exert effort. If a; E C then 4 succeeds with probability h4, and if a, & C, 4. succeeds with probability 4, Given C C T, we denote the probability task t; is successful as pt (C), where
( (bs 1446
P((C)
4
ift C
11

---

Under review as a conference paper at ICLR 2020
Consider subset of tasks T C T. When only the players in C' C I exert effort, the probability that exactly the tasks in T' are successful is:
Pr(TT) C
= II P.(C). II (1-p:(C))
CTT
Similarly, the the probability that any subset of tasks fulfilling the project achieved is Pre(Win) = ET. ETwin (rc(Tw).
To incentivize agents to exert effort, and maximize the probability of successfully completing the overall project, the principal offers the agents a reward vector (ri,...., Tn), conditioned on the project's success. If the project is successful, agent receives a reward of ry from the principal (and receive nothing if the project fails).
The joint project game is a normal form game G(r) obtained given the specific reward vector r chosen by the principal. When only the agents in C' C I exert effort (i.e. any a; & C does not exert effort), a,'s 's expected reward from the principle is:
e((C) =
Σ Te ETwnn
(T(Tw) M
Agent a; has cost o; for exerting effort, and can choose between two strategies: exerting effort (c), or not exerting effort (d), where exerting effort increases the probability of the project succeeding and thus the expected reward from the principal, but at the certain cost G₁. We denote by S the set of possible strategy profiles S = S x x S,,. where for any agent i we have S = {e, d].
Given a strategy profile s = (si.... sn) E S, we denote the set of agents who exert effort in by C, {a: E I|s; = e}. The payoffs u, S + R have a simple structure (note that setting s; increases the project success probability and thus the expected reward e; (C.)):
uz (s(s)
(C,) -4
Cj
if
(c,(C.) if s; =d
6.1 APPENDIX: A DETAILED DESCRIPTION OF THE JOINT PROJECT REWARD SCHEMES
We give a more detailed derivation of the reward schemes for the principal in the joint project problem: the Nash equilibrium scheme. the dominant strategy scheme, and the iterated dominance scheme. A Nash scheme is a reward scheme (r1, r.,...,. T')) where the strategy profile where all agents exert effort is a Nash equilibrium. Given the definition of a Nash equilibrium, this means that no agent wants to unilaterally deviate. In other words, the requirement is that for any agent under the assumption that all other agents are going to exert effort, agent would also rather exert effort. [ Such Nash based schemes widely studied in the mechanism design literature, with some work specifically discussing such schemes in joint project principal- ageent settings (Babaioff et al. 2006).
In contrast, dominant strategy scheme is reward scheme (r1, T2,..... ........ .n) where the dominant strategy of every agent is exerting effort. In other words, the requirement here is that no matter what the agent assumes others would do, they would rather exert effort.
We first discuss the model used in the empirical section of the main paper, where the joint project requires the success of all n tasks, each of which succeeds with probability h when the relevant agent exerts effort and probability when the relevant agents does not exert effort.
An agent's s expected reward us(s) depends its chosen action 8; as well the actions of other agents &_ In our simple joint project model, all tasks have a success probability when the relevant agent exerts effort, and a success probability of / if they do not exert effort. As these probabilities I, are the same for all tasks, it is sufficient to know how many agents exert effort in the profile s to know the success probability of the project (we do not need to know exactly which agents exerted effort).
Consider agent i who is promised a reward r; and who knows that exactly m of the remaining agents are going exert effort (and the remaining n m 1 will not exert effort).
Note that there requirement for this be the only Nash equilibrium.
12

---

Under review as a conference paper at ICLR 2020
If agent exerts effort, the probability of the project succeeding and the agent getting the reward r; is hmmf1 1 [=-m-1 and their expected reward is then h"* 1n m-- r; C.
Similarly, if agent i does not exert effort, the project succeeds with probability hm -m-" and their expected reward is then ht --"- T--
Agent i would exert effort if their expected reward when exerting effort is high than the expected reward when not exerting effort:
h 1--m-1 r - C 1tth 1n-m .i
Equivalently, the condition for exerting effort is hm pn-m-1. nm mm- c. We extract the threshold reward for exerting effort. as function of m:
ri(m) > c/ e/(h" m+ 1--m-1 hm 1 p)-m)
Observe that the threshold reward to induce i exert effort, rs (m)) is monotonically decreasing in m, so the more agents i assumes would exert effort, the less it needs to be rewarded to induce it to exert effort. Given the above function ry (m)) the threshold reward to induce agent to exert effort when assuming all other agents would not exert effort (m = 0) is: Ti > c/(h 1"-1 - -")), As r, (m) is decreasing in m, setting r > c/ 1n-1 - (*) is sufficient to induce to exert effort for any m {0, 1.... , 1}. In other words, by setting r; c/(h- e - I²)), we induce i to exert effort for any strategy profile s E S_i. making it the dominant strategy for to exert effort. Thus, setting ry > c/(h- 1n-1- 1n)) for any agent i is dominant strategy scheme.
In contrast, when i assumes all other agents would exert effort (m = n - 1), the threshold reward r; given the above function (m) is:
T; > c/(h" 11
Setting the above reward r; c/(h" -(-h"~~~---- 1) for all agents makes it a Nash equilibrium to exert effort; when agent assumes that all other agents exert effort, it assumes that m = n - 1. and given its own reward rę it would rather exert effort than not; thus, when all agent are exerting effort, no agent has an incentive to unilaterally deviate and stop exerting effort. Setting r; > c/(h" f1" h="1.1) therefore Nash reward scheme.
We now consider constructing a reward scheme based on iterated dominance. Given the discussion above, if r1 > c/hh=1 h=-1, 1), agent 1 would exert effort if they assume all the remaining m - 1 do not exert effort. As the threshold reward rı (m) to induce agent 1 to exert effort when they assume exactly ma other agents would exert effort is diminishing in m. this means that when setting ri > c/(h--1 -- -7) makes exerting effort dominant strategy for agent 1. We can now turn to agent 2. First, observe that if 71 > c/(h"
h- l), agent can climinate not exerting effort as strategy for agent 1. When agent 2 assumees agent would exert effort, they rule out the value m = 0 (when at least one other agent exerts effort, the number m of other agents exerting effort has to be at least m 1). As agent 2 can assume least agent (agent 1) would exert effort, can set r2 > c/(h2. _ h 1 and under iterated elimination of dominated strategies, agent 2 would exert effort. Following the same argument for agents 3, 4.... n, we can construct an iterated dominance reward scheme by setting:
r; > c/(h pn-m-1
nm (n-m)
The discussion above shows that the only action profile surviving iterated elimination of strictly dominated strategies being exerting effort. Note that this scheme means that each agent gets different reward, despite the symmetry in task success probabilities.
As we note in the main text, the total amount spent by the principal depends on the reward scheme used. Our simulations were based on an environment with five agents, an effort exertion cost of = 10, and task success probabilities / = 0.1 and / 0.8. As discussed above, the Nash scheme requires setting ri > c/(h" hn-1 1 1) for all agents, so under these parameters r; = 35 + e is a Nash scheme, which is a very low total payment to the principal. However, empirical analysis revealed that MARL does not converge to the desired outcome of exerting effort, but rather on not exerting effort.
13

---

Under review as a conference paper at ICLR 2020
In contrast, setting r; > c/(h- 10-1 -1") for all agents is dominant strategy scheme, under the above parameters, setting 7; = 142, 857 + for all agents results in a exerting effort being a dominant strategy. This dominant strategy implementation is much more costly to the principal, but agents guaranteed to converge to exert effort (as under this payment scheme, it is a dominant strategy to do so).
An iterated dominance scheme is far less costly than the dominant strategy scheme. As discussed above, in an iterated dominance scheme, agents are promised different rewards, as r; > c/ (hm+1. pn-m-1 - hm p=-m), ). For the settings above, the scheme offers rewards of r = (ri, : Tb) (142, 857 + e, 17858 + e, 2233 + c, 280 + c, + e). While this is far cheaper than the dominant strategy scheme, our theoretical results show that independent MARL would converge to all agents exerting effort.
The main text of the paper shows the empirical results for the above parameters, showing that MARL converges to the desired outcome of all agents exerting effort under the iterated dominance scheme, as well as the dominant scheme, but that agents end up exerting no effort under the Nash scheme.
6.2 THREE EFFORT LEVELS
So far we considered the case where every agent had two strategies: exert effort, or not exert effort. Exerting no effort had zero cost, while exerting effort had a cost e = 10. we now consider the case where there is an intermediate effort level. whose cost to the agent is cæ where 0 < Cd < c (for instance Cj 6), and which results in intermediate probability d for success in the relevant task, so 1 = 0.1 < d < h = 0.8 (for instance, d = 0.4).
In particular, we note that results int the main paper MARL converging to the iterated dominance solution under REINFORCE relate to games with at most two actions per agent, and thus do not hold for this case: for domains with more than two actions, we only proved convergence is guaranteed under the the importnace weighted version of MC policy improvement CeaeeeeentttMMMMe (IW-MCPI). We now analyze this setting empirically.
As before, to make exerting high effort a Nash equilibrium, we require the expected reward when exerting high effort to be higher than not exerting effort (assuming other agents are all exerting high
effort): hrr - e > -r-1(r or equivalently r カーー However, we also have the additional
condition that exerting high effort is preferable to exerting medium effort: h"T h²- dr Ca or equivalently:
Cd
h
h
Similarly, when assuming exactly m of the other agents would exert high effort, an agent would rather exert high effort than not exerting any effort when I'm > c/(h++1, -r--m-1 hmmh _?==m) (we call this condition D). Using similar arguments, when assuming exactly m of the other agents would exert high effort, agent would rather exert high effort than exerting medium effort when mm > hmjp-- (h (we refer to this condition IT). Both condition I and condition II place requirement for the m 'tt agent in an iterated dominance solution. Whether condition I is more demanding than condition II vice versa depends on the domain parameters h, d, C, ct. We note that for the setting discussed above where Cu = 6 and d' = 0.4 (and the remaining parameters of = 0.1, = 0.8, c = 10 as before), the more demanding condition condition so the earlier iterated dominance reward (142, 857 + c. 17858 + 2233 280 + c, 35 + c) also applies in this settings, making the strategy profile where all agents exert high effort the iterated dominance solution. Also, similarly to before, setting 35 + for all agents (for < 240) makes exerting high effort a Nash equilibrium, and setting r > 142, 857 + e for all agents makes exerting high effort dominant strategy for all agents.
e-64
the reward
scheme of r (r1, . rs))
Figure 6 and g show the proportion of time that agents exert high effort over training time in the 3 effort level case (similar the figures in the main paper regarding the two action case). The results here are very similar to the two action domain: agents converge on exerting effort in both the dominant strategy scheme and iterated dominance scheme, but not in the Nash scheme.
We again emphasize that, as opposed to the two action case, our theoretical results do not guarantee convergence in this setting for REINFORCE. However, given these encouraging empirical results,
14

---

Under review as a conference paper at ICLR 2020
0.9
Eadiin 203
Epsiin 220
0.0
6.7
Potten
0.5
0.4
310
213
323
200
250
50
103
150
200
250
Tarnip Inntion130
Thining tentartt33
Training Eoration
Figure 6: Nash scheme
Figure 7: Dominant scheme
Figure 8: Iterated Dominance scheme
conjecture that MARL converges to iterated dominance solutions under less restrictive conditions than those used to prove theoretical results (i.e. for less demanding algorithms, for REINFORCE or other known simple RL algorithms in less restricted classes of games).
6.2.1 JOINT PROJECTS WITH ALLOWED TASK FAILURES
So far we have focused on the restricted case where the entire joint project successful only if all the tasks are successful. We now consider the case where there is some redundancy between tasks, so the project may succeed even if some tasks fail. Specifically, we examine the setting where the project succeeds if at most one task fails. In the case of n = 5 tasks, this means we model the project as successful if at least n - = tasks succeed. We still use the same parameters as before: a cost 10 for exerting effort, and a success probability of / 0.1 for task when the relevant agent exerts no effort and h = 0.8 when the relevant agent does exert effort.
We note that the computation of the Nash, dominant strategy and iterated dominance schemes become slightly more elaborate in this case. We briefly discuss computing reward schemes for this case. An agent takes into account the probability of the overall project succeeding when they exert effort and when they do not. When the agent assumes exactly m other agents would exert effort, the probability of the project succeeding assuming they do exert effort is:
p(e, m)
(m- +h-h"
+hm (1-h)-h (0 --
Similarly, if the agent does not exert effort, and exactly of the other agents exert effort, the probability of the project succeeding is: p(s, m) (1-t)-h"" "aaimmm.mmmmm-----m +1-h" "a---mp------pp-
(1-
The above calculations based the following possibilities leading to the overall project succeed- ing: the event where the agent's task failed but all the other tasks succeeded, the event where all the tasks (the agent's and the other agents' tasks) succeeded, the case where the agent's task succeeded and the only failure was in task where the other relevant agent was exerting high effort, and the case where the agent's task succeeded and the only failure in a task where the other relevant agent was exerting no effort.
Similarly to the reward scheme computation discussed in the main text, we can compute three reward schemes for this setting. For a dominant strategy scheme we set r; c/ (p(e, 0) p(s, 0)) + e for all
agents, for a Nash scheme we set r; cp(pee, 1) p(s, n 1)) + c for all agents, and for an iterated dominance scheme, we set the reward of agent i to be = c/ (p(e, i - 1) - p(s,
1)) + c. Under our parameters, the dominant strategy scheme is thus r; = 3968. 25 + e, the Nash scheme = 35 + and the iterated dominance scheme is (r1,72, r5) = (3968.25 25 + e, 655.30 1...6066540 + e, 28.62 + e, 35 <).
We now present figures of agent effort (proportion of selecting the high effort action) over training times for this setting, under the three reward schemes. As the overall scale rewards much lower than in the setting where all tasks must succeed, we used smaller values of c.
Figures 10 and I are similar to those for the previous settings: MARL under the Nash scheme fails to converge to exerting effort, but does converge to the desired outcome under both the expensive dominant strategy scheme and the far cheaper iterated dominance scheme. These results show some robustness of our results to the technology function used for the joint project principal agent domains.
15

---

Under review as a conference paper at ICLR 2020
24
10-
0.0
0.8
0.6
Eodas: 20
Resterc 40
Eodln::
0.4
0.3
nrng tr
300
200
Thiing
180
150
320
Training Iteration
100
1.5
200
Figure 9: Nash scheme
Figure 10: Dominant scheme Figure 11: Iterated Dominance scheme
6.3 MARL MARKOV GAMES (ENVIRONMENTS WITH MULTIPLE TIMESTEPS
Our analysis in the main paper has focused on normal-form games. However, many environments relate to temporally extended interaction between agents. A key model for such repeated multi-agent interaction across multiple timesteps that of Markov games (Shapley 1953 Littman 1994). In Markov games, in each state agents take actions (possibly based only partial observations of the true world state), and each agent obtaining an individual reward. One prominent method for applying multi-agent learning in such settings is that of independent MARL, where agents each learn a behavior policy through their individual experiences interacting with one another in the environment.
Formally, one may consider an n-player Markov game M (Shapley) 1953 Littman 1994) defined on a finite state set S. An observation function O S x [l....,
R gives each agent's action from the state changes,
d-dimensional restricted view of the state space. On any state, each agent a
: A (one per agent). Given the joint action at . E AA' . A following a transition function T S X AA ..... AN + A(S) (this allows for stochastic transition, and we denote the set of probability distributions over S as (SS). By O' = {or E S,0' 0(s, i)} we denote the observation space of agent i. Each agent gets an individual reward : x A' x x... x A + RR.
Each agent has its own experience in the environment, and independently learns policy x² Oi A (AA') (denoted (aa lot)) given its own observation o² = =O(s, i) and reward r'(s, at ... a D). We ,....; x ()) Every
use the notation ū = (a!.... ........")), aa 0= (o'..... o and #(-lō) = (7 (-(o))))) (.lo")....,
agent attempts to maximize its long term y-discounted utility:
(50) = E
(st, Te) 8141 T(s,, a.)
(4)
In a Markov game, we denote the set of all possible (deterministic) policies that agent i can use as IT relating the set of all possible functions nt' O² A(At).
Our definition for a strategy 8a strictly dominating strategy Sy relates to the strategy 8, yielding agent a higher utility than sy no matter what the other agents do. This definition relates to normal form game, rather than the more general Markov game setting. However, this definition, as well as the iterated dominance solution concept, can easily be adapted to apply to Markov games. Given Markov game setting we identify the set S; of strategies available to each agent as the set II, of all policies agent i has in the Markov game, and identify the payoff for agent in the game under the policies मे Mi,, ... kn)) with the expected long term 7 discounted utility, so (T) = V (so).
Then, under the standard definition of strategy domination, we say policy T II, strictly dominates policy xy II, if for any joint policy the other agents may use Th the policy T.. achieves higher utility than Ty. so that for any x E 11,, we have (T (50) > (( Hence the
definition of iterated dominance can be used the setting of Markov games as well.
Note that the above definition considers deterministic policies, yielding finite set of strategies. While many RI. algorithms use stochastic policies, when agent i is responding fixed policies of other agents, the optimal policy is deterministic one.
16

---

Under review as a conference paper at ICLR 2020
24.
10.
Spalor: 180
0.9
Epsiion 209
Eprion: 229
0.8
Epation:
Porten
0.6
0.4
0.5
Thx to tratiovtt3
300
400
280
Thaingg
200
320
100
Training Iteratio
210
302
400
500
603
Figure 12: Nash schemefigure 13: Dominant scheme Figure 14: Iterated Dominance scheme
Opt-in Proportion
Opt-in proportion
Opt-in proportion
To demonstrate the how our work applies to a Markov game setting, we consider an environment similar to the principal-agent joint project setting discussed in the main text, but with multiple time-steps.
Each episode in our environment has two time-steps. In the first step, each agent has decide whether they want to participate in the project, and has two actions: opt-in and opt-out. If even one agent opts-out, all agents incur penalty p (negative reward). all agents opt-in, we proceed to the second time-step, in which agents make decisions about their effort level, exactly given in the original game discussed in Section 4 Agents can either exert effort or not, with cost c 10 for exerting effort, with a probability of h = 0.8 for a task succeeding under high effort and a probability I = 0.1 for it succeeding under no effort (and with the project only succeeding when tasks succeed). We examine the same reward schemes given in Table T (Nash scheme, Dominant Scheme and Iterated Dominance Scheme).
We note that by setting the opt-out penalty to 15 (i.e. opting out gives reward of -15), any policy which opts out in the first step is dominated by any policy that opts-in during the first step the worst possible outcome for agent which opted-in is exerting effort and having the project fail, and even that givens a reward -10, which better than opting out. Hence, in this case, under the iterated dominance payment scheme of Table [ we get dominance solvable game where all agents opt-in and exert high effort. In contrast, under the Nash scheme of Table [ one Nash equilibrium is having all agents opt-in but exerting effort.
We now provide the simulation results for this setting, similarly to Figure to Figure 5
Figure 12 Figure [3 and Figure 14 show the proportion of agents who opt-in during the first timestep under the Nash, Dominant and Iterated Dominance rewrd schemes, respectively. The figures show that under all reward schemes, agents quickly learn to opt-in during the first timestep. This unsurprising. due to the high opt-out penalty.
Figure 15 Figure and Figure 17 show the proportion of agents who choose to exert effort during the second timestep under the Nash, Dominant and Iterated Dominance reward schemes, respectively, The figures show results similar those obtained for the single timestep environment. Under the Nash scheme, all agents quickly learn not to exert effort. In contrast, under both the Dominant and Iterated Dominance schemes, all agents learn to exert effort during the second timestep (though the principal's 's payments are vastly different). In this case, agents learn to avoid the dominated policies starting with opting out, then learn to exert effort once they have opted-in.
For completeness, Figure 18 shows the proportion of high effort actions during the second timestep. and Figure 19 shows the the mean agent reward over training. Both figures show similar behavior to that in the single timestep environment.
The figures and discussion above show how our results relate to Markov games with multiple timesteps. In settings where one identify domination sequence policies describing agent behavior in temporally extended environments, agents would likely follow the elimination sequence policies, converging to iterated dominance solution, if one exists.
17

---

Under review as a conference paper at ICLR 2020
24
10-
Spaloo: 380
0.0
Epsion: 209
Epsion:
0.8
0.6
0.5
320
nrn 2005
500
280
Thaingg
200
320
100
Training
210
302
400
500
Figure 15: Nash schemefigure 16: Dominant scheme Figure 17: Iterated Dominance scheme
High effort proportion
High effort proportion
High effort proportion
Epdion 320
0.2
Agent 3
12000
14000
Easeione 360
Epalion: 360
Agent 4
0.7
Epdiaon 220
or
0.6
0000
40.00
2000
0.4
100
200
300
530
100
500
502
Traiiing Meration x100
Training itor Loraationo x1.00
Figure 18: Individual agent effort (Iterated Dominance) Figure 19: Rewards (Iterated Dominance)
7 CONVERGENCE RATES FOR IW-MCPI
Theorem 3.4
provides asymptotic result showing that in the limit of infinite data IW-MCPI almost surely converges
iterated elimination solution. The speed of convergence game-dependent. The important factor is the degree to which dominated actions are suboptimal, which is captured by the g in the proof of Theorem 3.4.
Suppose now that all dominated actions least e-suboptimal. To derive rate of convergence need to make each the arguments in (2) and (3) finite-time. Suppose that e, = -P for p E (0, 1).
Then by the proof of Theorem 3.3 the estimation error about the rewards is after rounds is
Ö(VE!+P)
Using the fact that g 2 by assumption follows from that T2 - T1 = O(e 22/(1p)() Since the proof is iterated over Ei=1 |S;| actions, the number of rounds before all IW-MPPI strategies play iterated elimination solution with high probability
S
Σ
2/(1
By high probability here, we mean with probability that is no more than constant times the amount of forced exploration é,, which by assumption decays with Ot- For example, when p = 1/2, the joint strategy of the algorithms will be iterated elimination solution with probability least
1 1(2-1/2) once
S.S et
1= Ω
CONVERGENCE ISSUES FOR REINFORCE WITH MORE THAN TWO ACTIONS
Here we argue that convergence of REINFORCE is not obvious when the number actions is larger than two.
18

---

Under review as a conference paper at ICLR 2020
The key observation is that the gradient update does not always guarantee that scores of dominated actions decrease relative to non-dominated actions. To see this, consider the case where the first player has three actions S₁ (1, Then the expected REINFORCE update when the opponents are playing strategy is
I 3nt (VV..")).) Iz, + apz, (a) -P,,T"
(5)
Suppose that a = is dominated. Our goal is to prove there exists an a' such that almost surely,
lim 2t,a 10000
F1,1 = 00.
Assume for a moment that there are just two actions. Then by the definition of dominance rf S <r2 and can easily from the gradient calculation in (5) that 14+1,1 is decreasing in expectation and 1,2 is increasing, which leads to the desired behaviour. Unfortunately this is no longer true when there are more than two actions. It is still true that r - Pzz r is negative, but the gradient can be negative for other actions well. Furthermore, the scaling by pz, (a) means that once ps, (1) is small, if action a 2 is also suboptimal, then
Ps. (2) pr,r") Pz. (1)69 - - pI,T²)
is possible and proving a separation between Tt,1 and Zt,a for some a > 1 is apparently non-tri -riviiivill.
As example of this, consider the case of player having 3 actions, where the reward from these actions depends on the action choice of player 2. with the rewards being م = (0, 0.5, 1) (respectively for the player I's actions) when player 2 takes the first action or being /² (0, 0.5, 0.1) when player 2 takes the other action. In other words, in this case the first action is always dominated for the player but depending on player 2's action, the optimal action for player 1 may be either its second third action.
We show that performing the REINFORCE update for player always reduces the logit of the first action. However, for some action logits, the update on nd increases the logit of action and decreases that of action 2. where the decrease in the logit of action is larger than the decrease in the logit of the dominated action 1. Similarly, the update on n increases the logit of action 2 and decreases that of action 3, where the decrease in the logit of action is larger than the decrease the logit of the dominated action 1.
More formally, consider the case of action logits of x (0,1,5), and Th (0, 0.5, 1). Then
L x (-0.0065, -0.0087, 0.0151),
which means the scores of actions and are getting closer.
Now consider the case where the other player takes a different action, so we have , = 0.1.).
so
J (-0.0007, 0.00703, -0.00631),
so that now the scores of actions and 3 are getting closer.
Although could not find con-connereence results, note that by oscillating between the two updates, one can keep all the action logits quite close together (and in particular, the probability of taking the dominate action monotinically decreasing).
COMPARISON OF OUR RESULTS AND EXISTING RESULTS ON THE CONVERGENCE OF OTHER ALGORRITMMS TO THE ITERATED DOMINANCE SOLUTION
Our theoretical results study the convergence of REINFORCE and version of importance weighted Monte-Carlo Policy Improvement to the iterated dominance solution in strict dominance solvable games. Iterated dominance is key solution concept in game theory, and some earlier work has considered the convergence of other algorithms to the iterated dominance solution.
Earlier work has also shown polynomial algorithm for computing the strict iterated dominance solution in dominance solvable games, but has shown that doing so for weak sterated-dominance is an hard problem (Conitzer & Sandholm, 2005).
19

---

Under review as a conference paper at ICLR 2020
One algorithm that has been studied in relation to dominance solvable games is Fictitious Play (Brown 1951). Fictitious Play is an iterative process designed to compute Nash equilibria, in which each player assumes the opponents are playing stationary mixed strategies. In every step, each player selects the best response to the historical empirical frequency of strategies played by their opponents. Though designed to compute Nash equilibrium, Fictitious Play only converges
Nash equilibrium in restricted classes of games, most notably two-player zero-sum games with a finite number of strategies (Robinson 195T). Fictitious play has been shown to converge to strict iterated dominance solution in dominance solvable games Naachbar 1990) (see various evolutionary game theory textbooks for a detailed discussion (Fudenberg al. 1998; Weibull [997))
Another evolutionary game theory dynamics that has been studied in relation to iterated dominance the Replicator Dynamics (Taylor & Jonker 1978 Schuster & Sigmund, 1983 Weibull 1997). model of the evolution of strategies in a population of agents participating in game, captured by a differential equation called the replicator equation. this model the relative frequencies of a strategy in population evolve over time. In each period strategies are randomly matched against other players from the population based on the current frequencies, and the expected payoff (fitness) a strategy achieves determines its rate of reproduction (yielding the frequencies of strategies in the next step). The replicator dynamics also converges to a strict iterated dominance solution in dominance solvable games (Fudenberg al. 1998 Bowling 2000).
The above results on Fictitious Play and the Replicator Dynamics indicate that some adaptive procedures identify a strict iterated dominance solution in dominance solvable games. However, convergence results on one type of algorithm may not apply to other types of algorithms. In other words, though different RL algorithms may sometimes converge the same outcome (if they converge at all), this is certainly not an automatic guarantee. Hence, our results are not subsumed by earlier work. Further, there are inherent differences between Fictitious Play and the Replicator Dynamics and the RL algorithms we study, which may lead to different convergence behavior.
Our motivation is not to compute the iterated dominance solution, as there are already good algorithms for doing so (Conitzer & Sandholm, (005).. Rather, we want to study how commonly used RL algorithms behave dominance solvable games. We focused on policy gradient methods as these lie at the heart of many popular agents, and on policy iteration as it is among the simplest and most basic methods.
As opposed to policy gradient methods like REINFORCE, Fictitious Play does not rely computing gradients, but rather on repeatedly finding the best response to the empirical distribution of actions taken by the opponents system from policy gradient methods; The Replicator Dynamics is regret minimizing approach which is known to have significant differences with policy gradient methods (Omidshafiei et al. 2019 Mertikopoulos et al. 2018). While we conjecture that other RL methods may also converge to an iterated dominance solution, there may not be an obvious way to extend such convergence results from one RL algorithm to another, making it an interesting open problem to identify RL algorithms that provably converge to iterated dominance solutions.
far. Similarly, the Replicator Dynamics remains a different dynamical
20


Reviews:
[{"review_id": "SyxMP-S9tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 work studies learning under independent MARL, and shows theoretically and experimentally that two independent MARL algorithms converge for games that can be solved by iterated dominance.\n\nThis work is clear and well-written, but I do not understand what the contribution of this work is to the literature. The fact that standard MARL learning rules (e.g. independent Q learning) converge in games with iterated dominance solutions is a very well-known result in Learning in Games (see [1], [2]). The authors examined slightly different learning rules (REINFORCE and MCPI), but I would expect that almost any reasonable learning rule would converge in iterated-dominance-solvable games; if anything, it would be surprising if this were *not* the case. The applications of the convergence result result to \"noisy effort\" games is pretty standard and the results expected based on the theory.\n\nQuestion to the authors:\n- How does this work differ from the known results about convergence of naive learners in iterated-dominance-solvable games?\n\n[1] Michael Bowling, \"Convergence Problems of General-Sum Multiagent Reinforcement Learning\", Sec. 5.2\n[2] Fudenberg & Levine, 1999", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "HJeqKrkBcS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 studies independent multi-agent reinforcement learning (MARL) in dominance solvable games. The main contribution of this paper is that the authors have proved the convergence to the iterated dominance solution for two RL algorithms: REINFORCE (Section 3.1, binary action case only) and Importance Weighted Monte-Carlo Policy Improvement (IW-MCPI, Section 3.2). Empirical analysis for principal-agent games is demonstrated in Section 4.\n\nThe paper is interesting in general, however, I do not think this paper has quite met the (very high) standard of ICLR, due to the following limitations:\n\n1) As the authors have mentioned, the dominance solvable games are quite limited.\n\n2) This paper only has *convergence* results, but does not have *convergence rate* results. In other words, the authors have not proved how fast the agents converge to the iterated dominance solution. Might the authors establish a convergence rate result such as a regret bound?\n\n3) This paper assumes an unrealistic setting in which when one agent learns, the strategies (policies) of all the other agents are fixed. In other words, the agents learn in a round-robin fashion, rather than learn simultaneously. I do not think this setting is realistic in most practical problems.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1x2QH4-cB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The main idea of this paper is to solve multi-agent reinforcement learning problem in dominance solvable games. The paper reviewed general multi-agent reinforcement learning and general norm-form game in game theory. The authors aim to recover multi-agent policies through independent MARL in norm-form dominance-solvable games. The paper states that one of solution concepts of dominance-solvable games is iterated dominance solution, which is different from Nash Equilibrium and may be more suitable under certain scenarios. Furthermore, the paper considers two common RL methods for control and learning policy: REINFORCE and Monte-Carlo policy iteration. The main contribution of the paper is to prove that both REINFORCE in binary action case and Monte-Carlo algorithms find the agents’ policies converging to the iterated dominance solution. The interesting aspect of this paper is that iterated dominance solution based reward scheme can guarantee convergence to the desired agents policies at a cheaper cost in practical principal-agent problems. In appendix, the paper extended its conclusion to Markov games and three possible action cases. To the current status of the paper, I have a few concerns below.\n\n1.\tIt takes too much space for preliminary work and basic concepts, in Sec 1.1 (preliminary) and Sec 2 (MA-RL and Dominance-Solvable Games).\n2.\tThe notations are inconsistent and unnecessarily complicated. For example, for agent i “its possible actions are the strategies in S_i” (section 2); any action “a \\in S_i” (section 2,1); for agent i “for all s_i \\in S_l” (Algorithm 1 line 2). It can be consistent to use the same notation to describe the same term. Moreover, “a score per action, x_1, …, x_{m_i}” and “each agent starts with initial logits for x_1, …, x_n”. Formally, the corner mark in the same location should represent the uniform meaning. \n3.\tTypos: lemma 3.1 proof “g = … (r_{s_h}-r_{s_h})” should be “g = … (r_{s_h}-r_{s_l})”; above section 3.2 “our proof of Theorem 3.1”, should be “Lemma 3.1”.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1luZksD9r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 studies reinforcement learning algorithms in a specific subset of multi-agent environments that are 'dominance solvable'. This means that, given an initial set of strategies in the game, if we iteratively remove 'dominated strategies' (those whose utility is strictly less than another strategy independent of the strategies used by other agents), then only one strategy remains for each player. The remaining strategy is called the iterated dominance solution. The paper proves the convergence of certain RL algorithms (REINFORCE in the 2-action case, and importance weighted monte-carlo policy iteration in the multi-action case) for normal-form games. The paper demonstrates the utility of this via mechanism design: in a principal-agent problem where one can design the rewarding scheme given by a 'principal agent' to various (RL) sub-agents, rewarding schemes motivated by iterated dominance guarantees the best solution for the principal agent, whereas schemes motivated by Nash equilibria do not. \n\nThe paper is quite well-written and understandable. To my knowledge, the idea is novel and has not yet been explored in the RL literature (UPDATE: based on Reviewer #1's review, this may not be the case. I'll wait to hear the author response to this). I did not check the proofs thoroughly. However, the experiments in the principal-agent problem make sense, and it's interesting to see that iterated dominance reward schemes results in good performance for the principal agent. I appreciate that, while the main results in the paper are limited to normal-form games (which are quite restricted), there are empirical results in the appendix showing the extension to Markov games with multiple timesteps, suggesting that the applicability of iterated dominance reward schemes extend beyond the simple two-action case, where no temporally extended decisions need to be made. Even so, the Markov game considered is fairly simplistic. \n\nMy personal curiosity about this paper revolves around scaling to real-world applications. This is not really discussed in the paper; the conclusion talks about directions for future work, for example expanding the number of RL algorithms where convergence can be proven, or producing complexity bounds for convergence. What I want to know is: what sorts of games can we compute the iterated dominance reward schemes for? How can this be applied when the space of policies becomes too large to be enumerated (and thus determining whether a policy is strictly dominated becomes impossible)? I don't expect this paper to solve these issues, but it would be nice to have a discussion of them. \n\nOverall, I'd say this paper is interesting to the multi-agent RL community and I could imagine others building off of this work, so I err on the side of acceptance. \n\n\nSmall fixes:\n- Our proof of Theorem 3.1 -> Theorem 3.2\n- I'd recommend extending the captions of figures 6-8 and 9-11 in the Appendix. \n- Close bracket in Section 6.3 title", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proofs that reinforcement learning (using two different algorithms) converge to iterative dominance solutions for a class of multi-player games (dominance solvable games). 

There was a lively discussion around the paper. However, two of the reviewers remain unconvinced of the novelty of the approach,  pointing to [1] and [2], with [1] only pertaining to supermodular games. The exact contribution over such existing results is currently not addressed in the manuscript.  There were also concerns about the scaling and applicability of the results, as dominance solvable games are limited. 

[1] http://www.parisschoolofeconomics.eu/docs/guesnerie-roger/milgromroberts90.pdf
[2] Friedman, James W., and Claudio Mezzetti. "Learning in games by random sampling." Journal of Economic Theory 98.1 (2001): 55-84.
Decision: Reject