On Finding a Solution in the Core of a Multicommodity Flow Game on a Spider

Motivated by the development of an efficient and stable routing scheme for the Internet, Papadimitriou introduced a multicommodity flow game and raised the problem of whether the core of a multicommodity flow game is always nonempty. Markakis and Saberi settled the problem affirmatively. However, thier proof is not constructive, and it is not known how to find a solution in the core of the game, to the best of my knowledge. This paper presents a polynomial-time algorithm for finding a multicommodity flow game if G is a spider