Subgame-perfection in free transition games

• Published in: European journal of operational research 2013-07, Vol.228 (1), p.201-207
• Main Authors: Flesch, J., Kuipers, J., Schoenmakers, G., Vrieze, K.
• Format: Article
• Language: English
• Subjects: Average payoff; Comparative analysis; Game theory; Iterative methods; Perfect information game; Probability; Recursive game; Stochastic game; Studies; Subgame-perfect equilibrium
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2013.01.034

► Subgame-perf. ε-eq. ∀>0 in free transition games without (semi-) continuous pay-offs. ► New technique to prove the existence of these subgame-perfect ε-equilibria. ► Polynomial time algorithm for construction of these subgame-perfect ε-equilibria. We prove the existence of a subgame-perfect ε-equilibrium, for every ε>0, in a class of multi-player games with perfect information, which we call free transition games. The novelty is that a non-trivial class of perfect information games is solved for subgame-perfection, with multiple non-terminating actions, in which the payoff structure is generally not (upper or lower) semi-continuous. Due to the lack of semi-continuity, there is no general rule of comparison between the payoffs that a player can obtain by deviating a large but finite number of times or, respectively, infinitely many times. We introduce new techniques to overcome this difficulty. Our construction relies on an iterative scheme which is independent of ε and terminates in polynomial time with the following output: for all possible histories h, a pure action ah1 or in some cases two pure actions ah2 and bh2 for the active player at h. The subgame-perfect ε-equilibrium then prescribes for every history h that the active player plays ah1 with probability 1 or respectively plays ah2 with probability 1−δ(ε) and bh2 with probability δ(ε). Here, δ(ε) is arbitrary as long as it is positive and small compared to ε, so the strategies can be made “almost” pure.