{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:38:49Z","timestamp":1760236729074,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T00:00:00Z","timestamp":1639612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>When several Nash equilibria exist in the game, decision-makers need to refine their choices based on some refinement concepts. To this aim, the notion of a \u03f5-proper equilibria set for polymatrix games is used to develop 0\u20131 mixed linear programs and compute \u03f5-proper Nash equilibria. A Branch-and-Bound exact arithmetics algorithm is proposed. Experimental results are provided on polymatrix games randomly generated with different sizes and densities.<\/jats:p>","DOI":"10.3390\/a14120365","type":"journal-article","created":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T11:27:36Z","timestamp":1639654056000},"page":"365","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Branch-and-Bound Algorithm for Polymatrix Games \u03f5-Proper Nash Equilibria Computation"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6567-2287","authenticated-orcid":false,"given":"Slim","family":"Belhaiza","sequence":"first","affiliation":[{"name":"Interdisciplinary Research Center on Smart Mobility and Logistics, Department of Mathematics, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1073\/pnas.36.1.48","article-title":"Equilibrium points in n-person games","volume":"36","author":"Nash","year":"1950","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF02293050","article-title":"A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra","volume":"8","author":"Avis","year":"1992","journal-title":"Discret. Comput. Geom."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/S1064827598339086","article-title":"Enumeration of all extreme equilibrium strategies of bimatrix games","volume":"23","author":"Audet","year":"2001","journal-title":"Siam J. Sci. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s10957-006-9070-3","article-title":"Enumeration of all Extreme Equilibria in Game Theory: Bimatrix and Polymatrix Games","volume":"129","author":"Audet","year":"2006","journal-title":"J. Optim. Theory Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1137\/070699652","article-title":"The complexity of computing a Nash equilibrium","volume":"39","author":"Daskalakis","year":"2009","journal-title":"Siam J. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1137\/090766991","article-title":"How hard is it to approximate the best Nash equilibrium?","volume":"40","author":"Hazan","year":"2011","journal-title":"Siam J. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2531","DOI":"10.1137\/080720826","article-title":"On the complexity of Nash equilibria and other fixed points","volume":"39","author":"Etessami","year":"2010","journal-title":"Siam J. Comput."},{"key":"ref_8","first-page":"381","article-title":"Equilibrium points in polymatrix games","volume":"8","author":"Yanovskaya","year":"1968","journal-title":"Latv. Math. Collect."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1287\/mnsc.18.5.312","article-title":"Equilibria of polymatrix games","volume":"18","author":"Howson","year":"1972","journal-title":"Manag. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0124043","article-title":"Polymatrix games with joint constraints","volume":"24","author":"Eaves","year":"1973","journal-title":"Siam J. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1287\/mnsc.21.3.313","article-title":"Bayesian equilibria of finite two-person games with incomplete information","volume":"21","author":"Howson","year":"1974","journal-title":"Manag. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF01254291","article-title":"A Note on Polymatrix Games","volume":"18","author":"Quintas","year":"1989","journal-title":"Int. J. Game Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0167-6377(91)90015-H","article-title":"Copositive-plus Lemke Algorithm Solves Polymatrix Games","volume":"10","author":"Miller","year":"1991","journal-title":"Oper. Res. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","article-title":"Bimatrix equilibrium points and mathematical programming","volume":"11","author":"Lemke","year":"1965","journal-title":"Manag. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1137\/0121011","article-title":"Computing Equilibria of N-Person Games","volume":"21","author":"Wilson","year":"1971","journal-title":"Siam J. Appl. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0112033","article-title":"Equilibrium points of bimatrix games","volume":"12","author":"Lemke","year":"1964","journal-title":"Siam J. Appl. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1016\/S0165-1889(03)00108-8","article-title":"Computing Nash equilibria by iterated polymatrix approximation","volume":"28","author":"Govindan","year":"2004","journal-title":"J. Econ. Dyn. Control"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1134\/S0005117914040043","article-title":"Polymatrix games and Optimization Problems","volume":"75","author":"Strekalovskii","year":"2014","journal-title":"Autom. Remote Control"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1379759.1379762","article-title":"Computing Correlated Equilibria in Multi-Player Games","volume":"55","author":"Papadimitriou","year":"2008","journal-title":"J. ACM"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"937070","DOI":"10.1155\/2014\/937070","article-title":"Computing Perfect Nash Equilibria for Polymatrix Games","volume":"2014","author":"Belhaiza","year":"2014","journal-title":"Game Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01753236","article-title":"Refinements of the Nash equilibrium concept","volume":"7","author":"Myerson","year":"1978","journal-title":"Int. J. Game Theory"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.automatica.2011.07.013","article-title":"On Proper Refinement of Bimatrix Games Nash Equilibria","volume":"48","author":"Belhaiza","year":"2012","journal-title":"Automatica"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1007\/s10957-018-1273-x","article-title":"On the Performance of Managers and Controllers: A Polymatrix Game Approach for the Manager-Controller-Board of Directors\u2019 Conflict","volume":"177","author":"Belhaiza","year":"2018","journal-title":"J. Optim. Theory Appl."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01783413","article-title":"On the structure of the set of perfect equilibria in bimatrix games","volume":"15","author":"Borm","year":"1993","journal-title":"O-R Spektrum"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1142\/S021919890900242X","article-title":"A new sequence form approach for the enumeration and refinement of all extreme Nash equilibria for extensive form games","volume":"11","author":"Audet","year":"2009","journal-title":"Int. Game Theory Rev."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/s00199-009-0449-x","article-title":"Enumeration of Nash equilibria for two-player games","volume":"42","author":"Avis","year":"2009","journal-title":"Econ. Theory"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/365\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:49:54Z","timestamp":1760168994000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,16]]},"references-count":26,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["a14120365"],"URL":"https:\/\/doi.org\/10.3390\/a14120365","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,16]]}}}