62

Which are the order matching algorithms most commonly used by electronic financial exchanges? Is there a list of order matching algorithms somewhere?

Kinnard Hockenhull
  • 2,790
  • 5
  • 27
  • 34

2 Answers2

87

In general, there are two groups of matching algorithms, one for each of the states of the market:

  • Continuous trading
  • Auction

There's quite a variety of algorithms for auction trading, which is used before the market opens, on market close etc. but most of the time, the markets do continuous trading. I'll therefore go into the latter category here.

The most commonly used ones would be Price/Time priority and Pro-Rata. Both have been adapted and extended for various types of products and use cases, but for brevity, I'll only explain the basics here.

Price/Time priority, aka FIFO, ensures that

all orders at the same price level are filled according to time priority; the first order at a price level is the first order matched.

Say the order book, sorted by price and time looks like this:

Id   Side    Time   Qty   Price   Qty    Time   Side  
---+------+-------+-----+-------+-----+-------+------
#3                        20.30   200   09:05   SELL  
#1                        20.30   100   09:01   SELL  
#2                        20.25   100   09:03   SELL  
#5   BUY    09:08   200   20.20                       
#4   BUY    09:06   100   20.15                       
#6   BUY    09:09   200   20.15

NB: The order for sorting by time is ascending for buy-side orders and descending for sell-side orders, so that the order with the highest priority is always in the center and priorities decrease outwards (up or down, depending on the side).

Now imagine a new limit order to "buy 250 shares at 20.35" comes in, then it will be filled, in this order:

  1. 100 shares at 20.25 (order #2)
  2. 100 shares at 20.30 (order #1)
  3. 50 shares at 20.30 (order #3)

This leaves the order book in the following state:

Id   Side    Time   Qty   Price   Qty    Time   Side  
---+------+-------+-----+-------+-----+-------+------
#3                        20.30   150   09:05   SELL  
#5   BUY    09:08   200   20.20                       
#4   BUY    09:06   100   20.15                       
#6   BUY    09:09   200   20.15

Pro-Rata ignores the time the orders were placed and allots fill quantities to all orders at a price level according to their relative quantities. Take again the initial order book above, and let us match the same "buy 250@20.35" order.

The fills would be:

  1. 100@20.25 (order #2, leaving 150)
  2. 50@20.30 (order #1, 150 x 1/3 = 50)
  3. 100@20.30 (order #3, 150 x 2/3 = 100)

Leaving the following order book like this:

Id   Side    Time   Qty   Price   Qty    Time   Side  
---+------+-------+-----+-------+-----+-------+------
#3                        20.30   100   09:05   SELL  
#1                        20.30    50   09:01   SELL  
#5   BUY    09:08   200   20.20                       
#4   BUY    09:06   100   20.15                       
#6   BUY    09:09   200   20.15

The CME group provides a list of matching algorithms they employ, and links to descriptions of each one.

For more, you might also want to take a look at the "Order matching" related documents on Rajeev's pages.

Evgeniy Berezovsky
  • 18,571
  • 13
  • 82
  • 156
  • Thanks. I understood what is happening from your description, but I'm a bit confused about the tables -- e.g. in the first table, why do you show order #3 before order #1 when sorting by price and time? And I presume the left 2 columns are for buy orders, and the right 2 for sell orders? – j_random_hacker Aug 30 '13 at 12:38
  • 1
    Whether it's a buy or sell is implied in which side of the table *Qty* and *Time* are on, but I added BUY/SELL indications to the table to make it immediately obvious. I use the ids just so you can relate orders between different tables. I chose the ids to reflect the submission time of the orders (-> *Time* column). – Evgeniy Berezovsky Sep 02 '13 at 01:21
  • Thanks for that improvement, but I have to say I'm still confused by the row ordering. As I understand it, you're sorting by price then time, so all orders of the same price should appear in increasing time order. So according to me, #4 correctly precedes #6, because they have the same price and #4 occurred first; but then I'd expect #1 to precede #3, because they have the same price and it happened first (9:01 for #1 vs. 9:05 for #3). How come #1 appears *after* #3? – j_random_hacker Sep 02 '13 at 11:40
  • 2
    The time ordering is a bit confusing, I agree. I added the following comment to my answer: `NB: The order for sorting by time is ascending for sell-side orders and descending for buy side order, so that the order with the highest priority is always in the center and priorities decrease outwards (up or down, depending on the side).` – Evgeniy Berezovsky Sep 03 '13 at 01:54
  • tx for the clear example. used it as a basis for a simple Java implementation https://github.com/matthiaszimmermann/order-matching-demo – matthias Mar 08 '17 at 23:16
  • @EugeneBeresovsky thanks for this. In your FIFO example what would happen if the buy for 250 shares was a market order? – MovieMe Sep 29 '17 at 07:42
  • @Barry A market buy order would be no different in this example. – Evgeniy Berezovsky Oct 03 '17 at 00:16
  • Are You sure? `NB: The order for sorting by time is ascending for sell-side orders and descending for buy side order`? As I see the example the times are descending for the SELL side and ascending for the BUY side – Kristóf Dombi Apr 25 '18 at 15:13
  • @EugeneBeresovsky How do these order books run with high availability and scale such as in the NASDAQ? Asked here: https://stackoverflow.com/questions/53570135/stock-exchange-order-book-scalability – fionbio Dec 01 '18 at 11:18
  • 1
    Rajeev's page is in wayback machine but all the PDFs are missing. Anybody have them? – Joseph Garvin Feb 07 '21 at 18:25
  • Hey guys. I see a clash of definitions between the FIFO, as a matching algorithm, and FIFO, as in first-in-first-out, an abstract data type definition for lists. FIFO, as the matching algorithm, doesn't feel anything like a FIFO list. Could someone explain why? – Rodrigo Novaes Apr 21 '22 at 13:45
  • @RodrigoNovaes In contrast to e.g. *pro-rata* algorithms, with the FIFO matching algorithm, the first order that comes into the system will be the first order to be matched - however after considering the price level. So every price level in FIFO matching could be considered a FIFO queue. – Evgeniy Berezovsky Apr 21 '22 at 22:02
  • Thanks @EvgeniyBerezovsky. That explains it. – Rodrigo Novaes Apr 22 '22 at 10:11
6

Generally they use First-In First-Out kinds of algorithms because they maximize the number of effective orders.

Each exchange has its own set of rules which is explained in their websites. This one here is an example.

alestanis
  • 21,519
  • 4
  • 48
  • 67