Equivalence between graphbased and sequencebased

Authors: J Jude Kline Shravan Luckraz

Publish Date: 2016/02/08

Volume: 4, Issue: 1, Pages: 85-94

PDF Link

Abstract

This note establishes an equivalence between the graphbased definition of an infinite extensive form game following Kuhn Contributions to the theory of games II Princeton Princeton University Press pp 193–216 1953 and the sequencebased definition by Osborne and Rubinstein A course in game theory Cambridge MIT Press 1994First we show that Vsuccsim is a partially ordered set with a maximum rin V Reflexivity is apparent from the definition of succsim which requires that x=y implies xsuccsim y For transitivity let xyzin V and suppose xsuccsim y and ysuccsim z If x=y or y=z then xsuccsim z from the assumption that ysuccsim z or xsuccsim y respectively Suppose that xne y and yne z Then from the definition of succsim there must be a walk p=v 1ldots v k from x to y and a walk q=u 1ldots u ell from y to z so v 1ldots v k u 2ldots u ell is a walk from x to z This implies xsuccsim z Antisymmetry and maximum element follow from 3Next we show STi For x=r yin Vysuccsim r=r which is a finite chain For xin Vbackslash r let wx=v 1ldots v k denote the unique walk from the root r to x guaranteed by 3 Then yin Vysuccsim x=v 1ldots v k is a finite chain by 3 and the definition of a walk from a vertex a to a vertex bFinally we show STii Let xsucc y Then there is a walk v 1 ldots v k from x to y Hence x has an immediate successor zprime on the walk to y By NTDV and K2ii x has another immediate successor zne zprime Therefore there is a walk from x to z Hence xsucc z By 3 neither ysuccsim z nor zsuccsim y square Clearly alpha cdot is a surjection We show that it is also an injection Let vk k=1K and uk k=1Kprime be two distinct vertex histories that may be finite or infinite Let j be the first instance where the two sequences differ ie vk=uk for all kj and vjne uj By K1 v1=u1=r where r is the root so j1 By K2ii psi vj11vjne psi uj11uj Hence alpha vk k=1Kne alpha uk k=1Kprime square i Clearly varOmega left varGamma right =left displaystyle bigcup nolimits vin V A vleft alpha qqin mathcal Pright right is an actionsequence pair It suffices to show OR1 OR2 and OR3 OR1 follows from the root assumption in K1 and the nonemptiness of V OR2 and OR3 follow from the definitions of walk K2 and 5

Keywords: