# Price of Fairness on Networked Auctions

Authors: Mariusz Kaleta
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We consider an auction design problem under network flow constraints. We focus on pricing mechanisms that provide fair solutions, where fairness is defined in absolute and relative terms. The absolute fairness is equivalent to “no individual losses” assumption. The relative fairness can be verbalized
as follows: no agent can be treated worse than any other in similar circumstances. Ensuring the fairness conditions makes only part of the social welfare available in the auction to be distributed on pure market rules. The rest of welfare must be distributed without market rules and constitutes the so-calledprice of fairness. We prove that there exists the minimum of price of fairness and that it is achieved when uniform unconstrained market price is used as the base price. The price of fairness takes into account costs of forced offers and compensations for lost profits. The final payments can be different than locational marginal pricing. That means that the widely applied locational marginal pricing mechanism does not in general minimize the price of fairness.


---

## Body

## 1. Introduction

Classical auction (through the whole paper by “auction” we mean closed double sealed exchange-like mechanism; in other words an “auction” is a set of trading rules for an exchange) mechanisms are based on the supply/demand curves intersection which sets accepted and rejected offers and determines the uniform market price. However, in many real-world infrastructure economies, a commodity flow is limited by the resources of some network system. This leads to a concept of the networked auctions [1]. Some examples come from electricity [2], gas [3, 4], water [5], telecommunication [6], and transport markets. Determination of auction winners not only must be based on economic grounds, but also must be aligned with network system resources, for example, transmission grid, water transmission network, telecommunication network, and road network resources.In [1] the network winner determination problem (NWDP), an extension of classical winner determination problem (WDP) with consideration of network resources, has been introduced. This model solves only the problem of social welfare maximization, but there is still the question of how social welfare should be distributed between the market participants. In classical auctions, the marginal pricing principle is usually applied, which provides the solution acknowledged to be fair. In case of networked auctions the fairness conditions can be disrupted and uniform market pricing cannot be used.To address fairness in the electricity markets, the locational marginal pricing (LMP) was introduced by Schweppe [7] and further developed by Hogan [8]. LMP sets the marginal prices at each node. Although this approach is widely recognized in a context of electricity markets, the LMP and similar marginal nodal pricing policies are also addressed for other markets [3, 5, 9]. The LMP has several flaws [10]. One of the main shortcomings is only partial distribution of social welfare between market participants. This means that there is some price that is paid to restore the fairness conditions.In this paper we introduce theprice of fairness (PoF) for networked auctions. We focus on multicommodity sealed-bids auctions. Our main theorem proves that the minimal PoF can be achieved if the unconstrained market price is used for settlements and some additional nodal components are paid at each node. This means that widely used locational marginal pricing approach does not minimize the PoF. Till now, there is very little literature devoted to fair networked auctions, and business is focused on LMP-like mechanisms. We think that our main result is to show that there is a wide interesting spectrum of fair auction mechanisms for networked systems. This spectrum should be further investigated including also aspects other than the PoF.The paper is organised as follows. A discussion of related works is provided in Section2. In Section 3, we introduce basic notions: the general model of networked auction with its components (a special case of winner determination problem and value mechanism) and the problem of finding the best value mechanism. The concept of fairness in the context of networked auction is introduced in Section 4. The main results of the paper are presented in Section 5. We define theprice of fairness and analyze it in the space of possible value mechanisms. We conclude and present some interesting future directions in Section 6.


## 2. Related Literature

The concept of fairness plays an important role in resource allocation problems [11–13]. Although fairness is a subjective notion, it implies equity and impartiality [14]. To achieve these conditions several ways of specifying the fairness are considered in the literature. Usually, some measure of inequality is to be minimized [15, 16]. The simplest measures are based on the absolute measurement of the spread of outcomes, for example, mean or maximum absolute difference, or measurement relative to the mean outcome, for example, mean absolute deviation or Gini coefficients [17, 18]. Unfortunately, direct minimization of typical inequality measures is in contradiction with optimization of individual outcomes [19]. One can use an aggregation function to solve the problem; however this function should satisfy several requirements [20]. Various solution concepts can be achieved when logarithmic function is used to obtain fair aggregation [20]. The concept of equitably efficient solution is another approach, which was formalized in [21].Unfortunately, all of these concepts of fairness and their underlying axiomatisation cannot be applied directly when the allocation is performed via auction mechanism. In this case, the fairness concept must take into consideration the prices of bids and thus different utility of bidders. Moreover, the incompleteness of information possessed by each bidder is also important.Auction has been widely considered as a mechanism of resource allocation in selfish, multiagents environments [22]. Although the theoretical literature on auctions is rich and multidimensional, fairness issues are relatively rare. In [23], two notions of fairness are introduced for combinatorial auctions: the basic fairness and the extended fairness. The basic fairness is related to conditions that must be satisfied to leave each agent with the feeling that he has a fair share. The extended fairness ensures envy-free allocation, which means that each agent is at least as happy with his share as he would be with share of any other agent.Murillo et al. [24] consider a recurrent auction model equipped with reservation price. In this setting, no selling offer below its reservation price can be winning. The incorporation of the reservation price forces the introduction of fairness considerations. The problem considered in [24] is a policy of setting the reservation prices to assure fairness condition understood as a similar probability of winning for every bidder.Wu et al. [25] consider fairness in the sealed-bid auctions rather more on procedural level than the market clearing rules. In order to mitigate the possibilities for collusion or cheating, they consider when and how the sealed bids should be opened.The concept of fairness for multicommodity auctions has been formalized by Toczyłowski in [26]. We follow this concept in our paper and we discuss the details in Section 4.The termprice of fairness has been introduced in [27]. In this work, the PoF has been analyzed in the context of general resource allocation problem. The authors define PoF as a relative system efficiency loss under fair conditions of the allocation. A characterization of the PoF for a broad spectrum of allocation problems is also provided in [27].There are also some studies, that refer to the PoF indirectly; They consider loss of efficiency due to fair conditions, mainly in allocation problems. In most works, the price of fairness or similar notion is defined as the performance loss incurred relative to utility, in making allocations under one of several possible fairness criteria formulations. In [28] some numerical computations for efficiency loss in several network configurations are presented under consideration of proportional and max-min fairness. Butler and Williams have proved that, for certain class of facility location problem, the price of fairness is zero [29]. Mo and Walrand have studied some family of parameterised objective of bandwidth allocations [30]. The max-min fairness and proportional fairness are special cases of this family.In [26] the fairness is defined by a set of requirements that must be satisfied in a fair solution of auction with uniform pricing. In our paper we follow this work and extend the analysis to the case of nodal pricing. Differentiation of buy and sell market prices is discussed in [31] with an application to electricity market. We derive the concept of separated prices for buying and selling from this work. However, we consider more general class of auction models.Theprice of anarchy is somehow similar concept to the PoF [32, 33]. It measures the system efficiency loss due to selfish behaviour of the agents. The PoA and PoF are only partially overlapped. Even if the agents would play truly, the PoF can be positive. However, the increase of PoA can be related to higher PoF that results from deficiency of considered auction mechanism.


## 3. Networked Auctions

We consider an organized market in which the sellers and buyers submit their offers. Then, the auction mechanism is run to find the winning offers and to set the value flows. The auction rules can be divided into two steps: the winners determination and the pricing.


### 3.1. Winners Determination Problem

Let us assume that an infrastructure network is modeled by graphG, where V is a set of vertices and E is a set of edges [4]. We assume that graph G is defined by an incidence matrix a
=
[
a
υ
e
]. To make the notation simpler, we also assume that G is a connected graph. Any solution to the winners determination problem is equivalent to some flows in the G and must satisfy Kirchoff’s laws. Each sell offer is related to a commodity that can be injected by a seller into the network at a given node. Similarly, any buy offer is related to a commodity that can be taken by a buyer from the network at a given node.Definition 1 (vertex-oriented network winner determination problem, VWDP).
The sellers submit the set of offersj
∈
J
=
{
1,2
,
…
,
J
}. An offer j is a tuple 〈
c
j
,
q
j
max
⁡
〉, where c
j
≥
0 is an offered unit price, and q
j
max
⁡
≥
0 is the maximal offered volume of a commodity. The buyers submit a set of offers m
∈
B
=
{
1,2
,
…
,
B
}. An offer m is a tuple 〈
e
m
,
d
m
max
⁡
〉, where e
m
≥
0 is an offered unit price, and d
m
max
⁡ is the maximal demanded volume of a commodity. Without loss of generality, to simplify the notation, we assume that each seller and each buyer are located in different node. Thus, the indexes of sellers and buyers can be also used for indexing the nodes. Let V
J
=
J
⊆
V be a set of seller nodes and let V
B
=
B
⊆
V be a set of buyer nodes. The vertex-oriented network winner determination problem (VWDP) is to find a set of winning offers and their volumes (
q
j
) and (
d
m
), 0
≤
q
j
≤
q
j
max
⁡ and 0
≤
d
m
≤
d
m
max
⁡, which is balanced (∑
j
∈
J
‍
q
j
=
∑
m
∈
B
‍
d
m) and social welfare-maximizing under the network flow constraints:
(1)
∑
e
∈
E
a
υ
e
f
e
=
{
q
υ
υ
∈
V
J
,
0
υ
∉
V
J
∪
V
B
,
-
d
m
υ
∈
V
B
,
∀
υ
∈
V
,
where f
e is the commodity flow over edge e and q
j and d
m are the accepted volumes of sell offer j and buy offer m, respectively. The VWDP maximizes the naturalutilitarian criterion—the sum of the surpluses of all individual players. Full formulation of VWDP is a simple extension of classical auction models [26] and can be expressed as linear programme.


### 3.2. Value Mechanism

The maximal total social welfareQ
=
∑
m
∈
M
‍
e
m
d
m
-
∑
j
∈
J
‍
c
j
q
j is achieved by solving VWDP. The buyers and sellers are selfish and tend to maximize their individual profits. Thus, we should notice that the submitted offers could be different than the market participants’ true valuations, and then Q would not be a true social welfare, but rather “declared” market surplus [31].The value mechanism is responsible for the surplus distribution. The distribution is usually expressed with the use of payment informationI, which may include market price, payments for individual offers, and other information. For instance, there are marginal prices at each node in I in case of LMP mechanism. The mechanism M is defined as the following mapping:
(2)
M
:
(
e
,
c
,
d
,
q
)
⟶
I
.A very generic approach to modeling the value mechanisms was formulated by Toczyłowski and calledparametric balancing model [26]. It introduces a virtual node denoted by 0 and connected to each other node. There are market price π
0 at virtual node and nodal prices π
υ at every node in V. If commodity is injected to the network at node k
∈
V and π
k is the nodal price, then π
k
0
=
π
0
-
π
k is the unit cost of commodity transport from node k to the virtual node 0. Similarly, if node l
∈
V is a consumption node with nodal price π
l then π
0
l
=
π
l
-
π
0 is the unit cost for commodity transport from the virtual node 0 to node l (see Figure 1).Figure 1
Model of pricing with nodal pricesπ
k, π
l, virtual node price π
0, and transmission prices π
k
0 and π
0
l.


### 3.3. Problem of Finding the Best Value Mechanism

Let us assume that there is a set ofL quality measures {
Q
1
(
M
)
,
…
,
Q
L
(
M
)
} of pricing mechanisms, where function Q
l
:
M
→
R is such that if Q
l
(
M
1
)
>
Q
l
(
M
2
), then mechanism M
1 is strictly preferred over the mechanism M
2 according to the measure l. Quality measures introduce the partial order to the space of mechanisms. Then, the problem of finding the best mechanism is defined as follows:
(3)
max
⁡
M
{
Q
1
(
M
)
,
…
,
Q
L
(
M
)
}
.For a given pricing mechanism it is interesting whether it is nondominated solution of multicriteria problem (3). In the next sections we will formulate a bit narrower space of possible mechanisms and we will analyze possible pricing mechanisms according to the PoF criterion.


## 3.1. Winners Determination Problem

Let us assume that an infrastructure network is modeled by graphG, where V is a set of vertices and E is a set of edges [4]. We assume that graph G is defined by an incidence matrix a
=
[
a
υ
e
]. To make the notation simpler, we also assume that G is a connected graph. Any solution to the winners determination problem is equivalent to some flows in the G and must satisfy Kirchoff’s laws. Each sell offer is related to a commodity that can be injected by a seller into the network at a given node. Similarly, any buy offer is related to a commodity that can be taken by a buyer from the network at a given node.Definition 1 (vertex-oriented network winner determination problem, VWDP).
The sellers submit the set of offersj
∈
J
=
{
1,2
,
…
,
J
}. An offer j is a tuple 〈
c
j
,
q
j
max
⁡
〉, where c
j
≥
0 is an offered unit price, and q
j
max
⁡
≥
0 is the maximal offered volume of a commodity. The buyers submit a set of offers m
∈
B
=
{
1,2
,
…
,
B
}. An offer m is a tuple 〈
e
m
,
d
m
max
⁡
〉, where e
m
≥
0 is an offered unit price, and d
m
max
⁡ is the maximal demanded volume of a commodity. Without loss of generality, to simplify the notation, we assume that each seller and each buyer are located in different node. Thus, the indexes of sellers and buyers can be also used for indexing the nodes. Let V
J
=
J
⊆
V be a set of seller nodes and let V
B
=
B
⊆
V be a set of buyer nodes. The vertex-oriented network winner determination problem (VWDP) is to find a set of winning offers and their volumes (
q
j
) and (
d
m
), 0
≤
q
j
≤
q
j
max
⁡ and 0
≤
d
m
≤
d
m
max
⁡, which is balanced (∑
j
∈
J
‍
q
j
=
∑
m
∈
B
‍
d
m) and social welfare-maximizing under the network flow constraints:
(1)
∑
e
∈
E
a
υ
e
f
e
=
{
q
υ
υ
∈
V
J
,
0
υ
∉
V
J
∪
V
B
,
-
d
m
υ
∈
V
B
,
∀
υ
∈
V
,
where f
e is the commodity flow over edge e and q
j and d
m are the accepted volumes of sell offer j and buy offer m, respectively. The VWDP maximizes the naturalutilitarian criterion—the sum of the surpluses of all individual players. Full formulation of VWDP is a simple extension of classical auction models [26] and can be expressed as linear programme.


## 3.2. Value Mechanism

The maximal total social welfareQ
=
∑
m
∈
M
‍
e
m
d
m
-
∑
j
∈
J
‍
c
j
q
j is achieved by solving VWDP. The buyers and sellers are selfish and tend to maximize their individual profits. Thus, we should notice that the submitted offers could be different than the market participants’ true valuations, and then Q would not be a true social welfare, but rather “declared” market surplus [31].The value mechanism is responsible for the surplus distribution. The distribution is usually expressed with the use of payment informationI, which may include market price, payments for individual offers, and other information. For instance, there are marginal prices at each node in I in case of LMP mechanism. The mechanism M is defined as the following mapping:
(2)
M
:
(
e
,
c
,
d
,
q
)
⟶
I
.A very generic approach to modeling the value mechanisms was formulated by Toczyłowski and calledparametric balancing model [26]. It introduces a virtual node denoted by 0 and connected to each other node. There are market price π
0 at virtual node and nodal prices π
υ at every node in V. If commodity is injected to the network at node k
∈
V and π
k is the nodal price, then π
k
0
=
π
0
-
π
k is the unit cost of commodity transport from node k to the virtual node 0. Similarly, if node l
∈
V is a consumption node with nodal price π
l then π
0
l
=
π
l
-
π
0 is the unit cost for commodity transport from the virtual node 0 to node l (see Figure 1).Figure 1
Model of pricing with nodal pricesπ
k, π
l, virtual node price π
0, and transmission prices π
k
0 and π
0
l.


## 3.3. Problem of Finding the Best Value Mechanism

Let us assume that there is a set ofL quality measures {
Q
1
(
M
)
,
…
,
Q
L
(
M
)
} of pricing mechanisms, where function Q
l
:
M
→
R is such that if Q
l
(
M
1
)
>
Q
l
(
M
2
), then mechanism M
1 is strictly preferred over the mechanism M
2 according to the measure l. Quality measures introduce the partial order to the space of mechanisms. Then, the problem of finding the best mechanism is defined as follows:
(3)
max
⁡
M
{
Q
1
(
M
)
,
…
,
Q
L
(
M
)
}
.For a given pricing mechanism it is interesting whether it is nondominated solution of multicriteria problem (3). In the next sections we will formulate a bit narrower space of possible mechanisms and we will analyze possible pricing mechanisms according to the PoF criterion.


## 4. Concept of Fairness

For a given set of nodal prices(
π
υ
) the set of offers can be divided intocompetitive andnoncompetitive subsets. A sell (buy) offer at node j
/
m iscompetitive if nodal price π
j
/
π
m is higher/lower than or equal to the offer price, that is, if c
j
≤
π
j
/
e
m
≥
π
m. An offer j isstrictly competitive if c
j
<
π
j or e
m
>
π
m. A sell (buy) offer j
/
m is considered to be noncompetitive offer if the nodal price is lower/higher than the offer price, that is, if c
j
>
π
k
/
e
m
<
π
k. If an accepted (fully or partially) offer is also noncompetitive offer then it is calledforced offer.Two notions of fairness have been introduced in [26]: absolute fairness and relative fairness.


### 4.1. Absolute Fairness

Fairness in absolute sense means that no offer brings individual loss. Figure2 illustrates an accepted (forced) sell offer j. Since the seller is paid with nodal price π
j lower than the offer price c
j, the entity gains loss q
j
(
c
j
-
π
j
). To compensate the loss, the cost of forced sell R
S
(
j
)
=
(
c
j
-
π
j
)
q
j must be also paid to the seller j. Of course, if it is possible to set nodal prices, that make each offer competitive, then no individual losses appear. A mechanism M can ensure no individual losses either by directly setting prices or by additional payment of losses compensation R
S
(
j
).Figure 2
CostR
S
(
j
) of forced sell.Similarly, the compensation of competitive buyer losses should be introduced. For forced buy offer the compensation isR
B
(
m
)
=
(
π
m
-
e
m
)
d
m. According to the concept of fairness introduced in [26], a mechanism M isfair in absolute sense if it ensures no individual losses.


### 4.2. Relative Fairness

Mechanism isfair in the relative sense if none of the parties can claim to be treated worse than others. This means that each strictly competitive offer must be fully accepted. For instance, a seller can claim to be treated clearly unfair if his offer price is lower than market nodal price, but his offer is not winning. If such situation cannot be avoided, the compensations for the loss of profit R
S
0
(
j
) should be introduced. Figure 3 illustrates the compensation for a sell offer j which is R
S
0
(
j
)
=
(
q
j
max
⁡
-
q
j
)
(
π
j
-
c
j
). Similarly, the compensation for uncompetitive buy offer m is defined as R
B
0
(
m
)
=
(
d
m
max
⁡
-
d
m
)
(
e
m
-
π
m
).Figure 3
Loss of profitsR
S
0
(
j
) for rejected, competitive sell offer.Also, two participants connected with undersaturated edge should have the same nodal prices. If this would not be satisfied, then the entity with the worse nodal price could trade in the neighbor’s node with better profits.A mechanismM is fair if it satisfies fairness conditions in absolute and relative senses.


## 4.1. Absolute Fairness

Fairness in absolute sense means that no offer brings individual loss. Figure2 illustrates an accepted (forced) sell offer j. Since the seller is paid with nodal price π
j lower than the offer price c
j, the entity gains loss q
j
(
c
j
-
π
j
). To compensate the loss, the cost of forced sell R
S
(
j
)
=
(
c
j
-
π
j
)
q
j must be also paid to the seller j. Of course, if it is possible to set nodal prices, that make each offer competitive, then no individual losses appear. A mechanism M can ensure no individual losses either by directly setting prices or by additional payment of losses compensation R
S
(
j
).Figure 2
CostR
S
(
j
) of forced sell.Similarly, the compensation of competitive buyer losses should be introduced. For forced buy offer the compensation isR
B
(
m
)
=
(
π
m
-
e
m
)
d
m. According to the concept of fairness introduced in [26], a mechanism M isfair in absolute sense if it ensures no individual losses.


## 4.2. Relative Fairness

Mechanism isfair in the relative sense if none of the parties can claim to be treated worse than others. This means that each strictly competitive offer must be fully accepted. For instance, a seller can claim to be treated clearly unfair if his offer price is lower than market nodal price, but his offer is not winning. If such situation cannot be avoided, the compensations for the loss of profit R
S
0
(
j
) should be introduced. Figure 3 illustrates the compensation for a sell offer j which is R
S
0
(
j
)
=
(
q
j
max
⁡
-
q
j
)
(
π
j
-
c
j
). Similarly, the compensation for uncompetitive buy offer m is defined as R
B
0
(
m
)
=
(
d
m
max
⁡
-
d
m
)
(
e
m
-
π
m
).Figure 3
Loss of profitsR
S
0
(
j
) for rejected, competitive sell offer.Also, two participants connected with undersaturated edge should have the same nodal prices. If this would not be satisfied, then the entity with the worse nodal price could trade in the neighbor’s node with better profits.A mechanismM is fair if it satisfies fairness conditions in absolute and relative senses.


## 5. Analysis of Fairness

### 5.1. Price of Fairness

LetQ be the social welfare resulting from the optimal solution of VWDP. Let M be a mechanism that satisfies absolute and relative fairness conditions. The mechanism produces some welfare distribution. Some part of the social welfare is distributed under pure market rules. The sellers obtain Q
S
=
∑
j
∈
J
‍
max
⁡
{
0
,
π
j
-
c
j
}
*
q
j and the buyers gain Q
B
=
∑
m
∈
B
‍
max
⁡
{
0
,
e
m
-
π
m
}
*
d
m. Some part of the social welfare is also distributed via lost profit compensations: R
S
0
(
j
) and R
B
0
(
m
). Finally, some social welfare may be not distributed and market becomes imbalanced.The difference between total social welfare and welfare distributed under the pure market rules is a price that must be paid to maintain fairness [34]. It can be partially paid as the compensations or it becomes an unbalanced value that should be allocated with some additional, not market, mechanism (like fees and subsidies). We call this difference theprice of fairness (PoF).


### 5.2. Space of Value Mechanisms

Lete
=
(
e
m
), c
=
(
c
j
), d
=
(
d
m
), q
=
(
q
j
), π
=
(
π
υ
), R
S
=
(
R
S
(
j
)
), R
B
=
(
R
B
(
m
)
), R
S
0
=
(
R
S
0
(
j
)
), R
B
0
=
(
R
B
0
(
m
)
). Let us define M the space of value mechanisms as follows:
(4)
M
=
{
M
:
(
e
,
c
,
d
,
q
)
⟶
(
π
,
π
0
,
R
S
,
R
B
,
R
S
0
,
R
B
0
)
}
.The spaceM is quite general. It covers LMP mechanism (R
S
=
R
B
=
R
S
0
=
R
B
0
=
0 and π are marginal). Also the single uniform price model is in M (π
0 is uniform market price and π
υ
=
π
0, ∀
υ
∈
V).Moreover, for the sake of generality, we also consider the mechanisms that, unlike the LMP or classical uniform pricing, assume two nodal market prices at each node: buying priceπ
υ
B and selling price π
υ
S. The idea of differentiation of sell and buy prices has been proposed in [26] and discussed in [31] in the context of balancing electrical energy market.


### 5.3. PoF Minimization

In the perfect situation, when no congestion manifests in the network, the maximal economic benefitQ
u
=
∑
m
∈
B
‍
e
m
*
d
m
u
-
∑
j
∈
J
‍
c
j
q
j
u can be reached, where d
m
u and q
j
u are the accepted volumes under neglected network constraints assumption. We will call the solution d
u
=
(
d
m
u
), q
u
=
(
q
j
u
) of the VWDP with network constraints neglected the unconstrained solution. The related social welfare Q
u will be called the unconstrained welfare. In most cases, as a result of limited resources in the system, the loss of aggregated economic benefits is observed. We refer to the solution d
=
(
d
m
), q
=
(
q
j
) as constrained solution for which constrained social welfare Q is obtained. Let D be the total trade volume, D
=
∑
j
‍
q
j
=
∑
j
‍
q
j
u.Lemma 2.
Price of fairness can be expressed as follows:(5)
P
o
F
=
(
π
0
B
-
π
0
S
)
D
+
∑
j
‍
π
j
0
q
j
+
∑
i
‍
π
0
i
d
i
.Proof.
Market sell cost received by the sellers is(6)
K
(
π
0
S
,
(
π
j
0
)
)
=
∑
j
‍
(
π
0
S
-
π
j
0
)
q
j
+
R
S
+
R
S
0
.
Market buy cost received by the buyers is(7)
Z
(
π
0
B
,
(
π
0
i
)
)
=
∑
i
‍
(
π
0
B
+
π
0
i
)
d
i
-
R
B
-
R
B
0
.
The basic balance is as follows:K
(
π
0
S
,
(
π
j
0
)
)
+
Q
0
=
Z
(
π
0
B
,
(
π
0
i
)
), where Q
0 is an imbalance of the market. Thus ∑
j
‍
(
π
0
S
-
π
j
0
)
q
j
+
R
S
+
R
S
0
+
Q
0
=
∑
i
‍
(
π
0
B
+
π
0
i
)
d
i
-
R
B
-
R
B
0, and after transformation Q
0
+
R
S
+
R
B
+
R
S
0
+
R
B
0
=
∑
i
‍
(
π
0
B
+
π
0
i
)
d
i
-
∑
j
‍
(
π
0
S
-
π
j
0
)
q
j, and after further simplifications Q
0
+
R
S
+
R
B
+
R
S
0
+
R
B
0
=
(
π
0
B
-
π
0
S
)
D
+
∑
i
‍
π
0
i
d
i
+
∑
j
‍
π
j
0
q
j.Let us analyze the properties ofK
(
π
0
S
,
(
π
j
0
)
). For given values of (
π
j
0
) we obtain the market sell cost function K
(
π
0
S
) of one variable π
0
S. If π
0
S is sufficiently small (i.e., it is below each of the offer prices), then the function K
(
π
0
S
) is equal to some minimal value K
0. Function K
(
π
0
S
) increases with π
0
S increase. K
(
π
0
S
) is a continuous, convex function (the derivative of this function is equal to volume of sell offers and prices lower than π
0
S).Similar analysis can be done for functionZ
(
π
0
B
,
(
π
0
i
)
). For given values of (
π
0
i
) we obtain function Z
(
π
0
B
), which for sufficiently big price π
0
B, no less than the maximal offer price, is equal to sell value Z
0. When the value of π
0
B goes down, the function Z
(
π
0
B
) becomes decreasing and its derivative is increasing. So, it is continuous, concave function.FunctionsK
(
π
0
S
) and Z
(
π
0
B
) are illustrated in Figure 4. It is easy to see from (5) and Figure 4 that, for given values (
π
j
0
) and (
π
0
i
), the PoF function of market prices π
0
S and π
0
B is a convex function. Let us denote the value of market trade by W
=
K
(
π
0
S
)
+
Q
0
=
Z
(
π
0
B
) for given values (
π
j
0
) and (
π
0
i
).Figure 4
Market sell cost and market buy cost functions.Lemma 3.
The PoF is a convex function with respect to the value of market tradeW.Proof.
The proof of convexity of function(
π
B
-
π
S
)
D, without congestion costs, is provided in [26]. For fixed congestion costs, that is, for given values of (
π
j
0
) and (
π
0
i
), PoF
(
W
) is a function of market trade value W in the range [
K
0
,
Z
0
] and it is a convex function (see Figure 4).
Notice that above property is true for all values of(
π
j
0
) and (
π
0
i
). Any change in values of (
π
j
0
) results in parallel shift of the function K
(
π
0
S
) by the value -
∑
j
‍
π
j
0
q
j. Any change in values of (
π
0
i
) results in parallel shift of function Z
(
π
0
B
) by ∑
j
‍
π
0
i
d
j. Due to market balance, any deviation in ∑
j
‍
π
j
0
q
j must be compensated by a change in ∑
j
‍
π
0
i
d
j; thus ∑
j
‍
π
j
0
q
j
+
∑
j
‍
π
0
i
d
j is constant. Finally, any shift in K
(
π
0
S
) must also result in the same shift in Z
(
π
0
B
). For different prices (
π
j
0
) and (
π
0
i
) the gap between K
(
π
0
S
) and Z
(
π
0
B
) is constant and PoF
(
W
) does not change when the values (
π
j
0
) and (
π
0
i
) are changing. Therefore, PoF
(
W
) is a convex function for any prices (
π
j
0
) and (
π
0
i
).Now, we will show that the minimum of PoF is reached for market priceπ
0
=
π
u. First, in the following two lemmas we consider two cases: (
1
) market price π
0 is lower than π
u; (
2
) market price π
0 is greater than π
u.Lemma 4.
The PoF for market priceπ
0
=
π
u is lower than PoF for π
0
<
π
u.Proof.
We assume that congestions involve some reduction of accepted volume of offers from setJ
R with total reduced volume q
R
=
∑
j
∈
J
R
‍
(
q
j
u
-
q
j
). Because these offers would be accepted in the unconstrained market, their prices must be lower than π
u. To meet the demand D, the reduction must be compensated by some forced offers. Let us denote the set of these offers by J
W. Their prices must be not lower than π
u and their total volume is q
R
=
∑
j
∈
J
W
‍
(
q
j
-
q
j
u
). Now, we will consider a decrease of market price by the value π
u
-
π
0. It would decrease the compensations by the value (
π
u
-
π
0
)
*
q
R, if π
0 is higher than c
j for j
∈
J
R, or the decrease would be even smaller if some of the offers would become competitive. Total change of compensation is determined as follows:
(8)
∑
j
∈
J
R
,
c
j
≤
π
0
‍
(
π
u
-
π
0
)
*
(
q
j
u
-
q
j
)
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
π
u
-
c
j
)
*
(
q
j
u
-
q
j
)
.
The above expression can be also rewritten in the following form:(9)
∑
j
∈
J
R
‍
(
π
u
-
π
0
)
*
(
q
j
u
-
q
j
)
-
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
(
q
j
u
-
q
j
)
.
Decreasing the market price causes increase in costs of forced sell with value(
π
u
-
π
0
)
*
q
j for j
∈
J
W and (
c
j
-
π
0
)
*
q
j for j
∈
J
R and c
j
>
π
0. Total change in the PoF is as follows:
(10)
increase
of
forced
costs
-
decrease
of
cost
of
compensations
=
(
π
u
-
π
0
)
*
q
R
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
q
j
-
(
π
u
-
π
0
)
*
q
R
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
(
q
j
u
-
q
j
)
=
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
q
j
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
(
q
j
u
-
q
j
)
>
0
.
Similar reasoning can be carried out for the buyers, showing that decreasingπ
0 leads to increase of the PoF.Lemma 5.
The PoF for market priceπ
0
=
π
u is lower than PoF for π
0
>
π
u.Proof.
The proof is similar to the proof of the previous lemma. Let us assume that congestions cause the reduction of accepted volume of offers from the setJ
R with total volume q
R
=
∑
j
∈
J
R
‍
(
q
j
u
-
q
j
). Because these offers would be accepted in the unconstrained market, their prices must be not higher than π
u. To meet the demand D, there must be also forced increase of other offers. Let us denote these offers by J
W. Their prices must be not lower than π
u and their total volume is q
R
=
∑
j
∈
J
W
‍
(
q
j
-
q
j
u
). Increase of market price by value π
0
-
π
u causes a compensation increase by value
(11)
∑
j
∈
J
R
‍
(
π
0
-
π
u
)
*
(
q
j
u
-
q
j
)
+
∑
c
j
=
π
u
‍
(
π
0
-
π
u
)
*
(
q
j
max
⁡
)
+
∑
j
∈
J
W
,
c
j
<
π
0
‍
(
π
0
-
c
j
)
*
(
q
j
max
⁡
-
q
j
)
+
∑
j
:
q
j
=
0
,
π
u
<
c
j
<
π
0
‍
(
π
u
-
c
j
)
*
q
j
max
⁡
.
The increase of market price causes the decrease cost of forced sell by(12)
∑
j
∈
J
W
,
c
j
>
π
0
‍
(
π
0
-
π
u
)
*
q
j
+
∑
j
∈
J
W
,
c
j
≤
π
0
‍
(
π
0
-
c
j
)
*
q
j
.
The above expression can be also rewritten as follows:
(13)
(
π
0
-
π
u
)
*
q
R
-
∑
j
∈
J
W
,
c
j
>
π
0
‍
(
π
0
-
c
j
)
*
q
j
.
Total change in PoF of balancing is as follows:(14)
increase
of
cost
of
compensations
-
decrease
of
forced
costs
=
(
π
0
-
π
u
)
*
q
R
+
∑
c
j
=
π
u
‍
(
π
0
-
π
u
)
*
(
q
j
max
⁡
)
+
∑
j
∈
J
W
,
c
j
<
π
0
‍
(
π
0
-
c
j
)
*
(
q
j
max
⁡
-
q
j
)
+
∑
j
:
q
j
=
0
,
π
u
<
c
j
<
π
0
‍
(
π
u
-
c
j
)
*
q
j
max
⁡
-
(
π
0
-
π
u
)
*
q
R
+
∑
j
∈
J
W
,
c
j
>
π
0
‍
(
π
0
-
c
j
)
*
q
j
>
0
.
Similar reasoning can be carried out for the buyers, showing that increasing π
0 leads to increase of the PoF.Finally, we can formulate the theorem about the minimal PoF.Theorem 6.
The minimum of PoF is achieved at the market priceπ
u at every node.Proof.
The proof is clear on the basis of Lemma3 about the convexity of PoF and Lemmas 4 and 5 about local minimum of PoF at price π
u.


## 5.1. Price of Fairness

LetQ be the social welfare resulting from the optimal solution of VWDP. Let M be a mechanism that satisfies absolute and relative fairness conditions. The mechanism produces some welfare distribution. Some part of the social welfare is distributed under pure market rules. The sellers obtain Q
S
=
∑
j
∈
J
‍
max
⁡
{
0
,
π
j
-
c
j
}
*
q
j and the buyers gain Q
B
=
∑
m
∈
B
‍
max
⁡
{
0
,
e
m
-
π
m
}
*
d
m. Some part of the social welfare is also distributed via lost profit compensations: R
S
0
(
j
) and R
B
0
(
m
). Finally, some social welfare may be not distributed and market becomes imbalanced.The difference between total social welfare and welfare distributed under the pure market rules is a price that must be paid to maintain fairness [34]. It can be partially paid as the compensations or it becomes an unbalanced value that should be allocated with some additional, not market, mechanism (like fees and subsidies). We call this difference theprice of fairness (PoF).


## 5.2. Space of Value Mechanisms

Lete
=
(
e
m
), c
=
(
c
j
), d
=
(
d
m
), q
=
(
q
j
), π
=
(
π
υ
), R
S
=
(
R
S
(
j
)
), R
B
=
(
R
B
(
m
)
), R
S
0
=
(
R
S
0
(
j
)
), R
B
0
=
(
R
B
0
(
m
)
). Let us define M the space of value mechanisms as follows:
(4)
M
=
{
M
:
(
e
,
c
,
d
,
q
)
⟶
(
π
,
π
0
,
R
S
,
R
B
,
R
S
0
,
R
B
0
)
}
.The spaceM is quite general. It covers LMP mechanism (R
S
=
R
B
=
R
S
0
=
R
B
0
=
0 and π are marginal). Also the single uniform price model is in M (π
0 is uniform market price and π
υ
=
π
0, ∀
υ
∈
V).Moreover, for the sake of generality, we also consider the mechanisms that, unlike the LMP or classical uniform pricing, assume two nodal market prices at each node: buying priceπ
υ
B and selling price π
υ
S. The idea of differentiation of sell and buy prices has been proposed in [26] and discussed in [31] in the context of balancing electrical energy market.


## 5.3. PoF Minimization

In the perfect situation, when no congestion manifests in the network, the maximal economic benefitQ
u
=
∑
m
∈
B
‍
e
m
*
d
m
u
-
∑
j
∈
J
‍
c
j
q
j
u can be reached, where d
m
u and q
j
u are the accepted volumes under neglected network constraints assumption. We will call the solution d
u
=
(
d
m
u
), q
u
=
(
q
j
u
) of the VWDP with network constraints neglected the unconstrained solution. The related social welfare Q
u will be called the unconstrained welfare. In most cases, as a result of limited resources in the system, the loss of aggregated economic benefits is observed. We refer to the solution d
=
(
d
m
), q
=
(
q
j
) as constrained solution for which constrained social welfare Q is obtained. Let D be the total trade volume, D
=
∑
j
‍
q
j
=
∑
j
‍
q
j
u.Lemma 2.
Price of fairness can be expressed as follows:(5)
P
o
F
=
(
π
0
B
-
π
0
S
)
D
+
∑
j
‍
π
j
0
q
j
+
∑
i
‍
π
0
i
d
i
.Proof.
Market sell cost received by the sellers is(6)
K
(
π
0
S
,
(
π
j
0
)
)
=
∑
j
‍
(
π
0
S
-
π
j
0
)
q
j
+
R
S
+
R
S
0
.
Market buy cost received by the buyers is(7)
Z
(
π
0
B
,
(
π
0
i
)
)
=
∑
i
‍
(
π
0
B
+
π
0
i
)
d
i
-
R
B
-
R
B
0
.
The basic balance is as follows:K
(
π
0
S
,
(
π
j
0
)
)
+
Q
0
=
Z
(
π
0
B
,
(
π
0
i
)
), where Q
0 is an imbalance of the market. Thus ∑
j
‍
(
π
0
S
-
π
j
0
)
q
j
+
R
S
+
R
S
0
+
Q
0
=
∑
i
‍
(
π
0
B
+
π
0
i
)
d
i
-
R
B
-
R
B
0, and after transformation Q
0
+
R
S
+
R
B
+
R
S
0
+
R
B
0
=
∑
i
‍
(
π
0
B
+
π
0
i
)
d
i
-
∑
j
‍
(
π
0
S
-
π
j
0
)
q
j, and after further simplifications Q
0
+
R
S
+
R
B
+
R
S
0
+
R
B
0
=
(
π
0
B
-
π
0
S
)
D
+
∑
i
‍
π
0
i
d
i
+
∑
j
‍
π
j
0
q
j.Let us analyze the properties ofK
(
π
0
S
,
(
π
j
0
)
). For given values of (
π
j
0
) we obtain the market sell cost function K
(
π
0
S
) of one variable π
0
S. If π
0
S is sufficiently small (i.e., it is below each of the offer prices), then the function K
(
π
0
S
) is equal to some minimal value K
0. Function K
(
π
0
S
) increases with π
0
S increase. K
(
π
0
S
) is a continuous, convex function (the derivative of this function is equal to volume of sell offers and prices lower than π
0
S).Similar analysis can be done for functionZ
(
π
0
B
,
(
π
0
i
)
). For given values of (
π
0
i
) we obtain function Z
(
π
0
B
), which for sufficiently big price π
0
B, no less than the maximal offer price, is equal to sell value Z
0. When the value of π
0
B goes down, the function Z
(
π
0
B
) becomes decreasing and its derivative is increasing. So, it is continuous, concave function.FunctionsK
(
π
0
S
) and Z
(
π
0
B
) are illustrated in Figure 4. It is easy to see from (5) and Figure 4 that, for given values (
π
j
0
) and (
π
0
i
), the PoF function of market prices π
0
S and π
0
B is a convex function. Let us denote the value of market trade by W
=
K
(
π
0
S
)
+
Q
0
=
Z
(
π
0
B
) for given values (
π
j
0
) and (
π
0
i
).Figure 4
Market sell cost and market buy cost functions.Lemma 3.
The PoF is a convex function with respect to the value of market tradeW.Proof.
The proof of convexity of function(
π
B
-
π
S
)
D, without congestion costs, is provided in [26]. For fixed congestion costs, that is, for given values of (
π
j
0
) and (
π
0
i
), PoF
(
W
) is a function of market trade value W in the range [
K
0
,
Z
0
] and it is a convex function (see Figure 4).
Notice that above property is true for all values of(
π
j
0
) and (
π
0
i
). Any change in values of (
π
j
0
) results in parallel shift of the function K
(
π
0
S
) by the value -
∑
j
‍
π
j
0
q
j. Any change in values of (
π
0
i
) results in parallel shift of function Z
(
π
0
B
) by ∑
j
‍
π
0
i
d
j. Due to market balance, any deviation in ∑
j
‍
π
j
0
q
j must be compensated by a change in ∑
j
‍
π
0
i
d
j; thus ∑
j
‍
π
j
0
q
j
+
∑
j
‍
π
0
i
d
j is constant. Finally, any shift in K
(
π
0
S
) must also result in the same shift in Z
(
π
0
B
). For different prices (
π
j
0
) and (
π
0
i
) the gap between K
(
π
0
S
) and Z
(
π
0
B
) is constant and PoF
(
W
) does not change when the values (
π
j
0
) and (
π
0
i
) are changing. Therefore, PoF
(
W
) is a convex function for any prices (
π
j
0
) and (
π
0
i
).Now, we will show that the minimum of PoF is reached for market priceπ
0
=
π
u. First, in the following two lemmas we consider two cases: (
1
) market price π
0 is lower than π
u; (
2
) market price π
0 is greater than π
u.Lemma 4.
The PoF for market priceπ
0
=
π
u is lower than PoF for π
0
<
π
u.Proof.
We assume that congestions involve some reduction of accepted volume of offers from setJ
R with total reduced volume q
R
=
∑
j
∈
J
R
‍
(
q
j
u
-
q
j
). Because these offers would be accepted in the unconstrained market, their prices must be lower than π
u. To meet the demand D, the reduction must be compensated by some forced offers. Let us denote the set of these offers by J
W. Their prices must be not lower than π
u and their total volume is q
R
=
∑
j
∈
J
W
‍
(
q
j
-
q
j
u
). Now, we will consider a decrease of market price by the value π
u
-
π
0. It would decrease the compensations by the value (
π
u
-
π
0
)
*
q
R, if π
0 is higher than c
j for j
∈
J
R, or the decrease would be even smaller if some of the offers would become competitive. Total change of compensation is determined as follows:
(8)
∑
j
∈
J
R
,
c
j
≤
π
0
‍
(
π
u
-
π
0
)
*
(
q
j
u
-
q
j
)
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
π
u
-
c
j
)
*
(
q
j
u
-
q
j
)
.
The above expression can be also rewritten in the following form:(9)
∑
j
∈
J
R
‍
(
π
u
-
π
0
)
*
(
q
j
u
-
q
j
)
-
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
(
q
j
u
-
q
j
)
.
Decreasing the market price causes increase in costs of forced sell with value(
π
u
-
π
0
)
*
q
j for j
∈
J
W and (
c
j
-
π
0
)
*
q
j for j
∈
J
R and c
j
>
π
0. Total change in the PoF is as follows:
(10)
increase
of
forced
costs
-
decrease
of
cost
of
compensations
=
(
π
u
-
π
0
)
*
q
R
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
q
j
-
(
π
u
-
π
0
)
*
q
R
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
(
q
j
u
-
q
j
)
=
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
q
j
+
∑
j
∈
J
R
,
c
j
>
π
0
‍
(
c
j
-
π
0
)
*
(
q
j
u
-
q
j
)
>
0
.
Similar reasoning can be carried out for the buyers, showing that decreasingπ
0 leads to increase of the PoF.Lemma 5.
The PoF for market priceπ
0
=
π
u is lower than PoF for π
0
>
π
u.Proof.
The proof is similar to the proof of the previous lemma. Let us assume that congestions cause the reduction of accepted volume of offers from the setJ
R with total volume q
R
=
∑
j
∈
J
R
‍
(
q
j
u
-
q
j
). Because these offers would be accepted in the unconstrained market, their prices must be not higher than π
u. To meet the demand D, there must be also forced increase of other offers. Let us denote these offers by J
W. Their prices must be not lower than π
u and their total volume is q
R
=
∑
j
∈
J
W
‍
(
q
j
-
q
j
u
). Increase of market price by value π
0
-
π
u causes a compensation increase by value
(11)
∑
j
∈
J
R
‍
(
π
0
-
π
u
)
*
(
q
j
u
-
q
j
)
+
∑
c
j
=
π
u
‍
(
π
0
-
π
u
)
*
(
q
j
max
⁡
)
+
∑
j
∈
J
W
,
c
j
<
π
0
‍
(
π
0
-
c
j
)
*
(
q
j
max
⁡
-
q
j
)
+
∑
j
:
q
j
=
0
,
π
u
<
c
j
<
π
0
‍
(
π
u
-
c
j
)
*
q
j
max
⁡
.
The increase of market price causes the decrease cost of forced sell by(12)
∑
j
∈
J
W
,
c
j
>
π
0
‍
(
π
0
-
π
u
)
*
q
j
+
∑
j
∈
J
W
,
c
j
≤
π
0
‍
(
π
0
-
c
j
)
*
q
j
.
The above expression can be also rewritten as follows:
(13)
(
π
0
-
π
u
)
*
q
R
-
∑
j
∈
J
W
,
c
j
>
π
0
‍
(
π
0
-
c
j
)
*
q
j
.
Total change in PoF of balancing is as follows:(14)
increase
of
cost
of
compensations
-
decrease
of
forced
costs
=
(
π
0
-
π
u
)
*
q
R
+
∑
c
j
=
π
u
‍
(
π
0
-
π
u
)
*
(
q
j
max
⁡
)
+
∑
j
∈
J
W
,
c
j
<
π
0
‍
(
π
0
-
c
j
)
*
(
q
j
max
⁡
-
q
j
)
+
∑
j
:
q
j
=
0
,
π
u
<
c
j
<
π
0
‍
(
π
u
-
c
j
)
*
q
j
max
⁡
-
(
π
0
-
π
u
)
*
q
R
+
∑
j
∈
J
W
,
c
j
>
π
0
‍
(
π
0
-
c
j
)
*
q
j
>
0
.
Similar reasoning can be carried out for the buyers, showing that increasing π
0 leads to increase of the PoF.Finally, we can formulate the theorem about the minimal PoF.Theorem 6.
The minimum of PoF is achieved at the market priceπ
u at every node.Proof.
The proof is clear on the basis of Lemma3 about the convexity of PoF and Lemmas 4 and 5 about local minimum of PoF at price π
u.


## 6. Summary

In the paper, we have introduced and analyzed the concept ofprice of fairness. PoF reflects the social welfare that must be distributed out of pure market mechanism to assure that the final distribution is fair according to the absolute and relative fairness definitions. Our main result is proving that the PoF is a convex function with respect to the market value W. It means that there exists the unique minimum of PoF function. In fact, we have proved that the minimal PoF is achieved for theoretical uniform price π
u coming from the unconstrained market solution. Instead of nodal marginality, the costs of forced offers and compensations of lost profits are paid. We observe that widely applied locational marginal pricing mechanism does not in general minimize the PoF.Our results open the doors for further investigations of new mechanisms. We have shown that there is still a lot of space for new mechanisms that can be even better than locational marginal pricing, at least in some criteria, for example, PoF. We have introduced the space of mechanismM, which is promising to contain new interesting mechanism designs. We believe that further researches should include more quality measures of mechanism, for example, efficiency market signals.



---

*Source: 860747-2014-07-17.xml*