Aspiration level approach in stochastic MCDM problems

The paper considers a discrete stochastic multiple criteria decision making problem. This problem is defined by a finite set of actions A, a set of attributes X and a set of evaluations of actions with respect to attributes E. In stochastic case the evaluation of each action with respect to each attribute takes form of a probability distribution. Thus, the comparison of two actions leads to the comparison of two vectors of probability distributions. In the paper a new procedure for solving this problem is proposed. It is based on three concepts: stochastic dominance, interactive approach, and preference threshold. The idea of the procedure comes from the interactive multiple objective goal programming approach. The set of actions is progressively reduced as the decision maker specifies additional requirements. At the beginning the decision maker is asked to define preference threshold for each attribute. Next, at each iteration the decision maker is confronted with the set of considered actions. If the decision maker is able to make a final choice then the procedure ends, otherwise he/she is asked to specify aspiration level. A didactical example is presented to illustrate the proposed technique.     

Classification systems based on rough sets under the belief function framework

In this paper, we present two classification approaches based on Rough Sets (RS) that are able to learn decision rules from uncertain data. We assume that the uncertainty exists only in the decision attribute values of the Decision Table (DT) and is represented by the belief functions. The first technique, named Belief Rough Set Classifier (BRSC), is based only on the basic concepts of the Rough Sets (RS). The second, called Belief Rough Set Classifier, is more sophisticated. It is based on Generalization Distribution Table (BRSC-GDT), which is a hybridization of the Generalization Distribution Table and the Rough Sets (GDT-RS). The two classifiers aim at simplifying the Uncertain Decision Table (UDT) in order to generate significant decision rules for classification process. Furthermore, to improve the time complexity of the construction procedure of the two classifiers, we apply a heuristic method of attribute selection based on rough sets. To evaluate the performance of each classification approach, we carry experiments on a number of standard real-world databases by artificially introducing uncertainty in the decision attribute values. In addition, we test our classifiers on a naturally uncertain web usage database. We compare our belief rough set classifiers with traditional classification methods only for the certain case. Besides, we compare the results relative to the uncertain case with those given by another similar classifier, called the Belief Decision Tree (BDT), which also deals with uncertain decision attribute values.     

INSDECM—an interactive procedure for stochastic multicriteria decision problems

A new interactive technique for a discrete stochastic multiattribute decision making problem is proposed in this paper. It is assumed that performance probability distribution for each action on each attribute is known. Two concepts are combined in the procedure: stochastic dominance and interactive approach. The first one is employed for generating efficient actions and constructing rankings of actions with respect to attributes. The second concept is used when the communication between the DM and the model is conducted. It is assumed that decision maker’s restrictions are defined by specifying minimal or maximal values of scalar criteria measuring either expected outcome or variability of outcomes. As such restrictions are, in general, not consistent with stochastic dominance rules, we suggest verifying this consistency and asking the decision maker to redefine inconsistent restrictions.     

A relationship between stochastic matrices and eigenvalues of products

Let {B₁,…,B_n} be a set of n rank one n×n row stochastic matrices. The next two statements are equivalent: (1) If A is an n×n nonnegative matrix, then 1 is an eigenvalue ofB_kA for each k=1,…,n if and only if A is row stochastic. (2) The n×n row stochastic matrix S whose kth row is a row of B_k for k=1,…,n is nonsingular. For any set {B₁, B₂,…, B_p} of fewer than n row stochastic matrices of order n×n and of any rank, there exists a nonnegative n×n matrix A which is not row stochastic such that 1 is eigenvalue of every B_kA, k=1,…,p.     

On entropy-preserving stochastic averages

When an n×n doubly stochastic matrix A acts on Rⁿ on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γ_n denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γ_n is a subset of B_n×Σ_n where B_n is the Birkhoff polytope and Σ_n is the probability simplex.We characterize Γ_n and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γ_n if and only if A^tAP=P. We show that for any n, Γ_n is a connected set, and is in fact piecewise-linearly contractible in B_n×Σ_n. We write Γ_n as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γ_n. Γ₃ is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable.     

Rough sets theory for multicriteria decision analysis

The original rough set approach proved to be very useful in dealing with inconsistency problems following from information granulation. It operates on a data table composed of a set U of objects (actions) described by a set Q of attributes. Its basic notions are: indiscernibility relation on U, lower and upper approximation of either a subset or a partition of U, dependence and reduction of attributes from Q, and decision rules derived from lower approximations and boundaries of subsets identified with decision classes. The original rough set idea is failing, however, when preference-orders of attribute domains (criteria) are to be taken into account. Precisely, it cannot handle inconsistencies following from violation of the dominance principle. This inconsistency is characteristic for preferential information used in multicriteria decision analysis (MCDA) problems, like sorting, choice or ranking. In order to deal with this kind of inconsistency a number of methodological changes to the original rough sets theory is necessary. The main change is the substitution of the indiscernibility relation by a dominance relation, which permits approximation of ordered sets in multicriteria sorting. To approximate preference relations in multicriteria choice and ranking problems, another change is necessary: substitution of the data table by a pairwise comparison table, where each row corresponds to a pair of objects described by binary relations on particular criteria. In all those MCDA problems, the new rough set approach ends with a set of decision rules playing the role of a comprehensive preference model. It is more general than the classical functional or relational model and it is more understandable for the users because of its natural syntax. In order to workout a recommendation in one of the MCDA problems, we propose exploitation procedures of the set of decision rules. Finally, some other recently obtained results are given: rough approximations by means of similarity relations, rough set handling of missing data, comparison of the rough set model with Sugeno and Choquet integrals, and results on equivalence of a decision rule preference model and a conjoint measurement model which is neither additive nor transitive.     

Monotonic Variable Consistency Rough Set Approaches

We consider probabilistic rough set approaches based on different versions of the definition of rough approximation of a set. In these versions, consistency measures are used to control assignment of objects to lower and upper approximations. Inspired by some basic properties of rough sets, we find it reasonable to require from these measures several properties of monotonicity. We consider three types of monotonicity properties: monotonicity with respect to the set of attributes, monotonicity with respect to the set of objects, and monotonicity with respect to the dominance relation. We show that consistency measures used so far in the definition of rough approximation lack some of these monotonicity properties. This observation led us to propose new measures within two kinds of rough set approaches: Variable Consistency Indiscernibility-based Rough Set Approaches (VC-IRSA) and Variable Consistency Dominance-based Rough Set Approaches (VC-DRSA). We investigate properties of these approaches and compare them to previously proposed Variable Precision Rough Set (VPRS) model, Rough Bayesian (RB) model, and previous versions of VC-DRSA.     

Inversion of nonlinear stochastic operators

The operator-theoretic method (Adomian and Malakian, J. Math. Anal. Appl.76(1), (1980), 183–201) recently extended Adomian's solutions of nonlinear stochastic differential equations (G. Adomian, Stochastic Systems Analysis, in “Applied Stochastic Processes,” Nonlinear Stochastic Differential Equations, J. Math. Anal. Appl.55(1) (1976), 441–452; On the modeling and analysis of nonlinear stochastic systems, in “Proceeding, International Conf. on Mathematical Modeling.” Vol. 1, pp. 29–40) to provide an efficient computational procedure for differential equations containing polynomial, exponential, and trigonometric nonlinear terms N(y). The procedure depends on the calculation of certain quantities A_n and B_n. This paper generalizes the calculation of the A_n and B_n to much wider classes of nonlinearities of the form N(y, y′,…). Essentially, the method provides a systematic computational procedure for differential equations containing any nonlinear terms of physical significance. This procedure depends on a recurrence rule from which explicit general formulae are obtained for the quantities A_n and B_n for any order n in a convenient form. This paper also demonstrates the significance of the iterative series decomposition proposed by Adomian for linear stochastic operators in 1964 and developed since 1976 for nonlinear stochastic operators. Since both the nonlinear and stochastic behavior is quite general, the results are extremely significant for applications. Processes need not, for example, be limited to either Gaussian processes, white noise, or small fluctuations.     

Ordinal regression revisited: Multiple criteria ranking using a set of additive value functions

We present a new method, called UTA^GMS, for multiple criteria ranking of alternatives from set A using a set of additive value functions which result from an ordinal regression. The preference information provided by the decision maker is a set of pairwise comparisons on a subset of alternatives A^R ⊆ A, called reference alternatives. The preference model built via ordinal regression is the set of all additive value functions compatible with the preference information. Using this model, one can define two relations in the set A: the necessary weak preference relation which holds for any two alternatives a, b from set A if and only if for all compatible value functions a is preferred to b, and the possible weak preference relation which holds for this pair if and only if for at least one compatible value function a is preferred to b. These relations establish a necessary and a possible ranking of alternatives from A, being, respectively, a partial preorder and a strongly complete relation. The UTA^GMS method is intended to be used interactively, with an increasing subset A^R and a progressive statement of pairwise comparisons. When no preference information is provided, the necessary weak preference relation is a weak dominance relation, and the possible weak preference relation is a complete relation. Every new pairwise comparison of reference alternatives, for which the dominance relation does not hold, is enriching the necessary relation and it is impoverishing the possible relation, so that they converge with the growth of the preference information. Distinguishing necessary and possible consequences of preference information on the complete set of actions, UTA^GMS answers questions of robustness analysis. Moreover, the method can support the decision maker when his/her preference statements cannot be represented in terms of an additive value function. The method is illustrated by an example solved using the UTA^GMS software. Some extensions of the method are also presented.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

p-Minors of a doubly stochastic matrix at which the permanent achieves a minimum

The author proves that if A is a matrix at which the permanent achieves a local minimum relative to the set of n x n doubly stochastic matrices, then for a_ij=0,

$\text{per A (i|j)?per A}$

.     

Euclidean ramsey theorems. I

The general Ramsey problem can be described as follows: Let A and B be two sets, and R a subset of A × B. For a?A denote by R(a) the set {b?B | (a, b) ?R}. R is called r-Ramsey if for any r-part partition of B there is some a?A with R(a) in one part. We investigate questions of whether or not certain R are r-Ramsey where B is a Euclidean space and R is defined geometrically.     

The decomposition of Cr(K) into the direct sum of subalgebras

Let A and B be closed subalgebras of C_r(X) whose direct sum is C_r(X). Some consequences of this relation are explored in this paper. For example if 1 ?A (as may be assumed) it is shown that the norm of the projection onto A is an odd integer and there is a retraction of X onto the set of common zeros of elements of B.     

r-Numbers completion problems of partial upper canonical form I

A pair (A, B), where A is an n × n matrix and B is an n × m matrix, is said to have the nonnegative integers sequence {r_j}_j=1^p as the r-numbers sequence if r₁ = rank(B) and r_j = rank[B AB … A^j−1 B] − rank[B AB … A^j−2B], 2 ≤ j ≤ p. Given a partial upper triangular matrix A of size n × n in upper canonical form and an n × m matrix B, we develop an algorithm that obtains a completion A_c of A, such that the pair (A^c, B) has an r-numbers sequence prescribed under some restrictions.     

On Supersets of Wavelet Sets

Considering a single dyadic orthonormal wavelet ψ in L ²(?), it is still an open problem whether the support of $\widehat{\psi}$ always contains a wavelet set. As far as we know, the only result in this direction is that if the Fourier support of a wavelet function is “small” then it is either a wavelet set or a union of two wavelet sets. Without assuming that a set S is the Fourier support of a wavelet, we obtain some necessary conditions and some sufficient conditions for a “small” set S to contain a wavelet set. The main results, which are in terms of the relationship between two explicitly constructed subsets A and B of S and two subsets T ₂ and D ₂ of S intersecting itself exactly twice translationally and dilationally respectively, are (1) if $A\cup B\not\subseteq T_{2}\cap D_{2}$ then S does not contain a wavelet set; and (2) if A∪B?T ₂∩D ₂ then every wavelet subset of S must be in S?(A∪B) and if S?(A∪B) satisfies a “weak” condition then there exists a wavelet subset of S?(A∪B). In particular, if the set S?(A∪B) is of the right size then it must be a wavelet set.     

Invariance principles for stochastic area and related stochastic integrals

Given an antisymmetric kernel K (K(z, z′) = ?K(z′, z)) and i.i.d. random variates Z_n, n?1, such that EK²(Z₁, Z₂)<∞, set A_n = ∑₁?i?j?nK(Z_i,Z_j), n?1. If the Z_n's are two-dimensional and K is the determinant function, A_n is a discrete analogue of Paul Lévy's so-called stochastic area. Using a general functional central limit theorem for stochastic integrals, we obtain limit theorems for the A_n's which mirror the corresponding results for the symmetric kernels that figure in theory of U-statistics.     

Attainable sets for linear stochastic control systems

Let x_t^u(w) be the solution process of the n-dimensional stochastic differential equation dx_t^u = [A(t)x_t^u + B(t) u(t)] dt + C(t) dW_t, where A(t), B(t), C(t) are matrix functions, W_t is a n-dimensional Brownian motion and u is an admissable control function. For fixed ? ? 0 and 1 ? δ ? 0, we say that x?Rⁿ is (?, δ) attainable if there exists an admissable control u such that P{x_t^u?S_?(x)} ? δ, where S_?(x) is the closed ?-ball in Rⁿ centered at x. The set of all (?, δ) attainable points is denoted by $\text{A}$(t). In this paper, we derive various properties of $\text{A}$(t) in terms of K(t), the attainable set of the deterministic control system $\text{x}\text{?}\text{= A(t)x + B(t)u}$. As well a stochastic bang-bang principle is established and three examples presented.     

Stochastic matrices. I. Similarity via stochastic transforms

Suppose two stochastic matrices A and B of order n are similar in the set

of all matrices of order n over a real field R. We obtain sufficient conditions in order that A and B be right similar, left similar, and similar in the set

of all stochastic matrices of order n over R. As a corollary, we obtain the known result that two doubly stochastic matrices of order n which are similar in

are also similar in the set

of all doubly stochastic matrices of order n over R. Examples are given to show that these sufficient conditions are not necessary and are also not vacuous. Finally, we give an application of some of these results to the transition probability matrices of stationary finite Markov processes.     

On diagonal products of doubly stochastic matrices

The following result is proved: If A and B are distinct n × n doubly stochastic matrices, then there exists a permutation σ of {1, 2,…, n} such that ∏_ia_iσ(i) > ∏_ib_iσ(i).     

Some monotonicity properties of Schur powers of matrices and related inequalities

A series of inequalities are developed relating the spectral radius ?(A ° B) of the Schur product A ° B of two nonnegative matrices A and B with those of ?(A ° A) and ?(B ° B) yielding $\text{?(A ° B) ? [?(A ° A)?(B ° B)]}\text{1}\text{2}$. As a corollary it is proved that the spectral radius of the Schur powers ?_r = ?(A^[r]), A^[r] = A ° A °?°A (r factors) satisfies $\text{(}\text{1}\text{r}\text{)}\text{log}\text{?}{}_{\mathrm{r}}$ is decreasing while $\text{(}\text{1}\text{r?1}\text{)}\text{log}\text{?}{}_{\mathrm{r}}$ is increasing, the latter provided A is a stochastic matrix. The entropy of a finite stationary Markov chain is identified with $\text{d?}{}_{\mathrm{r}}\text{dr|}{}_{\mathrm{r=1}}$. A number of majorization comparisons for the spectral radius of Schur powers is given.