Relevant Degree Programs
Affiliations to Research Centres, Institutes & Clusters
Graduate Student Supervision
Master's Student Supervision (2010 - 2020)
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 initiallyintroduced by Papadimitriou to model incentives in internet routing. He posed thequestions of whether such stable solutions exist and if we can find them. Markakisand 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. Yamadaand Karasawa provide an algorithm for generating one core solution in the specialcase 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 testcore membership efficiently in this same special case. We empirically characterizethis larger set of solutions. The data suggests that stability does not necessarilyimpede efficiency, and that there is little trade-off between efficiency and fairness.