# A New Representation of Efficient Point Sets and Its Applications in DEA

Authors: Maoqin Li
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

E
(
M
,
K
)
(
E
w
(
M
,
K
)
), the set of Pareto efficient (weak efficient) points of a set M with respect to a cone K in Rn, is expressed as a differencebetweentwo sets M and M+K∖{0} (M and M+intK). Using the new representation, the properties of E(M,K) are proved more easily than before. When M or K is in the form of union, intersection, sum, or difference of two sets or two cones, respectively, the properties of E(M,K) are considered. Most of the properties are proved by the binary operations of sets, which is a new method in the multiobjective optimization. Then these properties are used to solve some types of multiobjective linear programming problems corresponding to Data Envelopment Analysis (DEA) models. The structures of the DEA efficient solution sets of four most representative DEA models are developed. Further more, the relationships between efficiencies of the four DEA models are deduced.


---

## Body

## 1. Introduction and Preliminaries

Multiobjective programming is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints (see [1–3]). Data Envelopment Analysis (DEA) is a nonparametric method in operations research and economics for the estimation of production frontiers. It is used to empirically measure productive efficiency of decision maker units DMU1,…,DMUn by solving the linear programming [4–6]. Charnes et al.  and Wei et al. establish the equivalence of (weak) DEA efficient solutions in DEA model and (weak) Pareto solutions of multiobjective linear programming [7–9]. There is a multiobjective linear programming, corresponding to a DEA model, such that a DMUj0(1≤j0≤n) is (weak) DEA efficient if and only if (xj0,yj0) (associating with the DMUj0) is a (weak) Pareto efficient solution of the multiobjective linear programming whose feasible region is the production possibility set (see [10]).In this paper, we propose a new representation for the set of Pareto efficient (weak efficient) points. With the help of the new representation, not only the properties of the set of Pareto efficient (weak efficient) points which are given in [1, 3, 11] can be proved more simply, but also more new properties can be obtained. It is these new properties that reveal the relationships between the set of solutions and different multiobjective linear programmings which correspond to different DEA models. Further, the relationships between efficiencies of DMUs in different DEA models are obtained by a new way. Wei et al.  [10] develop a famous method to translate production possibility sets in the intersection form and in the sum form and find all DEA efficient DMUs. For each of the four most representative DEA models, we offers a simple way to get all DEA efficient DMUs by the binary operations of sets.Now let us recall the definition of efficiency and the representation of the set of efficient points deduced by the definition in vector optimization.Definition 1 ([1], efficiency, weak efficiency).
Given a nonempty setM and a cone K with intK≠∅ in Rn, x0∈M is called a Pareto efficient (weak efficient) point of M, if there is no y∈M with y≠x0 such that x0∈y+K(x0∈y+intK). The set of all Pareto efficient (weak efficient) points of M is denoted by E(M,K)(Ew(M,K)).
E
(
M
,
K
) (Ew(M,K)) is called the efficient (weak efficient) point set of M. By Definition 1, we have that
(1)E(M,K)={x∈M∣there is noy∈M,y≠xsuch thatx∈y+K},(2)(Ew(M,K)={x∈M∣there is noy∈Msuchthatx∈y+intK}).
In [2] when K=R+n, the set is also described as follows:
(3)E(M,K)={x∈M∣M∩(x-K)={x}},(4)(Ew(M,K)={x∈M∣M∩(x-intK)=∅}).
SinceK=R+n is a convex pointed cone, (1) and (3) are equivalent. So are (2) and (4). In Section 2, we give a new representation of the efficient (weak efficient) point set, which is expressed as the difference of two sets. The idea of the new representation is motivated by the following facts in the area of DEA:(i)
the structures of the production possibility sets and the relationships between these sets (5);(ii)
the equivalence of Pareto efficiency in multiobjective linear programming and DEA efficiency in DEA model (Theorem18);(iii)
the particularity of structures of the set of solutions to the multiobjective linear programmings corresponding to DEA models (detailed in Section3).
For the four most representative DEA modelsC2R, BC2, FG, and ST (for the details about the models, see [4, 5]), each of the DEA models associates with a production possibility set which is also the feasible set of the multiobjective linear programming corresponding to this DEA model. The production possibility sets are denoted by TC2R, TBC2, TFG, and, TST, respectively. The following relations hold (the structures of these production possibility sets are presented in Section 3):(5)(a)TC2R=TFG∪TST,(b)TBC2=TFG∩TST,(c)TC2R⊃TFG⊃TBC2,(d)TC2R⊃TST⊃TBC2.
It is the specialty of the relations of the production possibility sets and the equivalence of DEA efficiency and Pareto efficiency that motivate us to propose a new representation of (weak) efficient point set. Using the new representation,we obtain some new properties of efficient point setE(M,K), when the set M or K is in form at union, intersection, sum, or difference of two sets. By these properties, it is easier to get the relationship between the DEA efficiency of the four DEA models than before.
This paper is organized as follows. Section2 introduces the new representation of the efficient (weak efficient) point set of a set, discusses some new properties of efficient point set. Using the new expression of the set E(M,K)(Ew(M,K)), most of these properties are proved by the binary operations of sets. The multiobjective linear programming problems corresponding to the four DEA models are studied in Section 3. The structures of the efficient point sets and the efficient solution sets of the multiobjective linear programming problems are developed, and then the relationships between DEA efficiencies of DMUs in four DEA models are revealed. Section 4 is devoted to the conclusion.
The following notations are used in the paper.
LetM, M1, M2, and K be sets in Rn:
(6)M1+M2={x1+x2∣x1∈M1,x2∈M2},M1∖M2={x∣x∈M1,x∉M2},M¯={x∈Rn∣x∉M},K0=K∖{0}.


## 2. Some Properties of the Efficient Point Set

In this section, a new representation ofE(M,K) (Ew(M,K)) is presented. Then we prove that it is equivalent to the original ones when K is a cone. Lastly we focus on the properties of E(M,K), when M or K is in the form of the union, intersection, sum, or difference of two sets. Most of the proofs are completed by the binary operations of sets, which is a new method in multiobjective optimization.Definition 2.
Given a nonempty setM and a cone K with intK≠∅ in Rn, the efficient (weak efficient) point set of M with respect to K is defined by
(7)E(M,K)=M∖(M+K0),(8)(Ew(M,K)=M∖(M+intK)).Clearly, the following result holds.Theorem 3.
Equations (1) and (7) ((2) and (8)) are equivalent, that is,
(9)E(M,K)={x∈Mthereisnoy∈M,y≠xsuchthatx∈y+K}=M∖(M+K0),(Ew(M,K)={x∈M∣thereisnoy∈Msuchthatx∈y+intK}=M∖(M+intK)).Definition2 gives a new representation of E(M,K) that is, the efficient point set of a set M is the difference between two sets. Using this new representation, we prove the properties of E(M,K). Proposition 4 comes from Luc [1], Papageorgiou [3], and  Guerraggio et al. [11]. We give an easier proof of this proposition.Proposition 4.
Assume thatM, M1, and M2 are nonempty sets and K, K1, and K2 are cones in Rn, λ>0. Then(i)
E(M,K2)⊆E(M,K1),  ifK1⊆K2,(ii)
E(λM,K)=λE(M,K),(iii)
E(M1+M2,K)⊆E(M1,K)+E(M2,K),(iv)
E(M+H,K)=E(M,K),  for any{0}⊆H⊆K, K    is a convex cone.Proof.
For convenience, letK10=K1∖{0}, and let K20=K2∖{0}. Since K1⊆K2, we have M+K10⊆M+K20. And then
(10)E(M,K2)=M∖(M+K20)⊆M∖(M+K10)=E(M,K1),(11)E(λM,K)=(λM)∖(λM+K0)=(λM)∖(λM+λK0)=(λM)∖λ(M+K0)=λ[M∖(M+K0)]=λ[E(M,K)].
By Theorem3, it is sufficient to show that
(12)(M1+M2)∖(M1+M2+K0)⊆[M1∖(M1+K0)]+[M2∖(M2+K0)],
for all x=x1+x2∈(M1+M2)∖(M1+M2+K0), where x1∈M1, x2∈M2 and x1+x2∉M1+M2+K0. Then x1∉M1+K0, otherwise x1+x2∈M1+M2+K0, a contradiction. Similarly x2∉M2+K0. Hence
(13)x=x1+x2∈[M1∖(M1+K0)]+[M2∖(M2+K0)].
Since0∈H⊆K and K is a convex cone, we have M⊂M+H, H+K0=K0,
(14)E(M+H,K)=(M+H)∖(M+H+K0)=(M+H)∖(M+K0)⊃M∖(M+K0)=E(M,K).
On the other hand, For anyx∈E(M+H,K)=(M+H)∖(M+K0), x=m+h, m∈M, h∈H. If h≠0, then x∈(M+K0), a contradiction. Hence, x∈M, x∉M+K0, that is, x∈E(M,K).A spacial case of (ii) in Proposition4 is that
(15)E(M+⋯+M︷m,K)=E(mM,K)=mE(M,K),
if M is convex and K is a cone.Besides Proposition4, we state the following properties.Corollary 5.
Consider the following:(16)(v)E(M,K1+K2)⊆E(M,K1)∩E(M,K2),(vi)E(M,K1∩K2)⊇E(M,K1)∪E(M,K2).Proposition 6.
LetM, G1, and G2 be sets in Rn. Then
(17)M∖[M+(G1∪G2)0]=[M∖(M+G10)]∩[M∖(M+G20)].Proof.
It is obvious that(G1∪G2)0=G10∪G20 and M+(G1∪G2)0=M+(G10∪G20)=(M+G10)∪(M+G20). Hence
(18)M∖[M+(G1∪G2)0]=M∖[M+(G10∪G20)]=M∖[(M+G10)∪(M+G20)]=M∩(M+G10)∪(M+G20)¯=(M∩M+G10¯)∩(M∩M+G20¯)=[M∖(M+G10)]∩[M∖(M+G20)].LetG1=K1, and let G2=K2 in Proposition 6. We have Corollary 7.Corollary 7.
IfK1 and K2 are cones, then
(19)E(M,K1∪K2)=E(M,K1)∩E(M,K2).In the following, we investigate some new properties of the efficient set whenM is the union, intersection, sum, or difference of two sets.Lemma 8.
IfK is a convex cone, then
(20)E[M1∖(M2+K),K]⊂E(M1,K).Proof.
IfE[M1∖(M2+K),K]=∅, the result obviously holds.
Otherwise, for allx∈E[M1∖(M2+K),K], if x∉E(M1,K), ∃y1∈M1,k∈K such that x=y1+k,k≠0, where y1∈M1=[M1∖(M2+K)]∪[M1∩(M2+K)].
Ify1∈M1∖(M2+K), it contradicts that x∈E[M1∖(M2+K),K]. Hence y1∈M1∩(M2+K). ∃y2∈M2 such that y1∈y2+K, so x∈y1+K⊂y2+K⊂M2+K, which still contradicts that x∈E[M1∖(M2+K),K]. In consequence, x∈E(M1,K).A more accurate relationship between the two efficient sets in Lemma8 is described in the following proposition.Proposition 9.
IfK is a convex cone, then
(21)E[M1∖(M2+K),K]=E(M1,K)∖(M2+K).Proof.
E
[
M
1
∖
(
M
2
+
K
)
,
K
]
⊂
E
(
M
1
,
K
) obtained by Lemma 8.
Note that(M1∖M2+K)∩(M2+K)=∅, E[M1∖(M2+K),K]=E[M1∖(M2+K),K]∩(M2+K)¯. So E[M1∖(M2+K),K]=E[M1∖(M2+K),K]∩(M2+K)¯⊂E(M1,K)∖(M2+K).
Reciprocally, for allx∈E(M1,K)∖(M2+K), x∈E(M1,K), x∉M2+K. If x∉E[M1∖(M2+K),K], ∃y∈M1∖(M2+K) with x≠y such that x∈y+K, in contradiction to x∈E(M1,K). Therefore,
(22)E(M1,K)∖(M2+K)⊂E[M1∖(M2+K),K].UsuallyE(M1∖M2,K)≠E(M1,K)∖M2, is what Example 10 shows.Example 10.
Consider the following:(23)M1={(x,y)∈R2∣0≤x≤1,0≤y≤1},M2={(x,y)∈R2∣0≤x≤1,0≤y≤1-x},M1∖M2={(x,y)∈R2∣0≤x≤1,1-x≤y≤1},E(M1,R2+)={(0,0)},E(M1∖M2,R2+)={(x,y)∣x+y=1,0≤x≤1,0≤y≤1}.
About the efficient point set of differences between two setsM1 and M2, Proposition 11 gives the conclusion, without requiring K to be a convex but a cone.Proposition 11.
Consider the following:(24)E(M1∖M2,K)⊇[E(M1,K)∖M2]∪[E(M2¯,K)∖M1¯]Proof.
We have(25)E(M1∖M2,K)=(M1∖M2)∖[(M1∖M2)+K0]=(M1∩M2¯)∩(M1∩M2¯)+K0¯⊇(M1∩M2¯)∩(M1+K0)∩(M2¯+K0)¯=(M1∩M2¯)∩[M1+K0¯∪(M2¯+K0)¯]=[(M1∩M2¯)∩(M1+K0¯)]∪[(M1∩M2¯)∩(M2¯+K0¯)]=[E(M1,K)∩M2¯]∪[E(M2¯,K)∩M1]=[E(M1,K)∖M2]∪[E(M2¯,K)∖M1¯].Remark 12.
In the previously mentioned proposition, if(M1∩M2¯)+K0=(M1+K0)∩(M2¯+K0), the equation holds.Propositions13 and 15 present the properties of the efficient point sets; when M is the union or intersection of two sets, respectively, K is not required to be a convex.Proposition 13.
Consider the following:(26)E(M1∪M2,K)=[E(M1,K)∖(M2+K0)]∪[E(M2,K)∖(M1+K0)].Proof.
We have(27)E(M1∪M2,K)=(M1∪M2)∖[(M1∪M2)+K0]=(M1∪M2)∩(M1∪M2)+K0¯=(M1∪M2)∩(M1+K0)∪(M2+K0)¯=(M1∪M2)∩M1+K0¯∩M2+K0¯=(M1∩M1+K0¯∩M2+K0¯)∪(M2∩M2+K0¯∩M1+K0¯)=[E(M1,K)∖(M2+K0)]∪[E(M2,K)∖(M1+K0)].Remark 14.
It is obvious that ifE(M1,K)∩(M2+K0)=∅ and E(M2,K)∩(M1+K0)=∅, then
(28)E(M1∪M2,K)=E(M1,K)∪E(M2,K).Proposition 15.
Consider the following:(29)E(M1∩M2,K)⊇[E(M1,K)∩M2]∪[E(M2,K)∩M1].Proof.
Notice that(M1∩M2)+K0⊆(M1+K0)∩(M2∩K0). 							(30)E(M1∩M2,K)=(M1∩M2)∖[(M1∩M2)+K0]⊇(M1∩M2)∖[(M1+K0)∩(M2+K0)]=(M1∩M2)∩(M1+K0)∩(M2+K0)¯=(M1∩M2)∩[M1+K0¯∪M2+K0¯]=[(M1∩M2)∩M1+K0¯]∪[(M1∩M2)∩M2+K0¯]=[E(M1,K)∩M2]∪[E(M2,K)∩M1].Remark 16.
(i) Usually the equality does not hold in Proposition15. Let M1={(x,y)∣0≤x≤y≤1}, M2={(x,y)∣0≤x-1/2≤y≤1}. Then
(31)E(M1∩M2,K)={(1/2,1/2)},[E(M1,K)∩M2]∪[E(M2,K)∩M1]=∅,
(ii) for Proposition15, if (M1∩M2)+K0=(M1+K0)∩(M2+K0), then
(32)E(M1∩M2,K)=[E(M1,K)∩M2]∪[E(M2,K)∩M1],
(iii) since M1∖M2=M1∩M2¯, Proposition 11 can be obtained by Proposition 15.


## 3. Efficiency of Four Most Representative DEA Models

For each of DEA models, Charnes et al. and Wei et al. (e.g., see [5, 7, 9]) establish an associative multiobjective linear programming model and prove that a DMUj0 is DEA efficient if and only if (xj0,yj0) (associating with the DMUj0) is a Pareto efficient solution of the multiobjective linear programming problem (for the details about DEA efficient of DMUs in DEA model, see [4, 5] and the references therein). This beautiful conclusion provides the multiobjective linear programming as an efficient tool to solve DEA problems. So the key point now is to find all efficient solutions of the multiobjective linear programming problems. This section offers a simple way to do this.By the results of Section2, in the following, we investigate the multiobjective linear programming problems corresponding to the four DEA models and develop the structures of the efficient point sets and the efficient solution sets of these programmings. Based on these, the relationships between the DEA efficiency of the four DEA models are obtained.Denotexj=(x1j,…,xmj)>0(xj∈Rm) to be the input vector for the jth decision making unit (DMUj), and yj=(y1j,…,ysj)>0(yj∈Rs), to be the output vector for the jth decision making unit, for j=1,…,n. For convenience the notations x0=xj0,y0=yj0, for 1≤j0≤n are given. Let C=R+m⊂Rm,  and let D=R+s⊂Rs. The orderings in Rm and Rs are defined by C and D, respectively. K={(c,d)∣c∈C,d∈D},K1={(c,-d)c∈C,d∈D}, K0=K∖{0}, and K10=K1∖{0. The production possibility set T,T⊂{(x,y)∣x∈Rm,y∈Rs,x≥0,y≥0}, is based on postulate sets which are presented with a brief explanation (see [4, 5]). The four most representative models are, briefly, C2R,BC2,FG, and ST, which correspond to different production possibility sets TC2R, TBC2, TFG, and TST, respectively, [4–10]
(33)TC2R={(x,y)∣∑j=1n‍xjλj≤x,∑j=1n‍yjλj≥y≥0,λj≥0,j=1,…,n},TBC2={(x,y)∣∑j=1n‍xjλj≤x,∑j=1n‍yjλj≥y≥0,∑j=1n‍λj=1,λj≥0,j=1,…,n},TFG={(x,y)∣∑j=1n‍xjλj≤x,∑j=1n‍yjλj≥y≥0,∑j=1n‍λj≤1,λj≥0,j=1,…,n},TST={(x,y)∣∑j=1n‍xjλj≤x,∑j=1n‍yjλj≥y≥0,∑j=1n‍λj≥1,λj≥0,j=1,…,n}.Obviously, the following equalities and inclusions hold:(34)(a)TC2R=TFG∪TST,(b)TBC2=TFG∩TST,(c)TC2R⊇TFG⊇TBC2,(d)TC2R⊇TST⊇TBC2.For distinguishing the DEA efficiency of DMUs in DEA models, according to the equivalence of DEA efficiency in DEA models and Pareto efficiency in multiobjective linear programming obtained by Charnes et al. and Wei et al., we introduce the multiobjective linear programming problem corresponding to DEA models in the following. For the details about DEA models, see [7, 8].Consider multiobjective linear programming problem:(VP)V-min(x,-y),s.t.(x,y)∈T.
For T=TC2R, TBC2, TFG, or TST, the four multiobjective linear programming problems VPC2R, VPBC2, VPFG, and VPST correspond to the four DEA models respectively.Definition 17.
(
x
0
,
y
0
) is called an Pareto efficient (weak efficient) solution of (VP), if there is no (x,y)∈T, (x,y)≠(x0,y0) such that
(35)(x,-y)≤(x0,-y0),((x,-y)<(x0,-y0)).
SinceK defines the ordering in Rm+s(⊃T), the previous inequality can be written as
(36)(x0,-y0)∈(x,-y)+K0,((x0,-y0)∈(x,-y)+intK).
When K is a convex pointed cone, all conclusions in Section 2 hold for multiobjective programming problem (VP). Theorem 18 provides the equivalency of DEA efficiency of DMUs and the Pareto efficiency of the points corresponding to the DMUs. Consequently, the structures of the sets of efficient solutions to DEA models are obtained by solving the multiobjective programmings. Then the relationships between the DEA efficiencies of DMUs in DEA models are deduced.Theorem 18 (see [5]).
ADMUj0 is DEA efficient if and only if (x0,y0) is a Pareto efficient solution of (VP).For convenience, we denote byDMU0DMUj0. In the following, we investigate the structures of the efficient point sets and the efficient solution sets of the four vector optimization problems. Let(37)M0={(xj,-yj)∣j=1,…,n},T0={(xj,yj)∣j=1,…,n},MC2R={(x,-y)∣(x,y)∈TC2R},MBC2={(x,-y)∣(x,y)∈TBC2},MFG={(x,-y)∣(x,y)∈TFG},MST={(x,-y)∣(x,y)∈TST}.
The relations (a), (b), (c), and (d) imply:
(38)(a-)MC2R=MFG∪MST,(b-)MBC2=MFG∩MST,(c-)MC2R⊇MFG⊇MBC2,(d-)MC2R⊇MST⊇MBC2.As an example, consider the multiobjective linear programming problem(VPC2R). Let EC2R denote the efficient point set, and let SC2R denote the efficient solution set. Note that
(39)(x,-y)≤(x0,-y0)⟺(x0,-y0)∈(x,-y)+K.
By Definitions 2 and 17,
(40)EC2R=M0∖(MC2R+K0).
Since
(41)(x0,-y0)∈(x,-y)+K0⟺(x0,y0)∈(x,y)+K10,
we have
(42)SC2R=T0∖(TC2R+K10).
Similar argument is applied to other three multiobjective linear programming problems. Therefore the following two theorems hold.Theorem 19.
Consider the following:(43)(a--)EC2R=M0∖(MC2R+K0),(b--)EBC2=M0∖(MBC2+K0),(c--)EFG=M0∖(MFG+K0),(d--)EST=M0∖(MST+K0).Theorem 20.
Consider the following:(44)(a---)SC2R=T0∖(TC2R+K10),(b---)SBC2=T0∖(TBC2+K10),(c---)SFG=T0∖(TFG+K10),(d---)SST=T0∖(TST+K10).Inclusions(c), (d) and Theorem 20 imply Theorem 21.Theorem 21.
Consider the following:(45)(i)SC2R⊆SFG⊆SBC2,(ii)SC2R⊆SST⊆SBC2.Theorem21 shows the relationships between the solutions of the four vector optimization problems. Therefore, by Theorem 18, the relationships between DEA efficiencies of DMUs in DEA models are as the following:(i)
if DMU0 is C2R DEA efficient, then it is FG DEA efficient. If DMU0 is FG DEA efficient, then it is B2C DEA efficient;(ii)
if DMU0 is C2R DEA efficient, then it is ST DEA efficient. If DMU0 is ST DEA efficient, then it is B2C DEA efficient.By Proposition13, along with the equality (a-) and (a--), we obtain following Theorem 22.Theorem 22.
Consider the following:(46)EC2R=[M0∖(MFG+K0)]∖(MST+K0)=[M0∖(MST+K0)]∖(MFG+K0)=EFG∖(MST+K0)=EST∖(MFG+K0).By Theorem22, we conclude that if EC2R≠ϕ, then EFG≠ϕ and EST≠ϕ; by (a---), (c---), and (d---), we declaim that if DMU0 is C2R DEA efficient, then it is also FG DEA efficient and ST DEA efficient.Proposition15 and (b-) infer Theorem 23.Theorem 23.
Consider the following:(47)EBC2⊇(EFG∩MST)∪(EST∩MFG).Consider thatEFG=M0∖(MFG+K0), and M0⊂MST, if EFG≠ϕ, then EFG∩MST≠ϕ. Similarly, EST∩MFG≠ϕ. Therefore, the following consequences are obtained:(i)
if DMU0 is ST DEA efficient, then it is also BC2 DEA efficient;(ii)
if DMU0 is FG DEA efficient, then it is also BC2 DEA efficient.


## 4. Conclusion

In this paper, Definition2 presents a new representation to E(M,K). Then some new properties of E(M,K) are deduced by the new representation (Propositions 6 to 15 and their corollaries). Most of the properties are proved by mean of the binary operations of sets, which is a new method in multiobjective optimization. These conclusions are used to deal with the multiobjective linear programming problems corresponding to the four most representative DEA models. We investigate the structures of the efficient solution set of the four DEA models (Theorems 19 and 20) and deduce the relationships between DEA efficient solution sets of the four DEA models (Theorems 21 and 22). For each of the four DEA models, by Theorem 20, S=T0∖(T+K10); that is, all the DEA efficient DMUs are obtained by the binary operations of sets. Therefore, this is a simple way to get all DEA efficient DMUs theoretically. By using the new representation, it may be able to discuss the effects upon DEA efficiency of DMUs when the number of the DMUs changes in DEA models.



---

*Source: 607829-2013-03-31.xml*