The Revelation Principle

The Revelation Principle, due to Myerson (1979) in the context of Bayesian games (and to others in related contexts), is an important tool for designing games when the players have privat information. It can be applied in the auction and bilateral-trading problems described in the previous two sections, as well as in a wide variety of other problems. In this section we state and prove the Revelation Principle for static Bayesian games. (Extending the proof to cover dynamic Bayesian games is straightforward.) Before doing so, however, we sketch the way the Revelation Principle is used in the auction and bilateral-trading problems.

Consider a seller who wishes to design an auction to maximize his or her expected revenue. Specifying the many different auctions the seller should consider could be an enormous task. In the auction in Section 3.2.B, for example, the highest bidder paid money to the seller and received the good, but there are many other possibilities. The bidders might have to pay an entry fee. More generally, some of the losing bidders might have to pay money, perhaps in amounts that depend on their own and others' bids. Also, the seller might set a reservation price—a floor below which bids will not be accepted. More generally, the good might stay with the seller with some probability, and might not always go to the highest bidder when the seller does release it.

Fortunately, the seller can use the Revelation Principle to simplify this problem dramatically, in two ways. First, the seller can restrict attention to the following class of games:

1. The bidders simultaneously make (possibly dishonest) claims about their types (i.e., their valuations). Bidder i can claim to be any type r, from i's set of feasible types Tt-, no matter what i's true type, tj.

2. Given the bidders' claims (n,..., rn), bidder i pays ..., rM) and receives the good with probability (^¡(r^ , r«). For each possible combination of claims {t\, ... ,r„), the sum of the probabilities cji (tj ,..., t„) + - • • + qn(rj,..., r„) must be less than or equal to one.

Games of this kind (i.e., static Bayesian games in which each player's only action is to submit a claim about his or her type) are called direct mechanisms.

The second way the seller can use the Revelation Principle is to restrict attention to those direct mechanisms in which it is a Bayesian Nash equilibrium for each bidder to tell the truth—that is, payment and probability functions {x\ (ti ,..., rn),..., xn (t\ ,..., Tn); qi (n,..., t„),..., q„ (ti,..., r„)} such that each player i's equilibrium strategy is to claim r,(i,) = tl for each ti in T,. A direct mechanism in which truth-telling is a Bayesian Nash equilibrium is called incentive-compatible.

Outside the context of auction design, the Revelation Principle can again be used in these two ways. Any Bayesian Nash equilibrium of any Bayesian game can be represented by a new Bayesian Nash equilibrium in an appropriately chosen new Bayesian game, where by "represented" we mean that for each possible combination of the players' types (t\,... ,tn), the players' actions and payoffs in the new equilibrium are identical to those in the old equilibrium. No matter what the original game, the new Bayesian game is always a direct mechanism; no matter what the original equilibrium, the new equilibrium in the new game is always truth-telling. More formally:

Theorem (The Revelation Principle) Any Bayesian Nash equilibrium of any Bayesian game can be represented by an incentive-compatible direct mechanism.

In the auction analyzed in Section 3.2.B we assumed that the bidders' valuations are independent of each other. We also assumed (implicitly, in the definition of the bidders' valuations) that knowing bidder j's valuation would not change bidder i's valuation (although such knowledge typically would change i's bid). We characterize these two assumptions by saying that the bidders have independent, private values. For this case, My-erson (1981) determines which direct mechanisms have a truth-telling equilibrium, and which of these equilibria maximizes the seller's expected payoff. The Revelation Principle then guarantees that no other auction has a Bayesian Nash equilibrium that yields the seller a higher expected payoff, because such an equilibrium of such an auction would have been represented by a truth-telling equilibrium of a direct mechanism, and all such incentive-compatible direct mechanisms were considered. Myerson also shows that the symmetric Bayesian Nash equilibrium of the auction analyzed in Section 3.2.B is equivalent to this payoff-maximizing truth-telling equilibrium (as are the symmetric equilibria of several other well-known auctions).

As a second example of the Revelation Principle in action, consider the bilateral trading problem described in Section 3.2.C. We analyzed one possible trading game the buyer and seller could play—the double auction. In that game, if there is trade then the buyer pays something to the seller, while if there is no trade then there is no payment, but there are again many other possibilities. There could be payments (from the buyer to the seller, or vice versa) even if there is no trade, and the probability of trade could be strictly between zero and one. Also, the rule for determining whether trade is to occur could require that the buyer's offer exceed the seller's demand by a certain (positive or negative) amount; this amount could even vary depending on the prices the parties name.

We can capture these possibilities by considering the following class of direct mechanisms: the buyer and the seller simultaneously make claims about their types, rb and rs, after which the buyer pays the seller x(rb, ts), which could be positive or negative, and the buyer receives the good with probability q(rb, rs). Myerson and Satterthwaite determine which direct mechanisms have a truth-telling equilibrium. They then impose the constraint that each type of each party be willing to play the game (i.e., that each type of each party have an equilibrium expected payoff no less than the payoff that type could achieve by refusing to play— namely, zero for each buyer type and ts for the seller type ts). Finally, they show that none of these incentive-compatible direct mechanisms have trade with probability one if and only if trade is efficient. The Revelation Principle then guarantees that there is no bargaining game the buyer and seller would willingly play that has a Bayesian Nash equilibrium in which trade occurs if and only if it is efficient.

To give a formal statement and proof of the Revelation Principle, consider the Bayesian Nash equilibrium s* = (s*,... in the static Bayesian game G = {Ai,..., An; Tx,..., T„;pi,... ,p„; u\,..., u„}. We will construct a direct mechanism with a truth-telling equilibrium that represents s*. The appropriate direct mechanism is a static Bayesian game with the same type spaces and beliefs as G but with new action spaces and new payoff functions. The new action spaces are simple. Player i's feasible actions in the direct mechanism are (possibly dishonest) claims about i's possible types. That is, player i's action space is T,. The new payoff functions are more complicated. They depend not only on the original game, G, but also on the original equilibrium in that game, s*. The crucial idea is to use the fact that s* is an equilibrium in G to ensure that truth-telling is an equilibrium of the direct mechanism, as follows.

Saying that s* is a Bayesian Nash equilibrium of G means that for each player i, s* is i's best response to the other players' strategies (s*,..., s*_1, s*+1,..., s*). More specifically, for each of i's types tj in T{, s* (tj) is the best action for i to choose from A{, given that the other players' strategies are (s*,..., s*_4, s*+1,..., s*). Thus, if i's type is i, and we allow i to choose an action from a subset of A, that includes s* (f,-), then i's optimal choice remains s*(i,), again assuming that the other players' strategies are (s^,... ... ,s*). The payoff functions in the direct mechanism are chosen so as to confront each player with a choice of exactly this kind.

We define the payoffs in the direct mechanism by substituting the players' type reports in the new game, t — (ri,...,rn), into their equilibrium strategies from the old game, s*, and then substituting the resulting actions in the old game, s*(r) = (s|(ri),..., s*(t„)), into the payoff functions from the old game. Formally, i's payoff function is

Vt(T, t) = Uj[s* (t) , t], where t = (f1;... ,tn). One could imagine these payoffs occurring because a neutral outsider approaches the players and makes the following speech:

I know you already know your types and were about to play the equilibrium s* in the game G. Here is a new game to play—a direct mechanism. First, each of you will sign a contract that allows me to dictate the action you will take when we later play G. Second, each of you will write down a claim about your type, Tj, and submit it to me. Third, I will use each player's type report in the new game, r,-, together with the player's equilibrium strategy from the old game, s*, to compute the action the player would have taken in the equilibrium s* if the player's type really were t,-— namely, s*(t,-). Finally, I will dictate that each of you to take the action I have computed for you, and you will receive the resulting payoffs (which will depend on these actions and your true types).

We conclude this section (and the proof of the Revelation Principle) by showing that truth-telling is a Bayesian Nash equilibrium of this direct mechanism. By claiming to be type t; from T„ player i is in effect choosing to take the action s*(r,) from Ai. If all the other players tell the truth, then they are in effect playing the strategies (sj,..., s*_i, s*+1,..., s*). But we argued earlier that if they play these strategies, then when z's type is £,-the best action for i to choose is s*(£;). Thus, if the other players tell the truth, then when z's type is f; the best type to claim to be is t{. That is, truth-telling is an equilibrium. More formally, it is a Bayesian Nash equilibrium of the static Bayesian game {Tj,..., Tn; r1;..., T„;pi,... ,p„;vi,..., vn} for each player i to play the truth-telling strategy t;(t,) = £; for every i; in T;.

Fast Freelancing Funds

Fast Freelancing Funds

Learning About Fast Freelancing Funds Can Have Amazing Benefits For Your Life And Success! Get Instant Work And Fast Cash With Your Skills! Everybody could use some surplus money, especially in hard times.

Get My Free Ebook


Post a comment