of 17

Batchauctions

Description
1. Multi-token Batch Auctions with Uniform Clearing Prices - Features and Models Tom Walther tom@gnosis.pm June 1, 2018 ... abstract ... 1. Contents 1 Introduction 2 2…
Transcript
  • 1. Multi-token Batch Auctions with Uniform Clearing Prices - Features and Models Tom Walther tom@gnosis.pm June 1, 2018 ... abstract ... 1. Contents 1 Introduction 2 2 Problem statement 3 2.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Models and Formulations 6 3.1 Nonlinear programming model . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Mixed-integer linear programming model I . . . . . . . . . . . . . . . . . . . 9 3.3 Mixed-integer linear programming model II . . . . . . . . . . . . . . . . . . . 12 3.4 Mixed-integer linear programming model III . . . . . . . . . . . . . . . . . . 15 3.5 Min-cost flow model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.6 Computational comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4 Extensions 17 1 ... footnote ... 1
  • 2. 1 Introduction In continuous-time token exchange mechanisms, orders are typically collected in order books of two tokens that are traded against each other. A trade happens whenever a buy order of one token is matched by a sell order of the other, i.e., if there exists an exchange rate that satisfies the limit prices stated in the respective orders. In a setting of multiple tradeable tokens, one separate order book is required for every token pair combination. This may significantly limit liquidity for less frequently traded token pairs and lead to large bid-ask spreads and low trading volumes. In our approach, we want to collect orders for a set of multiple tokens in a single joint order book and compute exchange prices for all token pairs simultaneously at the end of discrete time intervals (multi-token batch auction). Trades between the same token pairs are then all executed at the same exchange rate (uniform clearing price). Moreover, this mechanism enables so-called ring trades, where orders are matched along cycles of tokens. In order to exclude arbitrage opportunities, we require prices to be consistent along such cycles, i.e., we want the constraint pA|B · pB|C = pA|C (1) to be satisfied for the prices of all tokens A,B,C. In this document, we want to describe the problem of determining uniform clearing prices for all pairs of tokens involved in a multi-token batch auction process, as well as present a mixed-integer programming solution approach. 2
  • 3. 2 Problem statement 2.1 Data Let T := {t0 . . . tn−1} denote the set of the n tokens that we want to consider. The token t0 shall be referred to as reference token, which will become important in our modelling approaches later on in Section 3. For convenience of notation, we use It := {0 . . . n − 1} to denote the indices of our token set. Pairwise exchange rates between two tokens ti and tj will be denoted by pi|j, meaning the price of one unit of ti measured in units of tj. As an example, if pi|j = 10, one would need to pay an amount of 10 units of tj in order to purchase a unit of ti. Let there be a set O = {o1 . . . oN } of N limit orders in the batch to be processed and let Ib, Is ⊆ {1 . . . N} =: Io denote the sets of indices of buy and sell orders, respectively. Every order must be of exactly one of the two types, so Ib ∩ Is = ∅ and Ib ∪ Is = {1 . . . N}. Moreover, every buy order consists of a tuple (tjb , tjs , x, π) that is to be read as ”Buy (at most) x units of token tjb for token tjs if the rate pjb|js is at most π”. Analogously, every sell order is represented by a tuple (tjs , tjb , y, π) with the meaning ”Sell (at most) y units of token tjs for token tjb if the rate pjs|jb is at least π”. The semantics of the two order types are somewhat similar in that there is one token to be exchanged against another, if a certain limit price is guaranteed. Such orders are hence referred to as limit orders. The difference between buy and sell orders is the following: • In a buy order, a fixed (maximum) buy volume x is set, so the buyer indicates a preference to buy x units of token tjb . The amount of units of token tjs to be sold is flexible, as long as the limit price is respected (the smaller, the better). • In a sell order, a fixed (maximum) sell volume y is set, so the seller indicates a preference to sell y units of token tjs . The amount of units of token tjb to be bought is flexible, as long as the limit price is respected (the higher, the better). Nevertheless, the question remains whether it makes sense to keep the distinction between buy and sell orders. Consider a buy order (tjb , tjs , x, π), which reveals that the buyer would be ready to sell at most π · x tokens tjs in exchange for tokens tjb . Then, from an economically rational point of view, the buyer should not object to receiving more than x tokens tjb for a maximum of π · x tokens tjs , i.e., if the exchange rate pjb|js is lower than π. Hence, the buy order could be translated into an equivalent sell order (tjs , tjb , π · x, π). In this paper, however, we will continue to treat the different order types separately. 3
  • 4. 2.2 Objectives Having collected a batch of buy and sell orders for our set of tokens, we ultimately want to compute exchange rates for all token pairs. Therefore, the following optimization criteria could be used: • maximize the amount of trade that is enabled (w.r.t. some reference token) • maximize trader welfare, e.g., defined as difference of paid price vs. limit price 2.3 Constraints The solution that we are aiming at needs to satisfy several requirements that can stated on a high level as follows: • (buy limit price): for all buy orders oi ∈ O, i ∈ Ib: the order can only be executed (fully or fractionally) if the exchange rate does not exceed the stated limit price, i.e., pb|s ≤ π. • (sell limit price): for all sell orders oi ∈ O, i ∈ Is: the order can only be executed (fully or fractionally) if the exchange rate is not lower than the stated limit price, i.e., ps|b ≥ π. • (token balance): for every token tj ∈ T : the amount of tokens tj that were bought must equal the amount of tokens tj that were sold. • (price coherence): for all token pairs (tj, tk): pj|k · pk|j = 1. • (arbitrage freeness): for all token triples (tj, tk, tl): pj|k · pk|l = pj|l. Lemma 2.1. (arbitrage freeness) ⇒ (price coherence). Proof. Consider three tokens {tj, tk, tl} ⊂ T . We apply the arbitrage-freeness condition twice: (i) pj|k · pk|l = pj|l (ii) pj|l · pl|k = pj|k Inserting (i) into (ii) yields pj|k · pk|l · pl|k = pj|k ⇔ pk|l · pl|k = 1 Notice that the above constraints also imply pj|j = 1 for every token tj ∈ T . 4
  • 5. 2.4 Properties (Before presenting different modelling approaches and formulations for the batch auction problem, we first want to analyse/show some important properties.) Here is a list of research questions that we would like to answer. • In an optimal solution, is it guaranteed that orders can always be fully executed if their limit prices are strictly higher (buy order) or lower (sell order) than the exchange rate between the respective token pair? If true, we would only need to resort to partially executing orders if the execution price is equal to the limit price. • Does the optimal solution depend on the choice of the reference token, or not? • What is the impact of optimizing the trading volume vs. the traders’ welfare? 5
  • 6. 3 Models and Formulations In this section, we want to present and discuss several solution approaches for our batch auction problem, mainly in terms of mathematical optimization formulations. We will begin with a nonlinear programming formulation (NLP) and proceed with mixed-integer linear (MIP) and network flow formulations thereafter. With the exchange rates between pairs of tokens being variables, modelling arbitrage-freeness constraints of type (1) intuitively leads to many multiplications being required. This may result in unnecessary limitations to the problem size that is tractable as well as numerical instability. However, we can do better by not considering all pairwise token rates explicitely but represent all token prices only with respect to a single reference token t0. Let pj := pj|0 denote the price of token tj expressed in units of token t0 (hence, p0 = 1). Applying the arbitrage-freeness and price-coherence conditions directly, we can express the exchange rate between two tokens tj and tk as pj|k = pj|0 · p0|k = pj|0 pk|0 = pj pk . (2) Data In the following, we will express all information given in the orders in terms of data matrices and vectors, aiming at being able to write down a complete optimization model. We introduce two data matrices Tb ∈ {0, 1}N×n with Tb tb i,j = 1 ⇔ token tj to be bought in order oi Ts ∈ {0, 1}N×n with Ts ts i,j = 1 ⇔ token tj to be sold in order oi As for now, we are only considering orders of one token type against one other, so there must be exactly one entry equal to 1 per row (order) in both Tb and Ts. The maximum number of units of tokens to be bought in an order oi shall be denoted by xi and stored, for all orders, in a vector x ∈ RN ≥0 ∪ {+∞}. Generically, xi takes a finite value if oi is a limit buy order (i.e., i ∈ Ib). In case oi is a sell order (i.e., i ∈ Is), xi can be set to infinity, since the seller does specify an upper limit on the tokens to be received. Similarly, let (yi) =: y ∈ RN ≥0 ∪ {+∞} contain the maximum amounts of tokens to be sold in every order. For all limit sell orders oi, we have yi < ∞. On the other hand, if oi is a limit buy order, we can either set yi = +∞ and rely on the implicit bound given via the limit price πi (as defined below), or state it explicitely as yi = xi · πi. 6
  • 7. The limit prices of all orders shall be stored as vector (πi) =: π ∈ RN ≥0, where πi ∈ π refers to the exchange rate between the respective buy and sell tokens at which order oi may be executed (according to the definition in Section 2.1). 3.1 Nonlinear programming model The first model that we developed involves nonlinear constraints through multiplication of token amounts and prices, but does not require binary variables. Variables We represent all token prices in a vector p ∈ Rn ≥0, i.e., pj denotes the price of token tj w.r.t. the reference token t0. It makes sense to incorporate some explicit lower and upper bound for the price of every token tj (for instance, in order to avoid excessive fluctuations), so let us require pj ∈ [pj , pj]. These bounds could for example be derived as half/double the previous token prices, or simply be set to some low/high values that appear reasonable and justified. However, the tighter the bounds, the better the optimization algorithm will perform. Since we want the price of the reference token to be p0 = 1, we set p0 = p0 = 1. The price bounds shall be stored in vectors p and p, respectively. For the executed volumes of all orders, we define a vector v ∈ RN , where vi ∈ v contains the traded volume of order oi in terms of units of the reference token t0. The number of tokens bought in an order oi shall be denoted by xi, with (xi) =: x ∈ RN ≥0. Conversely, (yi) =: y ∈ RN ≥0 represents the amount of tokens sold per order. 7
  • 8. Model maximize i∈Io vi (3a) subject to i∈Io tb i,j xi = i∈Io ts i,j yi ∀ j ∈ It (3b) vi = xi j∈It tb i,j pj ∀ i ∈ Io (3c) vi = yi j∈It ts i,j pj ∀ i ∈ Io (3d) xi ≤ xi ∀ i ∈ Ib (3e) yi ≤ xi πi ∀ i ∈ Ib (3f) yi ≤ yi ∀ i ∈ Is (3g) xi ≥ yi πi ∀ i ∈ Is (3h) xi, yi, vi ∈ R≥0 ∀ i ∈ Io (3i) The objective function (3a) maximizes the total volume in terms of units of the reference token t0 that is processed with all orders. Constraint (3b) ensures that the total numbers of tokens bought and sold are equal for every token across all orders. The summations in this constraint are only responsible for selecting the correct tokens that are traded in the orders. The constraints (3c) and (3d) compute the buy and sell trade volume for every order w.r.t. the reference token, and make sure these two are equal. This guarantees that the token prices are chosen such that they are consistent with the traded amounts of tokens. If the traded token amounts xi and yi are zero for some order oi, i.e., oi is not executed at all, the corresponding trade volume vi will be zero as well. However, this comes at the price of introducing nonlinearity (and even nonconvexity) into the model. Finally, the limits in terms of token amounts to be bought/sold in a limit order are incorpo- rated into the model via the constraints (3e)–(3h). One major weakness of the model is the fact that orders can be left unexecuted even if the 8
  • 9. computed token prices satisfy the given limit price. We believe that this can only be cured with the introduction of binary variables that indicate whether prices allow for an order to be executed, or not. 3.2 Mixed-integer linear programming model I As an alternative to the NLP model presented above, we are now going to propose a mixed- integer linear programming formulation. Variables In addition to the same price and volume variables as in the NLP model (3), p ∈ Rn and v ∈ RN , respectively, the MIP model requires several other variables. First and foremost, let z ∈ {0, 1}N be a vector of binary variables, where zi ∈ z indicates whether order oi may be (fully or partially) executed, or not. Precisely, we require z = 1 if and only if the prices of the tokens that are present in the order satisfy the respective limit price πi, otherwise z = 0. The feasible region for the execution volume vi of an order oi depends on the value of zi. In particular, vi must be set to zero if zi = 0 and can only be non-zero otherwise. In order to model this disjoint behaviour, we make use of a disjunctive programming formulation that needs the following auxiliary non-negative price variable vectors: pb,0 , pb,1 , ps,0 , ps,1 ∈ RN ≥0. Parameters The model allows for setting a minimum and maximum fraction of execution for every order. For now, we will use global values 0 ≤ r ≤ r ≤ 1 and for all current purposes set r = 1. 9
  • 10. Model maximize i∈Io vi (4a) subject to i∈Io tb i,j vi = i∈Io ts i,j vi ∀ j ∈ It (4b) j∈It tb i,j pj (1 − zi) ≤ pb,0 i ≤ j∈It tb i,j pj(1 − zi) ∀ i ∈ Io (4c) j∈It ts i,j pj (1 − zi) ≤ ps,0 i ≤ j∈It ts i,j pj(1 − zi) ∀ i ∈ Io (4d) j∈It tb i,j pj zi ≤ pb,1 i ≤ j∈It tb i,j pjzi ∀ i ∈ Io (4e) j∈It ts i,j pj zi ≤ ps,1 i ≤ j∈It ts i,j pjzi ∀ i ∈ Io (4f) j∈It tb i,j pj = pb,0 i + pb,1 i ∀ i ∈ Io (4g) j∈It ts i,j pj = ps,0 i + ps,1 i ∀ i ∈ Io (4h) pb,0 i ≤ πi ps,0 i (1 − ε) ∀ i ∈ Ib (4i) pb,1 i ≥ πi ps,1 i ∀ i ∈ Ib (4j) vi ≥ r xi pb,1 i ∀ i ∈ Ib (4k) vi ≤ r xi pb,1 i ∀ i ∈ Ib (4l) ps,0 i ≤ πi pb,0 i (1 − ε) ∀ i ∈ Is (4m) ps,1 i ≥ πi pb,1 i ∀ i ∈ Is (4n) vi ≥ r yi ps,1 i ∀ i ∈ Is (4o) vi ≤ r yi ps,1 i ∀ i ∈ Is (4p) zi ∈ {0, 1} ∀ i ∈ Io (4q) vi, pb,0 i , pb,1 i , ps,0 i , ps,1 i ∈ R≥0 ∀ i ∈ Io (4r) pj ∈ R≥0 ∀ j ∈ It (4s) 10
  • 11. The objective function (4a) maximizes the total volume in terms of units of the reference token t0 that is processed with all orders. Constraint (4b) secures that the total buy and sell volumes across all orders must be equal for every token. With uniform clearing prices, volume balance implies token balance. The auxiliary variables in pb,0 and ps,0 refer to the prices of the buy- and sell-token of every order oi if that order is not executed (zi = 0). In that case, their values must then lie within in the respective bounds provided by p and p, and otherwise shall be set to zero. This requirement is ensured by the constraints (4c) and (4d). Note that the summations in the constraints are only needed to ensure that the right variable is selected from the respective variable vector. Similarly as above, the constraints (4e) and (4f) control the auxiliary variables in pb,1 and ps,1 for the case that an order oi is executed (zi = 1). The relation between the auxiliary price variables and the actual token prices is established by the constraints (4g) and (4h). For buy orders, the disjunctive behaviour is modelled by the constraints (4i)–(4l). The idea is as follows: If some order oi is not to be executed (zi = 0), then the prices pb,0 i and ps,0 i must both lie within the bounds given by (4c) and (4d) as well as fulfill (4i) (i.e., not satisfy the limit price). We want to ensure that the token prices are at least a little margin off the stated limit price in that case, hence the multiplication with (1 − ε). At the same time, pb,1 i and ps,1 i are set to zero by (4e) and (4f), thus trivially satisfying (4j). This then also implies the volume vi to be set to zero by (4k) and (4l). Conversely, if oi is to be executed (zi = 1), pb,0 i and ps,0 i are set to zero by (4c) and (4d), while pb,1 i and ps,1 i lie within the bounds provided by (4e) and (4f) as well as fulfill (4j) (i.e., satisfy the limit price). This finally requires the execution volume vi to be within the specified fractions via the constraints (4l) and (4l). The reasoning is analogous for sell orders and expressed by (4m)–(4p). Computational results The following Table 1 should give an indication of the solving times of the model w.r.t. different numbers of tokens and orders. Every entry in the table represents the mean solving time of a set of 10 instances. The buy/sell token quantities and limit prices of the orders have been randomly generated. In order to guarantee feasibility for all instances, we have selected a value of r = 0, so the solver may choose to execute 0% of an order even if the token prices 11
  • 12. # orders per token pair # tokens (# pairs) 4 8 20 40 2 (1) 0.05 0.06 0.08 0.10 3 (3) 0.07 0.12 0.31 0.89 4 (6) 0.13 0.24 0.74 3.09 5 (10) 0.25 0.69 4.22 84.36 6 (15) 0.40 2.04 77.32 684.40 Table 1: Solving times in [s] of the MIP formulation to global optimality. comply with the limit price. We have modelled the problem using Python/Pyomo and employed Gurobi 7.5.2 as a solver. It can be seen that the running times increase sharply for 5 or more tokens and the many- order cases. One influencing factor might be the equal number of orders for all token pairs in our testset, which leads all token prices being maximally interconnected and which might not occur as such in practice. On the other hand, the more orders there are on some token pair, the denser the stated limit prices become, which might make it possible to aggregate orders as a means of preprocessing. 3.3 Mixed-integer linear programming model II The previous MIP model (4) considers all orders independent from each other, i.e., the deci- sion whether some order should be executed or not is not explicitely connected to the decision for other orders. The connection is only indirectly established through the propagation of feasible price ranges. In practice, however, there is more structure to the execution of orders, particularly within the same token pair. For instance, if some sell order with limit price π∗ is enabled by the current choice of prices, all other sell orders with higher limit prices should be executed as well (and vice-versa for buy orders). This insight gives rise to an alternative MIP formulation that we will present in the following. Data We want to aggregate orders on every pair of tokens that is traded, so let the set of token index pairs be denoted by Ip := {(j, k) ∈ It × It, j = k}, with (j, k) ∈ Ip representing the pair of tokens tj and tk. Notice that we consider the token pairs to be ordered tuples, so (j, k) ∈ Ip and (k, j) ∈ Ip are treated separately. For every token pair (j, k) ∈ Ip, we collect all buy and sell orders (tj, tk, · , · ) that were 12
  • 13. submitted for (j, k), and sort them in an increasing order by their limit prices. Assuming that there are m orders for token pair (j, k), we get pj|k =: π (0) j,k < π (1) j,k < π (2) j,k < . . . < π (m) j,k
  • 17 pages
    Free
    103 views
    0 times
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks