Computing the cheapest winning coalition in a multi-agent game - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance
Master Thesis Year : 2010

Computing the cheapest winning coalition in a multi-agent game

Abstract

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 and versions

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

Identifiers

  • HAL Id : dumas-00530790 , version 1

Cite

Loïs Vanhée. Computing the cheapest winning coalition in a multi-agent game. Computer Science and Game Theory [cs.GT]. 2010. ⟨dumas-00530790⟩
91 View
681 Download

Share

More