direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

A game-theoretical Model for the Firefighter Problem

Hendrik Molter (Universitat Politecnica de Catalunya)

The Firefighter Problem was proposed in 1995 as a deterministic discrete-
time model for the spread (and containment) of a fire. It takes place on a
finite, undirected graph, where a fire breaks out at a predetermined node
at time-step zero. In each subsequent time-step a firefighter can be
placed on a non-burning node, permanently protecting the node from
catching fire. Then the fire spreads from all burning nodes to their non-
protected neighbors. The process end when the fire cannot spread any
further. The decisional version (Can more than a certain number of nodes
be saved?) is known to be NP-hard.

We introduce a game-theoretical model for the Firefighter Problem to
explore its computational complexity from a different angle. Our strategic
game considers as many players as time-steps. Each player decides where to
put the firefighter at his corresponding time-step. The goal of each
player is to save as many nodes as possible. The outcomes of this game
represent solutions to the classical Firefighter Problem.

We show that the Price of Anarchy is linear for general graphs, but it is
at most 2 for trees. We also analyze the quality of the equilibria when
coalitions among players are allowed.

Hendrik Molter
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras