{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T15:23:49Z","timestamp":1771341829968,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>We study a market mechanism that sets edge prices to incentivize strategic agents to efficiently share limited network capacity. In this market, agents form coalitions, with each coalition sharing a unit capacity of a selected route and making payments to cover edge prices. Our focus is on the existence and computation of market equilibrium, where challenges arise from the interdependence between coalition formation among strategic agents with heterogeneous preferences and route selection that induces a network flow under integral capacity constraints. To address this interplay between coalition formation and network capacity utilization, we introduce a novel approach based on combinatorial auction theory and network flow theory. We establish sufficient conditions on the network topology and agents\u2019 preferences that guarantee both the existence and polynomial-time computation of a market equilibrium. Additionally, we identify a particular market equilibrium that maximizes utilities for all agents and the outcome is equivalent to the classical Vickrey-Clarke-Groves mechanism. Furthermore, we extend our results to multi-period settings and general networks, showing that when the sufficient conditions are not met, an equilibrium may still exist but requires more complex, path-based pricing mechanisms that set differentiated prices based on agents\u2019 preference parameters.<\/jats:p>","DOI":"10.1145\/3777901","type":"journal-article","created":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T11:52:11Z","timestamp":1763725931000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Market Design for Capacity Sharing in Networks"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1554-015X","authenticated-orcid":false,"given":"Saurabh","family":"Amin","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology","place":["Cambridge, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8585-6566","authenticated-orcid":false,"given":"Patrick","family":"Jaillet","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology","place":["Cambridge, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4100-0678","authenticated-orcid":false,"given":"Haripriya","family":"Pulyassary","sequence":"additional","affiliation":[{"name":"Cornell University","place":["Ithaca, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5334-4163","authenticated-orcid":false,"given":"Manxi","family":"Wu","sequence":"additional","affiliation":[{"name":"University of California Berkeley","place":["Berkeley, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,17]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Susanne Albers. 2009. On the value of coordination in network design. SIAM Journal on Computing 38 6 (2009) 2273\u20132302.","DOI":"10.1137\/070701376"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Nir Andelman Michal Feldman and Yishay Mansour. 2009. Strong price of anarchy. Games and Economic Behavior 65 2 (2009) 289\u2013317.","DOI":"10.1016\/j.geb.2008.03.005"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","unstructured":"Elliot Anshelevich Anirban Dasgupta Jon Kleinberg \u00c9va Tardos Tom Wexler and Tim Roughgarden. 2008. The price of stability for network design with fair cost allocation. SIAM Journal on Computing 38 4 (2008) 1602\u20131623.","DOI":"10.1137\/070680096"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Robert J. Aumann. 1959. Acceptable points in general cooperative n-person games. Contributions to the Theory of Games 4 40 (1959) 287\u2013324.","DOI":"10.1515\/9781400882168-018"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","unstructured":"Lawrence M. Ausubel and Paul Milgrom. 2006. The lovely but lonely Vickrey auction. Combinatorial Auctions 17 (2006) 22\u201326.","DOI":"10.7551\/mitpress\/9780262033428.003.0002"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"Lawrence M. Ausubel and Paul R. Milgrom. 2002. Ascending auctions with package bidding. The BE Journal of Theoretical Economics 1 1 (2002) 20011001.","DOI":"10.2202\/1534-5955.1019"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","unstructured":"Wolfgang W. Bein Peter Brucker and Arie Tamir. 1985. Minimum cost flow algorithms for series-parallel networks. Discrete Applied Mathematics 10 2 (1985) 117\u2013124.","DOI":"10.1016\/0166-218X(85)90006-X"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Markus Bl\u00e4ser and Lakshminarayanan Shankar Ram. 2008. Approximately fair cost allocation in metric traveling salesman games. Theory of Computing Systems 43 1 (2008) 19\u201337.","DOI":"10.1007\/s00224-007-9072-z"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134716"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","unstructured":"Ho-Lin Chen Tim Roughgarden and Gregory Valiant. 2010. Designing network protocols for good equilibria. SIAM Journal on Computing 39 5 (2010) 1799\u20131832.","DOI":"10.1137\/08072721X"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_31"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993708"},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","unstructured":"Sven de Vries James Schummer and Rakesh V. Vohra. 2007. On ascending vickrey auctions for heterogeneous objects. Journal of Economic Theory 132 1 (2007) 95\u2013118.","DOI":"10.1016\/j.jet.2005.07.010"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Richard J Duffin. 1965. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications 10 2 (1965) 303\u2013318.","DOI":"10.1016\/0022-247X(65)90125-3"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250924"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Ulrich Faigle S\u00e1ndor P. Fekete Winfried Hochst\u00e4ttler and Walter Kern. 1998. On approximately fair cost allocation in euclidean TSP games. Operations-Research-Spektrum 20 1 (1998) 29\u201337.","DOI":"10.1007\/s002910050049"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","unstructured":"Ulrich Faigle and Walter Kern. 1993. On some approximately balanced combinatorial cooperative games. Zeitschrift f\u00fcr Operations Research 38 2 (1993) 141\u2013152.","DOI":"10.1007\/BF01414210"},{"key":"e_1_3_2_19_2","unstructured":"Bryce L. Ferguson Dario Paccagnan Bary SR Pradelski and Jason R. Marden. 2023. Collaborative decision-making and the k-strong price of anarchy in common interest games. arXiv:2311.01379. Retrieved from https:\/\/arxiv.org\/abs\/2311.01379"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","unstructured":"Dimitris Fotakis Spyros Kontogiannis and Paul Spirakis. 2008. Atomic congestion games among coalitions. ACM Transactions on Algorithms 4 4 (2008) 1\u201327.","DOI":"10.1145\/1383369.1383383"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"Vasilis Gkatzelis Konstantinos Kollias and Tim Roughgarden. 2016. Optimal cost-sharing in general resource selection games. Operations Research 64 6 (2016) 1230\u20131238.","DOI":"10.1287\/opre.2016.1512"},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","unstructured":"Martin Gr\u00f6tschel L\u00e1szl\u00f3 Lov\u00e1sz Alexander Schrijver Martin Gr\u00f6tschel L\u00e1szl\u00f3 Lov\u00e1sz and Alexander Schrijver. 1993. The ellipsoid method. Geometric Algorithms and Combinatorial Optimization (1993) 64\u2013101.","DOI":"10.1007\/978-3-642-78240-4_4"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"Faruk Gul and Ennio Stacchetti. 1999. Walrasian equilibrium with gross substitutes. Journal of Economic Theory 87 1 (1999) 95\u2013124.","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"Bainian Hao and Carla Michini. 2024. The price of anarchy in series-parallel network congestion games. Mathematical Programming 203 1 (2024) 499\u2013529.","DOI":"10.1007\/s10107-022-01803-w"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Tobias Harks Martin Hoefer Anja Schedel and Manuel Surek. 2021. Efficient black-box reductions for separable cost sharing. Mathematics of Operations Research 46 1 (2021) 134\u2013158.","DOI":"10.1287\/moor.2020.1050"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","unstructured":"Tobias Harks and Konstantin Miller. 2011. The worst-case efficiency of cost sharing methods in resource allocation games. Operations Research 59 6 (2011) 1491\u20131503.","DOI":"10.1287\/opre.1110.0979"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Martin Hoefer. 2011. Competitive cost sharing with economies of scale. Algorithmica 60 4 (2011) 743\u2013765.","DOI":"10.1007\/s00453-009-9367-3"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","unstructured":"Ron Holzman and Nissan Law-Yone. 1997. Strong equilibrium in congestion games. Games and Economic Behavior 21 1-2 (1997) 85\u2013101.","DOI":"10.1006\/game.1997.0592"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","unstructured":"Ron Holzman and Dov Monderer. 2015. Strong equilibrium in network congestion games: Increasing versus decreasing costs. International Journal of Game Theory 44 3 (2015) 647\u2013666.","DOI":"10.1007\/s00182-014-0448-4"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"Nicole Immorlica Li Erran Li Vahab S. Mirrokni and Andreas S. Schulz. 2009. Coordination mechanisms for selfish scheduling. Theoretical Computer Science 410 17 (2009) 1589\u20131598.","DOI":"10.1016\/j.tcs.2008.12.032"},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","unstructured":"Ramesh Johari and John N. Tsitsiklis. 2004. Efficiency loss in a network resource allocation game. Mathematics of Operations Research 29 3 (2004) 407\u2013435.","DOI":"10.1287\/moor.1040.0091"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","unstructured":"Alexander S. Kelso Jr and Vincent P. Crawford. 1982. Job matching coalition formation and gross substitutes. Econometrica: Journal of the Econometric Society (1982) 1483\u20131504.","DOI":"10.2307\/1913392"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_43"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","unstructured":"Igal Milchtaich. 2006. Network topology and the efficiency of equilibrium. Games and Economic Behavior 57 2 (2006) 321\u2013346.","DOI":"10.1016\/j.geb.2005.09.005"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","unstructured":"Kazuo Murota. 1996. Valuated matroid intersection II: Algorithms. SIAM Journal on Discrete Mathematics 9 4 (1996) 562\u2013576.","DOI":"10.1137\/S0895480195280009"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","unstructured":"Kazuo Murota and Akihisa Tamura. 2003. Application of m-convex submodular flow problem to mathematical economics. Japan Journal of Industrial and Applied Mathematics 20 3 (2003) 257\u2013277.","DOI":"10.1007\/BF03167422"},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","unstructured":"Noam Nisan and Ilya Segal. 2006. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory 129 1 (2006) 192\u2013224.","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329625"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","unstructured":"Renato Paes Leme and Sam Chiu-wai Wong. 2020. Computing walrasian equilibria: Fast algorithms and structural properties. Mathematical Programming 179 1 (2020) 343\u2013384.","DOI":"10.1007\/s10107-018-1334-9"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337032"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","unstructured":"Jos AM Potters Imma J. Curiel and Stef H. Tijs. 1992. Traveling salesman games. Mathematical Programming 53 1 (1992) 199\u2013211.","DOI":"10.1007\/BF01585702"},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","unstructured":"Hans Reijnierse Anita van Gellekom and Jos AM Potters. 2002. Verifying gross substitutability. Economic Theory 20 4 (2002) 767\u2013776.","DOI":"10.1007\/s00199-001-0248-5"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_8"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","unstructured":"Stefan Ruzika Heike Sperber and Mechthild Steiner. 2011. Earliest arrival flows on series-parallel graphs. Networks 57 2 (2011) 169\u2013173.","DOI":"10.1002\/net.20398"},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","unstructured":"Arie Tamir. 1989. On the core of a traveling salesman cost allocation game. Operations Research Letters 8 1 (1989) 31\u201334.","DOI":"10.1016\/0167-6377(89)90030-8"},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","unstructured":"Alejandro Toriello and Nelson A. Uhan. 2013. On traveling salesman games with asymmetric costs. Operations Research 61 6 (2013) 1429\u20131434.","DOI":"10.1287\/opre.2013.1225"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804393"},{"key":"e_1_3_2_48_2","volume-title":"Mechanism Design: A Linear Programming Approach","author":"Vohra Rakesh V.","year":"2011","unstructured":"Rakesh V. Vohra. 2011. Mechanism Design: A Linear Programming Approach. Vol. 47. Cambridge University Press."},{"key":"e_1_3_2_49_2","doi-asserted-by":"crossref","unstructured":"Philipp von Falkenhausen and Tobias Harks. 2013. Optimal cost sharing for resource selection games. Mathematics of Operations Research 38 1 (2013) 184\u2013208.","DOI":"10.1287\/moor.1120.0567"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3777901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T14:44:07Z","timestamp":1771339447000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3777901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,17]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3777901"],"URL":"https:\/\/doi.org\/10.1145\/3777901","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,17]]},"assertion":[{"value":"2024-11-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}