<figure><img src="image_1.png" /></figure>

JOSSELIN GUÉNERON, GRÉGORY BONNET

Un protocole de concessions monotones pour la formation distribuée de coalitions
Volume 5, n° 1 (2024), p. 9-34.

https://doi.org/10.5802/roia.63

© Les auteurs, 2024.

<figure><img src="image_2.png" /></figure>

Cet article est diffusé sous la licence

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_3.png" /></figure>

La Revue Ouverte d'Intelligence Artificielle est membre du
Centre Mersenne pour l'édition scientifique ouverte

www.centre-mersenne.org

e-ISSN : 2967-9672
# Un protocole de concessions monotones pour la formation distribuée de coalitions

Josselin Guéneron<sup>a</sup>, Grégory Bonnet<sup>a</sup>

<sup>a</sup> Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France
E-mail: josselin.gueneron@unicaen.fr, gregory.bonnet@unicaen.fr.

RÉSUMÉ. — Nous nous intéressons dans cet article à la conception d'un protocole de formation de coalitions distribué et générique. Pour ce faire, nous étudions une adaptation au cadre de la formation de coalitions d'un protocole de négociation multilatérale initialement proposé par Ulle Endriss. Ce protocole utilise un mécanisme de concession monotone et nous proposons, d'une part, une adaptation directe au problème de formation de coalitions et, d'autre part, deux nouvelles stratégies de concession qui prennent explicitement en compte la notion de coalition. Nous étudions par la suite comment différents critères influencent les performances du protocole, y compris en termes de types de concession décrivant des contraintes sur les propositions que les agents peuvent formuler. Nous montrons expérimentalement que nos deux stratégies tenant compte explicitement des coalitions sont efficaces lorsqu'elles sont associées aux trois types de concession qui minimisent les pertes, à savoir les types fort, égalitaire et Pareto.

MOTS-CLÉS. — Formation distribuée de coalitions, théorie des jeux, négociation.

Dans un système multi-agent (SMA), les agents ne sont pas toujours capables de réaliser certaines tâches seuls et doivent, pour les réaliser, décider de collaborer avec d'autres agents. Lorsque le système est composé d'agents rationnels (i.e. qui cherchent à maximiser son utilité) et égoïstes (i.e. qui définissent leur utilité par rapport à des gains personnels), décider avec qui collaborer est un problème de formation de coalitions. Dans ce cadre, les agents forment des groupes, appelés coalitions, afin de réaliser conjointement les tâches qui ne peuvent pas être traitées individuellement. La formation de coalitions est un processus en trois étapes : la recherche d'une structure de coalitions – c'est-à-dire d'un ensemble de coalitions acceptables (stable) pour tous les agents –, la formation de ces coalitions, et la répartition des gains entre les agents [15]. Toutefois, résoudre un problème de formation de coalitions de manière centralisée n'est pas viable pour certaines applications, telles que les chaînes logistiques [12] ou les réseaux électriques intelligents [13]. En effet, dans le domaine des réseaux électriques intelligents, la formation de coalitions est envisagée pour le partage de ressources au sein de micro-grilles, soit en interne en ses composants, soit en externe avec d'autres micro-grilles. Pour un consommateur, il s'agit par exemple de décider quel groupe constitué de quels producteurs d'énergie solliciter en fonction de son besoin et des modes de production de ces producteurs. Du côté des producteurs, la question du partage du profit réalisé se pose ; et les deux questions se rejoignent dans une optique où les producteurs sont aussi des consommateurs. Dans le même ordre
d'idée au sein des chaînes logistiques, la problématique de la constitution d'alliances de producteurs sachant l'influence de nombreux paramètres comme leur réputation, leurs coûts ou la complexité des tâches à réaliser est aussi modélisée comme un problème de formation de coalitions. Or, rechercher une structure de coalitions optimale, c'est-à-dire qui maximise le bien-être social et qui est stable, dans un cadre centralisé implique d'explorer le treillis des structures, dont la taille croît exponentiellement. Ceci est problématique pour les domaines d'application précédemment cités, les acteurs y sont justement, d'une part, nombreux et, d'autre part, en possibilité d'entrer ou de quitter le système et donc de remettre en cause les groupes qui ont été constitués.

Ainsi, former des coalitions de manière distribuée, voire décentralisée, devient alors intéressant, même si cela implique des redondances ou des coûts de communication et de coordination, pour pouvoir passer à l'échelle. Beaucoup de travaux sur la formation distribuée de coalitions ont été proposés dans la littérature, mais ils sont souvent spécifiques au contexte comme par exemple dans [22], ou comprennent des contraintes fortes [4]. Par exemple, certains travaux fixent une taille de coalition maximale [20], ou proposent des algorithmes pour des jeux spécifiques (par exemple ayant des propriétés particulières pour leur fonction caractéristique, i.e. la fonction qui associe une utilité à chaque coalition) [10]. D'autres travaux encore proposent des algorithmes distribués mais dont certaines parties sont toujours centralisées en raison de la présence d'un commisseur-priseur [21]. Une question qui se pose alors naturellement est celle de la formation distribuée de coalitions, sans contexte spécifique ni contraintes sur le modèle.

Nous proposons dans cet article un protocole distribué fondé sur des concessions monotones. Il s'agit d'une adaptation pour la formation de coalitions d'un protocole de concessions monotones proposé par Ulle Endriss [7] dans le contexte de négociations multilatérales. Dans ce protocole, les agents font des propositions et ensuite, selon une stratégie de concession qui caractérise quel agent doit concéder, les agents peuvent concéder et faire une autre proposition. Cette dernière suit également une autre stratégie qui caractérise quelles propositions seront acceptables pour les autres agents. Le point clé de notre contribution réside dans le fait que le protocole original ne considère des négociations qu'entre les agents individuellement, alors que dans la formation de coalitions nous devons prendre en compte des groupes d'agents, c'est-à-dire les coalitions. Nous adaptons en particulier les stratégies de concession en fonction non seulement des gains individuels mais aussi du gain des coalitions. Nous analysons ensuite expérimentalement notre protocole, en termes de partitions explorées, de prix de la stabilité et d'optimalité.

Cet article est une extension d'un article précédemment publié aux JFSMA 2022 [9] enrichi avec une justification formelle des stratégies des agents, ainsi que de nouvelles expérimentations à plus large échelle. Cet article est structuré comme suit. Dans la section 1, nous présentons les jeux de coalitions et les travaux relatifs à la formation distribuée de coalitions. Dans la section 2, nous faisons le lien entre négociation et formation de coalitions, puis nous décrivons notre protocole. Enfin, la section 3 est consacrée aux résultats expérimentaux.
# 1. FORMATION DE COALITIONS

## 1.1. APPROCHE CLASSIQUE

Quand les agents coopèrent, ils forment une *coalition*. Celle-ci produit un certain montant d''utilité qui est décrit au travers d'une *fonction caractéristique*. Une partition des agents en coalitions est appelée une *structure de coalitions*.

**DÉFINITION 1.1 (Jeu de coalitions).** — Un jeu de coalitions est un tuple $G = \langle N, v \rangle$ où $N = \{a_1, \dots, a_n\}$ est un ensemble d'agents, et $v: 2^N \to \mathbb{R}$ est la fonction caractéristique qui indique l'utilité $v(C)$ de chaque coalition $C \subseteq N$.

Nous considérons dans cet article les jeux à utilité transférable, c'est-à-dire les jeux où la valeur d'une coalition peut être répartie arbitrairement entre ses membres. Ainsi, une *solution* à un tel jeu est définie comme suit.

**DÉFINITION 1.2 (Solution).** — Une *solution* à un jeu de coalitions $G$ est un tuple $S_G = \langle CS, \vec{x} \rangle$ où $CS$ est une *structure de coalitions* de $N$, $\vec{x} = \{x_1, \dots, x_n\}$ est un vecteur de gains pour les agents où $x_i \ge 0$ est le gain de l'agent $a_i$.

Les agents étant supposés rationnels et égoïstes, i.e. ils cherchent à maximiser leur gain personnel, tous doivent accepter une solution lorsqu'elle est proposée, c'est-à-dire qu'ils ne doivent pas vouloir former ou rejoindre une autre coalition où ils gagneraient plus. Une solution acceptable par tous les agents est dite *stable*. Différents critères de stabilité peuvent être définis et l'ensemble des solutions à un jeu respectant un de ces critères est appelé un *concept de solution*.

Intéressons-nous au concept du cœur et sa généralisation, l'**ϵ-cœur** [11, 19]. Le cœur est l'ensemble des solutions $\langle CS, \vec{x} \rangle$ pour lesquels il n'existe aucune autre coalition qui pourrait être formée et qui produirait une utilité supérieure à la somme des gains de ses agents dans $\vec{x}$. Si le cœur peut être vide, il existe une variante non vide, appelée **ϵ-cœur**.

**DÉFINITION 1.3 (ϵ-cœur).** — Une *solution* $(CS, \vec{x})$ appartient à l'**ϵ-cœur** si et seulement si :

$$ \forall C \subseteq N, x(C) \ge v(C) - \epsilon \text{ avec } x(C) = \sum_{a_i \in C} x_i $$

Cette variante permet aux agents de réduire leur gain de la valeur $\epsilon$, dans le but de rendre une solution stable. Ainsi, nous utilisons dans cet article uniquement l'**ϵ-cœur**, car toute solution à un jeu est comprise dans un **ϵ-cœur** dès lors que l'on a un **ϵ** suffisamment grand, étant donné que $\epsilon$ représente la pire perte en termes de gain parmi les agents afin d'assurer la stabilité. Plus précisément, nous nous intéressons à l'**ϵ-cœur** ayant le plus petit $\epsilon$ pour lequel une solution existe, appelé le dernier cœur [6].

Trouver de manière exacte une solution qui appartient à un concept de solution est un problème d'optimisation complexe. Classiquement, une solution approchée est acceptable. Il s'agit alors de trouver une structure de coalitions qui maximise le bien-être social et qui est dite *optimale*. En effet, si un jeu à utilité transférable a un 0-cœur
non vide alors ces structures de coalitions optimales en font partie et tout vecteur de gain est acceptable [2]. L'approche classique pour trouver la structure de coalitions optimale, par exemple incarnée par l'algorithme de Rahwan et Jennings [14], consiste à débuter l'exploration par la *grande coalition* (qui contient tous les agents) puis la décomposer et évaluer si cette décomposition est bénéfique pour le bien-être social. Si c'est le cas, le bien-être social est enregistré puis la décomposition continue. Si la décomposition n'était pas bénéfique, l'algorithme revient en arrière et essaye une autre décomposition. Toutefois, cette approche soulève deux problèmes : le premier est que cette façon de faire n'est pas adéquate pour beaucoup d'applications réelles. En effet, dans des applications de grande taille par exemple, le nombre d'agents rend une résolution centralisée difficilement envisageable. La seconde est la structure maximisant le bien-être social n'est pas nécessairement stable, par exemple quand le cœur est vide [6]. Afin de répondre à ces deux problèmes, nous allons nous intéresser à des approches distribuées de formation de coalitions.

## 1.2. APPROCHE DISTRIBUÉE

Il existe beaucoup de travaux sur la formation distribuée de coalitions dans la littérature, mais ils sont souvent spécifiques au contexte ou imposent des contraintes fortes sur le jeu. Nous pouvons trouver des contraintes sur la fonction caractéristique, où la forme de celle-ci est connue [10, 21], ou des contraintes sur les solutions possibles, qui limitent par exemple arbitrairement la taille des coalitions [20] ou les restreignent au sein d'un graphe [4, 22]. Certains modèles incluent un commisseur-priseur qui orchestre le processus, ce qui est une forme de recentralisation [10, 20, 21].

Par exemple, Shehory et Kraus [20] forment des coalitions pour des problèmes d'allocation de tâches. Les agents ne connaissent que leur propre utilité et communique avec les autres agents pour calculer une utilité espérée pour chaque coalition. Le processus est le suivant : chaque agent crée une liste restreinte de coalitions de taille maximale fixée, auxquelles ils appartiennent et qu'ils souhaitent former. Ils contactent les agents impliqués afin d'estimer leurs valeurs. Chaque agent calcule localement une valeur appelée *poids*, fondée sur l'utilité espérée, le coût de formation et la taille de chaque coalition. Ensuite, la coalition avec le poids le plus faible est formée. Le processus est répété jusqu'à ce que tous les agents rejoignent une coalition. Les solutions sont considérées comme stables tant que les coalitions formées peuvent réaliser leurs tâches, même si ce ne sont pas des solutions optimales.

Certains travaux sont similaires à ceux de Shehory et Kraus [4, 10, 21, 22]. Des contraintes spatiales sont considérées : les agents sont capables de se localiser et de localiser les autres dans l'environnement d'une manière spatiale. Dans [10, 21], les agents établissent également des préférences sur les coalitions qu'ils souhaitent former, sans communication mais en utilisant des heuristiques, basées sur la proximité spatiale des autres agents dans le système, par exemple, ils peuvent calculer un coût pour la formation des différentes coalitions en fonction de la localisation de leurs membres. Ensuite, des négociations menées par un commissaire-priseur ont lieu, et les solutions acceptables sont celles qui produisent le plus de gains selon la répartition des tâches proposée.
Tošić *et al.* proposent également un protocole pour des problèmes d'allocation de tâches [22] avec des contraintes spatiales. Les agents peuvent communiquer, mais ces communications dépendent d'un graphe dynamique où les agents (représentés par les sommets) reliés par une arête sont ceux qui peuvent communiquer. Dans ce protocole, la recherche d'une solution implique la recherche de cliques maximales dans ce graphe où les agents basent leurs décisions sur les informations qu'ils ont échangées, telles que les compétences requises pour les tâches ou la valeur qu'ils attribuent aux tâches. Cette approche suppose également que les agents sont totalement collaboratifs et non égoïstes. Par conséquent, la recherche d'une solution peut se résumer à la recherche d'une structure de coalitions qui maximise le bien-être social.

Un travail plus récent avec le même type de contrainte est proposé par Bistaffa *et al.* [4]. La formation de coalitions est également limitée aux agents qui peuvent communiquer par l'intermédiaire d'un réseau de communication et qui utilisent des heuristiques pour décider avec quels autres agents ils souhaitent former une coalition. Comme ils supposent que leur protocole est destiné à des problèmes à grande échelle, ils n'utilisent pas de concepts de solution, mais garantissent que les solutions approximées sont de bonne qualité, sur la base du bien-être social.

## 2. UN PROTOCOLE DISTRIBUÉ

Nous avons présenté dans la section précédente les approches distribuées existantes pour la formation de coalitions. Toutefois, ces modèles supposent des contraintes fortes qui ne sont pas désirables pour la distribution, en particulier la présence de commissaire-priseurs [10, 20, 21]. Afin de s'abstraire de telles contraintes, il peut être pertinent de s'intéresser à un cadre plus large que celui de la formation de coalitions, à savoir la négociation multilatérale entre agents utilitaristes. Dans ce domaine, il existe un protocole proposé par Ulle Endriss [7] qui possède des propriétés intéressantes. Il ne suppose pas d'entité centrale, est distribué, et ne formule pas d'hypothèse sur la structure du système. De plus, de par son aspect monotone, ce protocole respecte un certain nombre de propriétés intéressantes dans le cadre des négociations multi-agents que nous présenterons en section 2.5.

### 2.1. PROTOCOLE DE NÉGOCIATION MONOTONE

Le protocole proposé par Ulle Endriss [7] est un protocole de négociation multilatérale entre agents utilitaristes, c'est-à-dire entre agents individuels devant trouver un accord commun concernant une répartition d'utilité entre eux. Pour cela, les agents présentent chacun une proposition de répartition puis négocient en suivant un protocole de concessions monotones. Au premier tour, chaque agent fait simultanément une proposition initiale, en proposant celle qui lui rapporte le gain le plus élevé. À chaque tour suivant, les agents peuvent maintenir leur proposition ou concéder. Un agent qui concède doit alors faire une nouvelle proposition. Les tours de concessions et de nouvelle proposition se succèdent ainsi de suite jusqu'à ce qu'un accord commun ou un conflit (aucun agent ne peut concéder) émerge. Les propositions sont définies comme suit.
**DÉFINITION 2.1 (Proposition).** — Une proposition $p_i = \{x_1, \dots, x_n\}$ de l'agent $a_i$ est un vecteur de gain où $x_j(p_i) \ge 0$ est le gain de $a_j$.

Ensuite, la deuxième étape implique deux concepts importants : la **stratégie de concession** et le **type de concession**. La première décrit comment les agents décident qui doit concéder, et la seconde décrit comment les concessions (i.e. les nouvelles propositions) doivent être faites. Les principales stratégies présentées par Endriss sont appelées *Willingness to Risk Conflict* (WRC) et *Product Increasing* (PI). Ces stratégies consistent à calculer une *Z-valeur* (pour valeur de Zeuthen) pour chaque agent afin de définir celui qui doit concéder : l'agent concédant est celui qui obtient la plus petite valeur.

La stratégie WRC décrit comment un agent juge le risque s'il concède, comparé à ce que les autres agents lui offrent. Autrement dit, l'agent qui concède est celui qui perd le moins de gain entre sa propre proposition et celles des autres.

**DÉFINITION 2.2 (Willingness to Risk Conflict).** — L'agent qui concède est l'agent $a_i$ pour qui la valeur $Z_{a_i}$ est la plus petite, où :

$$Z_{a_i} = \begin{cases} 1 & \text{si } x_i(p_i) = 0, \\ \frac{x_i(p_i) - \min_{\forall a_j \in N} x_i(p_j)}{x_i(p_i)} & \text{sinon.} \end{cases}$$

La stratégie PI, elle, favorise une distribution équitable, c'est-à-dire que l'agent qui distribue les gains le moins équitablement sera le premier à concéder. Toutefois, dans le cadre de propositions dont les utilités totales sont différentes, une répartition moins équitable peut prendre le dessus sur une proposition offrant moins d'utilité totale, c'est-à-dire que le bien-être social peut passer avant le bien-être individuel.

**DÉFINITION 2.3 (Product Increasing).** — L'agent qui concède est l'agent $a_i$ pour qui la valeur $Z_{a_i}$ est la plus petite, où :

$$Z_{a_i} = \prod_{\forall a_j \in N} x_j(p_i).$$

**Exemple 2.4.** — Soit l'ensemble d'agents $N = \{a_1, a_2, a_3\}$. Supposons des propositions $p_i$ ayant des utilités $x_j$ pour ces agents $a_j$. La table 2.1 présente le calcul des valeurs WRC et PI pour ces propositions. Ici, l'agent $a_1$ concédera si nous considérons la stratégie WRC, tandis que ce sera l'agent $a_3$ si nous considérons la stratégie PI. En effet selon la stratégie WRC, l'agent $a_1$ est celui qui prend le moins de risques à concéder car, dans le pire des cas, il perd environ 19 % de gain par rapport à sa proposition initiale alors que les agents $a_2$ et $a_3$ perdraient respectivement environ 68 % et 65 % par rapport à leurs propres propositions. Concernant la stratégie PI, l'agent qui concède est celui dont la répartition est la moins égalitaire pour un même gain total. Dans cet exemple, il s'avère que l'agent $a_3$ fait la proposition ayant le bien-être social le plus faible, ce qui a pour conséquence de le désigner comme celui devant concéder.
<table><caption>TABLE 2.1 – Exemple de propositions et de valeurs de concessions.</caption><thead><tr><th></th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>WRC</th><th>PI</th></tr></thead><tbody><tr><th>p<sub>1</sub></th><td>2,60</td><td>2,12</td><td>1,81</td><td>0,18</td><td>9,98</td></tr><tr><th>p<sub>2</sub></th><td>2,12</td><td>3,33</td><td>0,87</td><td>0,68</td><td>6,40</td></tr><tr><th>p<sub>3</sub></th><td>2,38</td><td>1,06</td><td>2,47</td><td>0,65</td><td>6,23</td></tr></tbody></table>

Les types de concession décrivent les différentes façons que les agents ont de concéder afin que leur nouvelle proposition soit acceptable pour les autres agents. Ces types sont fondés sur la différence entre le vecteur de gain de l'ancienne et celui de la nouvelle proposition. Les différents types sont les suivants :

* **Fort** : le gain de tous les autres agents croît,

* **Faible** : le gain d'un autre agent croît,

* **Pareto** : le gain des agents reste au moins égal, et croît pour au moins un,

* **Égalitaire** : le gain minimal des autres croît,

* **Utilitaire** : la somme des gains des autres croît,

* **Nash** : le produit des gains des autres croît,

* **Égocentrique** : le gain du concédant décroît.

Les types *fort*, *faible* et *égocentrique* représentent des concessions qui semblent naturelles d'imaginer dans des contextes de négociations. Il s'agit respectivement d'améliorer le gain de tous les autres agents afin d'avoir une proposition acceptable, d'améliorer le gain d'au moins un agent pour obtenir son approbation, et enfin de faire une proposition dans laquelle le gain de l'agent qui concède doit diminuer afin que les autres ne le jalousent pas. Les autres types de concession sont quant à eux inspirés de concepts liés à l'économie du bien-être. Le type *Pareto* ne considère par exemple que les concessions bénéfiques à au moins un agent et qui ne diminuent pas les gains des autres. Le type *égalitaire* n'autorise que les concessions qui augmentent le gain de l'agent le moins bien doté. Le type *utilitaire* cherche à maximiser le bien-être social, c'est-à-dire la somme des gains de tous les agents, indépedemment de leur répartition. Enfin, le type *Nash*, en cherchant à maximiser le produit des gains des agents, ne considère que les concessions qui réduisent les inégalités tout en donnant un poids aux gains individuels.

**Exemple 2.5.** — Reprenons les propositions de l'exemple 2.4. La notation $p_i \to p_j$ désigne le fait que l'agent $a_i$ concède et fait la même proposition que $a_j$ au pas de temps suivant. Les types de concession respectés par les propositions sont montrés dans le tableau 2.2. Par exemple, si l'agent $a_1$ concède et fait la même proposition que $a_2$ (ce qui correspond à la ligne $p_1 \to p_2$), alors sa concession n'est pas forte. En effet, dans sa précédente proposition, $a_3$ gagnait 1,81 tandis que désormais il gagnerait 0,87. En revanche, comme l'agent $a_2$ passent d'un gain de 2,12 à une de 3,33, cela correspond à une concession faible. Étant donné que le gain de l'agent $a_3$ a diminué dans cette proposition, il ne s'agit pas non plus d'une concession de type *Pareto*, ni égalitaire. En effet, l'agent $a_3$ était déjà celui qui gagnait le moins, et son gain n'est
pas augmenté. Comme la somme des gains de $a_2$ et $a_3$ est de 3,93 dans l'ancienne proposition et de 4,2 dans la nouvelle, la concession est utilitaire mais elle n'est pas de type Nash car le produit de ces gains est passé de 3,84 à 2,9. Enfin, la concession est aussi égocentrique car l'agent $a_1$ passe d'un gain de 2,6 à 2,12.

<table><caption>TABLE 2.2 – Exemples de concessions typées.</caption><thead><tr><th>$p_i \to p_j$</th><th>Fort</th><th>Fai.</th><th>Par.</th><th>Éga.</th><th>Uti.</th><th>Nash</th><th>Égo.</th></tr></thead><tbody><tr><td>$p_1 \to p_2$</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td></tr><tr><td>$p_1 \to p_3$</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td></tr><tr><td>$p_3 \to p_1$</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>$p_3 \to p_2$</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

Remarquons dans cet exemple que les agents formulent leurs nouvelles propositions comme étant celles d'autres agents. Ceci n'a que pour but d'illustrer les différents types de concession, les nouvelles propositions ne sont pas contraintes dans le protocole à se ramener à celles déjà en jeu.

Le protocole, les types et les stratégies de concessions ayant été désormais décrits, nous pensons qu'un parallèle peut être fait entre l'accord dans la négociation et la stabilité dans la formation de coalitions. En effet, chacun de ces termes caractérise le moment où les agents sont tous d'accord et ne désirent plus dévier d'une proposition. Les concessions représentent des agents qui acceptent un gain plus faible afin d'atteindre un état de stabilité, comme l'exprime le concept de l'ε-cœur qui auto-rise d'abandonner une part de gains pour éviter les déviations. Ainsi, nous proposons d'adapter ce protocole à la formation de coalitions. Il nous faut désormais définir comment les agents construisent leurs propositions et répartissent l'utilité d'une coalition entre ses membres (voir section 2.2), comment les agents décident de concéder en tenant compte de ce que cela implique sur le collectif (voir section 2.3), puis de spécifier chaque étape du protocole (voir section 2.4).

## 2.2. PROPOSITIONS ET GAINS

Nous devons dans un premier temps redéfinir ce qu'est une proposition pour qu'elle représente la solution d'un jeu. Chaque agent va donc proposer une structure de coalitions et un vecteur de gains.

**DÉFINITION 2.6 (Proposition).** — Étant donné un jeu $\mathcal{G}$, une proposition de l'agent $a_i$, notée $p_i$, est une solution $S_{\mathcal{G}} = \langle CS, \vec{x} \rangle$ où $\vec{x}$ est un vecteur de gains $\langle x_j^i \rangle$ où $C_j^i$ est la coalition de l'agent $a_j$ dans la proposition $p_i$.

Pour évaluer une proposition, nous devons définir comment les agents distribuent l'utilité produite par les coalitions. Nous supposons que les agents souhaitent négocier sur le gain qu'ils recoivent à la formation des coalitions. Nous pouvons toutefois noter
que lorsque les agents négocient ce gain au sein d'une coalition, la notion de structure n'a pas d'importance. En effet, les autres coalitions qui sont formées, et donc intégrées à la structure, n'ont pas d'impact sur le gain de la première. Ainsi, cette négociation interne à la coalition peut être vue comme une simple négociation multilatérale entre agents utilitaristes, c'est pourquoi le protocole d'Endriss peut être utilisé pour cette négociation.

Dans le protocole d'Endriss, il est fait l'hypothèse que le gain minimal d'un agent est 0. Cependant, pour produire une solution rationnelle dans le cadre de la formation de coalitions, il faut que les coalitions proposées génèrent assez d'utilité pour que chaque agent obtienne au moins l'utilité produite par sa coalition singleton. Nous faisons donc l'hypothèse que la valeur minimale pour chaque agent est le montant d'utilité produit par sa coalition singleton. Pour une coalition quelconque, la somme des valeurs singleton de ses membres est alors réservée, afin que les agents puissent négocier sur le reste, appelé le *surplus*.

**DÉFINITION 2.7 (Surplus).** — Le surplus $S_C$ d'une coalition $C$ est :

$$S_C = v(C) - \sum_{a \in C} v(a)$$

Il est intéressant de souligner le fait que nous pouvons utiliser une simple règle de répartition égalitaire de ce surplus au lieu d'exécuter le protocole, tout en obtenant le même résultat, comme l'indique le théorème suivant.

**THÉORÈME 2.8.** — *Soit une coalition C d'agents. L'application du protocole d'Endriss avec une stratégie PI et un type écocentrique pour la répartition des gains entre les membres de C est équivalent à attribuer à chaque agent une utilité égale à la valeur de leur coalition singleton plus une part égale du surplus de C.*

*Démonstration.* — Soit une coalition $C$ de $n$ agents rationnels négociant leurs parts d'utilité au sein de cette coalition dans un cadre à utilité transférable. Sachant qu'un agent n'acceptera pas un gain inférieur à la valeur de sa coalition singleton, toute solution proposant un tel partage sera de fait rejetée. L'espace des propositions pouvant mener à un accord est donc composé des propositions qui assurent à chaque agent une utilité égale à celle de sa coalition singleton, plus une part de surplus. La négociation se fait donc sur le surplus uniquement. Soit la stratégie PI décrivant le fait que l'agent faisant la proposition dont le produit des utilités est le plus petit concédera.

Rappelons l'inégalité arthimético-géométrique qui est définie comme :

$$\frac{x_1 + \cdots + x_n}{n} \ge \sqrt[n]{x_1 \times \cdots \times x_n}$$

Il n'y a égalité entre les termes que si, et seulement si, $x_1 = x_2 = \cdots = x_n$. Ainsi, et en se rappelant que la fonction racine est une fonction strictement croissante pour tout nombre réel positif, nous pouvons déduire que le produit est maximal lors de l'égalité $x_1 = x_2 = \cdots = x_n$.
Or, si nous reprenons la coalition C et son surplus $S(C)$. Soit une répartition (efficace) de ce surplus réparti entre $n$ agents : $\vec{x} = \{x_1, \dots, x_n\}$, où $x_i$ est la part de surplus de l'agent $a_i$. Alors sa somme est telle que $\sum_{a_i \in C} x_i = S(C)$, et cette coalition possède un surplus moyen tel que $\frac{x_1+\dots+x_n}{n}$. Pour une coalition donnée, cette moyenne arithmétique est constante (car $S(C)$ et $n$ constants), et donc la répartition maximisant le produit est lorsque tous les agents gagnent la même part de surplus, c'est-à-dire $x_1 = x_2 = \dots = x_n$. La Z-valeur de la stratégie PI atteint donc une valeur maximale (qui assure donc de ne pas concéder) avec une répartition égalitaire pour un surplus donné. L'espace des propositions étant infini dans un cadre à utilité transférable, les agents proposant toujours le gain maximal pour eux et concédant de manière égocentrique, la répartition vers laquelle on tend est donc la répartition totalement égalitaire du surplus, car celle-ci maximise le produit et la valeur de la stratégie. La répartition égalitaire du surplus entre les agents d'une coalition, en plus de l'utilité de leur coalition singleton, produit donc le même résultat que si le protocole d'Endriss avec la stratégie PI et le type égocentrique avait été appliqué. $\square$

Ainsi, appliquer la stratégie PI d'un protocole de concessions monotones au sein de la coalition revient à répartir l'utilité de la coalition de sorte que chaque agent appartenant à celle-ci gagne le montant d'utilité de sa propre coalition singleton, auquel le surplus moyen (le surplus divisé par le nombre d'agents de la coalition) est additionné. Nous considérons donc une règle de distribution des gains rationnelle et égalitariste sur le surplus. Par définition, les coalitions singleton ont un surplus de 0. La règle est égalitaire car le surplus est alors distribué égalitairement entre les agents. Formellement,

**DÉFinition 2.9** (Part de surplus). — La part de surplus $S_C^{a_i}$ d'un agent $a_i$ dans sa coalition C, est le surplus de C divisé par son nombre d'agents :

$$S_C^{a_i} = \frac{S_C}{|C|}.$$

**DÉFinition 2.10** (Règle de distribution). — Le gain de l'agent $a_i$ appartenant à la coalition C avec un surplus $S_C > 0$ est défini comme :

$$x_i^C = v(\{a_i\}) + S_C^{a_i}.$$

Nous pouvons souligner le fait que cette règle de distribution est rationnelle car les coalitions proposées génèrent nécessairement assez d'utilité pour offrir à chaque agent l'utilité produite par sa coalition singleton.

## 2.3. STRATÉGIES ET TYPES DE CONCESSION

À chaque pas de temps, les agents font des propositions, et suivant une stratégie de concession, un ou plusieurs agents doivent abandonner leurs propositions et en faire de nouvelles. Pour ceci, nous utilisons et adaptons la stratégie WRC présente dans les travaux d'Endriss. Nous ne considérons la stratégie PI qu'au travers de la règle de distribution. En effet, la stratégie PI n'est pas adaptée à la formation de coalitions car les utilités ne sont transférables qu'au sein d'une coalition (i.e. au sens de la règle de
distribution) et non pas entre coalitions, et les agents n'ont pas pour objectif de réduire
les inégalités entre coalitions. Nous proposons donc trois adaptations de WRC que
nous présentons ci-après : une stratégie est fondée sur les gains individuels des agents,
une sur l'utilité des coalitions, et une dernière basée sur le surplus des coalitions. Nous
les appelons respectivement WRC-classic, WRC-coalitions et WRC-surplus.

DÉFINITION 2.11 (WRC-Classic). — L'agent qui concède est l'agent $a_i$ pour qui la valeur $Z_{a_i}$ est la plus petite, où :

$$
Z_{a_i} = \frac{x_i(p_i) - \min_{\forall a_j \in N} x_i(p_j)}{x_i(p_i)}
$$

où $x_i(p_j)$ est le gain de l'agent $a_i$ dans la proposition $p_j$.

DÉFINITION 2.12 (WRC-Coalitions). — L'agent qui concède est l'agent $a_i$ pour
qui la valeur $Z_{a_i}$ est la plus petite, où :

$$
Z_{a_i} = \frac{\sum_{C_i} x_i(p_i) - \min_{\forall a_j \in N} x_i(p_j)}{\sum_{C_i} x_i(p_i)}
$$

où $x_{C_i}(p_j)$ est la somme des gains de tous les agents dans la coalition $C_i$ dans la proposition $p_j$, où $C_i$ est la coalition dans laquelle l'agent $a_i$ est dans sa propre proposition :

$$
x_{C_i}(p_j) = \sum_{a_k \in C_i} x_k(p_j).
$$

DÉFINITION 2.13 (WRC-Surplus). — L'agent qui concède est l'agent $a_i$ pour qui la valeur $Z_{a_i}$ est la plus petite, où :

$$
Z_{a_i} = \frac{S_{C_i}(p_i) - \min_{\forall a_j \in N} S_{C_i}(p_j)}{S_{C_i}(p_i)}
$$

où $S_{C_i}(p_j)$ est la somme des parts de surplus de tous les agents dans la coalition $C_i$ dans la proposition $p_j$, où $C_i$ est la coalition dans laquelle l'agent $a_i$ est dans sa propre proposition :

$$
S_{C_i}(p_j) = \sum_{a_k \in C_i} S_{C_k}^{a_k}
$$

où $C_k^j$ est la coalition de l'agent $a_k$ dans la proposition $p_j$.

L'exemple suivant met en lumière les différences entre ces trois stratégies.

Exemple 2.14. — Soit une fonction caractéristique $v$ définie comme suit :

$$
v = \left\{
\begin{array}{ll}
\{a_1\} = 0,83; & \{a_2\} = 0,74; \\
\{a_3\} = 0,04; & \{a_1, a_2\} = 5,02; \\
\{a_1, a_3\} = 0,81; & \{a_2, a_3\} = 2,51; \\
\{a_1, a_2, a_3\} = 2,65; &
\end{array}
\right\} .
$$

La table 2.3 donne un exemple de propositions et leurs Z-valeurs associées pour les trois stratégies. Comme nous pouvons le voir, l'agent qui concède (celui pour lequel
la Z-valeur est soulignée) n'est pas le même selon que nous considérons la stratégie WRC-Classic et les deux autres stratégies tenant compte de la notion de coalition. Remarquons que les mêmes propositions, celles de l'agent $a_1$ et l'agent $a_2$, produisent les mêmes Z-valeurs pour WRC-Coalitions et WRC-Surplus, ce qui n'est pas le WRC-Classic en raison de son point de vue individuel. Enfin, bien que cet exemple donne le même agent concédant pour WRC-Coalitions et WRC-Surplus, ce n'est pas le cas en général. En effet, si deux coalitions génèrent la même utilité, leurs cardinalités ainsi que les agents les composant peuvent être différents, et par conséquent elles peuvent avoir des surplus eux-aussi différents.

<table><caption>TABLE 2.3 – Exemple de propositions et de Z-valeurs.</caption><thead><tr><th>Ag.</th><th>Propositions</th><th>W-Clas.</th><th>W-Coal.</th><th>W-Surp.</th></tr></thead><tbody><tr><td>a<sub>1</sub></td><td>⟨{{a<sub>1</sub>, a<sub>2</sub>}<sub>a<sub>3</sub></sub>}; {2,555, 2,465, 0,04}⟩</td><td>0,6751</td><td>0,5149</td><td>0,7493</td></tr><tr><td>a<sub>2</sub></td><td>⟨{{a<sub>1</sub>, a<sub>2</sub>}<sub>a<sub>3</sub></sub>}; {2,555, 2,465, 0,04}⟩</td><td>0,3489</td><td>0,5149</td><td>0,7493</td></tr><tr><td>a<sub>3</sub></td><td>⟨{{a<sub>1</sub>}<sub>a<sub>2</sub>, a<sub>3</sub></sub>}; {0,83, 1,605, 0,905}⟩</td><td>0,9558</td><td>0,002</td><td>0,003</td></tr></tbody></table>

Dans toutes ces stratégies, la condition où $Z_{a_i} = 1$ (l'agent ne peut plus concéder) si l'agent $a_i$ ne gagne rien dans sa propre proposition est modifiée pour que $Z_{a_i} = 1$ si l'agent $a_i$ se propose lui-même dans sa coalition singleton ou dans toute coalition dont le surplus est nul. Une telle règle représente l'absence de coopération car aucun agent n'acceptera d'être irrationnel.

Enfin, quand un agent concède, il doit faire une nouvelle proposition selon un certain type. Nous n'avons pas besoin d'adapter ces types à la formation car ils s'appliquent parfaitement aux vecteurs de gains, sans nécessité de changement.

## 2.4. ÉTAPES DU PROTOCOLE

Maintenant que les propositions et les stratégies ont été définies dans la cadre de la formation de coalitions, nous pouvons détailler les étapes du protocole.

Afin de s'assurer que le protocole se termine, les agents ne doivent pas proposer à nouveau une proposition qui a déjà été rejetée. Pour cela, chaque agent va maintenir une liste noire des coalitions dont il ne peut plus faire partie, et une liste noire des structures de coalitions qu'il est inutile de reproposer. La taille de ces listes est au pire cas respectivement de $2^{n-1}$ coalitions et du n-ième nombre de Bell pour les structures de coalitions. Notons que, bien que ces tailles croissent drastiquement avec le nombre d'agents, les expérimentations de la section 3 montrent que seul un nombre beaucoup plus faible de structures de coalitions ont besoin d'être explorées.

Ainsi, les étapes du protocole sont les suivantes :

1. Chaque agent calcule le surplus des coalitions dont il peut faire partie,

2. Chaque agent crée une liste noire privée de coalitions et structures de coalitions,
(3) Au premier tour, chaque agent fait une proposition initiale en choisissant sa coalition, notée $C^*$, parmi celles qui maximisent sa part de surplus, puis en choisissant la structure de coalitions qui maximise le bien-être social, notée $CS^*$, et qui inclut la coalition choisie $C^*$,

(4) À chaque tour suivant, chaque agent garde sa proposition ou concède, selon sa stratégie de concession,

(5) Si un agent concède, la structure de coalitions précédente $CS^*$ est ajoutée à la liste noire, et l'agent essaye de construire une nouvelle proposition satisfaisant son type de concession avec une autre structure de coalitions $CS^{*'}$ qui inclut également sa coalition choisie $C^*$. Si une structure $CS^{*'}$ ne satisfait pas un type de concession, elle est ajoutée à la liste noire. S'il n'y a plus de structure de coalitions possible avec la coalition $C^*$, cette dernière est ajoutée à la liste noire, et l'agent choisit une autre coalition, $C^{*'}$, qui maximise sa part de surplus. Un agent qui propose une coalition $C^{*'}$ dont le surplus est égal à 0 se retire du processus car il ne pourra pas gagner quoique ce soit.

(6) Répéter à partir de l'étape (4) jusqu'à ce qu'un accord soit atteint ou qu'aucun agent ne reste dans le processus, c'est-à-dire qu'aucun agent ne puisse faire une proposition où il gagnerait quelque chose (nous appelerons ce cas un *conflit*).

Si aucun agent ne peut faire une nouvelle proposition, le processus s'arrête et le protocole retourne la structure de coalitions singleton. C'est donc un protocole distribué car les agents exécutent certaines étapes localement (construction des propositions, gestion de leurs listes noires privées, calcul des concédants) tout en ayant une connaissance globale des propositions qui ont été faites et donc de celles qu'il reste à faire.

## 2.5. PROPRIÉTÉS

Le protocole originel [7] respecte certaines propriétés intéressantes dans un cadre de système multi-agents, nous allons désormais étudier si ces propriétés sont également vérifiées pour notre protocole. Les propriétés considérées sont les suivantes :

**Terminaison** : le protocole de négociation termine toujours,

**Absence de blocage** : si aucun agent ne peut effectuer une action, alors le protocole est dans un état terminal,

**Vérifiabilité** : il est possible de vérifier que tous les agents respectent les règles du protocole,

**Confidentialité** : les agents peuvent garder des informations privées,

**Compositionnalité** : la composition de deux propositions consécutives suivant le même type de concession est également une proposition simple du même type.

Notre protocole respecte les trois premières propriétés. Étant donné que le nombre de structures de coalitions et le nombre d'agents sont finis, et que les agents ne peuvent pas faire deux fois la même proposition grâce à la liste noire, la propriété de *terminaison* est respectée pour tout type de concession. Et ce même pour les concessions *faibles*, qui
ne respectent pas la propriété dans le protocole originel en raison de boucles possibles
sur les mêmes propositions.

La propriété d'absence de blocage est respectée car, à chaque pas de temps, au
moins un agent doit concéder et, si un agent ne peut plus faire de proposition, celui-ci
quitte le jeu. Si aucun agent ne reste dans le jeu, nous nous retrouvons dans l'état
terminal de conflit, c'est-à-dire la formation de la structure de coalitions singleton.

La propriété de vérifiabilité est respectée car la fonction caractéristique et la règle
de distribution sont connues, tout comme les types et stratégies de concession. Chaque
agent peut donc vérifier les propositions des autres. Il peut également reconstituer leurs
listes noires, ce qui a pour conséquence que la propriété de confidentialité n'est pas
respectée.

Concernant la propriété de *compositionnalité*, tout comme dans le protocole d'En-
driss, celle-ci n'est pas respectée dans le cadre des concessions *faibles*. Prenons un
exemple à trois agents $a_1, a_2$ et $a_3$. Supposons que $a_1$ fera deux concessions consécu-
tives. Avant la première concession, $a_2$ est dans une coalition non-singleton. Lors de
la première concession, $a_2$ est proposé dans sa coalition singleton (et donc baisse en
gain) tandis que $a_3$ augmente en gain. Lors de la concession suivante, $a_3$ baisse en gain
tandis que $a_2$ revient dans une autre coalition non-singleton (et donc récupère du gain).
Cependant, rien n'empêche $a_2$ et $a_3$ d'avoir moins de gain dans la dernière proposition
qu'avant les concessions, et donc que la *compositionnalité* n'est pas nécessairement
respectée.

Notre protocole respecte donc en grande majorité les propriétés citées ci-dessus,
hormis la *compositionnalité* pour les concessions *faibles* et la *confidentialité*. Le type
*faible* autorise à augmenter le gain d'un agent au détriment de n'importe lequel ou de
tous les autres, ce qui n'est pas une hypothèse très raisonnable pour des agents égoïstes
et rationnels. C'est pourquoi il parait naturel de ne pas considérer ce type de concession,
d'autant plus que les expérimentations présentées dans la section suivante indiquent
que le type faible est un des deux types de concession les moins performants. En
revanche, la propriété de *confidentialité* peut être d'intérêt en fonction des applications
visées. Il s'agit donc là d'une perspective importante de ce travail.

3. EXPÉRIMENTATIONS

Afin d'évaluer si notre protocole est efficace, et surtout pour comparer les différents
types et stratégies de concession, nous procédons empiriquement. Nous générons des
jeux aléatoires avec différentes fonctions caractéristiques et appliquons le protocole
plusieurs fois sur chaque jeu, avec différents paramètres pour les agents. Ces paramètres
sont le type et la stratégie de concession utilisés.

3.1. PROTOCOLE EXPÉRIMENTAL

Nous construisons dans un premier temps 100 jeux différents avec des fonctions
caractéristiques uniques, pour 8 agents. Remarquons ici que nous nous limitons à
8 agents, non pas en raison de la complexité de notre protocole mais en raison du calcul combinatoire de la solution optimale pour le jeu afin de comparer notre protocole à celle-ci. C'est pourquoi dans un second temps, nous expérimentons sans nous comparer à la solution optimale en construisant 10 000 jeux différents – toujours avec des fonctions caractéristiques uniques – pour 10 agents. Le temps de calcul nécessaire pour faire exécuter notre protocole (sans calculer les mesures de performance) sur un jeu est d'environ 0,19 secondes en moyenne pour 8 agents, et d'environ 8 secondes en moyenne pour 10 agents. Le temps de calcul des solutions optimales se compte en dizaines de minutes pour un jeu à 8 agents, et en heures pour un jeu à 10 agents.

Nous avons ainsi deux phases expérimentales : une à petite échelle où nous comparons aux résultats optimaux, et une à plus large échelle où nous nous intéressons uniquement aux résultats de notre protocole.

Dans les deux cas, nous faisons l'hypothèse que les agents sont homogènes, c'est-à-dire qu'ils utilisent tous les mêmes stratégies et types de concession qui paramètrent le protocole. En effet, il est nécessaire que les agents aient la même stratégie de concession afin qu'ils soient tous d'accord sur qui concède, bien que ce ne soit pas le cas pour le type de concession. Toutefois, nous nous contentons de cette homogénéité pour cette première étude. Le protocole est ensuite exécuté sur chacun des jeux avec chaque couple de stratégie et type de concession possible.

Les fonctions caractéristiques sont tirées selon le modèle NDCS (Normally Distributed Coalition Structures) [16]. Ce modèle permet d'avoir des fonctions caractéristiques structurées, mais sans contraindre fortement le modèle comme avec des structures monotones ou superadditives [6]. Ainsi, l'utilité $v(C)$ de chaque coalition $C \subseteq N$ est tirée selon une loi normale $N(|C|, \sqrt{|C|})$. La fonction caractéristique est ensuite normalisée sur l'invervalle [0, 1].

## 3.2. MESURES DE PERFORMANCE

Afin d'évaluer notre modèle, nous définissons quatre mesures empiriques, respectivement fondées sur le dernier cœur, sur le meilleur $\epsilon$-cœur atteignable par notre protocole, le bien-être social, et le nombre de Bell, c'est-à-dire le nombre de partitions possibles pour un nombre d'agents donné [3, 17]. Les deux premières mesurent la distance entre les solutions trouvées par le protocole par rapport au dernier cœur, ce dernier comprenant les meilleures solutions stables que l'on puisse trouver. Ces mesures nous permettent d'évaluer la perte de stabilité due à la négociation et à notre règle de distribution spécifique du surplus. La troisième est le *prix de la stabilité* [1, 15], qui mesure le gain que les agents doivent abandonner, par rapport au bien-être social maximal, afin de former une structure stable. La dernière mesure le nombre de structures de coalitions qui ont été explorées, c'est-à-dire le nombre de structures qui ont été sélectionnées à un moment dans le protocole, sans être nécessairement proposées. Afin d'avoir des données commensurables et comparables, chaque mesure est définie comme un ratio, avec des valeurs comprises sur l'intervalle [0, 1].
La première mesure est le ratio entre la valeur $\epsilon$ de l'-$\epsilon$-cœur auquel appartient la solution trouvée par le protocole et la valeur $\epsilon$ du dernier cœur, c'est-à-dire le minimum atteignable. Cette mesure requiert toutefois de calculer la valeur du dernier cœur. Or, vérifier si cette valeur est inférieure à un $\epsilon$ donné est un problème $\Delta_2^P$-complet pour les jeux qui ne sont pas superadditifs comme ceux que nous considérons [8]. C'est pourquoi cette mesure ne sera utilisée que pour les expérimentations à petite échelle. Nous procédons par approximation : nous calculons pour un ensemble d'imputations discrétisé à $10^{-1}$ les valeurs $\epsilon$ minimales qui les feraient appartenir à un $\epsilon$-cœur et retournons la valeur minimale.

**DÉFINITION 3.1 (Ratio au dernier cœur).** — Étant donné un jeu $\mathcal{G}$, soient $\epsilon^*(\mathcal{G})$ la valeur $\epsilon$ du dernier cœur, et $\epsilon^P(\mathcal{G})$ la valeur $\epsilon$ de l'-$\epsilon$-cœur auquel appartient la solution retournée par le protocole. Le ratio au dernier cœur, noté $R^*(\mathcal{G})$, est défini par :

$$R^*(\mathcal{G}) = \frac{1 - \epsilon^P(\mathcal{G})}{1 - \epsilon^*(\mathcal{G})}.$$

Ainsi, un ratio au dernier cœur ayant pour valeur 1 signifie que la solution trouvée par le protocole appartient au dernier cœur du jeu, et donc est optimale au sens du concept de solution de l'-$\epsilon$-cœur. Si la valeur du ratio est inférieure à 1, cela signifie donc que la solution n'est pas optimale au sens de ce concept. Plus la valeur tend vers 0, moins la solution est proche du dernier cœur.

La seconde mesure est le ratio entre la valeur $\epsilon$ de l'-$\epsilon$-cœur auquel appartient la solution trouvée par le protocole et la valeur $\epsilon$ du meilleur $\epsilon$-cœur (c'est-à-dire ayant la valeur $\epsilon$ la plus faible) atteignable par notre protocole s'il couvre toutes les partitions possibles, selon notre règle de distribution.

**DÉFINITION 3.2 (Ratio à l'optimal-protocole).** — Étant donné un jeu $\mathcal{G}$, soient $\epsilon^P(\mathcal{G})$ la valeur $\epsilon$ de l'-$\epsilon$-cœur optimal selon notre protocole et la règle de distribution, et $\epsilon^P(\mathcal{G})$ la valeur $\epsilon$ de l'-$\epsilon$-cœur auquel appartient la solution retournée par le protocole. Le ratio à l'optimal-protocole, noté $R^P(\mathcal{G})$, est défini par :

$$R^P(\mathcal{G}) = \frac{1 - \epsilon^P(\mathcal{G})}{1 - \epsilon^P(\mathcal{G})}.$$

De la même manière que pour la mesure précédente, un ratio à l'optimal-protocole ayant une valeur de 1 signifie que la solution est optimale au sens des solutions que la règle de distribution de notre protocole permet de construire. Si la valeur du ratio est inférieure à 1, cela signifie que le protocole n'a pas retourné la meilleure solution qu'il aurait pu trouver. Plus la valeur tend vers 0, moins le protocole a été performant.

La troisième, définie par Anshelevich et al. [1], est le ratio entre le bien-être social de la solution trouvée par le protocole, qui est stable, et le bien-être social maximal pour le jeu.

**DÉFINITION 3.3 (Prix de la stabilité).** — Étant donné un jeu $\mathcal{G}$, soient $\Pi(\mathcal{G})$ l'ensemble de toutes les structures de coalitions pour $\mathcal{G}$, et $S_{\mathcal{G}}^P = \langle CS^P, \bar{x}^P \rangle$ une solution
au jeu $\mathcal{G}$ retournée par le protocole. Le prix de la stabilité pour cette solution, noté $PS(S_{\mathcal{G}}^p)$, est défini par :

$$PS(S_{\mathcal{G}}^p) = \frac{\sum_{C \in \mathcal{C}} S^p v(C)}{\max_{\pi \in \Pi(\mathcal{G})} \sum_{C' \in \pi} v(C')}$$

À nouveau, la valeur du prix de la stabilité à atteindre est 1. En effet, cela signifie que le bien-être social généré par la solution trouvée par le protocole est maximal pour le jeu, et aucune autre structure ne peut produire davantage de bien-être social. Une valeur inférieure à 1 signifie donc que le bien-être social n'est pas optimal, et moins le prix de la stabilité est proche de 1, moins le bien-être social est optimal. Remarquons qu'en général, il n'y a pas de raison pour qu'une solution stable soit aussi celle qui maximise le bien-être social.

La dernière mesure est la proportion de structures de coalitions explorées par le protocole, c'est-à-dire qui ont été proposées ou sélectionnées puis mises dans la liste noire durant le protocole, comparé au nombre total de structures possibles, donné par le nombre de Bell. Étant donné que chaque agent peut proposer chaque partition une seule fois, et que leur liste noire est individuelle, le treillis des structures de coalitions peut être exploré autant de fois qu'il y a d'agents.

**DÉFinition 3.4 (Ratio de Bell).** — Étant donné le nombre de partitions explorées par l'agent $a_i$ et le nombre de Bell, respectivement notés $p_e^i$ et $B_n$ (avec $n = |N|$), le ratio de Bell, noté $B^%$, est :

$$B^% = \frac{\sum_{i \in N} p_e^i}{n \times B_n} \quad \text{avec } B_{m+1} = \sum_{k=0}^{m} \binom{m}{k} B_k.$$

Ce ratio est légèrement différent dans sa lecture, car un ratio de Bell de 1 signifie simplement que toutes les structures de coalitions possibles ont été considérées (ou explorées) lors du protocole, et un ratio de 0 signifie qu'aucune structure n'a été considérée. Moins il y a de structures considérées, moins il y a de propositions et de tours de protocoles, et moins les listes noires des agents sont grandes. Ainsi, plus ce ratio est faible, plus le protocole est performant au regard des autres mesures.

Ces différentes métriques nous permettent donc d'évaluer différents aspects de notre protocole. Les ratios au dernier cœur et à l'optimal-protocole nous donnent une vision d'optimalité au sens du concept de solution de l'ϵ-cœur à deux niveaux : le premier évalue à quel point les agents ont trouvé une solution proche de l'optimal du jeu sans restriction, tandis que le deuxième se compare au dernier cœur du jeu en se restreignant aux solutions atteignables par notre protocole. Cela nous permet d'une part d'évaluer les solutions mais l'association des deux nous permet également de juger l'impact de notre règle de distribution sur l'optimalité. Par exemple, si le ratio à l'optimal-protocole est de 1 tandis que celui au dernier cœur ne l'est pas, cela signifie que la règle de distribution est probablement l'élément empêchant de s'approcher davantage d'une solution optimale. Concernant le prix de la stabilité, il est l'analogue du premier ratio pour l'optimalité au sens du bien-être social, c'est-à-dire la somme des
utilités des coalitions de la solution. En effet, le champ de recherche de la génération de structures de coalitions s'intéresse à la formation de la structure de coalitions générant le plus de bien-être social, indépendamment de la répartition au sein des coalitions. Cette mesure nous permet donc de mesurer la perte d'optimalité au sens du bien-être social, sachant que le bien-être social est un des critères de proposition d'une structure de coalitions dans notre protocole, bien que n'étant pas le principal critère. Enfin, sachant qu'un tel protocole a pour vocation de réduire au maximum le nombre de potentielles solutions considérées avant d'arriver à un consensus, le ratio de Bell nous permet de mesurer la quantité d'exploration que les agents ont dû effectuer durant leurs négociations. La complémentarité de ces différentes métriques nous permet donc d'avoir une vue d'ensemble sur les performances de notre protocole.

### 3.3. RÉSULTATS À PETITE ÉCHELLE

Les figures 3.1 et 3.2 montrent le ratio au dernier cœur, le ratio à l'optimal-protocole, le prix de la stabilité et le ratio de Bell pour chaque stratégie de concession possible, sur les jeux à 8 agents. La figure 3.1 montre les résultats pour les types de concession *faible, égocentrique, Nash, utilitaire et fort*, et la figure 3.2 les résultats pour les types *égalitaire et Pareto*. Les données sont triées sur le ratio de l'optimal-protocole du plus grand au plus petit, et les trois autres mesures suivent ce tri pour rester liées au jeu correspondant. Également, les figures sont présentées dans un ordre particulier qui permet au lecteur de constater une évolution entre les résultats en fonction des différents types de concession, de ce qui semble empiriquement le moins bon, vers le meilleur. Pour rappel, concernant les différentes mesures et leurs significations graphiques : plus le ratio de Bell, étiquetté *bell*, est proche de 0, moins il y a eu de partitions explorées. Pour les trois autres mesures, la meilleure valeur est 1. Pour le ratio au dernier cœur, étiquetté *least-core*, et le ratio à l'optimal-protocole, étiquetté *optimal*, cela signifie que les solutions retournées par le protocole sont respectivement présentes dans le dernier cœur du jeu, et présentes dans le dernier cœur du jeu connaissant la règle de distribution. Pour le prix de la stabilité, étiquetté *welfare*, cela signifie que les solutions retournées par le protocole maximisent le bien-être social. Si ces mesures s'éloignent de 1, cela montre une perte d'efficacité.

Tout d'abord, nous pouvons voir que la courbe du ratio de Bell a une forme similaire pour toutes les paires (type, stratégie). Nous pouvons estimer l'exploration moyenne sur tous les jeux à 10 %, indépendamment du type et de la stratégie de concession. De plus, nous pouvons voir qu'il n'y a pas de corrélation apparente entre le fait d'explorer et une meilleure stabilité, ni l'inverse. Concernant le ratio à l'optimal-protocole, nous pouvons voir que les stratégies et les types de concession influent sur les résultats. Avec les types de concession *égocentrique, faible, utilitaire et Nash*, le ratio à l'optimal-protocole atteint des pertes de 40 %, avec parfois des effondements atteignant les 60 % pour certaines paires de paramètres. Bien qu'elle comprenne les plus gros effondrements, la stratégie WRC-surplus comprend avec la stratégie WRC-coalitions le meilleur taux de valeurs optimales. Plus précisément, sur les trois derniers types de concession (*fort, égalitaire et Pareto*), la stratégie WRC-classic atteint des pertes
<figure><img src="image_4.png" /><figcaption>(a) Égo. / WRC-Classic</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) Égo. / WRC-Coalitions</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(c) Égo. / WRC-Surplus</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(d) Faible / WRC-Classic</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(e) Faible / WRC-Coalitions</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(f) Faible / WRC-Surplus</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(g) Util. / WRC-Classic</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(h) Util. / WRC-Coalitions</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(i) Util. / WRC-Surplus</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(j) Nash / WRC-Classic</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(k) Nash / WRC-Coalitions</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(l) Nash / WRC-Surplus</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>(m) Fort / WRC-Classic</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>(n) Fort / WRC-Coalitions</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(o) Fort / WRC-Surplus</figcaption></figure>

FIGURE 3.1 – Différents ratios pour un couple (Type / Stratégie) de concession.
<figure><img src="image_19.png" /><figcaption>(a) Égal. / WRC-Classic</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(b) Égal. / WRC-Coalitions</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(c) Égal. / WRC-Surplus</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(d) Pareto / WRC-Classic</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(e) Pareto / WRC-Coalitions</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(f) Pareto / WRC-Surplus</figcaption></figure>

FIGURE 3.2 – Différents ratios pour un couple (Type / Stratégie) de concession.

<figure><img src="image_25.png" /><figcaption>(a) Faible</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>(b) Nash</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>(c) Fort</figcaption></figure>

FIGURE 3.3 – Exemples de différences entre stratégies.

maximales d'environ 30 %, contre 20 % pour les deux autres stratégies. Ces deux stratégies ont donc les meilleurs résultats, avec environ 60 % des jeux avec un ratio à l'optimal-protocole de 1. Les deux dernières mesures, le ratio au dernier cœur et le prix de la stabilité, se comportent de la même manière, à savoir qu'elles comportent des pics d'effondrement sur les mêmes jeux. Pour les types *faible* et *égocentrique*, nous pouvons voir de grandes pertes d'efficacité (régulièrement au dessus de 30 %), et ce pour toutes les stratégies. En s'intéressant aux différences entre les stratégies sur ces types, nous pouvons voir que les pertes sont plus limitées avec WRC-coalitions. Les valeurs entre WRC-classic et WRC-surplus sont proches, bien que cette dernière semble décroître un peu moins. Pour les types *Nash* et *utilitaire*, les pertes sont moins grandes. Elles sont de l'ordre de 20 %, bien qu'il y ait des effondrements autour de 60 %, comme avec le ratio à l'optimal-protocole. Pour le type *Nash*, les pertes de bien-être social sont réduites avec WRC-classic, mais WRC-coalitions est légèrement meilleure pour le ratio au dernier cœur. Pour le type *utilitaire*, ce sont WRC-coalitions
et WRC-surplus qui minimisent les pertes sur les mesures. Enfin, pour les trois derniers types (fort, égalitaire et Pareto), elles semblent toutes similaires. Il y a en réalité des différences mineures sur le nombre de partitions explorées et le nombre de concessions effectuées, mais les résultats du protocole sont identiques. Ce phénomène vient, à notre avis, de la règle de distribution choisie, qui doit contraindre davantage ces types de concession et les rapproche donc sémantiquement. Toutefois, il doit être noté que ces trois types sont empiriquement meilleurs que les autres, et ce notamment avec les stratégies WRC-coalitions et WRC-surplus, où les pertes sur le ratio au dernier cœur atteignent moins souvent 20 %, et où le prix de la stabilité excède très rarement 10 % tout en étant souvent à 0 %, c'est-à-dire optimal.

La figure 3.3 compare le ratio à l'optimal-protocole des trois stratégies sur trois différents types de concession : faible, Nash et fort. Nous choisissons de montrer seulement ces trois types car comme montré sur les figures précédentes, la tendance des courbes est semblable pour certains types : faible et égocentrique, Nash et utilitaire, égalitaire, fort et Pareto. Les données affichées sont triées de la plus grande à la plus petite valeur de ratio à l'optimal-protocole avec la stratégie WRC-classic, et les valeurs pour les autres stratégies suivent ce tri en restant liées au jeu correspondant. La figure 3.3(a) montre des valeurs qui varient beaucoup, mais celles-ci décroissent moins et moins souvent pour WRC-coalitions. WRC-surplus semble être la moins bonne stratégie de ce cas. Concernant le type Nash, WRC-surplus semble également la pire stratégie, avec des pertes atteignant 60 %. Comme précédemment, WRC-coalitions semble être la meilleure. Pour le type fort, les valeurs s'effondrent beaucoup moins, avec une perte maximale de 30 % environ. Ici, WRC-coalitions et WRC-surplus semblent proches, et presque toujours plus efficaces que WRC-classic.

**CONCLUSION.** — Pour résumer, trois types de concession minimisent les pertes plus que les autres : fort, égalitaire et Pareto. Pour les stratégies, WRC-coalitions semble être celle avec les meilleurs résultats, suivie de près par WRC-surplus (qui manque cependant d'efficacité sur certains types de concession). Ces résultats sont cohérents : une perte d'optimalité due à la distribution et des stratégies adaptées plus efficaces.

## 3.4. RÉSULTATS À LARGE ÉCHELLE

Concernant les expérimentations sur les jeux construits avec 10 agents, les figures 3.1, 3.2 et 3.3 synthétisent les moyennes et les variances respectivement des ratios à l'optimal-protocole, le prix de la stabilité et le ratio de Bell. Pour rappel, le ratio au dernier-cœur n'est pas mesuré ici en raison de sa complexité de calcul. Suite aux résultats précédents soulignant le fait que WRC-surplus est légèrement moins performante que WRC-coalitions, nous nous concentrons sur cette dernière, toujours en comparaison à WRC-classic. Les pourcentages présents dans les tableaux représentent le pourcentage de jeux pour lesquels la valeur maximale a été atteinte pour le ratio à l'optimal-protocole et pour le prix de la stabilité, et le pourcentage de structures de coalitions explorées pour le ratio de Bell.
<table><caption>TABLE 3.1 – Résultats pour le ratio à l'optimal-protocole.</caption><thead><tr><th>Optimal</th><th colspan="2">WRC-Classic</th><th colspan="2">WRC-Coalitions</th></tr></thead><tbody><tr><td>Égal.</td><td>(0,9592; 0,0025)</td><td>33,54 %</td><td>(0,9764; 0,0012)</td><td>44,71 %</td></tr><tr><td>Pareto</td><td>(0,9584; 0,0029)</td><td>33,45 %</td><td>(0,9743; 0,0022)</td><td>44,51 %</td></tr><tr><td>Fort</td><td>(0,9592; 0,0025)</td><td>33,52 %</td><td>(0,9764; 0,0012)</td><td>44,71 %</td></tr><tr><td>Nash</td><td>(0,9394; 0,0061)</td><td>22,28 %</td><td>(0,9658; 0,0054)</td><td>41,83 %</td></tr><tr><td>Util.</td><td>(0,9371; 0,0063)</td><td>22,06 %</td><td>(0,9648; 0,0056)</td><td>41,60 %</td></tr><tr><td>Égo.</td><td>(0,8615; 0,0127)</td><td>10,08 %</td><td>(0,9304; 0,0053)</td><td>22,68 %</td></tr><tr><td>Faible</td><td>(0,8965; 0,0072)</td><td>8,61 %</td><td>(0,9100; 0,0066)</td><td>15,80 %</td></tr></tbody></table>

<table><caption>TABLE 3.2 – Résultats pour le prix de la stabilité.</caption><thead><tr><th>Stabilité</th><th colspan="2">WRC-Classic</th><th colspan="2">WRC-Coalitions</th></tr></thead><tbody><tr><td>Égal.</td><td>(0,9690; 0,0017)</td><td>34,89 %</td><td>(0,9806; 0,0008)</td><td>40,97 %</td></tr><tr><td>Pareto</td><td>(0,9681; 0,0022)</td><td>34,88 %</td><td>(0,9784; 0,0020)</td><td>40,67 %</td></tr><tr><td>Fort</td><td>(0,9690; 0,0017)</td><td>34,93 %</td><td>(0,9806; 0,0008)</td><td>40,97 %</td></tr><tr><td>Nash</td><td>(0,9531; 0,0054)</td><td>21,37 %</td><td>(0,9687; 0,0053)</td><td>32,27 %</td></tr><tr><td>Util.</td><td>(0,9566; 0,0054)</td><td>23,71 %</td><td>(0,9704; 0,0055)</td><td>34,69 %</td></tr><tr><td>Égo.</td><td>(0,8649; 0,0143)</td><td>11,71 %</td><td>(0,9336; 0,0051)</td><td>19,94 %</td></tr><tr><td>Faible</td><td>(0,9070; 0,0063)</td><td>6,10 %</td><td>(0,9095; 0,0058)</td><td>10,26 %</td></tr></tbody></table>

<table><caption>TABLE 3.3 – Résultats pour le ratio de Bell.</caption><thead><tr><th>Bell</th><th colspan="2">WRC-Classic</th><th colspan="2">WRC-Coalitions</th></tr></thead><tbody><tr><td>Égal.</td><td>(0,0778; 0,0053)</td><td>7,78 %</td><td>(0,0648; 0,0039)</td><td>6,48 %</td></tr><tr><td>Pareto</td><td>(0,0777; 0,0053)</td><td>7,77 %</td><td>(0,0648; 0,0039)</td><td>6,48 %</td></tr><tr><td>Fort</td><td>(0,0778; 0,0053)</td><td>7,78 %</td><td>(0,0648; 0,0039)</td><td>6,48 %</td></tr><tr><td>Nash</td><td>(0,0752; 0,0050)</td><td>7,52 %</td><td>(0,0604; 0,0036)</td><td>6,04 %</td></tr><tr><td>Util.</td><td>(0,0754; 0,0050)</td><td>7,54 %</td><td>(0,0615; 0,0038)</td><td>6,15 %</td></tr><tr><td>Égo.</td><td>(0,0750; 0,0050)</td><td>7,50 %</td><td>(0,0689; 0,0047)</td><td>6,89 %</td></tr><tr><td>Faible</td><td>(0,0708; 0,0044)</td><td>7,08 %</td><td>(0,0595; 0,0036)</td><td>5,95 %</td></tr></tbody></table>

En ce qui concerne le ratio à l'optimal-protocole, les moyennes pour chaque type de concession sont plus élevées pour WRC-coalitions, avec un écart-type plus faible. Ce dernier est cependant très faible, même avec WRC-classic. L'efficacité de WRC-coalitions est mise en évidence par le pourcentage de jeux atteignant un ratio de 1, qui est toujours meilleur avec les WRC-coalitions. De plus, on peut dire que près
de 45 % des jeux atteignant la meilleure solution possible au regard de la règle de distribution est un bon score. Nous pouvons cependant constater que le protocole est beaucoup moins efficace avec certains types, en particulier faible et égocentrique, qui atteignent respectivement 22,68 % et 15,60 % des jeux avec la meilleure solution avec WRC-coalitions. Les types les plus efficaces sont les types fort et égalitaire, suivis de très près par le type Pareto. En ce qui concerne le prix de la stabilité, les mêmes observations peuvent être faites. La stratégie WRC-coalitions atteint toujours de meilleures moyennes que WRC-classic, et l'écart-type est également très faible. Le pourcentage de jeux atteignant un prix de stabilité de 1 est un peu plus faible que les pourcentages du ratio à l'optimal-protocole, mais avec le même ordre : les types égalitaire et fort sont les meilleurs, suivis de très près par Pareto, tandis que les types égocentrique et faible sont de loin les moins bons. Enfin, en ce qui concerne le ratio de Bell, nous pouvons dire que le pourcentage de partition exploré par le protocole est faible, avec moins de 8 % pour tous les types et stratégies, avec un minimum de 5,95 % pour le type faible et WRC-coalitions. Cependant, nous pouvons souligner que WRC-classic produit plus d'exploration que WRC-coalitions, alors que ce dernier produit de meilleurs résultats. Nous pouvons donc en déduire qu'une meilleure exploration ne permet pas nécessairement d'obtenir de meilleurs résultats.

**CONCLUSION.** — Pour résumer, ce passage à l'échelle confirme les résultats précé-
demment obtenus sur les expérimentations avec 8 agents. Les trois types de concession
les plus performants, à savoir *fort*, *égalitaire* et *Pareto*, sont les mêmes, tout comme
ceux qui le sont les moins, à savoir *égocentrique* et *faible*. La stratégie WRC-coalitions
confirme également son efficacité contre WRC-classic en surpassant cette dernière
sur tous les types de concession et ce pour toutes les mesures de performance. La
présence parmi les types les plus performants des types *égalitaire* et *Pareto*, qui pour
rappel sont fondés sur des concepts de l'économie du bien-être, n'est pas surprenante.
Les concepts sur lesquels ils reposent sont particulièrement adaptés à un cadre de
négociation multilatérale entre agents utilitaristes, étant donné qu'ils permettent res-
pectivement d'améliorer la condition des agents les plus délaissés et d'améliorer la
condition d'un agent seulement si cela ne dégrade pas celle des autres. L'intérêt des
concessions améliorant les gains des autres agents se voit aussi dans la présence du
type *fort* parmi les meilleurs types de concession. Toutefois de manière surprenante,
le type *Nash* qui cherche tout à la fois à maximiser les gains individuels et minimiser
les inégalités ne fait pas partie des types de concession les plus performants. Ceci
peut s'expliquer par le contexte spécifique de la formation de coalitions : il peut exis-
ter des inégalités structurelles entre coalitions qui font que les concessions réduisant
les inégalités diminuent de manière trop importante les gains individuels des agents.
Enfin, un facteur important à prendre en compte dans le processus est également la
règle de distribution car, comme nous l'avons vu dans les expérimentations à 8 agents,
un nombre important de jeux atteignant un ratio à l'optimal-protocole de 1 (résultat
optimal pour notre protocole sachant la règle de distribution) n'atteignent pas un ratio
au dernier cœur de 1, signifiant que la règle de distribution ne permet pas d'atteindre
le dernier cœur du jeu. Étudier d'autres règles de distribution serait donc intéressant.
4. CONCLUSIONS ET PERSPECTIVES

Nous avons proposé un protocole distribué pour la formation de coalitions, fondé sur
un protocole de négociations monotones, pour lequel nous avons proposé de nouvelles
stratégies de concession. Nous avons montré que nos stratégies, et notamment WRC-
coalitions, sont plus performantes que la stratégie originelle lorsqu'elles sont associées
à certains types de concession qui minimisent les pertes (types *fort*, *égalitaire* et
*Pareto*). Ces résultats sont confirmés lors du passage à l'échelle sur un large ensemble
de 10 000 jeux. De la même manière, WRC-coalitions explore moins – son ratio de
Bell est plus faible – que WRC-classic, tout en ayant de meilleurs résultats.

Cependant, dans tous les cas, notre approche distribuée nécessite l'exploration d'un
grand nombre de structures de coalitions par chaque agent. Il serait donc intéressant de
décentraliser totalement le protocole, et d'analyser les pertes d'efficacité dues à cette
décentralisation. Toutefois une manière intuitive de décentraliser consisterait à limiter
les propositions des agents à des coalitions (et non pas des structures de coalitions)
et de les former dynamiquement dès qu'un groupe d'agents n'a pas de meilleure
proposition à formuler. Or, cela revient intuitivement à former de manière gloutonne
des coalitions sans coordination entre les agents, ce qui peut être très sous-optimal.
Cependant, coordonner les agents pour partager des informations, et donc prendre de
meilleures décisions localement, peut être problématique si nous désirons respecter la
propriété de confidentialité dans un cadre décentralisé.

Il est également important de souligner qu'une des limites principales réside dans
la règle de distribution, qui est modérément efficace en termes de stabilité par rapport
à l'e-cœur, comme le montrent les expérimentations sur 8 agents. En effet, la règle de
distribution ne permet d'explorer qu'une sous-partie de l'ensemble des solutions. Il
semble pertinent d'envisager d'autres règles de distribution, comme par exemple une
règle fondée sur une valeur de contribution marginale comme la valeur de Shapley [18].
En effet, ce type de valeur satisfait des propriétés d'équité qui peuvent être désirables
pour les agents. L'avantage de notre règle de distribution est cependant sa facilité à être
calculée ; mais, si calculer la valeur de Shapley est complexe, il existe des algorithmes
d'approximation efficaces [5] qui pourraient être intégrés au protocole.

Plus généralement, la sous-partie de l'espace des solutions explorée par notre
protocole dépend des interactions entre règle de distribution, stratégie de concession
et type de concession. Notre étude étant essentiellement empirique, il serait alors
intéressant de caractériser formellement les solutions atteignables pour identifier les
propriétés des solutions vers lesquelles notre protocole peut converger.

BIBLIOGRAPHIE

[1] E. ANSHELEVICH, A. DASGUPTA, J. KLEINBERG, É. TARDOS, T. WEXLER & T. ROUGHGARDEN, « The price of stability for network design with fair cost allocation », *SIAM Journal on Computing* **38** (2008), n° 4, p. 1602-1623.

[2] R. J. AUMANN & J. H. DREZE, « Cooperative games with coalition structures », *International Journal of Game Theory* **3** (1974), p. 217-237.

[3] E. T. BELL, « The iterated exponential integers », Ann. of Math. (2) **39** (1938), n° 3, p. 539-557.
[4] F. BISTAFFA, A. FARINELLI, J. CERQUIDES, J. RODRÍGUEZ-AGUILAR & S. D. RAMCHURN, « Algorithms for graph-constrained coalition formation in the real world », *ACM Transactions on Intelligent Systems and Technology* **8** (2017), n° 4, p. 1-24.

[5] J. CASTRO, D. GÓMEZ & J. TEJADA, « Polynomial calculation of the Shapley value based on sampling », *Computers & Operations Research* **36** (2009), n° 5, p. 1726-1730.

[6] G. CHALKIADAKIS, E. ELKIND & M. WOOLDRIDGE, *Computational aspects of cooperative game theory*, vol. 5, Synthesis Lectures on Artificial Intelligence and Machine Learning, n° 6, Springer Cham, 2011, 168 pages.

[7] U. ENDRISS, « Monotonic concession protocols for multilateral negotiation », in *5th International Joint Conference on Autonomous Agents and MultiAgent Systems*, 2006, p. 392-399.

[8] G. GRECO, E. MALIZIA, L. PALOPOLI & F. SCARCELLO, « On the complexity of the core over coalition structures », in *22nd International Joint Conference on Artificial Intelligence*, 2011, p. 216-221.

[9] J. GUÉNERON & G. BONNET, « Un protocole de concessions monotones pour la formation distribuée de coalitions », in *30<sup>es</sup> Journées Francophones sur les Systèmes Multi-Agents*, 2022, p. 31-40.

[10] L. KHALOUZADEH, N. NEMATBAKHSH & K. ZAMANIFAR, « A Decentralized Coalition Formation Algorithm among Homogeneous Agents », *Journal of Theoretical & Applied Information Technology* **22** (2010), n° 1, p. 35-42.

[11] R. MOCHAOURAB & E. A. JORSWIECK, « Coalitional games in MISO interference channels : Epsilon-core and coalition structure stable set », *IEEE Transactions on Signal Processing* **62** (2014), n° 24, p. 6507-6520.

[12] M. NAGARAJAN & G. SOŞIĆ, « Game-theoretic analysis of cooperation among supply chain agents : Review and extensions », *European Journal of Operational Research* **187** (2008), n° 3, p. 719-745.

[13] A. NAVON, G. BEN YOSEF, R. MACHLEV, S. SHAPIRA, N. R. CHOWDHURY, J. BELIKOV, A. ORDA & Y. LEVRON, « Applications of game theory to design and operation of modern power systems : a comprehensive review », *Energies* **13** (2020), article no. 3982.

[14] T. RAHWAN & N. R. JENNINGS, « An improved dynamic programming algorithm for coalition structure generation », in *7th International Joint Conference on Autonomous Agents and MultiAgent Systems*, 2008, p. 1417-1420.

[15] T. RAHWAN, T. MICHALAK, M. WOOLDRIDGE & N. R. JENNINGS, « Coalition structure generation : A survey », *Artificial Intelligence* **229** (2015), p. 139-174.

[16] T. RAHWAN, S. D. RAMCHURN, N. R. JENNINGS & A. GIOVANNUCCI, « An anytime algorithm for optimal coalition structure generation », *Journal of Artificial Intelligence Research* **34** (2009), p. 521-567.

[17] G.-C. ROTA, « The number of partitions of a set », *Amer. Math. Monthly* **71** (1964), p. 498-504.

[18] L. S. SHAPLEY, « A value for n-person games », in *Contribution to the Theory of Games* (H. Kuhn & A. Tucker, éds.), vol. 2, Princeton University Press, 1953, p. 303-317.

[19] L. S. SHAPLEY & M. SHUBIK, « Quasi-cores in a monetary economy with nonconvex preferences », *Econometrica : Journal of the Econometric Society* **34** (1966), p. 805-827.

[20] O. SHEHORY & S. KRAUS, « Methods for task allocation via agent coalition formation », *Artificial Intelligence* **101** (1998), n° 1-2, p. 165-200.

[21] M. SIMS, C. V. GOLDMAN & V. LESSER, « Self-organization through bottom-up coalition formation », in *2nd International Joint Conference on Autonomous Agents and MultiAgent Systems*, 2003, p. 867-874.

[22] P. TOŞIĆ & C. ORDONEZ, « Distributed protocols for multi-agent coalition formation : a negotiation perspective », in *8th International Conference on Active Media Technology*, 2012, p. 93-102.
**ABSTRACT.** — In this article, we are interested to design a distributed and generic coalition formation protocol. To this end, we study an adaptation of a multilateral negotiation protocol originally proposed by Ulle Endriss. This protocol uses a monotonic concession mechanism and we propose, on the one hand, a direct adaptation to the coalition formation problem and, on the other hand, two new concession strategies that explicitly take into account the notion of coalition. We then study how different criteria influence the performance of the protocol, including concession types describing constraints on the proposals agents can make. We show experimentally that our two strategies that explicitly take coalitions into account are efficient when they are associated with the three loss-minimizing concession types, namely the strong, egalitarian and Pareto types.

**KEYWORDS.** — Distributed coalition formation, Game theory, Negotiation.

Manuscrit reçu le 15 mai 2023, révisé le 7 décembre 2023, accepté le 9 février 2024.