Best algorithm for netting orders

Question

I am building a marketplace, and I want to build a matching mechanism for market participants orders.

For instance I receive these orders:

A buys 50
B buys 100
C sells 50
D sells 20

that can be represented as a List<Orders>, where Order is a class with Participant,BuySell, and Amount

I want to create a Match function, that outputs 2 things:

1. A set of unmatched orders (List<Order>)
2. A set of matched orders (List<MatchedOrder> where MatchOrder has Buyer,Seller,Amount

The constrain is to minimize the number of orders (unmatched and matched), while leaving no possible match undone (ie, in the end there can only be either buy or sell orders that are unmatched)

So in the example above the result would be:

A buys 50 from C
B buys 20 from D
B buys 80 (outstanding)

This seems like a fairly complex algorithm to write but very common in practice. Any pointers for where to look at?

Answer 1

You can model this as a flow problem in a bipartite graph. Every selling node will be on the left, and every buying node will be on the right. Like this:

Then you must find the maximum amount of flow you can pass from source to sink.

You can use any maximum flow algorithms you want, e.g. Ford Fulkerson. To minimize the number of orders, you can use a Maximum Flow/Min Cost algorithm. There are a number of techniques to do that, including applying Cycle Canceling after finding a normal MaxFlow solution.

After running the algorithm, you'll probably have a residual network like the following: