A Symbolic Closed-Form Solution to Sequential Market Making with Inventory

1 Introduction

Financial markets are well known for their volatility [Mandelbrot, 1963; Sornette, 2004; Volt, 2005]. A prime driver of high volatility are periods of great uncertainty, such as those following price shocks, about the value of the assets being traded. These periods can lead to sparse trading, where there are few offers and counter-offers, which effectively stop markets from functioning. Market-makers (MMs) can be used in these situations to attract trading and maintain order in markets. Examples of markets which employ MMs include the NASDAQ, which allows for multiple MMs to compete, and prediction markets [Hanson, 2003; 2007].

Market-makers do not perform their services ex gratia. They aim to extract a profit, which is a component of what is known as the bid-ask spread. When setting the bid and ask price, MMs must trade-off between setting prices to extract maximum profit from the next trade versus setting prices to get as much information about the new value of the asset so as to generate larger profits from future trades.

In this paper we recast the sequential market-making problem as a new general class of continuous state Partially Observable MDPs (POMDPs) [Kaelbling et al., 1998] that subsumes our proposed market-making model and admits closed-form solutions. We also provide a Symbolic Dynamic Programming (SDP) [Boutilier et al., 2001] based algorithm that can efficiently derive a value function and policy for this new class of POMDPs.

By utilising the POMDP framework we enable several new advances in algorithmic market-making:

• ÷ We are the first to address the open question of sequentially optimal market-making with inventory based reasoning by extending the seminal work of Glosten and Milgrom [1985], Amihud and Mendelson [1980] and Das and Magdon-Ismail [2008].
• ÷ Our solution is more general than previous solutions and allows the use of arbitrary belief state priors to represent the MM's uncertainty about the true value of the asset, asymmetric bid-ask spreads around the mean of the MM's belief, flexible models of trader behaviour and a variety of inventory-based rewards with both hard constraints and preferences.
• ÷ Our solution provides sequentially optimal policies which maximise MM profit under a variety of inventory conditions and trader models, while simultaneously bounding loss. Previous solutions which neglected inventory are prone to selecting sub-optimal bid-ask spreads which may lead to unexpected losses.

2 Background

Market-makers serve an important liquidity provision role in many financial markets by providing immediacy to transactions. In practice MMs often operate in tandem with a continuous double auction [Smith et al., 2003] market structure in which both buyers and sellers submit limit orders in the form of bids and asks which are then matched algorithmically. Theoretical models of market-making typically abstract away limit orders from other traders and model the market as a dealer market, with the MM taking one side of every order. In these models it is common for the MM to quote a bid price, a price at which they are willing to buy some number of shares, and an ask price, the price at which they are willing to sell some number of shares, at every point in time. The difference between the two prices, known as the bid-ask spread, serves three main purposes: (1) to provide an incremental profit to motivate the MM to actually provide their services; (2) to compensate the MM for the risk inherent in holding inventory [Amihud and Mendelson, 1980]; and (3) to compensate the MM for the adverse selection encountered in trading with a potentially more informed population [Glosten and Milgrom, 1985].

In recent history, research into algorithmic market-making has focussed on financial [Das, 2008] and prediction market settings [Chen and Pennock, 2007; Othman and Sandholm, 2012]. Market-making in prediction markets starts from the notion of a proper Market Scoring Rule (MSR) [Hanson, 2003]. Proper MSRs are both myopically incentive compatible, that is, they incentivize agents to move prices to their valuation, and are also loss-bounded, at least in bounded-payoff markets. Despite these attractive features, proper MSRs are, in general, loss-making [Pennock and Sami, 2007] and MMs using proper MSRs must be subsidised in order to perform their task of liquidity provision. Although there has been some theoretical work on the design of MMs that can adapt their spread over time [Othman et al., 2010] they can be highly sensitive to the price path [Brahma et al., 2012].

Learning based approaches to market-making in financial markets attempt to infer either underlying values or future prices based on trader models [Das, 2008; Das and MagdonIsmail, 2008] or time-series analysis of prices [Chakraborty and Kearns, 2011]. Such models have been used to formulate efficient algorithms under zero-profit (competitive) conditions where, in perfect competition, the MM is pushed to setting bid and ask prices that yield a zero expected profit [Das, 2005]. An algorithm for a profit-maximising (monopolist) MM was presented by Das and Magdon-Ismail [2008]. In this setting with a fixed underlying asset value, bid and ask prices are set in a way that maximises the total discounted profit obtained by the MM. The profit-maximising marketmaking algorithm was cast as a belief state MDP where the MM's belief about the value of the asset was described by a Gaussian density function. The MM sets bid and ask prices based on the solution of the Bellman equation for a Gaussian belief state approximation of this MDP. While these models are promising in terms of their potential to provide liquidity while simultaneously operating at a profit, they come with no guarantees on worst case loss, since they do not take inventory into account when setting prices.

In this paper we study the problem of optimising profit while still maintaining inventory-sensitivity, the natural way to bound risk in the market-making setting. We present a new formalism for optimal sequential market-making based on continuous state POMDPs which allows for arbitrary belief state distributions, asymmetric bid-ask spreads, flexible trader models and a variety of inventory-based rewards, while still admitting exact closed-form solutions.

3 Market-Making as a POMDP

In this section we introduce our first contribution, a novel and flexible continuous state POMDP framework for sequentially optimal market-making with inventory that admits closedform dynamic programming solutions.

3.1 POMDP Preliminaries

A POMDP is defined by the tuple hS↪ A↪ T ↪ R↪ O↪ ⌦↪ H↪ γi [Kaelbling et al., 1998]. S specifies a potentially infinite (e.g., continuous) set of states while A and O respectively specify a finite set of actions and observations. The transition function T : S ⇥ A ⇥ S ! [0↪ 1] defines the effect of an action on the state. ⌦ : O ⇥ A ⇥ S ! [0↪ 1] is the observation function which defines the probability of receiving an observation given that an agent has executed an action and reached a new state. R : S ⇥ A ! R is the reward function which encodes the preferences of the agent. H represents the number of decision steps until termination and the discount factor γ 2 [0↪ 1) is used to geometrically discount future rewards.

Partial observability is encapsulated within a probabilistic observation model specified by O and ⌦, which relates possible observations to states. POMDP agents maintain a belief b 2 ∆(S), a probability distribution over S. Beliefs provide sufficient statistics for the observable history of a POMDP agent without loss of optimality [Astr¨om, 1965].

The objective of a POMDP agent is to find an optimal policy ⇡⇤ : ∆(S) ! A, which specifies the best action to take in every belief state b so as to maximise the expected sum of discounted rewards over the planning horizon H. The value function under the optimal policy can be written as:

The POMDP value function can be parameterized by a finite set of functions linear in the belief representation known as ↵-vectors and is convex in the belief [Sondik, 1971].

The value function at a given belief b 2 ∆(S) can be calculated using:

Monahans exact Value Iteration [Monahan, 1982] algorithm has been extended to a more efficient class of pointbased algorithms [Pineau et al., 2003] which considers only a finite subset of the belief space B. We cover such methods in Section 4.2. The results from the discrete state setting presented above can be generalised to the continuous case by replacing s, ↵-vectors and P by their continuous state counterparts ~x, ↵-functions and R , respectively [Porta et al., 2006].

In the next section we show how the expressive POMDP framework can be used to encapsulate an optimal sequential market-making model with inventory.

3.2 Optimal Sequential Market-MakingModel

The market-making model used in this paper extends the seminal theoretical model of Glosten and Milgrom [1985] and the sequential model of Das and Magdon-Ismail [2008] by incorporating the inventory control conditions of Amihud and Mendelson [1980] as well as arbitrary belief state priors, trader models and asymmetric bid-ask spreads.

We begin by formulating the MM's sequential decision problem in the POMDP framework:

• ÷ S = hv↪ ii, where v 2 R+ represents the value of the asset and i 2 N represents the MM's inventory.
• ÷ A = ¶(bid1↪ ask1) ↪ ▷ ▷ ▷ ↪ (bidN↪ askN)♦ represents a finite set of allowed N bid-ask pairs, where bidn↪ askn 2 R+ and bidn < askn.

The bid represents the price at which the MM is willing to buy one unit of the asset and the ask is the price at which the MM is willing to sell one unit of the asset.

• ÷ O = ¶buy↪ sell ↪ hold♦ represents the possible actions of a trader at each time step.

At each time step the MM interacts with a trader t drawn from a heterogeneous population of traders with a known prior distribution. The trader has an uninformed estimate of the value of the asset vt = v + ✏t, where ✏t 2 R specifies the noise. In this paper we allow the traders to be specified according to two trader models: (1) Glosten-Milgrom (GM) [Glosten and Milgrom, 1985]; and (2) Discrete noise (D). In the traditional GM setting, traders are either informed or uninformed, with ✏t set to 0.0. The Discrete setting involves informed, over-valuing and under-valuing traders, with ✏t set to 0.0, constant c 2 R and constant -c 2 R, respectively.

With the exception of uninformed traders, an arriving trader of type t will execute a buy order at an ask price askn if vt > askn, a sell order at the bid price bidn if vt < bidn, and will hold otherwise. We use an intermediate variable u ⇠ P(O), with P(u) = 1◁3 for uninformed trader orders.

• ÷ The transition function T for each state variable in S is given by:

The Dirac function δ[·] ensures that the transitions are valid conditional probability functions that integrate to 1▷0. The value v is assumed to be fixed but unknown to the MM. The inventory i increments or decrements according to the observed trader action.

• ÷ The observation function ⌦ for each trader action is specified by:

⌦ (buy♣i↪ v↪ bid↪ ask↪ t = informed↪ u) = ((v > ask + ✏t) ^ (i ≥ 1) : 1 otherwise : 0 ⌦ (sell ♣i↪ v↪ bid↪ ask↪ t = informed↪ u) = ((v < bid+ ✏t) : 1 otherwise : 0 ⌦ (hold ♣i↪ v↪ bid↪ ask↪ t = informed↪ u) = ((v > bid+ ✏t) ^ (v < ask + ✏t) : 1 otherwise : 0 ⌦ (o♣i↪ v↪ bid↪ ask↪ t = uninformed↪ u) = I [o = u]

⌦ encodes the signal received by the MM upon the action taken by the trader. We note that information is conveyed only by the direction of the trade. In the case of an uninformed trader, the observation follows directly from their probabilistic choice determined in the transition function.

• ÷ The reward function R, which constrains inventory to be non-negative, is specified as:

The reward received by the MM is dependent upon the action executed by the trader. In the case of a buy order, the MM receives the ask price, a sell order results in the MM paying the bid price, whereas a hold order results in no loss or gain. Our market-making model allows for an expressive class of reward functions that are piecewise linear in the value, inventory, and bid and ask prices. Hard constraints, such as the non-negative inventory condition, can be encoded using -1. Soft constraints, such as penalising linear deviations from a target inventory level, can be encoded using finite piecewise linear rewards.

The aim of the MM is to maximise its reward over a planning horizon H. In order to do this the MM must trade-off profit taking, which can be seen as exploiting a certain bidask pair, and price discovery, where the MM explores other bid-ask pairs in A. Figure 1 shows our model graphically.

As a critical insight in this work, we remark that by formulating the optimal sequential market-making model as a continuous state POMDP it is possible to separate belief state considerations from the dynamic programming solution. In subsequent sections we show that our model leads to an elegant piecewise linear structure in the ↵-functions derived through an SDP solution. This is in stark contrast with the approach of Das and Magdon-Ismail [2008] which required non-linear operations that complicate the consideration of inventory.

4 Symbolic Dynamic Programming

In this section we make our second contribution by showing how the continuous state POMDP based optimal sequential market-making model can be solved in closed-form via a Symbolic Dynamic Programming (SDP) [Boutilier et al., 2001] based version of PBVI [Pineau et al., 2003].

4.1 Symbolic Case Calculus

SDP assumes that all functions can be represented in case statement form [Boutilier et al., 2001] as follows:

Here, the φi are logical formulae defined over the state ~x that can consist of arbitrary logical combinations of boolean variables and linear inequalities (≥↪>↪<↪) over continuous variables. We assume that the set of conditions ¶φ1↪ ▷ ▷ ▷ ↪ φk♦ disjointly and exhaustively partition ~x such that f is welldefined for all ~x. In this paper we restrict the fi to be either constant or linear functions of the state variable ~x. Henceforth, we refer to functions with linear φi and piecewise constant fi as linear piecewise constant (LPWC) and functions with linear φi and piecewise linear fi as linear piecewise linear (LPWL) functions.

Operations on case statements may be either unary or binary. All of the operations presented here are closed-form for LPWC and LPWL functions. We refer the reader to [Sanner et al., 2011; Zamani and Sanner, 2012] for more thorough expositions of SDP for piecewise continuous functions.

Unary operations on a single case statement f, such as scalar multiplication c · f where c 2 R, are applied to each fi (1  i  k). Binary operations such as addition, subtraction and multiplication are executed in two stages. Firstly, the cross-product of the logical partitions of each case statement is taken, producing paired partitions. Finally, the binary operation is applied to the resulting paired partitions. The "cross-sum" ⊕ operation can be performed on two cases in the following manner:

"cross-subtraction" and "cross-multiplication" ⌦ are defined in a similar manner but with the addition operator replaced by the subtraction and multiplication operators, respectively. Some partitions resulting from case operators may be inconsistent and are thus removed.

In principle, case statements can be used to represent all POMDP components, i.e., R(~x↪ a), T (~x↪ a↪ ~x0 ), ⌦(o↪ a↪ ~x0 ), ↵(~x) and b(~x). In practice, case statements are implemented using a more compact representation known as Extended Algebraic Decision Diagrams (XADDs) [Sanner et al., 2011], which also support efficient versions of all of the aforementioned operations.

4.2 Closed-form Symbolic PBVI for Continuous State POMDPs

In this section we extend the Symbolic PBVI algorithm of Zamani et al. [2012] by relaxing its LPWC assumption to the more general LPWL case. We also show that the set of ↵-functions in the solution are LPWL functions that permit efficient computation. Symbolic PBVI for continuous state (and discrete A) POMDPs can be written solely in terms of the following case operations:

To calculate the optimal h-stage-to-go value function we modify the Bellman backup in Equation (1) to the following form where we marginalize out intermediate variables for the trader type t and outcome u:

In Equation (2) the backup operation is calculated as an expectation over trader types t in a given trader model and observations u 2 ¶buy↪ sell ↪ hold♦ from uninformed traders. We note that this algorithm can be easily extended to very long horizons through model predictive control methods [Qin and Badgwell, 2003] which optimise a single-step look-ahead followed by the execution of a static policy.

A critical insight in this work is that all operations used in the algorithm are closed-form for LPWC representations of ⌦(·) and LPWL representations of T (·) and R(·) [Sanner et al., 2011; Zamani and Sanner, 2012]. A LPWC ⌦(·) ensures that the ↵-functions are LPWL and closed-form after the Bellman backup operation; the integration operation in Equation (2) results in a LPWL function. In contrast, a LPWL ⌦(·) would not result in a closed-form LPWL ↵-function. Therefore, by induction, the Symbolic PBVI value function V h remains closed-form for arbitrary horizons. This result holds for the subclass of continuous state POMDPs with the aforementioned representations of ⌦(·), T (·) and R(·), of which the optimal sequential market-making model in Section 3.2 is an instance.

Symbolic PBVI gives a lower bound on the optimal exact VI [Monahan, 1982] value function and, if all belief states are enumerated to H, the solution is optimal. In the context of optimal sequential market-making, the lower bound policy guarantees that the MMmakes at least as much profit as indicated by the PBVI value function evaluated at a belief state.

5 Results

In this section we demonstrate that our novel optimal sequential market-making model: (1) is sequentially optimal; (2) utilises inventory based reasoning; (3) works with flexible trader models; and (4) is computationally tractable.

As far as we are aware, our model is the first to demonstrate these properties exactly and in closed-form. We note that the work of Das and Magdon-Ismail [2008] is restricted to Gaussian initial beliefs, the traditional GM trader model and does not reason about inventory.

5.1 Experimental Settings

For each of the analyses an initial set of beliefs over S = hv↪ ii is used to generate the set of all reachable beliefs B to H. Trader proportions under the Glosten-Milgrom and Discrete models were set to P(t) = 0▷5 and P(t) = 1◁3, respectively. The noise under the Discrete model for over-valuing and under-valuing traders was set to 10▷0 and -10▷0, respectively. While we can effectively solve for H = 30 or more, we intentionally restrict the horizon to H = 3 in the initial set of evaluations for purposes of interpretation and explanation.

5.2 Sequential Optimality

In Figure 2 we present the sequentially optimal policy of our MM operating within the Glosten-Milgrom trader model with an initial belief of h¶U[0▷0↪ 50▷0]↪ U[50▷0↪ 100▷0]♦ ↪ 1▷0i and A = {(bid↪ ask) ♣(bid < ask)↪ bid↪ ask 2 ¶0▷0↪ 25▷0↪ 49▷0↪ 51▷0↪ 75▷0↪ 99▷0♦ .

We can see that the MM changes the optimal H = 3 bid-ask pair of [0▷0↪ 75▷0] in response to trader actions: the ask price is raised in response to a buy, lowered following a hold and unchanged in the event of a sell order. The actions chosen at H = 2 reflect the optimal choice given the MM's updated belief. At H = 1 the MM chooses actions that ensure that a trader will buy, contingent upon having positive inventory. Furthermore, an optimal bid price of 0▷0 is used by the MM for all H, which is due to there being a non-zero probability that an uninformed trader will sell to the MM at this bid price, a fact which the MM exploits. The sequence of actions show how the MM chooses to (asymmetrically) modulate its bid and ask prices to explore market value while protecting itself against inventory constraints.

5.3 Inventory Sensitivity

In Figure 3 we present the optimal H = 3 actions of our MM operating within the Glosten-Milgrom trading model with different initial beliefs and A = {(bid↪ ask)♣(bid < ask)↪ bid↪ ask 2 ¶20▷0↪ 40▷0↪ 60▷0↪ 80▷0↪ 100♦ . Upon comparing Figure 3a and Figure 3b we notice that, with the exception of the i = 0▷0 case, a narrow initial value belief has a narrower optimal bid-ask spread. It is also evident that the MM uses higher ask prices when the trader population comprises of a higher proportion of uninformed traders. In summary, from Figure 3 we can clearly see that the MM sets its bid and ask prices based on its initial beliefs, characteristics of the trader population and inventory levels.

5.4 Trader Models

In the previous two experiments we showed how the optimal sequential market making-model presented in this paper can be used to calculate sequentially optimal and inventory sensitive policies, the two major contributions to algorithmic market making. In this experiment we demonstrate the flexibility of the model by examining the affect of different trader models on the MM's optimal bid and ask prices. In Figure 4 we present the optimal ↵-functions of our MM operating within the Glosten-Milgrom and Discrete trading model with an initial belief of h¶U[0▷0↪ 50▷0]↪ U[50▷0↪ 100▷0]♦ ↪ 1▷0i and A = {(bid↪ ask)♣(bid < ask)↪ bid 2 ¶0▷0↪ 25▷0↪ 50▷0↪ 75▷0♦ ↪ ask 2 ¶50▷0↪ 75▷0↪ 100▷0♦ .

In Figure 4a we can observe three distinct optimal actions in the ↵-function plots. If we set the width to 0▷0 and vary the mean, we notice that [0▷0↪ 100▷0] exploits the actions of uninformed traders who are equally likely to sell or buy. In the regions where [0▷0↪ 50▷0] and [0▷0↪ 75▷0] are optimal, we note that as the mean increases above the ask price, the MM is more likely to receive buy orders from an informed trader. In Figure 4b we can see two interesting trends with respect

(b) Initial value belief of v ⇠ U[49▷0↪ 51▷0].

Figure 4: Optimal ↵-functions for i = 1▷0 under different trader models. The upper surface of the plot indicates the optimal ↵-function for the market-maker's value belief defined by v ⇠ U[m - w↪ m + w], for a given mean m and width w.

to the optimal actions. Firstly, when the MM is certain about the value, they select actions with increasing ask prices. This phenomenon also occurs when uncertainty about the mean value increases. For example, when the MM becomes increasingly uncertain about a mean value of 70▷0, they use actions with a wider bid-ask spread. From Figure 4 it is evident that models of trader noise have a dramatic affect on the MM's optimal actions. Therefore, it is critical for an algorithmic market-making model to be flexible with regards to its reasoning about traders.

5.5 Time and Space Complexity

Figure 5 shows the relationship between horizon H, computation time and space using a dynamic programming model predictive control approach. It is clear that computation for moderate H remains tractable. The space requirement grows at a rate greater than time due to an inflation in the number of observation partitions per ↵-function. This in turn increases the computation time per backup operation.

6 Conclusions and FutureWork

In this paper, we have introduced the first optimal solution to sequential market-making with inventory based reasoning. We showed that by formulating the market-making problem as a new subclass of continuous state POMDPs, we substantially generalize the previous state of the art solution [Das and Magdon-Ismail, 2008] by allowing for more flexibility in the definition of prior beliefs (arbitrary in our formulation) and trader noise models, while also incorporating inventory constraints and operating with a bounded loss. We also provide a novel SDP solution, which allows us to solve this new subclass of POMDPs, and not just a particular market-making problem, in closed form.

There are a number of avenues for further research. Firstly, it is important to explore more expressive representations of the underlying market microstructure model such as incorporating different order sizes, their affect on market price and stealth trading by informed traders [Easley and O'Hara, 1987]. Another possible extension is to learn trader models from the order stream by using continuous extensions of Bayesian reinforcement learning methods for POMDPs [Poupart et al., 2006]. In an orthogonal direction, we can explore POMDP Monte Carlo Tree Search (MCTS) [Silver and Veness, 2010] alternatives to PBVI. Although MCTS cannot guarantee lower bound policies like PBVI does, it may scale to larger and more complex POMDPs. These extensions may then be used collectively to model and solve optimal sequential market-making in more complex financial domains. In summary, the modelling and algorithmic contributions in this work opens up an entirely new way to investigate market microstructure, trader noise and inventory models in algorithmic sequential marketmaking.

Acknowledgments

Sanmay Das acknowledges support from US NSF award 1414452. We thank the anonymous reviewers for their comments and suggestions.