Splitting Trade Units

Dividing a single executed trade proportionally for several customers is an interesting problem.  Naive decisions can lead to unpleasant and surprising results. In this post, I will describe the problem of fairly partitioning a trade with an integer number of units amongst a group of participants who are participating according to some numerical proportions (think pie chart).  The proportions will be specified as double precision floating point numbers, and they will be normalized relative to their overall sum.

Requirement: Make it Whole

Given a new trade for U units which establishes a new position, and N participants where participant i has P[i] >= 0 proportion.  If the total proportion (left-associated sum) is P>0, then the problem becomes finding values U[i] whose sum is U, and which are proportional to the P[i] values.

Using (P[i]/P)*U and rounding, seems like a good idea, but it is wrong.  Consider what happens with N = 3, P[0] = P[1] = P[2] = 10.0 and U = 20 : each participant is given 6.6666666666 units (but rounded  to the nearest integer using an unspecified rounding technique).  A deterministic round to 6 units each or 7 units each hands out the wrong number of total units (18 versus 21).  So this won't work.

Instead of trying to establish unit counts right away per client, I attempted to assign unit counts to two groups of participants (essentially abstracting the problem to two participants).  I wrote the following code:

 void inline position_split(
   int & units1
 , int & units2
 , const double & prop1
 , const double & prop2
 , int total_position)
{
 double total_proportion = prop1 + prop2;
 assert(total_proportion > 0 || total_position == 0);
 if(total_position) {
  units1 = ROUND_UNITS(total_position * prop1 / total_proportion);
  units2 = total_position - units1;
 } else {
  units1 = 0;
  units2 = 0;
 }
}

Going back to my N = 3 example, this is better since I can use it to determine (U[0], U[1]+U[2]) using (P[0],P[1]+P[2]) and then invoke it again in a similar way to find out what (U[0]+U[1],U[2]) is.  Applying the code above I obtain the following unit values: U[0]=7, U[1] = 6, U[2]=7.  Great, now the values add up to the expected total U.

Selling Out

Now that you are in a trade for U units and each participant has his piece the most interesting part happens.  How do you attribute profit as each unit is closed (in the worst case each one is done separately).  In essence, you have to have an ordering of the existing units of the position and an idea of whose unit will go next.  If the number of participants is very high, it would also be nice to not have to store the number of units left to each of them at all times.  This is key, since persisting that information can be a painful limit on performance as each update will cause a side-effect to an underlying database.

My initial approach was to leverage position_split to figure out what the position distribution would be if for (U-1) total units and then just compare that with the result for U to find out which participant lost a unit.  This does not work.  Back to our example plugging in 19 for position size we get U[0] = 6, U[1] = 7, and U[2] = 6.  This is a problem since the middle participant (i=1) actually gained a unit when we reduced the position.

Since position_split is not enough and we still want to avoid storing detailed per-participant data on the remaining position as it gets reduced, we return to considering how to order the units of the beginning position in a way that fairly strips them from the participants.  How can the ordering of the units sold off be deterministic and therefore, require no storage?

Partial Binary Trees 

A binary tree is a tree with two paths emenating from each non-leaf node in the tree.  The leaves can be addressed using the binary coded path from the root to the leaf.  A partial binary tree is a binary tree which is missing leaves beyond a particular coded address.  It should be obvious that a unique partial binary tree exists with U leaves for any positive integer U.  Consider the following tree for U = 5 (as an example):

I have written the coded binary path (0s and 1s for lefts and rights) on the leaves backwards.  Those backwards path numbers can be arranged as a sequence of unsigned binary numbers S = ( 0, 4, 2, 1, 3 ).  In this case, the sequence has no gaps (missing numbers), but that is not the case in general.  Using OS = sort(S),  to denote the ascending totally order sequence for S, we can say that after reducing the position by r units the next (ordered) unit to be picked is OS^-1[S[OS^-1[r]]].  For the above tree, OS = (0,1,2,3,4), so unit 0 goes first, unit 4 goes second, etc.  When there are gaps in OS, the point of using its inverse is clearer.

Essentially, for each trade which is originally U units in size, we can keep track of the number of units sold so far (r) and figure out which participants lose the next t units by evaluating OS^-1•S•OS^-1 at r,r+1,...r+t-1.  The position_split function indicates which participant originally had each of the units (e.g. participant 0 gets units 0 to U[0]-1, assuming U[0]>0).  I have empirically observed that the ordering of sold units using this technique is reasonably fair -- at each point the relative amount of units each participant has is roughly in line with their initial proportion amounts P[i].


Summary

Splitting the initial trade properly, requires a technique which is sensitive to rounding and floating point arithmetic. It distributes the units of a trade to several participants using their proportion amounts P[i] and it ensures that the right total number of units are distributed.

The reversed binary codes for a partial binary tree provide a deterministic permutation which can be used to fairly sell out a position so that at any point the participants still hold their proportion of what is left in aggregate.  By only knowing how many units were already sold r and the additional number to be sold t, an algorithm can tell you which participants are losing how many units.  The code to efficiently compute the permutation is a bit involved, so I have not posted it here.  The basics needed to reconstruct the approach are here, however. 

Trailing Stops: Rotating in two dimensions

Trailing stop orders are a computational challenge since they are state-full and react to every price change.  In 2008, I looked into the problem of implementing a data structure which could do better than a naive container at dealing with trailing stop orders.  In this post, I will describe the structure that I came up with, and critique it a little.

Hitching a Ride

A trailing stop order is designed to attempt to lock-in profit.  A stop order S (which is less fancy, and should be understood first) is typically used to close an open trade T at price P by specifying a market price which the trade T has accumulated a maximum allowable loss.  If T is a long position, then the stop order specifies a price lower than P, and otherwise (a short position) it specifies a price higher than P.  A trailing stop order TS is specified similarly but its trigger price creeps upwards so that it is never further from the market price than it started out.  Using this to control risk for trade T is advantageous since it sort of locks in profit.  If the price moves against T, then the TS price stays put (acting like a watermark).  If you want more explanation of how this works, please have a look at this helpful video.

I should stress that my purpose is to describe how to implement trailing stops, and not to endorse their use under any specific contexts.  Trading is risky, and strategic decisions to use various order types should be made with due caution.

Interface Design

Trailing stops for a particular instrument will enter the system with an insert() method, and be removable using a remove() method.  It is assumed that each of these orders has a unique integer identifier which can be used to refer to them.  Although the data structure should be concerned with the efficiency of these house keeping methods, the high-frequency operations of deepest concern are related to price movements.

The same structure should be used for orders which are buy or sell, its only really important to realize whether to use bid or ask prices, and to have an idea of which way is "up" or "down".  Prices will be dealt with internally as integers relative to the current market price (units which are pips or pipettes).  A trailing stop order has a pair of integers which describe its state (trailing_stop, trailing_amount).   To insert a new order which is 10 units off of market, the pair (10,10) is put into the structure.   The below diagram shows valid values for resting trailing stop orders (trailing amounts are not allowed below 1 and they cannot exceed the trailing stop):

Trailing amounts, which track how far the trailing stop order is from the market price, will change on the orders as market prices (Px) are applied to the structure.  The two different sides (buy and sell) will each have a data structure which reacts differently to market prices:

TS type	Px side	above/below market	Px increases	Px decreases
BUY	ASK	above	price_down()	price_up()
SELL	BID	below	price_up()	price_down()

If the price moves "down" by a single price unit we call price_down() which notionally changes the state of every trailing stop order from (ts,ta) to (ts,ta-1), and all (ts,0) state orders are removed as triggered orders.  A naive implementation would need to touch every order to update these records.

If the price moves "up" by a single price unit we call price_up() which notionally changes the state of every trailing stop order from (ts,ta) into (ts,min(ts,ta+1)).  Again, a naive implementation would need to touch every order to update all of the trailing amount records which is quite expensive.

Rotating Array of Arrays

In order to simplify the job of updating the trailing amounts, we could use the trailing amount to classify  and index each order.  This means that we can, in many cases, just have an array of orders move its position (changing the effective trailing amounts for all of its contents at once).  Consider the following array of array of lists (the inner arrays are connected by dotted lines, and each order with a particular (ts,ta) value is added to the list held at that box):

The outer array is the part we will rotate.  If the top box in the diagram (blue grid) is at position [0,0] of the NxN array, then an order with state (ts,ta) should be at logical array position [N-ts+ta-1,ts-1] (in the above diagram N=5).  The top "triangle" of boxes are unused since they do not represent reachable (ts,ta) states.

Completing a price_up() is only a matter of merging the red boxes at (ts,ts) up into the array above and rotating the whole top-level array (which is done in the usual way with modulus operations and an index variable):

The new empty lists (white boxes) simply appear as a result of the rotation, and the green boxes are not disturbed.  The magenta boxes are an inner array which moves as a result of the outer array rotation.

To do a price_down() operation, a similar trick happens.  The diagonal order list elements (trailing amount 1) boxes (shown as red) are removed, and the array is rotated in the other direction:

The new empty array that holds all the new (ts,ts) orders is shown as empty magenta boxes on the lower edge.  As a practical matter, the number of price unit levels supported (the value of N) has to be a fixed predetermined value.  As described, the data structure will work very well for large numbers of orders, but will use up considerable space when empty (an NxN array).  To mitigate this, the inner arrays (blue boxes linked with dotted lines) could be represented more sparsely with skip-lists or binary trees.  If the remaining dimension (top-level) array is still consuming too much memory, something could be done to make it sparse as well (allowing a larger value of N).

Summary

Using a benchmark which consisted of:

1. inserting 2 million orders at a spread of (ts,ta) values
2. price_up() 100 times
3. price_down() 100 times
4. insert 200k more random orders
5. price_down() 100 times
6. price_up() 100 times

The data structure described above (with sparse BST inner arrays) was 20 times faster than a naive implementation built around the glib hash table.  It is an interesting case of using a frame of reference to get free work done (rotating array) and mapping the problem to a data structure that attempts to reduce the number of operations.

If the structure has evenly distributed (ts,ta) valued trailing stop orders in it, price_up() and price_down() are both O(N) for the above structure.  In the case of a vector, list or hash-table something closer to O(N*N) is observed, as every element gets touched.  I have always been interested to know if something more space efficient, but with similar properties could be imagined in the future.