Bayesian game

In game theory, a Bayesian game is a strategic decision-making model which assumes players have incomplete information. Players may hold private information relevant to the game, meaning that the payoffs are not common knowledge. Bayesian games model the outcome of player interactions using aspects of Bayesian probability. They are notable because they allowed the specification of the solutions to games with incomplete information for the first time in game theory. Hungarian economist John C. Harsanyi introduced the concept of Bayesian games in three papers from 1967 and 1968: He was awarded the Nobel Memorial Prize in Economic Sciences for these and other contributions to game theory in 1994. Roughly speaking, Harsanyi defined Bayesian games in the following way: players are assigned a set of characteristics by nature at the start of the game. By mapping probability distributions to these characteristics and by calculating the outcome of the game using Bayesian probability, the result is a game whose solution is, for technical reasons, far easier to calculate than a similar game in a non-Bayesian context. Action sets, a i : The set of actions available to Player i. An action profile a = (a 1 , . . . , a N ) is a list of actions, one for each player Type sets, t i : The set of types of players i. "Types" capture the private information a player can have. A type profile t = (t 1 , . . . , t N ) is a list of types, one for each player Payoff functions, u: Assign a payoff to a player given their type and the action profile. A payoff function, u = (u 1 , . . . , u N ) denotes the utilities of player i Prior, p: A probability distribution over all possible type profiles, where p(t) = p(t 1 , . . . , t N ) is the probability that Player 1 has type t 1 and Player N has type t N .

Pure strategies

In a strategic game, a pure strategy is a player's choice of action at each point where the player must make a decision.

Bayesian Nash equilibrium

A Bayesian Nash Equilibrium (BNE) is a Nash equilibrium for a Bayesian game, which is derived from the ex-ante normal form game associated with the Bayesian framework. In a traditional (non-Bayesian) game, a strategy profile is a Nash equilibrium if every player's strategy is a best response to the other players' strategies. In this situation, no player can unilaterally change their strategy to achieve a higher payoff, given the strategies chosen by the other players. For a Bayesian game, the concept of Nash equilibrium extends to include the uncertainty about the state of nature: Each player maximizes their expected payoff based on their beliefs about the state of nature, which are formed using Bayes' rule. A strategy profile \sigma = (\sigma_1, \sigma_2, \dots, \sigma_N) is a Bayesian Nash equilibrium if, for every player i , the strategy \sigma_i maximizes player i 's expected payoff, given: Their beliefs about the state of nature (based on their type), The strategies played by other players. Mathematically: \sigma_i \text{ maximizes } \mathbb{E}[u_i(\sigma_i, \sigma_{-i}) \mid \text{type of player } i]. For finite Bayesian games (where the action and type spaces are finite), the BNE can be represented in two equivalent ways: Agent-Form Game: The number of players is expanded from |N| to \sum_{i=1}^ |\Theta_i| , where each type of a player is treated as a separate "player." This is detailed in Theorem 9.51 of the book Game Theory. Induced Normal Form Game: The number of players remains |N| , but the action space for each player i is expanded from |A_i| to |A_i|^ . This means the strategy now specifies an action for every type of player. This representation is discussed in Section 6.3.3 of the book Multiagent Systems. In both cases, the Nash equilibrium for the game can be computed using these representations, and the BNE can be recovered from the results. A linear program can be formulated to compute the BNE efficiently for two-player Bayesian games with a zero-sum objective.

Extensive form games with incomplete information

Elements of extensive form games

Extensive form games with perfect or imperfect information, have the following elements: Set of players Set of decision nodes A player function assigning a player to each decision node Set of actions for each player at each of her decision nodes Set of terminal nodes A payoff function for each player

Nature and information sets

An unfilled circle usually denotes nature's node. Its strategy is always specified and completely mixed. Although Nature is generally at the tree's root, it can also move to other points. An information set of player i is a subset of player is decision nodes that she cannot distinguish between. If player i is at one of her decision nodes in an information set, she does not know which node within the information set she is at. For two decision nodes to be in the same information set, they must Belong to the same player; and Have the same set of actions Information sets are denoted by dotted lines, the most common notation today.

The role of beliefs

In Bayesian games, players' beliefs about the game are denoted by a probability distribution over various types. If players do not have private information, the probability distribution over types is known as a common prior. An assessment satisfies Bayes' rule if μ(x|h i ) = Pr[x is reached given b ] / Σ Pr[x′ is reached given b −i ] whenever h i is reached with strictly positive probability according to .

Perfect Bayesian equilibrium

A perfect Bayesian equilibrium in an extensive form game is a combination of strategies and a specification of beliefs such that the following two conditions are satisfied: Bayesian consistency: the beliefs are consistent with the strategies under consideration; Sequential rationality: the players choose optimally given their beliefs. Bayesian Nash equilibrium can result in implausible equilibria in dynamic games, where players move sequentially rather than simultaneously. As in games of complete information, these can arise via non-credible strategies off the equilibrium path. In games of incomplete information, non-credible beliefs are also possible. To address these issues, Perfect Bayesian equilibrium, according to subgame perfect equilibrium, requires that subsequent play be optimal starting from any information set. It also requires that beliefs be updated consistently with Bayes' rule on every path of play that occurs with a positive probability.

Stochastic Bayesian games

Stochastic Bayesian games combine the definitions of Bayesian games and stochastic game to represent environment states (e.g., physical world states) with stochastic transitions between states as well as uncertainty about the types of different players in each state. The resulting model is solved via a recursive combination of the Bayesian Nash equilibrium and the Bellman optimality equation. Stochastic Bayesian games have been used to address diverse problems, including defense and security planning, cybersecurity of power plants, autonomous driving, mobile edge computing, self-stabilization in dynamic systems, and misbehavior treating in crowdsourcing IoT.

Incomplete information over collective agency

The definition of Bayesian games and Bayesian equilibrium has been extended to deal with collective agency. One approach is to continue to treat individual players as reasoning in isolation but to allow them, with some probability, to reason from the perspective of a collective. Another approach is to assume that players within any collective agent know that the agent exists but that other players do not know this, although they suspect it with some probability. For example, Alice and Bob may sometimes optimize as individuals and sometimes collude as a team, depending on the state of nature, but other players may not know which of these is the case. N = {Suspect, Sheriff} A Suspect = {Shoot, Not} , A Sheriff = {Shoot, Not} T Suspect = {Criminal, Civilian} , T Sheriff = {*} p Criminal = p , p Civilian = (1 − p) It is assumed that the payoffs, u, are given as follows: If both players are rational and both know that both players are rational and everything that any player knows is known to be known by every player (i.e., player 1 knows player 2 knows that player 1 is rational and player 2 knows this, etc. ad infinitum – common knowledge), play in the game will be as follows according to perfect Bayesian equilibrium: When the type is "criminal", the dominant strategy for the suspect is to shoot, and when the type is "civilian", the dominant strategy for the suspect is not to shoot; alternative strictly dominated strategy can thus be removed. Given this, if the sheriff shoots, he will have a payoff of 0 with probability p and a payoff of −1 with probability , i.e., an expected payoff of ; if the sheriff does not shoot, he will have a payoff of −2 with probability p and a payoff of 0 with probability , i.e., an expected payoff of . Thus, the Sheriff will always shoot if , i.e., when . Player 1 can guarantee herself a payoff of zero by bidding zero; hence, in equilibrium, p = 0 Since only "lemons" (used cars in bad conditions) are traded, the market collapses No trade is possible even when trade would be economically efficient

Names in other languages