INTERNET PROVIDER COMPARISON ALGORITHM, BASED ON THE FAMILY OF ELECTRE METHODS

Considering several conflicting criteria in making decisions is a relatively common, yet often difficult task. In this work we are concerned with comparing Internet providers to help Internet users choose which provider to use according to their personal needs. We designed a multiple-criteria method based on a family of decision making methods ELECTRE [1, 2]. The following three criteria were chosen for comparison: 1) speed of data transfer; 2) time, the measurement of speed is taken; 3) variety of tariff plans. Method allows to compare any number of providers, taking into account preferences of a decision maker about the importance of different criteria, as well as using a set of available measurements. Criteria weights are calculated according to the Simos’ procedure [3]. This method is implemented in wiRating program and can be used by Internet users to compare providers in one or several cities. As a result, this program calculates provider ratings and plots them in the form of histograms.

Keywords.

Method ELECTRE, provider rating, multiple-criteria decision making, Simos’ procedure, measurement of Internet connection speed.

Introduction.

For many people access to a computer and high speed Internet become more and more important day by day. We use computers and Internet to do homework at school, to look for a job, to plan a vacation and buy tickets, to watch movies and be in touch with relatives and friends, which undeniably shows the high importance of digital technologies in people's daily lives. The number of Internet providers grows with the improvement of the software and equipment used for Internet access. Access to the Internet using radio technologies, satellite and mobile communications is also rapidly developing. As a result, questions appear about the quality of the services, as well as the possibility of comparing and selecting the most appropriate provider according to user's particular needs and requirements.

In everyday life, as well as in professional settings, we are often faced with the necessity to consider several conflicting criteria in making decisions. We usually weigh multiple criteria implicitly based on only intuition. For example, when buying a car, we are guided by criteria such as price, safety, comfort, fuel consumption and others. The first two of these criteria can be considered as conflicting. In situations like these, we intuitively decide about the importance of various criteria, but with a large number of criteria and when the risks are high it is very useful to explicitly evaluate criteria and their effects. This work is dedicated to this kind of decision making calculations, when it is necessary to make a choice between several alternatives.

One of the methods of multiple-criteria decision analysis, ELECTRE, was developed in Europe in the mid-1960s, with the subsequent development of a family of decision-making methods addressing such problems as choosing, ranking and sorting. The acronym ELECTRE stands for: ELimination Et Choix Traduisant la REalité (ELimination and Choice Expressing REality). The method was first proposed by Bernard Roy and his colleagues at SEMA consultancy company, and is usually classified as an "outranking method" of decision making. It is designed for comparing objects by as many as 12 criteria, provided there are statistical data for at least one criterion.

This work is focused on Internet providers. In general, the main characteristics of providers include such factors as data transfer speed, connection stability, cost, coverage area, variety of tariff plans, the quality of user assistance, etc. Unfortunately, not all of these characteristics are available and, therefore, cannot be used for provider rating calculations.

The goal of this work is the development of a method to compare Internet providers, using a variable set of criteria. The following criteria were chosen: 1) the speed of data transfer; 2) the time, when the measurement of speed is taken; 3) the variety of tariff plans.

Theoretical foundations of the algorithm

ELECTRE methods aim at solving problems with given multiple-criteria alternatives (i.e. Internet providers in this work). Evaluation of alternatives is relative, that is, it only establishes superiority of one alternative over another. Pairwise comparison of alternatives, taking into account the numerical value of the weight of each criterion, allows to construct matrices of concordance and discordance. The elements of these matrices are then used to calculate numerical values of the ratings for each alternative. As a result, the calculation of the provider ratings, described in more detail later in this chapter, is done in three steps: determination of criteria weights, calculation of concordance and discordance matrices and calculation of provider ratings.

Data

To obtain a sample of data we take multiple measurements of data transfer speed for each provider from point A to point B (hereinafter, route AB) at different times using different devices that have access to the Internet. As a result, we obtain a set of pairs of values: the data transfer speed and time, when the measurement was taken.

Criteria

The following criteria were chosen to compare Internet service providers in this work. 1) Speed of data transfer, denoted as сs (criterion of speed). The higher the speed, the higher the score which is given to the provider. 2) Variety of tariff plans, сp (criterion of tariff plans). The greater the variation of speed, the more diverse tariff plans are and, consequently, the higher score is given to the provider. 3) Time when the speed measurement is taken, сt (criterion of time). Three periods are considered: night (from 12 am to 8 am), day (from 8 am to 8 pm) and evening (from 8 pm to 12 am). A higher score is given to the provider that has evening tariff plans with high data transfer speeds.

One of the main assumptions made in this work is the fact that the measurements of the connection speed for each route are assumed to be equally distributed, even if they are made using different devices. Data are also assumed to be homogeneous. The value of the speed criteria is calculated as the sample mean of all the values of speed obtained for one route:

The value of the criterion of tariff plans is calculated as the sample variance of speed measurements taken using devices with unique identifier, i.e. no two values correspond to the same device. This will ensure that tariff plan of a device with several speed measurements will not be taken into account more than once. If there are several values of speed corresponding to the same device, the maximum value is taken for the calculation of sample variance. The following formula is used for the calculations

Criteria scale.

Maximum values of the criteria are chosen as follows: 100,000 kb/s for the criterion of speed; 2,500,000,000 (which is the maximum value of the sample variance, taking into account that the maximum value of speed is 100,000 kb/s and the minimum is 0 kb/s) for the criterion of tariff plans; 1.5 for the criterion of time (which is the maximum element of the time criterion vector). It is important to note, that these values can vary and do not affect the algorithm and conclusions made in this work.

Determination of criteria weights.

Weights of the criteria can be determined by several ways. Firstly, based on the opinions of users that assign a numerical value within a predetermined range to each criterion. The closer the value to the maximum, the greater is the contribution of this criterion in the calculations of the concordance/discordance matrices and provider ratings.

The second method, also based on the personal opinion of users, is to associate a «playing card» with each criterion. This method was proposed in France by Simos J. in 1990 [3]. Suppose there are N criteria, and a user is given a set of N playing cards. The name of each criterion is written on each card. The user is also given a set of white cards of the same size as the cards for each criterion. The number of white cards depends on the user's needs as explained below.

The next step is to ask the user to rank these cards in ascending order of importance of the criteria according to his/her personal choice: the first card corresponds to the least important criteria, the last card corresponds to the most important criteria. If several criteria are ascribed equal importance, these cards are joined together in one set. Also, it is important that the difference of the importance between each two consecutive criteria may vary. This smaller or bigger difference in the importance of successive criteria should be taken into account in the determination of the criteria weights. To achieve this, the user is asked to insert a number of white cards between two successive cards (or subsets of cards, if equal importance was assigned to them). The greater the difference between the weights of the criteria (i.e. between the importance of the criteria), the greater the number of white cards. The absence of white cards between two neighboring criteria means that the difference of the importance between them is minimum, we denote it by u. If there is one card between two neighboring criteria, then the difference in the importance is two times u. The same procedure is applied to bigger numbers of white cards. A detailed example of the calculation of the weights of criteria, using a set of playing cards is described in [3]. Because the whole procedure is cumbersome and is used in this work exactly as intended by the authors, it is not presented here.

Thirdly, the number of white cards can also be calculated using a sample of speed measurements. For each provider Internet speed is measured at different times, and therefore the data sets are inhomogeneous. In this work, to assess different providers we have to neglect this heterogeneity and assume that the samples of measurements are normally distributed when the number of measurements is big enough. The number of white cards, n, for the criterion of speed is determined according to the formula  where am is the amplitude that corresponds to the mostcommon speed in the histogram of the normal distribution, normalized to the total number of measurements. Coefficient 3 is assigned to the greatest number of white cards and is set independently of the measurements. Formula was derived according to the following reasoning: the greater the variation in speed values (and, therefore, the lower the maximum amplitude of the histogram), the greater importance is attributed to the criterion. In this case, the number of white cards approaches maximum. And vice versa, the lower the speed sample variance, the lower the importance of that criterion, with the number of white cards approaching zero. The above formula can also be written as n = 3(1- f (x)) , where f (x) is the value of the probability density function at the sample mean. The normal distribution is given by a Gaussian 

The value of the criterion of tariff plans is calculated in a similar manner. The difference is that the speed sample variance is calculated taking into account only the measurements, taken from devices with unique identifiers. If there are several measurements that correspond to the same device, the maximum result is taken for the calculations. This is done in order not to take into account tariff plan of the same device (user) more than once.

The following three intervals were chosen to calculate the criterion of time: from 12 am to 8 am (night), from 8 am to 8 pm (day) and from 8 pm to 12 am (evening), with the number of measurements N1, N2 and N3, respectively. The number of white cards is   calculated using the  formula similar   to the formulas  for the previous criteria:

Numerator in the ratio is equal to the maximum number among the three values: N1, N2 or N3

Having done the calculations of the white cards, we return to the Simos' procedure to calculate the weights for each criterion [3].

Calculation of concordance and discordance matrices.

According to [1], for any pair of alternatives (i.e. providers) Au and Av there is a vector of elements, that correspond to each of N criteria:

zu  = (zu1 ,..., zuN ) . In our case, Au and Av are two providers being compared, and zu  is a set of values of criteria of a particular Internet provider. The way how the values of all the criteria are calculated was described above. The concordance coefficient, αuv, for the comparison of two operators, Au   and Av, is calculated as 

 In the numerator we only summarize over those weights, for which the criterion value of provider Au  is greater or equal to the criterion value of provider Av. In other words,
X (u, v) = {j | z³zvj } is the set of criteria, for which provider Au is better than Av.




Discussion.

Up until now we were discussing the measurements taken for one route, i.e. when the data are transferred from city A to city B, using different devices that have Internet access. But the algorithm also allows to take into account several routes and calculate the resulting rating. In this case each of the ratings is included in the result with a weight coefficient proportional to the number of users of a particular provider in the city, from which the measurement is made. As a result, route ratings with a small number of users is included in the overall rating with a smaller weight coefficient, increasing the priority of routes with a large number of users.

The most time consuming step is the calculation of the values of the criteria, i.e. sample means and sample variances. Over time, the number of measurements can grow to hundreds of millions, and therefore, it is important to be able to add new samples of data without recalculating the previous ones. To discuss the possibility of adding new data, consider the following steps, schematically describing the approach of the whole algorithm:

Step 1: Obtaining a set of data

Step 2: Determination of the criteria weights

Step 3: Calculation of the values of all criteria (this includes the calculation of sums of sample elements and sums of squares of the elements for each criterion and for each provider)

Step 4: Calculation of concordance and discordance matrices

Step 5: Calculation of the ratings for each route, as well as the resulting rating, which includes all the routes

Even for a few hundred providers steps 4 and 5 take the time several orders of magnitude less than Step 3, which includes the calculation of the sums of the elements. Therefore, it is important not to recalculate the data obtained on this step. To achieve this, it is necessary to return to Step 3, when a new set of data (obtained during the next time period, for example) is to be included in the calculations, and calculate the sums and sums of squares of the elements for this set. It is also important to keep the resulting sums obtained for the previous sets of data, as they are needed for the calculation of the criteria of a new combined sample. So, when two samples of data are combined, the new values of the sample mean and sample variance are calculated using the following  formulas:

and   - The sample sizes are assumed to be different, N and K correspond to the current and new sample, respectively. As can be seen from the formulas, it does not take much time to calculate the criteria for the combined sample, provided the sums and the sums of squares of the elements are known in advance. Sample variance is a biased estimator of the theoretical variance, but the difference between biased and unbiased estimates can be neglected for large sample sizes. The next step, as before, is the calculation of concordance and discordance matrices and new ratings, which takes relatively short time. This cycle is repeated each time when a new sample of measurements is added.

Conclusion.

We developed an algorithm of multiple-criteria comparison of Internet providers. It is implemented in the program wiRating and can be used by Internet users in order to compare different providers in one or several cities. As a result, this program calculates ratings as numerical values and presents them graphically in the form of histograms.

 

List of references

1.     B. Roy, Multicriteria Methodology for Decision Aiding, Dordrecht: Kluwer Academic Publishers, 1996.

2.     Б. Руа, Классификация и выбор при наличии многих критериев (метод ЭЛЕКТРА). В кн.: Вопросы анализа и процедуры принятия решений. - М.: Мир, 1976, С. 80-107.

3.     Jose Figueira, Bernard Roy Determining the weights of criteria in the ELECTRE type methods with a revised Simos’ procedure. // European Journal of Operational Research. 2002. V. 139. P. 317–326.