Scandinavian Working Papers in Economics

Discussion Papers on Economics,
University of Southern Denmark, Department of Economics

No 7/2020: Stable source connection and assignment problems as multi-period shortest path problems

Leanne Streekstra () and Christian Trudeau ()
Additional contact information
Leanne Streekstra: Department of Business and Economics, Postal: University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark
Christian Trudeau: Department of Economics, Postal: University of Windsor, 401 Sunset Avenue, Windsor, Ontario, Canada

Abstract: We extend the familiar shortest path problem by supposing that agents have demands over multiple periods. 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.

Keywords: Shortest path; demand over multiple periods; cooperative game; core; source-connection; assignment

JEL-codes: C71; D63

26 pages, August 19, 2020

Full text files 

dpbe7_2020.pdf PDF-file Full text

Download statistics

Questions (including download problems) about the papers in this series should be directed to Astrid Holm Nielsen ()
Report other problems with accessing this service to Sune Karlsson ().

RePEc:hhs:sdueko:2020_007This page generated on 2024-09-13 22:17:01.