Portfolio problems with two levels decision-makers: Optimal portfolio selection with pricing decisions on transaction costs

Portfolio problems with two levels decision-makers: Optimal portfolio selection with pricing decisions on transaction costs Marina Leal † ‡ Diego Ponce †§ Justo Puerto †‡ Abstract. This paper presents novel bilevel leader-follower portfolio selection problems in which the financial intermediary becomes a decision-maker. This financial intermediary decides on the unit transaction costs for investing in some securities, maximizing its benefits, and the investor chooses his optimal portfolio, minimizing risk and ensuring a given expected return. Hence, transaction costs become decision variables in the portfolio problem, and two levels of decision-makers are incorporated: the financial intermediary and the investor. These situations give rise to general Nonlinear Programming formulations in both levels of the decision process. We present different bilevel versions of the problem: financial intermediary-leader, investor-leader, and social welfare; besides, their properties are analyzed. Moreover, we develop Mixed Integer Linear Programming formulations for some of the proposed problems and effective algorithms for some others. Finally, we report on some computational experiments performed on data taken from the Dow Jones Industrial Average, and analyze and compare the results obtained by the different models. Keywords: Finance, Portfolio Optimization, Bilevel Optimization, Transaction Costs, Conditional Value at Risk (CVaR) 1 Introduction The classical model in portfolio optimization was originally proposed by Markowitz in 1952 [28]. This model has served as the initial point for the development of modern portfolio theory. Over time, portfolio optimization problems have become more realistic, incorporating real-life aspects that make the resulting portfolios more cost-effective than the alternatives that do not consider them [8, 13, 21, 24, 26]. Transaction costs can be seen as one of these important actual features to be included in portfolio optimization. These costs are those incurred by the investors when buying and selling assets on financial markets, charged by the brokers, the financial institutions or the market makers playing the role of intermediary. Transaction costs usually include banks and brokers’ commissions, fees, etc. These commissions or fees have a direct impact on the portfolio, especially for individual or small investors, since they will determine the net returns, reducing them and decreasing also the budget available for future investments [3, 4, 19]. To the best of our knowledge, in the existing literature, transaction costs are assumed to be given [10, 15, 20, 22, 24, 26, 30]. They can be a fixed cost applied to each selected security in the portfolio; or a variable cost to be paid which depends on the amount invested in each security included in the portfolio ∗This research has been funded by the Spanish Ministry of Science and Technology project MTM2016-74983-C2-1-R. †Institute of Mathematics of the University of Seville (IMUS), Spain ‡Department of Statistics and Operations Research, Faculty of Mathematics, University of Seville, Spain §CIRRELT and Department of Mechanical, Industrial and Aerospace Engineering, Faculty of Engineering and Computer Science, Concordia University, Montreal, Canada. 1 (see e.g. [3, 4, 11, 24, 26, 36, 37] and the references therein). This dependence can be proportional to the investment or given by a fixed cost that is only charged if the amount invested exceeds a given threshold, or by some other functional form (see e.g. [4, 14, 17, 24, 26] and the references therein). But in any case, unit transaction costs are known and predetermined in the optimization process. Nevertheless, it is meaningful to analyze the situations where transaction costs can be decision variables set by financial institutions so that they are trying to maximize its profit as part of the decision process that leads to optimal portfolios for the investors. The portfolio optimization problem considered in this paper is based on a single-period model of investment and incorporates a transaction costs setting phase. We assume that there are two decision-makers involved in the situation: on the one hand, the investor and on the other hand, the broker specialist, market maker or financial institution (that we will call from now on, for simplicity broker-dealer). At the beginning of a period, an investor allocates his capital among various assets and during the investment period, each asset generates a random rate of return. Moreover, we consider that the broker-dealer can charge some unit transaction costs on the securities selected by the investor trying to maximize its benefits but anticipating the rational response of the investor. This is a pricing phase in which the broker-dealer decides on how much is going to charge to the investor for the traded securities. Considering unit transaction costs as a decision variable of the model is a novel element in portfolio optimization and this is one of the main contributions of this paper. Then, at the end of the period, the result for the investor is a variation of his capital (increased or decreased) which is measured by the weighted average of the individual rates of return minus commissions or fees. In addition, the result for the broker-dealer is the amount paid by the investor, which depends on the revcosts set on the traded securities included in the portfolio chosen by the investor. Based on the structure of financial markets, we assume a hierarchical relationship between the parties involved in the portfolio problem, that is, we define a natural problem in which the broker-dealer sets the unit transaction costs first, trying to anticipate the rational response of the investor. This hierarchical analysis of the portfolio problem has not been addressed before and it is another contribution of our paper. Once the costs are fixed, the investor chooses his optimal portfolio. For the sake of completeness, we also analyze the case in which the investor chooses his portfolio first, and after that, the broker-dealer sets the transaction costs. In order to model these hierarchical structures, we use a bilevel optimization approach (see e.g. [2, 9, 16, 35]). Furthermore, we consider a social welfare problem where both, broker-dealer and investor, cooperate to maximize their returns. We assume in the different problems that all economic or financial information is common knowledge and that all the decision-makers in the problem have access to it. The contributions of this paper can be summarized as follows: 1) it incorporates for the first time the above hierarchical approaches with two-levels of decision-makers on portfolio optimization problems (the broker-dealer sets unit transaction costs trying to maximize its benefits, whereas the investor minimizes risk while ensuring a given expected return [5, 6]); 2) it introduces transaction costs as decision variables controlled by the broker-dealer; and 3) it develops different bilevel programming formulations to obtain optimal solutions for the considered problems. This paper introduces new models for the bilevel portfolio optimization problem. As far as we know, bilevel models for the portfolio selection that set unit transaction costs as decision variables of the problem have not been considered in the literature before. The rest of the paper is organized as follows. Section 2 states the preliminaries and the notation used throughout the paper. In Section 3, we present the problem in which the broker-dealer is the leader and we develop two different Mixed Integer Linear Programming (MILP) formulations to solve such problem. Section 4 introduces the investor-leader problem and develops a Linear Programming (LP) formulation for it. In the more general case where additional constraints are required on the portfolio selection, it is presented 2 a convergent iterative algorithm based on an “ad hoc” decomposition of the model. Next, in Section 5, it is addressed a social welfare problem . There, we propose a MILP formulation and an algorithm based on Benders decomposition for solving it. Section 6 is devoted to reporting on the computational study of the different problems and solution methods discussed in the previous sections. Our results are based on data taken from Dow Jones Industrial Average. Finally, Section 7 concludes the paper. 2 Preliminaries Let N={1, ..., n}be the set of securities considered for an investment, B⊆Na subset of securities in which the broker-dealer can charge unit transaction costs to the investor and R:=N\ {B}. In most cases, B=N, but there is no loss of generality to consider that Bis a proper subset of N. First, we assume that the broker-dealer can price security j∈Bfrom a discrete set, with cardinality sj, of admissible costs, Pj={cj1, ..., cjsj}, and the broker-dealer’s goal is to maximize its benefit. Further, we consider proportional transaction costs: the cost charged by the broker-dealer per security is proportional to the amount invested in such security. Hence, the broker-dealer’s decision variables are unit transaction costs (commissions, fees, ...) to be charged (proportionally) to the securities. Let x= (xj)j=1,...,n denote a vector of decision variables: xjbeing the weight of security jin the portfolio. We only assume that the invested capital can not exceed the available budget and non-negativity, i.e., x: n X j=1 xj≤1, xj≥0,for j= 1, ..., n. This budget constraint is the minimum requirement on the structure of the portfolios. Nevertheless and without loss of generality, we could have assumed that some other linear constraints are imposed on the structure of the requested portfolio x. All the results in this paper can be easily extended to more general situations that consider polyhedral sets of constraints defining the admissible set of portfolios. Let us denote by pjthe unit transaction cost chosen by the broker-dealer to charge security j,j∈B. Then, for a given portfolio x(fixed), the problem faced by the broker-dealer can be modeled using the following set of binary decision variables: ajk = 1 if cost cjk is assigned to pj, this is, if pj=cjk;ajk = 0 otherwise. Thus, to maximize his profit the broker-dealer solves the following problem: max X j∈B pjxj(PricP) s.t. pj= sj X k=1 cjkajk, j ∈B, (1) sj X k=1 ajk = 1, j ∈B, (2) ajk ∈ {0,1}, j ∈B, k = 1, ..., sj.(3) If no further constraints are imposed on costs the above is a valid formulation. However, in general, we will assume without loss of generality that the set of costs for the broker-dealer can be restricted to belong 3 to some polyhedron P, allowing P=R|B| +. This can be easily included in the above formulation with the following constraint: p∈P.(4) We observe that, if xis known, and constraint (4) is not included, the above problem is easy to solve (see Proposition 3): the broker-dealer will set transaction costs to the maximum ones among those available for each security. Nevertheless, if the portfolio is unknown (to be decided by the investor) or additional constraints, such as regulation constraints, are imposed into the model, the problem becomes more difficult to be solved, since there exists no explicit expression for an optimal solution. Moreover, we suppose that the investor wants to reduce the risk of his investment while ensuring a given expected return. At this point, several risk measures could be considered, among them variance of returns, Mean Absolute Deviation (MAD), Conditional Value at Risk (CVaR), Gini’s Mean Difference, etcetera. (Here, we refer the reader to [23] for further details on the topic.) In this paper, we have focused on a portfolio optimization problem based on the CVaR risk measure. This risk measure aims to avoid large losses: for a specific probability level α, the CVaR measures the conditional expectation of the smallest returns with a cumulative probability α, that is, the average return of the given size (quantile) of worst realizations [23, 33, 34]. Therefore, we assume that the investor’s goals are to maximize its CVaR and, at the same time, to ensure that a minimum expected reward µ0is obtained with his portfolio. There exist in the literature different ways of accounting for the transaction costs into the portfolio model [26, 27]. For instance, including them in the objective function [1, 31, 37], subtracting them from the expected return [12, 25], reducing the capital available for the investment [37], etcetera. We assume in our approach that transaction costs are directly removed from the expected return. In order to model the above situation, we consider that the rate of return of each security j∈Nis represented by a random variable Rjwith a given mean µj=E(Rj). Each portfolio xdefines a random variable Rx=Pn j=1 Rjxjthat represents the portfolio rate of return (its expected value can be computed as µ(x) = Pn j=1 µjxj). We consider Tscenarios, each of them with probability πt,t= 1, ..., T , and assume that for each random variable Rjits realization, rjt, under the scenario tis known. Thus, once the broker-dealer has set the transaction costs, p, the realization of the portfolio rate of return Rxunder scenario tis given as yt=Pn j=1 rjtxj−Pi∈Bpixi. With this information, we assume that the investor wants to maximize the CVaRα, namely the conditional expectation of the smallest returns with cumulative probability α, while ensuring a minimum expected return µ0. Thus, the portfolio optimization problem that the investor wants to solve can be formulated as: max η−1 α T X t=1 πtdt(CVaRP) s.t. yt= n X j=1 rjtxj−X i∈B pixi, t = 1, ..., T, (5) T X t=1 πtyt≥µ0,(6) dt≥η−yt, t = 1, ..., T, (7) dt≥0, t = 1, ..., T, (8) n X j=1 xj≤1,(9) 4 xj≥0, j = 1, ..., n, (10) Observe that ηis a continuous variable that models the αValue at Risk,V aRα, namely the value of the minimum threshold for which the probability of the scenarios with a return less than or equal to ηis at least α. Next, (5) and (6) are the scenario constraints. Constraint (5) gives the expected return in each scenario. Note that, the expected return in each scenario is for the net rate of returns, Pn j=1 rjtxj, minus the transaction rates Pi∈Bpixi. Whereas constraint (6) ensures an expected return of, at least, µ0. The objective function and the set of constraints (7) and (8) model the CVaR (see Mansini et. al [23] for details). And finally, the sets of constraints (9) and (10) force xto define a portfolio. We note also that by choosing different values for the parameters αand µ0, in the formulation above, different types of investors (i.e., different levels of attitude towards risk) can be incorporated in the model. 3 Bilevel broker-dealer-leader Investor-follower Portfolio Problem (BLIFP) We start analyzing a hierarchical structure in the financial markets in which the broker-dealer sets the transaction costs first, and after that, the investor chooses his portfolio. Observe that in this situation, the problem faced from the investor point of view reduces to a portfolio selection, under the considered criterion, which in this case is to hedge against risk maximizing the average α-quantile of his smallest returns (CVaRα). Therefore, we study this situation from the point of view of both the financial intermediary and the investor, simultaneously, which is a novel perspective. We model the situation as a bilevel leader-follower problem in which the broker-dealer has to fix the transaction costs, from the polyhedral set P∈R|B|, maximizing his benefits by assuming that, after his decision is made, the investor will choose his optimal portfolio. Using the bilevel optimization framework, the BLIFP can be modeled as follows: max X j∈B pjxj(BLIFP0) s.t. (1),(2),(3),(4),(Bank Constraints) x∈arg max η−1 α T X t=1 πtdt, s.t. (5),(6),(7),(8),(9),(10).(Investor Constraints) Our goal is to solve the above bilevel programming model to provide answers to the new portfolio optimization problem. We propose two different MILP formulations with the aim of making a computational comparison to check which one is more effective. 5 3.1 Formulation BLIFP1 The main difficulty in handling BLIFP0 is that some of its decision variables are constrained to be optimal solutions of a nested optimization problem. In order to overcome that issue we observe that the follower problem in BLIFP0 is linear on xwhen pis given. This allows us to easily compute its exact dual as: min β+µ0µ(Dual1) s.t. β− T X t=1 (rjt −pj)δt≥0, j ∈B, (11) β− T X t=1 rjtδt≥0, j ∈R, (12) − T X t=1 γt= 1,(13) γt≥ −πt α, t = 1, ..., T, (14) γt+δt+πtµ= 0, t = 1, ..., T, (15) γt≤0, t = 1, ..., T, (16) µ≤0, β ≥0.(17) We note in passing that variables δt,µ,γtand β, are the dual variables associated to constraints (5), (6), (7) and (9), respectively. Therefore, they can be interpreted as multipliers explaining the marginal variation of the objective function values as a function of the corresponding constraints’ right-hand-sides. Nevertheless, we do not go into details in the economic insights of this dual model, since our use is instrumental to obtain a single level reformulation of the hierarchical model. Then, BLIFP0 can be reformulated, applying the Strong Duality Theorem, including the constraints of the primal and dual problem together with the equation that matches the objective values of the follower primal and dual problems. Thus, BLIFP0 is equivalent to solving this new mathematical programming model: max X j∈B pjxj s.t. (1),(2),(3),(4),(Bank Constraints) η−1 α T X t=1 πtdt=β+µ0µ, (18) (5),(6),(7),(8),(9),(10),(Investor Constraints) (11),(12),(13),(14),(15),(16),(17).(Dual Constraints) We can observe that in the above formulation we have some bilinear terms, pjxjand pjδtthat appear in the leader objective function and constraints (5) and (11). In order to solve the problem using off-the-shelf 6 solvers, they can be linearized ‘a la’ McKormick, [29], giving rise to another exact MILP formulation for the bilevel problem. Indeed, since pj=Psj k=1 cjkajk,∀j∈B, we could substitute the terms pjxj=Psj k=1 cjkˆajk adding variables ˆajk,∀j∈B, k = 1, ..., sj,and the following set of constraints: ˆajk ≤xj, j ∈B, k = 1, ..., sj, ˆajk ≤ajk, j ∈B, k = 1, ..., sj, ˆajk ≥xj−(1 −ajk), j ∈B, k = 1, ..., sj, ˆajk ≥0, j ∈B, k = 1, ..., sj. (19) Furthermore, this linearization can be simplified. Observe that it is sufficient to include in (BLIFP0) variables ˆajk and constraints ˆajk ≤ajk, j ∈B, k = 1, ..., sj, ˆajk ≥0, j ∈B, k = 1, ..., sj,(20) from (19) and to substitute the variables xj=Psj k=1 ˆajk,∀j∈B. We obtain in this manner an equivalent, smaller formulation with the bilinear terms ajkxjlinearized for all j∈B, k = 1, ..., sj, but with less constraints and decision variables. Following a similar argument we can linearize the products pjδt=Psj k=1 cjkajkδt. To do that, take Ma sufficiently large positive number and define the new variables ˆ δjkt =ajkδt,∀j∈B, k = 1, ..., sj, t = 1, ..., T. This set of variables together with the following family of constraints linearize all the bilinear terms: ˆ δjkt ≤δt, j ∈B, k = 1, ..., sj, t = 1, ..., T, ˆ δjkt ≤Majk, j ∈B, k = 1, ..., sj, t = 1, ..., T, ˆ δjkt ≥δt−(1 −ajk)M, j ∈B, k = 1, ..., sj, t = 1, ..., T, ˆ δjkt ≥0, j ∈B, k = 1, ..., sj, t = 1, ..., T. (21) Combining the above elements, all together, we obtain a valid MILP formulation for BLIFP: max X j∈B sj X k=1 cjkˆajk (BLIFP1) s.t. sj X k=1 ajk = 1, j ∈B, (2) ajk ∈ {0,1}, j ∈B, k = 1, ..., sj,(3) η−1 α T X t=1 πtdt=β+µ0µ(18) yt=X j∈B rjt sj X k=1 ˆajk!+X j∈R rjtxj−X j∈B sj X k=1 cjkˆajk, t = 1, ..., T, (22) 7 T X t=1 πtyt≥µ0,(6) dt≥η−yt, t = 1, ..., T, (7) dt≥0, t = 1, ..., T, (8) X j∈B sj X k=1 ˆajk +X j∈R xj≤1,(23) xj≥0, j ∈R, (10) ˆajk ≤ajk, j ∈B, k = 1, ..., sj, ˆajk ≥0, j ∈B, k = 1, ..., sj,(20) β− T X t=1 rjtδt− sj X k=1 cjk ˆ δjkt!≥0, j ∈B, (24) β− T X t=1 rjtδt≥0, j ∈R, (12) − T X t=1 γt= 1,(13) γt≥ −πt α, t = 1, ..., T, (14) γt+δt+πtµ= 0, t = 1, ..., T, (15) γt≤0, t = 1, ..., T, (16) µ≤0, β ≥0,(17) ˆ δjkt ≤δt, j ∈B, k = 1, ..., sj, t = 1, ..., T, ˆ δjkt ≤Majk, j ∈B, k = 1, ..., sj, t = 1, ..., T, ˆ δjkt ≥δt−(1 −ajk)M, j ∈B, k = 1, ..., sj, t = 1, ..., T, ˆ δjkt ≥0, j ∈B, k = 1, ..., sj, t = 1, ..., T. (21) The above long formulation can be easily understood once the different sets of constraints are grouped by meaningful blocks. We observe that (2), (3) and (4) are the constraints that define the feasible domain of the broker-dealer problem. Constraint (18) imposes the strong duality condition among the primal and dual formulation of the follower problem. Next, (22), (6), (7), (8), (23), (10) and (20) are the constraints that correctly define the linearized version of the investor subproblem. Finally, the constraints that come from the linearized version of the dual of the follower problem are (24),(12), (13), (14), (15), (16), (17) and(21). Using these blocks of constraints BLIFP1 can be written in the following compact form. max X j∈B sj X k=1 cjkˆajk (BLIFP1) s.t. (2),(3),(4),(Linear broker-dealer Constraints) (18),(Strong Duality Constraint) (22),(6),(7),(8),(23),(10),(20),(Linear investor Constraints 1) (24),(12),(13),(14),(15),(16), (17),(21).(Linear Dual Constraints) 8 This valid formulation of BLIFP1 requires to set a valid value for the big-Mconstraint. Setting an appropriate value is important to improve the performance of the resulting MIP. In the following, we prove the existence of a valid upper bound for such a value. Proposition 1. Let B(p)be the set of all full rank submatrices of the matrix representing the constraints of problem Dual1 in standard form, where pis a fixed set of cost values, and let BS(p) be the set of all matrices that result from B(p)replacing, one each time, their columns by the RHS of that problem. Moreover, let ∆(p) := min{|det(B)|:B∈ B(p)}and ∆S(p) = max{|det(B)|:B∈ BS(p)}. Then UBδ:= max p∆S(p)/∆(p)is a valid upper bound for the big-Mconstant in BLIFP1. Proof. It is easy to observe that for each fixed set of costs p,M≤maxt=1,...,T δt. Therefore the proof reduces to bound the terms δt. From constraint (15) in formulation Dual1 we know that δt=−γt−πtµ, ∀t= 1, ..., T, which implies that δt≥0 for all t= 1, ..., T, since µ≤0, and δt≤0, and πt≥0 for all t= 1, ..., T. We observe that β+µ0µis bounded for any µ0and for any set of costs p(recall that this o.f. gives a CVaR). If we denote by rmax = max j=1,...,n,t=1,...,T rjt,rmin = min j=1,...,n,t=1,...,T rjt and cmax = max j=1,...,n, k=1,...,sj cjk, then rmin −cmax ≤β+µ0µ≤rmax. This implies that the solution of Dual1 is attained at an extreme point and therefore no rays have to be considered. Next, the extreme points of the feasible regions are solutions of systems of full dimensional equations taken from the constraint matrix of Dual1 in standard form. Therefore, applying Cramer’s rule we obtain that, at the extreme points, the values of any variable δtfor all t= 1, . . . , T satisfy: δt≤∆S(p)/∆(p). Next, letting pvary on the finite set of possible costs we obtain that δt≤max p∆S(p)/∆(p). This bound is only of theoretical interest and in our computational experiments, we have set it empirically to be more accurate. 3.2 Formulation BLIFP2 In this section, we derive an alternative formulation for BLIFP based on the representation of the costs as pjxj=Psj k=1 cjkˆajk in the follower problem before its dual problem is obtained. This artifact produces an alternative single level model that we will analyze in the following. Let us consider the CVaR problem in BLIFP0, and let us linearize the products of variables pixi, as in the previous formulation. This way we obtain: max η−1 α T X t=1 πtdt s.t. yt=X j∈B rjt sj X k=1 ˆajk!+X j∈R rjtxj−X j∈B sj X k=1 cjkˆajk, t = 1, ..., T, (22) T X t=1 πtyt≥µ0,(6) 9 pτ∈arg max X j∈B pjxτ−1 j s.t. (1),(2),(3),(4).(Broker-dealer Constraints) To complete the proof we need to check that constraint (5) is also satisfied. Since pτ∈arg max X j∈B pjxτ−1 j, then Pj∈Bpτ jxτ−1 j≥Pj∈Bpjxτ−1 jfor any cost pverifying (1), (2), (3) and (4). Using the same arguments that in Theorem 1 it follows that variable λis being minimized in ILBFP-Incompleteτ, thus λτ=Pj∈Bpτ jxτ−1 jand then constraint (5) holds. 5 The Maximum Social Welfare Problem (MSWP) In some actual situations, the investor and the broker-dealer may have an incentive to work together to improve the social welfare of society. They can agree to cooperate and share risk and benefits to improve, in this way, their solutions by designing a joint strategy. We also analyze this problem for the sake of completeness and to compare the performance of this situation where none of the parties has a hierarchical position over the other one. We think that even if the actual implementation of the cooperative model may be difficult, in a competitive actual market, one may gain some insights into the problem through analysis. In the social welfare model, we assume that both, broker-dealer and investor, cooperate. Let 0 < ξ < 1 be the marginal rate of substitution between the two objectives. That is, the rate at which one of the parties can give up some units of one of the objective functions in exchange for another unit of the other one while maintaining the same overall value. Then, the cooperative version of the problem can be written as a weighted sum of the two objective functions of each party in the feasible region delimited by the constraints of both problems: max ξX j∈B pjxj+ (1 −ξ) η−1 α T X t=1 πtdt! s.t. (1),(2),(3),(4),(Broker-dealer Constraints) (5),(6),(7),(8),(9),(10).(Investor Constraints) The above problem can be modeled as a MILP by linearizing the products of variables ajkxj,∀j∈B following the same scheme as in Section 3: max ξX j∈B sj X k=1 cjkˆajk + (1 −ξ) η−1 α T X t=1 πtdt!(MSWP0) 16 s.t. (2),(3),(4),(Linear broker-dealer Constraints) (22),(6),(7),(8),(23),(10),(20).(Linear investor Constraints 1) For simplicity, in the remaining, we consider an unweighted maximum social welfare model where the two objective functions Pj∈BPsj k=1 cjkajk (broker-dealer) and η−1 αPT t=1 πtdt(investor) are simply added. The following result proves that cooperation is always profitable for both parties in that the joint return exceeds the sum of individual returns of each of them. Proposition 4. An optimal solution of the unweighted maximum social welfare problem induces an objective value that is greater than or equal to the sum of the optimal returns of the two parties in the same bilevel problem in any of the hierarchical problems. Proof. Any feasible solution of BLIFP0 and ILBFP0 is feasible in MSWP0 since all the constraints in this last problem appear in the two former formulations. Therefore, the feasible region of MSWP0 includes the feasible regions of both, BLIFP0 and ILBFP0 and the result follows. 5.1 Benders decomposition We can also obtain a Benders decomposition, [7], in order to state a Benders like algorithm to solve MSWP0, and compare the performance of both proposed methods to solve the problem. Recall that the unweighted maximum welfare problem can be written as: max X j∈B pjxj+ η−1 α T X t=1 πtdt! s.t. (1),(2),(3),(4),(Broker-dealer Constraints) (5),(6),(7),(8),(9),(10).(Investor Constraints) In order to apply Benders decomposition we reformulate MSWP0 as follows: max X j∈B sj X k=1 cjkˆajk +q(y) (MSWP1) s.t. (2),(3),(4) (Linear broker-dealer Constraints) ˆajk ≤ajk, j ∈B, k = 1, ..., sj, ˆajk ≥0, j ∈B, k = 1, ..., sj,(20) yt=X j∈B rjt sj X k=1 ˆajk!+X j∈R rjtxj−X j∈B sj X k=1 cjkˆajk, t = 1, ..., T, (22) T X t=1 πtyt≥µ0,(6) 17 X j∈B sj X k=1 ˆajk +X j∈R xj≤1,(23) xj≥0, j ∈R, (10) where q(y) = max η−1 α T X t=1 πtdt s.t.: dt−η≥ −yt, t = 1, ..., T, dt≥0, t = 1, ..., T. Note that in q(y) we are essentially computing the CVaR for the given solution {yt:t= 1, . . . , T}. Computing again its dual problem, the evaluation of q(y) can also be obtained as: q(y) = min T X t=1 −γtyt(PrimalP) s.t.: γt≥−πt α, t = 1, ..., T, − T X t=1 γt= 1, γt≤0. Observe that the above problem, which we define as the Primal Problem, is a continuous knapsack problem with lower bounds, therefore it is well known that it can be solved by inspection. It suffices to sort non-increasingly the ytvalues and assigning, in that order, to each variable γtthe minimum feasible amount. Note that in the above formulation the feasible region does not depend on the variables in MSWP1, so if we denote by Ω the set of extreme point solutions of the feasible region of PrimalP,q(y) is equivalent to: q(y) = max q s.t. q≤ T X t=1 −γτ tyt, γτ∈Ω.(32) Therefore, the problem MSWP0 with discrete costs can be written as: max X j∈B sj X k=1 cjkˆajk +q(MasterP) 18 s.t. (2),(3),(4) (Linear broker-dealer Constraints) ˆajk ≤ajk, j ∈B, k = 1, ..., sj, ˆajk ≥0, j ∈B, k = 1, ..., sj,(20) yt=X j∈B rjt sj X k=1 ˆajk!+X j∈R rjtxj−X j∈B sj X k=1 cjkˆajk, t = 1, ..., T, (22) T X t=1 πtyt≥µ0,(6) X j∈B sj X k=1 ˆajk +X j∈R xj≤1,(23) xj≥0, j ∈R, (10) q≤ T X t=1 γτyt, γτ∈Ω.(32) This analysis allows us to state a Benders algorithm as follows: Benders Algorithm: Initialization Choose a solution y0of the master problem, solve the primal problem PrimalP for the chosen y0. Let γ0be an optimal solution for PrimalP under y0and q(y0) the corresponding optimal value. Take Υ={γ0}and go to iteration τ= 1. Iteration τ= 1,2, . . . Solve the master problem MasterP replacing Ω with Υ. Let y∗and q∗be optimal solutions of such problem. •If τ= 1 and q(y0) = q∗. END. •If τ > 1 and q(y∗) = q∗. END. •Otherwise, solve the primal problem PrimalP for y=y∗. Let γ∗be an optimal solution of such problem. Take γτ=γ∗,Υ=Υ∪ {γτ}, and go to iteration τ:= τ+ 1. 6 Computational study and empirical application This section is devoted to reporting some numerical experiments conducted to: 1) compare the effectiveness of the methods proposed to solve the different problems; 2) analyze the form of the solutions within each model; and 3) compare the profiles of the solutions, in terms of net values for the broker-dealer and expected return for the investor, across the three defined problems. The computational experiments were carried out on a personal computer with Intel(R) Core(TM) i7- 2600 CPU, 3.40GHz with 16.0 GB RAM. The algorithms and formulations were implemented and solved by using Xpress IVE 8.0. In order to conduct the computational study, we take historical data from Dow Jones Industrial Average. We considered daily returns of the 30 assets during one year (T= 251 scenarios), and these Thistorical 19 periods are considered as equiprobable scenarios (πt= 1/T). Furthermore, to perform a richer comparison, we consider different types of instances for the broker-dealer sets of possible transaction costs and different risk profiles for the investor. We assume that the broker-dealer charges transaction costs in a subset Bof the securities. In the instances we generated we compare the following cardinals for the set B:|B|= 30,20,10. In addition, each cost pj, j ∈Bwas chosen from a discrete set Pj={cj1, ..., cjsj}of admissible values . These parameters sj were randomly generated in the interval [0, K] with K= 5,15,50. The next table gathers the nine different types of instances (A to I) considered in our computational study: K= 5 K= 15 K= 50 |B|= 30 A B C |B|= 20 D E F |B|= 10 G H I Table 2: Types of instances for the sets of possible costs depending on the values of |B|and K Once the set Band the parameter sjwere set for each type of instance (A-I), we generate the possible transaction costs cij as follows: •randomly generated in the interval [0.001,0.003] (cheaper costs) in approximately 15% of the securities, •randomly generated in the interval [0.002,0.008] (normal costs) in approximately 70% of the securities, •randomly generated in the interval [0.006,0.010] (more expensive costs) in approximately 15% of the securities. For each type of instance defined in Table 2, five different instances are generated and the average values are reported in all the tables and figures. Different investor profiles are also considered varying the values of parameters µ0and α. We assume three thresholds for the expected return µ0= 0.0,0.05,0.1. This way, we are modeling investors willing not to lose anything, or to win at least, 5% or 10% of their invested amount. In addition, we consider five different CVaR risk levels, α= 0.01,0.05,0.5,0.9. Note that usually, the smaller the α, the higher the risk-aversion. 6.1 Comparing solution methods This section compares the computational performance of the different methods proposed to solve each one of the problems. For the first problem, BLIFP, we proposed two different formulations: BLIFP1 and BLIFP2. We show in all our tables, the average CPU time expressed in seconds (CPU) and the number of instances (#) solved to optimality (out of 5) for each formulation, with a time limit of 3600 seconds. 20 Table 3 is organized in three blocks of rows. Each block reports results for µ0= 0.0,0.05,0.1, respectively. Each row in the table refers to a type of instance (A, . . . , I). The columns are also organized in four blocks. Each block reports the results for a different risk level (α). It can be observed that BLIFP2 is always faster and it solves a higher number of problems than BLIFP1 to optimality. As anticipated in Section 3.2 this behavior is explained by the smaller dimension of BLIFP2 in terms of variables and constraints. For example, when α= 0.5 and µ= 0.0, BLIFP2 is able to solve all the instances of types D and H in few seconds, while BLIFP1 is not able to solve any of these instances. Therefore, we conclude that formulation BLIFP2 is more effective than BLIFP1 for solving BLIFP. The second problem in our analysis is the one presented in Section 4, namely ILBFP. For this situation, we have proposed a single level LP formulation ILBFP-LP and Algorithm 1 to solve the problem. We report the results concerning this model (when no additional constrains on transaction costs are imposed in the set of costs) in Table 4. It can be observed that the compact formulation is faster than the algorithm: all the instances can be solved by using the LP formulation in less than 7 seconds, meanwhile, the algorithm needs more than 100 seconds to solve some of them. However, the Algorithm 1 is also able to solve all the instances, and, as discussed in Section 4, it can also be used when more general sets of costs are considered. Finally, for the social welfare problem, MSWP, we have also proposed another single level formulation MSWP0 and a Benders’ like algorithm. The primal problems in the Benders Algorithm were solved by using the inspection method described in the previous section. We report the results concerning this model in Table 5 with the same layout as Table 4. It can be observed that again the compact formulation is much faster than the algorithm. In spite of that, the algorithm is also able to solve the considered instances. 21 α= 0.05 α= 0.1α= 0.5α= 0.9 µ0BLIFP1 BLIFP2 BLIFP1 BLIFP2 BLIFP1 BLIFP2 BLIFP1 BLIFP2 CPU # CPU # CPU # CPU # CPU # CPU # CPU # CPU # 0A3600 0 181 5 3600 0 916 4 3600 0 3291 1 3600 0 5 5 B3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3079 1 C3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 D3600 0 2 5 3204 1 17 5 3600 0 59 5 1603 3 2 5 E3600 0 890 4 3600 0 2024 3 3600 0 3377 1 1882 3 3 5 F3600 0 2895 1 3600 0 3600 0 3600 0 3600 0 2984 1 76 5 G841 5 1 5 375 5 1 5 810 5 1 5 571 5 1 5 H2282 2 2 5 3117 1 2 5 3600 0 7 5 2178 2 1 5 I2959 1 1444 3 3600 0 1562 3 3600 0 939 4 1804 3 5 5 0.05 A3600 0 28 5 3600 0 343 5 3600 0 3291 1 3156 1 5 5 B3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3079 1 C3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 D3600 0 2 5 3204 1 3 5 3600 0 59 5 2217 2 2 5 E3600 0 110 5 3600 0 1923 3 3600 0 3377 1 1793 3 3 5 F3600 0 2905 1 3600 0 3600 0 3600 0 3600 0 2930 1 76 5 G841 5 1 5 375 5 1 5 810 5 1 5 62 5 1 5 H2282 2 1 5 3117 1 2 5 3600 0 7 5 153 5 1 5 I2959 1 930 4 3600 0 1575 3 3600 0 939 4 2439 2 5 5 0.1 A3600 0 6 5 3600 0 23 5 3600 0 3291 1 3156 1 5 5 B3600 0 616 5 3600 0 1326 4 3600 0 3600 0 3600 0 3079 1 C3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 3600 0 D3600 0 1 5 3204 1 2 5 3600 0 59 5 2217 2 2 5 E3600 0 24 5 3600 0 55 5 3600 0 3377 1 1793 3 3 5 F3600 0 1277 4 3600 0 2227 2 3600 0 3600 0 2930 1 76 5 G841 5 1 5 375 5 1 5 810 5 1 5 62 5 1 5 H2282 2 1 5 3117 1 1 5 3600 0 7 5 153 5 1 5 I2959 1 1477 3 3600 0 736 4 3600 0 939 4 2439 2 5 5 Table 3: Comparison of the average CPU and number of instances (out of 5) solved to optimality, for BLIFP1 and BLIFP2 22 α= 0.05 α= 0.1α= 0.5α= 0.9 µ0LP Alg. 1 LP Alg. 1 LP Alg. 1 LP Alg. 1 0.0 A0.55 4.76 0.57 17.85 0.56 54.62 0.54 19.29 B1.51 12.64 1.61 50.68 1.60 144.21 1.49 47.97 C6.42 44.94 6.61 178.84 6.19 557.45 5.98 187.49 D0.39 6.80 0.41 12.09 0.42 40.26 0.42 13.18 E1.03 36.98 1.02 29.99 1.03 95.80 0.99 32.80 F3.26 24.52 3.31 86.80 3.31 298.50 3.23 89.21 G0.25 2.83 0.25 8.73 0.25 26.00 0.25 8.45 H0.47 3.99 0.47 14.37 0.48 46.73 0.46 15.32 I1.63 13.59 1.63 45.47 1.64 149.62 1.59 49.73 0.05 A0.55 4.76 0.57 17.85 0.56 54.62 0.54 19.29 B1.51 12.64 1.61 50.68 1.60 144.21 1.49 47.97 C6.42 44.94 6.61 178.84 6.19 557.45 5.98 187.49 D0.39 6.80 0.41 12.09 0.42 40.26 0.42 13.18 E1.03 36.98 1.02 29.99 1.03 95.80 0.99 32.80 F3.26 24.52 3.31 86.80 3.31 298.50 3.23 89.21 G0.25 2.83 0.25 8.73 0.25 26.00 0.25 8.45 H0.47 3.99 0.47 14.37 0.48 46.73 0.46 15.32 I1.63 13.59 1.63 45.47 1.64 149.62 1.59 49.73 0.1 A0.55 4.76 0.57 17.85 0.56 54.62 0.54 19.29 B1.51 12.64 1.61 50.68 1.60 144.21 1.49 47.97 C6.42 44.94 6.61 178.84 6.19 557.45 5.98 187.49 D0.39 6.80 0.41 12.09 0.42 40.26 0.42 13.18 E1.03 36.98 1.02 29.99 1.03 95.80 0.99 32.80 F3.26 24.52 3.31 86.80 3.31 298.50 3.23 89.21 G0.25 2.83 0.25 8.73 0.25 26.00 0.25 8.45 H0.47 3.99 0.47 14.37 0.48 46.73 0.46 15.32 I1.63 13.59 1.63 45.47 1.64 149.62 1.59 49.73 Table 4: Comparison of the average CPU for ILBFP-LP and Algorithm 1 α= 0.05 α= 0.1α= 0.5α= 0.9 µ0MSWP0 Ben. MSWP0 Ben. MSWP0 Ben. MSWP0 Ben. 0A0.55 4.76 0.57 17.85 0.56 54.62 0.54 19.29 B1.51 12.64 1.61 50.68 1.60 144.21 1.49 47.97 C6.42 44.94 6.61 178.84 6.19 557.45 5.98 187.49 D0.39 6.80 0.41 12.09 0.42 40.26 0.42 13.18 E1.03 36.98 1.02 29.99 1.03 95.80 0.99 32.80 F3.26 24.52 3.31 86.80 3.31 298.50 3.23 89.21 G0.25 2.83 0.25 8.73 0.25 26.00 0.25 8.45 H0.47 3.99 0.47 14.37 0.48 46.73 0.46 15.32 I1.63 13.59 1.63 45.47 1.64 149.62 1.59 49.73 0.05 A0.55 4.76 0.57 17.85 0.56 54.62 0.54 19.29 B1.51 12.64 1.61 50.68 1.60 144.21 1.49 47.97 C6.42 44.94 6.61 178.84 6.19 557.45 5.98 187.49 D0.39 6.80 0.41 12.09 0.42 40.26 0.42 13.18 E1.03 36.98 1.02 29.99 1.03 95.80 0.99 32.80 F3.26 24.52 3.31 86.80 3.31 298.50 3.23 89.21 G0.25 2.83 0.25 8.73 0.25 26.00 0.25 8.45 H0.47 3.99 0.47 14.37 0.48 46.73 0.46 15.32 I1.63 13.59 1.63 45.47 1.64 149.62 1.59 49.73 0.1 A0.55 4.76 0.57 17.85 0.56 54.62 0.54 19.29 B1.51 12.64 1.61 50.68 1.60 144.21 1.49 47.97 C6.42 44.94 6.61 178.84 6.19 557.45 5.98 187.49 D0.39 6.80 0.41 12.09 0.42 40.26 0.42 13.18 E1.03 36.98 1.02 29.99 1.03 95.80 0.99 32.80 F3.26 24.52 3.31 86.80 3.31 298.50 3.23 89.21 G0.25 2.83 0.25 8.73 0.25 26.00 0.25 8.45 H0.47 3.99 0.47 14.37 0.48 46.73 0.46 15.32 I1.63 13.59 1.63 45.47 1.64 149.62 1.59 49.73 Table 5: Comparison of the average CPU for MSWP0 and Benders Algorithm 23 6.2 Comparing solutions and risk profiles within problems This section analyzes the results provided by the two hierarchical problems in terms of broker-dealer’s net profit and risk and expected return attained by the investor. Figure 1 compares the CVaR values obtained for the different risk profiles for BLIFP. Each piecewise curve reports the CVaR values for different α-levels and µ0-levels and the nine market profiles (A, . . . , I). We observe that the CVaR always increases with the value of α, since this implies assuming more risk. It can also be seen in these figures that, when the value of αincreases, the CVaR for the different values of µ0becomes closer for each value of α. This can be explained because when α= 1, if the constraint that the expected return must be greater or equal to 0 is satisfied, both problems become the same, then, the bigger the αthe more similar the results for different values of µ0. Furthermore, for a given α, the CVaR for smaller µ0is higher because in these cases the constraint on the expected return enlarges the feasible region as compared with higher values of µ0. A B C D E F G H I −1.5 −1 −0.5 0 α:0.05, μ:0.0 α:0.05, μ:0.05 α:0.05, μ:0.1 α:0.1, μ:0.0 α:0.1, μ:0.05 α:0.1, μ:0.1 α:0.5, μ:0.0 α:0.5, μ:0.05 α:0.5, μ:0.1 α:0.9, μ:0.0 α:0.9, μ:0.05 α:0.9, μ:0.1 INSTANCE CVaR Figure 1: Values of the CVaR for BLIFP, for different αand µ0levels Figure 2 compares, with a similar organization as Figure 1, the broker-dealer net profit for different investor’s risk profiles. Analogously, Figure 3 represents the expected return for the investor. We observe in Figure 2 that the results of the broker-dealer net profit are bigger, in trend, for profiles with smaller values of α, that is, for more risk-averse investments. In addition, we also show in Figure 3 that, in general, bigger expected returns are obtained for higher values of α. The reason for this is that by increasing αone is considering a wider range of values to compute the CVaR, and then the result is a value closer to the expected return (note that when α= 1 the expected return is equal to the CVaR). 24 A B C D E F G H I 0 0.02 0.04 0.06 0.08 0.1 α:0.05, μ:0.0 α:0.05, μ:0.05 α:0.05, μ:0.1 α:0.1, μ:0.0 α:0.1, μ:0.05 α:0.1, μ:0.1 α:0.5, μ:0.0 α:0.5, μ:0.05 α:0.5, μ:0.1 α:0.9, μ:0.0 α:0.9, μ:0.05 α:0.9, μ:0.1 INSTANCE Broker-dealer Profit Figure 2: Values of the broker-dealer profit for BLIFP, for different values αand µ0levels A B C D E F G H I 0 0.05 0.1 0.15 0.2 α:0.05, μ:0.0 α:0.05, μ:0.05 α:0.05, μ:0.1 α:0.1, μ:0.0 α:0.1, μ:0.05 α:0.1, μ:0.1 α:0.5, μ:0.0 α:0.5, μ:0.05 α:0.5, μ:0.1 α:0.9, μ:0.0 α:0.9, μ:0.05 α:0.9, μ:0.1 INSTANCE Expected Return Figure 3: Values of the expected return for BLIFP, for different αand µ0levels Finally, to conclude with the analysis of BLIFP, we remark that the smaller the cardinality of the set B the better the CVaR and expected returns for the investor, but the worse the broker-dealer net profit. This is expected since we are reducing the number of securities where the broker-dealer could charge transaction costs. We proceed next to analyze the solutions of the second problem, namely ILBFP. We observe in Figure 25 [22] M. J. Magill and G.M. Constantinides. Portfolio selection with transactions costs. Journal of economic theory, 13(2), 245-263. 1976 [23] R. Mansini, W. Ogryczak, and M.G. Speranza. On LP Solvable Models for Portfolio Selection. Informatica, Vol. 14, No. 1, 37–62. 2003. [24] R. Mansini, W. Ogryczak, and M.G. Speranza. Twenty years of linear programming based on portfolio optimization. European Journal of Operational Research. Vol. 234, Issue 2, 518-535. 2014. [25] R. Mansini and M.G. Speranza. An exact approach for portfolio selection with transaction costs and dounds. IIE Transactions, 37, 919-929. 2005. [26] R. Mansini, W. Ogryczak, and M.G. Speranza.Portfolio Optimization and Transaction Costs, in Quantitative Financial Risk Management: Theory and Practice (eds C. Zopounidis and E. Galariotis), John Wiley, and Sons, Inc, Hoboken, NJ, USA. 2015. [27] R. Mansini, W. Ogryczak, and M.G. Speranza. Linear and Mixed Integer Programming for Portfolio Optimization. Springer, Berlin. 2015. [28] H. M. Markowitz. Portfolio selection. Journal of Finance, 7, 77–91. 1952. [29] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Mathematical programming, 10(1), 147-175. 1976. [30] A. J. Morton and Pliska, S. R. Optimal portfolio management with fixed transaction costs. Mathematical Finance, 5(4), 337-356. 1995. [31] A. V. Olivares-Nadal and V. DeMiguel. A Robust Perspective on Transaction Costs in Portfolio Optimization. Operations Research, 66(3):733-739. 2018. [32] W. Ogryczak, and T. Sliwinski. On efficient optimisation of the CVaR and related LP computable risk measures for portfolio selection. Mathematical and Statistical Methods for Actuarial Sciences and Finance. Springer, Milano. 2010. [33] J. Puerto, A.M. Rodr´ıguez-Ch´ıa, and A. Tamir, Revisiting k-sum Optimization, Mathematical Programming 165, 579–604. 2017. [34] R.T. Rockafellar and S. Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 21-41. 2000. [35] A. Sinha, M. Pekka, and D. Kalyanmoy. A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation 22.2: 276-295. 2017. [36] C.A.Valle, N.Meade, and J.E.Beasley. Absolute return portfolios. Omega, 45, 20-41. 2014. [37] M. Woodside-Oriakhi, C. Lucas, and J.E. Beasley. Portfolio rebalancing with an investment horizon and transaction costs. Omega, 41(2), 406–420. 2013. 32