{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T01:00:48Z","timestamp":1776214848203,"version":"3.50.1"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T00:00:00Z","timestamp":1730937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/501100001807","name":"S\u00e3o Paulo Research Foundation","doi-asserted-by":"publisher","award":["2019\/07665-4"],"award-info":[{"award-number":["2019\/07665-4"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004316","name":"IBM Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,4,24]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>A Nash equilibrium is a strategy profile of a game in which none of the players involved has any gain by changing alone his\/her own strategy. Given a two-player game, we show a codification of all of its Nash equilibria into \u0141ukasiewicz infinitely-valued logic, that is, we derive a propositional theory in this logic whose models codify all the Nash equilibria. Based on such propositional theory, we derive a polynomial reduction from the problem of computing a Nash equilibrium to the problem of satisfiability of (sets of) formulas of \u0141ukasiewicz infinitely-valued logic. These applications of logic to game theory lead to new methods for computing Nash equilibria.<\/jats:p>","DOI":"10.1093\/logcom\/exae073","type":"journal-article","created":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T15:28:42Z","timestamp":1729006122000},"source":"Crossref","is-referenced-by-count":1,"title":["Nash meets \u0141ukasiewicz: computing equilibria through logic"],"prefix":"10.1093","volume":"35","author":[{"given":"Sandro","family":"Preto","sequence":"first","affiliation":[{"name":"\u00a0Center for Mathematics, Computing and Cognition, Federal University of ABC , Santo Andr\u00e9 09280-560 ,","place":["Brazil"]},{"name":"Institute of Mathematics and Statistics, University of S\u00e3o Paulo , S\u00e3o Paulo 05508-090 ,","place":["Brazil"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcelo","family":"Finger","sequence":"additional","affiliation":[{"name":"Institute of Mathematics and Statistics, University of S\u00e3o Paulo , S\u00e3o Paulo 05508-090 ,","place":["Brazil"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"2026041420080663600_ref1","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1093\/jigpal\/jzw004","article-title":"Representing strategic games and their equilibria in many-valued logics","volume":"24","author":"B\u011bhounek","year":"2016","journal-title":"Logic Journal of the IGPL"},{"key":"2026041420080663600_ref2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1516512.1516516","article-title":"Settling the complexity of computing two-player Nash equilibria","volume":"56","author":"Chen","year":"2009","journal-title":"Journal of the ACM"},{"key":"2026041420080663600_ref3","article-title":"Algebraic foundations of many-valued reasoning","volume-title":"Trends in Logic","author":"Cignoli","year":"2000"},{"key":"2026041420080663600_ref4","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1145\/800157.805047","article-title":"The complexity of theorem-proving procedures","volume-title":"Proceedings of the Third Annual ACM Symposium on Theory of Computing. STOC '71. Shaker Heights, Ohio","author":"Cook","year":"1971"},{"key":"2026041420080663600_ref5","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 Journal on Computing"},{"key":"2026041420080663600_ref6","first-page":"627","article-title":"Fuzzy logics with enriched language","volume-title":"Handbook of Mathematical Fuzzy Logic - Vol. 2","author":"Esteva","year":"2011"},{"key":"2026041420080663600_ref7","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 Journal on Computing"},{"key":"2026041420080663600_ref8","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exad059","article-title":"Polyhedral semantics and the tractable approximation of \u0141ukasiewicz infinitely-valued logic","author":"Finger","year":"2023","journal-title":"Journal of Logic and Computation"},{"key":"2026041420080663600_ref9","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.ijar.2020.12.023","article-title":"On standard completeness and finite model property for a probabilistic logic on \u0141ukasiewicz events","volume":"131","author":"Flaminio","year":"2021","journal-title":"International Journal of Approximate Reasoning"},{"key":"2026041420080663600_ref10","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1016\/j.fss.2006.11.008","article-title":"A logic for reasoning about the probability of fuzzy events","volume-title":"Fuzzy Sets and Systems","author":"Flaminio","year":"2007"},{"key":"2026041420080663600_ref11","doi-asserted-by":"publisher","first-page":"103337","DOI":"10.1016\/j.apal.2023.103337","article-title":"Encoding de Finetti\u2019s coherence within \u0141ukasiewicz logic and MV-algebras","volume-title":"Annals of Pure and Applied Logic","author":"Flaminio","year":"2024"},{"key":"2026041420080663600_ref12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"Goldreich","year":"2008"},{"key":"2026041420080663600_ref13","first-page":"237","article-title":"Fuzzy logic and probability","volume-title":"Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence","author":"H\u00e1jek","year":"1995"},{"key":"2026041420080663600_ref14","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":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"2026041420080663600_ref15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2783436","article-title":"\u0141ukasiewicz games: A logic-based approach to quantitative strategic interactions","volume":"16","author":"Marchioni","year":"2015","journal-title":"ACM Trans. Comput. Logic"},{"key":"2026041420080663600_ref16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511794216","volume-title":"Game Theory","author":"Maschler","year":"2013"},{"key":"2026041420080663600_ref17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2268660","article-title":"A theorem about infinite-valued sentential logic","volume":"16","author":"McNaughton","year":"1951","journal-title":"Journal of Symbolic Logic"},{"key":"2026041420080663600_ref18","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0304-3975(87)90083-1","article-title":"Satisfiability in many-valued sentential logic is NP-complete","volume":"52","author":"Mundici","year":"1987","journal-title":"Theoretical Computer Science"},{"key":"2026041420080663600_ref19","doi-asserted-by":"crossref","first-page":"596","DOI":"10.2307\/2275410","article-title":"A constructive proof of McNaughton\u2019s theorem in infinite-valued logic","volume":"59","author":"Mundici","year":"1994","journal-title":"The Journal of Symbolic Logic"},{"key":"2026041420080663600_ref20","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","article-title":"Non-cooperative games","volume":"54","author":"Nash","year":"1951","journal-title":"Annals of Mathematics"},{"key":"2026041420080663600_ref21","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1017\/CBO9780511800481.004","article-title":"The complexity of finding Nash equilibria","volume-title":"Algorithmic game theory","author":"Papadimitriou","year":"2007"},{"key":"2026041420080663600_ref22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.entcs.2020.08.009","article-title":"An efficient algorithm for representing piecewise linear functions into logic","volume-title":"Electronic Notes in Theoretical Computer Science. Proceedings of LSFA 2020, the 15th International Workshop on Logical and Semantic Frameworks, with Applications (LSFA 2020)","author":"Preto","year":"2020"},{"key":"2026041420080663600_ref23","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1017\/S096012952200010X","article-title":"Efficient representation of piecewise linear functions into \u0141ukasiewicz logic modulo satisfiability","volume":"32","author":"Preto","year":"2022","journal-title":"Mathematical Structures in Computer Science"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/4\/exae073\/60462881\/exae073.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/4\/exae073\/60462881\/exae073.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T00:15:49Z","timestamp":1776212149000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exae073\/7877282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,7]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,4,24]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exae073","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,6]]},"published":{"date-parts":[[2024,11,7]]},"article-number":"exae073"}}