s2fieldsofstudy:
Economics
Computer Science

text:
Approval-Based Elections and Distortion of Voting Rules

We consider elections where both voters and candidates can be associated with points in a metric space and voters prefer candidates that are closer to those that are farther away. It is often assumed that the optimal candidate is the one that minimizes the total distance to the voters. Yet, the voting rules often do not have access to the metric space $M$ and only see preference rankings induced by $M$.Consequently, they often are incapable of selecting the optimal candidate. The distortion of a voting rule measures the worst-case loss of the quality being the result of having access only to preference rankings. We extend the idea of distortion to approval-based preferences. First, we compute the distortion of Approval Voting. Second, we introduce the concept of acceptability-based distortion---the main idea behind is that the optimal candidate is the one that is acceptable to most voters. We determine acceptability-distortion for a number of rules, including Plurality, Borda, $k$-Approval, Veto, the Copeland's rule, Ranked Pairs, the Schulze's method, and STV.

Introduction
We consider the classic election model: we are given a set of candidates, a set of votersthe voters have preferences over the candidates-and the goal is to select the winner, i.e., the candidate that is (in some sense) most preferred by the voters. The two most common ways in which the voters express their preferences is (i) by ranking the candidates from the most to the least preferred one, or (ii) by providing approval sets, i.e., subsets of candidates that they find acceptable. The collection of rankings (resp. approval sets), one for each voter, is called a ranking-based (resp. approval-based) profile. There exist a plethora of rules that define how to select the winner based on a given preference profile, and comparing these election rules is one of the fundamental questions of the social choice theory [3].
One such approach to comparing rules, proposed by Procaccia and Rosenschein [22], is based on the concept of distortion. Hereinafter, we explore its metric variant [2]: the main idea is to assume that the voters and the candidates are represented by points in a metric space M called the issue space. The optimal candidate is the one that minimizes the sum of the distances to all the voters. However, the election rules do not have access to the metric space M itself but they only see the ranking-based profile induced by M: in this profile the voters rank the candidates by their distance to themselves, preferring the ones that are closer to those that are farther. Since the rules do not have full information about the metric space they cannot always find optimal candidates. The distortion quantifies the worst-case loss of the utility being effect of having only access to rankings. Formally, the distortion of a voting rule is the maximum, over all metric spaces, of the following ratio: the sum of the distances between the elected candidate and the voters divided by the sum of the distances between the optimal candidate and the voters. The concept of distortion is interesting, yet-in its original form-it only allows to compare ranking-based rules. In this paper we extend the distortion-based approach so that it captures approval preferences. In the first part of the paper we analyze the distortion of Approval Voting (AV), i.e., the rule that for each approval-based profile A returns the candidate that belongs to the most approval sets from A. To formally define the distortion of AV one first needs to specify, for each metric space M, what is the approval-based profile induced by M. Here, we assume that each voter is the center of a certain ball and approves all the candidates within it. We can see that each metric space induces a (possibly large) number of approval-based profileswe obtain different profiles for different lengths of radiuses of the balls. This is different from ranking-based profiles, where (up to tie-breaking) each metric space induced exactly one profile. Thus, the distortion of AV might depend on how many candidates the voters decide to approve. Indeed, it is easy to observe that if each voter approves all the candidates, then the rule can pick any of them, which results in an arbitrarily bad distortion. On the other hand, by an easy argument we will show that for each metric space M there exists an approval-based profile A consistent with M, such that AV for A selects the optimal candidate. In other words: AV can do arbitrarily well or arbitrarily bad, depending on how many candidates the voters approve.
Our first main contribution is that we fully characterize how the distortion of AV depends on the length of radiuses of approval balls. Specifically, we show that the distortion of AV is equal to 3, when the lengths of approval radiuses of the voters are all equal and such that the optimal candidate is approved by between 1 /4 and 1 /2 of the population of the voters (and this is the optimal distortion for the case of radiuses of equal length). The exact relation between the number of voters approving the optimal candidate and the distortion of AV is depicted in Figure 1.
In the second part of the paper we explore the following related idea: assume that the goal of the election rule is not to select the candidate minimizing the total distance to the voters, but rather to pick the one that is acceptable for most of them. E.g., AV perfectly implements this idea. A natural question is how good are ranking-based rules with respect to this criterion. To answer this question we introduce a new concept of acceptability-based distortion (in short, ab-distortion). We assume that each metric space, apart from the points corresponding to the voters and candidates, contains acceptability balls-one for each voter (as before, each voter is the center of the corresponding ball). The optimal candidate is the one that belongs to the most acceptability balls, and the ab-distortion distortion measures the normalized difference between the numbers of balls to which the elected and the optimal candidates belong. The ab-distortion is a real number between 0 and 1, where 0 corresponds to selecting the optimal candidate and 1 is the worst possible value 1 .
Among the ranking-based rules that we consider in this paper, the best (and the optimal) ab-distortion is attained by Ranked Pairs and the Schulze's method. It is an open question, whether they are the only natural rules with this property. It is worth mentioning, that its abdistortion is closely related to the size of the Smith set, so in case it is small (in particular, when the Condorcet winner exists) these rules have even better ab-distortion. We have found an interesting result for the Copeland's rule. Although in case of classic (distance-based) distortion most Condorcet rules are equally good, this is no longer the case when acceptability is the criterion we primarily care about. The ab-distortion of the Copeland's rule is equal to 1, which is the worst possible value. This rule is optimal only if the Condorcet winner exists (e.g. when the metric space is one-dimensional). The distortion of scoring rules (Plurality, Borda, Veto, k-approval) is significantly worse that for Ranked Pairs. An another surprising result is the distortion of STV-while this rule is known to achieve a very good distance-based distortion, its ab-distortion is even worse than for Plurality (denoting the number of candidates as m, STV and Plurality achieve the ab-distortion of 2 m −1 2 m and m−1 m , respectively). In case of all these rules the worst-case instances were obtained in one-dimensional Euclidean metric spaces. Our results are summarized in Table 1.

Preliminaries
For each set S by 2 S and Π(S) we denote, respectively, the powerset of S and the set of all linear orders over S. By S ∁ we denote the complement set of S, and by S * -the set of all vectors with the elements from S. For each two sets S 1 , S 2 and a function f : S 1 → 2 S 2 by R f : S 2 → 2 S 1 we denote the function defined as follows: For convenience we assume that [−∞; +∞] denotes the affinely extended real number system (the set of real numbers R with additional symbols +∞, and −∞). We take the following convention for arithmetical operations: Expressions 0 0 , ±∞ ±∞ , 0 · ±∞ and ±∞ − ±∞ are undefined.

Our Metric Model
An election instance is a tuple (N, C, d, λ), where N = {1, 2, . . . , n} is the set of voters, C = {c 1 , c 2 , . . . , c m }, is the set of candidates, d : (N ∪C) 2 → R is a distance function (d allows us to view the candidates and the voters as points in a pseudo-metric space), and λ : N → 2 C is an acceptability function, mapping each voter i ∈ N to a subset of candidates that i finds acceptable. We assume that λ is nonempty, i.e., for each i ∈ N, λ(i) = ∅, and that is local Often we will also require that λ satisfies a stronger condition, called global consistency-for Intuitively, local-consistency means that for each voter i ∈ N we can associate λ(i) with a ball with the center at the point of this voter. A voter i ∈ N considers a candidate c j to be acceptable for him, c j ∈ λ(i), if and only if c j lies within the ball. Such a ball will be further called the acceptability ball and its radius-the acceptability radius. Then, global consistency can be interpreted as an assumption that all the acceptability radiuses have equal lengths. We will sometimes slightly abuse the notation: by saying that an instance satisfies local (global) consistency we will mean that the acceptability function in the instance satisfies the respective property.
By I, we denote the set of all election instances. Since issue spaces are often argued to be Euclidean spaces with small numbers of dimensions, we additionally introduce the following notation: for each k ∈ N let E k denote the set of all the instances where the elements of N and C are associated with points from R k , and d is the Euclidean distance.

Preference Representation
In most cases, it is difficult for the voters to explicitly position themselves in the issue space, and often even the space itself is unknown. Therefore, we will consider voting rules that take as inputs preference profiles induced by election instances, instead of instances themselves. We consider two classic approaches to represent preferences.
Ranking-based profiles. A ranking-based profile induced by an election instance I = (N, C, d, λ) is the function I : N → Π(C), mapping each voter to a linear order over C such that for all i ∈ N and all c a , For each voter i ∈ N, the relation I (i) (for convenience also denoted as i , whenever the instance is clear from the context) is called the preference order of i. If for some c x , c y ∈ C it holds that c x i c y , we say that i prefers c x over c y .
Approval-based profiles. An approval-based profile of an election instance I = (N, C, d, λ) is a locally consistent acceptability function A I : N → 2 C . We say that a candidate c x is approved by a voter i ∈ N if c x ∈ A(i). We will say that the approval-based profile is truthful if for all i ∈ N it holds that A(i) = λ(i).
Let us introduce some additional useful notation. Let P : C * → N be a function mapping vectors of distinct candidates to sets of voters as follows: For convenience, we will write P (c i 1 , c i 2 , ..., c i k ) instead of P ((c i 1 , c i 2 , ..., c i k )) 2 . Note that for all c a , c b ∈ C we have P (c a , c b ) ∩ P (c b , c a ) = ∅ and P (c a , c b ) ∪ P (c b , c a ) = N.
We say that c a dominates c b if |P (c a , c b )| > n 2 and that c a weakly dominates c b if |P (c a , c b )| ≥ n 2 . We say that a candidate c x Pareto-dominates a candidate c y if there holds that |P (c x , c y )| = n. A candidate c y is Pareto-dominated if there exists a candidate c x who Pareto-dominates c y .

Definitions of Voting Rules
An election rule (also referred to as a voting rule) is a function mapping each preference profile to a set of tied winners. We distinguish ranking-based rules-taking ranking-based profiles as arguments, and approval-based rules-defined analogously. Among approval-based rules, we focus on Approval Voting (AV)-the rule that selects those candidates that are approved by most voters. In the remaining part of this subsection we recall definitions of the ranking-based rules that we study in this paper.
Positional scoring rules For a given vector s = (α 1 , α 2 , α, α m ), the scoring rule implemented by s works as follows. A candidate c a gets α i points from each voter j who puts c a in the ith position in j . The rule elects the candidates whose total number of point, collected from all the voters, is maximal. Some well-known scoring rules which we will study in the further part of this work are the following: The Copeland's Rule The Copeland's rule elects candidates c w who dominate at least as many candidates as any other candidate. More formally, a candidate c w is a winner if and only if: Ranked Pairs Ranked Pairs works as follows: first we sort the pairs of candidates (c i , c j ) in the descending order of the values |P (c i , c j )|. Then, we construct a graph G where the vertices correspond to the candidates. We start with the graph with no edges; then we iterate over the sorted list of pairs-for each pair (c i , c j ) we add an edge from c i to c j unless there is already a path from c j to c i in G. If such a path exists, we simply skip this pair. Clearly, the so-constructed graph G is acyclic. The source nodes of G are the winners. STV Single Transferable Vote (STV) works iteratively as follows: if there is only one candidate, elect this candidate. Otherwise, eliminate the candidate who has the least points according to the Plurality rule and repeat the algorithm.
Note that the aforementioned rules are irresolute by definition. Further, we did not specify the tie-breaking rule used when sorting edges in Ranked Pairs and when eliminating candidates in STV. We will make all these rules resolute by using the lexicographical tie-breaking rule, denoted by lex .

Measuring the Quality of Social Choice
In this section we formalize the concept of distortion that, on the intuitive level, we already introduced in Section 1.
Distance-based approach A natural idea to relate the quality of a candidate c with the sum of the distances from this candidate to all the voters. The lower this sum is, the higher the quality. Following this intuition, the distortion of a voting rule ϕ in instance I ∈ I, is defined as follows (below, c o denotes the optimal candidate for I): where P I is the set of profiles induced by I (either ranking or approval, depending on the domain of ϕ). D(ϕ) ∈ [1; +∞]. This approach can be applied to any rule discussed so far. For ranking-based rules it has already been widely studied in the literature, hence in the further part we will focus on AV.
Acceptability-based approach Now we present an alternative way to measure the quality of candidates, based on the acceptability function. Intuitively, the more voters a candidate c is acceptable for, the higher his quality. Besides, we would like the maximal possible quality not to depend on the number of voters. Therefore, we define the acceptability-based distortion (ab-distortion, in short) of a voting rule ϕ in instance I ∈ I as the following expression: where P I is the set of profiles induced by I (either ranking-based or approval-based, depending on the domain of ϕ). Clearly, the ab-distortion is always a value from [0; 1]. By definition, Approval Voting always elects an optimal candidate in terms of ab-distortion. Thus, we will consider our acceptability-based measure only for ranking-based rules.
Let E be an expression that can depend on characteristics of an instance (e.g., on the number of candidates, or size of the Smith set). We say that the (acceptability-based) distortion of a rule ϕ is E, if for each instance I, D I (ϕ) ≤ E and for each E there is an instance I with D I (ϕ) = E.

Distortion of Approval Voting
In this section we analyze the distance-based distortion of Approval Voting (AV)-hereinafter we denote AV by ϕ AV .
We start by showing that in the most general case, if we do not make any additional assumptions about the acceptability function, the distortion of AV can be arbitrarily bad.
This result is rather pessimistic. However, one could ask a somehow related question-does there for each instance I always exist an approval profile consistent with I that would result in a good distortion? In contrast to Proposition 3.1, here the answer is much more positive.
Proposition 3.2. For each instance I ∈ I, there is an approval based profile p consistent with I such that ϕ(p) is the optimal candidate (minimizing the total distance to voters). Propositions 3.1 and 3.2 show that for each metric space M there always exists two approval profile A 1 , A 2 consistent with M such that for A 1 AV selects the worst possible candidate, and for A 2 it selects the optimal one-since A 1 and A 2 are both consistent with M, they only differ in the sizes of approval balls. This formally shows that the performance of AV strongly depends on how many candidates the voters decide to approve. Below, we provide our main result of this section-assuming that all the acceptability balls have radiuses of the same length, we show the exact relation between this length of approval radiuses and the distance-based distortion of AV. In particular, we show that the best approval radius is such that the optimal candidate is approved by between 1 /4 and 1 /2 fraction of all the voters.

Definition 3.3. An approval-based profile A induced by an instance
In words, a profile is p-efficient if the number of voters who approve the optimal candidate is the p fraction of n.
Theorem 3.4. For each globally consistent p-efficient instance I, we have the following results: The above function is depicted in Figure 1.
All these bounds are attained for instances in E 1 . While we omit the formal proof of this statement, in order to give the reader a better intuition, we illustrate hard instances for different values of p in Figure 2.
Finally, for completeness, we give an analogue of Proposition 3.2, but for globally-consistent instances.
Proposition 3.5. For each instance I ∈ I, there exists an approval profile p globally consistent with I, such that

AB-Distortion of Ranking Rules
Recall that the ab-distortion of a voting rule is a value from [0; 1], proportional to the difference between the number of voters accepting the optimal candidate and the number of voters accepting the winner. By definition, this value equals 0 for AV (provided the approval profile is truthful). In this section we analyze the ab-distortion of ranking-based rules.
We start by proving the lower bound on the ab-distortion of any ranking-based voting rule.
Theorem 4.1. For each ℓ ∈ N and each ranking-based rule ϕ, there exists a globally consistent instance I such that: Here, c w is the winner of the election and c o is the optimal candidate, c w lex c o lex c 1 lex c 2 lex . . .. R is the length of the acceptability radius. Since R is common for all the voters, the instances are globally consistent.

the size of the Smith set in the ranking-based profile induced by I equals ℓ,
In the subsequent part of this section we will assess the distortion of specific voting rules, specifically looking for one that meets the lower-bound from Theorem 4.1.

Condorcet Rules
We start by looking at Condorcet consistent rules. Note that the lower bound found in Theorem 4.1 is promising, as it depends on the size of the Smith set. In particular, if ℓ = 1, this bound equals From the above theorem, we get that for ℓ = 1 each Condorcet election method matches the lower bound from Theorem 4.1. Now we will prove that there exists election rules, namely Ranked Pairs and the Schulze's rule, which match this bound for each ℓ.
where ℓ is the size of the Smith set of I.
As we can see, there is no rule with a better ab-distortion than these two rules. Yet, it is not a feature of all the Condorcet methods. As we will see, even for the well-known Copeland's rule, the possible pessimistic distortion is much worse.

Scoring Rules
Let us now move to positional scoring rules. Here, we obtain significantly worse results than for Ranked Pairs and the Schulze's rule. A general tight upper bound for the ab-distortion of any scoring rule remains an open problem. Below we provide bounds that are tight for certain specific scoring rules.
The bound obtained in Theorem 4.5 is not tight in general. For example, for Plurality we have a tighter estimation.
Theorem 4.6. The ab-distortion of Plurality is m−1 m . This bound is achieved for globally consistent instances in E 1 .
Yet, for a number of scoring rules the bound from Theorem 4.5 is tight. Below, we give some sufficient conditions. Proposition 4.7. The bound from Theorem 4.5 is tight for each scoring rule satisfying the following conditions: even for globally consistent instances in E 1 .
Theorem 4.5 and Proposition 4.7 imply the ab-distortion for a number of scoring rules.
Corollary 4.8. There exists a globally consistent instance I ∈ E 1 , for which:

Iterative rules
All scoring rules that we considered have poor ab-distortion, and in particular are considerably worse than Condorcet rules (especially for instances with Condorcet winners). Interestingly, STV in terms of acceptability, behaves worse even than Plurality. This is somehow surprising since for distance-based distortion, STV is better than any positional scoring rules, and only slightly worse than Condorcet rules.
The above bound is tight even in one-dimensional Euclidean spaces. It is also tight if we restrict ourselves to global consistent instances. There, the hard instances that we found use (m − 2)-dimensional Euclidean space.

Related Work
The spatial model of preferences is quite popular in the social choice and political science literature. For example seminal works studying spacial models we refer the reader to [10,21,11,12,18,19,24].
The concept of distortion was first introduced by Procaccia and Rosenschein [22]. In their work they did not assume the existence of a metric space, but rather used a generic cardinal utility model (where the voters can have arbitrarily utilities for candidates). This model was later studied by Caragiannis and Procaccia [8] and Boutilier et al. [6]. Recently, Benadé et al. [5] introduced the concept of distortion for social welfare functions, i.e., functions mapping voters preferences to rankings over candidates, and Benade et al. [4] adapted and used the concept of distortion in the context of participatory budgeting to evaluate different methods of preference elicitation. The studies of the concept of distortion in metric spaces were initiated by Anshelevich et al. [2], and then continued by Anshelevich and Postl [1], Feldman et al. [13], Goel et al. [15], and Gross et al. [16].
The analysis of the distortion forms a part of a broader trend in social choice stemming from the utilitarian perspective. For classic works in welfare economics that discuss the utilitarian approach we refer the reader to the article of Ng [20] and the book of Roemer [23]. This approach has also recently received a lot of attention from the computer science community. Apart from the papers that directly study the concept of distortion that we discussed before, examples include the works of Filos-Ratsikas and Miltersen [14], Branzei et al. [7], and Chakrabarty and Swamy [9].

Conclusion
In this paper we have extended the concept of distortion of voting rules to approval-based preferences. This extension allows to compare rules that take different types of input: approval sets and rankings over the candidates. To the best of our knowledge, only very few formal methods are known that allow for such a comparison. We are aware of only one work that formally relates these two models: Laslier and Sanver [17] proved that in the strong Nash equilibrium Approval Voting selects the Condorcet winner, if such exists.
Our contribution is twofold. First, we have determined the distortion of Approval Voting, and explained how this distortion depends on voters' approval sets. We have shown that the socially best outcome is obtained when voters approve not too many and not too few candidates. If the lengths of voters' acceptability radiuses are all equal, the best distortion is obtained when the approval sets are such that between 1 4 and 1 2 of the voters approve the optimal candidate. Second, we have defined a new concept of acceptability-based distortion (ab-distortion).
Here, we assume that the voters have certain acceptability thresholds; the ab-distortion of a given rule ϕ measures how many voters (in the worst-case) would be satisfied from the outcomes of ϕ. We have determined the ab-distortion for a number of election rules (our results are summarized in Table 1), and reached the following conclusions. The analysis of the classic and the acceptability-based distortions both suggest that Condorcet rules perform better than scoring and iterative ones. Further, our acceptability-based approach suggests that Ranked Pairs and the Schulze's rule are particularly good rules, in particular significantly outperforming the Copeland's rule. Thus, our study recommends Ranked Pairs or the Schulze's method as rules that robustly perform well for both criteria (total distance, and acceptability). The question whether they are the only natural ranking-based rules performing well for both criteria is open. Approval Voting is also a very good rule that can be considered an appealing alternative to them, provided the sizes of the approval sets of the voters are appropriate. Proof. Consider the instance I from Figure 3. We have two candidates C = {c 1 , c 2 }, c 2 lex c 1 , and n voters. The voters are identical-for each i ∈ N we have d(i, c 1 ) = 0, and d(i, c 2 ) = 1 (thus c 1 i c 2 ), and they all approve all the candidates.
In I, c 1 is the optimal candidate, yet Approval Voting picks c 1 and c 2 which, together with the fact that c 2 lex c 1 , implies that c 2 is the winner. Thus, we get that D I (ϕ AV ) = n 0 = +∞.
A.2 Proof of Proposition 3.2 Proposition 3.2. For each instance I ∈ I, there is an approval based profile p consistent with I such that ϕ(p) is the optimal candidate (minimizing the total distance to voters).
Proof. Consider an instance I, and let c o be an optimal candidate in I. Consider the following approval-based profile consistent with I: each voter approves c o and all the candidates more preferred to c o , but does not approve any candidate less preferred than c o . Candidate c o gets n votes. Thus, c o will be the winner, unless some other candidate, call it c, also received n votes and is preferred by the tie-breaking rule. If this is the case, then c must Pareto dominate c o , which means that c is also an optimal candidate. This completes the proof.

A.3 Proof of Theorem 3.4
In the proof we will also use the following simple inequality: Lemma A.1. For each positive numbers a, b, c, d such that a ≥ b, c ≥ d we have that: For each positive numbers a, b, c, d such that a ≥ b, c ≥ d, we have: The above function is depicted in Figure 1.
Proof. Let I be a globally consistent p-efficient instance. Assume that p / ∈ {0, 1} (otherwise, the upper bound +∞ is obtained directly from the definition of distance-based distortion). Let c o and c w denote, respectively, the optimal candidate in I and the winner returned by Approval Voting. As I is globally consistent, there exists r ∈ R which is the length of acceptability radiuses of all the voters.
We first provide a few basic inequalities, which will be used in the further part of the proof. We will refer to these inequalities using their numbers-this will make the steps of our reasoning transparent. As c w is the winner of the voting, we have: From the definition of the voting radius: From trivial set properties: From the triangle inequality: From Lemma A.1: The further part of the proof will be split into three cases: For each p, the final worst-case distortion is the maximum of the worst-case distortions in all these three cases.
Analysis of Case 1. The following inequality holds: In this case we have: As the numerator is greater than the denumerator (because D I (ϕ AV ) ≥ 1): Analysis of Case 2. The following inequalities hold: In such case, we assess the distortion as follows: .
As the numerator is greater than the denumerator (because D I (ϕ AV ) ≥ 1): For p ≥ 1 2 the second part of the final sum is not positive, so we have: On the other hand, for p ≤ 1 2 we have: Analysis of Case 3. The following inequality holds: First, let us observe that in this case sets R A (c o ) and R A (c w ) are disjoint: . It also holds that: p Then we can limit the distortion (partially analogically as in Case 2) as follows: As the numerator is greater than the denumerator (because D I (ϕ AV ) ≥ 1): . Now we can easily see that: Hence, for p ∈ [ 1 4 ; 1 2 ] we can continue our calculations as follows: For p ∈ [0; 1 4 ] we can continue the calculations in a different way: Summarizing the results for the particular cases. Finally, we have the following results: 1. For p ∈ {0, 1}: +∞.

For
The hard instances for different values of p are illustrated in Figure 2.
A.4 Proof of Proposition 3.5 Proposition 3.5. For each instance I ∈ I, there exists an approval profile p globally consistent with I, such that i∈N d(i, ϕ(p)) i∈N d(i, c o ) Proof. Let us consider a globally consistent preference approval-based profile A induced by I satisfying the following conditions: 1. at least n /4 voters approve an optimal candidate c o , 2. the length of acceptability radiuses R is the shortest that satisfies the condition above.
If the number of voters approving c o is less than n 2 then A is p-efficient for some p ∈ [ 1 4 ; 1 2 ] and the statement is implied directly by Theorem 3.4. Suppose then that p > 1 2 . It means that there exists subsets of voters S ⊆ N, such that |S| < n 4 and for each i ∈ R A (c o ) \ S we have that d(i, c o ) = R, while for each i ∈ S we have that d(i, c o ) < R.
As R A (c w ) ≥ R A (c o ), we have that there exists a voter approving both c o and c w , hence d(c o , c w ) ≤ 2R. Then from the triangle inequality we obtain the following result: A.5 Proof of Theorem 4.1 for ℓ = 1. .
Proof. First, let us consider the case when ℓ ≥ 2. Note that ϕ does not depend neither on the acceptability function nor on the specific distance values in the metric space. We will now construct a set of ℓ instances I = {I 1 , I 2 , . . . , I ℓ } such that for each instance I i the following conditions are satisfied: 1. The number of candidates m equals ℓ.
2. The voters are divided into groups G (i,1) , G (i,2) , . . . , G (i,ℓ) -each group contains n ℓ voters and corresponds to a single point in the metric space.
3. The ranking-based preferences of the voters from each group are the same and form a cyclic shift of the vector (c 1 , c 2 , . . . , c ℓ ).

The voters from group G
and accept the first k candidates from the above ranking (hence, all the voters accept c i and only voters from group G (i,ℓ) accept c i+1 ).
For each instance we have n /ℓ voters with preferences c 1 . . . c ℓ , n /ℓ voters with preferences c ℓ c 1 . . . c ℓ−1 , etc. Hence, the ranking-based preference profile induced by each instance is the same subject to the permutation of the voters. Consequently, w.l.o.g., we can assume that in each instance the winner elected by ϕ is the same. Besides, one can easily verify that in each instance all the candidates are in the Smith set. Suppose that ϕ elects candidate c i . Then we take instance I i−1 as a witness-here, the optimal candidate is c i−1 , acceptable for n voters, and candidate c i is acceptable only for n /ℓ voters from G (i−1,ℓ) . Thus, for this instance we obtain the ab-distortion of 1 − 1 /ℓ = ℓ−1 /ℓ. To complete the proof for the case when ℓ ≥ 2, we need to show that it is possible to construct the instances from I using globally consistent acceptability functions.
Each instance I i can be constructed through the following procedure: 1. Put all the candidates in a metric space R ℓ−1 so that they are vertices of a regular (ℓ-1)simplex with all edges equal to 1.
2. Set the acceptability radius of all the voters to the length of the circumradius of the simplex; let R denote the length of this radius.
3. For each k, we locate n /ℓ voters from G (i,k) in the following way. Consider the subset of k candidates acceptable for these voters. These candidates are also vertices of a (k − 1)simplex. Put the voters from G (i,k) in the circumcenter of this (k − 1)-simplex.
The construction for ℓ = 3 is illustrated in Figure 4. Now we will show that for each i, k, the construction of G (i,k) is correct-we need to verify the following conditions: Cond 1: The distance from each candidate c i−k+1 , . . . , c i to G (i,k) does not exceed R, Cond 2: The distance from any other candidate to G (i,k) exceeds R, . . . c ℓ c 1 . . . c i−k is consistent with the metric space for the voters from G (i,k) .
Recall that for any regular k-simplex with length of edges equal to 1 the length of the circumradius is equal to k 2(k+1) and the height of the simplex is equal to k+1 2k (for k > 0). Directly from these formulas we have some simple properties that hold for any regular ksimplex and n-simplex, both with the length of edges equal to 1, k < n: Property 1: The circumradius of the k-simplex is smaller than the the circumradius of the n-simplex, Property 2: The height of the k-simplex is greater than the circumradius of the n-simplex.
Proof of Cond 1: Since R is the circumradius of the (ℓ − 1)-simplex and the distance from any candidate c i−k+1 , . . . , c i to G (i,k) equals the circumradius of a (k − 1)-simplex for k ≤ ℓ, then from Property 1 we have that this distance does not exceed R.
Proof of Cond 2: Consider a candidate c x outside of the set {c i−k+1 , . . . , c i }. This candidate together with candidates c i−k+1 , . . . , c i are vertices of a k-simplex. Consider now the height of this simplex dropped from c x . From the properties of regular simplexes the foot of this height is the circumcenter of the (k − 1)-simplex with vertices c i−k+1 , . . . , c i . Thus, this height equals the distance from c x to G (i,k) . From Property 2 we have that this distance is greater than R. Figure 4: The construction of I for ℓ = 3. White points correspond to the groups of voters, black ones correspond to the candidates. Circles mean acceptability spheres of the voters-as their length is common for all the voters, instances are globally consistent Proof of Cond 3: From Cond 1 and Cond 2 we have that candidates c i−k+1 , . . . , c i are closer to G (i,k) than any other candidate. Hence, they need to be put at the top of the rankings of all the voters from G (i,k) . Moreover, each such a ranking is consistent with the metric space we constructed (all candidates from {c i−k+1 , . . . , c i } have the same distance to G (i,k) , and similarly all the candidates outside of this set). In particular, the ranking c i−k+1 . . . c ℓ c 1 . . . c i−k is consistent with the metric. Now, let us move to the case when ℓ = 1. Here, we construct the following two instances, I 1 and I 2 . In both instances we have two candidates, c 1 and c 2 , placed in the one-dimensional Euclidean space in points 0 and 3, respectively. Further: 1. In I 1 we have n /2 + 1 voters placed in point 1, and n /2 − 1 voters placed in point 3. The length of the acceptability radius for all the voters is equal to 2, hence, all voters find c 2 acceptable, and only n /2 + 1 of them approve c 1 . White points correspond to groups of voters, black-to the candidates. As the length of the radius is common for all the acceptability balls, the instance is globally consistent.

In
case, we set the length of the acceptability radius to 2. Here, c 1 and c 2 are acceptable for, respectively, n and n /2 − 1 voters. Any deterministic rule cannot distinguish I 1 from I 2 , so the winner will be the same in both instances. Thus, in one of them, we will get the ab-distortion of 1 /2. Proof. Let c w be the winner and c o be the optimal candidate. Since we assumed that the Condorcet candidate exists in I, we have that c w weakly dominates c o . Then, we have: Further, we have that: This completes the first part of the proof. The hard instance is illustrated in Figure 5. We have four candidates C = {c x , c y , c z , c c }. There are n 2 − 1 voters with preferences c x c c c y , c z , approving only c x , n 4 + 1 voters with rankings c y c c c x , c z , approving only c y , and n 4 voters with preferences c z c c c x , c y , approving only c z . Candidate c c is the Condorcet winner and the optimal candidate is c x . The distortion of each rule electing c c is 1 2 − 1 n , which is arbitrarily close to 1 2 .

A.7 Proof of Theorem 4.3
In the proof of the theorem, we will use the following definitions: Definition A.2. Let the immunity set of instance I be the set of candidates such that each candidate c a from this set satisfies the following condition for each c b ∈ C: if c b dominates c a , then there exists a beatpath from c a to c b which strength is greater or equal to P (c b , c a ).
Definition A.3. The election rule is immune if for each instance it elects a candidate from the immunity set.
Note that for each instance the immunity set is the subset of the Smith set. Indeed, consider any election instance I. Let c a ∈ C belong to the immunity set of I and c b belong to the Smith set of I. If c a weakly dominates c b , then c a belongs to the Smith set. Otherwise, there exists a beatpath from c a to c b . The last element of this beatpath dominates c b , hence it belongs to the Smith set. If the ith element of the beatpath belongs to the Smith set, then so does the i − 1th element (which dominates the ith one). Finally, we have that c a dominates the first element on the beatpath, hence c a belongs to the Smith set. Now we would like to prove the following lemma: Lemma A.4. The ab-distortion of each immune ranking-based election rule ϕ is equal to: Proof. Let us denote the Smith set of the considered instance as S and let c w be the winner according to ϕ. We have that: In the further part of the proof we will upper bound |P (c o , c w )|. As the immunity set is a subset of the Smith set, it holds that c w ∈ S. Let us consider two cases: Case 1: Candidate c w weakly dominates c o . Then using the same reasoning as in the proof of Theorem 4.2 we get the bound of 1 /2. In this case we get the thesis, since for ℓ ≥ 2 we have that 1 2 ≤ ℓ−1 ℓ . Case 2: Candidate c o dominates c w . Then we have: We continue the analysis of Case 2. From the properties of the immunity set, there exists a vector of candidates (c x 1 , c x 2 , . . . , c c k −2 ) for some k ∈ N, such that c w dominates c x 1 , c x k −2 dominates c o and ∀i ∈ {1, . . . , k − 3} c x i dominates c x i+1 . Besides, this vector satisfies the following inequalities: Summing up both sides of these k − 1 inequalities, we have that: This is equivalent to: k Now let us consider the numerator in the right-hand side of the above inequality. Clearly, each of the k elements of this sum can be upper-bounded by the number of the voters, n. However, observe that a voter i ∈ N cannot be counted more than k−1 times, as her preferences are transitive and all the considered two-element vectors together make a cycle. Thus, we can upper-bound the sum by (k − 1)n, and so we get that |P (c o , c w )| ≤ k−1 k n. As c w ∈ S and c o dominates c w , then also c o ∈ S and, consequently, for each i we have that c x i ∈ S. Therefore, k ≤ |S|. Finally, we get that: The fact that this upper-bound is tight follows directly from Theorem 4.1.
Having this lemma proved, the proof of the main theorem is quite simple: • ℓ−1 ℓ for ℓ ≥ 2, • 1 2 for ℓ = 1, where ℓ is the size of the Smith set of I.
Proof. We will prove that both Ranked Pairs and the Schulze's rule are immune. Then the result will follow directly from Lemma A.4.
Consider an election instance I, and let c RP be the winner according to Ranked Pairs in I, and c be some other candidate. Assume that c dominates c RP . From the properties of Ranked Pairs, we know that the edge between c and c RP has not been added by the election algorithm to the graph. Hence, there must have existed a path in this graph from c RP to c, which had been added before pair (c, c RP ) was considered. Vertices on this path clearly form a beatpath from c RP to c. Besides, each edge on this path (c i , c j ) satisfies P (c i , c j ) ≥ P (c, c RP ), as it was considered by the algorithm before edge (c, c RP ). Hence, the strength of this beatpath from c w to c is greater of equal to P (c, c RP ) and, consequently, c RP belongs to the immunity set of I. Now, let us denote the winner according to the Schulze's rule by c S . Assume that c dominates c S . Then p[c, c S ] ≥ P (c, c S ). On the other hand, from the properties of the Schulze's rule, we know that p[c S , c] ≥ p[c, c S ]. Hence, there exists a beatpath from c S to c with the strength greater or equal to p[c, c S ], and, consequently, also to P (c, c S ). As a result, c S belongs to the immunity set of I.

D
Proof. Let c w be the winner elected by ϕ and c o be the optimal candidate. Let us consider the highest possible difference ψ between the number of points gained by c w and c o . Clearly ψ ≥ 0. Besides, we know that for all voters from P (c o , c w ) candidate c w gained less points than c o . Further, candidate c w could gain from each voter from this group at least min i,j |s i − s j | = p points less than c o . On the other hand, by considering the voters from P (c w , c o ) we infer that the highest possible difference in scores gained by the two candidates equals max i,j |s i − s j ||P (c w , c o )| = q|P (c w , c o )|. Finally we have the following inequality: Note that p + q = 0 is equivalent to the condition s 1 = . . . = s m . Assume now that p + q > 0.
In such a case we have that: Further, as in the first displayed inequality in the proof of Theorem 4.3, we get that: Thus, the ab-distortion of ϕ does not exceed q p+q .
A.10 Proof of Theorem 4.6 Theorem 4.6. The ab-distortion of Plurality is m−1 m . This bound is achieved for globally consistent instances in E 1 .
Proof. Note that the winner elected by Plurality needs to be the closest candidate for n m voters. Hence, from the non-emptiness and local consistency of the acceptability function, we have that c is acceptable for at least n m voters. Thus, the distortion does not exceed 1 − 1 m = m−1 m . This bound is tight for the instance constructed as follows: Let C = {c 1 , . . . , c m } be the set of candidates, c 1 lex c 2 lex . . . lex c m . We divide the voters into m equal-size groups, each putting a different candidate on the top position in their preference rankings. All the candidates are acceptable for voters voting for c 1 , and all the candidates except for c 1 are acceptable for the remaining voters. he illustration of a globally consistent instance in E 1 satisfying the above conditions is presented in Figure 7.
In this instance each candidate gains m n points and the winner is c 1 (due to the lexicographical tie-breaking rule). The optimal candidates are c 2 , . . . , c m , and they are acceptable for n voters. Hence, the distortion is m−1 m .
A.11 Proof of Proposition 4.7  Figure 7: The hard instance used in the proof of Theorem 4.6. White points correspond to groups of voters, black-to the candidates. For the clarity of the presentation, candidates c 2 , . . . , c m and voters voting for them are associated with the same points. R is the length of each acceptability radius. As this length is common for all the voters, the instance is globally consistent. White points correspond to groups of voters, black points correspond to the candidates. R is the length of each acceptability radius. As this length is common for all the voters, the instance is globally consistent.
even for globally consistent instances in E 1 .
Proof. Note that for the scoring rules satisfying the conditions of the proposition we have that max i,j |s i − s j | = s 1 − s m and min i,j |s i − s j | = s 1 − s 2 . Let us use the same notation as in the proof of Theorem 4.5: p = s 1 − s 2 , q = s 1 − s m . First let us consider the case when s 1 = . . . = s m , and consequently p + q = 0. In such case, the bound 1 is achieved by the following instance with m candidates, c m lex c 1 , . . . , c m−1 . All the voters have preferences c 1 . . . c m and approve only c 1 . This instance is illustrated in the upper row of Figure 8. The optimal candidate is c 1 , approved by n voters. However, all the candidates received the same number of points, and therefore the winner is c m , approved by no voter.
In the further part of the proof we assume that p + q > 0. Then the bound from Theorem 4.5 is q p+q = s 1 −sm 2s 1 −s 2 −sm . Now consider the following instance. We have m candidates, C = {c 1 , . . . , c m }, c 2 lex c 1 , and n voters divided into two groups: s 1 −sm 2s 1 −s 2 −sm n of them have preferences c 1 c 2 . . . c m and only c 1 is acceptable for them, and the remaining s 1 −s 2 2s 1 −s 2 −sm n voters have preferences c 2 . . . c m c 1 with all the candidates being acceptable. An illustration of a globally consistent instance in E 1 satisfying the above conditions is given in the lower row of Figure 8.
In this instance c 2 gains s 1 points from s 1 −s 2 2s 1 −s 2 −sm n voters and s 2 points from s 1 −sm 2s 1 −s 2 −sm n voters. The total number of points that c 2 received is: On the other hand, c 1 gains s 1 points from s 1 −sm 2s 1 −s 2 −sm n voters and s m points from s 1 −s 2 2s 1 −s 2 −sm n voters. Its total score is equal to: Since candidates c 3 , . . . , c m gain less points than c 2 (as they are farther away from each voter than c 2 and it holds that s 1 ≥ . . . ≥ s m ), none of them can become the winner. Thus, c 2 is the winner of the election due to the lexicographical tie-breaking. The optimal candidate is c 1 , and is acceptable for n voters, while c 2 only for s 1 −s 2 2s 1 −s 2 −sm n of them. Hence, the distortion is equal to s 1 −sm 2s 1 −s 2 −sm .
Proof. Let c w be the winner according to STV. Note that, the winner is the only candidate that survived to the the last round and in this round gains n votes. The number of rounds equals m. Note that if a candidate in some round gains k points (according to Plurality), then in the next round it gains at most 2k points. Indeed, otherwise this candidate would need to gain at least k + 1 points transferred from the removed candidate, so STV would not remove the candidate with the least number of points, a contradiction. Consequently, we have that c w , who has n points after m rounds, needs to get at least n 2 m−1 points in the first round. Similarly as in case of Plurality, from the non-emptiness and local consistency of the acceptability function, we have that c w is acceptable for at least n 2 m voters. Hence, the distortion does not exceed 1 − 1 2 m−1 = 2 m−1 −1 2 m−1 . We will prove the tightness in Proposition 4.10.
candidate is c 2 with n 2 m−2 points. In the next rounds, the removed candidates are respectively c 3 , . . . , c m , and all their points are always transferred to c m . The winner of the election is c m , and the optimal candidate is c 1 . Since c 1 is acceptable for n voters, and c m only for n 2 m−1 , we get the distortion of 2 m−1 −1 2 m−1 . Now, let us construct a globally consistent instance from E m−2 . We have C = {c 1 , . . . , c m }, c m lex c 1 , . . . , c m−1 , and all the candidates except for c 1 are vertices of a regular (m − 2)simplex in R m−2 ; c 1 is located in the circumcenter of the simplex-let us denote this point as O and the length of the circumradius of this simplex as R. The voters are divided into m groups (g 1 , . . . , g m ) as follows: g 1 consists of n 2 m−1 voters and is associated with the point O; for i > 1, g i consists of n /2 m−i voters and is associated with the point in the middle of the segment between c i and O (the distance from g i to c 1 equals the distance from g i to c i and equals R /2). The acceptability radius for each voter is equal to R /2. The example of this instance for m = 4 is presented in the lower row of Figure 9.
For i > 1, every voter from g i accepts only c i and c 1 . For each j = 1, i, consider the triangle {c i , c j , g i }. Recall that for any regular k-simplex with the edge length equal to 1 the circumradius is equal to k 2(k+1) , which is strictly less than 1. From this formula we obtain that R < d(c i , c j ). Hence, from the triangle inequality we have that: Hence, c j is not acceptable for g i . Voters from g 1 accept only c 1 (as d(g 1 , c 1 ) = 0 and for each i > 1 d(g 1 , c i ) = R). From the symmetry of the construction, we have that for each i > 1, all the candidates except for c 1 and c i are in the same distance from g i . Hence, we can assume that voters from g i have ranking c i ≥ c 1 ≥ c m ≥ c 2 , . . . , c m−1 STV applied to this rule gives exactly the same result as for the previous instance. We eliminate respectively candidates c 1 , c 2 , . . . , c m−1 -and all the voters who voted for c i in the ith round, transfer their vote to c m . Hence, finally c m will be selected as the winner (acceptable only for voters from g m ), while c 1 is the optimal candidate (acceptable for all the voters). Consequently, we get the distortion of 2 m−1 −1 2 m−1 .


A Comparative Study on Harvesting Plan Predicting Insurance with Two-Stage Stochastic Analysis

The exception of considering uncertainty could be very detrimental to the outcomes of any systems or phenomena in the long run. Stochastic Process describes the way of considering uncertainty in different sectors of our life. We use Linear Programming for planning at its best. It is also considered as the best optimization technique for taking decisions or planning. But this planning tool disappoints us in optimization for unexpected risk or stochasticity. Consideration of stochasticity for a farmer to devote land on different crops for harvesting could be some insurance for the farmer with the best possible outcomes. Stochastic Programming studies these types of optimization techniques with risk consideration for better decisions in every step of our life. In this paper, we described the early starting of uncertainty calculation or stochastic approach and the evolution of stochastic optimization fields. Stochastic optimization is rather important in the sense of uncertainty calculation than sensitivity analysis and works through data gained from experience. We also present a stochastic model with some uncertainty issues in harvesting to make better outcomes. Some application areas are also discussed.

Introduction
We want the best output in every step of our life with the limited resources we hold. That's why it is necessary for us that we make the best decision in every case. A good decision can help us to get a better output. A study that assists to choose our decision for the best possible outcomes is called optimization techniques. The optimization problem grows everywhere as we always seek the best output. Stochastic Process is one of the most used techniques for optimization. It is widely used in Mathematics, Finance, Economics, Medical Science, Engineering fields, etc. Stochastic Process discusses the matters where risk arises. And in the world risk is everywhere, nothing is certain. [8] Stochastic programming is the study of decision making under risk management in Optimization techniques. It was first introduced by George B. Dantzig by considering some cases related to uncertainty. We face uncertainty in every section of our life. Our expectation hampers in most cases due to uncertain parameters. These days harvesting is more challenging due to uncertain parameters arises in harvesting. A farmer has to make the decision on devoting lands for crops with a better outcome expectation. But in most cases, they fail to make a better decision due to uncertain parameters like a weather forecast, productivity of lands, selling price fluctuations, etc. Stochastic Programming could be an asset by calculating the uncertain parameters for the most possible better output.
There are many problems due to uncertainty. Influence maximization in social networks [15], Maintenance and Rehabilitation planting of Pavements [16], Ecological water requirements [17], Graph Routing Problem with risks [4,22], supply chain networks [18] are some examples where stochastic optimization techniques could be applied. Based on the problems arises for the consideration of a variety of risks in different periods of a system or phenomena, Stochastic Programming could be sectorized. The consideration of risks or uncertainty could help us to make better decisions in every step of our life.

Meaning of Stochastic
The word 'Stochastic' is a Greek word meaning something like 'aim' or 'goal'. But the word 'stochastic', we are familiar with means something happened randomly or some random approaches, which is a German word. This word appeared in English to describe some mathematical things known as the Stochastic Process. But stochastic refers to something random and so 'Stochastic Process' may refer to some randomly determined process. That is, we call it a random process for the stochastic process. [10,11] For example, let one have to go from the place 'P' to 'Q' in the following figure. There are three different ways to go to the destination. He can randomly choose any of the three ways. Similarly, we can randomly pick some students from a class, randomly choose lottery tickets and many more. Anything could happen in the future, that is also something random. That is anything that is not fixed is something random, could be happening or couldn't. We may also call it something uncertain.

Background
We live in an uncertain world. Everything around us is uncertain, nothing is certain. We don't know what happened next. A farmer could not know about the future, what will be the weather conditions in the next future. A fisherman doesn't know how many fish he will catch. A common man doesn't know whether this day will be good or bad for him. Even a researcher doesn't know about the result of this future experiments. Everywhere what we do is a prediction, predict based on the previous data. Most time these predictions result well. But is the data available everywhere, in every case? What will happen if a farmer needs to know about the weather conditions about six months earlier? What will be the predictions for share-markets? What will be the most predictable one chance?
Random things occurred in our world. Everything is uncertain or risks everywhere, anything could happen in our daily life means stochastics is everywhere. The study calculates these random things and brings us the most possible assumptions is called Stochastic Process. It is not obvious that it will be always something beneficial by calculating stochastically rather it may indicate the middle way. In case of business, something that will give you a better profit considering your losses or risks due to some uncertain cases like weather, death, etc. or some random process deficit.

Uncertainty and Stochasticity
In Stochastic Programming, three words are mostly used to describe stochasticity: uncertainty, randomness, and risk. Something is uncertain if you don't know the exact thing from many things. But if you can specify the probability of the exact thing among many things, it is stochastic then. Stochasticity means randomness, not exactly uncertainty. It means uncertainty with a possible probability distribution. For example, the weight of a book is uncertain even after you pick it up. Here the mass of the book is not random or not changes randomly and that's why it is not stochastic. Again, if we toss a coin, we know the possible probability distribution of the output and it means a coin toss is stochastic. It is easy to observe that, where is uncertainty is risks.
Remark 3.2.1. If the probability of a stochastic event is one, then the outcome is certain.

Stochastic Approach
A collection of random variables that are indexed by some mathematical set where each random variable is connected with an element in the set is called the Stochastic Process or Random Process. If we denote a set of time-indexed random variables by , then the stochastic Process is the family of the random variables defined as,

: ∈
where index set is which is a subset of the set of all real numbers. [9,10] Aleksandr Khinchin, a soviet mathematician gave the first mathematical definition of a Stochastic Process as a family of random variables indexed by the real line in the early 1930s. Other mathematicians as Andrey Kolmogorov, Joshep Doob, William Feller, Maurice Rene Frechet, Paul Levy, Wolfgang Doeblin, Harald Cremer also put considerable effort in the establishment of Stochastic Process. [11] To construct a Stochastic Process, there are two main approaches: Considering a space of functions defining a probability distribution to each element of the function or considering a set of random variables. Stochastic Process is an active topic in Mathematics, especially in Probability Theory for research as it is important for both theoretical reason and application. The stochastic Process is broadly used in mathematical models of systems and phenomena's that occur randomly.

Stochastic and Deterministic World
The theory of Stochastic Process is a field of Mathematics which deals with probabilistic systems evolving over time. The simplest Probabilistic system appears when you toss a coin. Tossing a coin is widely used in various games to determine the first. Here it is just a mechanical action, simply accelerate the coin and it moves according to some physical laws like gravity, air resistance, etc. Let's forget the physical background and concentrate on the result of the experiment, it can be either head or tail. That is, for both outcomes the probability is one-half for each. But actually, in some sense, you moved from deterministic (gravity, air resistance) to stochastic (randomness) world. [10]

Linear Programming
The Mathematical Technique for optimizing a linear function of several variables (maximizing output or minimizing cost) is called Linear Programming. It can also be called linear optimization. It is a process to gain optimizing output (maximizing output or minimizing cost) as required whose conditions are represented with the problem by using linear relationships. The linear function which has to be optimized is called the objective function and all the conditions expressed by linear relationships are called the constraints of the linear programming problem.
A linear programming problem can be expressed as the following canonical form: Optimize (Maximize or Minimize) Subject to , , And 0 where the vector of variables is and the vectors of the coefficient function are , . [20] Remarks 5.1. Sometimes 'Max' is written for Maximize and 'Min' is written for Minimize.

Why Stochastic Programming
Mathematical Programming (Optimization) is about decision making or planning. Stochastic Programming is about decision making under uncertainty. We may also call it "Mathematical Programming with random parameters." In most applications of optimization, randomness is ignored. Otherwise, it is dealt with using Sensitivity analysis. But For large-scale problems, sensitivity analysis is useless. No matter how careful you are, you can't get rid of inherent . randomness. Stochastic Programming is the way

History of Stochastic Programming
The first programming formulation of a problem and a solving process for it was given by Soviet economist Leonid Kantorovich in 1939, which is the foundation of Linear Programming (LP). Then in 1946, General Linear Programming formulation was developed by George B. Dantzig. It was about planning problems in the US air force. To solve the formulated Linear Programming Problem (LPP), Dantzig also proposed the well-known Simplex Method. Linear Programming focused on optimization of the linear objective function with respect to some requirements. In Linear Programming, we assume all the parameters of the problem are known numbers. [2,3] Most Practical decision problems involve uncertainty. Parameters are uncertain because of the lack of reliable data, measurable errors, future, and unobservable events. For the uncertainty or risks, the formulation of a developed framework that calculates the risk and gives the wished optimization with some unknown parameters is called the Stochastic Programming. Stochastic Programming stands on Robust Optimization Techniques [1950], where the parameters are known within certain bounds. [3,13] The Stochastic programming takes advantage of the probability distributions, where the rest is as same as Robust Optimization. Finding some policy that is feasible for all possible data to optimize the objective function (decision and random variables) is the aim of Stochastic Programming.

Data Requirements for Stochastic Programming
Data requirements for Stochastic Programming models are similar to the Linear Programming models except for randomness consideration. The addition data requirements in Stochastic Programming are representing uncertainty with some probability distributions. In most cases for stochastic programming, it is easy to consider some scenario distribution based on experience. A model with some random variables is easier to represent for computational algorithms. [6,7]

Introductory Stochastic Programming
There is a French saying, "The art of managing is anticipating." It is obvious that the future cannot be perfectly foreknew rather it should be considered as random or uncertain. The aim of Stochastic Programming is finding an optimal decision with random data. In that sense, stochastic is opposed to deterministic. [1] A Stochastic Programming problem can be expressed as the following canonical form: Optimize (Maximize or Minimize) , Subject to , , And 0 where the vector of variables is and the vectors of the coefficient function are , . The second term in the objective function comes for uncertain data.
is referred to as the Mathematical Expectations with respect to some random vector . [1,5,12] Stochastic Programming is decision making under risks. It may also refer to optimization under uncertainty. The field of Stochastic Programming is enriching with apace as contributions from many disciplines such as mathematics, finance, economics, operations research, probability, and statistics. [3]

Classifications of Stochastic Programming
There are many kinds of Stochastic Programming. Some mostly used kinds are: [1] a

) Two-Stage Stochastic Linear Programs with Fixed Recourse
The decision-maker takes some decision considering the randomness of some event or phenomena in the first stage. After that, some random event occurs and affects the outcome of the first stage decisions. The decision-maker has to make some second stage or recourse decision based on the outcome which may defend any bad effects that might have been experienced.

b) Probabilistic or Chance Constraints
It considers the term uncertainty of mother nature with many scenarios for taking the first stage decision which results from a big number of extra constraints including chance or probabilistic constraints.

c) Stochastic Integer Programs
It simply requires some integer in the first stage or in the second stage or both decisions while the Linear Programming problem deals with the variables that are non-negative real numbers.

d) Multi-stage Stochastic Programs with Recourse
For making the best decision on a system or phenomenon, more stages are needed. Multi-stage stochastic programs consist of a sequence of decisions that affect the outcomes over a time period.

e) Stochastic Non-linear Programs with Recourse
In this case, the objective function occurred in non-linear form like stochastic approaches for quadratic programming, quasi-concave programming, etc.

A Farmer's Scenario
Let's introduce a local Bangladeshi farmer Abdur Razzak, who lives with his two sons near Karapur village (along Nobogram Road) at Barishal District, Bangladesh. He has a total amount of 1-acre (43,560 square feet or about 2.52 Kani, a local land measurement unit) cornfield. He specializes in harvesting rice (irrigation), potatoes, chilies, groundnuts and pumpkins during the winter season in Bangladesh (December, January, February). We want to help the farmer for deciding how much land he should devote to each crop with the most possible benefits. He also raises 4 cows for producing milk or meat as per his choice. He needs rice and potato plants for the cattle feeds during that time. Since potato plants are available after cropping potatoes so it has no effect on production but he needs 0.25 metric ton potatoes for a home consumes. He needs rice plants before cropping paddy and that costs him about 0.5 metric tons of rice for cattle feed and household consumes, needed to raise in his lands. (1 metric ton equals 1000 kilograms) According to his experience, he knows that the mean yield per 0.4 acres (1 Kani) is 0.8 metric tons for rice, 3 metric tons for potatoes, 0.12 metric tons for chilies, 0.2 metric tons for groundnuts and 2.5 metric ton for pumpkins. Another profitable process is cultivating pumpkins with potatoes (mixture) which yields a total amount of 2.5 metric tons of potatoes and 1 metric ton pumpkins per 0.4-acre land. The farmer prefers this mixture process as it utilizes the land properly. The planting cost per 0.4-acre land is 24000 Taka for rice, 9600 Taka for chilies, 12000 Taka for groundnuts, 28000 Taka for the mixture of potatoes and pumpkins.
The average selling price (since it varies) for the crops are given below:

Result Explanation
The optimal solution describes that the farmer should spend his 0.25 acre land for cultivating rice which will fulfill his minimum requirements for his cattle feed and household consumes.
Raising potatoes and pumpkins is a mostly optimized category that gives him the best profit. He should devote his rest lands for raising potatoes and pumpkins. After satisfying the minimum requirements of potatoes, he can sell the rest of the products which will give him an amount of 76,062.50 Taka profit. And it is the most optimized profit for him.

Considering Stochastic Conditions
Introducing Stochastic conditions means considering uncertainty. The above problem gives us the optimal condition with an average situation of planting cost, selling price, production amount, etc. In that case, all of these things depend on some uncertainty conditions. Considering Stochastic conditions means we may assume some fixed previous data or we can also take the average situation data.
In the above example, optimized values are calculated for the farmer with a neutral position about any type of risk. But if we think something about risk aversion, we have to follow this stochastic process. In this problem, the weather forecast could be a great option for cultivating crops. For example, if there is rain this winter (not considering time), rice production will be good but potatoes production will be hampered. And that will cost the farmer a lot since he chooses to cultivate potatoes according to the optimized values. In the same manner, if it is too hot this year rice production costs will be increased.
Actually, we calculated the above-optimized values by considering the average situation of weather based on past experience. We did not calculate the possible risks in this case.
Since we could not accurately predict the risks (like weather conditions, insect prevalence, water availability, market fluctuations, etc.) earlier like four months ago. So, for the risk aversion, we may consider the stochastic process and that could make a perfect decision that would be best in all circumstances.
For the above example, we may consider three situations: (considering 20% changes in profit). Now for the construction of stochastic programming problem of the above model by using these three scenarios, we may consider some scenario index, 0 = 1, 2, 3; which may create some new variables " 12 (% = 1, 2, 3, 4, 5). If the three scenarios have probabilities of Now for the further optimized values, we will solve the above linear programming problem by using LINDO solver (a software for solving linear programming problem): [8,14] LINDO solver file

Result Explanation Based on Stochastic
Here the optimized amount of lands gives the planting areas, which has to be determined before the weather forecast and crop production. This is the first stage decision.
The other descriptions are productions, sales in three scenarios. They are the second stage decisions.
The last line gives us the overall profit which is 7,484.38 Taka less than the first optimized profit. Actually, it is the risk aversion cost.

Applications of Stochastic Programming
Randomness is everywhere and that says that stochastic programming has a variety of applications in every sector of life, society, business, etc. Based on the works on Stochastic Programming until now, we may classify the applications of Stochastic Programming into the following sections: [19] i. Production, Supply Chain and Scheduling a) Managing fleets of trailers, containers, boxcars, locomotives, business jets, etc. b) Problems with uncertain parameters like product price and demand, raw materials supply cost, production cost, operation execution durations, resource availability, etc. are the root approaches to Benders Decomposition, Lagrangian Decomposition. c) Supply Chain optimization in the meat industry, developed for Norwegian meat. Play. iii. Environment and Pollution a) Lake eutrophication (a process by which pollution over-rich in organic and mineral nutrients) management. b) Design of hedging experiments in stochastic environments where growth trajectories, climate sensitivities, and damage estimates are uncertain. c) Controlling a groundwater contaminant plume. d) Catastrophic risk management via flood and seismic risk case studies. iv. IFinance a) Refinancing mortgages with noncontractual maturity under liquidity restrictions in the market. b) Structuring index funds. c) Decentralized Risk management for Global P/C Insurance Companies. d) Asset allocation (invest) involving stocks, bonds, and cash wit wealth goals. e) Scenario-based risk management tool. f) Price protection strategies. g) Optimization of hedge funds. v. Telecom and Electricity a) A Short-term unit commitment of a hydrothermal power system under uncertainty to load, inflow to reservoirs, and prices for fuel and delivery contracts. b) Valuation of electricity generation capacity incorporating operational constraints such as start-up cost, ramp-up cost, and operating level-dependent heat rate. c) Telecommunication design problems with stochastic programming paradigm. There are more works on stochastic programming applications. These are some samples.


s2fieldsofstudy: Economics Business

text:
Determinants of Capital Budgeting Practices and Risks Adjustment among Cambodian Companies

This study uses a sample survey to analyse the capital budgeting practices of Cambodian companies in the manufacturing sector. The findings show that payback period, NPV, discounted payback period and accounting rate of return are the most popular evaluation techniques. The study also finds that interest rate risk as well as business cycle risk are mainly adjusted with a discount rate, and the commonly used method for calculating cost of capital is the after tax cost of debt and the weighted average cost of capital (WACC). Furthermore, the finding suggests that the longer the existence of a company, the more likely for it to use NPV method. The finding also reveals that the higher the amount of capital investment, the more it is likely to use the NPV method, while the smaller the amount of capital investment, the more likely the payback method will be used. With higher educational background, NPV and ARR are most likely the methods to be used in capital budgeting among the Cambodian firms.

INTRODUCTION
Companies need to invest in wealth-creating assets in order to renew, extend or replace the means by which they carry on their business. Capital investment allows companies to continue to generate cash flows in the future or to maintain the profitability of existing business activities (Watson & Head, 2010). Financial management is concerned with the planning and controlling, the provision of resources (financing decision), the allocation of resources (investment decision) and finally the control of resources (whether funds are being used effectively or not). This will ultimately lead to achieving the primary objective of financial management, i.e., the maximisation of shareholder wealth. The continuity and sustainability of every company will rely on the returns generated from its investments. According to Miller and Modigliani (1961), future corporate earnings rely on the company's investment policy, and investment decisions are responsible for a company's future profitability and its market value. The capital budgeting theory lies within the concept of shareholders' wealth maximization (Slagmulder et al., 1995) and involves investment decisions in which expenditures and receipts continue over a significant period of time (Peterson & Fabozzi, 2002;Dayananda et al., 2002).
Investment decisions have significant effects on the long term financial and operational performance of companies and are surrounded with complexity and uncertainty, which present particular challenges to management (Dempsey, 2003). Furthermore, capital investments involve huge capital outflow; it has its unique risks and estimations about the future cash flows. The uncertainty of future cash flows and other estimation difficulties that exist in practice have resulted in the development of various risk analysis and management science techniques to supplement traditional present value-based decision models (Klammer et al., 1991). One of the most difficult and intractable issues faced by decision makers and researchers is how to identify, capture and evaluate uncertainties associated with long-term investments. Thus, it requires a rigorous appraisal to weigh its cost and its benefit to the business, as well as its ultimate impact on shareholders wealth, as it requires prediction of future events (Slagmulder, 1997;Abdel-Kader & Dugdale, 1998). All capital investments involve risk and judgement. A disciplined approach helps management to make rational decisions based on the probable impact of an investment on the future of the business. The presentation of the proposed investment to the decision makers is as important as the process of gathering and evaluating information. The way such a presentation is made often determines the extent to which the appraisal influences the decision.
The main aim of this research is to investigate the prevailing capital budgeting practices when making investment decisions by Cambodian companies. This survey of prevailing capital budgeting practices within Cambodian companies includes the following: (1) examining the capital budgeting methods used in the evaluation of an investment proposal and (2) analysing the risk techniques of capital budgeting used in adjusting risk in investment proposals and (3) determinants of capital budgeting methods among Cambodian companies. During the last two decades, Cambodia experienced a strong economic growth, sustained an average growth rate of 7.6 percent between 1994 to 2015, ranking sixth in the world and the economy is expected to remain strong over the next five years (World Bank, 2017). Cambodia has attained lower middle-income status as of 2015, with gross domestic product (GDP) per capital reaching US$1,270, driven by garment exports and tourism. Cambodia has also experienced tremendous amount of business investment not only from local demand, but also heightened foreign interest in investment (Turunen & Zhou, 2017).
For example, according to statistics from the National Bank of Cambodia (NBC), total trade between Cambodia and the rest of the world in 2016 equalled US$29 billion, around 161 percent of the country's GDP. Exports from Cambodia reached US$11 billion, while imports totalled US$18 billion. Foreign direct investment (FDI) into Cambodia increased by 25 percent in 2016 amounting to $2.15 billion, most of which were channelled into the financial and manufacturing sectors (Chan, 2017). The investment inflow from foreign countries mostly went to the financial sector, especially to banking, due to the increase in banking institutions' capital reserves and the manufacturing sector. The reasons behind the increasing capital investments are underpinned by peaceful domestic environment, improved investors' confidence, favourable macroeconomic conditions, and increased capacity utilization together with expansion of economic activity (Turunen & Zhou, 2017). Therefore, nowadays, capital budgeting practices play a significant role than ever before and, to the best of researchers' knowledge, there has not been research on capital budgeting practices in Cambodia. Thus, this research has been designed to investigate prevailing capital budgeting practices in Cambodia.
investments in long-term assets, which includes either tangible (i.e. property, plant or equipment) or intangible assets (i.e. new technology, trademarks). Regardless of their nature (tangible or intangible), investment projects require careful evaluation as they require very large amounts of cash to be raised and invested, and they will determine whether the company is profitable in the future (Dayananda et al., 2002). Varshney and Maheshwari (2014) both see capital budgeting as a step by step process that businesses use to determine the merits of an investment project. The decision of whether to accept or deny an investment project as part of a company's growth initiatives involves determining the investment rate of return that such a project will generate.

Capital budgeting process
The specific capital budgeting procedure that a manager uses depends on a manager's level in the organisation, size and complexity of the project being evaluated, and the size of the organisation. Organisations seek to select the best or most profitable investment projects through a carefully designed process, so that they can maximise the return to their shareholders. They also seeks to avoid the negative strategic and financial consequences which could follow from poor investment decisions. The typical steps in the capital budgeting process highlighted by Stowe and Gagne (2018) is shown in Figure 1. However, the capital budgeting process could be dynamic, not static and could be influenced by many changing factors in an organizational environment. The process starts from generating ideas i.e. to generate a proposal for investments and there could be various reasons for taking up investments in a business. The second step in the process is to analyse the individual proposals i.e. collecting information and selecting all correct criteria to judge the desirability of the proposals. This has to match the objective of the firm to maximize its market value. The third step is to plan the capital budget i.e. organising the profitable proposals into a coordinated whole that fits within the company's overall strategies. Finally, monitoring and post-auditing i.e. involves comparison of actual results with the planned ones. Unfavourable results are identified and analysed; resolving the various difficulties of the projects helps for future selection and execution of the proposals.

Capital budgeting methods/models
Over the last three decades, significant research has been conducted on capital budgeting practices among companies. However, a review of this literature reveals inconsistent findings: financial managers and academics have not been in full agreement as to the choice of the best capital budgeting method. Therefore, there is no such defined method or model for the selection of a proposal for investments as different businesses have different requirements. The literature reveals net present value (NPV), internal rate of return (IRR), modified internal rate of return (MIRR), payback period (PB), discounted payback period (DPB), accounting rate of return (ARR) and profitability index (PI) as the more prevalent capital budgeting methods in today's business world (Elumilade et al., 2006;Maquieira et al., 2012;Ryan & Ryan, 2002). These capital budgeting methods can be either discounted cash flow (DCF) methods or non-DCF methods. The DCF is an application of the time value of money concept, i.e. the idea that money to be received or paid at some time in the future has less value, today, than an equal amount actually received or paid today. DCF analyses use future free cash flow projections and discounts them, using a required annual rate, to arrive at present value estimates. A present value estimate is then used to evaluate the potential for investment. Non-DCF do not use the concept of time value of money or discount the free cash flow projection. Largely, NPV and IRR are considered DCF methods, and PB and ARR are non-DFC methods.
Early studies generally report DCF models to be the least popular capital budgeting methods. This might be attributed to the lack of financial sophistication and limited use of computer technology in that era. Therefore, payback technique and the ARR as non-DCF were the most preferred methods (Pike, 1996;Schall, Sundam & Geijsbeek, 1978). However, with the modern financial theory, studies have shown that DCF model have now become the most prepared capital budgeting methods. Arnold and Hatzopoulos (2000) found that practitioners placed greatest emphasis on the discounting techniques (NPV and IRR) with NPV preferred to IRR (97% of large firms used NPV; 84% used IRR; 66% used payback). However, among the DCF methods, through the literature, NPV has trailed IRR in management preference. Managers have argued that the perception of a percentage return is more easily understood and comparable than an absolute dollar value increase in shareholder wealth (Liu & Stowe, 2005). Therefore, in the past, managers have chosen IRR over NPV. Management view IRR as a more cognitively efficient measure of comparison (Liu & Stowe, 2005). However, academics have long argued for the superiority of NPV over IRR.

METHODOLOGY
The study focuses on the manufacturing companies in Cambodia and a self-reported questionnaire has been administered for the collection of data. The manufacturing as well as other industrial sector accounts for 59 percent of the total GDP, while the services sector's contribution to the GDP is 41 percent (World Bank, 2016). The manufacturing sector, especially the garment industry, is the foremost driver of Cambodia's economic activity expansion, thus the selection of the manufacturing sector to be the subject of this study. The questionnaire adopted was originally used and developed in previous studies to facilitate comparison (Elumilade et al., 2006;Graham & Harvey, 2001;Maquieira et al., 2012;Ryan & Ryan, 2002;Verma et al., 2009). The structured questionnaire includes closed ended questions inquiring use of discounted/non-discounted and risk-adjusted techniques of capital budgeting, cost of capital calculations, and the capital budgeting process and activities on a Likert scale of 1 to 5.
A total of 130 questionnaires were distributed to the financial managers/CFOs on the basis that they are most likely to be involved in evaluating investment projects of the company. A covering letter attached to each questionnaire served as an introduction to the purpose of the survey and assured the confidentiality of the information supplied by each respondent. In an attempt to increase the response rate, the questionnaires were presented in-person and appointments were scheduled in advance. Fifty three usable responses were received, given a response rate of 40.8 percent, which is comparable to similar surveys. Data collected were presented and analysed using descriptive statistics and inferential statistics (including mean and percentage analysis).

ANALYSIS AND DISCUSSION Discussion on participants' characteristics
The classification of the educational background of the financial managers is presented in Table 1. Sixty percent (n=32) of managers had undergraduate degree qualification, followed by a 34 percent of them having masters/MBA (n=18). PhD and other qualifications where held by 2 percent (n=1) and 4 percent (n=2), respectively.

Source: Survey Data
The sampled companies have been classified in terms of number of years they are in business. The years were classified into 5 categories as shown in Table 2. Based on the respondents' feedback, 47 percent of the companies have been in business for between 10 and 20 years (n= 25), thirteen companies (25%) are considered to be newly established businesses that have been operating for less than 10 years. Nineteen percent of the respondents have been in business for between 31 and 40 years, while the remaining 9 percent of the respondents have stayed in business for between 21 and 30 years (n= 5). The companies have been classified in terms of size of the capital budgets that they invested. The size of the capital budgets is defined as total annual spending in term of property, plant and equipment (PPE). As shown in Table 3 below, 57 percent of companies' size in terms of their capital budgets is above $100,000 but below $10 million, while 16 of the companies (accounting for 30%) have a capital budget up to $100,000. Six companies (representing 11%) mentioned the size of their capital budget to be between $10 million and $100 million, while only one company has a capital budget between US$100 million to US$500 million. The reasons behind this huge investment could be as a result of the increased growth witnessed in the manufacturing sector and increased flow of FDI into Cambodia. This will increase the level of intense competition among companies and forcing businesses to invest in modern technological equipment and facilities in order to remain relevant and competitive.  Table 4 presents the survey findings on the purpose of investment. Forty seven percent of the respondent (n=20) stated that the dominant motivation for making investment is for expansion into new business and existing business. Moreover, 13 companies (24%) invest in order to expand existing business. Nine percent of the respondent mentioned that the reason is for equipment replacement and modernization of their operation. Expansion of existing business and equipment replacement is one the reasons of investment as mentioned by 8 percent of the respondents (n=4), while another 8 percent stated that expansion into new business (i.e., diversification) is the motive behind the investment. A majority of the respondents mentioned that expansion into existing business is the main reason for the investment. This could be in the form of increased production capacity, company acquisitions and the introduction of electronically integrated operations, thereby achieving economies of scale, increased sales or product volume to get more income and improve performance of company.

Factors determining capital budgeting method
The sample firms were asked about the factors determining the selection of capital budgeting method. Table 5 presents results from their respective managers. The most important factor determining capital budgeting method is top management familiarity (28.3%). This was followed by the importance of the project (20.8%), easy and understandability (17%), experience and competence (13.2%), finance theory (11.3%) and informal rule of thumb with just 7.5 percent. Notwithstanding, the remaining factor, i.e. other factors took the mean value less than two which implies "not important" in deciding capital budgeting decision. More so, even though Cambodia is a developing market, the findings show increase awareness and quality of management education. Financial managers are becoming more aware of the decision aids at their disposal and are more than equipped to apply the benefits of information technology explosion.

Capital budgeting methods in practice
The financial managers were asked to respond on which of the financial analysis technique(s) is (are) used in their respective businesses for the appraisal of major investments. According to the respondents, as summarized in Table 6, payback period method (PB) (n=18) is the most important technique used to evaluate investment. This was followed by the net present value (NPV) method (n=10), discounted payback (DPB) (n=9) and accounting rate of return (ARR) or ROCE (n=5). The least likely methods to be employed by the respondent are internal rate of return (IRR) (n=4), modified internal rate of return (MIRR) (n=4) and profitability index (PI) (n=3). The respondent were further asked to indicate which of the capital budgeting method is either used as primary, secondary or neither. Results are presented in Table 7.
Ninety five percent of financial managers reported that PB method is a primary method for capital budgeting, whereas 85 percent of the managers indicated NPV as a primary method. Similarly, 23 percent of the financial managers were reported to use DPB as a primary method, while only 13 percent of the managers used ARR as a primary method. The result also shows that the managers preferred to use IRR (79%), DPB (77%), PI (64%) and ARR (34%) as secondary methods. Furthermore, the result shows that MIRR is neither used as primary nor secondary method. The PB and the NPV methods are reportedly being used as both primary and secondary. Moreover, the survey results also indicate the use of multiple techniques among the companies in Cambodia; some respondents used more than one financial analysis technique when evaluating investment projects (some technique as primary, while others as secondary). This result is consistent with other studies (e.g. Alkaraan & Northcott, 2006;Arnold & Hatzopoulos, 2000;Lingesiya, 2015).

Estimation of the Cost of Capital
The respondents were asked to report on how their respective companies derive the discount rate in the appraisal of major capital investments. Table 8 presents information on usage and estimation of the cost of capital. A substantial majority of respondent companies (98%) used a cost of capital in their investment evaluation techniques, while only about 2 percent of the managers indicated that they do not use cost of capital in their capital budgeting analysis. Results show that cost of debt after tax is the most prevalent method in calculating cost of capital (n=16). The next widely used methods are the weighted average cost of capital (WACC) (n=12), the cost of debt before tax (n=8), cost of equity derived from capital asset pricing model (CAPM) (n=6) and average historical returns (n=5). Cost of equity derived from dividend growth model (DVM) and an arbitrary chosen figure are not popular methods in calculating cost of capital amongst Cambodian companies. The findings highlight that the major source of finance to fund capital investment in Cambodia is through debt finance.

Risk factors and adjustments
Appraising long-term capital investments can be quite challenging to businesses due to the uncertainty surrounding the projects' cash flows. Therefore, risk factors should be considered and adjusted for. Some of this risk factors could be unexpected inflation, interest rate movements, GDP growth or business cycle risk, movement in commodity price and movement in foreign exchange among other factors. The results of the survey as depicted in Table 9 shows that interest rate risk and business cycle risk are mainly adjusted by discount rate (63 and 85 percent, respectively). In contrast, risk of unexpected inflation, foreign exchange risk and commodity price risk are mainly adjusted by cash flows (70, 55 and 94 percent, respectively). Furthermore, risk of unexpected inflation and foreign exchange risk are both adjusted by cost of capital as well as cash flow according to some respondents, while 6 and 10 percent of the respondents neither adjust for risk of commodity price movement and foreign exchange risk respectively.

DEVELOPING AND TESTING HYPOTHESES
The discussion in the previous sub-sections was based on comparing averages. Although the discussion provided some interesting results on the use of capital budgeting methods, in this section, the study goes one step further by performing multivariate regression analysis in order to test hypotheses developed. The objective is to investigate the determinants of capital budgeting methods. In this regards, three hypotheses were developed as follows: H1. The age of the company affects the selection of capital budgeting methods. H2. The size of capital budget affects the selection of capital budgeting methods.

H3. The educational qualification of CFO affects the selection of capital budgeting methods.
With respect to the above hypotheses, the study investigated the determinants of four different capital budgeting methods, i.e. the PB, NPV, IRR and ARR methods. The MIRR and PI methods were left out, since the results in Table 6 and 7 showed that the methods were the least preferred method among Cambodian companies.
To test the hypotheses, estimations are carried out using the binary logistic regression method. Binary logistic regression 1 deals with situations in which the observed outcome for a dependent variable can have only two possible outcome. Using this approach to test the research hypotheses is also applied by Hermes, Smid and Yao (2007).
The dependent variables (Zi) are binary dummy variables created as follows: PB = 1 if the label value of a firm for the PB method is 4, it is 0 if the label value of a firm is otherwise; NPV = 1 if the score of a firm for the NPV method is 3, it is 0 if the label value of a firm is otherwise; IRR = 1 if the label value for a firm for the IRR method is 6, it is 0 if the label value of a firm is otherwise; ARR = 1 if the score of a firm for the ARR method is 7, it is 0 if the label value of a firm is otherwise. The independent variables (xi) are also binary variables. We have used the following variable specifications: SBUDGET = 1 if the size of the budget is less than 10 million dollars, it is 0 if the size of the budget is 10 million dollars or more; EDUC = 1 if the CFO of the firm has a PhD or Master/MBA degree, it is 0 if (s)he has an undergraduate degree; AGE = 1 if the firm is 30 years or older, it is 0 if firm is less than 30 years. ui = error term; Zi ranges fromα to +α.
The result from the logistic regression is presented in table 10. It shows the result for the determinants of the use of the different capital budgeting techniques. Size of capital budgeting budget (SBUDGET) and educational background of the finance managers (EDUC) are the most influential determinant of capital budgeting method among Cambodian firms. Furthermore, the results show a significant positive coefficient between age of company (AGE) and NPV; and it is statistically significant at the 10 percent level. The finding suggests that the longer the existence of a company, the more likely to use NPV method. Older companies probably have more experience and management capabilities (expertise). Thus, H1 is supported in case of NPV and not supported in case of all other methods (PB, ARR and IRR). *, **, *** significant at 10 percent, 5 percent and 1 percent levels respectively. The McFadden R 2 is an analogue to the R 2 reported for regular OLS regression models.
Moreover, the result shows a negative coefficient between SBUDGET and PB which is statistically significant at the 1 percent level. The larger the amount of capital investment, the less likely the PB method will be used. However, there is a positive relation between SBUDGET and NPV. The finding shows that the higher the amount of capital investment, the more likely the NPV method will be used. The variables are statistically significant at the 5 percent level. ARR and IRR are insignificant. The finding is consistent with previous studies where they found that organisations used NPV to appraise project when it involved huge investment (Brounen et al., 2004;Verbeeten, 2006;Hermes et al., 2007). Thus, it can be concluded that H2 was supported in case of NPV and PB, and not supported in case of all other methods.
On the other hand, with higher educational background (EDUC), NPV and ARR are most likely method to be used in capital budgeting. The result shows that EDUC is positively related to NPV and ARR and is statistically significant at the 10 percent and 5 percent levels respectively. Financial managers that are highly qualified preferred to use more advanced techniques such as NPV, while non-discounted methods like PB was preferred by less qualified personnel. Graham and Harvey, (2001) and Hermes et al. (2007) argued that managers with higher education have fewer problems in understanding more sophisticated capital budgeting techniques and consequently, they preferred to use them. Thus, H3 is supported in case of NPV and ARR.

CONCLUSION AND IMPLICATIONS
The capital budgeting practices of a sample of 53 manufacturing companies operating in Cambodia have been investigated. The results revealed that the most important factor determining capital budgeting method are top management familiarity, the importance of the project and experience and competency. PB is the most preferred capital budgeting method, followed NPV, DPB and ARR. Similarly, the study finds that interest rate risk and business cycle risk are mainly adjusted with a discount rate, and the commonly used method for calculating cost of capital was the after tax cost of debt and the WACC. Furthermore, the findings suggest that the longer the existence of a company, the more likely to use NPV method. The finding also revealed that the higher the amount of capital investment, the more likely the NPV method will be used; while the smaller the amount of capital investment, the more likely the PB method will be used. And with higher educational background, NPV and ARR are most likely the methods to be used in capital budgeting.
As far as the world of empirical knowledge is concerned, this is the first study to investigate on capital budgeting practice among Cambodian companies, thus it make a contribution to literature on practices in Cambodia and other frontier markets. The outcome of this study will be useful by practitioners in order for them to understand the prevailing capital budgeting practices at their respective firms. The study highlights the importance of firm's training and improving their skills, as well as understanding and upgrading the competencies of their staff's performance. This is because educational background has significant influence on the selection of capital budgeting method. The outcome of this study also signifies the importance of risk adjustment in capital budgeting decision. Doing so will help the organisation to find out the best technique to maximise shareholders' wealth. In general, this study serves as a foundation for future research.