Partial Order Games

Valeria Zahoransky, Julian Gutierrez, Paul Harrenstein and Michael Wooldridge
Additional contact information
Valeria Zahoransky: Fachbereich Informatik, Université du Luxembourg, Maison du Nombre, 6 Avenue de la Fonte, L-4364 Esch-sur-Alzette, Luxembourg
Julian Gutierrez: Faculty of Information Technology, Monash University, Woodside Building for Technology and Design, 20 Exhibition Walk, Clayton, VIC 3168, Australia
Paul Harrenstein: Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
Michael Wooldridge: Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK

Games, 2021, vol. 13, issue 1, 1-49

Abstract: We introduce a non-cooperative game model in which players’ 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 v 1 , … , v k , we mean that the information available to a strategy making a choice at v is precisely the choices that were made at v 1 , … , v k . 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.

Keywords: game theory; non-cooperative games; Nash equilibrium; backwards induction; computational complexity (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/13/1/2/pdf (application/pdf)
https://www.mdpi.com/2073-4336/13/1/2/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:13:y:2021:i:1:p:2-:d:707690

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().