Choix Social et Délibération - staff.science.uva.nl

Choix Social et Délibération

Mémoire de fin d’étude

Master Sciences et Technologies,Mention Informatique,

Parcours MIT

AuteurArthur Boixel

SuperviseursPierre Bisquert - CR INRA IATEMadalina Croitoru - MCF IUT Montpellier

Lieu de stageLIRMM UM5506 - CNRS, Université de Montpellier

soutenu publiquement le 26 juin 2018

Résumé

La théorie du choix social nous permet d’étudier la façon dont l’agrégation depréférences individuelles peut donner lieu à l’expression d’une préférence collective.Cela nous amène indirectement à réfléchir au sens que nous donnons à l’idée dedémocratie. Malheureusement la théorie du choix social est parsemée de résultatsd’impossibilité empêchant la construction de méthodes d’agrégation de préférencessimples et satisfaisantes au sens de la démocratie.

Nous avons tâché pendant ce stage de master de combiner des outils et résultatsisssus de divers domaines (théorie du choix social, délibération, représentation desconnaissances) dans le but de mettre au point un protocole de délibération permet-tant de contourner un certain résultat d’impossibilité concernant la construction deméthodes de vote démocratiques.

Ce rapport présente les contributions apportées au domaine ainsi que les résul-tats formels et expérimentaux obtenus durant ce stage.

Abstract

Social choice theory allows to study the way in which the aggregation of indi-vidual preferences can lead to the expression of a collective preference. It indirectlyleads to ponder on the meaning we give to the idea of democracy. Unfortunately,the theory of social choice is stained with impossibility results preventing the con-struction of simple and satisfactory preference aggregation methods.

In this thesis we have tried to combine tools and results from various fields(social choice theory, deliberation, knowledge representation) in order to developa deliberation protocol to circumvent a certain impossibility result concerning thedesign of democratic voting methods.

This report presents the contributions made to the field as well as the formaland experimental results obtained during this internship.

Table des matières

Introduction 1

1 Contexte 51.1 Agents et préférences personnelles . . . . . . . . . . . . . . . . . . . . . . 51.2 Problème de démocratie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Échappatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Contribution - Protocole de délibération 152.1 Préférences basées sur des propriétés . . . . . . . . . . . . . . . . . . . . . 152.2 Protocole de délibération à deux phases : une vue d’ensemble . . . . . . . 182.3 Formalisation du protocole . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4 Restructuration des préférences . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Résultats 353.1 Notions de proximité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2 Approche théorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.3 Expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Conclusion 47

A Annexes - Définitions formelles 49A.1 Choix social . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49A.2 Protocole de délibération . . . . . . . . . . . . . . . . . . . . . . . . . . . 53A.3 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

B Annexes - Expérimentations supplémentaires 59B.1 Évolution proximité à la single cavedness . . . . . . . . . . . . . . . . . . 59

Bibliographie 61

Introduction

La théorie du choix social vise à étudier comment l’agrégation de préférences indi-viduelles peut mener à l’expression d’une préférence collective.

Depuis l’énoncé du paradoxe de Condorcet [10] en 1785 par Nicolas de Condorcetla théorie du choix social a connu de nombreux développements. Les travaux d’Arrowet notamment son théorème d’impossibilité [4] formulé en 1951 posent les bases de lathéorie moderne du choix social.

Le problème sous-jacent à la théorie du choix social peut s’exprimer simplement.

Étant donné un ensemble d’agents possédant chacun des préférences propres surun ensemble d’alternatives, comment combiner ces préférences individuelles en unepréférence collective satisfaisante, c’est-à-dire qui représente la volonté des agents etainsi désigner l’alternative préférée par le groupe ?

Cette question soulève rapidement de nombreux problèmes concernant la façon dontsont agrégées les préférences. Une première observation étant que pour un ensemble depréférences individuelles donné, la préférence collective inférée peut être différente selonla méthode d’agrégation choisie. Afin de nous en rendre compte, considérons un premierexemple1.

Exemple 1 [ Un fil rouge ]

Imaginons qu’un ensemble de huit amis doivent décider du lieu où aller manger. Ils ontle choix entre les alternatives fastfood, chinois, italien. Les préférences individuellessont les suivantes :

1Emprunté (et modifié) aux cours d’Ulle Endriss : https://staff.science.uva.nl/u.endriss/teaching/comsoc/2017/.

1

https://staff.science.uva.nl/u.endriss/teaching/comsoc/2017/

https://staff.science.uva.nl/u.endriss/teaching/comsoc/2017/

2 TABLE DES MATIÈRES

# amis Préférences2 Fastfood Chinois Italien3 Chinois Italien Fastfood3 Italien Fastfood Chinois

Tâchons maintenant d’extraire une préférence collective de ces données en utilisant desméthodes d’agrégation de préférences différentes1 :

Méthode Vainqueur(s)Pluralité à un tour(scrutin le plus simple)

Chinois∼Italien(ex æquo)

Pluralité à deux tours(scrutin utilisé lors des élections françaises) Chinois

Condorcet(comparaison deux à deux des alternatives) ∅

de Borda(sommation des rangs attribués aux alternatives) Italien

Le résultat est clair, changez le mode de scrutin et le vainqueur de l’élection changera.On peut également remarquer que dans ce cas, la méthode de Condorcet ne permet pasde désigner un vainqueur, ce qui est différent de classer certaines alternatives ex æquo ;nous verrons en section 1.2.1 l’explication sous-jacente. Face à cette observation, ré-pondre à la question de l’agrégation de préférences peut finalement revenir à se poserdes questions sur la nature et l’existence même d’une préférence collective. Une remarqueque l’on peut faire pour répondre à ce problème est que a priori on ne souhaite utiliserlors d’un scrutin que des méthodes d’agrégation de préférences que l’on jugera « démo-cratiques ».

Dans son livre Social Choice and Individual Values [5], Arrow définit un ensemble dequatre propriétés désirables que doit vérifier une méthode de vote pour être considéréecomme démocratique. Nous aurons évidemment l’occasion de revenir sur ces propriétésplus en détail dans la section 1.2.1. Malheureusement, le résultat suivant la définitionde ces propriétés est un résultat d’impossibilité. Il s’agit du théorème d’impossibilitéd’Arrow [5] énonçant qu’aucune méthode de vote ordinale2 ne peut (sous des conditionsque nous verrons en section 1.2.1) vérifier toutes ces propriétés démocratiques à la fois.

Parmi les méthodes de vote étudiées, celle de Condorcet sur laquelle nous reviendronsdans la section 1.2.1 semble pourtant être une bonne façon d’agréger des préférences col-lectives. En effet, elle vérifie les quatre propriétés désirables. Cependant, dans certains cas

1Nous ne définissons pas formellement les méthodes utilisées ici. La pluralité à un et deux tours estla méthode de vote la plus connue, nous parlerons de la méthode de Condorcet en section 1.2.1. Enfin laméthode de Borda généralise les méthodes de pluralité en utilisant l’ensemble des préférences exprimées.

2On ne s’intéressera pas durant ce stage aux approches cardinales d’agrégation de préférences.

TABLE DES MATIÈRES 3

(notamment celui formalisé au sein du Paradoxe de Condorcet ou encore dans l’exempleprécédent), elle est incapable de donner un résultat. La méthode de Condorcet ne peutdonc pas être formellement qualifiée de méthode de vote.

On peut chercher à contourner ce problème en identifiant des conditions nécessairesou suffisantes portant sur les préférences individuelles permettant d’assurer une agréga-tion démocratique de celles-ci. De nombreuses pistes, aussi bien théoriques qu’expéri-mentales ont été étudiées.

En 2012, List et al. [20] propose une approche basée sur la délibération qui pourraitpermettre à des agents de restructurer leur préférences dans le but de contourner ceproblème. Dans cette expérience, après délibération, les préférences des agents sont plusproches (pour une certaine métrique) des conditions évoquées précédemment. C’est cetteapproche que nous suivrons.

Nous commencerons cette étude en rappelant au Chapitre 1 le contexte théoriquedans lequel nous nous placerons. Nous répondrons ensuite à la question de recherchesuivante.

Est-il possible de définir de façon formelle, un protocole de délibération permet-tant de vérifier, théoriquement ou expérimentalement, les résultats pratiques obtenuspar List et al. dans [20] ?

La réponse à cette question sera apportée par trois contributions. Tout d’abord,une formalisation d’un tel protocole sera donnée au Chapitre 2. Puis, nous étudieronsau Chapitre 3 les garanties d’efficacité qu’il est possible d’obtenir pour ce protocole.Premièrement des garanties théoriques en Section 3.2 qui nous permettrons en Section 3.3de prouver expérimentalement la validité de notre protocole.

1

Contexte

Afin de pouvoir discuter correctement du problème posé dans l’introduction, il estnécessaire de s’approprier quelques notions de choix social. Nous tenterons donc de définirle cadre formel dans lequel nous nous placerons tout au long de notre travail.

1.1 Agents et préférences personnelles

Tout problème de choix social fait intervenir un ensemble d’agents (électeurs, grouped’amis, etc.) qui devront se prononcer sur un ensemble d’alternatives (candidats,films, etc.). On récupère des agents un ensemble de préférences individuelles sur lesalternatives. Nous les définissons en utilisant une relation de préférence qui indiquerapour chaque agent et chaque paire d’alternatives, laquelle est préférée par celui-ci. Onsuppose cette relation réflexive, antisymétrique et transitive ce qui fait d’elle une relationd’ordre. De plus, nous considérerons ici qu’elle est totale1. L’ensemble des préférencesd’un agent i produit ainsi un ordre total sur l’ensemble des alternatives.

L’ensemble des préférences individuelles seront rassemblées au sein d’un profil depréférences regroupant l’ensemble des ordres totaux exprimés par les agents.

Afin de clarifier les choses nous pouvons reprendre l’exemple donné en introduction.

Exemple 1.1 [ Expression de préférences individuelles ]

Dans le groupe d’amis, un ensemble N de trois agents décident de discuter deleur côté. Définissons formellement l’ensemble N des trois agents impliqués : N =Arthur,Madalina, P ierre. Ces agents doivent décider où aller manger parmi unensemble X de quatre alternatives : X = fastfood, chinois, italien, nul − part.Considérons par exemple la relation de préférence Madalina. On a :

Madalina: (italien Madalina nul − part Madalina fastfood Madalina chinois)

1D’autres travaux s’intéressent à des préférences donnant des ordres partiels. Nous ne considéreronspas ce cas ici.

5

6 CHAPITRE 1. CONTEXTE

qui indique que Madalina préfère manger italien plutot qu’autre chose. Les préférencesexprimées par Madalina forment un ordre total que nous rajouterons au profil de préfé-rences N considéré :

(italien Madalina nul − part Madalina fastfood Madalina chinois) ∈ N

1.2 Problème de démocratie

1.2.1 Fonctions de choix social et démocratie

C’est une fois les préférences des agents récupérées qu’un problème se pose. Commentmettre au point une « bonne méthode » d’agrégation de préférences ? Nous commence-rons par formaliser ce que nous qualifions de « méthode » grâce à la notion de fonctionde choix social. Une fonction de choix social est une fonction qui prend en entrée unprofil de préférences et qui donne en sortie un vainqueur (ou plusieurs) parmi les alter-natives. Dans la suite de nos travaux nous nous restreindrons à n’utiliser que le termeanglophone de social choice function ou SCF pour parler d’une fonction de choix social.

Une notion similaire est la fonction de bien-être social ; nous emploierons parla suite le terme anglophone de social welfare function ou SWF qui englobe mieux lesprincipes derrière cette notion. Une SWF donne à partir d’un profil de préférences, unordre total sur les alternatives. Cette notion nous permettra de nous intéresser dans leparagraphe suivant à des propriétés désirables en démocratie.

Propriétés désirables en démocratie Maintenant que nous avons connaissance dece qu’est une méthode d’agrégation de préférences se pose le problème de savoir si, pourune méthode donnée, cette dernière est une « bonne » méthode ou non. Comme vudans l’introduction on peut supposer qu’une bonne méthode de vote est une méthodedémocratique. Arrow propose en 1951 [5] quatre propriétés désirables que doit posséderune méthode de vote pour être qualifiée de démocratique.

Soit N un ensemble d’agents, X un ensemble d’alternatives et N un profil depréférences. Soit f une SWF. Elle sera considérée démocratique si elle vérifie les quatrepropriétés suivantes :

1. Universalité - f ne doit imposer aucune restriction sur les préférences des agents.Ainsi chaque agent doit être libre de donner les préférences qu’il souhaite.

2. Unanimité - Si tous les agents préfèrent une alternative x à une alternative yalors f doit préférer x à y.

3. Indépendance aux alternatives non pertinentes - Le classement final de deuxalternatives ne doit dépendre que de leur classement relatif et pas de leur positiondans la relation de préférence.

4. Absence de dictateur - Le classement final des alternatives ne peut être dictépar un individu particulier.

1.2. PROBLÈME DE DÉMOCRATIE 7

Condorcet Attardons-nous maintenant sur une méthode de vote particulière : la mé-thode de Condorcet ou pair-wise majority introduite par Condorcet [10]. Cette méthodese base sur une idée simple : si une alternative est préférée à toute autre en duel parune majorité d’agents alors elle doit être choisie. Il s’agit de l’alternative vainqueur deCondorcet.

Étant donné un profil de préférences il n’existe par forcément un vainqueur deCondorcet. En effet il peut y avoir des incohérences dans le classement des alterna-tives qui nous empêche d’élire un vainqueur2. Dans ces cas-là on peut faire appel à unerègle de vote différente pour classer les alternatives.

Étant donnée cette définition, une méthode respectant le critère de Condorcet est uneméthode d’agrégation de préférences qui classe le vainqueur de Condorcet (s’il existe)devant toute les autres alternatives.

Dans Social Choice and Individual Values [5] Arrow montre que la pair-wise majorityvérifie les quatre propriétés désirables de la démocratie. Cependant il existe des cas pourlesquels elle ne vérifie pas la transitivité et ne fournit donc pas un ordre total sur lesalternatives. Cette dernière est alors incapable de désigner un vainqueur. Condorcet lui-même a le premier identifié de tels cas. De ce problème résulte le paradoxe de Condorcet.

Exemple 1.2 [ Paradoxe de Condorcet - The voting paradox ]

Soit X = a, b, c un ensemble de trois alternatives. Soit N = 1, 2, 3 un ensemblede trois agents ayant les préférences suivantes sur X :

Agent Préférences1 a 1 b 1 c

2 b 2 c 2 a

3 c 3 a 3 b

Aucune alternative ne bat les deux autres en duel. En effet, a est socialement préféréà b car une majorité d’agents (deux sur les trois) préfère a à b. Mais c est socialementpréféré à a car une majorité d’agents (deux sur les trois également) préfère c à a.L’alternative a ne gagne donc pas tous ses duels et n’est donc pas un vainqueur deCondorcet. Il est possible de voir, en répétant la même procédure, qu’aucune alternativen’est ici vainqueur de Condorcet. La méthode de Condorcet donnera alors un résultatnon transitif et donc non satisfaisant : a b c a.

La méthode de Condorcet, bien que vérifiant les propriétés nécessaires pour êtrequalifiée de démocratique, n’est en réalité pas une SWF au sens d’Arrow. Mais qu’enest-il des autres méthodes de vote ?

2Nous verrons par la suite que dans certains cas, le classement n’est pas « bien formé ».


1.2.2 Un résultat d’impossibilité : le théorème d’Arrow

En 1951 toujours dans Social Choice and Individual Values [5], Arrow énonce unrésultat général d’impossibilité. Durant ce stage c’est ce résultat fondamental que nousallons chercher à contourner.Théorème 1.1 [ Théorème d’impossibilité d’Arrow [1951] ]

S’il y a au moins deux agents et trois alternatives, alors il n’existe pas de SWFsatisfaisant les quatre propriétés de la démocratie.

C’est un résultat fort qui empêche la construction d’une « bonne » méthode de vote.Pour pallier ce problème, une première idée est d’affaiblir certaines contraintes sur laSWF considérée. Prenons quelques exemples.

• Universalité - Nous reviendrons plus tard sur cette condition, mais restreindreles préférences des agents permet de contourner ce théorème.

• Transitivité - On peut affaiblir cette condition en ne recherchant par exempleque l’absence de cycles [8], ou s’intéresser à la quasi-transitivité [24].

• Indépendance aux alternatives non pertinentes - On peut chercher à ex-plorer des conditions plus faibles : Relational Independent Decisiveness [11] parexemple.

1.3 Échappatoires

Intéressons-nous maintenant plus en détails à la propriété d’universalité. Affaiblircette condition a été une piste très étudiée pour contourner le théorème d’Arrow. Leprincipe est le suivant : imposer une restriction sur les préférences des agents afin defaire en sorte qu’elles vérifient certaines propriétés intéressantes. Nous allons dans cettesection faire un rapide tour d’horizon de ces différentes propriétés.

1.3.1 Structure des préférences

Single peakedness

Dans les années 1940, Duncan Black s’intéressa à la notion de préférences cycliques.C’est grâce à la notion de single peakedness qu’il trouva un moyen de contourner lethéorème d’Arrow. Cette notion est assez intuitive. Les préférences d’un agent sont singlepeaked par rapport à un ordre sur les alternatives s’il possède une alternative préféréeet que son intérêt pour les autres alternatives décroît à mesure que l’on s’éloigne deson alternative préférée en suivant l’ordre donné. Il s’agit d’une propriété facilementvisualisable sur de petits exemples.

1.3. ÉCHAPPATOIRES 9

Exemple 1.3 [ Single peakedness ]

Reprenons notre ensemble de trois agents N = Arthur,Madalina, P ierre ainsique l’ensemble de quatre alternative X = fastfood, chinois, italien, nul − part.Considérons les préférences de trois agents :

• Arthur : (nul − part Arthur chinois Arthur fastfood ∼Arthur italien)

• Madalina : (italien Madalina nul − part Madalina fastfood Madalina

chinois)

• Pierre : (fastfood P ierre chinois ∼P ierre italien P ierre nul − part)

Considérons également un ordre ≺ sur les alternatives, par exemple :(italien ≺ fastfood ≺ chinois ≺ nul − part) . Nous pouvons représen-ter toutes ces données graphiquement :

≺

Rang

ItalienFastfood

ChinoisNul-part

4

3

2

1 ← Arthur

←Madalina

← Pierre

Le tracé ci-dessus est une représentation de l’utilité accordée aux alternatives parchaque agent, on remarque que les courbes en noir qui représentent les préférences dePierre et Arthur ne possèdent qu’un seul pic, ces préférences sont donc single peakedsur cet ordre ≺. Ce n’est en revanche pas le cas pour les préférences de Madalina (repré-sentées en rouge). Nous pourrions nous convaincre en essayant d’autres ordres qu’aucunne permet d’obtenir trois courbes single peaked, le profil de préférences considéré n’estdonc pas single peaked.

On peut généraliser cette propriété et définir la notion de profil de préférencessingle peaked. Cette dernière permet à Black [7] de montrer le résultat suivant.


Théorème 1.2 [ The median voter theorem [1948] ]

Si chaque agent exprime ses vraies préférences et que celles-ci sont single peaked,alors la pair-wise majority retournera un résultat transitif et l’alternative préférée del’agent médian est un vainqueur de Condorcet.

Black montre donc que la single peakedness est une condition suffisante (mais nonnécessaire) à l’obtention d’un résultat transitif si l’on utilise la pair-wise majority. Ildonne en plus une caractérisation du vainqueur de Condorcet obtenu dans ce cas. Mal-heureusement si l’on souhaite l’utiliser alors on ne pourra construire qu’une SWF quine vérifiera pas l’universalité puisque le profil de préférences devra suivre une structureparticulière et qui donc ne sera pas démocratique. Enfin, espérer obtenir des préférencesvérifiant cette propriété est illusoire, en effet en pratique les préférences d’agents ne sontpas single peaked (voir [20] pour des exemples concrets).

Afin de pouvoir travailler sur de telles préférences on peut définir une notion deproximité à la single peakedness, Niemi [22] et List [19] introduisent une telle mesure quenous présenterons plus en détails au Chapitre 3. Une mesure de τsp = 1 indique qu’unensemble de préférences est single peaked et que l’on obtiendra un résultat transitif enutilisant la pair-wise majority sur ces préférences. Mais qu’en est-il pour τsp < 1 ? Nousavons vu que τsp = 1 n’est qu’une condition suffisante à la transitivité. L’obtention dela transitivité pourrait alors être envisageable pour un profil de préférences ayant uneproximité τsp < 1.

Cela nous amène au résultat suivant : la probabilité d’éviter les cycles augmentelorsque la proximité avec la single peakedness augmente [15][22]. Ce résultat se généra-lise aux mesures de proximité concernant les autres conditions suffisantes à l’obtentiond’un vainqueur de Condorcet. Nous tâcherons d’exploiter ce résultat durant ce stage.

Triple wise value restriction

En 1966 dans [25], Sen propose une condition suffisante portant sur les préférencesdes agents plus générale que la single peakedness qui permet d’obtenir un résultat tran-sitif lorsque l’on utilise la pair-wise majority. Il s’agit de la value restriction. L’idéeest la suivante : les préférences d’agents restreintes à un triplet d’alternatives sont valuerestricted s’il existe une alternative qui n’est jamais classée première ou qui n’est jamaisclassée deuxième ou qui n’est jamais classée dernière. Les préférences de l’agent vérifientcette propriété si elles sont value restricted pour chaque triplet d’alternatives. Cette no-tion se généralise là encore pour définir un profil de préférences value restricted.

Elle constitue une généralisation de la condition de single peakedness. Cette dernièrecorrespond au cas où pour trois alternatives, il en existe une qui n’est jamais classéedernière. Des spécialisations différentes de la value restriction existent, elles constituenttoutes des conditions suffisantes à l’obtention d’un résultat transitif (via pair-wise ma-jority). S’il existe une alternative qui n’est jamais classée première alors les préférencesdes agents sont dites single caved. Cette propriété avait été introduite plus tôt par Inada


[17]. Enfin dans le cas où une alternative n’est jamais classée deuxième, chaque sous-ensemble d’alternatives peut être séparé en deux groupes tels que les agents préfèrentsystématiquement une alternative du premier groupe à une du second groupe. C’est lacondition de separability into two groups également introduite par Inada [17].

La question est maintenant de savoir s’il est possible de mettre au point une méthodepermettant aux agents de restructurer leurs préférences de façon démocratique afin de lesrapprocher des propriétés présentées précédemment. Nous allons voir que la délibération,par le truchement d’un protocole rationnel et démocratique d’échange d’informations etde justifications, permet la création d’une telle méthode de restructuration.

1.3.2 Processus de délibération

La délibération est un des types de dialogues identifiés par Walton et Krabbe en 1995 [27].À la différence des dialogues de persuasion, ou encore de négociation, ce type de dialoguesurvient lorsqu’un ensemble d’agents cherchent à se mettre d’accord pour résoudre unproblème commun ne possédant pas de « bonne » solution. Dans ce cas-là, une solutiondoit être sélectionnée en fonction des buts et préférences des agents concernés.

Motivation expérimentale

La notion de délibération a récemment été étudiée par List et al. en 2012 [20]. Au traversd’une approche expérimentale, leurs travaux montrent que la délibération est une pisteintéressante pour la résolution de notre problème. Cette étude est la motivation expé-rimentale de notre sujet. L’expérience menée était la suivante : un échantillon d’agentssélectionnés aléatoirement donne pour une question posée (voir [20] pour les détails)leurs préférences sur différentes alternatives. Suite à cela leur sont remis des documentscontenant des informations équilibrées en faveur et contre les alternatives. Les agentssont ensuite invités à délibérer ensemble sur le sujet. À l’issue de cette phase de délibé-ration les agents doivent redonner leurs préférences sur les différentes alternatives.

Le résultat est le suivant : les préférences des agents sur les alternatives récupéréesaprès la phase de délibération sont en général plus proches3 de la single peakedness quecelles données avant la délibération. Cependant ce résultat n’est qu’expérimental, Listet al. ne proposent pas de protocole clair pour la délibération. Les agents se contententici de discussions informelles.

Approche théorique

Nous allons donc avoir besoin de formaliser cette notion de délibération. Commençonspar donner, au travers d’un exemple, un aperçu de ce que pourrait être un protocole dedélibération.

3Selon la métrique vue précdemment.


Exemple 1.4 [ Protocole de délibération ]

Tentons d’imagniner ce que pourrait être une discussion entre deux agents de notreexmeple fil rouge. Nous pourrons ainsi mieux appréhender ce qu’est un protocole dedélibération. Chaque agent impliqué dans la délibération possède un certain nombre« d’actes de langage » ou speech acts leur permettant de proposer des arguments, d’enattaquer, de faire des concessions, etc. Le résultat peut être représenté par un arbre.

(1) : proposer(manger gras)

(2) : pourquoi(manger gras)

(1) : argumenter(j’ai très faim ⇒ manger gras)

(2) : concéder(tu as très faim) (2) : rejeter(manger gras)

(1) : pourquoi− rejeter(manger gras)

(2) argumenter(manger gras ⇒ mauvais pour la santé)

(1) : argumenter(manger gras avec modération ⇒ non mauvais pour la santé)

Tout au long d’un protocole des délibération les agents peuvent faire avancer le débaten utilisant des speech act lors de différentes phases (proposition, révision, confirmation,etc.).

À partir des résultats obtenus après délibération nous pourrons être en mesure deraisonner sur les arguments utilisés par les agents, nous verrons ce qu’il en est au Cha-pitre 2. Afin de résoudre notre problème nous pourrons nous appuyer sur divers travauxthéoriques. Ces derniers proposent des cadres formels pour la mise en place de dialoguesde délibération. Nous allons en exposer deux qui présentent des approches différentes.Une première façon de mettre au point un protocole de délibération consiste à formaliserl’idée de speech act. La deuxième se base sur la théorie de l’argumentation et l’utilisationd’arguments.

En 2007, McBurney et al. [21] définissent un protocole de délibération en huit étapes.Lors de chaque étape les agents peuvent exprimer différents types de choses : proposi-tions, arguments, buts, faits, etc. Cet article se concentre sur la description des inter-actions que peuvent et ne peuvent pas avoir les agents. Ils montrent que leur protocolerespecte un grand nombre des règles introduites par Jürgen Habermas [16] ainsi queRobert Alexy [1] pour un discours éthique. Cependant certaines règles ne sont pas vé-rifiées. Il n’y ait notamment fait aucune supposition quant au fait qu’un agent soit ounon sincère.


Amgoud et al. proposent en 2008 [2] une autre approche. Il s’agit d’un système d’ar-gumentation particulier dans lequel différents types d’arguments sont considérés (épis-témiques et en faveur d’une option) ainsi qu’une relation d’attaque et une relation depréférences entre ces arguments. En une seule étape le modèle statue sur les alternativeset construit un pré-ordre total sur ces dernières. Tel quel, ce modèle pensé pour la prisede décision ne nous permet pas de contourner notre problème. En revanche il propose,tout comme les autres cadres formels existants ([26], [13], [18], etc.), des mécanismesintéressants qui pourront être utiles dans la suite de notre travail.

2

Contribution - Protocole de délibération

Au cours de ce chapitre nous présenterons la formalisation d’un protocole de déli-bération qui permettra aux agents de discuter formellement et de manière constructivede leurs préférences. Nous présenterons en premier lieu en section 2.1 le cadre formelnécessaire à l’établissement d’un tel protocole. Cela nous permettra d’expliciter plus pré-cisément les tenants et les aboutissants du protocole proposé. Dans cette optique nousdonnerons ensuite en section 2.2 une vue générale du protocole que nous tâcherons deformaliser en section 2.3. Enfin, nous verrons en Section 2.4 quels peuvent être les effetsde la délibération sur les préférences individuelles des agents. Un exemple fil rouge nouspermettra de mettre en application les notions présentées tout au long du chapitre.

2.1 Préférences basées sur des propriétésNous avons vu dans le chapitre précédent que chaque agent issu d’un groupe possède

des préférences individuelles sur un ensemble d’alternatives. Avant de chercher à lesagréger en une préférence collective, on peut se poser la question de leur origine. C’est àcette question que List et al. [12] apportent en 2013 une réponse intéressante. Selon leuridée, les préférences individuelles d’un agent sur un ensemble d’alternatives sont baséessur des préférences sur les propriétés possédées ou non par les alternatives. Intuitivement,un agent i préférera une alternative x à une alternative y, si x satisfait plus de propriétésdésirées par i que y.

Inspirés par ces travaux, nous ferons dans la suite de ce travail, l’hypothèse suivante.

Les préférences individuelles des agents sont basées sur des ensembles de pro-priétés désirables.

Exemple 2.1 [ Des critères aux propriétés ]

Plaçons-nous dans le cas où un ensemble N = Arthur,Madalina, P ierre detrois agents souhaitent choisir où aller déjeuner. Sans même évoquer les alternatives, ilexiste ici un ensemble infini de critères qui pourraient permettre aux agents de porter

15

16 CHAPITRE 2. CONTRIBUTION - PROTOCOLE DE DÉLIBÉRATION

un jugement sur les différentes alternatives. Considérons ici C une restriction finie decet ensemble. Prenons par exemple l’ensemble de critères C = prix, vitesse, teneur −gras, eco− responsabilité auquel nous pouvons associer PC l’ensemble des propriétésqui lui sont associé. Ici nous avons :

PC =cherprix,ncherprix ∪rapidevitesse,nrapidevitesse ∪grasteneur−gras,ngrasteneur−gras ∪ecoeco−res,necoeco−res

Étant donné un ensemble de critères et son ensemble de propriétés PC associées,chaque agent possède un ensemble de propriétés désirables. Cet agent préférerad’avantage les alternatives possédant ces propriétés.

On peut attribuer à chaque agent de l’exemple précédent un ensemble de propriétésdésirables.

Exemple 2.2 [ Propriétés désirables ]

Reprenons l’ensemble N = Arthur,Madalina, P ierre composé de trois agents.Étant donné l’ensemble de critères C et son ensemble de propriétés associées PC , lesagents possèdent leur propre ensemble de propriétés désirables inclus dans PC . Ces en-sembles sont donnés dans le tableau suivant.

Agent Propriétés désirablesArthur WArthur = ngrasteneur−gras,ncherprix, rapidevitesseMadalina WMadalina = ngrasteneur−gras, ecoeco−res, cherprixPierre WP ierre = grasteneur−gras, cherprix,nrapidevitesse,necoeco−res

Ici par exemple, inversement à Pierre, Arthur et Madalina favoriseront les alternativespossédant la propriété ngrasteneur−gras.

À partir des différents ensembles de propriétés désirables nous pouvons théorique-ment extraire les préférences individuelles de chaque agent sur un ensemble d’alterna-tives. Nous avons en effet fait l’hypothèse que celles-ci étaient basées sur ces propriétés.

Pour être en mesure de le faire nous devons associer à chaque agent un ensemble deconnaissances a priori sur les alternatives. Cela se traduit par l’association de chaquealternative à un ensemble de propriétés supposées possédées, et ce pour chaque agent.

Quel que soit i un agent de N et x une alternative de X, Six est inclus dans PC et

ne contient pas deux propriétés antagonistes relatives à un même critère c. Si tel étaitle cas, alors l’agent i ne sait pas si l’alternative x satisfait ou non le critère c et on peut

2.1. PRÉFÉRENCES BASÉES SUR DES PROPRIÉTÉS 17

retirer les deux propriétés antagonistes de Six.

Notons qu’en fonction des connaissances des agents, ces ensembles peuvent tout àfait avoir des cardinalités différentes. Reprenons l’exemple précédent afin d’évaluer lesdifférents niveaux de connaissance des agents.

Exemple 2.3 [ Des propriétés et des alternatives ]

Nous considérons toujours l’ensemble N = Arthur,Madalina, P ierrede trois agents. Soit X un ensemble de quatre alternatives, X =fastfood, chinois, italien, nul − part. Pour des raisons d’espace et de lisibi-lité mais aussi sous l’hypothèse que les agents sont rationnels, nous supposerons qu’ilsont les mêmes connaissances a priori sur les alternatives. Ainsi nous avons que, quelque soit x dans X, SArthur

x = SMadalinax = SP ierre

x , nous identifierons ces ensembles àl’ensemble SN

x . Ces connaissances a priori sont regroupées dans le tableau suivant.

Alternative Connaissances

fastfood SNfastfood = grasteneur−gras, rapidevitesse,necoeco−res, cherprix

chinois SNchinois = grasteneur−gras, rapidevitesse,necoeco−res,ncherprix

italien SNitalien = ngrasteneur−gras,nrapidevitesse, ecoeco−res, cherprix

nul − part SNnul−part = ngrasteneur−gras, rapidevitesse, ecoeco−res,ncherprix

Ces ensembles étant définis, on peut en extraire les préférences individuellesbasées sur les propriétés de chaque agent sur l’ensemble des alternatives. Un agentpréférera davantage une alternative possédant, selon lui, plus de ses propriétés désirablesà une alternative en possédant moins.

Dans le modèle de préférences que nous utilisons, nous supposons qu’un agent ne peutpas départager deux alternatives possédant la même quantité de propriétés désirables. Enrevanche, les travaux de List et al. [12] suggèrent que les agents possèdent des préférencessur leurs propriétés désirables, ces préférences étant dépendantes d’un certain contexte.Ils sont donc potentiellement capable de discriminer entre deux alternatives possédantle même nombre de propriétés désirables. Nous ferons ici l’hypothèse que ces préférencesse résument à des équivalences et ce quel que soit le contexte.

Complétons maintenant l’exemple précédent afin de comprendre comment lespropriétés influent sur les préférences individuelles.

Exemple 2.4 [ Des propriétés aux préférences ]

Les agents i de N = Arthur,Madalina, P ierre possèdent chacun un ensemblede propriétés désirables Wi. Ils possèdent également pour chaque alternative x de X,un ensemble Si

x de propriétés supposées possédées par x selon i. De ces ensembles nous


pouvons extraire les différentes préférences individuelles, elles sont regroupées dans letableau suivant.

Agent Relations de préférences

Arthur Arthur : nul − part Arthur chinois Arthur fastfood ∼Arthur italien

Madalina Madalina: italien Madalina nul − part Madalina fastfood Madalina chinois

P ierre P ierre : fastfood P ierre chinois ∼P ierre italien P ierre nul − part

Étant données ces préférences, nous pouvons tenter de les agréger en une préférencecollective en utilisant la pairwise majority. Le résultat obtenu peut être représenté via ungraphe des duels. Chaque sommet représente une alternative et un arc d’un sommet xvers un sommet y signifie que l’alternative x est préférée par une majorité à l’alternativey. Le graphe des duels associé à ces préférences est le suivant.

fastfood

chinois

italien

nul − part

Nous remarquons ici qu’il n’existe aucune alternative préférée à tout autre par unemajorité ; il n’existe pas de vainqueur de Condorcet et les préférences ne sont pas singlepeaked. Le but du protocole de délibération va donc être de modifier les propriétésstructurelles de ces préférences individuelles de façon à pouvoir éviter des cas commecelui-là.

Maintenant que le contexte formel est posé, nous donnerons, dans la section suivante,une vue d’ensemble du protocole mis en place et de ses objectifs. Nous verrons en quoicette notion de préférences basées sur des propriétés occupe une place importante dansnotre démarche et surtout nous tâcherons de comprendre de quelle façon elle pourraitnous permettre de résoudre notre problème général.

2.2 Protocole de délibération à deux phases : une vued’ensemble

L’idée générale du protocole est la suivante : permettre aux agents de restructurerleurs préférences sur un ensemble d’alternatives de manière à ce que celles-ci deviennentstructurellement plus intéressantes. Nous verrons ce qu’il en est au chapitre 3. Nous

2.2. PROTOCOLE DE DÉLIBÉRATION À DEUX PHASES : UNE VUED’ENSEMBLE 19

avons fait l’hypothèse dans la section précédente que les préférences individuelles sontbasées sur des ensembles de propriétés désirables ainsi que sur des connaissances a priorides agents sur les alternatives. Pour changer ses préférences, un agent devra donc faireévoluer son ensemble de propriétés désirables, mais également les connaissances qu’ilpossède sur chaque alternative.

La Figure 2.1 donne une vue générale du protocole proposé. Le protocole prend enentrée un ensemble N d’agents, chacun possédant des propriétés désirables ainsi quedes connaissances a priori sur un ensemble X d’alternatives. Le protocole se dérouleensuite en deux phases. Pour les agents, le but de la première phase est de construirecollectivement un ensemble P de propriétés désirables pour le groupe. Lors de la secondephase, l’objectif pour les agents sera d’harmoniser leurs connaissances sur les alternatives.À l’issue de ces deux phases, les agents seront en mesure de restructurer leurs préférencesindividuelles. Nous donnerons dans les deux sous-sections suivantes une vue générale desdeux phases du protocole. En complément, nous nous appuierons sur notre exemple filrouge introduit en section 2.1.

ENTRÉES

Wi : propriétés

désirables

Six : connaissances

⇒i : préférences

PHASE DEUX

Déliberation :

Uniformiser la

connaissance

SORTIE : ∀x ∈ X, Sx

PHASE UNE

Déliberation :

Choisir les

propriétés désirables

SORTIE : P

RESTRUCTURATION

W ′i : nouvelles

propriétés désirables

S′ix : nouvelles

connaissances sur x

SORTIE

∀i ∈ N

′i : nouvelles

préférences

Figure 2.1 – Vue d’ensemble - Protocole de délibération


2.2.1 Première phase

La première phase permet aux agents de faire évoluer les ensembles de propriétés qu’ilsconsidèrent comme désirables. Pour ce faire, les agents vont délibérer dans le but de semettre d’accord sur un ensemble commun que l’on notera P de propriétés désirables. Lespropriétés s’y trouvant seront considérées comme importantes par l’ensemble du groupe.Au cours de la délibération, le but pour un agent est alors que le reste du groupe accepteses propres propriétés désirables. Dans cette optique, les agents vont être amener, parcequ’on les considèrent rationnels et coopératifs, à avancer des arguments afin de justifierleurs positions. Chaque agent a également la possibilité de réagir aux autres arguments,de les accepter, de les rejeter, ou encore de les remettre en question. Nous verrons ensection 2.3 les spécificités techniques nécessaires à la réalisation de telles actions.

De façon à assurer un débat égalitaire, les agents seront invités à s’exprimer l’unaprès l’autre (round robin manner). Ils peuvent également, s’ils le souhaitent, passerleur tour. Les phases de délibération se terminent si tous les agents passent successi-vement leur tour. Autrement dit, la délibération s’arrête lorsque plus aucun agent nesouhaite intervenir.Afin de voir les différentes actions qu’un agent pourrait être amené à faire lors de ladélibération, nous pouvons prendre un exemple semi-formel.

Exemple 2.5 [ Première phase de délibération ]

Reprenons notre exemple fil rouge. Les agents de N =Arthur,Madalina, P ierre sont invités à délibérer dans le but de se mettred’accord sur un ensemble P de propriétés désirables. Chaque agent i, au moyen dedifférentes actions essayera de convaincre les autres que ses propriétés désirables (cellesde Wi) sont également désirables pour l’ensemble du groupe. Nous présenterons ici unevue générale de cette première phase au travers d’un extrait semi-formel de délibération.Chaque agent, exprimera, grâce à une action bien précise, une position, un doute, etc.Un tel extrait est donné dans le tableau 2.1.

Étant donné ce dialogue, nous verrons en section 2.3, comment le formaliserafin d’en extraire l’ensemble de propriétés désirables P construit par le groupe. Ici parexemple, on peut supposer que les agents sont d’accord pour considérer les propriétésrapidevitesse et grasteneur−gras comme désirable. En revanche, ils n’ont pas réussi à semettre d’accord sur le critère prix.


Table 2.1 – Exemple semi-formel de délibération. Extrait de la première phase.

# Réponse à Agent Action

1 − Arthur affirmer(J’ai une réunion bientôt, je veuxmanger rapidement.)

2 1 Pierre défier(Peux-tu prouver que tu as cetteréunion ?)

3 2 Arthur affirmer(Ce document le prouve.)

4 3 Pierre accepter(Très bien, nous devrions mangerrapidement.)

5 1 Madalina accepter(Je suis d’accord.)

6 − Madalina affirmer(Un prix élevé est synonyme dequalité, nous devrions choisir un restaurantcher.)

7 6 Arthur rejeter(Tu te trompes, manger au fastfoodest cher mais peu qualitatif .)

8 7 Madalina retirer(Oui en effet, j’avais tort.)

9 − Pierre affirmer(Je veux me remplir la panse, chois-sissons un endroit où l’on mange plutôt gras.)

10 9 Arthur accepter(Si tu veux, le gras c’est la vie.)

11 9 Madalina accepter(Très bien mais je prendrai quelquechose de léger.).


2.2.2 Seconde phase

À l’issue de la première phase, les agents se sont mis d’accord sur un ensemble P depropriétés désirables pour le groupe. Étant donné cet ensemble, on peut construire Cinclus dans C, l’ensemble des critères associés aux propriétés désirables P choisies parle groupe. Afin d’être en mesure de restructurer leurs préférences, ils doivent égalementaméliorer leurs connaissances sur les alternatives. C’est le but de cette seconde phase.Idéalement, tous les agents devraient avoir les mêmes connaissances sur les alternativesafin d’être en mesure de les juger de façon équitable. Pour atteindre ce but, ils vontdélibérer en utilisant les mêmes outils que lors de la première phase.Concrètement, pour chaque alternative x et pour au moins chaque critère c dans C, lesagents vont devoir déterminer si l’alternative x satisfait le critère c ou non. À l’issuede cette seconde phase, chaque alternative x sera associée à un ensemble de proprié-tés possédées Sx. Ces ensembles reflètent la connaissance commune des agents sur lesalternatives, ils s’en serviront pour exprimer leurs nouvelles préférences. Nous verronsformellement en section 2.4 de quelle manière les agents peuvent prendre en compte lesdécisions consensuelles du groupe afin d’établir leurs nouvelles préférences.

Afin d’avoir un meilleur aperçu du but de cette phase, nous pouvons continuer notreexemple précédent.

Exemple 2.6 [ Seconde phase de délibération ]

Dans cet exemple nous considérons que nos agents se sont mis d’accord sur unensemble de propriétés désirables P = rapidevitesse, cherprix, grasteneur−gras. Onpeut en déduire l’ensemble de critères associé C = vitesse, prix, teneur − gras.Les agents doivent maintenant délibérer afin d’affiner leurs connaissances. Un extraitsemi-formel d’un tel dialogue est donné dans le Tableau 2.2.

La formalisation de cette seconde phase sera également décrite en section 2.3.Ici, les agents sont collectivement d’accord pour dire que l’alternative fastfood possèdeles propriétés rapidevitesse et necoeco−res. Notons que même si le critère eco−res n’étaitpas dans C, les agents ont tout de même délibéré dessus comme ils peuvent le faire pourn’importe quel autre.

Nous avons donné dans cette section une idée générale du protocole de délibération etde la démarche suivie. Nous verrons dans la section suivante comment le formaliser afinde permettre à un groupe d’agents de restructurer leurs préférences de façon claire. Nousverrons par la suite de quelle manière celles-ci peuvent-elles être construites en prenanten compte les décisions consensuelles issues des différentes phases de délibération.


Table 2.2 – Exemple semi-formel de délibération. Extrait de la seconde phase.

# Réponse à Agent Action

1 − Pierre affirmer(Aller au fastfood permet de mangerrapidement.)

2 1 Madalina accepter(Oui je suis d’accord.)

3 1 Arthur accepter(C’est vrai.)

4 − Pierre affirmer(Le fastfood est eco − responsablecar ils servent des légumes.)

5 4 Madalina rejeter(Tu te trompes, les légumes sont im-portés, ce n’est pas une démarche eco −responsable.)

6 5 Pierre défier(Je ne suis pas sûr, peux-tu le prouver ?)

7 6 Madalina affirmer(Regarde, c’est écrit sur le site web.)

8 7 Pierre retirer(Très bien, tu as raison.)

9 − Madalina affirmer(Comme le fastfood importe ses lé-gumes, il n’est pas eco− responsable.)

10 9 Arthur accepter(Oui, cela semble évidemment.)

11 9 Pierre accepter(J’admets que tu as raison.)


2.3 Formalisation du protocole

Dans cette section, nous présenterons les détails techniques du protocole proposé. Nousdéfinirons notamment les différentes actions que peuvent réaliser les agents et les condi-tions sous lesquelles ils peuvent le faire. Nous présenterons également des mécanismesformels permettant de suivre l’évolution des connaissances et des désirs des agents toutau long du processus de délibération.

Dans le but de faire accepter une propriété comme désirable par l’ensemble du groupe,ou pour justifier toute autre position, les agents utiliserons des arguments. Nous sup-posons que les agents possèdent un langage logique du premier ordre (comme Datalogpar exemple) leur permettant d’exprimer ces arguments.

Les arguments utilisés ici sont similaires à ceux que l’on retrouve dans [6, 9, 3]. Enrevanche, nous faisons ici le choix de rendre la règle qui permet de prouver la conclusionde l’argument visible pour les agents. L’unicité de la conclusion est souhaitable afin defaciliter la récupération d’informations contenues dans les arguments comme nous leverrons par la suite.

Dans les sous-sections suivantes, nous verrons comment les agents peuvent utiliserces arguments et quels sont les effets de leurs actions sur l’avancement de la délibération.

2.3.1 Actes de langage

Les agents peuvent utiliser des arguments à des fins différentes en fonction d’un ensembled’actions possibles. Nous définissons ces actions comme un ensemble d’actes de langageou speech acts [23] que les agents pourront utiliser. Il s’agit d’actions que les agentspeuvent utiliser pour exprimer leurs positions. Ces actions sont des locutions pouvantêtre utilisées chacune dans un but différent. Les locutions que peuvent utiliser les agentssont les suivantes.

• affirmer(.) :

– Sens : un agent utilise cette locution dans le but de prouver formellementune position.

– Usage : affirmer(i, arg) où i est dans N et arg est un argument dont laconclusion est la position que i souhaite prouver.

• rejeter(.) :

– Sens : un agent utilise cette locution pour formellement rejeter une affirma-tion qu’un agent différent a essayé de prouver. Pour ce faire, l’agent utiliseun argument qui prouve que l’argument rejeté est faux.

– Usage : rejeter(i, j, F, arg) où i et j sont dans N et F est un ensemblede prémisses précédemment utilisées par j dans le but de prouver une posi-tion. La conclusion de l’argument arg et les prémisses rejetées dans F sontlogiquement incompatibles.

• défier(.) :

2.3. FORMALISATION DU PROTOCOLE 25

– Sens : un agent utilise cette locution pour demander à un autre agent dejustifier la validité de certaines prémisses précédemment utilisées pour prouverune position.

– Usage : défier(i, j, F ) où i et j sont dans N et F est une ensemble deprémisses précédemment utilisées par j dans le but de prouver une position.

• retirer(.) :

– Sens : un agent utilise cette locution quand il est incapable de justifiercertaines prémisses qu’il a précédemment utilisées pour prouver une position.

– Usage : retirer(i, arg) où i est dans N et arg est un argument précédem-ment avancé par i utilisant certaines prémisses que i ne peut pas justifier.

• accepter(.) :

– Sens : un agent utilise cette locution pour explicitement accepter une posi-tion prouvée par un autre agent.

– Usage : accepter(i, j, arg) où i et j sont dans N et arg est un argumentprécédemment utilisé par j que i accepte.

Ces actes de langage permettent aux agents de justifier leurs positions ainsi que dedemander des justifications à d’autres agents. Dans la section suivante, nous verronscomment ils peuvent les utiliser pour délibérer de manière constructive et cohérente.

2.3.2 Éléments de syntaxe

Structure de réponse

Afin de maintenir une cohérence dans le dialogue, les agents doivent utiliser les actes delangage de façon constructive. Ces locutions sont soumises à une structure de réponseparticulière qui assure que chaque locution est utilisée dans un contexte approprié. Elledéfinie quelles locutions peuvent être utilisées en réponse à une autre locution. Celaempêche les agents d’utiliser une locution inadaptée à une certaine situation. Cettestructure de réponse est présentée dans le Tableau 2.3.

Table 2.3 – Locutions et leurs relatives attaques et redditions.

Locutions Attaques Redditionsaffirmer(.) rejeter(.) ou défier(.) accepter(.) ou retirer(.)rejeter(.) rejeter(.) ou défier(.) retirer(.)défier(.) affirmer(.) retirer(.)retirer(.) ∅ ∅accepter(.) ∅ ∅

Nous pouvons par exemple observer que l’action retirer(.) peut être utilisée par unagent en réponse à une action défier(.) dans le cas où il n’a pas pu se justifier. Cette


action défier(.) peut elle avoir été utilisée pour demander une justification après uneaction affirmer(.).Cette structure de réponse particulière nous assure qu’aucun agent ne peut venir « pol-luer » la délibération en utilisant des locutions dans un contexte inadapté.

Conditions d’utilisation

Dans le but d’empêcher une mauvaise utilisation des locutions, ces dernières sont sujettesà un ensemble de conditions d’utilisation qui viennent compléter la structure de réponseprésentée précédemment. Ces conditions sont précisées au sein du Tableau 2.4.

Table 2.4 – Locutions et leurs conditions d’usage.

Locutions Conditions d’usageaffirmer(i, arg) L’argument arg n’a jamais été utilisé.rejeter(i, j, F, arg) Les prémisses rejetées dans F ont été utilisées par j dans le

but de prouver une position que i rejette. La conclusion del’argument arg et les prémisses de F sont incompatibles.

défier(i, j, F ) Les prémisses F défiées ont été utilisées par j pour prouverune position que i n’a pas encore acceptée.

retirer(i, arg) L’argument arg a été avancé par i.accepter(i, j, arg) L’argument arg a été avancé par j.

Ces conditions assurent que les agents utilisent les locutions de façon ciblée afin defaire progresser le débat.

Effets

En raison des conditions imposées sur l’usage des locutions, chaque action menée parun agent l’est dans un but précis. Les actions menées par chaque agent entraînent desconséquences sur leurs connaissances. Au cours du processus, chaque agent possède unensemble contenant les positions auxquelles il est publiquement associé, cet ensemble estclassiquement appelé un Commitment Store ([26, 13, 18]).

Sous l’hypothèse que les agents sont rationnels, le Commitment Store d’un agent nepeut contenir d’arguments aux conclusions incompatibles.

Les différentes actions menées par chaque agent entraînent des modifications ducontenu de son Commitment Store. Ces modifications permettent de garder une trace del’avancement du dialogue. Les modifications associées à chaque action sont répertoriéesau sein du Tableau 2.5.

Les modifications apportées au Commitment Store de chaque agent permettent deconstruire effectivement les ensembles attendus à l’issue de chaque phase de délibération.Les arguments présents dans l’intersection des Commitment Stores de tous les agentssont, par construction, consensuellement acceptés par le groupe.

À l’issue de la première phase de délibération, les propriétés désirables pour legroupe sont celles présentes en conclusions des arguments consensuellement acceptés.


Table 2.5 – Locutions et leurs effets sur les Commitment Stores.

Locutions Effets sur les Commitment Storesaffirmer(i, arg) Ajouter arg à CS(i).rejeter(i, j, F, arg) Ajouter arg à CS(i).défier(i, j, F ) -retirer(i, arg) Retirer arg de CS(i)accepter(i, j, arg) Ajouter arg à CS(i).

Entre les deux phases de délibération, le Commitment store de chaque agent est ré-initialisé à l’ensemble vide : les arguments utilisés lors de chaque phase ne mélangent pas.Au terme de la seconde phase, les couples (alternatives,propriétés possédées) constituantla connaissance du groupe sont ceux présents en conclusion des arguments consen-suellement acceptés par les agents.

Dans les deux sous-sections suivantes, nous mettrons en application le formalismedéfini au sein de notre exemple fil rouge afin d’observer les conséquences de la délibérationsur les propriétés désirables et les connaissances communes du groupe.

2.3.3 Exemple formalisé

Nous utiliserons ici l’exemple fil rouge dans le but d’illustrer la formalisation du protocoledonnée précédemment.

Application à la première phase

Comme vu précédemment, le but de la première phase est de permettre aux agents dese mettre d’accord sur un ensemble de propriétés désirables. Initialement, les agentsde notre exemple fil rouge possède chacun un ensemble de propriétés désirables, celles-ci sont données dans l’Exemple 2.2. Dans le Tableau 2.1 nous avons donné un extraitsemi-formel de délibération. Le Tableau 2.6 reprend cet extrait de manière formelle enutilisant le formalisme défini précédemment. Par souci de gain de place, les règles nesont pas explicitement données dans les arguments.

Table 2.6 – Extrait de la première phase de délibération.

# Réponse à Action Effet sur le Commitment Store

1 -

affirmer(Arthur, arg1 =<contrainte(Réunion) ∧ :viole(nrapidevitesse, Réunion),

.,

voulue(rapidevitesse)>)

CS(Arthur) := CS(Arthur) ∪ arg1

2 1 défier(Pierre,Arthur, contrainte(Réunion) -

3 2

affirmer(Arthur, arg2 =<possède(Agenda) ∧prouve(Agenda, contrainte(Réunion)),

.,

contrainte(Réunion)>)



4 3 accepter(Pierre,Arthur, arg1) CS(Pierre) := CS(Pierre) ∪ arg1

5 1 accepter(Madalina,Arthur, arg1) CS(Madalina) := CS(Madalina) ∪ arg1

P := P ∪ rapidevitesse

6 -

affirmer(Madalina, arg3 =<satisfait(cherprix, qualité) ∧but(qualité),

.,

voulue(cherprix)>)

CS(Madalina) := CS(Madalina) ∪ arg3

7 6

rejeter(Arthur, Madalina,satisfait(cherprix, qualité),

arg4 =< satisfait(fastfood, cherprix) ∧satisfait(fastfood, nqualité),

.,

¬satisfait(cherprix, qualité)>)


8 7 retirer(Madalina, arg3) CS(Madalina) := CS(Madalina)\arg3

9 -

affirmer(Pierre, arg5 =<satisfait(grasteneur−gras, satiété) ∧but(satiété),

.,

wanted(grasteneur−gras)>)

CS(Pierre) := CS(Pierre) ∪ arg5

10 9 accepter(Arthur,Pierre, arg5) CS(Arthur) := CS(Arthur) ∪ arg5

11 9 accepter(Madalina,Pierre, arg5) CS(Madalina) := CS(Madalina) ∪ arg5

P := P ∪ grasteneur−gras...

Chaque action menée par les agents a des conséquences sur leur Commitment Storepersonnel. Afin de pouvoir extraire l’ensemble P des propriétés désirables consensuel-lement acceptées comme telles, nous devons nous appuyer sur le contenu de ces Com-mitment Stores. Dans notre cas, le contenu de ces ensembles est donné au sein du Ta-bleau 2.7.

Table 2.7 – Contenu des Commitment Stores après délibération - Première phase

Agent Contenu du Commitment StoreArthur CSArthur = arg1, arg2, arg4, arg5Madalina CSMadalina = arg1,arg3, arg5Pierre CSP ierre = arg1, arg5

Conformément à la Définition 1.23, nous pouvons extraire de ces ensembles les pro-priétés désirables du groupe. Les arguments arg1 et arg5 sont communs aux CommitmentStores de tous les agents. Les propriétés présentes en conclusion de ces arguments ontdonc été consensuellement acceptées comme désirables par le groupe. On a donc :

P = rapidevitesse, grasteneur−gras

Nous n’avons donné ici qu’un extrait de cette phase. Dans la suite de l’exemple,nous considérerons que les agents se sont mis d’accord sur un ensemble plus large. Nousprendrons P = rapidevitesse, grasteneur−gras, cherprix.


Nous verrons dans la sous-section 2.4 de quelle façon la restructuration des préfé-rences des agents est influencée par cet ensemble. Nous allons tout d’abord voir commentappliquer le formalisme défini à la seconde phase de délibération.

Application à la seconde phase

Pour rappel, le but de cette phase est de permettre aux agents de partager leurs connais-sances personnelles sur les alternatives de façon à les uniformiser. Cela a pour consé-quence l’attribution d’un ensemble de propriétés possédées à chaque alternative. Cesensembles serviront également de base aux agents pour restructurer leurs préférences.Là encore, les agents possèdent un ensemble de connaissances a priori sur les alterna-tives. Dans notre exemple, ces connaissances ont été données dans l’Exemple 2.3. Dans leTableau 2.2, nous avons donné un extrait semi-formel de cette seconde phase du proto-cole de délibération. Le Tableau 2.8 reprend cet extrait en utilisant le formalisme défini.Là encore, par souci de gain de place, les règles ne sont pas explicitement données dansles arguments.

Table 2.8 – Extrait de la seconde phase de délibération.

# Reply to Action Commitment Store effects

1 -

affirmer(Pierre, arg1 =<permet(fastfood, drive) ∧satisfy(drive, rapidevitesse).,

satisfait(fastfood, rapidevitesse)>)


2 1 accepter(Madalina,Pierre, arg1) CS(Madalina) := CS(Madalina) ∪ arg1

3 1 accepter(Arthur,Pierre, arg1) CS(Arthur) := CS(Arthur) ∪ arg1

Sfastfood := Sfastfood ∪ rapidevitesse

4 -

affirmer(Pierre, arg2 =<vend(fastfood, légumes) ∧satisfait(légumes, ecoeco−res),

.,

satisfait(fastfood, ecoeco−res)>)


5 4

rejeter(Madalina, Pierre,satisfait(légumes, ecoeco−res),

arg3 =< importe(fastfood, légumes),

.,

¬satisfait(légumes, ecoeco−res

>)


6 5 défier(Pierre,Madalina, importe(fastfood, légumes)) -

7 6

affirmer(Madalina, arg4 =<possède(Site Web) ∧prouve(SW, importe(fastfood, légumes)),

.,

importe(fastfood, légumes)>)


8 7 retirer(Pierre, arg2) CS(Pierre) := CS(Pierre)\arg2

9 -

affirmer(Madalina, arg5 =<vend(fastfood, légumes) ∧importe(fastfood, légumes),

.,

satisfait(fastfood, necoeco−resp)>)


10 9 accepter(Arthur,Madalina, arg5) CS(Arthur) := CS(Arthur) ∪ arg5

11 9 accepter(Pierre,Madalina, arg5) CS(Pierre) := CS(Pierre) ∪ arg5


Sfastfood := Sfastfood ∪ necoeco−res...

De la même manière que lors de la première phase, les connaissances communes desagents sur les alternatives peuvent être extraites à partir du contenu de leur CommitmentStore respectif. Pour cet extrait de la seconde phase, les arguments présents dans cesensembles sont donnés dans le Tableau 2.9.

Table 2.9 – Contenu des Commitment Stores après délibération - Seconde phase

Agent Contenu du Commitment StoreArthur CSArthur = arg1, arg5Madalina CSMadalina = arg1, arg3, arg4, arg5Pierre CSP ierre = arg1,arg2, arg5

Les arguments arg1 et arg5 ont été consensuellement acceptés par les agents. Confor-mément à la Définition 1.24, les couples (alternatives/propriétés possédées) présents enconclusion de ces arguments constituent une connaissance commune pour les agents.Dans notre cas, les arguments arg1 et arg5 contiennent respectivement les couples(fastfood, rapidevitesse) et (fastfood,necoeco−res). On considère donc deux nouvellesconnaissances communes concernant l’alternative fastfood et ainsi :rapidevitesse,necoeco−res ⊆ Sfastfood.

Dans la suite de notre travail, nous considérerons que les connaissances communesdes alternatives sont plus nombreuses que celles obtenues dans l’extrait précédent. Nousferons l’hypothèse que les agents se sont mis d’accord sur les ensembles déjà présentsdans l’Exemple 2.31.

Dans la section suivante nous verrons comment tirer profit des résultats de la déli-bération dans le but de permettre aux agents de restructurer leurs préférences.

2.4 Restructuration des préférences

2.4.1 La manière forte

Une première façon pour les agents de restructurer leurs préférences est de considérerque les préférences du groupes comptent plus que les leurs. Sous cette hypothèse, lesagents prendront comme base pour leurs nouvelles préférences, le classement P induitpar l’ensemble P et les connaissances obtenues par le groupe à l’issue de la délibération.

1Notons tout de même que dans notre exemple, les connaissances des agents n’ont pas été modifiées.Sous l’hypothèse de ne considérer que des agents rationnels, nous supposons que ceux-ci ne possédaientque des connaissances réelles sur les alternatives. Or la seconde phase de délibération ne permet qued’uniformiser ces connaissances. Étant donné que les préférences des agents ne repose qu’en partie surces connaissances (partie non subjective), nous avons choisi de ne pas les modifier afin de ne pouvoirobserver que les seuls effets de la mise en commun de leur propriétés désirables personnelles, la véracitéde la connaissance étant, par définition non subjective.

2.4. RESTRUCTURATION DES PRÉFÉRENCES 31

Leurs anciennes propriétés désirables ne leur permettant que de résoudre des égalitésau sein de P . Cette hypothèse assurent que les nouvelles préférences des agents seronttrès homogènes ce qui pourrait permettre de résoudre notre problème de restructuration.Cependant c’est une hypothèse forte qui restreint énormément les agents. En effet, siil n’existe pas d’alternatives classées à égalité dans P , alors P devient la nouvellerelation de préférence de tous les agents et nous obtenons un consensus, ce qui estirréaliste. Nous ne ferons donc pas cette hypothèse ici.

2.4.2 La manière douce

Une seconde façon pour un agent de restructurer ses préférences à l’issue de la délibé-ration est de considérer que les propriétés choisies et les connaissances acceptées par legroupe le sont également pour lui. En effet, en tant que membre du groupe, un agent aaccepté et a contribué à proposer et à faire accepter des propriétés et des connaissances.

L’ensemble de propriétés désirables construit par le groupe est donc le reflet despréférences de chacun des agents. Suivre cette intuition modifie les préférences des agentsde façon moins drastique que de le faire comme précédemment. Sous l’hypothèse deconsidérer ses désirs et ceux du groupe comme équivalents, les nouvelles propriétésdésirable d’un agent seront le résultat de la fusion de son ensemble de propriétésdésirables avec celui du groupe. Lors de cette opération, il faut faire attention à ne paslaisser dans l’ensemble obtenu, des propriétés antagonistes relatives à un même critère.Dans ces cas-là, la propriété choisie par le groupe sera considérée comme plus importanteque celle présente à l’origine en ceci qu’elle est le fruit de la délibération.

Les nouvelles connaissances des agents sont également construites sur ce principe.Leurs nouvelles connaissances sont le fruit de la fusion de leurs anciennes avec cellesobtenues via le processus de délibération.

Les nouvelles relations de préférence des agents sont celles induites par lesnouveaux ensembles de propriétés désirables et sont basées sur les connaissances desagents sur les alternatives obtenues après la délibération. Elles sont construites de façonsimilaire aux préférences a priori des agents introduites à la Définition 1.20.

Ces définitions étant données, nous pouvons reprendre notre exemple fil rouge etobserver les effets de la délibération sur les préférences individuelles des agents.

Exemple 2.7 [ Restructuration des préférences - Manière douce ]

Reprenons notre ensemble N = Arthur,Madalina, P ierre de 3 agents. À l’issuede la délibération, chaque agent i de N possède un nouvel ensemble de propriétés dési-rablesW ′i construit à partir de l’ensemble P = rapidevitesse, grasteneur−gras, cherprixet de l’ancien ensemble de propriétés désirables Wi. Ces nouveaux ensembles ont étéconstruits conformément à la Définition 1.25 et sont donnés dans le tableau suivant.

Agent Nouveaux ensembles de propriétés désirables

Arthur W ′Arthur : grasteneur−gras, rapidevitesse, cherprix

Madalina W ′Madalina : grasteneur−gras, rapidevitesse, cherprix, ecoeco−res

P ierre W ′P ierre : grasteneur−gras, rapidevitesse, cherprix, necoeco−res


Les connaissances des agents n’ont elles pas été modifiées par le processus de délibé-ration. Nous pouvons maintenant récupérer les nouvelles préférences des agents sur lesalternatives conformément à la Définition 1.27. Celles-ci sont données dans le tableausuivant.

Agent Nouvelles relations de préférence

Arthur ′Arthur : fastfood ′Arthur chinois ′Arthur nul − part ∼′Arthur italien

Madalina ′Madalina: fastfood ∼′Madalina chinois ′Madalina italien ∼′Madalina nul − part

P ierre ′P ierre : fastfood ′P ierre chinois ∼′P ierre italien ∼′P ierre nul − part

À l’issue de la délibération, les agents ont donc restructuré leurs préférences. Le butde notre travail vise à étudier les effets de ce protocole sur les propriétés structurelles despréférences individuelles. Nous souhaitons en particulier nous intéresser aux effets sur lasingle peakedness. Nous faisons ci-dessous cette analyse dans le cadre de notre exemplefil rouge.

Exemple 2.8 [ Effets sur les propriétés structurelles des préférences ]

Intéressons-nous maintenant aux nouvelles propriétés structurelles des préférences denos agents. Comme on peut le voir dans la figure suivante qui représente pour chaqueagent i de N et chaque alternative x de X l’utilité accordée par i à x2, les nouvellespréférences des agents sont single peaked.

>

Utilité

nul− part italien fastfood chinois

4

3

2

1

← Arthur (rouge)

← Madalina

Pierre (bleu)

2.4. RESTRUCTURATION DES PRÉFÉRENCES 33

Cette propriété nous garantie l’obtention d’un vainqueur de Condorcet via pairwisemajority. Nous pouvons représenter le graphe des duels associé à ces nouvelles préférenceset observer qu’il s’agit de l’alternative fastfood qui gagne tous ses duels :

fastfood

chinois

italien

nul − part

Le processus de délibération a donc eu pour effet de rapprocher les préférencesdes agents de la single peakedness. Ici cette propriété est même atteinte. Cela nousgarantie un résultat cohérent lors de l’utilisation de la pairwise majority et nous permet decontourner notre problème. Nous avons réussi à observer ces effets sans pour autant violerla propriété d’universalité, désirable dans un processus démocratique. Les préférences desagents ont bien été en un sens restreintes, mais cette restiction vient des agents eux-mêmes et est le fruit de la délibération ce qui nous permet de contourner notre problèmede façon démocratique.

Nous avons donné dans ce chapitre, la formalisation d’un protocole de délibération,ses principes fondateurs ainsi qu’une intuition sur les conséquences qu’il pourrait avoirsur les propriétés structurelles des préférences individuelles d’un groupe d’agents.

Nous tâcherons, dans le chapitre suivant, de mieux comprendre ces conséquences afind’obtenir des garanties théoriques et expérimentales sur l’efficacité du protocole.

2Veuillez noter que la représentation graphique des préférences a uniquement pour but la visualisationde leurs propriétés structurelles. Les valeurs d’utilité représentent le rang le plus proche attribué parchaque agent à chaque alternative et seule la forme des courbes est importante.

3

Résultats

Dans ce chapitre, nous tâcherons de comprendre comment l’utilisation de ce protocolepeut permettre des modifications intéressantes dans la structure des préférences indi-viduelles. Nous détaillerons tout d’abord en Section 3.1 les différentes métriques quinous permettrons d’étudier ces modifications structurelles. Il s’agira plus précisément dedonner des méthodes permettant de mesurer une proximité à la single peakedness ou ad’autres propriétés constituant des conditions suffisantes à l’obtention d’un vainqueur deCondorcet. La motivation reste identique : plus un profil de préférences est proche (pourune métrique donnée) de la single peakedness ou de la single cavedness par exemple, plusla probabilité d’obtenir un vainqueur de Condorcet augmente. Nous présenterons ensuiteen Section 3.2, via une approche théorique, des notions et des résultats préliminaires quinous permettrons, en Section 3.3, d’effectuer expérimentalement des mesures de proxi-mité afin d’observer l’impact du processus de délibération sur les propriétés structurellesdes préférences individuelles.

3.1 Notions de proximitéNous dirons de notre protocole qu’il est efficace si après utilisation, les nouvelles pré-férences des agents concernés sont plus proches de certaines propriétés structurelles in-téressantes (single peakedness, single cavedness, etc.) que leurs préférences premières.Afin de tester cette efficacité, il nous faudra donc définir formellement ces notions deproximité. Nous verrons dans cette section plusieurs métriques différentes et tâcheronsde justifier leur utilisation.

3.1.1 Single peakedness - Mesure de compatibilité maximum

Cette métrique dont la valeur sera notée τsp s’appuie sur les travaux de Niemi en1969 [22] puis sur ceux de List en 2001 [19]. Étant donné un ensemble d’agents ayantchacun des préférences individuelles sur un ensemble d’alternatives, on considère le rap-port entre la taille du plus grand sous-ensemble d’agents dont les préférences sont singlepeaked et le nombre total d’agents.

La taille de cet ensemble maximum M rapporté au nombre total d’agents de Nconstitue une mesure de la proximité à la single peakedness. En effet, si N = M alors

35

36 CHAPITRE 3. RÉSULTATS

τsp = 1, le profil de préférences est single peaked et il existe un vainqueur de Condorcet.En revanche, si τsp < 1, on ne peut rien affirmer quand à l’existence d’un vainqueur deCondorcet, la single peakedness n’étant qu’une condition suffisante à son obtention [7].Des bornes inférieures pour cette mesure existent. Un profil de préférences ne pourrajamais afficher un mesure de proximité τsp inférieure à ces valeurs. Si les préférencesdes agents sont strictes, cette borne est égale à 2k−1

k! où k est le nombre d’alternativesconsidérées. Ainsi, pour 3 alternatives, au minimum 2

3 des agents concernés possèdentdes préférences single peaked.

Cette mesure s’appuie sur l’intuition suivante : plus une proportion importante desagents possèdent des préférences single peaked, et donc est implicitement d’accord sur unordre sur lequel ranger les alternatives (une plus grande dimension structurante), plus lespréférences individuelles des agents du groupe sont homogènes et pourront donner lieuà l’obtention d’un vainqueur de Condorcet. En revanche, si la mesure de proximité estfaible, cela indique des préférences individuelles disparates dont il sera difficile d’extraireune dimension structurante, affaiblissant ainsi la probabilité d’obtenir un vainqueur deCondorcet.

3.1.2 Single peakedness - Recherche d’un candidat unificateur

En 2004, Gehrlein [14] considère une variation de la mesure précédente. Considéronsle cas d’une élection à trois alternatives X = A,B,C. Les préférences individuellesd’agents sur ces alternatives sont limitées à ces six classements :

# Classement1 A B C2 B A C3 A C B4 C A B5 B C A6 C B A

Soit nc le nombre d’agents ayant pour préférences individuelles le classement c. Ona donc, n1 + n2 égal aux nombre d’agents ayant classé C en dernière position. De façonsimilaire, n3 + n4 agents ont classé B en dernière position et n5 + n6 agents ont classéA en dernière position. Dans notre cas, si une des trois alternatives n’est jamais classéedernière, alors le profil de préférences sera single peaked [25]. On définit ainsi notremesure de proximité : s’il existe un candidat rarement classé dernier par les agents,alors il s’agit d’un candidat unificateur dans le sens ou très peu d’agents considéreraientson élection comme le pire résultat possible. S’il existe de tels candidats, il sera d’autantplus probable d’obtenir un vainqueur de Condorcet.

Quand la valeur de la métrique est à 0, un candidat n’est jamais classé en dernièreposition, le profil de préférences est donc single peaked et il existe un vainqueur deCondorcet. Une borne supérieure triviale pour cette mesure vaut n

3 .On peut construire une métrique similaire dans le but de calculer une proximité à

la single cavedness, propriété miroir de la single peakedness. Un triplet d’alternatives estsingle caved lorsque qu’il existe une alternative qui n’est jamais classée première.

3.2. APPROCHE THÉORIQUE 37

3.1.3 Separability into two groups - Recherche d’un candidatpolarisant

En 2005 [15], Gehrlein propose une autre mesure, variante de la précédente. Toujoursdans le cas à trois alternatives, s’il existe un candidat rarement classé en deuxièmeposition par les agents, alors il s’agit d’un candidat polarisant. En effet, il est soit trèsapprécié par certains agents (classé premier), soit très peu apprécié par d’autres (classédernier). Dans une telle situation, il sera plus aisé d’extraire une dimension structurantedes préférences individuelles. La valeur de cette mesure sera notée r.

Cette mesure comme la précédente, s’appuie sur les travaux de Sen [25] concernantla triple wise value restriction et notamment sur la notion de separability into two groupsintroduite par Inada [17]. Dans le cas r = 0, il existe un candidat qui n’est jamais classédeuxième, le profil de préférences satisfait la condition de separability into two groupset un vainqueur de Condorcet existe. La même borne supérieure de n

3 s’applique à cettemesure.

À noter que ces mesures peuvent se combiner afin de calculer une proximité à latriple wise value restriction.

Dans la Section 3.3, nous utiliserons des variantes normalisées de ces deux dernièresmesures afin de pouvoir tester l’efficacité du protocole de délibération dans des cas ou ily a strictement plus de trois alternatives en jeu. La première mesure de proximité est elledifficile à calculer, en effet, le temps de recherche d’un plus grand sous-ensemble singlepeaked augmente exponentiellement avec le nombre d’agents considérés. Cette mesureest donc peu adaptée pour effectuer des expérimentations automatisées. En revancheil s’agit d’un bon indicateur et elle pourrait être utilisée pour mesurer l’impact de ladélibération dans des situations réelles1.

Nous introduirons dans la Section suivante, la notion de propriété problématiqueainsi que quelques résultats théoriques qui nous permettrons d’étudier en Section 3.3l’efficacité du protocole de délibération en fonction de divers paramètres.

3.2 Approche théorique

3.2.1 Attentes

Nous tenterons dans cette Section d’obtenir des garanties théoriques d’efficacité pourle protocole de délibération proposé. Nous avons vu dans la Section précédente diffé-rents outils permettant de mesurer la proximité des préférences des agents à différentespropriétés suffisantes pour l’obtention d’un vainqueur de Condorcet. L’idéal serait doncde montrer formellement que l’utilisation du protocole rapproche les préférences de cespropriétés en s’appuyant sur les métriques définies précédemment. Cependant, il s’agitlà d’un problème difficile faisant intervenir beaucoup de paramètres différents (nombred’agents, d’alternatives, de propriétés désirées, arguments potentiels qui dépendent del’étendue des connaissances des agents ce qui est difficile à borner, etc.). De plus, il estfacile de construire des exemples d’utilisation du protocole menant à des résultats non

1C’est cette mesure qu’utilise List et al. [20] pour mesurer l’impact de la délibération non formellesur les préférences d’agents.


satisfaisants. Pour ces raisons, obtenir une garantie formelle générale d’efficacité sembledifficile dans ce contexte.

Ces problèmes de généralisation difficiles sont fréquents en Choix Social et certainsrésultats utilisés dans notre étude sont basés sur des expérimentations tant obtenir unepreuve plus analytique est complexe. Niemi [22] ou List [19] par exemple, se sont en partieappuyés sur des résultats d’expérimentation pour montrer que la probabilité d’obtenirun résultat non transitif via pair-wise majority diminue lorsque la proximité à la singlepeakedness augmente.

Nous allons dans cette section définir la notion de propriété problématique qui nouspermettra de montrer formellement que le protocole de délibération homogénéise les pré-férences de agents. Ce résultat nous permettra d’identifier un paramètre sur lequel nousnous baserons pour obtenir en Section 3.3 une validation expérimentale de l’efficacité denotre protocole.

3.2.2 Propriétés problématiques

Chaque agent possède un ensemble de propriétés désirables lui permettant d’exprimer sespréférences conformément à la Définition 1.20. Parmi ces propriétés désirables, certainessont partagées par l’ensemble des agents (il y a consensus sur celles-ci), les autres sontplus personnelles. Ce sont ses propriétés personnelles résiduelles qui permettent à unagent de modifier le classement induit par les propriétés considérées comme désirablespar l’ensemble du groupe à l’issue de la délibération.

Certaines des propriétés personnelles des agents peuvent induire des modificationséloignant le profil de préférences du groupe de propriétés structurelles intéressantes.En effet, plus les agents possèdent des propriétés non désirées par le groupe plus leurspréférences seront hétérogènes et la probabilité d’obtenir un résultat transitif via pair-wise majority sera moindre.

Ainsi, nous qualifierons de propriété problématique toute propriété n’étant pasdésirée par l’ensemble des agents.

À l’issue de la délibération, chaque agent possède un nouvel ensemble de propriétésdésirables, construit selon la Définition 1.25. Ces ensembles contiennent tous l’ensembleP des propriétés considérées comme désirables par le groupe. Suite à la définition pré-cédente, nous pouvons faire une première observation triviale : si il y a consensus et quetous les agents possèdent les mêmes propriétés désirables à l’issue de la délibération,l’application de la pair-wise majority sur les nouvelles préférences des agents donneratoujours un résultat transitif.

Lemme 3.1 [ Absence de propriétés problématiques ]

Si à l’issue de la délibération aucun agent ne désire une propriété problématique,et que les agents possèdent tous les mêmes connaissances sur les alternatives, alors leclassement des alternatives via pair-wise majority est transitif.

3.2. APPROCHE THÉORIQUE 39

Preuve

S’il n’existe pas de propriété problématique, alors par définition, quel que que soit iet j dans N ,Wi = Wj . Sous l’hypothèse que les agents ont les mêmes connaissances surles alternatives, les préférences de chaque agent sont identiques et donc le classementdes alternatives après pair-wise majority est le même que le classement final de chaqueagent qui est transitif.

o

Ces propriétés problématiques étant caractérisées, il est maintenant intéressant deregarder leur évolution pendant la phase de délibération. Le Lemme 3.2.2 nous garantieun résultat transitif en cas de consensus. Le résultat suivant permet d’affirmer que leprocessus de délibération permet aux agents de se rapprocher d’un consensus.

Lemme 3.2 [ Diminution du nombre de propriétés problématiques ]

Le nombre de propriétés problématiques ne peut pas augmenter au cours du processusde délibération.

Preuve

Soit N = 1, . . . , n un ensemble de n agents. Chaque agent i de N possède avantla délibération, un ensemble Wi de propriétés désirables. Soit p appartenant à

⋃i∈N Wi,

• p est problématique : il existe i dans N tel que p appartient àWi. Les agents étantrationnels, i va proposer p au groupe. Deux cas de figure :

– si consensus sur p, alors p devient non problématique,– sinon p reste problématique, le nombre total de propriétés problématiques ne

change pas.

• p n’est pas problématique : il existe i dans N tel que p appartient àWi. Les agentsétant rationnels, i va proposer p au groupe. Deux cas de figure :

– si p est acceptée par le groupe, elle reste non problématique,– si p est refusée par le groupe : elle reste tout de même désirée par l’ensemble

des agents, donc non problématique.

Le nombre total de propriétés problématiques ne peut pas augmenter.

o


À l’issue de la délibération les agents ont convenu d’un ensemble P de propriétésdésirables pour le groupe. Cet ensemble induit une relation de préférences P sur l’en-semble X des alternatives. Les propriétés désirées des agents n’appartenant pas à Psont problématiques. Elles vont permettre à chaque agent i de N de modifier P afind’obtenir ses nouvelles préférences individuelles i. Tentons d’identifier les changementsque peut effectuer un agent dans P en fonction des propriétés problématiques qu’ilpossède.

Soit A et B deux alternatives de l’ensemble X considéré telles que A P B. Soit iun agent de N , pour obtenir B i A en modifiant P , i a besoin d’un certain nombrede propriétés problématiques. Supposons que A possède exactement une propriété de Pde plus que B. Dans ce cas, i ne pourra faire remonter B devant A que s’il existe deuxpropriétés p1 et p2 n’appartenant pas à P que i désire telles que A ne possède pas cespropriétés mais telles que B les possède.

On peut généraliser ce résultat dans le cas où la différence ∆A,B de propriétés de Ppossédées par A et B est supérieure à 1. Dans ces cas, au moins ∆A,B + 1 propriétésproblématiques possédées par B mais pas par A doivent être désirées par i pour obtenirB i A.

Cette remarque effectuée, nous pouvons utiliser le Lemme 3.2.2 pour obtenir le ré-sultat suivant qui nous fournit un paramètre que nous exploiterons dans les expérimen-tations détaillées en Section 3.3.

Théorème 3.1 [ Nombre maximum de modifications possibles ]

Lors de la délibération, plus les agents apportent des arguments effectifs, moins ilspourront modifier le classement P induit par P.

Preuve

D’après le Lemme 3.2.2, le nombre de propriétés problématiques diminue ou reste in-changé au cours de la délibération. En supposant que la différence maximale de propriétésde P possédées par deux alternatives est au plus 1, on obtient une borne supérieure surle nombre de remontées d’alternatives que peu effectuer un agent. Avec une différencede 1, il faut au moins deux propriétés problématiques satisfaisant les bonnes conditionspour échanger le rang de deux alternatives consécutives dans P. On a donc, quel quesoit i dans N , si à l’issue de la délibération i possède pbi propriétés problématiques alorsil pourra dans ce cas, effectuer au plus t = bpbi

2 c transpositions élémentaires dans P ,valeur qui décroit avec le nombre de propriété problématiques résiduelles.

o

3.3. EXPÉRIMENTATIONS 41

Le paramètre t, qui est une borne supérieure sur le nombre de transpositions élémen-taires que peut effectuer chaque agent à l’issue de la délibération nous permet de fixerle niveau de consensus obtenu par les agents. Il sert à quantifier ce que nous appeleronsla « qualité » de la délibération effectuée. Plus ce nombre est petit plus le niveau deconsensus est élevé et plus la délibération a été déterminante.

3.3 Expérimentations

Le paramètre t introduit dans la Section précédente nous permet de contrôler la « qua-lité » de la délibération qui a eu lieu entre les agents. Une faible valeur de t indique queles agents ont réduit la quantité de propriétés problématiques. Au contraire, une valeurde t élevée indique que les agents n’ont pas réussi à se mettre d’accord sur une grandequantité de propriétés désirables et chaque agent possède potentiellement une quantitéimportante de propriétés problématiques résiduelles.

En fixant ce paramètre, on peut donc simuler de nombreuses situations de délibé-ration différentes. Dans cette Section, nous étudierons la proximité des préférences desagents aux propriétés structurelles intéressantes après une délibération artificielle dontl’issue2 est paramétrée par t.

Le but de cette approche expérimentale est de pallier l’absence de résultats théo-riques forts garantissant l’efficacité du protocole. Nous répondrons dans cette Section àla question suivante.

La proximité aux propriétés structurelles intéressantes augmente-t-elle lorsque lenombre de propriétés problématiques diminue ?

3.3.1 Évolution mesure d’unification

La première mesure de proximité que nous voulons observer est celle à la single peaked-ness. En effet, se rapprocher de cette propriété faisait partie des motivations premièrespour l’élaboration de ce protocole. Afin de tester l’efficacité du protocole sur cette me-sure, nous avons mis en place l’expérience suivante. Il s’agit d’une implémentation de laDéfinition 1.29. L’expérience est fixée par les paramètres suivants :

• le nombre n d’agents,

• le nombre k d’alternatives,

• le nombre t correspond au nombre maximum de remontées d’alternatives quepeuvent faire les agents dans P ,

• le nombre r : valeur d’un point est égal à la moyenne des valeurs sur r répétititons.

2Ici le nombre maximum de propriétés résiduelles possédées par chaque agent et donc une bornesupérieure sur le nombre possible de remontées d’alternatives dans P .


Le protocole expérimental est le suivant. On part d’un ordre total P sur k alterna-tives qui simule la relation de préférence induite par l’ensemble P des propriétés considé-rées comme désirables par le groupe. Chaque agent peut ensuite effectuer au maximumt remontées aléatoires d’alternatives dans P (utilisation des propriétés problématiquesrésiduelles). Une fois les nouvelles préférences calculées, on calcule la proximité du profilde préférences à la single peakedness en généralisant la Définition 1.29 à l’ensemble destriplets d’alternatives : la mesure de proximité est le ratio de triplets single peaked parrapport au nombre total de triplets. Une mesure m = 1 indique que tous les triplets sontsingle peaked, et donc le profil de préférences est single peaked. En revanche une mesurem = 0 indique que tous les triplets sont problématiques et donnent lieu à un résultatnon transitif, le profil de préférences ne sera pas single peaked.

La Figure 3.1 montre le résultat de l’expérience sur n = 200 agents. Pour k = 3 àk = 10 alternatives, la proximité à la single peakedness a été calculée en fonction de t,nombre maximum de remontées d’alternatives que peut effectuer chaque agent. Afin detraiter et d’harmoniser les différents cas de figure que l’on peut rencontrer, chaque pointdu graphique correspond à une moyenne effectuée sur r = 10000 répétitions.

Figure 3.1 – Proximité à la single-peakedness : 200 agents.

Les résultats sont les suivants. La proximité à la single peakedness augmente lorsquet (et donc le nombre de propriétés problématiques) diminue. Ce résultat est en faveur del’hypothèse selon laquelle le protocole permet aux agents de restructurer leurs préférencesindividuelles de façon intéressante. Cependant, cette augmentation de la proximité sefait à des vitesses différentes en fonction du nombre d’alternatives. En effet, avec troisalternatives, il est très facile d’obtenir un profil de préférences non single peaked en nemodifiant que très peu un même classement3. En revanche, avec plus d’alternatives, plusde modifications personnelles de la part des agents dans leurs nouvelles préférences sontnécessaires pour s’éloigner de la single peakedness. À nombre de modifications égal, ilest à noter que la probabilité d’obtenir une bonne proportion de triplets single peaked

3Cas du paradoxe de Condorcet par exemple.


Figure 3.2 – Proximité à la single-peakedness : 20 agents.

augmente lorsque le nombre d’alternatives augmente, en effet dans ces cas là, le nombrede triplets à considérer augmente également.

Le protocole permet donc bien de rapprocher les préférences des agents de la singlepeakedness, cette proximité augmentant avec la « qualité » de la délibération effectuée.Cependant, une bonne proximité à la single peakedness ne garantit pas un résultat tran-sitif via pairwise majority. On peut tout de même espérer, dans ces cas-là, un vainqueurde Condorcet même si le classement général des alternatives n’est pas totalement tran-sitif. En effet, même si il existe un cycle dans le classement, une alternative vainqueurde Condorcet peut tout à fait exister et elle dominera ce cycle. C’est pour cela que larecherche de candidat unificateur est intéressante.

La Figure 3.2 présente les résultats de la même expérience réalisée sur 20 agents.La proximité à la single peakedness diminue moins rapidement qu’avec un ensemble de200 agents. Cela peut s’expliquer par le fait que, pour un triplet d’alternatives fixé, laprobabilité qu’il ne soit pas single peaked augmente avec le nombre de fois qu’il doit êtreconsidéré. Plus il y a d’agents, plus il y a de chance que leurs préférences individuellessoient incompatibles pour la single peakedness. Le protocole est donc plus efficace avecun nombre d’agents réduits. Bien qu’intuitif, ce résultat est intéressant car la mise enplace du protocole de délibération en situation réelle semble difficile s’il faut considérerun grand nombre d’agents.

Par souci de complétude, la même expérience a été réalisée pour mesurer la proximitéà la single cavedness, propriété miroir de la single peakedness. Les résultats sont similaireset sont présentés dans l’Annexe B.1.

3.3.2 Évolution mesure de polarisation

La seconde expérience vise à étudier la proximité à la separability into two groups tellequ’introduite à la Définition 1.30. Pour ce faire, on généralise la mesure à l’ensemble destriplets d’alternatives et on regarde la proportion de triplets satisfaisant cette condition


par rapport au nombre total de triplets. Les paramètres sont les mêmes que précédem-ment. Les résultats obtenus sont donnés sur la Figure 3.3. La forme générale des courbesest la même que précédemment, on peut donc en conclure que la proximité avec laseparability into two groups augmente lorsque t (et donc le nombre de propriétés problé-matiques) diminue. Cependant, la valeur de proximité à cette propriétés diminue plusrapidement que la proximité à la single peakedness, cela peut s’expliquer par la façondont sont générées les nouvelles propriétés individuelles. En effet, les alternatives respec-tivement première et dernière dans P ont deux fois moins de chance que les autres dechanger de position lors de remontées d’alternatives (la première ne peut pas remonteret le dernière ne peut descendre). Le profil de préférences final aura donc plus de chanced’être single peaked ou single caved que de vérifier la separability into two groups.

Figure 3.3 – Proximité à la separability into two groups : 200 agents.

3.3.3 Proximité à la triple wise value restriction

Les trois mesures de proximité étudiées précédemment concernent des propriétés struc-turelles dont la généralisation est la triple wise value restriction de Sen [25]. On peutgénéraliser les définitions des mesures de proximité afin de mettre au point une métriquepermettant de mesurer la proximité à la triple wise value restriction. De la même façonque précédemment, on regarde la proportion de triplets d’alternatives satisfaisant cettecondition : vérifiée si le triplet est single peaked, single caved ou vérifie la separabilityinto two groups.

Nous pouvons ensuite étudier cette proximité sur les mêmes cas que précédemment.Les résultats sont donnés sur la Figure 3.4.

Comme l’on pouvait s’y attendre, la forme des courbes reste identique. La proximité àla triple wise value restriction augmente lorsque le nombre de propriétés problématiquesrésiduelles diminue. On observe également toujours une chute rapide de la valeur deproximité lorsque peu d’alternatives sont considérées.


Figure 3.4 – Proximité à la Triple wise value restriction : 200 agents.

Figure 3.5 – Proximité à la Triple wise value restriction : 20 agents.

La même expérience a été réalisée pour n = 20 agents, les résultats sont donnés surla Figure 3.5. Comme pour la mesure de proximité à la single peakedness (mais de façonmoindre étant donné que la mesure de proximité à la separability into two groups entre enjeu), avec moins d’agents la proximité diminue moins drastiquement et ce quel que soitle nombre d’alternatives considéré. Pour un grand nombre d’alternatives on remarquemême qu’une proportion non négligeable (aux alentours de 25%) de triplets d’alternativesvérifient toujours une des trois conditions composant la triple wise value restriction etce même avec un très grand nombre de propriétés problématiques résiduelles.


3.3.4 Discussions

Génération de préférencesBien que les résultats des expériences précédentes semblent confirmer l’hypothèse

selon laquelle le protocole de délibération améliore les propriétés structurelles des pré-férences individuelles, nous avons pu faire quelques observations sur les conséquencesqu’impliquent nos choix de simulation. Le principal biais dans les résultats vient de lafaçon dont sont générées les préférences individuelles comme discuté en sous section 3.3.2.

Nous avons suivi ce processus de génération des préférences individuelles pour plu-sieurs raisons. Tout d’abord, il reprend parfaitement les actions que réaliserons les agentsà l’issue de la délibération : modifier le classement du groupe en utilisant leurs propriétésproblématiques résiduelles.

Nous avons également choisi de ne pas simuler le déroulement complet du protocole.Les résultats théoriques présentés en Section 3.2 nous fournissent un paramètre permet-tant de contrôler l’issue de la délibération. De plus, simuler l’exécution du protocole dansson ensemble est compliqué. En effet, énormément de paramètres doivent être considé-rés, nombre d’agents et d’alternatives évidemment, mais il faudra également décider dela distribution des propriétés désirables : quel agent désire cette propriété ? Quelle alter-native satisfait ce critère ? Beaucoup de questions complexes qui aurait inévitablementconduit à la mise en place d’une expérience plus coûteuse en calcul et présentant plusde biais que l’expérience réalisée.

Généralisation des mesuresDans l’expérience réalisée, nous avons choisi de généraliser les différentes mesures de

proximité à l’ensemble des triplets d’alternatives en observant la proportion de tripletssatisfaisant la condition voulue. Plusieurs raisons ont également motivé ce choix. Toutd’abord, nous avons vu qu’en ses valeurs extrêmes, la mesure reste cohérente ; une mesurede 1 signifiant que la condition est vérifiée pour le profil de préférences dans son ensemble,une mesure de 0 signifiant que la condition n’est absolument pas vérifiée.

Enfin, si une grande proportion de triplets d’alternatives vérifient des conditions suf-fisantes à l’obtention d’un vainqueur de Condorcet, alors on peut espérer en obtenir unmême si le résultat final n’est pas complètement transitif. Pour cause, un triplet d’al-ternatives vérifiant une bonne propriété structurelle est constitué d’alternatives pourlesquelles les agents ont des préférences individuelles présentant une dimension structu-rante commune, ce qui facilite l’obtention d’un vainqueur de Condorcet.

Conclusion

Contribution

Nous avons cherché durant ce stage à répondre à la question suivante.

Est-il possible de définir de façon formelle, un protocole de délibération permet-tant de vérifier, théoriquement ou expérimentalement, les résultats pratiques obtenuspar List et al. dans [20] ?

Nous avons tout d’abord fait l’hypothèse que les préférences individuelles d’agentsétaient basées sur des ensembles de propriétés désirables. Cela nous a permit au Cha-pitre 2 de définir de façon formelle un protocole de délibération permettant à un ensembled’agents de restructurer leurs préférences individuelles.

Après avoir étudié théoriquement ce que pouvait apporter ce protocole, nous avonsexpérimentalement montré au Chapitre 3 que son utilisation permettait de rapprocher lespréférences individuelles des agents de conditions suffisantes à l’obtention d’un vainqueurde Condorcet après leur agrégation. Ces conditions, telles que la single peakedness, latriple wise value restriction et d’autres, garantissent, si vérifiées, que l’agrégation despréférences via la méthode de Condorcet donnera un résultat transitif. Dans ces cas-là, un vainqueur de Condorcet pourra être identifié. Un résultat intéressant et que laprobabilité d’obtenir un classement transitif augmente avec la proximité à ces conditions.

Ce protocole permet donc d’augmenter la probabilité d’obtenir un résultat cohérentavec la méthode de Condorcet. De cette façon, nous avons pu contourné le théorèmed’impossibilité d’Arrow de façon démocratique, en particulier sans violer la conditiond’universalité.

Perspectives

Le travail effectué tout au long de ce stage bien que répondant à certaines questions ensoulève d’autres. Le protocole que nous avons formalisé n’est encore qu’un protoype etcertaines améliorations pourraient y être apportées.

47


En premier lieu, il serait bon d’améliorer la phase d’échange d’arguments entre lesagents. Que faire si deux agents possèdent tous les deux une bonne raison de vouloirdeux choses opposées ? Ou que faire si ces agents veulent la même chose mais pour desraisons incompatibles ? La résolution des conflits entre agents pourrait se faire grâce à lathéorie de l’argumentation. Définir des graphes d’argumentation au cours du processusde délibération permettrait de pouvoir choisir quels arguments considérer. Cela pourraitse faire selon différents points de vue grâce à la notion de sémantique d’acceptabilité. Lesagents pourraient vouloir accepter les arguments de façon naïve ou adopter une approcheplus sceptique.

La mise à jour des propriétés désirées par les agents ou de leurs connaissances pour-rait également se faire durant la délibération et non a posteriori. Cela permettrait auxagents de pouvoir adapter leurs arguments à la situation courante, ce qui apporteraitcertainement une délibération plus riche.

D’autres façons de mesurer l’efficacité du protocole pourrait être mises au point. Eneffet, il serait intéressant de creuser plus le lien entre répartition des propriétés désirableset probabilité d’obtenir un résultat incohérent via pair-wise majority.

Nous avons également fait l’hypothèse que les préférences des agents sont baséessur des propriétés. Nous pourrions regarder comment se comporte le protocole si l’onconsidère d’autres façon de générer des préférences.

Enfin, mettre au point une expérimentation en situation réelle permettrait de véri-fier un certain nombre de choses. Tout d’abord, la mesure introduite en Définition 1.28pourrait être utilisée. Cela permettrait de confirmer les résultats expérimentaux obte-nus jusqu’ici. Il serait également intéressant de tester notre hypothèse sur l’origine despréférences individuelles : à quel point les agents peuvent-il identifier des propriétés dé-sirables ? Vient ensuite la question des arguments : à quel point les agents peuvent-ilsarriver à défendre les propriétés qu’ils considèrent comme désirables ?

Toutes ces questions nous rappellent la complexité sous-jacente de la théorie duchoix social. Beaucoup de paramètres sont à prendre en compte et nombre d’hypothèsesréductrices doivent être faites. Cependant, les premiers résultats obtenus durant ce stagesont encourageants et de nombreuses choses restent à faire.

A

Annexes - Définitions formelles

Nous donnons dans cette annexe les définitions formelles de l’ensemble des notionsintroduites dans cette étude bibliographique.

A.1 Choix socialDéfinition 1.1 [ Ensemble d’agents ]

Un ensemble d’agents est un ensemble fini N = 1, . . . , n de n agents.

Définition 1.2 [ Ensemble d’alternatives ]

Un ensemble d’alternatives est un ensemble fini X = x1, . . . , xk de k alternatives.

Définition 1.3 [ Préférences ]

Soit N un ensemble d’agents, X un ensemble d’alternatives. Chaque agent i de Npossède une relation de préférence i (préféré à) sur X (i ⊆ X ×X) . Pour x et ydans X, x i y signifie que l’agent i préfère l’alternative x à l’alternative y.

À partir de l’expression de ces préférences on peut associer à chaque agent iune relation de préférence stricte i sur X. Pour deux alternatives x et y dans X, unagent i préfère strictement x à y (x i y) si et seulement si (x i y) et (y i x).

L’agent i sera indifférent entre x et y (x ∼i y) si et seulement si (x i y) et(y i x).

49

50 ANNEXE A. ANNEXES - DÉFINITIONS FORMELLES

Définition 1.4 [ Profil de préférences ]

Soit N un ensemble d’agents, X un ensemble d’alternatives. On note L(X) l’en-semble de tous les ordres totaux possibles sur X. Un profil de préférences N = 1, . . . ,n appartenant à L(X)n est l’ensemble des ordres totaux exprimés par les agentsde N sur X.

Définition 1.5 [ Fonction de choix social - Social choice function ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et L(X)n l’ensembledes profils de préférences de taille n sur X. Une fonction de choix social est unefonction f : L(X)n −→ 2X qui à partir d’un profil de préférences donne l’ensemble desalternatives désignées comme vainqueurs de l’élection.

Définition 1.6 [ Fonction de bien-être social - Social welfare function ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et L(X)n l’ensemble desprofils de préférences de taille n sur X. Une SWF est une fonction f : L(X)n −→ L(X)qui à partir d’un profil de préférences donne un ordre total f sur l’ensemble desalternatives.

Définition 1.7 [ Universalité ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et L(X)n l’ensembledes profils de préférences de taille n sur X. Soit f une SWF, f respecte la propriétéd’universalité si et seulement si dom(f) = L(X)n.

A.1. CHOIX SOCIAL 51

Définition 1.8 [ Unanimité ]

Soit N un ensemble d’agents, X un ensemble d’alternatives. Soit f une SWF, frespecte la propriété d’unanimité si et seulement si, quelles que soient x et y deuxalternatives de X, si pour tout i dans N x i y alors, x f y.

Définition 1.9 [ Indépendance aux alternatives non pertinentes ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et N un profil de pré-férences. On considère S

N la restriction des préférences présentes dans N aux seulesalternatives contenues dans S. Soit f une SWF, f respecte la propriété d’indépendanceaux alternatives non pertinentes si et seulement si, quelles que soient x et y deux alter-natives de X, si x x,y

N y alors, x f y.

Définition 1.10 [ Absence de dictateur ]

Soit N un ensemble d’agents, X un ensemble d’alternatives. Soit f une SWF, frespecte la propriété d’absence de dictateur si et seulement si quelles que soient x ety deux alternatives de X, il n’existe pas d’agent i dans N tel que pour tout profil depréférences N contenant les préférences de i, on ait que si x i y alors x f y.

Définition 1.11 [ Vainqueur de Condorcet ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et N = 1, . . . ,nun profil de préférences. Une alternative x dans X est dite vainqueur de Condorcet si etseulement si :

Pour toute alternative y différente de x, |x i y| > |y i x| quel que soit i dans N .


Définition 1.12 [ Préférences single peaked ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et i les préférencesd’un agent i de N sur X. Ces préférences sont single peaked s’il existe un ordre Ω surX tel que :

1. il existe une alternative x telle que, pour tout autre alternative y, x i y ;

2. pour toutes alternatives y et z avec x Ω y Ω z alors y i z ;

3. pour toutes alternatives y et z avec z Ω y Ω x alors y i z.

Définition 1.13 [ Profil de préférences single peaked ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et N un profil depréférences sur X. On dira que N est single peaked s’il existe un ordre Ω sur X telque chaque ensemble de préférences individuelles est single peaked sur Ω.

Définition 1.14 [ Ensemble de préférences value restricted ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et X ′ une restriction deX à seulement trois alternatives. On considère i les préférences d’un agent i dans Net X′

i la restriction de i à X ′. On dira que X′i est value restricted si et seulement

si il existe une alternative x dans X ′ telle que pour y et z dans X ′,

y i x ∨ z i x∨

x i y ∨ x i z∨

(x i y ∧ x i z) ∨ (y i x ∧ z i x)

Finalement les préférences i de l’agent i sont value restricted si pour chaque sous-ensemble X ′ de X composé de trois alternatives les restrictions X′

i de i aux X ′ sontvalue restricted.

Définition 1.15 [ Profil de préférences value restricted ]

Soit N un ensemble d’agents, X un ensemble d’alternatives et N un profil depréférences sur X. Si pour tout i dans N les préférences i sont value restricted alorsN est value restricted.

A.2. PROTOCOLE DE DÉLIBÉRATION 53

A.2 Protocole de délibérationDéfinition 1.16 [ Ensemble de critères ]

Un ensemble de critères est un ensemble fini C = c1, . . . , cm de m critères.

Définition 1.17 [ Ensemble de propriétés ]

Soit C un ensemble de critères. Chaque critère c de C est associé à deux propriétés :pc : le critère c est satisfaitnpc : le critère c n’est pas satisfait

On peut définir PC l’ensemble des propriétés relatives à C comme l’union des pro-priétés associées à chaque critère de C. Ainsi, on a :

PC =⋃c∈Cpc,npc

Définition 1.18 [ Ensemble de propriété désirables ]

Soit N un ensemble d’agents, C un ensemble de critères et PC l’ensemble de pro-priétés associé. Chaque agent i de N possède un ensemble de propriétés désirables Wi

tel que quel que soit i dans N , Wi est strictement inclus dans PC .Quel que soit i dans N , Wi ne contient pas deux propriétés antagonistes relatives à

un même critère. Si tel était le cas, alors soit l’agent i se contredit lui-même, impossiblesous l’hypothèse que les agents sont rationnels, soit il est indifférent à ce critère auquelcas on peut retirer les deux propriétés de Wi.

Définition 1.19 [ Connaissances a priori et propriétés possédées ]

SoitN un ensemble de n agents etX un ensemble de k alternatives. Soit C l’ensembledes critères considérés par les agents et PC l’ensemble des propriétés associées. Chaqueagent i de N possède pour chaque alternative x de X un ensemble Si

x de propriétéssupposées possédées par x selon les connaissances de i.


Définition 1.20 [ Préférences individuelles basées sur des propriétés désirables ]

Soit N un ensemble d’agents et X un ensemble d’alternatives. Soit i un agent de NetWi son ensemble de propriétés désirables. Pour tout x dans X, i possède un ensembleSi

x de propriétés supposées possédées par x. Soient x et y deux alternatives de X. Ondira que l’agent i préfère x à y (x i y) si et seulement si :

|p ∈ Six, p ∈Wi| ≥ |p ∈ Si

y, p ∈Wi|

Si i préfère x à y et ne préfère pas y à x, alors i préfère strictement x à y (x i y),sinon i est indifférent entre x et y (x ∼i y).

Définition 1.21 [ Argument ]

Un argument est un triplet arg = (premisses, règle, conclusion). Les prémissesutilisées permettent de déclencher la règle qui prouvera la conclusion. Les prémisses sontun ensemble d’atomes et la conclusion est un atome unique.

Définition 1.22 [ Commitment Store ]

Soit N un ensemble d’agents. Chaque agent i de N possède un Commitment Store,CS(i) = arg1, . . . , argmi qui est un ensemble de mi arguments publiquement accep-tés ou soutenus par i.

Définition 1.23 [ Propriétés désirables du groupe ]

Soit N un ensemble de n agents. Chaque agent i de N possède un CommitmentStore CS(i). L’ensemble Pi des propriétés désirables acceptées par i est le suivant :

Pi = conc(arg) | arg ∈ CS(i) et conc(arg) est une propriété

Les proprités désirables du groupe sont ensuite définies de la façon suivante :

P =⋂

i∈N

Pi

A.2. PROTOCOLE DE DÉLIBÉRATION 55

Définition 1.24 [ Connaissances du groupe ]

Soit N un ensemble de n agents. Chaque agent i de N possède un CommitmentStore CS(i). Soit X un ensemble de k alternatives. Pour chaque alternative x de X,l’ensemble accepté par i des propriétés possédées par x est défini de la façon suivante :

Six = conc(arg) | arg ∈ CS(i) et conc(arg) est un couple (alternative/propriété)

Pour chaque alternative x de X, la connaissance du groupe sur x est ensuite définie dela façon suivante :

Sx =⋂

i∈N

Six

Définition 1.25 [ Nouvelles propriétés désirables ]

Soit N un ensemble de n agents, chaque agent i de N possède un ensemble de pro-priétés désirablesWi. Soit P un ensemble de propriétés désirables issu de la délibération.Quel que soit i dans N , les nouvelles propriétés désirables de i, W ′i , sont définies de lafaçon suivante :

W ′i = (Wi ∪ P)\(p ∈Wi, np ∈ P ∪ np ∈Wi, p ∈ P)

Définition 1.26 [ Nouvelles connaissances des agents ]

Soit N un ensemble de n agents, chaque agent i de N possède pour chaque al-ternative x de X, un ensemble Si

x de propriétés supposées possédées par x. À l’issuede la délibération, chaque alternative x de X est associée à un ensemble de propriétéssupposées possédées par x construit par le groupe. Les nouvelles connaissances S′ix de isur x sont les suivantes :

Pour tout i dans N et tout x dans X,

S′ix = (Six ∪ Sx)\(p ∈ Si

x, np ∈ Sx ∪ np ∈ Six, p ∈ Sx)


Définition 1.27 [ Nouvelles relations de préférence ]

Soit N un ensemble de n agents, chaque agent i de N possède un nouvel ensemblede propriétés désirables W ′i . Soit X un ensemble de k alternatives, chaque alternativex de X est associée, pour chaque agent i de N , à un nouvel ensemble S′ix de propriétéssupposées possédées.Soit i un agent de N et soient x et y deux alternatives de X. Les nouvelles préférencesde i sont les suivantes : on dira que l’agent i préfère x à y (x ′i y) si et seulement si :

|p ∈ S′ix , p ∈W ′i| ≥ |p ∈ S′iy , p ∈W ′i|

Si i préfère x à y et ne préfère pas y à x, alors i préfère strictement x à y (x ′i y),sinon i est indifférent entre x et y (x ∼′i y).

A.3. RÉSULTATS 57

A.3 RésultatsDéfinition 1.28 [ Proximité à la single peakedness - Compatibilité maximum ]

Soit N = 1, . . . , n un ensemble de n agents. Chaque agent i de N possède unensemble i de préférences sur un ensemble d’alternatives. Soit M un sous-ensemble deN maximum pour l’inclusion tel que le profil de préférences M = ∪i∈M i est singlepeaked. Le profil de préférences N associé aux agents de N a une proximité à la singlepeakedness de τsp = |M |

n

Définition 1.29 [ Proximité à la single peakedness - Candidat unificateur ]

Soit X = A,B,C un ensemble de trois alternatives. Les classements possibles surces alternatives sont les suivants :

c Classement1 A B C2 B A C3 A C B4 C A B5 B C A6 C B A

Soit nc le nombre d’agents ayant classé ces alternatives selon le classement c. Ondéfinit la valeur de,

Min(n1 + n2, n3 + n4, n5 + n6)

comme la proximité du profil de préférences à la single peakedness.

Définition 1.30 [ Proximité à la separability into two groups - Candidat polarisant ]

Soit X = A,B,C un ensemble de trois alternatives. Soit nc le nombre d’agentsayant classé ces alternatives selon le classement c. On définit la valeur de,

Min(n3 + n5, n1 + n6, n2 + n4)

comme la proximité du profil de préférences à la separability into two groups.


Définition 1.31 [ Proximité à la triple wise value restriction ]

Soit X = A,B,C un ensemble de trois alternatives. Soit nc le nombre d’agentsayant classé ces alternatives selon le classement c. On définit,

Min(Min(n1 + n3, n2 + n5, n4 + n6),Min(n3 + n5, n1 + n6, n2 + n4),Min(n1 + n2, n3 + n4, n5 + n6),)

comme la proximité du profil de préférences à la triple wise value restriction.

Définition 1.32 [ Propriété problématique ]

Soit N = 1, . . . , n un ensemble de n agents, chaque agent i possède un ensembleWi de propriétés désirables. Soit W =

⋂i∈N Wi l’ensemble des propriétés consensuelle-

ment désirées par les agents. Soit p une propriété de⋃

i∈N Wi, p est problématique si etseulement si p n’appartient pas à W.

B

Annexes - Expérimentations supplémentaires

B.1 Évolution proximité à la single cavedness

Figure B.1 – Proximité à la single cavedness : 200 agents.

Figure B.2 – Proximité à la single cavedness : 20 agents.

59

Bibliographie

[1] Robert Alexy. A theory of practical discourse. The communicative ethics contro-versy, pages 151–190, 1990.

[2] Leila Amgoud, Yannis Dimopoulos, and Pavlos Moraitis. Making decisions throughpreference-based argumentation. In Gerhard Brewka and Jérôme Lang, editors,Principles of Knowledge Representation and Reasoning : Proceedings of the Ele-venth International Conference, KR 2008, Sydney, Australia, September 16-19,2008, pages 113–123. AAAI Press, 2008.

[3] Abdallah Arioua and Madalina Croitoru. Dialectical characterization of consistentquery explanation with existential rules. In FLAIRS Conference, pages 621–625,2016.

[4] Kenneth J Arrow. A difficulty in the concept of social welfare. Journal of politicaleconomy, 58(4) :328–346, 1950.

[5] Kenneth J Arrow. Social choice and individual values. Wiley, 1951.

[6] Philippe Besnard and Anthony Hunter. Elements of argumentation, volume 47.MIT press Cambridge, 2008.

[7] Duncan Black. The median voter theorem. The Journal of Political Economy,56(1) :23–34, 1948.

[8] Douglas H Blair, Georges Bordes, Jerry S Kelly, and Kotaro Suzumura. Im-possibility theorems without collective rationality. Journal of Economic Theory,13(3) :361–379, 1976.

[9] Madalina Croitoru and Srdjan Vesic. What can argumentation do for inconsistentontology query answering ? In International Conference on Scalable UncertaintyManagement, pages 15–29. Springer, 2013.

[10] Marie-Jean-Antoine-Nicolas Caritat Marquis de Condorcet. Essai sur l’applicationde l’analyse à la probabilité des décisions rendues à la pluralité des voix. L’impri-merie royale, 1785.

61

62 BIBLIOGRAPHIE

[11] Vincenzo Denicolò. Independent decisiveness and the arrow theorem. Social Choiceand Welfare, 15(4) :563–566, 1998.

[12] Franz Dietrich and Christian List. Where do preferences come from? InternationalJournal of Game Theory, 42(3) :613–637, 2013.

[13] Alejandro J García, Nicolás D Rotstein, Mariano Tucat, and Guillermo R Simari.An argumentative reasoning service for deliberative agents. In International Confe-rence on Knowledge Science, Engineering and Management, pages 128–139. Sprin-ger, 2007.

[14] William V Gehrlein. Consistency in measures of social homogeneity : A connectionwith proximity to single peaked preferences. Quality and Quantity, 38(2) :147–171,2004.

[15] William V Gehrlein. Probabilities of election outcomes with two parameters : therelative impact of unifying and polarizing candidates. Review of Economic Design,9(4) :317–336, 2005.

[16] Jürgen Habermas. Moral consciousness and communicative action. MIT press,1990.

[17] Ken-ichi Inada. A note on the simple majority decision rule. Econometrica : Journalof the Econometric Society, pages 525–531, 1964.

[18] Eric M Kok, John-Jules Ch Meyer, Henry Prakken, and Gerard AW Vreeswijk.A formal argumentation framework for deliberation dialogues. In InternationalWorkshop on Argumentation in Multi-Agent Systems, pages 31–48. Springer, 2010.

[19] Christian List. Mission impossible ? : the problem of democratic aggregation in theface of Arrow’s theorem. PhD thesis, University of Oxford, 2001.

[20] Christian List, Robert C Luskin, James S Fishkin, and Iain McLean. Deliberation,single-peakedness, and the possibility of meaningful democracy : evidence from de-liberative polls. The journal of politics, 75(1) :80–95, 2012.

[21] Peter McBurney, David Hitchcock, and Simon Parsons. The eightfold way of de-liberation dialogue. International Journal of Intelligent Systems, 22(1) :95–132,2007.

[22] Richard G Niemi. Majority decision-making with partial unidimensionality. Ame-rican Political Science Review, 63(2) :488–497, 1969.

[23] John R Searle. Speech acts : An essay in the philosophy of language, volume 626.Cambridge university press, 1969.

[24] Amartya Sen. Quasi-transitivity, rational choice and collective decisions. The Re-view of Economic Studies, 36(3) :381–393, 1969.

[25] Amartya K Sen. A possibility theorem on majority decisions. Econometrica :Journal of the Econometric Society, pages 491–499, 1966.

BIBLIOGRAPHIE 63

[26] Yuqing Tang and Simon Parsons. Argumentation-based dialogues for deliberation.In Proceedings of the fourth international joint conference on Autonomous agentsand multiagent systems, pages 552–559. ACM, 2005.

[27] Douglas Walton and Erik CW Krabbe. Commitment in dialogue : Basic conceptsof interpersonal reasoning. SUNY press, 1995.

Documents

Choix Social et Délibération - staff.science.uva.nl