I am currently trying to implement a trading engine. My code can successfully create and fill limit and market orders. In addition, I would like my engine to have the ability to successfully fill "Fill or Kill" orders. Unfortunately, I have no idea how to write an algorithm for this "Fill or Kill". Does anyone know if there is an efficient algorithm for doing this?
The following is some background for those of you with less trading knowledge. Usually assets to be bought are ordered in a manner such as the following:
Price Amount
$200 3
$300 4
$350 2.5
$400 1.11
If one wants to buy assets, a simple algorithm goes from top to bottom in order to give the customer the best value. A whole row does not have to be completely bought. For example, if I want 4 apples, the code will sell me 3 for $200 and 1 for $300 (going from top to bottom).
Now, certain sellers may give the option of "Fill or Kill". This means that a given row cannot be bought partially. So now lets say that the second row is designated "Fill or Kill":
Price Amount
$200 3
$300 4 (Fill or Kill)
$350 2.5
$400 1.11
In this case, if I want 4 apples, I cannot buy less than 4 from the second row. So now I have two obvious options. I can buy 4 apples from the second row for 4*$300=$1200, or I can buy three apples from the first row, and 1 from the third for a price of (3*$200)+(1*350)= $850. Now in this case, the second option is the better deal. Unfortunately, that will not always be the case depending on the different prices and amount of orders.
These tables will be implemented in SQL and ordered by price. I am trying to implement this algorithm in php. Any help will be greatly appreciated.
You can skip the offer with the attribute "Fill or kill" and pick the next product. Then repeat with the skipped offer and find the cheapest combination between both solutions.
The purpose of a "Fill or kill" order is, to ensure that a position is placed to the market at a desired price. Therefore the transaction should be immediately and completely or not enter the market at all. A FOK order prohibits a broker from partially filling. You need a 1:1 order to market match, before the order is placed in the queue/book.
The "no partial fulfillment" is what differentiates "Fill Or Kill" (and "All or None") orders from "Immediate Or Cancel" orders. IoC orders allow partial filling and wait in the book to get more stock incrementally until order expiration time.
The difference between FOK orders and AON orders is, that AON, which cannot be executed immediately remain active until they are executed or cancelled. AON keeps waiting in the book for full match. FOK gets dropped, if no immediate full match.
Efficient algorithm for Fill Or Kill?
There are two forms "Multi Fill Or Kill" and "Single Fill or Kill".
This is probably the easier one. It's a 1:1 match of order to market. If no direct order match, kill. If you do this with a SQL command you have WHERE equals comparisons.
Single means: the order will be rejected, if it cannot be immediately filled against a single order of equal or greater size.
This is probably the algorithm, which you are after.
Multi means: fill with multiple internal orders.
It's said that a FOK order prohibits a broker from partially filling. That's only true, for the order book communication to the outside. Internally, an "immediate interal partial filling" happens, until the order is "filled".
For the incoming FOK order, you create an OrderEventGroup. The matcher might have multiple orders sitting on the book that allow to satisfy the incoming FOK order, but only IF ADDED TOGETHER. On the MatchEvent the OrderEventGroup, is filled with contra-orders matching the order constraint. You match orders in order book, where the quantity/price is lower or equal to the requested amount and price. You fill the OrderEventGroup until the FOK.order.amount equals OrderEventGroup.amountTogether. If OrderEventGroup.amountTogether doesn't sum up at all and/or takes longer than, what you defined as "immediate" execution time, the FOK order is killed.
You get a single transaction, which might have multiple matching steps, with possibly different prices. But that's not communicated. The order report contains: "filled" and "price", "qty" - where price is the average price of the OrderEventGroup. The order submitter would not even know that his order was filled against more than one other order.
The good thing: elimination of execution risk for the order submitter. The bad thing: you get the average price, without a clue of min max prices in the OrderEventGroup or the number of collected contra-orders.
Then, there is "Fill and Kill". The order is filled to the extent of the quantity that can be immediately filled at the requested price. The remainder of the order is killed/canceled. These orders might end with a status "partially filled". The algo is the same as under 2., except that FOK.order.amount doesn't have to equal OrderEventGroup.amountTogether. The OrderEventGroup.amountTogether is allowed to be lower (partial fill).
The matching algorithm used is mainly a pure time priority (FIFO) algorithm, because this kind of algorithm maximizes the number of effective orders. (Some markets use Pro-Rata matching. And somewhere in-between are LIFFE and the CME algorithms, both combining elements from fifo and pro-rata.)
There should be a pseudo-polynomial dynamic programming solution, similar to that for the knapsack. Maintain a table giving, for all quantities <= the desired quantity, the lowest possible cost at which that quantity can be bought. Start with all entries in the table set to the best you can get using only ordinary offers. Take each fill or kill offer in turn and use this to ammend the table: the new cheapest price to quantity k is min(previous price for k, previous price for k-x plus cost to provide x shares according to the offer you are currently considering). Keep enough backtrack information to work back to a combination of offers from the cheapest price for the target quantity after considering all fill or kill offers. This could be, for instance, a note, for each offer, of the quantities for which it forms part of the cheapest price.
First, FOK don't sit on the order book. They are like IOC (Immediate Or Cancel) and have a Time In Force of zero. If they don't execute, they are cancelled immediately.
All Or None orders, which are even less supported and less standard, might be have a TIF of end of day or good till cancel. In that case they are not displayed and will execute when they are able to.
Now with that our if the way, are you trying to obey securities law, or is this just a toy system? FOK aren't as standardized a Limit, Market, or IOC orders. Some venues may not even implement them and some have have different definitions if they do.
But, if you are trying to obey RegNMS, you cannot skip the inside of the book to fill deeper (the trade through requirement). I only ever see FOK orders filled on the the NBBO (best bid/offer, the inside), but I think I've used them at once place only that I can remember.
So the algorithm would be simple to see if the inside of the book has enough size and if so, execute against it. If you wanted to be a little more lenient, you could work to the next level, however under RegNMS, a venue couldn't do that if another venue was also showing size at that level (trade through strikes again). That is kind of the point of the order type though, to prevent leakage of your intent to buy/sell.