x 1 ≤ 100 (7)
x 2 ≤ 100 (8)
x 3 ≤ 100 (9)
x 4 ≤ 100 (10)
x 5 ≤ 100 (11)
x 6 ≤ 100 (12)
x 1 ,x 2 , ...,x 6 ≥ 0Let us examine the formulation shown here. The objective in the linear
program is the sum of the flows across all the edges, and we are right-
fully looking to maximize this quantity. Constraints 1–3 state that the total
outflow from a bidder node must not be greater than the share quantity of
that node. Likewise, constraints 4–6 ensure that the inflow into a target
node must not be greater than the share quantity of the node. The con-
straints 7–12 fix the maximum capacity of every edge. Thus, maximizing
the flow along this bipartite network leads us to a solution for our pairing
problem.
The solution approach to the general max-flow problem has been well
researched and a number of algorithms have been proposed to solve it. Also,
the pairing problem we address has a special structure. On account of this,
the solution method that would work for us is fairly straightforward. A de-
tailed description of both the general method and one tailored to our prob-
lem can be found in the appendix. The important point, however, is that the
modeling process and the solution method provide us with some insights
into the nature of the pairing problem itself.
In fact, the solution approach reveals that the answer to the pairing
problem is not unique, and it is possible to have a number of optimal paring
configurations for a given set of executions. Looking at Figure 10.2 we can
see that there are at least three possible configurations for the given set of ex-
ecutions in Table 10.1, begging the question as to which configuration we
should use to measure execution efficiency. It is now easy to appreciate the
futility of measuring efficiency by way of pairing. Note, however, that the
average achieved spread is a constant value regardless of the pairing config-
uration. We therefore contend that it is this measure that should form the
basis for verifying executions.
There is a flip side to looking at just the average spread. The broker may
trade away the edge gained on an earlier execution, of course ensuring that
the average spread criteria is met. To see what we mean, consider the situa-
tion with a target spread of $1.00 where the broker has completed about
half of the whole order, achieving a spread of $1.05. To satisfy the average
criterion, the broker needs to achieve a spread of just $0.95 on the remain-
ing half, which may not be what was intended by the arbitrageur.
Trade Execution 159