Search

Best-worst method (BWM) has attracted increasing attention. It has been generalized to different fuzzy environments and applied to various real-life decision problems. This paper develops a new intuitionistic fuzzy (IF) best-worst method (IFBWM) for multi-criteria decision-making (MCDM). When a decision maker (DM) makes comparisons, there may be some hesitancies. Thus, the reference comparisons are represented as intuitionistic fuzzy values (IFVs), the Best-to-Others vector and the Others-to-Worst vector are IF vectors. According to the multiplicative consistency of intuitionistic fuzzy preference relation, this paper gives the consistency equations and views them as IF equations. The derivation of optimal IF weights of criteria is formulated as an IF decision-making problem. Thereby, a mathematical programming model is constructed to assure that the derived optimal IF weights of criteria is a normalized IF weight vector. Depending on the risk preference of DM, four linear programming models are presented to obtain the optimal IF weights based on the constructed mathematical programming model for the optimistic DM, the pessimistic DM and the neutral DM, respectively. Furthermore, this paper investigates the process of improving the consistency. Several examples are demonstrated to show the application and effectiveness of the proposed IF BWM.

The notion of zig-zag number was introduced as an attempt to provide a unified algorithmic framework for directed graphs. Nevertheless, little was known about the complexity of computing this directed graph invariant. We prove that deciding whether a directed graph has zig-zag number at most k is in NP for each fixed k ≥ 0 . Although for most of the natural decision problems this is an almost trivial result, settling k - zig-zag number in NP is surprisingly difficult. In addition, we prove that 2- zig-zag number is already an NP -hard problem.

The theory of capacities provides powerful formal methodology to account for criteria dependencies in multiple criteria decision problems. The discrete Choquet and Sugeno integrals aggregate criteria valuations accounting for criteria synergies and redundancies. We address an important problem of randomly generating capacities of special classes for simulation studies and for capacity learning through evolutionary algorithms. We discuss two efficient methods suitable for k-interactive capacities. The results are supported by the extensive numerical evidence and provide a useful tool for large scale simulations.

In this letter, we establish the convergence of fitted value iteration and fitted Q-value iteration for continuous-state continuous-action Markov decision problems (MDPs) with state-dependent action sets. We further extend the algorithm and the convergence result to the case of monotone MDPs.

Dynamic stochastic optimization models provide a powerful tool to represent sequential decision-making processes. Typically, these models use statistical predictive methods to capture the structure of the underlying stochastic process without taking into consideration estimation errors and model misspecification. In this context, we propose a data-driven prescriptive analytics framework aiming to integrate the machine learning and dynamic optimization machinery in a consistent and efficient way to build a bridge from data to decisions. The proposed framework tackles a relevant class of dynamic decision problems comprising many important practical applications. The basic building blocks of our proposed framework are: (1) a Hidden Markov Model as a predictive (machine learning) method to represent uncertainty; and (2) a distributionally robust dynamic optimization model as a prescriptive method that takes into account estimation errors associated with the predictive model and allows for control of the risk associated with decisions. Moreover, we present an evaluation framework to assess out-of-sample performance in rolling horizon schemes. A complete case study on dynamic asset allocation illustrates the proposed framework showing superior out-of-sample performance against selected benchmarks. The numerical results show the practical importance and applicability of the proposed framework since it extracts valuable information from data to obtain robustified decisions with an empirical certificate of out-of-sample performance evaluation.

The Satisfiability Modulo Theories (SMT) issue concerns the satisfiability of formulae from multiple background theories, usually expressed in the language of first-order predicate logic with equality. SMT solvers are often based on variants of the Nelson-Oppen combination method, a solver for the quantifier-free fragment of the combination of theories with disjoint signatures, via cooperation among their decision procedures. When each of the theories to be combined by the Nelson-Oppen method is convex (that is, any conjunction of its literals can imply a disjunction of equalities only when it implies at least one of the equalities) and decidable in polynomial time, the running time of the combination procedure is guaranteed to be polynomial in the size of the input formula. In this paper, we prove the convexity of a fragment of Zermelo-Fraenkel set theory, called Multi-Level Syllogistic, most of whose polynomially decidable fragments we have recently characterized., In Proceedings GandALF 2021, arXiv:2109.07798

Multi-criteria decision-making (MCDM) is concerned with structuring and solving decision problems involving multiple criteria for decision-makers in vague and inadequate environment. The “Technique for Order Preference by Similarity to Ideal Solution’’ (TOPSIS) is one of the mainly used tactic to deal with MCDM setbacks. In this article, we put forward an extension of TOPSIS with interval type-2 trapezoidal neutrosophic numbers (IT2TrNNs) using the concept of (α, β, γ)-cut. First, we present a novel approach to compute the distance between two IT2TrNNs using ordered weighted averaging (OWA) operator and (α, β, γ)-cut. Subsequently, we broaden the TOPSIS method in the context of IT2TrNNs and implemented it on a MCDM problem. Lastly, a constructive demonstration and several contrasts with the other prevailing techniques are employed to articulate the practicability of the proposed technique. The presented strategy yields a flexible solution for MCDM problems by considering the attitudes and perspectives of the decision-makers.

In this paper, we review some results of the solution of generalized stable sets introduced by Van Deemen (1991) as a variant of stable sets for abstract decision problems. This solution will be investigated and reviewed for the more general case of irreflexive but not necessarily asymmetric or complete dominance relations. It is proven that the fundamental properties of this solution are preserved also for this kind of dominance relations. Two main shortcomings of the solution of generalized stable sets are firstly that it may contain Pareto-suboptimal alternatives when the dominance relation is derived from pairwise majority comparison, and secondly that it may fail to discriminate among the alternatives under consideration when the dominance relation is a Hamilton cycle, i.e. a cycle that includes all alternatives. A refinement of generalized stable sets is proposed in order to address these two shortcomings. This refinement is called the solution of undisturbed generalized stable sets. It will be shown that undisturbed generalized stable sets are Pareto optimal and have discriminating power in the case of Hamilton cycles. In addition, and perhaps more important, we prove that this refinement is always a subset of the solutions of the uncovered set and of the unsurpassed set. This implies that undisturbed generalized stable set also may be seen as a refinement of both the uncovered set and the unsurpassed set.

We develop a mathematical and interpretative foundation for the enterprise of decision-theoretic (DT) statistical causality, which is a straightforward way of representing and addressing causal questions. DT reframes causal inference as “assisted decision-making” and aims to understand when, and how, I can make use of external data, typically observational, to help me solve a decision problem by taking advantage of assumed relationships between the data and my problem. The relationships embodied in any representation of a causal problem require deeper justification, which is necessarily context-dependent. Here we clarify the considerations needed to support applications of the DT methodology. Exchangeability considerations are used to structure the required relationships, and a distinction drawn between intention to treat and intervention to treat forms the basis for the enabling condition of “ignorability.” We also show how the DT perspective unifies and sheds light on other popular formalisations of statistical causality, including potential responses and directed acyclic graphs.

The model of coherent lower and upper conditional previsions, based on Hausdorff inner and outer measures, is proposed to represent the preference orderings and the equivalences, respectively assigned by the conscious and unconscious thought in human decision making under uncertainty. Complexity of partial information is represented by the Hausdorff dimension of the conditioning event. When the events, that describe the decision problem, are measurable is represented to the s-dimensional Hausdorff outer measure, where s is the Hausdorff dimension of the conditioning event, an optimal decision can be reached. The model is applied and discussed in Linda’s Problem and the conjunction fallacy is resolved.

In this paper, we introduce a method for resolving decision problems concerning multiple criteria in relation to a finite set of decision alternatives. This approach makes use of paraconsistent logic, Pavelka style fuzzy logic and many-valued similarity. To demonstrate the robustness of the method, two data sets, one on the performance of five mobile phone operators in Ghana and the other, a numerical example have been analysed and the rankings compared correspondingly with those of three existing dominant Multi-Attribute Decision Making (MADM) approaches, namely Elimination and Choice Translating Reality II (ELECTRE II); Preference Ranking Organisation MeTHod for Enrichment Evaluation (PROMETHEE I and II) and Technique for Order Preference by Similarity to Ideal Solution (TOPSIS). Apart from providing a ranking that is similar to these three famous outranking methods, the novel approach has the edge over them due to its ability to relatively handle large size decision problems - decision problems with numerous criteria and alternatives - without much difficulty.

In this paper, the complexity on dominating sets of the graph is suppose the G = (V, E) is a subset D of V each head not in D is adjacent to one member on the dominating number γ (G) is the number of vertices in the smallest dominant sets of G. The dominant sets problem by testing whether γ (G) ≤ K of a given graph is G and K input; It is an electronic card NP machines decision problem in computational complexity theory. Infographics, powerful infographics plus graphic mapping. In each example, each white head is adjacent to at least one red cape, and the white cap is said to be dominated by the red cape. The graph in graph is 2: The histogram is an example that illustrates the histogram.Keywords— Boundary Value Problem, Convergence of the Method, Cubic Order, Finite Difference Method, Non-uniform Step Length.

This paper first discusses the establishment of multi-attribute decision problem model and the determination of weights. Then this paper points out a situation that the method of updating weights using the fixed weight vector cannot effectively describe the weights’ variation when the state vector is continuously changing. To get rid of this problem, an iterative weight updating method is proposed. Finally, based on the existing optimistic coefficient method, the influence of high-order terms is discussed: updating weights with the fixed weight vector and updating weights with iteration. Experiments show that the higher-order terms in the state variable weight vector have a negative effect on the decision result.

Product portfolio optimization is a typical multiobjective problem. The multichoice goal programming method becomes a popular means of resolving multiobjective decision problems. However, the classic multichoice goal programming method treats the product portfolio optimization in isolation and does not consider the mutual influence between portfolio products. Researchers should consider the interaction between products in portfolio optimization so that they can be adjusted to “real world” problems. The interaction between products can be explained by population dynamics. Logistic model is a classical method to analyze the population interaction. The equilibrium point of logistic model can show the ideal state of product population coordinated development. The combination of logistic and multichoice goal programming method is an effective approach to analyze the interaction of product portfolio. This paper therefore proposes a new alternative method to formulate the multiobjective problem and also uses an illustrative example to demonstrate the usefulness of the proposed method. The comparative analysis of model optimization results shows that logistic multichoice goal programming model can take into account resource constraints, product collaboration, and output maximization. Logistic multichoice goal programming model shows good performance in the aspects of operation complexity, operation time, sensitivity analysis, and collaborative entropy evaluation.

We consider a certain class of hierarchical decision problems that can be viewed as single-leader multi-follower games, and be represented by a virtual market coordinator trying to set a price system for traded goods, according to some criterion that balances supply and demand. The objective function of the market coordinator involves the decisions of many agents, which are taken independently by solving convex optimization problems that depend on the price configuration and on realizations of future states of the economy. One traditional way of solving this problem is via a mixed complementarity formulation. However, this approach can become impractical when the numbers of agents and/or scenarios become large. This work concerns agent-wise and scenario-wise decomposition algorithms to solve the equilibrium problems in question, assuming that the solutions of the agents’ problems are unique, which is natural in many applications (when solutions are not unique, the approximating problems are still well-defined, but the convergence properties of the algorithm are not established). The algorithm is based on a previous work of the authors, where a suitable regularization of solution mappings of fully parameterized convex problems is developed. Here, we show one specific strategy to manage the regularization parameter, extend some theoretical results to the current setting, and prove that the smooth approximations of the market coordinator’s problem converge epigraphically to the original problem. Numerical experiments and some comparisons with the complementarity solver PATH are shown for the two-stage stochastic Walrasian equilibrium problem.

We define a new strict and computable hierarchy for the family of automaton semigroups, which reflects the various asymptotic behaviors of the state-activity growth. This hierarchy extends that given by Sidki for automaton groups, and also gives new insights into the latter. Its exponential part coincides with a notion of entropy for some associated automata. We prove that the Order Problem is decidable whenever the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. Gillibert showed that it is undecidable in the whole family. We extend the aforementioned hierarchy via a semi-norm making it more coarse but somehow more robust and we prove that the Order Problem is still decidable for the first two levels of this alternative hierarchy.

Some microfluidic lab-on-chip devices contain modules whose function is to mix two fluids, called reactant and buffer, in desired proportions. In one of the technologies for fluid mixing the process can be represented by a directed acyclic graph whose nodes represent micro-mixers and edges represent micro-channels. A micro-mixer has two input channels and two output channels; it receives two fluid droplets, one from each input, mixes them perfectly, and produces two droplets of the mixed fluid on its output channels. Such a mixing graph converts a set I of input droplets into a set T of output droplets, where the droplets are specified by their reactant concentrations. The most fundamental algorithmic question related to mixing graphs is to determine, given an input set I and a target set T, whether there is a mixing graph that converts I into T. We refer to this decision problem as mix-reachability. While the complexity of this problem remains open, we provide a solution to its natural sub-problem, called perfect mixability, in which we ask whether, given a collection C of droplets, there is a mixing graph that mixes C perfectly, producing only droplets whose concentration is the average concentration of C. We provide a complete characterization of such perfectly mixable sets and an efficient algorithm for testing perfect mixability. Further, we prove that any perfectly mixable set has a perfect-mixing graph of polynomial size, and that this graph can be computed in polynomial time., NSF grant CCF-1536026

Accidents occur frequently, causing huge losses to enterprises and individuals. Safety investment is an important means to prevent accidents, but how much to invest is a dilemma. Previous studies have assumed that the demand of safety investment follows some probability distribution. In practice, the distribution information of safety investment is usually limited or difficult to obtain, i.e., it is unknown. To deal with this kind of problem without a probability distribution, we construct the measures of marginal accident loss (MAL) and marginal opportunity loss (MOL) from the perspective of demand uncertainty. Robust optimization technology is utilized to establish three robust optimization models, which are the absolute robust models (ARM), deviation robust models (DRM), and relative robust models (RRM). The results of numerical analysis show that MAL is positively correlated with safety investment and MOL is negatively correlated with the uncertainty of safety investment. The above robust optimization models in this study can be applied to different enterprise’s risk scenarios. ARM, DRM, and RRM are suitable for high- and nonhigh-risk industries and other industries, respectively.

Various problems in the real world can be viewed as the Constraint Satisfaction Problem (CSP) based on several mathematical principles. This paper is a guideline for complete automation of the Timetable Problem (TTP) formulated as CSP, which we are able to solve algorithmically, and so the advantage is the possibility to solve the problem on a computer. The theory presents fundamental concepts and characteristics of CSP along with an overview of basic algorithms used in terms of its solution and forms the TTP as CSP and delineates the basic properties and requirements to be met in the timetable. The theory in our paper is mostly based on the Jeavons, Cohen, Gyssens, Cooper, and Koubarakis work, on the basis of which we've constructed a computer programme, which verifies the validity and functionality of the Constraint satisfaction method for solving the Timetable Problem. The solution of the TTP, which is characterized by its basic characteristics and requirements, was implemented by a tree-based search algorithm to a program and our main contribution is an algorithmic verification of constraints abilities and reliability when solving a TTP by means of constraints. The created program was also used to verify the time complexity of the algorithmic solution.

Pachinko is a Japanese mechanical gambling game similar to pinball. Recently, several mathematical models of Pachinko have been proposed. A number of pins are spiked in a field. A ball drops from the top of the playfield and the ball falls down. In the 50-50 model, if the ball hits a pin, it moves to the left or right passage of the pin with an equal probability. An arrangement of pins generates a distribution of the drop probability for all of the columns. This problem was considered by generating uniform distributions. Previous studies have demonstrated that the ( 1 / 2 a ) -uniform distribution is possible for a ∈ { 0 , 1 , 2 , 3 , 4 } and is conjectured so that it is possible for any positive integer a. This study describes the constructive proof for this conjecture. This study also formalizes a natural decision problem yielded by this model while investigating its computational complexity. More precisely, given any drop-probability distribution A and any partial drop-probability distribution B, this study uses non-deterministic polynomial-time (NP) hardness to determine if there exists a pin arrangement that transforms A into B.

For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consider the problem of determining whether there is a partition of the vertex set into in- and out-dominating sets of the digraph. In this paper, we obtain the following results: (1) The decision problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a polynomial time algorithm for deciding the existence of such partition.

Optimal policies in Markov decision problems may be quite sensitive with regard to transition probabilities. In practice, some transition probabilities may be uncertain. The goals of the present study are to find the robust range for a certain optimal policy and to obtain value intervals of exact transition probabilities. Our research yields powerful contributions for Markov decision processes (MDPs) with uncertain transition probabilities. We first propose a method for estimating unknown transition probabilities based on maximum likelihood. Since the estimation may be far from accurate, and the highest expected total reward of the MDP may be sensitive to these transition probabilities, we analyze the robustness of an optimal policy and propose an approach for robust analysis. After giving the definition of a robust optimal policy with uncertain transition probabilities represented as sets of numbers, we formulate a model to obtain the optimal policy. Finally, we define the value intervals of the exact transition probabilities and construct models to determine the lower and upper bounds. Numerical examples are given to show the practicability of our methods.

The well known cycle double cover conjecture in graph theory is strongly related to the compatible circuit decomposition problem. A recent result by Fleischner et al. (2018) gives a sufficient condition for the existence of a compatible circuit decomposition in a transitioned 2-connected Eulerian graph, which is based on an extension of the definition of K 5 -minors to transitioned graphs. Graphs satisfying this condition are called SUD- K 5 -minor-free graphs. In this work we formulate a generalization of this property by replacing the K 5 by a 4-regular transitioned graph H , which is part of the input. Furthermore, we consider the decision problem of checking for two given graphs if the extended property holds. We prove that this problem is NP -complete and fixed parameter tractable with the size of H as parameter. We then formulate an equivalent problem, present a mathematical model for it, and prove its correctness. This mathematical model is then translated into a mixed integer linear program (MIP) for solving it in practice. Computational results show that the MIP formulation can be solved for small instances in reasonable time. In our computations we found snarks with perfect matchings whose contraction leads to SUD- K 5 -minor-free graphs that contain K 5 -minors. Furthermore, we verified that there exists a perfect pseudo-matching whose contraction leads to a SUD- K 5 -minor-free graph for all snarks with up to 22 vertices.

Tree-based networks are a class of phylogenetic networks that attempt to formally capture what is meant by “tree-like” evolution. A given non-tree-based phylogenetic network, however, might appear to be very close to being tree-based, or very far. In this paper, we formalize the notion of proximity to tree-based for unrooted phylogenetic networks, with a range of proximity measures. These measures also provide characterizations of tree-based networks. One measure in particular, related to the nearest neighbour interchange operation, allows us to define the notion of “tree-based rank”. This provides a subclassification within the tree-based networks themselves, identifying those networks that are “very” tree-based. Finally, we prove results relating tree-based networks in the settings of rooted and unrooted phylogenetic networks, showing effectively that an unrooted network is tree-based if and only if it can be made a rooted tree-based network by rooting it and orienting the edges appropriately. This leads to a clarification of the contrasting decision problems for tree-based networks, which are polynomial in the rooted case but NP complete in the unrooted.

In 1946, Emil Leon Post (Bulletin of Amer. Math. Soc. 52 (1946), 264-268) introduced his famouscorrespondence decision problem, nowadays known as the Post Correspondence Problem (PCP).Post proved the undecidability of the PCP by areduction from his normal systems. In the presentarticle we follow the steps of Post, and give another, somewhat simpler and more straightforwardproof of the undecidability of the problem by using the same source of reductions as Post did.We investigate these, very different, techniques, and point out out some peculiarities in theapproach used by Post.

A subset $$M\subseteq E$$ of edges of a graph $$G=(V,E)$$ is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is the same as G[S], the subgraph of G induced by $$S=\{v \in V |$$ v is incident on an edge of $$M\}$$ . The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. Given a graph G and a positive integer k, the Induced Matching Decision problem is to decide whether G has an induced matching of cardinality at least k. The Maximum Weight Induced Matching problem in a weighted graph $$G=(V,E)$$ in which the weight of each edge is a positive real number, is to find an induced matching such that the sum of the weights of its edges is maximum. It is known that the Induced Matching Decision problem and hence the Maximum Weight Induced Matching problem is known to be NP-complete for general graphs and bipartite graphs. In this paper, we strengthened this result by showing that the Induced Matching Decision problem is NP-complete for star-convex bipartite graphs, comb-convex bipartite graphs, and perfect elimination bipartite graphs, the subclasses of the class of bipartite graphs. On the positive side, we propose polynomial time algorithms for the Maximum Weight Induced Matching problem for circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial time reductions from the Maximum Weight Induced Matching problem in these graph classes to the Maximum Weight Induced Matching problem in convex bipartite graphs.

Elementary net systems (ENS) are the most fundamental class of Petri nets. Given a labeled transition system (TS) A, feasibility is the NP-complete decision problem whether A can be synthesized into an ENS. We analyze the impact of state degree, the number of allowed successors and predecessors of states in A, and event manifoldness, the amount of occurrences that an event can have in A, on the computational complexity of feasibility and the related event state separation property (ESSP) and state separation property (SSP). Feasibility, ESSP and SSP are NP-complete for TSs with state degree one and event manifoldness not less than three and for TSs with state degree and event manifoldness at least two. As we also show that SSP becomes tractable for TSs with state degree one and event manifoldness two, the only cases left open are ESSP and feasibility for the same input restriction.

We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted-reward and average-reward Markov decision problems. By leveraging the value–policy duality, the algorithm adaptively samples state–action–state transitions and makes exponentiated primal–dual updates. We show that it finds an ɛ-optimal policy using nearly linear runtime in the worst case for a fixed value of the discount factor. When the Markov decision process is ergodic and specified in some special data formats, for fixed values of certain ergodicity parameters, the algorithm finds an ɛ-optimal policy using sample size and time linear in the total number of state–action pairs, which is sublinear in the input size. These results provide a new venue and complexity benchmarks for solving stochastic dynamic programs.

Nowadays, most real-world decision problems consist of two or more incommensurable or conflicting objectives to be optimized simultaneously, so-called multiobjective optimization problems (MOPs). Usually, a decision maker (DM) prefers only a single optimum solution in the Pareto front (PF), and the PF’s knee solution is logically the one if there are no user-specific or problem-specific preferences. In this context, the biomedical ontology matching problem in the Semantic Web (SW) domain is investigated, which can be of help to integrate the biomedical knowledge and facilitate the translational discoveries. Since biomedical ontologies often own large-scale concepts with rich semantic meanings, it is difficult to find a perfect alignment that could meet all DM’s requirements, and usually, the matching process needs to trade-off two conflict objectives, i.e., the alignment’s recall and precision. To this end, in this work, the biomedical ontology matching problem is first defined as a MOP, and then a compact multiobjective particle swarm optimization algorithm driven by knee solution (CMPSO-K) is proposed to address it. In particular, a compact evolutionary mechanism is proposed to efficiently optimize the alignment’s quality, and a max-min approach is used to determine the PF’s knee solution. In the experiment, three biomedical tracks provided by Ontology Alignment Evaluation Initiative (OAEI) are used to test CMPSO-K’s performance. The comparisons with OAEI’s participants and PSO-based matching technique show that CMPSO-K is both effective and efficient.

A binary matrix M has the consecutive ones property (C1P) for rows (resp. columns) if there exists a permutation of its columns (resp. rows) that arranges the ones consecutively in all the rows (resp. columns). If M has the C1P for rows and the C1P for columns, then M is said to have the simultaneous consecutive ones property (SC1P). In this article, we consider the classical complexity and fixed-parameter tractability of a few variants of decision problems related to the SC1P. Given a binary matrix M and a positive integer d , we focus on problems that decide whether there exists a set of rows, columns, and rows as well as columns, respectively, of size at most d in M , whose deletion results in a matrix with the SC1P. We also consider problems that decide whether there exists a set of 0-entries, 1-entries and 0-entries as well as 1-entries, respectively, of size at most d in M , whose flipping results in a matrix with the SC1P. In this paper, we show that all the above mentioned problems are NP-complete. We could also prove that all these problems are fixed-parameter tractable with respect to solution size as the parameter, except for two variants (flipping 1-entries and flipping 0/1-entries). We also give improved FPT algorithms for certain problems on restricted binary matrices.

Human decision-making involves cognitive processes of selection, evaluation, and interpretation among candidate solutions in order to solve decision problems. Nonintelligent decision support systems (DSS) lack automatic interpretations, at least in a low level scale, which can lead to undesired solutions. To tackle this limitation, hence producing enhanced decision making, a hybrid intelligent decision support approach is presented, which combines case-based reasoning cycle, semiotic concepts, and self-organizing maps. In addition, a novel sign deconstruction mechanism is introduced as foundation of the new approach and affords better interpretability and contextualization of candidate solutions without compromising efficiency and precision. The obtained results confirm that our proposed approach has the potential to be readily applicable to decision problems, particularly the ones that are of subjective nature. Moreover, the put forward approach may integrate some unlikely elements of linguistics and cognitive science which could fundamentally help the enhancement of DSS.

A group decision-making (GDM) process is a social cognition process, which is a sub-topic of cognitive computation. The normalization of attribute values plays an important role in multi-attribute decision-making (MADM) and GDM problems. However, this research finds that the existing normalization methods are not always reasonable for GDM problems. To solve the problem of attribute normalization in GDM systems, some new normalization models are developed in this paper. An integrative study contributes to cognitive MADM and GDM systems. In existing normalization models, there are some bounds, such as $\text {Max}(u_{j}), \text {Min}(u_{j}),\sum (u_{j}),\text {and} \sqrt {\sum (u_{j})^{2}}$ . They are limited to a single attribute vector uj. The bound of new normalization method proposed in this work is related to one or more attribute vectors, in which the attribute values are graded in the same measure system. These related attribute vectors may be distributed to all decision matrices graded by this decision system. That is, the new bound in developed normalization model is an uniform bound, which is related to a decision system. For example, this uniform bound can be written as one of $\text {Max}(.), \text {Min}(.), \sum (.),\sqrt {\sum (.)^{2}}$ . Some illustrative examples are provided. A practical application to the evaluation of software reliability is introduced in order to illustrate the feasibility and practicability of methods introduced in this paper. Some experimental and computational comparisons are provided. The results show that new normalization methods are feasibility and practicability, and they are superior to the classical normalization methods. This work has provided some new normalization models. These new methods can adapt to all decision problems, including MADM and GDM problems. Some important limitations and future research are introduced.

Pattern languages have been an object of study in various subfields of computer science for decades. This paper introduces and studies a decision problem on patterns called the finite distinguishability problem: given a pattern π, are there finite sets T + and T − of strings such that the only pattern language containing all strings in T + and none of the strings in T − is the language generated by π? This problem is related to the complexity of teacher-directed learning, as studied in computational learning theory, as well as to the long-standing open question whether the equivalence of two patterns is decidable. We show that finite distinguishability is decidable if the underlying alphabet is of size other than 2 or 3, and provide a number of related results, such as (i) partial solutions for alphabet sizes 2 and 3, and (ii) decidability proofs for variants of the problem for special subclasses of patterns, namely, regular, 1-variable, and non-cross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacher-directed learning, namely the teaching dimension and the recursive teaching dimension.

We study mean field Stackelberg games between a major player (the leader) and a large population of minor players (the followers). By treating the mean field as part of the dynamics of the major player and a representative minor player, we Markovianize the decision problems and employ dynamic programming to determine the equilibrium strategy in a state feedback form. We show that for linear quadratic (LQ) models, the feedback equilibrium strategy is time consistent. We further give the explicit solution in a discrete-time LQ model.

It is known that if there exists a Gr?bner-Shirshov basis for a group G, then we say that one of the decision problem, namely the word problem, is solvable for G as well. Therefore, as the main target of this paper, we will present a (non-commutative) Gr?bner-Shirshov basis for the braid group associated with the congruence classes of complex reflection group G12 which will give us normal forms of the elements of G12 and so will obtain a new algorithm to solve the word problem over it.

A graph H is a vertex-minor of a graph G if it can be reached from G by the successive application of local complementations and vertex deletions. Vertex-minors have been the subject of intense study in graph theory over the last decades and have found applications in other fields such as quantum information theory. Therefore it is natural to consider the computational complexity of deciding whether a given graph G has a vertex-minor isomorphic to another graph H, which was previously unknown. Here we prove that this decision problem is NP-complete, even when restricting H, G to be circle graphs, a class of graphs that has a natural relation to vertex-minors., Comment: 15 pages, 4 figures. arXiv admin note: text overlap with arXiv:1805.05306

Decisions are often based on imprecise, uncertain or vague information. Likewise, the consequences of an action are often equally unpredictable, thus putting the decision maker into a twofold jeopardy. Assuming that the effects of an action can be modeled by a random variable, then the decision problem boils down to comparing different effects (random variables) by comparing their distribution functions. Although the full space of probability distributions cannot be ordered, a properly restricted subset of distributions can be totally ordered in a practically meaningful way. We call these loss-distributions, since they provide a substitute for the concept of loss-functions in decision theory. This article introduces the theory behind the necessary restrictions and the hereby constructible total ordering on random loss variables, which enables decisions under uncertainty of consequences. Using data obtained from simulations, we demonstrate the practical applicability of our approach., Comment: preprint of a correction to the article with the same name, published with PLOS ONE, and currently under review

Let p be a positive integer. The bondage number (p-bondage number, p-total bondage number, p-tuple bondage number, double bondage number) of a graph G, is the minimum number of edges whose removal from G results in a graph with larger domination number (respectively, p-domination number, p-total domination number, p-tuple domination number, double domination number). In this paper we show that the decision problems for these variants are NP-hard, even when restricted to bipartite graphs, thus improving the results on the complexity of multiple bondage given in N. Jafari Rad (2015) [14] .

A total dominating set of a graph G = ( V , E ) with no isolated vertex is a set D ⊆ V ( G ) such that every vertex of G is adjacent to a vertex in D. A total dominating set D of G is a locating-total dominating set if for every pair of distinct vertices u and v in V − D , N ( u ) ∩ D ≠ N ( v ) ∩ D . Let γ L t ( G ) be the minimum cardinality of a locating-total dominating set of G. In this paper, we show that the decision problem for locating-total domination number is NP-complete for several classes of graphs. In particular, we answer a problem posed in Miller et al. (2017) [13] . We also define classes of graphs for which the complexities of domination number, locating domination number and locating-total domination number are different.

In this paper, we investigate the expressive power and the algorithmic properties of weighted expressions, which define functions from finite words to integers. First, we consider a slight extension of an expression formalism, introduced by Chatterjee. et. al. in the context of infinite words, by which to combine values given by unambiguous (max,+)-automata, using Presburger arithmetic. We show that important decision problems such as emptiness, universality and comparison are PSpace-c for these expressions. We then investigate the extension of these expressions with Kleene star. This allows to iterate an expression over smaller fragments of the input word, and to combine the results by taking their iterated sum. The decision problems turn out to be undecidable, but we introduce the decidable and still expressive class of synchronised expressions., FCT2017 Acceptance

This paper considers the problem of choice of an optimal decision under unknown state of nature when losses are not known exactly for some or all decisions and some or all states of nature. However, it is possible to determine probabilities for all states of nature on the basis of statistical data. So, there are two kinds of uncertainty, randomness and vagueness. That is why both methods of the probability theory and methods of the theory of fuzzy sets are used. There is no a unified approach to choice of an optimal decision even in the classical statistical decision theory. One of existing approaches is to use minimax decision rules when losses are crisp. In this paper, the approach is generalized for problems with trapezoidal fuzzy losses. A theorem about the existence of a minimax decision rule is proved when the set of all possible states of nature is finite.

Negligence in relation to aging infrastructure systems could have unintended consequences and is therefore associated with a risk. The assessment of the risk of neglecting maintenance provides valuable information for decision making in maintenance management. However, infrastructure systems are interdependent and interconnected systems of systems characterized by hierarchical levels and a multiplicity of failure scenarios. Assessment methodologies are needed that can capture the multidimensional aspect of risk and simplify the risk assessment, while also improving the understanding and interpretation of the results. This paper proposes to integrate the multi-criteria decision analysis with data mining techniques to perform the risk assessment of aging infrastructures. The analysis is characterized by two phases. First, an intra failure scenario risk assessment is performed. Then, the results are aggregated to carry out an inter failure scenario risk assessment. A cluster analysis based on the k-medoids algorithm is applied to reduce the number of alternatives and identify those which dominate the decision problem. The proposed approach is applied to a system of aging culverts of the German waterways network. Results show that the procedure allows to simplify the analysis and improve communication with infrastructure stakeholders.

When statistical decision theory was emerging as a promising new paradigm, Charles Stein was to play a major role in the development of minimax theory for invariant statistical problems. In some of his earliest work with Gil Hunt, he set out to prove that, in problems where invariant procedures have constant risk, any best invariant test would be minimax among all tests. Although finding it not quite true in general, this led to the legendary Hunt–Stein theorem, which established the result under restrictive conditions on the underlying group of transformations. In decision problems invariant under such suitable groups, an overall minimax test was guaranteed to reside within the class of invariant procedures where it would typically be much easier to find. But when it did not seem possible to establish this result for invariance under the full linear group, he instead turned to prove its impossibility with counterexamples such as the nonminimaxity of the usual sample covariance estimator where the full linear group was just too big for the Hunt–Stein theorem to apply. Further explorations of invariance such as the sometimes problematic inference under a fiducial distribution, or the characterization of a best invariant procedure as a formal Bayes procedure under a right Haar prior, are further examples of the far reaching influence of Stein’s contributions to invariance theory.

A graph G for which γR(G)=2γ(G) is the Roman graph, and if γRwc(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002). Moreover, we give a characterization of weakly connected Roman trees.

We investigate the computational complexity of the problem of deciding if an algebra homomorphism can be factored through an intermediate algebra. Specifically, we fix an algebraic language, $$\mathcal L$$ , and take as input an algebra homomorphism $$f:X\rightarrow Z$$ between two finite $$\mathcal L$$ -algebras X and Z, along with an intermediate finite $$\mathcal L$$ -algebra Y. The decision problem asks whether there are homomorphisms $$g:X\rightarrow Y$$ and $$h:Y\rightarrow Z$$ such that $$f=hg$$ . We show that this problem is NP-complete for most languages.

In this paper, we concentrate on study interval-valued fuzzy relations in decision problems based on preference relations, and a preference structure making up of the strict preference relation, indifference relation, and incomparability relation which may be defined with the use of interval-valued aggregation and interval-valued fuzzy negation function. We analyze the influence of some new types of fusion functions on the effectiveness of the decision process. The studies concern different aggregation classes due to the type of monotonicity/order used.

Marketers often use A/B testing as a tool to compare marketing treatments in a test stage and then deploy the better-performing treatment to the remainder of the consumer population. While these tests have traditionally been analyzed using hypothesis testing, we re-frame them as an explicit trade-off between the opportunity cost of the test (where some customers receive a sub-optimal treatment) and the potential losses associated with deploying a sub-optimal treatment to the remainder of the population. We derive a closed-form expression for the profit-maximizing test size and show that it is substantially smaller than typically recommended for a hypothesis test, particularly when the response is noisy or when the total population is small. The common practice of using small holdout groups can be rationalized by asymmetric priors. The proposed test design achieves nearly the same expected regret as the flexible, yet harder-to-implement multi-armed bandit under a wide range of conditions. We demonstrate the benefits of the method in three different marketing contexts -- website design, display advertising and catalog tests -- in which we estimate priors from past data. In all three cases, the optimal sample sizes are substantially smaller than for a traditional hypothesis test, resulting in higher profit.

In this paper the two player zero sum games with diagonal game matrixes TPZSGD are analyzed Many important applications of this particular class of games are found in military decision problems in customs and immigration strategies and police work Explicit functions are derived that give the optimal frequences of different decisions and the expected results of relevance to the different decision makers Arbitrary numbers of decision alternatives are covered It is proved that the derived optimal decision frequency formulas correspond to the unique optimization results of the two players It is proved that the optimal solutions for both players always lead to a unique completely mixed strategy Nash equilibrium For each player the optimal frequency of a particular decision is strictly greater than and strictly less than With comparative statics analyses the directions of the changes of optimal decision frequences and expected game values as functions of changes in different parameter values are determined The signs of the optimal changes of the decision frequences of the different players are also determined as functions of risk in different parameter values Furthermore the directions of changes of the expected optimal value of the game are determined as functions of risk in the different parameter values Finally some of the derived formulas are used to confirm earlier game theory results presented in the literature It is demonstrated that the new functions can be applied to solve common military problems