Bruce Shepherd


Relevant Degree Programs

Affiliations to Research Centres, Institutes & Clusters


Graduate Student Supervision

Master's Student Supervision (2010 - 2020)
On the core of the multicommodity flow game without side payments (2019)

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.

View record


Membership Status

Member of G+PS
View explanation of statuses

Program Affiliations


If this is your researcher profile you can log in to the Faculty & Staff portal to update your details and provide recruitment preferences.


Sign up for an information session to connect with students, advisors and faculty from across UBC and gain application advice and insight.