IMADA - Department of Mathematics and Computer Science |
We study Facility Location games played by n autonomous agents situated on the nodes of a network. Each agent orders installation of a facility at a node of the network and pays connection cost to the chosen node, and shares facility installation cost fairly with other agents having chosen the same location. This
game has pure strategy Nash equilibria, that can be found by simple improvements performed by the
agents iteratively. This game is a special case of recently studied network design games with fair cost
allocation (also known as Shapley cost allocation). We describe briefly these games and the questions that
arise in the context of their study. Subsequently we give an overview of our recent results on Facility
Location games, with respect to the overall cost of pure Nash equilibria, the complexity of the iterative
improvements procedure, and polynomial-time approximation of pure equilibria. Furthermore we also
study the overall cost of (approximate) strong equilibria, that generalize pure equilibria by being resilient
to coalitional pure deviations. Host: Jørgen Bang-Jensen SDU HOME | IMADA HOME | Previous Page Daniel Merkle |