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

https://dumas.ccsd.cnrs.fr/dumas-00530790
Contributor : Co-Responsables Du Mri V. Gouranton Et S. Blazy <>
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

Identifiers

  • HAL Id : dumas-00530790, version 1

Citation

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

Share

Metrics

Record views

148

Files downloads

1064