# Strategic bidding via the interplay of minimum income condition orders in
day-ahead power exchanges

Dávid Csercsik  Pázmány Péter Catholic University
Faculty of Information Technology and Bionics
Práter u. 50/A 1083 Budapest, Hungary
Tel.: +36-1 886 47 00 Fax: +36-1 886 47 24
<EMAIL_ADDRESS>
###### Abstract

In this paper we study the so-called minimum income condition order, which is
used in some day-ahead electricity power exchanges to represent the
production-related costs of generating units. This order belongs to the family
of complex orders, which imply non-convexities in the market clearing problem.
We demonstrate via simple numerical examples that if more of such bids are
present in the market, their interplay may open the possibility of strategic
bidding. More precisely, we show that by the manipulation of bid parameters, a
strategic player may increase its own profit and potentially induce the
deactivation of an other minimum income condition order, which would be
accepted under truthful bidding. Furthermore, we show that if we modify the
objective function used in the market clearing according to principles
suggested in the literature, it is possible to prevent the possibility of such
strategic bidding, but the modification raises other issues.

## Nomenclature

MCP | Market clearing price
---|---
DAPX | Day-ahead power exchange
TSW | Total social welfare
MIC | Minimum income condition
FT | Fixed term
VT | Variable term

##  1 Introduction

If one investigates trading and pricing mechanisms in various electricity
markets around the globe, it may be recognized that despite local market
integration advancements and the convergence implied by them, the evolution of
individual markets resulted in a diverse set of mechanisms and approaches [1,
2, 3]. Moreover, additional allocation and pricing mechanisms emerged in
relation with electricity trade, as balancing markets
[4] and transmission-related allocation and pricing
[5]. If we focus on short-term trading of electricity on competitive markets
and its diversity among continents, we must recall the well-known paradigm
that the general approach of such markets in the US is dominantly based on the
unit commitment approach [6]. This paradigm basically means that generators
submit their production characteristics to a independent system operator
(ISO), who determines their schedule, according to consumption demands and to
technological and economic constraints. In contrast, in the EU, portfolio-
bidding markets, or day-ahead power exchanges (DAPXs) are operating, where
self-scheduling generating units and further market participants have the
possibility to act as active market players and submit bids to two-sided
markets, which are cleared in order to obtain zonal market clearing prices. In
the general framework these markets are coupled, and the clearing mechanisms
also take transmission constraints into account [7, 8, 9]. In this paper, we
focus on the latter, European-type market structure.

###  1.1 Simple hourly bids in DAPXs

The fundamental setting of these two-sided multiunit markets is very simple:
Participants on the supply and the demand side submit bids characterized by
quantity ($q$) and price per unit ($p$) for the respective trading period(s)
(typically hour) of the following day, which in general may be fully or also
partially accepted, according to the resulting market clearing price (MCP) of
each hour. In this basic setup, we practically look for the intersection point
of demand and supply curves, which ensures the balance of consumption and
production. This way, in each period maximum one bid is partially accepted,
which determines the MCP.

Figure 1 shows a simple example of such a market clearing for a single-period,
single-zone case. We assume 3-3 bids on the supply and demand side denoted by
S1-S3 and D1-D3 respectively. The supply and demand curves depict bids sorted
by their price (in increasing/decreasing order).

The bid quantity of bid $i$ of type $w$ ($w\in\\{s,d\\}$) is denoted by
$q^{w}_{i}$, while its price is denoted by $p^{w}_{i}$. Demand bids are
considered with negative quantity ($q^{d}_{i}<0$). Cumulative quantities,
defining the breakpoints of the supply and demand curve are denoted by
$Q^{s}_{i}$ and $Q^{d}_{i}$ respectively.

$Q^{s}_{i}=\sum_{j=1}^{i}q^{s}_{j}~{}~{}~{}~{}~{}Q^{d}_{i}=-\sum_{j=1}^{i}q^{d}_{j}$
(1)

In this particular case, D2 (the second demand bid) is partially accepted,
thus its bid price determines the MCP ($MCP=p^{d}_{2}$), and the traded
quantity equals to $Q^{s}_{2}=q^{s}_{1}+q^{s}_{2}$.

Figure 1: Fundamental scheme of the day-ahead electricity spot market for a
trading period. $Q^{s}_{i}$ and $Q^{d}_{i}$ stand for the cumulative
quantities, i.e. $Q^{s}_{i}=\sum_{j=1}^{i}q^{s}_{j}$ and
$Q^{d}_{i}=-\sum_{j=1}^{i}q^{d}_{j}$.

We solved this simple case by determining the intersection point of the supply
and the demand curves. As we will see in the next subsection (1.2), special
bids in these markets may be present, which do not allow partial acceptance.
In this case, the curve-intersection approach may fail, if the intersection
point hits one of these bids.

However, the intersection point on Figure 1 has an other important
interpretation. Let us define acceptance values for each bid:
$y^{w}_{i}\in[0,1]$ denotes the acceptance ratio of bid $i$ of type $w$
($w\in\\{s,d\\}$). The acceptance values which determine the intersection
point in this case are

$y^{s}_{1}=1~{}~{}~{}y^{s}_{2}=1~{}~{}~{}y^{s}_{3}=0~{}~{}~{}y^{d}_{1}=1~{}~{}~{}y^{d}_{2}=\frac{3}{7}~{}~{}~{}y^{d}_{3}=0~{}.$
(2)

In electricity trade, the supply must always meet the demand, thus we require
the balance

$\sum_{i}y^{s}_{i}q^{s}_{i}+\sum_{i}y^{d}_{i}q^{d}_{i}=0~{}~{}~{}.$ (3)

Let us furthermore define the concept of the total social welfare (TSW). TSW
in this context is interpreted as the total utility of consumption, minus the
total cost of production, formally

$-\sum_{i}y^{d}_{i}q^{d}_{i}p^{d}_{i}-\sum_{i}y^{s}_{i}q^{s}_{i}p^{s}_{i}~{}~{}~{}.$
(4)

(Remember that $q^{d}_{i}<0$.)

This quantity equals to the area between the accepted part of the demand and
supply curves. It is easy to see that if we start from the point defined by
the values (2) and decrease or increase the total traded quantity (the supply-
demand balance must still hold), the TSW is strictly decreased. In fact, the
values described in (2) are exactly those values, which maximize the total
social welfare of the market, assuming the balance constraint 3.

This concept of TSW maximization may be generalized to more complex cases.
Indeed, this principle is usually a fundamental element of European-type
market clearing mechanisms.

In general, if multiple trading periods are considered and no
interdependencies arise between the periods, the above approach may be applied
for each of the periods independently. In this paper, we will assume a simple
two-period case, but as we will see in the following, the characteristic order
types of electricity trade will define interdependencies between the periods.

###  1.2 Complex orders in electricity markets

It is easy to see that the setup detailed above does not consider
technological constraints of generating units: It is possible that the
resulting MCPs imply that a unit submitting bids for two consecutive hours
must produce at full capacity in the first hour and shut down in the second
(if its bid is fully accepted in the first period, and fully rejected in the
second), while the technological constraints of the unit make this impossible.
The first approach to address these problems has been the introduction of so-
called block orders [10], which connect multiple bids submitted for various
periods and they must be fully accepted or rejected in all of the respective
periods (in other words, they are characterized by the ’ _fill-or-kill_ ’
condition). These bids imply non-convexities (integer variables) in the market
clearing problem [11], making the efficient clearing of large scale markets
challenging [12]. To guarantee the existence of MCP when block orders are
allowed, we must allow their deactivation, regardless of their bid prices
[13]. This may result in so-called paradoxically rejected block orders [14],
the rejection of which seemingly contradicts to the resulting market clearing
prices (but in fact, they can not be accepted without the violation of other
constraints, since if they get accepted the MCP will not exist anymore [11]).

Block orders are also beneficial for incorporating the non-negligible start-up
cost of the generating units. The simple cost model of generating units
usually includes a fixed term (FT) corresponding to start-up costs and a
variable term (VT), which is interpreted as the linear coefficient describing
the connection between the generated quantity and the variable (fuel) cost of
the units (see e.g. [15]). The efficient implementation and market effects of
block orders have been discussed in the literature [10, 14, 16].

####  1.2.1 Minimum income condition orders

In addition to block orders, one may find further so-called complex orders and
products in today’s practical electricity market implementations [17, 18, 19,
20]. One of these complex orders is the so-called _Minimum Income Condition
(MIC)_ order. The MIC was first introduced in the Spanish electricity market
[21] and since then it became quite commonly used in various market models
[22, 23, 18, 24, 25, 26], including novel approaches which aim to provide
optimization-based framework for the optimal joint energy and reserves market
clearing [27].

Nevertheless, the necessity [28], the effects on market outcomes [29, 11, 30]
and the efficient implementation of MIC orders [31, 32, 33, 12, 34] are still
subject to ongoing debates and studies.

EUPHEMIA, the market-coupling tool which was brought to life by European
market integration trends, and serves as a kind of reference for European
market design approaches, also includes MIC orders. In its public description
[35], Minimum Income Condition (MIC) orders are defined as supply orders
consisting of several hourly step bids (elementary bids) for potentially
different market hours, which are connected by the MIC which prescribes that
the overall income of the MIC order must cover its given costs. These costs
are defined by a fix term (representing the startup cost of a power plant) and
a variable term multiplied by the total assigned production volume
(representing the operation cost per MWh of a power plant). Formally, the
Minimum Income Condition constraint is defined by two parameters:

  * •

A fix term (FT) in Euros

  * •

A variable term (VT) in Euros per accepted MWh.

In the final solution, MIC orders may be activated or deactivated (as a
whole):

  * •

In case a MIC order is activated, each of the hourly sub-orders of the MIC
behaves like any other hourly order, which means that they are accepted if and
only if the MCP is higher or equal to the bid price.

  * •

In case a MIC order is deactivated, each of the hourly sub-orders of the MIC
is fully rejected, even the MCP is higher or equal to the bid price.

We can see that the MIC condition links multiple hourly bids, and the
necessary condition for the acceptance of these bids is the activation of the
MIC order, which can be described by a binary variable.

###  1.3 Incentive-compatibility and its relevance in electricity-related
markets

The concept of incentive-compatibility is originating from the 70’s [36, 37],
and it is related to the evaluation of allocation mechanisms under the
assumption of strategic behavior of participants. The topic is discussed in
auction theory [38], however most of the results in this field correspond to
single-unit auctions of indivisible goods [39], while in the case of
electricity markets a multi-unit auction framework applies. Let us however
note that the problem of simultaneous allocation of multiple indivisible goods
with complementarities is addressed in the framework of combinatorial auctions
[40, 41].

As formulated by [42], ’ _A mechanism is called incentive-compatible if every
participant can achieve the best outcome to themselves just by acting
according to their true preferences_ ’. As the original problem statement
assumes indivisible goods, which does not hold in multi-unit electricity
auctions, preferences translate to evaluations in our case: Considering the
simple example depicted in Fig. 1, in ideal case, bidders on the demand side
bid their real consumption utilities and bidders on the supply side bid their
real marginal costs. We consider strategic bidding compared to this reference
case of truthful bidding.

Figure 2: Possible small variations of the bid price of supply bid 1
($\Delta$) has no effect on the MCP, thus the acceptance and payoff supply bid
1 is not affected.

Figure 2 demonstrates, why the standard, marginal (i.e. MCP based) clearing
model of multi-unit electricity markets is considered to be _practically_
incentive-compatible.

If we perturb the bid price of supply bid 1 (S1) by $\Delta$ as depicted in
the picture, the outcome of the auction does not change: The MCP determining
the set of accepted/rejected bids will be the same as before. In addition, as
bids are paid off according to the MCP, the resulting utility of the deviating
player also remains the same. If e.g. the bid price is increased, the nominal
income of the bid is increased, but the surplus resulting from the difference
of the MCP and the bid price is decreased by the same amount.

The above deduction is on the one hand only true for small deviations (e.g. in
our case we assume that for the modified value $\hat{p}^{s}_{1}$ the
inequality $\hat{p}^{s}_{1}<p^{s}_{2}$ still holds) and on the other hand it
is not true for all bids. As in the proposed case the second demand bid (D2)
sets the MCP, $p^{d}_{2}$ is in fact affecting the market clearing price, and
if the bidder of D2 decreases $p^{d}_{2}$, it can effectively increase its own
surplus (as long as the inequality $p^{d}_{2}\geq p^{d}_{3}$ holds).

If we consider an other bid than D2, but perturb the price so much that it
changes the ordering of bids, and the actual bid will be exactly the price-
setter (e.g. if we decrease $p^{d}_{1}$ to
$p^{d}_{3}<\hat{p}^{d}_{1}<p^{d}_{2}$), the same effect arises.

In practice, the number of standard bids for any period in DAPXs is high
(several thousand or tens of thousands), and as in the bid submission process
the actual other bids are not known, at first glance it seems unlikely that
such manipulation can be effectively carried out. On the other hand, as recent
examples have shown [43], the number of big players may be limited, and high
proportion of bids may originate from the same players. In this case,
oligopolistic behavior and related phenomena may emerge on electricity markets
[44].

Regarding MIC orders, according to the publicly available data of OMIE (the
Spanish DAPX), where this formulation is used (https://www.omie.es), the
number of these orders is significantly lower, about 75-85 per day.

In the above reasoning, we assumed the manipulation of bid price. This is
however not the only alternative. Let us assume a market scenario, where there
are some large suppliers with significant bid quantities, like S2 in Fig. 1).
As depicted in Fig. 3, if $q^{s}_{2}$ is reduced to
$\hat{q}^{s}_{2}=0.5~{}q^{s}_{2}$, the intersection point of the two curves
will change, the MCP is increased, and the bidder of S2 receives significantly
more payoff for one unit of energy. This phenomena is also termed as _capacity
withholding_ , discussed by [45] in a similar auction-based but also network-
constrained framework. The possibility also arises on the other side (demand
reduction), although in electricity markets, large producers (i.e. big power
plants) are more prevalent than large consumers.

Figure 3: Reduction of supply: The quantity of the bid S2 is modified to the
half of its original value. This causes the MCP to increase.

While in this very case the supply is reduced in the market, in order to get a
higher payoff, similar effects may arise if multiple participants are
competing for a fixed set of goods, as in the case of treasury and spectrum
auctions. In this case, as discussed by [46], we talk about demand reduction.

Up to this point we discussed cases in which one participant unilaterally
changes its bidding behavior to improve its payoff, while it was assumed that
the rest of the bids is unchanged. The question however may be formulated in a
more general context as well, where all submitted bids are subject to
strategic behavior. The paper of [47] considers power generation companies
(GenCos) located in a network as leaders of a Stackelberg type game, in which
the independent system operator (ISO) plays the role of the follower. The
paper develops a bi-level mathematical programming framework to model the
market clearing mechanism of the ISO where the behavior of GenCos and network
constraints are taken into account. In this model, the authors are able to
describe the collusive behavior of GenCos, and also provide numerical examples
demonstrating the possible uniqueness/non uniqueness of Nash Equilibria. As we
will see later, our main aim in this paper is to show how the minimum income
condition orders may be used for strategic bidding. Potential equilibrium
problems resulting from such strategic behavior are not the main focus of this
study, they are discussed only marginally.

####  1.3.1 Pay-as-bid auction and incentive-compatibility

Let us note that in addition to the marginal clearing model described in
subsection 1.1, the pay-as-bid method is also applies in the case of some
electricity related markets, like for example the Iranian electricity market
(http://www.irema.ir/trading/day-ahead-market). However, as discussed by [48],
in this case, in contrast to the marginal clearing market model, all
participants do have clear incentives: Suppliers aim to raise their bid prices
up to the maximum acceptable level to earn the most payoff. This results in a
flattened supply curve, and according to [48], it exacerbates market
competitiveness.

In other studies, agent based simulations were used to determine optimal
strategic bidding behavior and market efficiency in the context of pay as bid
vs marginal pricing [49, 50, 51, 52, 53].

###  1.4 Contribution and structure of the paper

The possibilities of strategic bidding via MIC orders have not been explicitly
discussed in the literature. In this paper, our aim is to show that under the
current practice, bidders submitting MIC bids may have additional incentives
for strategic bidding, if multiple such bids are present on the actual market.
To demonstrate this, based on the widely used EUPHEMIA framework and the
respective definition and formalism of MIC orders, we introduce a simple
market clearing framework for a two period market, where the phenomenon may be
studied in its purest form.

In section 2, we introduce the computational implementation of the market in
detail. Section 3 demonstrates how strategic bidding may increase the payoff
of MIC bids via the interplay of such bids, and also analyses the scenario,
when a modification in the objective function of the market clearing algorithm
is introduced to address this issue. Section 4 evaluates and discusses the
proposed results, and finally section 5 concludes and drafts future prospects
of the work.

##  2 Materials and Methods

In the next subsection, we introduce the market model in which the interplay
of MIC orders is studied. To clarify our terminology, MIC _orders_ are
composed of multiple hourly _bids_ (termed ’sub-orders’ in the EUPHEMIA
description cited in subsection 1.2), belonging to different trading periods
(hours).

###  2.1 Computational implementation

The market clearing in DAPXs is implemented as an optimization problem. In
this section, we introduce the components (variables) of this problem and
formulate the corresponding constraints and the objective function.

We assume a simplified single-zone market model, where only two time periods
are considered. In addition, we assume that only two types of bids are present
on the market:

  * •

Simple hourly bids. The acceptance of these bids is solely determined by the
MCP of the respective period.

  * •

Hourly bids belonging to complex MIC orders. The acceptance of these bids
depend not only on the MCP of the period to which the bid belongs, but on the
total income of the order, which, in turn, depends on the MCP values of other
periods as well.

Since MIC conditions of complex orders define interdependencies between
trading periods, the bids submitted for various periods must be cleared
simultaneously.

The computational form of the market model used in this paper includes the
following variables:

  * •

Market clearing prices (MCPs) of the two trading periods, denoted by $MCP_{1}$
and $MCP_{2}$ respectively. In the current paper we assume that every $MCP$ is
nonnegative.

  * •

Acceptance variables of simple hourly supply bids. The acceptance variable of
the i-th simple supply bid is denoted by $y^{s}_{i}$. All acceptance variables
are bounded as $0\leq y\leq 1$.

  * •

Acceptance variables of simple hourly demand bids. The acceptance variable of
the i-th simple demand bid is denoted by $y^{d}_{i}$.

  * •

Acceptance variables of hourly bids belonging to complex orders. The
acceptance variable corresponding to the i-th component of complex order $c$
is denoted by $y^{c}_{i}$

  * •

Variables corresponding to the income of individual bids of complex orders.
The income of bid $y^{c}_{i}$ is denoted by $I^{c}_{i}$.

  * •

Auxiliary integer variables corresponding to the big-M implementations of
logical implications. The vector of these variables is denoted by $z$.

####  2.1.1 Simple hourly orders

The acceptance constraints in the case of simple hourly supply bids may be
written as

$\displaystyle y^{s}_{i}>0~{}~{}~{}\rightarrow~{}~{}~{}p^{s}_{i}\leq MCP_{t}$
$\displaystyle y^{s}_{i}<1~{}~{}~{}\rightarrow~{}~{}~{}MCP_{t}\leq p^{s}_{i}$
(5)

where $p^{s}_{i}$ is the bid price of the simple hourly supply bid $i$, and
$MCP_{t}$ denotes the $MCP$ of period $t$, for which the bid is submitted
($t\in\\{1,2\\}$).

The implications may be easily included in the MILP formulation. Let us
consider e.g. the first implication of eq. 5, which is equivalent to

$p^{s}_{i}\leq MCP_{t}~{}~{}~{}or~{}~{}~{}y^{s}_{i}\leq 0~{}~{}.$ (6)

The equivalent of the logical expression (6) is the set of the inequalities
(7), where $z\in\\{0,1\\}$ is an auxiliary integer variable and
$\overline{MCP}$ is the upper bound of the variable $MCP$.

$\displaystyle p^{s}_{i}-z\overline{MCP}_{t}\leq MCP_{t}$ $\displaystyle
y^{s}_{i}-(1-z)\leq 0$ (7)

We can use the variable $z$ to ’cancel’ one of the inequalities of 6, but not
both of them. In the following we assume that all implications are implemented
using the above ’bigM’ method (where the bigM refers to $\overline{MCP}$ the
upper bound of $MCP$ used in the formulation).

Similarly to supply bids, in the case of simple hourly demand bids, the
constraints may be written as

$\displaystyle y^{d}_{i}>0~{}~{}~{}\rightarrow~{}~{}~{}MCP_{t}\leq p^{d}_{i}$
$\displaystyle y^{d}_{i}<1~{}~{}~{}\rightarrow~{}~{}~{}p^{d}_{i}\leq MCP_{t},$
(8)

where $p^{S}_{i}$ is the bid price of the simple hourly demand bid $i$.

####  2.1.2 Bids of complex orders

The first part of the constraints described in the formula (5) is also active
in the case of supply bids belonging to complex orders:

$y^{c}_{i}>0~{}~{}~{}\rightarrow~{}~{}~{}p^{c}_{i}\leq MCP_{t},$ (9)

where $p^{c}_{i}$ is the bid price of the i-th component of the complex order
$c$, corresponding to time period $t$.

The considerations of an MIC bid described in subsection 1.2 are formulated in
the optimization framework of market-clearing algorithms as

$\displaystyle\sum_{i}y^{c}_{i}>0\rightarrow
FT_{c}~{}~{}+~{}~{}VT_{c}\sum_{i}q^{c}_{i}y^{c}_{i}\leq I^{c}$ (10)

where $y_{k}$ is the acceptance indicator of the elementary bid $k$ belonging
to set of bids of the complex order $c$. $FT_{c}$ and $VT_{c}$ denote the
fixed and variable cost terms of complex order $c$. $q^{c}_{i}$ is the bid
quantity of bid $y^{c}_{i}$, and $I^{c}$ is the variable representing the
total income of the complex (MIC) order $c$, which may be calculated as

$I^{c}=\sum_{i}I^{c}_{i}$ (11)

Intuitively $I^{c}_{i}$ may be calculated as

$\displaystyle I^{c}_{i}=MCP_{t}~{}q^{c}_{i}~{}y^{c}_{i}$ (12)

where $q^{c}_{i}$ stands for the quantity of the bid $y^{c}_{i}$.

Equation (12) however includes a quadratic expression of variables, namely the
product of $MCP_{t}$ and $y^{c}_{i}$, the implementation of which which would
result in a computationally demanding quadratically constrained problem
(MIQCP). To overcome this issue, and obtain a linear form of expressions,
following [33, 34], we formulate the expressions for income as

$\displaystyle
y^{c}_{i}>0~{}~{}\rightarrow~{}~{}I^{c}_{i}=y^{c}_{i}q^{c}_{i}p^{c}_{i}+q^{c}_{i}MCP_{t}-q^{c}_{i}p^{c}_{i}$
(13) $\displaystyle
y^{c}_{i}<1~{}~{}\rightarrow~{}~{}I^{c}_{i}=y^{c}_{i}q^{c}_{i}p^{c}_{i}$ (14)

As described by [33], taking into account the bid acceptance rule described in
(9), three possibilities may arise:

  1. 1.

If the bid is entirely accepted ($y^{c}_{i}=1$), $I^{c}_{i}$ equals the
product of $q^{c}_{i}$ and $MCP_{t}$ according to (13).

  2. 2.

If the bid is partially accepted ($MCP_{t}=p^{c}_{i}$), $I^{c}_{i}$ equals to
$y^{c}_{i}q^{c}_{i}p^{c}_{i}$. Both (13) and (14) are active in this case and
they result in the same inequality.

  3. 3.

And finally, if the bid is entirely rejected ($y^{c}_{i}=0$), according to
(14) $I^{c}_{i}=0$.

####  2.1.3 Power balance

Formula (15) describes that the quantity of accepted supply bids must be equal
the quantity of accepted demand bids for all periods. Let us note again that
the quantity of demand bids is negative by definition.

$\sum_{i\in B_{t}}y^{s}_{i}+\sum_{\\{c,i\\}\in B_{t}}y^{c}_{i}+\sum_{i\in
B_{t}}y^{d}_{i}=0~{}~{}~{}~{}~{}\forall t$ (15)

where $B_{t}$ denotes the set of bids corresponding to period $t$.

####  2.1.4 The objective function

Following the fundamental concepts of day-ahead electricity auctions [13], the
objective function of the problem is to maximize the total social welfare
(TSW), defined as

$TSW=-\sum_{i}y^{d}_{i}q^{d}_{i}p^{d}_{i}-\sum_{i}y^{s}_{i}q^{s}_{i}p^{s}_{i}-\sum_{c,i}y^{c}_{i}q^{c}_{i}p^{c}_{i}$
(16)

In other words, the TSW is the total utility of consumption minus the total
cost of production, in the context of the acceptance/rejection of hourly bids.
As $q^{D}_{i}<0$ by definition for all $i$, the corresponding terms must be
multiplied with -1.

Let us note that this objective is in accordance with the concept used in
EUPHEMIA [35], where a somewhat different terminology is used. The EUPHEMIA
description aims to maximize the sum of the _consumer surplus_ and the
_producer surplus_ , which is in fact the TSW. The consumer surplus ($CS$) and
the producer surplus ($PS$) may be derived as

$\displaystyle CS=\sum_{t}\sum_{i\in
B_{t}}y^{d}_{i}q^{d}_{i}(p^{d}_{i}-MCP_{t})$ $\displaystyle
PS=\sum_{t}\sum_{i\in B_{t}}y^{s}_{i}q^{s}_{i}(MCP_{t}-p^{s}_{i})$ (17)

If one considers a simple case without block bids, as depicted Fig. 1, the TSW
is the area between the demand and the supply curve, considering those parts
which are leftmost of the intersection point. The MCP divides this area into
two parts: The upper is CS, while the lower is PS ($TSW=CS+PS$).

Overall, the market clearing problem may be summarized as

$\displaystyle\max_{MCP,Y^{S}_{i},Y^{D}_{i},Y^{c}_{i},Z}TSW~{}~{}~{}~{}\text{wrt.}$
$\displaystyle\sum_{i\in B_{t}}y^{s}_{i}+\sum_{\\{c,i\\}\in
B_{t}}y^{c}_{i}+\sum_{i\in B_{t}}y^{d}_{i}=0~{}~{}~{}~{}~{}\forall t$
$\displaystyle y^{s}_{i}>0~{}~{}~{}\rightarrow~{}~{}~{}p^{s}_{i}\leq
MCP_{t}~{}~{}\forall i$ $\displaystyle
y^{s}_{i}<1~{}~{}~{}\rightarrow~{}~{}~{}MCP_{t}\leq p^{s}_{i}~{}~{}\forall i$
$\displaystyle y^{d}_{i}>0~{}~{}~{}\rightarrow~{}~{}~{}MCP_{t}\leq
p^{d}_{i}~{}~{}\forall i$ $\displaystyle
y^{d}_{i}<1~{}~{}~{}\rightarrow~{}~{}~{}p^{d}_{i}\leq MCP_{t}~{}~{}\forall i$
$\displaystyle y^{c}_{i}>0~{}~{}~{}\rightarrow~{}~{}~{}p^{c}_{i}\leq
MCP_{t}~{}~{}\forall i$ $\displaystyle\sum_{i}y^{c}_{i}>0\rightarrow
FT_{c}~{}~{}+~{}~{}VT_{c}\sum_{i}q^{c}_{i}y^{c}_{i}\leq I^{c}~{}~{}\forall c$
$\displaystyle
y^{c}_{i}>0~{}~{}\rightarrow~{}~{}I^{c}_{i}=y^{c}_{i}q^{c}_{i}p^{c}_{i}+q^{c}_{i}MCP_{t}-q^{c}_{i}p^{c}_{i}~{}~{}\forall
c,~{}\forall i$ $\displaystyle
y^{c}_{i}<1~{}~{}\rightarrow~{}~{}I^{c}_{i}=y^{c}_{i}q^{c}_{i}p^{c}_{i}~{}~{}\forall
c,~{}\forall i$

where MCP is the vector of market clearing prices for the two periods,
$MCP_{t}$ denotes the MCP for the respective time period (for which the bid is
submitted). $Y^{S}_{i}$ and $Y^{D}_{i}$ are the vectors of acceptance
variables corresponding to simple supply and demand bids, $Y^{c}_{i}$ is the
vector of bids belonging to complex orders, $I$ is the vector of incomes of
these bids (auxiliary variables), and $Z$ holds the auxiliary binary variables
used in the big-M formulations of the logical implications (5,8,9,10,13 and
14.

##  3 Results

In this section, we introduce a simple example bid set in a 2-period example,
to demonstrate that due to the special interplay between MIC bids,
participants may have incentives to bid false production cost. Let us assume
the bids described in Table 1.

ID | t | q | p | var
---|---|---|---|---
S1 | 1 | 2 | 5 | $y^{s}_{1}$
S2 | 1 | 2 | 6 | $y^{s}_{2}$
S3 | 2 | 2 | 5 | $y^{s}_{3}$
S4 | 2 | 2 | 6 | $y^{s}_{4}$
S5 | 1 | 2 | 1 | $y^{c1}_{1}$
S6 | 2 | 2 | 1 | $y^{c1}_{2}$
S7 | 1 | 2 | 4 | $y^{c2}_{1}$
S8 | 2 | 2 | 4 | $y^{c2}_{2}$
D1 | 1 | -5 | 10 | $y^{d}_{1}$
D2 | 2 | -5 | 10 | $y^{d}_{2}$
Table 1: Hourly bids of example I: Parameters and corresponding variables.

We suppose that S5-S6 and S7-S8 are part of complex MIC orders ($c1$ and $c2$
respectively), while the rest of the bids are standard bids, cleared purely
according to the resulting MCP.

Let us furthermore assume that the production cost parameters of the units
corresponding to $c1$ and $c2$ are described by the following parameters:

$\displaystyle FT_{1}=10~{}~{}~{}VT_{1}=2$ $\displaystyle
FT_{2}=10~{}~{}~{}VT_{2}=2~{}~{}~{}.$ (19)

We assume that the participant submitting the complex order $c1$ is the only
strategic player, and we call this participant player 1 in the following.

###  3.1 Case 1

In this case, we assume that player 1 submits its real production costs as
parameters of the complex order (i.e. submits the real $FT_{1}$ and $VT_{1}$
values, as described in (3)). As player 2 is not considered as a strategic
player in this example, in the following we assume that $FT_{2}$ and $VT_{2}$
is always equal to the values in (3). This case serves as the reference
describing truthful bidding.

In this case, if we maximize the total social welfare based on the hourly bids
(as described in subsection 2.1 and as it is usual in the case of European
portfolio-bidding type markets), we get the following result. The MCP is 5 in
both periods, and regarding the standard bids, the acceptance indicators are
as

$\displaystyle\left(\begin{array}[]{c}y^{s}_{1}\\\ y^{s}_{2}\\\ y^{s}_{3}\\\
y^{s}_{4}\\\ y^{d}_{1}\\\ y^{d}_{2}\\\
\end{array}\right)=\left(\begin{array}[]{c}0.5\\\ 0\\\ 0.5\\\ 0\\\ 1\\\ 1\\\
\end{array}\right)~{}~{}~{}.$ (32)

The acceptance values of the bids corresponding to complex orders $c1$ and
$c2$ are

$\displaystyle\left(\begin{array}[]{c}y^{c1}_{1}\\\ y^{c1}_{2}\\\
\end{array}\right)=\left(\begin{array}[]{c}1\\\ 1\\\
\end{array}\right)~{}~{}~{}~{}\left(\begin{array}[]{c}y^{c2}_{1}\\\
y^{c2}_{1}\\\ \end{array}\right)=\left(\begin{array}[]{c}1\\\ 1\\\
\end{array}\right)$ (41)

The total cost of MIC bid $c1$ is 18, while its total income is 20, thus the
MIC condition holds. The profit of the strategic player is 2 units in this
case. Similarly, the total cost of MIC bid $c2$ is 18, while its total income
is also 20, thus the MIC condition holds here as well. The resulting dispatch
is depicted in Fig. 4.

Figure 4: Resulting dispatch in case 1.

###  3.2 Case 2

In this case, we assume that the parameters of the hourly bids are the same
(as described in Table 1), while player 1 increases the submitted FT value
from 10 to 14.

$\displaystyle FT_{1}=\textbf{14}~{}~{}~{}VT_{1}=2$ $\displaystyle
FT_{2}=10~{}~{}~{}VT_{2}=2$ (42)

In this case, it is impossible to accept both $c1$ and $c2$. If we consider
the dispatch depicted in Fig. 4, which corresponds to the simultaneous
acceptance of $c1$ and $c2$, we can see that the total income of $c1$ is still
20, but the respective total cost (according to the reported parameters) is 22
(14 units from the fixed cost and 8 units from the variable cost), thus the
market clearing algorithm will not allow this outcome.

If we perform the optimization of the market clearing in this case, we get the
following results. The MCP is 6 in both periods, and regarding the standard
bids, we get the acceptance indicators

$\displaystyle\left(\begin{array}[]{c}y^{s}_{1}\\\ y^{s}_{2}\\\ y^{s}_{3}\\\
y^{s}_{4}\\\ y^{d}_{1}\\\ y^{d}_{2}\\\
\end{array}\right)=\left(\begin{array}[]{c}1\\\ 0.5\\\ 1\\\ 0.5\\\ 1\\\ 1\\\
\end{array}\right)~{}~{},$ (55)

while the values of the complex MIC bids $c1$ and $c2$ are

$\displaystyle\left(\begin{array}[]{c}y^{c1}_{1}\\\ y^{c1}_{2}\\\
\end{array}\right)=\left(\begin{array}[]{c}1\\\ 1\\\
\end{array}\right)~{}~{}~{}~{}\left(\begin{array}[]{c}y^{c2}_{1}\\\
y^{c2}_{2}\\\ \end{array}\right)=\left(\begin{array}[]{c}0\\\ 0\\\
\end{array}\right)$ (64)

According to the submitted parameters, the total cost of MIC bid $c1$ is 22,
while its total income is 24, thus the MIC condition holds. Considering the
real parameters, the production cost of $c1$ is still 18, thus the real profit
of player 1 is increased from 2 to 6 compared to the truthful bidding case
described in subsection 3.1. As no hourly bid of MIC order $c2$ is accepted,
its cost is zero, thus the corresponding MIC holds.

The resulting dispatch is depicted in Fig. 5 As the complex order $c2$ is
deactivated, its hourly bids (S7 and S8) are not included in the supply curve.

Figure 5: Resulting dispatch in case 2.

We can see that by increasing the $FT$ value, player 1 has ’pushed out’ MIC
order S2, and increased its own profit. The reason behind this is the
following: The increase of $FT_{1}$ would intuitively imply the rejection of
$c1$, because its MIC condition is not valid anymore. As the objective
function (the TSW) is however determined on the basis of the hourly bids, the
solver does not want to ’loose’ the hourly bids S5 and S6 corresponding to
$c1$, since, due to their low bid price, they significantly contribute to the
TSW. A more optimal solution is to drop the bids $S7$ and $S8$ of $c2$. By the
deactivation of the complex order $c2$, all corresponding constraints are
fulfilled, and $c1$ may remain active.

In this case, $c2$ is a paradoxically rejected MIC order in this case. If we
consider only the resulting MCPs, it seems that the hourly bids belonging to
$c2$ may be (fully) accepted, and its MIC may be fulfilled. This is however
not a feasible scenario, exactly as in the case of paradoxically rejected
block orders [13].

Let us note furthermore that any submitted FT value for $c1$ satisfying
$12<FT_{1}\leq 16$ will do the job for player 1, in the sense that in any such
case the hourly bids of $c1$ will fully be accepted, while the order $c2$ will
be deactivated. The resulting MCP and thus the (real) profit of player 1 is
independent of the exact value of $FT_{1}$ in this case (if $12<FT_{1}\leq
16$). If $FT_{1}\leq 12$, the MIC condition will also be satisfied with the
MCP of 5, thus the acceptance of $c2$ is allowed, and if $16<FT_{1}$, the MIC
of $c1$ will not hold, thus it will be deactivated and $c2$ will be accepted.

###  3.3 Modifying the objective function

As the anomaly discussed above originates from the fact that the objective
function is determined solely by the acceptance values and parameters of the
hourly bids, a quite straightforward approach to resolve such problem is the
modification of the objective function. In this case, the hourly bids
corresponding to complex orders are not considered in the objective function.
Instead of them, the cost of production in the case of complex orders is
considered based on the given price parameters corresponding to fixed and
variable terms (FT and VT). There are examples present in the literature,
which follow a similar approach. Start-up costs are included in the objective
function in [54, 29], and [12] also consider the start-up costs in the
objective, however the formulation is different in this case.

Formally, we can write the modified objective function as described in eq.
(65).

$TSW=-\sum_{i}y^{d}_{i}q^{d}_{i}p^{d}_{i}-\sum_{i}y^{s}_{i}q^{s}_{i}p^{s}_{i}-\sum_{c}y^{c}FT_{c}-\sum_{c,i}y^{c}_{i}q^{c}_{i}VT_{c}$
(65)

where $y^{c}\in\\{0,1\\}$ equals to 1 if the complex order $c$ is activated,
$FT_{c}$ and $VT_{c}$ are the respectively the fixed and variable costs of
complex bid $c$.

In the following, we will show that this modification of the objective
function resolves the possibility of strategic bidding described in subsection
3.2, but it implies a different kind of issue.

####  3.3.1 Outcome of case 1 assuming the modified TSW

If we apply the modified TSW described in eq. (65) for the bid set described
in subsection 3.1, the results do not change. All the resulting acceptance
indicators, MCPs and payoffs are the same as in the original case.

####  3.3.2 Outcome of case 2 assuming the modified TSW

On the other hand, if the modified TSW described in eq. (65) is applied for
the bid set described in subsection 3.2, the results are affected. In this
case, we get the following results. The MCP is 6 in both periods, regarding
the standard bids,

$\displaystyle\left(\begin{array}[]{c}y^{s}_{1}\\\ y^{s}_{2}\\\ y^{s}_{3}\\\
y^{s}_{4}\\\ y^{d}_{1}\\\ y^{d}_{2}\\\
\end{array}\right)=\left(\begin{array}[]{c}1\\\ 0.5\\\ 1\\\ 0.5\\\ 1\\\ 1\\\
\end{array}\right)$ (78)

while the values of the complex MIC bids $c1$ and $c2$ are

$\displaystyle\left(\begin{array}[]{c}y^{c1}_{1}\\\ y^{c1}_{2}\\\
\end{array}\right)=\left(\begin{array}[]{c}0\\\ 0\\\
\end{array}\right)~{}~{}~{}~{}\left(\begin{array}[]{c}y^{c2}_{1}\\\
y^{c2}_{2}\\\ \end{array}\right)=\left(\begin{array}[]{c}1\\\ 1\\\
\end{array}\right)$ (87)

As no hourly bid of MIC order $c1$ is accepted, its cost is zero, thus the
corresponding MIC holds. The total cost of MIC order $c2$ is 18, while its
total income is 24, thus the MIC condition holds.

We can see that assuming this formulation, increasing FT does not work for
player 1, as it results in the deactivation of its bid, thus its profit is
decreased compared to the reference scenario (Case 1, with truthful bidding).
At first glance, it seems that the modification of the objective function
resolved the problem of the possibility of strategic bidding.

####  3.3.3 Case 3

In this subsection, we show that if we assume the modified objective function
described by eq. (65), which omits the terms corresponding to the hourly bids
of MIC orders, and considers the cost of these bids based on FT and VT,
another potential problems may arise during the clearing process.

Let us assume that the true cost of units submitting complex orders is still
as described in subsection 3.1. We have seen in subsection 3.3.1 that in the
case of truthful bidding, the modified objective function (TSW) has no effect
on the outcome.

Let us now furthermore assume that player 1 modifies the bid price of the
hourly bids belonging to its complex order $c1$ from 1 to 5.5. We assume that
all other hourly bids remain unchanged, as summarized in Table 2.

ID | t | q | p | var
---|---|---|---|---
S1 | 1 | 2 | 5 | $y^{s}_{1}$
S2 | 1 | 2 | 6 | $y^{s}_{2}$
S3 | 2 | 2 | 5 | $y^{s}_{3}$
S4 | 2 | 2 | 6 | $y^{s}_{4}$
S5 | 1 | 2 | 5.5 | $y^{c1}_{1}$
S6 | 2 | 2 | 5.5 | $y^{c1}_{2}$
S7 | 1 | 2 | 4 | $y^{c2}_{1}$
S8 | 2 | 2 | 4 | $y^{c2}_{2}$
D1 | 1 | -5 | 10 | $y^{d}_{1}$
D2 | 2 | -5 | 10 | $y^{d}_{2}$
Table 2: Hourly bids of example I: Parameters and corresponding variables.

Furthermore, we suppose that regarding FT and VT, true values are submitted.

$\displaystyle FT_{1}=10~{}~{}~{}VT_{1}=2$ $\displaystyle
FT_{2}=10~{}~{}~{}VT_{2}=2$ (88)

Let us first note that in this case it is impossible to accept both complex
bids. Fig 6 depicts the resulting dispatch in the case if both MICs are
accepted.

Figure 6: Resulting dispatch if both MICs would be accepted.

As it can be seen, the bid acceptance constraints, which connect the bid
prices of hourly bids to the MCP result in the MCP of 5.5 for both periods,
implying that the hourly bids of $c1$ are partially accepted. In this case,
the total cost of the MIC order $c1$ is 10+4=14, while its income is 11, thus
the MIC condition does not hold. This shows that $c1$ and $c2$ can not be
accepted in the same time. Furthermore, it can be seen in Fig. 6, that any
price for the hourly bid between 5 and 6 will do the job: The implied MCP and
thus the income of $c1$ will be different, but even an MCP of 6 and the
implied income of 12 will not satisfy the MIC constraint (12<10+4).

Either $c1$ or $c2$ can be accepted, furthermore, as the hourly bids of
complex orders are not considered in the modified objective function (the
modified TSW), and the parameters $FT$ and $VT$ are the same for $c1$ and
$c2$, they result in the same TSW. In both cases, according to eq. (65), the
resulting TSW may be calculated as the value of the accepted hourly demand
bids (100), minus the value of accepted hourly bids, which are not part of
complex orders (S1 and S3 are relevant, with the value of 20), minus the cost
of MIC bids according to equation 10, namely 10+4=14, resulting in the TSW
value of 66, considering either the acceptance of $c1$ or $c2$. In either
case, the resulting dispatch will look like the one depicted in Fig. 5,
resulting in the MCP of 6, and implying an income of 24 for the accepted MIC
order (in contrast to the original 20, while the cost is the same).

This means that the objective function has no unique maximum in this case. In
such scenarios, the outcome of the market clearing depends on the
implementation of the optimization problem, and on the properties of the used
solver as well. In general it can be said, that if player 1 modifies its bid
parameters as in Table 2, it is possible that during the clearing $c1$ will be
favoured, $c2$ will be ’pushed out’ again, and the profit of $c1$ will be
increased. More importantly, the resulting optimization problem has no unique
solution, and the outcome of the market may depend on implementation details.

##  4 Discussion

The modification of the objective function as proposed in eq. (65) may prevent
strategic bidding through the manipulation of the submitted FT value, but this
modification also implies that strategic bidding trough the bid parameters of
hourly bids becomes potentially possible.

Regarding the principle of the phenomena, the examples presented in the paper
demonstrate that if a complex order brings large benefits for the objective
function, but it can be accepted only under certain circumstances (e.g. the
MCP must be higher than a given value, as in the examples above for $c1$), the
solver tends to drop other complex orders with less significant contribution
to meet these requirements.

If we consider the original objective function described in eq. (16), which
does not consider the production costs computed from the FT and VT values, the
minimum income conditions based on these values may raise issues.

On the other hand, if we neglect the contribution of hourly bids belonging to
complex orders, but we do consider the FT/VT-based costs in the objective as
in eq. (65), the bid acceptance constraints related to hourly bids can make
some dispatches impossible

One may raise the question if the inclusion of both the hourly bid-based
components and the FT/VT-based components in the objective function is
possible. Theoretically this can be done, however in this case the cost of
these supply bids will be considered twice in the objective, which will imply
that standard supply bids will be preferred compared to MIC bids during the
clearing.

In addition, let us note that irrespective of which formulation (eq. (4) or
eq. (65) ) of the TSW is used, it is possible that players provide false FT
and VT values to the ISO. As we have seen, the consequences of this depend on
the other bids present in the market and also on the clearing mechanism used,
but in any case, such decisions may create the potential of gaming. A possible
approach could be to fix these parameters during the registration of the users
in the market, and allow their modification only rarely (e.g. once or twice a
year). It is also possible that VT is taken into account as the function of
the actual fuel prices. This approach may prevent that the submitted FT and VT
values are adjusted according to actual market states to maximize the expected
income.

Let us furthermore note that the implicit assumption of perfect information
has been used through the paper. In realistic cases, the validity of this
assumption depends on the publicly available data of DAPXs. The general idea
of the paper may be used however also without perfect information. If an MIC
order submitted to a DAPX with low hourly bid price values is regularly
accepted (thus the contribution to the TSW is large), the bidder may try to
increase the submitted FT value in order to test, weather the order is able to
’push out’ other MIC bids from the dispatch and increase the resulting MCP.

##  5 Conclusions and future work

In this paper, we have shown how the formalism of minimum income condition
orders allows strategic bidding trough the manipulation of various bid
parameters and trough the interplay of multiple MIC orders. In addition, we
have also shown that various modifications of the objective function used in
the market clearing (TSW) only partially resolve this issue. As these orders
are widely used in various DAPXs (mainly because they make the bidding process
of generating units easier), and according to the current result they may open
possibilities for strategic bidding, further research of the discussed topic
is advised.

Additional studies are necessary to determine the practical implications of
the discussed theoretical results. The scale of these possible practical
implications depends on the typical number and parameters of MIC orders
submitted to various markets. Further studies considering real market data (as
in [14] in the case of block orders) can provide results about the practical
relevance of the results presented in this paper.

Furthermore, new approaches in the computational formulation of MIC orders and
market clearing algorithms may possibly alleviate undesired properties and
effects of MIC orders. In particular, innovative formulation of minimum income
condition orders, as described in [12], where the general class of so called
’MP bids’ covers the MIC orders as well, may be free of the disadvantages
discussed in this paper – this, however must be the subject of future studies.

## Acknowledgements

This work has been supported by the Funds PD 123900 and K 131545 of the
Hungarian National Research, Development and Innovation Office, and by the
János Bolyai Research Scholarship of the Hungarian Academy of Sciences.

## Bibliography

## References

  * [1] M. Oksanen, R. Karjalainen, S. Viljainen, D. Kuleshov, Electricity markets in Russia, the US, and Europe, in: 2009 6th International Conference on the European Energy Market, IEEE, 2009, pp. 1–7.
  * [2] F. P. Sioshansi, Competitive electricity markets: design, implementation, performance, Elsevier, 2011.
  * [3] K. Imran, I. Kockar, A technical comparison of wholesale electricity markets in north america and europe, Electric Power Systems Research 108 (2014) 59–67.
  * [4] H. Singh, A. Papalexopoulos, Competitive procurement of ancillary services by an independent system operator, IEEE Transactions on Power Systems 14 (2) (1999) 498–504.
  * [5] J. Pan, Y. Teklu, S. Rahman, K. Jun, Review of usage-based transmission cost allocation methods under open access, IEEE transactions on power systems 15 (4) (2000) 1218–1224.
  * [6] N. P. Padhy, Unit commitment-a bibliographical survey, IEEE Transactions on power systems 19 (2) (2004) 1196–1205.
  * [7] D. I. Chatzigiannis, G. A. Dourbois, P. N. Biskas, A. G. Bakirtzis, European day-ahead electricity market clearing model, Electric Power Systems Research 140 (2016) 225–239.
  * [8] P. N. Biskas, D. I. Chatzigiannis, A. G. Bakirtzis, European electricity market integration with mixed market designs-part i: Formulation, IEEE Transactions on Power Systems 29 (1) (2013) 458–465.
  * [9] P. N. Biskas, D. I. Chatzigiannis, A. G. Bakirtzis, European electricity market integration with mixed market designs-part ii: Solution algorithm and case studies, IEEE Transactions on Power Systems 29 (1) (2013) 466–475.
  * [10] L. Meeus, K. Verhaegen, R. Belmans, Block order restrictions in combinatorial electric energy auctions, European Journal of Operational Research 196 (3) (2009) 1202–1206.
  * [11] M. Madani, M. Van Vyve, A. Marien, M. Maenhoudt, P. Luickx, A. Tirez, Non-convexities in european day-ahead electricity markets: Belgium as a case study, in: 2016 13th International Conference on the European Energy Market (EEM), IEEE, 2016, pp. 1–5.
  * [12] M. Madani, M. Van Vyve, Revisiting minimum profit conditions in uniform price day-ahead electricity auctions, European Journal of Operational Research 266 (3) (2018) 1072–1085.
  * [13] M. Madani, Revisiting european day-ahead electricity market auctions: Mip models and algorithms, Ph.D. thesis, Université catholique de Louvain (2017).
  * [14] M. Madani, M. Van Vyve, Minimizing opportunity costs of paradoxically rejected block orders in european day-ahead electricity markets, in: 11th International Conference on the European Energy Market (EEM14), IEEE, 2014, pp. 1–6.
  * [15] J. C. Richstein, C. Lorenz, K. Neuhoff, An auction story: How simple bids struggle with uncertainty (2018).
  * [16] M. Madani, M. Van Vyve, Computationally efficient mip formulation and algorithms for european day-ahead electricity market auctions, European Journal of Operational Research 242 (2) (2015) 580–593.
  * [17] Á. Sleisz, D. Raisz, Complex supply orders with ramping limitations and shadow pricing on the all-european day-ahead electricity market, International Journal of Electrical Power & Energy Systems 83 (2016) 26–32.
  * [18] G. A. Dourbois, P. N. Biskas, European market coupling algorithm incorporating clearing conditions of block and complex orders, in: 2015 IEEE Eindhoven PowerTech, IEEE, 2015, pp. 1–6.
  * [19] M. Van Vyve, et al., Linear prices for non-convex electricity markets: models and algorithms, Tech. rep., CORE (2011).
  * [20] D. I. Chatzigiannis, P. N. Biskas, G. A. Dourbois, European-type electricity market clearing model incorporating pun orders, IEEE Transactions on Power Systems 32 (1) (2016) 261–273.
  * [21] J. Contreras, O. Candiles, J. I. De La Fuente, T. Gomez, Auction design in day-ahead electricity markets, IEEE Transactions on Power Systems 16 (1) (2001) 88–96.
  * [22] R. Garcia-Bertrand, A. J. Conejo, S. Gabriel, Electricity market near-equilibrium under locational marginal pricing and minimum profit conditions, European Journal of Operational Research 174 (1) (2006) 457 – 479\.
URL http://www.sciencedirect.com/science/article/pii/S0377221705003814

  * [23] L. H. Lam, V. Ilea, C. Bovo, European day-ahead electricity market coupling: Discussion, modeling, and case study, Electric Power Systems Research 155 (2018) 80–92.
  * [24] G. A. Dourbois, P. N. Biskas, A novel method for the clearing of a day-ahead electricity market with mixed pricing rules, in: 2017 IEEE Manchester PowerTech, IEEE, 2017, pp. 1–6.
  * [25] I. M. Operator, Daily and intraday electricity market operating rules, Tech. rep., Tech. Rep. July, OMEL, Madrid, Spain, available: http://www.omel.es/files/20140509_reglas_v11_ingles.pdf (2013).
  * [26] Power spot exchange NL, Tech. rep., available: http://www.apxgroup.com/trading-clearing/day-ahead-auction/ (2016).
  * [27] N. E. Koltsaklis, A. S. Dagoumas, Incorporating unit commitment aspects to the european electricity markets algorithm: An optimization model for the joint clearing of energy and reserve markets, Applied energy 231 (2018) 235–258.
  * [28] D. Poli, M. Marracci, Clearing procedures for day-ahead italian electricity market: are complex bids really required?, International Journey of Energy 5 (3) (2011).
  * [29] C. Ruiz, A. J. Conejo, S. A. Gabriel, Pricing non-convexities in an electricity pool, IEEE Transactions on Power Systems 27 (3) (2012) 1334–1342.
  * [30] H. A. Gil, A. L. Trigo-Garcia, J. R. Santos, Minimum income orders in the european price coupling of regions: Use or abuse?, The Electricity Journal 30 (7) (2017) 1–7.
  * [31] B. Polgári, P. Sőrés, D. Divényi, Á. Sleisz, D. Raisz, New offer structure for a co-optimized day-ahead electricity market, in: European Energy Market (EEM), 2015 12th International Conference on the, IEEE, 2015, pp. 1–5.
  * [32] Á. Sleisz, D. Divényi, B. Polgári, P. Sőrés, D. Raisz, Challenges in the formulation of complex orders on european power exchanges, in: European Energy Market (EEM), 2015 12th International Conference on the, IEEE, 2015, pp. 1–5.
  * [33] Á. Sleisz, D. Raisz, Efficient formulation of minimum income condition orders on the all-european power exchange, Periodica Polytechnica Electrical Engineering and Computer Science 59 (3) (2015) 132–137.
  * [34] Á. Sleisz, D. Divényi, D. Raisz, New formulation of power plants’ general complex orders on european electricity markets, Electric Power Systems Research 169 (2019) 229–240.
  * [35] Euphemia public description,
http://www.belpex.be/wp-content/uploads/euphemia-public-description-
nov-2013.pdf, Tech. rep. (2015).
URL http://www.belpex.be/wp-content/uploads/Euphemia-public-description-
Nov-2013.pdf

  * [36] L. Hurwicz, The design of mechanisms for resource allocation, The American Economic Review 63 (2) (1973) 1–30.
  * [37] T. Groves, J. Ledyard, Incentive compatibility since 1972, Information, incentives, and economic mechanisms: Essays in honor of Leonid Hurwicz (1987) 48–111.
  * [38] P. Klemperer, Auctions: theory and practice, Princeton University Press, 2004.
  * [39] A. E. Roth, Incentive compatibility in a market with indivisible goods, Economics letters 9 (2) (1982) 127–132.
  * [40] S. De Vries, R. V. Vohra, Combinatorial auctions: A survey, INFORMS Journal on computing 15 (3) (2003) 284–309.
  * [41] P. Cramton, Y. Shoham, R. Steinberg, An overview of combinatorial auctions, ACM SIGecom Exchanges 7 (1) (2007) 3–14.
  * [42] N. Nisan, T. Roughgarden, E. Tardos, V. V. Vazirani, Algorithmic Game Theory, Cambridge University Press, 2007.
  * [43] J. Moylan, Energy firms face competition inquiry, Tech. rep. (2014).
URL https://www.bbc.com/news/business-26734203

  * [44] A. K. David, F. Wen, Market power in electricity supply, IEEE Transactions on energy conversion 16 (4) (2001) 352–360.
  * [45] D. Esmaeili Aliabadi, Analysis of collusion and competition in electricity markets using an agent-based approach, Ph.D. thesis (2016).
  * [46] L. M. Ausubel, P. Cramton, Demand reduction and inefficiency in multi-unit auctions (2002).
  * [47] D. E. Aliabadi, M. Kaya, G. Şahin, Determining collusion opportunities in deregulated electricity markets, Electric Power Systems Research 141 (2016) 432–441.
  * [48] S. F. Tierney, T. Schatzki, R. Mukerji, Uniform-pricing versus pay-as-bid in wholesale electricity markets: does it make a difference?, New York ISO (2008).
  * [49] G. Xiong, S. Okuma, H. Fujita, Multi-agent based experiments on uniform price and pay-as-bid electricity auction markets, in: 2004 IEEE International Conference on Electric Utility Deregulation, Restructuring and Power Technologies. Proceedings, Vol. 1, IEEE, 2004, pp. 72–76.
  * [50] A. G. Bakirtzis, A. C. Tellidou, Agent-based simulation of power markets under uniform and pay-as-bid pricing rules using reinforcement learning, in: 2006 IEEE PES Power Systems Conference and Exposition, IEEE, 2006, pp. 1168–1173.
  * [51] J. Bower, D. Bunn, Experimental analysis of the efficiency of uniform-price versus discriminatory auctions in the england and wales electricity market, Journal of economic dynamics and control 25 (3-4) (2001) 561–592.
  * [52] Z. Liu, J. Yan, Y. Shi, K. Zhu, G. Pu, Multi-agent based experimental analysis on bidding mechanism in electricity auction markets, International Journal of Electrical Power & Energy Systems 43 (1) (2012) 696–702.
  * [53] D. E. Aliabadi, M. Kaya, G. Şahin, An agent-based simulation of power generation company behavior in electricity markets under different market-clearing mechanisms, Energy Policy 100 (2017) 191–205.
  * [54] S. A. Gabriel, A. J. Conejo, C. Ruiz, S. Siddiqui, Solving discretely constrained, mixed linear complementarity problems with applications in energy, Computers & Operations Research 40 (5) (2013) 1339–1350.


# Information Extraction from Visually Rich Documents with Font Style
Embeddings

Ismail Oussaid  BNP Paribas
<EMAIL_ADDRESS>William Vanhuffel  BNP Paribas
<EMAIL_ADDRESS>
Pirashanth Ratnamogan  BNP Paribas
<EMAIL_ADDRESS>Mhamed Hajaiej  BNP Paribas
<EMAIL_ADDRESS>Alexis Mathey  BNP Paribas
<EMAIL_ADDRESS>Thomas Gilles  BNP Paribas
<EMAIL_ADDRESS>
###### Abstract

Information extraction (IE) from documents is an intensive area of research
with a large set of industrial applications. Current state-of-the-art methods
focus on scanned documents with approaches combining computer vision, natural
language processing and layout representation. We propose to challenge the
usage of computer vision in the case where both token style and visual
representation are available (i.e native PDF documents). Our experiments on
three real-world complex datasets demonstrate that using token style
attributes based embedding instead of a raw visual embedding in LayoutLM model
is beneficial. Depending on the dataset, such an embedding yields an
improvement of 0.18% to 2.29% in weighted F1-score with a decrease of 30.7% in
the final number of trainable parameters of the model, leading to an
improvement in both efficiency and effectiveness.

##  I Introduction

Extracting specific information from complex documents is paramount in many
business activities. It is a key but complex process because of the wide range
of business documents and templates: contracts, invoices, reports or news
articles for instance. Despite the recent advances in the field, this task
still remains mostly manual and time consuming in various business processes.

Information Extraction is the associated task that aims to automatically
extract specific textual information from complex documents. Literature in the
domain mainly focuses on two tasks: information extraction from plain text [2,
3] or information extraction from scanned documents [4, 5, 6]. While
promising, none are completely suited to the growing task of extracting
information from machine-readable documents. Indeed, information extraction
from plain text is not adapted to document structure underlying complexity
that requires not only text related information but also the original layout
information [1] (table structure, paragraphs, two dimensional position on the
page…). On the opposite, the complexity of scanned document processing
involves the usage of prior text extraction tools [7] and doesn’t allow
efficient word-level annotation [9] (position of the information to extract is
approximated). However, information extraction from native PDF documents
represents a large and growing number of real-world use cases. This specific
task combines the inherent complexity of document processing with the fact
that documents, in this case, can be efficiently parsed without approximation
and with all the layout attributes (especially text style and position).

In this paper, we introduce a new way of building a visual token
representation for the information extraction task on machine-readable
documents (_i.e_ native PDFs). Indeed, visual information encoding is a key
component of most state-of-the-art methods [1, 8, 9]. Previous approaches rely
on encoding the token image representation from the original PDF using
computer vision methods like Faster-RCNN [10] or U-Net [11]. Although
successful, the addition of a computer-vision based approach involves an
overall complexity increase of the pipeline, thus increasing the number of
parameters and reducing the scalability.

In the context of native PDFs, using dedicated PDF parsing tools, one can
directly extract an interpreted version of token visual attributes in what we
can call token style: font, font size, color, _etc_. Our approach is based on
replacing the original image embedding with embeddings that rely on these
style attributes that integrate by nature the meaningful information that can
be parsed from the token image.

We experiment a token style variant of the state-of-the-art LayoutLM model on
three real-world datasets of native PDF documents (invoices, trade
confirmations and fee schedules). We show that it outperforms the image based
LayoutLM variant detailed in their paper [1].

Our main contribution can be separated in three parts:

  * •

We propose a new intuitive style attributes based embedding in replacement of
the image based embedding which outperforms the original approach;

  * •

To the best of our knowledge, we provide the first information extraction
benchmark of precisely annotated native PDF documents. It is based on three
real-world use cases : invoices, trade confirmations, and fee schedules;

  * •

We compare the aggregation of style attributes based embedding by addition or
by concatenation.

##  II Background

###  II-A PDF raw content extraction

The PDF format is broadly adopted and used for exchanging digital documents.
In the context of information extraction, the raw content that can be
extracted without approximation varies depending on the way the PDF was
created. We can distinguish two type of PDFs: the Scanned PDFs and the Native
PDFs.

####  II-A1 Scanned PDF Documents

Scanned PDF Documents consist on images only. The PDF was generated using a
scanner or camera and it lost its digital formatting in the process. In the
task of information extraction, one need to get textual information from the
document. The conversion from a raw set of textual document images to textual
content is called Optical Character Recognition (OCR) [7]. One of the most
popular methods is Tesseract OCR Engine [26]. An OCR Engine converts the set
of original images into a textual document $\mathcal{D}_{s}$ where :

$\displaystyle\mathcal{D}_{s}={}$ $\displaystyle(e_{s}^{i})_{i=1...p}\
\text{with}\ e_{s}^{i}=(t^{i},g^{i})$ (1)

$p$ is the number of tokens in the document
$e^{i}_{s}$ is the $i$-th token in $\mathcal{D}_{s}$
$t^{i}$ is the textual content the $i$-th token
$g^{i}$ is the coordinates, width and height of the $i$-th token in the
document

####  II-A2 Native PDF Documents

Native PDF Documents are the direct output of an authoring software. It
contains all its original formatting like the text, its associated style
attributes or the graphics. Hence, native PDFs can be efficiently parsed into
a machine-readable document using tools like
PDFMiner111https://github.com/pdfminer/pdfminer.six or Apache
PDFBox222https://github.com/apache/pdfbox. For example, a native PDF document
can be converted into a document $\mathcal{D}_{n}$ where

$\displaystyle\mathcal{D}_{n}=(e_{n}^{i})_{i=1...p}\ \text{with}$ (2)
$\displaystyle
e_{n}^{i}=(t^{i},g^{i},b^{i},f^{i},f_{size}^{i},t_{tab}^{i},c^{i})$

$p,e_{n}^{i},t^{i},g^{i}$ share the denomination from II-A1
$b^{i}$ is a boolean assessing if the $i$-th token is bold
$f^{i}$ is the font type the $i$-th token
$f_{size}^{i}$ is the font size of the $i$-th token
$t_{tab}^{i}$ is a boolean assessing if the $i$-th token is in a table or not,
it can be obtained by parsing the PDF graphics on simple cases or using more
advanced computer vision based solution for the extraction [27][28]
$c^{i}$ is the color of the $i$-th token

###  II-B Information Extraction

Information Extraction is the natural language processing task that aims at
extracting structured information from unstructured data. In practice, it is
often turned into a token classification problem. Given a set of tokens
$\mathcal{D}=(e^{i})_{i=1...p}$, the goal is to classify each token $e^{i}$
into a label $l^{i}$ from a set of labels $\mathcal{L}=(l^{i})_{i=1...p}$.

In order to correctly extract entities made of more than one token, IOB
(Inside-Outside-Beginning) tagging [25] is used. The words prefixed with I-
(for ”Inside”) are inside a chunk associated to an entity. The words not
corresponding to any entity are labelled as O (for ”Other”). The first word
associated to an entity is prefixed with B- (for ”Beginning”). This allows us
to correctly identify and separate entities inside a text even if they are
next to each other.

In the literature, we can distinguish two main applications. Information
extraction from plain text that aims at extracting entities from raw textual
sentences [2, 3] and information extraction from scanned documents [4, 5, 6].
Depending on the task, the information to efficiently model a problem vary.
Indeed, layout information is critical for document understanding models as
the unique one-dimensional sequential representation used in the prior
approaches loses key information [13].

##  III Related Work

###  III-A Information extraction datasets

Although the literature is rich and a large number of open source datasets
have been released, none of them focus on one of the main challenges of
extracting information from native PDF documents annotated at the word level.
Indeed, as described above, the existing literature focuses on extraction from
plain text documents [2, 3] and extraction from scanned documents [4, 5, 6].
However, scanned documents processing is an extremely specific domain where
raw input is a single image and extraction from plain text doesn’t contain the
inherent complexity of document processing (tables, title, structure, etc.).
In our case we propose to focus the research on native PDF Documents with
word-level annotation allowing to purely evaluate the information extraction
model on the token classification problem. To the best of our knowledge the
only complex dataset based on native PDFs is Kleister datasets [12]. However,
entities in this dataset are labeled without their positions. Therefore, we
have to use imprecise heuristics to find the exact positions of these entities
inside the document. Moreover, Kleister documents are not as visually rich as
other datasets (long contract documents).

###  III-B Visual token representation

Understanding the layout of documents is an obvious step in the task of
understanding documents which has been tackled using dedicated methods.
Document layout modeling methods were historically numerous. They were mainly
graph-based [13] or based on computer-vision methods enriched with text
information [14, 15]. Recently, transformers [16] and pre-trained language
models are starting to be widely used for Natural Language Understanding (NLU)
with BERT [17] and its extensions. These models are very powerful to
semantically learn a language and can be used for many downstream tasks.
However they are built to deal with plain text.

The first adaptation for document understanding is LayoutLM [1] that is pre-
trained on millions of documents with the additional token coordinates and
image representation (see Section IV-A). More recently, a second version
LayoutLMv2 [8] enriched the first version by including image information in
the pre-training framework and the TILT neural network [9] used a new encoder-
decoder architecture that uses text, positions, and image information.
LayoutLMv2 and the TILT architectures have slightly higher performances than
LayoutLM in some scanned document benchmarks. However, those methods embed
complex image embedding during the pre-training phase (while LayoutLM adds it
during the fine-tuning) and hence its associated complexity cannot be soften.
LayoutLM provides a state-of-the-art baseline with a large architecture
overlapping all the other methods. Hence, we will use LayoutLM [1] enriched
with various image embeddings as our main baseline. This, will allow to
underline the relevance of replacing image based embeddings by style based
embeddings when available without having to reproduce the proprietary pre-
training of other methods.

###  III-C Style attributes usage

Using style attributes in document processing is not a common practice. Indeed
as explained, the information is not always available depending on the file
format of the document and dominant research is focusing on using token’s
image representation. On HTML documents, [18] used handcrafted features based
on font size and color in order to improve the performance on information
extraction from HTML documents. These results have been extended to other less
complex tasks like heading detection as shown by [19] work. Here,
incorporating style based manually crafted features allows to improve standard
classifiers. To the best of our knowledge, our work is the first preliminary
work integrating style attributes embedding representation in state-of-the-art
pre-trained language model based models for the information extraction task.

##  IV Information extraction with visual token representation

Our approach is largely based on LayoutLM, so it is important to understand
this model first. We will discuss about it in the next section. The authors
also proposed to add visual embeddings thanks to a computer vision network.
This approach is promising but adds a lot of trainable parameters and does not
greatly enhance general performances. We will discuss about this idea in
section IV-B. Our work is an alternative to the latter, which offers
significant improvements while maintaining a reasonable model size.

###  IV-A LayoutLM

LayoutLM [1] architecture is like a BERT Transformer with a slightly different
positional embedding. The authors proposed to change it by adding (element-
wise sum) a 2D-embeddings on top of the usual 1D-positional embedding. In
fact, knowing all tokens relative position is a key information for
information extraction for documents. In short, the positional embedding
$\bm{\mathrm{P}}^{i}_{layoutlm}$ of the $i$-th token in a document
$\mathcal{D}$ is given by :

$\displaystyle\bm{\mathrm{P}}^{i}_{layoutlm}=\bm{\mathrm{P}}^{i}+\bm{\mathrm{G}}^{i}$
(3)
$\displaystyle\bm{\mathrm{G}}^{i}=\bm{\mathrm{P}}^{i}_{x_{1}}+\bm{\mathrm{P}}^{i}_{x_{2}}+\bm{\mathrm{P}}^{i}_{y_{1}}+\bm{\mathrm{P}}^{i}_{y_{2}}+\bm{\mathrm{P}}^{i}_{w}+\bm{\mathrm{P}}^{i}_{h}$

$\bm{\mathrm{P}}^{i}$ : 1D positional embedding introduced in BERT
$\bm{\mathrm{G}}^{i}$ : 2D positional embedding introduced in LayoutLM
$(\bm{\mathrm{P}}^{i}_{j})_{j\in[x_{1},x_{2},y_{1},y_{2}]}$ : embedding of the
bounding box coordinates introduced in section II-A1
$\bm{\mathrm{P}}^{i}_{w}$ : embedding of the bounding box width
$\bm{\mathrm{P}}^{i}_{h}$ : embedding of the bounding box height

This allows the transformer to use both 1D and 2D position information. For
the training phase, they initialized the network with BERT weights and random
weights for the 2D embeddings. The model is pre-trained on 2 objectives : Mask
Language Modeling (MLM) where some tokens are masked and the model has to
predict them; and Multi-label Document Classification (MDC). Pre-training
datasets were large enough (11 million scanned images) to build an efficient
pre-trained language model adapted to document understanding. Finally,
LayoutLM serves as a multi-purpose network and can be used for many downstream
tasks, especially information extraction. This approach greatly improved the
state-of-the-art on many document understanding tasks such as information
extraction for scanned receipts [4], and Document classification [22]. Pre-
trained model and code were made available by
authors.333https://github.com/microsoft/unilm/tree/master/layoutlm

###  IV-B LayoutLM with image embedding

The classical LayoutLM model might struggle to understand the full layout of a
document as it doesn’t depend upon visual information, but only geometric
positions. The authors originally propose to add an image embedding following
the process illustrated in Figure 1

They suggest to feed the image $\mathcal{I}$ of a document $\mathcal{D}$ to a
Faster R-CNN [10] that has a backbone $\mathscr{B}$ in order to build a
feature map for the document page. The visual feature of a given token should
then be extracted from this feature map.

Figure 1: The process of an image embedding

Traditional Regional Proposal Network (RPN) of the Faster R-CNN is not needed
as token bounding boxes are given either by an OCR system or by the PDF
parsing tool.

Given the document feature map, and token coordinates, the so-called RoIAlign
[21] allows to extract a fixed-size visual representation associated to the
token (whatever the token size). This visual embedding can then be projected
using linear layers in order to match BERT output dimension.

The overall process can be summarized with the following equation:

$\bm{\mathrm{v}}_{i}=\phi(\bm{\mathrm{RoIAlign}}(\bm{\mathrm{f}}^{\mathcal{I}},g^{i}))$
(4)

$\bm{\mathrm{v}}_{i}$ : image embedding of the $i$-th token
$\phi$ : linear layer
$\bm{\mathrm{f}}^{\mathcal{I}}$ : feature map of $\mathcal{I}$
$g^{i}$ : bounding box of the $i$-th token

Token image embedding encompass all the token visual information. In the
original paper [1], the authors propose to do an element-wise sum between
textual embedding and the visual embedding at the end of the network.

This output token embedding will be fed to a classification layer that will be
trained to classify the token in the given categories for the information
extraction task. During fine-tuning, all the weights from both LayoutLM and
Faster R-CNN are trained.

###  IV-C Token Style based Embeddings

Intuitively, image embedding purpose is to capture visual attributes from a
token. The current approach involves a tremendous number of trainable
parameters and a complexification of models using geometrical and textual
information. However, in the case of native PDFs, visual attributes can be
directly extracted from the document in what is called styled attributes as
explained in II-A2. As an alternative to image embedding, we propose to embed
token style attributes instead, as it adds less weights and increases
interpretability.

During fine-tuning, we suggest to train a combination of LayoutLM (Section
IV-A) with token style embeddings. As LayoutLM was pre-trained, the additional
embedding will be aggregated to LayoutLM original output in order to not
corrupt the original pre-training. As detailed previously, the following
visual information is available in most PDF parsing tool at token level:

  * •

_bold_ : whether the token written in bold,

  * •

_inTable_ : whether a token belongs to a Table in the document,

  * •

_font_ : font type of the token,

  * •

_fontSize_ : size of the token,

  * •

_color_ : triplet corresponding to its coordinates in the RGB system.

Figure 2: Processes of LayoutLM + style based embeddings (left) and LayoutLM +
image embeddings (right)

Depending on the PDF parser, one could choose what suits best their needs. For
example, one can add the style features that assess if a token is in italic or
is in a bullet point. Indeed, native PDF format encompass a lot of information
that, we think, must be used in the document understanding models.

Figure 2 shows that the PDF Parser provides the positions and tokens to
LayoutLM and extracts meta information that can be used to generate a token
style embeddings. Each style feature is linked to an embedding table whose
vectors are of size $d_{m}$. $d_{m}$ is chosen the same across all style
features, but will vary depending on how the fusion with LayoutLM embeddings
is done. If we define $d=d_{m}$, the M embedding tables are of shape
${V_{m}}\times d$ where ${V_{m}}$ is the vocabulary size of the style feature
$m$. In the next sections, we will study this number of parameters for two
different aggregation methods : element-wise sum or concatenation.

####  IV-C1 Aggregation by concatenation

Concatenating various token embeddings in order to obtain a large and more
complete representation of a token is the most traditional way of combining
information. In this specific case, we concatenate the representation vectors
for M meta features.

Concatenating representation involves that the immediate next layer size that
projects the embedding into the set of classification labels will be
increased. Concatenating allows to be free to chose embedding dimension. For
instance, embedding boolean value like _bold_ should not require a large
dimension.

####  IV-C2 Aggregation by element-wise sum

Element-wise combination is known to be an efficient way of combining
embeddings. Theoretically, it allows the model to learn which embedding
feature to prioritize depending on the instance with no prior on which
(because all the elements have the same size).

The dimension of the style features, in this case, is determined by the output
dimension of LayoutLM.

##  V Experiments

To compare all these methods, we will focus on a key Information Extraction
task on three real-world datasets of trade confirmations, invoices, and fee
schedules (Section V-A) which have great complexity. We will compare standard
LayoutLM, with LayoutLM model enriched with image embedding, and our proposed
method LayoutLM enriched with style based embeddings.
In addition, we have also enriched our experiments with tests on two public
datasets of scanned documents SROIE [4] and FUNSD [5] where only the
integration of images can apply as ”style” embeddings are not available.
The experimental protocol is described in detail in Section V-B.

###  V-A Datasets

####  V-A1 Real-world datasets

The real-world datasets444More details in Appendix are composed of native PDF
documents written in multiple languages and containing tables, titles and
different font attributes.

They are extremely diverse and commonly shared in the banking business:

  * •

Trade Confirmations: 209 one-page PDFs in English with very few original
templates (4 font types, 11 font sizes only for instance)

  * •

Invoices: 626 one/two-page PDFs written in multiple languages, mostly English
and Portuguese, with around 30 different templates. It is diversified (414
font types, 529 font sizes).

  * •

FeeSchedule: 273 long PDFs of 1 to 129 English-written pages, with extremely
diversified sources (124 font types, 3846 font sizes)

They are manually annotated by business experts at word-level, meaning that we
know exactly which tokens participate to the entity.

####  V-A2 Public datasets

The two public datasets are the most common in the information extraction
task. They are based on scanned documents and have been labeled at document
level, meaning that we do not know the exact position of the entity in the
full document.

  * •

SROIE: 973 scanned receipts in English which were part of ICDAR 2019
competition

  * •

FUNSD: 199 scanned and noisy forms in English

###  V-B Experimental protocol

To limit the model size, we chose to group style attributes by hand crafted
clusters. For example, color embeddings will be grouped into ”Black” or ”Not
Black”, font weights are grouped into into 3 clusters ($\left[0,1.2\right[$,
$\left[1.2,2.0\right]$, and $\left]2.0+\infty\right[$). Of course, this
processing step is to be adapted to the distribution of the features.

For the experiments, we used PDFBox in order to parse native PDF documents and
extract relevant assets. We used our own implementation of pdftable [28]
combined with the extract graphics assets in order to detect tables. Our
LayoutLM model is pre-trained and based on the implementation provided in the
transformers library [23] while the computer vision part is based on
torchvision [24].

We cross-validated all the models using 5 folds and a batch size of 2
documents. The trainings were made on one NVIDIA Tesla V100 16GB GPU with a
constant learning rate: $l_{r}=2\times 10^{-5}$ over 20 epochs per iteration
of the cross validation. In fact, extending the number of epochs showed no
significant improvement. We train with a multi-class cross entropy loss and
with Adam optimizer. During the training, we randomly change 10% of the tokens
for improved generalization. We also randomly shift and resize all the
bounding boxes to reduce over-fitting during the fine-tuning. In each case,
the best model for each iteration of the cross-validation was selected using
the validation set.

We used pre-trained LayoutLM base model in order to assess the style embedding
relevance. Indeed, one of the main purpose of the proposed work is to limit
the number of parameters and LayoutLM large model doesn’t outperform the base
model by a significant margin.

The main criteria to assess our models is the entity-level weighted average F1
score. F1 scores per model on each dataset (Table II) is provided for analysis
purpose.

Using a grid search over validation set to determine the optimal style
embedding dimension, we selected $d=64$ for all the styles when aggregating
embeddings using concatenation. Also, when dealing with the aggregation of
LayoutLM with style embeddings

|  | 5-fold weighted average F1 (%)
---|---|---
Model | Parameters | Trade Confirmations | Invoices | FeeSchedule | SROIE | FUNSD
LayoutLM $+$ ResNet 152 | 163.74M | 96.81 $\pm$ 2.22 | 66.29 $\pm$ 2.76 | 75.76 $\pm$ 2.54 | 95.8 $\pm$ 1.26 | 78.42 $\pm$ 2.96
LayoutLM-Style Sum | 113.50M | 96.76 $\pm$ 0.71 | 67.60 $\pm$ 2.23 | 76.14 $\pm$ 2.22 |  $-$555Style attribute based approach cannot be used on scanned documents | $-^{5}$
LayoutLM-Style Concatenation | 113.49M |  97.09 $\pm$ 0.06 |  68.58 $\pm$ 1.27 |  76.64 $\pm$ 0.01 | $-^{5}$ | $-^{5}$

Table I:  Score & Number of parameters for LayoutLM, with image embedding, and
Style-LayoutLM models

(Style LayoutLM), we use the five features: _bold_ , _font_ , _fontSize_ ,
_inTable_ , and _color_ as Style LayoutLM can learn the important style
attributes.

To select the backbone used to generate the image embedding, we use a grid
search over the set of torchvision available
backbones666https://pytorch.org/vision/stable/models.html. After multiple
experiments, the model studied in this article is a pre-trained ResNet 152.

In order to perform the IOB tagging task, the token embedding output obtained
at the end of the pipeline is fed into a dense layer with a dropout rate of
0.3 and softmax as an activation function to predict token classification.

Models are usually limited in terms of sequence length, which is an issue for
long documents. For FeeSchedule dataset, we split each document into
overlapping shorter documents (called chunks), to aggregate the results at the
end. After multiple experiments, we have chosen chunks to be 512 tokens long
with an overlap of 100 tokens.

##  VI Results

###  VI-A Quantitative results

In Table II, we compare the efficiency and the overall performance of the
baseline with the models with additional embeddings777both sum and
concatenation style embeddings.

The image embeddings models have 44.3% more parameters than LayoutLM. They
don’t necessarily contribute to enhance the original model, even when the
backbone is ResNet 152. Indeed, because of the large volume of parameters,
fine-tuning with image embeddings results highly depends on the seed and the
fold. It reduces the positive input of LayoutLM pre-training.

The style models increase the number of trainable parameters by 0.01% as the
additional embeddings tables with only thousands of parameters at most. The
method allows to integrate visual embedding at a low cost. Even with such a
small parameters increase, we could improve the performance in all the
datasets for the concatenation fusion. Therefore, style embeddings prove to be
a good trade-off between performance and efficiency.

Regarding the comparison between the models with additional embeddings, the
concatenation fusion model happens to be very efficient and consistent in
enhancing the overall performance with 30.7% less parameters than image
embeddings model. Also, we get to know which features matter for our task.
Independently from the diversity, complexity and length of documents, this
aggregation of style based embeddings is the best one as it outperforms
LayoutLM in the three datasets in average. We also computed a paired t-test on
our 5-fold cross validation in our, the associated p-value was 6.89%. These
results show that the approach based on style embedding performs at least as
well as the image-based approach with a lower number of parameters, even if
the statistical significance of the improvement at the 5% level is not
reached.

However, image-based embeddings takes advantage on public scanned datasets
where the fact that style information is not available makes the approach with
styles unusable.

###  VI-B Qualitative analysis

In the three datasets, there is no significant visual difference between
entities of the different classes but the style embedding models happen to
improve the detection of some classes888Scores per class for all datasets
available in Appendix. Regarding the variety of documents, it is difficult for
a human to define which attributes will contribute the most in the final
model. Random permutations, and training with various combinations of features
allows us to define that for the Trade Confirmations dataset the attributes
_bold_ and _inTable_ are the most meaningful while for FeeSchedule and
Invoices respectively _fontSize_ & _inTable_ , and _inTable_ & _color_ are the
most importance.

Indeed, looking at the datasets, we can fully understand that:

  * •

In the Trade confirmations dataset, entities are often introduced by a word in
bold. And many information are presented in a table format,

  * •

In Fee Schedules dataset, names of clients are often written with larger fonts
and some figures (Rates and Margins) are often presented in tables,

  * •

In Invoices datasets, multiple significant figures are described in tables,
and some total amount are often in color.

##  VII Conclusion

In this paper, we demonstrate the relevance of having dedicated approaches for
native PDF documents where token style attributes can be extracted. We confirm
the intuitive result that having the style attributes instead of the raw image
in order to provide visual information to the model we were able to obtain
better performances in the information extraction task while reducing the
number of parameters. While benchmarked against state-of-the-art LayoutLM we
think that this work can be applied to other approaches and could be extended
by using font style embeddings during the pre-training process.

## References

  * [1] Yiheng Xu and Minghao Li and Lei Cui and Shaohan Huang and Furu Wei and Ming Zhou, “Layout LM: Pre-training of text and layout for document image understanding” KDD ’20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
  * [2] Erik F. Tjong Kim Sang and Fien De Meulder, Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition, Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003, 2003.
  * [3] Weischedel, R and Palmer, M and Marcus, M and Hovy, E and Pradhan, S and Ramshaw, L and Xue, N and Taylor, A and Kaufman, J and Franchini, M and others, “OntoNotes Release 5.0 LDC2013T19. Linguistic Data Consortium, Philadelphia, PA (2013)” 2013.
  * [4] Zheng Huang and Kai Chen and Jianhua He and Xiang Bai and Dimosthenis Karatzas and Shjian Lu and C.V. Jawahar, “Icdar2019 competition on scanned receipt ocr and information extraction” 2019 International Conference on Document Analysis and Recognition (ICDAR), p. 1516-1520, 2019.
  * [5] Jaume, Guillaume and Ekenel, Hazim Kemal and Thiran, Jean-Philippe, “Funsd: A dataset for form understanding in noisy scanned documents” 2019 International Conference on Document Analysis and Recognition Workshops (ICDARW), vol. 2, p. 1-6, 2019.
  * [6] Park, Seunghyun and Shin, Seung and Lee, Bado and Lee, Junyeop and Surh, Jaeheung and Seo, Minjoon and Lee, Hwalsuk, “CORD: A Consolidated Receipt Dataset for Post-OCR Parsing” Workshop on Document Intelligence at NeurIPS 2019, 2019.
  * [7] Mori, Shunji and Suen, Ching Y and Yamamoto, Kazuhiko, “Historical review of OCR research and development”, vol. 80, p.1029-1058, 1992.
  * [8] Xu, Yang and Xu, Yiheng and Lv, Tengchao and Cui, Lei and Wei, Furu and Wang, Guoxin and Lu, Yijuan and Florencio, Dinei and Zhang, Cha and Che, Wanxiang and others, ”LayoutLMv2: Multi-modal Pre-training for Visually-Rich Document Understanding”, 2020.
  * [9] Powalski, Rafał and Borchmann, Łukasz and Jurkiewicz, Dawid and Dwojak, Tomasz and Pietruszka, Michał and Pałka, Gabriela, ”Going Full-TILT Boogie on Document Understanding with Text-Image-Layout Transformer”, 2021.
  * [10] Shaoqing Ren and Kaiming He and Ross Girshick, and Jian Sun, ”Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks”, 2016.
  * [11] Olaf Ronneberger and Philipp Fischer and Thomas Brox, ”U-net: Convolutional networks for biomedical image segmentation”. International Conference on Medical image computing and computer-assisted intervention, p.234-241, 2015.
  * [12] Graliński, Filip and Stanisławek, Tomasz and Wróblewska, Anna and Lipiński, Dawid and Kaliska, Agnieszka and Rosalska, Paulina and Topolski, Bartosz and Biecek, Przemysław, ”Kleister: A novel task for information extraction involving long documents with complex layout”. International Conference on Medical image computing and computer-assisted intervention, 2020.
  * [13] Liu, Xiaojing and Gao, Feiyu and Zhang, Qiong and Zhao, Huasha, ”Graph Convolution for Multimodal Information Extraction from Visually Rich Documents”. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Industry Papers), p. 32-39, 2019.
  * [14] Katti, Anoop Raveendra and Reisswig, Christian and Guder, Cordula and Brarda, Sebastian and Bickel, Steffen and Höhne, Johannes and Faddoul, Jean Baptiste, ”Chargrid: Towards understanding 2d documents”, 2018.
  * [15] Mohamed Kerroumi and Othmane Sayem and Aymen Shabou, ”VisualWordGrid: Information Extraction From Scanned Documents Using A Multimodal Approach”, 2020.
  * [16] Ashish Vaswani and Noam Shazeer and Niki Parmar and Jakob Uszkoreit and Llion Jones and Aidan N. Gomez and Lukasz Kaiser and Illia Polosukhin, ”Attention Is All You Need”, 2017.
  * [17] Jacob Devlin and Ming-Wei Chang and Kenton Lee and Kristina Toutanova, ”BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), 2019.
  * [18] Emilia Apostolova and Noriko Tomuro, ”Combining Visual and Textual Features for Information Extraction from Online Flyers”. EMNLP, 2014.
  * [19] Budhiraja, Sahib Singh and Mago, Vijay, ”A supervised learning approach for heading detection”. Expert Systems, vol. 37. 2020.
  * [20] Emilia Apostolova and Noriko Tomuro, ”Combining Visual and Textual Features for Information Extraction from Online Flyers”. EMNLP, 2014.
  * [21] He, Kaiming and Gkioxari, Georgia and Dollár, Piotr and Girshick, Ross, ”Mask r-cnn”. Proceedings of the IEEE international conference on computer vision, p. 2961-2969, 2017.
  * [22] Adam W. Harley and Alex Ufkes and Konstantinos G. Derpanis, ”Evaluation of Deep Convolutional Nets for Document Image Classification and Retrieval”. International Conference on Document Analysis and Recognition (ICDAR), 2015.
  * [23] Thomas Wolf and Lysandre Debut and Victor Sanh and Julien Chaumond and Clement Delangue and Anthony Moi and Pierric Cistac and Tim Rault and Remi Louf and Morgan Funtowicz and Joe Davison and Sam Shleifer and Patrick von Platen and Clara Ma and Yacine Jernite and Julien Plu and Canwen Xu and Teven Le Scao and Sylvain Gugger and Mariama Drame and Quentin Lhoest and Alexander M. Rush, ”HuggingFace’s Transformers: State-of-the-art natural language processing”. arXiv preprint arXiv:1910.03771, 2019.
  * [24] Marcel, Sébastien and Rodriguez, Yann, ”Torchvision the machine-vision package of torch”. Proceedings of the 18th ACM international conference on Multimedia, p. 1485-1488, 2010.
  * [25] Lance Ramshaw and Mitch Marcus, ”Text Chunking using Transformation-Based Learning”. Third Workshop on Very Large Corpora, June 1995, pp. 82-94, 1995.
  * [26] Smith, Ray, ”An overview of the Tesseract OCR engine”. Ninth international conference on document analysis and recognition (ICDAR 2007), IEEE, vol. 2, p. 629-633, 2007.
  * [27] Prasad, D., Gadpal, A., Kapadni, K., Visave, M., & Sultanpure, K. (2020). CascadeTabNet: An approach for end to end table detection and structure recognition from image-based documents. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops (pp. 572-573).
  * [28] Yildiz, B., Kaiser, K., & Miksch, S. (2005, December). pdf2table: A method to extract table information from pdf files. In IICAI (Vol. 2005, pp. 1773-1785).

##  Appendix A Datasets

###  A-A Trade Confirmations

Trade confirmations are financial documents that summarise all the details of
one of multiple financial trades. It is usually well structured with tables
clear structure. Our dataset consist of derivatives products with the
following business related labels:

  * •

BUYSELL : direction of the trade (buy or sell)

  * •

CALLPUT : is it a call or a put (the contract allows to buy or sell the
option)

  * •

CLEAR INFO : account number

  * •

CONTRACT : contract number

  * •

EXECUTIVE BROKER : broker associated to the trade

  * •

EXPIRY DATE : maturity of the trade

  * •

MARKET : market where the trade applies

  * •

TRADE PRICE : contract price

  * •

STRIKE VALUE: fixed price to buy or sell the underlying as defined in the
contract

  * •

TRADE DATE : date of the trade

  * •

TRADE STATUS : status of the trade

  * •

TRADE VOLUME : quantity to buy

BUYSELL and CALLPUT are easier to extract because the majority of datapoints
take their values in a finite set of words (buy, sell, call, put …). On the
contrary TRADE PRICE and TRADE VOLUME are more difficult to parse because they
are often displayed within multiple tables and require layout understanding in
order to be efficiently extracted.

###  A-B Invoices

Invoices are the classic document that shows what goods were purchased and at
what price. Our annotators labeled the following entities:

  * •

ACCOUNTNUMBER : account ID

  * •

ADDRESS : all the addresses in the document

  * •

COMPANYNAME : company name

  * •

DOCUMENTDATE : date of the document

  * •

GROSSWEIGHT : the weight of an item (optional)

  * •

IBAN : relates to the account paying the invoice

  * •

INVOICENUMBER : invoice ID

  * •

PERSONNAME : name of a person

  * •

TOTAL : total amount to be paid

As described above, the dataset difficulty comes from the wide range of
templates within the documents.
Moreover, some datapoints are particularly hard to extract: ADDRESS are
difficult to parse because it is made up from 5 to 10 words written in
multiple lines, COMPANYNAME is made up of non common words and often comes
without easy to parse context, finally GROSSWEIGHT is often displayed in
tables without border that requires the model to gain a complex layout
understanding.

###  A-C FeeSchedule

FeeSchedule is dataset of financial documents that detail a pricing proposal
for a specific client. The most important information are the interest rates
applied to the client. They are composed of two parts: a base rate and a
margin.
The labeled entities are :

  * •

APPLICATION DATE : date of the pricing

  * •

BRANCH NAME : the branch of the bank responsible for the proposal

  * •

CLIENT NAME : name of the concerned client

  * •

MARGIN : base rate of the Fees

  * •

RATE : the margin associated to the rate

The dataset consist of documents where the fees are presented in tables of
different structures, but also inside the paragraphs in some cases.
All FeeSchedule documents are passed through the OCR before the processing
which resulted in errors in the retrieved text especially for the data of the
cover page and the signature page.
This affects mainly the datapoints APPLICATION DATE, BRANCH NAME and CLIENT
NAME, which were often tagged with inconsistent values. Indeed, sometimes
information can be handwritten or can be presented in multiple parts of the
document which makes labelling consistently hard and in consequence impacts
the overall performances for those datapoints.

##  Appendix B Detailed performances

Label | Image Embeddings | Style Embeddings | Support
---|---|---|---
| R152 | Concatenation | Sum |
BUYSELL | 99.34 | 99.15 | 98.98 | 236
CALLPUT | 96.13 | 96.68 | 93.13 | 117
CLEAR INFO | 97.29 | 96.83 | 97.05 | 207
CONTRACT | 96.88 | 97.80 | 97.33 | 207
EXECUTIVE BROKER | 97.37 | 97.33 | 96.83 | 208
EXPIRY DATE | 97.20 | 96.80 | 97.84 | 229
MARKET | 98.31 | 98.58 | 98.30 | 207
TRADE PRICE | 88.32 | 89.93 | 90.83 | 237
STRIKE VALUE | 99.78 | 99.59 | 99.37 | 231
TRADE DATE | 100 | 99.52 | 99.52 | 207
TRADE STATUS | 100 | 100 | 99.68 | 161
TRADE VOLUME | 92.56 | 94.22 | 92.22 | 238

Table II:  Average 5-fold F1 score (%) per class for all models on Trade
Confirmations

Label | Image Embeddings | Style Embeddings | Support
---|---|---|---
| R152 | Concatenation | Sum |
ACCOUNTNUMBER | 73.78 | 75.53 | 75.96 | 463
ADDRESS | 57.26 | 61.46 | 59.46 | 2037
COMPANYNAME | 64.24 | 65.65 | 64.68 | 2164
DOCUMENTDATE | 77.89 | 76.67 | 78.86 | 555
GROSSWEIGHT | 45.47 | 49.85 | 43.93 | 244
IBAN | 86.60 | 90.76 | 86.43 | 258
INVOICENUMBER | 74.25 | 75.73 | 74.32 | 581
PERSONNAME | 74.35 | 75.80 | 76.28 | 1096
TOTAL | 65.84 | 69.59 | 70.40 | 538

Table III:  Average 5-fold F1 score (%) per class for all models on Invoices

Label | Image Embeddings | Style Embeddings | Support
---|---|---|---
| R152 | Concatenation | Sum |
APPLICATION DATE | 41.74 | 42.90 | 32.07 | 273
BRANCH NAME | 18.27 | 23.22 | 27.67 | 270
CLIENT NAME | 23.40 | 29.19 | 20.61 | 274
MARGIN | 81.32 | 81.44 | 81.44 | 3907
RATE | 78.71 | 79.67 | 79.46 | 5913

Table IV:  Average 5-fold F1 score (%) per class for all models on FeeSchedule