Game Theory for Internetworking

1.2. MULTI-AGENT DECISION PROBLEM
that are appealing for the game theory are simple, and thereby this hypothesis is
practically not binding.
1.1.2 Rationality
The meaning of rationality in game theory may not correspond to the common
meaning for the reader. A classical assumption of game theory is to consider a
player as rational, i.e., the player is supposed to be able to choose among several
alternatives and to take decisions consistently with the preferences the player had
on (the consequences of) those alternatives.
Furthermore, the preferences of a rational player are transitive. To explain this
with an example rather than mathematically, consider a player that prefers apples
to pears, and pears to bananas. If he is rational, he does not prefers bananas to
apples. Otherwise, interacting with rational players he could be swiped. Indeed,
another player with an apple, a pear and a banana may give you an apple as a
gift; then, he may propose to exchange your apple with the banana for a few euros
since you prefer bananas to apples; then, he may propose you to exchange your
banana with the pear since you prefers pears to bananas; then, the apple for the
pear, and so on so forth he can impoverish you to infinity.
1.2 Multi-agent Decision Problem
In a game, an intelligent and rational player would choose a move so as to maximise
the expected utility that the choice could return.
Let us consider an example. In Table 1.1 we have a table describing a reduced
version of the following roulette game: “to play 100 euro on the number 13 (strategy
P), or not to play (strategy NP); if 13 is selected by the roulette (36 possible
numbers), the player earns 3500, otherwise the player looses his 100 units”. Each
cell of the table indicates the expected gain for the single player as function of the
state of nature, where for this case the state of nature is the number selected by
the roulette.
action | state of nature 0 1 ... 13 ... 35
P -100 -100 ... 3500 ... -100
NP 0 0 ... 0 ... 0
Table 1.1: The roulette game
Let u : R → R be the utility function associating to a monetary gain a per-
ceived utility. In order to take a decision, the decision-maker needs to know the
probability of occurrence for each state of nature. In this way he can estimate the
expected utility of each possible move. A rational decision-maker for which such
an utility function and such calculations have sense, i.e., for which - under risk
conditions - the preference relation over a finite set of states can be written as an
expected utility, is said to be a Von Neumann-Morgenstern decision-maker; this is
the affection we adopt for the decision-maker in the following.
2
1.2. MULTI-AGENT DECISION PROBLEM
1.2.1 Risk
If the probability distribution on the network states is exogenously given, the
decision problem is said to be under risk conditions. For instance, let us consider
the game described by the Table 1.1. If each state of nature is equally probable,
the player can estimate an expected utility for the strategy P equal to 136u(3500)−
35
36u(100), for the strategy NP equal to u(0), and a rational player will choose P
only if the first value is bigger than the latter.
1.2.2 Uncertainty
If the state of nature probability distribution is not externally given, the player has
to devise it. The player assigns endogenously the probability of each state starting
by his preferences on the problem data. In this case, the decision problem is said
to be under uncertainty conditions (and the player in this case is usually called a
Bayesian decision-maker).
1.2.3 Interactivity
If in the place of the state of nature events there is a list of possible choices of
another player, we have two players and thus an interactive decision. In such a
game, the interaction is not intended in the sense that one player can directly
influence the decision of the other player, but in the sense that the game result
depends on the decisions of both the players.
Even if practically an interactive game may seem very close, if not equivalent,
to a decision problem under uncertainty, in this case the player has to consider that
on the other side there is not the luck, but another rational player as himself with
different strategies and preferences on the results. Surely, the states of nature can
encompass aspects due to others’ decisions. However, in decision problems under
uncertainty there is no awareness on the possible interaction with other agents.
Hence, the procedures that assign probabilities to state of nature and to other
player’s decisions are different, because of the different meaning the external states
assume.
1.2.4 Dominance
A classical assumption is that all the parameters of the game are common knowl-
edge among the players2, i.e., each player knows the other player’s possible strate-
gies, the preferences he has on the alternative strategies, and this fact is also known,
it is known that this fact is known, etc. In a strategic interaction context, the de-
cision problem is usually not simple except the case in which the players dispose
of strongly dominant strategies. A few definitions are needed to characterize the
three different dominance levels. We use in the following a different terminology
than the classical one, adopting the one suggested in [1].
2
In the following, for simplicity we will refer to a two player game, when not differently
mentioned.
3
1.2. MULTI-AGENT DECISION PROBLEM
Weak dominance
A strategy weakly dominates another alternative strategy if the payoff it grants is
greater than or equal to the alternative payoff whatever the strategy of the other
player will be.
Strict dominance
A strategy strictly dominates another alternative strategy if it weakly dominates
the other strategies, and if for at least one strategy of the other player the payoff
it grants is strictly greater than the alternative payoff.
Strong dominance
A strategy strongly dominates another alternative strategy for a player if the payoff
it grants is strictly greater than the alternative payoff whatever the strategy of the
other player will be.
Therefore, if both players have a strongly dominant strategy, the rational solu-
tion of the game is the pair of the two dominant strategies; rational in the sense
that if the two players are rational, their moves should stop in this solution point.
Consider for example the game whose “strategic form” is represented in Ta-
ble 1.2. In this case, each cell indicates the payoffs for player I and player II
respectively, within brackets and separated by a comma. The player I has three
I | II L R
T (2,1) (3,0)
M (1,0) (1,1)
B (3,1) (2,0)
Table 1.2: A game with strongly dominating strategies.
possible strategies (T, M and B), and the player II has twos (L and R). Each cell
contains the two payoffs for the corresponding pair of strategies of player I and
player II. At a first sight one can notice that M is strongly dominated by both
T and B, and thus I will never choose M. Under the condition that II knows the
payoffs of I and that I is rational, II assumes that I will not play M, and since R
is strongly dominated by L, II chooses L. Under the condition that I knows the
payoffs of II, that I knows that II is rational and that II knows that I knows, I
plays B. Hence by iterated reduction of strategies each player can determinate that
the solution pair of strategies will be (B,L).
Nevertheless, when there are no strongly dominating strategies, the iterated
reduction of strategies has no bite.
1.2.5 Equilibrium Strategies
An equilibrium of strategies is a pair of strategies such that, assuming the player II
strategy given, player I’s strategy gives a payoff greater than or equal to the payoffs
4
1.2. MULTI-AGENT DECISION PROBLEM
of his other alternative strategies, and vice-versa3. This definition of strategic
equilibrium is due to Nash, and it is commonly referred to as “Nash equilibrium”.
It has sense only for the class of games to which we have focused till now, that is
the class of non-cooperative games in which there can not be binding agreements
among players. A Nash equilibrium is thus the solution to which rational players
of a non-cooperative game shall implicitly tend.
A Nash equilibrium satisfies all the players, because it naturally represents an
acceptable point for rational players. This is due to the fact that both the players
would not have interest in deviating from a Nash equilibrium. Indeed, if a couple
of strategy does not correspond to a Nash equilibrium, at least for one player it
would be better to change to a strategy that gives him a greater payoff (this is true
because the players are rational).
Rationality and Efficiency
Nevertheless, an issue may arise: even if the players are rational, an equilibrium
may not be efficient.
Consider for example the game in Table 1.3, commonly named “the prisoner’s
dilemma”. In this example, the payoffs may indicate the years spent out of jail, for
two prisoners, different whether a prisoner confesses (C) or does not confesses (NC)
a crime he has committed with the other prisoner. If both confess, each prisoner
gets out from jail 1 year before; if both do not confess, both get out 2 years before;
otherwise, who does confess gets out 3 years before and the other one sticks.
I | II NC C
NC (2,2) (0,3)
C (3,0) (1,1)
Table 1.3: The prisoner’s dilemma.
The dilemma is the following: the Nash equilibrium apparently is (C,C), even
if the efficient pair of strategies for both would be (NC, NC). The strategies for
the Nash equilibrium (C,C) are strongly dominating strategies. (NC, NC) is not
an equilibrium because each player would prefer to change strategy to earn 1 year
more whether he assumes that the other player would choose NC, and viceversa.
Hence this would not happen, being both players rational and intelligent: the
assumption that the other player would choose NC is thus wrong and not rational.
The conclusion is that even if the players are rational and intelligent, this is not
sufficient for getting an efficient result. Even if they could communicate somehow
to agree on (NC,NC), a rational player should not hope the other will do what
they agreed upon.
If cooperation is needed, it would have sense only if the players can subscribe
binding agreements so that, for example, each prisoner can be reassured somehow
that the other will not confess to reach the efficient solution (NC,NC). In this case
3Please note that this differs from the weak dominance that stands for all the possible strategies
of the other player, and thus not constrained to a single strategy of the other player.
5
1.2. MULTI-AGENT DECISION PROBLEM
we would have a cooperative game. For a non cooperative game, one may thus
have inefficient Nash equilibrium solutions.
Multiple Equilibria and Coordination
Another issue that may arise in games is the Nash equilibrium non-uniqueness.
Consider for example the game in Table 1.4. There are two equilibria: (T,L)
and (B,R). In this case there is room for an implicit coordination between players
and both would rationally choose (T,L) since both have the same preference on
that result.
I | II L R
T (2,2) (0,0)
B (0,0) (1,1)
Table 1.4: A coordination game.
Consider now the game in Table 1.5. There are two equilibria: (T,L) and
(B,R), and the players have the same preferences for both the equilibria. This
game is dramatic for both the players because a 1 bit coordination message would
be enough to successfully play for (T,L) or (B,R). Hence, such a game is classified
as a pure coordination game.
I | II L R
T (1,1) (0,0)
B (0,0) (1,1)
Table 1.5: A pure coordination game.
Consider finally the game in Table 1.6. Also for this game we have the two
equilibria (T,L) and (B,R), but the players have adverse preferences for them. For
this reason, such a game is commonly named “the battle of the sexes”: suppose
that player I and II are a man and a woman, the man prefers to go the stadium
(T) rather than to the theatre (B), while the woman prefers the inverse (R and
B, respectively), and both have a null preference in going alone to the theatre or
to the stadium and a not null preference, however, if they go in the not preferred
place with the partner. Keeping such preferences, even with coordination between
players one can not say what rational players would decide. A form of coordination
would be useful only in that it could at least allow avoiding results with null payoffs.
I | II L R
T (2,1) (0,0)
B (0,0) (1,2)
Table 1.6: The battle of the sexes.
An implicit coordination approach among players is to choose a Nash equilib-
rium that is efficient in the Pareto sense. The Pareto-efficiency is a formal criterion
6