You are currently browsing the category archive for the ‘Bayesian Games’ category.

I had the opportunity to participate in a delightful workshop on mechanism design and the informed principal organized by Thomas Troeger and Tymofiy Mylovavnov. The setting was a charming `schloss‘ (manse rather than castle) an hour and half outside of Mannheim. They had gathered together a murderer’s row of speakers and auditors. Suffice it to say I was the infimum of the group and lucky to be there.

One (among many) remarkable talks was given by Roger Myerson on his 1983 paper entitled `Mechanism Design by an Informed Principal‘. Kudos to Thomas and Tymofiy for coming up with the idea of doing this. It brought to mind some couplets from Locksley Hall:

When the centuries behind me like a fruitful land reposed;

When I clung to all the present for the promise that it closed:When I dipt into the future far as human eye could see;

Saw the Vision of the world and all the wonder that would be.—

By the way, the last pair of lines appears on the dedication plaque that graces the USS Voyager (of the Star Trek franchise).

What did Roger do? He tried as best as possible, given the gulf of time, to explain why he had chosen the tack that he did in the paper (axiomatic) and his hope for how it would influence research on the subject.

A principal with private information must propose a mechanism to an agent. However, the choice of mechanism will reveal something of the principal’s private information to the agent. Thus, the problem of mechanism design in this setting is not a straight optimization problem. It is, at a high level, a signaling game. The signals are the set of mechanisms that the principal can propose. Thus, one seeks an equilibrium of this game. But which equilibrium?

In section 7 of the paper, Roger approaches the question axiomatically in the spirit of Nash bargaining. Indeed, Roger made just such an analogy in his talk. Nash did not have in mind any particular bargaining protocol, but a conviction that any reasonable protocol must satisfy some natural invariance conditions. Some decades later Rubinstein arrives with a bargaining protocol to justify Nash’s conviction. So, Roger sought the same here and expressed the wish to see this year a vindication of his hopes.

Lest you think the audience accepted Roger’s axioms uncritically, Thomas Troeger, pointed out Roger’s axiom 1 ruled out some possibly natural settings like Rothschild & Stiglitz. Roger argued that it was right and proper to rule this out and battle joined!

In Harsanyi games with incomplete information, also known as Bayesian games, each player has a type. The type of the player describes all that he knows and believes about the situation he faces: who are the players, what are his and their available actions, what are his and their utility functions, and what are the beliefs of the other players about the situation.

Since the player’s type describes his knowledge and beliefs, a player always knows his own type. But a player need not know the other players’ types. Indeed, a chess player knows his own abilities, but he may not the level of his opponent: he may ascribe probability 1/3 to the event that his opponent is familiar with the Benko gambit, and probability 2/3 to the event that the opponent is not familiar with this opening.

In a Bayesian game, a chance move selects a vector of types, one type for each player, according to a known probability distribution *p* at the outset of the game. Each player learns his own type, but he does not know the types chosen for the other players. He does have a belief about the other players’ types, which is the conditional distribution of *p* given his own type.

The Bayesian game is an auxiliary construction. In reality there is no chance move that selects the player’s types: the knowledge and beliefs each player is equipped with determine his or her type. Bayesian games are merely a way to model the incomplete information each player has on the other players’ types. Thus, the true situation the players face is the situation after the vector of types was selected, which is called the *interim stage*. The situation before the vector of types is chosen, which is called* ex ante* *stage*, is the mathematical way that Harsanyi found to model the game.

Consider now the following Bayesian game, that depends on a real number *a* (which is in the unit interval; below, all additions and subtractions are modulo 1). There are two players; the type space of each player is the unit interval [0,1]. The types of the players are correlated: if player 1 has type x, then he believes that player 2′s type is either x of x+a (each with probability 1/2); if player 2 has type x, then he believes that player 1′s type is either x of x-a (each with probability 1/2). This belief structure can be described by a common prior distribution: the types of the two players are chosen according to the uniform distribution over the following set T (this is a variation of an example of Ehud Lehrer and Dov Samet):

If player 1′s type is *x*, then he believes that player 2 may be of type *x* or *x+a*. It follows that player 2 may believes that player 1′s type is *x-a*, *x*, or *x+a*. So player 2 may believe that player 1 believes that player 2′s type is *x-a*, *x*, *x+a* or *x+2a*. When the situation is a game, to decide how to play, player 1 needs to take all types of player 2 (and of himself) of the form {*x+na*, *n* is an integer}. This set of finite if *a* is a rational number, and countable if *a* is an irrational number. Denote by Zx the set of all pairs of type {(*x+na,x+na*), *n* is an integer} union with {(*x+na,x+(n+1)a*), *n* is an integer}. The set Zx is called the *minimal belief subspace* of player 1. In the interim stage, after his type was selected and told to him, player 1 knows that the type vector is in Zx, that only type vectors in Zx appear in the belief hierarchy of player 2, and therefore he can think about the situation as if the Bayesian game is restricted to Zx: a type vector in Zx was chosen according to the conditional distribution over Zx. To determine how to play, player 1 should find an equilibrium in the game restricted to Z.

The uniform distribution of the set T that appears in the figure above induces a probability distribution over Zx. When Zx is finite (= *a* is a rational number), this is the uniform distribution over a finite set. Alas, when Zx is countable (*a* is irrational) there is no uniform distribution over Zx. In particular, the interim stage is not well defined! Thus, even though the interim stage is the actual situation the players face, and even though they can describe their beliefs using a Harsanyi game with a larger type space, the situation they face cannot be described as a Harsanyi game if they take into account only the types that are possible according to their information.

It is interesting to note that one can find a Bayesian equilibrium in the game restricted to Zx, for every x. However, when one tries to “glue” these equilibria together, one might find out that the resulting pair of strategies over [0,1] is not measurable, and in particular an equilibrium in the Harsanyi game (over T) need not exist. This finding was first noted by Bob Simon.

Since indeed the true situation the players face is the interim stage, and the ex ante stage is merely an auxiliary construction, how come the ex ante stage does not define a proper game in the interim stage? If this is the case, is the auxiliary construction of Harsanyi game over T the correct one?

## Recent Comments