D3C: Reducing the Price of Anarchy in Multi-Agent Learning
Authors: Ian Gemp
Kevin McKee
Richard Everett
Edgar Alfredo Duenez-Guzman
Yoram Bachrach
David Balduzzi
Andrea Tacchetti
Venue:  (2021)
Keywords: multiagent
social dilemma
reinforcement learning

Abstract: Even in simple multi-agent systems, fixed incentives can lead to outcomes that are poor for the group and each individual agent. We propose a method, D3C, for online adjustment of agent incentives that reduces the loss incurred at a Nash equilibrium. Agents adjust their incentives by learning to mix their incentive with that of other agents, until a compromise is reached in a distributed fashion. We show that D3C improves outcomes for each agent and the group as a whole in several social dilemmas including a traffic network with Braess’s paradox, a prisoner’s dilemma, and several reinforcement learning domains.

Under review as a conference paper at ICLR 2021
D3C: REDUCING THE PRICE OF ANARCHY IN MULTI-AGENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Even in simple multi-agent systems, fixed incentives can lead to outcomes that are poor for the group and each individual agent. We propose method, D3C, for online adjustment of agent incentives that reduces the loss incurred at a Nash equilibrium. Agents adjust their incentives by learning to mix their incentive with that of other agents, until a compromise is reached We show that D3C improves outcomes for each agent and the group whole on several social dilemmas including traffic network with Braess's 's paradox, a prisoner's dilemma, and several reinforcement learning domains.
distributed fashion.
INTRODUCTION
We consider a setting composed of multiple interacting artificially intelligent agents. These agents will be instantiated by humans, corporations, or machines with specific individual incentives. However, it is well known that the interactions between individual agent goals can lead to inefficiencies at the group level, for example, in environments exhibiting social dilemmas (Braess 1968 Hardın 1968 Leibo et al. 2017). In order to resolve these inefficiencies, agents must reach a compromise.
Any arbitration mechanism that leverages central coordinator faces challenges when attempting to scale to large populations. The coordinator's ' task becomes intractable as it must both query preferences from a larger population and make decision accounting for the exponential growth of agent interactions. If agents or their designers are permitted to modify their incentives over time, the principal must collect all this information again, exacerbating the computational burden. A central coordinator represents single point of failure for the system whereas one motivation for multi-agent systems research inspired by nature (e.g.. humans, ants, the body, etc.) robustness to node failures (Edelman and Gally, 2001). Therefore, we focus on decentralized approaches.
trivial form of decentralized compromise is to require every agent minimize group loss (max- imize welfare). Leaving the optimization problem aside, this removes inefficiency, but similar to a mechanism with a central coordinator, requires communicating all goals between all agents, an expensive step and one with real consequences for existing distributed systems like wireless sensor networks (Kulkarni et al, 2010) where transmitting a signal saps a node's 's energy budget. There is also the obvious issue that this compromise may not appeal to individual agent, especially one that is expected to trade its low-loss state for a higher average group loss. One additional, more subtle consequence of optimizing group loss is that it cannot distinguish between behaviors in environments with group loss that is constant sum, for instance, in zero-sum games. But zero-sum games have rich structure which we would like agents respond. Electing a team leader (or voting on decision) implies one candidate (decision) wins while another loses. Imagine two agents differ on their binary preference with each trying to minimize their probability of losing. A group loss is indifferent; we prefer the agents play the game (and in this, case argue their points).
Design Criteria:
We seek an approach to compromise in multi-agent systems that applies to the setting just described. The celebrated
theorem [Arrow] 1970 Satterthwaite 1975, Green and Laftont 1977; Myerson and Satterthwaite 1983) states that no mechanism exists that simultancously achieves optimal efficiency (welfare-maxet maximizini behavior),
saddet-bbllnce (no taxing agents and burning side-paymen manepaammnns), appeals to rational individuals (individuals want to opt-in to the mechanism), and is incentive compatible (resulting behavior is Nash equilibrium). Given
For example, the VCG mechanism Clarke 1971

---

Under review as a conference paper at ICLR 2021
this impossibility result, aim to design mechanism that approximates weaker notions of these criteria. In addition, the mechanism should be decentralized, extensible to large populations, and adapt to learning agents with evolving incentives in possibly non-stationary environments.
Design: We formulate compromise as agents mixing their incentives with others. In other words, an agent may become incentivized to minimize mixture of their loss and other agents' losses. We design a decentralized meta-algorithm to search over the space of these possible mixtures.
We model the problem of efficiency using price of anarchy. The price of anarchy, P E 20, is measure of inefficiency from algorithmic game theory with lower values indicating more efficient games (Nisan al., 2.07). Forcing agents to minimize a group (average) loss with single local minimum results in "game" with p = 1. Note that any optimal group loss solution is also Pareto- efficient. Computing the price of anarchy of a game is intractable in general. Instead, we derive differentiable upper bound on the price of anarchy that agents can optimize incrementally over time. Differentiability of the bound makes easy to pair the proposed mechanism with, for example, deep learning agents that optimize via gradient descent (Lerer and Peysakhovich 2017 [penAl et al.) 2019). Budget balance is achieved exactly by placing constraints on the allowable mixtures losses. We appeal to individual rationality in three ways. One, we initialize all agents to optimize only their own losses. Two, we include penalties for agents that deviate from this state and mix their losses with others. Three, we show empirically on several domains that opting into the proposed mechanism results in better individual outcomes. We also provide specific, alheit narrow, conditions under which agents may achieve Nash equilibrium, i.e. the mechanism is incentive compatible, and demonstrate the agents achieving a Nash equilibrium under our proposed mechanism in a traffic network problem.
The approach we propose divides the loss mixture coefficients among the agents to be learned individually; critically, the agents do not need to observe or directly differentiate with respect to the other agent strategies. In this work. we do not tackle the challenge of scaling communication of incentives to very large populations; we leave this to future work. Under our approach, scale can be achieved through randomly sharing incentives according to the learned mixture weights or sparse
optimization over the simplex (Pilanci et al. 2012, Kyrillidis et al. 2013) Li et al. 2016
We propose a differentiable, local estimator of game inefficiency, as measured by price of anarchy. We then present two instantiations of a single decentralized meta-algorithm, one 1st order (gradient-feedbace and one Oth order (bandit-feedback) that reduce this inefficiency. This meta-algorithm is general and can be applied to any group of individual agent learning algorithms.
Our Contribution:
This paper focuses on how to enable group of agents to respond to an unknown environment and minimize overall inefficiency. Agents with distinct losses may find their incentives well aligned to the given task, however, they may instead encounter a social dilemma (Sec. B. We also show that our approach leads to interesting behavior in scenarios where agents may need to sacrifice team reward to save an individual (Sec. F.4) or need to form parties and vote on a new team direction (Sec. 3.4). Ideally, one meta- algoritto would allow multi-agent system to perform sufficiently well in all these scenarios. The approach we propose, D3C (Sec. 2 is not that meta-algorithm, but it represents a holistic effort to combine critical ingredients that we hope takes a step in the right direction
DYNAMICALLY CHANGING THE GAME
In our approach, agents may consider slight re-definitions of their original losses, thereby changing the definition of the original game. Critically, this is done in way that conserves the original sum of losses (budget-balanced) so that the original group loss can still be measured. In this section, we derive our approach to minimizing the price of anarchy in several steps. First we formulate minimizing the price of anarchy via compromise as an optimization problem. Second we specifically consider compromise as the linear mixing of agent incentives. Next, we define a local price of anarchy and derive an upper bound that agents can differentiate. Then, we decompose this bound into a set of differentiable objectives, one for each agent. Finally, we develop gradient estimator to minimize the agent objectives in settings with bandit feedback (e.g.. RL) that enables scalable decentralization.
2D3C is agnostic to any action or strategy semanties. We are interested in rich environments where high level actions with semanties such as "cooperation" and "defection" are not casily extracted do not exist.
2

---

Under review as a conference paper at ICLR 2021
2.1 NOTATION AND TRANSFORMED LOSSES
Let agent i's loss be fi:):) x E X' + R where x: is the joint strategy of all agents. We denote the joint strategy iteration by æ. when considering discrete updates and x=()) when considering continuous time dynamics. Let (x) denote agent i's transformed loss which mixes losses among agents. Let f(x = (x) the number of agents. In general, require f/ > 0 and Σ. (x)
and fA(x) [f(())... (x))) (x)] where n E Z denotes fi(z) that total loss is conserved note that the agents are simply exploring the space of possible non-negative group loss decompositions. We consider transformations of the form f*(x) = A f(x) where each agent i controls row i of A with each row constrained to the simplex, i.e. A, E A A X denotes the set of Nash equilibria, [a; b] = [a] signifies row stacking of vectors.
2.2
PRICE OF ANARCHY
(007)) define price of anarchy as the worst value of an equilibrium divided by the best value in the game. Here, value means sum of player losses, best means lowest, and Nash is the cquilibrium. It is well known that Nash can be arbitrarily bad from both an individual agent and group perspective; Appendix presents simple example and demonstrates how opponent shaping is not a balm for these issues (Foerster et al. 2018 Letcher et al. 2018). With the above notation, the price of anarchy, p, is defined
Nisan et al.
Px (f der maxx. Ei minx (x)) 2 1.
Note that computing the price of anarchy precisely requires solving for both the optimal welfare and the worst case Nash equilibrium. We explain how we circumvent this issue with a local approximation
in 2.4
2.3
COMPROMISE AS AN OPTIMIZATION PROBLEM
Given game, want minimize the price of anarchy by perturbing the original agent losses:
min (=) 1''1
px(f)++DDD
(2)
where and = (a(f) denote the vectors of original and perturbed losses respectively, dia IR" + IR" is parameterized by weights A, v is a regularization hyperparameter, and DD penalizes deviation of the perturbed losses from the originals or represents constraints through indicator function. To ensure minimizing the price of anarchy of the perturbed game improves on the original, incorporate the constraint that the sum of perturbed losses equals the sum of original losses. We refer to this approach as p-minimization.
Our agents reconstruct their losses using the losses of all agents basis. For simplicity, consider linear transformations of their loss functions, although the theoretical bounds hereafter are independent of this simplification. We also restrict ourselves convex combinations so that agents do not learn incentives that are directly adverse to other agents. The problem can now be reformulated. Let (f) A f and D(f. fff.fl f') Σ, PKz(e, || As) where A R is right stochastic matrix (rows are non non-negatte negative and sum to 1), e; E R" is a unit vector with a at index i, and Dxi. denotes the Kullback- divergence. Note OpenAl Five (OpenAl al. 2019) also used a linear mixing approach where the "team spirit" mixture parameter (T) is manually annealed throughout training from 0.3 to 1.0 (i.c., AG = 1 - 0.8r, A.j 0.2T, *
The A matrix is interpretable and reveals the structure of "teams" that evolve and develop over training. In experiments we measure relative reward attention for each agent as In((n-1)Au)-in jæt Aja) to reveal how much agent attends to their own loss versus the other agents on average (e.g., Figure 4b). This number is 0 when A; = for all i.j. Positive values indicate agent mostly attends to its own loss. Negative values indicate agent i attends to others' losses more than its own. We also discuss the final A in the election example in $3.4
"The price of anarchy assumes positive losses. This is accounted for in 2.5 to allow for losses in R.
3

---

Under review as a conference paper at ICLR 2021
2.4 A LOCAL PRICE OF ANARCHY
The price of anarchy, 2 1, is defined over the joint strategy space of all players. Computing is intractable for general games. However, many agents learn via gradient-based training, and only observe the portion of the strategy space explored by their learning trajectory. Hence, we imbue our agents with the ability to locally estimate the price of anarchy along this trajectory. Definition (Local Price of Anarchy). Define
maxx: EE)A(=))
Pe At) JE E: ( -FF()) 21
(3)
where F(x)
(x))), [a)) At is small step size, f.A is assumed positive A and X² denotes the set of equilibria of the game when constrained to the line.
2V, ff))) (z);
V J
X
X p
X
1
X p
Figure I: Agents estimate the price of anarchy assuming the joint strategy space, X. of the game is restricted local linear region, Xy extending from the currently learned joint strategy, Tr, the next, Z4+1. and Pr denote the global and local price of anarchy.
To obtain bounds, we leverage theoretical results on smooth games, summarized as a class of games where "the externality imposed any one player by the others is bounded" (Roughgarden, 2015). We assume a Lipschitz property on all f:a (x) (details in Theorem 1. which allows us to appeal to this class of games. The bound in Eqn 4 is tight for some games. Proofs can be found in appendix D
Theorem (Local Utilitarian Price of Anarchy). Assuming each agent's loss is positive and its loss gradient is Lipschitz, there exists a learning rate At > O sufficiently small such that, to ( the local utilitarian price of anarchy of the game, Pa (f At), is upper bounded by
max(1 + AtRELU ( d (og(sA(x(t))) + ([,,,A())) fA(z))
(4)
dt
where indexes each agent, j is a user defined positive scalar, ReI.(=)) max (2, 0), and Lipschitz implies there exists Be such that ((zz,)A(x)) y. < 3:|1 yll Var, y,
Recall that this work focuses on price of anarchy defined using total loss as the value of the game. This is a utilitarian objective. We also derive an upper bound on the local egalitarian price anarchy where value is defined as the max loss over all agents (replace E, with max; in Eqn B see D.2)
2.5 DECENTRALIZED LEARNING OF THE LOSS MIXTURE MATRIX A
Minimizing Eqn 2 w.r.t. A can become intractable if n is large. Moreover, if solving for A at each central authority, the system vulnerable this authority failing, A
step the responsibility distributed solution is therefore appealing, and the local price of anarchy bound admits natural decomposition over agents. Equation becomes
min Pa + VDKI(e: As) A.A
where A = 1 AtReLU d di log(f/(((t))) + 11V (1=)))1()111 This objective is differentiable w.r.t.
(a))
each A, with gradient V.P & RA,RUL log(s/ (x(t))) + IIV (1=,)(())))))))) The log appears fA(m))
due to price of anarchy being defined as the worst case Nash total loss divided by the minimal total loss. We propose the following modified learning rule for hypothetical price of anarchy which is
Larger (less smooth loss) requires smaller At.
4

---

Under review as a conference paper at ICLR 2021
defined as a difference and accepts negative loss: A, A. 1I VA where 7/ is learning rate and
G (c)
A.P: = A. Retu
[e a hyperparameter.
(6)
The update direction in o is proportional to VA,P: asymptotically for large f/A see D.1.1 for further discussion. Each agent i updates V; and A, simultaneously using /f, and V Pi
Improve-Stay, Suffer-Shift-V V A:P: encodes the rule: if the loss is decreasing, maintain the mixing weights, otherwise, change them. This strategy applies Win-Stay, Lose-Shift (WSLS) (Robbins) 1952) to learning (derivatives) rather than outcomes (losses). WSLS was shown to outperform Tit-for- Tat in an iterated prisoner's dilemma (Nowak and Sigmund 1993 Imhof et al. 2007).
Note that the trival solution of minimizing average group loss coincides with A, = n for all i.j.
If the agent strategies converge to social optimum, this is fixed point in the augmented strategy
space (at, A). This can be seen by noting that 1) convergence to an optimum implies v.. = 0
and 2) convergence alone implies dfz 0 for all agents so VA; by Eqn 6 assuming = 0.
2.6 DECENTRALIZED LEARNING & EXTENDING TO REINFORCEMENT LEARNING
The time derivative each agent's 's loss, d (f((((()) in Eqn 6 requires differentiating through potentially all other agent loss functions, which precludes scaling large populations. In addition, this derivative is not always available as differentiable function. In order to estimate V Va, when only scalar estimates of Pr are available as in, e.g., reinforcement learning (RL), each agent perturbs their loss mixture and commits to this perturbation for a random number of training steps. If the loss increases over the trial, the agent updates their mixture in a direction opposite the perturbation. Otherwise, no update is performed.
Algorithm 2L, example learner
Algorithm D3C Update for RL Agent i
Input: À [A:::... A.)
Input: TJ., 8, V, Twins maxx AQ, e, I, h, LL, iterations T
while episode not terminal do
A; + A {Initialize Mixing Weights}
draw action from agent policy
[Draw Initial Random Mixing Trial]
play action and observe reward r; broadcast r; to all agents
A, ā. T, tb, Gb = trial(6, Tmin, Tmax: A4, 0, G?) G 0 {Initialize Mean Return of Trial]
update policy with r; E, AgTs
for t = 0: do
end while
g [A, v i) (Update Policy With Mixed Rewards)
Output: return over episode
AG, = [. L. (Elapsed Trial Steps]
G (G(A4, - 1) g) (Update Mean Return]
Algorithm trial helper function
if At, = (Trial Complete) then
A = ReLu( G--G + +) (Approximate p)
Input: d, Tmin. Tmax. A,, f, G
(Sample Perturbation Direction)
V A: = ~. ve, A, (Estimate Gradient
a. (n)
A. A = softmax/ [log(A,) VA. 1 {Update]
[Perturb Mixture]
{ Draw New Random Mixing Trial)
A softmax(log(AA) Sā,)
A, a, T, ts. G3 trial((, Tmin Tmax A,,t
( (Draw Random Trial Length)
end if
7 Uni fo rm (Tmin Tmax).
end for
Output: A,, a, T,
This is formally accomplished with approximate one-shot gradient estimates "Shale-SShwarze et al. 2012). one-shot gradient estimate of (A,,)) performed by first evaluating P: (log(A,) + da,) where 5 is a scalar and a; ~ (n) is drawn uniformly from the unit sphere in R". Then, an unbiased gradient is given by P: (log(A) + 5ā, ),; where A; E A In practice, we cannot dt (xx()) term that appears in the definition of pi. Instead, Algorithm 1 uses finite differences and we assume the evaluation remains accurate enough across training steps.
evaluate in one shot the d
Algorithm requires arguments: 7A is global learning rate for each AG, 8 is a perturbation scalar for the one-shot gradient estimate, Tmin and Tmaz specify the lower and upper bounds for the duration of the mixing trial for estimating finite difference of du (x)))))))) I and h specify lower and upper
5

---

Under review as a conference paper at ICLR 2021
bounds for clipping A in logit space (11-7),, and L, is a learning algorithm that takes A as input (in order to mix rewards) and outputs discounted return. ② indicates elementwise division.
2.7 ASSESSMENT
We assess Algorithm T with respect to original design criteria. As described, agents perform gradient descent on a decentralized and local upper bound on the price of anarchy. Recall that a minimal global price of anarchy (p 1) implies that even the worst case Nash equilibrium of the game is socially optimal; similarly, A searches searchee for a locally socially optimal equilibrium. By design, A, A ensures the approach is budget-balancing. We justify the agents learning weight vectors A; by initializing them to attend primarily to their own losses as in the original game. they can minimize their original loss, then they never shift attention according Equ O di because di < 0 for all They only shift A, if their loss increases. We also include a KL term to encourage the weights to return to their initial values. In addition, in our experiments with symmetric games, learning A helps the agents' outcomes in the long run. We also consider experiments in Appendix E.2.2 where only subset of agents opt into the mechanism. If each agent's 's original loss is convex with diagonally dominant Hessian and the strategy space is unconstrained, the unique, globally stable fixed point of the game defined with mixed losses is a Nash (see Appendix H.44. Exact gradients V, require each agent differentiates through all other agents losses precluding a fully decentralized and scalable algorithm. We circumvent this issue with noisy oneshot gradients. All that is needed in terms of centralization is to share the mixed scalar rewards; this is cheap compared to sharing x, IR.. As mentioned in the introduction, the cost of communicating rewards can be mitigated by learning A, via sparse optimization or sampling but is outside the scope of this paper.
EXPERIMENTS
Here, we show that agents minimizing local estimates of price of anarchy achieve lower loss on average than selfish, rational agents in three domains. Due to space, we leave two other domains to the appendix. In the first domain, a traffic network (4 players), players optimize using exact gradients (see Eqn 66) Then in two RL domains, Coins and Cleanup, players optimize with approximate gradients as handled by Algorithm I Agents train with deep networks and A2C (Espeholt et al.) 2018
We refer to both algorithms as D3C (decentralized, differentiable, dynamic compromise).
i. We initialize away from onehot because we use entropic mirror descent (Beck and Teboulle, 2003) to update A,, and this method requires iterates to be initialized to the interior of the simplex. In the RL domains, updates to A, are clipped in logit-space to be within = -5 and h (see Algorithm DT. We set the DxL coefficient to 0 except for in Coins, where y = 10 10-5 Additional hyperparameters are specified in S In experiments, reported price of anarchy refers the ratio of the sum of losses of the strategy learning converged to over that of the strategy learned by fully cooperative agents (Aij = )-
For D3C, we initialize Aa 0.99 and A;j 0.01
3.1 TRAFFIC NETWORKS AND BRAESS'S PARADOX
In 2009, New York city's mayor closed Broadway near Times Square alleviate traffic conges- tion (Neuman and Barbaro 2009). This counter-intuitive phenomenon, where restricting commuter choices improves outcomes, is called Braess's paradox (Wardrop) 1952 Beckmann et al., 1956
Braess 1968). and has been observed in real traffic networks (Youn et al. 2008; Steinberg and Zangwill 1983). Braess's ' paradox also found in physics (Youn et al. 2008 decentralized energy grids (Witthaut and Timme 2012), and can cause extinction cascades in ecosystems (Sahasrabudhe
and Motter 2011). Knowing when a network may exhibit this paradox is difficult, which means knowing when network dynamics may result in poor outcomes is difficult.
Figure presents a theoretical traffic network. Without edge AB, drivers commute according to the Nash equilibrium, either learned by gradient descent or D3C. Figure -b shows the price of anarchy approaching 1 for both algorithms. If edge AB is added, the network now exhibits Braess's 's paradox. Figure shows that while gradient descent converges to Nash (p 80), ) D3C achieves a price of anarchy near 1. Figure shows that when faced with a randomly drawn network, D3C agents achieve shorter commutes average than agents without the ability compromise.

---

Under review as a conference paper at ICLR 2021
Randim Network
Ret.
A
15
Gradient
D3C
1.2
nSa E {0- -4,, ABg E {0-4]
0
10MSA + 10TBE < 100SA + 45
1.1
1005A + 10 10 +
2000 4000
6000
8000 10000
Training Iterations
(a) Traffic Network
(b) Random Network Results
Figure 2: Four drivers aim minimize commute time from S to E. Commute time each edge depends on the number of commuters, Rij. Without edge AB, drivers distribute evenly across SAE and SBE for 65 min commute. After edge AB added, switching to the shorteut, SABE, always decreases commute time given the other drivers maintain their routes, however, all drivers are incentivized to take the shortcut resulting an 80 min commute. (b) The price of anarchy throughout training for 1000 randomly generated three road networks exhibiting Braess's paradox. Gradient descent and D3C are compared with shaded regions representing + standard devation.
Gradient Descent toward Kath
Gradient
DBC
median
median Paue
median Pros.
1:3
11
1.
11
mediinn Paue
5000 10000
15000
20000
3000
10000
20000
1.0
10000 15000 20000
3000
10000
15006 20003
(a) Without Shortcut (Edge AB Removed)
(b) With Shortcut (Edge AB Included)
Figure 3: Traffic Network A Without edge AB, agents are initialized with random strategies and train with either gradient descent (left) or D3C (right)-simila similar performance expected. Statistics of 1000 runs are plotted over training. Median Puax tracks the median over trials longest-commute among the four drivers. The shaded region captures + 1 standard deviation around the mean. (b) After edge AB is added, agents are initialized with random strategies and trained with either gradient descent (left) D3C (right). Statisties of 1000 runs are plotted training. Median Pmax tracks the median over trials of the longest-commutt among the four drivers. The shaded region captures + 1 standard deviation around the mean.
3.2 COIN DILEMMA
In the Coins game (Eccles et al. 2019at Lerer and Peysakhovich 2017). two agents move on fully-observed 5 gridworld, which coins of two types corresponding each agent randomly spawn at each time step with probability 0.005. When an agent moves into square with a coin of either type, they get a reward of When agent picks up coin of the other player's type, the other agent gets a reward of - 2. The episode lasts 500 steps. Total reward is maximized when each agent picks up only coins of their own type, but players are tempted to pick up all coins.
60
Comparatinn
Average Total Return
Total Raturn (Al Aimmmm Nean
1.0
Proportion own Coins
Retative Reward Attention
Payer
2.5
Payer
20
Marvic Sapen Invation
0.6
0.0
0.0
0.2
0.4
0.6
0.8
1.0
000
0.25
0.0
1.00
0.00
0.25
0.50
0.75
1.0
0.00
0.25
055
0.75
1.00
Training Epochs (Siliion))
Training Epochs (Billons)
Traniing Epochs (Billons!
Tre ning Epochs (Billins)
(a) Trial Statistics
(b) Individual Run
Figure 4: Coin Dilemma Mean total return ten training runs for agents. Mean return over all epochs is next to each method name in the legend. D3C hyperparameters were selected using five independent validation runs. Cooperative agents trained to maximize total return represent the best possible baseline. Shaded region captures + standard deviation around the mean. (b) One training (4% 0.9): of agent returns (left); % of coins picked up that the agent's type (middle); relative reward attention measured as In( (n 1)A4) In In(2, j Aji) (right).
7

---

Under review as a conference paper at ICLR 2021
D3C agents approach optimal cooperative returns (see Figure 1 Matching Imitation (Eccles et al. 2019b), which was previously tested on Coins and designed to exhibit reciprocal behavior towards co-players.
We compare against Metric
Figure shows D3C agents learning to cooperate, then temporarily defecting before rediscovering cooperation. Note that the relative reward attention of both players spikes towards selfish during this small defection window; agents collect more of their opponent's 's coins during this time. Oscillating between cooperation and defection occurred across various hyperparameter settings, Relative reward attention trajectories between agents appear to be reciprocal, i.e., move in relative synchrony (see for analysis).
H.2
3.3 CLEANUP
We provide additional results on Cleanup, five-player gridworld game (Hughes et al. 2018). Agents are rewarded for eating apples. but must keep river clean to ensure the apples receive sufficient nutrients. The option to be freeloader and only eat apples presents social dilemma. D3C is able to increase both welfare and individual reward over A2C (no loss sharing). We also observe that direct welfare maximization (Cooperation) always results in three agents collecting rewards from apples while two agents sacrifice themselves and clean the river. In contrast, D3C avoids this stark division of labor. Agents take turns each task and all achieve some positive cumulative return over training.
3000
Return
1020
Inditiuaal Allime Mean Return
1000
Indivicusl All
Mean Returnn
1000
Inclviduaa Altima Nean Return
750
750
750
500
500
500
1000
250
250
120
500
0.5 0.0
230
0.8
Traiing spacts (D-lborn))
Training Spochs (Bilion))
Taining Epocte [Balenst
Training Epechs (B1llon))
(a) Cleanup
(b) Individual Runs
Figure 5: Mean total return over ten training runs for agents. D3C hyperparameters were selected using five independent validation runs. Cooperative agents trained to maximize total return represent the best possible baseline. Shaded region captures standard deviation around the mean. b Three randomly selected runs. Each curve shows the mean return up to the current epoch for I of 5 agents.
helative Reward Altention
Relative Reward Attention
Rolaiive Reward Attention
2.0
3.0
0.2
2.0
0.5 (c) RRA= + Cooperation
1.0
Training (Billons)
(Bilionc)
(a) RRRRROO 0 > Altruism
(b) RRA< 0 ->
Altruism
Figure 6: Average relative reward attention (RRA) over 10 runs for five agents in Cleanup a and Harvest Patch hb and agents in Mini-Cleanup
3.4 A ZERO-SUM ELECTION
Consider a hierarchical election in which two parties compete in a zero-sum game- for example, only one candidate becomes president. If, at the primary stage, candidates within one party engage in negative advertising, they hurt their chances of winning the presidential election because these ads are now out in the open. This presents a prisoner's 's dilemma within each party. The goal then is for each party to solve their respective prisoner's 's dilemma and come together as one team, but certainly not maximize welfare- simple simulation with two parties consisting of two candidates each initially participating in negative advertising converges to the desired result after running D3C.
zero-sum game between the two parties should be retained. A
The final x 4 loss mixing matrix, A, after training 1000 steps is an approximate block matrix with 0.46 the 2 2 block diagonal and 0.04 elsewhere. We make duck duck-typing argument that when
8

---

Under review as a conference paper at ICLR 2021
multiple agents optimizing the same loss, they are functioning multiple components of single agent because mathematically. there is no difference between this multi-agent system and a single agent optimization problem. This matrix then indicates that two approximate teams have formed: the first two agents captured by the upper left block and vice versa. Furthermore, the final eigenvalues of the game Jacobian are (1.84 0.21e) x2; perfect team formation gives (2 + 0.25i) x2. The existence of imaginary eigenvalues indicates that the zero-sum component of the game is retained. In contrast, minimizing total loss gives imaginary part because Hessians (Jac( (V)) are symmetric.
RELATED WORK
Our work is most similar to (Hostalero et al. 2020p. This work also provides a decentralized approach that transforms the game by modifying rewards, however, it does not guarantee "budget- "budget-balance" nor does derive its proposed algorithm from any principle (e.g., price of anarchy): the proposed algorithm is heuristic supported by experiments. In other work, and Precup (2020) explore gifting rewards to agents as well, but it does so by simply expanding the action space of agents to include gifting action. It is also not budget balanced.
4.1 LEARNING LOSS FUNCTIONS
Choosing the right loss function for a given task is historically unsolved problem. Even in single- agent settings, the designated reward function can either often be suboptimal for learning (Sorg et al. 2010) or result in "reward hacking" (Amodei al., 2016). In the multiagent setting, OpenAl Five trains on an objective that mixes single agent and group agent rewards (OpenAl et all, 2019). The "team spirit" mixture parameter (r) manually annealed throughout training from 0.3 to 1.0 (i.e.,
A; = 0.8r, Aig = 0.2r, * i). Liu et al. (2019) find a team of soccer agents is better trained with agent-centric shaping rewards evolved via population based training, a technique that also led to human level performance in Capture the Flag (Jaderberg al. 2019.. Aguera y Arcas 2020) trains populations of simulated bacteria to maximize randomly drawn reward functions and discovers that significant portion of the surviving populations are actually ones rewarded for dying. In contrast to the work just described, we provide a decentralized approach, devoid of a central authority, that automates the design of incentives for multi-agent system.
4.2 SOCIAL PSYCHOLOGY, NEUROSCIENCE, AND EVOLUTIONARY BIOLOGY
Loss transformation is also found in human behavior. Within social psychology, interdependence theory (Kelley and Thibaut 1978) holds that humans make decisions based on a combination of self interest and social preferences. In game theoretic terms, humans deviate from rational play because they consider a transformed game rather than the original. Although rational play in the transformed game may result in lower payoff in single round of play, groups with diverse transformations are oftentimes able to avoid poor Nash equilibria. McKee et al. (022)) mirrored this result empirically with RL agents. Neuroscience research also supports this interpretation, showing that neural processing responds to others' losses, even if one's 's own outcomes are not affected (Fukushima and Hiraki 2009 Kang et al. 2010). The most fundamental account within evolutionary biology predicts that nature selects for individuals who care only for their own fitness. Absent other mechanisms, local selection for selfishness can drive a population to extinction (Grande Pérez al. 2005). The emergence of other-regardigg preferences seems particularly important for humans. Empathy results in altruistic choices, raising the fitness their group as a whole (Alexanderi and Bargia 1978).
CONCLUSION
Directly maximizing welfare can solve many social dilemmas, but it fails to draw out the rich behavior we would expect from agents in other interesting scenarios. We formulate learning incentives as a price of anarchy minimization problem and propose a decentralized, gradient- based approach, namely D3C, that incrementally adapts agent incentives to the environment at hand. We demonstrate its effectiveness on achieving near-optimal agent outcomes in socially adversarial environments. Importantly, it also generates reasonable responses where welfare maximization is indifferent.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Blaise Aguera y Arcas. Social intelligence. In Talk presented at the 33rd Conference on Neural Information Processing Systems Conference, Vancouver, Canada., 2020.
Richard D. Alexander and Gerald Bargia. Group selection, altruism, and the levels of organization of life. Annual Review of Ecology and Systematics, 9(1):449 474, 1978.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint arXiv:1606.0656. 2016.
Kenneth Arrow. Social choice and individual values, volume 12. Yale university press, 1970.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):667-77,, 2003.
Martin Beckmann, Charles B McGuire, and Christopher B Winsten. Studies in the economics of transportation. Technical report, 1956.
Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of fairness. Operations research, 59(1):17-31, 201
Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. On the efficiency-fairnes trade-off. Management Science, 58(12):2234-224) 2012.
Dietrich Braess. Über ein paradoxon aus der verkehrsplanung. Unternehmensforcchunng 12(1): 258-268, 1968.
Ennio Cavazzuti, Massimo Pappalardo, Mauro Passacantando, et al. Nash equilibria, variational inequalities, and dynamical systems. Journal of optimization theory and applications, 1 11(3):: 491-506, 2002.
Edward Clarke. Multipart pricing of public goods. Public choice, pages 17-33, 1971.
Tom Eccles, Edward Hughes, János Kramár, Steven Wheelwright, and Joel Z Leibo. The imitation game: Learned reciprocity in markov games. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, pages 1934-1936. International Foundation for Autonomous Agents and Multiagent Systems, 2019a.
Tom Eccles, Edward Hughes, János Kramár, Steven Wheelwright, and Joel 7. Leibo. Learning reciprocity in complex sequential social dilemmas. arXiv preprint arXiv: 1903v:/903.000000 2019h.
Gerald M Edelman and Joseph Gally. Degeneracy and complexity in biological systems. Proceed- ings of the National Academy of Sciences, 13724):13763-13700 2001.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint 1802.0106600 2018
Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complemen- tarity problems. Springer Science & Business Media, 2007.
Jakob Foerster, Richard Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with peponent-learning awareness. In Proceedings of the 17th Interna- tional Conference on Autonomous Agents and MultiAgent Systems, pages 122-130. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Hirokata Fukushima and Kazuo Hiraki. Whose loss it? human electrophyssiooggcall correlates of non-self reward processing. Social Neuroscience, (33)22112777 2009.
Kurtuluş Gemici, Elias Koutsoupias, Barnaéé Monnot, Christos Papadimitriou. and Georgios Pil- iouras. Wealth inequality and the price of anarchy. arXiv preprint arXiv: 2018.
10

---

Under review as a conference paper at ICLR 2021
Ana Grande-Pérez, Ester Lázaro, Pedro Lowenstein, Esteban Domingo, and Susanna C. Manrubia. Suppression of viral infectivity through lethal defection. Proceedings of the National Academy URL
of Sciences, 102((1):4444) 4452, 2005. ISSN 0027-8424. doi: 00.1073/pnax.04088711
ht..ts:// www pwws.
Jerry Green and Jean-Jacques Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica: Journal of the Econometric Society, pages 427-438,
1977.
Jerry R Green and Jean-Jacques Laffont. Incentives in public decision making. 1979.
Garrett Hardin. The tragedy of the commons. Science, 162(3859):1243-12445 1968.
Jason D Hartline and Tim Roughgarden. Optimal mechanism design and money burning. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 75-84, ACM, 2008.
David Earl Hostallero, Daewoo Kim, Sangwoo Moon, Kyunghwan Son, Wan Ju Kang, and Yung Yi. Inducing cooperation through reward reshaping based on peer evaluations in deep multi-agent reinforcement learning. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 520-528, 2020.
Edward Hughes, Joel Z Leibo, Matthew Phillips, Karl Tuyls, Edgar Dueiiez-Guzman, Antonio García Castañeda, Jain Dunning, Tina Zhu, Kevin McKee, Raphael Koster, et al. Inequity aversion improves cooperation in intertemporal social dilemmas. In Advances neural information processing systems, pages 3326-3336, 2018.
Lorens A Imhof, Drew Fudenberg, and Martin A Nowak. Tit-for-tat win-stay, lose-shift? Journal of theoretical biology, 247(3):374-580, 2007.
Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human- level performance in 3d multiplayer games with population-basee based reinforcement learning. Science, 364(6443):859-30) 865, 2019.
Sonia K. Kang, Jacob B. Hirsh, and Alison L. Chasteen. Your mistakes are mine: Self-other overlap predicts neural response observed errors. Journal of Experimental Social Psychology. 46(1): 229-232, 2010.
Harold H. Kelley and John W. Thibaut. Interpersonal Relations: Theory Interdependence. John Wiley & Sons, 1978.
Raghavendra V Kulkarni, Anna Förster, and Ganesh Kumar Venayagamoorthy. Computational intelligence in wireless sensor networks: survey. IEEE communications surveys & tutorials, 13 (1):68-96, 2010.
Anastasios Kyrillidis, Stephen Becker, Volkan Cevher, and Christoph Koch. Sparse projections onto the simplex. In International Conference on Machine Learning, pages 235-243, 2013.
Joel Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint arXiv:/702.030.. 2017.
Adam Lerer and Alexander Peysakhovich. Maintaining cooperation in complex social dilemmas using deep reinforcement learning. arXiv preprint arXiv: 2017.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games. arXiv preprint FfXXv:8811.084660 2018.
Ping Li, Syama Sundar Rangapuram, and Martin Slawski. Methods for sparse and low-rank recovery under simplex constraints. arXiv preprint arXiv:1605.00507, 2016.
Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emergent coordination through competition. arXiv preprint arXiv: 1902.07/000//1 2019.
11

---

Under review as a conference paper at ICLR 2021
Andrei Lupu and Doina Precup. Gifting in multi-agent reinforcement learning. In Proceedings of the 19th International Conference on Autonomous Agents and MuntiAgent Systems, pages 789-797, 2020.
Kevin R. McKee, lan Gemp, Brian McWilliams, Edgar A, Duéîtzz-Gzzmán, Edward Hughes, and Joel Z. Leibo. Social diversity and social preferences in mixed-motive reinforcement learning. arXiv preprint arXiv:2002.02325. 2020.
Michael P Murray. A drunk and her dog: An illustration of cointegration and error correction. The American Statistician, 48(1):37-39, 1994.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2):265-25) 1983.
Anna Nagurney and Ding Zhang. Projected dynamical systems and variational inequalities with applications, volume 2. Springer Science & Business Media, 2012.
William Neuman and Michael Barbaro. Mayor plans to close parts broadway to traffic. NY- Times.com, Feb 2009.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge university press, 2007.
Martin Nowak and Karl Sigmund. A strategy of win-stay, lose-shift that outperforms tit-for-tat the prisoner's ' dilemma game. Nature, 364(6432):56, 1993.
Travis E Oliphant. A guide NumPy, volume 1. Trelgol Publishing USA, 2006.
OpenAI, Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota with large scale deep reinforcement learning. 2019. URL patttss//arxttee org. /ttrg//b//// 01111111221660610111
Mert Pilanci, Laurent E Ghaoui, and Venkat Chandrasekaran. Recovery of sparse probability measures via convex programming. In Advances in Neural Information Processing Systems, pages 2420 2428, 2012.
Anatol Rapoport, Albert M Chammah, and Carol J Orwant. Prisoner's dilemma: A study in conftict and cooperation, volume 165. University of Michigan press, 1965.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Sociery, 58(5):527-535 1952.
Michael H Rothkopf. Thirteen reasons why the vickrey-clarke-grove process is not practical. Operations Research, 1512)11 2007.
Tim Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM (JACM), 62(5): 32, 2015.
Tim Roughgarden and Florian Schoppmann. Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 356:317-342,2011
Sagar Sahasrabudhe and Adilson E Motter. Rescuing ecosystems from extinction cascades through compensatory perturbations. Nature Communications, 2:170, 2011.
Mark Allen Satterthwaite. theorems for voting procedures and social welfare functions. Journal of economic theory, 10(2): 187-217, 1975.
and arrow's conditions: Existence and correspondence
Florian Schäfer and Anima Anandkumar. Competitive gradient descent. In Advances in Neural Information Processing Systemx, pages 7623-7633, 2019.
12

---

Under review as a conference paper at ICLR 2021
Shai Shalev-Shwartz al. Online learning and online convex optimization. R in Machine Learning, 4(2):107-19,, 2012.
Foundations and
Jonathan Sorg, Richard L Lewis, and Satinder P Singh. Reward design via online gradient ascent. In Advances in Neural Information Processing Systems, pages 2190-2198, 2010.
Richard Steinberg and Willard Zangwill. The prevalence of braess' paradox. Transportation Science, 17(3):301-318, 1983.
Robert J Tibshirani and Bradley Efron. An introduction to the bootstrap. Monographs statistics and applied probability, 57:1-436, 1993.
John Glen Wardrop. Some theoretical aspects of road traffic research. Proceedings of the institution of civil engineers, 13):3225-322, 1952.
Ronald J Williams. Simple statistical Pradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-23) 256, 1992.
Daniel J Wilson. The harmonic mean p-vauue for combining dependent tests. Proceedings of the National Academy of Sciences, 116(4):1195-1200, 2019.
Dirk Witthaut and Marc Timme. Braess's s paradox oscillator networks, desynchronization and power outage. New journal of physics, 14(8):08303,, 2012.
Jiachen Yang, Ang Li, Mehrdad Farajtabar, Peter Sunehag, Edward Hughes, and Hongyuan Zha. Learning to incentivize other learning agents. arXiv preprint Ttt::2000000051. 2020.
Hyejin Youn, Michael T Gastner, and Hawoong Jeong. Price of anarchy in transportation networks: efficiency and optimality control. Physical review letters, (0((1)):28700)) 2008.
13


Reviews:
[{"review_id": "o4d9oGl3tb4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "##########################################################################\n\nSummary:\n\nThis paper proposes a differentiable, local estimator of multi game inefficiency, as measured\nby price of anarchy. We then present two instantiations of a single decentralized meta-algorithm, one\n1st order (gradient-feedback) and one 0th order (bandit-feedback), that reduce this inefficiency. Experiments conducted in three domains (traffic network, Coins and Cleanup) show that agents minimizing local estimates of price of anarchy achieve lower loss on\naverage than selfish agents without the ability to compromise.\n\n##########################################################################\n\nReasons for score: \n\nOverall the paper is well organized and provided clear motivation of the problem. The proposed approach is well-presented and the idea of mixing losses is interesting. An upper bound for the optimized price of anarchy is presented.\n\n##########################################################################Pros: \n\nDetailed comments and concerns:\n\n1. What is the implication of \"mixing losses\" in practical systems? What are the incentives for agents to adjust their original incentives? I would like to see more discussions addressing the incentive compatibility issue in adjusting for a mixing losses.\n\n2. The authors show that if each agent’s original loss is convex with diagonally dominant Hessian and the strategy space is unconstrained, the the unique, globally stable fixed point of the game defined with mixed losses is a Nash. I would be willing to see more discussions on if these restrictions could be relaxed to achieve Nash under the mixed losses.\n\n3. What are the computation times for running D3C, and how does that compare to the baselines?\n\n----- Post Discussion ---- Updates to the paper have helped make the motivation/technical parts of the paper more clear. The authors' response are helpful w.r.t the questions I raised in the review.\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "i0gnl7khcAs", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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 authors propose to change agents' incentives in order to lead to a better Nash equilibrium outcome. \nThey propose a practical decentralized approach to computing the \"optimal\" change of incentives.\nI'm confused by many aspects of this paper:\n1. How would you implement the change of incentives in a any of the game theoretic domains? I.e. in what context would agents who lose money agree to participate without a centralized authority ordering them to?\n2. Why do you consider changes of incentives with bounded KL-divergence? What does that have to do with your motivating concern around communication (3rd paragraph of intro)?\n3. Why do you optimize the price of anarchy instead of social welfare at worst Nash equilibrium? These should be the same when you don't change the total loss, but then I don't understand the denominator of (3).\n4. What is $t$ in (4)? How does f^A_i depend on t?\n5. Shouldn't \\beta_i appear in (4)? Or does (4) hold for all \\beta_i (e.g. approaching infinity)?\n6. What should I conclude from your experiments? Of course if you completely mix the agents' utilities the Nash equilibrium would be locally optimal. The Nash equilibrium utilities at the modified games seem better, but it's not clear how much the games were modified.\n\nMisc:\n(A) Computing the Price of Anarchy in general is NP-complete rather than PPAD-complete because PPAD corresponds to finding *any* Nash equilibrium rather than the worst one.\n(B) \"set of the equilibria of the game restricted to the line\" - I don't understand what this sentence means.\n(C) Why don't you define utilitarian/egalitarian before Theorem 1?\n(D) Typos: \"one-hot\" \"the the\"\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "T9ChW_VUW-_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 proposes a (decentralized) method for online adjustment of agent incentives in multi-agent learning scenarios, as a means to obtain higher outcomes for each agent and for the group as a whole. The paper uses the “price of anarchy” (the worst value of an equilibrium divided by the best value in the game) as a proxy for the efficiency of the game outcome, and derive an upper bound on a local price of anarchy that agents can differentiate. In several experiments (a traffic network, the coin game, Cleanup), their method leads to improved individual agent and group outcomes relative to baselines, while avoiding cases of stark division of labor that sometimes emerges when agents directly optimize the sum of all agent rewards. \n\nPros:\nOverall, I thought this paper was quite strong. I agree with the claim in the paper that having agents simply optimize the cooperative return is not always realistic or interesting. The framing of compromise as the mixing of agent incentives is particularly interesting, and it makes intuitive sense to me. I’m not familiar enough with the literature to know if this formulation is novel (and unfortunately the paper does not have a Related Work section). The paper makes significant contributions towards making this idea practical, including relaxing the requirement that the agents can observe or directly differentiate with respect to the other agent strategies. \n\nThe paper is also pretty well written and communicated, though I did not dive into the proofs and skimmed some of the technical details. I appreciated the frankness with which the paper describes their method, e.g. in the following excerpts:\n“Ideally, one meta-algorithm would allow a multi-agent system to perform sufficiently well in all these scenarios. The approach we propose, D3C (Sec. 2), is not that meta-algorithm, but it represents a holistic effort to combine critical ingredients that we hope takes a step in the right direction”\n“We also provide specific, albeit narrow, conditions under which agents may achieve a Nash equilibrium”\n\nCons:\nOf course, the ‘mixing of losses’ strategy proposed in the paper requires that agents be able to observe the losses of other agents, which is not always feasible in practice.\n\nOther notes:\nI was a bit confused by the sentence: “Our agents reconstruct their losses using the losses of all other agents as a basis”, which seems to imply that the agents’ own loss function is not used as part of this basis. \n\nThe Appendix also seems to be missing from the paper, although there are references to it in the text (e.g. reference to F.4). \n\nOverall:\nOn the whole, I think this paper is quite good and worthy of acceptance. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EbZqAXVsDTN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 paper details a method by which it attempts a method to change the utility function for agents so they incorporate the utilities of other agents, resulting in more cooperating agents, so that the price of anarchy is minimized. It examines such trained agents in several problem settings, seeing them performing quite well.\n\nThe attempt to change the utility is quite interesting, but, sadly, it is not really explored enough. That is, while agents improve, no attempt has been made to examine the new \"mixing\" matrix, and see what changed to make the agents collaborate better (or not). It is quite a pity, as in this case, unlike many other learning cases, the result is quite interpretable for us.\n\nAs more a game-theorist than a ML expert, I did struggle a bit with the technical bits in section 2. The definition of \"local price of anarchy\" seems sometime overlapping, but not really the same as the definition of that of Ben-Zwi and Ronen from 2011 (\"Local and global price of anarchy of graphical games\", TCS 412, 1196-1207). I had some difficulty following algorithm 1, as \\Delta t_b seems always negative, and it was not clear to me what G is (and in particular, for negative values).\n\nIn the experimental section, as noted above, an interpretation of the A matrix would have helped. At least in some of the examples, it seems a matrix A with each value being 1/n seems to satisfy all that's needed (e.g. the Braess paradox). I could not follow the setting of the \"zero-sum election\", and what is the described game. Moreover, the introduction promises an incentive-compatible setting. What is intended to be an IC mechanism?\n\nUPDATE POST-REBUTTAL\n————————————\nMany of my questions have been answered, though I do think reviewers should explicitly note Ben-Zwi and Ronen's paper, and change their use of \"incentive compatible\". I think a deeper and more systematic analysis of the A matrix is also warranted, but I do now feel the paper has better scientific merit.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method of decentralized mechanism design to reduce the price of anarchy. Based on the detailed responses of the authors, all reviewers were satisfied by the technical contribution after the rebuttal period. 

There was, however, a heavily engaged and lengthy discussion between most reviewers regarding the applicability of the method and how it links to the motivation given in the paper. The paper could be improved by (1) highlighting an exemplar real world use case in the paper motivation (there are a couple mentioned briefly in the introduction but one of these could be emphasized more); and (2) connecting the choices made in the design of the approach to the opening motivation sections and exemplar use case.

The level of engagement from most reviewers demonstrates a good level of interest from a representative sample of the ICLR community but demonstrated that their remained work outstanding to clarify the core message and significance of the contribution.
Decision: Reject