Skip to Main content Skip to Navigation
Master Thesis

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.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Co-Responsables Du Mri V. Gouranton Et S. Blazy Connect in order to contact the contributor
Submitted on : Friday, October 29, 2010 - 7:58:46 PM
Last modification on : Monday, February 15, 2021 - 10:37:44 AM
Long-term archiving on: : Friday, October 26, 2012 - 12:45:49 PM


  • HAL Id : dumas-00530790, version 1


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



Record views


Files downloads