{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T21:30:53Z","timestamp":1768253453591,"version":"3.49.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a branch-and-prune procedure for discrete Nash equilibrium problems with a convex description of each player\u2019s strategy set. The derived pruning criterion does not require player convexity, but only strict convexity of some player\u2019s objective function in a single variable. If satisfied, it prunes choices for this variable by stating activity of certain constraints. This results in a synchronous branching and pruning method. An algorithmic implementation and numerical tests are presented for randomly generated instances with convex polyhedral strategy sets and convex quadratic as well as non-convex quadratic objective functions.<\/jats:p>","DOI":"10.1007\/s10589-023-00500-4","type":"journal-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T19:01:37Z","timestamp":1688756497000},"page":"491-519","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A branch-and-prune algorithm for discrete Nash equilibrium problems"],"prefix":"10.1007","volume":"86","author":[{"given":"Stefan","family":"Schwarze","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9514-6317","authenticated-orcid":false,"given":"Oliver","family":"Stein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"key":"500_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492913000032","volume":"22","author":"P Belotti","year":"2013","unstructured":"Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numer. 22, 1\u2013131 (2013)","journal-title":"Acta Numer."},{"key":"500_CR2","unstructured":"Carvalho, M., Dragotto, G., Lodi, A., Sankaranarayanan, S.: The cut and play algorithm: Computing nash equilibria via outer approximations. Preprint arXiv:2111.05726v2 (2022)"},{"issue":"3","key":"500_CR3","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.1016\/j.ejor.2022.03.048","volume":"303","author":"M Carvalho","year":"2022","unstructured":"Carvalho, M., Lodi, A., Pedroso, J.P.: Computing equilibria for integer programming games. Eur. J. Oper. Res. 303(3), 1057\u20131070 (2022)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"500_CR4","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s10898-011-9727-9","volume":"53","author":"A Dreves","year":"2012","unstructured":"Dreves, A., Kanzow, C., Stein, O.: Nonsmooth optimization reformulations of player convex generalized Nash equilibrium problems. J. Glob. Optim. 53(4), 587\u2013614 (2012)","journal-title":"J. Glob. Optim."},{"issue":"1\u20132","key":"500_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s10107-007-0160-2","volume":"117","author":"F Facchinei","year":"2009","unstructured":"Facchinei, F., Fischer, A., Piccialli, V.: Generalized Nash equilibrium problems and Newton methods. Math. Program. 117(1\u20132), 163\u2013194 (2009)","journal-title":"Math. Program."},{"issue":"3","key":"500_CR6","first-page":"173","volume":"5","author":"F Facchinei","year":"2007","unstructured":"Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. Ann. Oper. Res 5(3), 173\u2013210 (2007)","journal-title":"Ann. Oper. Res"},{"issue":"2","key":"500_CR7","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10589-010-9331-9","volume":"50","author":"F Facchinei","year":"2011","unstructured":"Facchinei, F., Piccialli, V., Sciandrone, M.: Decomposition algorithms for generalized potential games. Comput. Optim. Appl. 50(2), 237\u2013262 (2011)","journal-title":"Comput. Optim. Appl."},{"key":"500_CR8","unstructured":"Harks, T., Schwarz, J.: Generalized nash equilibrium problems with mixed-integer variables. Preprint arXiv:2107.13298v2 (2022)"},{"issue":"6","key":"500_CR9","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1287\/opre.1110.0964","volume":"59","author":"M K\u00f6ppe","year":"2011","unstructured":"K\u00f6ppe, M., Ryan, C.T., Queyranne, M.: Rational generating functions and integer programming games. Oper. Res. 59(6), 1445\u20131460 (2011)","journal-title":"Oper. Res."},{"issue":"1","key":"500_CR10","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.S.: Potential games. Games Econom. Behav. 14(1), 124\u2013143 (1996)","journal-title":"Games Econom. Behav."},{"issue":"1","key":"500_CR11","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium points in n-person games. Proc. Natl. Acad. Sci. 36(1), 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"2","key":"500_CR12","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"JF Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"issue":"1","key":"500_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10288-014-0256-5","volume":"12","author":"M Pappalardo","year":"2014","unstructured":"Pappalardo, M., Mastroeni, G., Passacantando, M.: Merit functions: a bridge between optimization and equilibria. 4OR 12(1), 1\u201333 (2014)","journal-title":"4OR"},{"issue":"4","key":"500_CR14","doi-asserted-by":"publisher","first-page":"2190","DOI":"10.1137\/15M1052445","volume":"26","author":"S Sagratella","year":"2016","unstructured":"Sagratella, S.: Computing all solutions of Nash equilibrium problems with discrete strategy sets. SIAM J. Optim. 26(4), 2190\u20132218 (2016)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"500_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1080\/02331934.2018.1545125","volume":"68","author":"S Sagratella","year":"2019","unstructured":"Sagratella, S.: On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. Optimization 68(1), 197\u2013226 (2019)","journal-title":"Optimization"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00500-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00500-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00500-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T16:08:16Z","timestamp":1695830896000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00500-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["500"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00500-4","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"22 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the contents of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}