190 9. Coexisting Wireless LANs as Multi Stage Game

BEH-B, BEH-C, BEH-D, as defined in the previous chapter, see Section 8.3.2, p. 184. Static strategies, where one behavior is selected continuously throughout the complete MSG are studied first and discussed in Section 9.2. Dynamic strategies allow a player to select different behaviors as response to the behavior of the opponent player throughout the course of the MSG. Dynamic strategies are discussed in Section 9.3. This section concludes this chapter by discussing the advantages and drawbacks of the game approach taken in this thesis.

Before introducing static and dynamic strategies, the payoff calculation in the MSG and the Nash equilibrium in the MSG are introduced in the following Section 9.1.

9.1Strategies in MSGs

In this thesis, strategies are defined as state machines that describe which behavior to select at what stage of the game. Payoffs in an MSG are calculated differently than payoffs in an SSG, which will be explained in Section 9.1.1. Further, Nash equilibria in the MSG are defined between strategies rather than between actions, as it was the case in the SSG. This is explained in Section 9.1.2.

9.1.1Payoff Calculation in the MSGs, Discounting and Patience

In every stage n of the MSG, players take the decision of which action to take (or, what behavior to select out of the set of available behaviors). When taking the decision, the influence of the behavior in the present stage on the observed payoffs of the following stages must be taken into account. This is done in an MSG by discounting future expected payoffs (Osborne and Rubinstein, 1994), as explained in the following.

Players give present payoffs a higher weight than payoffs of future stages, as future payoffs are potentially uncertain and are estimated in the present stage. A general approach to model this preference is to discount the payoffs for each stage of a game. A discounting factor δ , with 0 ≤δ ≤1 is used in the payoff calculation which reflects in the present stage the relative level of importance of the payoff of following stages.

As δ →1 , future payoffs have the same importance as the payoff of the present stage. A player that discounts with such a large discounting factor is referred to as being a patient player. On the other hand, with δ →0 , a player focuses on the present payoff only and pays no attention to potential future payoffs. Such a player is referred to as an impatient player.

9.1 Strategies in MSGs

191

Table 9.1: Discounting factors of different QoS characteristics (Berlemann 2003)

application	discounting factor δ
data, best effort	0.5
video, voice, CCHC (802.11 overlapping QBSS)	0.9
Network Control, CCHC (802.11 - HiperLAN/2)	1.0

The value of this discounting factor δ is determined with the help of the QoS requirements a player attempts to achieve throughout the MSG. As the QoS requirements remain constant during the course of the MSG, the discounting factor remains constant as well. Table 9.1 illustrates corresponding discounting factors for some typical applications.

The payoff a payer i observes in an infinitely often repeated SSG is then calculated with a discounting factor δ through

Vinfinitei	∞
	MSG =V i(0) +δV i(1) +δ2V i( 2) +…= ∑δtV i(n) .	(9.1)

n =0

With δ <1 , the later the stages the smaller the contribution of this stage to the payoff in the present stage. Future payoffs are worth less in the present stage. A MSG consists of a finite number of repeated SSGs with an existing end. Thus, the MSG is not infinitely repeated. The interaction of two CCHCs in the coexistence scenario has a typical duration of some seconds or minutes, but is clearly not infinite. However, the end of the interaction is unknown to the players, because of the unknown situation of the opponent player: players can only define a certain probability p that there will be no next stage after the present stage. Assuming that p is the probability that the MSG ends after each stage, the payoff is calculated as

V finitei MSG =V i(0) +(1 − p)V i(1) +(1 − p)2V i( 2)

N MSG	(1 − p)tV i(n)
= ∑
n =0

+…

,(9.2)

where N MSG is the unknown number of stages of the MSG. In literature of game theory, the probability p is often used as a measure for what is called the shadow of the future. The larger the value of p is, the more important the future stages are when taking a decision at a particular stage. Note that the payoff calculation by discounting in an infinite MSG, as shown in Equation (9.1), and the probability version of the payoff calculation in an finite MSG with unknown end, as shown in Equation (9.2), are very similar.