Module-4

Bayesian Games

BEARYS INSTITUTE OF TECHNOLOGY

• In algorithmic game theory, a Bayesian game models situations where players have incomplete information about each other—typically about their private characteristics or preferences
• A “Bayesian game”, which generalizes the notion of a strategic game to allows us to analyze any situation in which each player is imperfectly informed about some aspect of her environment relevant to her choice of an action.

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

Simple Bayesian Game(BoS): Cake or Ice Cream

• Two friends are deciding where to go for dessert.�Each can choose: Cake (C) or Ice Cream (I).�They want to be together, but each has a preference.

BEARYS INSTITUTE OF TECHNOLOGY

Types

• Player 1 has known preferences (loves Cake more).
• Player 2 could be:
• Type A: Prefers Cake
• Type B: Prefers Ice Cream
• Player 1 doesn't know Player 2's type but believes:
• Pr⁡(Type A)=0.6
• Pr⁡(Type B)=0.4

​

BEARYS INSTITUTE OF TECHNOLOGY

Payoff Matrix by Type:

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

Expected utility of player1

BEARYS INSTITUTE OF TECHNOLOGY

If Player 1 picks Cake

• If Player 1 picks Ice Cream:

​

BEARYS INSTITUTE OF TECHNOLOGY

• Since 1.2 > 0.4

​

• Player 1 should choose Cake, expecting Player 2 to most likely be Type A.

BEARYS INSTITUTE OF TECHNOLOGY

Motivational Examples�

• EXAMPLE271.1(Variantof BoS with imperfect information) Consider a variant of the situation modeled by BoS (Figure 16.1) in which player 1 is unsure whether player 2 prefers to go out with her or prefers to avoid her, whereas player 2, as before, knows player 1’s preferences. Specifically, suppose player 1 thinks that with probability 1/2 player 2 wants to got out with her, and with probability 1/2 player 2 wants to avoid her.

BEARYS INSTITUTE OF TECHNOLOGY

• (Presumably this assessment comes from player 1’s experience: half of the time she is involved in this situation she faces a player who wants to go out with her, and half of the time she faces a player who wants to avoid her.) That is, player 1 thinks that with probability 1/2 she is playing the game on the left of Figure 272.1 and with probability 1/2 she is playing the game on the right. Because probabilities are involved, an analysis of the situation requires us to know the players’ preferences over lotteries, even if we are interested only in pure strategy equilibria; thus the numbers in the tables are Bernoulli payoffs.

​

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

Figure 272.1 A variant of BoS in which player 1 is unsure whether player 2 wants to meet her or to avoid her. The frame labeled 2 enclosing each table indicates that player 2 knows the relevant table. The frame labeled1 enclosing both tables indicates that player 1 does not know the relevant table; the probabilities she assigns to the two tables are printed on the frame

Types

• From player 1’s point of view, player 2 has two possible types,
• If she thinks that the type who wishes to meet her will choose B and the type who wishes to avoid her will choose S,
• Player 1 chooses type B of player 2- the type who wishes to Meet her
• then she thinks that B will yield her a payoff of 2 with probability 1/2 and a pay off of 0 with probability 1/2,

BEARYS INSTITUTE OF TECHNOLOGY

A Bayesian game consists of

• a set of players

• a set of states

and for each player

• a set of actions

• a set of signals that she may receive and a signal function that associates a signal with each state

• For each signal that she may receive, a belief about the states consistent with the signal (a probability distribution over the set of states with which the signal is associated)

• A Bernoulli payoff function over pairs (a,ω),where a is an action profile and ω is a state, the expected value of which represents the player’s preferences among lotteries over the set of such pairs

BEARYS INSTITUTE OF TECHNOLOGY

The game in Example271.1fits into this general definition as follows.

Players: The pair of people.

States : The set of states is {meet, avoid}.

Actions: The set of actions of each player is {B,S}.

Signals: Player 1 may receive a single signal, say z; her signal function τ1 satisfies τ1(meet)=τ1(avoid)=z. Player 2 receives one of two signals, say m and v; her signal function τ2 satisfies τ2(meet)=m and τ2(avoid)=v.

Beliefs: Player 1 assigns probability 1/2 to each state after receiving the signal z. Player 2 assigns probability 1 to the state meet after receiving the signal m, and probability 1 to the state avoid after receiving the signal v.

Payoffs: The payoffs ui(a,meet) of each player i for all possible action pairs are given in the left panel of Figure 272.1, and the payoffs ui(a,avoid) are given in the right panel.

BEARYS INSTITUTE OF TECHNOLOGY

• Players: The pair of people.
• States: The set of states is {yy,yn,ny,nn}.
• Actions: The set of actions of each player is {B,S}.
• Signals: Player 1 receives one of two signals, y1 and n1; her signal function τ1 satisfies τ1(yy)=τ1(yn)=y1 and τ1(ny)=τ1(nn)=n1. Player 2 receives one of two signals, y2 and n2; her signal function τ2 satisfies τ2(yy)= τ2(ny)=y2 and τ2(yn)=τ2(nn)=n2

BEARYS INSTITUTE OF TECHNOLOGY

A Nash equilibrium of a Bayesian game is a

• Nash equilibrium of the strategic game (with vNM preferences) defined as follows.
• Players The set of all pairs (i,ti) where i is a player in the Bayesian game and ti is one of the signals that i may receive.
• Actions The set of actions of each player (i,ti) is the set of actions of player i in the Bayesian game.
• Preferences The Bernoulli payoff function of each player (i,ti)

BEARYS INSTITUTE OF TECHNOLOGY

Two examples concerning information

More information may hurt

A decision-maker in a single-person decision problem cannot be worse off if she has more information: if she wishes, she can ignore the information. In a game the same is not true: if a player has more information and the other players know that she has more information then she may be worse off.

Beliefs Player 1 assigns probability 1/2 to each of the states yy and yn after receiving the signal y1 and probability 1/2 to each of the states ny and nn after receiving the signal n1. Player 2 assigns probability 2/3 to the state yy and probability 1/3 to the state ny after receiving the signal y2, and probability 2/3 to the state yn and probability 1/3 to the state nn after receiving the signal n2.

• Payoffs The payoffs ui(a,ω) of each player i for all possible action pairs and states.

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

• Infection
• The notion of a Bayesian game may be used to model not only situations in which players are uncertain about each others’ preferences, but also situations in which they are uncertain about each others’ knowledge. Consider, for example,the Bayesian game in Figure 282.1.

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

• Now extend the game as in Figure283.1. Consider state δ. In this state, player2 knows player 1’s preferences(because she knows that the state is either γ or δ, and in both states player 1’s preferences are the same). What player 2 does not know is whether player 1 knows that player 2 knows player 1’s preferences.
• The reason is that player 2 does not know whether the state is γ or δ; and in state γ player 1 does not knowthatplayer2knows her preferences, because she does not know whether the state is β or γ, and in stateβ player 2 (who does not know whether the state is α or β) does not know her preferences.
• Thus the level of the shortcoming in the players’ information is higher than it is in the game in Figure 282.1. Nevertheless, the incentives faced by player 1 in state α again “infect” the remainder of the game, and in the only Nash equilibrium every type of each player chooses R.

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY

BEARYS INSTITUTE OF TECHNOLOGY