CORE DISCUSSION PAPER 2002/14 Values for Cooperative Games with Incomplete Information: an Eloquent Example Geoffroy de Clippel1 January 2002 Abstract Myerson (1984b)’s extension of the λ-transfer value to cooperative games with incomplete information focus among other things on the strength of the incentive constraints at the solution for determining the power of coalitions. We construct an intuitive three-player game where the player whose only contribution is to partly release the two other players from the incentive constraints they face when they co- operate, receives a zero payoff, according to Myerson’s solution. On the contrary, the random order arrival procedure attributes a strictly positive payoff to him. Our example is thus an analog of the banker game of Owen (1972) that was designed for evaluating the λ-transfer value under complete information. Asymmetric information now takes up the role that was formerly attributed to the lack of transferability of utilities. JEL Classification: C71. 1Aspirant FNRS; CORE, Université catholique de Louvain, Belgium; e-mail: declip- pel@core.ucl.ac.be. Special thanks to Professors Jean-François Mertens and Enrico Minelli; errors are mine. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed by the author. Introduction Shapley (1969) designed the fictitious transfer procedure in order to extend the value he introduced in 1953, to the class of NTU games. The per- tinence of the so-defined λ-transfer value, was tested afterwards in many different ways. In particular, the banker game of Owen (1972) appeared to be a very con- structive example. Two players generate some surplus by cooperating (e.g. via the provision of a public good, or via mutually beneficial exchanges), but are limited in their ability to share this surplus. The third player (the “banker”) can only release them from this restriction, but creates no real additional surplus. In this context, should the banker receive a strictly positive payoff or not? According to the λ-transfer value, the answer is no. Other fairness criteria, such as the random order arrival procedure (cf. Maschler and Owen (1989)), imply a positive answer to the question. Myerson (1984b) generalized the fictitious transfer procedure in order to ex- tend Shapley (1953)’s value, to the class of cooperative games with incomplete information. The so-defined M-solution focus among other things on the strength of the incentive constraints at the solution for determining the power of coalitions. Starting from the bargaining problem studied in section 10 of Myerson (1984a), we add a third player whose only contribution is to partly release the two original players from the incentive constraints they face when they cooperate. Some may consider this contribution important enough for giving a strictly positive payoff to player 3 in any fair solution. The random order arrival procedure appears to abide to this principle, while Myerson (1984b)’s solution does not. The Example Let us consider the following cooperative game with incom- plete information: (using concepts and notations introduced in section 2 of My- erson (1984b)) N = {1, 2, 3}, T1 = {L, H}, T2 = T3 = {∗}, Prob(L) = 0.2, D{1} = {d1}, D{2} = {d2}, D{3} = {d3}, D{1,3} = {[d1, d3]}, D{2,3} = {[d2, d3]}, D{1,2} = {[d1, d2], d12, d21}, D{1,2,3} = {[d1, d2, d3], [d12, d3], [d21, d3], d213, d312}, and [d1, d2, d3] [d12, d3] [d21, d3] d213 d312 u1(., L) 0 30 −60 0 0 u1(., H) 0 90 0 0 0 u2(., L) 0 0 90 30 0 u2(., H) 0 0 90 90 0 u3(., L) 0 0 0 0 30 u3(., H) 0 0 0 0 90 1 We observe that the game has orthogonal coalitions (cf. section 6 of Myerson (1984b)). Let S be a coalition. A mechanism for S is a function mS : TS → ∆(DS). When S is different from {1, 2} or {1, 2, 3}, there exists only one mechanism, as DS then corresponds to a singleton. Let S be the coalition {1, 2} or the grand coalition and let mS be a mechanism. Then, mS is incentive compatible if ∑ d∈DS mS(d|t)u1(d, t) ≥ ∑ d∈DS mS(d|t′)u1(d, t), for each t ∈ {L, H} and each t′ ∈ {L, H} \ {t}. In other words, mS is incentive compatible if and only if player 1 does not have a strict interest to lie when he has to report his type. We may interpret the game as follows. Players 1 and 2 face a bilateral trade problem with incomplete information. Player 2 owns one unit of a good that has no value for himself, but that has some value for player 1. This value can be relatively low (30$), with probability 0.2, or relatively high (90$), with probability 0.8. Decision [d1, d2] represents the no-exchange alternative. Decision d12 (resp. d21) represents the situation where player 1 receives the good from player 2 for free (resp. in exchange of 90$). Any other transfer of money from player 1 to player 2 (between 0$ and 90$) can be represented by a lottery defined on {d12, d21}. Although utilities are transferable ex-post, the two players are limited in their abilities to share the cooperative gains at the interim stage. Indeed, the mechanism (2 3d12 + 1 3d21, d21) that is needed in order to give the entire surplus to player 2 in both states, is not incentive compatible. Player 3 does not generate any surplus ex-post. Nor does he help players 1 and 2 for transfering utility between themselves, as it was the case for the banker game. Nevertheless, his participation allows to partly release them from the incentive constraints they face when they cooperate. Indeed, the collective actions d213 and d312 are added to D{1,2} ×D{3} in the definition of D{1,2,3}. Decision d213 (resp. d312) amounts to give the whole surplus to player 2 (resp. 3) in both states of the world. Putting some positive weight on d312 allows to reward player 3 for his services. Before analyzing the game, let us introduce some additional notations and concepts. Let m and m′ be two mechanisms for the grand coalition. Then, m′ interim Pareto dominates m if u1(m′(L), L) ≥ u1(m(L), L), u1(m′(H), H) ≥ u1(m(H), H), 0.2u2(m′(L), L)+0.8u2(m′(H), H) ≥ 0.2u2(m(L), L)+0.8u2(m(H), H), 0.2u3(m′(L), L) + 0.8u3(m′(H), H) ≥ 0.2u3(m(L), L) + 0.8u3(m(H), H), with at least one of the four inequalities being strict. The mechanism m is interim in- centive efficient if it is incentive compatible and there does not exist any other incentive compatible mechanism that interim Pareto dominates it. A TU-game is a function v : P (N) → R. Shapley (1953)’s value is denoted Sh. In what follows, we assume that it appropriately represents fairness for TU-games with complete information. 2 Myerson (1984b)’s solution is an extension of the λ-transfer value (cf. Shapley (1969)), defined for cooperative games with incomplete information. The virtual utilities used in order to express interpersonal comparisons of utilities, do not only involve a possible rescaling of the individual utilities, but also some adjustment associated to the presence of incentive constraints. For our game, a mechanism m for the grand coalition is an M-solution if it is incentive compatible and there exist a vector (λ1.L, λ1.H ;λ2;λ3) ∈ R4 ++ and a vector (α(L|H), α(H|L)) ∈ R2 + such that   (1) λ1.L + λ1.H + λ2 + λ3 = 3 (2) v1(m(L), L, λ, α) = Sh1(v(L, λ, α)) (3) v1(m(H), H, λ, α) = Sh1(v(H, λ, α)) (4) 0.2v2(m(L), L, λ, α) + 0.8v2(m(H), H, λ, α) = 0.2Sh2(v(L, λ, α)) + 0.8Sh2(v(H, λ, α)) (5) 0.2v3(m(L), L, λ, α) + 0.8v3(m(H), H, λ, α) = 0.2Sh3(v(L, λ, α)) + 0.8Sh3(v(H, λ, α)) (6) α(H|L)(u1(m(L), L)− u1(m(H), L)) = 0 (7) α(L|H)(u1(m(H), H)− u1(m(L), H)) = 0 where, for each d ∈ D{1,2,3},   v1(d, L, λ, α) := 1 0.2 [(λ1.L + α(H|L))u1(d, L)− α(L|H)u1(d, H)] v1(d, H, λ, α) := 1 0.8 [(λ1.H + α(L|H))u1(d, H)− α(H|L)u1(d, L)] v2(d, L, λ, α) := λ2u2(d, L) v2(d, H, λ, α) := λ2u2(d, H) v3(d, L, λ, α) := λ3u3(d, L) v3(d, H, λ, α) := λ3u3(d, H) and, for each t ∈ {L, H}, v(t, λ, α) is the TU-game whose value is zero for each coalition different from {1, 2} and {1, 2, 3}. When S equals {1, 2} or {1, 2, 3}, then1 v(S, t, λ, α) := max d∈DS ∑ i∈S vi(d, t, λ, α). Condition (1) amounts to a simple normalization of the vector λ. On the other hand, conditions (6) and (7) are traditional complementary slackness conditions. Given λ and α, the number vi(d, t, λ, α) is the virtual utility of decision d in state t for player i. It amounts to a rescaling of ui(d, t) that is then adjusted by the utility received for d by the other types of player i. The vector α influences the virtual util- ity for player 1 only if some incentive constraint is binding at the solution. It can be shown that any M-solution is interim incentive efficient, that the vector λ support- ing it, is orthogonal to the set of utility profiles achievable by incentive compati- ble mechanisms at the utility profile (u1(m(L), L), u1(m(H), H); 0.2u2(m(L), L)+ 0.8u2(m(H), H); 0.2u3(m(L), L) + 0.8u3(m(H), H)), and that the vector α corre- sponds to a list of dual variables associated to the incentive constraints involved 1The expression is well-defined, even in the case where S = {1, 2}, as the game has orthogonal coalitions. 3 in this linear programming problem. The warrant equations (2)-(5) can be inter- preted as follows. Considering that, in (λ, α)-virtual utilities, types are verifiable and utilities are transferable, the players should agree on a mechanism that gen- erates the (λ, α)-virtual utility profile (Sh1(v(L, λ, α)), Sh1(v(H, λ, α)); 0.2Sh2(v(L, λ, α)) + 0.8Sh2(v(H, λ, α)); 0.2Sh3(v(L, λ, α)) + 0.8Sh3(v(H, λ, α))). Following Shapley (1969)’s philosophy, the vector (λ, α) specifying the relevant virtual utility scales, is then determined endogenously in order to obtain the fea- sibility of the corresponding (λ, α)-virtually fair utility profile. It can be shown that (15, 45; 39; 0) (which is simply the interim evaluation of the Shapley values of the ex-post games) is the only utility profile that can be supported by an M-solution in our three-player game. For instance, the mechanism (1 2d12 + 1 2d213, 1 2d12 + 1 2d213) is an M-solution for λ = (0.2, 0.8; 1; 1) and α = (0, 0) (virtual and real utilities then coincide). It is natural to take α(L|H) = α(H|L) = 0, as the mechanism is ex-post optimal, which means that the incentive constraints are not essential. We observe that player 3 is considered de facto as a null player according to the M-solution. This is due to the fact that the virtual value of coalition {1, 2} is computed while using the vector (λ, α) as specified for the grand coalition. By doing so, we act as if incentive constraints don’t matter in coalition {1, 2}, although they do. Even though it is true that player 3 does not create any surplus per se, it could look fair to give him some positive payoff, as players 1 and 2 have to rely on him in order to weaken the incentive constraints they face when they cooperate. As it was the case for the banker game under complete information, the random order arrival procedure generates an interesting alternative to the M- solution in our example. This procedure could also be considered as being the natural generalization of the random dictatorship approach proposed by Myerson (1984a) to games involving more than two players. We formalize explicitely the procedure via a Bayesian game in extensive form, in order to take asymmetric information correctly into account. After player 1 has learned his type, nature chooses a specific ordering o of the three players, according to a uniform probability distribution. Afterwards, player o(3) proposes a mechanism m for the grand coalition. Player o(2) then chooses wether to accept player o(3)’s proposal. If he accepts, then player o(1) chooses wether to accept m. If both players accepted m, then it is implemented. If player o(2) rejects m, then he proposes a mechanism m′ for coalition {o(1), o(2)} and player o(3) is left alone, having to choose d3. Player o(1) chooses wether to accept player o(2)’s proposal. If he accepts, then m′ is implemented. Whenever player o(1) rejects some proposition, there is no cooperation, and the outcome is [d1, d2, d3]. In the following table, we record the six possible enumeration of the three 4 players, and we indicate the unique utility profile that is supported by some weak perfect Bayesian equilibrium in the corresponding subgame. o MW (o) (1, 2, 3) (0, 0; 72; 6) (1, 3, 2) (0, 0; 78; 0) (2, 1, 3) (30, 90; 0; 0) (2, 3, 1) (30, 90; 0; 0) (3, 1, 2) (0, 0; 78; 0) (3, 2, 1) (30, 90; 0; 0) In the first enumeration, player 2 proposes the mechanism ([d1, d2], d21) to player 1. This amounts to solve a simple screening game. Given the associated reservation utilities (0, 0; 72) for players 1 and 2, player 3 obtains an expected pay- off of 6 in equilibrium by proposing, for instance, the mechanism (d312, d213). When player 2 is the first mover, he obtains an expected payoff of 78 in equilibrium by proposing, for instance, the mechanism (d213, d213), which satisfies the interim individual rationality constraints of players 1 and 3. When player 1 is the first mover, matters could be more complicated as we have to solve a signalling game. Nevertheless, in our case, the mechanism ([d12, d3], [d12, d3]) is the most prefered by both types of player 1 and it satisfies the ex-post individual rationality constraints of players 2 and 3 (it is a strong solution in the sense of Myerson (1983)). In equilibrium, player 1 of type L (resp. H), obtains a payoff of 30 (resp. 90). Similarly, for the enumeration (2, 1, 3), player 1 and 2 “agree” on the mechanism (d12, d12), so that there are no more surplus left for player 3 who has to distribute the reservation utilities (30, 90; 0) to players 1 and 2. The unique utility profile that can be supported by some weak perfect Bayesian equilibrium in the previously defined game in extensive form, is the mean of the six vectors appearing in the right column of the table, which is equal to (15, 45; 38; 1). As this utility profile is interim incentive efficient, it could be considered as a fair solution in the utility space. Comparing this solution with the utility profile that is supported by the M- solution, it is as if player 2 was paying 1$ to player 3 in exchange of his services. This looks reasonable, as only player 2 needs the help of player 3 in order to extract the cooperative surplus in both states. Concluding Comment Under complete information, examples such as the banker game, stimulated further research that increased our understanding of the concept of fairness for NTU games. We consider the following related contributions 5 as fundamental. Aumann (1985) axiomatized the λ-transfer value, Maschler and Owen (1989-1992) proposed an attractive alternative value based on the random order arrival procedure, and Hart and Mas-Collel (1996) studied explicit bargain- ing procedures in order to support the consistent Shapley value of Maschler and Owen (1992). In this context, the present note should not be considered at all as a criticism against Myerson (1984b)’s solution. Instead, it is aimed at stimulating further research on the topic of values for cooperative games with incomplete information. References [1] Aumann, R. J. (1985), “An Axiomatization of the Non-Transferable Utility Value”, Econometrica, 53(3), 599-612. [2] Hart, S., and A. Mas-Collel (1996), “Bargaining and Value”, Econometrica, 64(2), 357-380. [3] Maschler, M., and G. Owen (1989), “The Consistent Shapley Value for Hyperplane Games”, International Journal of Game Theory, 18, 389-407. [4] Maschler, M., and G. Owen (1992), “The Consistent Shapley Value for Games without Side Payments”, in “Rational Interaction” edited by R. Selten, Springer Verlag, 5-11. [5] Myerson, R. B. (1983), “Mechanism Design by an Informed Principal”, Econometrica, 51, 1767-1797. [6] Myerson, R. B. (1984a), “Two-Person Bargaining Problems with Incom- plete Information”, Econometrica, 52(2), 461-487. [7] Myerson, R. B. (1984b), “Cooperative Games with Incomplete Informa- tion”, International Journal of Game Theory, 13(2), 69-96. [8] Owen, G. (1972), “Values of Games without Side Payments”, International Journal of Game Theory, 1, 95-109. [9] Shapley, L. S. (1953), “A Value for n-person Games”, in H. Kuhn and A. W. Tucker eds., “Contributions to the Theory of Games II”, pages 307-317, Princeton University Press. [10] Shapley, L. S. (1969), “Utility Comparisons and the Theory of Games”, in La Decision, G. Th. Guilbaud, ed. Paris: CNRS, pp 251-263. 6