2 Motivation

In this section, we will explain the main weaknesses of the SWP and MOOP. The main motivation for developing the NSWP is to overcome these weaknesses.

2.1 The multi-objective optimization program

In general, when solving the MOOP, decision makers are only interested in the so-called Pareto-optimal solutions (see Definition 2.1).

Definition 2.1. A feasible solution $\boldsymbol {x}\in \mathcal {X}$ is called Pareto-optimal if there is no other $\boldsymbol {x}'\in \mathcal {X}$ such that

$$ \begin{align*} f_i(\boldsymbol{x})& \leq f_i(\boldsymbol{x}') \quad \text{for all } i \in S^+,\\ f_i(\boldsymbol{x}) &\geq f_i(\boldsymbol{x}') \quad \text{for all } i \in S^-,\\ f_i(\boldsymbol{x}) &\ne f_i(\boldsymbol{x}') \quad \text{there exists } i \in S^+\cup S^-. \end{align*} $$

The image of each Pareto-optimal solution in the criterion space is called a Pareto-optimal point. The set of all Pareto-optimal points, also known as the Pareto-optimal frontier, shows the trade-off between the objectives. An illustration of the trade-off of the MOOP involving only two objectives (in the form of maximization) can be found in Figure 1.

Figure 1

An illustration of a Pareto-optimal frontier with two (maximization) objective functions in the criterion space.

A typical challenge when dealing with the MOOP is to answer “how should a Pareto-optimal solution be selected for implementation in practice?” A natural answer to this question is that modellers have no responsibility in identifying a desirable solution and the decision makers (or managers) are expected to do that in practice. In other words, modellers need to compute the trade-off (between Pareto-optimal solutions) and ask the decision makers to select the one which is suitable. Such a process is typically implemented using either a two-phase approach or a step-by-step approach. In the two-phase approach, the complete trade-off will be computed in the first phase and then the entire information will be sent to the decision makers. However, the step-by-step approach is interactive in the sense that at each iteration, one (or some) Pareto-optimal solutions will be computed by the modellers and then the opinions of the decision makers will be obtained. If the decision makers are happy with the provided solution(s), then the search terminates, otherwise the search will be modified for finding some other Pareto-optimal solutions (if any). This process repeats until a desirable solution is found.

Although the approaches described above are useful in many practical situations for selecting a desirable Pareto-optimal solution, they do not work in many other situations, because they suffer from two main weaknesses described in the following.

Weakness 2.2. In some practical situations, computing even a single Pareto-optimal solution is computationally infeasible (or expensive). So, selecting a desirable Pareto-optimal solution using the existing approaches will be infeasible.

Weakness 2.3. In some practical situations, either there is no decision maker or the decision maker(s) do not know how to select a desirable solution [Reference Jorge8]. So, selecting a desirable Pareto-optimal solution using the existing approaches will be infeasible.

For Weakness 2.2, a possible remedy is to employ heuristic or evolutionary solution methods. However, inexact methods do not guarantee optimality and may perform poorly. More importantly, they still do not address Weakness 2.3. Our proposed technique in this study, that is, the NSWP, addresses both weaknesses at the same time, because it is designed to directly generate a Pareto-optimal solution (see Proposition 3.3) that can create a desirable balance between the objectives.

2.2 The social welfare program

To explain the main weaknesses of the SWP, we first show that the SWP itself is trying to solve the MOOP. Observe that the MOOP can be written in the following form:

$$ \begin{align*} \begin{aligned} \max\quad & \{\kern1.8pt f_i(\boldsymbol{x})\mid i\in S^+\},\\ \max\quad & \{-f_i(\boldsymbol{x})\mid i\in S^-\} , \\ \mbox{subject to}\quad & \boldsymbol{x}\in \mathcal{X}. \end{aligned} \end{align*} $$

Now, a popular solution technique to deal with the MOOP is to aggregate its objective functions with some positive weights, and then solve the following single-objective optimization problem instead:

(2.1) $$ \begin{align} \begin{aligned} \max \bigg \{\sum_{i\in S^+} w_i\,f_i(\boldsymbol{x})- \sum_{i\in S^-} w_i\,f_i(\boldsymbol{x})\; \bigg| \;\boldsymbol{x}\in \mathcal{X} \bigg \}. \end{aligned} \end{align} $$

Equation (2.1) is sometimes called the weighted sum optimization in the literature of multi-objective optimization [Reference Ehrgott7]. We can observe that the weighted sum optimization is precisely equation (1.1), because $S^+=[1, p']$ and $S^-=[\kern1.5pt p'+1, p]$ . Therefore, when modellers are trying to solve the SWP, they are basically trying to find a desirable Pareto-optimal solution for equation (1.2) by setting the weight of $f_i(\boldsymbol {x})$ to $w_i$ for all $i\in [1, p]$ . In other words, they implicitly have p criteria in their mind, that is, $f_1(\boldsymbol {x})$ , …, $f_p(\boldsymbol {x})$ with $w_1,\ldots ,w_p$ as their corresponding degrees of importance.

Given that the SWP can be viewed as an approach for computing a desirable Pareto-optimal solution for the MOOP, it is natural to ask whether it actually results in finding a desirable solution in practice. Note that one may argue that the SWP can remove Weaknesses 2.2 and 2.3 that the MOOP causes. While for many practical situations this can be indeed true, we will argue in the rest of this section that the SWP should be generally avoided, because it may not generate a desirable Pareto-optimal solution, that is, it may not provide a good balance between the values of different objectives in practice.

Weakness 2.4. For nonconvex multi-objective optimization problems, there can exist many (and possibly infinite) Pareto-optimal points that cannot be obtained by optimizing a (positive) weighted summation of all objective functions over the feasible set (even by testing all possible positive weights). Such points are called unsupported Pareto-optimal points [Reference Ehrgott7]. So, a weakness of the SWP is that it completely ignores the existence of unsupported Pareto-optimal points that can possibly better balance different objectives.

To better understand Weakness 2.4, consider Figure 1 again. In the figure, we have $p=2$ and $S^-=\emptyset $ , that is, there are two objectives in the form of maximization. It is not hard to see that if we use the SWP, then we will find either the point (2,5.5) or point (5.5,2) for any possible values of $w_1$ and $w_2$ (note that $w_1,w_2>0$ ). So, none of the three middle points can be obtained using the SWP because they are unsupported Pareto-optimal points. Observe that this can be problematic (in some practical cases) because from the view point of multi-objective optimization, those middle points balance the conflicting objectives better than the endpoints.

Weakness 2.5. In many practical situations,  $f_1(\boldsymbol {x}), \ldots , f_p(\boldsymbol {x})$  represent the objective functions of p independent players (or components) of an environment (or system). So, by developing the SWP for such cases, a modeller is basically trying to coordinate these players with respect to their powers, denoted by  $w_1,\ldots , w_p$ , and make sure that the benefit of the system is distributed (almost) fairly among players with respect to their powers. However, a weakness of the SWP is that it does not necessarily ensure the fairness.

By fairness, we mean less extreme solutions in which the total cost (or gain) of the system is distributed among the players according to their powers (or contributions). To explain Weakness 2.5 better, consider Figure 1 again where $p=2$ and $S^-=\emptyset $ . We know that in this example, we will find either the point (2,5.5) or (5.5,2) for any possible values of $w_1$ and $w_2$ . So, suppose that $w_1=w_2=1$ . In this case, both (2,5.5) and (5.5,2) are optimal, and so the SWP returns one of them randomly. However, the powers of the players are exactly the same. So no matter which point is returned by the SWP, it will not be fair and make (one of) the players unhappy. For this particular example, we can easily see that the point (3.25,3) is indeed the only fair point that can make both players happy at the same time. Overall, our proposed technique in this study, that is, the NSWP, addresses both Weaknesses 2.4 and 2.5 at the same time, because it is designed to directly generate a Pareto-optimal solution that can create a desirable balance between the objectives.

2.3 A practical example

To better illustrate the weaknesses mentioned earlier, we now provide a (simplified) real-world problem (or scenario). In the field of conservation planning, one of the most important problems is the so-called reserve selection problem [Reference Sierra-Altamiranda, Charkhgard, Eaton, Martin, Yurek and Udell20]. Suppose that there are n parcels of land, and parcel $j\in [1,n]$ has an associated cost denoted by $c_j$ . As a modeller, you have a budget, denoted by b, to spend on buying some of these parcels and you want to develop an optimization model that can help natural resource managers to identify which parcels should be selected to be reserved. Suppose that there are (in total) p species where $S^+$ represents the index set of engendered (or important species) and $S^-$ represents the index set of invasive species. Accruing parcel $j\in [1,n]$ has an impact on species $i\in [1,p]$ , for example, increases its population size, which is denoted by parameter $u_{ij}\ge 0$ . Observe that for this problem, we have

$$ \begin{align*} \mathcal{X}=\bigg\{\boldsymbol{x}\in\{0,1\}^n\; \bigg| \sum_{j=1}^n c_jx_j\le b\bigg\}, \end{align*} $$

where $x_j$ is a binary variable that shows whether parcel j should be bought or not. Also, for each species $i\in [1,p]$ , we have

$$ \begin{align*} f_i(\boldsymbol{x})=\sum_{j=1}^n u_{ij}x_j. \end{align*} $$

Modellers in the field of conservation planning address the problem mentioned above by either using the SWP or the MOOP [Reference Sierra-Altamiranda, Charkhgard, Eaton, Martin, Yurek and Udell20]. However, it is easy to see that if they use the MOOP, Weaknesses 2.2 and 2.3 can arise when n and p are large, respectively. Also, if they use the SWP, Weakness 2.4 can arise because this problem is nonconvex. Moreover, Weakness 2.5 can arise because the modeller is indeed working on a system where each species is a player on its own.

3 The Nash social welfare program

The underlying idea of the NSWP comes from the field of cooperative game theory. A well-known problem in the field of cooperative game theory is the so-called bargaining problem. The bargaining problem is a game in which all (competing) players agree to create a grand coalition, instead of competing with each other to get a higher payoff [Reference Charkhgard, Savelsbergh and Talebian5, Reference Serrano19]. To be able to create a grand coalition, the agreement of all players is necessary. Therefore, the main concern when dealing with a bargaining problem is what the payoff for each player should be in a grand coalition (and how it should be computed). One of the well-known solution techniques to this problem, introduced by Nash [Reference Nash14] and extended further by Kalai [Reference Kalai9], is what we use in this paper. Specifically, we assume that there are p number of (imaginary) players and each player $i\in S^+ \cup S^-$ has an objective function $f_i(\boldsymbol {x})$ . Note that $|S^+ \cup S^-|=p$ . Hence, we try to create a coalition between these players by solving the following optimization problem:

(3.1) $$ \begin{align} \begin{aligned} \max\quad & \prod_{i\in S^+} (\kern1.8pt f_i(\boldsymbol{x})-d_i)^{w_i} \times \prod_{i\in S^-}(d_i-f_i(\boldsymbol{x}))^{w_i}\\ \mbox{subject to}\quad & \boldsymbol{x}\in \mathcal{X},\\ & f_i(\boldsymbol{x})\ge d_i \quad \text{for all } i\in S^+,\\ & f_i(\boldsymbol{x})\le d_i \quad \text{for all } i\in S^-, \end{aligned} \end{align} $$

where $\boldsymbol {d}\in \mathbb {R}^{p}$ is the reference point, an input parameter for the NSWP. The reference point in the literature of the bargaining problem is sometimes referred to as the disagreement point and it basically indicates the payoff of each player under no coalition. We will later in Section 3.1 explain some natural choices for the reference point (if it is unknown to modellers). The following remark is helpful.

The objective function of equation (3.1) is basically the (weighted) Nash social welfare function which is why we refer to equation (3.1) as the NSWP. Note that since player $i\in S^+$ is interested in maximizing its objective function, $(\kern1.8pt f_i(\boldsymbol {x})-d_i)$ captures the benefit that it will obtain as the result of creating a coalition (with respect to the reference point). Similarly, since player $i\in S^-$ is interested in minimizing its objective function, $(d_i-f_i(\boldsymbol {x}))$ captures the benefit that it obtains as the result of creating a coalition (with respect to the reference point). So, the (weighted) Nash social welfare function is the product of benefits of players (considering their negotiating powers/weights) and the goal of the NSWP is to maximize the value of this function.

Proof. Suppose that $\boldsymbol {x}^*$ is an optimal solution of the NSWP, but it is not a Pareto-optimal solution. By definition of Pareto-optimality (Definition 2.1), this implies that there must exist a feasible solution denoted by $\boldsymbol {x}\in \mathcal {X}$ that dominates $\boldsymbol {x}^*$ , that is,

$$ \begin{align*} f_i(\boldsymbol{x}^*) &\leq f_i(\boldsymbol{x}) \quad \text{for all } i \in S^+,\\ f_i(\boldsymbol{x}^*) &\geq f_i(\boldsymbol{x}) \quad \text{for all } i \in S^-,\\ f_i(\boldsymbol{x}^*) &\ne f_i(\boldsymbol{x}) \quad \text{there exists } i \in S^+\cup S^-. \end{align*} $$

In addition, by assumptions, we have $w_i> 0$ for all $i\in [1,p]$ . This, combined with Assumption 3.2, implies that

$$ \begin{align*} 0<\prod_{i\in S^+} (\kern1.8pt f_i(\boldsymbol{x}^*)-d_i)^{w_i} \times \prod_{i\in S^-}(d_i-f_i(\boldsymbol{x}^*))^{w_i} < \prod_{i\in S^+} (\kern1.8pt f_i(\boldsymbol{x})-d_i)^{w_i} \times \prod_{i\in S^-}(d_i-f_i(\boldsymbol{x}))^{w_i}. \end{align*} $$

Consequently, $\boldsymbol {x}^*$ cannot be an optimal solution, which is a contradiction.

To illustrate what the NSWP actually does, consider the same example described in Figure 1 where $S^-_i=\emptyset $ and $S^+_i=\{1,2\}$ . Suppose that $w_1=w_2=1$ and $\boldsymbol {d}=(2,2)$ . The Pareto-optimal point that NSWP selects for this example is $(3.25,3.5)$ , as shown in Figure 2, which is not only an unsupported Pareto-optimal point, but also the only fair Pareto-optimal point from the view point of both players. Note that since $w_1=w_2=1$ , we observe that, geometrically, the NSWP attempts to find a Pareto-optimal point such that the area of the box between this point and $\boldsymbol {d}$ is maximized. In other words, the objective function of the NSWP captures the area of the box. The green box (online) in Figure 2 shows the box with the maximum area. The following propositions and remark are also helpful.

Figure 2

Selection of the Pareto-optimal point by the NSWP. (Colour available online.)

Proof. Using the notation presented in Section 4, we just need to show that

$$ \begin{align*} \max_{\boldsymbol{y}\in \mathcal{Y}}\ \prod_{i\in S^+\cup S^-} y_i^{\alpha w_i} \end{align*} $$

is equivalent to equation (4.1). This immediately follows from two observations: first, equation (4.1) is equivalent to equation (4.2). Second, by multiplying the objective function of equation (4.2) by a positive constant, that is, $\alpha $ , an equivalent problem can be constructed.

Note that from Proposition 3.4, one can also infer that the NSWP with equal negotiating powers, that is, $w_i=w_j$ for all $i,j\in S^+\cup S^-$ , is equivalent to the NSWP with unit negotiating powers, that is, $w_i=1$ for all $i\in S^+\cup S^-$ .

Proposition 3.5. The NSWP is local-benefit-scale-free, that is, by replacing the objective function of the NSWP with the following function:

(3.2) $$ \begin{align} \max \ \prod_{i\in S^+} (\alpha_i\,f_i(\boldsymbol{x})-\alpha_i d_i)^{w_i} \times \prod_{i\in S^-}(\alpha_i d_i-\alpha_i\,f_i(\boldsymbol{x}))^{w_i}, \end{align} $$

an equivalent problem will be constructed where $\alpha _1, \ldots , \alpha _p$ are arbitrary positive constants.

Proof. Observe that equation (3.2) is equivalent to

$$ \begin{align*} \begin{aligned} \max\quad & \prod_{i=1}^p \alpha_i^{w_i} \times \prod_{i\in S^+} (\kern1.8pt f_i(\boldsymbol{x})- d_i)^{w_i} \times \prod_{i\in S^-}(d_i-f_i(\boldsymbol{x}))^{w_i}. \end{aligned} \end{align*} $$

Since $\prod _{i=1}^p \alpha _i^{w_i}$ is a positive constant, it has no impact on the optimization and can be dropped.

Again note that in the NSWP, the term $(\kern1.8pt f_i(\boldsymbol {x})- d_i)$ captures the benefit of player $i\in S^+$ and the term $(d_i-f_i(\boldsymbol {x}))$ captures the benefit of player $i\in S^-$ with respect to the reference point. In Proposition 3.5, if we set

$$ \begin{align*} \alpha_i= & \frac{1}{\max_{\boldsymbol{x}\in \mathcal{X}'} \ f_i(\boldsymbol{x})-d_i} \quad \text{for all } i\in S^+,\\ \alpha_i= & \frac{1}{\max_{\boldsymbol{x}\in \mathcal{X}'} \ d_i-f_i(\boldsymbol{x})} \quad \text{for all } i\in S^-, \end{align*} $$

where

$$ \begin{align*}\mathcal{X}'=\{\boldsymbol{x}\in \mathcal{X}\mid f_i(\boldsymbol{x})\ge d_i \text{ for all } i\in S^+ , \mbox{ and }\, f_i(\boldsymbol{x})\le d_i \text{ for all } i\in S^- \},\end{align*} $$

then the maximum benefit that each player can obtain will be precisely one in the equivalent problem. This implies that from any NSWP, an equivalent NSWP with unit-maximum-benefit can be constructed, because for each $i\in [1,p]$ , $\alpha _if_i(\boldsymbol {x})$ and $\alpha _id_i$ can be viewed as the new $f_i(\boldsymbol {x})$ and the new $d_i$ , respectively.

In summary, the NSWP is a single-objective optimization problem. It resolves Weakness 2.2, because it returns a single Pareto-optimal solution (just like the SWP) if being solved to optimality (see Proposition 3.3). Evidently, generating only a single Pareto-optimal solution can decrease the computational time significantly. Even for the cases where the NSWP is computationally expensive, one can develop a heuristic method for finding high-quality feasible solutions for it. The NSWP resolves Weakness 2.3, because it generally tries to avoid the endpoints of the Pareto-optimal frontier and generates a good balance between objectives (which is generally for what decision makers look). The NSWP resolves Weakness 2.4 because it does not ignore unsupported Pareto-optimal points and its output can be even an unsupported Pareto-optimal point. Finally, the NSWP resolves Weakness 2.5 because it attempts to ensure that the benefits are distributed fairly (based on Remark 3.6) with respect to the power of players. Specifically, if the negotiating powers are equal, then the NSWP attempts to create equality in benefits. Otherwise, it attempts to deviate from the equality based on the power of players.

3.1 The reference point

As mentioned earlier, in the context of game theory, the reference point should denote the payoff of each player under no coalition, that is, the status quo of the game. While in many applications the reference point can be identified easily, in some cases, it is not clear how the reference point should be determined. For such cases, one natural choice for the reference point can be the so-called nadir point, that is, a point in the criterion space that denotes the worst value for each objective function in the Pareto-optimal frontier. Note that the nadir point is not necessarily a feasible point, that is, it may lie outside the feasible region in the criterion space. For example, in Figure 2, both objectives are in the form of maximization. So, the worst value for both $f_1(x)$ and $f_2(x)$ in the Pareto-optimal frontier is 2. Hence, the nadir point is (2,2).

However, computing the nadir point could be computationally expensive, especially for cases with $p>2$ . For cases with $p=2$ , the nadir point can be generated by computing the two endpoints of the Pareto-optimal frontier (see Figure 2). However, for cases with $p>2$ , this is not necessarily true in general [Reference Ehrgott7]. Hence, alternatively, one can set the reference point to an approximation of the nadir point. For example, for each $i\in S^+$ , one can set

$$ \begin{align*} \begin{aligned} d_i=\min\,\{\kern1.8pt f_i(\boldsymbol{x})\mid \boldsymbol{x}\in \mathcal{X} \} \quad \text{or} \quad d_i=\min\,\{\kern1.8pt f_i(\boldsymbol{x})\mid \boldsymbol{x}\in \mathcal{X}^R \}, \end{aligned} \end{align*} $$

where $\mathcal {X}^R$ is a relaxation of $\mathcal {X}$ , for example, linear programming relaxation. Similarly, for each $i\in S^-$ , one can set

$$ \begin{align*} \begin{aligned} d_i=\max \,\{\kern1.8pt f_i(\boldsymbol{x})\mid \boldsymbol{x}\in \mathcal{X} \} \quad \text{or} \quad d_i=\max \,\{\kern1.8pt f_i(\boldsymbol{x})\mid \boldsymbol{x}\in \mathcal{X}^R \}. \end{aligned} \end{align*} $$

We complete this section by emphasizing that the reference point is an input parameter for the NSWP. The choice of this point does highly impact the solution obtained by solving the problem. In particular, a poor choice of the reference point could result in a solution which does not necessarily resolve all the weaknesses mentioned in this paper. Therefore, the reference point should be selected with care and by considering the particular problem to which it is applied.

4 Solution methods for the Nash social welfare program

Observe that, in the NSWP, we have $f_i(\boldsymbol {x})-d_i\ge 0$ for all $i\in S^+$ , because $f_i(\boldsymbol {x})\ge d_i$ . Similarly, we have $d_i-f_i(\boldsymbol {x})\ge 0$ for all $i\in S^-$ , because $f_i(\boldsymbol {x}) \le d_i$ . Hence, for notational convenience, let

$$ \begin{align*} \begin{aligned} \mathcal{Y}=\big\{&\,\boldsymbol{y}\in \mathbb{R}^p\mid \boldsymbol{x}\in \mathcal{X},\\ & \,y_i=f_i(\boldsymbol{x})-d_i \mbox{ and } y_i\ge 0 \text{ for all } i\in S^+,\\ &\,y_i=d_i- f_i(\boldsymbol{x}) \mbox{ and } y_i\ge 0 \text{ for all } i\in S^-\big\}, \end{aligned} \end{align*} $$

be the feasible set of the NSWP in the criterion space. Using this notation, the NSWP can be rewritten as

(4.1) $$ \begin{align} \begin{aligned} \max_{\boldsymbol{y}\in \mathcal{Y}}\ \prod_{i\in S^+\cup S^-} y_i^{w_i}. \end{aligned} \end{align} $$

We now describe a few solution approaches for solving the NSWP using Assumption 4.1. The first approach is straightforward. It applies the log-transformation to the objective function of the NSWP. So, the NSWP can be rewritten as follows:

(4.2) $$ \begin{align} \begin{aligned} \max_{\boldsymbol{y}\in \mathcal{Y}}\ \sum_{i\in S^+\cup S^-} w_i\log (y_i). \end{aligned} \end{align} $$

Observe that equation (4.2) is basically maximizing a concave function over a mixed integer convex set (due to Assumption 4.1). So, the first approach calls a mixed integer convex programming solver to solve equation (4.2).

The second approach applies piecewise linearization techniques to first linearize the log functions in equation (4.2), and then call a (mixed) integer convex/linear programming solver to solve the linearized problem [Reference Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang3]. In general, the piecewise linear function is an approximation of $\sum _{i\in S^+\cup S^-} w_i\log (y_i)$ . However, if $y_i$ can only take integer values in the interval $[l_i,u_i]$ for all $i\in S^+\cup S^-$ , where $l_i,u_i\in \mathbb {Z}_+$ and are nonnegative, then the piecewise linear function can be an exact representation of $\sum _{i\in S^+\cup S^-} w_i\log (y_i)$ . This is because one can set the breakpoints of the piecewise linear function for $y_i$ where $i\in S^+\cup S^-$ is to be all integer values in the interval $[l_i,u_i]$ . For example, if $y_i$ can only take integer values for all $i\in S^+\cup S^-$ , then an exact piecewise linearized reformulation of equation (4.2) can be stated as follows:

(4.3) $$ \begin{align} \begin{aligned} \max_{\boldsymbol{y}\in \mathcal{Y}}& \quad \sum_{i\in S^+\cup S^-} w_i \sum_{j=1}^{u_i-l_i+1} b_{ij}\log(l_i+j-1) , \\ \mbox{subject to} & \quad y_i=\sum_{j=1}^{u_i-l_i+1} b_{ij} (l_i+j-1) \quad \text{for all } i\in S^+\cup S^- , \\ & \quad \sum_{j=1}^{u_i-l_i+1} b_{ij}=1 \quad \text{for all } i\in S^+\cup S^- , \\ & \quad b_{ij}\in\{0,1\} \quad \text{for all } i\in S^+\cup S^- \mbox{ and } \\ &\qquad \qquad \quad\ \ \ \ \kern1.2pt\text{for all }j\in [1, u_i-l_i+1] .\\ \end{aligned} \end{align} $$

Observe that the interval $[l_i,u_i]$ consists of $u_i-l_i+1$ integer values for any ${i\in S^+\cup S^-}$ . Hence, in equation (4.3), $b_{ij}$ is a binary decision variable that takes the value of one if the value of $y_i$ is equal to the jth smallest integer value in the interval $[l_i,u_i]$ , that is, $l_i+j-1$ , and zero otherwise. The constraints of equation (4.3) ensure that $b_{ij}$ follows its definition for all $ i\in S^+\cup S^-$ and $j\in [1, u_i-l_i+1]$ . In addition, the terms

$$ \begin{align*}\sum_{j=1}^{u_i-l_i+1} b_{ij}\log(l_i+j-1)\end{align*} $$

in the objective function of equation (4.3) capture the value of $\log (y_i)$ for all $ {i\in S^+\cup S^-}$ . Note that the term $\log (l_i+j-1)$ is a parameter and can be computed in advance. The following remark is helpful.

The third approach assumes that $w_i$ is a positive integer value for all $i\in S^+\cup S^-$ . Of course this is not an unreasonable assumption because, by Proposition 3.4, one can multiply the objective function of equation (4.2) by a sufficiently large (positive) number to change all fractional (rational) weights to integer values. So, we can assume that $w_i\in \mathbb {Z}$ for all $i\in S^+\cup S^-$ . The third approach is motivated by this observation that the NSWP can be reformulated as a geometric-mean optimization problem as follows:

$$ \begin{align*} \max_{\boldsymbol{y}\in \mathcal{Y}}&\quad \gamma ,\\ \mbox{subject to } &\quad 0 \le \gamma \le \sqrt[W]{\prod_{i\in S^+\cup S^-} y_i^{w_i}}, \end{align*} $$

where $W=\sum _{i=1} ^p w_i$ and $\gamma $ is a nonnegative decision variable that captures the value of the geometric mean (for optimal solutions). Note that because the problem is in the form of maximization, we must have $\gamma ^W=\prod _{i\in S^+\cup S^-} y_i^{w_i}$ for any optimal solution. However, the main question is how equation (4.3) should be solved. The underlying idea of the third approach is that equation (4.3) should be reformulated in a form that can be solved by commercial solvers. As stated by Chrakhgard et al. [Reference Charkhgard, Savelsbergh and Talebian4], based on the work of Ben-Tal and Nemirovski [Reference Ben-Tal and Nemirovski2], a geometric-mean constraint can be replaced by some linear constraints and second-order cone constraints (and introducing some additional continuous variables). To do so, in the geometric-mean constraint, $y_i^{w_i}$ should be first replaced by the multiplication of $w_i$ copies of $y_i$ for each $i\in S^+\cup S^-$ . In other words, for each $i\in S^+\cup S^-$ , we can replace $y_i^{w_i}$ by

$$ \begin{align*} \prod_{j=\mathcal{W}_{i-1}+ 1}^{\mathcal{W}_i} \tau^0_j, \end{align*} $$

$\mathcal {W}_i= \sum _{k=1}^{i} w_k$ and $\tau ^0_j=y_i$ for all $j\in [\mathcal {W}_{i-1}+1, \mathcal {W}_{i}]$ . Note that the superscript of $\tau $ is just an index and it does not indicate its power. With this in mind, let K be the smallest positive integer value such that $2^K \ge W$ . By introducing some additional nonnegative variables and constraints, equation (4.3) can be reformulated as follows:

(4.4) $$ \begin{align} \begin{aligned} \max &\quad \gamma ,\\ \mbox{subject to} &\quad 0 \le \gamma\le \sqrt{\tau_1^{K-1}\tau_2^{K-1}}, \\ & \quad 0 \le \tau^l_j\le \sqrt{\tau^{l-1}_{2j-1}\tau^{l-1}_{2j}} \quad\text{for all } j\in[1, 2^{K-l}] \mbox{ and } \\ &\qquad\qquad\qquad\qquad\qquad\text{for all } l\in[1, K-1],\\ & \quad 0 \le \tau^0_j=y_i \quad\text{for all } i\in S^+\cup S^- \mbox{ and } \\ &\qquad\qquad\qquad\ \,\text{for all } j\in[\mathcal{W}_{i-1} + 1, \mathcal{W}_i], \\ &\quad 0 \le \tau^0_j=\gamma \quad\text{for all } j\in[ W+1, 2^K],\\ & \quad\boldsymbol{y}\in\mathcal{Y}. \end{aligned} \end{align} $$

Interested readers may refer to the work of Ben-Tal and Nemirovski [Reference Ben-Tal and Nemirovski2] for details regarding this transformation. Note that any constraint of the form ${\{u,v,z\kern1.2pt{\ge}\kern1.2pt 0 \mid u\,{\le} \sqrt {vz}\}}$ is equivalent to

$$ \begin{align*}\bigg\{u,v,z\ge 0\; \bigg | \sqrt{u^2+\bigg(\frac{v-z}{2}\bigg)^2}\le \frac{v+z}{2}\bigg\}, \end{align*} $$

which is a second-order cone constraint.

Finally, it is worth mentioning that some other effective (but sophisticated) approaches have been developed for solving the NSWP in recent years. Those approaches fall under the category of “solution methods for optimization over the Pareto-optimal solutions,” because they are based on this observation that the NSWP is trying to return a Pareto-optimal solution that maximizes the Nash social welfare function. In other words, those approaches try to find a Pareto-optimal point in each iteration and then check its optimality for the NSWP. If it is not optimal, then they modify the search and find a different Pareto-optimal point. To the best of our knowledge, those approaches are shown to be competitive with (and even better than) all the approaches mentioned above when $\mathcal {Y}$ is represented by only linear constraints involving continuous and/or integer decision variables. Interested readers may refer to the papers by Charkhgard et al. [Reference Charkhgard, Savelsbergh and Talebian4], Saghand and Charkhgard [Reference Saghand and Charkhgard16, Reference Saghand and Charkhgard17], Saghand et al. [Reference Saghand, Charkhgard and Kwon18] and Vazirani [Reference Vazirani21] to learn more about those approaches. Specifically, a detailed computational study comparing different solution approaches was given by Saghand and Charkhgard [Reference Saghand and Charkhgard17].

5 Final remarks

In this paper, we introduced four main challenges when dealing with single- or multi-objective optimization problems including computational barrier, confusion (or nonexistence) of decision makers, ignoring unsupported Pareto-optimal solutions and fairness/equity. To overcome the challenges, we proposed to develop a game-theoretic mathematical program, named as the NSWP, for any single- or multi-objective optimization problem. We showed that there are several effective techniques to solve the NSWP. To see the effectiveness of the NSWP in different fields, interested readers may refer to the works of Sierra-Altamiranda et al. [Reference Sierra-Altamiranda, Charkhgard, Eaton, Martin, Yurek and Udell20] in conservation planning/ecology, Acuna et al. [Reference Acuna, Zayas-Castro and Charkhgard1] and Mendoza-Alonzo et al. [Reference Mendoza-Alonzo, Zayas-Castro and Charkhgard12] in healthcare, and Melendez et al. [Reference Melendez, Subramanian, Das and Kwon11] in energy. Overall, we hope that the simplicity and advantages of the proposed approaches encourage more practitioners as well as researchers to use the NSWP in practice.