Being building block of data sciences, link prediction plays a vital role in revealing the hidden mechanisms that lead the networking dynamics. Since many techniques depending in vertex similarity and edge features were put forward to rule out many well-known link prediction challenges, many problems are still there just because of unique formulation characteristics of sparse networks. In this study, we applied some graph transformations and several inequalities to determine the greatest value of first and second Zagreb invariant, S K (...) and S K 1 invariants, for acyclic connected structures of given order, diameter, and pendant vertices. Also, we determined the corresponding extremal acyclic connected structures for these topological indices and provide an ordering giving a sequence of acyclic connected structures having these indices from greatest in decreasing order. (shrink)

We analyze the decisiveness structures associated with acyclical collective choice rules. In particular, we examine the consequences of adding anonymity to weak Pareto, thereby complementing earlier results on acyclical social choice. Both finite and countably infinite populations are considered. As established in contributions by Donald Brown and by Jeffrey Banks, acyclical social choice is closely linked to prefilters in the presence of the weak Pareto principle. We introduce the notion of a conditional prefilter and use it to generalize their results. (...) In the finite-population case, adding anonymity implies that the collection of decisive sets is a special case of a conditional prefilter. We then identify the decisiveness structure that results from adding anonymity to the weak Pareto principle. Moving to infinite populations, we obtain the decisive set that consists of the entire population as a possibility, along with a new class of prefilters that we refer to as symmetric free Fréchet prefilters. The choice of the term Fréchet prefilter is motivated by the observation that they share a defining property with the well-known Fréchet filter—namely, that all sets in the requisite collection are such that their complement is finite. (shrink)

In this paper weak utilities are obtained for acyclic binary relations satisfying a condition weaker than semicontinuity on second countable topological spaces. In fact, in any subset of such a space we obtain a weak utility that characterizes the maximal elements as maxima of the function. The addition of separability of the relation yields the existence of semicontinuous representations. This property of the utility provides a result of existence of maximal elements for a class of spaces that include compact spaces. (...) However, we offer a negative result that continuity may not be reached under such hypotheses. (shrink)

Weakly acyclic games form a natural generalization of the class of games that have the finite improvement property. In such games one stipulates that from any initial joint strategy some finite improvement path exists. We classify weakly acyclic games using the concept of a scheduler introduced in Simon and Apt. We also show that finite games that can be solved by the iterated elimination of never best response strategies are weakly acyclic. Finally, we explain how the schedulers allow us to (...) improve the bounds on finding a Nash equilibrium in a weakly acyclic game. (shrink)

The money-pump argument is the standard argument for the acyclicity of rational preferences. The argument purports to show that agents with cyclic preferences are in some possible situations forced to act against their preference. In the usual, diachronic version of the money-pump argument, such agents accept a series of trades that leaves them worse off than before. Two stock objections are (i) that one may get the drift and refuse the trades and (ii) that one may adopt a plan (...) to only accept some of the trades. This article argues that these objections are irrelevant. If the diachronic money-pump argument is cogent, so is a more direct synchronic argument. The upshot is that the standard objections to the diachronic money-pump argument do not affect this simpler synchronic argument. Hence the standard objections to the money-pump argument for acyclicity are irrelevant. (shrink)

Self-reference in semantics, which leads to well-known paradoxes, is a thoroughly researched subject. The phenomenon can appear also in decision theoretic situations. There is a structural analogy between the two and, more interestingly, an analogy between principles concerning truth and those concerning rationality. The former can serve as a guide for clarifying the latter. Both the analogies and the disanalogies are illuminating.

This paper addresses the existence of Hopf bifurcations in a directed acyclic network of neurons, each of them being modeled by a Hindmarsh–Rose neuronal model. The bifurcation parameter is the small parameter corresponding to the ratio of time scales between the fast and the slow dynamics. We first prove that, under certain hypotheses, the single uncoupled neuron can undergo a Hopf bifurcation. Hopf bifurcation occurrences in a directed acyclic network of HR neurons are then discussed. Numerical simulations are carried out (...) to observe these bifurcations and to illustrate the theoretical results. (shrink)

Barry Smith recently discussed the diagraphs of book eight of Jacob Lorhard’s Ogdoas scholastica under the heading “birth of ontology” (Smith, 2022; this issue). Here, I highlight the commonalities between the original usage of diagraphs in the tradition of Ramus for didactic purposes and the the usage of their present-day successors–modern ontologies–for computational purposes. The modern ideas of ontology and of the universal computer were born just two generations apart in the breakthrough century of instrumental reason.

Stuart Rachels and Larry Temkin have offered a purported counter-example to the acyclicity of the relationship 'all things considered better than'. This example invokes our intuitive preferences over pairs of alternatives involving a single person's painful experiences of varying intensity and duration. These preferences, Rachels and Temkin claim, are confidently held, entirely reasonable, and cyclical. They conclude that we should drop acyclicity as a requirement of rationality. I argue that, together with the findings of recent research on the (...) way people evaluate episodes of pain, the use of a heuristic known as similarity-based decision-making explains why our intuitive preferences may violate acyclicity in this example. I argue that this explanation should lead us to regard these preferences with suspicion, because it indicates that they may be the result of one or more biases. I conclude that Rachels' and Temkin's example does not provide sufficient grounds for rejecting acyclicity. (shrink)

Learning equivalence classes of acyclic models with latent and selection variables from multiple datasets with overlapping variables is discussed. The problem of inferring the presence of latent variables, their relation to the observables, and the relation among themselves, is considered. A different approach for identifying causal structures, one that results in much simpler equivalence classes, is provided. It is found that the computational cost is much higher than the procedure implemented, but if datasets are individually of modest dimensionality, it might (...) be doable in practice. From the point of view of search algorithms for optimizing structure, much of the machinery of combinatorial optimization could optimize the penalized composite likelihood score by enforcing constraints such that the independence models over different subsets of variables agree on the overlapping sets. (shrink)

The standard argument for the claim that rational preferences are transitive is the pragmatic money-pump argument. However, a money-pump only exploits agents with cyclic strict preferences. In order to pump agents who violate transitivity but without a cycle of strict preferences, one needs to somehow induce such a cycle. Methods for inducing cycles of strict preferences from non-cyclic violations of transitivity have been proposed in the literature, based either on offering the agent small monetary transaction premiums or on multi-dimensional preferences. (...) This paper argues that previous proposals have been flawed and presents a new approach based on the dominance principle. (shrink)

Let G = V G, E G be a molecular graph, where V G and E G are the sets of vertices and edges. A topological index of a molecular graph is a numerical quantity which helps to predict the chemical/physical properties of the molecules. The Wiener, Wiener polarity, and the terminal Wiener indices are the distance-based topological indices. In this paper, we described a linear time algorithm that computes the Wiener index for acyclic graphs and extended this algorithm for (...) unicyclic graphs. The same algorithms are modified to compute the terminal Wiener index and the Wiener polarity index. All these algorithms compute the indices in time O n. (shrink)

Different directed acyclic graphs may be Markov equivalent in the sense that they entail the same conditional independence relations among the observed variables. Chickering provided a transformational characterization of Markov equivalence for DAGs, which is useful in deriving properties shared by Markov equivalent DAGs, and, with certain generalization, is needed to prove the asymptotic correctness of a search procedure over Markov equivalence classes, known as the GES algorithm. For DAG models with latent variables, maximal ancestral graphs provide a neat representation (...) that facilitates model search. However, no transformational characterization -- analogous to Chickering's -- of Markov equivalent MAGs is yet available. This paper establishes such a characterization for directed MAGs, which we expect will have similar uses as it does for DAGs. (shrink)

Different directed acyclic graphs may be Markov equivalent in the sense that they entail the same conditional indepen- dence relations among the observed variables. Meek characterizes Markov equiva- lence classes for DAGs by presenting a set of orientation rules that can correctly identify all arrow orienta- tions shared by all DAGs in a Markov equiv- alence class, given a member of that class. For DAG models with latent variables, maxi- mal ancestral graphs provide a neat representation that facilitates model search. (...) Earlier work has identified a set of orientation rules sufficient to con- struct all arrowheads common to a Markov equivalence class of MAGs. In this paper, we provide extra rules sufficient to construct all common tails as well. We end up with a set of orientation rules sound and complete for identifying commonalities across a Markov equivalence class of MAGs, which is partic- ularly useful for causal inference. (shrink)

By recent work on some conjectures of Pillay, each definably compact group in a saturated o-minimal structure is an extension of a compact Lie group by a torsion free normal divisible subgroup, called its infinitesimal subgroup. We show that the infinitesimal subgroup is cohomologically acyclic. This implies that the functorial correspondence between definably compact groups and Lie groups preserves the cohomology.

Stuart Rachels and Larry Temkin have offered a purported counterexample to the acyclicity of the relationship “all things considered better than”. This example invokes our intuitive preferences over pairs of alternatives involving a single person’s painful experiences of varying intensity and duration. These preferences, Rachels and Temkin claim, are confidently held, entirely reasonable, and cyclical. They conclude that we should drop acyclicity as a requirement of rationality. I argue that, together with the findings of recent research on the (...) way people evaluate episodes of pain, the use of a heuristic known as similarity-based decision-making explains why our intuitive preferences may violate acyclicity in this example. I argue that this explanation should lead us to regard these preferences with suspicion, because it indicates that they may be the result of one or more biases. I conclude that Rachels’ and Temkin’s example does not provide sufficient grounds for rejecting acyclicity. (shrink)

Christopher Meek. Related Graphical Frameworks: Undircted, Directed Acyclic and Chain Graph Models.

Peter Spirtes. Calculating TETRAD Constraints Implied by Directed Acyclic Graphs.

Peter Spirtes. Discovering Causal Relations Among Latent Variables in Directed Acyclical Graphical Models.

It is well known that there may be many causal explanations that are consistent with a given set of data. Recent work has been done to represent the common aspects of these explanations into one representation. In this paper, we address what is less well known: how do the relationships common to every causal explanation among the observed variables of some DAG process change in the presence of latent variables? Ancestral graphs provide a class of graphs that can encode conditional (...) independence relations that arise in DAG models with latent and selection variables. In this paper we present a set of orientation rules that construct the Markov equivalence class representative for ancestral graphs, given a member of the equivalence class. These rules are sound and complete. We also show that when the equivalence class includes a DAG, the equivalence class representative is the essential graph for the said DAG. (shrink)

This paper will be concerned with hard choices—that is, choice situations where an agent cannot make a rationally justified choice. Specifically, this paper asks: if an agent cannot optimize in a given situation, are they facing a hard choice? A pair of claims are defended in light of this question. First, situations where an agent cannot optimize because of incompleteness of the binary preference or value relation constitute a hard choice. Second, situations where agents cannot optimize because the binary preference (...) or value relation violates acyclicity do not constitute a hard choice. (shrink)

We characterize the existence of semicontinuous weak utilities in a general framework, where the axioms of transitivity and acyclicity are relaxed to that of consistency in the sense of Suzumura (Economica 43:381–390, 1976). This kind of representations allow us to transfer the problem of the existence of the ${{\mathcal{G}}{\mathcal{O}}{\mathcal{C}}{\mathcal{H}}{\mathcal{A}}}$ set of a binary relation to the easier problem of getting maxima of a real function. Finally, we show that the maxima of these representations correspond to the different levels of (...) satiation that each of individual has (an individual reaches his or her level of satiation when an increase of consuming an alternative product/service brings no increase in utility). (shrink)

Directed acyclic graphs (DAGs) constitute a qualitative representation for conditional independence (CI) properties of a probability distribution. It is known that every CI statement implied by the topology of a DAG is witnessed over it under a graph-theoretic criterion of d-separation. Alternatively, all such implied CI statements are derivable from the local independencies encoded by a DAG using the so-called semi-graphoid axioms. We consider Labeled Directed Acyclic Graphs (LDAGs) modeling graphically scenarios exhibiting context-specific independence (CSI). Such CSI statements are modeled (...) by labeled edges, where labels encode contexts in which the edge vanishes. We study the problem of identifying all independence statements implied by the structure and the labels of an LDAG. We show that this problem is coNP-hard for LDAGs and formulate a sound extension of the semi-graphoid axioms for the derivation of such implied independencies. Finally we connect our study to certain qualitative versions of independence ubiquitous in database theory and teams semantics. (shrink)

This is the classic work upon which modern-day game theory is based. What began as a modest proposal that a mathematician and an economist write a short paper together blossomed, when Princeton University Press published Theory of Games and Economic Behavior. In it, John von Neumann and Oskar Morgenstern conceived a groundbreaking mathematical theory of economic and social organization, based on a theory of games of strategy. Not only would this revolutionize economics, but the entirely new field of scientific inquiry (...) it yielded--game theory--has since been widely used to analyze a host of real-world phenomena from arms races to optimal policy choices of presidential candidates, from vaccination policy to major league baseball salary negotiations. And it is today established throughout both the social sciences and a wide range of other sciences. (shrink)

The connected and acyclic components contained in a network are identified by the computation of its complexity, where complexity of a network refers to the total number of spanning trees present within. The article in hand deals with the enumeration of the complexity of various networks’ operations such as sum, product, difference K 2, n ⊖ K 2, and the conjunction of S n with K 2. All our computations have been concluded by implementation of the methods of linear algebra (...) and matrix theory. Our derivations will also be highlighted with the assistance of 3D plots at the end of this article. (shrink)

This paper provides a general introduction to the use of causal models in the metaphysics of causation, specifically structural equation models and directed acyclic graphs. It reviews the formal framework, lays out a method of interpretation capable of representing different underlying metaphysical relations, and describes the use of these models in analyzing causation.

Inheritance diagrams are directed acyclic graphs with two types of connections between nodes: x → y and x ↛ y . Given a diagram D, one can ask the formal question of “is there a valid path between node x and node y?” Depending on the existence of a valid path we can answer the question “x is a y” or “x is not a y”. The answer to the above question is determined through a complex inductive algorithm on paths (...) between arbitrary pairs of points in the graph. This paper aims to simplify and interpret such diagrams and their algorithms. We approach the area on two fronts. Suggest reactive arrows to simplify the algorithms for the winning paths. We give a conceptual analysis of inheritance diagrams, and compare our analysis to the “small” and “big sets” of preferential and related reasoning. In our analysis, we consider nodes as information sources and truth values, direct links as information, and valid paths as information channels and comparisons of truth values. This results in an upward chaining, split validity, off-path preclusion inheritance formalism of a particularly simple type. We show that the small and big sets of preferential reasoning have to be relativized if we want them to conform to inheritance theory, resulting in a more cautious approach, perhaps closer to actual human reasoning. We will also interpret inheritance diagrams as theories of prototypical reasoning, based on two distances: set difference, and information difference. We will see that some of the major distinctions between inheritance formalisms are consequences of deeper and more general problems of treating conflicting information. It is easily seen that inheritance diagrams can also be analysed in terms of reactive diagrams - as can all argumentation systems. AMS Classification: 68T27, 68T30. (shrink)

This paper generalizes rationalizability of a choice function by a single acyclic binary relation to rationalizability by a set of such relations. Rather than selecting those options in a menu that are maximal with respect to a single binary relation, a weakly pseudo-rationalizable choice function selects those options that are maximal with respect to at least one binary relation in a given set. I characterize the class of weakly pseudo-rationalizable choice functions in terms of simple functional properties. This result also (...) generalizes Aizerman and Malishevski's characterization of pseudo-rationalizable choice functions, that is, choice functions rationalizable by a set of total orders. (shrink)

This paper will be concerned with hard choices—that is, choice situations where an agent cannot make a rationally justified choice. Specifically, this paper asks: if an agent cannot optimize in a given situation, are they facing a hard choice? A pair of claims are defended in light of this question. First, situations where an agent cannot optimize because of incompleteness of the binary preference or value relation constitute a hard choice. Second, situations where agents cannot optimize because the binary preference (...) or value relation violates acyclicity do not constitute a hard choice. (shrink)

Should you be willing to forego any sure good for a tiny probability of a vastly greater good? Fanatics say you should, anti-fanatics say you should not. Anti-fanaticism has great intuitive appeal. But, I argue, these intuitions are untenable, because satisfying them in their full generality is incompatible with three very plausible principles: acyclicity, a minimal dominance principle, and the principle that any outcome can be made better or worse. This argument against anti-fanaticism can be turned into a positive (...) argument for a weak version of fanaticism, but only from significantly more contentious premises. In combination, these facts suggest that those who find fanaticism counterintuitive should favor not anti-fanaticism, but an intermediate position that permits agents to have incomplete preferences that are neither fanatical nor anti-fanatical. (shrink)

In solving judgment aggregation problems, groups often face constraints. Many decision problems can be modelled in terms the acceptance or rejection of certain propositions in a language, and constraints as propositions that the decisions should be consistent with. For example, court judgments in breach-of-contract cases should be consistent with the constraint that action and obligation are necessary and sufficient for liability; judgments on how to rank several options in an order of preference with the constraint of transitivity; and judgments on (...) budget items with budgetary constraints. Often more or less demanding constraints on decisions are imaginable. For instance, in preference ranking problems, the transitivity constraint is often contrasted with the weaker acyclicity constraint. In this paper, we make constraints explicit in judgment aggregation by relativizing the rationality conditions of consistency and deductive closure to a constraint set, whose variation yields more or less strong notions of rationality. We review several general results on judgment aggregation in light of such constraints. (shrink)

I provide a characterization of weakly pseudo-rationalizable choice functions---that is, choice functions rationalizable by a set of acyclic relations---in terms of hyper-relations satisfying certain properties. For those hyper-relations Nehring calls extended preference relations, the central characterizing condition is weaker than (hyper-relation) transitivity but stronger than (hyper-relation) acyclicity. Furthermore, the relevant type of hyper-relation can be represented as the intersection of a certain class of its extensions. These results generalize known, analogous results for path independent choice functions.

This paper examines the logic of conditional obligation, which originates from the works of Hansson, Lewis, and others. Some weakened forms of transitivity of the betterness relation are studied. These are quasi-transitivity, Suzumura consistency, acyclicity and the interval order condition. The first three do not change the logic. The axiomatic system is the same whether or not they are introduced. This holds true under a rule of interpretation in terms of maximality and strong maximality. The interval order condition gives (...) rise to a new axiom. Depending on the rule of interpretation, this one changes. With the rule of maximality, one obtains the principle known as disjunctive rationality. With the rule of strong maximality, one obtains the Spohn axiom (also known as the principle of rational monotony, or Lewis’ axiom CV). A completeness theorem further substantiates these observations. For interval order, this yields the finite model property and decidability of the calculus. (shrink)

Mechanistic philosophy of science views a large part of scientific activity as engaged in modelling mechanisms. While science textbooks tend to offer qualitative models of mechanisms, there is increasing demand for models from which one can draw quantitative predictions and explanations. Casini et al. (Theoria 26(1):5–33, 2011) put forward the Recursive Bayesian Networks (RBN) formalism as well suited to this end. The RBN formalism is an extension of the standard Bayesian net formalism, an extension that allows for modelling the hierarchical (...) nature of mechanisms. Like the standard Bayesian net formalism, it models causal relationships using directed acyclic graphs. Given this appeal to acyclicity, causal cycles pose a prima facie problem for the RBN approach. This paper argues that the problem is a significant one given the ubiquity of causal cycles in mechanisms, but that the problem can be solved by combining two sorts of solution strategy in a judicious way. (shrink)

The idea that rational agents should have acyclic preferences and should obey conditionalization has been defended on the grounds that otherwise an agent is threatened with becoming a “money pump.” This essay argues that such arguments fail to prove their claims.