ow the stream(0, 0,,, 0, 2, 2, 2, . )will always be preferred to(1, 1, ..), whereas for low enough o, the reverse is true. Conversely, the limit-of-means criterion does not distinguish between(1, 1,0,0, .. )and(0, 0,..., whereas, for all 8 E(0, 1), the latter stream is preferred to the former ote that, for any pair of streams, there exists a discount factor such that the ordering of those two streams according to the limit-of-means and discounting criteria is the same (but, you need to pick a different d for every pair of streams Overtaking The limit-of-means criterion completely disregards finite histories. Thus, for instance, it does not distinguish between(-1, 2,,. )and(-1, 1, 0, 0, . ). This might seem a bit extreme Thus consider the following variant (u4)121x(u4)≥1分 lim inf t=1 Then, according to the overtaking criterion, a stream is preferred to another if it eventually yields a higher cumulative payoff. In particular, (-1, 2, 0, 0,.) is preferred to(-1, 1, 0, 0 In some sense, the overtaking criterion is "the best of both worlds: it treats games symmetrically, and it does give some weight to finite histories Having said that, we shall forget about any criterion other than discounting Machines Let me just remind you of the definition from OR. We do not really need them in this lecture. Definition 2 Fix a normal-form game G. A machine for Player i E N is a tuple M (Qi, q i, fi, Ti), where (Qi is a finite set(whose elements should be thought of as labels (ii) qi is the initial state of the machine; Gi)fi: Qi- Ai is the action function: it specifies what Player i does at each state; and (v)Ti: Qi x AQi is the transition function: if action a E A is played and Player i's machine state is qi E Qi, then at the next stage Player i' s machine state will be Ti (gi, a) Note that every machine defines a strategy, but not conversely. This is clear: a strategy is a sort of "hyper-machine"which has as states the set of non-terminal histories; but of course there are infinitely many such histories, so we cannot"shoehorn"strategies into our definition of machinesNow the stream (0, 0, 0, . . . , 0, 2, 2, 2, . . .) will always be preferred to (1, 1, . . .), whereas, for low enough δ, the reverse is true. Conversely, the limit-of-means criterion does not distinguish between (−1, 1, 0, 0, . . .) and (0, 0, . . .), whereas, for all δ ∈ (0, 1), the latter stream is preferred to the former. Note that, for any pair of streams, there exists a discount factor such that the ordering of those two streams according to the limit-of-means and discounting criteria is the same (but, you need to pick a different δ for every pair of streams!) Overtaking The limit-of-means criterion completely disregards finite histories. Thus, for instance, it does not distinguish between (-1, 2, 0, 0, . . .) and (-1, 1, 0, 0, . . .). This might seem a bit extreme. Thus, consider the following variant: (u t i )t≥1 i (w t i )t≥1 ⇔ lim inf t→∞ X T t=1 (u t i − w t i ) > 0 Then, according to the overtaking criterion, a stream is preferred to another if it eventually yields a higher cumulative payoff. In particular, (-1, 2, 0, 0, . . .) is preferred to (-1, 1, 0, 0, . . .). In some sense, the overtaking criterion is “the best of both worlds:” it treats all stage games symmetrically, and it does give some weight to finite histories. Having said that, we shall forget about any criterion other than discounting! Machines Let me just remind you of the definition from OR. We do not really need them in this lecture. Definition 2 Fix a normal-form game G. A machine for Player i ∈ N is a tuple Mi = (Qi , q0 i , fi , τi), where: (i) Qi is a finite set (whose elements should be thought of as labels); (ii) q 0 i is the initial state of the machine; (iii) fi : Qi → Ai is the action function: it specifies what Player i does at each state; and (iv) τi : Qi × A → Qi is the transition function: if action a ∈ A is played and Player i’s machine state is qi ∈ Qi , then at the next stage Player i’s machine state will be τi(qi , a). Note that every machine defines a strategy, but not conversely. This is clear: a strategy is a sort of “hyper-machine” which has as states the set of non-terminal histories; but of course there are infinitely many such histories, so we cannot “shoehorn” strategies into our definition of machines. 3