Open Collections

On the core of the multicommodity flow game without side payments

University of British Columbia

In this thesis we investigate the core, or the set of stable solutions, of a cooperative game without side payments. This "multicommodity flow" game was initially introduced by Papadimitriou to model incentives in internet routing. He posed the questions of whether such stable solutions exist and if we can find them. Markakis and Saberi showed both how to solve this game in the setting with side payments, and that such stable solutions always exist with or without side payments. Yamada and Karasawa provide an algorithm for generating one core solution in the special case when the underlying transit graph is a path (as well as special cases of trees). We provide a new algorithm for generating more core elements and a method to test core membership efficiently in this same special case. We empirically characterize this larger set of solutions. The data suggests that stability does not necessarily impede efficiency, and that there is little trade-off between efficiency and fairness.

Text

2019-08-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/71389

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/