# Opérateurs totalement informatifs et ordres linéaires partitionnés en révision de croyances

Khaled Belahcene, Jérome Gaigne, Sylvain Lagrue

► To cite this version:

Khaled Belahcene, Jérome Gaigne, Sylvain Lagrue. Opérateurs totalement informatifs et ordres linéaires partitionnés en révision de croyances. 17èmes Journées d'Intelligence Artificielle Fondamentale (JIAF-JFPDA 2023), Jul 2023, Strasbourg, France. pp.43-54. hal-04430609

HAL Id: hal-04430609

https://hal.science/hal-04430609v1

Submitted on 1 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Opérateurs totalement informatifs et ordres linéaires partitionnés en révision de croyances

Khaled Belahcene¹ Jérôme Gaigne² Sylvain Lagrue²

¹MICS, CentraleSupélec, Université Paris-Saclay, Gif-Sur-Yvette, France

²Université de technologie de Compiègne, CNRS, Heudiasyc (Heuristics and Diagnosis of Complex Systems), CS 60 319 – 60 203 Compiègne Cedex

khaled.belahcene@centralesupelec.fr {jerome.gaigne,sylvain.lagrue}@hds.utc.fr

## Résumé

Cet article traite d'opérateurs de révision des croyances qui conduisent à des situations totalement informées. Ce type de situation peut être représenté dans le cadre de révision de Katsuno et Mendelzon par une formule propositionnelle complète à partir de laquelle n'importe quelle formule ou sa négation peut être déduite. Nous caractérisons de tels opérateurs par un ensemble de postulats et fournissements un théorème de représentation qui conduit à totalement ordonner les interprétations. Nous présentons une famille d'opérateurs concrets basée sur des fonctions de départage. Néanmoins, les ordres linéaires sont extrêmement difficiles à obtenir dans la pratique. C'est pourquoi nous proposons dans une deuxième partie une structure ordonnée originale, appelée ordre linéaire partitionné (OLP). Ces structures peuvent être considérées comme des restrictions d'ordres linéaires indépendants, chacun d'entre eux représentant une situation locale totalement informée. Nous étudions les propriétés de la famille des OLP en termes d'expressivité, de représentations graphiques et de modèles interdits. Enfin, nous proposons des postulats rationnels et un théorème de représentation pour les opérateurs de révision aboutissant à un les OLP sur les interprétations, ainsi qu'un opérateur concret satisfaisant ces postulats.

## Abstract

This paper focuses on belief revision operators leading to totally informed situations. This kind of situation can be represented in Katsuno Mendelzon revision framework by a complete propositional formula from which either any formula or its negation can be entailed. We characterize such operators by a set of postulates and provide a representation theorem that leads to linear orders on interpretations. We exhibit a concrete operator family satisfying this new set of postulates by combining KM revision operators with tie-breaking functions. Nevertheless, linear orders are extremely difficult to obtain in practice. For that reason, we propose in a second part a new ordered structure named par-

titioned linear orders (PLO). These structures can be viewed as split independent linear orders, each of them representing a local totally informed situation. We study the properties of PLO in terms of expressiveness, graphical representations, and forbidden patterns. Finally, we propose rational postulates and a representation theorem for revision operators handling PLOs.

## 1 Introduction

La révision de croyance correspond au problème pouvant survenir lorsqu'un agent reçoit une nouvelle information potentiellement en contradiction avec ses croyances actuelles. Cet article se place dans le cadre de Katsuno Mendelzon (KM), dans lequel les croyances d'un agent, c'est-à-dire sa représentation du monde (de la situation), sont représentées par une formule propositionnelle $\varphi$ et la nouvelle information par une autre formule $\alpha$. Il peut arriver que le processus de révision de croyance permette de raffiner les croyances courantes de l'agent et ainsi lui donner une meilleure appréciation de la situation. Par exemple, en se référant au postulat ($R_2$), si la nouvelle information $\alpha$ est cohérente avec les croyances actuelles de l'agent $\varphi$, alors le résultat se doit d'être la conjonction $\varphi \wedge \alpha$.

Cet article approfondit cette idée et se focalise sur les opérateurs de révision menant à des *situations totalement informées*. Ce type de situation est représenté par une formule propositionnelle complète depuis laquelle toute formule ou sa négation peut être déduite. Autrement dit, il s'agit d'une formule satisfaite par un seul modèle. Ce type de d'information, sans équivoque, est particulièrement important dans une situation de décision. Par exemple, les procédures de vote mises effectivement en pratique sont *décisives*, en ce sens qu'elles désignent systématiquement un vainqueur
univoque, généralement en complétant une règle idéale respectant le principe d'anonymat (telle que le vote à majorité simple ou le décompte de Borda) à l'aide d'une procédure de départage, par exemple en privilégiant un électeur spécifique ou en se référant à une variable exogène (telle que l'âge du candidat). Dans le domaine de la décision dans l'incertain, dans une situation de complète ignorance, on obtient une procédure de décision quasi décisive en appliquant le principe d'indifférence de Laplace, qui consiste à considérer que les mondes possibles sont équirépartis et à choisir l'option majoritaire, et pour laquelle [34] propose le qualificatif de "pignistique". En décision multicritère, il est fréquent que les procédures paramétriques servant à agréger les points de vue soient élicitées de manière incomplète. On peut alors envisager de raisonner de manière prudente vis-à-vis de l'espace des versions du modèle, mais l'approche de loin la plus fréquente (c.f. par exemple [4] au sujet des modèles de tri multicritère) consiste à sélectionner un agrégateur jugé représentatif parmi l'ensemble des agrégateurs possibles en cherchant à optimiser une fonction objectif adéquate. Ainsi, la procédure d'agrégation n'abouftira jamais à une situation d'incomparabilité.

Un opérateur de révision totalement informatif est un opérateur menant à une situation totalement informée. Nous proposons dans cet article un jeu de postulats capturant ce comportement. Nous définissons aussi un opérateur basé sur celui proposé par Dalal qui, équipé avec une fonction de tie-break, satisfait tous ces postulats. Nous proposons aussi un théorème de représentation en termes de structures ordonnées et montrons que nos postulats mènent à des ordres linéaires, c'est-à-dire des ordres où la plausibilité relative de deux situations quelconques peut être comparée strictement.

Néanmoins, les ordres linéaires sont difficiles à obtenir en pratique. C'est pourquoi nous proposons, dans un second temps, une nouvelle structure ordonnée nommée ordres linéaires partitionnés (OLP). Cette structure peut être vue comme un ensemble d'ordres linéaires indépendants et séparés, chacun d'entre eux représentant localement une situation totalement informée. Nous étudions en détail ces structures et proposons un jeu de postulats les capturant. Nous proposons aussi un opérateur basé sur les diagrammes de Voronoï et les fonctions de tie-break vérifiant nos postulats de rationalité.

La section 2 rappelle les concepts nécessaires sur les structures ordonnées et la révision de croyance. Ensuite, la section 3 se concentre sur notre première contribution, la caractérisation des opérateurs de révisions totalement informatifs. Nous proposons aussi dans cette section un exemple d'opérateur. Comme les opérateurs de révisions totalement informatifs peuvent être considérés comme excessivement spécifiques pour la représentation de croyances, nous proposons et étudions une structure ordonnée originale, les ordres linéaires partitionnés (OLP) dans la section 4. Par la

suite, la section 5 se focalise sur la révision de croyances utilisant les OLP. Finalement, avant de conclure, la section 6 propose une discussion sur les travaux associés.

## 2 Préliminaires

Nous proposons dans cette section les éléments nécessaires à la compréhension du papier. Dans une première partie, nous rappelons différentes notions sur les structures ordonnées. Puis, dans une seconde partie, nous traitons la logique propositionnelle, la révision de croyance ainsi que son lien avec les structures ordonnées.

### 2.1 Structures ordonnées

**Relation binaire** Soit $\mathcal{R}$ une relation binaire sur l'ensemble $X$. Alors $\mathcal{R}$ est :

- réflexive lorsque $\forall x \in X, x \mathcal{R} x$;

- transitive lorsque $\forall x, y, z \in X$, si $x \mathcal{R} y$ et $y \mathcal{R} z$, alors $x \mathcal{R} z$;

- antisymétrique lorsque $\forall x, y \in X$, si $x \mathcal{R} y$ et $y \mathcal{R} x$ alors $x = y$;

- asymétrique lorsque $\forall x, y \in X$, si $x \mathcal{R} y$ alors $\neg(y \mathcal{R} x)$;

- totale lorsque $\forall x, y \in X$, soit $x \mathcal{R} y$ soit $y \mathcal{R} x$.

Un préordre, noté $\leq$, est une relation réflexive et transitive. Un ordre, noté $\leq$, est un préordre antisymétrique. Un ordre linéaire (alias un ordre total) est un ordre total. Étant donné un préordre $\leq$, nous notons par $<$ sa partie asymétrique, et par $\approx$ sa partie symétrique, et par $\sim$ la relation d'incomparabilité, c'est-à-dire :

- $x < y$ lorsque $x \leq y$ et non $y \leq x$;

- $x \approx y$ lorsque à la fois $x \leq y$ et $y \leq x$; et

- $x \sim y$ lorsque ni $x \leq y$ ni $y \leq x$.

Ces notations sont les mêmes pour les ordres $\leq$.

**Posets** Un ensemble $X$ associé à un (pré)ordre $\mathcal{R}$ est un ensemble (pré)ordonné noté $P = (X, \mathcal{R})$. Un ensemble partiellement ordonné, également appelé poset, est un ensemble ordonné par un ordre partiel.

L'union de posets disjoints est définie comme suit. Étant donné deux posets $P_a = (X_a, \leq_a)$ et $P_b = (X_b, \leq_b)$ tels que $X_a \cap X_b = \emptyset$, nous avons $P = (X, \leq) = P_a \cup P_b$ tel que $X = X_a \cup X_b$ et $\forall x, y \in X, x \leq y \text{ ssi}$

$$ \begin{cases} x, y \in X_a & \text{et } x \leq_a y, & \text{ou} \\ x, y \in X_b & \text{et } x \leq_b y & \end{cases} $$

Finalement, étant donnés un ensemble préordonné $P = (X, \leq)$ et $Y \subseteq X$, nous en définissons les éléments minimaux de $Y$ de la manière suivante :

$$ \text{Min}(Y, \leq) = \{x \in Y : \forall y \in Y, \text{ non } y < x\} $$
## 2.2 Rappel sur la révision de croyance

Nous commençons par établir les notations utilisées tout au long de l'article.

### 2.2.1 Logique propositionnelle

Nous notons par $\mathcal{P}$ un ensemble fini de variables positionnelles et par $\mathcal{L}$ l'ensemble des formules propositionnelles qui peuvent être construites à partir de $\mathcal{P}$. Nous utilisons les connecteurs usuels $\lor, \land, \neg, \to, \leftrightarrow$ et les symboles $\top$ et $\bot$ pour représenter respectivement la formule toujours vraie et la formule toujours fausse. Les éléments de $\mathcal{L}$ sont représentés par des lettres grecques. L'ensemble de toutes les interprétations de $\mathcal{L}$ est noté $\Omega$ et $[\alpha]$ représente l'ensemble des modèles de $\alpha$, c'est-à-dire l'ensemble $\{\omega \in \Omega : \omega \models \alpha\}$. La formule $\alpha_M$ avec $M \subseteq \Omega$ dénote la formule ayant pour modèles $M$ et seulement $M$.

### 2.2.2 Révision de croyances

La révision de croyances correspond au problème apparaissant lorsqu'une nouvelle information à propos du monde est donnée à un agent, tel que cette nouvelle information et les croyances actuelles de l'agent soient potentiellement incohérentes. Le cadre AGM [1] propose un ensemble de postulats de rationalité qui sont la base du cadre AGR pour la révision de croyance qui est communément accepté. Une reformulation des postulats AGM en logique propositionnelle a été développée dans [21] et a conduit aux postulats suivants :

$$ (R_1) \varphi \circ \alpha \vdash \alpha $$

$$ (R_2) \text{ si } \varphi \wedge \alpha \varphi \perp, \text{ alors } \varphi \circ \alpha \equiv \varphi \wedge \alpha $$

$$ (R_3) \text{ si } \alpha \varphi \perp, \text{ alors } \varphi \circ \alpha \text{ est cohérent} $$

$$ (R_4) \text{ si } \varphi_1 \equiv \varphi_2 \text{ et } \alpha \equiv \beta \text{ alors } \varphi_1 \circ \alpha \equiv \varphi_2 \circ \beta $$

$$ (R_5) \text{ (}\varphi \circ \alpha) \wedge \beta \vdash \varphi \circ (\alpha \wedge \beta) $$

$$ (R_6) \text{ si } (\varphi \circ \alpha) \wedge \beta \varphi \perp, \text{ alors } \varphi \circ (\alpha \wedge \beta) \vdash (\varphi \circ \alpha) \wedge \beta $$

Il a également été montré qu'un opérateur de révision ◦ satisfaisant tous ces postulats est équivalent à chercher le minimum dans un préordre total spécifique obtenu par le biais d'un *assignement fidèle* de ◦.

**Définition 1** (Assignement fidèle, [21]). *Une fonction assignant, à une formule $\varphi$, un préordre total $\lesssim_{\varphi}$ sur $\Omega$ est un assignement fidèle ssi*

$$ (1) \text{ si } \omega_1, \omega_2 \in [\varphi] \text{ alors } \omega_1 <_{\varphi} \omega_2 \text{ est faux} $$

$$ (2) \text{ si } \omega_1 \in [\varphi] \text{ et } \omega_2 \notin [\varphi] \text{ alors } \omega_1 <_{\varphi} \omega_2 \text{ est vrai} $$

$$ (3) \text{ si } \varphi \equiv \psi, \text{ alors } \lesssim_{\varphi} = \lesssim_{\psi} $$

La première condition stipule que les modèles des croyances actuelles sont équivalents. La seconde requiert que tous les modèles soient préférés à tous les contre-modèles. La troisième condition exprime l'indépendance à la syntaxe.

**Théorème 1** ([21]). *Un opérateur de révision ◦ satisfait les postulats $(R_1)-(R_6)$ ssi il existe un assignement fidèle qui fait correspondre $\varphi$ et le préordre total $\lesssim_{\varphi}$ tel que*

$$ [\varphi \circ \mu] = \text{Min} ([\mu], \lesssim_{\varphi}). $$

### 2.2.3 Révision d'informations partiellement ordonnées

L'utilisation des postulats KM implique que les informations puissent être représentées par un préordre total. Ce prérequis constitue une limite en termes d'expressivité lorsque la situation comporte des informations incomplètes. C'est pourquoi, deux postulats plus faibles ont été proposés dans [21] pour remplacer $(R_6)$, à savoir $(R_7)$ et $(R_8)$, afin de représenter des informations partiellement ordonnées. Néanmoins, cette proposition est insuffisante pour représenter tous les ordres partiels. Dès lors, il a été proposé dans [6] d'utiliser un affaiblissement de $(R_2)$, $(R'_2)$, pour pouvoir représenter l'ensemble des informations partielle-ment ordonnées.

$$ (R'_2) \varphi \circ \top \equiv \varphi $$

$$ (R_7) \text{ si } \varphi \circ \alpha \vdash \beta \text{ et } \varphi \circ \beta \vdash \alpha \text{ alors } \varphi \circ \alpha \equiv \varphi \circ \beta $$

$$ (R_8) \text{ si } (\varphi \circ \alpha) \wedge (\varphi \circ \beta) \vdash \varphi \circ (\alpha \vee \beta) $$

Ils ont aussi défini la notion de *p-assignement fidèle* pour capter la notion d'ordre partiel.

**Définition 2** (*p-assignement fidèle*, [6]). *Une fonction assignant à une formule $\varphi$, un préordre partiel $\lesssim_{\varphi}$ sur $\Omega$ est un p-assignement fidèle ssi :*

$$ (1) \text{ si } \omega_1, \omega_2 \in [\varphi] \text{ alors } \omega_1 <_{\varphi} \omega_2 \text{ est faux} $$

$$ (2') \text{ si } \omega_2 \notin [\varphi] \text{ alors il existe } \omega_1 \text{ tel que } \omega_1 \in [\varphi] \text{ et } \omega_1 <_{\varphi} \omega_2 \text{ soit vrai} $$

$$ (3) \text{ si } \varphi \equiv \psi, \text{ alors } \lesssim_{\varphi} = \lesssim_{\psi} $$

La première différence avec la définition de *assignement fidèle* réside dans le fait que le préordre n'est plus total. La seconde différence est la condition (2'). Relaxant la condition (2), elle requiert uniquement l'existence d'un modèle préféré pour chaque contre-modèle.

Finalement, le théorème de représentation suivant a été proposé.

**Théorème 2** ([6]). *Un opérateur de révision p ◦ satisfait les postulats $(R_1), (R'_2), (R_3)-(R_5), (R_7), (R_8)$ ssi il existe un p-assignement fidèle qui fait correspondre $\varphi$ au préordre partiel $\lesssim_{\varphi}$ tel que :*

$$ [\varphi \circ \mu] = \text{Min} ([\mu], \lesssim_{\varphi}). $$

## 3 Opérateurs de révision totalement informatifs

Par essence, l'un des objectifs des opérateurs de révision de croyance n'est pas seulement d'intégrer une information potentiellement incohérente avec les croyances initiales
de l'agent, mais aussi d'utiliser cette nouvelle information pour les raffiner. Par exemple, si la nouvelle information $\alpha$ est cohérente avec les croyances initiales de l'agent, en satisfaisant ($R_2$), le résultat de la révision conduit toujours au raffinement des croyances initiales $\varphi \circ \alpha \equiv \varphi \wedge \alpha$. La situation représentée par $\varphi \circ \alpha$ est plus spécifique que la croyance initiale $\varphi$ de l'agent, dans le sens qu'elle décide plus de formules. De façon équivalente, si nous nous formalisons sur les modèles, si $\varphi$ et $\alpha$ ne sont pas incohérents entre eux, les mondes possibles pour l'agent, représentés par $[[\varphi \circ \alpha]]$, forme un sous-ensemble des modèles de ses croyances initiales $[[\varphi]]$.

L'objectif de cette section est d'aller encore plus loin dans cette idée en nous concentrant sur les opérateurs mechant à une situation totalement informée, c'est-à-dire à une formule complète qui décide toute formule. De façon équivalente, en termes de modèles, il s'agit d'une formule n'admettant qu'un seul modèle.

**Exemple 1.**

Considérons les connaissances expertes d'un médecin concernant les patients atteints de la grippe (g) et de la toux (t). Les deux situations qui sont les plus plausibles pour eux sont $\neg t \wedge \neg g$ où le patient ne tousse pas et n'a pas la grippe, et $t \wedge g$ où le patient tousse et souffre de la grippe. En d'autres mots, $[[\varphi]] = \{\{\neg t, \neg g\}, \{t, g\}\}$.

Étant donné la nouvelle information disant que le patient tousse, modélisée par $\alpha = t$, le résultat du processus de révision est $\varphi \circ \alpha \equiv t \wedge g$. Dans ce cas, la situation est dite totalement informée, les croyances du médecin n'ayant qu'un seul modèle, $\{t, g\}$. Le médecin peut alors prendre une décision se basant sur ses croyances en étant totalement informé à propos de toutes les variables du langage.

Nous formalisons le concept d'opérateur de révision totalement informatif dans la sous-section suivante, y compris si la nouvelle information est contradictoire avec les croyances actuelles de l'agent, et nous les capturons au travers de postulats de rationalité.

## 3.1 Formalisation

Un opérateur de révision ◦ est totalement informatif s'il satisfait la propriété suivante :

(TI) $\forall \alpha \in \mathcal{L}$, si $\alpha \nparallel \perp$, alors $\varphi \circ \alpha$ est complète.

Autrement dit, si la nouvelle information n'est pas incohérente, un opérateur TI mène à une situation totalement informée, c'est-à-dire à une formule ne possédant qu'un seul et unique modèle.

Un opérateur satisfaisant ($R_2$) ne peut pas être un opérateur de révision totalement informatif.

**Proposition 1.** *Les postulats (R<sub>2</sub>) et (TI) sont mutuellement inconsistants.*

Cette proposition nous amène à considérer l'affaiblissement suivant de ($R_2$) :

($R_{2w}$) si $\varphi \wedge \alpha \nparallel \perp$ alors $\varphi \circ \alpha \vdash \varphi \wedge \alpha$

Cet affaiblissement de ($R_2$) peut se retrouver dans la littérature, par exemple dans [6], [31], ou dans [19] où ($R_{2w}$) apparaît sous le nom de ($R_7$). Il y est présenté comme le postulat de vacuité dans la formulation AGM, cela permet à l'agent d'ignorer une partie de l'information sur ses croyances même si celle-ci est cohérente avec la nouvelle information. Nous préférons l'interpréter ici comme la possibilité pour l'agent de sélectionner arbitrairement un sous-ensemble de ces mondes, ce qui peut être vu comme un gain d'information.

Nous proposons maintenant un postulat original, nommé ($R_L$), pour caractériser les opérateurs de révision totalement informatifs. Celui-ci stipule que si $\alpha$ et $\beta$ sont cohérents, mais ensemble incohérents, alors la disjonction de $\varphi \circ \alpha$ et $\varphi \circ \beta$ ne permet pas de déduire la révision par la disjonction de $\alpha$ et $\beta$.

($R_L$) si $\alpha \nparallel \perp, \beta \nparallel \perp$, et $\alpha \wedge \beta \vdash \perp$ alors $(\varphi \circ \alpha) \vee (\varphi \circ \beta) \nparallel \varphi \circ (\alpha \vee \beta)$

**Proposition 2.** *Les postulats ($R_2$) et ($R_L$) sont mutuellement inconsistants.*

La proposition suivante stipule que, en présence de ($R_1$), ($R_{2w}$), ($R_3$)–($R_6$), les postulats ($R_L$) et (TI) sont équivalents.

**Proposition 3.** *Considérons un opérateur de révision ◦ satisfaisant ($R_1$), ($R_{2w}$), ($R_3$)–($R_6$). Alors :*

◦ satisfait ($R_L$) ssi ◦ satisfait (TI).

Finalement, nous proposons un théorème de représentation pour les opérateurs de révision TI. Ce théorème se réfère à la notion de TI-assignement fidèle qui fait correspondre une formule et un ordre linéaire où tous les contre-modèles sont dominés par les modèles (1). Cet ordre est aussi indépendant à la syntaxe (condition (2)). La différence principale avec les assignements fidèles et p-fidèles, si nous ignorons le fait que l'ordre doit être linéaire, est que les modèles peuvent être strictement comparés.

**Définition 3 (TI-assignement fidèle).** Une fonction assignant, à une formule $\varphi$, un ordre linéaire $\leq_{\varphi}$ sur $\Omega$ est un assignement fidèle totalement informé ssi

(1) si $\omega_1 \in [[\varphi]]$ et $\omega_2 \notin [[\varphi]]$ alors $\omega_1 <_{\varphi} \omega_2$ est vrai

(2) si $\varphi \equiv \psi$, alors $\leq_{\varphi} \leq \psi$

Nous pouvons maintenant introduire le théorème de représentation suivant. Globalement, ce théorème dit que, étant donné un opérateur de révision TI, il est possible d'associer aux croyances d'un agent un ordre linéaire correspondant sur l'ensemble des interprétations.
**Théorème 3.** Un opérateur de révision TI ◦ satisfait ($\mathbf{R}_1$), ($\mathbf{R}_{2w}$), ($\mathbf{R}_3$)–($\mathbf{R}_6$) et ($\mathbf{R}_L$) ssi il existe un TI-assignement fidèle qui fait correspondre $\varphi$ et l'ordre linéaire $\leq_{\varphi}$ tel que :

$$ \llbracket \varphi \circ \alpha \rrbracket = \text{Min} (\llbracket \alpha \rrbracket, \leq_{\varphi}) $$

## 3.2 Un opérateur totalement informatif concret

Nous présentons dans cette section un opérateur concret démontrant la cohérence de notre ensemble de postulats. En pratique, un opérateur de révision totalement informatif peut être obtenu en couplant un opérateur de révision de Dalal [13] avec une fonction de tie-break. Un opérateur de révision de Dalal est un opérateur de révision basé sur la distance de Hamming entre les interprétations, où $d_H(\omega, \omega') = |\{x \in \mathcal{P} : \omega(x) \neq \omega'(x)\}|$. Cette distance peut directement être étendue à la distance entre une interprétation $\omega$ et une formule $\varphi$ en considérant la distance minimale entre $\omega$ et les modèles de $\varphi$, c'est-à-dire $d_H(\varphi, \omega) = \min\{d_H(\omega', \omega) : \omega' \in \llbracket \varphi \rrbracket\}$.

**Exemple 2.** Soit $\mathcal{P} = \{a, b, c, d\}$. La distance de Hamming entre $\omega = \{a, b\}$ et $\varphi$ telle que $\llbracket \varphi \rrbracket = \{\neg a, \neg b\}, \{a, \neg b\}\}$, est alors $d_H(\varphi, \omega) = \min\{d_H(\neg a, \neg b), \{a, b\}), d_H(\{a, \neg b\}, \{a, b\})\} = 1$.

Étant donné une formule $\varphi$, il est possible d'ordonner les interprétations en fonction de leur distance de Hamming à la formule $\varphi$ :

$$ \omega \lesssim_{\varphi}^{d_H} \omega' \text{ ssi } d_H(\varphi, \omega) \leq d(\varphi, \omega'). $$

Le résultat de la révision de Dalal est équivalent à l'ensemble des éléments minimaux pour ce préordre :

$$ \llbracket \varphi \circ_{d_H} \alpha \rrbracket = \text{Min}(\llbracket \alpha \rrbracket, \lesssim_{\varphi}^{d_H}). $$

Nous proposons d'associer à $\circ_{d_H}$ une fonction de départage. Ce type de fonction est d'habitude utilisé dans la prise de décision collective et dans le choix social (computationnel); par exemple [12, 16]. Étant donné un ensemble d'alternatives, une fonction de départage est capable de sélectionner exactement un élément préféré. Pour ce partir, nous ne considérons uniquement que les fonctions de départage déterministes $\mathcal{T}$ sur $\Omega$ satisfaisant la propriété d'indépendance suivante (noté $\alpha$ dans [32]):

$$ \forall E, E' \in 2^{\Omega} \text{ t.q. } \mathcal{T}(E) \in E' \subseteq E, \text{ nous avons } \mathcal{T}(E') = \mathcal{T}(E) $$

En considérant $d_H$ et une fonction de départage $\mathcal{T}$, nous pouvons dériver, d'une formule $\varphi$, un ordre linéaire $\leq_{\varphi}^{d_H, \mathcal{T}}$ tel que : $\omega \leq_{\varphi}^{d_H, \mathcal{T}} \omega'$ ssi $\omega <_{\varphi}^{d_H} \omega'$ ou $(\omega \approx_{\varphi}^{d_H} \omega') \text{ et } \mathcal{T}(\{\omega, \omega'\}) = \omega)$.

**Définition 4** (Opérateur de révision totalement informatif de Dalal). Étant donné une fonction de départage $\mathcal{T}$, une formule $\varphi$ et une nouvelle information $\alpha$, $\varphi \circ_{d_H, \mathcal{T}} \alpha$ est tel que :

$$ \llbracket \varphi \circ_{d_H, \mathcal{T}} \alpha \rrbracket = \text{Min} (\llbracket \alpha \rrbracket, \leq_{\varphi}^{d_H, \mathcal{T}}). $$

<figure><img src="image_1.png" /><figcaption>FIGURE 1 – Diagramme de Hasse<fnref n="1" /> représentant $\varphi$ de l'Exemple 3 avec $\lesssim_{\varphi}^{d_H}$ étant le préordre obtenu avec les distances de Hamming, $\lesssim_{\mathcal{T}}$ l'ordre linéaire dérivé de $\mathcal{T}$, et $\leq_{\varphi}^{d_H, \mathcal{T}}$ l'ordre obtenu en appliquant la fonction de tie-break.</figcaption></figure>

À partir d'une fonction de départage $\mathcal{T}$ satisfaisant la propriété d'indépendance, il est possible de construire un ordre linéaire $\leq_{\mathcal{T}}$ sur l'ensemble des interprétations : l'élément préféré est $\mathcal{T}(\Omega)$, le second est $\mathcal{T}(\Omega \setminus \{\mathcal{T}(\Omega)\})$, etc. L'ordre linéaire $\leq_{\varphi}^{d_H, \mathcal{T}}$ défini ci-dessus est équivalent au raffinement lexicographique du préordre $\lesssim_{\varphi}^{d_H}$ par l'ordre linéaire $\leq_{\mathcal{T}}$.

Un tel raffinement lexicographique peut être retrouvé dans la littérature, par exemple dans [5] où les états épistémiques sont révisés par d'autres états épistémiques. Il peut aussi être trouvé dans [2] qui se focalise sur les propriétés rationnelles de la combinaison de relations de préférence qui conduisent à une combinaison lexicographique. Cette idée est la pierre angulaire des modèles de décision non compensatoire (voir par exemple [11] pour trier des alternatives dans de multiples catégories ou [30] pour les classer) obtenue par raffinement successif via des préordres partiels bivalués [10]. Cette idée de raffiner les modèles de la nouvelle information, même s'ils ne sont pas aussi drastiques que nous le sommes, peut être trouvée chez [19].

**Exemple 3.** Soit $\mathcal{P} = \{a, b\}$, et $\Omega = \{\omega_0, \omega_1, \omega_2, \omega_3\}$ tel que $\omega_0 = \{\neg a, \neg b\}, \omega_1 = \{\neg a, b\}, \omega_2 = \{a, \neg b\}, \omega_3 = \{a, b\}$. Considérons $\varphi = \neg b$, donc $\llbracket \varphi \rrbracket = \{\omega_0, \omega_2\}$. Comme fonction de départage $\mathcal{T}$, nous prenons l'ordre lexicographique sur les interprétations induit par l'ordre suivant sur les variables propositionnelles falsifiées $a < b$. La Figure 1 représente, dans un diagramme de Hasse<fnref n="1" />, $\varphi$ premièrement, comme le préordre de Dalal $\lesssim_{\varphi}^{d_H}$ correspondant uniquement au calcul des distances de Hamming, puis comme un ordre $\leq_{\varphi}^{d_H, \mathcal{T}}$ obtenu en appliquant la fonction de départage sur ce préordre. Considérons maintenant que $\varphi$ est révisé par $\alpha = b$. Alors $\llbracket \alpha \rrbracket = \{\omega_1, \omega_3\}$, et nous avons $\llbracket \varphi \circ \alpha \rrbracket = \{\omega_1\}$.

Comme attendu, l'opérateur de révision $\circ_{d_H, \mathcal{T}}$ est un opérateur de révision totalement informatif.

<footnote n="1">1. Les diagrammes de Hasse sont une représentation graphique des préordres où ni la réflexivité, ni la transitivité ne sont représentées et où les éléments minimaux sont au bas de la figure.</footnote>
**Proposition 4.** *L'opérateur de révision ◦<sub>d<sub>H</sub>,T</sub> satisfait (R<sub>1</sub>), (R<sub>2w</sub>), (R<sub>3</sub>)-(R<sub>6</sub>), (R<sub>L</sub>).*

# 4 Ordres linéaires partitionnés

En révision de croyance, des structures ordonnées peuvent être employées pour modéliser les croyances et la plausibilité qu’un agent associe à chaque monde. Pour ces structures ordonnées, la propriété de totalité est à la fois très exigeante quand il s’agit d’alimenter le modèle en information et d’une portée sans limites, ce qui peut parfois paraître abusif quand nous nous intéressons à la sémantique des modèles dans le monde réel. C’est pourquoi nous introduisons une relaxation de cette propriété, nommée comparabilité transitive, ainsi que la catégorie d’ordres la satisfaisant, appelée ici ordres linéaires partitionnés (OLP).

## 4.1 Définition

Nous introduisons la catégorie des ordres linéaires partitionnés via un détour avec la notion de comparabilité : étant donné une relation binaire $\mathcal{R}$ sur un ensemble $X$, on dit que deux éléments $x, y \in X$ sont comparables quand $x \mathcal{R} y$ ou $y \mathcal{R} x$. La relation de comparabilité est structurellement symétrique. La propriété de totalité d’une relation $\mathcal{R}$ peut alors se réécrire comme la complétude de la relation de comparabilité, c’est-à-dire la situation où toute paire d’éléments est comparable. Nous relâchons cette propriété globale pour n’imposer que la comparabilité soit seulement transitive, dans le but qu’elle se propage par contagion. En effet, quand n’importe quelle paire d’éléments est en relation avec un troisième, ils sont considérés comme faisant partie de la relation. Appliquée à un poset $(X, \leq)$, cette notion conduit à une partition de $X$ en classe d’équivalence sur la relation de comparabilité associée à $\leq$, où deux éléments de classes différentes sont incomparables. La relation binaire induite par $\leq$ sur chaque classe est alors un préordre total. Appliquée à un ensemble fini $X$ ordonné par $\leq$, la partition est finie et la relation induite par chaque classe est un ordre linéaire.

**Définition 5 (Ordre linéaire partitionné).** La relation binaire sur $X$, notée $\leq$, est un ordre linéaire partitionné ssi $\exists m \in \mathbb{N}^*$ tel que $X_1, \dots, X_m$ est une partition de $X$ (c’est-à-dire $\bigcup_{i=1}^m X_i = X$ et $\forall i, j \in \{1, \dots, m\}$ tel que $i \neq j$, $X_i \cap X_j = \emptyset$) et $\exists <_i$, un ordre linéaire sur $X_i$, $\forall i \in \{1, \dots, m\}$ tel que $(X, \leq) = \bigcup_{i=1}^m (X_i, <_i)$.

**Exemple 4.** Soit l’ensemble $X = \{a, b, c, d, e, f, g, h\}$ et l’ordre linéaire partitionné $\leq = \{(c, c), (c, b), (c, a), (b, b), (b, a), (a, a), (f, f), (f, e), (f, d), (e, e), (e, d), (d, d), (h, h), (h, g), (g, g)\}$. La partition de $X$ suivante, $X_1 = \{a, b, c\}$, $X_2 = \{d, e, f\}$ et $X_3 = \{g, h\}$ associée respectivement aux ordres linéaires $\leq_1 = \{(c, c), (c, b), (c, a), (b, b), (b, a), (a, a)\}$, $\leq_2 = \{(f, f)$,

<figure><img src="image_2.png" /><figcaption>FIGURE 2 – OLP $\leq$ sur $X$.</figcaption></figure>

$(f, e), (f, d), (e, e), (e, d), (d, d)$ et $\leq_3 = \{(h, h), (h, g), (g, g)\}$ conduit aux trois ensembles linéairement ordonnés $(X_1, \leq_1), (X_2, \leq_2)$, et $(X_3, \leq_3)$ tels que $(X, \leq) = \bigcup_{i \in \{1, 2, 3\}} (X_i, \leq_i)$. La Figure 2 représente ces ordres.

## 4.2 Représentations

Il est d’usage de représenter les ordres partiels comme une intersection d’ordres linéaires, ou encore à l’aide de fonctions numériques. Par exemple, n’importe quel préordre total $\leq$ sur un ensemble fini $X$ peut être représenté par une fonction de score $f: X \to \mathbb{N}$ telle que $x \leq y \iff f(x) \geq f(y)$. La relation $\leq$ est un ordre linéaire ssi $f$ est injective. Nous proposons ces deux types de représentation pour les ordres linéaires partitionnés.

Soit $\leq$ un OLP sur un ensemble fini $X$ menant à une partition $X = \bigcup_{i=1}^n X_i$ en classes de comparabilités. Soit $\mathcal{R}^>$ et $\mathcal{R}^<$ les relations binaires définies sur $X$ comme suivent :

$$ \forall x, y \in X, x \mathcal{R}^> y \text{ ssi } x \leq y \text{ ou } x \in X_i, y \in X_j \text{ et } i > j \quad (1) $$

$$ \forall x, y \in X, x \mathcal{R}^< y \text{ ssi } x \leq y \text{ ou } x \in X_i, y \in X_j \text{ et } i < j \quad (2) $$

**Proposition 5.** $\mathcal{R}^>$ et $\mathcal{R}^<$ sont des ordres linéaires sur $X$ qui raffine $\leq$ et tels que $\leq$ est le produit d’ordre de $\mathcal{R}^>$ et $\mathcal{R}^<$ (c’est-à-dire $x \leq y$ ssi $x \mathcal{R}^> y$ et $x \mathcal{R}^< y$).

Nous pouvons remarquer que les deux relations $\mathcal{R}^>$ et $\mathcal{R}^<$ dépendent de l’ordre arbitraire sur les classes de comparabilité de $(X, \leq)$, mais que leur produit d’ordre non. Comme nous le verrons dans la Section 4.3, la Proposition 5 positionne les ordres linéaires partitionnés comme une sous-catégorie des ordres bilinéaires. De plus, il est possible de produire trois représentations numériques des ordres linéaires partitionnés.

**Représentation en produit** Un OLP sur un ensemble fini $X$ peut être représenté avec deux fonctions de score $f, g$ :
<table><caption>TABLE 1 – f, g, f', g' : X $\mapsto$ $\mathbb{R}$, deux paires de fonctions de score, (f, g) offrant une représentation en produit et (f', g') une représentation en intervalles de $\triangle$.</caption><thead><tr><th>x &isin; X</th><th>f(x)</th><th>g(x)</th><th>f'(x)</th><th>g'(x)</th></tr></thead><tbody><tr><td>a</td><td>1</td><td>6</td><td>1</td><td>14</td></tr><tr><td>b</td><td>2</td><td>7</td><td>2</td><td>15</td></tr><tr><td>c</td><td>3</td><td>8</td><td>3</td><td>16</td></tr><tr><td>d</td><td>4</td><td>3</td><td>4</td><td>11</td></tr><tr><td>e</td><td>5</td><td>4</td><td>5</td><td>12</td></tr><tr><td>f</td><td>6</td><td>5</td><td>6</td><td>13</td></tr><tr><td>g</td><td>7</td><td>1</td><td>7</td><td>9</td></tr><tr><td>h</td><td>8</td><td>2</td><td>8</td><td>10</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>FIGURE 3 – Représentation graphique des fonctions f et g.</figcaption></figure>

$X \to \mathbb{N}$ telles que $x \triangleq y$ ssi $f(x) < f(y)$ et $g(x) < g(y)$ comme illustré par la Figure 3.

**Représentation en intervalle** Il peut être montré que la condition $\forall x \in X$, $f(x) > g(x)$ peut être imposée sans perte de généralité à la représentation en produit présentée ci-dessus. Alors, chaque élément de l'ensemble X peut être représenté par un intervalle non vide $[f(x), g(x)]$ [3, 28]. L'incomparabilité d'une paire d'éléments est représentée par l'inclusion/le fait d'être contenu de leurs intervalles respectifs, comme le montre la Figure 4. Cela implique que la relation de comparabilité stricte, c'est-à-dire $x < y$, est encodée par $f(x) < f(y)$ et $g(x) < g(y)$ comme présenté ci-dessus, ce qui diverge de la définition des ordres d'intervalle, où celle-ci est encodée par $g(x) < f(y)$.

**Ordre linéaire divisé** Un OLP sur un ensemble fini avec n classes de comparabilité peut être représenté via une fonction de score injective $f : X \to \mathbb{N}$ et un ensemble de $n-1$ seuils $\tau_1, \dots, \tau_{n-1}$ de la façon suivante : $x \triangleq y$ ssi $f(x) \le f(y)$ et $\mathfrak{H}i \in \{1, \dots, n-1\} f(x) < \tau_i < f(y)$.

**Exemple 5.** La Table 1 contient une représentation numérique de $(X, \triangleq)$ en tant que produit d'ordres de deux fonctions de score f et g. La représentation graphique de f et g est disponible Figure 3. Les éléments de X sont représentés par des segments tels que les segments représentant deux objets se croissent ssi ces objets sont incomparables. La représentation graphique de f' et g' est disponible Figure 4. Les éléments de X sont représentés par des intervalles tels qu'un intervalle en contient un autre ssi les deux éléments correspondants sont incomparables.

<figure><img src="image_4.png" /><figcaption>FIGURE 4 – Représentation graphique de $[f', g']$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIGURE 5 – Modèles interdits.</figcaption></figure>

## 4.3 Modèles interdits

Nous situons maintenant la catégorie des ordres linéaires partitionnés au sein de la cartographie de sous-catégories d'ordres partiels proposée dans la littérature. La Proposition 5 montre que les OLP sont une sous-catégorie des ordres bilinéaires, qui sont définis comme le produit d'ordres de deux ordres linéaires<fnref n="2" />.

Une autre façon de définir une sous-catégorie d'ordres partiels consiste à exclure certains sous-motifs du diagramme de Hasse, c'est-à-dire ce que cette catégorie est incapable de représenter.

Nous rappelons la définition d'ordres d'intervalle, de semi-ordres et d'ordres forts en termes de modèles interdits comme définis dans [15], ces modèles sont représentés Figure 5 :

- Ordres d'intervalle : pas de 2+2

- Semi-ordre : pas de 1+3 ni de 2+2

- Ordres forts : pas de 1+2

La catégorie des ordres linéaires partitionnés peut être définie au moyen de deux modèles interdits. Soit $(X, \leq)$ un poset et $x, y, z \in X$ un triplet d'éléments de X.

- $x, y, z$ forment un modèle en $\lor$ quand $z \leq x, z \leq y$ et ni $x \leq y$, ni $y \leq x$;

- $x, y, z$ forment un modèle en $\land$ quand $x \leq z, y \leq z$ et ni $x \leq z$, ni $y \leq x$.

Tous ces modèles sont représentés sur la Figure 5.

**Proposition 6.** Un ordre partiel $\leq$ sur un ensemble fini $X$ est un ordre linéaire partitionné ssi il n'y a aucun triplet $x, y, z \in X$ formant un modèle en $\lor$ ou un modèle en $\land$.

<footnote n="2">2. Les ordres bilinéaires correspondent au cas $n = 2$ des ordres n-linéaires, définis comme la catégorie obtenue par produit d'ordres de n ordres linéaires. Cette catégorie se trouve presque au plus bas de la hiérarchie, juste au-dessus de celle des ordres linéaires.</footnote>
<figure><img src="image_6.png" /><figcaption>FIGURE 6 – Diagramme d’inclusions propres des parties asymétriques de structures ordonnées proposées dans [15]. PO = ordre partiel ; IO = ordre d’intervalles ; SO = semi-ordre ; BO = ordre bilinéaire ; OLP = ordre linéaire partitionné ; WO = ordre fort ; et LO = ordre linéaire. R* étant la partie asymétrique de la relation R.</figcaption></figure>

Pour conclure cette section, la Figure 6 insère les ordres linéaires partitionnés au sein du diagramme d'inclusions propres des parties asymétriques de certains posets proposé dans [15]. Sur ce diagramme, les classes non connectées ne sont pas incluses l'une dans l'autre et parmi deux classes connectées, la plus basse est strictement incluse dans la plus haute.

## 5 Révision et OLP

Comme les OLP semblent être des structures plus réalistes que les ordres linéaires pour représenter la révision de croyances, nous proposons un jeu de postulats capturant la notion de *assignement fidèle* à un OLP.

### Exemple 6.

Considérons à nouveau l'exemple du médecin, la grippe (g) et la toux (t). En général, il peut ordonner la plausibilité de chaque situation de la façon suivante : {$\neg t \wedge \neg g$} $\le$ {$t \wedge g$} $\le$ {$t \wedge \neg g$} $\le$ {$\neg t \wedge g$}. En effet, il semble que le plus réaliste soit que les personnes sont en bonne santé, mais, si un patient tousse, alors il doit avoir la grippe. La situation la moins plausible est lorsque le patient a la grippe, mais ne tousse pas.

Si maintenant, nous considérons une nouvelle variable h, qui représente "c'est l'hiver", il peut être beaucoup plus simple pour le médecin de considérer deux ordres linéaires locaux dépendant du contexte h et $\neg h$ : {$\neg h, \neg t, \neg g$} $\le$1 {$\neg h, t, \neg g$} $\le$1 {$\neg h, t, g$} $\le$1 {$\neg h, \neg t, g$} et {$h, \neg t, \neg g$} $\le$2 {$h, t, g$} $\le$2 {$h, t, \neg g$} $\le$2 {$h, \neg t, g$}.

Le premier ordre linéaire exprime le fait que, lorsque ce n'est pas l'hiver, il est plus plausible pour un patient de tousser sans avoir la grippe (par exemple à cause des allergies), au contraire, quand c'est l'hiver, il est plus plausible pour qu'un patient tousse à cause de la grippe. L'union de

<figure><img src="image_7.png" /><figcaption>FIGURE 7 – Contre-exemple d'OLP pour ($\mathbf{R}_2$) et ($\mathbf{R}_6$).</figcaption></figure>

ces deux ordres conduit à un OLP.

Les structures OLP peuvent aussi se rencontrer dans la fusion de croyance [24, 23], en particulier en cas d'incommensurabilité des plausibilités fournies par les agents [7]. Ce problème est également intimement lié à celui des comparaisons interpersonnelles d'utilité [33, 8].

### 5.1 Un nouveau postulat de rationalité

Tout d'abord, nous pouvons remarquer que les postulats KM ne permettent pas de capturer la structure des OLP et ne pouvaient pas non plus être utilisés pour les opérateurs de révision totalement informatifs. Par exemple, considérons les croyances $\varphi$ d'un agent tel que $[[\varphi]] = \{\omega_1, \omega_5, \omega_6\}$ et l'opérateur de révision $\circ_{OLP}$ menant à l'OLP représenté sur la Figure 7. Considérons maintenant une nouvelle information $\alpha_1$ telle que $[[\alpha_1]] = \{\omega_0, \omega_4, \omega_5\}$. Si $\circ_{OLP}$ satisfait ($\mathbf{R}_2$), comme $[[\varphi \wedge \alpha]] = \{\omega_5\}$, le résultat, de la révision devrait être $[[\varphi \circ_{OLP} \alpha_1]] = \{\omega_5\}$, alors qu'il n'y a aucune raison de rejeter $\omega_0$ qui n'est plus dominée. De la même manière, un opérateur de révision OLP ne devrait pas satisfaire ($\mathbf{R}_6$), en considérant par exemple $\alpha_2$ tel que $[[\alpha_2]] = \{\omega_2, \omega_4, \omega_7\}$ et $\alpha_3$ tel que $[[\alpha_3]] = \{\omega_2, \omega_7\}$. Alors, $[[\varphi \circ_{OLP} (\alpha_2 \wedge \alpha_3)] = \{\omega_2, \omega_7\}$, alors que $[[\varphi \circ_{OLP} \alpha_2]] = \{\omega_2, \omega_4\}$ et $[[ (\varphi \circ_{OLP} \alpha_2) \wedge \alpha_3]] = \{\omega_2\}$.

Cette incompatibilité avec ($\mathbf{R}_2$) et ($\mathbf{R}_6$) n'est pas une surprise puisque les OLP sont des ordres partiels, ce qui permet des situations d'incomparabilité que les opérateurs KM ne capturent pas. De notre côté, nous nous plaçons dans le cadre de [6] auquel nous proposons d'ajouter le postulat ($\mathbf{R}_{OLP}$).

($\mathbf{R}_{OLP}$) Si $\alpha \wedge \beta \vdash \perp$ et $(\varphi \circ \alpha) \vee (\varphi \circ \beta) \vdash \varphi \circ (\alpha \vee \beta)$, alors pour tout formule complète $\gamma$, on a $(\varphi \circ \alpha) \vee (\varphi \circ \gamma) \vdash \varphi \circ (\alpha \vee \gamma)$ ou $(\varphi \circ \beta) \vee (\varphi \circ \gamma) \vdash \varphi \circ (\beta \vee \gamma)$

La pierre angulaire du postulat ($\mathbf{R}_{OLP}$) est la déduction $(\varphi \circ \alpha) \vee (\varphi \circ \beta) \vdash \varphi \circ (\alpha \vee \beta)$. Une fois ramenée aux structures ordonnées, cette déduction conduit à l'incomparabilité entre les deux éléments $\alpha$ et $\beta$ quand $\alpha$ et $\beta$ sont complets. C'est pourquoi, ($\mathbf{R}_{OLP}$) exprime le fait que pour tout triplet d'éléments où une paire est incomparable, il y a forcément au moins une autre paire incomparable. Imposer ($\mathbf{R}_{OLP}$) à une structure transitive est équivalent à exclure les modèles en $\vee$ et en $\wedge$.
Comme attendu, le théorème de représentation suivant montre qu’en ajoutant ($R_{OLP}$) aux postulats de la révision avec des ordres partiels (($R_1$), ($R'_2$), ($R_3$), ($R_4$), ($R_5$), ($R_7$), and ($R_8$)), il est possible de construire des opérateurs de révisions OLP.

**Théorème 4.** *Un opérateur de révision OLP ○ satisfait les postulats ($R_1$), ($R'_2$), ($R_3$)–($R_5$), ($R_7$), ($R_8$), ($R_{OLP}$) ssi il existe un p-assignement fidèle qui fait correspondre $\varphi$ et le OLP $\preceq_{\varphi}$ tel que :*

$$ \llbracket \varphi \circ \mu \rrbracket = \text{Min} (\llbracket \mu \rrbracket, \preceq_{\varphi}). $$

La prochaine section présente un exemple d'opérateur de révision OLP basé sur la distance de Hamming et sur les diagrammes de Voronoï non ambigu.

## 5.2 Un opérateur de révision OLP concret

Nous proposons un opérateur de révision OLP concret. Étant donné une formule $\varphi$, notre opérateur procède en 2 étapes pour construire un OLP. Pour cela, nous utilisons deux fonctions de départage différentes $\mathcal{T}_1$ et $\mathcal{T}_2$. En premier, nous construisons une partition de $\Omega$ autour des modèles de $\varphi$ en utilisant la distance de Hamming, où chaque interprétation est associée au modèle le plus proche. En cas d'égalité, $\mathcal{T}_1$ est utilisé. Cette partition en cellule peut être vue comme diagramme de Voronoï non ambigu. La deuxième étape consiste à ordonner totalement les interprétations au sein de chaque cellule en utilisant pour cela la distance au centre de chaque cellule, les égalités sont résolues par $\mathcal{T}_2$.

**Définition 6** (Diagramme de Voronoï non ambigu). Étant donné $\varphi$ tel que $\llbracket \varphi \rrbracket = \{\omega_1, ..., \omega_m\}$ et une fonction de tie-break $\mathcal{T}$, alors $\Delta_{\varphi}^{\mathcal{T}} = \{V_{\omega_1}, ..., V_{\omega_m}\}$ est une partition $\Omega$ telle que :

$$ \omega \in V_{\omega^*} \text{ ssi } \mathcal{T}(\text{Argmin}_{\omega' \in \llbracket \varphi \rrbracket} d_H(\omega', \omega)) = \omega^*. $$

Il peut être remarqué que cette partition peut être construite de façon équivalente en utilisant les opérateurs de dilatation [9].

**Définition 7** (Opérateur de révision de Voronoï non ambigu). Étant donné une formule $\varphi$, une nouvelle information $\alpha$ et deux fonctions de tie-break $\mathcal{T}_1$ et $\mathcal{T}_2$, nous définissons la relation binaire $\preceq_{\varphi}^{\mathcal{T}_1, \mathcal{T}_2}$ sur $\Omega$ par $\omega \preceq_{\varphi}^{\mathcal{T}_1, \mathcal{T}_2} \omega'$ lorsque $\{\omega, \omega'\} \subseteq V_{\omega^*}$ et soit $d_H(\omega^*, \omega) < d_H(\omega^*, \omega')$ soit $d_H(\omega^*, \omega) = d_H(\omega^*, \omega')$ et $\mathcal{T}_2(\{\omega, \omega'\}) = \omega$, où $V_{\omega^*} \in \Delta_{\varphi}^{\mathcal{T}_1}$ est une cellule du diagramme de Voronoï non ambigu de $\varphi$.

L'opérateur de révision ○$_V$ associé est défini par :

$$ \llbracket \varphi \circ_V \alpha \rrbracket = \text{Min}(\llbracket \alpha \rrbracket, \preceq_{\varphi}^{\mathcal{T}_1, \mathcal{T}_2}) $$

$\preceq_{\varphi}^{\mathcal{T}_1, \mathcal{T}_2}$ est un ordre linéaire partitionné où les classes de comparabilités sont les cellules du diagramme de Voronoï non ambigu $\Delta_{\varphi}^{\mathcal{T}_1} = \{V_{\omega_1}, ..., V_{\omega_m}\}$.

<figure><img src="image_8.png" /><figcaption>FIGURE 8 – Table de Karnaugh représentant le diagramme de Voronoï non ambigu de $\varphi$ de l'Exemple 7.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>FIGURE 9 – $\preceq_{\varphi}^{\mathcal{T}_1}$, le préordre partiel induit par la distance de Hamming aux modèles de $\varphi$ de l'Exemple 7 au sein des cellules de Voronoï non ambiguë de la Figure 8 et $\preceq_{\varphi}^{\mathcal{T}_1, \mathcal{T}_2}$, l'OLP obtenu après application du second tie-break avec $\llbracket \alpha \rrbracket$.</figcaption></figure>

L'exemple suivant permet d'illustrer ces définitions. Nous prenons $\mathcal{T}_1 = \mathcal{T}_2$, un simple ordre lexicographique sur les variables.

**Exemple 7.** Soit les croyances actuelles de notre agent $\varphi$ telles que $\llbracket \varphi \rrbracket = \{\omega_1, \omega_5, \omega_6\}$.

Comme fonctions de départage, nous prenons $\mathcal{T}_1$ et $\mathcal{T}_2$, l'ordre lexicographique sur les interprétations obtenu par l'ordre suivant sur les variables propositionnelles falsifiées : $a < b < c$.

La Figure 8 montre les cellules du diagramme de Voronoï non ambigu de $\varphi$ sur une table de Karnaugh <fnref n="3" /> où $V_{\omega_1}$ est en bleu et $V_{\omega_5}$ est en rouge et $V_{\omega_6}$ est en vert. Sur cette figure, nous pouvons voir que bien que $\omega_4$ et $\omega_7$ sont à une distance de Hamming de 1 avec à la fois $\omega_5$ et $\omega_6$, ils sont associés à $\omega_5$ via $\mathcal{T}_1$. Cette figure peut être représentée par le préordre partiel $\preceq_{\varphi}^{\mathcal{T}_1}$ disponible Figure 9(a).

Appliquée une nouvelle fois, la fonction de tie-break répondant les indifférences conduisant à l'OLP $\preceq_{\varphi}^{\mathcal{T}_1, \mathcal{T}_2}$ représenté sur la Figure 9(b).

Maintenant, supposons que notre agent soit confronté à la nouvelle information $\alpha = \neg c$, nous pouvons calculer $\varphi \circ \alpha$ en utilisant $\preceq_{\varphi}^{\mathcal{T}_1, \mathcal{T}_2}$. Nous avons alors $\llbracket \varphi \circ \alpha \rrbracket = \text{Min}(\llbracket \alpha \rrbracket, \preceq_{\varphi}) = \{\omega_0, \omega_6, \omega_4\}$ comme le montre la Figure 9(b).

Comme attendu, la proposition suivante dit que ○$_V$ est un opérateur de révision OLP.

**Proposition 7.** L'opérateur de révision ○$_V$ satisfait ($R_1$), ($R'_2$), ($R_3$)–($R_5$), ($R_7$), ($R_8$), et ($R_{OLP}$).

<footnote n="3">3. En utilisant une table de Karnaugh, les cellules directement voisines sont à une distance de Hamming de 1.</footnote>
<table><caption>TABLE 2 – Un bref panorama des théorèmes de représentation de la littérature.</caption><thead><tr><td>Référence</td><td>Structure ordonnée</td></tr></thead><tbody><tr><td>[21]</td><td>préordre total</td></tr><tr><td>[21]</td><td>min-préordre partiel</td></tr><tr><td>[6]</td><td>préordre partiel</td></tr><tr><td>[29]</td><td>min-semi-ordre</td></tr><tr><td>[26]</td><td>semi-ordre</td></tr><tr><td>ici</td><td>ordre linéaire</td></tr><tr><td>ici</td><td>ordre linéaire partitionné</td></tr></tbody></table>

À première vue, notre opérateur peut être confondu avec un opérateur de mise à jour [22, 20], comme l'opérateur PMA [35] très connu. Dans les deux cas, une famille d'ordres est définie, chacun d'entre eux étant issu d'un modèle de la croyance initial $\varphi$. La différence la plus importante est que chaque ordre que nous produisons n'est pas sur l'ensemble des interprétations $\Omega$ mais seulement sur les éléments d'une partition. Une autre différence est que nous obtenons uniquement des comparabilités strictes. Cependant, une étude plus approfondie sur les liens entre la mise à jour et les opérateurs OLP doit être réalisée.

## 6 Discussion en rapport avec d'autres travaux

Les structures ordonnées jouent un rôle central dans la révision de croyance, à la fois dans sa version classique [1, 17] mais aussi dans sa version itérée [14]. Au moyen de théorèmes de représentation, ils offrent une meilleure compréhension des postulats de rationalité et confèrent une sémantique aux opérateurs de révisions. La Table 2 résume et situe notre contribution dans le paysage de la révision de croyance. Elle complète celle proposée dans [26]. Tous les articles mentionnés comme références dans la colonne de gauche donnent les théorèmes de représentations conduisant aux structures ordonnées données dans la colonne de droite.

Tout d'abord, nous présentons à nouveau la famille des opérateurs KM qui couvrent les opérateurs de révision pouvant être traduits par des préordre totaux. Un opérateur de révision totalement informatif quelconque est beaucoup plus spécifique qu'un opérateur de KM quelconque puisqu'il retourne toujours une formule complète. Les opérateurs de révision OLP sont significativement moins spécifiques puisqu'ils ne traitent que des situations localement totalement informées et de fait réintroduisent de l'incomparabilité.

Une première famille manipulant l'incomparabilité est celle proposée dans [21] obtenue en remplaçant ($R_6$) par ($R_7$) et ($R_8$). Cette famille a été créée pour gérer un type spécifique d'informations partiellement ordonnées où les modèles des croyances actuelles sont préférés à toutes les autres interprétations. Afin de capturer l'ensemble des ordres par-

tiels, même ceux ne disposant pas de minima globaux, il a été introduit dans [6] une nouvelle famille d'opérateur, déjà présentée dans la Section 2. Les opérateurs de révisions OLP sont une sous-classe de cette deuxième famille d'opérateurs de révision.

Une famille d'opérateur de révision pouvant être représentée par des semi-ordres avec des minima globaux a été proposée dans [29]. Pour ce faire, ils remplacent ($R_6$) par ($R_8$), ($R_9$) et ($R_{10}$).

($R_9$) Si $(\varphi \circ \alpha) \wedge \beta \vdash \varphi \circ \beta$ alors $(\varphi \circ \beta) \wedge \alpha \vdash \varphi \circ \alpha$

($R_{10}$) Si $(\varphi \circ \alpha) \wedge \beta \vdash \bot$ et $(\varphi \circ \alpha) \wedge \gamma \vdash \bot$ alors $(\varphi \wedge \gamma) \wedge (\alpha \wedge \beta) \vdash \varphi \circ (\alpha \wedge \beta)$

Les semi-ordres sont un type de structure ordonnée très connu dans le monde de l'économie pour être plus précautionneux vis-à-vis de l'indifférence. Cette structure a la capacité de rendre l'indifférence non transitive, ce qui est analogue avec l'exemple classique du sucre dans le café de [27]. Dans le but de pouvoir manipuler l'ensemble des semi-ordres, une autre famille d'opérateurs basés sur ceux de [29] mais en remplaçant ($R_2$) par ($R'_2$) a été proposée dans [26]. Aucune de ces familles ne peut gérer les situations localement totalement informées, cela peut se voir facilement via les modèles interdits des structures qu'elles représentent.

Notre famille d'opérateurs totalement informatifs permet à un agent de raffiner leur jugement entre les modèles qu'il ne pouvait pas distinguer avant de recevoir de nouvelles informations. Nous parvenons à ce résultat en affaiblissant ($R_2$) en ($R_{2w}$). Cette idée d'affaiblir ($R_2$) de plusieurs manières a été étudiée en détail dans [19] au côté de l'étude du comportement de ce type d'opérateurs lorsqu'ils sont confrontés à la même information de façon répétée, conduisant au développement d'une notion de stabilité.

## 7 Conclusion et perspectives

Nous définissons dans cet article la notion d'opérateur totalement informatif (TI) et apportons un nouveau postulat ($R_L$). Nous proposons un jeu de postulats basé sur ceux de KM (à l'exception d'un affaiblissement de ($R_2$)) ainsi qu'un théorème de représentation conduisant aux ordres linéaires. Dans ce contexte, ($R_L$) s'avère être équivalent à (TI). Nous donnons un exemple d'opérateur totalement informatif, basé sur l'opérateur de Dalal couplé à une fonction de départage. Nous proposons une nouvelle structure, plus générale que les ordres linéaires, les ordres linéaires partitionnés OLP, dont nous étudions les propriétés en termes d'expressivité, de représentations graphiques et numériques, et de modèles interdits. Nous positionnons les OLP dans une constellation de structures ordonnées. Cette structure ne peut pas être capturée par les ordres d'intervalles ni par les ordres forts. Ensuite, nous proposons un nouveau postulat ($R_{OLP}$), qui, couplé aux postulats de la révision partiellement ordonnée, conduit au théorème de
représentation capturant les OLP. Enfin, nous apportons un
opérateur satisfaisant tous ces postulats.

Ces résultats ouvrent nombre de nouvelles perspectives. D'emblée, il semble intuitif de les appliquer à la révision de croyances itérée [14]. En particulier, une question intéressante est de savoir comment rester dans le même fragment de structures ordonnées tout au long du processus itéré. Il semble aussi naturel d'étudier les ordres forts partitionnés, qui constituent une généralisation directe des OLP. La création d'opérateurs utiles en pratique constitue une autre de ces questions. Ceux proposés dans cet article ont été réalisés avec un objectif d'illustration et afin de prouver la consistance de nos ensembles de postulats. La complexité computationnelle de ces opérateurs de révision reste une question théorique et pratique ouverte et les OLP sont de potentiels candidats pour efficacement représenter des modèles non représentables par des préordres totaux ou des ordres d'intervalle. Comme mentionné précédemment, nos travaux sont reliés à la fusion de croyances et partage des similitudes avec la mise à jour. Il pourrait aussi être intéressant de se pencher sur ces autres facettes de la dynamique de croyances et il en va de même concernant le raisonnement non monotone [25].

Références

[1] Alchourrón, Carlos E., Peter Gärdenfors et David Ma-
kinson: *On the Logic of Theory Change : Partial Meet
Functions for Contraction and Revision*. Journal of
Symbolic Logic, 50 :510–530, 1985.

[2] Andrèka, Hajnal, Mark Ryan et Pierre Yves Schobbens: *Operators and Laws for Combining Preference Relations*. Journal of Logic and Computation, 12(1):13–53, 2002.

[3] Arrow, K. J. et L. Hurwicz: *An optimality criterion for decision-making under ignorance*. Uncertainty and Expectations in Economics, 1979.

[4] Belahcène, Khaled, Vincent Mousseau, Wassila Ouerdane, Marc Pirlot et Olivier Sobrie: *Multiple criteria sorting models and methods—Part I : survey of the literature*. 4OR, pages 1–46, 2023.

[5] Benferhat, Salem, Sébastien Konieczny, Odile Papini et Ramón A. Pino Pérez: *Iterated Revision by Epistemic States : Axioms, Semantics and Syntax*. Dans *Proceedings of European Conference on Artificial Intelligence (ECAI’2000)*, pages 13–17, 2000.

[6] Benferhat, Salem, Sylvain Lagrue et Odile Papini: *Revision of Partially Ordered Information : Axiomatization, Semantics and Iteration*. Dans *Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’05)*, pages 376–381, 2005.

[7] Benferhat, Salem, Sylvain Lagrue et Julien Rossit: *Max-based Prioritized Information Fusion without Commensurability*. Journal of Logic and Computation, 19(6):1577–1610, 2009.

[8] Binmore, Kenneth G.: *Interpersonal Comparison of Utility*. Oxford Handbook of Philosophy of Economic Science, page 200–254, 2007.

[9] Bloch, Isabelle, Jérôme Lang, Ramón Pino Pérez et Carlos Uzcátegui: *Morphologic for knowledge dynamics : revision, fusion, abduction*. CoRR, abs/1802.05142, 2018. http://arxiv.org/abs/1802.05142.

[10] Bouyssou, Denis et Thierry Marchant: *An axiomatic approach to noncompensatory sorting methods in MCDM, I : The case of two categories*. European Journal of Operational Research, 178(1):217–245, 2007.

[11] Bouyssou, Denis et Thierry Marchant: *An axiomatic approach to noncompensatory sorting methods in MCDM, II : More than two categories*. European Journal of Operational Research, 178(1):246–276, 2007.

[12] Bubboloni, Daniela et Michele Gori: *Breaking ties in collective decision-making*. Decisions in Economics and Finance, 44:411–457, 2021.

[13] Dalal, Mukesh: *Investigations into a Theory of Knowledge Base Revision*. Dans *Proceedings of the 7th National Conference on Artificial Intelligence (AAAI’88)*, pages 475–479, 1988.

[14] Darwiche, Adnan et Judea Pearl: *On the logic of iterated belief revision*. Artificial intelligence, 89:1–29, 1997.

[15] Fishburn, Peter C.: *Generalizations of Semiorders : A Review Note*. Journal of Mathematical Psychology, 41(4):357–366, 1997, ISSN 0022-2496.

[16] Freeman, Rupert, Markus Brill et Vincent Conitzer: *General Tiebreaking Schemes for Computational Social Choice*. Dans *Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015*, pages 1401–1409, 2015.

[17] Gärdenfors, Peter: *Knowledge in flux : modeling the dynamics of epistemic states*. Bradford Books. MIT Press, Cambridge, 1988.

[18] Gärdenfors, Peter (rédacteur): *Belief Revision*. Cambridge University Press, 1992.

[19] Haret, Adrian et Stefan Woltran: *Belief Revision Operators with Varying Attitudes Towards Initial Beliefs*. Dans *Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI’19)*, pages 1726–1733, 2019.

[20] Herzig, Andreas et Omar Rifi: *Propositional belief base update and minimal change*. Artificial Intelligence, 115(1), 1998.
[21] Katsuno, Hirofumi et Alberto O. Mendelzon: *Propositional Knowledge Base Revision and Minimal Change*. Artificial Intelligence, 52(3):263-294, 1991.

[22] Katsuno, Hirofumi et Alberto O. Mendelzon: *On the Difference between Updating a Knowledge Base and Revising it*. Dans [18], pages 183-203, 1992.

[23] Konieczny, Sébastien, Jérôme Lang et Pierre Marquis: *DA² Merging Operators*. Artificial Intelligence, 157(1-2):49-79, 2004.

[24] Konieczny, Sébastien et Ramón Pino Pérez: *Merging Information Under Constraints: a Logical Framework*. Journal of Logic and Computation, 12(5):773-808, 2002.

[25] Kraus, Sarit, Daniel Lehmann et Menachem Magidor: *Nonmonotonic reasoning, preferential models and cumulative logics*. Artificial Intelligence, 44:167-207, 1990.

[26] León, María Victoria et Ramon Pino Pérez: *Orders and Belief Revision*. Dans *Proceedings of the 19th International Workshop on Non-Monotonic Reasoning (NMR21)*, pages 11-20, 2021.

[27] Luce, R. Duncan: *Semiorders and a Theory of Utility Discrimination*. Econometrica, 24(2):178-191, 1956.

[28] Öztürk, Meltem, Marc Pirlot et Alexis Tsoukiàs: *Representing preferences using intervals*. Artificial Intelligence, 175(7-8):1194-1222, 2011.

[29] Peppas, Pavlos et Mary-Anne Williams: *Belief Change and Semiorders*. Dans *Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014*, 2014.

[30] Rolland, Antoine: *Reference-based preferences aggregation procedures in multi-criteria decision making*. Eur. J. Oper. Res., 225(3):479-486, 2013.

[31] Ryan, Mark: *Belief Revision and Ordered Theory Presentations*. Logic, Action, and Information, page 129-151, 1996.

[32] Sen, Amartya K: *Choice functions and revealed preference*. The Review of Economic Studies, 38(3):307-317, 1971.

[33] Sen, Amartya K.: *Handbook of Mathematical Economics*, tome 3. North-Holland, 1982.

[34] Smets, Philippe: *Decision making in the TBM: the necessity of the pignistic transformation*. International journal of approximate reasoning, 38(2):133-147, 2005.

[35] Winslett, M: *Reasoning about action using a possible models approach*. Dans *Proceedings of the 7th National Conference on Artificial Intelligence (AAAI'88)*, pages 89-93, 1988.