# Prediction market algorithm

I play on FX (Foresight Exchange), which as I recall is a direct outgrowth of that research. The algorithm they use for making trades is simplicity itself. Make a sorted list of buy and sell orders by price (two lists, obviously). Any time a new buy or sell order is entered check whether it can cause a trade. If it can cause a trade, check whether the appropriate trading partners are capable of trading now (this generally means verifying that they have the cash/stocks still available). If not, nuke the offending order and check again if appropriate. If so, execute as much of the trade as possible. If you still have unsatisifed parts of the trade, continue until you have done as many orders as possible. If you still have unsatisfied parts of the trade, put them in the appropriate list of orders.

Example:

Sell
Bob wants to sell 500 shares at 30
Cindy wants to sell 300 shares at 45
Dan wants to sell 25 shares at 50

Alice wants to buy 250 shares at 25
Edgar wants to buy 1 share at 26
Francis wants to buy 1000 shares at 29

Note that currently no trades are possible (if you follow the above instructions in a threadsafe manner that should always be true except when you're inserting a new order into the list).

Suppose Patrick comes in with an order for 1000 shares at 47.

I immediately get all of Bob's shares at 30.
I attempt to buy Cindy's shares at 45 but lets suppose she already sold them, so that order gets nixed and I get nothing.
I don't try to get Dan's because the price is too high.

So I end up with 500 shares, pay 500*30, and the order list looks like:

Sell
Dan wants to sell 25 shares at 50