David Batista Soares
email: david.batista-soares@unicaen.fr

Alain Bretto

Joël Priolon

Efficiency and volatility of spot and futures agricultural markets: Impact of trade frequencies

Keywords: commodities, spot and futures prices, market efficiency, volatility, stock and fragmentation

In efficient markets, asset prices are equal to their fundamentals. This classical view is considered valid for agricultural commodities' spot and futures markets. However, fragmentation of orders impacts price dynamics, leading to modification in spot and futures' trade frequency, relative trade frequency, and quantities exchanged. To highlight public policies on the impacts of fragmentation of orders, it is necessary to improve the understanding of its theoretical consequences.

Based on a sequential trading framework, our main result showed that unbiased prices and a minimal volatility of fundamental basis are achieved not with optimal trade frequencies but with an optimal relative trade frequency.

Introduction

The physical market (also called spot market) and the financial market (referred to as the futures market where futures contracts are exchanged), are linked for a single standardized agricultural raw material (also called a commodity; cf. [START_REF] Anthropelos | An Equilibrium Model for Spot and Forward Prices of Commodities[END_REF], [17]). There exists retro-action between the prices in these two markets. The basis, defined as the spread between these two prices, is a source of risk, and its volatility is a major stake for farmers and processors: it represents a major component of their production and selling decisions (cf. [START_REF] Moschini | Uncertainty, risk aversion, and risk management for agricultural producers[END_REF]). However, price in the futures market evolves faster than that in the spot market (cf. [START_REF] Hara | High frequency market microstructure[END_REF], [18]). Fragmentation of orders, defined as the division of one specific order into several suborders, occurs in both markets. It entails a decrease in quantities exchanged per transaction and an increase in the number of transactions in a market (cf. [START_REF] Hara | Is market fragmentation harming market quality[END_REF], [START_REF] Hara | High frequency market microstructure[END_REF], [19]). Consequently, to buy the same quantity, agents pass more orders and trade frequency increases. Although such fragmentation of orders is used in both spot and futures markets, transaction costs in these two markets are not the same (cf. [18]). Fragmentation of orders is neither equal or proportional in these two markets: it impacts both relative trade frequency (RTF) and quantities exchanged per transaction in these markets. Several empirical studies analyzed the impact of order fragmentation on market liquidity and price volatility (cf. [START_REF] Bennett | Market structure, fragmentation, and market quality[END_REF], [START_REF] Boehmer | Trading your neighbor's ETFs: Competition or fragmentation[END_REF], [START_REF] Kwan | Trading rules, competition for order flow and market fragmentation[END_REF]), but only for equity markets. However, equity markets and agricultural commodity markets differ in many ways (cf. [START_REF] Back | Commodity price dynamics and derivative valuation: A review[END_REF] for a review). The crucial difference between the current study and this work is that we show how fragmentation of orders in the spot market modifies the fundamental futures' commodity price and fundamental volatility, in particular regarding its impact on the released information and its price impact. The link between financial information and market prices has been popularized by Eugene Fama (cf. [START_REF] Fama | Efficient capital markets: a review of theory and empirical work[END_REF], [START_REF] Fama | Efficient capital markets: II[END_REF]): "I take the market efficiency hypothesis to be the simple statement that security prices fully reflect all available information." -(cf. [START_REF] Fama | Efficient capital markets: II[END_REF], p1575)

In fact, the market efficiency hypothesis is a double one : first the market prices are supposed to be fundamentally determined by information. Second, the process that turns information into prices is supposed to be as efficient as it should be. The market efficiency research program belongs mainly to empirical economics. The main conclusion of Fama is that the program that has been followed by so many financial economists has never lead to reject the hypothesis. In this work, we use the central part of Fama's concept that is market prices result from the processing of financial information. We can sum it up in a general manner: p t = g(I t ) where p t is the price at period t, I t is the set of available information and g is an economic function that turns information into prices (see below subsection 3.5). The main difference with Fama's tradition is that we use the concept of market efficiency for a research that is, in a first stage, a theoretical framework; that framework is dedicated to the study of the formation of two series of market prices that are perfectly connected at the level of the underlying fundamental values but which are not in fact perfectly correlated. Spot and futures prices normally evolve in a like manner but they are not thoroughly linked at least because their dynamics are not perfectly synchronized.

This study aims to examine the extent to which the difference in trade frequencies between the two markets and the evolution of that difference influence market efficiency as well as to examine the fundamental volatility of the basis, the spread between the two prices. Finally, we consider whether there is an optimal level of trade frequencies that satisfies these two objectives. Our main result has a major implication. We show that the use of limit order book pricing with fragmentation of orders in the futures market coupled with fragmentation of orders in the spot market is not optimal, except if order fragmentation in the futures market leads to infinite trade frequency in that market. Otherwise, we argue that synchronization of trade frequency allows unbiased prices and minimal fundamental basis volatility. We extrapolate from this result that there is a dilemma between market liquidity and the two objectives.

The article is organized as follows. Section 2 presents all parameters and variables whereas section 3 presents the definitions and hypothesis of the model. Section 4 derives the influence of trade's frequencies and section 5 discusses in detail the impacts of fragmentation on whether only the spot market, only the futures market, or proportional on both markets. In section 6, we study the existence of optimal trade's frequencies. Section 7 concludes and discusses the limitations of the model.

Parameters and variables

The parameters

The following set of parameters is used for the futures and spot markets:

Futures market t r ω f e a Q op T r Spot market t r ω s e t r
Unit of real time considered, such as a second or minute. Advantages of possessing a unit of the storable commodity in monetary value, per unit of real time. Q op Optimal stock level of the commodity for agents. T r Maturity of the futures contract, expressed in a unit of real time.

The variables

The following set of variables is used for the futures and spot markets:

Futures market t T I ]t 1 ,t 2 ] Q t CY t Spot market t I ]t 1 ,t 2 ] q Q t Futures market f t+1 f t F V ft Spot market s t+1 s t F V st t
Time step of the model, which represents a transaction in the futures market: t = t r × ω f and t ∈ N.

T

Maturity expressed in the time scale t: T = T r × ω f and T ∈ N.

I ]t 1 ,t 2 ]
Spot market information delivered in monetary value between t 1 and t Observed spot price and futures price, respectively, at time t. F V st , F V ft Fundamental value of the spot price and futures price, respectively, at time t.

3 Definitions and hypotheses

Time scale and frequencies

We define F s and F f as the sets of all possible frequencies on the spot and futures markets. We have 0 / ∈ (F s ∪ F f ), which means that the two markets exist. Therefore, (ω s , ω f ) ∈ F s ×F f . Furthermore, we assume that ω s ≤ ω f . Futures are more frequently traded than the commodity itself since transaction costs are inferior (cf. [18]). This explains why we choose the transaction on the futures as the time step (the smallest one). We assume that transactions on the futures markets are equally spaced out, according to the futures market trade frequency (FTF),ω f . The real time between two transactions on the futures market is constant. The effective FTF during the period is known, and the effective spot market trade frequency (STF), is unknown. The historical STF, ω s , only gives the probability of having a transaction in the spot market per unit of real time.

At each transaction in the futures market, there is an independent probability ωs ω f of having a transaction in the spot market. This probability is equal to the historical RTF.

Let define a relation wherein t represents the latest period when there was a synchronized transaction in the spot and futures markets until t so that the following is true: t t if t ≤ t, and there is no element y = t nor y = t such that t ≤ y ≤ t. Thus, (t -1) is the latest period when there was a synchronized transaction in the spot market and futures market until t -1, and (t -1) t -1. However, we do not have (t -1) t -1. Indeed, t and (t -1) can both be equal to 0 such that 0 ≤ -1, which is impossible.

Spot market information

We assume that the monetary impact of incoming spot market information delivered at time t, denoted I ]t-1,t] , follows any probabilistic law L whose mean is E I ]t-1,t] = e ω f (t -(t -1)) = e ω f . This mean is a strictly decreasing function of ω f . As spot market information arrives between each transaction in the futures market, we can naturally assume that if transactions are more frequent in the futures market, spot market information between two transactions in the futures market has, on average, a lower price impact.

So, I ]t ,t] represents the spot market information delivered in monetary value since the last transaction on the spot market (t ).

Quantities exchanged and influence of stock dynamics

We now define q, which indicates the quantities traded per transaction in the spot market as a function such that q :

F s → R +, * ω s → q(ω s ) = ω - s , ∈ Q + (1)
From the above function, quantities traded per transaction in the spot market are decreasing when the spot market trade frequency increases. Note that parameter corresponds to the absolute value of the elasticity of quantities traded per transactions in the spot market to the STF.

The available stock of the commodity at time t is defined using a discrete random variable (D.R.V).

Q 0 > 0 and Q t := Q t-1 if t = t Q t-1 -q (ω s ) if t = t = Q t-1 -q (ω s ) 1 {t} t ∀ t ∈ [1, T ] ∈ N (2)
We assume that Q 0 is such that for any ω s in F s and any t in [0; T -1], Q t -q (ω s ) ≥ q (ω s ). We naturally assume that the available commodity is only purchased in the spot market during the period considered (at maturity, commodity is purchased and consumed according to the commitments taken in the futures market). We assume that production or harvest of the commodity is less frequent than the consumption. Therefore, we do not insert it since it would only have a symmetric effect to the stock consumption on the expectations and fundamental value. However, we can do it easily. Consequently, the available stock evolves when and only when there is a transaction in the spot market. It is important to underline that this assumption requires us to not consider that commodity is purchased only to be sold later. For the sake of simplicity, there is no speculation on the spot market. Once again, we could integrate a speculation Bernoulli D.R.V. We assume that the storage cost per unit of real time is the same during the period considered, and, consequently, they are linear with the time and will be perfectly expected. For the sake of simplicity, we do not model them, but it can be done easily.

Despite positive stocks, the futures' price can be inferior to the spot price because of the necessity for corporates to maintain their stocks to face uncertainty (cf. [START_REF] Kaldor | Speculation and Economic Stability[END_REF]). This advantage (or disadvantage) to detain a unit in stock at transaction t in monetary value until maturity, also called convenience yield and denoted by CY t , is given by the following equation:

CY t := a ω f (T -t) (Q op -Q t ) (3)
We assume that Q op is exogenous to the model. This is the same for all agents. When the stock is above this level, there is no advantage to detain more units, and the convenience yield is negative. When the stock is under this level, there is an advantage to detain the units of stock. This advantage also depends on the number of transactions on the futures market remaining until maturity weighted by the advantage per unit of real time between a transaction on the futures market ( a ω f (T -t) = a (T r -t r )).

Agents' expectations

We assume that all information is freely available and that, at time t, all agents know all prices and market characteristics. Therefore, Φ t = {s t , f t , Q t , I ]t ,t] , CY t } is the common knowledge at time t. Furthermore, we assume that agents form rational expectations in the sense that, on average, their expectations reflect fundamental prices. They compute the average expected price evolution. The expectation of the spot price is computed by

E ( s t+1 |Φ t ) = s t + I ]t ,t] + e ω f (4)
Recall that t represents the latest period when there was a synchronized transaction in the spot market and futures market until t. Agents add to the current spot price (at period t), all spot market information that should have been included in the spot price I ]t ,t] , and the expected incoming spot market information for its average value E I ]t,t+1] = e ω f . Expectations of the stock dynamics are given by

E Q t+1 |Φ t = Q t -q (ω s ) ω s ω f (5)
The expected stock evolution is given by quantities exchanged at each transaction on the spot market (that we suppose consumed) weighted by the probability of having a transaction on the spot market at the next transaction on the futures market. The convenience yield is expected such that

E CY t+1 |Φ t = a ω f (T -(t + 1)) Q op -E Q t+1 |Φ t (6)
To prevent an arbitrage operation (defined as an operation that guarantees a positive profit without risk of loss; cf. [START_REF] Poncet | Mathématiques financieres: Evaluation des actifs et analyse du risque[END_REF]), the basis must include the current level of stock since the lower stocks are, the more agents have an interest in detaining it depending on the level of their optimal stock. Between each transaction in the futures market, the advantage in detaining stocks decreases by a ω f for the same level of stock than at t. However, there is a probability of ωs ω f of having a stock movement, and the average stock evolution is not null. Thus, expected stock movement affects the expected advantage in detaining stocks until maturity.

Finally, expectations of the futures price for the next period are

E f t+1 |Φ t := E s t+1 -CY t+1 |Φ t (7)
Equation 7 translates the fact that agents know what is the no arbitrage condition.

Price dynamics and fundamental values

Prices evolve according to the agents' expectations if and only if a transaction occurs. Agents expect the next prices but do not necessarily pass an order at these prices. Thus,

s t+1 := s t if (t + 1) = t + 1 E ( s t+1 |Φ t ) if (t + 1) = t + 1 = s t + 1 {t+1} (t + 1) I ]t ,t] + e ω f f t+1 := E f t+1 |Φ t (8)
The fundamental value of a price corresponds to the instantaneous integration of all available information on the price (cf. [START_REF] Fama | The theory of finance[END_REF]). Assuming that F V s 0 = s 0 and F V f 0 = f 0 , the fundamental values are naturally defined by

F V s t+1 := s 0 + I ]0,t+1] F V f t+1 := F V s t+1 -CY t+1 (9)
The futures' fundamental value is computed using a classical view, by its no arbitrage value (cf. [START_REF] Black | The pricing of commodity contracts[END_REF], [START_REF] Black | The Pricing of Options and Corporate Liabilities[END_REF], [START_REF] Robert | Theory of Rational Option Pricing[END_REF]).

Market efficiency and fundamental volatility

We study price bias and we refer to it as market efficiency, denoted by B. We are aware that an unbiased price does not ensure that at each time t, the price fully reflects the information on the market, but unbiased price is a sine qua non condition. We give the following function for the market efficiency:

B : R + → R + p t → B(p t ) = |E (p t -F V pt )| , p t ∈ {s t , f t } where | . | denote the absolute value (10)
Then, we consider the fundamental volatility criterion, denoted by V . It is computed using a standard variance such that at time t

V : R + → R + F V pt → V (F V pt ) = V ar (F V pt ) , p t ∈ {s t , f t } (11)

Impact of trade frequencies

In this section, we study the impact of trade frequencies on market efficiency and fundamental basis volatility. Market efficiency regarding the fragmentation of orders has already been studied empirically in previous literature (cf. [START_REF] Bennett | Market structure, fragmentation, and market quality[END_REF], [START_REF] Kwan | Trading rules, competition for order flow and market fragmentation[END_REF], [START_REF] Hara | Is market fragmentation harming market quality[END_REF], [START_REF] Hara | High frequency market microstructure[END_REF]). We provide a theoretical explanation of its impacts. Finally, we show within this framework that fragmentation of orders also impacts fundamental basis volatility.

Impact of trade frequencies on the market efficiency

Theorem 1. Let SM and F M respectively be a spot market and a futures market under our hypothesis. For e = 0 and ω s = ω f , SM is not an efficient market, and the spot price bias is equal to

B (s t ) = |-e| ω f t k=1 1 - ω s ω f k > 0 ( 12
)
Proof. See appendix A If e = 0 and ω s = ω f , trade frequencies have an impact on spot market efficiency. They generate a bias on the spot price dynamic that results in an adjustment delay in a number of transactions. However, spot market information is released between transactions. The adjustment delay in monetary value is strictly positive.

Remark 1. For e = 0, B (s t ) = 0 ∀ t ∈ [1, T ].
When incoming information has no impact on average on the spot price, an adjustment delay in the number of transactions does not generate a bias in the market. As the released spot market information has on average no impact on monetary value, the adjustment delay in monetary value corresponding to the bias is null.

For

ω s = ω f , t = t ∀ t ∈ [1, T ], we have E (t ) = t; hence, B (s t ) = 0 ∀ t ∈ [1, T ].
When transactions are synchronized in both the spot and futures markets, there is no adjustment delay in number of transactions on the futures market. Thus, the rational expectations assumption ensures an unbiased spot price.

In reality, the FTF is higher than the STF. Furthermore, commodity prices have a seasonal tendency such that e = 0 (cf. [START_REF] Back | Commodity price dynamics and derivative valuation: A review[END_REF]). Then, the adjustment delay of the spot market can be important.

Corollary 1. Let F M be a futures market under our hypothesis. F M is an unbiased market, and thus it can be an efficient market.

By construction, agents form rational expectations, and information arrives between two transactions in the futures market. They perfectly expect, on average, the fundamental prices. As the futures price always evolves according to the expectations, this leads to an unbiased futures price.

Remark 2. The futures market efficiency is independent from trade frequencies. However, the STF has an indirect impact on stock dynamics and its expectations (cf. equations 2 and 5). One can infer that this indirect impact is, on average, equal on both futures' price and fundamental value dynamics.

Impact of trade frequencies on the fundamental basis volatility

Theorem 2. Let SM and F M respectively be a spot market and a futures market under our hypothesis. For a = 0, t < T , and ω s = ω f , we have the following properties:

(i) The volatility of the available stock at time t, denoted by V ar (Q t ), is impacted by both STF and FTF.

V ar

(Q t ) = tq (ω s ) 2 1 - ω s ω f ω s ω f (13)
(ii) The fundamental basis volatility at time t, denoted by V ar (F V ft -F V st ), is impacted by both STF and FTF.

V ar

(F V ft -F V st ) = a ω f 2 ((T r ω f ) -t) 2 q (ω s ) 2 t 1 - ω s ω f ω s ω f (14)
Proof. See appendix B If a = 0, ω s = ω f , and t < T , trade frequencies have an impact on the fundamental basis volatility. They generate uncertainty on the dynamic of the commodity stock. Furthermore, the STF has an impact on quantities exchanged in the spotmarket according to the absolute value of the elasticity . A representation of the sensitivity of the fundamental basis volatility to trade frequencies according to the elasticity of quantities traded at each transaction on the spot market to the STF is given in figures 5, 6 and 7.

Remark 3. For a = 0, V ar (F V ft -F V st ) = 0 ∀ t ∈ [1, T ].
If there is no advantage in detaining stock until maturity, as we do not integrate storage costs, both fundamental basis volatility and fundamental basis are null.

For

ω s = ω f , V ar (F V ft -F V st ) = 0 ∀ t ∈ [1, T ].
There are only synchronized transactions in both markets. Consequently, there is no uncertainty; There is a transaction of q (ω s ) unit(s) of the commodity at each transaction in the futures market.

For t = T , V ar (F V ft -F V st ) = 0. As a consequence of the no arbitrage condition, if there is no more time until maturity, the basis must be null and so its volatility.

In reality, the FTF is more important than the STF. Transaction costs on the spot market are significant, and they prevent the STF from increasing. Then, quantities exchanged at each transaction on the spot market are significant. Furthermore, the advantage of detaining stock is a major component of the basis, such that a = 0. Then, basis fundamental volatility is higher with these market characteristics.

Impact of a fragmentation of orders

From theorems 1 and 2, we proved that under the assumptions made, trade frequencies influence the fundamental basis volatility and the spot price bias. We study in this section how this impact evolves when these frequencies increase. We present some simulations and the associated mechanisms. We study the impact of the fragmentation of orders on the spot market and futures market separately as well as the impact of a proportional fragmentation of orders on the two markets. First, the spot price bias (see below subsection 5.1) and, second, the fundamental basis volatility (see below subsection 5.2). (ii) If the FTF increases

• For ωs ω f ∈ 0; 1 -1 t+1 1 t
⊂ 0; 1 2 , the spot price bias strictly decreases;

• For ωs ω f ∈ 1 -1 t+1 1 t ; 1 ⊃ 1 2 ;
1 , the spot price bias strictly increases.

(iii) If both STF and FTF increase such that the RTF, equal to ωs ω f , is unchanged, the spot price bias strictly decreases.

Proof. See appendix C

An increase in the STF (i.e., fragmentation of orders on the spot market) decreases the average adjustment delay in number of transactions on the futures market (cf. Figure 1; the bias is strictly decreasing when ω s increases). As the average spot market information impact between two transactions in the futures market is unchanged, the spot price bias decreases in monetary value. This explains the first assertion of theorem 3.

An increase in the FTF (i.e., fragmentation of orders on the futures market) increases the average adjustment delay in number of transactions in the futures market. However, the average spot market information impact between two transactions in the futures market decreases. The first effect overcomes the second one when the RTF is initially sufficiently low. The impact of the FTF on the RTF and thus on the probability of having a transaction in the spot market at each transaction on the futures market is not linear. Figure 1 graphically represents the upper level of the plan, wherein for a given (little) STF, there is an FTF above that the bias decreases. This explains the second assertion of theorem 3.

Remark 4. The above condition depends on the number of transactions in the futures market considered, denoted by t. To have fragmentation in the futures market that reduces the spot price bias, the more we consider a high t, the lower the RTF must be (i.e., ω f >> ω s ). With a high initial FTF, an increase in the FTF has a small effect on the RTF. Figures 2, 3 and 4 illustrate the effect of t considered. Looking at the upper part of the plan, the higher t is when ω f >> ω s , the less the spot price bias decreases. A proportional increase in both STF and FTF such that ωs ω f is unchanged does not modify the probability of synchronized transaction's occurrence. However, between two transactions in the futures market, the average monetary impact of the information on the futures market strictly decreases. Thus, the spot price bias strictly decreases. This result explains the third assertion of theorem 3. Figure 1 illustrates it. When following a parallel of the first bisector, the RTF is unchanged and the spot price bias decreases.

Impact of a fragmentation of orders on the fundamental basis volatility

Theorem 4. For e = 0, a = 0, t < T , and ω s = ω f , we have the following properties:

(i) If the STF increases,

• For ωs ω f ∈ 0, 1 2 , the fundamental basis volatility strictly decreases if the following condition is verified:

-< - ω f -2ω s 2 (ω f -ω s )
, where -is the elasticity of q (ω s ) to ω s (see equation 1)

• For ωs ω f ∈ 1 2 , 1 , the fundamental basis volatility strictly decreases.

(ii) If the FTF increases,

• For ωs ω f ∈ 0, 1 2 , the fundamental basis volatility strictly decreases if the following condition is verified:

-

ω f -2ω s 2 (ω f -ω s ) < - t T r ω f -t (16)
• For ωs ω f ∈ 1 2 , 1 , the fundamental basis volatility increases.

(iii) If both STF and FTF increase such that the RTF, equal to ωs ω f , is unchanged, the fundamental basis volatility strictly decreases if the following condition is verified:

-< - t T r ω f -t (17)
Proof. See appendix D Remark 5. Let f be a function such that

f : F s \ {ω f } × F f → R (ω s , ω f ) → f (ω s , ω f ) = - ω f -2ωs 2(ω f -ωs)
It is easy to prove that f is a C1 class function.

For ωs ω f ∈ 0, 1 2 , ∂f (ωs,ωf ) ∂ωs = - -2(2(ω f -ωs))-(ω f -2ωs)(-2) (2(ωf -ωs)) 2 = ω f 2(ω f -ωs)
2 > 0. The higher ω s is, the higher the elasticity of spot quantities traded to ω s can be to verify equation 27.

For ωs ω f ∈ 0, 1 2 ,
∂f (ωs,ωf )

∂ω f = - 12(ω f -ωs)-(ω f -2ωs)2 4(ω f -ωs) 2 = - ωs 2(ω f -ωs)
2 < 0. The higher ω f is, the lower has to be to verify equation 27.

Remark 6. Let g be a function such that

g : F f × [1; (T r × ω f ) -1] → R (ω f , t) → g (ω f , t) = - t (Trωf -t) (18)
It is easy to prove that g is a C1 class function.

For ωs ω f ∈ 0, 1 2 , ∂g(ω f ,t) ∂ω f = -t(-Tr) (Trωf -t) 2 > 0.
Referring to remark 5, the left term of the condition given by equation 16 is decreasing when ω f increases. The higher ω f is, the less restrictive is the condition given by equation 16.

For ωs ω f ∈ 0, 1 2 , ∂g(ω f ,t) ∂t = - 1(Trω f -t)-t(-1) (Trωf -t) 2 = - Trω f (Trωf -t) 2 < 0.
The higher is the number of transactions on the futures market t, the more restrictive is the condition of equation 16.

An increase in the STF (i.e., fragmentation of orders on the spot market) reduces the volatility of the fundamental basis by two mechanisms if the RTF is superior to 1 2 (cf. Figure 5; the fundamental basis volatility curve decreases with an increasing STF when ωs ω f > 1 2 ). First, the volatility of the occurrence of transactions in the spot market decreases. Second, quantities traded per transaction in the spot market are inferior, smoothing the stock dynamic. If the RTF is inferior to 1 2 , the first mechanism does not hold but the second still holds. The volatility of the occurrence of transactions on the spot market increases. The "smoothing per trade exchanged quantities" effect must overcome the "increasing occurrence of transaction's volatility" effect. To smooth the stock dynamic enough, the elasticity must be under a threshold (sufficiently high in absolute value) such that quantities exchanged per trade sufficiently decrease. This condition is given by equation 15 and illustrated in Figures 6 and7. For = 0, 8 (cf. Figure 7), the elasticity is high in absolute value, and the volatility is decreasing with an increasing ω s . On the contrary, for = 0, 2 (cf. figure 5), the volatility is increasing when the STF is originally low. These results explain the first assertion of theorem 4. A study of the condition is presented in Remark 5, and highlights the following remark.

Remark 7. This condition depends on the initial levels of trade frequencies. The higher the STF initially is, the lower are the quantities exchanged per transaction in the spot market. Thus, the higher the elasticity can be (the lower in absolute value) such that quantities traded will decrease enough, and overcome the increasing volatility in the stock dynamic. Near the first bisector, the fundamental basis volatility decreases with an increasing STF for all values of (cf. Figures 5, 6, and7). Based on the same reasoning, the higher the FTF is, the more restrictive is the threshold. The increasing part of the curve for a given STF is more important when the FTF increases. To overcome this increasing effect, the elasticity must be sufficiently high in absolute value to ensure a sufficient decrease in quantities exchanged per trade on the spot market. The analytic condition is given in equation 16. In Figures 5,6, and 7, the plan twists according to the value of , representing this threshold. We observe that the higher is, the less the plan is twisted starting from low values of FTF.

An increase in the FTF (i.e., fragmentation of orders in the futures market) strictly increases the volatility of the fundamental basis by two mechanisms if the RTF is superior to 1 2 (cf. Figure 5; the fundamental basis volatility plan increases with an increasing ω f when ωs ω f > 1 2 ). The volatility of the occurrence of synchronized transactions increases. Furthermore, a transaction in the spot market long before the maturity has more impact on the convenience yield than if it happens at maturity, as a consequence of the no arbitrage value and the time remaining until maturity. Here, we have horizon t, expressed by a number of transactions in the futures market, to study the fundamental basis volatility. An increase in the FTF reduces the real time at which the first t transactions are made. Each transaction takes place earlier, and there is more real time remaining until maturity. An increase in the FTF gives more weight to the first t possible transactions in the spot market. It consequently increases the fundamental basis volatility. However, when the RTF is inferior to 1 2 , an increasing FTF decreases the volatility of synchronized transaction's occurrence. This effect overcomes the real-time scale effect if the condition given by equation 16 is verified. Figures 8,9 and 10 illustrate the latest condition. These results explain the second assertion of theorem 4.

A proportional increase in the STF and the FTF such that ωs ω f is unchanged does not modify the occurrence of synchronized transaction's volatility. However, for a given real time, there are more transactions in the futures' market. When considering a given number of transactions in the futures market t, it reduces the "real time" considered. Therefore, each potential evolution of the stock has more impact on the convenience yield, since the real time remaining between the first t transactions and maturity is superior. The increase of the STF reduces quantities traded per transaction in the spot market such that it reduces the stock dynamic volatility at an unchanged time horizon. To ensure that this effect overcomes the higher importance of stock evolution until maturity, the elasticity of quantities traded per transaction on the spot market to the STF must be under the threshold given by equation 17 (i.e., sufficiently high in absolute value). This result explain the third assertion of theorem 4. A study of this condition is presented in Remark 6.

Remark 8. Equation 17 underlies the importance of the choice in the number of transactions considered to study the effect of a proportional increase in the STF and the FTF. This threshold firstly depends on t. The nearer to maturity t is, the more restrictive is the condition given by equation 17. The impact of the modification of the real-time scale is higher if the initial real time considered is important. Consequently, the longest the initial horizon is, the higher the quantity effect has to be. Second, this threshold depends on the FTF. The modification of the "time scale effect" relies on the initial level of the FTF. Hence, a study of the condition shows that the higher the FTF is, the less restrictive is the condition given by equation 17. If the t transactions considered occur with a high FTF, only a little real time is considered. Consequently, an increase in the FTF reduces the real time considered but not significantly, and the quantity effect is not strong. Remark 9. The condition given by equation 17 is independent from the RTF. Since the increases in the STF and the FTF are proportional such that the RTF is unchanged, there is no effect on the volatility of occurrence of synchronized transactions. Then, the only condition to ensure a reducing fundamental basis volatility relies on the elasticity of quantities traded at each transaction on the spot market to the STF and the initial levels of both STF and FTF.

The latest result has strong implications. In subsection 5.1, we demonstrated that a proportional fragmentation reduces spot market bias. One could think that proportional fragmentation can reduce fundamental basis volatility. However, this intuition is unverified if the decreasing quantities exchanged per transaction in the spot market are insufficient. This strong result shows the extent to which the spot market and its structure influences the futures market and can reduce the benefit of proportional fragmentation in both markets.

The elasticity of quantities traded per transaction in the spot market to the STF is constant. Otherwise, we could face a condition (given by equation 17) depending on the current level of the STF. Based on the same reasoning, one could assume an elasticity of quantities traded per transaction in the spot market depending on the FTF. Spot and futures markets are linked, and we can imagine that when there are more trades in the futures market, producers and buyers of the commodity adjust their orders' frequency and thus quantities traded. A further extension of this work could be to study the evolution of these results according to the form of the q function.

6 Existence of an optimal STF and FTF A policymaker's objectives in commodity markets are to minimize the fundamental basis volatility and increase market efficiency in both spot and futures markets. As the futures price is unbiased (cf. corollary 1), the policymaker focuses on spot market efficiency. We consider here that trade frequencies are the policymaker's tools, and thus the policymaker can implement a fixed pricing and transaction frequency. This section has major issues. At some point, it can question the commodity futures pricing by limit order book if the optimal trade frequencies are inferior to the actual FTF where a limit order book pricing operates. Definition 1. We define a utility function U in the following way:

U : F s × F f U 1 -→ R + × R + U 2 -→ X R - (ω s , ω f ) -→ (B (s t ) , V (F V ft -F V st )) -→ U (B (s t ) , V (F V ft -F V st )) (19) Hence, we have U (ω s , ω f ) = U 2 • U 1 (ω s , ω f )
, verifying the following two properties:

(i) U 2 (0, 0) = 0; (ii) ∂U 2( B(st),V (F V f t -F Vs t )) ∂B(st)
< 0, and

∂U 2( B(st),V (F V f t -F Vs t )) ∂V (F V f t -F Vs t ) < 0.
We assume that a policymaker, to maximize the market efficiency and fundamental basis volatility, uses the utility function U as defined above. Properties (i) and (ii) above correspond respectively to the following natural insights: (i) If the spot price bias and fundamental basis volatility are both null, we assume that U 2 takes its maximal value on R -: 0;

(ii) If either the spot price bias or fundamental basis volatility increases, the policymaker's utility decreases.

The policymaker consequently has the following maximization program:

   max ωs,ω f U (ω s , ω f ) = U |-e| ω f t k=1 1 -ωs ω f k , a ω f 2 (T r ω f -t) 2 q (ω s ) 2 t 1 -ωs ω f ωs ω f s.t. ω f ≥ ω s ( 20
)
Theorem 5. For e = 0, a = 0, t < T , and F s ∩ F f = ∅, a policymaker whose utility function is U has an optimal solution and an optimal solution by limit:

(i) A policymaker does not have to fix the trade frequencies of both spot and futures markets but has to synchronize them. This implies an RTF equal to 1 (the subset of optimal solutions is

O = (ω s , ω f ) ∈ (F s ∩ F f ) 2 : ωs ω f = 1 );
(ii) For any value of ω s except ω s → +∞, a policymaker can allow infinite fragmentation in the futures contract. This implies an RTF converging to 0 (the subset of optimal solutions by limit is

O bl = (ω s ; ω f ) ∈ F s × F f : ωs ω f → 0, ω f → +∞ ).

Proof. See appendix E

This result implies that independently of the absolute value of both STF and FTF, the synchronization of the trade frequencies ensures minimal fundamental basis volatility and minimal spot price bias.

Remark 10. If ω s = ω f , there is no uncertainty on the stock dynamic and no unexpected elements on the basis (cf. equation 5; E ( s t+1 |Φ t ) = s t+1 ∀ t). With synchronized transactions and rational expectations, the basis is always equal to its fundamental value. This result implies that the links between a spot market and a futures market of a commodity responding to our framework prevent the STF and the FTF from being disconnected in order to achieve market efficiency and minimal fundamental basis volatility. Only more fragmentation on the futures market (i.e., an increase in the FTF) can lead to an increasing spot price bias and increasing fundamental basis volatility (cf. section 5), except if the fragmentation is relatively infinite. There are no optimal values for the STF and FTF, but there are co-dependent conditions. Theorem 6. For e = 0, a = 0, and t < T , a policymaker whose utility function is U has optimal solutions by limit relying on the following market characteristic:

(i) For -> -1
2 , there is no conditional optimal solution different from unconditional optimal solutions to the policymaker's utility maximization program given in theorem 5;

(ii) For -< -1 2 , the policymaker's utility is maximized by limit for all values in the following subset:

O > 1 2 bl = (ω s , ω f ) ∈ F s × F f : ωs ω f → 1, ω s → +∞, ω f → +∞ ; (iii) For -= -1 2
, there is no conditional optimal solution different from unconditional optimal solutions of the policymaker's utility maximization program given in theorem 5.

Proof. See appendix F

There is also a subset of optimal values by limit for the policymaker that is conditional to market characteristics (value of ). The analytical proof of this result is presented in theorem 6. If -≥ - 1 2 , there is no conditional optimal solution different from the unconditional optimal solutions of the policymaker's utility maximization program. However, if -< - 1 2 , the optimal solution by limit for the policymaker can be to implement the centralization of orders by brokers and reduce transaction costs as much as possible in the spot market such that ωs ω f → 1 and ω f → +∞ independently of the FTF (the RTF is converging to 1). However, despite the possibility of having high elasticity, implementing a market structure such that ω s → +∞ is impossible since there are structural transaction costs. We can qualify this conditional subset of optimal solutions as a limit case.

Conclusion

This work has major implications. It shows that commodity futures pricing by limit order book is not an efficient policy regarding the two objectives when fragmentation in the futures market is not infinite. Although previous empirical studies argued that fragmentation allows for better market efficiency, their finding does not necessarily contradict our results (depending on the initial RTF). Our results recommend the implementation of a fixing price operating at the same frequency as the trade of the commodity in the associated spot market. Indeed, a relatively infinite fragmentation in futures market, the only other optimal solution independent from the market characteristics, seems compromised. This can also be understood as an arbitrage between liquidity in the futures market and achievement of the two objectives; We showed in section 5 that proportional increase in both frequencies could lead to increasing fundamental basis volatility according to the value of . A way to improve liquidity and market efficiency of the spot market could be a regulation of the spot market structure to facilitate the transactions in this market, in order to allow an increase in the absolute value of . To conclude, the simultaneous determination of spot and futures prices is optimal and independent from the market characteristics. We are aware that this model presents some limits. Some extensions of this work could be made depending on the form of the q function as well as in the implementation of several commodities (or other markets in general). Finally, we could also integrate the possibility of speculation in the spot market, such that trade in the spot market would not necessarily imply commodity consumption.

[17] Jerome L. Stein. The simultaneous determination of spot and futures prices. The American Economic Review, pages 1012-1025, 1961.

[18] Holbrook Working. Futures trading and hedging. In The Economics of Futures Trading, pages 68-82. Springer, 1976.

[ A Proof of theorem 1

Proof. Using equation 8, we have

s (1) = s 0 + 1 {1} (1 ) I ]0 ,0] + e ω f s (2) = s 1 + 1 {2} (2 ) I ]1 ,1] + e ω f s (2) = s 0 + 1 {1} (1 ) I ]0 ,0] + e ω f + 1 {2} (2 ) I ]1 ,1] + e ω f
Hence, we express s (t-1) according to s 0 as follows:

s (t-1) = s 0 + (t-1) k=1
1 {k} k I ](k-1) ,k-1] + e ω f (21)
We express the dynamic of s t according to s 0 using equations 8 and 21:

s t = s 0 + t k=1 1 {k} k I ](k-1) ,k-1] + e ω f
Then, its average value is

E (s t ) = E s 0 + t k=1 1 {k} (k ) I ](k-1) ,k-1] + e ω f = = s 0 + t k=1 E 1 {k} (k ) I ](k-1) ,k-1] + e ω f = s 0 + t k=1 E 1 {k} (k ) E I ](k-1) ,k-1] + e ω f = s 0 + ωs ω f e ω f t k=1 k -1 -E (k -1) + 1 E (s t ) = s 0 + ωs ω f e ω f t k=1 k -E (k -1)
We compute the average spot fundamental value at time t:

E (F V st ) = E s 0 + I ]0,t] = s 0 + e ω f t
We have the following expression of the bias:

B (s t ) = s 0 + ωs ω f e ω f t k=1 k -E (k -1) -s 0 -e ω f t B (s t ) = e ω f ωs ω f t k=1 k - ω f ωs -E (k -1) (22)
Focusing on the t variable, we have P r

(t = k) = ωs ω f 1 -ωs ω f t-k ∀ k ∈ [1; t] and P r (t = 0) = 1 -ωs ω f t
. Hence, we compute

E (t ) = t k=0 kP r (t = k) = t k=1 k ωs ω f 1 -ωs ω f t-k E (t ) = -ωs ω f 1 -ωs ω f t+1 t k=0 -k 1 -ωs ω f -k-1 Let z = 1 -ωs ω f , 0 ≤ z < 1.
For a fixed t, we have

t k=0 -kz -k-1 = t k=0 d (z -1 ) k dz = d t k=0 (z -1 ) k dz = d t k=0 (z -1 ) k dz = d (z -1 ) 0 1-( z -1 ) t+1 1-z -1 dz = (t+1)z -t -tz -(t+1) -1 (z-1) 2
Then, we have

E (t ) = -ωs ω f 1 -ωs ω f t+1 (t+1) 1-ωs ω f -t -t 1-ωs ω f -(t+1) -1 ωs ω f 2 = -(t+1) 1-ωs ω f +t+ 1-ωs ω f t+1 ωs ω f = -t-1+t ωs ω f + ωs ω f +t+ 1-ωs ω f t+1 ωs ω f E (t ) = t + -1+ ωs ω f + 1-ωs ω f t+1 ωs ω f = t -1 -ωs ω f 1-1-ωs ω f t 1-1-ωs ω f
This can be rewritten as follows:

E t = t - t k=1 1 - ω s ω f k (23)
Remark 11. The D.R.V t can be decomposed into two parts. First, t is the maximal value of t (since t t). The second part is stochastic and can be assimilated to a truncated geometric law with t experiences -maximum -starting from t in backwardation and ending to 0. Hence, its mean is equal to its maximal value minus the average delay for having a synchronized transaction looking backward in number of transactions on the futures market.

Replacing the value of equation 23 in 22, we obtain the following expression of the bias:

B (s t ) = e ω f ωs ω f t k=1 k - ω f ωs -k -1 -k-1 j=1 1 -ωs ω f j = e ω f ωs ω f t k=1 1 - ω f ωs + k-1 j=1 1 -ωs ω f j = -e ω f t k=1 1 -ωs ω f -ωs ω f k-1 j=1 1 -ωs ω f j = -e ω f t k=1   1 -ωs ω f -ωs ω f 1 -ωs ω f 1-1-ωs ω f k-1 1-1-ωs ω f   = -e ω f t k=1 1 -ωs ω f -1 -ωs ω f 1 -1 -ωs ω f k-1 B (s t ) = |-e| ω f t k=1 1 -ωs ω f k
For e = 0 and ω s = ω f , B (s t ) > 0. Hence, the spot price is biased, and SM cannot be an efficient market.

B Proof of theorem 2

Proof. First, we compute V ar (Q t ) and show that it depends on parameters ω s and ω f .

V ar

(Q t ) = V ar Q 0 -q (ω s ) t k=1 1 {t} (t ) = q (ω s ) 2 V ar t k=1 1 {t} (t ) = q (ω s ) 2 t k=1 V ar 1 {t} (t ) V ar (Q t ) = q (ω s ) 2 t k=1 1 -ωs ω f ωs ω f = q (ω s ) 2 t 1 -ωs ω f ωs ω f
The expression of V ar (Q t ) depends on ω s and ω f , which proves the first assertion. Then, we compute the fundamental variance of the spread between the futures price and spot price. We show that it also depends on parameters ω s and ω f .

V (F V ft -F V st ) = V ar (CY t ) = V ar a ω f (T -t) (Q op -Q t ) V (F V ft -F V st ) = a ω f 2 ((T r ω f ) -t) 2 V ar (Q op -Q t ) = a ω f 2 ((T r ω f ) -t) 2 V ar (Q t )
Knowing the value of V ar (Q t ) from the first assertion's proof above, we obtain the expression of equation 14.

For a = 0, t < T , and

ω s = ω f , V (F V ft -F V st ) > 0.
The expression of V (F V ft -F V st ) depends on ω s and ω f , which proves the second assertion.

C Proof of theorem 3

Proof. To prove the first assertion, we calculate the derivation of the spot price bias according to ω s , and we show that it is negative. Using equation A we have

∂B(st) ∂ωs = ∂ |-e| ω f t k=1 1-ωs ω f k ∂ωs ∂B(st) ∂ωs = |-e| ω f t k=1 k -1 ω f 1 -ωs ω f k-1 < 0
Hence, first assertion is proved.

To prove the second assertion, we calculate the derivation of the spot price bias according to ω f , and we study its sign. Using equation A we have

∂B(st) ∂ω f = ∂ |-e| ω f t k=1 1-ωs ω f k ∂ω f = | -e | ∂ 1 ω f t k=1 1-ωs ω f k ∂ω f = | -e | -1 ω f 2 t k=1 1 -ωs ω f k + 1 ω f t k=1 k 1 -ωs ω f k-1 ωs ω f 2 = |-e| ω f 2 -t k=1 1 -ωs ω f k + t k=1 k ωs ω f 1 -ωs ω f k-1 = |-e| ω f 2   -1 -ωs ω f 1-1-ωs ω f t 1-1-ωs ω f + ωs ω f    1-(t+1) 1-ωs ω f t 1-1-ωs ω f + 1-ωs ω f -1-ωs ω f t+1 1-1-ωs ω f 2       = |-e| ω f ωs -1 -ωs ω f -1 -ωs ω f t+1 + 1 -(t + 1) 1 -ωs ω f t ωs ω f + 1 -ωs ω f -1 -ωs ω f t+1 ∂B(st) ∂ω f = |-e| ω f 2 1 -(t + 1) 1 -ωs ω f t ( 24
)
Equation 24 is strictly negative if and only if

1 -(t + 1) 1 -ωs ω f t < 0 ⇔ 1 < (t + 1) 1 -ωs ω f t ⇔ ωs ω f < 1 -1 t+1 1 t
Let h be a function such that

h : [1; T r × ω f ] ⊂ N → R t → h (t) = 1 -1 t+1 1 t (25)
It is easy to prove that h is a C1 class function. Then,

dh(t) dt = --1 t 2 1 t+1 1 t -1 -1×1 (t+1) 2 = -1 t 2 (t+1) 2 1 t+1 1-t t < 0. The maximal value of h is h (1) = 1 2 . The minimal value of h is then lim t→Tr×ω f →∞ h (t) = 1 -0 0 = 0.
This proves the second assertion.

To prove the last assertion, we compute the total derivation of spot price bias and study its sign. A proportional increase of the frequencies implies that the RTF is unchanged such that ωs+dωs ω

f +dω f = ωs ω f ⇔ ω f (ω s + dω s ) = ω s (ω f + dω f ) ⇔ dω f = ω f dωs ωs . This gives d (B (s t )) = ∂(B(st)) ∂ωs dω s + ∂(B(st)) ∂ω f dω f = |-e| ω f t k=1 k -1 ω f 1 -ωs ω f k-1 dω s + |-e| ω f 2 -t k=1 1 -ωs ω f k + t k=1 k ωs ω f 1 -ωs ω f k-1 ω f ωs dω s = |-e| ω f 2 dω s -t k=1 k 1 -ωs ω f k-1 - ω f ωs t k=1 1 -ωs ω f k + t k=1 k 1 -ωs ω f k-1 d (B (s t )) = -|-e| ωsω f dω s t k=1 1 -ωs ω f k < 0
This proves the last assertion.

D Proof of theorem 4

Proof. To prove the first assertion, we calculate the derivation of the fundamental basis volatility according to ω s , and we study its sign. Using equation 14 we have

∂V (F V f t -F Vs t ) ∂ωs = ∂ a ω f 2 ((Trωf )-t) 2 q(ωs) 2 t 1-ωs ω f ωs ω f ∂ωs = a ω f 2 ((T r ω f ) -t) 2 t 1 ω f ∂ q(ωs) 2 ωs- q(ωs) 2 ωs 2 ω f ∂ωs = a ω f 2 ((T r ω f ) -t) 2 t 1 ω f q (ω s ) 2 + 2ω s q (ω s ) dq(ωs) dωs -1 ω f 2ω s q (ω s ) 2 + 2ω s 2 q (ω s ) dq(ωs) qωs ∂V (F V f t -F Vs t ) ∂ωs = a ω f 2 ((T r ω f ) -t) 2 t r q (ω s ) × q (ω s ) 1 -2 ωs ω f + 2ω s dq(ωs) dωs 1 -ωs ω f ( 26
)
Equation 26 is strictly negative if and only if

q (ω s ) 1 -2 ωs ω f + 2ω s dq(ωs) dωs 1 -ωs ω f < 0 ⇔ q (ω s ) ω f -2ωs ω f < -2ω s dq(ωs) dωs ω f -ωs ω f ⇔ ω f -2ωs ω f ω f 2(ω f -ωs) < - ωs dq(ωs) dωs q(ωs) ⇔ - < - ω f -2ωs 2(ω f -ωs) (27)
This condition is always verified when

ω f -2ωs 2(ω f -ωs) < 0 ⇔ ωs ω f > 1 2 .
Otherwise, the relation expressed in equation 27 must be verified. This proves the first assertion.

To prove the second assertion, we derive the fundamental basis volatility regarding ω f and study its sign.

∂V (F V f t -F Vs t ) ∂ω f = ∂ a ω f 2 ((Trωf )-t) 2 q(ωs) 2 t 1-ωs ω f ωs ω f ∂ω f = a 2 q (ω s ) 2 tω s ∂ 1 ω f 2 ((Trωf )-t) 2 1-ωs ω f 1 ω f ∂ω f = a 2 q (ω s ) 2 tω s ∂ ((Trωf )-t) 2 ω f -ωs ω f 4 ∂ω f = a 2 q (ω s ) 2 tω s 2T r ((T r ω f ) -t) ω f -ωs ω f 4 + ((T r ω f ) -t) 2 4ωs-3ω f ω f 5 ∂V (F V f t -F Vs t ) ∂ω f = a 2 q (ω s ) 2 tω s ((T r ω f ) -t) 2T r ω f -ωs ω f 4 + ((T r ω f ) -t) 4ωs-3ω f ω f 5 (28)
This term is strictly negative if and only if

2T r ω f -ωs ω f 4 + ((T r ω f ) -t) 4ωs-3ω f ω f 5 < 0 ⇔ 2T r ω f -ωs ω f 4 < -((T r ω f ) -t) 4ωs-3ω f ω f 5 ⇔ Trω f (Trωf )-t < - 4ωs-3ω f ω f 4 ω f 4 2(ω f -ωs) ⇔ Trω f Trω f -t < 1 + ω f -2ωs 2(ω f -ωs) ⇔ -t Trω f -t > - ω f -2ωs 2(ω f -ωs) (29) For t ∈ [0; T r × ω f -1] ⊂ N, t Trω f -t ≥ 0. Then, this condition is never verified for ω f -2ω s 2 (ω f -ω s ) < 0 ⇔ ω s ω f > 1 2 (30)
For a = 0, t < T , and

ω s = ω f , ∂V (F V f t -F Vs t ) ∂ω f > 0 when ωs ω f > 1 2 .
Otherwise, the relation expressed in equation 29 must be verified. This proves the second assertion.

To prove the third assertion, we compute the total derivation of the fundamental basis volatility considering a proportional increase of the two frequencies.

Using equations 26, 28, and the variation of ω f explained with the variation of ω s computed above, we get:

dV (F V ft -F V st ) = ∂V ar(F V f t -F Vs t ) ∂ωs dω s + ∂V ar(F V f t -F Vs t ) ∂ω f dω f = a ω f 2 (T -t) 2 t 1 ω f q (ω s ) × q (ω s ) 1 -2 ωs ω f + 2ω s dq(ωs) dωs 1 -ωs ω f dω s +a 2 q (ω s ) 2 tω s (T -t) × 2T r ω f -ωs ω f 4 + (T -t) 4ωs-3ω f ω f 5 ω f
ωs dω s = a 2 (T r -t r ) 2 t 1 ω f q (ω s ) 2 1 -2 ωs ω f + 2 ωs q(ωs) dq(ωs) dωs = a 2 (T r -t r ) 2 t ω f q (ω s ) 2 dω s 1 -2 ωs ω f + 2 ωs q(ωs) dq(ωs) dωs 1 -ωs ω f +2 Tr (Tr-tr) 1 -ωs ω f + 4 ωs ω f -3 dV (F V ft -F V st ) = a 2 (T r -t r ) 2 t r q (ω s ) 2 This proves the third assertion.

E Proof of Theorem 5

Proof. The maximal value of the utility function is 0. According to properties (i) and (ii) of U , the maximal value of U is reached if and only if B (s t ) = V (F V ft -F V st ) = 0 (or B (s t ) → 0 and V (F V ft -F V st ) → 0). From theorems 1 and 2 as well as remarks 1 and 3, the only frequencies allowing B (s t ) = V (F V ft -F V st ) = 0 are given by the subset O = (ω s , ω f ) ∈ (F s ∩ F f ) 2 : ωs ω f = 1 . This proves the first assertion.

For e = 0, a = 0, t < T , and ω s = ω f , we have B (s t ) > 0 and V (F V ft -F V st ) > 0. We look for optimal solutions by limit for the two arguments. This gives the following conditions for the second argument:

a ω f 2 (T r ω f -t) 2 q (ω s ) 2 t ωs ω f 1 -ωs ω f = 0 ⇔ q (ω s ) 2 ωs ω f 3 (T r ω f -t) 2 = 0 ⇔ (ω - s ) 2 ωs ω f 3 (T r ω f -t) 2 = 0 ⇔ ωs 1 2 - ω f 3 2 (T r ω f -t) = 0 (32)
As lim

ωs ω f → 0 ω f → +∞ ωs 1 2 - ω f 3 2
(T r ω f -t) = 0, a subset of optimal solutions by limit can exist. This subset is O bl = (ω s ; ω f ) ∈ F s × F f : ωs ω f → 0, ω f → +∞ , and it is independent of the value of . Focusing on the first argument gives the following:

|-e| ω f t k=1 1 -ωs ω f k-1 = 0 ⇔ 1 ω f t k=1 1 -ωs ω f k-1 = 0 ⇔ 1 ω f 1-ωs ω f 1-ωs ω f 1-1-ωs ω f t-1+1 1-1-ωs ω f = 0 ⇔ 1 ωs 1 -1 -ωs ω f t = 0 (33)
We study the limit of the left term of equation 33 within the subset O bl . It gives:

lim ωs ω f → 0 ω f → +∞ 1 ωs = 1 ωs lim ωs ω f → 0 ω f → +∞ ωs ω f = 0 ⇒ lim ωs ω f → 0 ω f → +∞ 1 -1 -ωs ω f t = 0
By product lim

ωs ω f → 0 ω f → +∞ 1 ωs 1 -1 -ωs ω f t = 0
Hence, O bl is also a subset of optimal solutions by limit to the first argument of U . It is consequently the subset of all optimal solutions by limit independent from market characteristics ( value). This proves the second assertion of the theorem.

F Proof of theorem 6

Proof. We use the proof of theorem 5 to identify the other optimal and quasi-optimal trade frequencies.

For e = 0, a = 0, t < T , and ω s = ω f , we have B (s t ) > 0 and V (F V ft -F V st ) > 0. Equation 32 gives the conditions for the second argument to be equal to 0.

If 1 2 -> 0 ⇔ -> -1 2 , no ω s exists that satisfies equation 32. However, the subset O (ω s , ω f ) ∈ F s × F f : ωs ω f → 0 + with ω s → 0 + gives optimal solutions by limit for the second argument of the utility function U . This subset, conditional to the values of , is such that

O < 1 2 bl ⊂ O bl
Hence, there are no other optimal solutions by limit for the second argument in the case of -> - 1 2 . This proves the first assertion.

If 1 2 -< 0 ⇔ -< -1 2 , there exists no ω s satisfying equation 32. However, O > 1 2 bl = (ω s , ω f ) ∈ F s × F f : ωs ω f → 1, ω s → +∞, ω f → +∞ gives optimal solutions by limit for the second argument of the utility function U .

Equation 33 gives the condition for the first argument of the utility function U .

We study the limit of the left term of equation 33 within the subset O (ω s ; ω f ) ∈ F s × F f : ωs ω f → 0, ω f → +∞ gives optimal solutions by limit for the second argument of the utility function U . However, this subset is such that

O = 1 2 bl = O bl
Hence, there are no other optimal solutions by limit in the case of -= -1 2 . This proves the third assertion.

  ω f Historical trade frequency in the futures market per unit of real time: Number of transactions in the futures market tr ω s Historical trade frequency in the spot market per unit of real time: Number of transactions in the spot market tr e Trend of the spot market information delivered in monetary value per unit of real time. a

Figure 1 :

 1 Figure 1: Representation of the spot price bias B (s t ). Parameters used are e = 0.01 and t = 40.

Figure 2 :

 2 Figure 2: Representation of the spot price bias B (s t ). Parameters used are e = 0, 01 and t = 20.

Figure 3 :

 3 Figure 3: Representation of the spot price bias B (s t ). Parameters used are e = 0, 01 and t = 60.

Figure 4 :

 4 Figure 4: Representation of the spot price bias B (s t ). Parameters used are e = 0, 01 and t = 100.

Figure 5 :

 5 Figure 5: Representation of the fundamental basis volatility V ar (F V ft -F V st ). Parameters used are a = 0.01, t = 50, T r = 2500, and = 0.2.

Figure 6 :

 6 Figure 6: Representation of the fundamental basis volatility V ar (F V ft -F V st ). Parameters used are a = 0.01, t = 50, T r = 2500 and = 0, 4.

Figure 7 :

 7 Figure 7: Representation of the fundamental basis volatility V ar (F V ft -F V st ). Parameters used are a = 0.01, t = 50, T r = 2500 and = 0, 8.

Figure 8 :

 8 Figure 8: Representation of the fundamental basis volatility V ar (F V ft -F V st ). Parameters used are a = 0.01, = 0.2, T r = 250, and t = 25.

Figure 9 :

 9 Figure 9: Representation of the fundamental basis volatility V ar (F V ft -F V st ). Parameters used are a = 0.01, = 0.2, T r = 250, and t = 100.

Figure 10 :

 10 Figure 10: Representation of the fundamental basis volatility V ar (F V ft -F V st ). Parameters used are a = 0.01, = 0.2, T r = 250, and t = 200.

1 -ωs ω f dω s +a 2 qω f ω f 3 2

 123 (ω s ) 2 tω f (T r -t r ) 2 Tr (Tr-tr) ω f -ωs ω f + (T -t) (Tr-tr) 4ωs-3ω f ω f 2 dω s

1 2 bl∩ 2 -

 122 of optimal solutions by limit which maximizes U . This subset is such thatO > O bl = ∅This proves the second assertion.If 1 = 0 ⇔ -= -12 , there is no ω s satisfying equation 32. However, the subset O

  19] S. C. P. Yam and W. Zhou. Optimal Liquidation of Child Limit Orders. Mathematics of Operations Research, 42(2):517-545, May 2017.


Liang-Ting Chen
email: liang-ting.chen@swansea.ac.uk

Markus Roggenbach
email: m.roggenbach@swansea.ac.uk

John V Tucker
email: j.v.tucker@swansea.ac.uk

An algebraic theory for data linkage

There are countless sources of data available to governments, companies, and citizens, which can be combined for good or evil. We analyse the concepts of combining data from common sources and linking data from different sources. We model the data and its information content to be found in a single source by an ordered partial monoid, and the transfer of information between sources by different types of morphisms. To capture the linkage between a family of sources, we use a form of Grothendieck construction to create an ordered partial monoid that brings together the global data of the family in a single structure. We apply our approach to database theory and axiomatic structures in approximate reasoning. Thus, ordered partial monoids provide a foundation for the algebraic study for information gathering in its most primitive form.

Introduction

There are countless public and private sources of data that can be linked and analysed for all sorts of reasons, and with all sorts of consequences. The extraordinary variety of what may be considered data-i.e., data that is informative in some way-is a challenge to attempts to discover general principles and techniques for understanding linkage. Motivated by movements for data sharing we try to uncover general structures common to disparate situations.

. Motivation: Exploiting open datasets

The vast stores of data built up by governments, agencies, institutions and companies in the course of their operations hold information of value in diverse and unexpected situations. Some governments have launched initiatives to encourage bodies to share their data with other organisations and the public. The released open data is intended to improve transparency, allowing accountability and engagement with decision making. A systematic review is [ ].

For example, in the UK, there are several national and local registers and a plethora of statistical data that are now widely shared. A simple example of the commercial use of open datasets are web services for selling and letting properties such as Zoopla. In addition to traditional information about a property, official financial data about local house sales and crime statistics are provided. The UK's Open Data Initiative demonstrates the ambition to publish internal government data as open datasets. There are many patterns of data sharing, of which three are particularly important: i) making data public-data release into the wild; ii) data sharing by contract with a data analysis organisation; and iii) data sharing with delegation to a new data controller for further onward sharing. However, data custodians have a legal duty, and a social duty of care, to ensure that privacy is not breached by the release of open data sets.

The technical question arises: What information is revealed by, or can be inferred from, the data? Naturally, prior to its release, a data set can be filtered and anonymised but i) anonymisation is difficult and often flawed; and ii) data from various other sources can be combined with a given data set to reveal much more. There are many data sources to call upon, and many unknown unintended consequences in making data publicly available.

An early example is Sweeney's finding [ ] that 97% of voters in Cambridge, Massachusetts, USA, can be uniquely identified by birth dates and postcodes; these can be further linked with a hospital discharge database to discover individuals' medical history-e.g., of the governor of Massachusetts at that time [ ].

Lately, Narayanan and Shmatikov [ ] devised an algorithm exploiting sparsity to combine datasets. As a case study they analysed the Netflix prize dataset and found '84% of (Netflix) subscribers present in the dataset can be uniquely identified if the adversary knows six out of eight movies outside the top ' that the subscriber rated. Such source of film ratings may come from social engineering or the Internet Movie Database (IMDb). In response to these privacy concerns, Netflix decided to withdraw the datasets. Unfortunately, they are still available to download using BitTorrent or https://archive.org.

.

Algebraic models of combination and linkage

In this paper we take a fresh look at the challenge of combining data sets and linking pieces of data. Our aim is to develop abstract tools to analyse formally the general nature of data sharing, and technical issues of policy specification and compliance. To this end, we seek algebras of data representations, whose operations combine two or more pieces of data from the same source to form data with higher information content. These data representation algebras are to be defined axiomatically. In its simplest form-that presented here-such an algebra is an ordered structure with a partial commutative binary operation ⊕ and an identity element 0, namely, an ordered partial commutative monoid.

The operation ⊕ combines data from the same source. Morphisms between such monoids model the transfer of data between sources-a process we call linkage.

We create an ordered partial commutative monoid that brings together all the data from a family of sources using a simplified Grothendieck construction. We show that our monoid theory of linkage applies to databases and approximate reasoning.

A complete set of proofs can be found at arXiv: . .

Algebras for data combination

.

Information ordering

Data itself is often hierarchical or due to uncertainty becomes so. In this paper, when we reason about data, we implicitly work on a set with an ordering that measures specificity, knowledge, or informativeness. Ideas of information ordering are nothing new, as they appear to be well-known to different communities working on uncertainty reasoning [ , Section . ], multi-valued logic [ ], program semantics [ ], formal concept analysis [ , Chapter ], and (implicitly) anonymisation techniques [ , ], to name but a few.

Definition . . Given a set X, an information order on X is a preorder, i.e. i) x x and ii) x y z implies x z. An information space is merely a preordered set (X, ).

To illustrate the use of preordered sets in the context of data release and privacy, we discuss in some detail the use of postcodes to identify locations.

Example . . The taxonomic hierarchy of British postal codes mostly consists of 6 to 8 alphanumeric characters in a format detailed below. Each postcode is divided into the outward code and the inward code by a single space '␣'. Each component is formed of two further parts and each part covers a smaller area. For example, SA ␣ PP is the full postcode of the Singleton Campus of Swansea University and it is understood as follows:

SA PP Postcode Area Postcode District Postcode Sector Postcode Unit Outward Code Inward Code Postcode
Let the set of all full postcodes be denoted by Post UK .

For simplicity, a partial postcode refers to a code, where less significant parts might be missing, ordered by prefix order including the empty string ' ' as a special postcode indicating everywhere. For example, SA stands for Swansea and SA for a district in Swansea, and we have partial postcodes SA SA2 SA ␣ SA ␣ PP note that ???␣ PP is not a partial postcode. Let us denote the set of all partial postcodes by PPost UK . Each full postcode is incomparable with another, as each of them stands for a disjoint set of postal addresses. On the contrary, the set of partial postcodes possesses the prefix order for the hierarchy. Every partial postcode P can be realised as a set of full postcodes by

vP w := { p ∈ Post UK | P is a prefix of p }.
For instance, an empty string is realised by Post UK , as it contains no information apart from being a postcode. Each full postcode P in Post UK is realised by the singleton set {P }. Note that vP w's are always non-empty.

The reader may find our definition of information space intriguing. For example, why is this only a preordered set instead of a partially ordered set? Indeed, as we can observe from the above example, there are two possible representations of partial knowledge for postcode: i) P + (Post UK )-the non-empty powerset of full postcodes, or ii) PPost UK -the set of partial postcodes determined by its format.

The first (i) can be called the possible world representation [ , Section . ]. It is well-understood in the community of knowledge representation. It is more expressive and general than (ii). Every taxonomic hierarchy of a set of entities can be realised by a possible world interpretation, as each classification level defines a partition of all the entities. The reverse inclusion order '⊇' reflects the information order of taxonomic hierarchy, i.e. P is of higher hierarchy than Q only if vP w ⊆ vQw and '⊇' is surely a partial order. We return to this general points in Section . .

On the other hand, the second kind of representations is often what we have in the first place or what we would like to use in data release. The information order requires some effort to decide, but generally it is clear from the context. However, we may have two different representations for the very same set of entities. If a weight is attached to the data in question, then the second representation is more manageable than the first: vSA ␣ w has the same probability 1/k where k is the possibly unknown number of postcodes in vSA ␣ w. Even if k is known, the presumed probability 1/k is an over-approximation of the given information.

On the other hand, no matter what probability is assigned to subsets of full postcodes, the probability of Pr[SA2 X] is always the sum

SA2 Q Pr[X = Q] = 3/4
without knowing any further information. The expressiveness is limited if we confine ourselves to probabilities of partial postcodes only, since partial postcodes are not closed under Boolean connectives contrary to the subset representation. Yet this limitation enables us to represent the exact information of data.

Another problem of the possible world representation arises if the information order is by nature not anti-symmetric. It is intuitive to see that Fig. a is more informative than Fig. b. There are at least three applicable orderings over subsets P, Q of elements in an information space X, which are

P Q ⇐⇒ ∀x ∈ P. ∃y ∈ Q. x y P Q ⇐⇒ ∀y ∈ Q. ∃x ∈ P. x y P Q ⇐⇒ P Q ∧ P Q
The ordering can model a number of processes or situations. P Q models that everything in P has a more informative datum in Q. So Q is an enrichment of P . Conversely, P Q models that everything in Q has a less informative datum in P , so P is an adulteration of Q.

Each of the orderings plays a role in various contexts, such as non-deterministic computation [ ] and relative likelihood [ , Section . ]. These orderings are preorders but not anti-symmetric in general.

Example . . Ignoring user ID and repetitions, we have two sets representing the information in Fig.

:

P 1 := {SA ␣ PP, SA ␣ PW, SA ␣ LP, SA ␣ QF} P 2 := {SA ␣ , SA ␣ }
The set P 1 is more informative than P 2 with respect to , , and .

Even further, the standard equality '=' on the data in X is irrelevant from the information-theoretic perspective, as we only care about the information content of data. For example, any subset P of an information space (X, ) is indistinguishable from but fails to be equal to its convex hull K(P ) := { a ∈ X | ∃x, y ∈ P. x a y }, i.e.

P

K(P ) P but generally P = K(P ).

So, we introduce:

See, e.g., [ , p. ].

Definition . . Given an information order on a set X, define an equivalence relation by

x ∼ = y ⇐⇒ x y and y x and x is said to be equivalent to y. Each element in the same equivalence class is of the same information content.

From a mathematical viewpoint, each element x is a representative of the information class [x]. Every representative of the same class embodies the same amount of information with respect to the information order . Computing and deciding the information class could be costly and conceptually gain little, so it is easier to work and present our latter formulations with representatives directly.

Remark . . From this, we can argue further that ' ∼ =' is the right notion of equality where the strict equality '=' plays no role at all in an ordered setting. Indeed, the convention is to consider the quotient (X/ ∼ =, / ∼ =) as the poset of information and [x] = [y] is equivalent to x ∼ = y, but this convention makes notations rather heavy.

So the point is that only the preorder for information matters and it fails to be a partial order in general.

. Ordered partial commutative monoids

To combine and link data across various domains yields data that is presumably more informative than the separate pieces of information alone. In this section, we introduce an algebraic operation over an information space for combining data. Central to our investigation is the concept of ordered partial commutative monoids. Whilst monoids of many kinds, e.g., ordered commutative monoids [ ] and partial commutative monoids [ , ], have been discovered and developed in many application areas, surprisingly we have not found a monoid combining both-ordering and partiality. A possible exception we found is monoids viewed as a degenerated class of partial monoidal categories defined in [ ].

Definition . . An ordered partial commutative monoid (M, , ⊕, 0) consists of i) a preordered set (M, ), ii) a constant 0 ∈ M , and iii) a partial binary operation ⊕ : M × M M , i.e. x ⊕ y may not be defined. For brevity, 'x ⊥ y' stands for 'x ⊕ y' is defined. Further, (M, , ⊕, 0) satisfies the properties below.

(OPCM ) 0 ⊕ x ∼ = x. (OPCM ) y ⊥ x and x ⊕ y ∼ = y ⊕ x if x ⊥ y. (OPCM ) x ⊥ y, (x ⊕ y) ⊥ z, and x ⊕ (y ⊕ z) ∼ = (x ⊕ y) ⊕ z if y ⊥ z and x ⊥ (y ⊕ z). (OPCM ) x 1 ⊕ y x 2 ⊕ y if x i ⊥ y for i = 1, 2 and x 1 x 2 .
An ordered partial commutative monoid is written as OPCM for short. An (unordered) partial commutative monoid (M, ⊕, 0), PCM for short, is an OPCM with the discrete ordering x y ⇐⇒ x = y. An ordered commutative monoid is an OPCM with the binary operation ⊕ being total.

The element x ⊕ y denotes data that represents a combination of the information of x and y. The constant 0 stands for some vacuous information so that x ⊕ 0 is always defined and equivalent to x. Partiality enables us to encapsulate consistency or other premises. That is, x may contradict y so that no viable information can be derived; see Example . . Referring to Remark . , the following fact shows that the use of ' ∼ =' is equivalent to the standard equality '=' in the partially ordered quotient:

Proposition . . Let (M, , ⊕, 0) be an OPCM. Then, i) the relation defined by [x] ≤ [y] ⇐⇒ x y on the quotient set M / ∼ = is a partial order and [x] = [y] ⇐⇒ x ∼ = y; ii) ( M / ∼ =, ≤, [⊕], [0]) with [x] [⊕] [y] defined as [x ⊕ y] is an OPCM.
The algebraic structure of a PCM also gives rise to a natural ordering between information purely determined by the combination ⊕.

Definition . . The algebraic ordering on an OPCM is defined by

x y ⇐⇒ ∃z. x ⊕ z ∼ = y. Proposition . . Every PCM (M, ⊕, 0) with algebraic ordering is an i) OPCM which satisfies ii) 0 x, and that iii) if (x, y) (x , y ), x ⊥ y , x ⊥ x, then x ⊕ y x ⊕ y .
The algebraic ordering of an OPCM (M, , ⊕, 0) is compatible with the information ordering if the identity 0 is the -least informative element: Proposition . . Let (M, , ⊕, 0) be an OPCM such that 0 x. Then, i) x y =⇒ x y; ii) x, y x ⊕ y whenever x ⊥ y. Remark . . The implication i) in Proposition . along with ii) in Proposition . suggests the hypothesis 0 x is decisive, otherwise ⊕ may not represent 'combination of information' but something else (cf. the semantics of Belnap's 4-valued logic [ ]). However, the property that 0 x for all x ∈ M is not needed for our technical results.

Example . . Consider the collection of all non-empty subsets of full postcodes P + (Post UK ) equipped with the reverse inclusion order P 1 P 2 iff P 2 ⊆ P 1 . The intersection ∩ of subsets as a combination operation ⊕, is a partial operation, since P 1 ∩ P 2 might be empty and ∈ P + (Post UK ). Clearly, intersection is monotone with respect to the reverse inclusion order. Similarly, the set of partial postcodes equipped with the prefix ordering discussed in Example . has a simple OPCM structure: x ⊕ y is defined as max{x, y}.

. Homomorphisms

The internal structure of an OPCM models data and information of a single source. So the external interaction between OPCMs models a comparison, combination, interpretation, or linkage between sources. Various kinds of structure preserving maps between OPCMs arise naturally, e.g., order-preserving maps, ⊕-preserving maps, or both. We begin with the familiar one.

Definition . . A homomorphism M f -→ N of OPCMs is a function satisfying (HOM ) x M y =⇒ f x N f y (HOM ) f (0 M ) ∼ = 0 N (HOM ) x ⊥ y =⇒ f (x ⊕ M y) ∼ = f x ⊕ N f y
The collection of OPCMs with their homomorphisms forms a category PCM .

An 'interpretation' of information in a different domain of discourse or context, is a typical example of a homomorphism. The trivial map f : M → N defined by f (x) = 0 is a homomorphism that destroys all the information in M . The set of partial postcodes per se is merely a set of strings following a specific format, so it makes little sense to say how rare a postcode P is among other postcodes; it becomes meaningful when it refers to certain geographic area, population, or other associated information.

Example . . Let Pop UK denote the UK population. Assume that i) everyone (of interest) is registered with exactly one postcode for their main residence, and ii) each postcode is associated with someone. The assumption amounts to a surjective function f :

Pop UK → Post UK .
Consider the possible world representation for Pop UK . Each set S of postcodes then can be interpreted as the set vSw := f -1 (S) ⊆ Pop UK of population officially registered in the area specified by P . The mapping v-w : P + Post UK → P + Pop UK is clearly homomorphic w.r.t. the OPCM discussed in Example . , since i) it is monotone, as vS 1 w ⊇ vS 2 w if S 1 ⊇ S 2 ; ii) it preserves the identity, as f -1 (Post UK ) = Pop UK ; iii) and moreover vS 1 ∩ S 2 w = vS 1 w ∩ vS 2 w as f -1 preserves intersection.

Besides concrete homomorphisms, one has the following standard notions: isomorphism, monomorphism, embedding, epimorphism, and so on, following the doctrine of category theory. Among them, the product of two OPCMs can be understood as pairs of independent sources of information.

Definition . . The product monoid M 1 × M 2 of M i = (M i , i , ⊕ i , 0 i ) for i = 1, 2 is the cartesian product equipped with i) the pointwise ordering (x 1 , x 2 ) (y 1 , y 2 ) ⇐⇒ x 1 1 y 1 ∧ x 2 2 y 2 , ii) 0 := (0 1 , 0 2 ), and iii) (x 1 , x 2 ) ⊕ (y 1 , y 2 ) := (x 1 ⊕ 1 y 1 , x 2 ⊕ 2 y 2 ) if x 1 ⊥ y 1 and x 2 ⊥ y 2 .
The universal property for product shows that M 1 × M 2 consists of pairs of independent pieces of information from M 1 and M 2 : Proposition . . For any OPCM N and any pair of homomorphisms f i : N → M i for i = 1, 2, there exists a unique homomorphism h :

N → M 1 × M 2 such that π i • h = f i , where π i is the i-th projection homomorphism.
Other useful notions are embedding and isomorphism.

Definition . . A homomorphism e : M

N is an order-embedding if it not only preserves but also reflects the ordering: e(x) e(y) ⇐⇒ x y. An isomorphism is a bijective order-embedding.

Further examples

.

Flat algebras

The most simple OPCM is perhaps a set X equipped with an additional element ⊥ denoting unknown and x ≤ y iff x = ⊥ or x = y with x ⊕ y := (the join of x and y). In spite of its simplicity, it has been elaborated further in relational database theory [ , Chapter ].

.

Possibilities over a set

We have used a possible world representation discussing postcodes (Section . ).

In this section, we study its general properties. As the reader may have observed from our examples about non-empty subsets of full postcodes, the argument is completely generic and can be applied to any non-empty set X. In short, we have the following generalisation of Example . :

Proposition . . For any non-empty set X, the non-empty powerset P + X with the reverse inclusion and intersection forms an OPCM (P + X, ⊇, ∩, X).

In general, the set X represents some elementary form of atomic information such as codes, labels, tags or facts from which is made. The data in the source is a non-empty subset S of X containing a set of possible choices from X.

.

Possibilities over an OPCM

It is often the case that only pieces of information shared by a group of people is known instead of each individual's. As each piece of information in our algebraic theory is an element of some OPCM, we proceed with non-empty subsets of an OPCM which is in turn another OPCM. The starting point is the observation that a mere intersection of two subsets of an OPCM (M, , ⊕, 0) would exclude combinable but not exactly the same information. Note that we can reformulate intersection in a rather silly way as

P ∩ Q = { x | x ∈ P, y ∈ Q, x = y }
We can utilise '⊕' and define a combination of two subsets of OPCM by

P ⊕ Q := { x ⊕ y | x ∈ P, y ∈ Q, x ⊥ y }
consisting of refined information only. How about the information order between subsets? It turns out that only one of the orderings for powersets introduced in Section . ,

P Q ⇐⇒ ∀y ∈ Q. ∃x ∈ P. x y
is a sensible preorder with respect to the definition of P ⊕ Q.

Theorem . . Let (M, , ⊕, 0) be an OPCM such that M is ⊕-downward closed, i.e. if x x and x ⊥ y then x ⊥ y. For non-empty subsets P and Q,

P ⊕ Q := { x ⊕ y | x ∈ P, y ∈ Q, x ⊥ y }.
Then, i) P + M = (P + M, , ⊕, {0}) is also an OPCM; ii) {0} P for any P if 0 x for any x ∈ M .

Data linkage

A domain of discourse can have a number of data sources so that the same piece of information can be understood in various contexts differently. How do we know that the original information remains intact?

.

Change of domain

A homomorphism f : M → N qualifies as a mapping changing domains from M to N but it can lose data, e.g. the trivial map f (x) = 0 destroys all data.

One way to avoid this problem is to use homomorphisms with a restriction map f * : N → M satisfying a 'preservation condition' x f * f (x) for x ∈ M .

Definition . . A homomorphism f : M → N is a change of domain if f is a lower adjoint, i.e. there exists an order-preserving map f * : N → M such that

f x N y ⇐⇒ x M f * y
Our formal definition requires that an extension f with its restriction f * forms a Galois connection [ ].

Every Galois connection (f, f * ) gives rise to a closure operator-a monotone function

f * • f satisfying i) x f * f (x) and ii) f * f (f * f x) f * f x.
Intuitively, the information represented by f * f (x) is at least as informative as x.

Every adjoint is unique up to order isomorphism-that is, if g is an upper adjoint of f then f * y ∼ = gy for any y, so we can say that a homomorphism f is a change of domain without referring to f * .

The class of changes of domain is closed under composition. It is not hard to see that the composite k • f of two lower adjoints is again a lower adjoint, because k • f is homomorphic and by definition

k(f x) z ⇐⇒ f x k * z ⇐⇒ x f * k * z.
Trivially, an identity function id is itself a change of domain. Therefore, the class of OPCMs and changes of domain forms a subcategory of PCM .

Example . . The homomorphism v-w : P + Post UK → P + Pop UK discussed in Example . is indeed a change of domain. The restriction from P + Pop UK to P + Post UK is given by mapping a set of population to the set of their registered postcodes. The existence of this restriction follows from the assumption that everyone of interest signs a register with a full postcode. Formally, the restriction is the forward-image function of the surjection f : Pop UK → Post UK given by our assumption, so

vSw A ⇐⇒ f -1 (S) ⊇ A ⇐⇒ S ⊇ f [A] ⇐⇒ S f [A]
for any non-empty S ⊆ Post UK and A ⊆ Pop UK .

Given a change of domain f : M → N , there are two different ways to combine x ∈ M with y ∈ N . Their relationship can be stated as follows:

Proposition . . Given a change of domain f : M → N , the following

x ⊕ f * y f * (f x ⊕ y)
always holds for any x ∈ M and y ∈ N .

Armed with these notions, we now formally define 'linkage' as follows.

Definition . . A linking passage (f i , g i ) i=1,2 of M 1 and M 2 is a commutative diagram of changes of domain up to equivalence:

K g2 = = g1 a a M 2 ∼ = f2 a a M 1 f1 = = N i.e. the equation f 1 • g 1 (k) ∼ = f 2 • g 2 (k) for any k ∈ K. Given a linking passage as above, elements x i ∈ M i can be linked as i f i x i in N .
In the context of information, the OPCM K above is some common domain of discourse between M 1 and M 2 ; N is some domain at least including M 1 and M 2 . Given a linking passage of M 1 and M 2 , there are two ways transferring information from M 1 to M 2 -one through the larger domain N and the other through their common domain K. The former route intuitively preserves more information than the other, and this intuition can be justified as follows.

Proposition . . Given a linking passage (f i , g i ) i=1,2 and for any

x ∈ M 1 , the inequation g 2 (g * 1 (x)) f * 2 (f 1 (x)) holds. Diagrammatically, N f * 2 ! ! M 1 f1 = = g * 1 ! ! M 2 K g2 = = Example . . Assume that M 1 = P + (X × Y ) and M 2 = P + (Y × Z). Then, P + Y g1 5 5 g2 h h P + (X × Y ) f1 h h P + (Y × Z) f2 6 6 P + (X × Y × Z)
is a linking passage where f 1 , f 2 , g 1 , g 2 are preimage functions of corresponding projections. Moreover, the subset

f 1 (U ) ∩ f 2 (V ) is equal to { (x, y, z) | (x, y) ∈ U ∧ (y, z) ∈ V } for any non-empty U ⊆ X × Y and V ⊆ Y × Z,
which is the natural join in relational database theory. For a plausible example in practice, consider U ⊆ Pop UK × Addr UK a non-empty set of suspects with their hiding places and V ⊆ Addr UK ×Pop UK a non-empty set of house addresses and their owners. The combined information f 1 (U ) ∩ f 2 (V ) may represent triplets of suspects, addresses, and house owners who possibly provide shelters to suspects.

Local computation scheme

In practice, each datum x i about the attribute i is collected from various data sources M i . To combine all x i 's, we can combine them in a common domain M and then restrict the combined information to a smaller domain N of interest, i.e. g * n i=1 f i x i represented symbolically. The computation is usually costly, however. One interesting observation stated as the combination axiom from [ ] in a similar form is that the above information can be computed locally without the need of extending everything to M if inequalities in Propositions . and . are in fact equivalences for the involved changes of domains. This observation would be useful for developing an efficient computation algorithm, however, which is beyond the scope of this paper.

. Possibilities over a set

A surjective function X Y gives rise to a change of domain from P + Y to P + X. The surjectivity requirement is essential to ensure that a non-empty subset S ⊆ Y is mapped to a non-empty subset f -1 (S) ⊆ X.

Proposition . . For any surjective function

f : X Y , there is a Galois connection f -1 (V ) ⊇ U ⇐⇒ V ⊇ f [U ]
where the preimage function f -1 is a homomorphism from P + Y to P + X and the forward-image function f [-] :

P + X → P + Y is monotonic.
It is straightforward to see that the inequality of Proposition . is an equality for any change of domain given by a surjective function. That is,

f [f -1 (U ) ∩ V ] = U ∩ f (V )
for any U and V by simple calculations.

Proposition . . Suppose that there are f i :

X i Z and g i : Y X i for i = 1, 2 with g 1 • f 1 = g 2 • f 2 . Then, (g -1 i , f -1 i ) is a linking passage, i.e. Y g1 ~~g 2 X 1 f1 X 2 f2 ~Z implies P + Y P + X 1 g -1 1 : : P + X 2 g -1 2 d d P + Z f -1 2 : : f -1 1 d d
If a linking passage is created by functions g i : Y → X i , then non-empty subsets U i ⊆ X i can be linked as a subset of Y

U 1 U 2 = g -1 1 (U 1 ) ∩ g -1 2 (U 2 ).
Example . . Let A be a set of attributes and for each a ∈ A a set Φ a of values for the attribute i. For example, i can be g for 'gender', p for 'British postcode', s for 'salary', etc., then Φ g could be the two-element set {♂, ♀}, Φ p = Post UK the set of all full British postcodes, and Φ s = N the set of natural numbers. Given any two sets I, J ⊆ A of attributes, we have a commutative diagram

k∈I∪J Φ k g1 / / / / g2 i∈I Φ i f1 j∈J Φ j f2 / / / / l∈I∩J Φ l
where g i and f i are all projections.

Data sources and linkage

So far, an OPCM M is an abstract collection of data from a data source for a single domain of discourse that can be combined and compared. A model of data linkage requires a family of PCMs (M i , i , ⊕ i , 0 i ), for i ∈ I, and ways to move among various sources and domains. Further, the nature of sources and domains induces a structure to the index set I, typically an ordering , that reflects the relationship between sources and domains such as i j. With these components, we will model and illustrate data linkage using a form of Grothendieck construction for I-indexed OPCMs.

We will develop the theory in two steps and compare our construction with axiomatic frameworks in the community of approximate reasoning such as ordered valuation algebras [ ] and information algebras [ , ].

.

Grothendieck construction for preordered sets

Let I be a preordered set and P an I-indexed family of preordered sets P i for i ∈ I together with order-preserving functions P i j : P i → P j whenever i j satisfying i) P i i ∼ = id Pi : P i → P i is the identity function, and

ii) P j k • P i j ∼ = P i k : P i → P k where P j k • P i j ∼ = P i k means P j k • P i j (x) ∼ = P i k (x)
for every x and similarly for P i i ∼ = id. Note that P is a pseudo-functor. If the above equations hold strictly, then P is a (proper) functor.

Definition . . The Grothendieck completion of P consists of

P := { (i, x) | x ∈ P i }
with a relation defined by (i, x) (j, y) ⇐⇒ i j and P i j (x) y for x ∈ P i and y ∈ P j

The ordering appears natural in our context: P i j is typically a change of domain, and P i j (x) is merely an extension of x and (i, x) (j, y) if and only if j is a larger domain of discourse than i and the extended form of x is still less informative than y.

Proposition . . The following statements are true:

i) The above Grothendieck completion P is a preordered set. ii) If (I, ≤) and every (P i , ≤) is partially ordered, then so is ( P, ).

iii) The projection p : P → (I, ) is functorial. iv) p is an opfibration. That is, for every (i, x) ∈ P , j with i j there exists (j, y) such that (i, x) (j, y) and moreover for any (k, z) with (i, x) (k, z) and j k it is also true that (j, y) (k, z).

v) If each P i j has a right adjoint, then p is an bifibration, i.e. p op : ( P, ) → (I, ) is also an opfibration.

Remark . . The construction presented here is a form of Grothendieck construction. The full construction works no only for preordered sets but also categories and beyond. See, e.g., [ ], for details.

.

Grothendieck construction for OPCMs

In this section, we extend the Grothendieck construction to OPCMs indexed by a ∨-semilattice (L, ), where L is partially ordered with a least element denoted by ⊥ and for every pair (i, j) of elements there is a least upper bound i ∨ j.

Given a (pseudo-)functor from (L, ≤) to PCM we extend the local combination operations ⊕ i for each i ∈ L to a global combination operation for M . To simplify our discussion, we confine ourselves to functors instead of pseudofunctors. Indeed, all of our discussion and examples in the remaining section do not require this generality.

Theorem . . Let (L, ≤) be a bounded ∨-semilattice and M : (L, ≤) → PCM a functor. Then, the Grothendieck completion ( M, ) can be equipped with an OPCM given by

(i, x) (j, y) := (k, M i k (x) ⊕ M j k (y)) and 0 := (⊥, 0 ⊥ )
where

k = i ∨ j and (i, x) (j, y) is defined if M i k (x) ⊕ M j k (y) is defined.
The above construction is a slight modification of a form of Grothedieck construction for monoidal categories, see [ ] for details.

. Example: Natural join for relational dataset

Before we show our general result of ordered valuation algebras, we proceed with our simplest example-the possibility representation. The linkage operation derived from Theorem . is the natural join in relational database theory [ ].

First of all, we assume that there is a set A of known attribute names and a set Φ a of values for each attribute a ∈ A. For example, A may consist of tags for UK postcode, personal information, medical conditions, and so on. By abuse of notation, we denote by Φ A for A ⊆ A the cartesian product Φ A := a∈A Φ a . Whenever A ⊆ B, we have projections p B,A from Φ B to Φ A which sends (x b ) b∈B to (x a ) a∈A . A functor P from the powerset P(A, ⊆) to PCM is defined by

(A ⊆ A) → (P + Φ A , ⊇, ∩, Φ A ) and (A ⊆ B) → p -1 B,A : P + Φ A → P + Φ B .
In our interpretation, any set S ∈ P + Φ A is a set of possibilities where only one of them is true, so having more elements in S means less specific information.

S T = { x ∈ a∈A∪B Φ a | p A∪B,A (x) ∈ S ∧ p A∪B,B (x) ∈ T }
which is by definition the natural join in relational database theory.

.

Ordered valuation algebras

It is observed in the community of approximate reasoning that with two algebraic operations of combination and marginalisation a number of approximating inference techniques can be formalised under reasonable assumptions. The axiomatic approach is pursued by Shenoy and Shafer [ ], Shenoy and Kohlas [ ],

Haenni [ ], etc. In this section, we show that a variant of their axiomatic frameworks can be derived by our Grothendieck construction for ordered (total) commutative monoids, clarifying the relationship between our approach and theirs.

The following concept is derived from [ ]:

Definition . . A (stable) ordered valuation algebra is a two-sorted algebra (Φ, ≤, D), consisting of a partially ordered set (Φ, ≤) of valuations and a bounded lattice D of domains with operations

i) ⊗ : Φ × Φ → Φ called combination, ii) d : Φ → D such that d(ϕ) is called the domain of ϕ, iii) (-) ↓-: Φ × D Φ called
focusing where ϕ ↓x is defined for x ≤ d(ϕ), iv) and e : D → Φ such that e x is (called) an identity element satisfying conditions below. In the following context,

Φ x = { ϕ ∈ Φ | d(ϕ) = x }. i) (Φ, ⊗) is a commutative semigroup. ii) Comparable valuations are of the same domain: ϕ ≤ ψ implies d(ϕ) = d(ψ). iii) Identity element: d(e x ) =
x, e x ⊗ e y = e x∨y , and ϕ ⊗ e x = ϕ for ϕ ∈ Φ x . iv) Stability of identity under focusing:

e ↓x y = e x for x ≤ y. v) Labelling: d(ϕ ⊗ ψ) = d(ϕ) ∨ d(ψ) and ϕ ↓x ∈ Φ x if x ≤ d(ϕ). vi) Transitivity of focusing (ϕ ↓y ) ↓x = ϕ ↓x for x ≤ y ≤ d(ϕ). vii) Distributivity of focusing over combination: (ϕ ⊗ ψ) ↓d(ϕ) = ϕ ⊗ ψ ↓d(ϕ)∧d(ψ) . viii) Combination preserves ordering: ϕ 1 ⊗ ϕ 2 ≤ ψ 1 ⊗ ψ 2 whenever ϕ i ≤ ψ i .
ix) Focusing preserves ordering: ϕ ↓x ≤ ψ ↓x for any x ≤ d(ϕ) = d(ψ) and ϕ ≤ ψ.

The focusing operation ↓ formalises marginalisation in probability theory and projection in relational database theory. The intuitive meaning of every other operation is self-evident. In addition to the focusing operation, a vacuous extension operation, coined in [ ], (-) ↑y : Φ x → Φ y can be defined for every y ≥ x via ϕ ↑y := ϕ ⊗ e y

We will see that ↓ and ↑ form a Galois connection under mild conditions.

Remark . . The original formulation in [ ] imposes additional requirements. For example, D is only a powerset instead of a lattice and Φ x also requires a null (or, absorbing) element which in [ ] represents a special inconsistent information.

For the sake of brevity, we refrain to discuss these conditions. More variants of (unordered) valuation algebras can be found in [ , ].

Proposition . . Let (Φ, ≤, D; ⊗, d, ↓, e) be an ordered valuation algebra. Then, the following statements hold:

i) (Φ x , ≤, ⊗, e x
) is an ordered commutative monoid. ii) For any x ≤ y, the vacuous extension operation (-) ↑y is an order-preserving monoid homomorphism from Φ x to Φ y . iii) (Φ, ≤, D; ⊗, d, ↓, e) gives rise to a functor from D to the category of ordered commutative monoids.

As we intend to view ordered valuation algebras as Grothendieck completions of families of commutative monoids, an obvious discrepancy is that ϕ and ψ are comparable only if d(ϕ) = d(ψ) in ordered valuation algebras while elements (x, ϕ) and (y, ψ) in P are comparable even if domains x and y are different. This can be readily mitigated by extending ≤ canonically: By applying the Grothendieck construction (Theorem . ) to the D-indexed family of ordered commutative monoids Φ x (Proposition . ), we have a partially ordered set ( Φ, ). The mapping (x, ϕ) → ϕ is evidently bijective since d(ϕ) = x, and (x, ϕ) (y, ψ) ⇐⇒ ϕ ≤ ψ by definition. That is, the bijection (x, ϕ) → ϕ is an order isomorphism between ( Φ, ) and (Φ, ≤ ).

It is clear that the domain operation d : Φ → D is the projection p : Φ → D through the isomorphism, i.e. p(x, ϕ) = d(ϕ). Similarly, e x ∈ Φ x is unique for each x, so it defines e : D → Φ.

As for the combination operations ⊗ and , note that is given by (x, ϕ) (y, ψ) = z, ϕ ↑z ⊗ ψ ↑z

The order-preservation property of focusing accordingly becomes 'if ϕ ≤ ψ and x ≤ d(ϕ) then ϕ ↓x ≤ ψ ↓x '.

where z = x ∨ y and ϕ ↑z ⊗ ψ ↑z = ϕ ⊗ ψ by an easy calculation. Henceforth, ⊗ is the same as via the isomorphism. It remains to derive the focusing operation from the Grothendieck construction. To this point, we need a regularity condition: Every adjoint is uniquely determined by the other adjoint, so in particular the focusing operation ↓ is uniquely determined by the vacuous extension ↑.

To sum up, we have shown that the combination operation ⊗ of an ordered valuation algebra can be derived by the Grothendieck construction: Theorem . . Every regular ordered valuation algebra (Φ, ≤, D; ⊗, ↓, e) with e x ≤ ϕ for any ϕ ∈ Φ x is isomorphic to the Grothendieck completion ( Φ, , , 0) of the functor given by Proposition . . Remark . . Both Theorems . and . justify our claim that data linkage is made of data combination and changes of domain. The Grothendieck construction is in fact an equivalence of categories so that a pseudo-functor from a preorder to monoidal structures is essentially an opfibration equipped with a global monoidal structure. For interested readers, see [ , Theorem . ].

Concluding remarks

Ubiquitous computing has led to ubiquitous data. Technologies exist that explore information content by combining data in a dataset and, in particular, linking data from different datasets. Given the diversity of what passes for data-exact, approximate, erroneous, fictitious-a very abstract conceptual framework is needed to discover any general principles in today's datafest.

We have presented an abstract algebraic framework based on axiomatic notions that model a data source, data representations and their combination '⊕', a measure of information content ' ', and linkage between data sources. By stripping down intuitions we have found that ordered partial commutative monoids provide algebraic structures to be found at the heart of many quite disparate data sharing situations.

Our approach could be developed further using category-theoretic notions which have proved successful in database theory, see e.g., [ ]. While databases provide useful examples for our theory, the exact connection remains unclear.

Our next steps are to map the scope of ordered partial commutative monoids by exploring new and various i) types of data, especially those in approximate reasoning such as belief functions and those discussed in uncertainty reasoning [ ], and so on; ii) types of operations on and between our algebras.

Returning to our background motivation in the introduction, clearly more attention needs to be paid to the concept of data privacy and how linkage of data can lead to privacy breach, e.g., de-anonymisation. This is the subject of ongoing investigations, cf. [ ].

Interestingly, there does not seem to be much of a theory of ordered partial commutative monoids so that, too, is something to do.

Figure :

 : Figure : Datasets containing postal information

  If A ⊆ B, then p -1 B,A (S) is merely the set S padded with all combinations, i.e. S × b∈B-A Φ b . So, p -1 B,A (S) contains no information about attributes B -A. Therefore the ordering on the Grothendieck completion Φ (A, S) ≤ (B, T ) ⇐⇒ A ⊆ B and S × b∈B-A Φ b ⊇ T simply means that (A, S) is less informative than (B, T ) if (B, T ) contains more attributes and is more specific on those already known in A. By Theorem . , the derived operation is given as (A, S) (B, T ) = (A ∪ B, S T ) for A, B ⊆ A, S ∈ P + (Φ A ), and T ∈ P + (Φ B ) where

ϕ

  ≤ ψ ⇐⇒ d(ϕ) ≤ d(ψ) and ϕ ⊗ e d(ψ) ≤ ψ. Proposition . . The ordered algebraic structure (Φ, ≤ , D; ⊗, d, ↓, e) satisfies the conditions of ordered valuation algebra except that ϕ ≤ ψ implies d(ϕ) = d(ψ).

Lemma . .

 . For any ordered valuation algebra Φ = (Φ, ≤, D; ⊗, d, ↓, e), the following statements are true:i) ϕ ↑y ≤ ψ implies ϕ ≤ ψ ↓x . ii) If e x ≤ ϕfor any ϕ ∈ Φ x and Φ is regular, i.e. for any ϕ and x ≤ d(ϕ) there is χ ∈ Φ x such that ϕ ↓x ⊗ χ ⊗ ϕ ≤ ϕ, then ϕ ≤ ψ ↓x implies ϕ ↑y ≤ ψ. Remark . . The condition(s) in Lemma . are studied in [ ]. Idempotent valuation algebras are called information algebras by Kohlas [ ].

This research was supported by the EPSRC project Data Release-Trust, Identity, Privacy and Security (EP/N / and EP/N / ).