In this work, we introduce the notion of targeting for multi-criteria decision making. The problem involves selecting the best alternatives related to one particular alternative, called the target. We use an axiomatic approach to this problem by establishing properties that any targeting method should satisfy. We present a representation theorem and show that satisfying the main properties of targeting requires aggregating the evaluations of the alternatives related to the target. We propose various candidate targeting methods and examine the properties satisfied by each method.

We investigate the truth-tracking performance of iterated belief change operators. In particular, we show that a class of improvement operators is guaranteed to converge to the truth when the input sequence contains sufficiently many correct pieces of information, and we establish a corresponding convergence theorem. We also report experimental results indicating that this convergence typically occurs with relatively short input sequences.

Recently epistemic spaces have been introduced to formalize instantiations of iterated belief change operators and their translations from one concrete representation (epistemic space) to another. In this work, we build on these notions to deepen the understanding of iterated belief change and propose a general method for comparing the expressiveness of existing epistemic spaces. We introduce the notion of canonicity for epistemic spaces as a tool for identifying those that are sufficient, or necessary, to realize certain classes of iterated belief change operators. In particular, we give the canonical epistemic space (up to equivalence) that allows one to instantiate any iterated belief change operator.

In this work, we show how the class of improvement operators --- a general class of iterated belief change operators --- can be used to define a learning model. Focusing on binary classification, we present learning and inference algorithms suited to this learning model and we evaluate them empirically. Our findings highlight two key insights: first, that iterated belief change can be viewed as an effective form of online learning, and second, that the well-established axiomatic foundations of belief change operators offer a promising avenue for the axiomatic study of classification tasks.

In credibility-limited (CL) belief revision, an agent may reject new information if it is considered not credible relative to its current beliefs. A core principle of CL revision requires that all consequences of a credible formula must themselves be credible. We propose a new framework, context-based (CB) belief revision, which generalizes CL revision by relaxing this requirement. In CB revision, a formula may be deemed credible because it strengthens one of its non-credible consequences by providing sufficient supporting context, a situation that CL revision does not allow. We introduce an axiomatic framework for CB revision operators, identify specific subclasses, provide representation theorems, and examine the relationships between CB revision operators, their subclasses, and CL revision operators.

This paper presents BeliefFlow, a novel framework for representing how logical beliefs spread among interacting agents within a network. In a Belief Flow Network (BFN), agents communicate asynchronously. The agents' beliefs are represented using epistemic states, which encompass their current beliefs and conditional beliefs guiding future changes. When communication occurs between two connected agents, the receiving agent changes its epistemic state using an improvement operator, a well-known type of rational iterated belief change operator that generalizes belief revision operators. We show that BFNs satisfy appealing properties, leading to two significant outcomes. First, in any BFN with strong network connectivity, the beliefs of all agents converge towards a global consensus. Second, within any BFN, we show that it is possible to compute an optimal strategy for influencing the global beliefs. This strategy, which involves controlling the beliefs of a least number of agents through bribery, can be identified from the topology of the network and can be computed in polynomial time.

We introduce a new epistemic space: the space of rational rankings. This space is very useful for understanding some aspects of belief dynamics. In particular, the issues which concern improving the new information. Thus, we define in a very clear and succinct way a class of operators capturing the fact that the new information is improved. An interesting feature of this space is that the behavior of these operators can be characterized through a few equations and inequalities which are very simple and whose meaning is transparent. We prove that these operators are indeed improvement operators. Moreover, we show that these operators have good behavior when they undergo a sufficient number of iterations. In such a case, they become Darwiche and Pearl revision operators.

This paper is about editing Boolean classifiers, i.e., determining how a Boolean classifier should be modified when new pieces of evidence must be incorporated. Our main goal is to delineate what are the rational ways of making such edits. This goes through a number of rationality postulates inspired from those considered so far for belief revision. We give a representation theorem and present some families of edit operators satisfying the postulates.

In this work, we address one important problem of Katsuno and Mendelzon update operators, that is to require that any updated belief base must entail any new input in a consistent way. This assumes that any situation can be updated into one satisfying that input, which is unrealistic. To solve this problem, we must relax either the success or the consistency principle. Each case leads to a distinct family of update operators, that we semantically characterize by plausibility relations over possible worlds, considering a credibility limit that aims to forbid unrealistic changes. We discuss in which cases one family is more adequate than the other one.

The behavior of Iterated Belief Revision operators with respect to iteration has been characterized by a set of four postulates proposed by Darwiche and Pearl. These postulates give constraints on a single iteration step, and this is not enough to forbid some pathological operators. In this paper, we propose a generalization of these postulates to solve this issue and we study its implications. One surprising consequence is that, for TPO-representable operators (i.e., for operators defined as transitions on total pre-orders on interpretations), there are very few operators that satisfy this generalization.

Belief revision aims at incorporating, in a rational way, a new piece of information into the beliefs of an agent. Most works in belief revision suppose a classical logic setting, where the beliefs of the agent are consistent. Moreover, the consistency postulate states that the result of the revision should be consistent if the new piece of information is consistent. But in real applications it may easily happen that (some parts of) the beliefs of the agent are not consistent. In this case then it seems reasonable to use paraconsistent logics to derive sensible conclusions from these inconsistent beliefs. However, in this context, the standard belief revision postulates trivialize the revision process. In this work we discuss how to adapt these postulates when the underlying logic is Priest's LP logic, in order to model a rational change, while being a conservative extension of AGM/KM belief revision. This implies, in particular, to adequately adapt the notion of expansion. We provide a representation theorem and some examples of belief revision operators in this setting.

Bi-objective optimisation aims to optimise two generally competing objective functions. Typically, it consists in computing the set of nondominated solutions, called the Pareto front. This raises two issues: 1) time complexity, as the Pareto front in general can be infinite for continuous problems and exponentially large for discrete problems, and 2) lack of decisiveness. This paper focusses on the computation of a small, “relevant” subset of the Pareto front called the representative set, which provides meaningful trade-offs between the two objectives. We introduce a procedure which, given a pre-computed Pareto front, computes a representative set in polynomial time, and then we show how to adapt it to the case where the Pareto front is not provided. This has three important consequences for computing the representative set: 1) does not require the whole Pareto front to be provided explicitly, 2) can be done in polynomial time for bi-objective mixed-integer linear programs, and 3) only requires a polynomial number of solver calls for bi-objective problems, as opposed to the case where a higher number of objectives is involved. We implement our algorithm and empirically illustrate the efficiency on two families of benchmarks.

Iterated belief change aims to determine how the belief state of a rational agent evolves given a sequence of change formulae. Several families of iterated belief change operators (revision operators, improvement operators) have been pointed out so far, and characterized from an axiomatic point of view. This paper focuses on the inference problem for iterated belief change, when belief states are represented as a special kind of stratified belief bases. The computational complexity of the inference problem is identified and shown to be identical for all revision operators satisfying Darwiche and Pearl's (R*1-R*6) postulates. In addition, some complexity bounds for the inference problem are provided for the family of soft improvement operators. We also show that a revised belief state can be computed in a reasonable time for large-sized instances using SAT-based algorithms, and we report empirical results showing the feasibility of iterated belief change for bases of significant sizes.

In this work we define iterated change operators that do not obey the primacy of update principle. This kind of change is required in applications when the recency of the input formulae is not linked with their reliability/priority/weight. This can be translated by a commutativity postulate that asks the result of a sequence of changes to be the same whatever the order of the formulae of this sequence. Technically then we end up with a sequence of formulae that we have to combine in order to obtain a meaningful belief base. Belief merging operators are then natural candidates for this task. We show that we can define improvement operators using an incremental belief merging approach. We also show that these operators can not be encoded as simple preorders transformations, contrary to most iterated revision and improvement operators.

We consider the problem of identifying the change formula in a belief revision scenario: given that an unknown announcement (a formula mu) led a set of agents to revise their beliefs and given the prior beliefs and the revised beliefs of the agents, what can be said about mu? We show that under weak conditions about the rationality of the revision operators used by the agents, the set of candidate formulae has the form of a logical interval. We explain how the bounds of this interval can be tightened when the revision operators used by the agents are known and/or when mu is known to be independent from a given set of variables. We also investigate the completeness issue, i.e., whether mu can be exactly identified. We present some sufficient conditions for it, identify its computational complexity, and report the results of some experiments about it.

We define a consensus postulate in the propositional belief merging setting. In a nutshell, this postulate imposes the merged base to be consistent with the pieces of information provided by each agent involved in the merging process. The interplay of this new postulate with the IC postulates for belief merging is studied, and an incompatibility result is proved. The maximal sets of IC postulates which are consistent with the consensus postulate are exhibited. When satisfying some of the remaining IC postulates, consensus operators are shown to suffer from a weak inferential power. We then introduce two families of consensus operators having a better inferential power by setting aside some of these postulates.

Existing belief merging operators take advantage of all the models from the bases, including those contradicting the integrity constraint. In this paper, we argue that this is not suited to every merging scenario, especially when the integrity constraint encodes physical laws. In that case the bases have to be ‘rationalized’ with respect to the integrity constraint during the merging process. We define several conditions characterizing the operators that are independent to such a rationalization process, and we show how these conditions interact with the standard IC postulates for belief merging. Especially, we give an independence-based axiomatic characterization of a distance-based operator.

Abstract We address the problem of belief revision of logic programs (LPs), i.e., how to incorporate to a LP P a new LP Q. Based on the structure of SE interpretations, Delgrande et al. (2008. Proc. of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR'08), 411–421; 2013b. Proc. of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13), 264–276) adapted the well-known AGM framework (Alchourrón et al. 1985. Journal of Symbolic Logic 50, 2, 510–530) to LP revision. They identified the rational behavior of LP revision and introduced some specific operators. In this paper, a constructive characterization of all rational LP revision operators is given in terms of orderings over propositional interpretations with some further conditions specific to SE interpretations. It provides an intuitive, complete procedure for the construction of all rational LP revision operators and makes easier the comprehension of their semantic and computational properties. We give a particular consideration to LPs of very general form, i.e., the generalized logic programs (GLPs). We show that every rational GLP revision operator is derived from a propositional revision operator satisfying the original AGM postulates. Interestingly, the further conditions specific to GLP revision are independent from the propositional revision operator on which a GLP revision operator is based. Taking advantage of our characterization result, we embed the GLP revision operators into structures of Boolean lattices, that allow us to bring to light some potential weaknesses in the adapted AGM postulates. To illustrate our claim, we introduce and characterize axiomatically two specific classes of (rational) GLP revision operators which arguably have a drastic behavior. We additionally consider two more restricted forms of LPs, i.e., the disjunctive logic programs (DLPs) and the normal logic programs (NLPs) and adapt our characterization result to disjunctive logic program and normal logic program revision operators.

Belief revision games (BRGs) are concerned with the dynamics of the beliefs of a group of communicating agents. BRGs are "zero-player" games where at each step every agent revises her own beliefs by taking account for the beliefs of her acquaintances. Each agent is associated with a belief state defined on some finite propositional language. We provide a general definition for such games where each agent has her own revision policy, and show that the belief sequences of agents can always be finitely characterized. We then define a set of revision policies based on belief merging operators. We point out a set of appealing properties for BRGs and investigate the extent to which these properties are satisfied by the merging-based policies under consideration.

We address the problem of multi-objective constraint optimization problems (MO-COPs). Solving a MO-COP traditionally consists in computing the set of all Pareto optimal solutions, which is an exponentially large set in the general case. So this causes two main problems: first is the time complexity concern, second is a lack of decisiveness. In this paper, we formalize the notion of a MO-COP operator which associates every MO-COP with a subset of Pareto optimal solutions satisfying some desirable additional properties. Then, we present two specific classes of MO-COP operators that give preference to some subsets of Pareto optimal solutions. These operators correspond to two classical doctrines in Decision Theory: utilitarianism and egalitarianism. They compute solutions much more efficiently than standard operators computing all Pareto optimal solutions. In practice, they return a very few number of solutions even for problems involving a high number of objectives.

This paper is centered on the problem of merging (possibly conflicting) information coming from different sources. Though this problem has attracted much attention in propositional settings, propositional languages remain typically not expressive enough for a number of applications, especially when spatial information must be dealt with. In order to fill the gap, we consider a (limited) first-order logical setting, expressive enough for representing and reasoning about information modeled as half-spaces from metric affine spaces. In this setting, we define a family of distance-based majority merging operators which includes the propositional majority operator ΔdH,Σ. We identify a subclass of interpretations of our representation language for which the result of the merging process can be computed and expressed as a formula.

We address the problem of merging qualitative constraints networks (QCNs). We point out a merging algorithm which computes a consistent QCN representing a global view of the input set of (possibly conflicting) QCNs. This algorithm is generic in the sense that it does not depend on a specific qualitative formalism. The efficiency of our method comes from the fact that it merges locally the constraints of the input QCNs bearing on the same pairs of variables. We define several constraint merging operators in a way to ensure that the induced QCNs merging operator satisfies some expected properties from a logical standpoint.