Fundamenta Informaticae - Volume 158, issue 1-3

Authors: Chen, Qingliang | Torroni, Paolo | Villata, Serena

Article Type: Other

DOI: 10.3233/FI-2018-1639

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. v-vii, 2018

Authors: Dunin-Kęplicz, Barbara | Powała, Alina

Article Type: Research Article

Abstract: Some conflicts appearing in multi-agent settings may be resolved via communication. In this paper, besides conflicts of opinions , paradigmatically resolved by a persuasion dialogue, we study semantically deeper conflicts reaching to motivations of opinions. This investigation led us to discerning deep persuasion dialogues aiming at the resolution of conflicting motivations of opinions . In our overall research program we focus on realistic modeling of agency. This includes a proper representation of agents’ ignorance and inconsistencies , appearing in their informational stance. Therefore, our formal framework TalkLOG , designed to provide and embed different forms of …dialogues, employs a 4-valued logic with two additional logical values, unknown and inconsistent . Within TalkLOG soundness and completeness of persuasion was proved by comparing the outcomes of the persuasion dialogues performed by n -agents with the outcomes obtained by merging knowledge of these n agents. In this context the key point was a proper construction of this merge operator. Another critical issue is complexity of agents’ communication, which is typically interleaved with reasoning in the context of multi-agent or autonomous systems. In TalkLOG tractability of both aspects is obtained thanks to the implementation tool: rule-based 4-valued query language 4QL. Show more

Keywords: persuasion, multi-party dialogue, paraconsistent reasoning, nonmonotonic reasoning, conflict resolution

DOI: 10.3233/FI-2018-1640

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 1-39, 2018

Authors: Ihara, Takamasa | Tsuruta, Shunsuke | Todo, Taiki | Sakurai, Yuko | Yokoo, Makoto

Article Type: Research Article

Abstract: The cake cutting problem is concerned with the fair allocation of a divisible good among agents whose preferences vary over it. Recently, designing strategy-proof cake cutting mechanisms has caught considerable attention from AI and MAS researchers. Previous works assumed that an agent’s utility function is additive so that theoretical analysis becomes tractable. However, in practice, agents have non-additive utility over a resource. In this paper, we consider the all-or-nothing utility function as a representative example of non-additive utility because it can widely cover agents’ preferences for such real-world resources as the usage of meeting rooms, time slots for computational resources, …bandwidth usage, and so on. We first show the incompatibility between envy-freeness and Pareto efficiency when each agent has all-or-nothing utility. We next propose two strategy-proof mechanisms that satisfy Pareto efficiency, which are based on the serial dictatorship mechanism, at the sacrifice of envy-freeness. To address computational feasibility, we propose a heuristic-based allocation algorithm to find a near-optimal allocation in time polynomial in the number of agents, since the problem of finding a Pareto efficient allocation is NP-hard. As another approach that abandons Pareto efficiency, we develop an envy-free mechanism and show that one of our serial dictatorship based mechanisms satisfies proportionality in expectation, which is a weaker definition of proportionality. Finally, we evaluate the efficiency obtained by our proposed mechanisms by computational experiments. Show more

Keywords: Mechanism design, Cake cutting, Strategy-proofness, Non-additive preference

DOI: 10.3233/FI-2018-1641

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 41-61, 2018

Authors: Matsui, Toshihiro | Silaghi, Marius | Okimoto, Tenda | Hirayama, Katsutoshi | Yokoo, Makoto | Matsuo, Hiroshi

Article Type: Research Article

Abstract: Distributed Constraint Optimization Problem (DCOP) has been studied as a fundamental component of multiagent systems. With DCOPs, various applications on multiagent systems are formalized as constraint optimization problems where variables and functions are distributed among agents. Leximin AMODCOP has been proposed as a class of Multiple Objective DCOPs, where multiple objectives for individual agents are optimized based on the leximin operator. This problem also relates to Asymmetric DCOPs based on its the criteria of fairness among agents. Previous studies explore only Leximin AMODCOPs on constraint graphs limited to functions with unary or binary scopes. We address the Leximin AMODCOPs on …factor graphs that directly represent n-ary functions. A dynamic programming method on factor graphs is investigated as an exact solution method. In addition, for relatively dense problems, we also investigate several approximate/inexact algorithms. Show more

Keywords: distributed constraint optimization, asymmetric, multiple objectives, leximin, egalitarian

DOI: 10.3233/FI-2018-1642

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 63-91, 2018

Authors: Leask, Sam | Logan, Brian

Article Type: Research Article

Abstract: A key advantage of BDI-based approaches to agent programming, is that agents can deliberate about which course of action to adopt to achieve a goal or respond to an event. However, while state-of-the-art BDI-based agent programming languages allow the programmer to specify the context(s) in which a particular plan is applicable, they are typically limited to a single, hardcoded, deliberation strategy for all task environments. In this paper, we present an alternative approach, in which an agent’s deliberation strategy forms part of the agent program. We show how both conventional agent programs and the agent’s deliberation strategy can be encoded …in the agent programming language meta-APL. Key steps in the deliberation cycle of meta-APL are reflected in the state of the agent and can be queried and updated by meta-APL rules, allowing application-specific BDI deliberation strategies to be programmed in a straightforward way. To illustrate the flexibility of meta-APL, we show how three typical BDI deliberation strategies can be programmed using meta-APL rules. We then show how meta-APL can used to program a simple adaptive deliberation strategy that avoids interference between intentions. Show more

DOI: 10.3233/FI-2018-1643

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 93-120, 2018

Authors: Lorini, Emiliano | Mühlenbernd, Roland

Article Type: Research Article

Abstract: In this study we present a game-theoretic model of guilt in relation to sensitivity to norms of fairness. We focus on a specific kind of fairness norm à la Rawls according to which a fair society should be organized so as to admit economic inequalities to the extent that they are beneficial to the less advantaged agents. In a first step, we analyze the impact of the sensitivity to this fairness norm on the behavior of agents who play a repeated Prisoner’s Dilemma and learn via fictitious play. In a second step we transform the base game into a meta-game …that represents a static description of a repeated game updated via fictitious play. We analyze such a meta-game under population dynamics by means of evolutionary game theory. Our results reveal two things: first of all, a great sensitivity to the fairness norm is beneficial in the long term when agents have the time to converge to mutual cooperation. Secondly, cooperativeness and fairness norm sensitivity can coevolve in a population of initially solely defectors. Show more

Keywords: Fairness norm à la Rawls, Prisoner’s Dilemma, fictitious play, evolutionary game theory

DOI: 10.3233/FI-2018-1644

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 121-148, 2018

Authors: Liu, Chanjuan | Liu, Fenrong | Su, Kaile

Article Type: Research Article

Abstract: An unrealistic assumption in classical extensive game theory is that the complete game tree is fully perceivable by all players. To weaken this assumption, a class of games (called games with short sight ) was proposed in literature, modelling the game scenarios where players have only limited foresight of the game tree due to bounded resources and limited computational ability. As a consequence, the notions of equilibria in classical game theory were refined to fit games with short sight. A crucial issue that thus arises is to determine whether a strategy profile is a solution to a game. To study …this issue and address the underlying idea and theory on players’ decisions in such games, we adopt a logical way. Specifically, we develop a logic called DLS through which features of these games are demonstrated. More importantly, it enables us to characterize the solutions to these games via formulas of this logic. Moreover, we study the algorithm for model checking DLS, which is shown to be PTIME-complete in the size of the model. This work not only provides an insight into a more realistic model in game theory, but also enriches the possible applications of logic. Show more

Keywords: Extensive games, Short sight, Dynamic logic, Solution Concept, Model checking

DOI: 10.3233/FI-2018-1645

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 149-169, 2018

Authors: Le, Tiep | Son, Tran Cao | Pontelli, Enrico

Article Type: Research Article

Abstract: This paper presents an extension of the Multi-Context Systems (MCS) framework to allow the encoding of preferences at the level of the contexts. The work is motivated by the observation that a naive use of preference logics at a context level in an MCS can lead to undesirable outcomes, such as inconsistency of the MCS. To address this issue, the paper introduces the notion of ranked logics , suitable for use with multiple sources of preferences, and employs them in the definition of weakly and strongly-preferred equilibria in a Multi-Context Systems with Preferences (MCSP) framework. …The usefulness of MCSP is demonstrated in two applications: modeling distributed configuration problems and finding explanations for distributed abductive diagnosis problems. Show more

Keywords: Multi-context System, Logic Programming with Preferences, Answer Set Optimization

DOI: 10.3233/FI-2018-1646

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 171-216, 2018

Authors: Calardo, Erica | Governatori, Guido | Rotolo, Antonino

Article Type: Research Article

Abstract: We study how the non-classical n -ary operator ⊗, originally intended to capture the concept of reparative obligation, can be used in the context of social choice theory to model preferences. A novel possible-world model-theoretic semantics, called sequence semantics, was proposed for the operator. In this paper, we propose a sound and complete axiomatisation of a minimal modal logic for the operator, and we extend it with axioms suitable to model social choice consistency principles such as extension consistency and contraction consistency. We provide completeness results for such extensions.

Keywords: Sequence semantics, preferences, modal logic, non normal modal logics, neighbourhood semantics, social choice theory, choice consistency

DOI: 10.3233/FI-2018-1647

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 217-238, 2018

Authors: Porello, Daniele

Article Type: Research Article

Abstract: We introduce a number of logics to reason about collective propositional attitudes that are defined by means of the majority rule. It is well known that majoritarian aggregation is subject to irrationality, as the results in social choice theory and judgment aggregation show. The proposed logics for modelling collective attitudes are based on a substructural propositional logic that allows for circumventing inconsistent outcomes. Individual and collective propositional attitudes, such as beliefs, desires, obligations, are then modelled by means of minimal modalities to ensure a number of basic principles. In this way, a viable consistent modelling of collective attitudes is obtained.

Keywords: Collective Propositional Attitudes, Group Agency, Substructural Logics, Non-Normal Modal Logics, Collective Rationality, Majority rule, Judgment Aggregation, Social Choice Theory

DOI: 10.3233/FI-2018-1648

Citation: Fundamenta Informaticae, vol. 158, no. 1-3, pp. 239-275, 2018