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)

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)

It has been shown that the Mere Addition Paradox occurs in a choice-functional approach with Path Independence (Stewart R.T., 2021, Path independence and a persistent paradox of population ethics, Journal of Philosophy, forthcoming). The present study is a three-part response to this finding. First, I show that Path Independence is not an essential property leading to this paradox and that logically weaker properties can get the same result. Second, I present a rationalizable choice function that does not yield the paradox. (...) And third, I argue that menu-dependent relations are nicely examined if Path Independence is relaxed to Property $\alpha $ (or equivalently, Contraction Consistency). (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)

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)

We characterize the epimorphisms in homotopy type theory (HoTT) as the fiberwise acyclic maps and develop a type-theoretic treatment of acyclic maps and types in the context of synthetic homotopy theory as developed in univalent foundations. We present examples and applications in group theory, such as the acyclicity of the Higman group, through the identification of groups with 0-connected, pointed 1-types. Many of our results are formalized as part of the agda-unimath library.

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)

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 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)

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 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)

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.

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.

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)

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)

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

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

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.

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)

dialectical frameworks (ADFs) are generalizations of Dung argumentation frameworks where arbitrary relationships among arguments can be formalized. This additional expressibility comes with the price of higher computational complexity, thus an understanding of potentially easier subclasses is essential. Compared to Dung argumentation frameworks, where several subclasses such as acyclic and symmetric frameworks are well understood, there has been no in-depth analysis for ADFs in such direction yet (with the notable exception of bipolar ADFs). In this work, we introduce certain subclasses of (...) ADFs and investigate their properties. In particular, we show that for acyclic ADFs, the different semantics coincide. On the other hand, we show that the concept of symmetry is less powerful for ADFs and further restrictions are required to achieve results that are similar to the known ones for Dung’s frameworks. A particular such subclass (support-free symmetric ADFs) turns out to be closely related to argumentation frameworks with collective attacks (SETAFs); we investigate this relation in detail and obtain as a by-product that even for SETAFs symmetry is less powerful than for AFs. We also discuss the role of odd-length cycles in the subclasses we have introduced. Finally, we analyse the expressiveness of the ADF subclasses we introduce in terms of signatures. (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)

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)

dialectical frameworks (ADFs) are generalizations of Dung argumentation frameworks where arbitrary relationships among arguments can be formalized. This additional expressibility comes with the price of higher computational complexity, thus an understanding of potentially easier subclasses is essential. Compared to Dung argumentation frameworks, where several subclasses such as acyclic and symmetric frameworks are well understood, there has been no in-depth analysis for ADFs in such direction yet (with the notable exception of bipolar ADFs). In this work, we introduce certain subclasses of (...) ADFs and investigate their properties. In particular, we show that for acyclic ADFs, the different semantics coincide. On the other hand, we show that the concept of symmetry is less powerful for ADFs and further restrictions are required to achieve results that are similar to the known ones for Dung’s frameworks. A particular such subclass (support-free symmetric ADFs) turns out to be closely related to argumentation frameworks with collective attacks (SETAFs); we investigate this relation in detail and obtain as a by-product that even for SETAFs symmetry is less powerful than for AFs. We also discuss the role of odd-length cycles in the subclasses we have introduced. Finally, we analyse the expressiveness of the ADF subclasses we introduce in terms of signatures. (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)

We construct bounded degree acyclic Borel graphs with large Borel chromatic number using a graph arising from Ramsey theory and limits of expander sequences.

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)

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)

In order to make scientific results relevant to practical decision making, it is often necessary to transfer a result obtained in one set of circumstances—an animal model, a computer simulation, an economic experiment—to another that may differ in relevant respects—for example, to humans, the global climate, or an auction. Such inferences, which we can call extrapolations, are a type of argument by analogy. This essay sketches a new approach to analogical inference that utilizes chain graphs, which resemble directed acyclic graphs (...) (DAGs) except in allowing that nodes may be connected by lines as well as arrows. This chain graph approach generalizes the account of extrapolation I provided in my (2008) book and leads to new insights that integrate the contributions of the other participants of this symposium. More specifically, this approach explicates the role of “fingerprints,” or distinctive markers, as a strategy for avoiding an underdetermination problem having to do with spurious analogies. Moreover, it shows how the extrapolator’s circle, one of the central challenges for extrapolation highlighted in my book, is closely tied to distinctive markers and the Markov condition as it applies to chain graphs. Finally, the approach suggests additional ways in which investigations of a model can provide information about a target that are illustrated by examples concerning nanomaterials in sunscreens and Wendy Parker’s discussion of fingerprints in climate science. (shrink)

Public-policy choices frequently have to be carried out in the presence of incommensurabilities. These incommensurabilities may manifest themselves in the form of incompleteness—that is, some of the options under consideration are not comparable by a decision maker. As a consequence, it may be impossible to select policies that are at least as good as all competing proposals. When faced with incommensurabilities of this nature, transitivity can be considered too demanding a requirement. An attractive weakening of transitivity consists of a property (...) that Kotaro Suzumura (Economica, 43:381–390, 1976) introduced under the label of consistency. Suzumura consistency postulates that goodness cycles with at least one instance of betterness are to be avoided thus strengthening the well-known acyclicity condition that precludes the existence of betterness cycles. The property is compared to alternative weakenings of transitivity, and it is shown that it has numerous advantages over other contenders. For instance, Suzumura consistency is precisely what is needed to avoid a money pump. The issue of rational choice in the context of public decision-making is discussed in order to provide an illustration of the usefulness of Suzumura consistency. (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.

Mechanisms play an important role in many sciences when it comes to questions concerning explanation, prediction, and control. Answering such questions in a quantitative way requires a formal represention of mechanisms. Gebharter (2014) suggests to represent mechanisms by means of one or more causal arrows of an acyclic causal net. In this paper we show how this approach can be extended in such a way that it can also be fruitfully applied to mechanisms featuring causal feedback.

The causal Markov condition (CMC) plays an important role in much recent work on the problem of causal inference from statistical data. It is commonly thought that the CMC is a more problematic assumption for genuinely indeterministic systems than for deterministic ones. In this essay, I critically examine this proposition. I show how the usual motivation for the CMC—that it is true of any acyclic, deterministic causal system in which the exogenous variables are independent—can be extended to the indeterministic case. (...) In light of this result, I consider several arguments for supposing indeterminism a particularly hostile environment for the CMC, but conclude that none are persuasive. Introduction Functional models and directed graphs The causal Markov theorem The causal Markov theorem and genuine indeterminism Are the exogenous variables independent? EPR Conclusion. (shrink)

The papers focuses on pragmatic arguments for various rationality constraints on a decision maker’s state of mind: on her beliefs or preferences. An argument of this kind typically targets constraint violations. It purports to show that a violator of a given constraint can be confronted with a decision problem in which she will act to her guaranteed disadvantage. Dramatically put, she can be exploited by a clever bookie who doesn’t know more than the agent herself. Examples of pragmatic arguments of (...) this kind are synchronic Dutch Books, for the standard probability axioms, diachronic Dutch Books, for the more controversial principles of reflection and conditionalization, and Money Pumps, for the acyclicity requirement on preferences. The paper suggests that the proposed exploitation set-ups share a common feature. If the violator of a given constraint is logically and mathematically competent, and if she prefers to be better off rather than worse off, she can be exploited only if she is disunified in her decision-making, i.e. only if she makes decisions on various issues she faces separately rather than jointly. Unification in decision making is relatively unproblematic in synchronic contexts, but it may be costly and inconvenient diachronically. On this view, therefore, pragmatic arguments should be seen as delivering conditional recommendations: If you want to afford disunification, then you’d better satisfy these constraints. They identify safeguards of a disunified mind. Isaac Levi’s position on these matters is diametrically different. According to Levi, only synchronic pragmatic arguments are valid. The diachronic ones, he argues, lack any validity at all. This line of reasoning is questioned in the paper. (shrink)