Thursday, June 20, 2013

BazaarBot: An Open-Source Economics Engine

Via GameDev.net:

 By Lars Doucet | Published Jun 20 2013 11:39 AM in Game Programming
Peer Reviewed by (Hodgman, Michael Tanczos, Alpha_ProgDes) open source economics engine haxe


This availability of commodity physics engines has freed designers to focus on interesting new games, powering everything from Crysis to Angry Birds. The key is straightforward API's that let developers just throw things around and let the chips fall where they may (literally!).

For years, I've been wondering whether we could do the same with an economics engine. I remember playing strategy games where prices would rise and fall in proportion to supply and demand, but I could never find an open source engine to handle this, nor was I able to program it myself.

That is, until I found this research paper by Jonathon Doran and Ian Parberry. Entitled "Emergent Economies for Role Playing Games," it outlines exactly how to write a basic free-market simulator, in much the same style as Baraff and Witkin's seminal papers on rigid body simulations.

Over the course of two days I wrote a straight implementation of Doran and Parberry's method, and I figure I'd share my results. Behold: bazaarBot!

bazaarBot


bazaarBot is a simple, open-source free market simulator written in Haxe. This means it can be easily compiled down to multiple languages, including actionscript 3, C++, javascript, and more. It's very basic for now, but I would like to eventually turn it into a sophisticated engine with a decent API that can be used for games and simulations.

Let's talk about what makes it tick.

Prices emerge from Beliefs


I knew a free market simulator needed at least the following things:
  • Some kind of market, a clearing/auction house to handle trades
  • Agents that hold and trade commodities
  • A currency to denominate commodity prices
  • Recipes and/or jobs that define how commodities are transformed
But what was I missing? For starters, I was missing price beliefs. In a free market, goods don't have some inherent value stamped into their very being. Instead, their value is simply whatever someone is willing to pay. This willingness is modeled as a Price Belief that each agent maintains about each commodity in the market, defined as a range of two numbers. This represents not only what they think the price is, but also how certain they are of that price. When it comes time to decide the cost of a good when buying or selling, the agent picks a random number within their belief range.

Each trading round, agents create "bid" (buy) and "ask" (sell) orders for various commodities, and the market fills up with orders. Then, the market resolves the orders thus:
  • Shuffle the bid and ask lists
  • Sort bids by -> highest to lowest
  • Sort asks by -> lowest to highest
  • Match bid[0] with ask[0]
Clear the trade:
  • clearing_price = Average of bid/ask prices
  • Trade the minimum of units offered in bid or ask @ clearing_price
  • If bid[0] units == 0, remove it from list
  • If ask[0] units == 0, remove it from list
  • Continue until either bid or ask list is empty
  • Reject all remaining offers
The "average market price" of a commodity for a given round is defined as the average clearing price for a successfully traded unit that round.
Each round, agents update their pricing models. If they had a successful trade, they become more confident in their price belief and tighten the range around the mean. If they failed, they become less confident in their price belief and expand the range. Furthermore, failed agents will look at the average market price from the last round, and translate their price beliefs towards that range.

There's a bit more to it than that (see the paper), but the result is that commodity prices rise and fall in proportion to supply and demand. Some agents will be more successful than others, so some will have a tight range and others a large one.

When supply is high, selling prices will be all over the place. If demand is low, buyers can fill their orders entirely with just the goods offered at the low end of the price spectrum.

When demand is high, buying prices are all over the place. If supply is low, sellers can offload their entire inventory with just the offers at the high end of the price spectrum.

The result of that round then reinforces price beliefs, causing next round's prices to change.

Agent AI


That's just the first step. Next, there has to be some feedback to make agents respond properly to price signals. Agents have very rudimentary AI that works like this:
  • ideal_amount = Decide how many units to buy/sell of COMMODITY
  • curr_price = Check current market price of COMMODITY
  • favorability = Compare curr_price to my_observed_trading_range
  • Buy/sell (ideal_amount * favorability) units of COMMODITY
This block simply determines, "Assuming I want 10 hamburgers, how many will I actually buy if they cost $5 a pop?" It has nothing to do with how the Agent comes up with its generalized lust for hamburgers. In the paper's example (and which I model in the bazaarBot's example project), each agent just tries to maintain static, pre-defined units of each commodity in its inventory at all times. Under ideal conditions, Blacksmiths just always want X units of metal, and Farmers just always want Y units of wood, etc. During production (defined separately) they will consume these input commodities to make tools and food, and then they'll want to replenish their stocks next round.

The price signal logic simply makes the Agent buy low and sell high. How the agent determines what counts as "high" and "low" is based on its own history of successful trades. This value (my_observed_trading_range) is simply a list of trading prices per commodity. This means that more successful agents have better information and are less likely to make mistakes, but also more likely to bid conservatively and miss opportunities when prices change sharply.

There's a few other things thrown in, but that's the basics of it.

Agent Replacement


Finally, some agents will run out of money due to bad trades and/or market conditions. In this simulation, the bankrupt agent is replaced by a new one of the currently most profitable job type. This is another driver of supply and demand - if so much wood is being sold that the price collapses and woodcutters start going broke, people quit woodcutting and start farming. The supply of wood goes down, the price rises, the few remaining woodcutters stick with their jobs, and the population reaches a more stable distribution or careers.

There were a few kinks in this system. I stored each job's profitability per round in a public information list, which worked nicely for a while until a particular job was completely abandoned. At that point, that job's profit per round would be continuously logged as "0." At this point, no new agents would ever consider the job again, even if there was enormous demand (and zero supply!) of that job's chief export!

I couldn't figure out how Doran and Parberry solved this issue, so I added in a special case during agent replacement to check for a good "market opportunity," defined as any commodity with signicantly higher demand than supply. If such an opportunity existed, the new agent would favor the job that creates the most of that commodity rather than the default behavior of picking the most profitable existing job. This covered that case pretty well - any time all the woodcutters or blacksmiths would go out of business, eventually the pent-up demand for wood or tools would become high enough to encourage a short boom in those careers.

The above formula for agent replacement works well enough, but it should probably be a lot more customizable as each game's needs will be different.

Where to Go From Here


A lot of work remains to be done to make bazaarBot the kind of open-source economics engine that can drive the strategy games of the future. Here are some futher thoughts on that.

A well designed API


Right now the engine doesn't have much of an API to speak of, it's just a simple proof-of-concept. Further work is needed to decide what should be the walled-off internal guts, and what parts should be for public consumption.

Most physics engines work by creating two parallel universes - the game world, and the physics world, and closely linking them. Thus, every game object has a corresponding physics object, and the physics object is used to update the game object's position every frame.

bazaarBot's API would be similar - there's a game world, and an economics world, and game objects will somehow be linked to economics objects via bazaarBot instances.

So, you could have a simple game town filled with NPC's that walk around, some are woodcutters that find and cut down trees (which grow back according to some schedule), some are miners that look for and mine ore (which is finite and unreplenishable), and at the end of each day they bring their goods to the town square, itself a game object which is linked to a bazaarBot.

Each NPC updates their economic Agent's inventories and desires, the market object runs a round of trading, and the NPC's pull their new inventories from their economic Agent's, and then go out and do another day's work before coming back to trade.

This would be one of the more simpler implementations, but you could go further.

A Tale of Two Cities


By creating multiple bazaarBot instances, you could model separate economies for cities that can then trade with one another. Let's create two cities, Paris and London, each with their own economies. Prices for goods in each city will be different, and let's say wheat has been cheaper in Paris for the last 10 rounds.

A Londoner could notice this, and game logic could make him become a "merchant," with knowledge of both markets. This merchant checks the cost of the "travel-to-paris" token (redeemable in game for the travel-to-paris service), and it's currently favorable, so he hops on a ship across the English channel.

Next round he's in Paris, and the price of Wheat is way below his observed trading range in London, so he offers a generous price (for Paris) and buys as much as he can carry.

He buys a "travel-to-london" token as well and travels back to London the next round. He checks the price of Wheat in London, and it's well above what he paid for it in Paris, so he sells it all at slightly below the current market price.

The activity of trading merchants would eventually cause prices in each city to communicate somewhat, mediated by the time and expense of travel, as well as any policy restrictions (such as tariffs) imposed by governments. Furthermore, the price of travel would respond to demand by merchants.

Some work might need to be done to enable the "Tale of Two Cities" example specified above. Currently bazaarBot Agents do not have any mechanism for explicitly keeping track of what they've paid for the items they currently own, this is just sort of handled implicitly via price signals and observed trading ranges.

There also might need to be first-class support for "merchants," though this could also be left entirely to the game logic side just by moving Agents from one market to another. Support could also be added for "government policies" such as taxes, import duties, subsidies, bans, and price controls. These rules could be set on a per-market basis.

There's currently no formal support for multiple currencies, but it could be handled implicitly by how we treat the "money" in each market. In the above example, London and Paris can freely exchange, so they might as well be cities in the same country. Now, let's instead call a unit of "money" in London "Pounds" and units of money in Paris "Francs."

The exchange rate between a Pound and a Franc would be done by comparing the total value of goods in one country versus that of another. In a simple example, the only commodity available is wheat, so if Paris has 100 wheat trading @ 1 Franc and London has 50 wheat trading @ 1 Pound, then 1 Franc = 2 Pounds, showing that it's currently cheaper to import wheat from Paris. I'm really not sure what effect formal currency exchanges and money changers would have on things.

(Feel free to correct me if you know something about currency exchange and valuation)

Agent AI


It should be noted that Agents are kind of stupid. bazaarBot has rudimentary support for a basic data-driven scripting engine, but it's honestly some cheapo thing I hacked together letting you specify actions and conditions in JSON, so it's not ideal. In the future I might expand this, switch to an actual scripting language like lua, or just leave it entirely to the game logic side to extend Agent objects and provide your own code for handling their production logic.

Perhaps it's even best for Agents to have as little AI as possible beyond economic matters, and all the user does is update their inventory and desire for certain products, with the entire matter of how those values are created being entirely left to game logic.

One caveat I should mention is that AI is stupid, really stupid. This is no replacement for a real human-driven economy, nor is it likely to be an incredibly accurate simulation of one.

Complex Finance


bazaarBot has no current support for anything beyond buying and selling commodities of uniform value. It doesn't even have support for borrowing or loans, let alone interest rates, bonds, short selling, options, or credit-default swaps. Services could easily be modeled just by mapping them to a tradeable token, which could work just like a commodity.

Some or all of these could be added later, I suppose, but this brings me to my next point.

Finding the Fun


Emergent complexity is no magic formula for fun, and is often quite the opposite. I'm a data nerd at heart, and I get a huge kick out of tweaking intricate and complex systems, but I've found players are mostly interested in systems with clear inputs and outputs, and choices that are easy to understand. I think an economy engine could be really useful, but it will take special care to make a fun game out of it.

I'd recommend keeping economies simple at first before going too far down the rabbit hole with complex Agent behaviors or whacky financial instruments.


Ideological Bias


I've tried to keep things as simple as possible, but it bears mentioning that any economic simulation is going to reflect a certain bias. My hope is that bazaarBot will be flexibile enough to model many different kinds of economies, as well as demonstrate economic principles from a multitude of perspectives, be they Keynesian, Hayekian, Marxist, Georgist, etc. Most of that high-level bias will come from the actual scenario that's modeled, as well as how the game designer decides to reduce real-world entities to economic objects.

From the engine's perspective, a commodity is just a commodity. But if you treat land as a simple commodity, you are at odds with Georgism, and if you treat labor as a simple commodity, Marxists might have something to say.

There are already some fundamental biases, however, that I can see in the current engine. For one, it assumes that commodities are uniform in value and quality. This is how the United States treats agricultural products on major commodities exchanges, and some would argue (including myself) that favoring commoditizable goods can have serious repurcussions for the health and welfare of humans, animals, and the environment.

Flexibility


However you feel about food politics, I think we can all agree there are limitations to the "commodity" model as a one-size-fits-all model for tradeable goods. Some designers might want more flexibility. I suppose one way to do that is to add quality "grades" to commodities, and treat each as separate commodity types that are still somehow linked to a parent type. For example, if you want to buy Grade-A pork bellies, but they're too expensive, you might be willing to substitute Grade-B pork bellies instead.

Further considerations could let us define goods that don't act like commodities at all, so instead of having unique data structures in the market for each commodity type, you could have "flea market" lists that are a random grab-bags of goods, where items aren't defined by what they are but insetad by what they can do.

So, if an agent is just looking for something -anything- that is "sharp," they could make bids for axes, knives, swords, etc, based on the properties of those items.

I'm not sure I want to dive down that rabbit hole just yet, though, but it's one possible solution.

Signing Off


Well, that's my economics engine! It only took me two days to write over the weekend, but I've been thinking about if for a long time. If anyone else has some tips for me, I'd really appreciate it, as I'm constantly looking for ways to improve this thing.

Here's the Github link again, in case you want to contribute (I'll put it under MIT license):

And here's a link to the page where I found the research paper, it's got lots of other good stuff in it!



About the Author(s)


Lars A. Doucet is the Co-Founder of Level Up Labs, LLC, an independent game design studio based in Bryan, TX, and has a Master's degree in Visualization Sciences from Texas A&M University.

His latest project is the successful RPG/Tower Defense hybrid Defender's Quest.

In addition to his work at LUL, Lars has been a consultant who specializes in "Applied Gaming," an emerging field that uses game design and game technology for new uses both in and out of the entertainment sector.

Lars' applied gaming projects include Super Energy Apocalypse, in collaboration with the Houston Advanced Research Center, and CellCraft, through Wake Forest University and the MacArthur foundation.

Lars has also consulted for Rice University's Center for Technology in Teaching and Learning and Texas A&M University.


License


GDOL (Gamedev.net Open License)

No comments:

Post a Comment