-
My part is bigger than yours -- assessment within a group of peers using the pairwise comparisons method
Authors:
Konrad Kułakowski,
Jacek Szybowski
Abstract:
A project (e.g. writing a collaborative research paper) is often a group effort. At the end, each contributor identifies his or her contribution, often verbally. The reward, however, is quite often financial in nature. This leads to the question of what (percentage) share in the creation of the paper is due to individual authors. Different authors may have various opinions on the matter, and, even…
▽ More
A project (e.g. writing a collaborative research paper) is often a group effort. At the end, each contributor identifies his or her contribution, often verbally. The reward, however, is quite often financial in nature. This leads to the question of what (percentage) share in the creation of the paper is due to individual authors. Different authors may have various opinions on the matter, and, even worse, their opinions may have different relevance. In this paper, we present a simple models that allows aggregation of experts' opinions linking the priority of his preference directly to the assessment made by other experts. In this approach, the greater the contribution of a given expert, the greater the importance of his opinion. The presented method can be considered as an attempt to find consensus among a group of peers involved in the same project. Hence, its applications may go beyond the proposed study example of writing a scientific paper.
△ Less
Submitted 1 July, 2024;
originally announced July 2024.
-
Detection of decision-making manipulation in the pairwise comparisons method
Authors:
Michał Strada,
Sebastian Ernst,
Jacek Szybowski,
Konrad Kułakowski
Abstract:
Most decision-making models, including the pairwise comparison method, assume the decision-makers honesty. However, it is easy to imagine a situation where a decision-maker tries to manipulate the ranking results. This paper presents three simple manipulation methods in the pairwise comparison method. We then try to detect these methods using appropriately constructed neural networks. Experimental…
▽ More
Most decision-making models, including the pairwise comparison method, assume the decision-makers honesty. However, it is easy to imagine a situation where a decision-maker tries to manipulate the ranking results. This paper presents three simple manipulation methods in the pairwise comparison method. We then try to detect these methods using appropriately constructed neural networks. Experimental results accompany the proposed solutions on the generated data, showing a considerable manipulation detection level.
△ Less
Submitted 26 May, 2024;
originally announced May 2024.
-
Establishing a leader in a pairwise comparisons method
Authors:
Jacek Szybowski,
Konrad Kułakowski,
Jiri Mazurek,
Sebastian Ernst
Abstract:
Abstract Like electoral systems, decision-making methods are also vulnerable to manipulation by decision-makers. The ability to effectively defend against such threats can only come from thoroughly understanding the manipulation mechanisms. In the presented article, we show two algorithms that can be used to launch a manipulation attack. They allow for equating the weights of two selected alternat…
▽ More
Abstract Like electoral systems, decision-making methods are also vulnerable to manipulation by decision-makers. The ability to effectively defend against such threats can only come from thoroughly understanding the manipulation mechanisms. In the presented article, we show two algorithms that can be used to launch a manipulation attack. They allow for equating the weights of two selected alternatives in the pairwise comparison method and, consequently, choosing a leader. The theoretical considerations are accompanied by a Monte Carlo simulation showing the relationship between the size of the PC matrix, the degree of inconsistency, and the ease of manipulation. This work is a continuation of our previous research published in the paper (Szybowski et al., 2023)
△ Less
Submitted 21 March, 2024;
originally announced March 2024.
-
Almost optimal manipulation of a pair of alternatives
Authors:
Jacek Szybowski,
Konrad Kułakowski,
Sebastian Ernst
Abstract:
The role of an expert in the decision-making process is crucial, as the final recommendation depends on his disposition, clarity of mind, experience, and knowledge of the problem. However, the recommendation also depends on their honesty. But what if the expert is dishonest? Then, the answer on how difficult it is to manipulate in a given case becomes essential. In the presented work, we consider…
▽ More
The role of an expert in the decision-making process is crucial, as the final recommendation depends on his disposition, clarity of mind, experience, and knowledge of the problem. However, the recommendation also depends on their honesty. But what if the expert is dishonest? Then, the answer on how difficult it is to manipulate in a given case becomes essential. In the presented work, we consider manipulation of a ranking obtained by comparing alternatives in pairs. More specifically, we propose an algorithm for finding an almost optimal way to swap the positions of two selected alternatives. Thanks to this, it is possible to determine how difficult such manipulation is in a given case. Theoretical considerations are illustrated by a practical example.
△ Less
Submitted 12 April, 2023; v1 submitted 6 April, 2023;
originally announced April 2023.
-
Towards secure judgments aggregation in AHP
Authors:
Konrad Kułakowski,
Jacek Szybowski,
Jiri Mazurek,
Sebastian Ernst
Abstract:
In decision-making methods, it is common to assume that the experts are honest and professional. However, this is not the case when one or more experts in the group decision making framework, such as the group analytic hierarchy process (GAHP), try to manipulate results in their favor. The aim of this paper is to introduce two heuristics in the GAHP, setting allowing to detect the manipulators and…
▽ More
In decision-making methods, it is common to assume that the experts are honest and professional. However, this is not the case when one or more experts in the group decision making framework, such as the group analytic hierarchy process (GAHP), try to manipulate results in their favor. The aim of this paper is to introduce two heuristics in the GAHP, setting allowing to detect the manipulators and minimize their effect on the group consensus by diminishing their weights. The first heuristic is based on the assumption that manipulators will provide judgments which can be considered outliers with respect to those of the rest of the experts in the group. The second heuristic assumes that dishonest judgments are less consistent than the average consistency of the group. Both approaches are illustrated with numerical examples and simulations.
△ Less
Submitted 3 April, 2023; v1 submitted 27 March, 2023;
originally announced March 2023.
-
Manipulation of individual judgments in the quantitative pairwise comparisons method
Authors:
M. Strada,
K. Kułakowski
Abstract:
Decision-making methods very often use the technique of comparing alternatives in pairs. In this approach, experts are asked to compare different options, and then a quantitative ranking is created from the results obtained. It is commonly believed that experts (decision-makers) are honest in their judgments. In our work, we consider a scenario in which experts are vulnerable to bribery. For this…
▽ More
Decision-making methods very often use the technique of comparing alternatives in pairs. In this approach, experts are asked to compare different options, and then a quantitative ranking is created from the results obtained. It is commonly believed that experts (decision-makers) are honest in their judgments. In our work, we consider a scenario in which experts are vulnerable to bribery. For this purpose, we define a framework that allows us to determine the intended manipulation and present three algorithms for achieving the intended goal. Analyzing these algorithms may provide clues to help defend against such attacks.
△ Less
Submitted 1 November, 2022;
originally announced November 2022.
-
Heuristic Rating Estimation Method for the incomplete pairwise comparisons matrices
Authors:
Konrad Kułakowski,
Anna Kędzior
Abstract:
The Heuristic Rating Estimation Method enables decision-makers to decide based on existing ranking data and expert comparisons. In this approach, the ranking values of selected alternatives are known in advance, while these values have to be calculated for the remaining ones. Their calculation can be performed using either an additive or a multiplicative method. Both methods assumed that the pairw…
▽ More
The Heuristic Rating Estimation Method enables decision-makers to decide based on existing ranking data and expert comparisons. In this approach, the ranking values of selected alternatives are known in advance, while these values have to be calculated for the remaining ones. Their calculation can be performed using either an additive or a multiplicative method. Both methods assumed that the pairwise comparison sets involved in the computation were complete. In this paper, we show how these algorithms can be extended so that the experts do not need to compare all alternatives pairwise. Thanks to the shortening of the work of experts, the presented, improved methods will reduce the costs of the decision-making procedure and facilitate and shorten the stage of collecting decision-making data.
△ Less
Submitted 21 July, 2022;
originally announced July 2022.
-
Multiple-criteria Heuristic Rating Estimation
Authors:
Anna Kędzior,
Konrad Kułakowski
Abstract:
One of the most widespread multi-criteria decision-making methods is the Analytic Hierarchy Process (AHP). AHP successfully combines the pairwise comparisons method and the hierarchical approach. It allows the decision-maker to set priorities for all ranked alternatives. But what if, for some of them, their ranking value is known (e.g., it can be determined differently)? The Heuristic Rating Estim…
▽ More
One of the most widespread multi-criteria decision-making methods is the Analytic Hierarchy Process (AHP). AHP successfully combines the pairwise comparisons method and the hierarchical approach. It allows the decision-maker to set priorities for all ranked alternatives. But what if, for some of them, their ranking value is known (e.g., it can be determined differently)? The Heuristic Rating Estimation (HRE) method proposed in 2014 tried to bring the answer to this question. However, the considerations were limited to a model that did not consider many criteria. In this work, we go a step further and analyze how HRE can be used as part of the AHP hierarchical framework. The theoretical considerations are accompanied by illustrative examples showing HRE as a multiple-criteria decision-making method.
△ Less
Submitted 20 May, 2022;
originally announced May 2022.
-
Some Notes on the Similarity of Priority Vectors Derived by the Eigenvalue Method and the Geometric Mean Method
Authors:
Jiří Mazurek,
Konrad Kułakowski,
Sebastian Ernst,
Michał Strada
Abstract:
This paper examines the differences in ordinal rankings obtained from a pairwise comparison matrix using the eigenvalue method and the geometric mean method. First, we introduce several propositions on the (dis)similarity of both rankings concerning the matrix size and its inconsistency expressed by the Koczkodaj's inconsistency index. Further on, we examine the relationship between differences in…
▽ More
This paper examines the differences in ordinal rankings obtained from a pairwise comparison matrix using the eigenvalue method and the geometric mean method. First, we introduce several propositions on the (dis)similarity of both rankings concerning the matrix size and its inconsistency expressed by the Koczkodaj's inconsistency index. Further on, we examine the relationship between differences in both rankings and Kendall's rank correlation coefficient $τ$ and Spearman's rank coefficient $ρ$. Apart from theoretical results, intuitive numerical examples and Monte Carlo simulations are also provided.
△ Less
Submitted 5 September, 2022; v1 submitted 11 March, 2022;
originally announced March 2022.
-
On the Derivation of Weights from Incomplete Pairwise Comparisons Matrices via Spanning Trees with Crisp and Fuzzy Confidence Levels
Authors:
Jiri Mazurek,
Konrad Kułakowski
Abstract:
In this paper, we propose a new method for the derivation of a priority vector from an incomplete pairwise comparisons (PC) matrix. We assume that each entry of a PC matrix provided by an expert is also evaluated in terms of the expert's confidence in a particular judgment. Then, from corresponding graph representations of a given PC matrix, all spanning trees are found. For each spanning tree, a…
▽ More
In this paper, we propose a new method for the derivation of a priority vector from an incomplete pairwise comparisons (PC) matrix. We assume that each entry of a PC matrix provided by an expert is also evaluated in terms of the expert's confidence in a particular judgment. Then, from corresponding graph representations of a given PC matrix, all spanning trees are found. For each spanning tree, a unique priority vector is obtained with the weight corresponding to the confidence levels of entries that constitute this tree. At the end, the final priority vector is obtained through an aggregation of priority vectors achieved from all spanning trees. Confidence levels are modeled by real (crisp) numbers and triangular fuzzy numbers. Numerical examples and comparisons with other methods are also provided. Last, but not least, we introduce a new formula for an upper bound of the number of spanning trees, so that a decision maker gains knowledge (in advance) on how computationally demanding the proposed method is for a given PC matrix.
△ Less
Submitted 30 May, 2023; v1 submitted 19 December, 2021;
originally announced December 2021.
-
On the similarity between ranking vectors in the pairwise comparison method
Authors:
Konrad Kułakowski,
Jiří Mazurek,
Michał Strada
Abstract:
There are many priority deriving methods for pairwise comparison matrices. It is known that when these matrices are consistent all these methods result in the same priority vector. However, when they are inconsistent, the results may vary. The presented work formulates an estimation of the difference between priority vectors in the two most popular ranking methods: the eigenvalue method and the ge…
▽ More
There are many priority deriving methods for pairwise comparison matrices. It is known that when these matrices are consistent all these methods result in the same priority vector. However, when they are inconsistent, the results may vary. The presented work formulates an estimation of the difference between priority vectors in the two most popular ranking methods: the eigenvalue method and the geometric mean method. The estimation provided refers to the inconsistency of the pairwise comparison matrix. Theoretical considerations are accompanied by Montecarlo experiments showing the discrepancy between the values of both methods.
△ Less
Submitted 9 October, 2020;
originally announced October 2020.
-
New inconsistency indicators for incomplete pairwise comparisons matrices
Authors:
Jacek Szybowski,
Konrad Kułakowski,
Anna Prusak
Abstract:
We introduce two new inconsistency measures for the incomplete pairwise comparisons matrices and show several examples of their calculation. We also carry out a comparative analysis of the new inconsistency indices with the existing ones based on the Monte Carlo simulation.
We introduce two new inconsistency measures for the incomplete pairwise comparisons matrices and show several examples of their calculation. We also carry out a comparative analysis of the new inconsistency indices with the existing ones based on the Monte Carlo simulation.
△ Less
Submitted 6 December, 2019; v1 submitted 1 December, 2019;
originally announced December 2019.
-
Satisfaction of the Condition of Order Preservation: A Simulation Study
Authors:
Jiri Mazurek,
Konrad Kułakowski
Abstract:
We examine satisfaction of the condition of order preservation (COP) with respect to different levels of inconsistency for randomly generated multiplicative pairwise comparison matrices (MPCMs) of the order n = {3,4,...,9}, where a priority vector is derived both by the eigenvalue method (EV) and the geometric mean (GM) method. Our results suggest the GM method and the EV method preserve the COP c…
▽ More
We examine satisfaction of the condition of order preservation (COP) with respect to different levels of inconsistency for randomly generated multiplicative pairwise comparison matrices (MPCMs) of the order n = {3,4,...,9}, where a priority vector is derived both by the eigenvalue method (EV) and the geometric mean (GM) method. Our results suggest the GM method and the EV method preserve the COP condition almost identically, both for the less inconsistent matrices (with Saaty's consistency index CI <0.10), and the more inconsistent matrices (with CI >= 0.10). Further, we find that the frequency of the COP violations grows (almost linearly) with increasing inconsistency of MPCMs measured by Koczkodaj's inconsistency index and Saaty's consistency index respectively, and we provide graphs to illustrate these relationships for MPCMs of the order n ={4, 7, 9}.
△ Less
Submitted 22 November, 2019;
originally announced November 2019.
-
On the geometric mean method for incomplete pairwise comparisons
Authors:
Konrad Kułakowski
Abstract:
When creating the ranking based on the pairwise comparisons very often, we face difficulties in completing all the results of direct comparisons. In this case, the solution is to use the ranking method based on the incomplete PC matrix. The article presents the extension of the well known geometric mean method for incomplete PC matrices. The description of the methods is accompanied by theoretical…
▽ More
When creating the ranking based on the pairwise comparisons very often, we face difficulties in completing all the results of direct comparisons. In this case, the solution is to use the ranking method based on the incomplete PC matrix. The article presents the extension of the well known geometric mean method for incomplete PC matrices. The description of the methods is accompanied by theoretical considerations showing the existence of the solution and the optimality of the proposed approach.
△ Less
Submitted 18 May, 2019; v1 submitted 11 May, 2019;
originally announced May 2019.
-
Inconsistency indices for incomplete pairwise comparisons matrices
Authors:
Konrad Kułakowski,
Dawid Talaga
Abstract:
Comparing alternatives in pairs is a very well known technique of ranking creation. The answer to how reliable and trustworthy ranking is depends on the inconsistency of the data from which it was created. There are many indices used for determining the level of inconsistency among compared alternatives. Unfortunately, most of them assume that the set of comparisons is complete, i.e. every single…
▽ More
Comparing alternatives in pairs is a very well known technique of ranking creation. The answer to how reliable and trustworthy ranking is depends on the inconsistency of the data from which it was created. There are many indices used for determining the level of inconsistency among compared alternatives. Unfortunately, most of them assume that the set of comparisons is complete, i.e. every single alternative is compared to each other. This is not true and the ranking must sometimes be made based on incomplete data. In order to fill this gap, this work aims to adapt the selected twelve existing inconsistency indices for the purpose of analyzing incomplete data sets. The modified indices are subjected to Monte Carlo experiments. Those of them that achieved the best results in the experiments carried out are recommended for use in practice.
△ Less
Submitted 12 November, 2019; v1 submitted 28 March, 2019;
originally announced March 2019.
-
Towards quantification of incompleteness in the pairwise comparisons method
Authors:
Konrad Kułakowski,
Anna Prusak,
Jacek Szybowski
Abstract:
Alongside consistency, completeness of information is one of the key factors influencing data quality. The objective of this paper is to define ways of treating missing entries in pairwise comparisons (PC) method with respect to inconsistency and sensitivity. Two important factors related to the incompleteness of PC matrices have been identified, namely the number of missing pairwise comparisons a…
▽ More
Alongside consistency, completeness of information is one of the key factors influencing data quality. The objective of this paper is to define ways of treating missing entries in pairwise comparisons (PC) method with respect to inconsistency and sensitivity. Two important factors related to the incompleteness of PC matrices have been identified, namely the number of missing pairwise comparisons and their arrangements. Accordingly, four incompleteness indices have been developed, simple to calculate, each of them take into account both: the total number of missing data and their distribution in the PC matrix. A numerical study of the properties of these indices has been also conducted using a series of Montecarlo experiments. It demonstrated that both incompleteness and inconsistency of data equally contribute to the sensitivity of the PC matrix. Although incompleteness is only just one of the factors influencing sensitivity, a relative simplicity of the proposed indices may help decision makers to quickly estimate the impact of missing comparisons on the quality of final result.
△ Less
Submitted 9 December, 2018;
originally announced December 2018.
-
When is the condition of order preservation met?
Authors:
Konrad Kulakowski,
Jiri Mazurek,
Jaroslav Ramik,
Michael Soltys
Abstract:
This article explores a relationship between inconsistency in the pairwise comparisons method and conditions of order preservation. A pairwise comparisons matrix with elements from an alo-group is investigated. This approach allows for a generalization of previous results. Sufficient conditions for order preservation based on the properties of elements of pairwise comparisons matrix are derived. A…
▽ More
This article explores a relationship between inconsistency in the pairwise comparisons method and conditions of order preservation. A pairwise comparisons matrix with elements from an alo-group is investigated. This approach allows for a generalization of previous results. Sufficient conditions for order preservation based on the properties of elements of pairwise comparisons matrix are derived. A numerical example is presented.
△ Less
Submitted 23 March, 2018; v1 submitted 7 February, 2018;
originally announced February 2018.
-
Inconsistency in the ordinal pairwise comparisons method with and without ties
Authors:
Konrad Kułakowski
Abstract:
Comparing alternatives in pairs is a well-known method of ranking creation. Experts are asked to perform a series of binary comparisons and then, using mathematical methods, the final ranking is prepared. As experts conduct the individual assessments, they may not always be consistent. The level of inconsistency among individual assessments is widely accepted as a measure of the ranking quality. T…
▽ More
Comparing alternatives in pairs is a well-known method of ranking creation. Experts are asked to perform a series of binary comparisons and then, using mathematical methods, the final ranking is prepared. As experts conduct the individual assessments, they may not always be consistent. The level of inconsistency among individual assessments is widely accepted as a measure of the ranking quality. The higher the ranking quality, the greater its credibility. One way to determine the level of inconsistency among the paired comparisons is to calculate the value of the inconsistency index. One of the earliest and most widespread inconsistency indexes is the consistency coefficient defined by Kendall and Babington Smith. In their work, the authors consider binary pairwise comparisons, i.e., those where the result of an individual comparison can only be: better or worse. The presented work extends the Kendall and Babington Smith index to sets of paired comparisons with ties. Hence, this extension allows the decision makers to determine the inconsistency for sets of paired comparisons, where the result may also be "equal." The article contains a definition and analysis of the most inconsistent set of pairwise comparisons with and without ties. It is also shown that the most inconsistent set of pairwise comparisons with ties represents a special case of the more general set cover problem.
△ Less
Submitted 6 April, 2017; v1 submitted 3 February, 2017;
originally announced February 2017.
-
Consecutive partitions of social networks between rivaling leaders
Authors:
Malgorzata J. Krawczyk,
Krzysztof Kulakowski,
Janusz A. Holyst
Abstract:
A model algorithm is proposed to study subsequent partitions of complex networks describing social structures. The partitions are supposed to appear as actions of rivaling leaders corresponding to nodes with large degrees. The condition of a partition is that the distance between two leaders is at least three links. This ensures that the layer of nearest neighbours of each leader remains attached…
▽ More
A model algorithm is proposed to study subsequent partitions of complex networks describing social structures. The partitions are supposed to appear as actions of rivaling leaders corresponding to nodes with large degrees. The condition of a partition is that the distance between two leaders is at least three links. This ensures that the layer of nearest neighbours of each leader remains attached to him. As a rule, numerically calculated size distribution of fragments of scale-free Albert-Barabasi networks reveals one large fragment which contains the original leader (hub of the network), and a number of small fragments with opponents that are described by two Weibull distributions. Numerical simulations and mean-field theory reveal that size of the larger fragment scales as the square root of the initial network size. The algorithm is applied to the data on political blogs in U.S. (L. Adamic and N. Glance, Proc. WWW-2005). The obtained fragments are clearly polarized; either they belong to Democrats, or to the GOP.
△ Less
Submitted 17 November, 2016;
originally announced November 2016.
-
Axioms of the Analytic Hierarchy Process (AHP) and its Generalization to Dependence and Feedback: The Analytic Network Process (ANP)
Authors:
Thomas Saaty,
Konrad Kułakowski
Abstract:
The AHP/ANP are multicriteria decision-making theories that deal with both hierarchic structures when the criteria are independent of the alternatives and with networks when there is any dependence within and between elements of the decision. Both of them have been repeatedly used in practice by various researchers and practitioners. From the perspective of almost 40 years of practice in solving p…
▽ More
The AHP/ANP are multicriteria decision-making theories that deal with both hierarchic structures when the criteria are independent of the alternatives and with networks when there is any dependence within and between elements of the decision. Both of them have been repeatedly used in practice by various researchers and practitioners. From the perspective of almost 40 years of practice in solving problems using both theories, some of their properties seem to be more important than others. The article indicates four of them as fundamental for understanding AHP/ANP. These are the axioms related to structure, computation, and expectation. The mathematical formulation of the axioms is preceded by an introduction explaining the motivation behind the introduced concepts. The article is expository and it is an improved and refined version of the work [1].
△ Less
Submitted 21 June, 2016; v1 submitted 18 May, 2016;
originally announced May 2016.
-
Inferring cultural regions from correlation networks of given baby names
Authors:
Mateusz Pomorski,
Malgorzata J. Krawczyk,
Krzysztof Kulakowski,
Jaroslaw Kwapien,
Marcel Ausloos
Abstract:
We report investigations on the statistical characteristics of the baby names given between 1910 and 2010 in the United States of America. For each year, the 100 most frequent names in the USA are sorted out. For these names, the correlations between the names profiles are calculated for all pairs of states (minus Hawaii and Alaska). The correlations are used to form a weighted network which is fo…
▽ More
We report investigations on the statistical characteristics of the baby names given between 1910 and 2010 in the United States of America. For each year, the 100 most frequent names in the USA are sorted out. For these names, the correlations between the names profiles are calculated for all pairs of states (minus Hawaii and Alaska). The correlations are used to form a weighted network which is found to vary mildly in time. In fact, the structure of communities in the network remains quite stable till about 1980. The goal is that the calculated structure approximately reproduces the usually accepted geopolitical regions: the North East, the South, and the "Midwest + West" as the third one. Furthermore, the dataset reveals that the name distribution satisfies the Zipf law, separately for each state and each year, i.e. the name frequency $f\propto r^{-α}$, where r is the name rank. Between 1920 and 1980, the exponent alpha is the largest one for the set of states classified as 'the South', but the smallest one for the set of states classified as "Midwest + West". Our interpretation is that the pool of selected names was quite narrow in the Southern states. The data is compared with some related statistics of names in Belgium, a country also with different regions, but having quite a different scale than the USA. There, the Zipf exponent is low for young people and for the Brussels citizens.
△ Less
Submitted 8 December, 2015; v1 submitted 7 December, 2015;
originally announced December 2015.
-
Dynamic concurrent van Emde Boas array
Authors:
Konrad Kułakowski
Abstract:
The growing popularity of shared-memory multiprocessor machines has caused significant changes in the design of concurrent software. In this approach, the concurrently running threads communicate and synchronize with each other through data structures in shared memory. Hence, the efficiency of these structures is essential for the performance of concurrent applications. The need to find new concur…
▽ More
The growing popularity of shared-memory multiprocessor machines has caused significant changes in the design of concurrent software. In this approach, the concurrently running threads communicate and synchronize with each other through data structures in shared memory. Hence, the efficiency of these structures is essential for the performance of concurrent applications. The need to find new concurrent data structures prompted the author some time ago to propose the cvEB array modeled on the van Emde Boas Tree structure as a dynamic set alternative. This paper describes an improved version of that structure - the dcvEB array (Dynamic Concurrent van Emde Boas Array). One of the improvements involves memory usage optimization. This enhancement required the design of a tree which grows and shrinks at both: the top (root) and the bottom (leaves) level. Another enhancement concerns the successor (and predecessor) search strategy. The tests performed seem to confirm the high performance of the dcvEB array. They are especially visible when the range of keys is significantly larger than the number of elements in the collection.
△ Less
Submitted 23 September, 2015;
originally announced September 2015.
-
Emerging communities in networks - a flow of ties
Authors:
Przemyslaw Gawronski,
Malgorzata J. Krawczyk,
Krzysztof Kulakowski
Abstract:
Algorithms for search of communities in networks usually consist discrete variations of links. Here we discuss a flow method, driven by a set of differential equations. Two examples are demonstrated in detail. First is a partition of a signed graph into two parts, where the proposed equations are interpreted in terms of removal of a cognitive dissonance by agents placed in the network nodes. There…
▽ More
Algorithms for search of communities in networks usually consist discrete variations of links. Here we discuss a flow method, driven by a set of differential equations. Two examples are demonstrated in detail. First is a partition of a signed graph into two parts, where the proposed equations are interpreted in terms of removal of a cognitive dissonance by agents placed in the network nodes. There, the signs and values of links refer to positive or negative interpersonal relationships of different strength. Second is an application of a method akin to the previous one, dedicated to communities identification, to the Sierpinski triangle of finite size. During the time evolution, the related graphs are weighted; yet at the end the discrete character of links is restored. In the case of the Sierpinski triangle, the method is supplemented by adding a small noise to the initial connectivity matrix. By breaking the symmetry of the network, this allows to a successful handling of overlapping nodes.
△ Less
Submitted 23 May, 2015;
originally announced May 2015.
-
Heider balance, asymmetric ties, and gender segregation
Authors:
Małgorzata J. Krawczyk,
Marcelo del Castillo-Mussot,
Eric Hernández-Ramirez,
Gerardo G. Naumis,
Krzysztof Kułakowski
Abstract:
To remove a cognitive dissonance in interpersonal relations, people tend to divide our acquaintances into friendly and hostile parts, both groups internally friendly and mutually hostile. This process is modeled as an evolution towards the Heider balance. A set of differential equations have been proposed and validated (Kulakowski {\it et al}, IJMPC 16 (2005) 707) to model the Heider dynamics of t…
▽ More
To remove a cognitive dissonance in interpersonal relations, people tend to divide our acquaintances into friendly and hostile parts, both groups internally friendly and mutually hostile. This process is modeled as an evolution towards the Heider balance. A set of differential equations have been proposed and validated (Kulakowski {\it et al}, IJMPC 16 (2005) 707) to model the Heider dynamics of this social and psychological process. Here we generalize the model by including the initial asymmetry of the interprersonal relations and the direct reciprocity effect which removes this asymmetry. Our model is applied to the data on enmity and friendship in 37 school classes and 4 groups of teachers in México. For each class, a stable balanced partition is obtained into two groups. The gender structure of the groups reveals stronger gender segregation in younger classes, i.e. of age below 12 years, a fact consistent with other general empirical results.
△ Less
Submitted 13 May, 2015; v1 submitted 11 May, 2015;
originally announced May 2015.
-
Heavy context dependence---decisions of underground soldiers
Authors:
K. Kułakowski,
K. Malarz,
M. J. Krawczyk
Abstract:
An attempt is made to simulate the disclosure of underground soldiers in terms of theory of networks. The coupling mechanism between the network nodes is the possibility that a disclosed soldier is going to disclose also his acquaintances. We calculate the fraction of disclosed soldiers as dependent on the fraction of those who, once disclosed, reveal also their colleagues. The simulation is immer…
▽ More
An attempt is made to simulate the disclosure of underground soldiers in terms of theory of networks. The coupling mechanism between the network nodes is the possibility that a disclosed soldier is going to disclose also his acquaintances. We calculate the fraction of disclosed soldiers as dependent on the fraction of those who, once disclosed, reveal also their colleagues. The simulation is immersed in the historical context of the Polish Home Army under the communist rule in 1946-49.
△ Less
Submitted 21 March, 2015; v1 submitted 5 February, 2015;
originally announced February 2015.
-
The working group performance modeled by a bi-layer cellular automaton
Authors:
Krzysztof Malarz,
Agnieszka Kowalska-Styczeń,
Krzysztof Kułakowski
Abstract:
The problem `human and work' in a model working group is investigated by means of cellular automata technique. Attitude of members of a group towards work is measured by an indicator of loyalty to the group (the number of agents who carry out their tasks), and lack of loyalty (the number of agents, who give their tasks to other agents). Initially, all agents realize scheduled tasks one-by-one. Age…
▽ More
The problem `human and work' in a model working group is investigated by means of cellular automata technique. Attitude of members of a group towards work is measured by an indicator of loyalty to the group (the number of agents who carry out their tasks), and lack of loyalty (the number of agents, who give their tasks to other agents). Initially, all agents realize scheduled tasks one-by-one. Agents with the number of scheduled tasks larger than a given threshold change their strategy to unloyal one and start avoiding completing tasks by passing them to their colleagues. Optionally, in some conditions, we allow agents to return to loyal state; hence the rule is hysteretic. Results are presented on an influence of i) the density of tasks, ii) the threshold number of tasks assigned to the agents' forcing him/her for strategy change on the system efficiency. We show that a `black' scenario of the system stacking in a `jammed phase' (with all agents preferring unloyal strategy and having plenty tasks scheduled for realization) may be avoided when return to loyalty is allowed and either i) the number of agents chosen for task realization, or ii) the number of assigned tasks, or iii) the threshold value of assigned tasks, which force the agent to conversion from loyal strategy to unloyal one, or iv) the threshold value of tasks assigned to unloyal agent, which force him/her to task redistribution among his/her neighbors, are smartly chosen.
△ Less
Submitted 3 July, 2015; v1 submitted 18 November, 2014;
originally announced November 2014.
-
Opinion formation in an open system and the spiral of silence
Authors:
P. Gawronski,
M. Nawojczyk,
K. Kulakowski
Abstract:
A new model is formulated of the sociological effect of the spiral of silence, introduced by Elisabeth Noelle-Neumann in 1974. The probability that a new opinion is openly expressed decreases with the difference between this new opinion and the perceived opinion of the majority. We also assume that the system is open, i.e. some people enter and some leave during the process of the opinion formatio…
▽ More
A new model is formulated of the sociological effect of the spiral of silence, introduced by Elisabeth Noelle-Neumann in 1974. The probability that a new opinion is openly expressed decreases with the difference between this new opinion and the perceived opinion of the majority. We also assume that the system is open, i.e. some people enter and some leave during the process of the opinion formation. An influence of a leader is simulated by a comparison of two runs of the simulation, where the leader has different opinion in each run. The difference of the mean expressed opinions in these two runs persists long after the leader's leave.
△ Less
Submitted 26 July, 2014; v1 submitted 10 July, 2014;
originally announced July 2014.
-
Heuristic rating estimation - geometric approach
Authors:
Konrad Kułakowski,
Katarzyna Grobler-Dębska,
Jarosław Wąs
Abstract:
Heuristic Rating Estimation (HRE) is a newly proposed method supporting decisions analysis based on the use of pairwise comparisons. It allows that the ranking values of some alternatives (herein referred to as concepts) are initially known, whilst the ranks for the other concepts have yet to be estimated. To calculate the missing ranks it is assumed that the priority of every single concept can b…
▽ More
Heuristic Rating Estimation (HRE) is a newly proposed method supporting decisions analysis based on the use of pairwise comparisons. It allows that the ranking values of some alternatives (herein referred to as concepts) are initially known, whilst the ranks for the other concepts have yet to be estimated. To calculate the missing ranks it is assumed that the priority of every single concept can be determined as the weighted arithmetic mean of priorities of all the other concepts. It has been shown that the problem has admissible solution if the inconsistency of pairwise comparisons is not too high. The proposed approach adopts the heuristics according to which to determine the missing priorities a weighted geometric mean is used. In this approach, despite an increased complexity, the solution always exists and their existence does not depend on the inconsistency of the input matrix. Thus, the presented approach might be appropriate for a larger number of problems than the previous method. The formal definition of the proposed geometric heuristics is accompanied by two numerical examples.
△ Less
Submitted 28 April, 2014;
originally announced April 2014.
-
Mental ability and common sense in an artificial society
Authors:
Krzysztof Malarz,
Krzysztof Kułakowski
Abstract:
We read newspapers and watch TV every day. There are many issues and many controversies. Since media are free, we can hear arguments from every possible side. How do we decide what is wrong or right? The first condition to accept a message is to understand it; messages that are too sophisticated are ignored. So it seems reasonable to assume that our understanding depends on our ability and our cur…
▽ More
We read newspapers and watch TV every day. There are many issues and many controversies. Since media are free, we can hear arguments from every possible side. How do we decide what is wrong or right? The first condition to accept a message is to understand it; messages that are too sophisticated are ignored. So it seems reasonable to assume that our understanding depends on our ability and our current knowledge. Here we show that the consequences of this statement are surprising and funny.
△ Less
Submitted 24 March, 2014;
originally announced March 2014.
-
Notes on the existence of solutions in the pairwise comparisons method using the Heuristic Rating Estimation approach
Authors:
Konrad Kułakowski
Abstract:
Pairwise comparisons are a well-known method for modelling of the subjective preferences of a decision maker. A popular implementation of the method is based on solving an eigenvalue problem for M - the matrix of pairwise comparisons. This does not take into account the actual values of preference. The Heuristic Rating Estimation (HRE) approach is a modification of this method in which allows mode…
▽ More
Pairwise comparisons are a well-known method for modelling of the subjective preferences of a decision maker. A popular implementation of the method is based on solving an eigenvalue problem for M - the matrix of pairwise comparisons. This does not take into account the actual values of preference. The Heuristic Rating Estimation (HRE) approach is a modification of this method in which allows modelling of the reference values. To determine the relative order of preferences is to solve a certain linear equation system defined by the matrix A and the constant term vector b (both derived from M). The article explores the properties of these equation systems. In particular, it is proven that for some small data inconsistency the A matrix is an M-matrix, hence the equation proposed by the HRE approach has a unique strictly positive solution.
△ Less
Submitted 3 April, 2014; v1 submitted 17 February, 2014;
originally announced February 2014.
-
On the Properties of the Priority Deriving Procedure in the Pairwise Comparisons Method
Authors:
Konrad Kułakowski
Abstract:
The pairwise comparisons method is a convenient tool used when the relative order of preferences among different concepts (alternatives) needs to be determined. There are several popular implementations of this method, including the Eigenvector Method, the Least Squares Method, the Chi Squares Method and others. Each of the above methods comes with one or more inconsistency indices that help to de…
▽ More
The pairwise comparisons method is a convenient tool used when the relative order of preferences among different concepts (alternatives) needs to be determined. There are several popular implementations of this method, including the Eigenvector Method, the Least Squares Method, the Chi Squares Method and others. Each of the above methods comes with one or more inconsistency indices that help to decide whether the consistency of input guarantees obtaining a reliable output, thus taking the optimal decision. This article explores the relationship between inconsistency of input and discrepancy of output. A global ranking discrepancy describes to what extent the obtained results correspond to the single expert's assessments. On the basis of the inconsistency and discrepancy indices, two properties of the weight deriving procedure are formulated. These properties are proven for Eigenvector Method and Koczkodaj's Inconsistency Index. Several estimates using Koczkodaj's Inconsistency Index for a principal eigenvalue, Saaty's inconsistency index and the Condition of Order Preservation are also provided.
△ Less
Submitted 20 June, 2014; v1 submitted 31 January, 2014;
originally announced January 2014.
-
Notes on discrepancy in the pairwise comparisons method
Authors:
Konrad Kułakowski
Abstract:
The pairwise comparisons method is a convenient tool used when the relative order among different concepts (alternatives) needs to be determined. One popular implementation of the method is based on solving an eigenvalue problem for the pairwise comparisons matrix. In such cases the ranking result the principal eigenvector of the pairwise comparison matrix is adopted, whilst the eigenvalue is used…
▽ More
The pairwise comparisons method is a convenient tool used when the relative order among different concepts (alternatives) needs to be determined. One popular implementation of the method is based on solving an eigenvalue problem for the pairwise comparisons matrix. In such cases the ranking result the principal eigenvector of the pairwise comparison matrix is adopted, whilst the eigenvalue is used to determine the index of inconsistency. A lot of research has been devoted to the critical analysis of the eigenvalue based approach. One of them is the work (Bana e Costa and Vansnick, 2008). In their work authors define the conditions of order preservation (COP) and show that even for a sufficiently consistent pairwise comparisons matrices, this condition can not be met. The present work defines a more precise criteria for determining when the COP is met. To formulate the criteria a discrepancy factor is used describing how far the input to the ranking procedure is from the ranking result.
△ Less
Submitted 20 June, 2014; v1 submitted 10 December, 2013;
originally announced December 2013.
-
Concurrent bisimulation algorithm
Authors:
Konrad Kułakowski
Abstract:
The coarsest bisimulation-finding problem plays an important role in the formal analysis of concurrent systems. For example, solving this problem allows the behavior of different processes to be compared or specifications to be verified. Hence, in this paper an efficient concurrent bisimulation algorithm is presented. It is based on the sequential Paige and Tarjan algorithm and the concept of the…
▽ More
The coarsest bisimulation-finding problem plays an important role in the formal analysis of concurrent systems. For example, solving this problem allows the behavior of different processes to be compared or specifications to be verified. Hence, in this paper an efficient concurrent bisimulation algorithm is presented. It is based on the sequential Paige and Tarjan algorithm and the concept of the state signatures. The original solution follows Hopcroft's principle "process the smaller half". The presented algorithm uses its generalized version "process all but the largest one" better suited for concurrent and parallel applications. The running time achieved is comparable with the best known sequential and concurrent solutions. At the end of the work, the results of tests carried out are presented. The question of the lower bound for the running time of the optimal algorithm is also discussed.
△ Less
Submitted 10 January, 2014; v1 submitted 25 November, 2013;
originally announced November 2013.
-
Heuristic Rating Estimation Approach to The Pairwise Comparisons Method
Authors:
Konrad Kułakowski
Abstract:
The Heuristic Ratio Estimation (HRE) approach proposes a new way of using the pairwise comparisons matrix. It allows the assumption that the weights of some alternatives (herein referred to as concepts) are known and fixed, hence the weight vector needs to be estimated only for the other unknown values. The main purpose of this paper is to extend the previously proposed iterative HRE algorithm and…
▽ More
The Heuristic Ratio Estimation (HRE) approach proposes a new way of using the pairwise comparisons matrix. It allows the assumption that the weights of some alternatives (herein referred to as concepts) are known and fixed, hence the weight vector needs to be estimated only for the other unknown values. The main purpose of this paper is to extend the previously proposed iterative HRE algorithm and present all the heuristics that create a generalized approach. Theoretical considerations are accompanied by a few numerical examples demonstrating how the selected heuristics can be used in practice.
△ Less
Submitted 15 May, 2014; v1 submitted 23 August, 2013;
originally announced September 2013.
-
How many parameters to model states of mind ?
Authors:
Krzysztof Kulakowski,
Piotr Gronek,
Antoni Dydejczyk
Abstract:
A series of examples of computational models is provided, where the model aim is to interpret numerical results in terms of internal states of agents minds. Two opposite strategies or research can be distinguished in the literature. First is to reproduce the richness and complexity of real world as faithfully as possible, second is to apply simple assumptions and check the results in depth. As a r…
▽ More
A series of examples of computational models is provided, where the model aim is to interpret numerical results in terms of internal states of agents minds. Two opposite strategies or research can be distinguished in the literature. First is to reproduce the richness and complexity of real world as faithfully as possible, second is to apply simple assumptions and check the results in depth. As a rule, the results of the latter method agree only qualitatively with some stylized facts. The price we pay for more detailed predictions within the former method is that consequences of the rich set of underlying assumptions remain unchecked. Here we argue that for computational reasons, complex models with many parameters are less suitable.
△ Less
Submitted 11 June, 2013;
originally announced June 2013.
-
Competing of Sznajd and voter dynamics in the Watts-Strogatz network
Authors:
Marcin Rybak,
Krzysztof Kulakowski
Abstract:
We investigate the Watts-Strogatz network with the clustering coefficient C dependent on the rewiring probability. The network is an area of two opposite contact processes, where nodes can be in two states, S or D. One of the processes is governed by the Sznajd dynamics: if there are two connected nodes in D-state, all their neighbors become D with probability p. For the opposite process it is suf…
▽ More
We investigate the Watts-Strogatz network with the clustering coefficient C dependent on the rewiring probability. The network is an area of two opposite contact processes, where nodes can be in two states, S or D. One of the processes is governed by the Sznajd dynamics: if there are two connected nodes in D-state, all their neighbors become D with probability p. For the opposite process it is sufficient to have only one neighbor in state S; this transition occurs with probability 1. The concentration of S-nodes changes abruptly at given value of the probability p. The result is that for small p, in clusterized networks the activation of S nodes prevails. This result is explained by a comparison of two limit cases: the Watts-Strogatz network without rewiring, where C=0.5, and the Bethe lattice where C=0.
△ Less
Submitted 22 May, 2013; v1 submitted 14 January, 2013;
originally announced January 2013.
-
Strategies in crowd and crowd structure
Authors:
P. Gawronski,
K. Malarz,
M. J. Krawczyk,
J. Malinowski,
A. Kupczak,
W. Sikora,
K. Kulakowski,
J. Was,
J. Kantelhardt
Abstract:
In an emergency situation, imitation of strategies of neighbours can lead to an order-disorder phase transition, where spatial clusters of pedestrians adopt the same strategy. We assume that there are two strategies, cooperating and competitive, which correspond to a smaller or larger desired velocity. The results of our simulations within the Social Force Model indicate that the ordered phase can…
▽ More
In an emergency situation, imitation of strategies of neighbours can lead to an order-disorder phase transition, where spatial clusters of pedestrians adopt the same strategy. We assume that there are two strategies, cooperating and competitive, which correspond to a smaller or larger desired velocity. The results of our simulations within the Social Force Model indicate that the ordered phase can be detected as an increase of spatial order of positions of the pedestrians in the crowd.
△ Less
Submitted 28 September, 2012;
originally announced September 2012.
-
The Simmel effect and babies names
Authors:
M. J. Krawczyk,
A. Dydejczyk,
K. Kulakowski
Abstract:
Simulations of the Simmel effect are performed for agents in a scale-free social network. The social hierarchy of an agent is determined by the degree of her node. Particular features, once selected by a highly connected agent, became common in lower class but soon fall out of fashion and extinct. Numerical results reflect the dynamics of frequency of American babies names in 1880-2011.
Simulations of the Simmel effect are performed for agents in a scale-free social network. The social hierarchy of an agent is determined by the degree of her node. Particular features, once selected by a highly connected agent, became common in lower class but soon fall out of fashion and extinct. Numerical results reflect the dynamics of frequency of American babies names in 1880-2011.
△ Less
Submitted 1 August, 2012;
originally announced August 2012.
-
Combinatorial aspect of fashion
Authors:
M. J. Krawczyk,
K. Kulakowski
Abstract:
Simulations are performed according to the Axelrod model of culture dissemination, with modified mechanism of repulsion. Previously, repulsion was considered by Radillo-Diaz et al (Phys. Rev. E 80 (2009) 066107) as dependent on a predefined threshold. Here the probabilities of attraction and repulsion are calculated from the number of cells in the same states. We also investigate the influence of…
▽ More
Simulations are performed according to the Axelrod model of culture dissemination, with modified mechanism of repulsion. Previously, repulsion was considered by Radillo-Diaz et al (Phys. Rev. E 80 (2009) 066107) as dependent on a predefined threshold. Here the probabilities of attraction and repulsion are calculated from the number of cells in the same states. We also investigate the influence of some homogeneity, introduced to the initial state. As the result of the probabilistic definition of repulsion, the ordered state vanishes. A small cluster of a few percent of population is retained only if in the initial state a set of agents is prepared in the same state. We conclude that the modelled imitation is successful only with respect to agents, and not only their features.
△ Less
Submitted 10 May, 2012;
originally announced May 2012.
-
Bounded confidence model: addressed information maintain diversity of opinions
Authors:
Krzysztof Malarz,
Krzysztof Kulakowski
Abstract:
A community of agents is subject to a stream of messages, which are represented as points on a plane of issues. Messages are sent by media and by agents themselves. Messages from media shape the public opinion. They are unbiased, i.e. positive and negative opinions on a given issue appear with equal frequencies. In our previous work, the only criterion to receive a message by an agent is if the di…
▽ More
A community of agents is subject to a stream of messages, which are represented as points on a plane of issues. Messages are sent by media and by agents themselves. Messages from media shape the public opinion. They are unbiased, i.e. positive and negative opinions on a given issue appear with equal frequencies. In our previous work, the only criterion to receive a message by an agent is if the distance between this message and the ones received earlier does not exceed the given value of the tolerance parameter. Here we introduce a possibility to address a message to a given neighbour. We show that this option reduces the unanimity effect, what improves the collective performance.
△ Less
Submitted 15 December, 2011; v1 submitted 11 January, 2011;
originally announced January 2011.
-
Line graphs as social networks
Authors:
Malgorzata Krawczyk,
Lev Muchnik,
Anna Mańka-Krasoń,
Krzysztof Kułakowski
Abstract:
The line graphs are clustered and assortative. They share these topological features with some social networks. We argue that this similarity reveals the cliquey character of the social networks. In the model proposed here, a social network is the line graph of an initial network of families, communities, interest groups, school classes and small companies. These groups play the role of nodes, and…
▽ More
The line graphs are clustered and assortative. They share these topological features with some social networks. We argue that this similarity reveals the cliquey character of the social networks. In the model proposed here, a social network is the line graph of an initial network of families, communities, interest groups, school classes and small companies. These groups play the role of nodes, and individuals are represented by links between these nodes. The picture is supported by the data on the LiveJournal network of about 8 x 10^6 people. In particular, sharp maxima of the observed data of the degree dependence of the clustering coefficient C(k) are associated with cliques in the social network.
△ Less
Submitted 12 October, 2010;
originally announced October 2010.
