Author name cluster

Nicolas Schwind

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Characterizing Consensuses in Belief Flow Networks

Nicolas Schwind
Gauvain Bourgne
Katsumi Inoue

The BeliefFlow framework models how logical beliefs spread in networks of interacting agents. In a Belief Flow Network (BFN), agents hold epistemic states capturing current and conditional beliefs and revisethemasynchronously, takingintoaccountthebeliefsofthose that influence them as specified by an acquaintance graph, using an improvement operator, a rational form of iterated belief change. Earlier work showed that in strongly connected BFNs, all agents always converge to a global consensus, regardless of initial beliefs, revision policies, or the stochastic order of communications. This paper examines the nature of such consensuses. While past results proved that consensus is reached, we characterize which formulas mayemerge. GivenaBFNschemedefinedbyitsacquaintancegraph and the agents’ initial beliefs, we provide necessary and sufficient conditions for a formula to be realizable as a consensus outcome. A key outcome of our study is that deciding whether a formula is a possible consensus for a given scheme can be done in polynomial time with polynomially many calls to an NP oracle. This matches the complexity of inference for single iterated belief change operators, showing that consensus characterization in BFNs is no harder than reasoning about belief change itself.

PDF

AAAI Conference 2026 Conference Paper

Targeting in Multi-Criteria Decision Making

Nicolas Schwind
Patricia Everaere
Sébastien Konieczny
Emmanuel Lonca

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.

PDF Details DOI

KR Conference 2025 Conference Paper

Context-Based Belief Revision

Nicolas Schwind

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.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Iterated Belief Change as Learning

Nicolas Schwind
Katsumi Inoue
Sébastien Konieczny
Pierre Marquis

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.

PDF Details DOI

KR Conference 2024 Conference Paper

Belief Change on Rational Rankings

Nerio Borges
Sébastien Konieczny
Ramón Pino Pérez
Nicolas Schwind

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.

PDF Details DOI

AAAI Conference 2024 Conference Paper

BeliefFlow: A Framework for Logic-Based Belief Diffusion via Iterated Belief Change

Nicolas Schwind
Katsumi Inoue
Sébastien Konieczny
Pierre Marquis

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.

PDF Details DOI

JAAMAS Journal 2023 Journal Article

Algorithms for partially robust team formation

Nicolas Schwind
Emir Demirović
Jean-Marie Lagniez

Abstract In one of its simplest forms, Team Formation involves deploying the least expensive team of agents while covering a set of skills. While current algorithms are reasonably successful in computing the best teams, the resilience to change of such solutions remains an important concern: Once a team has been formed, some of the agents considered at start may be finally defective and some skills may become uncovered. Two recently introduced solution concepts deal with this issue proactively: 1) form a team which is robust to changes so that after some agent losses, all skills remain covered, and 2) opt for a recoverable team, i. e. , it can be "repaired" in the worst case by hiring new agents while keeping the overall deployment cost minimal. In this paper, we introduce the problem of partially robust team formation (PR–TF). Partial robustness is a weaker form of robustness which guarantees a certain degree of skill coverage after some agents are lost. We analyze the computational complexity of PR-TF and provide two complete algorithms for it. We compare the performance of our algorithms with the existing methods for robust and recoverable team formation on several existing and newly introduced benchmarks. Our empirical study demonstrates that partial robustness offers an interesting trade-off between (full) robustness and recoverability in terms of computational efficiency, skill coverage guaranteed after agent losses and repairability. This paper is an extended and revised version of as reported by (Schwind et al. , Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’21), pp. 1154–1162, 2021).

Details DOI

KR Conference 2023 Conference Paper

Credible Models of Belief Update

Eduardo Fermé
Sébastien Konieczny
Ramón Pino Pérez
Nicolas Schwind

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.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Editing Boolean Classifiers: A Belief Change Perspective

Nicolas Schwind
Katsumi Inoue
Pierre Marquis

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.

PDF Details DOI

KR Conference 2023 Conference Paper

Iteration of Iterated Belief Revision

Nicolas Schwind
Sébastien Konieczny
Ramón Pino Pérez

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.

PDF Details DOI

AAAI Conference 2022 Conference Paper

On Paraconsistent Belief Revision in LP

Nicolas Schwind
Sébastien Konieczny
Ramón Pino Pérez

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.

PDF Details

KR Conference 2022 Conference Paper

On the Representation of Darwiche and Pearl’s Epistemic States for Iterated Belief Revision

Nicolas Schwind
Sébastien Konieczny
Ramón Pino Pérez

The seminal characterization of iterated belief revision was proposed by Darwiche and Pearl, which uses an abstract notion of epistemic states. In this work we look for a canonical representation of these epistemic states. Total preorders are not expressive enough to be used as such a canonical representation. Actually, we show that some operators can even not be represented on a countable epistemic space. Nonetheless, under a very reasonable assumption on the epistemic space, we show that OCFs (Ordinal Conditional Functions) can be considered as a canonical representation.

PDF Details DOI

KR Conference 2022 Conference Paper

Region-Based Merging of Open-Domain Terminological Knowledge

Zied Bouraoui
Sébastien Konieczny
Thanh Ma
Nicolas Schwind
Ivan Varzinczak

This paper introduces a novel method for merging open-domain terminological knowledge. It takes advantage of the Region Connection Calculus (RCC5), a formalism used to represent regions in a topological space and to reason about their set-theoretic relationships. To this end, we first propose a faithful translation of terminological knowledge provided by several and potentially conflicting sources into region spaces. The merging is then performed on these spaces, and the result is translated back into the underlying language of the input sources. Our approach allows us to benefit from the expressivity and the flexibility of RCC5 while dealing with conflicting knowledge in a principled way.

PDF Details DOI

JAAMAS Journal 2021 Journal Article

On the computation of probabilistic coalition structures

Nicolas Schwind
Tenda Okimoto
Pierre Marquis

Abstract In Coalition Structure Generation (CSG), one seeks to form a partition of a given set of agents into coalitions such that the sum of the values of each coalition is maximized. This paper introduces a model for Probabilistic CSG (PCSG), which extends the standard CSG model to account for the stochastic nature of the environment, i. e. , when some of the agents considered at start may be finally defective. In PCSG, the goal is to maximize the expected utility of a coalition structure. We show that the problem is \({\mathsf{NP}}^{\mathsf {PP}}\) -hard in the general case, but remains in \({\mathsf{NP}}\) for two natural subclasses of PCSG instances, when the characteristic function that gives the utility of every coalition is represented using a marginal contribution network (MC-net). Two encoding schemes are presented for these subclasses and empirical results are reported, showing that computing a coalition structure with maximal expected utility can be done efficiently for PCSG instances of reasonable size. This is an extended and revised version of the paper entitled “Probabilistic Coalition Structure Generation” published in the proceedings of KR’18, pages 663–664 [ 33 ].

Details DOI

AAMAS Conference 2021 Conference Paper

Partial Robustness in Team Formation: Bridging the Gap between Robustness and Resilience

Nicolas Schwind
Emir Demirović
Katsumi Inoue
Jean-Marie Lagniez

Team formation is the problem of deploying the least expensive team of agents while covering a set of skills. Once a team has been formed, some of the agents considered at start may be finally defective and some skills may become uncovered. Two solution concepts have been recently introduced to deal with this issue in a proactive manner: one may form a team which is robust to changes so that after some agent losses, all skills remain covered; or one may opt for a recoverable team, i. e. , it can be “repaired” in the worst case by hiring new agents while keeping the overall deployment cost minimal. In this paper, we introduce the problem of partially robust team formation (PR-TF). Partial robustness is a weaker form of robustness which guarantees a certain degree of skill coverage after some agents are lost. We analyze the computational complexity of PR-TF, and provide a complete algorithm for it. The performance of our algorithm is empirically compared with the existing methods for robust and recoverable team formation, on a number of existing benchmarks and some newly introduced ones. Partial robustness is shown to be an interesting trade-off notion between (full) robustness and recoverability in terms of computational efficiency, skill coverage guarantees after agent losses, and repairability.

PDF

KR Conference 2020 Conference Paper

Non-Prioritized Iterated Revision: Improvement via Incremental Belief Merging

Nicolas Schwind
Sébastien Konieczny

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.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

On Computational Aspects of Iterated Belief Change

Nicolas Schwind
Sebastien Konieczny
Jean-Marie Lagniez
Pierre Marquis

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.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Representative Solutions for Bi-Objective Optimisation

Emir Demirovi?
Nicolas Schwind

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 inﬁnite 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 precomputed 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 efﬁciency on two families of benchmarks.

PDF Details

IJCAI Conference 2019 Conference Paper

What Has Been Said? Identifying the Change Formula in a Belief Revision Scenario

Nicolas Schwind
Katsumi Inoue
Sébastien Konieczny
Jean-Marie Lagniez
Pierre Marquis

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.

PDF Details

KR Conference 2018 Conference Paper

On Belief Promotion

Nicolas Schwind
Sébastien Konieczny
Pierre Marquis

We introduce a new class of belief change operators, named promotion operators. The aim of these operators is to enhance the acceptation of a formula representing a new piece of information. We give postulates for these operators and provide a representation theorem in terms of minimal change. We also show that this class of operators is a very general one, since it captures as particular cases belief revision, commutative revision, and (essentially) belief contraction.

AAAI Conference 2018 Conference Paper

On Consensus in Belief Merging

Nicolas Schwind
Pierre Marquis

We deﬁne 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.

PDF Details

KR Conference 2018 Short Paper

Probabilistic Coalition Structure Generation

Nicolas Schwind
Tenda Okimoto
Katsumi Inoue
Katsutoshi Hirayama
Jean-Marie Lagniez
Pierre Marquis

F (CS) = Ci ∈CS f (Ci). A coalition structure CS ∈ ΠA We introduce a model for probabilistic coalition structure generation (PCSG). This model generalizes the standard CSG model to the case when some of the agents considered at start may be finally defective but a new coalition structure based on the remaining agents cannot be formed. In a PCSG, one seeks to maximize the expected utility of a coalition structure. Two policies making precise how the value of a coalition structure evolves when some agents are missing are also introduced.

AAMAS Conference 2018 Conference Paper

Recoverable Team Formation: Building Teams Resilient to Change

Emir Demirovic
Nicolas Schwind
Tenda Okimoto
Katsumi Inoue

Team formation consists in finding the least expensive team of agents such that a certain set of skills is covered. In this paper, we formally introduce recoverable team formation (RTF), a generalization of the above problem, by taking into account the dynamic nature of the environment, e. g. after a team has been formed, agents may unexpectedly become unavailable due to failure or illness. We analyze the computational complexity of RTF, provide both complete and heuristic algorithms, and empirically evaluate their performance. Furthermore, we demonstrate that RTF generalizes robust team formation, where the task is to build a team capable of covering all required skills even after anyk agents are removed. Despite the high complexity of forming a recoverable team, we argue that recoverability is a crucial feature, and experimentally show that it is more appropriate for some applications than robustness.

PDF

IJCAI Conference 2016 Conference Paper

Is Promoting Beliefs Useful to Make Them Accepted in Networks of Agents?

Nicolas Schwind
Katsumi Inoue
Gauvain Bourgne
S
eacute; bastien Konieczny
Pierre Marquis

We consider the problem of belief propagation in a network of communicating agents, modeled in the recently introduced Belief Revision Game (BRG) framework. In this setting, each agent expresses her belief through a propositional formula and revises her own belief at each step by considering the beliefs of her acquaintances, using belief change tools. In this paper, we investigate the extent to which BRGs satisfy some monotonicity properties, i. e. , whether promoting some desired piece of belief to a given set of agents is actually always useful for making it accepted by all of them. We formally capture such a concept of promotion by a new family of belief change operators. We show that some basic monotonicity properties are not satisfied by BRGs in general, even when the agent's merging-based revision policies are fully rational (in the AGM sense). We also identify some classes where they hold.

PDF Details

KR Conference 2016 Short Paper

Representative Solutions for Multi-Objective Constraint Optimization Problems

Nicolas Schwind
Tenda Okimoto
Maxime Clement
Katsumi Inoue

Solving a multi-objective constraint optimization problem (MO-COP) typically consists in computing all Pareto optimal solutions, which are exponentially many in the general case. This causes two problems: time complexity and lack of decisiveness. We present an approach which, given a number k of desired solutions, selects k Pareto optimal solutions that are representative of the Pareto front. We analyze the computational complexity of the underlying computational problem and provide exact and approximation procedures. Preliminaries We consider a given ﬁxed number m of objectives. A multiobjective constraint optimization problem (MO-COP) is a tuple X, D, C h, C s , where: X = {x1,..., xn } is a set of variables; D = {D1,..., Dn } is a multiset of non-empty domains for the variables; C h is a ﬁnite set of hard constraints, i. e., for each Cjh ∈ C h, Cjh ⊆ Di1 × · · · × Dij for some {Di1,..., Dij } ⊆ D; and C s is a ﬁnite set of soft, polyadic constraints, i. e., each Cjs ∈ C s is a mapping from {Di1,..., Dij } to Nm, for some {Di1,..., Dij } ⊆ D. Each constraint from C h ∪ C s involves a set of variables Xj ⊆ X called its scope. Let P be an MO-COP X, D, C h, C s . An assignment A of P associates each xi ∈ X with a value from Di; A is a solution of P if there is no Cjh ∈ C h such that (A(xi1),..., A(xij)) ∈ Cjh, where {xi1,..., xij } is the scope of Cjh. Sols(P) denotes the set of solutions of P. Given an m-vector U, we denote by U k or U (k) its k th component, with k ∈ {1,..., m}. The cost vector of A is the mvector denoted deﬁned for each k ∈ {1,..., m} as by V (A) s C (A(x V (A)k = s s i1),..., A(xij))(k), where for j Cj ∈C each Cjs, {xi1,..., xij } is the scope of Cjs. When S is a set of solutions, V (S) denotes the set {V (A) | A ∈ S}. Let m be the product ordering over Nm, i. e., ∀V1, V2 ∈ Nm, V1 m V2 iff ∀k ∈ {1,..., m}, V1k ≤ V2k. The preordering P ar over Sols(P), called the Pareto dominance relation, is deﬁned ∀A, A ∈ Sols(P) as A P ar A iff V (A) m V (A); we say that A Pareto dominates A. A Pareto optimal solution of P is a solution S ∈ Sols(P) which is not strictly Pareto dominated by an other solution S ∈ Sols(P). SP ar (P) denotes the set of Pareto optimal solutions of P, and PF(P) = S∈SP ar (P) V (S) is called the Pareto front of P.

AAAI Conference 2015 Conference Paper

Belief Revision Games

Nicolas Schwind
Katsumi Inoue
Gauvain Bourgne
Sébastien Konieczny
Pierre Marquis

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.

PDF Details

AIJ Journal 2014 Journal Article

Lost in translation: Language independence in propositional logic – application to belief change

Pierre Marquis
Nicolas Schwind

While propositional logic is widely used as a representation framework for many AI applications, the concept of language independence in the propositional setting has not received much attention so far. In this paper, we define language independence for a propositional operator as robustness w. r. t. symbol translation. We motivate the need to focus on symbol translations of restricted types, introduce and study several families of translations of interest, and provide a number of characterization results. We also identify the computational complexity of recognizing symbol translations from those families. Then we investigate the robustness of belief merging, belief revision and belief update operators w. r. t. translations of different types. It turns out that some rational merging/revision/update operators are not guaranteed to offer the most basic (yet non-trivial) form of language independence.

Details DOI

IJCAI Conference 2011 Conference Paper

Belief Base Rationalization for Propositional Merging

S
eacute; bastien Konieczny
Pierre Marquis
Nicolas Schwind

Existing belief merging operators take advantage of all the models from the bases, including those contradicting the integrity constraints. In this paper, we show that this is not suited to every merging scenario. We study the case when the bases are "rationalized" with respect to the integrity constraints during the merging process. We define in formal terms several independence conditions for merging operators and show how they interact with the standard IC postulates for belief merging. Especially, we give an independence-based axiomatic characterization of a distance-based operator.

PDF Details DOI

IJCAI Conference 2011 Conference Paper

Lost in Translation: Language Independence in Propositional Logic - Application to Belief Revision and Belief Merging

Pierre Marquis
Nicolas Schwind

Despite the importance of propositional logic in artificial intelligence, the notion of language independence in the propositional setting (not to be confound with syntax independence) has not received much attention so far. In this paper, we define language independence for a propositional operator as robustness w. r. t. symbol translation. We provide a number of characterizations results for such translations. We motivate the need to focus on symbol translations of restricted types, and identify several families of interest. We identify the computational complexity of recognizing symbol translations from those families. Finally, as a case study, we investigate the robustness of belief revision/merging operators w. r. t. translations of different types. It turns out that rational belief revision/merging operators are not guaranteed to offer the most basic (yet non-trivial) form of language independence; operators based on the Hamming distance do not suffer from this drawback but are less robust than operators based on the drastic distance.

PDF Details DOI

ECAI Conference 2010 Conference Paper

Majority Merging: from Boolean Spaces to Affine Spaces

Jean-François Condotta
Souhila Kaci
Pierre Marquis
Nicolas Schwind

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.

Details