Christian Trudeau, University of Windsor - October 2, 2019

Title: Stable source connection and matching problems as time-varying shortest path problems

Abstract: We extend the familiar shortest path problem by supposing that agents have time-varying demands. This potentially allows agents to combine their paths if their demands are complementary; for instance if one agent only needs a connection to the source in the summer while the other requires it only in the winter. We show that the resulting cost sharing problem always has a non-empty core, regardless of the number of agents and periods, the cost structure or the demand profile. We then exploit the fact that the model encompasses many well-studied problems to obtain or reobtain non-vacuity results for the cores of source-connection problems, (m-sided) assignment problems and minimum coloring problems.