Stéphane Le Roux
-
Non-Determinism and Nash Equilibria for Sequential Game over Partial Order
dmtcs:3468 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
-
https://doi.org/10.46298/dmtcs.3468
Non-Determinism and Nash Equilibria for Sequential Game over Partial OrderConference paper
Authors: Stéphane Le Roux 1,2
NULL
Stéphane Le Roux
1 Laboratoire de l'Informatique du Parallélisme
2 Japan Advanced Institute of Science and Technology
In sequential games of traditional game theory, backward induction guarantees existence of Nash equilibrium by yielding a sub-game perfect equilibrium. But if payoffs range over a partially ordered set instead of the reals, then the backward induction predicate does no longer imply the Nash equilibrium predicate. Non-determinism is a solution: a suitable non-deterministic backward induction function returns a non-deterministic strategy profile which is a non-deterministic Nash equilibrium. The main notions and results in this article are constructive, conceptually simple and formalised in the proof assistant Coq.
Stéphane Le Roux, Lecture notes in computer science, Acyclic Preferences and Existence of Sequential Nash Equilibria: A Formal and Constructive Equivalence, pp. 293-309, 2009, 10.1007/978-3-642-03359-9_21.