718 research outputs found
Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting
No full textAggregating preferences over combinatorial domains has many applications in artificial intelligence (AI). Given the inherent exponential nature of preferences over combinatorial domains, compact representation languages are needed to represent them, and (m)CP-nets are among the most studied ones. Sequential and global voting are two different ways of aggregating preferences represented via CP-nets. In sequential voting, agents' preferences are aggregated feature-by-feature. For this reason, sequential voting may exhibit voting paradoxes, i.e., the possibility to select sub-optimal outcomes when preferences have specific feature dependencies. To avoid paradoxes in sequential voting, one has often assumed the (quite) restrictive constraint of O-legality, which imposes a shared common topological order among all the agents' CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during the preference aggregation process. For this reason, global voting is immune from the voting paradoxes of sequential voting, and hence there is no need to impose restrictions over the CP-nets' structure when preferences are aggregated via global voting. Sequential voting over O-legal CP-nets received much attention, and O-legality of CP-nets has often been required in other studies. On the other hand, global voting over non-O-legal CP-nets has not carefully been analyzed, despite it was explicitly stated in the literature that a theoretical comparison between global and sequential voting was highly promising and a precise complexity analysis for global voting has been asked for multiple times. In quite a few works, only very partial results on the complexity of global voting over CP-nets have been given. In this paper, we start to fill this gap by carrying out a thorough computational complexity analysis of global voting tasks, for Pareto and majority voting, over not necessarily O-legal acyclic binary polynomially connected (m)CP-nets. We show that all these problems belong to various levels of the polynomial hierarchy, and some of them are even in P or LOGSPACE. Our results are a notable achievement, given that the previously known upper bound for most of these problems was the complexity class EXPTIME. We provide various exact complexity results showing tight lower bounds and matching upper bounds for problems that (up to now) did not have any explicit non-obvious lower bound
A novel characterization of the complexity class Θ^P_k based on counting and comparison
No full textThe complexity class Θ^P_2, which is the class of languages recognizable by deterministic Turing machines in polynomial time with at most logarithmic many calls to an NP oracle, received extensive attention in the literature. Its complete problems can be characterized by different specific tasks, such as deciding whether the optimum solution of an NP problem is unique, or whether it is in some sense “odd” (e.g., whether its size is an odd number). In this paper, we introduce a new characterization of this class and its generalization Θ^P_k to the k-th level of the polynomial hierarchy. We show that problems in Θ^P_k are also those whose solution involves deciding, for two given sets A and B of instances of two Σ^P_{k−1}-complete (or Π^P_{k−1}-complete) problems, whether the number of “yes”-instances in A is greater than those in B. Moreover, based on this new characterization, we provide a novel sufficient condition for Θ^P_k-hardness. We also define the general problem Comp-Valid_k, which is proven here Θ^P_{k+1}-complete. Comp-Valid_k is the problem of deciding, given two sets A and B of quantified Boolean formulas with at most k alternating quantifiers, whether the number of valid formulas in A is greater than those in B. Notably, the problem Comp-Sat of deciding whether a set contains more satisfiable Boolean formulas than another set, which is a particular case of Comp-Valid_1, demonstrates itself as a very intuitive Θ^P_2-complete problem. Nonetheless, to our knowledge, it eluded its formal definition to date. In fact, given its strict adherence to the count-and-compare semantics here introduced, Comp-Valid_k is among the most suitable tools to prove Θ^P_k-hardness of problems involving the counting and comparison of the number of “yes”-instances in two sets. We support this by showing that the Θ^P_2-hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Θ^P_k introduced in this paper
Introducing Ontological CP-Nets
No full textPreference representation and reasoning is a key issue in many real-world
scenarios. Currently, there are many approaches allowing preferences to be assessed in a
qualitative or quantitative way. The most prominent qualitative approach for representing
preferences are CP-nets. Their clear graphical structure unifies an easy representation of
user desires with nice computational properties when computing the best outcome. Here,
we introduce ontological CP-nets, which allow the representation of preferences using a
CP-net over an ontological domain, i.e., variable values are logical formulas constrained
relative to a background domain ontology
Game−Theoretic Agent Programming in Golog
No full textWe present the agent programming language GTGolog, which integrates explicit agent programming in Golog with game-theoretic multi-agent planning in Markov games. It is a generalization of DTGolog to a multi-agent setting, where we have two competing single agents or two competing teams of agents. The language allows for specifying a control program for a single agent or a team of agents in a high-level logical language. The control program is then completed by an interpreter in an optimal way against another single agent or another team of agents, by viewing it as a generalization of a Markov game, and computing a Nash strategy. We illustrate the usefulness of this approach along a robotic soccer example
Tractable reasoning with bayesian description logics
No full textThe DL-Lite family of tractable description logics lies between the semantic web languages RDFS and OWL Lite. In this paper, we present a probabilistic generalization of the DL-Lite description logics, which is based on Bayesian networks. As an important feature, the new probabilistic description logics allow for flexibly combining terminological and assertional pieces of probabilistic knowledge. We show that the new probabilistic description logics are rich enough to properly extend both the DL-Lite description logics as well as Bayesian networks. We also show that satisfiability checking and query processing in the new probabilistic description logics is reducible to satisfiability checking and query processing in the DL-Lite family. Furthermore, we show that satisfiability checking and answering unions of conjunctive queries in the new logics can be done in LogSpace in the data complexity. For this reason, the new probabilistic description logics are very promising formalisms for data-intensive applications in the Semantic Web involving probabilistic uncertainty. © 2008 Springer-Verlag
On the construction of three-valued Lukasiewicz-Moisil algebras
No full textAbstractThe author constructs a three-valued Lukasiewicz-Moisil algebra from a monadic three-valued Lukasiewicz-Moisil algebra, generalizing A. Monteiro's (1974) construction of a three-valued Lukasiewicz-Moisil algebra from a monadic Boolean algebra, and constructs a monadic three-valued Lukasiewicz-Moisil algebra from a monadic n-valued one, generalizing V. Boicescu's (1971) construction of a three-valued Lukasiewicz-Moisil algebra from an n-valued one, n ⩾ 3. Thus one can construct a three-valued Lukasiewicz-Moisil algebra from a monadic n-valued Lukasiewicz-Moisil algebra, n ⩾ 2
Game−Theoretic Reasoning About Actions in Nonmonotonic Causal Theories
No full textWe present the action language GC+ for reasoning about actions in multi-agent systems under probabilistic uncertainty and partial observability, which is an extension of the action language C+ that is inspired by partially observable stochastic games (POSGs). We provide a finite-horizon value iteration for this framework and show that it characterizes finite-horizon Nash equilibria. We also describe how the framework can be implemented on top of nonmonotonic causal theories. We then present acyclic action descriptions in GC+ as a special case where transitions are computable in polynomial time. We also give an example that shows the usefulness of our approach in practice
Structure-Based Causes and Explanations in the Independent Choice Logic
No full textThis paper is directed towards combining Pearl's structural-model approach to causal reasoning with high-level formalisms for reasoning about actions. More precisely, we present a combination of Pearl's structural-model approach with Poole's independent choice logic. We show how probabilistic theories in the independent choice logic can be mapped to probabilistic causal models. This mapping provides the independent choice logic with appealing concepts of causality and explanation from the structural-model approach. We illustrate this along Halpern and Pearl's sophisticated notions of actual cause, explanation, and partial explanation. This mapping also adds first-order modeling capabilities and explicit actions to the structural-model approach
Adaptive Multi−Agent Programming in GTGolog
No full textWe present a novel approach to adaptive multi-agent programming, which is based on an integration of the agent programming language GTGolog with adaptive dynamic programming techniques. GTGolog combines explicit agent programming in Golog with game-theoretic multi-agent planning in stochastic games. In GTGolog, the transition probabilities and reward values of the domain must be provided with the model. The adaptive generalization of GTGolog proposed here is directed towards letting the agents themselves explore and adapt these data. We use high-level programs for the generation of both abstract states and optimal policies
- …
