Essays on competition and cooperation in game theoretical models

UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Departamento de Estatística e Investigación Operativa ESSAYS ON COMPETITION AND COOPERATION IN GAME THEORETICAL MODELS Julio González Díaz Santiago de Compostela, April 2005 Supported by the Ministerio de Educación y Ciencia and FEDER, under projects BEC2001-0535 and BEC2002- 04102-C02-02 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Departamento de Estatística e Investigación Operativa Essays on Competition and Cooperation in Game Theoretical Models PhD candidate Julio González Díaz Advisors: Ignacio García Jurado Estela Sánchez Rodríguez Santiago de Compostela, April 22, 2005 A mi familia, por hacerlo todo más fácil... Un pelda˜no m´as Preface This thesis is the result of my first four years as a researcher in game theory. Nonetheless, my devotion for games, specially the zero-sum ones, is much older than that. I would say that it really began when I first saw my eldest brother playing chess with my father; by that time I was six years old. Both of them passed me the love for this game, which I still practice. Apart from chess, I have also wasted part of my leisure time over the last few years playing computer games, cards, and many other board and table games with my family and friends. It was not before the fifth year of my undergraduate studies in Mathematics that I realized that the scope of the theory of games goes far beyond simple (and not so simple) diversions. My first formal approach to game theory was during a course taught by Ignacio García Jurado. After Ignacio’s course, games were not just a hobby anymore. Hence, after finishing the degree, I joined the PhD program of the Department of Statistics and Operations Research with the idea of writing my thesis in game theory. Soon after that, Ignacio became my advisor. He is the one who has helped me most during these four years, not only because of his academic guidance, but also for being the main responsible for the fruitful years I have spent as a game theorist so far. Many thanks, Ignacio, for the time you have spent on me. Many thanks, too, to my other advisor, Estela, for all the time she has devoted to this thesis; mainly through her co-authorship in Chapters 5, 6, and 7. Thanks for all the discussions, so central to the core of this thesis. Joint research with different people has helped me to deepen into game theory and to understand many other aspects of a researcher’s life. Hence, I am grateful to all my co-authors: Ignacio, Estela, Peter, Henk, Ruud, Marieke, and Antonio. Besides, special thanks to my advanced mathematics consultants: Roi and Carlitos for their helpful discussions that contributed to most of the Chapters of this thesis, mainly through Chapters 5 and 6. I have also had the possibility of visiting some prestigious universities during these years. These stays have substantially influenced my formation not only as a researcher, but also in many other aspects of life. Because of this, I am indebted to Peter, Henk, Ruud, Arantza,. . . and all the people at CentER for the pleasant atmosphere I had during my three-month visit to Tilburg University. I am also indebted to Inés and Jordi for having invited me to visit the Unit of Economic Analysis of the Universitat Autònoma de Barcelona, and to the other members of the Department for their reception; I am specially grateful to the PhD students at IDEA for their iii iv Preface warm welcome, where Sergio and Joan deserve a special mention. Finally, I am deeply indebted to William for inviting me to visit the Department of Economics of Rochester University. My gratitude to all the members of the Department, to the PhD students, to Diego, Paula, Ricardo, Cagatay, and many others. Moreover, William’s influence on this thesis goes further than just the invitation to visit Rochester University. He has taught to me some of the secrets of correct (scientific) writing, and I have tried to follow his credo throughout this thesis. Unfortunately, it was already too late to implement his principles in some of the chapters of this thesis (in the others just blame me for my inaptitude). I deeply appreciate the kind support from the group of Galician game theorists and from the people in the Department of Statistics and Operations Research. I am also grateful to my two officemates, Rosa and Manuel. Because of them I have developed my research in a very comfortable environment. Also, thanks Manuel for your countless LaTeX recommendations. Finally, I want to mention all the other PhD students at the Faculty of Mathematics for the enjoyable conversations and discussions during the daily coffee breaks. Thanks to Marco, Carlitos, Tere, Bea,. . . . Last, but not least, I have to render many thanks to my family and to my friends. They have provided me with a very pleasant and relaxed atmosphere during all these years. Julio González Díaz April 2005, Santiago de Compostela Contents Preface iii Contents v Notations vii I Noncooperative Game Theory 1 Introduction 3 Short Bibliography ...................................... 4 1 A Silent Battle over a Cake 5 1.1 Introduction........................................ 6 1.2 TheModel ........................................ 7 1.3 TwoPlayers........................................ 9 1.4 MorePlayers ....................................... 14 1.5 ConcludingRemarks................................... 19 Bibliography ......................................... 20 2 Finitely Repeated Games: A Generalized Nash Folk Theorem 21 2.1 Introduction........................................ 22 2.2 Basic Notation, Definitions and an Example . . . . . . . . . . . . . . . . . . . . . . 23 2.3 TheTheorem....................................... 26 2.4 Unobservable Mixed Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 ConcludingRemarks................................... 31 Bibliography ......................................... 32 3 Unilateral Commitments in Repeated Games 33 3.1 Introduction........................................ 34 3.2 Notation.......................................... 35 3.3 TheFolkTheorems.................................... 39 3.4 ConcludingRemarks................................... 44 Bibliography ......................................... 46 4 A Noncooperative Approach to Bankruptcy Problems 47 4.1 Introduction........................................ 48 4.2 The Model and the Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3 Bankrupcty Games and Bankruptcy Rules . . . . . . . . . . . . . . . . . . . . . . . 53 4.4 ConcludingRemarks................................... 55 Bibliography ......................................... 56 v 4 Introduction to Noncooperative Game Theory Short Bibliography Benoît, J.-P. and V. Krishna (1987): “Nash Equilibria of Finitely Repeated Games,” International Journal of Game Theory, 16, 197–204. (Quoted in pp. 3) García-Jurado, I. and J. González-Díaz (2005): “Unilateral Commitments in Repeated Games,” Preprint. (Quoted in pp. 3) García-Jurado, I., J. González-Díaz, and A. Villar (2004): “A Noncooperative Approach to Bankruptcy Problems,” Preprint. (Quoted in pp. 3) García-Jurado, I., L. Méndez-Naya, and F. Patrone (2000): “Unilateral Commitments in Finitely Repeated Games,” International Game Theory Review, 2, 129–139. (Quoted in pp. 3) González-Díaz, J. (2003): “Finitely Repeated Games: A Generalized Nash Folk Theorem,” Tech. Rep. 03-08, Department of Statistics and OR, University of Santiago de Compostela, to appear in Games and Economic Behavior. (Quoted in pp. 3) González-Díaz, J., P. Borm, and H. Norde (2004): “A Silent Battle over a Cake,” Tech. rep., CentER discussion paper series. (Quoted in pp. 3) Hamers, H. (1993): “A Silent Duel over a Cake,” Methods and Models of Operations Research, 37, 119–127. (Quoted in pp. 3) Smith, L. (1995): “Necessary and Sufficient Conditions for the Perfect Finite Horizon Folk Theorem,” Econometrica, 63, 425–430. (Quoted in pp. 3) Chapter 1 A Silent Battle over a Cake Contents 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Two Players . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 More Players . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Bibliography ................................... 20 5 6 Chapter 1. A Silent Battle over a Cake 1.1 Introduction There are many strategic situations in which some agents face a decision problem in which timing is important. The literature on timing games has been devoted to analyze these situations and provide theoretical models to study the underlying strategic problem. A first approach to timing games appears in Karlin (1959) in the zero sum context. More recent contributions are Baston and Garnaev (2000) and Laraki et al. (2003). A classic example of timing game is the war of attrition, introduced in Smith (1974) and widely studied, for instance, in Hendricks et al. (1988). More specifically, consider the following war of attrition game. Two rival firms are engaged in a race to make a patentable discovery, and hence, as soon as one firm makes the discovery, all the previous effort made by the other firm turns out to be useless. This patent race model has been widely studied in literature (see, for instance, Fudenberg et al. (1983)). In this model it is assumed that, as soon as one of the firms leaves the race, the game ends. The motivation for this assumption is that, once there is only one firm in the race, the game reduces to a decision problem in which the remaining firm has to optimize its resources. Hence, the strategy of each firm consists of deciding, for each time t, whether to leave the race or not. Most of the literature in timing games models what we call non-silent timing games, that is, as soon as one player acts, the others are informed and the game ends.1In this Chapter, on the contrary, we provide a formal model for the silent situation. We use again the patent race to motivate our approach. Consider a situation in which two firms are engaged in a patent race and also in an advertising campaign. Suppose that one of the two rival firms, say firm 1, decides to leave the patent race. Then, it will probably be the case that firm 1 does not want firm 2 to realize that 1 is not in the race anymore; and therefore, firm 1 can get a more advantageous position for the advertising campaign. Moreover, if firm 2 does not realize about the fact that firm 1 has already left the race, it can also be the case that, having already firm 1 left the race, firm 2 leaves the race before making the discovery, benefiting again firm 1. Next, we introduce our silent timing game. We consider the situation that nplayers have to divide a cake of size S. At time 0 player ihas the initial right to receive the amount αi, where it is assumed that Pi∈Nαi< S. If player iclaims his part at time t > 0then he receives the discounted part δtαiof the cake, unless he is the last claimant in which case he receives the discounted remaining part of the cake δt(S−Pj6=iαj). We refer to this game as a cake sharing game. Hamers (1993) showed that 2-player cake sharing games always admit a unique Nash equilibrium. In this Chapter we consider cake sharing games that are slightly different from the games introduced in Hamers (1993). We first provide an alternative, but more direct, existence and uniqueness result for 2-player cake sharing games and we generalize this result to cake sharing games with more players. It is worth to mention the similarities between our results and some well known results in all- 1An exception is Reinganum (1981), although her model is very different from ours. 1.2. The Model 7 pay auctions (Weber, 1985). At first glance, our model seems quite different from that of all-pay auctions, but it turns out to be the case that they have many similarities. Indeed, in this Chapter we show that the same kind of results obtained for the all-pay auction (Hilman and Riley, 1989; Baye et al., 1996) can be obtained for our timing game. Anyhow, even when both the results and also the arguments underlying some of the proofs are very similar, the two models are different enough so that our results can not be derived from those in the all-pay auctions literature. This Chapter is organized as follows. In Section 1.2 we introduce the cake sharing games. In Sections 1.3 and 1.4 we deal with 2-player cake sharing games and more player cake sharing games, respectively. 1.2 The Model In this Section we formally introduce the cake sharing games. Let N={1,...,n}be a set of players with n≥2, let S > 0, let α= (α1,...,αn)∈RN + be such that α1+···+αn< S, and let δ∈(0,1). Throughout this Chapter we assume that 0< α1< α2<···< αn. The number Sis called the size of the cake, the vector αthe initial right vector and δthe discount factor. The cake sharing game with pure strategies associated with S,α, and δ, is the triple Γpure S,α,δ := (N, {Ai}i∈N,{πi}i∈N), where Ai:= [0,∞)is the set of pure strategies of player i∈N, πiis the payoff function of player i∈N, defined by: πi(t1,...,tn) :=    (S−X j6=i αj)δtiti>max j6=itj αiδtiotherwise. Hence, if there is a unique last claimant, then he receives the discounted value of the cake that remains after that other players have taken their initial rights. If there is not a unique last claimant, then all players receive the discounted value of their initial rights. Note that the payoff functions defined above differ slightly from the payoff functions introduced in Hamers (1993), where, in case there is not a unique last claimant, the discounted value of the remaining cake is shared equally between the last claimants. This change in the model does not affect the results, but it helps to have cleaner proofs. 2 One easily verifies that Γpure S,α,δ has no Nash equilibria. If there is a unique last claimant, then this player can improve his payoff by claiming a little bit earlier (and remaining the last 2Let us make some comments concerning the relation between the cake sharing game (CS) and the all-pay auctions model (AP). For simplicity, we think of the two player case. Setting aside the issue of timing, note the following differences: (i) Initial rights: in CS they depend on the player (αi), in AP they are 0; (ii) in CS each player wants to get 1−(α1+α2), in AP the valuation of the object depends on the player; and (iii) In CS waiting till time t, each player is “paying” αi−(αi)δt,i.e., it depends on the player, in AP bidding v, each player is “paying” v. All the other strategic elements are analogous in the two models. 8 Chapter 1. A Silent Battle over a Cake claimant). If there is no unique last claimant, then one of the last claimants can improve his payoff by claiming a little bit later (becoming the unique last claimant in this way). Hence, for an appropriate analysis of cake sharing games we need to consider mixed strategies. Formally, a mixed strategy is a function G: [0,∞)→[0,1] satisfying: G(0) = 0, Gis a nondecreasing function, Gis left-continuous, limx→∞ G(x) = 1. For a mixed strategy Gwe can always find a probability measure Pon [0,∞)such that:3 for each x∈[0,∞), G(x) = P[0, x).(1.1) On the other hand, every probability measure Pon [0,∞)defines by formula (1.1) a mixed strategy G. Hence, the set of mixed strategies coincides with the set of probability measures on [0,∞).4Let Gdenote the set of all mixed strategies. We introduce now some other notations related to mixed strategy G: for each x∈[0,∞), we denote limy↓xG(y), the probability of choosing an element in the closed interval [0, x], by G(x+). if there is x > 0such that for each pair a, b ∈[0,∞), with a < x < b, we have G(b)> G(a+) (i.e., the probability of choosing an element in (a, b)is positive), then xis an element of the support of G. If for each b > 0,G(b)>0(i.e., the probability of choosing an element in [0, b)is positive), then 0is an element of the support of G. Let S(G)be the support of the distribution function G. One easily verifies that S(G)is a closed set. the set of jumps (discontinuities) of Gis J(G) := {x∈[0,∞) : G(x+)> G(x)},i.e., the set of pure strategies which are chosen with positive probability. If player ichooses pure strategy tand all other players choose mixed strategies {Gj}j6=ithen the expected payoff for player iis πi(G1,...,Gi−1, t, Gi+1,...,Gn) = Y j6=i Gj(t)δt(S−X j6=i αj) + (1 −Y j6=i Gj(t)) δtαi =δt(αi+ (S−X j∈N αj)Y j6=i Gj(t)). 3See Rohatgi (1976) for more details. 4An alternative way of defining mixed strategies Gis as a nondecreasing, right-continuous function from [0,∞) to [0,1] with limx→∞ G(x) = 1. For such a function we can always find a probability measure Pon [0,∞)such that for each x∈[0,∞),G(x) = P  [0, x]  ,i.e.,Gis the (cumulative) distribution function corresponding to P. Although this equivalent approach seems more natural, it would lead to technical problems when computing Lebesgue-Stieltjes integrals later on. 1.3. Two Players 9 If player ialso chooses a mixed strategy Gi, whereas all other players stick to mixed strategies {Gj}j6=i, then the expected payoff for player ican be computed by use of the Lebesgue-Stieltjes integral: πi(G1, . . . , Gn) = Zπi(G1,...,Gi−1, t, Gi+1,...,Gn)dGi(t).(1.2) Note that, with a slight abuse of notation, the functions πido not only denote payoffs to players when pure strategies are played, but also when mixed strategies are used. The cake sharing game associated with S,α, and δ, is defined by the triple ΓS,α,δ := (N, {Xi}i∈N,{πi}i∈N), where Xi:= Gis the set of mixed strategies of player i∈N, πi, defined by (1.2), is the (expected) payoff function of player i∈N. Given a strategy profile G= (G1, G2,...,Gn)∈ Gn, let πG i(t)be the corresponding payoff πi(G1,...,Gi−1, t, Gi+1, . . . , Gn). Hence, πG i(t)is the expected payoff for player iwhen he plays the pure strategy tand all the other players act in accordance with G. 1.3 Two Players In this Section we provide an alternative proof of the result of Hamers (1993) for 2-player cake sharing games. Our incentives for doing this job are threefold. First of all we want to recall that our model is slightly different from the model of Hamers (1993), and hence, a new proof is required. Secondly, our proof is more direct than Hamers’ proof. Finally, our proof forms the basis for the results in Section 1.4 for cake sharing games with three or more players. First, we derive a number of properties for Nash equilibria of n-player cake sharing games. The following Lemma shows that in a Nash equilibrium players do not put positive probability on a pure strategy t > 0. Lemma 1.1. Let ΓS,α,δ be an n-player cake sharing game and let the profile G= (Gi)i∈N∈ GN be a Nash equilibrium of ΓS,α,δ. Then, for each i∈N,J(Gi)∩(0,∞) = ∅. Proof. Let i∈N. We show that J(Gi)∩(0,∞) = ∅. Assume, without loss of generality, that i= 1. Suppose that u∈J(G1)∩(0,∞). If there is i6= 1 such that Gi(u+) = 0, then, for each t∈[0, u],πG 1(t) = δtα1. Since the function πG 1(·)is strictly decreasing on [0, u], player 1 would be better off moving the probability in uto 0. Hence, for each i∈N,Gi(u+)>0. Now, for each i∈N\{1}, consider the functions πG i(t) = δt(αi+ (S−X j∈N αj)Y j6=i Gj(t)). Since G1is discontinuous at u,i.e.,G1(u+)> G1(u), there are u1< u,u2> u, and ε > 0such 10 Chapter 1. A Silent Battle over a Cake that for each i6= 1 and each t∈[u1, u], πG i(u2)−πG i(t)≥ε. If player i∈N\{1}puts positive probability on [u1, u],i.e., if Gi(u+)> Gi(u1), then he can increase his payoff by at least ε(Gi(u+)−Gi(u1)) by moving all this probability to u2. Hence, for each i∈N\{1}, we have Gi(u+) = Gi(u1)and, for each t∈[u1, u],Gi(t) = Gi(u). Hence, the function πG 1(t) = δt(α1+ (S−X j∈N αj)Y j6=1 Gj(t)) is strictly decreasing on [u1, u]. Now, player 1 can improve his payoff by moving some probability from uto u1. Lemma 1.1 implies that, in a Nash equilibrium G, the players use mixed strategies which are continuous on (0,∞). Hence, for each i∈Nand each t > 0, we can write Gi(t+) = Gi(t). Moreover, the functions πG i(·)are continuous on (0,∞). Lemma 1.2. Let ΓS,α,δ be an n-player cake sharing game and let the profile G= (Gi)i∈N∈ GN be a Nash equilibrium of ΓS,α,δ. Let i∈Nand t∈S(Gi). Then, there is j∈N\{i}such that t∈S(Gj). Proof. Suppose that t /∈ ∪j6=iS(Gj). We distinguish between two cases: Case 1: t > 0. There are t1, t2>0, with t1< t < t2, such that for each j6=i,Gj(t2) = Gj(t1).5Hence, for each u∈[t1, t2]and each j6=i,Gj(u) = Gj(t2). Hence, the function πG i(u) = δu(αi+ (S−X j∈N αj)Y j6=i Gj(u)) is strictly decreasing on [t1, t2]. Since t∈S(Gi), we have Gi(t2)> Gi(t+ 1),i.e., player iputs positive probability on (t1, t2). Now, player ican strictly improve his payoff by moving all this probability to t1. Case 2: t= 0. Let b > 0be the smallest element in ∪j6=iS(Gj)(recall that all the S(Gj)are closed). Clearly, for each j6=i,Gj(b) = 0. Again, if Gi(b)> Gi(0+),i.e., if player iputs positive probability on (0, b), then similar arguments as in Case 1 can be used to show that player ican strictly improve his payoff by moving this probability to 0. Hence, Gi(b) = Gi(0+)and hence, since 0∈S(Gi), we have Gi(0+)>0. Moreover, for each t∈(0, b],Gi(t) = Gi(b)(this is relevant only for the 5For each j∈N\{i}there are tj 1, tj 2>0, with tj 1< t < tj 2, such that Gj(tj 2) = Gj(tj 1). Hence, we take t1= maxj∈N\{i}tj 1and t2= minj∈N\{i}tj 2. 1.3. Two Players 11 case n= 2). Hence, for each j∈N\{i}, the function πG j(t) = δt(αj+ (S−X k∈N αk)Y k6=j Gk(t)) is strictly decreasing on (0, b]. Let a∈(0, b)and let j∈N\{i}be a player such that b∈S(Gj). Let ε:= πG j(a)−πG j(b)>0. Since the function πG j(·)is continuous on (0,∞), we have that, for δ > 0sufficiently small, for each t∈[b, b +δ], πG j(a)−πG j(t)>1 2ε. Since b∈S(Gj),Gj(b+δ)>0 = Gj(b). Hence, player jcan improve his payoff by moving the probability he assigns to [b, b +δ)to a. Contradiction. The following Lemma shows that if some pure strategy tdoes not belong to the support of any of the equilibrium strategies, then no pure strategy t′> t belongs to the support of any of the equilibrium strategies either. Lemma 1.3. Let G= (Gi)i∈Nbe a Nash equilibrium of the n-player cake sharing game ΓS,α,δ. Let t∈[0,∞)be such that for each j∈N,t /∈S(Gj). Then, for each j∈N,(t, ∞)∩S(Gj) = ∅. Proof. Let K:= ∪j∈NS(Gj). Clearly, Kis closed and t /∈K. We have to show that K∩(t, ∞) = ∅. Suppose that K∩(t, ∞)6=∅. Let t∗:= min{u∈K:u > t}. Let j∗∈Nbe such that t∗∈S(Gj∗). Since for each j∈N,[t, t∗)∩S(Gj) = ∅, then we have that, for each j∈N, Gj(t) = Gj(t∗). Hence, the functions Gjare constant on [t, t∗]. Now, since for each u∈[0,∞), πG j∗(u) = δu(αj∗+ (S−X j∈N αj)Y j6=j∗ Gj(u)), then, the function πG j∗(·)is strictly decreasing on [t, t∗]. By the continuity of πG j∗(·)at t∗, for each u∈[t∗, t∗+ε], with ε > 0sufficiently small, we have πG j∗(t)> πG j∗(u). Hence, Gj∗is constant on [t∗, t∗+ε]as well, contradicting the fact that t∗∈S(Gj∗). Now, we provide specific results for 2-player cake sharing games. The following Lemma shows that, in a Nash equilibrium, the players use mixed strategies of which the supports coincide. Lemma 1.4. Let ΓS,α,δ be a 2-player cake sharing game and let (G1, G2)∈ G × G be a Nash equilibrium of ΓS,α,δ. Then, S(G1) = S(G2). Proof. This result is just a consequence of Lemma 1.2. In the following Lemma we show that the supports of the strategies in a Nash equilibrium are compact intervals. Lemma 1.5. Let ΓS,α,δ be a 2-player cake sharing game and let G= (G1, G2)∈ G×G be a Nash equilibrium of ΓS,α,δ. Let k:= logδα2 S−α1. Then, S(G1) = S(G2) = [0, k]. 12 Chapter 1. A Silent Battle over a Cake Proof. First, we show that S(G1) = S(G2)⊆[0, k]. For each t∈(k, ∞), we have πG 2(t) = δt(α2+ (S−α1−α2)G1(t)) ≤δt(α2+ (S−α1−α2)) =δt(S−α1) < δk(S−α1) =α2 =πG 2(0). If G2(k) = G2(k+)<1,i.e., if player 2 puts positive probability on (k, ∞), then he can improve his payoff strictly by moving all this probability to 0. Hence G2(k) = 1 and S(G1) = S(G2)⊆[0, k]. Let k∗be the largest element in the closed set S(G1). Clearly, k∗≤k. If k∗= 0, then (G1, G2) would be an equilibrium in pure strategies, a contradiction. Hence, k∗>0. Now, by Lemma 1.3, S(G1) = S(G2) = [0, k∗]. The only thing which remains to be shown is that k∗=k. Suppose that k∗< k. Now, for each τ∈(0, k −k∗), πG 1(k∗+τ) = δk∗+τ(α1+ (S−α1−α2)G2(k∗+τ)) =δk∗+τ(α1+ (S−α1−α2)) =δk∗+τ(S−α2) > δk(S−α2) =α2(S−α2) S−α1 ≥α1 =πG 1(0), where at the weak inequality we used that α2(S−α2)≥α1(S−α1). Hence, if G1(0+)>0,i.e., if player 1 plays pure strategy 0 with positive probability, then he can improve his payoff by moving some probability from 0 to pure strategy k∗+τ. Hence, G1(0+) = 0. Now, there is t∈(k∗, k) such that πG 2(t) = δt(α2+ (S−α1−α2)G1(t)) =δt(α2+ (S−α1−α2)) =δt(S−α1) > δk(S−α1) =α2 =πG 2(0). Since 0∈S(G1)and πG 2(·)is continuous at 0 (because G1(0+) = 0), player 2 can strictly improve his payoff by moving some probability from the neighborhood of 0 to t. Contradiction. Hence, k∗=k. Now, we are ready to prove the main theorem of this Section. 1.3. Two Players 13 Theorem 1.1. Let ΓS,α,δ be a 2-player cake sharing game and k:= logδα2 S−α1. Define G∗= (G∗ 1, G∗ 2)∈ G ×G by G∗ 1(t) :=    α2−α2δt δt(S−α1−α2)0≤t≤k 1t > k, G∗ 2(t) :=          0t= 0 α2(S−α2)−α1(S−α1)δt δt(S−α1)(S−α1−α2)0< t ≤k 1t > k. Then, G∗is the unique Nash equilibrium of ΓS,α,δ. Moreover, the equilibrium payoffs are π1(G∗ 1, G∗ 2) = α2(S−α2) S−α1 , π2(G∗ 1, G∗ 2) = α2. Proof. One easily verifies that πG∗ 1(t) =        α1t= 0 α2(S−α2) S−α1 0< t ≤k δt(S−α2)t > k, and πG∗ 2(t) = (α20≤t≤k δt(S−α1)t > k. Hence, π1(G∗ 1, G∗ 2) = α2(S−α2) S−α1 and π2(G∗ 1, G∗ 2) = α2. Since for each t∈[0,∞), π1(t, G∗ 2)≤α2(S−α2) S−α1 and π2(G∗ 1, t)≤α2, we have that G∗is a Nash equilibrium of ΓS,α,δ. In order to show that there are no other Nash equilibria, let (G1, G2)be a Nash equilibrium of ΓS,α,δ. By Lemma 1.1, the strategies G1and G2are continuous on (0,∞). In the same way as in the proof of Lemma 1.5, we can show that G1(0+) = 0. Hence, the function πG 1(·)is continuous on (0,∞)and the function πG 2(·)is continuous on [0,∞). By Lemma 1.5, S(G1) = S(G2) = [0, k]. Hence, there are constants cand dsuch that for each t∈(0, k], c =πG 1(t) = δt(α1+ (S−α1−α2)G2(t)), for each t∈[0, k], d =πG 2(t) = δt(α2+ (S−α1−α2)G1(t)). 20 Chapter 1. A Silent Battle over a Cake Bibliography Baston, V. J. and A. Y. Garnaev (2000): “On a Game in Manufacturing,” Mathematical Methods of Operations Research, 52, 237–249. (Quoted in pp. 6) Baye, M. R., D. Kovenock, and C. G. de Vries (1996): “The All-Pay Auction with Complete Information,” Economic Theory, 8, 291–395. (Quoted in pp. 7) Fudenberg, D., R. Gilbert, J. Stiglitz, and J. Tirole (1983): “Preemption, Leapfrogging and Competition in Patent Races,” European Economic Review, 22, 3–31. (Quoted in pp. 6) Hamers, H. (1993): “A Silent Duel over a Cake,” Methods and Models of Operations Research, 37, 119–127. (Quoted in pp. 6, 7, 9) Hendricks, K., A. Weiss, and C. Wilson (1988): “The War of Attrition in Continuous Time with Complete Information,” International Economic Review, 29, 663–680. (Quoted in pp. 6) Hilman, A. L. and J. G. Riley (1989): “Politically Contestable Rents and Transfers,” Economics and Politics, 1, 17–39. (Quoted in pp. 7) Karlin, S. (1959): Mathematical Methods and Theory in games. Programming and Economics, Addison-Wesley. (Quoted in pp. 6) Laraki, R., E. Solan, and N. Vieille (2003): “Continuous-time Games of Timing,” Discussion Paper 1363, Kellogg School of Management, Northwestern University. (Quoted in pp. 6) Reinganum, J. (1981): “On the Diffusion of a New Technology: A Game Theoretic Approach,” The Review of Economic Studies, 48, 395–405. (Quoted in pp. 6) Rohatgi, V. K. (1976): An Introduction to Probability Theory and Mathematical Statistics, Wiley series in probability and mathematical statistics. (Quoted in pp. 8) Smith, J. M. (1974): “The Theory of Games and Evolution in Animal Conflicts,” Journal of Theoretical Biology, 47, 209–221. (Quoted in pp. 6) Weber, R. J. (1985): “Auctions and Competitive Bidding,” in Fair Allocation, ed. by H. P. Young, American Mathematical Society, Proceedings of symposia in applied mathematics, 143– 170. (Quoted in pp. 7) Chapter 2 Finitely Repeated Games: A Generalized Nash Folk Theorem Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Basic Notation, Definitions and an Example . . . . . . . . . . . . . . 23 2.2.1 The Stage Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 The Repeated Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.3 Minimax-Bettering Ladders . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.4 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.5 Further Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 The Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Unobservable Mixed Actions . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Bibliography ................................... 32 21 22 Chapter 2. Finitely Repeated Games: A Generalized Nash Folk Theorem 2.1 Introduction Over the past thirty years, necessary and sufficient conditions have been published for numerous “folk theorems”, asserting that the individually rational feasible payoffs of finitely or infinitely repeated games with complete information can be achieved by Nash or subgame perfect equilibria.1 The original folk theorem was concerned about the Nash Equilibria of infinitely repeated games. This folk theorem stated that every individually rational feasible payoff of the original game can be obtained as a Nash Equilibrium of the repeated game; no assumption was needed for this result (a statement and proof of this result can be found in Fudenberg and Maskin (1986)). Then, the theorists turned to study subgame perfection in infinite horizon models and they found a counterpart of the previous result for undiscounted repeated games; again, no assumptions were needed (Aumann and Shapley, 1976; Rubinstein, 1979). A few years later, discount parameters were incorporated again into the model; in this case, some conditions were needed to get the perfect folk theorem (Fudenberg and Maskin, 1986). These conditions were refined in the mid-nineties (Abreu et al., 1994; Wen, 1994). Together with the previous results, also the literature on finitely repeated games grew. The main results for finite horizon models obtained conditions for the Nash folk theorem (Benoît and Krishna, 1987), and also for the perfect one (Benoît and Krishna, 1985). This perfect folk theorem relied on the fact that mixed strategies were observable; the same result but without that assumption was obtained in the mid-nineties (Gossner, 1995). Assuming again observable mixed strategies, Smith (1995) obtained a necessary and sufficient condition for the arbitrarily close approximation of strictly rational feasible payoffs by subgame perfect equilibria with finite horizon: that the game have “recursively distinct Nash payoffs”, a premise that relaxes the assumption in Benoît and Krishna (1985) that each player have multiple Nash payoffs in the stage game. Smith claimed that this condition was also necessary for approximation of the individually rational feasible payoffs of finitely repeated games by Nash equilibria. In this Chapter we show that this is not so by establishing a similar but distinct sufficient condition that is weaker than both Smith’s condition and the assumptions made by Benoît and Krishna (1987). Moreover, our condition is also necessary. Essentially, the difference between the subgame perfect and Nash cases hinges on the weakness of the Nash solution concept: in the Nash case it is not necessary for threats of punitive action against players who deviate from the equilibrium not to involve loss to the punishing players themselves, i.e., threats need not be credible. The kind of equilibrium we define in this Chapter requires for its corresponding path ρ, to finish, for each player i, with a series Qiof rounds in which icannot unilaterally improve his stage payoff by deviation from ρi, and for this terminal phase to start with a series Q0 iof rounds in which the other players, regardless of the cost to themselves, can punish him effectively for any prior deviation by imposing a loss that wipes out any gains he may have made in deviating. Many of the results mentioned above concern the approximability of the entire set of individ- 1The survey by Benoît and Krishna (1996) includes many of these results. 2.2. Basic Notation, Definitions and an Example 23 ually rational feasible payoffs. The main theorem in this Chapter is more general in that, for any game, it characterizes the set of feasible payoffs that are approximable. Although subgame perfect equilibrium is a desirable refinement of Nash equilibrium, results for the latter are still needed for games in which the perfect folk theorem does not apply. Game G in Figure 2.1 shows that, indeed, this is the case for a generic class of games. The assumptions for the perfect folk theorem do not hold for game G. Moreover, Theorem 2 in Smith (1995) implies that (3,3) is the unique payoff achievable via subgame perfect equilibrium in any repeated game such that Gis its stage game. However, every feasible and individually rational payoff, (e.g., (4,4)) can be approximated in Nash equilibrium in many of those repeated games (for small enough discount and big enough number of repetitions). L R T 3,3 6,2 B 2,6 0,0 Figure 2.1: A game for which the Nash folk theorem is needed. We have structured this Chapter as follows. We introduce notation and concepts in Section 2.2. In Section 2.3 we state and prove the main result. Next, in Section 2.4 we are concerned about unobservable mixed strategies. Finally, we conclude in Section 2.5. 2.2 Basic Notation, Definitions and an Example 2.2.1 The Stage Game Astrategic game Gis a triplet (N, A, ϕ), where: N:= {1,...,n}is the set of players, A:= Qi∈NAiand Aiis the set of player i’s strategies, ϕ:= (ϕ1,...,ϕn)and ϕi:A→Ris the payoff function of player i. Let GNbe the set of games with set of players N. We assume that, for each i∈N, the sets Aiare compact and the functions ϕiare continuous. Let a−ibe a strategy profile for players in N\{i}and A−ithe set of such profiles. For each i∈Nand each a−i∈A−i, let µi(a−i) := maxai∈Ai{ϕi(a−i, ai)}. Also, for each i∈N, let vi:= mina−i∈A−i{µi(a−i)}. The vector v:= {v1,...,vn}is the minimax payoff vector. Let Fbe the set of feasible payoffs: F:= co{ϕ(a) : a∈A}. Let ¯ Fbe the set of all feasible and individually rational payoffs: ¯ F:= F∩ {u∈Rn:u≥v}. To avoid confusion with the strategies of the repeated game, in what follows we refer to the strategies ai∈Aiand the strategy profiles a∈Aof the stage game as actions and action profiles, respectively. 24 Chapter 2. Finitely Repeated Games: A Generalized Nash Folk Theorem 2.2.2 The Repeated Game Let G(δ, T)be the game consisting in the T-fold repetition of Gwith payoff discount parameter δ∈(0,1]. In this game we assume perfect monitoring,i.e., each player can choose his action in the current stage in the light of all actions taken by all players in all previous stages. Let σbe a strategy profile of G(δ, T), and the action profile sequence ρ={ρ1, . . . , ρT}its corresponding path. Let ϕt i(ρ)be the stage payoff of player iat stage twhen all players play in accordance with ρ. Then, player i’s payoff in G(δ, T)when σis played is his average discounted stage payoff: ψi(σ)≡ψi(ρ) := ((1 −δ)/(1 −δT)) PT t=1 δt−1ϕt i(ρ).2 2.2.3 Minimax-Bettering Ladders Let Mbe an m-player subset of N. Let AM:= Qi∈MAiand let G(aM)be the game induced for the n−mplayers in N\Mwhen the actions of the players in Mare fixed at aM∈AM. By abuse of language, if i∈N\M,aM∈AM, and σ∈AN\Mwe write ϕi(σ)for i’s payoff at σin G(aM). A minimax-bettering ladder of a game Gis a triplet {N,A,Σ}, where Nis a strictly increasing chain {∅ =N0(N1(··· (Nh}of h+ 1 subsets of N(h≥1), Ais a chain of action profiles {aN1∈AN1,...,aNh−1∈ANh−1}and Σis a chain {σ1,...,σh}of Nash equilibria of G=G(aN0), G(aN1),...,G(aNh−1), respectively, such that at σlthe players of G(aNl−1)receiving payoffs strictly greater than their minimax payoff are exactly those in Nl\Nl−1: for each i∈Nl\Nl−1,ϕi(σl)> vi, and for each i∈N\Nl,ϕi(σl)≤vi. Let the sets in Nbe the rungs of the ladder. In algorithmic terms, if the first l−1rungs of the ladder have been constructed, then, for the l-th rung to exist, there must be aNl−1∈ANl−1 such that the game G(aNl−1)has an equilibrium σl. Moreover, σlhas to be such that there are players i∈N\Nl−1for whom ϕi(σl)> vi. Let Nl\Nl−1be this subset of players of G(aNl−1). The game played in the next step is defined by some action profile aNl. The set Nhis the top rung of the ladder. A ladder with top rung Nhis maximal if there is no ladder with top rung Nh′ such that Nh(Nh′. A game Gis decomposable as a complete minimax-bettering ladder if it has a minimax-bettering ladder with Nas its top rung. We show below that being decomposable as a complete minimax-bettering ladder is a necessary and sufficient condition for it to be possible to approximate all payoff vectors in ¯ Fby Nash equilibria of G(δ, T)for some δand T. Clearly, being decomposable as a complete minimax-bettering ladder is a weaker property than the requirement in Smith (1995), that at each step l−1of a similar kind of ladder there be action profiles aNl−1,bNl−1such that the games G(aNl−1)and G(bNl−1)have Nash equilibria σl aand σl bwith ϕi(σl a)6=ϕi(σl b)for a nonempty set of players (those in Nl\Nl−1). 2.2.4 An Example Let G∈ GN, let Lbe a maximal ladder of G, and Nmax its top rung. For each i∈N, let li be the unique integer such that i∈Nli\Nli−1. In the equilibrium strategy profile constructed 2Or, ψi(σ)≡ψi(ρ) := (1/T) P T t=1 ϕt i(ρ)if there are no discounts (δ= 1). 2.2. Basic Notation, Definitions and an Example 25 in Theorem 2.1 below, the action profile sequence in the terminal phase Qireferred to in the Introduction, consists of repetitions of (aNli−1, σli),(aNli−2, σli−1),...,(aN2, σ2)and σ; and the σjare Nash equilibria of the corresponding games G(aNj−1). Since player iis a player in all these games, he can indeed gain nothing by unilateral deviation during this phase. In the potentially punishing series of rounds Q0 i, the action profile sequence consists of repetitions of (aNli−1, σli), in which iobtains more than his minimax payoff, with the accompanying threat of punishing a prior unilateral deviation by iby minimaxing him instead. l m r l m r T 0, 0, 3 0,-1, 0 0,-1, 0 T 0, 3,-1 0,-1,-1 1,-1,-1 M -1, 0, 0 0,-1, 0 0,-1, 0 M -1, 0,-1 -1,-1,-1 0,-1,-1 B -1, 0, 0 0,-1, 0 0,-1, 0 B -1, 0,-1 -1,-1,-1 0,-1,-1 L R Figure 2.2: A game that is decomposable as a complete minimax-bettering ladder As an illustration of the above ideas, consider the three-player game Gshown in Figure 2.2. Its minimax payoff vector is (0,0,0), and its unique Nash equilibrium is the action profile σ1= (T, l, L), with associated payoff vector (0,0,3). Hence, N1={3}; player 3 can be punished by 1 and 2 by playing one of his minimax profiles instead of playing (T, l, ·). If player 3 now plays R (aN1=R), the resulting game G(aN1) = G(R)has an equilibrium σ2= (T, l)with payoff vector (0,3). Hence, N2={2,3}and player 2 can be punished by 1 and 3 by playing one of his minimax profiles instead of playing (T, ·, R). Finally if players 2 and 3 now play rand R(aN2= (r, R)), the resulting game G(aN2) = G(r, R)has the trivial equilibrium σ3= (T)with payoff 1 for player 1. Hence, player 1 can be punished by 2 and 3 if they play one of his minimax profiles instead of playing (·, r, R). 2.2.5 Further Preliminaries As a consequence of the next Lemma we can unambiguously refer to the top rung of a game G. Lemma 2.1. Let G∈ GN. Then, all its maximal ladders have the same top rung. Proof. Suppose there are maximal ladders L={N,A,Σ},L′={N′,A′,Σ′}with N={N0( N1(··· (Nh}and N′={N′ 0(N′ 1(··· (N′ k}such that Nh6=N′ k. Assume, without loss of generality, that N′ k\Nh6=∅. For each j∈N′ k, let ljbe the unique integer such that j∈N′ lj\N′ lj−1. Let i∈argminj∈N′ k\Nhlj. Then, N′ li−1⊆Nh. Let aNhbe the action profile defined as follows: for each j∈N, (aNh)j=((a′ N′ li−1)jj∈N′ li−1 (σ′li)jj∈Nh\N′ li−1, where σ′li∈Σ′is an equilibrium of the game G(a′ N′ li−1)induced by the action profile a′ N′ li−1∈ A′. 26 Chapter 2. Finitely Repeated Games: A Generalized Nash Folk Theorem Now, let σh+1 be the restriction of σ′lito N\Nh. Since σ′liis an equilibrium of G(a′ N′ li−1), and N\Nh⊆N\N′ li−1,σh+1 is an equilibrium of G(aNh). Moreover, the set of players j∈N\Nh for whom ϕj(σh+1)> vjis N′ li\Nh. Let Nh+1 := N′ li\Nh. Since Nh+1 contains i, it is nonempty. Let L′′ ={N′′,A′′,Σ′′}be the ladder defined by N′′ ={N0(N1(···(Nh(Nh+1}, A′′ ={aN1,...,aNh−1, aNh}, Σ′′ ={σ1,...,σh, σh+1}. The top rung of L′′ strictly contains that of L. Hence, L is not maximal, which proves the Lemma. Let Gbe a game with set of players Nand let N′⊆N. We say that G∈TRN′(GN)if the top rung of any maximal ladder of Gis N′. Hence, a game Gis decomposable as a complete minimax-bettering ladder if and only if G∈TRN(GN). Let G∈TRNmax (GN)and ˆa∈ANmax . Let Λ(ˆa) := {λ= (ˆa, σ)∈A:σNash equilibrium of G(ˆa)}and Λ := Sˆa∈ANmax Λ(ˆa). Let ϕ(Λ) := {ϕ(λ) : λ∈Λ}. Let ¯ FNmax be the set of Nmax -attainable payoffs of G:¯ FNmax := ¯ F∩co ϕ(Λ). Note that, by the definition of Nmax, for each u∈¯ FNmax and each i∈N\Nmax,ui=vi. Moreover, when Nmax =Nwe have Λ = Aand ¯ FNmax =¯ F. Lemma 2.2. Let G∈TRNmax (GN). Then, the set ¯ FNmax is closed. Proof. First, we show that Λis closed. Let {(an, σn)}be a sequence of action profiles in Λwith limit (a, σ). Since ANmax is compact, a∈ANmax . Since ϕis continuous, σis a Nash equilibrium of G(a). Hence, (a, σ)∈Λ. The set ϕ(Λ) is the image of a closed set under a continuous function. Since ϕhas a compact domain, ϕ(Λ) is closed. Hence, ¯ F∩co ϕ(Λ) is closed. The promised result concerning the approximability of all payoffs in ¯ Fby Nash equilibrium payoffs is obtained below as an immediate corollary of a more general theorem concerning the approximability of all payoffs in ¯ FNmax . In this more general case, the collaboration of the players in Nmax is secured by a strategy analogous to that sketched in the Example of Section 2.2.4, while the collaboration of the players in N\Nmax is also ensured because none of them is able to obtain any advantage by unilateral deviation from any action profile in Λ. 2.3 The Theorem In the theorem that follows, the set of action profiles Amay consist either of pure or mixed action profiles; in the latter case, we assume that all players are cognizant not only of the pure actions actually put into effect at each stage, but also of the mixed actions of which they are realizations. 2.3. The Theorem 27 We discuss unobservable mixed actions in Section 2.4. Also, we assume public randomization: at each stage of the repeated game, players can let their actions depend on the realization of an exogenous continuous random variable. The assumption of public randomization is without loss of generality. Given a correlated mixed action, its payoff can be approximated by alternating pure actions with the appropriate frequencies. More precisely, for each u∈¯ Fand each ε > 0, there are pure actions a1,...,alsuch that ||u−(a1+...+al)/l|| < ε. Hence, if the discount parameter δis close enough to 1, the same inequality is still true if we consider discounted payoffs. Then, since we state Theorem 2.1 in terms of approximated payoffs, public randomization assumption can be dispensed with.3 Theorem 2.1. Let G∈TRNmax (GN). Let u∈F. Then, a necessary and sufficient condition for there to be for each ε > 0, an integer T0and a positive real number δ0<1such that for each T≥T0and each δ∈[δ0,1],G(δ, T)has a Nash equilibrium payoff wsuch that kw−uk< ε is that ube Nmax -attainable ( i.e.,u∈¯ FNmax ). Proof. suffic ⇐=Let a∈Λbe an action profile of Gsuch that ϕ(a) = u, and let L={N,A,Σ}be a maximal minimax-bettering ladder of G. By the definition of Λ, players in N\Nmax have no incentive for unilateral deviation from a. Let ρbe the following action profile sequence: ρ:= {a, . . . , a |{z } T−T0+q0 , λh,...,λh |{z } qh , λh−1,...,λh−1 | {z } qh−1 , . . . , λ1,...,λ1 | {z } q1 }, where for each l∈ {1,...h},λl= (aNl−1, σl)with aNl−1∈ A and σl∈Σ. Let ε > 0. Next, we obtain (in this order) values for qh,...,q1, the discount δ0,q0, and T0to ensure that for each T≥T0and each δ∈(δ0,1], there is a Nash equilibrium of G(δ, T)whose path is ρand such that ||ϕ(ρ)−u|| < ε. First, we calculate how many repetitions of G(aNli−1)are necessary for the players in N\{i} to be able to punish a player i∈Nmax for prior deviation. For each action profile ˆa∈A, let ¯µi(ˆa) := µi(ˆa−i)−ϕi(ˆa),i.e., the maximum “illicit” profit that player ican obtain by unilateral deviation from ˆa. Let ¯µi= max{¯µi(a),¯µi((aNh−1, σh)),...,¯µi(σ1)}and mi= min{ϕi(a) : a∈ A}. Let li∈Nbe such that i∈Nli\Nli−1. Let δ0∈(0,1) and let qh,...,q1be the natural numbers defined through the following iterative procedure: Step 0: For each i∈Nh\Nh−1, let ri∈Nand δi∈(0,1) be ri:= min{r∈N:r(ϕi(σli)−vi)>¯µi},4 δi:= min{δi∈(0,1) : ¯µi−Pri t=1 δt i(ϕi(σli)−vi)<0}. Let qh∈Nbe 3For further discussion on public randomization refer to Fudenberg and Maskin (1991) and Olszewski (1997). Also, refer to Gossner (1995) for a paper in which public randomization is not assumed and the approximation procedure we described above is explicitly made (though discounts are not considered). 4The natural number riis such that, at each step, punishing player iduring ristages suffices to wipe out any stage gain he could get by deviating from ρwhen the discount is δ= 1. 28 Chapter 2. Finitely Repeated Games: A Generalized Nash Folk Theorem qh:= max{ri:i∈Nh\Nh−1}. Step k(k < h): Let Tk:= Pk−1 l=0 qh−l. For each i∈Nh−k\Nh−k−1, let ri∈Nand δi∈(0,1) be ri:= min{r∈N:r(ϕi(σli)−vi)>¯µi+Tk(vi−mi)}, δi:= min{δi∈(0,1) : ¯µi+PTk t=1 δt i(vi−mi)−PTk+ri t=Tk+1 δt i(ϕi(σli)−vi)<0}. Let qh−k∈Nbe qh−k:= max{ri:i∈Nh−k\Nh−k−1}. Step h: δ0:= maxi∈Nδi. The natural numbers qh,...,q1and the discount δ0are such that for each l∈ {1,...,h},ql repetitions of G(aNl−1)suffice to allow any player in Nl\Nl−1to be punished. Next, we obtain the values for q0and T0. Let q0be the smallest integer such that:     q0ϕ(a) + qhϕ(λh) + ···+q1ϕ(λ1) q0+qh+···+q1−ϕ(a)   < ε. (2.1) Let T0:= q0+q1+···+qh. Let T≥T0and δ∈[δ0,1]. We prescribe for G(δ, T)the strategy profile in which all players play according to ρunless and until there is a unilateral deviation. In such a deviation occurs, the deviating player is minimaxed by all the others in the remaining stages of the game. It is straightforward to check that this profile is a Nash equilibrium of G(δ, T ). Moreover, by inequality (2.1), its associated payoff vector wdiffers from uby less than T0 Tεif δ= 1. Hence, the same observation is certainly true if δ < 1, in which case payoff vectors of the early stages, ϕ(a), receive greater weight than the payoff vectors of the endgame. necess =⇒Let u /∈¯ FNmax . Suppose that Nmax =N. Then, ¯ FNmax =¯ F. Hence, uis not individually rational. Hence, it can not be the payoff associated to any Nash equilibrium. Then, we can assume Nmax (N. Since ¯ FNmax is a closed set, there is ε > 0such that kw−uk< ε implies w /∈¯ FNmax . Hence, if for some Tand δthere is a strategy profile σof G(δ, T)such that kϕ(σ)−uk< ε, then ϕ(σ)/∈¯ FNmax . Hence, by the definition of ¯ FNmax , there is at least one stage of G(δ, T)in which, with positive probability, σprescribes an action profile not belonging to Λ. Let qbe the last such stage and ¯a= (¯aNmax ,¯aN\Nmax )the corresponding action profile. By the definition of ¯ FNmax ,¯aN\Nmax cannot be a Nash equilibrium of G(¯aNmax ). Hence, there is a player j∈N\Nmax who can increase his payoff in round qby deviating unilaterally from ¯a. Since, by the definition of q,σassigns ja stage payoff of vjin all subsequent rounds, this deviation cannot subsequently be punished. Hence, σis not an equilibrium of G(δ, T). Corollary 2.1. Let G∈ GNbe decomposable as a complete minimax-bettering ladder, (i.e., G∈TRN(GN)). Then, for each u∈¯ Fand each ε > 0, there is T0∈Nand δ0<1such that for each T≥T0and each δ∈[δ0,1], there is a Nash equilibrium payoff wof G(δ, T)with kw−uk< ε. 2.4. Unobservable Mixed Actions 29 Proof. N=Nmax ⇒¯ F=¯ FNmax . Hence, this result is a consequence of Theorem 2.1. Corollary 2.2. Let G∈ GNbe not decomposable as a complete minimax-bettering ladder ( i.e., G /∈TRN(GN)). Then, for each T∈N, each δ∈(0,1], each i∈N\Nmax , and each Nash equilibrium σof G(δ, T)we have ϕi(σ) = vi. Proof. For each u∈¯ FNmax and for each i∈N\Nmax,ui=vi. Hence, this result follows by an argument paralleling the proof of necessity in Theorem 2.1. 2.4 Unobservable Mixed Actions In what follows, we drop the assumption that mixed actions are observable. Hence, if a mixed action is chosen by one player, the others can only observe its realization. To avoid confusion, for each game G, let Gube the corresponding game with unobservable mixed actions. We need to introduce one additional piece of notation to distinguish between pure and mixed actions. Let Aiand Sibe the sets of player i’s pure and mixed actions respectively (with generic elements ai and si). Similarly, let Aand Sbe the sets of pure and mixed action profiles. Hence, a game is now a triplet (N, S, ϕ). The game G(or Gu) in Figure 2.3 illustrates some of the differences between the two frameworks. Although it is not entirely straightforward, it is not difficult to check that the minimax payoff of Gis v= (0,0,0). Let s3= (0,0.5,0.5) be the mixed action of player 3 in which he plays L with probability 0, and M and R with probability 0.5. Let σ2∈A{1,2}. Let N={∅,{3}, N}, S={s3}and Σ = {(T, l, L), σ2}. Then, L={N,S,Σ}is a complete minimax-bettering ladder of Gregardless of σ2(note that in the game G(s3), for each σ2∈A{1,2}, both players 1 and 2 receive the constant payoff 0.5). Hence, Gsatisfies the assumptions of Corollary 2.1, so every payoff in ¯ Fcan be approximated in Nash equilibrium. l r l r l r T 0, 0, 2 0, 0, 0 T 0, 0,-1 2,-1,-1 T 1, 1,-8 -1, 2,-8 B 0, 0, 0 0, 0, 0 B -1, 2,-1 1, 1,-1 B 2,-1,-8 0, 0,-8 L M R Figure 2.3: A game where unobservable mixed actions make a difference Consider now the game Gu. Let u∈¯ F, and let abe such that ϕ(a) = u(recall that we assumed public randomization). If we follow the path ρconstructed in the proof of Theorem 2.1, there are natural numbers q0,q1, and q2such that ρleads to play (i) aduring the first q0stages, (ii) (σ2, s3)during the following q2stages, and (iii) (T,l,L) during the last q1stages. Let Qbe the phase described in (ii). Since player 3 is not indifferent between the two actions in the support of s3, we need a device to detect possible deviations from that support. But, once such a device has been chosen, it is not clear whether we can ensure that there are not realizations for the first 36 Chapter 3. Unilateral Commitments in Repeated Games Fbe the set of feasible payoffs, F:= co{ϕ(a) : a∈A}. Now, for each i∈N, let p−i∈ argmina−i∈A−i{µi(a−i)}. To avoid confusion with the strategies of the repeated game, in what follows we refer to the strategies ai∈Aiand the strategy profiles a∈Aof the stage game as actions and action profiles, respectively. Next, given a game G= (N, A, ϕ), we define the repeated game G(δ, T); the T-fold repetition of Gwith discount parameter δ∈(0,1]. A history at stage t∈ {1,...,T}is defined as follows: (i) for t= 1, an element of A0={∗}, where ∗is any element not belonging to Sk∈NAk. (ii) for t∈ {2,...,T}, an element of At−1. The set of all histories is H:= ST t=1 At−1. In the repeated game we assume perfect monitoring, i.e., each player can choose his action in the current stage in the light of all actions taken by all players in all previous stages. Hence, let G(δ, T)be the triplet (N, S, ϕδ), where: The set of players Nremains the same. S:= Qi∈NSiis the set of strategy profiles, where Si:= AH i,i.e., the set of mappings from Hto Ai. Let σ= (σ1,...,σn)∈Sand h∈H; then, we denote the action profile (σ1(h),...,σn(h)) by σ(h). A strategy profile σ∈Srecursively determines the sequence of action profiles π(σ)∈ATas follows: π1(σ) := σ(∗)and, for each t∈ {2,...,T},πt(σ) = σ(π1(σ),...,πt−1(σ)). We refer to π(σ)as the path determined by σ. The payoff function ϕδis defined as follows. Let σ∈S. Then, player i’s payoff in G(δ, T) is his average discounted stage payoff: ϕδ i(σ) := 1−δ 1−δT T X t=1 δt−1ϕi(πt(σ)).1 Finally, recall that, from our definitions, we only use pure actions. If mixed actions are to be taken into account for a given game, then we just define a new game having them as pure actions. Hence, we are implicitly assuming that, when working with mixed actions, they are observable, i.e., the players do not only observe the realization of a mixed action, but also the randomization process that leads to such a realization. 3.2.1 Virtually Subgame Perfect Equilibria A repeated game with perfect monitoring can be represented as an extensive game and, more specifically, as a multi-stage game with observed actions.2Subgame perfect equilibrium (Selten, 1965), shortly SPE, is probably the most important equilibrium concept within this class of games. 1If there are no discounts (i.e., if δ= 1), we have ϕδ i(σ) := (1/T ) P T t=1 ϕi(πt(σ)). 2We model extensive games following the framework used in Kreps and Wilson (1982), except for the fact that we consider that the sets of nodes may be infinite. 3.2. Notation 37 Its main target is to disregard those Nash equilibria which are only possible if some players give credit to irrational plans of others. More formally, a SPE is a Nash equilibrium which, moreover, induces a Nash equilibrium in every subgame. In this Section we introduce a new equilibrium concept for extensive games which is essential for this Chapter: the virtually subgame perfect equilibrium, shortly VSPE. This equilibrium concept has the same effect as subgame perfection, but it only concentrates on those subgames which are relevant for a given strategy profile; relevant in the sense that they are reachable if exactly one player deviates from the strategy profile in any subgame which has already been classified as relevant. Despite of being based on the same idea, SPE and VSPE are different concepts, the latter existing in many games which do not have SPE. Hence, VSPE is especially useful when dealing with extensive games having large trees. There are many extensive games without SPE, but still, they can have sensible equilibria. This is the case when the non-existence of SPE is because some subgames which are irrelevant for a certain strategy profile do not have Nash equilibria. Let Γbe an extensive game and let xand σbe a single-node information set and a strategy profile, respectively. Then, Γxdenotes the subgame of Γthat begins at node xand σxthe restriction of σto Γx. Now, let Γbe an extensive game, σa strategy profile of Γ, and xa singlenode information set. Then, the subgame Γxis σ-relevant if either (i) Γx= Γ, or (ii) there are a player i, a strategy σ′ i, and a single-node information set ysuch that Γyis σ-relevant and node x is reached by (σ−i, σ′ i)y. Definition 3.1. Let Γbe an extensive game. The strategy profile σis a virtually subgame perfect equilibrium of Γif for each σ-relevant subgame Γx, then σxis a Nash equilibrium of Γx. Let SPE(Γ) and VSPE(Γ) denote the sets of SPE and VSPE of game Γ, respectively. By definition, for each extensive game Γ, we have SPE(Γ) ⊆VSPE(Γ). However, the reciprocal is not true as the following example illustrates. Example 3.1. Consider the extensive game depicted in Figure 3.1. Let σ=(D1, ai 1),(D2, ai 2), with i∈ {1,2}. Clearly, since the subgame that begins after playing (U1, U2)is σ-irrelevant, σis a VSPE. However, this game does not have any SPE (in pure strategies). Moreover, the equilibrium σis a sensible one. Next, we point out one more relation between SPE and VSPE. Let Γbe an extensive game. Let σand ˆσbe two strategy profiles of Γ. Now, let ¯σbe the strategy profile which consists of playing in accordance with σin the σ-relevant subgames and in accordance with ˆσelsewhere. Then, the following statements hold: (i) The payoffs associated with σand ¯σcoincide (they define the same path). (ii) If σ∈VSPE(Γ), then ¯σ∈VSPE(Γ). (iii) If σ∈VSPE(Γ) and ˆσ∈SPE(Γ), then ¯σ∈SPE(Γ). 38 Chapter 3. Unilateral Commitments in Repeated Games 1 2 1 2 (1,1) (1,0) (0,1) (1,-1) (-1,1) (-1,1) (1,-1) U1 D1 U2 D2 U2 D2 a1 1 a2 1 a1 2 a2 2 a1 2 a2 2 Figure 3.1: A game without SPE, but with VSPE. Remark. In this Chapter we study a special family of multistage games with observed actions. The main reason why we need the concept of VSPE is that we work with pure strategies. Hence, although we mainly deal with finite extensive games with perfect recall, we cannot apply the general results for the existence of subgame perfect equilibria. 3.2.2 Unilateral Commitments The main objective of this Chapter is to study the effect of unilateral commitments on the appearing of constructive behavior in repeated games. Given a game G, the corresponding game with unilateral commitments consists of adding an initial stage to G; in this new stage each player can commit not to play certain strategies of game G. Moreover, these commitments are made simultaneously and unilaterally. The fact that the commitments have to be unilateral is quite important; if players could condition their commitments on the commitments of the others, then we would be in a completely cooperative model, and hence, the players could easily achieve in equilibrium the cooperative payoffs of the game. The problem of unilateral commitments, henceforth UC, has already been tackled in García- Jurado et al. (2000). They obtained a Nash folk theorem for finitely repeated games with UC. In this Chapter we deepen a little bit more in the impact of UC in the assumptions needed for the folk theorems. Next, following García-Jurado et al. (2000), we formally define the UC-extension of a game. Given a game G= (N, A, ϕ), we define the UC-extension of G,U(G), as follows. There is a preliminary stage in which players choose, simultaneously and independently, a nonempty subset of their sets of strategies. Formally, each player i∈Nchooses Ac i⊆Ai, where Ac ihas to be a compact set. This election is interpreted as a commitment to play strategies only in Ac i. Then, this preliminary stage ends and the commitments of the players, Ac, are made public, i.e., they become common knowledge. Finally, a reduced version of game Gin which players have to respect their commitments is played. Note that, as we have already pointed out, this kind of 3.3. The Folk Theorems 39 commitments are unilateral because we do not allow them to be conditional on the other players’ commitments. The compactness assumption for the sets Ac iresponds, as usually, to technical reasons; it ensures that the subgames starting after the stage of commitments belong to the class of games defined at the beginning of this Section. Note that, in the particular case in which the sets of strategies of the game under consideration are finite, the compactness requirement imposes no restriction at all. Throughout the rest of this Section, with a slight abuse of notation, given a set A, we use 2Ato denote the set of compact subsets of A. Now, U(G) := (N, AU, ϕU), where: The set of players Nremains the same. AU:= Qi∈NAU i, where AU iis the set of all couples (Ac i, αi)such that (i) ∅(Ac i⊆Ai, (ii) αi:Qj∈N2Aj−→ Aiand, for each Ac∈Qj∈N2Aj,αi(Ac)∈Ac i. The payoff associated with a strategy profile (Ac, α)is ϕU(Ac, α) := ϕ(α(Ac)). 3.3 The Folk Theorems The appearing of constructive behavior in repeated games has been widely treated in the game theoretical literature.3Given a game G, the classic Nash folk theorem for finitely repeated games (Benoît and Krishna, 1987) states that if the game Gis such that, for each player i, there are two Nash equilibria that give idifferent payoffs, then every feasible and individually rational payoff of Gcan be approximated by a Nash equilibrium of G(δ, T )for big enough Tand δclose enough to 1. Recently, González-Díaz (2003) introduced a new condition, namely that the game Gis decomposable as a complete minimax-bettering ladder; this new condition, besides being weaker than the former, turned out to be both necessary and sufficient for the finite horizon Nash folk theorem. Next, we state and prove a Nash folk theorem for finitely repeated games with unilateral commitments. This result, Theorem 3.1, is a variation of the main result in García-Jurado et al. (2000) to place it within our framework. More precisely, here we deal with utilities instead of with preferences, we allow for discounts, and we consider the set Finstead of the set {ϕ(a) : a∈A}. We assume public randomization: at each stage of the repeated game, the players can let their actions depend on the realization of an exogenous continuous random variable. The assumption of public randomization is without loss of generality. Given a correlated action, its payoff can be approximated by alternating actions with the appropriate frequencies. More precisely, for each u∈Fand each ε > 0, there are actions a1,...,alsuch that ||u−(a1+. . . +al)/l|| < ε. Hence, if the discount parameter δis close enough to 1, the same inequality is still true if we consider discounted payoffs. Then, since we state Theorem 3.1 in terms of approximated payoffs, public randomization assumption can be dispensed with.4 3Refer to Benoît and Krishna (1996) for a complete survey on the topic. 4For further discussion on public randomization refer to Fudenberg and Maskin (1991) and Olszewski (1997). 40 Chapter 3. Unilateral Commitments in Repeated Games Theorem 3.1. Let G= (N, A, ϕ)and let vbe its minimax payoff vector. Let u∈F,u > v. Then, for each ε > 0, there are δ0∈(0,1) and T0∈Nsuch that for each δ∈[δ0,1] and each T≥T0, the game U(G(δ, T)) has a Nash equilibrium payoff wsuch that kw−uk< ε. Proof. Let G= (N, A, ϕ). Let u∈Fand let ¯a∈Abe a (possibly correlated) action profile such that ϕ(¯a) = u. Now, for each δ∈(0,1] and each T∈N, let G(δ, T ) = (N, S, ϕδ). We define the following strategy profile (¯ Sc,¯α)of U(G(δ, T)): (i) For each i∈N,¯ Sc i:= “If ¯ais played in the first stage, then I play ¯aiforever”. (ii) For each i∈Nand each Sc∈Qj∈N2Sj, we define ¯αi(Sc)as follows: If Sc=¯ Sc: –iplays ¯aiin the first stage. –If ¯ais played in the first stage, then iplays ¯aiforever. –If in the first stage only player j6=ihas deviated from ¯a, then, iplays (p−j)i forever. –Otherwise, iplays ad libitum. If Sc= (Sc j,¯ Sc −j), where j6=iand Sc j6=¯ Sc j:iplays (p−j)iforever. Otherwise: iplays ad libitum. Note that ϕc(¯ Sc,¯α) = ϕδ(¯α(¯ Sc)) = ϕ(¯a) = u. For each i∈N, let Tibe such that Tiui> µi(¯a−i)+ (T−1)viand let δi∈(0,1) be such that PTi t=1 δt−1ui> µi(¯a−i)+ PTi t=2 δt−1vi. Finally, let T0:= maxi∈NTiand δ0:= maxi∈Nδi. Now, it is straightforward to check that for each δ∈[δ0,1] and each T≥T0, the strategy profile (¯ Sc,¯α)is a Nash equilibrium of U(G(δ, T)) whose payoff wis such that kw−uk= 0 < ε (Note that we have obtained an exact result, i.e.,w=ubecause of the public randomization assumption).5 The main purpose for the rest of this Section is to state and prove a subgame perfect folk theorem with UC. The trick of the proof of Theorem 3.1, in which the strategies corresponding with many subgames were defined ad libitum, does not work for subgame perfection. Moreover, when dealing with unilateral commitments, we face extremely large game trees. They have many subgames, some of which may correspond to senseless commitments. Thus, we need to use the VSPE concept instead of the classical SPE. Theorem 3.1 says that, when unilateral commitments are possible, no condition is needed for the Nash folk theorem to hold. Note that the Nash equilibrium profile (¯ Sc,¯α)defined in the proof of Theorem 3.1 is neither a SPE nor a VSPE; this is because, in general, the punishments to a player who deviates from the commitment are not credible. Now, Proposition 3.1 shows that not only the proof of Theorem 3.1 fails when we write VSPE instead of Nash equilibrium, but also the result itself is false. 5The reader willing to deepen into the arguments of this proof is referred to García-Jurado et al. (2000). 3.3. The Folk Theorems 41 Proposition 3.1. The counterpart of Theorem 3.1 for VSPE does not hold. Proof. We do the proof by means of an example. Let G= (N, A, ϕ)be the game defined in Figure 3.2. The game Gdoes not have a Nash equilibrium. Moreover, v= (1,1) and ϕ(U, L) = L R U 10,11 1,10 D 11,0 0,1 Figure 3.2: A counterexample for Proposition 3.1 (10,11) > v. However, for each T∈Nand each δ∈(0,1],U(G(δ, T)) does not have a VSPE. Suppose, on the contrary, that there are δ∈(0,1] and T∈Nsuch that (Sc, α)is a VSPE of U(G(δ, T)). If Sccontains a unique element, then one of the players can change his commitment to no commitment at all (i.e.,Sc i=Siif iis such a player) and deviate from the strategy in the final stage. Hence, there is a last stage in which, according to the path defined by (Sc, α), one of the players is free to play any action. Let tbe that stage and assume, without loss of generality, that, following the path of (Sc, α), player 1 can play both Uand Dat stage t. Moreover, let x∗ be the corresponding single-node of G(δ, T). Now, let player 2 deviate to the strategy (¯ Sc 2,¯α2)defined as follows: (i) ¯ Sc 2:= “from stage t+ 1 on, I play according to the path defined by (Sc, α)” and (ii) for each ˆ Sc 1∈2S1,¯α2(ˆ Sc 1,¯ Sc 2) := α2(Sc). Let ybe the single-node reached after (Sc 1,¯ Sc 2)is played. By definition, U(G(δ, T ))y is a relevant subgame. Let now player 1 deviate, in U(G(δ, T))y, to the strategy ¯α1defined as follows: for each ˆ Sc 2∈2S2,¯α1(Sc 1,ˆ Sc 2) := α1(Sc). The subgame U(G(δ, T))yis such that, when playing according to (α1, α2), the single-node x∗of G(δ, T)is reached again at stage t. Hence, the subgame beginning at the corresponding single-node of U(G(δ, T)), namely x, is relevant for (Sc, α). According to the commitments, both players can choose their two actions at xand, from the stage t+ 1 on, player 2’s actions are determined by the commitment. Now, it is immediate to check that the relevant subgame U(G(δ, T))xdoes not have any Nash equilibrium. Hence, (Sc, α) cannot be a VSPE. In the counterexample we used in the proof above, we defined a game Gwith no Nash equilibrium. Moreover, for each T∈Nand each δ∈(0,1], the game G(δ, T )did not have any Nash equilibrium. On the other hand, we have the following positive result concerning the existence of VSPE for games with UC. Proposition 3.2. Let G= (N, A, ϕ)and let ¯a∈Abe a Nash equilibrium of G. Then, the game U(G)has a VSPE (¯ Ac,¯α)with payoff ϕ(¯a). Proof. Let (¯ Ac,¯α)be such that for each i∈N, we have (i) ¯ Ac i={¯ai}, (ii) for each j6=iand each Ac j∈2Aj,¯αi(¯ Ac −j, Ac j) = ¯ai. Finally, for each Ac i∈2Ai, ¯αi(¯ Ac −i, Ac i) = ˆai, where ˆai∈argmaxai∈¯ Ac i{ϕi(¯a−i, ai)}. 42 Chapter 3. Unilateral Commitments in Repeated Games It is immediate to check that each such strategy profile (¯ Ac,¯α)is a VSPE of U(G). In view of Proposition 3.2, it is clear that every Nash folk theorem for finitely repeated games can be easily adapted to provide a subgame perfect folk theorem for finitely repeated games with unilateral commitments. More precisely, the necessary and sufficient condition for the Nash folk theorem in González-Díaz (2003), “that the game is decomposable as a complete minimax-bettering ladder”, is a sufficient condition for the VSPE folk theorem with UC. The former condition implies among other things, the existence of a Nash equilibrium in the stage game G; this implication is all we use in this Chapter. Example 3.2 shows that such condition is not necessary. Example 3.2. Let G= (N, A, ϕ)be the game defined in Figure 3.3. L M R U 10,10 0,1 1,0 D 11,0 1,1 0,2 Figure 3.3: A game without Nash equilibria The game Gdoes not have a Nash equilibrium. Hence, Git is not decomposable as a complete minimax-bettering ladder. Moreover, v= (1,2). Now, for each T∈Nand each δ∈(0,1], the payoff (10,10) can be supported by a VSPE of U(G(δ, T)) = (N, SU, ϕU). To check this assertion, consider the strategy profile (¯ Sc,¯α)of U(G(δ, T)) defined as follows: (i) ¯ Sc 1:= “I play Uin every stage”, (ii) ¯ Sc 2:= “I never play R”, and (iii) for each i∈ {1,2}and each Sc i∈2Si,¯α(¯ Sc −i, Sc i) consists of playing, at each stage, the unique Nash equilibrium of the corresponding one stage game. Then, (¯ Sc,¯α)is a VSPE and ϕU(¯ Sc,¯α) = (10,10). Proposition 3.2 says that we can use the UC to make actions credible, even actions that in the original game could be dominated. On the other hand, Example 3.2 shows that we can use the UC to go further than that. Hence, some more research is needed to find new sufficient conditions for the VSPE folk theorem; conditions weaker than the existence of a complete minimax-bettering ladder. Although we have made some research in this specific issue, we have not found any satisfactory condition. Nevertheless, we have found the following result, which, with the aid of Proposition 3.2, is straightforward. Theorem 3.2. Let G= (N, A, ϕ)and let vbe its minimax payoff vector. Let u∈F,u > v. Then, for each ε > 0, there are δ0∈(0,1) and T0∈Nsuch that for each δ∈[δ0,1] and each T≥T0, the game U(U(G(δ, T))) has a VSPE with payoff wsuch that kw−uk< ε. Proof. Immediate from the combination of Theorem 3.1 and Proposition 3.2. Theorem 3.2 implies that, when two stages of commitments are possible, any feasible and individually rational payoff of the original game can be achieved as a VSPE of the repeated game with unilateral commitments. No assumption is needed for the original game, not even the existence of a Nash equilibrium. 3.3. The Folk Theorems 43 Next, we briefly discuss the impact of Theorem 3.2 within the delegation framework discussed in the Introduction. First, from the point of view of our model with unilateral commitments, the game U(U(G(δ, T))) can be difficult to motivate. It is true that we get a very strong result for the set of equilibrium payoffs of this game, but the fact that we allow for commitments on commitments might have unnatural features in some models. The point is that, when we introduced unilateral commitments, we emphasized the fact that they were unilateral, i.e., the commitments of one player could not be conditional on the other players’ commitments; if we allow for two stages of commitments, then we are indirectly allowing for commitments on commitments, and hence, we achieve the same payoffs we could get with a cooperative model. On the other hand, if we reassess the delegation situation corresponding with our unilateral commitments model, and we do it in a similar way to that in the Introduction, then we have the following interpretation for the two stages of commitments. Consider a situation in which two firms are engaged in a competitive situation. Initially, the players are the presidents, and hence, in the first stage each president signs a contract with his principal in which the latter is committed not to play certain strategies and he will be paid proportionally to the payoff he finally gets. Then, in a second stage, a similar contract is signed between each principal and his agent. Finally, the agents play the original game but honoring the commitments. This situation has some important differences with the one stage situation: (i) the commitments that the president includes in the contract in the first stage can take into account the commitments that the principal will make with the agent at stage two, i.e., the contract between each president and his principal also commits the latter on the commitments he can sign with his agent, (ii) in the second stage the principals, being consistent with the commitments of their contract with the principals and in view of the commitments made by the rivals, choose a new commitment for the agents, i.e., a commitment on the commitment, and (iii) finally, the agents have to play being consistent with all the previous commitments. The hierarchical delegation model we have just described is quite natural and it is not difficult to think of real life situations with these sub-delegation structures. Hence, if such situations also correspond to some repeated game, then Theorem 3.2 says that, regardless of the properties of the underlying stage game, the “cooperative” (collusive) payoffs can be supported as a VSPE in the game with two stages of commitments. 3.3.1 Infinitely Repeated Games Although we have not formally introduced the model with infinitely repeated games, the definitions can be immediately extended to encompass also this family of games; basically, replacing T by ∞in the definition of history and in the subsequent ones. Now, within this new framework, Proposition 3.2 still carries over. Now, recall that the classic Nash folk theorem for infinitely repeated games (see, for instance, Fudenberg and Maskin (1986)) states that, if the discount is close enough to 1, every feasible and individually rational payoff can be achieved as a Nash equilibrium of the infinitely repeated game. Hence, if we combine this classic result with Proposition 3.2 we get the following Corollary: 44 Chapter 3. Unilateral Commitments in Repeated Games Corollary 3.1. Let G= (N, A, ϕ)and let vbe its minimax payoff vector. Let u∈F,u > v. Then, there is δ0∈(0,1) such that for each δ∈[δ0,1] the game U(G(δ, ∞)) has a VSPE with payoff u. Proof. It is immediate from the combination of Proposition 3.2 with the classic Nash folk theorem for infinitely repeated games. 3.3.2 The State of Art Table 3.1 summarizes the results we have proved in this Chapter along with the classic folk theorems for repeated games with complete information. In particular, it shows the strength of Proposition 3.2, that allows to obtain many folk theorems for repeated games with unilateral commitments as immediate corollaries of the classic ones. Hence, by looking at Table 3.1, one easily understands the strength of unilateral commitments within this framework. Note that all the cells in the Table contain necessary and sufficient conditions, all of them but the one corresponding with the virtual subgame perfect folk theorem for finitely repeated games with unilateral commitments; some more research is still needed concerning this case. Without UC 1 stage of UC 2 stages of UC Nash Theorem None None None Infinite Horizon (Fudenberg and Maskin, 1986) (Prop. 3.2) (Prop. 3.2) (Virtual) Perfect Th. Non-Equivalent Utilities None None Infinite Horizon (Abreu et al., 1994) (Prop. 3.2) (Prop. 3.2) Nash Theorem Minimax-Bettering Ladder None None Finite Horizon (González-Díaz, 2003) (García-Jurado et al., 2000) (Prop. 3.2) (Virtual) Perfect Th. Recursively-distinct Minimax-Bettering Ladder None Finite Horizon Nash payoffs (Smith, 1995) (Prop. 3.2, only sufficient) (Th. 3.2) Table 3.1: Necessary and Sufficient conditions for the folk theorems 3.4 Concluding Remarks In this Chapter we have deepened in the literature of commitments. More specifically, we have studied the impact of unilateral commitments in the folk theorems for repeated games. We want to emphasize again the following fact. Because of the way we have modeled unilateral commitments, it could seem that they are very far from the more standard models of commitment via delegation. But, as we pointed out in the Introduction and in the discussion of Theorem 3.2, unilateral commitments can be used to model situations in which there is a principal who signs a contract with his agent with two natural features: (i) The agent has committed not play certain strategies and (ii) among the remaining ones his payoff is proportional to that of the principal, i.e., the agent can be thought of as a shareholder of the firm. 3.4. Concluding Remarks 45 Moreover, we have shown that unilateral commitments have very strong implications within the literature of repeated games with complete information. They lead to new folk theorems in which the assumptions needed for the classic results have been notably relaxed. Finally, there are several open questions that should be tackled in the future. One of them is to refine the conditions for the finite horizon perfect folk theorem with unilateral commitments. There is another important issue where some research is needed: the impact of unilateral commitments in repeated games with incomplete information. 52 Chapter 4. A Noncooperative Approach to Bankruptcy Problems Suppose that the profile α∗is a Nash equilibrium and that, for some fixed i, j ∈N, we have α∗ j> α∗ iand mi> α∗ i. If πj(α∗) = 0,then player jcan ensure for himself a positive payoff with the strategy ε, for εsmall enough. Hence, πj(α∗)must be positive. Now, player ican obtain a greater payoff by switching to strategy α′ i∈(α∗ i,min{α∗ j, mi}); player ihas still a lower index than player jand, since fiis increasing, his payoff increases. Hence, if α∗is a Nash equilibrium and α∗ j> α∗ ifor some i, j ∈N, we have α∗ i=mi.Combining this with the fact that ρis the unique positive real number for which F(ρ) = E, we get that the strategies α∗ i= min{ρ, mi} define a Nash equilibrium. Note that there can exist j∈N, such that for each i6=j, (i) α∗ i=mi, and (ii) α∗ j> α∗ i; in this case player jcan change his strategy to a new αj> α∗ j, obtaining a new Nash equilibrium of the game. Nonetheless, the payoff remains unchanged. Case 2: Functions fiare decreasing. Take again the function F, now we have (i) F(0) = Pi∈Ndi> E and (ii) F(maxi∈N{mi}) = 0. Define again ρas the unique real number in (0,maxi∈N{mi})such that F(ρ) = E. The situation is similar to the case with increasing functions: the profile α∗with α∗ i= min{ρ, mi}is again a Nash equilibrium. Again, suppose that πi(α∗) = 0 for some i∈N. In this situation, if player ichanges his strategy, no matter how, the new profile is still a Nash equilibrium. Nonetheless, the payoff remains unchanged. Moreover, all the Nash equilibria in the Proposition above are in fact strong equilibria, as the following Proposition shows. Proposition 4.2. Let (N, E, d)be a bankruptcy problem, hN, D, πian associated noncooperative bankruptcy game, and α∗a strategy profile. Then, under Axioms 4.1 and 4.2, α∗is a Nash equilibrium if and only if α∗is a strong equilibrium. Proof. Since a strong equilibrium is a Nash equilibrium only one implication has to be proved. Assume that the functions fiare increasing. Suppose that α∗is a Nash equilibrium which is not strong. Then, there are T⊆Nand αT∈Qj∈TDjsuch that for each j∈T,πj(α∗)< πj(α∗ N\T, αT). By Proposition 4.1, there is ρsuch that for each i∈N,α∗ i= min{ρ, mi}. Moreover, it is easy to check that, for each i∈N,πi(α∗) = fi(α∗ i). Now, for each j∈T, fj(αj)≥πj(α∗ N\T, αT)> πj(α∗) = fj(α∗ j). Hence, αj> α∗ j. Hence, α∗ j< mj. Hence, α∗ j=ρand αj> ρ. Now, since for each i∈N\T, α∗ i≤ρ, then for each j∈Tand each i∈N\T, we have αj> α∗ i. Hence, for each i∈N\T, πi(α∗ N\T, αT) = fi(α∗ i) = πi(α∗). Since Pi∈Nπi(α∗ N\T, αT)≤E, then cannot be the case that, for each j∈T,πj(α∗)< πj(α∗ N\T, αT). In the decreasing case, a similar argument can be formulated. 4.3. Bankrupcty Games and Bankruptcy Rules 53 4.3 Bankrupcty Games and Bankruptcy Rules Now, we illustrate how the results in Section 4.2 apply to the standard bankruptcy rules. The proportional rule,P, which is probably the best known and most widely used solution concept, distributes awards proportionally to claims. It is defined as follows: for each (N, E, d), P(N, E, d) = λd, with λ=E P i∈Ndi.It is easy to see that, if we take, for each i∈N,Di= [0,1] and fi(αi) = αidi, then the (unique) Nash equilibrium of the game produces the proportional solution to the bankruptcy problem. The constrained equal-awards rule, A, applies an egalitarian principle on the awards received, provided no player gets more than he claims. It is defined as follows: for each (N, E, d)and each i∈N,Ai(N, E, d) = min{di, λ}, where λsolves Pi∈Nmin{di, λ}=E. By letting Di= [0, di] and fi(αi) = αi,we get the constrained equal awards solution as the unique Nash equilibrium of the associated bankruptcy game. The constrained equal-loss rule,L, is the dual of the latter. It distributes equally the difference between the amount available and the aggregate claims, with one proviso: no player ends up with a negative transfer. Namely, Li(N, E, d) = max{0, di−λ},where λsolves Pi∈Nmax{0, di−λ}=E. Taking Di= [0, di]and defining fi(αi) = di−αi,we obtain the constrained equal-losses solution as the Nash equilibrium payoff of the game. Aumann and Maschler (1985) introduced the Talmud rule as the consistent extension of the contested garment rule. It is defined as follows: for each (N, E, d)and each i∈N, Ti(N, E, d) = min{1 2di, λ}if E≤1 2Pi∈Ndi,and Ti(N, E, d) = max{1 2di, di−µ}if E≥1 2Pi∈Ndi,where λ and µare chosen such that Pi∈NTi(N, E, d) = E. If we let Di= [0, di]and fi(αi) = (1 2αiE≤1 2Pi∈Ndi 1 2di−αiE≥1 2Pi∈Ndi, the Nash equilibrium payoff of the game yields the allocation corresponding to the Talmud rule. More generally, if we let Di= [0, di]and fi(αi) = (θαiE≤θPi∈Ndi θdi−αiE≥θPi∈Ndi, we generate the solutions corresponding to the TAL-family (Moreno-Ternero and Villar, 2003) which encompasses the constrained equal awards, the constrained equal losses, and the Talmud rule.1 These results illustrate on the applicability of this procedure to provide a noncooperative sup- 1The TAL-family consists of all rules with the following form: there is θ∈[0,1] such that for each bankruptcy problem (N, E, c)and each i∈N, Rθ i(N, E, d) =  min {θdi, λ}E≤θ P i∈Ndi max {θdi, di−µ}E≥θ P i∈Ndi, where and λand µare chosen such that P i∈NRθ i(N, E, d) = E. 54 Chapter 4. A Noncooperative Approach to Bankruptcy Problems port to the best known bankruptcy rules. But these results can actually be extended to virtually any meaningful rule. Consider now the following definition which introduces an extremely mild requirement on bankruptcy rules: Definition 4.1. A bankruptcy rule Ris called acceptable if there are no bankruptcy problem (N, E, d)and players i, j ∈Nsuch that Ri(N, E, d) = 0 and Rj(N, E, d) = dj. Acceptable rules are those which never concede a player his claim in full whereas some other player gets nothing. Most of the rules which have been studied in the literature are acceptable. The following proposition shows that for all acceptable bankruptcy rules there is a bankruptcy game whose equilibrium payoff coincides with the allocation proposed by the selected rule. Formally: Proposition 4.3. Let R be an acceptable bankruptcy rule and (N, E, d)a bankruptcy problem. Then, there is a noncooperative bankruptcy game hN, D, πi, satisfying Axioms 4.1 and 4.2, whose unique equilibrium payoff coincides with R(N, E, d). Proof. The proof consists of showing that we can define sets of strategies Diand functions fiin such a way that the result is a consequence of Proposition 4.1. Let (N, E, d).To simplify notation we write Riinstead of Ri(N, E, d).Since the rule is acceptable, either for each i∈N,Ri>0, or for each i∈N,Ri< di. Next, we define the sets of strategies and the functions fi. Case 1: For each i∈N,Ri>0. Let mi:= R1 Ri diand fi(αi) := Ri R1 αi. It is clear that the functions fiare monotone (in fact, increasing) and that, for each i∈N, fi is a bijection mapping [0, mi]onto [0, di]. By Proposition 4.1, the noncooperative bankruptcy game has a unique equilibrium payoff. Clearly, in this case, ρ=R1. Hence, α∗= (R1,...,R1)is a Nash equilibrium (which is, moreover, strong by Proposition 4.2); its associated payoff is R(N, E, d). Case 2: For each i∈N,Ri< di. The reasoning is the same as before, except in that, now, we define: mi:= d1−R1 di−Ri diand fi(αi) := di−di−Ri d1−R1 αi. Now, since (d1−R1, . . . , d1−R1)is a Nash equilibrium of this game and its associated payoff vector is R(N, E, d), then Proposition 4.1 gives again the desired result. 4.4. Concluding Remarks 55 4.4 Concluding Remarks We have presented in this Chapter a simple and intuitive game form which supports virtually all bankruptcy rules. The allocation proposed by each rule is obtained as the unique payoff vector corresponding to the Nash equilibrium of a specific game. In this respect, choosing the rules of the game (and most particularly the strategy space of the players) determines the bankruptcy rule that will emerge. Interestingly enough, the game form that allows to implement those bankruptcy rules is a oneshot game in which every player sends a message concerning his own awards exclusively. Those messages refer to the cuts in their claims they might be ready to accept, given their claims and the existing shortage. The game form induces an equilibrium in which all players choose “the same” message. Selecting the nature of those messages (e.g. awards, shares, losses) amounts to deciding on the bankruptcy rule whose allocation will result (the equal awards-rule, the proportional rule, the equal-losses rule). The game form proposed here implicitly assumes that all the data of the problem are public knowledge. In particular that the planner may know both the players’ claims and the amount to divide. This is a natural assumption in most of the bankruptcy situations, where claims have to be eventually credited. The case of taxation problems may be an exception in this respect. Dagan et al. (1999) show that those problems are implementable when all players other than the planner know all the data of the problem. Even though this is an arguable assumption in this context, they also show an impossibility result when this is not the case (see also Corchón and Herrero (2004) on this point). 56 Chapter 4. A Noncooperative Approach to Bankruptcy Problems Bibliography Aumann, R. J. (1959): “Acceptable Points in General Cooperative n-Person Games,” in Contributions to the theory of games IV, ed. by A. Tucker and R. Luce, Princeton University Press, 287–324. (Quoted in pp. 51) Aumann, R. J. and M. Maschler (1985): “Game Theoretic Analysis of a Bankruptcy Problem from the Talmud,” Journal of Economic Theory, 36, 195–213. (Quoted in pp. 53) Chun, Y. (1989): “A Noncooperative Justification for the Egalitaria Surplus Sharing,” Mathematical Social Sciences, 17, 245–261. (Quoted in pp. 48) Corchón, L. and C. Herrero (2004): “A Decent Proposal,” Spanish Economic Review, 6, 107–125. (Quoted in pp. 49, 55) Dagan, N., R. Serrano, and O. Volij (1997): “A Noncooperative View of Consistent Bankrupcty Rules,” Games and Economic Behavior, 18, 55–72. (Quoted in pp. 48) ——— (1999): “Feasible Implementation of Taxation Methods,” Review of Economic Design, 4, 52–72. (Quoted in pp. 49, 55) de Frutos, M. A. (1999): “Coalitional Manipulation in a Banfruptcy Problem,” Journal of Economic Theory, 4, 255–272. (Quoted in pp. 49) Herrero, C. (2003): “Equal Awards versus Equal Losses: Duality in Bankruptcy,” in Advances in Economic Design, ed. by M. Sertel and S. Koray, Springer-Verlag. (Quoted in pp. 48) Herrero, C., J. D. Moreno-Ternero, and G. Ponti (2003): “An Experiment of Bankruptcy,” Tech. Rep. Working paper AD 2003-03, Ivie. (Quoted in pp. 49) Ju, B.-G. (2003): “Manipulation via Merging and Splitting in Claims Problems,” Review of Economic Design, 8, 205–215. (Quoted in pp. 49) Moreno-Ternero, J. D. (2004): “Bankruptcy Rules and Coalitional Manipulation,” Tech. rep., Yale University. (Quoted in pp. 49) Moreno-Ternero, J. D. and A. Villar (2003): “The TAL-Family of Rules for Banruptcy Prolems,” Tech. rep., University of Alicante. (Quoted in pp. 53) Moulin, H. (2002): “Axiomatic Cost and Surplus Sharing,” in Handbood of Social Choice and Welfare, ed. by K. Arrow, A. Sen, and K. Suzumura, Elsevier Science B.V., vol. 1. (Quoted in pp. 48) O’Neill, B. (1982): “A Problem of Rights Arbitration from the Talmud,” Mathematical Social Sciences, 2, 345–371. (Quoted in pp. 48) Serrano, R. (1995): “Strategic Bargaining, Surplus Sharing Problems and the Nucleolus,” Journal of Mathematical Economics, 24, 319–329. (Quoted in pp. 48) Sonn, S. (1992): “Sequential Bargaining for Bankruptcy Problems,” Preprint. (Quoted in pp. 48) Thomson, W. (2003): “Axiomatic and Game Theoretic Analysis of Bankruptcy and Taxation Problems,” Mathematical Social Sciences, 45, 249–297. (Quoted in pp. 48) Part II Cooperative Game Theory 59 Introduction to Cooperative Game Theory This second Part is devoted cooperative game theory. We set the focus on the geometry underlying some of the best known solution concepts in the TU games literature. We describe the structure of this Part below. The first three Chapters deal with the geometry of the core of a TU game. More specifically, we define a new solution concept for balanced games, the core-center, which is deeply studied in this Part of the dissertation. These three Chapters are based on the papers González-Díaz and Sánchez-Rodríguez (2003a,b). In Chapter 5 we formally introduce the core-center as the barycenter of the core and we carry out an analysis of the properties satisfied by this new allocation rule. The main focus is on the continuity property, which turns out to be a serious concern. We have also made an important effort studying the monotonicity properties of the core-center; the necessity of this effort comes from the existing negative results concerning the possibility of defining monotonic selections from the core of a TU game (Young, 1985; Housman and Clark, 1998). In Chapter 6 we combine some of the properties studied in Chapter 5 with an additivity property to obtain an axiomatic characterization of the core-center. Next, in Chapter 7, we develop some tools to establish a connection between the core-center and the Shapley value (Shapley, 1953) within the class of convex games. In this Chapter, we describe the formation of the core as the result of a dynamic process among coalitions. Based on this interpretation, we define the utopia games, a family of games associated with each TU game which naturally arise from the mentioned description. The utopia games are the corner stone for the connection between the core-center and the Shapley value. Finally, in Chapter 8 we switch to the geometry underlying the τvalue (Tijs, 1981). In this Chapter, which is based on the paper González-Díaz et al. (2005), we characterize the τvalue as the barycenter of the edges of the core-cover of a quasi-balanced game (multiplicities have to be taken into account). Summarizing, in this second Part we deepen in the geometry of the TU games. We do it by establishing some connections between set valued solutions and allocation rules. It is a well known property of the Shapley value the fact that it is the center of gravity of the vectors of marginal contributions. On the other hand, the nucleolus is many times referred to as the lexicographic center of the core. These two “central” properties of the Shapley value and the nucleolus have been used many times to motivate the use of these two allocation rules. Here, we add two more “central” relations, namely, (i) we introduce the core-center, defined as the center of gravity of the core, and hence, an allocation rule occupying a central position within the core and (ii) we show that the τvalue lies, in general, in a central position inside the core-cover of a quasi-balanced game. 60 Introduction to Cooperative Game Theory Short Bibliography González-Díaz, J., P. Borm, R. Hendrickx, and M. Quant (2005): “A Geometric Characterisation of the Compromise Value,” Mathematical Methods of Operations Research, 61. (Quoted in pp. 59) González-Díaz, J. and E. Sánchez-Rodríguez (2003a): “The Core-Center and the Shapley Value: A Comparative Study,” Reports in Statistics and Operations Research 03-10, University of Santiago de Compostela. (Quoted in pp. 59) ——— (2003b): “From Set-Valued Solutions to Single-Valued Solutions: The Centroid and the Core-Center,” Reports in Statistics and Operations Research 03-09, University of Santiago de Compostela. (Quoted in pp. 59) Housman and Clark (1998): “Core and Monotonic Allocation Methods,” International Journal of Game Theory, 27, 611–616. (Quoted in pp. 59) Shapley, L. S. (1953): “A Value for n-Person Games,” in Contributions to the theory of games II, ed. by H. Kuhn and A. Tucker, Princeton: Princeton University Press, vol. 28 of Annals of Mathematics Studies.(Quoted in pp. 59) Tijs, S. (1981): “Bounds for the Core and the τ-Value,” in Game theory and mathematical economics, ed. by O. Moeschlin and D. Pallaschke, Amsterdam: North Holland Publishing Company, 123–132. (Quoted in pp. 59) Young, H. (1985): “Monotonic Solutions of Cooperatives Games,” International Journal of Game Theory, 14, 65–72. (Quoted in pp. 59) Chapter 5 A Natural Selection from the Core of a TU game: The Core-Center Contents 5.1 Game Theory Background . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 The Core-Center . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.2.1 A Fairness Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2.3 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2.4 Continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2.5 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.3 Continuity of the Core-Center . . . . . . . . . . . . . . . . . . . . . . . 71 5.3.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.3.2 A New Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.3.3 Back to Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.A Appendix (Classical Results) . . . . . . . . . . . . . . . . . . . . . . . 81 5.A.1 The Riesz Representation Theorem . . . . . . . . . . . . . . . . . . . . 81 5.A.2 The Weak∗Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.A.3 Lebesgue’s Dominated Convergence Theorem . . . . . . . . . . . . . . 82 Bibliography ................................... 84 61 68 Chapter 5. A Natural Selection from the Core of a TU game: The Core-Center in the core, it cannot not satisfy coalitional monotonicity when the number of players is greater than three. Hence, the core-center does not satisfy coalitional monotonocity. Things do not get better if we weaken the monotonicity property in the direction of aggregate monotonicity. Proposition 5.1. Let n≥4. Then, the core-center does dot satisfy aggregate monotonicity within the class of balanced games with n-players. Proof. The proof is made by means of an example when n= 4. If n > 4the example can be adapted by adding dummy players. Let (N, v)∈Gnbe such that N={1,2,3,4}and vis defined as follows: S1 2 3 4 12 13 14 23 24 34 123 124 134 234 N v(S)0 0 0 0 0 1 1 1 1 0 1 1 1 2 2 Now, C(N, v) = {(0,0,1,1)}and hence, µ(N, v) = (0,0,1,1). Let co(A)stand for the convex hull of the set A. Let (N, w)be such that w(N) = 3 and for each S6=N,w(S) = v(S). Then, S1 2 3 4 12 13 14 23 24 34 123 124 134 234 N w(S)0 0 0 0 0 1 1 1 1 0 1 1 1 2 3 and C(N, w) = co{(1,0,1,1),(0,0,2,1),(0,0,1,2),(0,1,1,1),(1,1,1,0),(1,1,0,1),(1,2,0,0)}. Next, we prove that the core-center does not satisfy aggregate monotonicity by showing that µ3(N, v)> µ3(N, w). Let (N, ˆw)be the game defined as follows: S1 2 3 4 12 13 14 23 24 34 123 124 134 234 N ˆw(S)0 0 0 0 0 1 1 1 1 0 1 1 2 2 3 with core C(N, ˆw) = co{(1,0,1,1),(0,0,2,1),(0,0,1,2),(0,1,1,1),(1,1,1,0),(1,1,0,1)}. The game (N, ˆw)only differs from (N, w)in the value for the coalition {1,3,4}. Figures 5.2 and 5.3 show the cores of (N, w)and (N, ˆw), respectively. Note that, because of the stronger restriction for coalition {1,3,4},C(N, ˆw)(C(N, w). Now, C(N, ˆw)is symmetric with respect to the point (0.5,0.5,1,1),i.e.,x∈C(N, ˆw)⇔ −x−(0.5,0.5,1,1)+ (0.5,0.5,1,1) ∈C(N, ˆw). Hence, µ(N, ˆw) = (0.5,0.5,1,1). Now, C(N, w)\C(N, ˆw)(co{(1,1,1,0),(0,1,1,1),(1,1,0,1),(1,2,0,0)}. Hence, for each x∈ C(N, w)\C(N, ˆw),x3≤1. Moreover, the volume of the points in C(N, w)\C(N, ˆw)with the third coordinate smaller than 1 is positive. Hence, by the definition of the core-center, since µ3(N, ˆw) = 1, we have µ3(N, w)<1 = µ3(N, v). Hence, the core-center does not satisfy aggregate monotonicity. 5.2. The Core-Center 69 1 2 4 3 Figure 5.2: The core of the game (N, w) 1 2 4 3 Figure 5.3: The core of the game (N, ˆw) The nucleolus (Schmeidler, 1969) also violates the three monotonicity properties we have studied so far. Zhou (1991) introduces the weak coalitional monotonicity and shows that the nucleolus satisfies it. This weakening of the coalitional monotonicity only requires that, when one coalition improves moving from (N, w)to (N, v)and there is no difference for all the other coalitions, then, the coalition as a whole (instead each player separately) has to be better off in the allocation selected for (N, v). Proposition 5.2. The core-center satisfies weak coalitional monotonicity. Proof. Let (N, v)and (N, w)be two balanced games as in the definition of weak coalitional monotonicity, i.e., they only differ in the fact that w(T)> v(T)for a given coalition T. If T=Nthe result is immediately derived from the efficiency property. Hence, we can assume T(N. If C(N, w) = C(N, v)then µ(N, w) = µ(N, v)and Pi∈Tµi(N, w)≥Pi∈Tµi(N, v). Hence, we can assume that C(N, w)(C(N, v). Let x∈C(N, v)\C(N, w)and y∈C(N, w), then Pi∈Tyi≥w(T)>Pi∈Txi. Since the core-center is the expectation of the uniform distribution over the core, and passing from C(N, v)to C(N, w)we have removed the “bad” allocations for coalition T(as a whole), this coalition is better off in the core-center of (N, w). Hence, the core-center and the nucleolus have an analogous behavior with respect to all monotonicity properties discussed in this Chapter. 5.2.4 Continuity When introducing a new allocation rule, one of the first things to study is whether it is continuous or not. Intuitively, one could think that the center of gravity of the core of a game (N, v)varies continuously as a function of (N, v). Although the result is true, that intuition could lead to wrong arguments. The core is a set-valued mapping from R2n−1to Rn, and there is a huge literature 70 Chapter 5. A Natural Selection from the Core of a TU game: The Core-Center studying the problem of continuous selection from set-valued mappings (see, for instance, Michael (1956)). If two balanced games are close enough (as vectors of R2n−1), then the corresponding cores are also close to each other (as sets). We are computing the center of gravity of these sets when they are endowed with the uniform distribution. Hence, the question is: are also the corresponding measures (associated with the uniform distribution) close to each other? This problem is not trivial at all. The following example shows what the problem is: Example 5.1. Consider the triangle with vertices (a, 0),(−a, 0) and (0,1). The center of gravity of this triangle is (0,1/3), no matter the value atakes. If we let atend to 0then, “in the limit”, we get the segment joining the points (0,0) and (0,1), whose center of gravity is (0,1/2), which is not the limit of the centers of gravity. The problem with the continuity arises when the number of dimensions of the space under consideration is not fixed, i.e., an (n−2)-polytope can be expressed (as a set) as the limit of (n−1)-polytopes. As we have shown in the previous example, the continuity property is quite sensitive to this kind of degenerations. Hence, this problem must be handled carefully, taking into account that the center of gravity of a convex polytope does not necessarily vary with continuity if degenerations are permitted. Even so, the following statement is true: Theorem 5.1. The core-center is continuous. The proof of this statement is quite technical. In Section 5.3 we formally introduce the problem along with the concepts needed for the proof. 5.2.5 Computation The complexity of the computation of any allocation rule is a concept which also needs to be studied. Here, we provide some insights to this problem when working with the core-center. The computation of the center of gravity of a convex polytope is a problem which has been widely studied in computational geometry. There are many negative results concerning the complexity of this problem. In the case of the core-center, even if we are given a polynomial description of the game (i.e., of the function v), the computation time can grow exponentially with the number of players. Basically, there are two ways for obtaining the center of gravity of a convex polytope. The classical one consists of the exact computation; many algorithms have already been developed for this issue, but all of them are exponential in the number of players. The second approach consists of using randomizing procedures to estimate the center of gravity. Roughly speaking, these procedures lead to algorithms which allow to obtain the estimations in polynomial time whenever we are able to find out whether a point belongs or not to the core in polynomial time; this is not a mild assumption, but it cannot be dispensed with. 5.3. Continuity of the Core-Center 71 5.3 Continuity of the Core-Center 5.3.1 The Problem First, we introduce the exact formulation of the problem to be solved. Henceforth, we denote a game (N, v)by v. Note that in order to prove Theorem 5.1 it is enough to show that for each balanced game v, and each sequence of balanced games converging to v(under the usual convergence of vectors in R2n−1), the associated sequence of the core-centers of the games converges to the core-center of v. Formally, Theorem 5.2. Let ¯vbe a balanced game and {vt}a sequence of balanced games such that limt→∞ vt= ¯v. Then, limt→∞ µ(vt) = µ(¯v). Clearly, Theorems 5.1 and 5.2 are equivalent. The next Proposition, which is a weaker version of the previous Theorem contains the difficult part of the proof. Theorem 5.2, and hence Theorem 5.1, are an easy consequence. Proposition 5.3. Let ¯vbe a balanced game and {vt}a sequence of balanced games such that (i) for each t∈N, we have ¯v(N) = vt(N), (ii) limt→∞ vt= ¯v. Then, limt→∞ µ(vt) = µ(¯v). In contrast with Theorem 5.2, where every possible sequence of games is considered, Proposition 5.3 only concerns specific sequences. Next, we prepare the ground for Proposition 5.3. We do it by stating and proving a general result. Then, Proposition 5.3 is easily derived. We make use of some measure theory and functional analysis results, which help us to place our result on a firm basis. 5.3.2 A New Framework Next, we introduce a new framework in which we state and prove a general convergence result for uniform measures. Then, the main part of the proof of Proposition 5.3 is a particular case. The idea of the whole procedure can be summarized as follows: whenever we think about a balanced game and its core-center, we can just think of a polytope (its core) and its center of gravity. Similarly, whenever we have a polytope and its center of gravity, we can just think of the uniform measure defined over the polytope and the integral of the identity function with respect to it. Following this idea, if we want to prove that the core-center of a sequence of games converges to the core-center of the limit game (Theorem 5.2), it is enough to prove that the integrals over the corresponding uniform measures also converge. 72 Chapter 5. A Natural Selection from the Core of a TU game: The Core-Center Notation A (convex) polyhedron is defined as the intersection of a finite number of closed halfspaces. A polyhedron Pis an m-polyhedron if its dimension is m,i.e., the smallest integer such that P is contained in an m-dimensional space. A (convex) polytope is a bounded polyhedron. Let Mm λstand for the Lebesgue measure on Rm. Let A⊆Rmbe a Lebesgue measurable set and let m′≥m; we denote Mm′ λ(A)by Volm′(A),i.e., the m′-dimensional volume of A; hence, if A⊆Rm and m′> m, then, Volm′(A) = 0. Let Pbe an m-polytope and XPits characteristic function; let MPbe the Borel measure such that MP:= 1 Volm(P)XPMm λ,i.e., the uniform measure defined over polytope P. Let ube a vector in Rm. Let Hu αbe the following hyperplane normal to u,Hu α:= {x∈Rm: Pm j=1 ujxj=α}. Let BH be the halfspace below hyperplane H. Let Pbe a polytope, then we say that hyperplane His a supporting hyperplane for Pif H∩P6=∅and BH contains P. Usually, a face of a polytope Pis defined as (i) Pitself, (ii) the empty set, or (iii) the intersection of Pwith some supporting hyperplane. With a slight abuse of language, we use the term face to designate only (m−1)-dimensional faces of an m-polytope. Let F(P)be the set of all faces of P and Fbe an arbitrary face. Let Pbe an m-polytope. Then, the finite set of polytopes {P1,...,Pk}is a dissection of Pif (i) P=Sk j=1 Pjand (ii) for each pair {j, j′} ⊆ {1,...,k}, with j6=j′,Volm(Pj∩Pj′) = 0. Next, we state, without proof, two elemental results. Lemma 5.2. Let Pand P′be two m-polytopes such that P′⊆P. Then, P′belongs to some dissection of P. Lemma 5.3. Let Pbe an m-polyhedron, let u∈Rm, and let α, β ∈R. Let P∩Hu α6=∅and P∩Hu β6=∅. Then, P∩Hu αis bounded if and only if P∩Hu βis bounded. Let Pbe an m-polytope, let r > 0be such that P((−r, r)m( Rm. Let R:= [−r, r]m. The pair (R, B), where Bstands for the collection of Borel sets of R, is a measure space. Let M(R)be the set of all complex-valued regular Borel measures defined on (R, B)and M+(R)the subset of real-valued and positive Borel measures. Also, let C(R)and CR(R)be the sets of all continuous functions f:R→Cand f:R→Rrespectively. As a consequence of the Riesz Representation Theorem, C(R)∗=M(R),i.e.,M(R)is the dual of C(R). This allows us to use the weak∗topology (henceforth w∗) in M(R). According to this topology, a sequence of measures {Mt}converges to a measure Mif and only if for each f∈C(R),limt→∞ RfdMt=RfdM. For each f∈C(R), and each measure M∈ M(R),hf, Mi denotes RfdM. Remark. We apologize for the readers that are not familiar with these concepts. They lead to a more consistent notation, cleaner statements, and less tedious proofs. Henceforth, convergence of a sequence of measures {Mt}to a measure Munder w∗just means that, for each continuous function f, the sequence of real numbers obtained by integration of funder the Mt’s converges to 5.3. Continuity of the Core-Center 73 the integral under M. Moreover, for notational convenience, we denote those integrals by hf, Mti and hf, Mi, respectively. The results Next, we prove two technical lemmas. Lemma 5.4. Let f:R2→Rbe a continuous function and K( R a compact set. Then, the function h:R→Rdefined by h(x) := maxy∈Kf(x, y)is continuous. Proof. Suppose, on the contrary, that his not continuous. Then, there is a sequence of real numbers {xt}such that (i) limt→∞ xt=x, and (ii) the sequence {h(xt)}does not converge to h(x). Let y∗∈Kbe such that f(x, y∗) = maxy∈Kf(x, y) = h(x). For each t∈N, let yt∈Kbe such that h(xt) = f(xt, yt). Since each yt∈K, the sequence {yt}has a convergent subsequence. Assume, without loss of generality, that {yt}itself converges and let y′be its limit. Then, f(x, y∗) = h(x) assumpt 6= lim t→∞h(xt) = lim t→∞f(xt, yt)fcont =f(x, y′). Hence, f(x, y∗)> f(x, y′). Then, there is δ > 0such that |xt−x|< δ |yt−y′|< δ )fcont =⇒f(xt, y∗)−f(xt, yt)>0, contradicting h(xt) = f(xt, yt). Corollary 5.1. Let f:Rm→Rbe a continuous function and K( Rl,1< l < m, a compact set. Then, the function h:Rm−l→Rdefined by h(x) := maxy∈Kf(x, y)is continuous. Proof. The proof of Lemma 5.4 can be immediately adapted to this general case. Note that analogous results to Lemma 5.4 and Corollary 5.1 can be stated using min instead of max. Lemma 5.5. Let M∈ M(R)and let {Mt}be a sequence of measures in M(R)such that for each f∈CR(R),limt→∞hf, Mti=hf, Mi. Then, for each f∈C(R),limt→∞hf, Mti=hf, Mi. Proof. For each f∈C(R), there exist functions f1and f2in CR(R)such that for each x∈R, f(x) = f1(x) + f2(x)i. Then, hf, Mti=Zf dMt=Zf1dMt+iZf2dMt t→∞ −→ Zf1dM +iZf2dM =hf, Mi. As a consequence of Lemma 5.5, to prove a convergence under w∗, it suffices to study functions in CR(R). Now we are ready to state the main result. 74 Chapter 5. A Natural Selection from the Core of a TU game: The Core-Center Theorem 5.3. Let Pbe an m-polytope and Ran m-dimensional cube [−r, r]mcontaining Pin its interior. Let u∈Rm. Let ¯α∈Rand let {αt}be a sequence in [¯α, ∞)with limit ¯α. Let Pt:= P∩BHu αtand ¯ P:= P∩BHu ¯α. Then, MPt w∗ −→ M¯ P. Proof. Without loss of generality, we assume that u=e1= (1,0,...,0) (otherwise a change of coordinates can be carried out) and that {αt}is a decreasing sequence of positive numbers. If ¯ P is an m-polytope, there are no degeneracies and the result is straightforward. Hence, we assume that ¯ Pis not an m-polytope. Hence, ¯α= minx∈Px1. Now, we distinguish two cases: ¯ Pis an (m−1)-polytope, and ¯ Pis an (m−l)-polytope, with l > 1(multiple degeneracy). Case 1: ¯ Pis an (m−1)-polytope. Let Qbe the polyhedron defined as follows, Q:= {y∈Rm:y=x+γe1,where x∈¯ Pand γ > 0}. Now, for each t∈N, we define the auxiliary polytopes Qt:= Q∩BHe1 αt. Also, let ¯ Q:= Q∩BHe1 ¯α(see Figure 5.4). Note that, by definition, ¯ Q=¯ P. ¯ P Qt−1Qt He1 αt He1 αt−1 ···He1 ¯α x Qt(x) R P Figure 5.4: The Qtpolytopes The proof is in three steps. In Step 1 we prove that the sequence of measures induced by the auxiliary polytopes, {MQt}, converges to M¯ Q. In Step 2, we study the relations between the volumes of Pt\Qt,Qt\Pt, and Qt. Finally, in Step 3 we obtain the desired convergence result, i.e., that of the sequence {MPt}to M¯ P. Recall that, by Lemma 5.5, we can restrict our attention to functions in CR(R)whenever we have to prove some convergence under w∗. Step 1: MQt w∗ −→ M¯ Q. We want to prove that for each f∈CR(R),limt→∞hf, MQti=hf, M ¯ Qi. Step 1.a: Let f∈CR(R)be such that there exists c: [−r, r]m−1→Rwith the following property: for each x∈[−r, r]m,f(x) = c(x−1). Let dx−1stand for dx2. . . dxm. Also, for each 5.3. Continuity of the Core-Center 75 x∈¯ Qand each t∈N, we define the 1-polytopes Qt(x) := {y∈Qt:y−1=x−1}. Note that, if x6=x′, then Qt(x)∩Qt(x′) = ∅and Vol1(Qt(x)) = Vol1(Qt(x′)) = αt−¯α. Moreover, for each x∈¯ Q,fis constant in Qt(x). Then, hf, MQti=1 Volm(Qt)Z¯ QZQt(x) c(x−1)dx−1dx1 =αt−¯α Volm(Qt)Z¯ Q c(x−1)dx−1 =1 Volm−1(¯ Q)Z¯ Q c(x−1)dx−1 =hf, M ¯ Qi. Step 1.b: Let f∈CR(R). Define the three auxiliary functions f∗(x1, x−1) := f(¯α, x−1), ct(x1, x−1) := max z∈[¯α,αt]f(z, x−1),and ct(x1, x−1) := min z∈[¯α,αt]f(z, x−1). By Corollary 5.1, functions ctand ctare continuous. Hence, by Step 1.a, we have hct, MQti= hct, M ¯ Qiand hct, MQti=hct, M ¯ Qi. By the continuity of f, for each x∈R,limt→∞ ct(x) = f∗(x) = limt→∞ ct(x). Let gbe the constant function such that for each x∈R,g(x) := maxx∈R|f(x)|. Since Rg dM ¯ Q= maxx∈R|f(x)|,gis Lebesgue integrable with respect to M¯ Q. Moreover, for each x∈R,|ct(x)| ≤ g(x)and |ct(x)| ≤ g(x). Since MQt∈ M+(R), then hct, MQti ≤ hf, MQti ≤ hct, MQti. Now, the Lebesgue’s Dominated Convergence Theorem completes Step 1, hct, MQti ≤ hf, MQti ≤ hct, MQti Step 1.a hct, M ¯ Qi t→ ∞ ↓Dom Conv hf∗, M ¯ Qi f∗(x) = f(x),x∈¯ Q hf, M ¯ Qi Step 1.a hct, M ¯ Qi t→ ∞ ↓Dom Conv hf∗, M ¯ Qi f∗(x) = f(x),x∈¯ Q hf, M ¯ Qi. Hence, for each f∈CR(R),limt→∞hf, MQti=hf, M ¯ Qi. Step 2: lim t→∞ Volm(Pt\Qt) Volm(Qt)= lim t→∞ Volm(Qt\Pt) Volm(Qt)= 0 and lim t→∞ Volm(Pt) Volm(Qt)= 1. We show that limt→∞ Volm(Pt\Qt) Volm(Qt)= 0, being the proof for Qt\Ptanalogous. By Lemma 5.2, there are polytopes P1 1, . . . , Pk 1,k≥1, such that {P1 1,...,Pk 1, Q1∩P1}is a dissection of P1. Hence, P1\Q1(∪k j=1Pj 1= co(P1\Q1). Note that co(P1\Q1)coincides with the closure of P1\Q1. Now, for each t∈Nand each j∈ {1,...,k}, let Pj t:= Pj 1∩BHe1 αt. Then, for each 76 Chapter 5. A Natural Selection from the Core of a TU game: The Core-Center t∈N,{P1 t,...,Pk t, Qt∩Pt}is a dissection of Ptand Pt\Qt(∪k j=1Pj t= co(Pt\Qt). Hence, Volm(Pt\Qt)≤Pk j=1 Volm(Pj t)(actually, they are equal). Now, since Volm(Qt) = Volm−1(¯ P)(αt−¯α),Volm(Qt) = O(αt−¯α),i.e.,Volm(Qt)is a linear function of (αt−¯α).1Let j∈ {1,...,k}, since ¯ Q=¯ P,Pj 1∩BHe1 ¯αis contained in some face of ¯ P,i.e., it is in the boundary of ¯ P. Hence, Pj 1∩BHe1 ¯αis, at most, an (m−2)-polytope. Hence, if for each t∈N,Pj tis an m-polytope, we have that, in the limit, there is, at least, a 2-dimensional degeneracy. Hence, Volm(Pj t) = o((αt−¯α)2).2Now, since the number of polytopes in the dissection is finite, we have Volm(Pt\Qt) = o((αt−¯α)2). Finally, lim t→∞ Volm(Pt\Qt) Volm(Qt)= lim t→∞ o((αt−¯α)2) O(αt−¯α)= 0. We turn now to Volm(Pt) Volm(Qt). Since Pt=Qt\(Qt\Pt)∪(Pt\Qt), and Qt\(Qt\Pt)and Pt\Qtare disjoint sets, then Volm(Pt) = Volm(Qt)−Volm(Qt\Pt) + Volm(Pt\Qt). Hence, lim t→∞ Volm(Pt) Volm(Qt)= lim t→∞1−Volm(Qt\Pt) Volm(Qt)+Volm(Pt\Qt) Volm(Qt)= 1. Step 3: MPt w∗ −→ M¯ P. Zf dMPt=ZfXPt Volm(Pt)dMm λ =1 Volm(Pt)Zf(XQt−XQt\Pt+XPt\Qt)dMm λ =ZfXQt Volm(Pt)dMm λ−ZfXQt\Pt Volm(Pt)dMm λ+ZfXPt\Qt Volm(Pt)dMm λ. We want to show that both the second and the third addend tend to 0. We can assume that Volm(Qt\Pt)6= 0, otherwise, RfXQt\PtdMm λ= 0 and we are done with the corresponding addend. Similarly, we assume that Volm(Pt\Qt)6= 0. Now, Zf dMPt=A1−A2+A3, where, A1=Volm(Qt) Volm(Pt)ZfXQt Volm(Qt)dMm λ=Volm(Qt) Volm(Pt)Zf dMQt, A2=Volm(Qt\Pt) Volm(Pt)ZfXQt\Pt Volm(Qt\Pt)dMm λ=Volm(Qt\Pt) Volm(Pt)ZfdMQt\Pt,and A3=Volm(Pt\Qt) Volm(Pt)ZfXPt\Qt Volm(Pt\Qt)dMm λ=Volm(Pt\Qt) Volm(Pt)Zf dMPt\Qt. 1We say that f(t) = O(g(t)) if there are c1, c2>0and t′∈Nsuch that, for each t > t′,c1|g(t)| ≤ |f(t)| ≤ c2|g(t)|. The notation f(t) = o(g(t)) means that there is c > 0and t′∈Nsuch that, for each t > t′,|f(t)| ≤ c|g(t)|. 2Just because, roughly speaking, the volume of a polytope is a linear function of its “length” in each dimension. 5.3. Continuity of the Core-Center 77 Since RfdMQt\Pt≤maxx∈Rf(x)and RfdMPt\Qt≤maxx∈Rf(x), then, by Step 2, both A2 and A3tend to 0. We move now to A1. By Step 2, limt→∞ Volm(Qt) Volm(Pt)= 1. Since, by Step 1, limt→∞ Rf dMQt=Rf dM ¯ P, we have limt→∞ Rf dMPt=Rf dM ¯ P. Case 2: ¯ Pis an (m−l)-polytope, l > 1. We have multiple degeneracy. To study this case, new auxiliary polytopes Qtand ¯ Qhave to be defined, but the idea of the proof is the same. Assume that the degeneracies are in the first l components. Then, there exist a1,...,al∈Rsuch that for each x∈¯ P,x1=a1,...,xl=al. Let {F1,...,Fk} ⊆ F(P)be the set of the faces of Pcontaining ¯ P; since ¯ Pis an (m−l)-polytope, k≥2. For each j∈ {1, . . . , k}, let Hjbe the hyperplane containing Fjand assume, without loss of generality, that P(BHj. For each i∈ {1,...,m}, let ei∈Rmbe the i-th canonical vector. Let Qbe the polyhedron defined as follows, Q:= (y∈Rm:for each j∈ {1,...,k}, y ∈BHjand y=x+Pl i=1 γiei,where x∈¯ Pand, for each i∈ {1,...,l}, γi>0). Now, for each t∈N, we define the auxiliary polytopes Qt:= Q∩BHe1 αt. Also, let ¯ Q:= Q∩BHe1 ¯α(see Figure 5.5). Note that, by definition, ¯ Q=¯ P. Since Qt∩He1 ¯α=¯ Qis bounded, applying Lemma 5.3, we have that Qtis bounded. Hence, each Qtis indeed a polytope. Now, all the steps in Case 1 can be adapted for the Qt’s. Only some minor (and natural) changes have to be made. Next, we go through these steps, stressing where modifications are needed. Step 1: MQt w∗ −→ M¯ Q. Step 1.a: Let xL:= (x1,...,xl)and x¯ L:= (xl+1,...,xm). Let f∈CR(R)be such that there exists c: [−r, r]m−l→Rwith the following property: f(xL, x¯ L) = c(xL). Also, for each x∈¯ Q and each t∈N, we define the l-polytope Qt(x) := {y∈Qt:y−L=x−L}(Figure 5.6). Again, if x6=x′, then Qt(x)∩Qt(x′) = ∅and Voll(Qt(x)) = Voll(Qt(x′)) = Volm(Qt) Volm−l(¯ Q). Moreover, for each x∈¯ Q,fis constant in Qt(x). The rest is analogous to Case 1. Step 1.b: Let f∈CR(R). Let ˆx∈¯ Q. For each t∈N, we define the compact set Kt:= {z∈Rl:z=yL,where (yL, y¯ L) = y∈Qt(ˆx)},i.e.,Ktis the projection of Qt(x)into Rl. Note that the definition of Ktis independent of the selected ˆx∈¯ Q. Define the three auxiliary functions f∗(xL, x¯ L) := f(a1,...,al, x¯ L), ct(xL, x¯ L) := max z∈Kt f(z, x¯ L),and ct(xL, x¯ L) := min z∈Kt f(z, x¯ L). With these definitions Corollary 5.1 still applies. The rest is analogous to Case 1. Step 2: lim t→∞ Volm(Pt\Qt) Volm(Qt)= lim t→∞ Volm(Qt\Pt) Volm(Qt)= 0 and lim t→∞ Volm(Pt) Volm(Qt)= 1. 84 Chapter 5. A Natural Selection from the Core of a TU game: The Core-Center Bibliography Aumann, R. J. and M. Maschler (1964): “The Bargaining Set for Cooperative Games,” in Advances in Game Theory, ed. by M. Dresher, L. S. Shapley, and A. Tucker, Princeton University Press, vol. 52 of Annals of Mathematical Studies, 443–476. (Quoted in pp. 62) Billingsley, P. (1968): Convergence of Probability Measures, New York: Wiley. (Quoted in pp. 81) Conway, J. B. (1990): A Course in Functional Analysis, Springer-Verlag. (Quoted in pp. 81) Davis, M. and M. Maschler (1965): “The Kernel of a Cooperative Game,” Naval Research Logistics Quarterly, 12, 223–259. (Quoted in pp. 62) Dutta, B. and D. Ray (1989): “A Concept of Egalitarianism under Participation Constraints,” Econometrica, 57, 615–635. (Quoted in pp. 65) Gautier, S. and R. Morchadi (1992): “A Selection of Convex-Compact-Valued Multi- Functions with Remarkable Properties: the Steiner Selection,” Numerical Functional Analysis and Optimization, 13, 513–522. (Quoted in pp. 62) Gillies, D. B. (1953): “Some Theorems on n-Person Games,” Ph.D. thesis, Princeton. (Quoted in pp. 62, 64) González-Díaz, J., P. Borm, R. Hendrickx, and M. Quant (2005): “A Geometric Characterisation of the Compromise Value,” Mathematical Methods of Operations Research, 61. (Quoted in pp. 63) Housman and Clark (1998): “Core and Monotonic Allocation Methods,” International Journal of Game Theory, 27, 611–616. (Quoted in pp. 67) Maschler, M., B. Peleg, and L. S. Shapley (1979): “Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts,” Mathematics of Operations Research, 4, 303–338. (Quoted in pp. 62, 67) Michael, E. (1956): “Continuous Selections. I,” The Annals of Mathematics, 63, 361–382. (Quoted in pp. 62, 70) Rudin, W. (1966): Real and Complex Analysis, McGraw-Hill. (Quoted in pp. 81) Schmeidler, D. (1969): “The Nucleolus of a Characteristic Function Game,” SIAM Journal on Applied Mathematics, 17, 1163–1170. (Quoted in pp. 62, 69) Shapley, L. S. (1953): “A Value for n-Person Games,” in Contributions to the theory of games II, ed. by H. Kuhn and A. Tucker, Princeton: Princeton University Press, vol. 28 of Annals of Mathematics Studies.(Quoted in pp. 62) Tijs, S. (1981): “Bounds for the Core and the τ-Value,” in Game theory and mathematical economics, ed. by O. Moeschlin and D. Pallaschke, Amsterdam: North Holland Publishing Company, 123–132. (Quoted in pp. 62) von Neumann, J. and O. Morgenstern (1944): Theory of Games and Economic Behavior, Princeton: Princeton University Press. (Quoted in pp. 62) BIBLIOGRAPHY 85 Young, H. (1985): “Monotonic Solutions of Cooperatives Games,” International Journal of Game Theory, 14, 65–72. (Quoted in pp. 67) Zhou, L. (1991): “A Weak Monotonicity Property for the Nucleolus,” International Journal of Game Theory, 19, 407–411. (Quoted in pp. 69) Chapter 6 A Characterization of the Core-Center Contents 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.2 Game Theory Background . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.2.1 The Core and its Relatives . . . . . . . . . . . . . . . . . . . . . . . . 90 6.2.2 Some Geometric Considerations . . . . . . . . . . . . . . . . . . . . . . 90 6.2.3 The Core-Center . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.3 Fair Additivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.3.1 T-Solutions and RT -Solutions . . . . . . . . . . . . . . . . . . . . . . 92 6.3.2 RT -Solutions and Balanced Games: Fair Additivity . . . . . . . . . . 94 6.4 The Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.4.1 An Elemental Core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.4.2 The Core is Full Dimensional . . . . . . . . . . . . . . . . . . . . . . . 100 6.4.3 The Core is Not Full Dimensional . . . . . . . . . . . . . . . . . . . . 104 6.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.A Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.A.1 The Geometry of the Core-Center in Depth . . . . . . . . . . . . . . . 106 Bibliography ...................................109 87 88 Chapter 6. A Characterization of the Core-Center 6.1 Introduction In González-Díaz and Sánchez-Rodríguez (2003), the core-center, a new allocation rule for the class of balanced games is introduced. That paper contains a first approach both to the study of the axiomatic properties of the core-center and to the search for an axiomatic characterization. This Chapter focuses in the latter. We formally develope and refine the characterization provided there. The key property for the characterization is a weighted additivity, based on a principle of fairness with regard to the core, that we call fair additivity. This property, along with other standard properties in game theory leads to the axiomatic characterization of the core-center. It has a certain parallelism with the characterization of the Shapley value based on the additivity property. First, we prove the result for games with a simplicial core, which play the role of the unanimity games in Shapley’s characterization. Second, we prove the result for arbitrary games by means of simplicial dissections of their cores. In the fair additivity property the weights depend on the volumes of the cores. There are antecedents in game theory that look for this kind of fairness. One of the solutions for two person bargaining problems which depends on the whole feasible set is the Equal Area Solution. Anbarci and Bigelow (1994) interpreted equal area as equal concessions. Later Calvo and Peters (2000) looked at the underlying dynamic process. The structure of this Chapter is as follows. In Section 6.2 we introduce the preliminary game theoretical concepts along with the definition of the core-center. In Section 6.3 we introduce and discuss the fair additivity property. In Section 6.4 we state and prove the characterization of the core-center. Finally, in the Appendix we provide rigorous proofs of some technical statements which have been skipped in the text; moreover, it also includes formal definitions and properties of some geometric concepts used along the Chapter. 6.2 Game Theory Background A transferable utility or TU game is a pair (N, v), where N:= {1, . . . , n}is a set of players and v: 2N→Ris a function assigning to each coalition S⊆Na payoff v(S). By convention, v(∅) = 0. Since each game assigns a real value to each nonempty subset of N, it corresponds with a vector in R2n−1. Let |S|be the number of elements of coalition S. Saving notation, when no ambiguity arises, we use ito denote {i}. Given a game (N, v),the imputation set is defined by I(N, v) := {x∈Rn:Pi∈Nxi=v(N)and, for each i∈N,xi≥v(i)}. Let x∈Rnbe an allocation. Then, xis efficient if Pn i=1 xi=v(N). A game (N, v)is superadditive if for each S, T ⊆Nsuch that T∩S=∅, we have v(S∪T)≥v(S) + v(T). We restrict our attention to efficient allocations. Within this framework, it is widely accepted that superadditivity is quite a reasonable requirement for the game. This is because we expect the grand coalition to form, and then, share the amount v(N)among the players; if the game was not 6.2. Game Theory Background 89 superadditive this expectation might be unfounded. Hence, in the present Chapter we restrict to the class of superadditive TU games, denoted by G(Gndenotes the superadditive games with n players). An allocation rule is a function which, given a game (N, v), selects an allocation in Rn,i.e., ϕ: Ω ⊆Gn−→ Rn (N, v)7−→ ϕ(N, v). Next, we define some properties for allocation rules. Let (N, v)∈Gnand let ϕbe an allocation rule: ϕis continuous if the function ϕ:R2n−1→Rnis continuous; ϕis efficient if it always select efficient allocations; ϕis translation invariant if for each two games (N, v)and (N, w), and each α= (α1,...,αn)∈Rnsuch that for each S⊆N,w(S) = v(S) + Pi∈Sαi, then ϕ(N, w) = ϕ(N, v) + α. Next, we define some properties regarding symmetry. Let (N, v)∈Gnand let i, j ∈N. Then, iand jare symmetric if for each S⊆N\{i, j},v(S∪i)−v(S) = v(S∪j)−v(S);iand jare quasi-symmetric if for each S⊆N\{i, j},v(S∪i)−(v(S)+v(i)) = v(S∪j)−(v(S)+v(j)). Now, (N, v)is symmetric if for each pair i, j ∈N,iand jare symmetric; (N, v)is quasi-symmetric if for each pair i, j ∈N,iand jare quasi-symmetric or, equivalently, a game is quasi-symmetric if the corresponding 0-normalized game is symmetric. Note that, for a symmetric game, v(S)depends only on the cardinality of S(this gives an idea of the strength of this property). Quasi-symmetric games are important in this Chapter because their cores are symmetric sets from the geometric point of view. Finally, we define two symmetry properties for an allocation rule. Let ϕbe an allocation rule. We say ϕsatisfies weak symmetry if for each symmetric game (N, v)and each pair i, j ∈N, ϕi(N, v) = ϕj(N, v);ϕsatisfies extended weak symmetry if for each quasi-symmetric game (N, v) and each pair i, j ∈N,ϕi(N, v)−v(i) = ϕj(N, v)−v(j). The extended weak symmetry property says that if for each pair i, j ∈N, their contribution to any coalition differs only in v(i)−v(j), then, the difference in the payoffs is also v(i)−v(j). This property, besides being a symmetry property (it implies weak symmetry) has some flavor to translation invariance; roughly speaking, it says that the allocation rule satisfies weak symmetry and, moreover, translation invariance within the class of quasi-symmetric games. Next Lemma illustrates this point. Lemma 6.1. Translation invariance +weak symmetry ⇒extended weak symmetry. Proof. Let ϕbe an allocation rule satisfying both translation invariance and weak symmetry. Let (N, v)be a quasi-symmetric game and α= (−v(1),...,−v(n)). Now, let (N, w)∈Gnbe such that, for each S⊆N,w(S) = v(S) + Pi∈Sαi. Then (N, w)is symmetric. Hence, by weak symmetry, for each pair i, j ∈N,ϕi(N, w) = ϕj(N, w). Now, by translation invariance, we have ϕi(N, v) + αi=ϕj(N, v) + αj. Since αi=−v(i)and αj=−v(j), the result is proved. 90 Chapter 6. A Characterization of the Core-Center 6.2.1 The Core and its Relatives We introduce now the notions of core (Gillies, 1953) and strong ε-core (Maschler et al., 1979); both of them are based on efficiency and stability. An allocation x∈Rnis stable if there is no coalition S⊆Nsuch that Pi∈Sxi< v(S), analogously, for each ε∈R,xis ε-stable if there is no coalition S⊆Nsuch that Pi∈Sxi< v(S)−ε. The core of a game (N, v),C(N, v), is the set of all efficient and stable allocations C(N, v) := {x∈Rn:X i∈N xi=v(N)and, for each S(N, X i∈S xi≥v(S)}. The class of games with nonempty core is the class of balanced games. Let BG (Gbe the class of superadditive balanced games (BGn(Gndenotes the set of superadditive balanced games with nplayers). Let ε∈R. The strong ε-core of a game (N, v),Cε(N, v)is the set of all efficient and ε-stable allocations: Cε(N, v) := {x∈Rn:X i∈N xi=v(N)and, for each S(N, X i∈S xi≥v(S)−ε}. By definition, if ε= 0,C0(N, v)≡C(N, v). The least core of (N, v),LC(N, v), is the intersection of all nonempty strong ε-cores. Equivalently, let ε0(N, v)be the smallest εsuch that Cε(N, v)6=∅, then LC(N, v) = Cε0(N,v)(N, v).1 Let (N, v)∈Gn. The family of “shifted” games (N, vε)is defined by:2 vε(S) := (v(S)−ε∅(S(N v(S)S=∅or S=N. Finally, we introduce a last concept related to balanced games: a balanced game (N, v)is exact (Schmeidler, 1972) if for each S⊆N, there is x∈C(N, v)such that Pi∈Sxi=v(S). Moreover, let (N, v)∈BGnwith core C(N, v), then, there is a unique exact game (N, ˆv)such that C(N, ˆv) = C(N, v); this game is the exact envelope of (N, v). Note that if we have two exact games with the same core, then they are the same game. From the point of view of stability, we can say that (N, ˆv)throws away the redundant information of (N, v). 6.2.2 Some Geometric Considerations For the sake of clarity, and if it does not entail confusion, henceforth we denote a game (N, v)by v. We need to introduce some notation and make some considerations regarding the underlying geometry of a TU game. We denote the efficient hyperplane by HN v; hence, HN v:= {x∈Rn: 1In Maschler et al. (1979) it is shown that ε0(N, v)exists and is unique. 2This concept has also been taken from Maschler et al. (1979) 6.2. Game Theory Background 91 Pi∈Nxi=v(N)}. All the sets we consider in this Chapter are contained in HN vand hence, we develop all our framework in an (n−1)-dimensional euclidean space. A(convex) polytope Pis the convex hull of a finite set of points V={x1,...,xk}in Rn, equivalently, it is a bounded subset of Rnwhich can be expressed as the intersection of a finite number of halfspaces. The core of a game, when nonempty, is a convex polytope (it is the intersection of halfspaces in HN v). An m-polytope is a polytope that lies in an m-dimensional space but there is no (m−1)-dimensional space containing it. Let Pbe an m-polytope and let m′≥m, then, Volm′(P)denotes the m′-dimensional volume of P. Let Pbe an m-polytope. Then, a set of polytopes {P1,...,Pk}define a dissection of Pif (i) P=Sk l=1 Pland (ii) for each pair l, l′∈ {1,...,k}, with l6=l′,Volm(Pl∩Pl′) = 0. Lemma 6.2. Except for the least core, all nonempty strong ε-cores are (n−1)-polytopes. The least core is always an m-polytope with m < n −1. Proof. The statement in this lemma has been taken from Maschler et al. (1979). Hence, we do not prove it. Anyway, not being a completely straightforward result, it is quite intuitive. Whenever the core of a game in Gnis an (n−1)-polytope, we say it is a full dimensional core. Otherwise, it is degenerate. By definition, all the restrictions in the core of a game are as follows: let S(N,RS v:= {x∈Rn:Pi∈Sxi≥v(S)}. Let RS vbe a restriction, then we say that RS vis a |S|-restriction. The 1-restrictions play a special role in this Chapter; we call them elemental restrictions. We say a restriction is redundant in the core if removing it does not change the core. Conversely, the restrictions which are not redundant ones are active restrictions. Let HS vbe the hyperplane associated with the restriction RS v,i.e.,x∈HS vif and only if x∈HN v and Pi∈Sxi=v(S). Note that, because of the efficiency condition, the hyperplanes HS vhave dimension n−2. Lemma 6.3. Let v∈Gnand let ∅(S(N. Then, the hyperplanes HS vand HN\S vare parallel in HN v. Proof. Let v∈Gnand ∅(S(N. Then, HS v:= {x∈Rn:Pi∈Sxi=v(S)}. We claim that there is k∈Rsuch that HS vcan be expressed as Pi∈N\Sxi=k. Once this claim is proved, the statement of the Lemma is immediately derived. Since we work in HN v,Pi∈Sxi+Pi∈N\Sxi= v(N). If we impose the restriction Pi∈Sxi=v(S), we have v(S) + Pi∈N\Sxi=v(N). Hence, Pi∈N\Sxi=v(N)−v(S) = k. 6.2.3 The Core-Center The core of a game is the set of all the stable and efficient allocations. Now, if we consider that all these allocations are equally reasonable, then it makes sense to think of the core as if it was endowed with a uniform distribution. The core-center summarizes the information of such a distribution of probability. Let U(A)be the uniform distribution defined over the set Aand E(P)the expectation of the probability distribution P. 92 Chapter 6. A Characterization of the Core-Center Definition 6.1. Let (N, v)be a balanced game with core C(N, v). The core-center of (N, v), µ(N, v), is defined as follows: µ(N, v) := E[U(C(N, v))] . 6.3 Fair Additivity We devote this Section to the motivation and definition of the fair additivity property. This property is crucial in the characterization of the core-center we obtain in Section 6.4. First, before introducing the fair additivity property, we define a general family of allocation rules, that we call T-solutions. Then, we say that an allocation rule satisfies the fair additivity property if it belongs to a special subfamily of T-solutions. 6.3.1 T-Solutions and RT-Solutions We need to introduce some concepts before formally defining what a T-solution is. Let v∈Gn, ∅(T(N, and k≥v(T). We use constant kto define two games: v, a good game for coalition T, and va good game for coalition N\T. Suppose that, because of some change in the situation underlying our TU game, coalition Talone can obtain kinstead of v(T). We define vas the game obtained when introducing this change in v: v(S) = (max{v(S), v(S\T) + k}T⊆S v(S)otherwise. We define ¯v(S)as max{v(S), v(S\T) + k}to ensure that vis a superadditive game. Superadditivity also implies that v(T)≤v(N)−v(N\T). Hence, if we want game vto remain in the class of superadditive games, kmust belong to the interval [v(T), v(N)−v(N\T)]. So, for value k, we have naturally defined a game vin which coalition Thas improved with respect to v. Now, for this constant k, we define a game vin which coalition Tis worst-off. We do it by letting coalition N\Timprove, i.e., defining v(N\T) := v(N)−k. The motivation for this definition comes from the idea of stability. Since v(T) = k, coalition Tshould receive at least kin game v. On the other hand, v(N\T) = v(N)−kimplies that coalition N\Tshould receive, at least, v(N)−kand hence, coalition Tshould obtain at most k. This change leads to the superadditive game: v(S) = (max{v(S), v(S\(N\T)) + v(N)−k}N\T⊆S v(S)otherwise. At this point, we have defined two games: v, in which coalition Thas improved with respect to v, and v, in which coalition N\Tis the one that is better-off. A cut on the game vfor coalition Tat height k∈[v(T), v(N)−v(N\T)] is denoted by χT,k(v)and defined as the pair of games {v, v}. The reason for the name cut becomes clear when dealing with balanced games below. 6.3. Fair Additivity 93 An extra condition needs to be imposed on cuts, namely, if v(T) = v(N)−v(N\T), then no cut is permitted for coalition T. This last requirement is quite natural, if omitted, we could have a situation in which v=v=v, and the cut makes no sense. Note that, by definition, if χT,k(v) = {v, v}and χN\T,v(N)−k(v) = {v′, v′}, then v=v′and v=v′. Lemma 6.4 shows that the games vand vare superadditive. Lemma 6.4. Let v∈Gn. Let ∅ 6=T(Nbe such that v(T)< v(N)−v(N\T). Let χT,k(v) = {v, v}. Then, both vand vare superadditive games. Proof. Let χT,k(v) = {v, v}. We do the proof for the superadditivity of v, being the one for vanalogous (just think of the cut χN\T,v(N)−k(v) = {v′, v′}where v′=v). Let S, S′⊆N, S∩S′=∅. We want to show that v(S) + v(S′)≤v(S∪S′). Now we have four possibilities: (i) T*S∪S′. Now, v(S) = v(S),v(S′) = v(S′), and v(S∪S′) = v(S∪S′). Hence, the result follows from the superadditivity of v. (ii) T⊆S∪S′,T*S, and T*S′. Now, v(S) = v(S),v(S′) = v(S′), and v(S∪S′)≥v(S∪S′). Hence, the result follows from the superadditivity of v. (iii) T*Sand T⊆S′. By definition of v,v(S) = v(S)and v(S′) = max{v(S′), v(S′\T) + k}. If v(S′) = v(S′), then, since v(S∪S′)≥v(S∪S′), we are done. Hence, we can assume that v(S′) = v(S′\T) + k. Now, since S∩S′=∅, we have T∩S=∅and hence, (S∪S′)\T=S∪(S′\T). Hence, by the definition of vand the superadditivity of v, v(S∪S′)≥v((S∪S′)\T) + k≥v(S) + v(S′\T) + k=v(S) + v(S′). (iv) T⊆Sand T*S′. Analogous to (iii). Next, we introduce the definition of T-solution, where Tstands for trade-off. Definition 6.2. An allocation rule ϕis a T-solution if for each game vand each cut χT,k(v) = {v, v}, there is α∈[0,1] such that ϕ(v) = αϕ(v) + (1 −α)ϕ(v). The idea of a T-solution is that ϕ(v), the solution of the original game, must be a trade-off between ϕ(v)and ϕ(v). The result of a give and take between coalitions Tand N\T. The coefficient αmeasures how important vand vare for the original game vwhen ϕis being considered. Once the allocation rule is fixed, the coefficient αis a function depending on the game v, the coalition T, and the constant k. Therefore, the concept of T-solution is very general and dealing with the whole family of T-solutions is not an easy task. Next, we impose a regularity condition on how the trade-off has to be made. Let v∈Gnand let {v1, v2}be a cut on v. Now, a new cut {v2, v2}can be defined on v2. Hence, we have cut the original game vinto the games {v1,v2, v2}. The generalization of this idea leads to the definition of dissection. The collection of games G={v1, v2, . . . , vr}is a dissection 100 Chapter 6. A Characterization of the Core-Center Proof. If C(v)is elemental, C(v) = I(v). For each v∈Gn,I(v)is a regular simplex4with vertices u1,...,unwhere, for each i∈N, ui= (v(1), v(2),..., i z}| { v(N)−X j6=i v(j),...,v(n)). Hence, to obtain the result, we only need to calculate the center of gravity of the simplex, i.e., the average of the vertices. Lemma 6.8. Let v∈BGn. If C(v) = I(v), then, vis quasi-symmetric. Proof. I(v)is a regular (n−1)-simplex. Hence, if C(v) = I(v), then, for each S(N, with |S|>1, the restrictions RS vare redundant. Let S(N,|S|>1. By superadditivity, v(S)≥Pi∈Sv(i). Moreover, since RS vis redundant, v(S)≤Pi∈Sv(i). Hence, v(S) = Pi∈Sv(i). Now, regardless of v(N), the game is quasi-symmetric. Proposition 6.2. Let v∈BGnbe such that C(v)is elemental. Let ϕbe an allocation rule satisfying efficiency and extended weak symmetry. Then, ϕ(v) = µ(v). Proof. Since vhas an elemental core, C(v) = I(v). By Lemma 6.8, vis quasi-symmetric. Now, by extended weak symmetry, we have that, for each pair i, j ∈N,ϕi(v)−v(i) = ϕj(v)−v(j). Hence, there is k∈Rsuch that, for each i∈N,ϕi(v) = k+v(i). The latter comment, along with the efficiency property, implies that, for each i∈N, ϕi(v) = v(N)−Pj∈Nv(j) n+v(i). Now, by Lemma 6.7, ϕ(v)is the center of gravity of C(v),i.e., the core-center. Hence, ϕ(v) = µ(v). 6.4.2 The Core is Full Dimensional In this Section we combine Proposition 6.2 with the continuity and the fair additivity properties to show that a game with a non degenerate core belongs to TG. At this point we know that games with an elemental core belong to TG. The class of games with an elemental core plays an important role in the forthcoming results. This role is similar to that of the unanimity games in the characterization of the Shapley value using additivity. The outline of this part of the proof is as follows. Let vbe a balanced game and let C(v)be full dimensional. First, successively cutting v, we obtain a dissection of C(v); being this dissection primarily composed by small parallelepipeds. Second, we cut the games corresponding to these parallelepipeds, obtaining an elemental core inside each of them. Then, we successively repeat this procedure with the remaining non-elemental cores. Finally, we show that, using cuts, the 4Go over the Appendix to find a rigorous definition of a simplex and related concepts. 6.4. The Characterization 101 core of vcan be covered with elemental cores (this is indeed a kind of triangulation). Finally, the fair additivity property leads to the conclusion of this part of the proof. Figure 6.2 illustrates this outline. =⇒ Original situation, I(v),C(v)Dissecting I(v)into parallelepipeds =⇒ All dark shaded cores Cutting the parallelepipeds are parallelepipeds to obtain elemental cores Figure 6.2: Scheme of the proof for full dimensional cores Proposition 6.3. Let v∈BGnbe such that C(v)is full dimensional. Let ϕbe an allocation rule satisfying the four properties T1-T4. Then, ϕ(v) = µ(v). Proof. Let ϕbe an allocation rule satisfying the properties T1-T4. Let v∈BGnbe a game with a full dimensional core. The body of the proof consists of dissecting C(v)into elemental cores; we do it in such a way that we can combine Proposition 6.2 with the continuity and the fair additivity properties to get ϕ(v). Hence, we describe a procedure which “nearly” triangulates any full dimensional core. Henceforth, till the end of the proof, Vol(P)denotes the (n−1)-dimensional volume of polytope P. First, we divide I(v)into small (n−1)-parallelepipeds.5Let i∈N,i’s payoff in his best allocation within I(v)is v(N)−Pj6=iv(j), and in his worst one is v(i); hence, regardless of i, the 5A rigorous definition of a k-parallelepiped can be found in the Appendix. 102 Chapter 6. A Characterization of the Core-Center difference between these two payoffs is v(N)−Pj∈Nv(j). Let L:= v(N)−Pj∈Nv(j). From now on, and for the sake of clarity, v(i)is denoted by mi. Let q∈N(for simplicity we assume q > 2), and let δ=L/q. For each face in I(v), different to that corresponding with the hyperplane xn=mn, we make q+ 1 cuts on it, all of them parallel to the hyperplane in which that face lies. Hence, we partition I(v)using the following hyperplanes: for each i∈N,i6=n, and for each k∈ {0,...,q},Hi k:= {x∈Rn:xi=mi+kδ}. We use these hyperplanes to define a dissection of C(v). Let χi,k be a cut, and let Gbe a collection of games. We denote by χi,k(G)the result of cutting successively all the cores of the games in Gwith the hyperplane xi=k. Hence, χi,k({w, w′, w′′,...}) = {w, w, w′, w′,w′′, w′′,...}. It can be the case that some of these cuts is not permitted, i.e.,k /∈[w(i), w(N)−w(N\i)]; besides, it is also possible that one of the games in χi,k(w)is not balanced. In the last two cases we take {w}instead of χi,k(w),i.e., we do not consider those cuts. Let v∈BGnbe such that C(v)is full dimensonal. Let Gδbe the collection of games defined as follows: Stage 0:We begin with the set of games G0≡ G0,q ={v}. . . . Stage i, i ∈N, i 6=n:We define the cuts for player i. Step i.0:We cut I(v)with xi=mi;Gi,0=χi,mi(Gi−1,q). Step i.1:Gi,1=χi,mi+δ(Gi,0). . . . Step i.k:Gi,k =χi,mi+kδ(Gi,k−1). . . . Step i.q:Gi,q =χi,mi+qδ(Gi,q−1). Let Gδdenote the set Gn−1,q. In order to save notation, if no ambiguity arises, we denote C(v′)by C′. Now, Sv′∈GδC′=Cand, for each pair v1, v2∈ Gδ,Vol(C(v1)∩C(v2)) = 0,i.e., the cores of the games in Gδdefine a dissection of C. It is quite intuitive that, for each 0< ε < 1, we can find δ > 0such that the sum of the volumes of the cores of games in Gδwhich are not parallelepipeds is, at most, εVol(C)(note that εis fixed now for all the proof). All these parallelepipeds are equal and they have positive (n−1)-dimensional volume. Let GNP (Gδ be the set of games such that their core is not a parallelepiped. The second part of the proof consists of cutting each one of the parallelepipeds to obtain an elemental core, a simplex, inside the parallelepiped. It is quite intuitive, and not difficult to check, that for 0< α < 1small enough, we can find a procedure which divides each parallelepiped Pin such a way that the core 6.4. The Characterization 103 of one of the resulting games is elemental and its volume is, at least, αVol(P).6Let GNE be the set of games obtained in this second step such that their core is not elemental. We can ensure now that at least a volume α(1 −ε) Vol(C)has been covered by elemental cores. Period 1is finished. The procedure continues as follows. We begin period 2: for each game v′∈ GNP ∪ GNE, we repeat the procedure we have made for v(we have to find a new constant δ′which will probably be smaller than δ), covering at least a volume α(1 −ε) Vol(C′) of its core with elemental cores. Note that the constant αkeeps constant. This is because in this second period we obtain the same kind of parallelepipeds we had in the first one (but smaller). Hence, the procedure obtained to “put” a simplex inside each parallelepiped is the same, and the proportion of covered volume also remains unchanged. Note that δvaries as the period changes but both αand εkeep constant. We claim that if we repeat successively this procedure, the volume of Cwhich is not covered by elemental cores tends to 0. We begin with a volume RV 0= Vol(C)which needs to be covered by elemental cores. After the first period, this volume has been reduced to RV 1= (1 −α)(1 −ε) Vol(C) + εVol(C). Then, after tperiods we have RV t= (a+b)tVol(C), where a= (1 −α)(1 −ε)and b=ε. The proof of this statement is easily done by induction: Case 1: RV 1= (1 −α)(1 −ε) Vol(C) + εVol(C) = (a+b) Vol(C). Case t: Assume the result is true for this case (induction assumption). Case t+1: Finally, we have RV t+1 = (1 −α)(1 −ε)RV t+εRV t=aRV t+bRV tinduc = a(a+b)tVol(C) + b(a+b)tVol(C) = (a+b)t+1 Vol(C). Hence, since a+b= (1 −α)(1 −ε) + ε < 1, we have limt→∞ RV t= limt→∞(a+b)tVol(C) = 0. This means that, in the limit, this procedure defines an infinite dissection of C(v). Let Gtbe the collection of games after period tand EGtthose with an elemental core. Now, by the fair additivity of ϕ: ϕ(v) = X v′∈Gt Vol(C′) Vol(C)ϕ(v′) = 1 Vol(C)X v′∈EGt Vol(C′)ϕ(v′) + X v′∈Gt\EGt Vol(C′)ϕ(v′).(6.1) By Proposition 6.2, we have already characterized ϕfor the games in the first addend of the last term in Equation (6.1). Moreover, since ϕis continuous, it is uniformly continuous in the set B={w∈Gn:for each S⊆N, v(S)≤w(S)≤v(N)}. Hence, ϕis bounded in B. Since all the games we have defined so far belong to B, we have limt→∞ Pv′∈Gt\EGtVol(C′)ϕ(v′) = 0. Now, 6We prove in the Appendix that the cuts divide the core of the original game in many parallelepipeds and that the proportion of the core covered by these sets is as close to one as needed. We also provide there an example of a procedure to “put” an elemental core inside each parallelepiped. 104 Chapter 6. A Characterization of the Core-Center for each t∈N,ϕ(v) = Pv′∈Gt Vol(C′) Vol(C)ϕ(v′). Then, ϕ(v) = lim t→∞ X v′∈Gt Vol(C′) Vol(C)ϕ(v′) =1 Vol(C)lim t→∞ X v′∈EGt Vol(C′)ϕ(v′) + lim t→∞ X v′∈Gt\EGt Vol(C′)ϕ(v′) = lim t→∞ 1 Vol(C)X v′∈EGt Vol(C′)ϕ(v′) Prop 6.2 = lim t→∞ 1 Vol(C)X v′∈EGt Vol(C′)µ(v′) =µ(v). 6.4.3 The Core is Not Full Dimensional Now, the core is an m-polytope with 1≤m≤n−2. Proposition 6.4. Let v∈BGnbe such that C(v)is not full dimensional. Let ϕbe an allocation rule satisfying the properties T1-T4. Then, ϕ(v) = µ(v). Proof. By Lemma 6.2, C(v)is the least core of v. Let {v1/t}t∈Nbe a sequence of shifted games. Now, limt→∞ v1/t =v. The core of v1/t coincides with the 1 t-core of v. By Lemma 6.2, all these 1 t-cores are full dimensional, and now, by Proposition 6.3 we know that these games have already been characterized. Hence, ϕ(v)cont = lim t→∞ϕ(v1/t)Prop 6.3 = lim t→∞µ(v1/t)cont =µ(v). Proof of Theorem 6.1.The assertion of the theorem follows from Propositions 6.2, 6.3, and 6.4. Next, we prove that the properties in Theorem 6.1 are tight. In order to do this we need a last Lemma. Lemma 6.9. Let vbe a quasi-symmetric game. Then, C(v)either is a point or is full dimensional. Proof. This is a geometric result. As we have already seen, the core of a quasi-symmetric game can be transformed in that of a symmetric game just using a translation. To prove this Lemma it suffices to show that the result is true for symmetric games. Hence, let vbe a symmetric game, and assume that it has a degenerate core. Hence, there are 1≤s≤n−1and an s-player coalition S, such that v(S) + v(N\S) = v(N). By efficiency and stability, we have that there is k∈Rsuch that, for each x∈C(v),Pi∈Sxi=v(S) = k(this is the reason for the degeneration). Now, by 6.4. The Characterization 105 symmetry, for each x∈C(v)and each s-player coalition S′, we have Pi∈S′xi=k. If s= 1, we have that, for each i∈Nand each x∈C(v),xi=kand we are done. Hence, we can assume that s > 1. Now, we claim that, for each x∈C(v)and each i∈N,xi=k/s. Suppose, on the contrary, that there are x∈C(v)and i∈Nsuch that xi> k/s. Hence, for each s-player coalition Scontaining i, there is j∈Ssucht that xj< k/s. But this contradicts that, for each s-player coalition Pi∈Sxi=k(just taking an s-player coalition with all these j’s such that xj< k/s and the lower of the remaining to have splayers). Hence, we have that, for each i∈N,xi=k/s. Now, by efficiency, k=sv(N)/n. Hence C(v) = {x}, where, for each i∈N,xi=v(N)/n. Proposition 6.5. None of the properties used in Theorem 6.1 to characterize the core-center is redundant. Proof. Next, we show that if we remove one of these properties there are allocation rules different from the core-center satisfying the remaining ones. Remove Fair Additivity: Both Shapley value and nucleolus satisfy efficiency, extended weak symmetry, and continuity. Remove Efficiency: Take k6= 0. The allocation rule ϕ(v) = µ(v) + (k,...,k)where µ(v) denotes the core-center of the game vsatisfies fair additivity, extended weak symmetry, and continuity. Remove extended weak symmetry: The allocation rule ϕ(v) = (v(N),0,...,0) satisfies fair additivity, efficiency and continuity. Remove continuity: This is the most complex situation, we need to distinguish different cases in the definition of our allocation rule ϕ: The core is a single point: ϕselects the point (the core-center). The core is degenerate but not a single point: In this case the allocation ϕselects the point (v(N),0,...,0). The core is not degenerate: ϕselects the core-center. This allocation rule satisfies fair additivity, efficiency and extended weak symmetry. It satisfies fair additivity because of the following: if a cut divides a core in two new cores, and one of them is not full dimensional while the original was, then, the weight of this degenerate core is 0. Efficiency is straightforward. It also satisfies extended weak symmetry: in the non-degenerate case it coincides with the core-center so extended weak symmetry is met; in the degenerate case, as a consequence of Lemma 6.9 there are no quasi-symmetric games with degenerate core with more than one point and hence, extended weak symmetry can never be violated. 106 Chapter 6. A Characterization of the Core-Center 6.5 Concluding Remarks In this Chapter we have presented a characterization of the core-center. The main result we stated uses three standard properties along with a new one, the fair additivity property. Recall that, according to the definitions of T-solution and fair additivity, given a game we can “cut” it using any nonempty coalition different from the grand coalition. Nonetheless, the proofs we presented here involve cuts that only use 1-player coalitions and hence, we could state and proof a new characterization result, similar to Theorem 6.1, but with a weakened version of the fair additivity. Although we have provided a first characterization of the core-center, more research is needed in order to find more convincing characterizations. One possibility is to deepen into the concepts of T-solution and RT-solution, and try to characterize the core-center without the additional restriction imposed by the fair additivity property. Similarly, the problem of finding an independent characterization that does not need the concept of T-solution is still to be solved. 6.A Appendix 6.A.1 The Geometry of the Core-Center in Depth -Definition of Simplex. Let {a0, a1,...,an}( Rnbe a geometrically independent set.7The simplex ∆nspanned by a0, a1,...,anis the set of all x∈Rnsuch that x=Pn i=0 tiai, where Pn i=0 ti= 1 and, for each i∈ {1,...,n},ti≥0. Each aiis a vertex of the n-simplex. The superscript nof ∆ncorresponds with the dimension of the simplex. An n-simplex is regular if the distance between any two vertices is constant. The barycenter of a simplex ∆nspanned by the points a0, a1,...,anis Θ(∆n) := Pn i=0 ai n+1 . Let m≤n, let ∆mbe an m-simplex contained in Rn, and let a0,...,ambe its vertices. The m-dimensional volume of ∆m,Volm(∆m), can be computed in the following way: Let B= (βij) denote the (m+ 1) ×(m+ 1) matrix given by βij =kai−ajk2. Then, 2m(m!)2Volm(∆m)2=|det( ˆ B)|, where ˆ Bis the (m+2)×(m+2) matrix obtained from B by bordering it with a top row (0,1,...,1) and left column (0,1,...,1)T. This is known as the Cayley-Menger determinant formula.8 7A set {a0, a1,...,an}( Rnis geometrically independent if for each vector (t0, t1,...,tn)∈Rn+1, the equations P n i=0 ti= 0 and P n i=0 tiai= (0, . . . , 0), hold only if t0=t1=···=tn= 0. Note that {a0, a1,...,an} is geometrically independent if and only if the vectors a1−a0,...,an−a0are linearly independent. 8For references on this and other formulas for computing simplicial volumes look at Gritzman and Klee (1994). 6.A. Appendix 107 -Definition of Parallelepiped. Let {u1, u2,...,um}be mlinearly independent vectors in Rn, with m≤n. The m-parallelepiped Pmspanned by u1, u2,...,umis the set of all x∈Rnsuch that x=Pm i=1 tiui, where, for each i∈ {1,...,m},0≤ti≤1. Let Abe the matrix whose rows are the vectors u1, u2,...,um. The m-dimensional volume of Pmis |det ATA|1/2. Proof of the statements relative to Proposition 6.3 (footnote 6). We divide this proof in three parts. First, we show that the procedure defined in the proof of Proposition 6.3 provides a dissection of I(v); this dissection is mainly formed by (n−1)- parallelepipeds. Second, we show that for each ε > 0, there is δ > 0such that the sum of the the volumes of the parallelepipeds in the induced dissection of Cis ε-close to Vol(C). Finally, we show a procedure to “put” an elemental core inside a parallelepiped. In order to make this proof more readable we assume, without loss of generality, that for each i∈N,mi= 0. The procedure described in the proof of Proposition 6.3 is a “quasi-dissection in parallelepipeds” of I(v): Let x∈I(v). There is r= (r1,...,rn−1)∈Rn−1such that, (i) for each i∈N,ri∈ {0,...,q} and (ii) for each i∈N,i6=nwe have riδ≤xi≤(ri+ 1)δ; note that the second inequality is equivalent to Pj6=ixj≥v(N)−(ri+ 1)δ. Next, we find the parallelepiped corresponding with this vector r(note that the same point xcan lie more than one parallelepiped at the same time). Let Pbe the parallelepiped spanned by the vectors {u1,...,un−1}, where ui=eiδ−enδ(ei denotes the ith vector of the canonical base in Rn). Now, since the vectors {u1,...,un−1}are independent, they generate a parallelepiped. Now, for each x∈I(v), and an associated vector r∈Rn−1,xlies in the parallelepiped Pr:= P+(r1δ, r2δ,...,rn−1δ, v(N)−Pi6=nriδ). Note that we have also shown that all the parallelepipeds are equal (changing the translation we just move Ponto a different position). But now, as it can be seen in Figure 6.2, a small amount of these parallelepipeds is not completely included in I(v); those for whom the restriction xn≥0is not redundant. We show in the next step that this is not a problem. The induced “quasi-dissection in parallelepipeds” in Ccan be arbitrarily tight: Next, we show that, for each 0< ε < 1, we can find δ > 0such that the sum of the volumes of the cores of the games in Gδwhich are not parallelepiped is, at most, εVol(C). The situation we have is similar to that in Figure 6.2, most of the cores of games in Gδare strictly contained in C. Let v′∈ Gδbe such that C′is nonempty. There is a parallelepiped P′such that C′=P′∩C. We want to show that, in most of the cases, we have C′=P′∩C=P′and C′ is a parallelepiped (dark shaded zone in the third picture of Figure 6.2). Let dδbe the maximum euclidean distance between any two points in P(since all the parallelepipeds are translations of each other, dδis common to all of them). By definition of P,limδ→0dδ= 0.9 9The maximum dδis achieved when x= (0,...,0) and y= P n−1 i=1 ui= (δ, . . . , δ, −(n−1)δ). The distance between these two points is (n(n−1))1/2δ. Hence, it goes to 0as δdoes. 108 Chapter 6. A Characterization of the Core-Center Each face of Cis determined by a restriction RS v, where ∅(S(N. Hence, the maximum number of faces of the core of a game with nplayers is fn= 2n−2. Let F(C)denote the set of all faces of C. Let y∈Cbe such that the distance from yto each face in F(C)is more than dδ. Then, y is inside a core C′such that C′=P′∩C=P′for some parallelepiped P′,i.e.,C′is itself a parallelepiped. Hence, we can find an upper bound for the volume of the points y∈Cwhich are not in a parallelepiped. Let F∈F(C). Let B(F, δ) := {x∈Rn:d(x, F)< dδ}. Now, limδ→0B(F, δ) = Fand, since Flies in an (n−2)-dimensional space, Voln−1(F) = 0. Now, since for each F∈F(C),B(F, δ)is bounded, we have that Vol(B(F, δ)) goes to 0as δdoes. Hence, for each 0< ε < 1, we can find δ > 0such that for each F∈F(C),Vol(B(F, δ)) <ε fn. Once one such δhas been chosen, if y∈Cbut it is not in a parallelepiped, then it must lie in B(F, δ)for some face Fof C. Hence, the total volume of these points is bounded from above by PF∈F(C)Vol(B(F, δ)<PF∈F(C)ε fn=fnε fn=ε. Cutting a parallelepiped to obtain an elemental core: Let vrbe the game such that its core is the parallelepiped Prdefined by P+ (r1δ, r2δ,...,rn−1δ, v(N)−Pi6=nriδ). Let χn,k(vr)be the cut where k=v(N)−(1 + Pi6=nri)δ. The game vrhas an elemental core ∆ whose vertices are the following nextreme points: for each i∈N, pi= (r1δ, r2δ,...,rn−1δ, v(N)−X i6=n riδ) + eiδ−enδ. The constant αused in the proof can be calculated as the quotient of the (n−1)-dimensional volumes of the simplex ∆and the parallelepiped Pcontaining it. Making some computations with the formulas we introduced when we defined simplices and parallelepipeds we have Vol(∆) = √n (n−1)!δn−1and Vol(P) = √nδn−1. Hence, α=Vol(S) Vol(P)=1 (n−1)! . Once nis fixed, αkeeps constant.  Bibliography 109 Bibliography Anbarci, N. and J. Bigelow (1994): “The Area Monotonic Solution to the Cooperative Bargaining Problem,” Mathematical Social Sciences, 28, 133–142. (Quoted in pp. 88) Calvo, E. and H. Peters (2000): “Dynamics and Axiomatics of the Equal Area Bargaining Solution,” International Journal of Game Theory, 29, 81–92. (Quoted in pp. 88) Gillies, D. B. (1953): “Some Theorems on n-Person Games,” Ph.D. thesis, Princeton. (Quoted in pp. 90) González-Díaz, J. and E. Sánchez-Rodríguez (2003): “From Set-Valued Solutions to Single- Valued Solutions: The Centroid and the Core-Center,” Reports in Statistics and Operations Research 03-09, University of Santiago de Compostela. (Quoted in pp. 88) Gritzman, P. and V. Klee (1994): “On the Complexity of Some Basic Problems in Computational Convexity: Volume and Mixed volumes,” in Polytopes: Abstract, convex and computational, ed. by T. Bisztriczky, P. McMullen, R. Schneider, and A. Weiss, Kluwer, Boston MA, 373–466. (Quoted in pp. 106) Maschler, M., B. Peleg, and L. S. Shapley (1979): “Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts,” Mathematics of Operations Research, 4, 303–338. (Quoted in pp. 90, 91) Rudin, W. (1966): Real and Complex Analysis, McGraw-Hill. (Quoted in pp. 97) Schmeidler, D. (1972): “Cores of Exact Games,” Journal of Mathematical Analysis and Applications, 40, 214–225. (Quoted in pp. 90) 116 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection Corollary 7.1. Let (N, v)∈G2be such that v(N)> v({1}) + v({2}). Then, Sh(N, v) = Θ(I(N, v)) = µ(N, v). Moreover, they coincide with the barycenter (midpoint) of the segment joining the two points v({1}), v(N)−v({1})and v(N)−v({2}), v({2}). Proof. Immediate from Lemma 7.1. Let Dvbe the set of dummy players of (N, v)and dvits cardinality. Recall that, if dv=n, then the game is additive. Lemma 7.2. Let (N, v)∈Gn. Then, the following statements are true: (i) dv6=n−1. (ii) Let (N, v)∈BGnand dv< n. Then, xN∈C(N, v)if and only if (i) for each i∈Dv, xi= v({i})and (ii) xN\Dv∈C(N\Dv, vN\Dv). (iii) Let (N, v)∈CGnand dv< n. Then, (N\Dv, vN\Dv)∈CGn−dv,i.e., it is a convex game with full dimensional core. Proof. a) Suppose that dv≥n−1. Then, there is i∈Nsuch that N\{i} ⊆ Dv. Suppose now that i /∈Dv. Let Sbe a minimal coalition among those such that i /∈Sand v(S∪{i})−v(S)6=v({i}). Clearly, S6=∅. Let j∈S, then, v((S∪{i})\{j}) = v((S∪{i})\{j})−v(S\{j}) + v(S\{j}) S\{j}(S =v({i}) + X l∈S\{j} v({l}). Now, v({j}) = v(S∪ {i})−v((S∪ {i})\{j}) = v(S∪ {i})−v({i})−Pl∈S\{j}v({l}). Hence, since Pl∈Sv({l}) = v(S), we have v(S∪{i})−v(S) = v({i}), contradicting the definition of S. Hence, i∈Dvand dv=n. b) Follows from the equality v(N) = v(N\Dv) + Pj∈Dvv({j}). c) Each subgame of a convex game is a convex game. Hence, (N\Dv, vN\Dv)is a convex game with no dummy players. Let (N, w)be a convex game. Since (i) for each i∈N, there is a marginal vector such that mσ i=v({i})and (ii) C(N, w)is the convex hull of the marginal vectors, C(N, w)has at least one point in each face of I(N, w). Now, if (N, w)has no dummy players, then, for each i∈N, there is a marginal vector such that mσ′ i> v({i}). The full dimensionality of the core of each convex game with no dummy players follows from the combination of the two previous observations. Corollary 7.2. Let (N, v)be a convex game with n−2dummy players. Then, Sh(N, v) = µ(N, v). Proof. It follows from Lemma 7.2 and Corollary 7.1. 7.4. The Utopia Games 117 Remark. Lemma 7.2 shows that coalitions involving dummy players are not needed in order to compute the core-center. Then, µi(N, v) = (v({i})i∈Dv µi(N\Dv, vN\Dv)i /∈Dv. Note that the Shapley value also satisfies that for each i∈Dv,Shi(N, v) = v({i}). Because of the previous Remark, we do not consider games with dummy players anymore. The main results in the next Section hold for convex games without dummy players or, equivalently, convex games with full dimensional core. 7.4 The Dynamic Process between Coalitions. The Utopia Games The class of exact games (Schmeidler, 1972) is a subclass of BGn. The main property of the games in this subclass is that, given two exact games, if they have the same core, then they are the same game, i.e., no two distinct exact games have the same core. Hence, when working with exact games, the core uses all the information of the underlying game. Since the class of convex games is contained in the class of exact games, the last observation is also relevant to our framework: no two distinct convex games have the same core. This property reinforces the motivations for the core-center within the class of convex games. Since the core uses all the information of the game, why not to select the allocation rule that summarizes all the information of the core? The results in this Section are for games with full dimensional core. Hence, when no confusion arises, Vol(P)denotes the (n−1)-dimensional volume of polytope P. Let Nbe a set of players and suppose that the game (N, v)is gradually defined. First, the players agree on the amount v(N)that is to be divided. Then, they agree on the individual values. Hence, only v(N)and, for each i∈N, the value v({i})are determined. To formalize this step we define the game (N, v∅), where the players do not gain anything by forming coalitions different from N, v∅(S) = (Pl∈Sv({l})S6=N v(N)S=N. At this point, a fair allocation rule should provide some payoff in the imputation set, and without any more information, why not choose the center of the imputation set? Suppose now that coalitions enter in the game and, for instance, players 1 and 2 announce that, together, they can get v({1,2}). At this point, the set of “stable” points is C1,2={x∈ I(N, v) : x1+x2≥v({1,2})}. Clearly, C1,2is a subset of the imputation set and, the larger is the difference v({1,2})−(v({1})+v({2})), the smaller is C1,2. Next, we want measure how big is this set of “stable” points, which is contained in I(N, v). One natural way is through the difference of the volumes, i.e.,Vol(I(N, v)) −Vol(C1,2)(note that allocations in I(N, v)\C1,2are the good 118 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection ones for coalition N\{1,2}). Now, we can repeat the argument with some other coalition different from {1,2}; we can compare the different coalitions and “measure” their differences. Next, we introduce a new class of games: the utopia games. Roughly speaking, these games are such that the core of the utopia game for coalition Sis precisely the set of allocations that are not “stable” after coalition N\Sannounces v(N\S). Formally, let (N, v)be a convex game, and let T∈2N\∅. Let H∈2T\∅. Then, we define the game (N, vH T)∈Gnas follows:5 vH T(S) =    v((T∩S)∪(N\T)) −v(N\T) + v(S\(T∩S)) H⊆S v((T∩S)∪(N\T)) −v(N\T) + P l∈S\(T∩S) v({l})otherwise. Despite of the apparent complexity of this definition, the specific utopia games we look at in this Chapter allow for more transparent expressions. It is easy to check that vH T(∅) = 0, vH T(N) = v(N), if T∩S=∅,vH T(S) = Pl∈Sv({l}). Next, we interpret the game (N, vH T). For each coalition S6=T, the value vH T(S)is the sum of two quantities. First, the marginal contribution of the players in Sthat are in Tto N\T. Second, the contribution of players in Sthat are not in T. Hence, what a coalition S⊆Tobtains in the game vH Tis its marginal contribution to N\T,i.e.,vH T(S) = v(S∪(N\T)) −v(N\T); note that, if S=T,vH T(T) = v(N)−v(N\T). Take now S⊆Nsuch that ∅(T∩S(S. The contribution of the players in Sthat are not in Tdepends on the coalition H. Fixed H, if H⊆S, the contribution of players in S\(T∩S) is the utility that they can guarantee themselves by joining together, i.e.,v(S\(T∩S)). On the other hand, if H*S, that contribution is computed by Pl∈S\(T∩S)v({l}). Roughly speaking, players in Hcan be thought as the ones who have the key to allow for cooperation. The main idea underlying the games vH Tis that the players in Tare the ones who have the power in the game, but always respecting the minimum rights of players in N\T. In addition, the game also establishes, via coalition H, a hierarchical structure among players in T. As next proposition reads, these games are convex. Proposition 7.1. Let (N, v)∈CGn,T∈2N\∅, and H∈2T\∅. Then, (N, vH T)∈CGn. Proof. See the Appendix. Next, we study utopia games defined by coalitions with, at most, two players. For these special utopia games, the intuitions highlighted in the discussion above should become clearer. 5We do not use the subgames (S, vS)anymore. Hence, no confusion can arise because of the notation for utopia games. 7.4. The Utopia Games 119 Let i∈Nand T={i}; in this case H=T. Henceforth, we denote, for each i∈N, the game (N, v{i} {i})by (N, vi). The game (N, vi)is the utopia game for player i, shortly, i-utopia game: For each S⊆N, vi(S) = (v(N)−v(N\{i}) + v(S\{i})i∈S Pl∈Sv({l})i /∈S. In this game player ihas the key for cooperation. The other players by themselves can only get the sum of their individual values. We describe now the games vH Twhere Tis a 2-player coalition, T={i, j} ⊆ Nwith i6=j. To this extent, we define two games: (N, v{i} {i,j})and (N, v{j} {i,j}),6 that we denote by (N, v(i,j))and (N, v(j,i)), respectively. The former, that we call (i, j)-utopia game is good for both players 1and 2, but excellent for player 1: v(i,j)(S) = (v((T∩S)∪(N\T)) −v(N\T) + v(S\(T∩S)) i∈S v((T∩S)∪(N\T)) −v(N\T) + Pl∈S\(T∩S)v({l})i /∈S =           v(N)−v(N\{i, j}) + v(S\{i, j})i∈S, j ∈S v(N\{j})−v(N\{i, j}) + v(S\{i})i∈S, j /∈S v(N\{i})−v(N\{i, j}) + Pl∈S\{j}v({l})i /∈S, j ∈S Pl∈Sv{l})i /∈S, j /∈S. Analogously, by interchanging the role of iand j, we can define the (j, i)-utopia game. The next concept leads to a classification of the games in CGn. This classification looks at the size of the smaller coalition, say S, such that v(S)>Pi∈Sv({i}),i.e., joining together to form S is profitable for the players in S. Formally, let (N, v)∈CGn,n > 2. Let t∈ {1,...,n−1}. Then, (N, v)∈CGn tif (i) for each S⊆Nwith |S| ≤ t,v(S) = Pi∈Sv({i})and (ii) there is a coalition S,|S|=t+ 1, such that v(S)>Pi∈Sv({i}). On the other hand, if v(N) = Pi∈Nv({i}), then (N, v)∈CGn n. Let (N, v)∈CGn, then there is t∈ {1,...,n}such that (N, v)∈CGn t.Note that I(N, v) = C(N, v)if and only if (N, v)∈CGn t, with t≥n−1, and then, by Lemma 7.1 both Shapley value and core-center coincide with the barycenter of the imputation set. Let (N, v)∈CGn t, with t < n, then, (i) the core restrictions originated by the m-player coalitions, 1< m ≤t, are redundant and (ii) there is at least one coalition with more than tplayers imposing a non-redundant restriction on C(N, v). Lemma 7.3. Let (N, v)∈CGn n−2, n > 2.Then: 6We could also define the game (N, v{i,j} {i,j}), where H=T. But, since we do not use it in our results, we skip its definition. 120 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection 1 2 4 3 Figure 7.1: Core of a game in CG4 2 1 2 4 3 1-utopia core 2-utopia core Figure 7.2: Cores of two utopia games (i) For each i∈N, C(N, vi) = I(N, vi)and Vol(C(N, vi)) Vol(I(N, v)) = v(N\{i})−Pl∈N\{i}v({l}) v(N)−Pl∈Nv({l})!n−1 . (ii) Let i, j ∈N, i 6=j. Then, C(N, (vi)j) = mσ(N, v), where σ∈Π(N)is such that σ(i) = n and σ(j) = n−1. (iii) I(N, v) = Si∈NC(N, vi)∪C(N, v). (iv) Vol(I(N, v)) = Pi∈NVol(C(N, vi)) + Vol(C(N, v)). Proof. See the Appendix. Let (N, v)∈CGn n−2. Let p:= Vol(C(N, v)),p0= Vol(C(N, v∅)), and, for each i∈N, pi= Vol(C(N, vi). Let the fair game associated with (N, v),(N, v∗), be defined as follows: v∗(S) = 1 pp0v∅(S)−X i∈N pivi(S). Theorem 7.1. Let (N, v)∈CGn n−2,n > 2. Then, µ(N, v) = Sh(N, v∗). Proof. The core-center satisfies w-additivity and, by Lemma 7.3, the imputation set can be dissected into n+ 1 polytopes, the core of (N, v)and the cores of the utopia games. Hence, µ(N, v∅) = p p0µ(N, v) + Pi∈N pi p0µ(N, vi). By Lemma 7.1, µ(N, v∅) = Sh(N, v∅),and, for each 7.4. The Utopia Games 121 i∈N,µ(N, vi) = Sh(N, vi). Hence, µ(N, v) = p0 pµ(N, v∅)−X i∈N pi p0 µ(N, vi)=p0 pSh(N, v∅)−X i∈N pi pSh(N, vi) =1 pp0Sh(N, v∅)−X i∈N piSh(N, vi)= Sh(N, v∗), where the last equality holds by the additivity of the Shapley value. Remark. This proof has the following feature: we start with the core-center of a game and, in two steps, using both the w-additivity of the core-center and the additivity of the Shapley value, we end up with the Shapley value of the fair game. Corollary 7.3. Let (N, v)∈CG3. Then, µ(N, v) = Sh(N, v∗). Proof. Immediate from Theorem 7.1. Remark. If (N, v)∈CG3, the game (N, v∗)summarizes all the information of the core. The core of the fair game coincides with its imputation set and contains C(N, v). Following the definition of (N, v∗)we have, for each i∈N,v∗({i}) = v({i})−pi pv(N)−v(N\{i}) + v({i}). Hence, µ(N, v) = v∗({i}) + 1 nv(N)−X k∈N v∗({k}). Example 7.1. Let (N, v)∈G3be such that, for each i∈N,v({i}) = 0;v({1,2}) = 2, v({1,3}) = v({2,3}) = 5,and v(N) = 10.Then, S v∅v1v2v3v{1,2}v{1,3}v{2,3}v∗ {1}0 5 0 0 5 2 0 −2.7174 {2}0 0 5 0 5 0 2 −2.7174 {3}0 0 0 8 0 5 5 −0.6957 {1,2}0 5 5 0 10 2 2 −5.4348 {1,3}0 5 0 8 5 10 5 −3.4130 {2,3}0 0 5 8 5 5 10 −3.4130 N10 10 10 10 10 10 10 10 and, Sh(N, v) = (2.8333,2.8333,4.3333) µ(N, v) = (2.6594,2.6594,4.6812). Let r:= p/p0and, for each i∈N,ri:= pi/p0. In this example we have r1=r2= 1/4,r3= 1/25 and r= 1 −(r1+r2+r3) = 23/50. Hence, players 1 and 2 are less powerful than player 3. Note 122 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection that C(N, v(1,2)) = C(N, v(2,1)) = (5,5,0). Moreover, x∈C(N, v{1,2})if and only if v({1,3})−v(3) ≤x1≤v(N)−v({2,3}), v({2,3})−v(3) ≤x2≤v(N)−v({1,3}),and x3=v({3}). 1 2 3 C(N, v) I(N, v) Figure 7.3: Core of a game in CG3 1 2 3 I(N, v) C(N, v) C(N, v∗) = I(N, v∗) Figure 7.4: The core of the fair game Since Pri= 1 and, for each i∈N,0≤ri≤1, the ratios rihave the following interpretation. They determine a probability distribution over the cores of the utopia games and hence, over the imputation set; ris the probability that an allocation in I(N, v)belongs to C(N, v)and, for each i∈N,riis the probability that an allocation in I(N, v)belongs to C(N, vi). Hence, the greater the core of the i-utopia game is, the worse is i’s situation in the game. Roughly speaking, Figures 7.3 and 7.4 show that for (N, v), the “big” utopia cores are those of the utopia games of players 1 and 2. Hence, in the core of the fair game, the “bad” section that has been added for player 3 (with respect to the core of the original game) is smaller than those for players 1 and 2. We turn now to study games in CGn n−3. We denote the game (v(i,j))jby v(i,j)j. Lemma 7.4. Let (N, v)∈CGn n−3,n > 3, and let i∈N. Then, (i) (N, vi)∈CGn n−t,t < 3. (ii) For each i, j ∈N,i6=j,C(N, (vi)j) = I(N, (vi)j). (iii) µ(N, vi) = Sh(N, (vi)∗). Proof. (i) It suffices to show that, for each S⊆Nsuch that |S| ≤ n−2, we have vi(S) = 7.4. The Utopia Games 123 1 2 4 3 1-utopia core 1 2 4 3 1-utopia core 2-utopia core (1,2)-utopia core  1 2 4 3 1-utopia core 2-utopia core 1 2 4 3 1-utopia core 2-utopia core (1,2)-utopia core (1,2)2-utopia core  o Figure 7.5: Example of a game in CG4 3with some of its utopia games 124 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection Pk∈Svi({k}). Now, for each S⊆N, vi(S) =      v(N)−v(N\{i}) + v(S\{i})i∈S, |S| ≥ n−2 v(N)−v(N\{i}) + Pl∈S\{i}v({l})i∈S, |S|< n −2 Pl∈Sv({l})i /∈S. Hence, if |S|< n −2,the result is immediate; if |S|=n−2, since |S\{i}| =n−3we have v(S\{i}) = Pl∈S\{i}v({l}). Hence, for each S⊆Nsuch that |S| ≤ n−2,vi(S) = Pk∈Svi({k}). (ii) and (iii) follow from Lemma 7.3 and Theorem 7.1. Lemma 7.5. Let (N, v)∈CGn n−3,n > 3. Let i, j ∈N,i6=jand let (N, v(i,j))be the (i, j)-utopia game. Then, if C(N, v(i,j))is full dimensional we have (i) Sh(N, v(i,j)) = µ(N, v(i,j)). (ii) Vol(C(N, v(i,j))) = =√n (n−2)!v(N\{i, j})−X l∈N\{i,j} v({l})n−2v(N)−v(N\{i}) + v(N\{i, j})−v(N\{j}) Proof. See the Appendix. Lemma 7.6. Let (N, v)∈CGn n−3,n > 3. Let i, j ∈N,i6=jand let (N, v(i,j))be the (i, j)-utopia game. Then, (i) For each S⊆N,v(i,j)j(S) = (vj)i(S)and C(N, v(i,j)j) = C(N, (vj)i). (ii) µ(N, v(i,j)j) = Sh(N, v(i,j)j). (iii) We have the following dissection of the set of imputations: I(N, v) = C(N, v∅) = [ i∈N C(N, vi)∪[ i<j C(N, v(i,j))∪C(N, v(i,j)j)∪C(N, v). Proof. See the Appendix. Let (N, v)∈CGn n−3. As before, let p:= Vol(C(N, v)),p0= Vol(C(N, v∅)), and, for each i∈N,pi= Vol(C(N, vi). Moreover, for each pair i, j ∈N, let p(i,j)= Vol(C(N, v(i,j))) and p(i,j)j= Vol(C(N, v(i,j)j)). Let the fair game associated with (N, v),(N, v∗), be defined as follows: v∗(S) = 1 pp0v∅(S)−X i∈N pivi(S)−X i6=j 1 2p(i,j)v(i,j)(S) + p(i,j)jv(i,j)j(S). Since for each (N, v)∈CGn n−2, the coefficients p(i,j)and p(i,j)jare 0, this definition of fair game is consistent with the old one. 7.4. The Utopia Games 125 Let r(i,j)=p(i,j)/p0and r(i,j)j=p(i,j)j/p0. Then, r(i,j)= √n (n−2)! v(N\{i,j})− P l∈N\{i,j}v({l})n−2v(N)−v(N\{i})+v(N\{i,j})−v(N\{j}) √n (n−1)! v(N)− P l∈Nv({l})n−1 = (n−1) v(N\{i,j})− P l∈N\{i,j}v({l}) v(N)− P l∈Nv({l})n−1v(N)−v(N\{i})+v(N\{i,j})−v(N\{j}) v(N)− P l∈Nv({l}), and, r(i,j)j= v(N\{i, j})−Pl∈N\{i,j}v({l}) v(N)−Pl∈Nv({l})!n−1 . Again, the numbers r(i,j)and r(i,j)jcan be interpreted as the probabilities that an allocation in C(N, v(i,j))or C(N, v(i,j)j), respectively, is chosen. According to our interpretation of the utopia games, if an allocation in C(N, v(i,j))is chosen, the coalition {i, j}would receive an “utopic” payoff, i.e., allocations in C(N, v(i,j))are the best for coalition {i, j}within I(N, v). Note that r(i,j)=r(j,i)and r(i,j)j=r(j,i)i. This observation is crucial to understand the following result. Lemma 7.7. Let (N, v)∈CGn n−3,n > 3. Let i, j ∈N,i6=jand let (N, v(i,j))be the (i, j)-utopia game. Then, r(i,j)µ(N, v(i,j)) + r(i,j)jµ(N, (v(i,j)){j}) = r(j,i)µ(N, v(j,i)) + r(j,i)iµ(N, (v(j,i)){i}). Proof. This result is a consequence of the following equality: C(N, v(i,j))∪C(N, v(i,j)j) = C(N, v(j,i))∪C(N, v(j,i)i). Lemma 7.7 shows that, given any two players, there is an important symmetry between the two corresponding 2-player utopia games. Next, we state our main Theorem. It provides a direct relation between the core-center and the Shapley value of the fair game. Theorem 7.2. Let (N, v)∈CGn n−3,n > 3. Then, µ(N, v) = Sh(N, v∗). Proof. Since C(N, v∅) = [ i∈N C(N, vi)∪[ i<j C(N, v(i,j))∪C(N, v(i,j)j)∪C(N, v), we have µ(N, v∅) = P i∈N pi p0µ(N, vi) + P i<j p(i,j) p0µ(N, v(i,j)) + p(i,j)j p0µ(N, v(i,j)j)+p p0µ(N, v) =P i∈N pi p0µ(N, vi) + P i6=jp(i,j) 2p0µ(N, v(i,j)) + p(i,j)j 2p0µ(N, v(i,j)j)+p p0µ(N, v), 132 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection Again, since (N, v)∈CGn n−3, the latter expression can be reduced to mσ k(N, v(i,j)) =            v(N\{j})−v(N\{i, j})k=i v(N)−v(N\{j})k=j v(N\{i, j})−Pl∈N\{i,j,k}v({l})σ(k) = n v({k})σ(k)< n. Now, |Π4a(N)|=(n−1)! 2(n−2) with, at most, n−2different marginal vectors. Let Π4b(N) = {σ∈Π(N) : σ(j) = nand σ(i)< n −1}. Let σ∈Π4b(N). Again, the following expressions for the marginal vectors can be derived: mσ k(N, v(i,j)) =            v(N\{j})−v(N\{i, j})k=i v(N)−v(N\{j})k=j v(N\{i, j})−Pl∈N\{i,j,k}v({l})σ(k) = n−1 v({k})σ(k)< n −1. Now, |Π4b(N)|= (n−2)!(n−2) with, at most, n−2different marginal vectors. Let Π4(N) = Π4a(N)∪Π4b(N). Then, |Π4(N)|=|Π4a(N)|+|Π4b(N)|=n2−n−2 2(n−2)!. Moreover, it is easy to check that the permutations in Π4(N)define, at most, n−2different marginal points. Finally, we have that the permutations in Π(N)define, at most, 2n−2different points. For ease of exposition we assume that these points are different to each other.8 Computation of the Shapley value: Shi(N, v(i,j)) = 1 n!X σ∈Π(N) mσ i(N, v(i,j)) = 1 n! 4 X l=1 X σ∈Πl(N) mσ i(N, v(i,j)). Player i Shi(N, v(i,j)) = (n−1)! n!v(N)−v(N\{i}) + v(N\{i, j})−Xl∈N\{i,j}v({l}) +(n−1)! 2n!(n−2)v(N)−v(N\{i}) +(n−2)! n!v(N\{j})−Xl6=i,j v({l}) +n2−n−2 2n!(n−2)!v(N\{j})−v(N\{i, j}). 8This assumption does not affect the algebra used in this proof, but it helps to get a better understanding of the geometric situation underlying the result. 7.A. Appendix 133 Simplifying we have, Shi(N, v(i,j)) = v(N) + v(N\{j})−v(N\{i}) 2−1 n−1(n−3) 2v(N\{i, j}) + X l∈N\{i,j} v({l}). Player j: Shj(N, v(i,j)) = v(N\{i})−v(N\{i, j}) + v(N)−v(N\{j}) 2. Player k6=i, j: Shk(N, v(i,j)) = (n−1)! n!v({k} +(n−1)! 2n!(n−3)v({k}) + (n−1)! 2n!v(N\{i, j})−Xl∈N\{i,j,k}v({l} +(n−2)! n!v({k}) +n2−n−2 2n!(n−3)!(n−3)v({k}) + v(N\{i, j})−Xl∈N\{i,j,k}v({l}. Simplifying we have, Shk(N, v(i,j)) = v({k}+1 n−1v(N\{i, j})−X l∈N\{i,j} v({l}). Computation of the core-center: First, we describe the geometry of C(N, v(i,j))(Figure 7.6 illustrates the geometry of the core in an example with four players). Note that, for player j, 1 2 4 3 Figure 7.6: The core of the game (N, v(i,j)) 134 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection mσ j(N, v(i,j)) = (v(N\{i})−v(N\{i, j})σ∈Π1(N)∪Π2(N) v(N)−v(N\{j})σ∈Π3(N)∪Π4(N). Hence, the marginal vectors lie either in the hyperplane xj=v(N)−v(N\{j})or in the hyperplane xj=v(N\{i})−v(N\{i, j})and there are, at most, n−1different marginal vectors in each one of the two hyperplanes. Now, if there is a pair of coincident points in one of the two hyperplanes, then there is also a pair of coincident points in the other one; inducing a degeneracy in the core. Hence, since C(N, v(i,j))is full dimensional, these n−1points in each hyperplane have to be different. Let k∈N\{i, j}and σ∈Π(N). We have already shown that either mσ k(N, v(i,j)) = v({k}) or mσ k(N, v(i,j)) = v(N\{i, j})−Pl∈N\{i,j,k}v({l}). Now, let σ∈Π3(N)∪Π4(N). Then, mσ(N, v(i,j))lies in the hyperplane v(N)−v(N\{j}). Moreover, there are σ1, σ2∈Π3(N)∪Π4(N) such that (i) mσ1 k(N, v(i,j)) = v({k})and (ii) mσ2 k(N, v(i,j)) = v(N\{i, j})−Pl∈N\{i,j,k}v({l}). An analogous observation is true for the hyperplane xj=v(N\{i})−v(N\{i, j})and a pair of permutations σ′ 1, σ′ 2∈Π1(N)∪Π2(N). Next, we take the n−1marginal vectors in the hyperplane xj=v(N)−v(N\{j})and we show that they span an (n−2)-simplex. The same can be done for the n−1points in xj=v(N\{i})−v(N\{i, j}). Let k∈N\{i, j})and let ukbe the marginal vector lying on the hyperplane xj=v(N)− v(N\{j})in which player kis better off. The coordinates of each ukare the following: (uk)l=           v(N\{j})−v(N\{i, j})l=i v(N)−v(N\{j})l=j v(N\{i, j})−Pl∈N\{i,j,k}v({l})l=k. v({l})l6=i, j, k. Besides, let u0be the remaining marginal vector in xj=v(N)−v(N\{j}): (u0)l=     v(N\{j})−Pl∈N\{i,j}v({l})l=i v(N)−v(N\{j})l=j v({l})l6=i, j. Now, since the vectors uk−u0are linearly independent, the n−1marginal vectors in xj= v(N)−v(N\{j})define a geometrically independent set in Rn. Hence, they span an (n−2)- simplex. Now, for the hyperplane xj=v(N\{i})−v(N\{i, j})we define the same n−1points but with the following differences: (i) the j-th coordinate is v(N\{i})−v(N\{i, j})and (ii) the ith coordinate is changed to recover efficiency (iii) the remaining coordinates remain unchanged. Now, since (N, v(i,j))is convex, C(N, v(i,j)) = co{mσ(N, v) : σ∈Π(N)}. Hence, there is an (n−2)-simplex ∆n−2such that, for each t∈R, either the intersection of C(N, v(i,j))with the 7.A. Appendix 135 hyperplane xj=tis empty or it is a translation of ∆n−2. Hence, µj(N, v(i,j)) = v(N\{i})−v(N\{i, j}) + v(N)−v(N\{j}) 2, and it coincides with the corresponding coordinate of the Shapley value. Now, because of the symmetries in C(N, v(i,j)), to compute the core-center it suffices to compute the barycenter of the simplex generated by the n−1points on the hyperplane xj= µj(N, v(i,j)). Hence, for each k∈N\{i, j}, µk(N, v(i,j)) = v({k}) + 1 n−1v(N\{i, j})−X l∈N\{i,j} v({l})= Shk(N, v(i,j)). Finally, because of the efficiency property of both the Shapley value and the core-center, we have Shi(N, v(i,j)) = µi(N, v(i,j)). (ii) Immediate from the description of C(N, v(i,j))we have made above. 7.A.4 Proof of Lemma 7.6 Proof. (i) Since vj(S) = (v(N)−v(N\{j}) + v(S\{j})if j∈S Pl∈Sv({l})if j /∈S and v(i,j)(S) =            v(N)−v(N\{i, j}) + v(S\{i, j})i∈S, j ∈S v(N\{j})−v(N\{i, j}) + v(S\{i})i∈S, j /∈S v(N\{i})−v(N\{i, j}) + Pl∈S\{j}v({l})i /∈S, j ∈S Pl∈Sv({l})i /∈S, j /∈S. Then, (v(i,j))j(S) = (v{i,j}(N)−v{i,j}(N\{j}) + v{i,j}(S\{j})j∈S Pl∈Sv{i,j}({l})j /∈S =           v(N)−v(N\{i, j}) + v(S\{i, j})i∈S, j ∈S v(N)−v(N\{j}) + Pl∈S\{j}v({l})i /∈S, j ∈S v(N\{j})−v(N\{i, j}) + Pl∈S\{j,i}v({l})i∈S, j /∈S Pl∈Sv({l})i /∈S, j /∈S. 136 Chapter 7. The Core-Center and the Shapley Value: A Direct Connection Finally, (vj)i)(S) = (vj(N)−vj(N\{i}) + vj(S\{i})i∈S Pl∈Svj({l})i /∈S. =           v(N)−v(N\{i, j}) + v(S\{i, j})i∈S, j ∈S v(N\{j})−v(N\{i, j}) + Pl∈S\{i}v({l})i∈S, j 6∈ S v(N)−v(N\{j}) + Pl∈S\{j}v({l})i /∈S, j ∈S Pl∈Sv({l})i /∈S, j 6∈ S. (ii) It follows from the combination of (i) and Lemma 7.4. The proofs of (iii) follow similar lines to the proofs of their counterparts in Lemma 7.3. Bibliography 137 Bibliography Gillies, D. B. (1953): “Some Theorems on n-Person Games,” Ph.D. thesis, Princeton. (Quoted in pp. 113) González-Díaz, J. and E. Sánchez-Rodríguez (2003): “From Set-Valued Solutions to Single- Valued Solutions: The Centroid and the Core-Center,” Reports in Statistics and Operations Research 03-09, University of Santiago de Compostela. (Quoted in pp. 112) Gritzman, P. and V. Klee (1994): “On the Complexity of Some Basic Problems in Computational Convexity: Volume and Mixed volumes,” in Polytopes: Abstract, convex and computational, ed. by T. Bisztriczky, P. McMullen, R. Schneider, and A. Weiss, Kluwer, Boston MA, 373–466. (Quoted in pp. 115) Schmeidler, D. (1972): “Cores of Exact Games I,” Journal of Mathematical Analysis and Applications, 40, 214–225. (Quoted in pp. 117) Shapley, L. S. (1953): “A Value for n-Person Games,” in Contributions to the theory of games II, ed. by H. Kuhn and A. Tucker, Princeton: Princeton University Press, vol. 28 of Annals of Mathematics Studies.(Quoted in pp. 112) Chapter 8 A Geometric Characterization of the Compromise Value Contents 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 8.2 The τ∗Value .................................140 8.3 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 8.4 Proof of the Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . 146 8.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 Bibliography ...................................159 139 140 Chapter 8. A Geometric Characterization of the Compromise Value 8.1 Introduction Most game-theoretic solution concepts that have been proposed in the literature are defined on the basis of or characterized by properties. These properties are usually formulated in terms of individual payoffs and reflect notions like monotonicity and rationality. For some values, there exist additional characterizations in terms of geometry. The best-known example is the Shapley value (Shapley, 1953), which is the barycenter of the vectors of marginal contributions. For some classes of games, there exist nice geometric expressions for the compromise or τ value (Tijs, 1981). In particular, the compromise value is the barycenter of the extreme points of the core cover in big boss games (Muto et al., 1988) and 1-convex games (Driessen, 1988). In this Chapter, we extend the APROP rule for bankruptcy problems (Curiel et al., 1987) to the whole class of compromise admissible (or quasi-balanced) games (Tijs, 1981). This extended rule, which we call τ∗, turns out to be the barycenter of the edges of the core cover, which is our main result. Moreover, τ∗and the compromise value coincide for most of quasi-balanced games. This Chapter is organized as follows. In Section 8.2, we extend the APROP rule and define the barycenter ζof the edges of the core cover. In Section 8.3, we state our main result and give an overview of the proof, which consists of six steps. Finally, in Section 8.4, we prove our main result. 8.2 The τ∗Value Atransferable utility or TU game is a pair (N, v), where N={1,...,n}is a set of players and v: 2N→Ris a function assigning to every coalition S⊆Na payoff v(S). By convention, v(∅) = 0. Following Tijs and Lipperts (1982), the utopia vector of a game (N, v),M(v)∈RN, is defined, for each i∈N,by Mi(v) := v(N)−v(N\{i}). The minimum right vector mi(v)∈RNis defined, for each i∈N, by mi(v) := max S⊆N,i∈S{v(S)−X j∈S\{i} Mj(v)}. The core cover of a game (N, v)consists of those allocations of v(N)according to which every player receives at most his utopia payoff and at least his minimal right: CC(v) := {x∈RN:X i∈N xi=v(N), m(v)≤x≤M(v)}. A game is compromise admissible if it has a nonempty core cover. We denote the class of compromise admissible games with player set Nby CAN. An allocation rule on a subclass 8.2. The τ∗Value 141 A⊆CANis a function ϕ:A→RNassigning to each v∈Aa payoff vector ϕ(v)∈RN. Moreover, we say that ϕis efficient if Pi∈Nϕi(v) = v(N). The compromise value or τvalue (Tijs, 1981) is the rule on CANdefined as the point on the line segment between m(v)and M(v)that is efficient: τ(v) := λm(v) + (1 −λ)M(v), where λ∈[0,1] is such that Pi∈Nτi=v(N). Abankruptcy problem is a triple (N, E, c), where E≥0is the estate to be divided and c∈RN +with Pi∈Nci≥Eis the vector of claims. The corresponding cooperative bankruptcy game (N, vE,c)is defined, for each S⊆N, by vE,c(S) = max{E−Pi∈N\Sci,0}. We denote the class of bankruptcy problems with player set Nby BRN. The class of corresponding games is a proper subclass of CAN. A bankruptcy rule is a function f:BRN→RNassigning to every bankruptcy problem (N, E, c)∈BRNa payoff vector f(E, c)∈RN +such that Pi∈Nfi(E, c) = E. In the literature, many bankruptcy rules have been proposed. One interesting question is how these can be extended in a natural way to the whole class of compromise admissible games. In this Chapter, we consider the proportional rule and the adjusted proportional rule (Curiel et al., 1987). The proportional rule P ROP simply divides the estate proportional to the claims, i.e., for each (N, E, c)∈BRNand each i∈N, PROPi(E, c) = ci Pj∈Ncj E. The adjusted proportional rule APROP first gives each player i∈Nhis minimal right mi(E, c) = max{E−Pj∈N\{i}cj,0}and the remainder is divided using the proportional rule, where each player’s claim is truncated to the estate left: APROP(E, c) = m(E, c) + P ROP (E′, c′), where E′=E−Pi∈Nmi(E, c)and for each i∈N,c′ i= min{ci−mi(E, c), E′}. The compromise value can be seen as an extension of the PROP rule: τ(v) = m(v) + PROP(v(N)−X i∈N mi(v), M(v)−m(v)). Note that it follows from the definition of compromise admissibility that the argument of PROP is indeed a bankruptcy problem. Similarly, we can extend the APROP rule: τ∗(v) = m(v) + APROP(v(N)−X i∈N mi(v), M(v)−m(v)). To simplify the expression for τ∗, we show that the minimum rights in the associated bankruptcy