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

No 7/2020, Discussion Papers on Economics from University of Southern Denmark, Department of Economics

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 (search for similar items in EconPapers)
JEL-codes: C71 D63 (search for similar items in EconPapers)
Pages: 26 pages
Date: 2020-08-19
New Economics Papers: this item is included in nep-des, nep-gth and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.sdu.dk/-/media/files/om_sdu/institutte ... _2020/dpbe7_2020.pdf Full text (application/pdf)

Related works:
Journal Article: Stable source connection and assignment problems as multi-period shortest path problems (2024)
Working Paper: Stable source connection and assignment problems as multi-period shortest path problems (2022)
Working Paper: Stable source connection and assignment problems as multi-period shortest path problems (2022)
Working Paper: Stable source connection and assignment problems as multi-period shortest path problems (2022)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:sdueko:2020_007

Access Statistics for this paper

More papers in Discussion Papers on Economics from University of Southern Denmark, Department of Economics Department of Economics, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Astrid Holm Nielsen ().