Computing the cheapest winning coalition in a multi-agent game - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance Accéder directement au contenu
Mémoires Année : 2010

Computing the cheapest winning coalition in a multi-agent game

Résumé

To run a company, employers need to hire people to realize a product, a sport coach can motivate some players intend to win a match, a designer have to force synchronization of some parallel processes to avoid deadlocking. In these examples, a device external to the global system tries to force the behavior of some agents, aiming at achieving a global objective. For realism purposes, we assume that forming a coalition has a cost that should be minimal. This cost models the fact that individuals of the coalition may be deviated from their original objective. Game theory is a vast field that addresses this kind of problem. In this work we focus on turn-based games, a simple and broadly explored branch of game theory. Turn-based games offer well-known tools, among which the most famous minmax algorithm where a constrained optimization problem is addressed [19]. The problem we aim at solving is to find a minimal cost coalition which enforces some position in a given set (the goal) to be eventually reached.
Fichier principal
Vignette du fichier
Vanhee_Lois.pdf (2.23 Mo) Télécharger le fichier
Loading...

Dates et versions

dumas-00530790 , version 1 (29-10-2010)

Identifiants

  • HAL Id : dumas-00530790 , version 1

Citer

Loïs Vanhée. Computing the cheapest winning coalition in a multi-agent game. Computer Science and Game Theory [cs.GT]. 2010. ⟨dumas-00530790⟩
77 Consultations
665 Téléchargements

Partager

Gmail Facebook X LinkedIn More