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.

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)

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)

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.

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)

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

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 discuss a simple logic to describe one of our favourite games from childhood, hide and seek, and show how a simple addition of an equality constant to describe the winning condition of the seeker makes our logic undecidable. There are certain decidable fragments of first-order logic which behave in a similar fashion and we add a new modal variant to that class of logics. We also discuss the relative expressive power of the proposed logic in comparison to the (...) standard modal counterparts. (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)

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)

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.

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)

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)

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)

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)

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)

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)

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)

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)

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)

Prior research suggests brokers do not always act in the best interests of clients, although morally obligated to do so. We empirically investigated this issue focusing on trades executed at best execution price, before and after the introduction of electronic limit-order trading, on the London Stock Exchange. As a result of limit-order trading, the proportion of trades executed at the best execution price for the customer significantly increased. We attribute this to a sustained increase in the liquidity of stocks as (...) a result of limit-order trading, regardless of market capitalisation. We discuss the ethical implications of our findings and conclude that market structures that enhance market competitiveness may help reconcile broker and client interests. (shrink)

Graph games are interactive scenarios with a wide range of applications. This position paper discusses old and new graph games in tandem with matching logics and identifies general questions behind this match. Throughout, we pursue two strands: logic as a way of analyzing existing graph games, and logic as an inspiration for designing new graph games. Our aim is modest: we propose a perspective that complements existing game-theoretic and computational ones, we raise questions, make observations, and (...) suggest research directions—technical results are left to future work. But frankly, our main aim with this survey paper is to show that graph games are concrete, fun, easy to grasp, and yet challenging to study. (shrink)

In this paper, a game-theoretical semantics is developed for the so-called alpha part of Charles S. Peirce's System of Existential Graphs of 1896. This alpha part is that portion of Peirce's graphs that corresponds to propositional logic. The paper both expounds a game-theoretical semantics for the graphs that seems close to Peirce's own intentions and proves for the alpha part of the graphs that this semantics is adequate.

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)

PREFACEProf. Göran Sundholm of Leiden University inspired the group of Logic at Lille and Valparaíso to start a fundamental review of the dialogical conception of logic by linking it to constructive type logic. One of Sundholm's insights was that inference can be seen as involving an implicit interlocutor. This led to several investigations aimed at exploring the consequences of joining winning strategies to the proof-theoretical conception of meaning. The leading idea is, roughly, that while introduction rules lay down the conditions (...) under which a winning strategy for the Proponent may be built, the elimination rules lay down those elements of the Opponent's assertions that the Proponent has the right to use for building winning strategy. It is the pragmatic and ethical features of obligations and rights that naturally lead to the dialogical interpretation of natural deduction.During the Visiting Professorship of Prof. Sundholm at Lille in (2012) the group of Lille started delving into the ways of implementing Per Martin-Löf's Constructive Type Theory with the dialogical perspective. In particular, Aarne Ranta's (1988) paper, the first publication on the subject, was read and discussed during Sundholm’s seminar. The discussions strongly suggested that the game-theoretical conception of quantifiers as deploying interdependent moves provide a natural link between CTT and dialogical logic. This idea triggered several publications by the group of Lille in collaboration with Nicolas Clerbout and Juan Redmond at the University of Valparaíso, including the publication of the book (2015) by Clerbout / Rahman that provides a systematic development of this way of linking CTT and the dialogical conception of logic. However the Clerbout / Rahman book was written from the CTT perspective on dialogical logic, rather than the other way round. The present book should provide the perspective from the other side of the dialogue between the Dialogical Framework and Constructive Type Theory. The main idea of our present study is that Sundholm's (1997) notion of epistemic assumption is closely linked to the Copy-Cat Rule or Socratic Rule that distinguishes the dialogical framework from other game-theoretical approaches. One way to read the present book is as a further development of Sundholm’s extension of Austin's (1946, p. 171) remark on acts of assertion to inference. Indeed, Sundholm (2013, p. 17) gave the following forceful formulation: When I say therefore, I give others my authority for asserting the conclusion, given theirs for asserting the premisses.Per Martin-Löf, in recent lectures, have utilized the dialogical perspective on epistemic assumptions to get out of a certain circle that threatens the explanation of the notions of inference and demonstration. A demonstration may be explained as a chain of (immediate) inferences starting from no premisses. That an inference J1... Jn—————Jis valid means that the conclusion J can be made evident on the assumption that J1, …, Jn are known. The notion of epistemic assumption thus enters in the explanation of valid inference. We cannot, however, in this explanation understand 'known' in the sense of demonstrated, for then we are explaining the notion of inference in terms of demonstration, whereas demonstration has been explained in terms of inference. Martin-Löf suggests that we here understand 'known' in the sense of asserted, so that epistemic assumptions are judgements others have made, judgements for which others have taken the responsibility; that the inference is valid then means that, given that others have taken responsbility for the premisses, I can take responsibility for the conclusion:The circularity problem is this: if you define a demonstration to be a chain of immediate inferences, then you are defining demonstration in terms of inference. Now we are considering an immediate inference and we are trying to give a proper explanation of that; but, if that begins by saying: Assume that J1, …, Jn have been demonstrated – then you are clearly in trouble, because you are about to explain demonstration in terms of the notion of immediate inference, hence when you are giving an account of the notion of immediate inference, the notion of demonstration is not yet at your disposal. So, to say: Assume that J1, …, Jn have already been demonstrated, makes you accusable of trying to explain things in a circle. The solution to this circularity problem, it seems to me now, comes naturally out of this dialogical analysis. […]The solution is that the premisses here should not be assumed to be known in the qualified sense, that is, to be demonstrated, but we should simply assume that they have been asserted, which is to say that others have taken responsibility for them, and then the question for me is whether I can take responsibility for the conclusion. So, the assumption is merely that they have been asserted, not that they have been demonstrated. That seems to me to be the appropriate definition of epistemic assumption in Sundholm's sense. One of the main tenets of the present study is that the further move of relating the Socratic Rule rule with judgemental equality provides both a simpler and more direct way to implement the constructive type theoretical approach within the dialogical framework. Such a reconsideration of the Socratic Rule, roughly speaking, amounts to the following. 1.A move from P that brings-forward a play-object in order to defend an elementary proposition A can be challenged by O. 2.The answer to such a challenge, involves P bringing forward a definitional equality that expresses the fact that the play-object chosen by P copies the one O has chosen while positing A. For short, the equality expresses at the object-languaje level that the defence of P relies on the authority given to O to be able to produce the play-objects she brings forward. More generally, according to this view, a definitional equality established by P and brought forward while defending the proposition A, expresses the equality between a play-object (introduced by O) and the instruction for building a play-object deployed by O while affirming A. So it can be read as a computation rule that indicates how to compute O's instructions. Let us recall that from the strategic point of view, O's moves correspond to elimination rules of demonstrations. Thus, the dialogical rules that prescribe how to introduce a definitional equality – correspond – at the strategic level – to the definitional equality rules for CTT as applied to the selector-functions involved in the elimination rules. So, what we are doing here is extending the dialogical interpretation of Sundholm's epistemic assumption to the rules that set up the definitional equality of a type.The present work is structured in the following way:•In the Introduction we state the main tenets that guide our book•Chapter II contains a brief overview of Constructive Type Theory penned by Ansten Klev with exercises and their solutions. •Chapter III offers a novel presentation of the dialogical conception of logic. In fact, the first two sections of the chapter provide an overview of standard dialogical logic – including solved exercises, slightly adapted to the content of the present volume. The rest of the sections develop a new dialogical approach to Constructive Type Theory. •Chapters IV and V contain the main body of our study, namely the relation between the Socratic Rule, epistemic assumptions, and equality. The chapter provides the reader with thoroughly worked out examples with comments. •After the Final Remarks the book containsa.An appendix containing a an overview of all the rules for the new formulation of dialogical approach to constructive type theory developed in the book; b.a brief outline of Per Martin-Löf's informal presentation of the demonstration of the axiom of choice.c.two examples of a tree-shaped graph of an extensive strategy. Acknowledgments: Many thanks to Mark van Atten (Paris1), Giuliano Bacigalupo (Zürich), Charles Zacharie Bowao (Univ. Ma Ngouabi de Brazzaville, Congo), Christian Berner (Lille3), Michel Crubellier (Lille3), Pierre Cardascia (Lille3), Oumar Dia (Dakar), Marcel Nguimbi ((Univ. Marien Ngouabi de Brazzaville, Congo), Adjoua Bernadette Dango (Lille3 / Alassane Ouattara de Bouaké, Côte d'Ivoire), Steephen Rossy Eckoubili (Lille3), Johan Georg Granström (Zürich), Gerhard Heinzmann (Nancy2), Muhammad Iqbal (Lille3), Matthieu Fontaine (Lille3), Radmila Jovanovic (Belgrad), Hanna Karpenko (Lille3), Laurent Keiff (Lille3), Sébastien Magnier (Saint Dennis, Réunion), Clément Lion (Lille3), Gildas Nzokou (Libreville), Fachrur Rozie (Lille3), Helge Rückert (Mannheim), Mohammad Shafiei (Paris1), and Hassan Tahiri (Lisbon), for rich interchanges, suggestions on the main claims of the present study and proof-reading of specific sections of the text. Special thanks to Gildas Nzokou (Libreville), Steephen Rossy Eckoubili (Lille3) and Clément Lion (Lille3), with whom a Pre-Graduate Textbook in French on dialogical logic and CTT is in the process of being worked out – during the visiting-professorship in 2016 of the former. Eckoubili is the author of the sections on exercises for dialogical logic, Nzokou cared of those involving the development of CTT-demonstrations out of winning-strategies. Special thanks also to Ansten Klev (Prague) for helping with technical details and conceptual issues on CTT, particularly so as author of the chapter introducing CTT. (shrink)

We study a multilateral bargaining problem, where the buyer intends to purchase a subset of available items, each owned by a seller. The subset purchased must satisfy a notion of contiguity, which is modeled using graphs. The graph theoretic approach allows us to study different degrees of complementarity and substitutability between items. It also allows us to examine how degrees of complementarity and substitutability affect the share of surplus obtained by the buyer in the equilibrium of the bargaining game. (...) We characterize necessary and sufficient conditions on the graphs for the buyer to extract full surplus in subgame perfect equilibrium. When the conditions are not met, we provide upper bounds on the equilibrium surplus share of the buyer. (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)

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)

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)

In his pioneering work on Abstract Argumentation, P.M. Dung set a wide scenario by connecting stable models in Logic and Game Theory to simple Abstract Argumentation Frameworks ( AAF), which are essentially directed graphs in which arguments are represented as nodes, and the attack relation is represented by arrows. From such abstraction and simplicity, it is possible to capture important properties in many different fields. The Stable Marriage ( SM) problem is exactly one of such representable problems. Given two (...) sets of individuals partitioned into men and women, a matching is stable when there does not exist any man-woman match by which both man and woman would be individually better off than they are with the person to which they are currently matched. Stable matchings correspond to stable extensions if an AAF is correctly generated from the given SM problem. In this paper we elaborate on the original formulation by Dung, by also encoding SM problems with ties and incomplete preference lists into AAFs. Moreover, we use Weighted Abstract Argumentation to represent optimality criteria in the optimal extension of SM problems, where some matchings are better than others: criteria may consider only the preference of either men, or women, or a more global view obtained by combining the preferences of both. (shrink)

In his pioneering work on Abstract Argumentation, P.M. Dung set a wide scenario by connecting stable models in Logic and Game Theory to simple Abstract Argumentation Frameworks ( AAF), which are essentially directed graphs in which arguments are represented as nodes, and the attack relation is represented by arrows. From such abstraction and simplicity, it is possible to capture important properties in many different fields. The Stable Marriage ( SM) problem is exactly one of such representable problems. Given two (...) sets of individuals partitioned into men and women, a matching is stable when there does not exist any man-woman match by which both man and woman would be individually better off than they are with the person to which they are currently matched. Stable matchings correspond to stable extensions if an AAF is correctly generated from the given SM problem. In this paper we elaborate on the original formulation by Dung, by also encoding SM problems with ties and incomplete preference lists into AAFs. Moreover, we use Weighted Abstract Argumentation to represent optimality criteria in the optimal extension of SM problems, where some matchings are better than others: criteria may consider only the preference of either men, or women, or a more global view obtained by combining the preferences of both. (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)

In this article, we reflect on the use of formal methods in the philosophy of science. These are taken to comprise not just methods from logic broadly conceived, but also from other formal disciplines such as probability theory, game theory, and graph theory. We explain how formal modelling in the philosophy of science can shed light on difficult problems in this domain.

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery is NP-hard. Computationally hard problems that can be employed in these realizations include the Graph Colorability problem, the Diophantine problem, and many others.

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)

Peirce believed that his pragmaticism can be conclusively proven. Beginning in 1903, he drafted several attempts, ending by 1908 with a semeiotic proof. Around 1905, he exposes the proof using the theory of Existential Graphs . This paper modernizes the semantics Peirce proposed for EGs in terms of game-theoretic semantics . Peirce's 1905 proof is then reconstructed in three parts, by relating pragmaticism to the GTS conception of meaning, showing that Peirce's proof is an argument for a relational structure (...) of the meaning of intellectual signs that our interpretative and strategic practices give rise to, and bringing out the key links between EGs and pragmaticism. (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.