Formation de coalitions répétée dans un contexte stochastique : protocoles et expérimentations - GREYC mad Access content directly
Theses Year : 2022

Repeated coalition formation in a stochastic context : protocols and experiments

Formation de coalitions répétée dans un contexte stochastique : protocoles et expérimentations

Abstract

This thesis focuses on the study of repeated stochastic coalitional games which allow to lift some strong assumptions often considered in classic coalition formation, such as the a priori knowledge of the utilities of the coalitions or the deterministic nature of these utilities. In the first part of this thesis, we have established a model of stochastic coalition formation, and we have proposed a protocol for learning the characteristic function on the basis of repeated games. We have also defined several solution concepts based on a notion of exploration-exploitation equilibrium. Experiments show that one of our concepts is as efficient as a greedy approach however without surpassing it. In the second part of this thesis, we have adapted a well-known multilateral negotiation protocol to the framework of coalition formation, and proposed strategies that are adapted to this framework, first in a distributed and then in a decentralized context. Then, we have extended this protocol to the case of repeated and stochastic games, with new strategies, for both distributed and decentralized contexts. An empirical analysis allowed us to show that our strategies are efficient in the distributed deterministic and stochastic settings.
Cette thèse porte sur l'étude des jeux de coalitions stochastiques répétés qui permettent de lever certaines hypothèses fortes souvent considérées dans les jeux classiques, comme la connaissance a priori des utilités associées aux coalitions ou la nature détermiste de ces utilités. Dans la première partie de cette thèse, nous avons établi un modèle de formation de coalitions stochastique, et nous avons proposé un protocole d’apprentissage de la fonction caractéristique sur la base de jeux répétés. Nous avons également défini plusieurs concepts de solution fondés sur une notion d’équilibre exploration-exploitation. Des expérimentations montrent qu'un de nos concepts est aussi efficace qu'une approche gloutonne sans toutefois la surpasser. Dans la seconde partie de cette thèse, nous avons adapté un protocole connu de négociations multilatérales au cadre de la formation de coalitions classique, et proposé des stratégies mieux adaptées à ce cadre, d’abord dans un contexte distribué, puis décentralisé. Ensuite, nous avons étendu ce protocole au cas des jeux répétés et stochastiques, avec de nouvelles stratégies, pour les contextes distribué et décentralisé. Une analyse empirique a permis de montrer que nos stratégies sont efficaces dans les cadre distribués déterministe et stochastique.
Fichier principal
Vignette du fichier
sygal_fusion_39167-gueneron-josselin_64006e84232d0.pdf (3.81 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)

Dates and versions

tel-04011230 , version 1 (02-03-2023)

Identifiers

  • HAL Id : tel-04011230 , version 1

Cite

Josselin Gueneron. Formation de coalitions répétée dans un contexte stochastique : protocoles et expérimentations. Apprentissage [cs.LG]. Normandie Université, 2022. Français. ⟨NNT : 2022NORMC252⟩. ⟨tel-04011230⟩
58 View
20 Download

Share

Gmail Facebook X LinkedIn More