Order matching

Abstract

The disclosure relates to an automated trading system, comprising an interface for receiving a plurality of orders comprising bid orders and ask orders and a trading module for matching the bid orders and the ask orders, the trading module comprising a memory for storing the plurality of orders, a subset sum module configured to find the subset sums of the bid orders and the subset sums of the ask orders of the plurality of orders, and an order matching module for matching a combination of bid orders to a combination of ask orders based on the subset sums for the bid orders and the subset sums of the ask orders.

1 . An automated trading system, comprising:
 an interface for receiving a plurality of orders comprising bid orders and ask orders; and   a trading module for matching the bid orders and the ask orders, the trading module comprising:
 a memory for storing the plurality of orders; 
 a subset sum module configured to find the subset sums of the bid orders and the subset sums of the ask orders of the plurality of orders; and 
 an order matching module for matching a combination of bid orders to a combination of ask orders based on the subset sums for the bid orders and the subset sums of the ask orders, 
   wherein the subset sum module is configured to find the subset sums of a set of orders by considering a first set of orders of the set of orders, determining the subset sums of the first set of orders, considering a second set of orders of the orders wherein the second set of orders comprises at least one more order than the first set of orders and determining the subset sums of the second set of orders by using the determined subset sums of the first set of orders.   
     
     
         2 . An automated trading system according to  claim 1 , wherein the set of orders comprise orders a i  with minimum volume conditions c i , and wherein the subset sum module is configured to determine a value g i,j  indicating whether a set S i ={a 1 , . . . , a i } comprises a subset that sums to value j by noting that set S i ={a 1 , . . . a i } has a subset that sums to j, if S i−1  has a subset that sums to j or if S i−1  has a subset that sums to j-k, where c i ≦k≦a i . 
     
     
         3 . An automated trading system according to  claim 2 , wherein the minimum volume condition orders comprise at least one All-or-None order, wherein k=a i =c i . 
     
     
         4 . An automated trading system according to  claim 2 , wherein subset sum module is arranged to construct a matrix in which every row correspond to a set of orders, S i,j , every column corresponds to a subset sum j and the element g i,j  at a particular position i,j indicates whether the set S i  has a subset summing to sum j and the subset sum module is configured to populate a row by considering a set of orders comprising one more order than the set of orders corresponding to the previous row and using the value of the elements of the previous row. 
     
     
         5 . An automated trading system according to  claim 4 , wherein said one more order is an AoN order and the subset sum module is configured to:
 add a first copy of the previous row to the new row; and   add a second copy of the previous row, shifted a number of columns corresponding to the volume of said one more order, to the new row.   
     
     
         6 . An automated trading system according to  claim 4 , wherein said one more order is any minimum volume condition order, and the subset sum module is configured to:
 add a first copy of the previous row to the new row; and   add a second copy of the previous row, shifted a number of columns corresponding to a possible volume of said one more order and spread to represent all the possible volumes of the order, to the new row.   
     
     
         7 . An automated trading system according to  claim 6 , wherein the second copy is shifted a number of columns corresponding to the minimum volume of said one more orders and the subset module is configured to:
 add the second copy, shifted said number of columns, to a temporary row; and   set element g i,j  in the temporary row to indicate that j is a subset sum if g i,j−m  of the second copy of the previous row, shifted said number of columns, indicates that j-m is a subset sum of the previous row, where m is an integer 0<m≦a i −c i .   
     
     
         8 . An automated trading system according to  claims 4 , wherein g i,j =1 indicates that the set S i  has a subset that sums to j and g i,j =0 indicates that the set S i  does not have a subset that sums to j, and the subset sum module is configured to populate the rows of the matrix by setting g 0,j =1 for j=0 and g 0,j =0 for j>0 and using the recursion g i,j =1 iff (g i−1,j =1 or g i−i,j−a     i   =1). 
     
     
         9 . An automated trading system according to  claim 4 , wherein g i,j =1 indicates that the set S i  has a subset that sums to j and g i,j =0 indicates that the set S i  does not have a subset that sums to j, and the subset sum module is configured to populate the rows of the matrix by setting g 0,j =1 for j=0 and g 0,j =0 for j>0 and using the recursion g i,j =1 iff (g i−1,j =1 or g i−1,j−k     i   =1) where c i ≦k≦a i . 
     
     
         10 . An automated trading system according to  claim 4 , further comprising means for ordering the set orders into a sequence with respect to price and wherein the subset sum module is configured to select said one more order as the next order in the sequence. 
     
     
         11 . An automated trading according to  claim 4 , wherein
 the trading module further comprises means for finding the highest common sum of said subset sums for the bid orders and said subset sums for the ask orders and the order matching module is configured to determine a combination of bid orders and a combination of ask orders that sum to the highest common sum.   
     
     
         12 . An automated trading system according to  claim 11 , wherein the order matching module is configured to find, from the set of orders, a solution subset that sums to the highest common sum by
 a) setting parameter V equal to the highest common sum;   b) finding the one more order added to form the set corresponding to the lowest row in the matrix with subset sum V;   c) adding this order to the solution subset;   d) determining the volume of said one more order that is allowed to trade and the volume V next  that remains after said one more order is allowed to trade the determined volume;   e) setting V=V−V next ; and   f) repeating steps b) to e) until V=0.   
     
     
         13 . An automated trading system according to  claims 4 , further comprising an equilibrium price calculation module configured to determine the turnover at each possible price based on said matrix. 
     
     
         14 . An automated trading system according to  claim 1 , wherein the interface is configured to receive the plurality of orders from a plurality of user terminals, the order matching module is configured to create trades between said combination of bid orders and said combination of ask orders; and the interface is further configured to communicate information about the matched orders that are allowed to trade to said user terminals. 
     
     
         15 . A method for matching orders in an automated trading system comprising:
 receiving a plurality of orders in an automated trading system, the plurality of orders comprising bid orders and ask orders;   storing the plurality of orders submitted to the system in an order book;   determining the subset sums of a set or orders corresponding to the bid orders and determining the subset sums of a set or orders corresponding to the ask orders; and   matching a combination of bid orders to a combination of ask orders based on the subset sums for the bid orders and the subset sums for the ask orders,   wherein determining the subset sums of a set of orders comprises:
 considering a first set of orders, 
 determining the subset sums of the first set of orders, 
 considering a second set of orders wherein the second set of orders comprises at least one more orders than the first set of orders, and 
 determining the subset sums of the second set of orders by using the determined subset sums of the first set of orders. 
   
     
     
         16 . A method according to  claim 15 , wherein the set of orders comprise orders a i  with minimum volume conditions c i , and the wherein determining the subset sum of a set of orders comprises determining a value g i,j  indicating whether a set S i ={a 1 , . . . a i } comprises a subset that sums to value j by noting that set S i ={a 1 , . . . a i } has a subset that sums to j, if S i−1  has a subset that sums to j or if S i−1  has a subset that sums to j−k, where c i ≦k≦a i . 
     
     
         17 . A method according to  claim 16 , wherein the minimum volume condition orders comprise at least one All-or-None (AoN) order, wherein k=a i =c i . 
     
     
         18 . A method according to  claim 16 , wherein determining the subset sum of a set of orders comprises:
 constructing a matrix in which every row correspond to a set of orders, S i,j  every column corresponds to a subset sum j and the element g i,j  at a particular position i,j indicates whether the set S i  has a subset summing to value j, and   populating a new row by considering a set of orders comprising one more order than the set of orders corresponding to the previous row and using the values of the elements of the previous row.   
     
     
         19 . A method according to  claim 18 , wherein said one more order added is an AoN order, and populating said new row comprises:
 adding a first copy of the previous row to said new row, and   adding a second copy of the previous row, shifted a number of columns corresponding to the volume of said one more order, to the new row.   
     
     
         20 . A method according to  claim 19 , wherein the one more order is any minimum volume condition order, and populating said new row comprises:
 adding a first copy of the previous row to said new row, and   adding a second copy of the previous row, shifted a number of columns corresponding to a possible volume of said one more order and smeared to represent all the possible volumes of the order, to the new row.   
     
     
         21 . A method according to  claim 20 , wherein the second copy is shifted a number of columns corresponding to the minimum volume of said one more order and populating said row further comprises:
 adding the second copy, shifted said number of columns, to a temporary row; and   setting element g i,j  in the temporary row to indicate that j is a subset sum if g i,j−m  of the second copy of the previous row, shifted said number of columns, indicates that j-m is a subset sum of the previous row, where m is an integer 0<m≦a i −c i .   
     
     
         22 . A method according to  claim 18 , wherein g i,j =1 indicates that the set S i  has a subset that sums to j and g i,j =0 indicates that the set S i  does not have a subset that sums to j, and the populating said row comprises setting g 0,j =1 for j=0 and g 0,j =0 for j>0 and using the recursion g i,j =1 iff (g i−1,j =1 or g i−1,j−a =1). 
     
     
         23 . A method according to  claim 18 , wherein g i,j =1 indicates that the set S i  has a subset that sums to j and g i,j =0 indicates that the set S i  does not have a subset that sums to j, and populating said row comprises setting g 0,j =1 for j=0 and g 0,j =0 for j>0 and using the recursion g i,j =1 iff (g i−1,j =1 or g i−1,j−k     i   =1) where c i ≦k≦a i . 
     
     
         24 . A method according to  claim 18 , wherein the method further comprises ordering the orders in terms of price into a sequence and selecting said one more order as the next order in the sequence. 
     
     
         25 . A method according to  claim 18 , wherein matching a combination of bid orders to a combination of ask orders comprises determining the highest common sum of said subset sums for the bid orders and said subset sums for the ask orders. 
     
     
         26 . A method according to  claim 25  wherein matching a combination of bid orders to a combination of ask orders further comprises determining, from the set of orders, a solution subset that sums to the highest common sum by:
 a) setting parameter V equal to the highest common sum; 
 b) finding the one more order added to form the set corresponding to the lowest row in the matrix with subset sum VII; 
 c) adding this order to the solution subset; 
 d) determining the volume of said one more order that is allowed to trade and the volume V next  that remains after said one more order is allowed to trade the determined volume; 
 e) setting V=V−V next ; and 
 f) repeating steps b) to e) until V=0. 
 
     
     
         27 . A method according to  claim 18 , further comprising:
 determining the turnover at each equilibrium price of a set of orders based on the constructed matrix.   
     
     
         28 . A method according to  claim 18 , wherein receiving a plurality of orders comprises receiving a plurality of orders from a plurality of member terminals, the method further comprises creating trades between the combination of ask orders and the combination of bid orders and communicating information about the matched orders that are allowed to trade to said member terminals. 
     
     
         29 . (canceled) 
     
     
         30 . An automated trading system, comprising:
 a trading module for matching orders, the trading module comprising a memory storing a plurality of orders submitted to the system and a subset sum module configured to find the subset sums of a set of orders of the plurality of orders by considering a first set of orders of the set of orders, determining the subset sums of the first set of orders, considering a second set of orders of the orders wherein the second set of orders comprises at least one more order than the first set of orders and determining the subset sums of the second set of orders by using the determined subset sums of the first set of orders.   
     
     
         31 . A method for matching orders in an automated trading system comprising:
 storing an order book comprising a plurality of orders submitted to the system;   determining the subset sums of a set of orders of the plurality of orders by:
 considering a first set of orders of the set of orders, 
 determining the subset sums of the first set of orders, 
 considering a second set of orders wherein the second set of orders comprises at least one more orders than the first set of orders, and 
 determining the subset sums of the second set of orders by using the determined subset sums of the first set of orders.