Fundamental changes in the electrical energy sector are drawing on serious implications. One key arising challenge regards current energy markets, which are undergoing a transformation towards accommodating a more decentralized and sustainable provision of energy. As the number of traders in the market is increasing steadily and the trading activities are becoming more complex, the energy markets are becoming more exposed to potential fraud. In this paper we address the problem of detecting collusive behavior, where a group of individual traders act together, inconsistently with the competitive model, to arti cially manipulate the market and elicit illegal pro ts. We investigate collusion attacks in the energy market and propose a novel mechanism, showing the e ectiveness and practical applicability of our method to real scenarios.
Market surveillance represents a serious challenge and it refers broadly to the detection of abnormal market behaviors, which are known to be predominant especially in the emerging markets. In practice, an e cient way for in uencing the market and gaining illegal pro ts is represented by the class of collusionbased malpractices. Conceptually, collusive behavior represents an attempt of a group of individual traders, that act together, to arti cially manipulate the market (e.g. through price or market share) for maximizing their gains, in a manner inconsistent with a competitive model and in detriment to the other participants in the market.
While collusion has been reported in various market domains, the damages
discovered were averaged at about a 25% increase in costs incurred by costumers
[
Though there are many ways in which collusion could be discovered, we address in this work collusion detection via the analysis of economic data, freely available in the market. The set of laws that regulate the market require continuous surveillance of trading activities. This can essentially be achieved either through online or o ine surveillance. The former is constrained to analysing short-term data as well as being restricted to a limited time-window, thus being prone to overlooking occurrences of more complex types of fraud. Alternatively, o ine techniques can encompass a wider spectrum of illegal trading strategies, while having an anticipatory or retroactive character. Obviously though, both approaches remain dependent on the amount of input data available.
In this paper, we propose an e ective o ine method to identify collusive
groups with respect to the domain of energy markets, which are being reoriented
towards replacing the traditional top-down energy supply with a decentralized,
market-oriented provision [
This paper is organized as follows: in Section 2 we provide a survey of some related work. Section 3 introduces our novel mechanism and discusses how to apply it to detect collusive behavior in the energy market. In Section 4 we show the experimental results. Finally, Section 5 concludes the paper and points directions for future work. 2
Emerging nancial markets are inherently exposed to malpractices, whereas a subset of traders collaborate tacitly to manipulate the market for maximizing their individual gains. In the course of the last years, new challenges in the Electricity Market have come to the forefront, due to the transformations occurring in the power supply infrastructure. As new distributed energy resources (DERs: e.g. wind plants, photovoltaics, combined heat and power units) are pervading the electricity grid, they provide for an increasing number of participants in the market. This trend has driven the liberalization of electricity markets and the creation of power exchanges with the emphasis on decentralized power provision.
More formally, the participants in the market, consumers and suppliers of power, can be denoted by the market agent set A = fa1; : : : ; ang, which exists in a bijective relationship with the set of devices D = fd1; : : : ; dng connected to the grid. The day-ahead market is discretized over a nonempty and nite set of distinct and successive time periods T = ft1; : : : ; tmg. Under this setting, a bid of agent ai timestamped at tmpij is represented by the function bij : T ! R R, specifying respectively, for time slot ti, the amount of electricity requested or o ered and the intended price per unit, as bij (ti) = (vj ; pj ). To summarize the trading activity for agent ai at trading day tmpij we associate the time-series Xij = fbij (t1); : : : ; bij (tm)g, which captures the existing bids for each time-slot in T , else being considered a null bid.
Several approaches have attempted to automate the process of collusion
detection based on economic data. A common method would be to apply supervised
learning techniques, given that proven fraudulent activities, previously detected,
could be obtained. Of course such datasets for training are not usually available
in signi cant amount. Thus, some work has looked into unsupervised learning,
namely using graph clustering algorithms. In [
In this paper we address the phenomenon of collusion in the emerging energy markets where the collusive markers identi ed above do not hold, as novel domain driven markers need to be derived. 3
To start with, for discovering collusion in a market we need to be speci c as to what behavioral patterns, that might be indicative of collusion, we will be looking for.
Our goal is to detect the presence of colluders that are coordinating their behavior at the expense of the rest of the market participants, by adopting a behavior inconsistent with what a competitive environment might entail. In this work, the collusive marker that we investigate in order to provide evidence of economic collusion consists of detecting colluders in the energy market based on the similar trading behaviors of agents. Colluders can generally be di erentiated by similar trading patterns (which also depart from competition), as opposed to those outside their coalition. Thus, within a coalition of colluders their trading behavior should exhibit correlations when they should normally be independent.
Consequently, we design our collusion detection method as a two-stage process: a screening phase and a veri cation phase, as depicted in the diagram of Fig 1. The screening phase has the role of performing a triage through the order record of the market and identifying a set of market agents that are worthy of closer scrutiny. Due to the combinatorial explosion of possible colluder subsets and the data-intensive analysis, this phase is ought to output a set of candidates that will be further addressed during the veri cation phase.
Speci cally, the screening phase is testing each market agent, looking for structural breaks in its behavior. Such behavioral breakpoint could be associated with the formation of a coalition of colluders (or with its dissolution). We approach this by running a change-point analysis (CPA) over the discretized order record of each market agent. If any behavioral breakpoints, which may be conductive to colluding coalitions, have been identi ed, they will represent the input for the second phase. Obviously such behavioral changes could be expected even when no collusion takes place. During veri cation we are essentially looking at two aspects: i) whether there is a price or volume correlation between the candidates' breakpoint and ii) if there appears inconsistencies with the competitive model.
While this methodology preserves a broad outlook into the realm of collusion detection in nancial markets in general, further approaches can be directly derived for di erent contexts based upon the available data of the speci c markets and agents. Additional domain-speci c insights (see case study in Section 4.2), such as inferring estimates of costs, may ease the distinction between collusion and competition. 3.1
CPA based Behavioral Screening Phase
This section demonstrates the potential usefulness of change-point analysis
techniques for detection of colluding behavior in Energy markets. The approach
undertaken in this paper falls under the class of nonparametric change point
detection methods [
Change-point detection is the problem of discovering time points at which properties of time-series data change. Suppose that X = fx1; : : : ; xng is a sequence of independent random variables, such that the rst r observations XA = fx1A; : : : ; xrAg are distributed as FA and the remaining observations XB = fx1B; : : : ; xB
n rg come from another unknown distribution FB, where FA 6= FB. Hence, integer r is called change point. Representing the trading activity of each market agent ai 2 A in terms of time-series enables us to perform a change-point analysis (Algorithm 1).
So, when a behavioral breakpoint occurs this corresponds to a step change of the mean value of X at r from to + , where represents the minimum increase of the mean value of X. Then, the deviation from the average may indicate that a collusion attack is being launched, if the cumulative deviation is noticeably higher than the random uctuations, lower-bounded by .
A popular method based on a recursive nonparametric change point detection
scheme uses a combination of cumulative sum charts (CUSUM) and
bootstrapping to detect the changes [
The cumulative sums can be recursively de ned using a new sequence fSng: Sn = Sn 1 + (xj S0 = 0
X) where by X we denote the mean of the sample:
Pn X = i=1 xi (2)
n
Thus, the cumulative sum series can be obtained iteratively by adding to the previous sum the di erence between a current value and the sample mean. This means that the sequence fSng always ends at zero ( Sn = 0), as the di erences computed at each iteration sum to zero. Based on these remarks a CUSUM chart can be interpreted as follows. An upward slope of the chart indicates that the corresponding values tend to be above the overall mean of the sample, while a downward slope indicates a period of time where the values tend to be below. When a sudden turn occurs this indicates that around this time, the mean has shifted, which represents a potential changepoint. Likewise, a relatively straight CUSUM represents a period where the average did not change.
In order to associate a con dence level with a changepoint occurrence, a bootstrap analysis can be performed. To start with, a number of bootstrap samples are generated by sampling without replacement, which essentially is a random reordering of the original sample values. Thus, considering the initial sample X of size n, a bootstrapping sample at iteration i will be obtained by permuting without replacing k elements, generating Xki = fx1; xi2; : : : ; xing. For each i of these samples, the bootstrap CUSUM is computed similarly. Moreover, for each sample we need to determine the maximum, minimum and di erence of the bootstrap CUSUM denoted respectively as Smiax = j=m0;1a;x:::;nSj , Smiinj=0m;1i;n:::;nSj and Sdiiff = Smiax Smiin. A bootstrap analysis consists of performing a large number of bootstraps and counting the number of bootstraps for which Sdiiff is less than Sdiff of the initial sample. Let N be the number of bootstrap samples performed. Then, the probability of a changepoint occurrence for a xed point r is given by:
Pr = #fj : Sdiiff (3)
The bootstrapping technique basically compares the Sdiff value of the original data with the Sdiiff values from a number of bootstrap samples, which estimate how much Sdiff would vary if no change took place and checks whether these results are consistent. It is clear that a better estimate can be obtained by increasing the number of bootstrap samples, however statistically signi cant result can typically be obtained for a reasonable number of generations.
Now, if a changepoint has been detected, in order to determine when the change has occurred, di erent estimators can be employed. A straightforward approach would be to determine the changepoint r as the point furthest from zero in the CUSUM chart: j Sr j= argmax j Si j
i=0;1;:::;n
The point r estimates last point before the change occurred, while the point r + 1 estimates the rst point after the change.
Alternatively, the changepoint occurrence can be estimated by applying the mean square error estimator (MSE). The idea behind this estimator is that of partitioning the data in two sequences X1 = fx1; : : : ; xrg and X2 = fxr+1; : : : ; xng and estimating the mean of each sequence and compare this against the initial data:
M SE(r) =
r X(xi i=1
X1)2 + n X (xi i=r+1
X2)2 where X1 =
Pir=1 xi and X2 = r
Pin=r+1 xi .
n r (4) (5) Algorithm 1: Change point analysis
Data: Xn, N , k, Result: changepoint r (if any) S0 0; for i
Si 1 to n do Si 1 + (xi
X) ; end for j 1 to N do generate bootstrap sample Xkj , S0
j for i 1 to n do
Sij Sij 1 + (xij Xj ); end
0; 1 to N do j Sdiff = Smjax
j if Sdiff
cnt else end
Sdiff then cnt + 1;
Smjin, cnt
0; end for j else end end P = cnt
N if P 1 then
apply estimator to determine changepoint r 3.2
Veri cation Phase for Collusive Coalitions Now, having identi ed a candidate set of potential colluders, which allows to narrow our search space, we proceed to the second phase. Here, the focus is on detecting correlations between any members of the candidate set, resulting in a coalition structure1. Considering two timeseries X = fx1; x2; : : : xng and Y = fy1; y2; : : : yng representing the trading activities of agents ax and ay respectively, we are interested to capture linear dependencies between the two variables: X and Y . As a measure of similarity, we evaluate the covariance, which determines how X and Y vary together:
i=1 where x is the sample mean of the X values and y is the sample mean of the Y values. The covariance measure ranges from 1 for perfectly correlated results, 1 If all members of the candidate set show correlations we refer to this as the grand colluding coalition, while no correlations corresponds to the empty set.
n Cov(X; Y ) = 1 X(x(i) n x)(y(i) y) (6) through 0 when there is no relation between X and Y , to -1 when the results are perfectly correlated negatively.
More generally, if we consider k variables we can construct the covariance matrix (k k), where an element (i; j) represents the covariance between the ith and jth variables. Removing the dependence of the covariance on the ranges of the variables can be done by standardization, dividing the result by the standard deviations of X and Y . The result is the correlation coe cient between X and Y : (X; Y ) =
Pn i=1(x(i) x)(y(i)
y) Pn i=1(x(i) x)2 Pn i=1(x(i) x)2 1=2 (7)
Algorithm 2 summarizes the veri cation phase according to the computations previously detailed.
Algorithm 2: Collusion detection
Data: order record set O from one trading day discretize over a xed time slot sequence = ft1; : : : ; tkg; set of market agents
A = fa1; : : : ; ang Result: collusion candidate set C = fS1; : : : ; Slg C ;; for each market agent ai do extract order record Xi associated to agents ai from O run change point analysis for given Xi if probability of change point occurrence 95% then
C C [ ai; determine change point r with estimator ; else end generating covariance matrix for elements ai 2 C , l = 1; for i 1 to sizeof(C) do for j i to sizeof(C) do
M (i; j) Cov(Xi; Yi); if M (i; j) 1 then
Sl fai; aj g; if ai Sk or aj Sk then
append Sl to Sk; end else l l + 1; append Sl to C; else end end end
Data preparation Prior to running our collusion detection mechanism, the dataset needs to undergo a pre-processing phase. As discussed in Section 2, we retain from the order record of the Energy Market, for every agent, a time-series for each day consisting of their bids, with respect to the prede ned time-slots T of the day-ahead market. Therefore, agent ai is characterized at day j by Xij = fbij (t1); : : : ; bij (tm)g.
Now, in order to run a meaningful change-point analysis over this data, detecting relevant behavioral breakpoints, we need to span the investigation over a time-window of several days. Moreover, we need to relate the agents' trading patterns to the temporal organization of the day-ahead market, T . Speci cally, let's assume a time-window of length l days and a xed discretization of the day-ahead market T = ft1; : : : ; tmg. This requires constructing for each agent ai the set of time-series Xki = fb1(tk); : : : ; bl(tk)g, k = 1; m. Next, recall that a bid, bij (ti) = (vj ; pj ), from an energy supplier consists of the amount of electricity offered and the intended price per unit. This further implies that for each Xki there corresponds a time-series denoting price Pki = fp1(tk); : : : ; pl(tk)g and another for the intended trading volume Vki = fv1(tk); : : : ; vl(tk)g. This representation of the data is used during the screening phase for generating the collusion candidate set, as well as during the veri cation phase for detecting price or volume correlations. 4.2
Case study
In this section we report on results2 obtained from applying our model to
real datasets, collected from the Philippine Wholesale Electricity Spot Market
(WESM) [
We proceed with the screening phase by conducting an exhaustive changepoint analysis over the bid records of each market participant. Table 1 summarizes the results obtained at this stage, outlining the colluding candidate set as input for the following phase. For the given scenario we have generated 1000 bootstrap samples for each run of the algorithm. The results indicate that out of the total number of market agents, behavioral breakpoints have been detected for 10 agents, some of which exhibiting multiple ones. An illustration of this process is given in Figure 2 for market agent a6. Figure 2a is a representation 2 We remind the reader that the analysis of economic data only, has the role of discovering suspicious behavior and is not meant to provide conclusive evidence of collusion, nor substitute antitrust authorities, but rather to provide supporting evidence and triggers for deciding whether antitrust authorities should actively engage and further pursue such an investigation.
Fig. 2. a) Plot of the trading activity P16 corresponding to market agent a6 for January 2012. b) The associated CUSUM chart for the time-series of market agent a6. of a6's trading activity during the speci ed time-window. The result of performing the screening analysis over this data, using the MSE estimator, detects the occurrence of one change-point timestamped at day 24. The con dence level associated, indicates a 100% accuracy. In Figure 2b we plot the corresponding CUSUM chart, highlighting a sudden shift in the average, associated with the change-point detection. Generally, it is not the case that change-points can be readily detected visually from the time series plot. A CUSUM chart however, can facilitate pinpointing shifts in the mean of the data, by identifying slope changes at the points where a change has occurred.
Next, the mechanism proceeds with the veri cation phase. As previously detailed, for the designated candidate set, generated during screening, we investigate further correlations between the market agents' trading patterns. This phase yields the covariance matrix, a representation of which is given in Figure 3. Here, we perform an exhaustive pairwise comparison of the candidate set. White squares denote a perfect correlation between the respective market agents, while black stands for no similarities. The color shading inbetween is indicative of the correlation strength. Finally, according to Algorithm 2 the coalition structure of colluders is determined. For the considered scenario, the coalition structure of potential colluders consists of solely one group: CS = ffa1; a5; a6; a7; a10gg. For privacy concerns, we omit other direct reference to the suspected colluders. Note that the particular choice of the value of the correlation coe cient threshold is ought to impact the number of resulting colluders. One one hand, higher thresholds imply a higher level of con dence for the collusion detection process, but on the other hand it may as well reduce the number of possible suspects, disregarding certain abnormal trading behaviors. Alternatively, lower thresholds may result in including false colluders to the coalition structure and therefore reducing the accuracy of the mechanism. In this context, selecting a reliable correlation coe cient threshold is an important issue for the overall performance of the mechanism, which we plan to address in future work. Speci cally, we intend to calibrate the system based on already proven cases of collusion and use such scenarios as training data. In addition to this, we plan to extend the model to integrate details regarding the devices D, which are controlled by the market agents A, such as DER type and geographical location. Adding this domain-dependent dimension is ought to provide further insight into di erentiating between correlations that may come as a result of external conditions (e.g. weather conditions) and those that are irrespective to this regard. 5
In this paper we have addressed the challenge of detecting collusive traders that collaborate illegally to increase their bene ts at the expense of the other market participants. We have pose this question in the domain of the emerging energy markets, that are adapting to the integration of a diversity of distributed energy generators. Such contexts are especially susceptible to various trading malpractices.
The proposed method for discovering colluders consists of two phases. Firstly we apply a screening phase that performs a change-point analysis in order to detect behavioral breakpoint in the traders' activities, proposing a reduced candidate set of possible colluders. Secondly, for the denominated group we run a veri cation phase aimed at revealing behavioral correlations. The procedure determines a potential coalition structure of colluders. We evaluate our mechanism on real datasets and show the e ectiveness and practical applicability of our method, even for scenarios that are exploiting a minimal amount of data, that is freely available on the market. Continuing along these lines, future work will further investigate and exploit other collusive markers that may expose potential vulnerabilities in the energy market.