Feasible Coalition Sequences

Tabajara Krausburg (Pontifical Catholic University of Rio Grande do Sul & Clausthal University of Technology), Jürgen Dix (Clausthal University of Technology), Rafael H. Bordini (Pontifical Catholic University of Rio Grande do Sul)

Abstract

We introduce the idea of a finite sequence of coalition formation games over a set of agents, and we call it Sequential Characteristic-Function Game (SCFG). We define the solution of such a game as a corresponding sequence of coalition structures that must be related by a given feasibility relation, so no coalition structure can be evaluated in isolation. A sequence satisfying this condition is called Feasible Coalition-Structure Sequence (FCSS). Such games can be a useful abstraction for modelling various scenarios, in particular those for real-world disaster management that we consider in this paper. We give an algorithm for computing an FCSS and evaluate it experimentally. Our results show that an SCFG can represent various classical variations of characteristic-function games, and our algorithm solves instances with a reasonable number of agents.