The descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to (...) be tilted towards favoring the duplicator. These seemingly more favorable rules make it easier to prove separation results, since separation results are proven by showing that the duplicator has a winning strategy. In this paper, the relationship between these games is investigated. It is shown that in one sense, the two games are equivalent. Specifically, each family of graphs used in one game to prove a separation result can in principle be used in the other game to prove the same result. This answers an open question of Ajtai and the author from 1989. It is also shown that in another sense, the games are not equivalent, in that there are situations where the spoiler requires strictly more resources to win one game than the other game. This makes formal the informal statement that one game is easier for the duplicator to win. (shrink)

When seeking to coordinate in a game with imperfect information, it is often relevant for a player to know what other players know. Keeping track of the information acquired in a play of infinite duration may, however, lead to infinite hierarchies of higher-order knowledge. We present a construction that makes explicit which higher-order knowledge is relevant in a game and allows us to describe a class of games that admit coordinated winning strategies with finite memory.

Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees and (...) class='Hi'>graphs are explored. The Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed. (shrink)

We investigate Maker–Breaker games on graphs of size $\aleph _1$ in which Maker’s goal is to build a copy of the host graph. We establish a firm dependence of the outcome of the game on the axiomatic framework. Relating to this, we prove that there is a winning strategy for Maker in the $K_{\omega,\omega _1}$ -game under ZFC+MA+ $\neg $ CH and a winning strategy for Breaker under ZFC+CH. We prove a similar result for the $K_{\omega _1}$ -game. (...) Here, Maker has a winning strategy under ZF+DC+AD, while Breaker has one under ZFC+CH again. (shrink)

What is it that evolves in cultural evolution? This is a question easily posed but not so easily answered. According to common interpretations of cultural evolutionary theory, it is not strictly agents that change over time or proliferate during cultural transmission, but their socially transmitted behavior, what they communicate or acquire via social learning – in short: their interactions. This means that we have to put these cultural interactions into an evolutionary setting and show how they evolve within cultural populations, (...) i.e. within social networks. But the social networks themselves also evolve, which brings us to a multi-level approach of cultural evolution, implementing both, individual and group selection. In this paper I will assume that the microlevel is given by a description of cultural agents, their behavior and decisions, whereas the macrolevel describes the dynamics on population structure and in particular population boundaries in social networks (since we are not really able to identify something analogous to ‘species’ in cultural evolution). In this paper, I am going to offer a specific mathematical model, that makes use of game theory for representing the cultural microlevel and graph theory for the cultural macrolevel. It has to be shown, how both can formally be linked in a synthetic attempt. (shrink)

The concept of an infinite game played on a finite graph is perhaps novel in the context of an rather extensive recent literature in which infinite games are generally played on an infinite game tree. We claim two advantages for our model, which is admittedly more restrictive. First, our games have a more apparent resemblance to ordinary parlor games in spite of their infinite duration. Second, by distinguishing those nodes of the graph that determine the winning and (...) losing of the game , we are able to offer a complexity analysis that is useful in computer science applications. (shrink)

Axelrod (The evolution of cooperation, 1984) and others explain how cooperation can emerge in repeated 2-person prisoner’s dilemmas. But in public good games with anonymous contributions, we expect a breakdown of cooperation because direct reciprocity fails. However, if agents are situated in a social network determining which agents interact, and if they can influence the network, then cooperation can be a viable strategy. Social networks are modelled as graphs. Agents play public good games with their neighbours. After (...) each game, they can terminate connections to others, and new connections are created. Cooperative agents do well because they manage to cluster with cooperators and avoid defectors. Computer simulations demonstrate that group formation and exclusion are powerful mechanisms to promote cooperation in dilemma situations. This explains why social dilemmas can often be solved if agents can choose with whom they interact. (shrink)

The authors consider reflexive games that describe the interaction of subjects making decisions based on an awareness structure, i.e., a hierarchy of beliefs about essential parameters, beliefs about beliefs, and so on. It was shown that the language of graphs of reflexive games represents a convenient uniform description method for reflexion effects in bélles-léttres.

In the 1890s, Peirce reformulated quantification theory by expressing it in a language of diagrams, called existential graphs. Peirce thought that the iconicity of his graphs made them suitable for analyzing logical reasoning. Iconic signs can be said to show their meaning, and this paper studies the ways in which graphs do this. Peirce's pragmatic analysis of propositions resembles game-theoretical semantics, and existential graphs show what they mean by displaying the structure of the semantic game for (...) the proposition represented by a graph. (shrink)

Inexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures.In this article a new method is introduced that allows, under certain conditions, the extension of a winning strategy of Duplicator on some small parts of two finite structures to a global winning strategy.As applications of this technique it is shown that • — Graph Connectivity is not expressible in existential monadic second-order (...) logic , even in the presence of a built-in linear order,• — Graph Connectivity is not expressible in MonNP even in the presence of arbitrary built-in relations of degree n0, and• — the presence of a built-in linear order gives MonNP more expressive power than the presence of a built-in successor relation. (shrink)

Information protocols (IP's) were developed to describe players who learn their social situation by their experiences. Although IP's look similar to colored multi-graphs (MG's), the two objects are constructed in fundamentally different ways. IP's are constructed using the global concept of history, whereas graphs are constructed using the local concept of edges. We give necessary and sufficient conditions for each theory to be captured by the other. We find that the necessary and sufficient condition for IP theory to (...) be captured by MG theory, which we call SE, excludes relevant game situations. Hence, we conclude that IP theory remains a vital tool and cannot be replaced by MG theory. (shrink)

We consider Effort Games, a game-theoretic model of cooperation in open environments, which is a variant of the principal-agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, (...) called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project.We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort.We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P-hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series-Parallel Graphs. (shrink)

In the vertex pursuit game of cops and robbers on finite graphs, the cop has a winning strategy if and only if the graph admits a dominating order. Such graphs are called constructible in the graph theory literature. This equivalence breaks down for infinite graphs, and variants of the game have been proposed to reestablish partial connections between constructibility and being cop-win. We answer an open question of Lehner about one of these variants by giving examples of (...) weak cop-win graphs which are not constructible. We show that the index set of computable constructible graphs is Π11 hard and the index set of computable constructible locally finite graphs is Π40 hard. Finally, we give an example of a computable constructible graph for which every dominating order computes 0″. (shrink)

As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players – they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the informational dependencies between variables in a game. More precisely, dependency graphs play two roles. First, when we say that variable x (...) depends on variable y, then we mean that when a strategy assigns a value to variable x, it can be informed by the value that has been assigned to y. Second, and as a consequence of the first property, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs implicitly define a partial ordering of the run-time events in a game: if x is dependent on y, then the assignment of a value to y must precede the assignment of a value to x; if x and y are independent, however, then we can say nothing about the ordering of assignments to these variables—the assignments may occur concurrently. We refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly logic. (shrink)

We study repeated normal form games where the number of players is large. We argue that it is interesting to look at such games as being divided into subgames, each of which we call a neighbourhood. The structure of such a game is given by a graph G whose nodes are players and edges denote visibility. The neighbourhoods are maximal cliques in G. The game proceeds in rounds where in each round the players of every clique X of (...) G play a strategic form game among each other. A player at a node v strategises based on what she can observe, i.e., the strategies and the outcomes in the previous round of the players at vertices adjacent to v. Based on this, the player may switch strategies in the same neighbourhood, or migrate to another neighbourhood.We are interested in addressing questions regarding the eventual stability of such games. We incrementally impose constraints on the ‘types’ of the players. First, we look at players who are unconstrained in their strategising abilities, in that, players who may use unbounded memory. We then consider the case of memoryless players. We show that in both these cases the eventual stability of the game can be characterised in terms of potentials. We then introduce a simple modal logic in which the types of the players can be specified. We show that when the players play according to these specified types, it can be effectively decided whether the game stabilises. Finally, we look at the important heuristic of imitation. Simple imitative strategies can be specified in the logic introduced by us. We show that in a population of optimisers and imitators, we can decide how ‘worse-off’ the imitators are by playing imitative strategies rather than optimal ones. (shrink)

We give a sufficient condition for the inexpressibility of the k-th extended vectorization of a generalized quantifier $\sf Q$ in ${\rm FO}({\vec Q}_k)$ , the extension of first-order logic by all k-ary quantifiers. The condition is based on a model construction which, given two ${\rm FO}({\vec Q}_1)$ -equivalent models with certain additional structure, yields a pair of ${\rm FO}({\vec Q}_k)$ -equivalent models. We also consider some applications of this condition to quantifiers that correspond to graph properties, such as connectivity and (...) planarity. (shrink)

The article studies properties of functional dependencies between strategies of players in Nash equilibria of multiplayer strategic games. The main focus is on the properties of functional dependencies in the context of a fixed dependency graph for payoff functions. A logical system describing properties of functional dependence for any given graph is proposed and is proven to be complete.

There have been two main lines in the literature on restricted games: the first line was started by Myerson (1977) that studied graph-restricted games an the second one was initiated by Faigle (1989). The present paper provides a unified way to look on the literature and establishes connections between the two different lines on restricted games. The strength and advantages of this unified approach becomes clear in the study of the inheritance of the convexity from the game (...) to the restricted game where an interesting result by Nouweland and Borm (1991) on the convexity of graph-restricted games is turned into a direct consequence of the corresponding result by Faigle (1989), by means of this relation. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:Signs of Logic: Peircean Themes on the Philosophy of Language, Games, and CommunicationRobert W. BurchAhti-Veikko Pietarinen Signs of Logic: Peircean Themes on the Philosophy of Language, Games, and Communication Dordrecht, The Netherlands: Springer, 2006. xiv + 496 pp.This compendious volume of fourteen of Pietarinen's essays on Peirce, plus a three-page set of "Final Words" relating to the work of Robert Aumann, is a "must-have" for both (...) the Peirce scholar and any other philosopher who wishes to relate Peirce's thinking on language and logic to other major thinkers and logical themes of the twentieth century (and beyond). The essays extend or complement discussions of Peirce's logic and philosophy of language that have come to be expected from the "Finnish school" of philosophers, which includes Hintikka and Hilpinen, as well as Pietarinen.Nine of the essays (Chapters 3, 4, 5, 7, 8, 10, 12, 13, and 14), comprising about two-thirds of the entire book, are revised and expanded versions of essays that Pietarinen has previously published. The remaining one-third (approximately) of the book is brand new. Chapters 1 and 2 serve as general introductions to the book's major interests. Chapter 6 is on evidence for constructivism in Peirce, as well as several other topics. Chapter 9 compares Peirce's ideas with Wilfred Hodges's "dialogue foundations" and contains a small philosophical dialogue, which has Peirce, Wittgenstein, and Hodges as its characters. Chapter 11 concerns evolutionary semantics and language [End Page 577] games. And the cursory Chapter 15 of "Final Words" predicts that the game-theoretical approach to semantics and Peirce scholarship has an exploding future, like an erupting volcano.From the foregoing one can gather, correctly, that each essay in the book is separately conceived and that the book is not a single continuous line of argumentative development of one or even of a few themes. Still, the essays are similar to one another in two ways, which ways are closely related to each other. First, they all concern the Peircean doctrine that semeiotic and semeiosis constitute the heartland of logic, and that this heartland is vastly richer than the sort of pure mathematical calculi that might mistakenly be taken for logic itself (and were in fact so taken for much of the twentieth century). Second, they all deal with the Peircean insistence that semeiosis is inherently a form of Praxis in which interchanges occur between or among various "agents" or "actors," one of which might be nature itself; so that at the very least logic is dialogic, and so that more generally one may justifiably speak of semeiosis as involving something like a "game." These lines of exploration will surprise no seasoned Peirce scholar, but the special genius of the Finnish "school" of Peirce interpretation from Hintikka forward is to have spotlighted in dramatic fashion the game-theoretical nature of many elements in Peirce's semeiotic.In these essays Pietarinen amply exhibits two attainments of mind that are indispensable for the serious Peirce scholar. One is the object of what we might call "The Eisele Imperative" after the vehement urgings of Carolyn Eisele: this is the possession of some significant degree of sophistication in mathematics. Pietarinen's mathematical skills are plainly sufficient for his discussions of logic and game theory. For example, his Chapter 5 is an excellent technical discussion of Peirce's existential graphs, and his Chapter 7 is an admirable technical discussion of certain aspects of game theory and generalized quantifiers. Another crucial skill needed by the serious Peirce scholar is the object of what we might call "The Pietarinen Corrective" after the practices exemplified in these essays: this is the possession of extremely broad knowledge of recent and contemporary philosophy, especially philosophy of language, logic, metaphysics, epistemology, and philosophy of science.Indeed, the breadth of Pietarinen's acquaintance with twentieth century logic and philosophy of language, both "analytic" and "continental," is breathtaking. This allows him scope for comparisons of Peirce's views with an extraordinarily wide, and not always easily anticipated, range of philosophers and philosophic traditions. Pietarinen's range of reference is so extensive that it would be pointless to attempt to discuss in... (shrink)

In this paper, a two-level green supply chain composed of a manufacturer and a retailer is taken as the background. Considering the consumer’s double consumption preference and the manufacturer’s green product R&D investment, a differential game model of the green supply chain under the government cost subsidy strategy is constructed. Firstly, the equilibrium points of the system are solved and their stability is discussed and analyzed. Secondly, the dynamic evolution process of Nash equilibrium under the parameters of green degree, green (...) preference coefficient, retail channel preference coefficient, coefficient of the sensitivity of price, and adjustment speed are described by numerical simulation. The results show that the two ways of a system entering chaos are Flip bifurcation and N-S bifurcation, respectively, by 2D bifurcation graph, and it is also verified in 1D bifurcation diagram. When the bifurcation parameters are small, the system maintains Nash equilibrium stability. If the green degree of products is increased, the green preference coefficient will also increase; on the contrary, the retail preference coefficient will decrease. Research and development cost subsidy policy can effectively improve the green degree of products and increase the sales volume of products, so as to improve the profit of supply chain members. (shrink)

User modeling is a key topic in many applications, mainly social networks and information retrieval systems. To assess the effectiveness of a user modeling approach, its capability to classify personal characteristics (e.g., the gender, age, or consumption grade of the users) is evaluated. Due to the fact that some of the attributes to predict are multiclass (e.g., age usually encompasses multiple ranges), assessing fairness in user modeling becomes a challenge since most of the related metrics work with binary attributes. As (...) a workaround, the original multiclass attributes are usually binarized to meet standard fairness metrics definitions where both the target class and sensitive attribute (such as gender or age) are binary. However, this alters the original conditions, and fairness is evaluated on classes that differ from those used in the classification. In this article, we extend the definitions of four existing fairness metrics (related to disparate impact and disparate mistreatment) from binary to multiclass scenarios, considering different settings where either the target class or the sensitive attribute includes more than two groups. Our work endeavors to bridge the gap between formal definitions and real use cases in bias detection. The results of the experiments, conducted on four real-world datasets by leveraging two state-of-the-art graph neural network-based models for user modeling, show that the proposed generalization of fairness metrics can lead to a more effective and fine-grained comprehension of disadvantaged sensitive groups and, in some cases, to a better analysis of machine learning models originally deemed to be fair. The source code and the preprocessed datasets are available at the following link: https://github.com/erasmopurif/toward-responsible-fairness-analysis. (shrink)

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...) \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $x$\end{document} can be derived in a grammar \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $G$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps, or whether a permutation has a factorization of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} over a given set of generators. We show hardness and completeness for these problems for various levels of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W$\end{document} hierarchy. In particular, we show that Short TM Computation is complete for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W[1]$\end{document}. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. (shrink)

This volume contains selected essays in moral and political philosophy by Thomas Hurka. The essays address a wide variety of topics, from the well-rounded life and the value of playing games to proportionality in war and the ethics of nationalism. They also share a common aim: to illuminate the surprising richness and subtlety of our everyday moral thought by revealing its underlying structure, which they often do by representing that structure on graphs. More specifically, the essays all give (...) what the first in the volume calls "structural" as against "foundational" analyses of moral views. Eschewing the grander ambition of grounding our ideas about, say, virtue or desert in claims that use different concepts and concern some other, allegedly more fundamental topic, they examine these ideas in their own right and with close attention to their details. As well as illuminating their individual topics, the essays illustrate the insights this structural method can yield. (shrink)

Threshold models and their dynamics may be used to model the spread of ‘behaviors’ in social networks. Regarding such from a modal logical perspective, it is shown how standard update mechanisms may be emulated using action models – graphs encoding agents’ decision rules. A small class of action models capturing the possible sets of decision rules suitable for threshold models is identified, and shown to include models characterizing best-response dynamics of both coordination and anti-coordination games played on (...) class='Hi'>graphs. We conclude with further aspects of the action model approach to threshold dynamics, including broader applicability and logical aspects. Hereby, new links between social network theory, game theory and dynamic ‘epistemic’ logic are drawn. (shrink)

Differential leadership as a localized leadership style gradually developed on the basis of the Pattern of Differential Sequence. It plays a dual role in stimulating “insider subordinates” and “outsider subordinates” through the dynamic transformation of the roles. Using the process of game reasoning, the study identifies the differing principles used by insider subordinates and outsider subordinates in implementing deviant innovative behaviors. The simulation graph presents the perceived benefits of employees performing or not performing deviant innovative behaviors as clues during the (...) reasoning process, and implements deviant innovative behaviors for the high risk-taking trait of insider subordinates and the high internal control personality of outsider subordinates who implement deviant innovation. The theoretical derivation of behavior provides relevant references, and provides counter measures for effectively promoting employees’ deviant innovative behavior in the context of differential leadership. (shrink)

This thirteenth volume of Collected Papers is an eclectic tome of 88 papers in various fields of sciences, such as astronomy, biology, calculus, economics, education and administration, game theory, geometry, graph theory, information fusion, decision making, instantaneous physics, quantum physics, neutrosophic logic and set, non-Euclidean geometry, number theory, paradoxes, philosophy of science, scientific research methods, statistics, and others, structured in 17 chapters (Neutrosophic Theory and Applications; Neutrosophic Algebra; Fuzzy Soft Sets; Neutrosophic Sets; Hypersoft Sets; Neutrosophic Semigroups; Neutrosophic Graphs; Superhypergraphs; (...) Plithogeny; Information Fusion; Statistics; Decision Making; Extenics; Instantaneous Physics; Paradoxism; Mathematica; Miscellanea), comprising 965 pages, published between 2005-2022 in different scientific journals, by the author alone or in collaboration with the following 110 co-authors (alphabetically ordered) from 26 countries: Abduallah Gamal, Sania Afzal, Firoz Ahmad, Muhammad Akram, Sheriful Alam, Ali Hamza, Ali H. M. Al-Obaidi, Madeleine Al-Tahan, Assia Bakali, Atiqe Ur Rahman, Sukanto Bhattacharya, Bilal Hadjadji, Robert N. Boyd, Willem K.M. Brauers, Umit Cali, Youcef Chibani, Victor Christianto, Chunxin Bo, Shyamal Dalapati, Mario Dalcín, Arup Kumar Das, Elham Davneshvar, Bijan Davvaz, Irfan Deli, Muhammet Deveci, Mamouni Dhar, R. Dhavaseelan, Balasubramanian Elavarasan, Sara Farooq, Haipeng Wang, Ugur Halden, Le Hoang Son, Hongnian Yu, Qays Hatem Imran, Mayas Ismail, Saeid Jafari, Jun Ye, Ilanthenral Kandasamy, W.B. Vasantha Kandasamy, Darjan Karabašević, Abdullah Kargın, Vasilios N. Katsikis, Nour Eldeen M. Khalifa, Madad Khan, M. Khoshnevisan, Tapan Kumar Roy, Pinaki Majumdar, Sreepurna Malakar, Masoud Ghods, Minghao Hu, Mingming Chen, Mohamed Abdel-Basset, Mohamed Talea, Mohammad Hamidi, Mohamed Loey, Mihnea Alexandru Moisescu, Muhammad Ihsan, Muhammad Saeed, Muhammad Shabir, Mumtaz Ali, Muzzamal Sitara, Nassim Abbas, Munazza Naz, Giorgio Nordo, Mani Parimala, Ion Pătrașcu, Gabrijela Popović, K. Porselvi, Surapati Pramanik, D. Preethi, Qiang Guo, Riad K. Al-Hamido, Zahra Rostami, Said Broumi, Saima Anis, Muzafer Saračević, Ganeshsree Selvachandran, Selvaraj Ganesan, Shammya Shananda Saha, Marayanagaraj Shanmugapriya, Songtao Shao, Sori Tjandrah Simbolon, Florentin Smarandache, Predrag S. Stanimirović, Dragiša Stanujkić, Raman Sundareswaran, Mehmet Șahin, Ovidiu-Ilie Șandru, Abdulkadir Șengür, Mohamed Talea, Ferhat Taș, Selçuk Topal, Alptekin Ulutaș, Ramalingam Udhayakumar, Yunita Umniyati, J. Vimala, Luige Vlădăreanu, Ştefan Vlăduţescu, Yaman Akbulut, Yanhui Guo, Yong Deng, You He, Young Bae Jun, Wangtao Yuan, Rong Xia, Xiaohong Zhang, Edmundas Kazimieras Zavadskas, Zayen Azzouz Omar, Xiaohong Zhang, Zhirou Ma.‬‬‬‬‬‬‬‬. (shrink)

Philosophers and social scientists have recently turned to Lewis sender–receiver games to provide an account of how lexical terms can acquire meaning through an evolutionary process. However, the evolution of meaning is contingent on both the particular sender–receiver game played and the choice of evolutionary dynamic. In this paper I explore some differences between models that presume an infinitely large and randomly mixed population and models in which a finite number of agents communicate with their neighbors in a social (...) network. My results show that communication with neighbors is more conducive to the evolution of meaning than communication with strangers. Additionally, I show that the behavior of the system is highly dependent on the topological structure of the social network. I argue that a specific class of networks—small world graphs—is especially conducive to the evolution of meaning. This is because small world graphs have a short characteristic path length while still maintaining a high degree of correlation between neighbors. Since many actual social networks, such as friendship networks and nervous systems, are conjectured to be small world structures, these results indicate that these networks are quite hospitable to the efficient evolution of meaning. (shrink)

Let Mn♯ denote the minimal active iterable extender model which has n Woodin cardinals and contains all reals, if it exists, in which case we denote by Mn the class-sized model obtained by iterating the topmost measure of Mn class-many times. We characterize the sets of reals which are Σ1-definable from R over Mn, under the assumption that projective games on reals are determined:1. for even n, Σ1Mn=⅁RΠn+11;2. for odd n, Σ1Mn=⅁RΣn+11.This generalizes a theorem of Martin and Steel for (...) L, that is, the case n=0. As consequences of the proof, we see that determinacy of all projective games with moves in R is equivalent to the statement that Mn♯ exists for all n∈N, and that determinacy of all projective games of length ω2 with moves in N is equivalent to the statement that Mn♯ exists and satisfies AD for all n∈N. (shrink)

Any set x is uniquely specified by the graph of the membership relation on the set obtained by adjoining x to the transitive closure of x. Thus any operation on sets can be looked at as an operation on these graphs. We look at the operations of ordinal arithmetic of sets in this light. This turns out to be simplest for a modified ordinal arithmetic based on the Zermelo ordinals, instead of the usual von Neumann ordinals. In this arithmetic, (...) addition of sets corresponds to concatenating graphs, and multiplication corresponds to replacing each edge of a graph by a copy of another graph. Characterizations for the von Neumann case are also given. (shrink)

A graph-theoretic account of fibring of logics is developed, capitalizing on the interleaving characteristics of fibring at the linguistic, semantic and proof levels. Fibring of two signatures is seen as a multi-graph (m-graph) where the nodes and the m-edges include the sorts and the constructors of the signatures at hand. Fibring of two models is a multi-graph (m-graph) where the nodes and the m-edges are the values and the operations in the models, respectively. Fibring of two deductive systems is an (...) m-graph whose nodes are language expressions and the m-edges represent the inference rules of the two original systems. The sobriety of the approach is confirmed by proving that all the fibring notions are universal constructions. This graph-theoretic view is general enough to accommodate very different fibrings of propositional based logics encompassing logics with non-deterministic semantics, logics with an algebraic semantics, logics with partial semantics and substructural logics, among others. Soundness and weak completeness are proved to be preserved under very general conditions. Strong completeness is also shown to be preserved under tighter conditions. In this setting, the collapsing problem appearing in several combinations of logic systems can be avoided. (shrink)

​This volume brings together a group of philosophically oriented logicians and logic-minded philosophers, mainly from Asia, to address a variety of logical and philosophical topics, such as modal logic and related directions (e.g. temporal logic, epistemic logic, deontic logic, logic of conditionals, and modal proof theory), theory of truth, paradoxes, intentionality, and social networks. New approaches are also proposed, such as extended modal logic with planarity of graphs, extended branching time temporal logic with conditional operators, and a relational treatment (...) of language and logical systems, to name but a few.Given the variety of topics and issues discussed here, the book will appeal to readers from a broad range of disciplines, from mathematical/philosophical logic, computing science, cognitive science and artificial intelligence, to linguistics, game theory and beyond. (shrink)

We argue that pedagogic authority relies on love, which is misunderstood if seen as a matter of actions and subjects. Love is based not on finite subjects and objects existing in Euclidean space and linear time, but, rather, on the non-finite ontology, space and time of relations. Loving authority is a matter of calling and vocation, arising from the spontaneous and simultaneous call-and-response of a lively relation. We make this argument through a reading of Buber’s I–You relation and Murdoch’ s (...) account of the responsiveness of ascetic discipline. In presenting this analysis, we draw upon a case study from a research project on Australian teachers and students. (shrink)

We show that base matrices for P(ω)∕fin of regular height larger than h necessarily have maximal branches that are not cofinal. The same holds for base matrices of height h if tSpoilergames” by Brendle, Hrušák, and Torres-Pérez.

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

A cardinal characteristic can often be described as the smallest size of a family of sequences which has a given property. Instead of this traditional concern for a smallest realization of the given property, a basically new approach, taken in [4] and [5], asks for a realization whose members are sequences of labels that correspond to 1-way infinite paths in a labelled graph. We study this approach as such, establishing tools that are applicable to all these cardinal characteristics. As an (...) application, we demonstrate the power of the tools developed by presenting a short proof of the bounded graph conjecture [4]. (shrink)

The game is played on a complete Boolean algebra in ω-many moves. At the beginning White chooses a non-zero element p of and, in the nth move, White chooses a positive pn

(...) positive Maharam submeasure or contains a countable dense subset, then Black has a winning strategy in the game played on . A Suslin algebra on which the game is undetermined is constructed and the game is compared with the well-known cut-and-choose games , and introduced by Jech. (shrink)

The well-known game of chess has traditionally been modeled in artificial intelligence studies by search engines with advanced pruning techniques. The models were thus centered on an inference engine manipulating passive symbols in the form of tokens. It is beyond doubt, however, that human players do not carry out such processes. Instead, chess masters instead carry out perceptual processes, carefully categorizing the chunks perceived in a position and gradually building complex dynamic structures to represent the subtle pressures embedded in the (...) positions. In this paper we will consider two hypotheses concerning the underlying subcognitive processes and architecture. In the first hypothesis, a multiple-leveled chess representational structure is presented, which includes distance graphs (with varying levels of quality) between pieces, piece mobilities, and abstract roles. These representational schemes seem to account for numerous characteristics of human player’s psychology. The second hypothesis concerns the extension of the architecture proposed in the Copycat project as central for modeling the emergent intuitive perception of a chess position. We provide a synthesis on how the postulated architecture models chess intuition as an emergent mixture of simultaneous distance estimations, chunk perceptions, abstract role awareness, and intention activations. This is an alternative model to the traditional AI approaches, focusing on the philosophy of active symbols. (shrink)

The aim of this present study is to investigate the influence of three learning contexts on the development of motor creativity of young footballers. In team sport, creativity is a fundamental issue because it allows players to adapt in an environment of high social uncertainty. To carry out this work, we suggest a method for assessing motor creativity into ecological situations based on the analysis of praxical communications. Creativity originates from an interaction between divergence and convergence. In our case, the (...) number of communications and the diversity of updated communications are our divergence indicators. Convergence, understood as the ability to make good decisions, is assessed by two expert judges. Sixty boys’ football players coming from three football clubs participated in this research. The study lasted 2 years. Each year, a team of 10 players from each club participated in the research twice a week for 32 weeks, these groups attended different training sessions: the control group followed a classical learning; the decoding group attended training focused on learning the praxemes of football; the traditional sporting games group followed a training session that was jointly focused on praxemes and the practice of traditional sporting games. The motor creativity of players and groups was assessed both at the beginning and at the end of the year during football matches. Compared to the control group, in the post-test, the group with the highest fluidity is the decoding group and the one with the highest fluidity is the traditional sporting games group. The latter group is also the one with the best convergence. The results showed that traditional games can help develop players’ creative abilities. This research invites us to investigate the complementarity between the different offered training. (shrink)

We present preliminary results on modelling structure of solutions to a task involving abductive reasoning. Research data were gathered using our new tool—Find Out, which has been designed in order to account empirically for abduction relatively close to everyday reasoning processes, with the necessary level of procedure standardization. The tool enables to capture abduction as a compound form of reasoning, from both product and process perspective. Find Out is set up as a game that requires playing the role of an (...) investigator seeking an explanation of what has happened in the presented enigmatic situation. The task consists of three time-limited stages that require different reasoning activities. In the paper, we present quantitative models of structures of solutions to the task proposed by the subjects in the form of situational graphs. We present also some ideas concerning qualitative characteristics of these solutions. (shrink)

This paper brings two major research lines in current sociology together. Research on social networks has long focused primarily on network effects but meanwhile also addresses the emergence and dynamics of networks. Research on trust in social and economic relations shows that networks have effects on trust. Using game theory, we provide a simple model that allows for an integrated and simultaneous analysis of network effects on trust and for the endogenous emergence of the network. The model also allows for (...) characterizing the value of the network. We use standard assumptions on full strategic rationality. Testable implications of the model as well as model extensions are sketched. (shrink)

We discuss the relationships between the notions of $\kappa $ -cub game on $\lambda $ , $\kappa $ -cub subset of $\lambda $ , the ideal of good subsets of $\lambda $ and the problem of adding a $\kappa $ -cub into a given $\kappa $ -stationary subset of $\lambda $ . We also give a short introduction to the ideal of good subsets of $\lambda $.

Two structures A and B are n-equivalent if Player II has a winning strategy in the n-move Ehrenfeucht-Fraïssé game on A and B. In earlier articles we studied n-equivalence classes of ordinals and coloured ordinals. In this article we similarly treat a class of scattered order-types, focussing on monomials and sums of monomials in ω and its reverse ω*.