redacted Mike Johanson<EMAIL_ADDRESS>or Joel Leibo
<EMAIL_ADDRESS>
# Emergent Bartering Behaviour in Multi-Agent Reinforcement Learning

Michael Bradley Johanson  DeepMind  Edward Hughes  DeepMind  Finbarr Timbers
DeepMind  Joel Z. Leibo  DeepMind

###### Abstract

Advances in artificial intelligence often stem from the development of new
environments that abstract real-world situations into a form where research
can be done conveniently. This paper contributes such an environment based on
ideas inspired by elementary Microeconomics. Agents learn to produce resources
in a spatially complex world, trade them with one another, and consume those
that they prefer. We show that the emergent production, consumption, and
pricing behaviors respond to environmental conditions in the directions
predicted by supply and demand shifts in Microeconomics. We also demonstrate
settings where the agents’ emergent prices for goods vary over space,
reflecting the local abundance of goods. After the price disparities emerge,
some agents then discover a niche of transporting goods between regions with
different prevailing prices—a profitable strategy because they can buy goods
where they are cheap and sell them where they are expensive. Finally, in a
series of ablation experiments, we investigate how choices in the
environmental rewards, bartering actions, agent architecture, and ability to
consume tradable goods can either aid or inhibit the emergence of this
economic behavior. This work is part of the environment development branch of
a research program that aims to build human-like artificial general
intelligence through multi-agent interactions in simulated societies. By
exploring which environment features are needed for the basic phenomena of
elementary microeconomics to emerge automatically from learning, we arrive at
an environment that differs from those studied in prior multi-agent
reinforcement learning work along several dimensions. For example, the model
incorporates heterogeneous tastes and physical abilities, and agents negotiate
with one another as a grounded form of communication. To facilitate further
work in this vein we will release an open-source implementation of the
environment as part of the Melting Pot suite (Leibo et al., 2021).

###### Contents

  1. 1 Introduction
  2. 2 Related Work
    1. 2.1 Exploration and the road to AGI
    2. 2.2 Pure conflicting interests
    3. 2.3 Pure common interest
    4. 2.4 Mixed motivation settings
    5. 2.5 Agent-Based Computational Economics
    6. 2.6 AI Economist
    7. 2.7 Comparison to this work
  3. 3 Background
    1. 3.1 Markov Games
    2. 3.2 Reinforcement learning
    3. 3.3 Multi-agent reinforcement learning
    4. 3.4 Supply and Demand
  4. 4 The Fruit Market Environment
    1. 4.1 Movement, Production, and Consumption
    2. 4.2 Offers and Exchanges
    3. 4.3 Opportunity Costs
    4. 4.4 Distributed Training
    5. 4.5 Overview
  5. 5 Experiments
    1. 5.1 Production, Consumption, and Trade
    2. 5.2 Supply and Demand Shifts
    3. 5.3 Marketplaces
      1. 5.3.1 Moving the Marketplace
    4. 5.4 Trade Radius
    5. 5.5 Regions, Borders, and Merchant Behavior (Arbitrage)
      1. 5.5.1 Quantifying the Neutral Region Advantage
      2. 5.5.2 Emergence of Merchant Behaviour
      3. 5.5.3 Merchant Behaviour in Other Settings
  6. 6 Ablations and Tuning
    1. 6.1 Hunger penalty
    2. 6.2 Movement Penalty
    3. 6.3 Agent Architecture
    4. 6.4 Trade Mechanics
      1. 6.4.1 Drop and Give Actions
      2. 6.4.2 Compatible versus Inverse Offer Resolution
      3. 6.4.3 Accept Actions
      4. 6.4.4 Dynamic Offer Actions
  7. 7 Future Work
  8. 8 Conclusion
  9. A Agent Architecture

##  1 Introduction

We would like to build artificial agents capable of innovating as humans do.
We believe that theoretical and algorithmic frameworks such as decision theory
and reinforcement learning (or RL) are relevant to this goal. However, one
reason we have not yet succeeded in building such agents stems from a
fundamental tension between what these theories are good at—mainly
strengthening weak and unlikely behaviors so they become more prevalent and
refined—and what we actually want them to do: discover truly novel and
innovative behaviors that do not occur with any frequency at all at the start
of their learning.

As anyone who ever tried to train a pigeon to bowl will attest, if you must
wait to provide the first reward until the pigeon naturally emits an
approximation of the desired behavior, you will have to wait a very long time
indeed (Peterson, 2004). In terms of Bayesian decision theory, the prior
distribution must contain the novel behavior within its support. Otherwise, no
amount of evidence for its superiority will suffice to nudge its probability
off zero (Kalai and Lehrer, 1993). L. J. Savage illustrated the problem with a
pair of proverbs. A small world is one where you can always “look before you
leap”. A large world is one where you must sometimes “cross that bridge when
you come to it” (Binmore, 2007; Savage, 1951). Bayesian decision theory is
only valid in small worlds. Yet the real world is large.

In large worlds, RL becomes a theory of how to strengthen weak behaviors, not
a theory of how to generate wholly new ones. This is because an innovative
behavior cannot be reinforced until a close-enough approximation to it has
been emitted for the first time. RL researchers employ a variety of methods to
encourage agents to continually emit novel behaviors. Many amount to injecting
randomness in to action selection, as in $\epsilon\text{-greedy}$ and entropy
regularized Boltzmann exploration (Sutton and Barto, 2018). Osband et al.
(2019) calls this approach random _dithering_. Dithering provides an agent
with opportunities to experience the rewards that may be obtained with
behaviors it never tried before. However, dithering is an inefficient way to
traverse a large world. Consider: an $\epsilon\text{-greedy}$ agent selects
the action it currently thinks is best with probability $1-\epsilon$ and
otherwise selects uniformly at random from all available actions. The
probability of it emitting any particular novel behavioral sequence— _i.e_. a
sequence containing no actions initially thought to be valuable—decays
exponentially as the length of the sequence increases (Kakade, 2003; Osband et
al., 2019). Optimistic initialization is another approach to exploration,
which positively biases the agent’s initial reward estimates for every state
and action (Sutton and Barto, 2018). However, absent prior knowledge
concerning where to place one’s optimism, it reduces to a general drive to
explore all states and actions, an impossible task and an inefficient and
distracting bias in large worlds.

There are many other more sophisticated approaches to exploration in RL but
all struggle in large worlds for the same reason: the farther the target
behavior is from the current best known behavior, the more the agent must
experiment with actions it believes to be unattractive in order to find it. In
large worlds the target behavior may be very far away indeed. More
sophisticated approaches to exploration seek to choose experimental actions
more judiciously than random dithering, but there are limits to how much
efficiency can be gained this way without incorporating prior knowledge
(Osband et al., 2019). As a result, RL is often bad at discovering beneficial
behaviours (_i.e_. action sequences) when they never occur by chance before
learning and a random agent never emits them. Yet these are exactly the
behaviors that we are most interested in discovering. We know that humans can
innovate: examples include composing Beethoven’s 5th symphony, designing
spacecraft to take astronauts to the moon, and devising agricultural
technology to feed billions of people. We want to develop algorithms that can
innovate as humans do.

So far we have assumed that we cannot rely on the agent’s learning environment
having any particular structure. The logic underlying this assumption is
clear: since we want our RL agents to succeed in any environment it follows we
must prefer exploration techniques such as $\epsilon\text{-greedy}$ that
eventually converge in all environments, particularly those where no prior
knowledge can be leveraged. This starting point led us to a pessimistic
conclusion about RL’s ability to explain innovation. On the other hand,
allowing prior knowledge would completely change the picture. There are many
RL algorithms that explore efficiently when provided with correct prior
knowledge in one form or another, even in large worlds (e.g Gupta et al.
(2018)). Perhaps by restricting our attention to natural environments like
those in which humans evolved we can uncover the roots of innovation. After
all, natural environments do not cover more than a vanishingly tiny slice of
the space of all possible environments, and they may have useful properties
relevant to promoting exploration by the agents that inhabit them. Moreover,
the RL environments we typically use for research were never intended as
models of situations conducive to the evolution or development of natural
intelligence. They could systematically fail to capture the important
properties of natural environments.

Indeed, two independent strands of biological evidence and reasoning suggest
that most of our RL environments miss something important that is present in
natural environments. In laboratory animals, manipulations of the rearing
environment produce profound effects on both brain structure and behavior. For
example, laboratory rodent environments may be enriched by using larger cages
which contain larger groups of other individuals—creating more opportunities
for social interaction, variable toys and feeding locations, and a wheel to
allow for voluntary exercise. Rearing animals in such enriched environments
improves their learning and memory, increases synaptic arborization, and
increases total brain weight (Van Praag et al., 2000). The second strand of
biological reasoning concerns the “social brain hypothesis” for the
evolutionary emergence of intelligence in the primate order (Dunbar, 1998). It
is based on the observation that a species’ brain size correlates well with
its typical social group size (adjusted for overall body size). The
correlation holds over the entire primate order, which spans three orders of
magnitude in brain size (Dunbar and Shultz, 2017). As a general rule, primates
who live in larger groups have larger brains. The social brain hypothesis
suggests that larger social groups, which were necessary for reasons such as
mitigating predation risk, gave rise to myriad new problems of social origin.
The need to solve these was the driver for the evolution of greater and
greater intelligence in the primate order. In RL terms, the hypothesis is that
the socially enriched environments of the “brainier” species contained the
right mix of problems to encourage agents to devote effort toward finding
intelligent solutions.

Moreover, many critical innovations concern the coordinated behavior of more
than one agent. The RL community’s standard method of addressing the problem
of exploration, intrinsic motivation (e.g. Pathak et al. (2017)), is uniquely
unsuited for the finding of equilibria involving extensive coordination
between agents since intrinsic motivations are, by definition,
intrinsic—depending only on self-generated signals, which cannot easily be
correlated to those in others.

Fortunately there is a subfield of RL that considers social enriched
environments: multi-agent reinforcement learning (MARL). Multi-agent
environments are inherently non-stationary, as each agent’s stream of
experience and optimal behaviour changes as the other agents learn and change
their behaviour. As the population learns, new niches may be created that an
agent can fill, or other agents may start to contest an agent’s current niche.
This provides agents with _extrinsic_ motivation to continually explore new
behaviors as the population adapts (Leibo et al., 2019a; Balduzzi et al.,
2019; Baker et al., 2019; Wang et al., 2019b). In theory such multi-agent
systems may continue to explore forever. In practice they often reach an
equilibrium point and stop exploring. Efforts to understand how these systems
work create tension with the dominant “single-agent paradigm” of artificial
intelligence and cognitive science. In short, all the representations that
matter are no longer inside the agent’s “head”, but rather are distributed in
some fashion between the agent, the population, the environment, and the
training protocol itself.

Multi-agent environments feature causal forces that provide extrinsic
motivation to explore. For example: consider the supply and demand forces in
Microeconomics. They are created by the aggregate behavior of individual
agents. They constitute real motivational forces for the utility maximizing
agents who populate economic theory in the sense that changes in supply and
demand cause systematic incentives for agents to change their behavior in
specific directions. For instance, an increase in the price at which I can
sell a widget incentivizes me to produce more widgets. Likewise, a decrease in
the number of agents competing with one another to buy my widgets incentivizes
me to lower the price at which I sell them, or to decrease production. These
same forces can sometimes motivate innovation. If demand for the widgets made
in my factory increases strongly enough—and I cannot simply raise the
price—then I become incentivized to find ways to make more of them or to make
them more efficiently, perhaps by improving a manufacturing process. The
example illustrates that there is not necessarily any explore-exploit trade-
off. In fact, real world environments often have properties that make it
possible for agents to explore by exploitation (see also Leibo et al.
(2019b)).

So far we have argued that the social environment—that is, the set of other
agents in the world—shape the reward landscape and thereby provide extrinsic
motivation for agents to explore and innovate. The underlying environment, or
substrate, that these agents inhabit also plays a role in motivating agents to
innovate. For instance, a very simple substrate consisting of just an empty
room devoid of objects admits no innovation, no matter how large or complex
the agent population is that inhabits it. We can extend this kind of argument
much further. Consider what would happen if you connected a large language
model such as GPT-3 (Brown et al., 2020) to the latest RL-based agent that
solves complex problems in a 3D world (to be concrete, perhaps consider
Parisotto et al. (2020) or any other state of the art single-agent RL
algorithm applicable to 3D simulated worlds). Also, for this thought
experiment, assume that we have somehow solved the problem of language
grounding (described in for example Harnad (1990)). Choose as the substrate a
3D simulation with realistic physics such as the one underlying the DMLab-30
suite of environments (Espeholt et al., 2018). Then connect 100 of these
state-of-the-art RL agents to it. Give them the ability to talk to one another
by querying the large language model and sending one another streams of text.
Since we have assumed that the language grounding problem has already been
solved, the agents are thus able to refer to all the objects in their world by
name, and that knowledge is integrated into their broader language
understanding provided by the language model. Let all 100 agents live
simultaneously in the same simulated world. Now, what would happen? The
“social-is-all-you-need” hypothesis appears to suggest that this would be
enough to set off a cumulative cultural innovation explosion ratchet. But
would it really? Surely the specific properties of the substrate matter too.
We do not believe that any environment containing sufficient complexity can
generate innovation, not even for a multi-agent system with deeply complex
individual agents having a lot of cognitive capacity111For instance, some
environments are just too simple or afford too little means of communication
and too little interdependence for a “social-is-all-you-need” intelligence
ratchet to get off the ground.. This raises the question: which properties of
the environment matter and which do not? Are there necessary and sufficient
conditions for an environment to “allow for” substantial innovation? How do we
even study such questions? The present paper concerns a particular hypothesis
in this realm: that properties that are important in microeconomics will also
be important for motivating agents to explore and innovate. The reason is that
economics is a science of incentives. The environmental properties highlighted
in economics are those that create incentives for agents to interact.
Meanwhile in AI, incentives are also the motive force for agents to explore.
Incentives are what we think are lacking in the social-only thought
experiment. Without any incentive to innovate, agents simply won’t.

Exploration by exploitation depends on the environment to furnish incentives
for exploration. Incentives induce gradients in value over policy space. For
instance, competitive incentives provide an intrinsic drive for exploration.
As soon as one agent starts habitually exploiting any particular solution it
creates an incentive for other agents to invest time and energy into learning
how to adapt in response. In strictly competitive two-player settings such as
the games of go or heads-up poker (Silver et al., 2017; Bowling et al., 2015),
we would describe the agents as adapting to exploit each other, and (if using
appropriate algorithms) would eventually converge to a stalemate: a Nash
equilibrium. However, that point may be arbitrarily far away from their
initial behavior. In a large world, it is possible for agents to continually
refine their behaviours and innovate new ones to better adapt to each other
for a very long time.

Economic behaviors like production, consumption, and trade are enacted by
individuals, but weaved together in a complex whole composed of the
interaction of many individuals and the environments they inhabit. A mutually
supporting system of such behavior exerts incentives on individuals to learn
specific kinds of things, such as how to improve the efficiency of a
production process. This is true for human economies and ought also to be true
in artificial economies. Read (1958) illustrates the idea with a short story
told from the perspective of a pencil proudly describing its heritage. The
pencil’s wood came from a straight grain cedar tree in Northern California,
cut down by a team of loggers bearing saws, trucks, and rope. The pencil’s
graphite was mined in Sri Lanka and its mining involved a range of other
tools, and had to be shipped by sea to the pencil factory. Numerous
dockworkers, sailors, and lighthouse keepers all take action to ensure its
safe passage. The story goes on like this for several pages, until the reader
is left with real sense of awe at the complexity of the globe-spanning
cooperative machine that gave birth to the pencil. Read (1958) points out that
it is not even necessary that all the people involved in the pencil’s
construction ever lay eyes on the final product or have any interest in it
themselves. But the pencil-producing system as a whole hangs together anyway.
Indeed, it does more than that that: it thrives. The individuals involved need
not care about pencils, or be aware of upstream or downstream steps in the
creation of pencils, but are all linked nonetheless through the system of
incentives provided by the market economy. All act toward their local ends,
and the “invisible hand” of the market coordinates their activities.
Furthermore, consider what happens if demand for pencils increases, something
that could occur for instance if the overall population size increased. All
else being equal, greater demand for pencils creates greater demand for
graphite and cedar wood. It incentivizes all of the many different individuals
involved in the pencil production supply chain to make local efficiency
improvements, so they may ultimately sell more of their product to obtain
greater profits, taking advantage of the increased demand. In terms of
reinforcement learning, the incentives created by the market economy are
experienced by agents as gradients in value over policy space. Imposing such a
gradient has a strong effect on the policies that agents may ultimately learn.

The emergence of economic behavior in MARL engages somewhat different logic
than in economics. Consider the following illustrative example resembling what
can be found in any introductory economics textbook. Farmer Alice—who has
corn—and farmer Bob—who has chickens—have utility functions such that they can
benefit from trade. Alice wants some chickens and Bob wants some corn. A
simple economic analysis proceeds from there. One result is a model that
predicts their supply and demand behavior: the classic intersecting supply and
demand curves model (e.g. Samuelson and Nordhaus (1995)). However, this
derivation assumed from the outset that Alice and Bob already know how to
trade. For example: Alice must know that she would gain more utility if she
had chickens, that Bob has chickens, that Bob wants corn, that there exists a
sequence of actions they could each take to exchange these goods, and that Bob
is also aware of these facts. In economic models that assume rational agents,
this knowledge and behaviour is taken for granted. This assumption makes
sense: the human agents being modelled perform these exchanges many times
every day without much thought. However, when the agents are reinforcement
learning agents that learn through their own stream of experience, with no a
priori knowledge of what their observations mean, what effect their actions
have, or that other agents are in fact goal-seeking and adapting entities and
not just non-adaptive parts of the environment that happen to move around, it
is not at all clear that the agents will learn to trade with each other.
Further, even if they do discover the sequences of actions required to
produce, trade, and consume goods, it is similarly unclear that their
behaviour will evolve in the directions we predict of theoretical rational
agents under the pressure of abstract supply and demand forces.

In this paper, we will study exactly this emergence of microeconomic
behaviour—production, trading, and consumption—in populations of state-of-the-
art reinforcement learning agents. In our environment called Fruit Market,
deep reinforcement learning agents learn from scratch how to produce, trade,
and consume resources in order to maximize their individual reward. When the
environment is changed in ways familiar to a Microeconomics 101 student, by
adjusting environmental features related to supply or demand, the population’s
equilibrium production, consumption, and pricing behaviour largely shifts in
the directions we expect from Microeconomics. Our environment includes
dimensions of space and time, allowing for the emergence of phenomenon such as
local prices reflecting the nearby abundance of resources, and arbitrage
behaviour by agents who learn to exploit those price differences. However, our
work is not really about applying state-of-the-art artificial intelligence to
economic modeling (for that, see instead Zheng et al. (2020)). Instead, our
goal is to explore this emergence of microeconomic behaviour just as we would
study any other social behaviour within the broad project of creating
artificial general intelligence (AGI).

A key element of this work is our exploration of what microeconomic knowledge,
if any, must be built into the environment in order for current state-of-the-
art agents to discover and refine production, consumption, barter, and
arbitrage behaviors. We restrict ourselves to only adjusting the environment.
The agents we use are generic deep reinforcement learning agents which have
been widely used in other MARL research. They start training from a randomly
initialized state and have no domain-specific prior knowledge, parameter
tuning, or code. In this setting, we find numerous ways to manipulate the
environment that can radically change the final behavior that a population
converges to, including whether trade flourishes between agents, or does not
emerge at all. In addition to our empirical results demonstrating successful
learning by the agents, we also include a large analysis of these
environmental choices to show why they were made, and how alternative choices
perform. For example, we will demonstrate that current agents do not learn to
trade if their actions for doing so are overly generic, such as “drop an item
on the ground” or “give an item to another agent”. These actions could be used
to trade goods, but it is difficult to learn to use them appropriately: why
give an item to another agent if they have not yet learned to give something
else in return? However, if the environment includes a mechanism that
facilitates trading by making the exchange atomic—simultaneously swapping
items between agents that have agreed—then the agents do consistently learn
how to trade. In the real world, there would be a whole system of conventions,
norms, and institutions to support this, such as concepts of private property
ownership that serve to coordinate everyone’s expectations so that trades can
proceed more-or-less atomically (Segal and Whinston, 2013). When we assume an
automatic trade facilitation mechanism we sidestep the critical question of
how all that structure could emerge. This move turns out to be essential for
the present work. We would not have been able to make progress using today’s
state-of-the-art generic agents otherwise. However, if our agents cannot learn
without such mechanisms in the future, it will ultimately have negative
implications for our MARL agents’ generality since there are surely many
important economic behaviors and phenomena that follow from properties of the
underlying market-inducing conventions, norms, and institutions (Coase, 1988).
Without dismissing the importance of such market-inducing structures, we set
them aside for now. By focusing our attention on the case featuring the
automatic trade resolution mechanism we are able to make progress on
downstream questions like how environmental changes (_e.g_. supply and demand
shifts) affect emergent production, consumption, barter, and arbitrage
behaviors. Learning these behaviors is still a complex feat for MARL agents as
they involve interleaved decisions of where and what to harvest and where to
travel to find others to trade with, as well as what offers to make and
accept.

AI research relies on simulation environments that capture important cognitive
and social challenges. This is because agents that learn in such environments
face incentives that push them to develop habits of cognition and discover
essential concepts that describe their world and how they can effectively
behave in it (Silver et al., 2021). One implication of this research method is
that, towards the goal of constructing generally capable agents, researchers
must continually grow the set of environments under consideration. Eventually
it should reflect a full accounting for all conceptually distinct principles
of intelligence. For the domain of social intelligence, so rich in real-life,
its mirror in MARL research remains woefully incomplete. Our goal in this work
is to add these themes of trading, negotiation, specialization, and adaptation
to a changing population to the areas examined in MARL research. To facilitate
further research in this direction, we have prepared an open-source version of
our environment which we will incorporate into the next release of the Melting
Pot environment suite (Leibo et al., 2021)222Melting Pot is available at
https://github.com/deepmind/meltingpot..

##  2 Related Work

Many AGI researchers take an approach to building advanced learning systems
based on the idea of reverse engineering human intelligence. Part of the
reverse engineering approach involves trying to elucidate the correct list of
cognitive abilities that one would need to establish a putative AGI possesses
in order for us to declare victory and consider it a human-like artificial
agent. The most obvious such abilities are the “classic” cognitive abilities
like perception, attention, and memory. However, numerous other schemes exist
(e.g. Spelke and Kinzler (2007); Schneider and McGrew (2018)), and the problem
of how to measure whether or not a putative AGI displays a particular ability
is not entirely resolved (Hernández-Orallo, 2017). However, recent
developments that adapt to RL the relentless focus on measuring generalization
long advocated by the supervised machine learning community are widely seen as
a positive methodological development (e.g. Zhang et al. (2018); Machado et
al. (2018); Fortunato et al. (2019); Cobbe et al. (2019); Juliani et al.
(2019); Crosby et al. (2020); Leibo et al. (2021)).

###  2.1 Exploration and the road to AGI

In one paradigm, the cognitive abilities are themselves regarded as
potentially emergent from generic experiential learning under a simple reward
function (Silver et al., 2021); it is called the _reward is enough_
hypothesis. It contrasts with the hypothesis that specialized inductive biases
will be needed for each ability (as advocated for instance by Lake et al.
(2017) and Marcus (2018)). From our vantage point, the important thing about
the reward is enough hypothesis is that it casts the problem of cognitive
ability discovery as one of extremely deep exploration. It requires agents to
emit behaviors very far from those they would emit randomly, “sculpting”
subsystems like long-term memory out of a pluripotent initial neural
machinery333In cognitive science, Cecilia Heyes has articulated a theory of
cognitive ability discovery that is broadly compatible with ours (Heyes,
2019). In her view, some cognitive abilities such as natural linguistic
proficiency are built up by generic learning processes operating within the
context of cultural evolution. Her term for these is cognitive gadget. For
instance, the ability to read is clearly a cognitive gadget since written
language is no more than 6000 years old, too recent for genetic evolution to
have produced a specialized reading mechanism. The reward is enough account of
Silver et al. (2021) similarly holds that cognitive abilities may emerge from
generic learning mechanisms and adds the unique hypothesis that for AI, one
specific such mechanism, reinforcement learning, is sufficient to originate
all the other cognitive abilities.. The distance in behavior space that such
exploration much traverse is truly gargantuan.

For years the prototypical exploration problem in RL has been the Atari game
Montezuma’s Revenge (Bellemare et al., 2013). In this 2D “flip-screen” game,
the player must guide a character through a series of rooms where only a
rather precise sequence of movements can get them through safely and non-zero
rewards are very rare. Thus policy and value gradients are often near zero and
reinforcement learning is very inefficient. Exploration research motivated by
Montezuma’s Revenge addresses the hypothesis that sparse rewards are the main
difficulty in exploration. The idea is that if only the rewards were instead
dense— _i.e_. frequent—then, even if those rewards were not the “real” reward,
they would still induce a strong gradient capable of guiding policy learning
around the space, where it would eventually discover the solution. The sparse
reward hypothesis led researchers to propose a great variety of intrinsic
motivation models: modified reward functions that push agents to seek novelty
or empowerment (e.g. Bellemare et al. (2016); Gregor et al. (2017); Burda et
al. (2018); Eysenbach et al. (2018); Karl et al. (2019)). These methods have
been successful in Montezuma’s Revenge. But, on their own, it is unclear how
they could be made to scale up to the truly gargantuan amount of exploration
required to discover novel cognitive abilities demanded by Silver et al.
(2021).

Many researchers have sought to build off the observation that correct prior
knowledge of the environment, when presented in an accessible fashion, can be
used to structure exploration (e.g. Schwartz et al. (2019); Goyal et al.
(2019); Mirchandani et al. (2021); Mu et al. (2022) and Tam et al. (2022) all
explored natural language-based representations of prior knowledge). Much of
the emphasis in AGI-oriented single-agent RL research is accordingly based on
approaches that seek to learn rich models and representations of the world
that can then be deployed to support such long-term goal directedness (Hung et
al., 2019; Schrittwieser et al., 2020; Hessel et al., 2021). For instance,
starting with some amount of common sense, agents could represent that they do
not know about a certain area, make a concerted plan to investigate it, and
then sequence all their actions over a long period of time in order to follow
through on that plan, integrating the knowledge thus acquired into their
general world model, and then repeat the process again from its new stronger
starting point (e.g. Botvinick et al. (2017); Lampinen and McClelland (2020);
Shanahan and Mitchell (2022)). One version of this approach makes the goal
directedness explicit via generalized value functions (Sutton et al., 2011)
with the idea that, ideally, the (sub)-goals themselves would come from
something like the agent’s abstract understanding of its world (Vezhnevets et
al., 2017; Veeriah et al., 2021).

An alternative, and really quite different, approach starts by essentially
giving up on solving the sparse reward problem within the simulation itself.
Instead, this approach relies on human trainers to provide the diverse data
needed to train the artificial agent using imitation learning (Ziebart, 2010;
Ho and Ermon, 2016; Finn et al., 2016; Osa et al., 2018), offline RL (Zolna et
al., 2020), or by abstracting RL away to treat the problem as one of data-
driven sequence modeling Chen et al. (2021). Using human data in this way it
is possible to resolve the chicken-and-egg problem of RL. You need not first
emit a behavior before it can be reinforced if real humans provide the stream
of experience (Abramson et al., 2020).

In their own ways, all the aforementioned approaches have been motivated via
the sparse reward hypothesis concerning the difficulty of engendering
exploration deep enough to build cognitive abilities. The central hypothesis
motivating much of the AGI-oriented MARL research on the other hand is quite
different. In MARL it is natural to cast the problem not as sparse reward, but
rather as premature convergence to local optima that are not good enough. Even
bad local optima, if isolated from the better regions of policy space by vast
intervening regions that are even worse, create basins of attraction that are
difficult to escape once entered. In MARL these local optima are also
associated with equilibria. Other players will be acting in some fashion that
creates a local part of policy space with an incentive structure from which
gradient-guided learning cannot escape. The problem of exploring deeply enough
to build cognitive abilities is thus recast for MARL as a problem of
equilibrium selection (Harsanyi et al., 1988; Gintis, 2009). A similar
perspective prevails in the study of ecosystem evolution (e.g. Swenson et al.
(2000)) and game theoretically informed political philosophy (Sugden et al.,
1986; Binmore et al., 1994; Skyrms, 1996; Gintis, 2014). Successful
origination of significant new innovations entails adaptive radiation in niche
space (Boyd et al., 2011; Leibo et al., 2019b).

The critical factors controlling multi-agent joint exploration are thus which
equilibria exist in joint policy space and how smooth and traversable are the
non-zero gradient paths that link them to one another. Both are determined by
the interaction of physical and social properties of the simulated system.
Physical properties include the simulated landscape. Social properties include
the numbers of other agents as well as their tastes and preferences. In light
of this, MARL researchers have considered a variety of different basic models
of the multi-agent learning problem (Shoham et al., 2007), often stressing
just one component (e.g. physical or social) at a time. One basic distinction
is between algorithms that assume the “rules of the game” are _not_ given
(incomplete information, large worlds), in which case they must explore to
discover them; versus those that assume access to a perfect simulator of the
game (or world) dynamics. The latter is often called the _planning_ setting
and it includes recent work on games like poker and go (Silver et al., 2017;
Bowling et al., 2015; Moravčík et al., 2017; Brown and Sandholm, 2018; Bard et
al., 2020). The present paper is concerned with the former case: settings
where exploration is needed to discover the dynamics of the world.

Most prior multi-agent reinforcement learning research on complex social
situations where it is necessary to explore falls into one of the following
three categories:

  1. 1.

Pure conflicting interests (zero sum games)

  2. 2.

Pure common interest (pure coordination games)

  3. 3.

Mixed motivation settings such as sequential social dilemmas and bargaining
problems

Lately there has been a push to consolidate all these disparate strands of
research into a single combined benchmark called Melting Pot, the idea being
that MARL algorithms ought to be generic enough to work across all three
categories (Leibo et al., 2021).

###  2.2 Pure conflicting interests

Exploration is often facilitated in zero sum games as a result of “arms race”
type learning dynamics—called exogenous autocurricula in the terminology of
Leibo et al. (2019a). For instance, in one project agents were trained to play
a team-based first-person shooter computer game based on Quake 3 (Jaderberg et
al., 2019). The game was 2v2 Capture the Flag. Doing well in this game
requires agents to develop “martial” skills such as aiming, chasing, shooting,
dodging behind cover, and competitive strategizing, as well as navigation and
memory skills like exploring to find the opposing team’s flag and remembering
a quick path to bring it back to the goal, and cooperation skills to work
effectively with a teammate. Learning of these skills was driven by the need
to continually outperform opponent teams. Since all teams trained
simultaneously, there would usually be, for any given agent, another in the
population at an appropriate skill level such that learning to defeat them
would convey valuable lessons. When an agent’s performance is weak or overfit
to a particular situation or opponent, other agents in the co-training
population learn to exploit them, thereby incentivizing them to unlearn the
aspects of their behavior that cause it to perform poorly. In this way, the
training process becomes self-correcting and may accumulate new innovations
over time. Bansal et al. (2018) applied a similar approach to a 3D sumo
wrestling game with simulated physics. In practice, successful co-adaptation
algorithms for pure conflict settings generally play not just against the
latest (and strongest) policy, but also against as large and diverse as
possible a set of older policies (Lanctot et al., 2017; Balduzzi et al., 2019;
Czarnecki et al., 2020). This is the same insight underpinning the successful
Nash league approach to Starcraft II Vinyals et al. (2019). Among poker
researchers and professionals (who similarly learn from experience), such
interactions are described with the phrase: “When you exploit your opponent,
you are also teaching them.”.

Some of the most impressive examples of innovation arising from competitive
multi-agent co-adaptation are in cases with asymmetric agent roles. For
instance, the interactions of adversarial setter and solver agents can be used
to motivate substantial exploration (Sukhbaatar et al., 2018), an idea that
was also applied impressively to robotics applications (OpenAI et al., 2021).
Also, a team from Open AI showed that a population of co-adapting agents
playing the game of hide-and-seek were driven to discover tools and how to use
them strategically in their environment (Baker et al., 2019).

###  2.3 Pure common interest

Unlike pure conflict situations where co-adaptation effects are often helpful
to exploration and generalization, in pure common interest settings co-
adaptation usually has the opposite effect. When your task is to cooperate
with a partner, finding a good response to their current policy
_disincentivises_ them from further exploration. Thus partner agents overfit
to each other’s quirks, which causes them to generalize poorly and not explore
enough. Accordingly, recent research in this area has been directed toward
generating agents capable of adapting on the fly, _e.g_. by metalearning (Duan
et al., 2016; Wang et al., 2016), so that they can then coordinate with a
diverse set of other teammates, who might even be human in some cases (Carroll
et al., 2019; Wu et al., 2020; Strouse et al., 2021).

Another line of work on situations of pure common interest is concerned with
emergent communication and signalling systems. For instance, Foerster et al.
(2016) studied the benefits of using a differentiable communication channel to
pass information between agents and Lazaridou et al. (2017) studied how
emergent communication patterns in referential games can be grounded in
natural language by co-training networks on both an interactive task (a multi-
agent referential game) and a passive task (supervised image-labeling task
with natural language image labels). More recent work in this area considered
zero-shot coordination protocols where agents must adapt to new partners who
may have learned different “languages” (Bullard et al., 2020; Zhu et al.,
2021; Hu et al., 2020).

One especially relevant strand of this literature concerns communication that
is intrinsically grounded in the semantics of the underlying game and thus is
not “cheap talk” (Lewis et al., 2017; Cao et al., 2018). In this line of work,
communication is regarded as negotiation over how to divide a set of items. It
is a temporally extended interaction because agents make a sequence of
proposals, continuing until acceptance, whereupon rewards are provided to both
agents according to their preferences for each item and their agreed split.
Agents have different preferences over the items from one another, and do not
know each other’s preferences. Thus it is possible to negotiate cleverly and
thereby capture a larger share of reward for oneself. Initially Cao et al.
(2018) found that it was necessary to modify the reward function to force
agents to be prosocial by having them optimize the collective return (sum of
both players’ rewards). However, more recently Noukhovitch et al. (2021)
showed how that restriction could be lifted, turning the environment into a
mixed motivation setting, the class of environments featuring both competitive
and cooperative motivations to which we now turn.

###  2.4 Mixed motivation settings

Several new concepts are important for describing how physical and social
properties of multi-agent systems jointly cause the emergence of mixed
motivation incentive structures. On the physical side, the concept of a
resource is useful for explaining how environments differ from one another.
Following Ostrom (2005)’s schema, we classify resources along two dimensions
excludability and subtractability (Table 1). Excludability refers to how
efficiently users of the resource may be excluded from accessing it. For
example, I can exclude others from accessing resources in my home by locking
the door, but I cannot exclude others from accessing the fish in the harbor
without some extraordinary intervention like sending naval vessels to blockade
it. Subtractability refers to the degree to which one user obtaining a benefit
from the resource depletes the amount of resource remaining. For instance, a
hamburger is a subtractable resource because once I have eaten it it is gone.

| Exclusion is Feasible | Exclusion is Not Feasible
---|---|---
4 Subtractable | private goods | common-pool resources
Non-Subtractable | club goods | public goods
Table 1: Classification of resources by excludability and subtractability
properties (adapted from Ostrom (2005)). A resource is excludable when it is
possible to exclude another agent from accessing it. A resource is
subtractable when consumption by one agent reduces the amount available for
consumption by others. Standard examples of different categories of resources
are: public safety (public good), clean drinking water (common-pool resource),
cable TV channel (club good), and housing (private good).

Non-excludability makes individuals interdependent. Actions to consume or
produce non-excludable resources typically have externalities. That is, the
choices taken by any one individual have an effect on many others. Non-
excludable resources are thus often associated with social dilemmas (Ostrom,
2005). Social dilemmas are situations where there is a tension between
individual and collective rationality (Kollock, 1998). They have been studied
in game theory for decades and more recently generalized to sequential social
dilemmas to enable their study in more complex environments containing spatial
and temporal structure and dynamics using MARL (Leibo et al., 2017).

Resources that are both non-excludable and non-subtractable are called public
goods (Ostrom, 2005), see Table 1. Real life examples include clean air and
national defense. Groups often face situations where they must invest in order
to provide a public good. In such situations it is possible for individuals to
free ride: benefiting from the work of the others without working oneself.
Thus situations calling for public good provision are generally rife with
social dilemmas that, when they go unresolved, produce incentives— _i.e_.
individual policy gradients—pointing toward under-investment relative to the
socially optimal amount of investment. McKee et al. (2021) studied a
sequential social dilemma game called Clean Up that models an irrigation
dilemma in which food only grows if an aquifer is clean, so at least some
individuals must expend time and effort to clean it, an activity that
contributes to the public good. However, all face incentives to free ride by
standing away from the aquifer, near where the food will grow, waiting for
others to do the hard work of cleaning so that they may enjoy its benefits
without contributing any of their own work. McKee et al. (2021) found that
humans are only able to find cooperative solutions to Clean Up when they can
easily track one another’s identity and reputation for contributing to the
public good. Generic self-interested deep RL agents failed to learn to
cooperate regardless of whether they were in anonymous or identifiable
conditions. The authors then showed that by endowing the agents with an
inductive bias encoding the concept of competitive altruism (Hardy and van
Vugt, 2006), their results then resembled the human results: failure to
cooperate in the case of anonymous players but success in the case of
identifiable players with salient reputations.

Any resource that is non-excludable and subtractable is called a common pool
resource (Ostrom, 2005), see Table 1. In this case, when individuals act
selfishly, they may destroy a surplus that would otherwise accrue to all
(Ostrom, 1990), for instance by over-consuming and thereby destroying
resources on which all would otherwise benefit. Examples include common
grazing pastures, fisheries, and forests. In each it is difficult or
impossible for individuals to exclude one another’s access. But whenever an
individual obtains a benefit from such a common-pool resource, the remaining
amount available for appropriation by others is at least somewhat diminished.
For example, the overall fish stock is reduced whenever you remove fish from
the sea; the trick is to appropriate _sustainably_ by removing fish more
slowly than their natural birth rate replaces them given the size of the
existing stock. If each individual agent’s marginal benefit of appropriation
exceeds their share of the cost of further depletion, then they are predicted
to continue their appropriation until the resource becomes degraded. This
inexorable logic is called the tragedy of the commons (Hardin, 1968; Ostrom,
1990). It is typically impossible for an individual acting unilaterally to
escape this fate; since even if one were to restrain their appropriation, the
effect would be too small to make a difference (assuming the group is large).
Thus individual-level innovation is not sufficient to evade the tragedy of the
commons. Any group-level innovation that resolves such a social dilemma must
involve changing the behavior of a critical fraction of the participants
(Schelling, 1973).

Common pool resources give rise to situations where agents face incentives
that guide their exploration in a systematically self-defeating direction. For
the sequential social dilemma game “Commons Harvest”, first introduced in
Perolat et al. (2017), agents that emit random actions typically get higher
scores than agents who have begun to learn. However, there are endogenous ways
by which agents can, through their learning, come to alleviate the effect of
these perverse incentives. Suppose that, by building a fence around the
resource or some other means, access to it can be made exclusive to just one
agent. That agent is then called the owner and the resource is called a
private good (Ostrom, 2003), see Table 1. The owner is incentivized to avoid
over-appropriation so as to safeguard the value of future flow of benefits
from the resource from which they and they alone will profit. Such effects are
recapitulated in these models. Agents learn strategies wherein they exclude
others from a portion of the resource. Then, in accord with predictions from
economics (Ostrom, 1990; Acheson and Gardner, 2005; Janssen and Ostrom, 2008;
Turner et al., 2013), sustainable appropriation strategies emerge more readily
in the “privatized” zones than they do elsewhere.

The different incentive structures of Clean Up and Commons Harvest have myriad
implications. For instance, they respond differently to sanctioning
motivations. Inducing agents to police one another’s behavior by making (some
of) them averse to disadvantageous inequity leads to cooperation in Commons
Harvest but not Clean Up. In Commons Harvest, agents must learn to associate
their overconsumption with negative consequences. Disadvantageous inequity
averse agents feel incentivized to punish the agents who consume the most
resources the most rapidly. The punishment pattern thus provided is sufficient
to teach restraint, which is cooperation in Commons Harvest. On the other
hand, disadvantageous inequity aversion is ineffective for Clean Up because it
doesn’t actually signal what the agent needs to positively do. It merely
communicates what _not_ to do rather than what _to_ do. There is not enough
information in the disadvantageous-inequity-aversion-induced pattern of
punishment to build a whole new behavior this way (Hughes et al., 2018).

Beyond inequity aversion, there are a range of other agents and learning
mechanisms capable of resolving sequential social dilemmas. Several of them
are algorithmically similar to the inequity aversion mechanism; they work by
replacing purely self-interested individual reward functions with reward
functions that take the rewards of other agents into account (Gemp et al.,
2020; McKee et al., 2020; Baker, 2020). Other work in this vein extended the
reward function modification method by coupling it to population-based
training (Jaderberg et al., 2019) so that the reward functions themselves can
evolve over the course of training (Wang et al., 2019a). The authors used this
model to study the conditions under which the more altruism-promoting reward
functions could evolve and found their best results in a case resembling group
selection, in accord with the expectation from evolutionary theory (Nowak,
2006). Another prominent and rather different approach is based on the concept
of reciprocity. Famously in iterated prisoners dilemma, agents are
incentivized to cooperate if their partner always punishes defection by
defecting themselves (tit-for-tat Axelrod (1984)). Both Kleiman-Weiner et al.
(2016) and Lerer and Peysakhovich (2017) describe hierarchical MARL agents
where a hard-coded high-level controller implementing tit-for-tat decides
whether to play a cooperating policy, trained with joint reward, or a
defecting policy, trained using the default self-interested rewards. Eccles et
al. (2019) explored a different way of achieving cooperation via reciprocity:
learn to recognize the “niceness level” of other agents’ policies and then
imitate their niceness level back to them. This approach performed well on
both Clean Up and Commons Harvest.

The concept of heterogeneous preferences is important for MARL in mixed
motivation settings, and will be especially important in the present paper. We
regard an individual’s taste as their own private information concerning the
utilities they may place over the set of possible outcomes. Taste differences
between agents give rise to bargaining problems. One recent paper considers
normative disagreement as a bargaining problem (Stastny et al., 2021). Other
work considers the case of multiple mutually exclusive public goods with
complex spatial and temporal dynamics using MARL (Köster et al., 2020;
Vinitsky et al., 2021). These interlinked collective action problems admit
more than one way to cooperate, but agents have divergent preferences over
which way is best. In this case, uncoordinated cooperation may be no better
than mutual defection. Heterogeneous preferences make these social-dilemma-
like bargaining situations more difficult. However, in the more
straightforward bargaining setting of the present work, heterogeneous
preferences will have the opposite effect. Agents can gain surplus utility by
trading with one another precisely because they have different tastes for the
various items in their world.

In the environment considered in the present work, Fruit Market, the
underlying resources are both excludable and subtractable; thus they are
classified as private goods (Ostrom, 2005). Also, agents have heterogeneous
preferences. Thus Fruit Market falls into a part of the mixed motivation
design space that has not been explored much in prior MARL work. For instance,
Fruit Market is not a social dilemma. However, it is closer to the incentives
structures often studied in agent-based computational economics—the field to
which we now turn.

###  2.5 Agent-Based Computational Economics

In economics, Agent-based Modeling (ABM or AB) or Agent-based Computational
Economics (ACE) are approaches to predicting and understanding the behaviour
of economies through the interaction of individual agents (Tesfatsion, 2021,
2006; Richiardi, 2017, 2014). Unlike statistical approaches that model real
data, or theoretical approaches that assume a population’s convergence to
equilibrium, agent-based approaches model the behaviours and incentives of
independent entities (_e.g_. firms, families, or individuals). The goal of
this approach is to model and understand the emergent population-level
economic phenomenon from the interaction of smaller components, without the
rationality and consistency assumptions needed by approaches that assume
equilibrium behaviour.

While the architecture of an ABM or ACE computational experiment appears to
have much in common with MARL (one environment process which many individual
agent processes connect to), their different objectives lead to different
choices in the environments and agents. For example, for agent-based economic
models to be useful, their agents’ individual behavior should be simple. Hand-
crafted and non-adaptive rules-based agents are commonly used. This is
suitable for purpose because the focus is on generating surprising population-
level results. Complex population-level effects often arise from simple
individual behaviors. When adaptive or learning agents are used, their
behaviour may appear constrained (from a MARL point of view) to only choose
somewhat reasonable actions. ABM and ACE models emphasize the interaction
between agents more so than the architecture or learning abilities of the
agents themselves. In contrast, in MARL research, it is the agents and their
learning dynamics that we are most concerned with, and we usually do not
require our agents to accurately model any real-life or rational behaviour, so
long as they earn reward. With that distinction in objective noted, however,
we found the ACE modelling principles proposed by Tesfatsion to be well
aligned with MARL objectives (Tesfatsion, 2021, Section 2), and also note the
aspiration to environments complex enough to support the emergence of
generally intelligent agents (Tesfatsion, 2021, Section 6).

Several decades of prior work in economics used agent-based models to study
trading between agents, as we do in this work. However, as with any scientific
model, including ours, the problem is abstracted from the real life setting to
create a simpler and more tractable model that excludes extraneous details.
For example, models in ABM, ACE, and economics-themed MARL environments may
make simplifying choices in the following aspects, each representing a
spectrum of options:

  * •

Production. Do agents decide what and how much to produce? Alternatively, are
they automatically granted goods at the start of each episode, or are
production decisions only represented at a very high level to focus attention
on trading?

  * •

Consumption. Do agents make choices about what and how much to consume, or are
all goods automatically consumed as a “bundle” at the end of each episode? Are
goods only consumed for immediate reward, or can agents also use them in other
ways, such as saving them for future consumption, or selling or trading them
to earn more reward?

  * •

Trade Prices. Do agents choose what prices to buy and sell goods at, or what
offers to make when negotiating with other agents? Alternatively, are the
agent’s prices determined automatically (_e.g_. at the midpoint of two trading
agents’ marginal utility functions), or does the environment calculate one
optimal price (_e.g_. a Walrasian equilibrium price) and enforce its use by
all agents?

  * •

Trade Partners and Interaction. Do agents choose which specific other agents
to negotiate and trade with? Are agents restricted to only trade with other
predetermined “nearby” agents according to an adjacency graph, or can they
trade with anyone in the population? Do agents interact directly with each
other to exchange goods by using a sequence of actions, or does the
environment facilitate trading by swapping their goods in one atomic step, or
do agents submit bids and asks to a local or global “order book” in the
environment which pairs them up and exchanges goods automatically, without
direct interaction?

  * •

Trade Quantity. Do agents decide how many goods to buy and sell at a chosen
time and price, thus allowing strategic decisions (_e.g_. hold some back to
consume for reward, or to trade in the future if prices improve)?
Alternatively, is the quantity decision automated, or do agents always sell
all of their goods (if possible) after selecting a price, or are the goods
being sold valueless to the agent such that they should always be sold at any
available price?

  * •

Spatial granularity. Does the environment have spatial dimensions, such that
some agents, resources, or other entities are closer together than others? Are
agents fixed in one location, or can they move through space, requiring
decisions about where to produce and trade goods? Are spatial locations
represented as discrete states representing nations, cities, square
kilometers, square meters (about a person-sized area), or smaller (_e.g_. does
the environment represent the difference between a player holding an apple in
an outstretched hand suggesting a gift, versus the player carrying that same
apple in a backpack)? Alternatively, is space essentially continuous (_e.g_.
modelled at an extremely fine granularity) but with the relevant players and
entities represented at one of those larger resolutions? Alternatively, is
space removed as a consideration, and all agents are “in the same location”
(_e.g_. in one room, or online) while they interact?

  * •

Temporal granularity. Is each episode represented as a single timestep, where
players take one action and then see a result? Does the interaction take place
over a number of discrete rounds where players take specific types of actions
(_e.g_., all players commit to production levels, then all players choose
prices to sell goods at, then all goods are sold and players receive their
payouts)? Alternatively, are episodes a long series of discrete (potentially
fine-grained) timesteps where players choose arbitrary actions? Does each
timestep represent a time interval on the order of months, days, minutes,
seconds, or less (approaching continuous time)?

  * •

Observation richness. Do all agents observe the true state of the environment,
or does each agent have a private observation (_e.g_. as in an imperfect
information game such as poker) that provides each agent with their own
perspective? Does the observation contain only a small number of highly
relevant state variables, or is the observation a rich and multimodal set of
sensory inputs, such as egocentric (the world appears to move around the
player, whether first-person or top-down) or allocentric (the player moves
through the world) visual data represented by pixels?

  * •

Model provided. Are agents given a perfect model of part or all of the
environment to use for planning, or must they learn their behaviour (or build
their own internal model) from experience? A common case is the agent’s
knowledge of their own utility function: is reward granted through some known
function that can be tractably optimized (_e.g_. a Cobb-Douglas utility
function444A Cobb-Douglas function is of the form
$f(\vec{x})=\prod_{i}x_{i}^{\lambda_{i}}$, where $x_{i}$ is an expenditure on
good $i$ and $\lambda_{i}$ is an elasticity constant for that good: whether
there are increasing or diminishing returns for having more of it. Cobb-
Douglas functions can be used to model an agent’s production or utility
objectives; both involve choosing a bundle of goods to consume in order to
maximize some value. As a utility function, an agent might need to divide
their budget between expenditures on food and housing, where spending zero on
either good gives zero utility, and the optimal allocation can be computed
tractably.), or does the agent have an unknown utility function and must learn
what behaviours grant reward through trial and error?

  * •

Agent quality. Are the agents simple programs written by hand to produce a
desired behaviour, such as decision trees or state machines? Do they optimize
a small number of internal parameters to adjust to recent conditions, without
deviating too far from a predetermined policy? Alternatively, are they
reinforcement learning agents that learn arbitrary behaviours from their own
experience, and so might perform randomly, poorly, or unrealistically early or
even late in training, but might also discover effective behaviours on their
own, or innovate new behaviours that would have been too difficult to program
in manually?

The best choices for each of these aspects depends on the research goal being
pursued. If the goal is to model a specific real-world scenario with agents,
it makes sense to manually design the agents to encode or stay close to the
desired behavior reflecting how the real-world agents behave, and to simplify
the environment to expose only the most salient factors and decisions. There
is no need to use computationally expensive state-of-the-art deep
reinforcement learning agents that learn their own policy from experience, if
you can already program in the specific (and economically rational) behaviour
that you want them to use, and only intend to study the emergent population-
level phenomenon arising from those simple agents. Much of the related work we
have encountered uses simple environments and agents in order to study such
emergent population-level behaviours. We will briefly note several examples
here, focusing on abstract environments that attempt to investigate trading
behaviour itself, and not on work that attempts to model real-world economies
or behaviours. After this, we will describe in more detail the recent “AI
Economist” work Zheng et al. (2020) that we believe is the closest comparison
to our work because both use deep reinforcement learning agents.

In an introduction to ACE, Tesfatsion (2006) describes an environment called
“The ACE Trading World”. The environment has two resources (hash and beans)
and money, and three types of agents (hash-producing firms, beans-producing
firms, and consumers). The environment has no spatial component and takes
place over a series of discrete time periods, where agents make specific types
of decisions. The firms start by choosing how much of their resource to
produce and what price to charge, and then consumers attempt to buy bundles of
hash and beans to maximize their utility, purchasing the lowest-priced goods
first. The process then repeats, with agents updating their internal models of
the predicted availability and price of each resource. The environment is used
in two settings: one that is not agent-based and instead uses a “Walrasian
Auctioneer” to calculate the equilibrium quantities and prices, and another
that instead uses agents that learn to make these production and pricing
decisions independently. In this work, Tesfatsion stresses the importance of
agent survival in ACE models: in this environment, firms that become insolvent
and consumers that fail to meet their subsistence needs are removed from the
simulation, so that only successful agents remain. Where standard economic
models focus on the behavior of economies operating at equilibrium and
“survival is assured as a modeling assumption”, Tesfatsion sees ACE models as
stressing the agents’ ability to both survive and prosper (Tesfatsion, 2006,
Section 4.2).

In a set of related papers, Albin and Foley (1992), Wilhite (2001), and Venkat
and Wakeland (2010) studied the impact of spatial layouts of agents on trade.
These works considered large sets of agents and adjacency graphs describing
which pairs of agents were close enough to trade, and in Venkat and Wakeland
(2010), a distance between those agents used for a transaction cost. Thus,
space was represented discretely and abstractly, and agents could not move.
The environments each used two goods and did not involve money; instead,
agents exchanged goods with each other when trading would immediately improve
both of their utilities. The experiments did not include agent choices about
production (agents were granted a random mix of the two goods at the start of
each episode), consumption (each agent $i$ optimized for a known Cobb-Douglas
utility function, $U^{i}=g_{1}^{i}*g_{2}^{i}$, with all items consumed at the
end of the episode), or the prices that they traded goods at (the price in
each trade is automatically set to the midpoint of the two agents’ marginal
utilities for the goods). In Albin and Foley (1992), the agents were arranged
in a circle, and received a random mix of each good, with 100 items total. The
agents could choose to pay a cost to advertise (within $r$ steps around the
circle) their intent to trade, and two nearby agents wanting different items
would reveal their marginal utilities and trade goods at the midpoint price,
making both better off. Trading continued in this way until no agents chose to
advertise offers. This decentralized approach involves trades happening at
prices other than the equilibrium price (which would equally value both
goods), and wastes some goods through advertising, but still converges to an
allocation of goods across the population that is more rewarding than the
initial random allocation. In Wilhite (2001), a similar arrangement of agents
in a circle is used, but the emphasis is on the effort required to pick
trading partners: similar to the computational cost of $O(n^{2})$ for two
nested for loops to consider all pairs of agents. If all agents are adjacent
then the allocation of goods is efficient, but it is computationally expensive
to find trading partners; when agents are arranged in local neighborhoods each
exchange requires less computation to find the best partner, but more total
trades are required for goods to flow through the network. By adding a small
number of edges across the graph to reduce its diameter (analogous to
merchants who connect otherwise distant areas), the goods are allocated
quickly and efficiently. Venkat and Wakeland (2010) examines a case where
agents are arranged in a grid, and the random mixture of goods that each agent
starts with varies between the east and west halves of the map. Agents can
trade with anyone but with a linear cost determined by the distance between
them. This distance cost largely determines how efficient the resulting
allocation of goods is: as the cost increases local prices persist (caused by
the initial skewed distribution of goods), and the collective utility of the
agents drops quickly.

Manson et al. (2020) presents a survey of ACE models that involve dimensions
of time and space, and notes several of the challenges in using such models in
practice. The authors describe different approaches for how space can be
represented in the environment and observed by the agents. For example, space
can be represented in an absolute way (coordinates, fixed locations for
objects and entities), in a relative way (focusing on the relationships
between nearby objects), or abstractly as a graph or network (Manson et al.,
2020, Section 3). Specifically, the authors note possible representations of
space for the agents: a tiling to discretize space and represent the entities
contained in each tile, or a “vector data model” that represents entities as
objects in the object oriented programming sense: a collection of coordinates
and data elements, perhaps using lines or polygons to describe regions. This
is very different from the standard approach in recent deep multi-agent
reinforcement learning, where the environment’s internal state representation
might be entirely independent of, and not at all similar in format to the
agents’ observations or their internal representations. For example, a MARL
environment may indeed use an object oriented approach to represent the agents
and objects it contains; however, the agents are normally given a vector,
image (pixel matrix), or multi-modal observation on each timestep, and the
agent’s internal representation of that observation is learned from
experience. Any internal representation of space, therefore, is not chosen by
the programmer but is instead learned and possibly different for each agent in
the population.

The challenges in using spatial agent-based models decribed by Manson et al.
(2020) are collected from twenty years of prior work. Recurring themes include
validating that models reflect the desired real world scenario, difficulty in
programming the models and agents and integrating them with data sources such
as GIS systems, and in communicating or sharing the models with other
researchers. Similar problems are also described by Richiardi, who describes
agent-based models as often lacking empirical grounding, being poorly
documented and hard to replicate, and being hard to program and re-use
(Richiardi, 2017, Page 2). These difficulties in programming and reuse are not
surprising if the agents in agent-based models are implemented as a hand-coded
collection of rules and state transitions. The use of reinforcement learning
agents may help in some of these aspects and cause extra difficulty in others.
For example, programming a deep reinforcement learning agent is initially a
difficult programming task, but once implemented can potentially be shared
with other researchers and reused in a wide range of environments with no
further programming time, at the cost of requiring training time in each
environment. On the other hand, such MARL agents would have no guarantees at
all about producing behaviour aligned with the real-world behaviour being
modelled, making validation and interpretation of results even more difficult.

The papers we have mentioned thus far largely use simple and handcrafted
agents instead of such MARL agents. This is unsurprising as the above papers
predate the advances in deep learning, deep reinforcement learning, and MARL
throughout the 2010s. Tesfatsion does mention reinforcement learning, deep
learning, and neural networks in the 2021 survey and ACE resource webpage
(Tesfatsion, 2021, 2022). However, with a few exceptions, in our literature
review we have largely not found recent application of deep learning or deep
reinforcement learning techniques. One exception is a survey by van der Hoog
(2017), which proposes possible applications of deep learning to agent-based
economic models. These proposals largely focus on training a deep learning
model to emulate the policy of an agent from data, or to emulate an entire
agent-based model (van der Hoog, 2017, Page 2). In particular, an agent-based
model using millions of agents would be computationally expensive to operate,
and a single deep learning model might be trained to approximate the behaviour
of that multi-agent system, at a much lower computational cost. This would use
deep learning to avoid a computationally expensive multi-agent simulation,
whereas in this work we use (computationally expensive) deep learning for each
agent within such a simulation. However, the survey also briefly mentions uses
such as ours: creating agents with rich cognitive structure and internal
models of the environment, allowing for social interaction between agents (van
der Hoog, 2017, Page 6).

###  2.6 AI Economist

Of the related work in the field of agent-based computational economics, the
recent “AI Economist” work by Zheng et al. (2020) is the most closely related
to this paper. Both our paper and theirs use deep reinforcement learning for
agents in a 2D environment, thus emphasizing environmental richness and agent
quality. From our perspective, we see our paper as “Economics for MARL”
whereas the AI Economist paper is “MARL for Economics”. This difference in
objective leads to different choices in environments and agent training. The
goal of the AI Economist work is to discover optimal tax policies to impose on
a population of agents, in order to find the Pareto-optimal tradeoffs between
the population metrics of equality and productivity. To do this, two types of
agents are trained at once: a population of low-level agents that learn to
produce, buy, sell, and consume resources, and a high-level planner agent that
designs tax brackets to trade off between the population metrics. The main
contribution of the work is to the field of economics, demonstrating that the
high-level planner agent can choose tax brackets that better balance
productivity and equality than conventional methods, while also being robust
to behaviour changes by the low-level agents. Overall, the work demonstrates
that deep learning agents can be a powerful component of an agent-based model
for economics research.

To support that goal and contribution, the authors made several reasonable
choices for the environment and agents. In the environment, the players buy
and sell two types of building material (wood and stone) using coins, and
coins grant reward when carried but cannot otherwise be used or consumed. The
building materials are used to build houses, and the builder is given coins by
the environment for doing so. Thus, the environment builds in a priori
knowledge of currency and an incentive for players to collect it. To
facilitate trading between agents, the environment operates a global order
book, allowing them to enter bids and asks that are fulfilled automatically,
without requiring the trading agents to be nearby or to interact directly.
This global order book also helps agents to explore the bid and ask actions to
discover trade: the agents’ joint exploration problem is easier when each
agent can individually try their actions when separated in space and time,
instead of having to explore when nearby and acting simultaneously. However,
this also cuts off some interesting areas of investigation, such as the
possible emergence of different prices for goods in different regions
reflecting the local demand or abundance of resources, discovery of
conventions by agents such as a “marketplace” area where they might meet up to
trade, or the necessity of labour to transport goods from the production site
to a trade partner and from there to the house building site.

On the agents side, the training procedure only trains a single set of agent
parameters that is shared by all of the low-level agents. Each agent in the
environment has their own private state (skills, observations, hidden state,
and so on) and so still act differently from each other in order to maximize
their individual reward. However, since all agents share one set of learned
parameters, there is no notion of one agent learning a behaviour before, or
more effectively, than their competitors. Training a single agent that
interacts with many copies of itself, as they do, also simplifies the learning
problem in environments that require joint exploration to discover a
convention (_e.g_. a standard price). Once two copies of the agent randomly
explore their bid and ask actions and experience a trade for the first time,
all of the other copies of the agent can immediately begin exploring those
actions intentionally and simultaneously, making future trades much more
likely to occur. If many individual agents were trained instead, like we did,
then each agent would have to discover the behaviour through their own
exploration, albeit with later agents being more likely to find a trade
partner because early adopters would already be trading with each other.

All of these environmental and agent choices are reasonable ways to make agent
training efficient. They may also encourage the development of economically
rational and interpretable behaviour in the low-level agents and the tax
policy planner.

###  2.7 Comparison to this work

Our goal in this work is to study the emergence of trading and rudimentary
microeconomic behaviour with as little a priori knowledge introduced as
possible. Following the bullet points in 2.5, we emphasize the aspects of
environmental richness (spatial and temporal dimensions, and with visual
observations), requiring agents to learn about production, consumption,
prices, quantities, and partners, and using a population of independent state-
of-the-art deep reinforcement learning agents. Unlike the related work that we
have described, we do not require that our agents’ behaviour after training
matches any real-life or theoretically optimal behaviour. We are interested in
if and how current agents can learn these skills, not whether they closely
converge to an expected equilibrium behaviour.

While we do hope that our agents will learn behaviour that appears
economically rational, there is no guarantee that this approach will succeed
in producing a useful economic model. State-of-the-art agents could fail to
learn any useful behaviour555In Section 6.3 we present results using an
alternative agent architecture, only a few years older than the state-of-the-
art agent we mainly investigate. This older agent architecture largely obtains
the worst possible episodic reward in our environment. So learning to trade in
Fruit Market is not at all a trivial AI problem., could earn reward but only
as individuals that produce and then consume goods and not through interacting
to trade those goods, could learn to trade but not to adapt their prices to
differing environmental conditions, or could in fact learn to make decisions
in accord with microeconomics of supply and demand. All of these outcomes are
interesting for MARL research, but only the last could potentially make
contact with rationality-oriented economics research.

Our environment differs from the related agent-based computational economics
work, and in particular from the AI Economist environment, due to our goal of
learning microeconomic behaviours from scratch. In our environment, agents
learn to barter goods for goods, with no hard-coded notion of currency, coins,
or of one good being a special numeraire good used as the basis for valuing
other goods, unless the agents adopt such a convention on their own (something
they did not yet do, but perhaps could in future work). Rewards are granted
instantly for fundamental causes such as consuming tasty fruit or suffering
hunger pains, instead of reward being granted at episode end through a known
Cobb-Douglas function, or granted on each timestep for carrying coins which
abstractly represent an agent’s overall well-being (_e.g_., coins representing
the ability to buy food and avoid hunger). In particular, we will highlight a
difficulty in agents learning to barter with a consumable good: once an agent
learns that they can consume a good for reward, they will begin to do so
whenever possible, and then have no goods left over with which to explore
trading them for something better. This difficulty cannot arise when the only
use for coins is to spend them.

Our environment does introduce some domain knowledge by facilitating exchanges
between agents who make offers. It is somewhat similar to the global order
book used in the AI Economist work (Zheng et al., 2020). However, instead of
one global order book, our environment considers potential offers in a small
radius around each agent. This captures a more embodied guiding intuition
where trades and prices are local and entail physical interaction between
nearby agents. For instance, agent i hands an apple to agent j, accepting a
banana in return. This permits effects such as the emergence of different
prices in different parts of the map, agents having to labour to transport
goods across the map to a buyer, and agents needing to find and closely
approach a trade partner in order to exchange goods with them. The agents
learn this mechanism even when agents must be directly adjacent to observe
each others’ offers and trade resources, requiring intentional actions by
agents to trade with one specific partner. Finally, unlike in AI Economist,
our population of agents is independent, each agent learns their own policy
through only their own stream of experience. They share no parameters and
never experience episodes where they interact with copies of themselves. This
permits each agent to learn a unique policy, for some agents to learn a
behaviour before or more effectively than others, and for some agents to
discover a niche created by other agents’ behaviours. For example, in some of
our experiments, a subset of the agents discover an “arbitrage niche” by
transporting goods between parts of the map to exploit a persistent price
difference. This behavior can only emerge once other agents have already
learned to trade goods in a way that, as a byproduct, creates the persistent
price difference which renders arbitrage rewarding.

##  3 Background

###  3.1 Markov Games

We consider multi-agent reinforcement learning in partially observable
general-sum Markov games (Shapley, 1953; Littman, 1994). In each game state,
agents take actions based on a partial observation of the state space and
receive an individual reward. The rules of the game are not assumed given;
agents must explore to discover how the environment can be controlled and
which behaviours lead to reward. Thus it is simultaneously a game of
_imperfect_ information—each player possesses some private information not
known to their adversary (as in card-games like poker)—and _incomplete_
information—lacking common knowledge of the rules (Harsanyi, 1967). Agents
must learn through experience an appropriate behavior policy while interacting
with one another.

We formalize this as an $N$-player partially observable Markov game
$\mathcal{M}$ defined on a finite set of states $\mathcal{S}$. The observation
function
$\mathcal{O}:\mathcal{S}\times\\{1,\dots,N\\}\rightarrow\mathbb{R}^{d}$,
specifies each player’s $d$-dimensional view on the state space. In each
state, each player $i$ is allowed to take an action from its own set
$\mathcal{A}^{i}$. Following their joint action
$(a^{1},\dots,a^{N})\in\mathcal{A}^{1}\times\\!\dots\\!\times\mathcal{A}^{N}$,
the state changes obeys the stochastic transition function
$\mathcal{T}:\mathcal{S}\times\mathcal{A}^{1}\times\\!\cdots\\!\times\mathcal{A}^{N}\rightarrow\Delta(\mathcal{S})$,
where $\Delta(\mathcal{S})$ denotes the set of discrete probability
distributions over $\mathcal{S}$, and each player $i$ receives an individual
reward defined as
$r^{i}:\mathcal{S}\times\mathcal{A}^{1}\times\dots\times\mathcal{A}^{N}\rightarrow\mathbb{R}$.

###  3.2 Reinforcement learning

Let $\mathcal{D}(\Omega)$ denote the space of distributions over the space
$\Omega$. A Markov Decision Process (MDP) (Howard, 1960; Sutton and Barto,
2018) is a tuple $\langle\mathcal{S},\mathcal{A},T,r,\gamma\rangle$ where
$\mathcal{S}$ is a set of states, $\mathcal{A}$ is a set of actions,
$T:\mathcal{S}\times\mathcal{A}\to\mathcal{D}(\mathcal{S})$ is a transition
function, $r:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is a reward function,
and $\gamma\in[0,1]$ is a discount factor. A mapping
$\pi:\mathcal{S}\to\mathcal{D}(\mathcal{A})$ is called a stochastic policy.

A partially observable Markov Decision Process (POMDP) is defined by the tuple
$\langle\mathcal{O},\mathcal{A},T,r,\gamma\rangle$, where each element of
$\mathcal{O}$ is a partial observation of a true underlying state in
$\mathcal{S}$. Typically, multi-agent settings are automatically POMDPs
because each agent does not have access to the observations, actions, policies
or rewards of their co-players (Littman, 1994).

Given a policy $\pi$ and an initial state $s_{0}$, we define the value
function
$V_{\pi}(s_{0})=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}\;r(s_{t},\pi(s_{t}))]$
where $s_{t}$ is a random variable defined by the recurrence relation
$s_{t}=T(s_{t-1},\pi(s_{t-1}))$. Reinforcement learning seeks to find an
optimal policy $\pi^{*}$ which maximises the value function from an initial
state $s_{0}$. We assume that the agent experiences the world in episodes of
finite length $T$. During training, our RL agent receives many episodes of
experience, and updates its policy to become closer to the optimal policy. We
use distributed training, running several environment instances in parallel
and aggregating the experience in batches for learning, resulting in a shorter
wall-clock time to convergence.

Reinforcement learning methods can be classified according to whether they
represent the value function as a table of exact values (tabular) or learn it
as a parametric function (function approximation). Although tabular methods
have better convergence guarantees, they are impractical when the state space
is large, as is the case in our 2D environment. As we will present in Table 2,
on each timestep our agents observe a mix of visual data (a [15,15,3] matrix
of pixels) and numerical data (representing inventories, offers, etc), making
any tabular approach too coarse to be of use. Therefore, we employ function
approximation in an actor-critic architecture, representing the policy and
value function by neural networks. The reinforcement learning update rule then
becomes an objective which is optimized using backpropagation.

The standard actor-critic architecture for our setting processes visual
observations of the environment with convolutional and then multi-layer
perceptron (MLP) layers. Any non-visual observations are flattened, and then
concatenated with the processed visual output to form a vector. This vector is
fed into an LSTM layer, which allows the network to retain information through
time. The output of this “torso” is fed into a policy head MLP and a value
head MLP, which produce action probabilities and state value estimates used
for training, respectively. A listing of the network architecture and agent
and training hyperparameters are provided in Appendix A.

We update our agent’s policy using value-based maximum a posteriori policy
optimization (V-MPO, Song et al. (2019)). This method is an approximate policy
iteration algorithm which uses expectation maximization (EM) under certain
constraints to estimate an improved policy. Approximate policy iteration has
two steps, policy evaluation and policy improvement. For policy evaluation, a
value function is learned online for a policy which is fixed for a certain
amount of experience $T_{\textrm{target}}$. The loss function for learning the
parametric value function $V_{\phi}^{\pi}(s)$ with parameters $\phi$ is

$\mathcal{L}_{V}(\phi)\propto\sum_{s_{t}}\left(V_{\phi}^{\pi}(s_{t})-G_{n}^{\pi}(s_{t})\right)^{2}\,,$
(1)

where the $s_{t}$ are drawn from a dataset of trajectories using the policy
$\pi$ and $G_{n}^{\pi}(s_{t})$ is the $n$-step bootstrapped return from
$s_{t}$, which uses the trajectory rewards for the first $n$ steps, and
subsequently bootstraps using the value function. From the learned value
function, we define the advantage function
$A^{\pi}(s_{t},a_{t})=G_{n}^{\pi}(s_{t})-V^{\pi}(s_{t})$ for each pair
$(s_{t},a_{t})$ in the dataset of trajectories.

The policy improvement step seeks to find the maximum a posteriori estimate
over policy parameters $\theta$ conditioned on the event that the new policy
is an improvement. To optimize towards this objective, V-MPO takes a two step
approach akin to expectation maximization under constraints. The expectation
step optimizes the tightness of a lower bound on the probability that the
policy is improved. The maximization step maximizes this lower bound, subject
to a trust region constraint that the improved policy should not deviate from
the old policy too much, as measured by the KL divergence. The policy loss
turns out to be a weighted version of the familiar policy gradient loss, viz.

$\mathcal{L}_{\pi}(\theta)=-\sum_{s,a}\psi(s,a)\log\pi_{\theta}(a|s)\,,\qquad\psi(s,a)=\frac{\exp\left(\eta^{-1}A^{\pi}(s,a)\right)}{\sum_{s,a}\exp\left(\eta^{-1}A^{\pi}(s,a)\right)}\,,$
(2)

where $\eta$ is a hyperparameter, automatically tuned by another loss
function. We refer the reader to the original paper for a full account of all
loss functions. In our ablation studies, we compare V-MPO with advantage actor
critic (A2C) (Mnih et al., 2016). Similar to V-MPO, this is an earlier
distributed policy-gradient algorithm using deep neural networks for function
approximation. The sequence of layers in our V-MPO and A2C networks are the
same, although our V-MPO agent uses more neurons in each layer, which we found
to result in higher reward with V-MPO but had no benefit for A2C.

###  3.3 Multi-agent reinforcement learning

In multi-agent reinforcement learning, a population of reinforcement learning
agents learn through interactions with each other in a shared environment. In
the literature, a range of options have been explored for how the agents are
represented and trained. For example: is there just one shared environment, or
several running in parallel; does each agent have their own set of parameters,
or are some parameters shared during training; how large is the population of
agents being trained, in comparison with the number of players participating
in each episode of the environment.

In this paper, we follow the independent reinforcement learning approach which
is standard in the recent MARL literature on sequential social dilemmas (Leibo
et al., 2017). We will train a population of 16 independent agents, which
learn only from their own stream of experience and do not share any parameters
with each other. Each agent is represented by a neural network and is trained
using the V-MPO algorithm. To train the population, we use a set of 800
environment processes running asynchronously in parallel. When each
environment process starts an episode, it randomly samples without replacement
a set of 10 agents from the population to participate as players. The streams
of experience from these many parallel episodes are sent back to the agents,
who train on it to update their policy so as to maximize reward.

Each experiment that we will present in this work involved training a new
population of agents from scratch, with no reuse of experience from earlier
experiments. In each experiment, we ran our distributed training framework
until the agents had experienced an average of $8108$ training steps.

To keep our terminology precise, we will use the term agent to refer to one
instance of an algorithm and its set of learned parameters. In contrast, we
will use the term player to refer to a position in the environment or game.
For example, an agent such as AlphaZero can learn to play as the white player
or the black player in chess; in any one game, AlphaZero is playing as the
black player or as the white player. The rules of the game of chess describe
what actions players are allowed to take, but have nothing to say about how
agents should choose those actions. Thus, when describing our environment’s
mechanics, observations, and actions, we will refer to players; when
describing learning, behaviours, and performance metrics, we will refer to
agents. Since an agent may play as many different players across their
episodes, we will describe an agent’s performance using metrics such as
“average reward per episode”.

###  3.4 Supply and Demand

In microeconomics, supply and demand curves provide a way of thinking causally
about the aggregate effects of individual production, consumption, and trading
decisions. Some number of agents produce a good for sale, and some others are
interested in purchasing that same good; these agents need not be mutually
exclusive. We refer to the interactions between these agents as a _market_.
For any set of environmental conditions (_e.g_., the abundance of goods, the
reward for consuming them, and so on), we expect learning agents (both human
and artificial) to converge to some equilibrium behaviour of production,
consumption, and the prices that goods are exchanged at.

Comparative statics is a way to study how changes to these environmental
conditions affect the set of equilibria that a population of agents can reach.
For example, we might run one experiment with an environment’s default
conditions, and measure the population’s equilibrium behaviour in terms of
metrics measuring production, consumption, and the price in exchanges. We
might change the environmental conditions (_e.g_., by making apples more
plentiful), train a new population of agents from scratch, and measure the new
equilibrium behaviour. Comparative statics is the practice of comparing these
static equilibrium points from different populations, without considering how
one might transition to the other under changing conditions.

Figure 1: Theoretical supply demand curve for our setting. The x-axis measures
the amount of apples produced, while the y-axis measures the price: the ratio
of apples demanded per banana. While the y-axis would usually measure prices
in a currency (_e.g_., dollars), our environment uses barter, where goods are
valued in terms of each other.

Supply and demand graphs are graphical depictions of possible equilibrium
points that a population might converge to under different conditions,
relating a population’s willingness to produce or consume goods to the price
they are be paid, or will pay, to do so. Figure 1 shows an example of a supply
and demand graph, and Chapter 4 of Mankiw (2020) is an excellent overview of
the subject. Note that the quantity of apples produced and consumed is on the
x-axis, while the price of apples is on the y-axis. The supply curve, $S_{p}$,
demonstrates how the number of apples produced changes with price: when the
price of apples is high individuals should produce more, and when the price is
low individuals should produce less. If apples are expensive, an individual
can get more in return for selling apples thus justifying additional labour to
produce them; likewise, an individual who desires apples might choose to
produce more apples themselves instead of paying the high cost. The demand
curve $D_{p}$ relates price and consumption: when apples are expensive
individuals will consume less _ceteris paribus_ , and if inexpensive will
consume more. The intersection point of the supply and demand curves,
indicated by $P_{e}$ and $Q_{e}$, is the equilibrium point where supply equals
demand, and is the behaviour that we expect agents to converge to.

A supply and demand graph allows one to predict how a population might respond
to changing environmental conditions. If apples are made more abundant, the
supply curve will shift right, leading to higher production at every price. If
nothing changes the desire to consume apples, the demand curve will not
change, and the new intersection point between the curves will have more
production and a lower price. If apples became less rewarding to individuals,
we could predict that all points on the demand curve would shift to the left:
lower consumption at every price, reflecting a lower willingness to pay for an
apple. The equilibrium will shift to a lower price with less production. See
Mankiw (2020) for a more detailed overview.

To generate a supply and demand graph as in in Figure 1, we use an empirical
approach. We choose an environmental factor related to supply, such as the
prevalence of apples, and run a number of experiments with differing values.
For each value, we train a new population of agents and measure the resulting
equilibrium behaviour. Every equilibrium point reveals an intersection of the
supply and demand curves; thus, by shifting the supply curve, the intersection
points reveal the shape of the _demand_ curve. Similarly, we vary an
environmental factor related to demand to shift the demand curve, and the
intersection points reveal the shape of the _supply_ curve.

Introducing these sources of variation is non-trivial. For one, price is not
an exogenous variable that the experimenter can manipulate directly; the
experimenter must manipulate other experimental measures and observe the
resulting change. For another, the supply and demand curves demonstrate the
relationship between equilibrium values, which require the individuals which
constitute the market to have performed sufficient price discovery to
determine the final price. In the real world, this is not a well-defined
concept, as prices are constantly changing as the underlying conditions
change. Empirical estimation of these curves is an active research topic with
fractal complexity. The curves predict what happens if the price were to
change ceteris paribus: if the price were to increase, more suppliers would
perform work, leading to more production, but the consumers would consume
less, as each additional unit is more expensive.

When we discuss these points as the outcome at equilibrium, what we mean is
that there is a process of negotiation in the marketplace which determines the
market clearing price, _i.e_. the price at which the demand for a good by
consumers is equal to the number of goods that suppliers will provide for the
given price. One can imagine a merchant appearing at, say, a farmer’s market
to sell vegetables as an illustrative example. The merchant must guess how
many vegetables will sell at a given price. At the end of each appearance, the
merchant notes whether they have sold all of their vegetables or if they have
remaining vegetables. If they have a surplus of vegetables, the merchant will
lower their price or reduce the amount of vegetables they grow; if they had to
turn customers away as they ran out of vegetables, they will either raise
their price or produce more vegetables. They will continue to adjust the price
they charge and the number of vegetables they supply until they either find
the market clearing price, supplying the precise number of vegetables demanded
by consumers, or run into some external constraint; for example, closing their
shop if consumers are not willing to pay a price that is higher than the
merchants cost, or being unable to sell more vegetables as they cannot
increase production.

At least, this is what the suppliers and consumers want to do. In practice,
they might not be able to. For instance, if there are no more apples to be
harvested, the suppliers are not able to produce more, and price could
increase without an increase in production. Similarly, if a price is already
sufficiently high for individuals to spend all of their time producing, then
an increase in price cannot incentivise further production. On the consumer
side, as we use a barter environment, prices are calculated as the ratio of
integer quantities of goods exchanged in trade. Thus, prices are discrete
options and not a continuous range that can be fine-tuned. This may slow or
prevent convergence. One agent might be willing to increase the price they
would pay for a good, but as their only option is to offer another unit or
request one less unit, the resulting price may change more than they are
willing to pay.

There is also the question as to what our reinforcement learning agents will
actually do. Our agents learn from a stochastic stream of experience, must
explore behaviours in order to learn their value, approximate the value of
those behaviours with a neural network, and attempt to optimize their reward
with respect to other members of the population, who are similarly not
perfectly rational. Some joint behaviours, such as the sequence of actions by
two parties required to exchange goods, might be highly mutually rewarding but
still unlikely to occur through random exploration, and so agents might
(suboptimally) learn to earn reward by other means without ever discovering
trade. We are studying an agent-based simulation that may be prima facie
similar to a standard economics case that is analytically solvable, but in
practice is a much richer interaction between complex agents.

Finally, it is important to note that supply and demand curves are a concept
that may help us interpret results and predict agent behaviour after
environmental changes, but are not in any way programmed into our environment
or agents. Our agents learn only to maximize their individual rewards, and we
will show that in many cases, their equilibrium production, consumption, and
pricing behaviour does indeed move in the direction predicted by supply or
demand shifts. But our goal is not for our agents to closely match an a priori
supply and demand curve or to converge to an analytically-derived optimal
price. Instead, our goal is to discover what factors affect the emergence of
trading behaviour in agents, and to see if their behaviour matches our rough
microeconomic predictions.

##  4 The Fruit Market Environment

(a) Version used in this paper.

(b) Upcoming Melting Pot version.

Figure 2: The Fruit Market environment. (a) depicts the pixel version used in
the experiments in this paper. Apples and Bananas (light red and green
respectively) grow on trees, and the trees turn to a darker shade after being
harvested. The white square in the middle represents an optional marketplace
(disabled unless otherwise mentioned) which may trade goods with the players.
The pale blue lines represent water that the players can cross with a negative
reward. The remaining colored squares (brown, purple, yellow, pink, _etc_.)
are the player avatars. Agents observe a subset of this map: a $[15,15,3]$
patch of pixels (width, height, RGB color channels), with their avatar in the
center of the bottom row, showing the pixels in the direction their avatar
faces. (b) depicts a graphical version which will be released in the open
source Melting Pot package. The graphical version uses sprites for each entity
instead of single pixels, both for visualising the map for humans, and for the
agent observations.

Fruit Market is an episodic multi-player game in a partially observable 2D
world, where players can produce, barter, and consume fruit (apples and
bananas) to earn reward. Each player’s goal is to maximize their own total
reward earned per episode. The environment is designed to elicit microeconomic
behaviour from the players: each player must make decisions about what type of
fruit it wants to produce and consume, and which offers—phrased as “I’ll give
X apples to get Y bananas”—it will use to trade with nearby players. The
environment is configured such that trading resources should be very mutually
beneficial for both parties, if those players, who are presumably controlled
by reinforcement learning agents exploring the environment with no a priori
knowledge, can discover how to trade.

A high level summary of the intended interaction is that half of the players
(called Apple Farmers) are skilled at producing apples but earn more reward
for consuming bananas, and the other half (Banana Farmers) are skilled at
producing bananas but earn more reward for consuming apples. Each player takes
actions to move around the map, and can produce either fruit and can consume
either fruit. While Apple Farmers can slowly produce their own bananas and
Banana Farmers can slowly produce their own apples—and in fact this is what
happens in practice, before the agents learn to trade—it is much more
rewarding for all participants if the players instead specialize in producing
what they are good at, and then meet up to negotiate a trade and exchange
goods. The players use actions to negotiate what quantities of apples and
bananas they want to trade, allowing a player to demand a high price (if they
can find a partner willing to pay it) or offer a low price to undercut their
competition. This assignment of roles (_i.e_. constant production abilities
and consumption preferences) is of course not the only way to create the
conditions for trade, but it is simple, has results that are easy to
interpret, and is meant to replicate introductory Microeconomics textbook
examples where participants have differing resources and desires666An example
of an alternative role-free approach for incentivising trade would be to have
homogeneous players with diminishing returns for consuming each type of fruit
(or a preference for consuming bundles of an apple and a banana together) in
combination with having apple trees and banana trees located in separate areas
of the map. This could result in players learning to harvest apples, start to
carry them to the banana area, but meet a banana-carrying player on the way
and trade with them. However, we have found that in practice, reinforcement
learning agents will much more easily learn to satisfy their own desires
independently by producing all of their own goods, than they will jointly
learn to over-produce one good and trade for what they lack. Even if the
latter behaviour is more rewarding for all players, the additional difficulty
of joint learning means agents are less likely to discover it. Our use of
fixed roles gives additional incentive for agents to discover trading
behaviour: they can produce their desired goods independently, but very
inefficiently, making trading more rewarding by comparison. See Section 6.1
for further insight into environmental conditions affecting the emergence of
trade..

Figure 2 shows two top-down views of the environment. Figure 2(a) shows the
pixel version used in the experiments presented in this paper, while Figure
2(b) shows a graphical version that will be available in a future release of
the open-source Melting Pot package (Leibo et al., 2021). The Fruit Market map
is made up of discrete tiles. In Figure 2(a), the light and dark red tiles are
apple trees, and the light and dark green tiles are banana trees. Black tiles
represent empty space that players can move through easily, and the light blue
rings of tiles are bodies of water that players can cross with effort. The
outer gray tiles are walls that players cannot move through. The other colored
tiles in Figure 2(a), such as yellow, purple, brown, and so on, are the ten
players that participate in the game. Players cannot move onto a tile
containing a wall or another player, but can move onto a tile containing a
tree or water.

Each episode of Fruit Market begins by randomly spawning apple and banana
trees across the empty black tiles of the map. Such procedural generation of
map layouts has been shown in other settings to improve reinforcement learning
agent generalization (Risi and Togelius, 2020). For our experiments we can
choose the placement of each type of tree independently, both in distribution
(_e.g_., uniform, gaussian, skewed to the left, skewed to the right, and so
on) and in frequency (_e.g_., 15% apples and 15% bananas, 30% apples and 15%
bananas, 5% apples and 10% bananas, _etc_.). For the moment, we will assume
that trees are placed at uniform random with an equal probability of 15% of
each type of tree per black tile, which were the parameters used to generate
Figure 2(a). Ten players (five Apple Farmers and five Banana Farmers) are then
spawned onto the map at predetermined starting locations. On each timestep the
players are shown the observations listed in Table 2 and then submit one
action from Table 3; both of these tables will be described in detail below.
The episode ends after 1000 timesteps.

Name | Shape | Description
---|---|---
Vision | $[15,15,3]$ |  A rectangular visual field with the agent centered at the bottom. 14 tiles ahead, 7 tiles to either side, RGB color channels.
Inventory | $[2]$ | Number of apples and bananas the agent is carrying.
Needs | $[1]$ | Agent’s “hunger satiation” level. A scalar ranging from 0 to 30.
Own Offer | $[2]$ | Vector of [apples, bananas] representing the player’s current offer.
Offers | $[P,2]$ |  Matrix of observed offers from nearby players. $P$ is the number of players in the environment. Each row is an offer vector of [apples, bananas]. Rows are $[0,0]$ when the other player is out of range.
Previous Action | [1] | Index of the action chosen on the previous timestep.
Reward | [1] | Total reward earned since the previous timestep.
Table 2: Observation Specification for players in Fruit Market. Players are provided with these observations on each timestep, and the agent acting as that player may use them however they wish (_e.g_., flatten, concatenate, and use as input to a neural net) to choose an action. Action | Description
---|---
Moving (7) | Stand Still | Do nothing.
Left | Move one tile.
Right
Forward
Backward
Turn Left | Turn 90 degrees.
| Turn Right
Consuming (2) | Eat Apple | Consume one fruit from inventory.
Eat Banana
Offers (19) | Cancel | Set offer vector to $[0,0]$.
1a:1b | Set offer vector to $[-1,1]$.
1a:2b | Set offer vector to $[-1,2]$.
2a:1b | Set offer vector to $[-2,1]$.
2a:2b | Set offer vector to $[-2,2]$.
1a:3b | Set offer vector to $[-1,3]$.
2a:3b | Set offer vector to $[-2,3]$.
3a:1b | Set offer vector to $[-3,1]$.
3a:2b | Set offer vector to $[-3,2]$.
3a:3b | Set offer vector to $[-3,3]$.
1b:1a | Set offer vector to $[1,-1]$.
1b:2a | Set offer vector to $[2,-1]$.
2b:1a | Set offer vector to $[1,-2]$.
2b:2a | Set offer vector to $[2,-2]$.
1b:3a | Set offer vector to $[3,-1]$.
2b:3a | Set offer vector to $[3,-2]$.
3b:1a | Set offer vector to $[1,-3]$.
3b:2a | Set offer vector to $[2,-3]$.
3b:3a | Set offer vector to $[3,-3]$.
Table 3: Action Specification for players in Fruit Market. Players have 28 discrete actions, and choose one to take on each timestep. Fruit is produced by using the movement actions to stand on a tree tile, and not moving away until it is automatically picked up into the player’s inventory. Players can still consume fruit or make offers while waiting to harvest fruit. Name | Production Quantity | Production % | Consumption Rewards
---|---|---|---
| Apple | Banana | Apple | Banana | Apple | Banana
Apple Farmer (AF) | 2 | 2 | 100% | 5% | 1 | 8
Banana Farmer (BF) | 2 | 2 | 5% | 100% | 8 | 1
Table 4: Role production and consumption constants. Players of each role produce two of each fruit when they successfully harvest a tree. Apple Farmers have a 100% probability per timestep of harvesting ripe apple trees, but only a 5% probability per timestep of harvesting ripe banana trees. Apple Farmers earn 1 reward for consuming an apple, and 8 for consuming a banana. Banana Farmers have these constants reversed. Constant | Value | Description
---|---|---
Fruit Ripening Time | 50 | Number of timesteps for fruit to regrow after harvest.
Movement Penalty | -0.25 | Reward per tile moved, representing exertion.
Water Penalty | -1.0 | Reward per timestep touching water, representing exertion.
Hunger Level | 0 – 30 |  Satiation, starting at 30, and decreasing by 1 per timestep. Refilled to 30 after consuming any fruit.
Hunger Penalty | -1 | Reward per timestep if Hunger Level is 0.
Trade Radius | 4 |  Euclidean distance radius another player making a complementary offer must be within for an exchange to happen.
Offer Visibility Radius | 4 |  Euclidean distance radius another player must be within to observe their offer.
Table 5: Additional environmental and player constants that are not role-
dependent.

###  4.1 Movement, Production, and Consumption

Each player has seven movement actions: one to stand still, four to take a
step (forwards, backwards, left, right) and two to turn (left, right). The
players do not observe the complete map as shown in Figure 2(a), but instead
observe a smaller patch of it: an egocentric $[15,15,3]$ matrix with their own
avatar in the middle of the bottom row, showing what is ahead of them in the
direction they are facing (7 tiles to either side, 14 tiles ahead). As they
move and turn, the world appears to move around them in their visual
observation. Since they can only see a small portion of the map, the players
need to move around to discover where they can find apples and bananas, and
where other players are, so that they can move away to avoid competing for the
same resources, or approach them to trade goods.

Each player, regardless of their role, can produce and consume both apples and
bananas. Each role’s constants for production and consumption are listed in
Table 4 and other related constants in the environment are listed in Table 5,
all of which we will now describe in detail. Production occurs when a player
moves on top of a tree bearing ripe fruit. With a fixed probability per
timestep, the player harvests two fruit from the tree and places them into
their inventory. This inventory mechanic is not found in most reinforcement
learning environments, where an agent would typically immediately consume a
rewarding object on touch. Apple Farmers have a 100% probability per timestep
of harvesting apples and a 5% probability per timestep of harvesting bananas,
while Banana Farmers have these constants reversed. After fruit is harvested
from a tree, the tree is empty and requires 50 timesteps to grow new fruit.
The difference between a tree with ripe fruit and an empty tree is displayed
visually, by switching from a light shade of green or red to a dark shade, and
then back to a light shade when the tree is ready to be harvested again.

Consumption occurs when a player has apples or bananas in their inventory and
uses the “Consume Apple” or “Consume Banana” action, which consumes one fruit.
An Apple Farmer earns 1 reward for consuming an apple and 8 reward for
consuming a banana, while Banana Farmers have these values reversed. Our
environment uses constant rewards for consumption, and the difference between
the fruit is a simple model of an Apple Farmer’s likely satiation of their
desire for apples777A more realistic satiation model would involve diminishing
reward for repeated consumption of each good, and then gradual recovery over
time. This would lead to a “natural” lower reward for apples in Apple Farmers,
without requiring role-specific rewards. It would also give Apple Farmers a
reason to produce some of each fruit for their own consumption even before
they discover trading, instead of specializing in producing whichever type of
fruit had the higher expected value per timestep (harvesting probability times
reward, for example). We intend to explore such nonlinear reward models in
future work.. In addition to earning reward, consuming fruit also addresses a
player’s hunger needs. Each player has a hunger level that they observe, which
starts at 30 (full) and decreases at 1 per timestep towards 0 (starving).
Eating one fruit of any type resets their hunger level to 30. If it reaches 0,
then the player suffers a reward of -1 per timestep until they consume any
fruit. In the experiments that we will present, trained agents learn to
produce and consume fruit frequently enough to almost entirely avoid the
hunger penalty. However, it plays a critical role in the emergence of trading
behaviour, which we will explore later in Section 6.1.

###  4.2 Offers and Exchanges

Finally, we can describe the actions and mechanics that allow players to trade
resources with each other. First, we will note that there is a broad range of
mechanics we could use for this, trading off realism, precise control over
price, quantities, and trading partners, and the difficulty for agents to
learn the mechanics. For example, we could implement simple and fundamental
actions such as picking up and dropping fruit, or giving one fruit to an
adjacent player. Players could then drop an apple next to a trade partner,
wait for them to drop a banana, and then each pick up the other’s fruit.
Alternatively, we could use an abstract mechanism where agents choose to enter
a bartering interface, similar to computer role-playing games. We could choose
a mechanism that allows players to explore any behaviour, including “bad”
behaviour such as giving items away for nothing or running away with the
partner’s offered goods while giving nothing in return, or we could constrain
the players’ behaviour to allow only reasonable offers and disallow theft.
Finally, we could choose a trade mechanism that uses domain knowledge such as
currency (_e.g_. selling apples for dollars and buying bananas with dollars)
which is a convention that humans have already discovered, or have the
environment facilitate exchanges by pairing up players who want to buy and
sell the same good at mutually acceptable prices and automatically exchanging
their goods.

The trade mechanism we will present strikes a balance, with our goal being to
create a system that is simple, gives agents control over their trade
quantities, prices, and partners, and includes minimal domain knowledge, while
still being learnable by our current agents such that trading behaviour
emerges. When we have compromised in these aspects, it is with the intent that
future research can use this work as a benchmark where agents consistently do
learn to trade, and then pursue the emergence of trade with fewer compromises.
At the end of the paper, in Section 6.4, we will re-examine our decisions by
presenting a series of simpler and more expressive trade mechanisms, and show
that our current agents do not yet demonstrate rational trading behaviour in
those settings.

Our trade mechanism involves a set of actions that allow players to make
offers to trade quantities of apples and bananas. An offer is represented by a
vector of $[\textrm{apples},\textrm{bananas}]$, such as $[-1,1]$, which means
“I will give 1 apple to get 1 banana”. The two elements of the vector
represent the player’s desired change in inventory of apples and bananas. Put
another way, negative numbers are what a player is willing to give, and
positive numbers are what a player wants in return. The offer $[1,-1]$ means
“I will give 1 banana to get 1 apple”, and is the inverse of the previous
offer: two players making these offers should be happy to trade, as they are
each willing to give exactly what the other wants. The offer $[-2,1]$, which
means “I will give 2 apples to get 1 banana” thus gives more, and $[-1,2]$ or
“I will give 1 apple to get 2 bananas” demands more. Throughout the text, we
will describe offers like $[-1,1]$ with a phrase such as “Give 1 apple for 1
banana” or the short name “1a:1b”, where what is being given is on the left of
the colon, and what is demanded is on the right.

Each player has a persistent offer vector which is “advertised” to other
nearby players within an offer visibility radius of 4 tiles. Each player
observes their own offer vector and other nearby offer vectors on each
timestep. The default value of an offer vector is $[0,0]$, the null offer,
which means that the player does not want to trade right now. Players can
change the value of their offer vector by taking one of nineteen offer
actions, listed in Table 3. Each offer action sets the player’s offer vector
to a specific value, and eighteen of the offer actions enumerate all possible
exchanges of apples and bananas up to a maximum quantity of 3 items of each
type. The final “cancel offer” action resets a player’s vector back to
$[0,0]$. Once set to a value, the player’s offer vector persists through time
and is advertised to other players as they move around the world to produce
and consume items. It only changes when the player uses a different offer
action to set it to a new value, cancels their offer to set it to $[0,0]$, or
fulfills their offer by trading with another player, after which it resets to
$[0,0]$. A player can only set their offer vector to an offer that they can
fulfill: they cannot offer to give away three apples if they only have one.
Attempting to do so instead resets their offer vector back to $[0,0]$.
Similarly, if a player is already making an offer and then consumes an item
such that they can no longer fulfill it, their offer vector is reset to
$[0,0]$.

We use the term compatible to describe a pair of offers that satisfy each
other. Specifically, two offers are compatible if each gives at least as many
items of each type as the other requests. When two offers exactly satisfy each
other, such as $[-1,1]$ and $[1,-1]$, we call them inverse offers, which are a
subset of compatible offers. But what if the first player is unnecessarily
generous by offering $[-2,1]$, thus willing to give two apples while the
second player’s offer of $[1,-1]$ only requested one apple? These offers are
not inverse, but are still compatible, because both players would be happy to
trade using either offer’s quantities. With either offer, one player would
simply get a better deal than expected: either getting an extra apple, or only
having to give away one apple, respectively. Thus, the inverse offers of
$[-1,1]$ and $[1,-1]$ are compatible, as are $[-2,1]$ and $[1,-1]$, or even
$[-2,1]$ and $[1,-2]$ where both players offer more than the other requests.
The offers $[-1,2]$ and $[1,-1]$ are not compatible, since the first player
wants two bananas, and the second player is only willing to give one.

An exchange of goods occurs when two players are simultaneously making
compatible offers and are within a trade radius of 4 tiles888Note that the
offer visibility radius for observing another player’s offer, and the trade
radius for exchanging goods with another player, are both set to 4 by default.
There is no need for these constants to be equal: two people might speak
across a room to negotiate a deal, but have to move close together in order to
exchange goods. Later, in Section 5.4, we will investigate the impact of
shrinking or growing both of these constants on the agents’ ability to learn
to trade.. This exchange of goods is automatic (the players do not take any
additional “exchange” action) and atomic (the items are swapped between their
inventories in one step). This is an abstraction of the physical task of
exchanging items: the players state their willingness to trade through their
offers, and then the environment intercedes by exchanging their goods when it
detects two nearby players have compatible offers. An alternative mechanism
could require agents to take a sequence of actions to exchange goods, but
might be too difficult for our current reinforcement learning agents to learn
through joint exploration.

The precise exchange process is as follows. At the end of each timestep, the
environment loops over all players making offers in a random order, so as to
not give any advantage to lower-indexed players (_e.g_., player 1 versus
player 10). Next, there is a two step task: selecting which partner (if any)
that player will trade with, and then determining the quantities of goods
exchanged. To select the partner, the environment makes a list of all
potential partners in their trade radius that are making compatible offers.
Any of these potential partners whose offers are dominated by other offers in
the list are removed. For example, if player A offers $[-1,1]$, potential
partner B offers $[1,-1]$ and potential partner C offers $[1,-2]$, then C’s
offer dominates B’s by offering an extra banana, and so B is removed from A’s
list of potential trade partners. The resulting list contains the most
generous partners’ offers from the player’s perspective. For each partner in
the list, the environment generates a similar list of compatible undominated
offers from the partner’s perspective; if the player is not also among the
partner’s most generous offers, then the partner is removed from the player’s
list. If multiple partners remain in the list, the environment breaks ties by
distance between the players, and then randomly selects one.

The second step is to determine the quantity of goods exchanged. Because we
selected a pair of players whose offers were compatible, and not strictly
inverse, there could be a range of quantities agreeable to both players. In
our implementation, we exchange the minimum quantity of goods that satisfies
both parties, and this might be different from either or both players’ offers.
For example, if player A offers $[-2,1]$ and players B offers $[1,-1]$, then
we exchange $[-1,1]$ from player A’s perspective, which happens to be the
inverse of player B’s offer. If player A offers $[-2,1]$ and player B offers
$[1,-2]$, then both players are willing to give more than the other requests,
and we exchange $[-1,1]$ from player A’s perspective.

Having selected both a partner and a quantity, the environment then atomically
exchanges the items between the player’s and partner’s inventories, and resets
their offers back to $[0,0]$. The environment then continues its randomized
loop over the players to check for other exchanges to perform.

The exchange mechanism described above is similar to a spatially local order
book, where nearby bids and asks are paired together. Players have fine