On the core of the multicommodity flow game

On the core of the multicommodity flow game

0.00 Avg rating0 Votes
Article ID: iaor20051922
Country: Netherlands
Volume: 39
Issue: 1
Start Page Number: 3
End Page Number: 10
Publication Date: Mar 2005
Journal: Decision Support Systems
Authors: ,
Abstract:

In the work of Papadimitriou, he proposed a game theoretic framework for analyzing incentive issues in Internet routing. In particular, he defined the following coalitional game: Given a network with a multicommodity flow satisfying node capacity and demand constraints, the payoff of a node is the total flow originated or terminated at it. A payoff allocation is in the core of the game if and only if there is no subset of nodes that can increase their payoff by seceding from the network. We answer one of the open problems in the work of Papadimitriou by proving that for any network, the core is non-empty in both the transferable (where the nodes can compensate each other with side payments) and the non-transferable case. In the transferable cases, we show that such an allocation can be computed in polynomial time. We also generalize this result to the case where a strictly concave utility function is associated with each commodity.

Reviews

Required fields are marked *. Your email address will not be published.