Final_1.pdf

(^3) The linear programming formulation here is different from the conventional linear
programming representation of the max-flow problem. The interpretation of the
dual in this case is a minimum weighted set cover problem. However, since this is not
germane to the discussion, we will not pursue this in detail.
Note that in Figure 10.1 we have explicitly shown the source and the
sink to identify the direction of flow, which should be from the source to the
sink. Each node represents an execution, and the details of the execution are
listed for each node. The maximum capacity of each edge is not shown in the
picture but is actually the smaller of share quantities of the nodes on either
end of the edge. The pairing problem is now equivalent to maximizing the
flow on this bipartite network. The linear programming formulation^3 may
be written as
Maximizex 1 +x 2 +x 3 +x 4 +x 5 +x 6
sub:
x 1 ≤ 100 (1)
x 2 +x 3 ≤ 100 (2)
x 4 +x 5 +x 6 ≤ 100 (3)
x 4 ≤ 100 (4)
x 2 +x 5 ≤ 150 (5)
x 1 +x 3 +x 6 ≤ 150 (6)
158 RISK ARBITRAGE PAIRS
FIGURE 10.1 The Max-Flow Formulation.
100 at
$19.0
100 at
$19.5
100 at
$20.0
Source
50 at
$19.0
150 at
$18.5
150 at
$18.0
Sink
x 1
x 3
x 6
x 5
x 2
x 4
Bidder Trades Target Trades