Bayesian game

https://gyazo.com/14decc98dff6e1f695cb86ec87577552

summary

m0t0k1ch1.icon ベイジアンゲームの概要を把握する

---.icon

Summary

A Bayesian game is a game in which the players have incomplete information on the other players (e.g. on their available strategies or payoffs).

Nature assigns a random variable to each player which could take values of types for each player and associating probabilities or a probability mass function with those types.

The type of a player determines that player's payoff function.

Players have initial beliefs about the type of each player (where a belief is a probability distribution over the possible types for a player) and can update their beliefs according to Bayes' rule as play takes place in the game.

---.icon

Formal Definitions

$ G = \langle N, \Omega, \langle A_i, u_i, T_i, \tau_i, p_i, C_i \rangle_{i \in N} \rangle

$ Nis the set of players

$ \Omegais the set of states of nature

For instance, in a card game, it can be any order of the cards.

$ A_iis the set of actions for player$ i

Let$ A = A_1 \times A_2 \times \cdots \times A_N.

$ u_i : \Omega \times A_i \rightarrow Ris the payoff function for player$ i

More formally, let$ L = \{ (\omega, a_1, \ldots, a_N) \mid \omega \in \Omega, \forall{i}, (a_i, \tau_i(\omega)) \in C_i \}, and$ u_i : L \rightarrow R.

$ T_i is the type of player$ i, decided by the function$ \tau_i.

The outcome of the players is what determines its type.

Players with the same outcome belong to the same type.

$ \tau_i : \Omega \rightarrow T_i

$ p_iis the probability distribution over$ \Omegafor each player$ i

$ C_i \subseteq A_i \times T_idefines the available actions for player$ iof some type in$ T_i

The pure storategy$ s_i = T_i \rightarrow A_ishould satisfy$ (s_i(t_i), t_i) \in C_i.

The strategy for each player only depends on his type, since he may not have any knowledge about other players' types.

The expected payoff to player$ ifor such a strategy profile is$ u_i(S) = E_{\omega \sim p_i} \lbrack u_i(\omega, s_1(\tau_1(\omega)), \ldots, s_N(\tau_N(\omega))) \rbrack

Let$ S_ibe the set of pure strategies, $ S_i = \{ s_i : T_i \rightarrow A_i \mid (s_i(t_i), t_i) \in C_i, \forall{t_i} \}

A Bayesian Equilibrium of the game$ Gis defined to be (possibly mixed strategy) Nash equilibrium of the game$ \hat{G} = \langle N, \hat{A} = S_1 \times S_2 \times \cdots \times S_N, \hat{u} = u \rangle.

For any finite game$ G, Bayesian Equilibria always exist.

m0t0k1ch1.icon $ \timesは直積

Bayesian Games and Stochastic Games

The definition of Bayesian games has been combined with stochastic games to allow for environment states (e.g. physical world states) and stochastic transitions between states.

The resulting "stochastic Bayesian game" model is solved via a recursive combination of the Bayesian Nash equilibrium and the Bellman optimality equation.

---.icon

TODO