{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T22:14:49Z","timestamp":1777068889940,"version":"3.51.4"},"reference-count":28,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T00:00:00Z","timestamp":1640044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>We introduce a non-cooperative game model in which players\u2019 decision nodes are partially ordered by a dependence relation, which directly captures informational dependencies in the game. In saying that a decision node v is dependent on decision nodes v1,\u2026,vk, we mean that the information available to a strategy making a choice at v is precisely the choices that were made at v1,\u2026,vk. Although partial order games are no more expressive than extensive form games of imperfect information (we show that any partial order game can be reduced to a strategically equivalent extensive form game of imperfect information, though possibly at the cost of an exponential blowup in the size of the game), they provide a more natural and compact representation for many strategic settings of interest. After introducing the game model, we investigate the relationship to extensive form games of imperfect information, the problem of computing Nash equilibria, and conditions that enable backwards induction in this new model.<\/jats:p>","DOI":"10.3390\/g13010002","type":"journal-article","created":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T09:50:43Z","timestamp":1640080243000},"page":"2","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Partial Order Games"],"prefix":"10.3390","volume":"13","author":[{"given":"Valeria","family":"Zahoransky","sequence":"first","affiliation":[{"name":"Fachbereich Informatik, Universit\u00e9 du Luxembourg, Maison du Nombre, 6 Avenue de la Fonte, L-4364 Esch-sur-Alzette, Luxembourg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Gutierrez","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Monash University, Woodside Building for Technology and Design, 20 Exhibition Walk, Clayton, VIC 3168, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Harrenstein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9329-8410","authenticated-orcid":false,"given":"Michael","family":"Wooldridge","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1007\/s11229-015-0991-y","article-title":"Partial-order Boolean games: Informational independence in a logic-based model of strategic interaction","volume":"193","author":"Bradfield","year":"2016","journal-title":"Synthese"},{"key":"ref_2","unstructured":"Koller, D., and Milch, B. (2001, January 4\u201310). Multi-agent influence diagrams for representing and solving games. Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), Seattle, WA, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0899-8256(02)00544-4","article-title":"Multi-agent influence diagrams for representing and solving games","volume":"45","author":"Koller","year":"2003","journal-title":"Games Econ. Behav."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Maschler, M., Solan, E., and Zamir, S. (2013). Game Theory, Cambridge University Press.","DOI":"10.1017\/CBO9780511794216"},{"key":"ref_5","unstructured":"Osborne, M.J., and Rubinstein, A. (1994). A Course in Game Theory, MIT Press."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Vollmer, H. (1999). Introduction to Circuit Complexity: A Uniform Approach, Texts in Theoretical Computer Science; Springer.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Jukna, S. (2012). Boolean Function Complexity: Advances and Frontiers, Springer. Algorithms and Combinatorics.","DOI":"10.1007\/978-3-642-24508-4"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Greenlaw, R., Hoover, H.J., and Ruzzo, W.L. (1995). Limits to Parallel Computation: P-Completeness Theory, Oxford University Press.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1109\/TEC.1956.5219786","article-title":"Complexity in electronic switching circuits","volume":"1","author":"Muller","year":"1956","journal-title":"IRE Trans. Electron. Comput."},{"key":"ref_10","first-page":"120","article-title":"A method of circuit synthesis","volume":"1","author":"Lupanov","year":"1958","journal-title":"Izvesitya VUZ Radiofiz"},{"key":"ref_11","unstructured":"van Benthem, J. (2001). Boolean Games. Proceeding of the Eighth Conference on Theoretical Aspects of Rationality and Knowledge (TARK VIII), Morgan Kaufmann."},{"key":"ref_12","unstructured":"Harrenstein, P. (2004). Logic in Conflict. [Ph.D. Thesis, Utrecht University]."},{"key":"ref_13","unstructured":"Bonzon, E., Lagasquie, M., Lang, J., and Zanuttini, B. (September, January 28). Boolean games revisited. Proceedings of the ECAI 2006, Riva del Garda, Italy. Available online: https:\/\/www.researchgate.net\/publication\/48445144_Boolean_Games_Revisited."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10458-008-9040-2","article-title":"Compact preference representation and Boolean games","volume":"18","author":"Bonzon","year":"2009","journal-title":"Auton. Agents Multi-Agent Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/j.artint.2012.11.003","article-title":"Incentive engineering for Boolean games","volume":"195","author":"Wooldridge","year":"2013","journal-title":"Artif. Intell."},{"key":"ref_16","unstructured":"Endriss, U., Now\u00e9, A., Dignum, F., and Lomuscio, A. (2021, January 3\u20137). Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice. Proceedings of the 20th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201921), Online. Available online: https:\/\/arxiv.org\/pdf\/2102.05008.pdf."},{"key":"ref_17","unstructured":"Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems, Morgan Kaufmann."},{"key":"ref_18","first-page":"721","article-title":"Influence Diagrams","volume":"Volume 2","author":"Howard","year":"1994","journal-title":"Readings on the Principles and Applications of Decision Analysis"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kjaerulff, U.B., and Madsen, A.L. (2008). Bayesian Networks and Influence Diagrams, Springer Science+ Business Media 200.","DOI":"10.1007\/978-0-387-74101-7"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(81)90112-2","article-title":"Petri Nets, Event Structures and Domains, Part I","volume":"13","author":"Nielsen","year":"1981","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","first-page":"82","article-title":"A Classification of Models for Concurrency","volume":"Volume 715","author":"Best","year":"1993","journal-title":"Proceedings of the CONCUR \u201993, 4th International Conference on Concurrency Theory"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Clairambault, P., Gutierrez, J., and Winskel, G. (2012, January 25\u201328). The Winning Ways of Concurrent Games. Proceedings of the IEEE Symposium on Logic in Computer Science, Dubrovnik, Croatia.","DOI":"10.1109\/LICS.2012.34"},{"key":"ref_23","unstructured":"Gutierrez, J., and Wooldridge, M. (, January 14\u201318). Equilibria of concurrent games on event structures. Proceedings of the CSL-LICS, Vienna, Austria."},{"key":"ref_24","first-page":"5:1","article-title":"The True Concurrency of Herbrand\u2019s Theorem","volume":"Volume 119","author":"Ghica","year":"2018","journal-title":"Proceedings of the CSL"},{"key":"ref_25","first-page":"18:1","article-title":"Thin Games with Symmetry and Concurrent Hyland-Ong Games","volume":"15","author":"Castellan","year":"2019","journal-title":"Log. Methods Comput. Sci."},{"key":"ref_26","unstructured":"Thompson, F.B. (1952). Equivalence of Games in Extensive Form, Research Memorandum RM-759; Rand Corporation."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Hearn, R.A., and Demaine, E.D. (2009). Games, Puzzles and Computation, A.K. Peters.","DOI":"10.1201\/b10581"},{"key":"ref_28","unstructured":"Fudenberg, D., and Tirole, J. (1991). Game Theory, The MIT Press."}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/13\/1\/2\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:50:33Z","timestamp":1760169033000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/13\/1\/2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,21]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["g13010002"],"URL":"https:\/\/doi.org\/10.3390\/g13010002","relation":{},"ISSN":["2073-4336"],"issn-type":[{"value":"2073-4336","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,21]]}}}