{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T03:54:08Z","timestamp":1648526048806},"reference-count":34,"publisher":"Walter de Gruyter GmbH","issue":"2","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we present the application of the Differential Evolution (DE) algorithm to the problem of finding approximate Nash equilibria in matrix, non-zero sum games for two players with finite number of strategies. Nash equilibrium is one of the main concepts in game theory. It may be classified as continuous problem, where two probability distributions over the set of strategies of both players should be found. Every deviation from the global optimum is interpreted as Nash approximation and called \u03b5-Nash equilibrium. The main advantage of the proposed algorithm is self-adaptive mutation operator, which direct the search process. The approach used in this article is based on the probability of chosing single pure strategy. In optimal mixed strategy, every strategy has some probability of being chosen. Our goal is to determine this probability and maximize payoff for a single player.<\/jats:p>","DOI":"10.2478\/s13537-012-0008-6","type":"journal-article","created":{"date-parts":[[2012,6,27]],"date-time":"2012-06-27T18:46:30Z","timestamp":1340822790000},"source":"Crossref","is-referenced-by-count":2,"title":["A new evolutionary approach for computing Nash equilibria in bimatrix games with known support"],"prefix":"10.2478","volume":"2","author":[{"given":"Urszula","family":"Boryczka","sequence":"first","affiliation":[]},{"given":"Przemyslaw","family":"Juszczuk","sequence":"additional","affiliation":[]}],"member":"374","reference":[{"key":"8_CR1","volume-title":"Mathematical Methods of Game and Economic Theory","author":"J. Aubin","year":"1979","unstructured":"Aubin J., Mathematical Methods of Game and Economic Theory (North-Holland Publ. CO., New York, 1979)"},{"key":"8_CR2","unstructured":"Boryczka U., Juszczuk P., Klosowicz L., A Comparative Study of Various Strategies in Differential Evolution. KAEiOG 2009 \u2014 Evolutionary Computing and Global Optimization (Ed. J. Arabas, 19\u201326, Warszawa, 2009)"},{"key":"8_CR3","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.tcs.2009.09.023","volume":"411","author":"H. Bosse","year":"2010","unstructured":"Bosse H., Byrka J., Markakis E., New Algorithms for Approximate Nash Equilibria in Bimatrix Games, J. Theor. Comp. Sci., 411, 164\u2013173, 2010","journal-title":"J. Theor. Comp. Sci."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Chen X., Deng X., Settling the complexity of two-player nash equilibrium, In: Proceedings of 47th FOCS, 261\u2013272, 2006","DOI":"10.1109\/FOCS.2006.69"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Daskalakis C., Goldberg P., Papadimitriou C., The complexity of computing a nash equilibrium, In: Proceedings of STOC, 71\u201378, 2006","DOI":"10.1145\/1132516.1132527"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Daskalakis C., Mehta A., Papadimitriou C., A note on approximate Nash equilibria, Workshop on Internet and Network Economics, 297\u2013306, 2006","DOI":"10.1007\/11944874_27"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Daskalakis C., Mehta A., Papadimitriou C., Progress on approximate Nash equilibria. In: ACM Conference on Electronic Commerce, 355\u2013358, 2007","DOI":"10.1145\/1250910.1250962"},{"key":"8_CR8","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1145\/1461928.1461951","volume":"52","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis C., Goldberg P.W., Papadimitriou C., The complexity of computing a Nash equilibrium, Mag. Comm. ACM, 52, 89\u201397, 2009","journal-title":"Mag. Comm. ACM"},{"key":"8_CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/978-3-642-04170-9_7","volume":"252","author":"W. Froelich","year":"2009","unstructured":"Froelich W., Juszczuk P., Predictive Capabilities of Adaptive and Evolutionary Fuzzy Cognitive Maps \u2014 A Comparative Study, Studies in Comput. Int., 252, 153\u2013174, 2009","journal-title":"Studies in Comput. Int."},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Hammerstein P., Selten R., Handbook of game theory \u2014 Chapter Game theory and evolutionary biology (University of Bonn, 1994)","DOI":"10.1016\/S1574-0005(05)80060-8"},{"key":"8_CR11","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1109\/IITA.2009.301","volume":"3","author":"H. Jun","year":"2009","unstructured":"Jun H., Chun G., An Electronic Marketplace Based on Game Theory, In: Proceedings of the 2009 Third International Symposium on Intelligent Information Technology Application, 3, pp. 111\u2013114, 2009","journal-title":"Proceedings of the 2009 Third International Symposium on Intelligent Information Technology Application"},{"key":"8_CR12","unstructured":"Kaplan T., Dickhaut J., A Program for Finding Nash Equilibria (University of Minnesota, Department of Economics in its series Working papers, number 004)"},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0096-3003(91)90088-5","volume":"45","author":"I. Krohn","year":"1991","unstructured":"Krohn I., Moltzahn S., Rosenmuller J., Sudholter P., Wallmeier H.M., Implementing the modified LH algorithm, Appl. Math. Comput., 45, 31\u201372, 1991","journal-title":"Appl. Math. Comput."},{"key":"8_CR14","unstructured":"Lampinen J., Zelinka I., Mixed variable non-linear optimization by differential evolution, In: Proceedings of Nostradamus, 45\u201355, 1999"},{"key":"8_CR15","unstructured":"Lampinen J., Zelinka I., On stagnation of the differential evolution algorithm, In: Proceedings of Mendel, 6th International Mendel Conference on Soft Computing, 76\u201383, 2000"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C.E. Lemke","year":"1964","unstructured":"Lemke C.E., Howson J.T., Equilibrium Points of Bimatrix Games, J. Soc. Ind. Applied Math., 12, 413\u2013423, 1964","journal-title":"J. Soc. Ind. Applied Math."},{"key":"8_CR17","first-page":"1011","volume":"2","author":"Y. Li","year":"2003","unstructured":"Li Y. et al., Image Reconstruction of EIT using Differential Evolution Algorithm, In: Proceedings of the Twenty \u2014 Fifth IEEE Annual International Conference on Engineering in Medicine and Biology Society, 2, 1011\u20131014, 2003","journal-title":"Proceedings of the Twenty \u2014 Fifth IEEE Annual International Conference on Engineering in Medicine and Biology Society"},{"key":"8_CR18","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1016\/j.asoc.2004.01.005","volume":"4","author":"G.D. Magoulas","year":"2004","unstructured":"Magoulas G.D., Plagianakos V.P., Vrahatis M.N., Neural Network-BasedColonoscopic Diagnosis using On-Line Learning and Differential Evolution, Appl. Soft. Comput., 4, 369\u2013379, 2004","journal-title":"Appl. Soft. Comput."},{"key":"8_CR19","unstructured":"Richard D. McKelvey, Andrew M. McLennan, Theodore L. Turocy, Gambit: Software Tools for Game Theory, Version 0.2010.09.01. http:\/\/www.gambit-project.org , 2010"},{"key":"8_CR20","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1142\/S021919890600103X","volume":"8","author":"I. Milchtaich","year":"2006","unstructured":"Milchtaich I., Computation of completely mixed equilibrium payoffs in bimatrix games, Int. Game Theory Rev., 8, 483\u2013487, 2006","journal-title":"Int. Game Theory Rev."},{"key":"8_CR21","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J.F. Nash","year":"1951","unstructured":"Nash J.F., Non-cooperative games, Ann. Math., 54, 286\u2013295, 1951","journal-title":"Ann. Math."},{"key":"8_CR22","unstructured":"Nudelman E., Wortman J., Shoham Y., Leyton-Brown K., Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms, In: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2, 2004"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Ordeshook P., Game theory and political theory (Cambridge University Press, 1986)","DOI":"10.1017\/CBO9780511666742"},{"key":"8_CR24","unstructured":"Panagopoulou P., Spirakis P., Approximate and well-supported approximate Nash equilibria of random bimatrix games, In: Proceedings of the 11th Panhellenic Conference on Informatics, 56\u2013578, 2007"},{"key":"8_CR25","first-page":"2004","volume":"2","author":"S. Paterlini","year":"2004","unstructured":"Paterlini S., Krink T., High Performance Clustering with Differential Evolution, In: Proceedings of the IEEE Congress on Evolutionary Computation, 2, 2004\u20132011, 2004","journal-title":"Proceedings of the IEEE Congress on Evolutionary Computation"},{"key":"8_CR26","unstructured":"Porter R., Nudelman E., Shoham Y., Simple search methods for finding a Nash equilibrium, Games and Economic Behavior, 664\u2013669, 2004"},{"key":"8_CR27","unstructured":"Price K., Storn R., Lampinen J., Differential evolution: a practical approach to global optimization (Springer Verlag, 2005)"},{"key":"8_CR28","first-page":"495","volume":"2","author":"T. Sandholm","year":"2005","unstructured":"Sandholm T., Gilpin A., Conitzer V., Mixed-integer programming methods for finding Nash equilibria, In: Proceedings of the 20th national conference on Artificial intelligence, 2, 495\u2013501, 2005","journal-title":"Proceedings of the 20th national conference on Artificial intelligence"},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"Spirakis P., Tsaknakis H., An optimization approach for approximate Nash equilibria. In: WINE\u201907 Proceedings of the 3rd international conference on Internet and network economics, 42\u201356, 2007","DOI":"10.1007\/978-3-540-77105-0_8"},{"key":"8_CR30","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1023\/A:1008202821328","volume":"11","author":"R. Storn","year":"1997","unstructured":"Storn R., Price K., Differential evolution \u2014 a simple and effcient heuristic for global optimization over continuous spaces, J. Glob. Optimiz., 11, 341\u2013359, 1997","journal-title":"J. Glob. Optimiz."},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"Sureka A., Wurman P., Using tabu best-response search to find pure strategy nash equilibria in normal form games, In: 4th Int. joint conference on Autonomous agents and multiagent systems, 1023\u20131029, 2005","DOI":"10.1145\/1082473.1082628"},{"key":"8_CR32","unstructured":"Tennenholtz M., Game Theory and Artificial Intelligence, Springer Verlag, 2403, 34\u201352, 2002"},{"key":"8_CR33","unstructured":"Tsaknakis H., Spirakis P., A Graph Spectral Approach for Computing Approximate Nash Equilibria, ArXiv e-prints, 96\u201396, 2009"},{"key":"8_CR34","doi-asserted-by":"crossref","unstructured":"Widger J., Grosu D., Computing Equilibria in Bimatrix Games by Parallel Support Enumeration, International Symposium on Parallel and Distributed Computing, 250\u2013256, 2008","DOI":"10.1109\/ISPDC.2008.38"}],"container-title":["Open Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.2478\/s13537-012-0008-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.2478\/s13537-012-0008-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.2478\/s13537-012-0008-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T16:19:14Z","timestamp":1614529154000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.2478\/s13537-012-0008-6\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,1]]},"references-count":34,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.2478\/s13537-012-0008-6","relation":{},"ISSN":["2299-1093"],"issn-type":[{"value":"2299-1093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,1]]}}}