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
26 pages, August 19, 2020
Full text files
dpbe7_2020.pdfFull text
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 ().
This page generated on 2024-02-05 17:13:32.