A non-cooperative approach to the cost spanning tree problem

Abstract

We associate to each cost spanning tree problem a non-cooperative game, which is inspired by a real-life problem. We study the Nash equilibria and subgame perfect Nash equilibria of this game. We prove that these equilibria are closely related with situations where agents connect sequentially to the source.