{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:45Z","timestamp":1787341425351,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We study the sensitivity of optimal solutions of convex separable optimization problems over an integral polymatroid base polytope with respect to parameters determining both the cost of each element and the polytope. Under convexity and a regularity assumption on the functional dependency of the cost function with respect to the parameters, we show that reoptimization after a change in parameters can be done by elementary local operations. Applying this result, we derive that starting from any optimal solution, there is a new optimal solution to new parameters such that the $L_1$-norm of the difference of the two solutions is at most two times the $L_1$-norm of the difference of the parameters. We apply these sensitivity results to a class of noncooperative games with a finite set of players where a strategy of a player is to choose a vector in a player-specific integral polymatroid base polytope defined on a common set of elements. The players' private cost functions are regular, convex-separable, and the cost of each element is a nondecreasing function of the own usage of that element and the overall usage of the other players. Under these assumptions, we establish the existence of a pure Nash equilibrium. The existence is proven by an algorithm computing a pure Nash equilibrium that runs in polynomial time whenever the rank of the polymatroid base polytope is polynomially bounded. Both the existence result and the algorithm generalize and unify previous results appearing in the literature. We finally complement our results by showing that polymatroids are the maximal combinatorial structure enabling these results. For any nonpolymatroid region, there is a corresponding optimization problem for which the sensitivity results do not hold. In addition, there is a game where the players' strategies are isomorphic to the nonpolymatroid region and that does not admit a pure Nash equilibrium.<\/jats:p>","DOI":"10.1137\/16m1107450","type":"journal-article","created":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T11:26:00Z","timestamp":1533641160000},"page":"2222-2245","source":"Crossref","is-referenced-by-count":12,"title":["Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids"],"prefix":"10.1137","volume":"28","author":[{"given":"Tobias","family":"Harks","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Max","family":"Klimm","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Britta","family":"Peis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.035"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00172-N"},{"key":"atypb4","unstructured":"M. Beckmann, C. B. McGuire, and C. B. Winsten,\n                      Studies in the Economics and Transportation\n                      , Yale University Press, New Haven, CT, 1956."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9128-8"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582230"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0322"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.6.909"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.024"},{"key":"atypb10","unstructured":"S. Fujishige,\n                      Submodular Functions and Optimization\n                      , Elsevier, Amsterdam, 2005."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0825"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"key":"atypb13","first-page":"2687","author":"Gai Y.","year":"2011","journal-title":"NY"},{"key":"atypb14","first-page":"98","author":"Gairing M.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/1978782.1978786"},{"key":"atypb16","first-page":"142","author":"Goemans M. X.","year":"2005","journal-title":"NY"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(91)90300-K"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0543"},{"key":"atypb19","first-page":"189","author":"Harks T.","year":"2014","journal-title":"Berlin"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1000"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96597"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.872880"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600523"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/210346.210415"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"P. Krysta, P. Sanders, and B. Vo\u0308cking,\n                      Scheduling and traffic allocation for tasks with bounded splittability\n                      , in Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, B. Rovan and P. Vojtas, eds., Lect. Notes Comput. Sci. 2747, Springer, Heidelberg, Berlin, 2003, pp. 500-510.","DOI":"10.1007\/978-3-540-45138-9_44"},{"key":"atypb26","unstructured":"C. Meyers,\n                      Network Flow Problems and Congestion Games: Complexity and Approximation Results\n                      , Ph.D. thesis, MIT, Cambridge, MA, 2006."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0027"},{"key":"atypb28","first-page":"87","author":"Milchtaich I.","year":"2006","journal-title":"Berlin"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/080736156"},{"key":"atypb30","unstructured":"K. Murota,\n                      Discrete Convex Analysis: Monographs on Discrete Mathematics and Applications 10\n                      , Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0466-7"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030104"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"T. Roughgarden,\n                      Selfish Routing and the Price of Anarchy\n                      , MIT Press, Cambridge, MA, 2005.","DOI":"10.21236\/ADA637949"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"R. Srikant,\n                      The Mathematics of Internet Congestion Control\n                      , Birkha\u0308user, Basel, 2003.","DOI":"10.1007\/978-0-8176-8216-3"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.2.305"},{"key":"atypb37","unstructured":"D. M. Topkis,\n                      Supermodularity and Complementarity\n                      , Princeton University Press, Princeton, NJ, 1998."},{"key":"atypb38","first-page":"236","author":"Tran-Thanh L.","year":"2011","journal-title":"Berlin"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1680\/ipeds.1952.11259"},{"key":"atypb40","first-page":"89","author":"Yao D. D.","year":"2002","journal-title":"Berlin"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1107450","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:04Z","timestamp":1787339944000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1107450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1107450"],"URL":"https:\/\/doi.org\/10.1137\/16m1107450","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}