Mesa Lessons

Implementing Sugarscape has some interesting lessons.

In this post I’d like to cover engineering the simulation.

Seperating the environment from the agents

Mesa is a great tool for ABM but it has some limitations. One of these is that the reporting mechanism tries to get the same data from all agents. The way Sugarscape is implemented is that there are agents for sugar, spice and pollution as well as different actors. This makes it impractical to get a single data frame for all agents. This assumption is also carried over to the visualization code so that it is not a simple fix. Another problem with this approach it increases the number of agents in proportion to the size of the simulation.

For example for a 50x50 grid we have 2500 agents. If we have 2 resources and pollution which also requires tracking pollution flux and two iterations to perform the diffusion. Python isn’t particularly fast since it is interpreted and adding all this overhead makes the simulation slow. Also I wanted to also test some ideas with more resources which would require a larger grid.

One way to reduce the number of agents is to have a single patch agent type that can handle resources and pollution - which had been implemented in the Sugarscape with traders sample. This still means most agent are patches and makes agent’s code more complex. Data processing becomes flaky and there are not samples or documentation to help out.

What this led me to do is to make a clearer separation between the environment and the agents. I migrated the resource code into the grid which had the added bonus of making agents simpler.

Encapsulating rules in classes

A second idea issue that arises when trying to implement Sugarscape is the keeping track of the code belonging to each rule. And a second facet for this is to be able to support different variants of the rules. E.g constant growth, full growth, seasonal growth. This got me thinking about using a strategy pattern and then the agent delegating the rule’s behavior to the rule. THis is perhaps not the most elegant solution - but it does have a number of advantages.

1. it allows one to define an api for the model and agent step.
2. it allows one to easily swap out rules and test different variants.
3. it allows one to easily extend the rules by inheriting from the base rule class.
4. it allows one to store data collection and visualization code in the rule along size the code that generates the data. This is made simpler by also using the builder pattern to construct the data collector.
5. it also easy to add two functions to support rules’ initialization, at the model and agent levels
6. these can be expanded with a update model and agent state operation that facilitates controlling the simulation from a ui at run time - another big advantage of the strategy pattern.

Makeing sugrscape more dynamic

There are a number of ways to make Sugerscape more dynamic.

Dynamic rules - swapping rules during the simulation

One way is to swap rules in the middle of the simulation as the book frequently does. The simple way to do this is use an array of rules which specific the rules in use. This is frequently used in the book which generally used three or four rules in most cases.

Evolution based on fitness and reproduction

This concept is not fully implemented in the book but at least two aspects are inherent in the simulation

1. selection weeds out less fit agents
2. sexual reproduction allows for the creation of new agents with a mix of the parents’ traits.

what the authors did not include are

1. mutation

2. differential reproduction based on fitness

3. a fitness function - based on the expected progeny of an agent.

4. This can be based recusively by a linear model of intrinsics like high vision and low metabolism a smaller initial endowment the total amount of resources an agent has collected thier age the number of progeny they have - and the thier fitness.

the amount of resources an agent has.

Private information and coalitions

Agents do not have private information.

The agents form coalitions through culture but these are not used in any social sense nor for optimizing behaviour.

Adding private information can make trade more realistic. Adding private opens the door to construction of bayesian agents that can estimate the private information of other agents based on watching thier actions.

Establishing coalitions can be used to coordinate activities in ways that are optimal for the group and possibly over come the social dilemmas that arise in the simulation like the problems posed by pollution.

Private information and coalitions can be used to implement more realistic trade rules. These could be rudimentary versions of cooperative and companies but could also lead to a form of goverment.

Learning and reinforcement learning

Learning and reinforcement learning

This idea is already inhernet in of the sugarscape pardigm. IT basicaly involves adding a fitness function to the agents and then selecting the best agents to reproduce. The book uses a simple fitness function based on the amount of resources an agent has. This can be extended to include other factors such as pollution, trade, combat, and culture.

2. More challenging and beyond the scope of what is discussed in the book are scenarios where we test different rule variants during a single run. For example we can use a variant of culture that turns combat/trade rule on or off for agents with culture rule c_1 but other agents can have trade and combat on or of controlled by sex - i.e. at birth. This can let us study highly dynamic version of hawk dove game from game theory in simulations before we analyze it mathematically.
3. Agent having private information, and forming coalitions. Both concepts are discussed in to text but not implemented. The first in the context of more realistic trade rules. The latter in the context of paying agents to reduce harvesting to avoid pollution.
4. Even more dynamic is granting agents the ability to learn optimal behavior and take charge of their actions which also involves adding reinforcement learning to the model. This is already extant in Sugarscape through selection and reproduction but adding RL add a much greater level of dynamism to the model. Note also that this is a different behavioural paradigm from the one used in the book and requires some deeper thinking on hot to implement it. (What are the limits on experience for agent learning - do they only have thier last state, thier full sim’s history, all thier past lives, every past life. What about being taught by their parents at some cost or rate of transmision. Basicaly what is the minimal experience to get to pareto optimality on a set of rules.)

The problem of using an array is that some of the logic for action in the book have constraints on order. e.g. agents move, harvest, pollute, eat pollute again, perhaps die die if they are out of resources trade reproduce etc and then die of old age and pass of thier inheritance. This is a lot of steps for only some of the rules and and the order is important in some cases.

More challanging and beyond the scope of what is discussed in the book are scenarios where we test different rule variants during a single run. For example we can use a variant of culture that turns combant rule on or off for agents Alson side agent that have combat on or off permamently.

Even more intersting is granting agents the ability to learn optimal behavior and take charge of thier actions which also involves adding reinforcement learning to the model.

A third

This becomes a problem when we want to test different variants of the rules or change rules during the simulation. My approach to this is to to encapsulate each rule in a class this also makes it much simpler to extend simple rules using inheriatance.

The next idea was to make each rule also take charge of it’s own data collection and visualization. Again this makes it easier to extend the rules and to keep track of the data.

Second order effects - linking rules

Following Schelling segregation model, Sugarscape is a model of social activity that emerges from simple rules. One of the key ideas in the development of the sugarscape model is the reductionsit study of how a social activity like segregation can emerge from a simple rule. Many aspects of a society are considered in the book yet many others are not.

However it would seem that the next step in a reductionist study of society would be to consider how different rules interact with each other. The book does consider many such cases - most simulations cobine just a few rules. This is not done in the book.

from hetrogineity interacting with simple rules. THe One of the things that is not done in the book is to link the rules. For example

The next Idea I had to handle this is to move the environment to the grid. This has a few implications

1. we need to override the grid.
2. agents need to access the grid during the simulation.
3. the environment will need to activate the resource growth and pollution diffusion.

However, this seems to be a good way to separate the environment from the agents and indeed the agent code get a little bit simpler in when it comes to harvesting.

We also have a sigle type of agent allowing the data collection to proceed in the way mesa is designed.

It is now possible to replace Multigrid with SingleGrid. - This quickly uncovered a bug in the agent creation code. It does not check if a new agent’s position is already occupied. - The following fixes this issue.

pos = self.random.choice(self.grid.select_cells(only_empty=True))

I want some help in coding Sugarscape pollution diffusion rule using mesa’s new add_property_layer

I have written the following code:

class ResourceGrid(SingleGrid):

    def __init__(self, width, height, torus):
        super().__init__(width, height, torus)
        # Initialize each cell with resource attributes

        sugar_distribution = np.genfromtxt(Path(__file__).parent / "sugar-map.txt")
        spice_distribution = np.flip(sugar_distribution, 1)

        #elevation = PropertyLayer("elevation", width, height, default_value=0)
        max_sugar = PropertyLayer('max_sugar',width,height,sugar_distribution)
        sugar = PropertyLayer('sugar',width,height,sugar_distribution)
        max_spice = PropertyLayer('max_spice',width,height,spice_distribution)        
        spice = PropertyLayer('spice',width,height,spice_distribution)
        pollution_flux = PropertyLayer('pollution_flux',width,height,default_value=0.0)
        pollution = PropertyLayer('pollution',width,height,default_value=0.0)

        #self.add_property_layer(elevation )
        self.add_property_layer(max_sugar)
        self.add_property_layer(max_spice)
        self.add_property_layer(sugar)
        self.add_property_layer(spice)
        self.add_property_layer(pollution_flux)
        self.add_property_layer(pollution)

    def get_resource(self, x,y, key='sugar'):        
        return self.properties[key].data[x,y]


    def set_resource(self, x,y, amount,key='sugar'):        
        return self.properties[key].set_cell((x,y),amount)

    def get_resources(self, pos, key='sugar'):        
        return self.properties[key].data[pos[0],pos[1]]


    def step(self, sugar_growth_rate=1, spice_growth_rate=1, pollution_decay_rate=1.0):   
        # growback can be done without a loop using a lambda.

        self.properties['sugar'].modify_cells(np.add,sugar_growth_rate)
        self.properties['sugar'].modify_cells(np.fmin,self.properties['max_sugar'].data)

        self.properties['spice'].modify_cells(np.add,spice_growth_rate)
        self.properties['spice'].modify_cells(np.fmin,self.properties['max_spice'].data)

           def step(self, sugar_growth_rate=1, spice_growth_rate=1, pollution_decay_rate=1.0):   
        # growback can be done without a loop using a lambda.

        self.properties['sugar'].modify_cells(np.add,sugar_growth_rate)
        self.properties['sugar'].modify_cells(np.fmin,self.properties['max_sugar'].data)

        self.properties['spice'].modify_cells(np.add,spice_growth_rate)
        self.properties['spice'].modify_cells(np.fmin,self.properties['max_spice'].data)

        self.properties['pollution_flux'].modify_cells(np.multiply,pollution_decay_rate)
        self.properties['pollution'].data= self.properties['pollution_flux'].data

Note: the diffusion rule should: 1. update the pollution_flux using the mean pollution from the adjacent cells 2. apply the pollution_decay_rate to the flux 3. update the pollution from the flux

Some more ideas.

As I went on improving the design of my sugarscape simulaition I came across.

There are many variants on even the most basic rule.

The motion rule:

1. the ability to go to any of the maximal sugar points in the field of view creates a nomadic type of individual.

2. there was a bug in mesa’s randomization which led to near cyclic motion for agents at the edge of the sugar contours. Periodic motion is a form of teratorilaism which could be good for avoiding desiases and may make it easier to mate with other nearby teritorial agents. The idea here is to implement an exploter agent that prefers to go and exploit places it visted before if they are maximal. This can lead to near periodic motion. Is this a form of chaos. Also we may give it a epsilon chance to explore which may let it discover nearby maxima.

3. A friend suggested letting agents leave phenome tracks. These can form the basis of a signaling system.

   • The first signal is a phenome trail from distant maximum sugar/spice zones.
   • The second might indicate where a viable mates might be found. Since i’m interested in adding basic and complex singaling sytems to ABM these can be intersting to implemnt using new resource layers.

4. Boids/Flocking motion.

5. Fire fighthing - go the the hottest safe spot and put out the fire.

6. Pollution cleaners - go to highest safe pollution and clean up.

7. A missonary might go to pockets of counter culture to switch them over. This might work better if the culture had memory based on age. I.e. a binomial with a,b where a is the time steps it was 0 and b the time steps it was one. making it harder to convert you and increasing the chance you flip back. More generaly an urn model is even more genral.

   These can be used to comunicate

Pheromone Signaling:

if agents can signal using a pheromene trail they could lay a path from higher levels of resources to a nest…. (there might be unique pheromones for each resource or a more complex signal using combination of multiple pheromenes to encode each resource) a weak diffusion rule would create a gradient to lead to the agent or to the resource.

The SugarScape Trade rule issues

1. the rule is unfair.

• While the Edgeworth box has pareto-efficent solutions where indifference curves are at a tangent and therefore the MRS which corresponding to prices for trade are in agreement. Also there is only one such point for each pair of curves if they have a common point. Also there is one point where both utilities are highest. This seems to be the best trade to consider.

  The trade algorithms uses points where the two curves intersect not tangents. However each indiffence curve probably intersect with all the other traders curves. Some may have more curves in the box (their utility levels are packed closer) Others less. Without some mechanism to sort these out we cant be certain that bragaining steps are sensible. The problem is that agents are not realy indiffernt to all the combinatino of sugar and spice - at least in the sense that under a certain amount of sugar or spice they will be wealthy on paper but likely starve in the next time step. The algorithm leads to more on diagonal solutions but what if I am very sugar rich. I may trade 1/N of my excess sufar with each nighbour for one unit of spice. But one unit of spice from each may mean they have less then thier metabolism and they will starve before they can makr a trade or harvest ay spice.

  One agent may have more viable cuves than the other. idealy we should be picking two curves with similar utiltiy levels…. The intersection points can represent radicaly different pricing levels, particularly for an agent with a highly imballnced endowment. The pareto point leads to a point where both MRS are equal and the resulting endowments are better.

  But we don’t really consider which points on the current curve to use. Each intersection corresponds to different utility level for our trading partner. It seem the intersection closest to the diagonal is best for our partner but we seem to be picking the one which is furthest - most likely to be the worst for them - possibly starving them.

  So on this issue we should pick a point on the indiffeerence curve that at a utility level that at least won’t starve out trade partner or ourseves.

  This mean clipping the indiffernce curves at the metabolic minimum.

• there is no mony and trades are in integral units and detrmine the trade amount

• the trade amount are unfair because the prices are unfair and because one side is pegged to 1.

• All this is moot if the alg can reach the same pareto optimal solution by small steps. But I think that its unlikely. In the trade because the steps are integral and one side is pegged to one there are roundoff errors. With every trade some value is lost (on one or both sides).

  • after each both sides are reevaluated reducing the price as well and the price drops so that the more needy agent will less willing or able to make all the trades it needs to make to get the the pareto point. And they may now be approximating different pareto point.

• Both agents agent who participite in trade could be better off if allowed to pick
  their preffered trade partner.

• perhaps in view of this agents should be allowed to refuse unless they get a better deal. This suggest looking at stable marriage alg. where prior to trade the are serveral rounds in each neighbourhood for matching traders.

2. trade is inefficent.

• trade always use 1 unit for one of the agents.
• to trade 3 for 3 3 trades are needed.

3. trade increases utulity but can make an agent worse off.

• after a trade a fertile agent can become wealthier but infertile if they are reduced below a multiple of thier endowment.
• after a trade an agent can be wealthier in utility but not in survivability so they may have an extra unit of sugar they don’t need but not enogh spice so they might starve.

4. agents that have participate in tradetraded will generaly
5. a smarter agent who can pick his trade partners and thier order can do them some damage

Better trade rules:

A fundumental question is this:

If localy markets are hertogenious and weakly ineracting can we be sure of the globall market reaching an reaching an equilibrium between supply and demand? It there are many possible equilibiria how long to reach one and if not what other can we say for the long term, i.e. is there a local and global steady state where supply and demand meet or can we have other outcomes like periodic, chaotic, and random states globably.

• How long until will prices reflect the equilibrium of global supply and demand ?

• If the market is out of equilibrium does it mean that an agent with a good estimate of the true equilibrium price can trade or use arbitrage to benefit from this state?

• Is the trade rule realy inefficnet ?

• Can a better trade rules

  • let prices reach equilibrium prices
  • increase trade amounts
  • increase overall welfare and
  • reduce welfare inequality

• What is in the way of equilibrium formation ?

  • is it lack of information
  • inability or inefficency of making tades accross market boundries
  • not enough trades within markets for them to reach equilibria?
    • will it help if there are multiple rounds of trades for all agents.

The down side of a inefficent trade rule is that it may lead to less efficent market. The market in SC can be viewd as localy fragmented or if there are enough agents it may be a collection of weakly interacting markets.

Intuitively

Agents with lower vision tend to persist at the local market edges and beocome inefficent conduits of trade in the trade network instead of finding strategic locations where they could maximize the benefit of arbitrage between local markets.

Arbitraders

We can explore this by letting some agents who are less efficent harvesters have a movement rule that lets them seek out such locations with maximal arbitrage option. If there landscape is made of K blobs of different resources there may be greater need for such traders, and As more regions

Supertraders

We can setup a supertrader that is basicalt a supermarket in each neighbourhood. These agents with better vision that dont have a metablism cost or harvesting step.

They can see each other and trade with each other allowing for greater efficency in the market.

WE can rerun markets with or without supertraders and with supertraders with more vision. Thier wealth distribution could be a way to track the lost benefits due to vision fragmentation.

Edgworth box with pareto-efficent trades maximising utility objective

0. neighbours := agents in field of visions
1. for each neighbour in neighbours:

1. setup the edgeworth box with
2. store the pareto-optimal solution that maximises both agents’ utilities and is viable for both agents
3. do the trade with the highest gain in utility to me.
4. remove agent from neighbours
5. my prefrences have changed so return to 1

Edgworth box with pareto-efficent trades for survivability objective

we want to restric solutions to trades that increase the survivability this is like a quantum contraint on the utility.

1. are the any solutions ?
2. what is the best solution - and what is the closest option.

Edgworth box with pareto-efficent trades for hybrid objective

1. we want a multiterm utility for
2. survivability of n rounds Quant(U(M))
3. reproduction endowments for up to 4 offsprings U(E)
4. trades for U(M) that do not reduce the above two utility componenets
5. side trades that reduce pollutions ?

the tricky part here is to define an hybrid utlities and solve its edgworth box as we add more rules we arrive at more complex utilities.

So we may need to rethink a simlpler way to find accaptable trades….

Gale-Shapley Trade partner allocation

A second idea - based on Gale–Shapley algorithm for Stable marriage within neighborhoods

1. Each agent should find their preferred trades within thier FOV.

Median approximate solution to the stable trade partner lattice simplex

GS alg is best for one side (proposers or acceptors) Can we find a variant that leads to a median graph ?

This seems very hard to do.

The originals GS alg considers all marriages within the population. Here I want and trade alg in which optimal trades emerge in the the median point on the trader’s marriage simplex.

For this variant for ABM we want to impose two restrictions on marriages: 1. offers made are restricted by miopia to the agents FOV. 2. offers received are restricted localy to the agents Max_Vision FOV.

we should iterate over all agents once to so all

, yet if all agents get to play both roles per round then it should cancel out the proposer advantage and give a median solution!

Better trades ?

Lessons from the history of the East India Company suggest that if agents can form temporary trading companies they may be able to trade more efficiently.

Different forms of companies can be tested to see which maximally parsimonious structure emerge as most realistic while local and need minimal computation:

1. A set of Agent contributes (resources) or money to partnership at some price becoming an share owner of this company.

2. agents can be silent partners of active members acting on behalf of company

3. providing information on market conditions, supply, (by agent and on ground) demand, prices.

4. Getting and receiving trade offers.

5. Making localized decisions on behalf of the company (possibly subject to share majority in a neighborhood)

6. Once the company has traded agents can contribute/withdraw resources with ownership adjustments

7. the company can be dissolved after n-time steps, if enough agents migrate, or if the inventory is too low

8. The partnership has no Metabolism so it will need a different utility function - (this can be ml based based on info from agents).

9. members of a company may use an information utility to deploy to locations that maximize information….

10. will agents have shares in multiple companies. (perhaps conflict of interest can force agent to be a silent partner in the coorporation)

11. can agents get rewards for bringing in trades

12. can agents get loans from companies

13. will comparative advantage let certain agent gain control of such companies

Owners can cash out individuals or other

Emergence in ABM

If we consider lessons in thinking for ABM here are some guidelines:

Let us consider some effect we wish to study, say segregation.

1. We need to have a metric which we can measure the effect in our world.
2. We want to find a maximally parsimonious rule for which the effect emerges