Simulating a market in Python
Published
Markets, be they goods markets or financial markets, are variations around the concept of auctions. Notable auctions types are the Dutch Auction, which was commonly used in the crypto bull market of 2017 by investors to sell their stakes in initial coin offerings, and the Double Auction which we’ll be using in this article.
What’s a Double Auction?
In a double auction, potential buyers and sellers submit their orders to the marketplace, which will then define a clearing price at which sellers who provided a price below the clearing price, and buyers who bid higher than this computed price, will be matched.
Here’s a simple example:
- Actor A sends a sell order for a quantity of 100 with a price of 9
- Actor B sends a buy order for a quantity of 100 with a price of 10
- Since quantities are equal, clearing price will be at 9.5, which is the midpoint between the two orders
This procedure has 2 objectives:
- Maximize volume traded
- Maximize utility of actors involved
From this it follows that our previous example is optimal: all outstanding orders have been completely met and both parties involved receive a better than expected outcome (buyer got the goods for cheaper that his bid price, while seller got a more expensive price).
The additional benefit is that a double auction is pretty simple to implement.
Implementing a Double Auction
It’s good practice to add typing information to your classes, and I also like to define dataclasses to serve as a kind of struct, so we’ll start by defining an order class, which stores the information from an order, and a match object to store bid and offer which have been matched.
from typing import List
from dataclasses import dataclass
@dataclass
class Order(object):
CreatorID: int
Side: bool
Quantity: int
Price: int
@dataclass
class Match(object):
Bid: Order
Offer: Order
Now we’ll create a Market class, which will handle information related to orders and matches, and expose a function to add Orders and seperate them according to whether they are bids or offers
class Market(object):
def __init__(self):
self.Bids: List[Order] = []
self.Offers: List[Order] = []
self.Matches: List[Match] = []
def AddOrder(self, order: Order):
if order.Side:
self.Offers.append(order)
else:
self.Bids.append(order)
Now we’ll focus on matching orders. Orders can only be matched if proposed buying price >= proposed selling price, so our first step will be to order bids from high to low, and offers from low to high.
Then we’ll iterate on all orders following these steps and try to match trades according to price and quantity:
- Check if bid price >= offer price. If not, break loop
- Check if one of the order has higher quantity and split the extra in a new order which is appended to the start of the bid or offer stack
- use the bid and offer as inputs to create a new match object
- Go to next element
class Market(object):
...
...
...
def MatchOrders(self):
self.Bids = sorted(self.Bids, key=lambda x: x.Price)[::-1]
self.Offers = sorted(self.Offers, key=lambda x: x.Price)
while (len(self.Bids) > 0 and len(self.Offers) > 0):
if self.Bids[0].Price < self.Offers[0].Price:
break
else: # self.Bids[0].Price >= self.Offers[0].Price:
currBid = self.Bids.pop()
currOffer = self.Offers.pop()
if currBid.Quantity != currOffer.Quantity:
if currBid.Quantity > currOffer.Quantity:
newBid = Order(currBid.CreatorID, currBid.Side, currBid.Quantity - currOffer.Quantity, currBid.Price)
self.Bids.insert(0, newBid)
currBid.Quantity = currOffer.Quantity
else:
newOffer = Order(currOffer.CreatorID, currOffer.Side, currOffer.Quantity - currBid.Quantity, currOffer.Price)
self.Offers.insert(0, newOffer)
currOffer.Quantity = currBid.Quantity
self.Matches.append(Match(currBid, currOffer))
Now that we have matched our orders, we can compute our clearing price. Here, we’ll compute it as volume-weighted average of midpoints which is (buyprice + sellPrice) / 2.
class Market(object):
...
...
...
def ComputeClearingPrice(self) -> int:
if len(self.Matches) == 0:
return 0
clearingPrice = 0
cumulativeQuantity = 0
for match in self.Matches:
cumulativeQuantity += match.Bid.Quantity
clearingPrice += match.Bid.Quantity * (match.Bid.Price + match.Offer.Price) / 2
return int(clearingPrice / cumulativeQuantity)
Now let’s perform a quick check to ensure our market works as expected.
# Create market instance and test orders
market = Market()
buyOrder = Order(CreatorID=0, Side=False, Quantity=100, Price=10)
sellOrder = Order(CreatorID=1, Side=True, Quantity=100, Price=9)
# Send orders to market
market.AddOrder(buyOrder)
market.SellOrder(sellOrder)
# Match orders
market.MatchOrders()
# Get the clearing price
market.ComputeClearingPrice()
# returns 9
Our little example seems to show everything working as expected: our orders get matched and we get 9 as the average price for 9 + 10… Wait a minute! 9 is not the mean between 9 and 10, what’s going on?
Well if you look back to the code we wrote, you’ll notice we have defined prices as integers, and the calculated midpoint gets cast back to int.
There are 2 main reasons for using integers instead of float:
- Faster computations. Integers are faster than floats
- Precision. Integers have no accumulating error
We’ll be losing information with casting the clearing price back to int, but I think that should be ok as long as we adjust the prices to allow for better precision. Python usually allocates 32 bits for an integer (so you get a value of up to 2^31 since we are using signed integers), and python allocates even more bits if needed (longint in Python2 which became part of the std of Python3). If you instead want to use floats, feel free to do it, there’s only a few things to change.
I’m working on a complete simulation model with multiple auctions and hope to release it soon, the code used in this article on double auctions is available on my github.