|
on Game Theory |
|
Issue of 2008‒12‒14
fifteen papers chosen by Laszlo A. Koczy Budapest Tech and Maastricht University |
| By: | René van den Brink (VU University Amsterdam); Ilya Katsev (St. Petersburg Institute for Economics and Mathematics, Russian Academy of Sciences); Gerard van der Laan (VU University Amsterdam) |
| Abstract: | A situation in which a finite set of players can obtain certain payoffs by cooperation can be described by a cooperative game with transferable utility, or simply a TU-game. A (single-valued) solution for TU-games assigns a payoff distribution to every TU-game. A well-known solution is the nucleolus. A cooperative game with a permission structure describes a situation in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. The corresponding restricted game takes account of the limited cooperation possibilities by assigning to every coalition the worth of its largest feasible subset. In this paper we consider the class of non-negative additive games with an acyclic permission structure. This class generalizes the so-called peer group games being non-negative additive games on a permission tree. We provide a polynomial time algorithm for computing the nucleolus of every restricted game corresponding to some disjunctive non-negative additive game with an acyclic permission structure. We discuss an application to market situations where sellers can sell objects to buyers through a directed network of intermediaries. |
| Keywords: | TU-game; additive game; acyclic permission structure; disjunctive approach; peer group game; nucleolus; algorithm; complexity |
| JEL: | C71 |
| Date: | 2008–10–31 |
| URL: | http://d.repec.org/n?u=RePEc:dgr:uvatin:20080104&r=gth |
| By: | Pedro Miranda (Universidad Complutense de Madrid - Department of Statistics and O.R.); Michel Grabisch (CES - Centre d'économie de la Sorbonne - CNRS : UMR8174 - Université Panthéon-Sorbonne - Paris I) |
| Abstract: | In this paper, we present a generalization of the concept of balanced game for finite games. Balanced games are those having a nonempty core, and this core is usually considered as the solution of game. Based on the concept of k-additivity, we define to so-called k-balanced games and the corresponding generalization of core, the k-additive core, whose elements are not directly imputations but k-additive games. We show that any game is k-balanced for a suitable choice of k, so that the corresponding k-additive core is not empty. For the games in the k-additive core, we propose a sharing procedure to get an imputation and a representative value for the expectations of the players based on the pessimistic criterion. Moreover, we look for necessary and sufficient conditions for a game to be k-balanced. For the general case, it is shown that any game is either balanced or 2-balanced. Finally, we treat the special case of capacities. |
| Keywords: | Coopertaive games, k-additivity, balanced games, capacities, core. |
| Date: | 2008–11 |
| URL: | http://d.repec.org/n?u=RePEc:hal:cesptp:halshs-00344809_v1&r=gth |
| By: | Inés Macho-Stadler; David Pérez-Castrillo; David Wettstein |
| Abstract: | We consider cooperative environments with externalities (games in partition function form) and provide a recursive definition of dividends for each coalition and any partition of the players it belongs to. We show that with this definition and equal sharing of these dividends the averaged sum of dividends for each player, over all the coalitions that contain the player, coincides with the corresponding average value of the player. We then construct weighted Shapley values by departing from equal division of dividends and finally, for each such value, provide a bidding mechanism implementing it. |
| Keywords: | Shapley value, dividends, games with externalities, implementation |
| JEL: | D62 C71 |
| Date: | 2008–12–01 |
| URL: | http://d.repec.org/n?u=RePEc:aub:autbar:758.08&r=gth |
| By: | Flesch János; Kuipers Jeroen; Schoenmakers Gijs; Vrieze Koos (METEOR) |
| Abstract: | We consider a class of n-player stochastic games with the following properties: (1) in every state, the transitions are controlled by one player, (2) the payoffs are equal to zero in every non-absorbing state, (3) the payoffs are non-negative in every absorbing state. With respect to the expected average reward, we provide a constructive proof that a subgame-perfect ε -equilibrium exists in pure strategies, for every ε > 0. More-over, if all transitions of a game in our class are deterministic, then the game has a subgame-perfect 0-equilibrium in pure strategies. |
| Keywords: | mathematical economics; |
| Date: | 2008 |
| URL: | http://d.repec.org/n?u=RePEc:dgr:umamet:2008041&r=gth |
| By: | Michel Grabisch (CES - Centre d'économie de la Sorbonne - CNRS : UMR8174 - Université Panthéon-Sorbonne - Paris I); Lijue Xie (CES - Centre d'économie de la Sorbonne - CNRS : UMR8174 - Université Panthéon-Sorbonne - Paris I) |
| Abstract: | Finding a solution concept is one of the central problems in cooperative game theory, and the notion of core is the most popular solution concept since it is based on some rationality condition. In many real situations, not all possible coalitions can form, so that classical TU-games cannot be used. An interesting case is when possible coalitions are defined through a partial ordering of the players (or hierarchy). Then feasible coalitions correspond to teams of players, that is, one or several players with all their subordinates. In these situations, it is not obvious to define a suitable notion of core, reflecting the team structure, and previous attempts are not satisfactory in this respect. We propose a new notion of core, which imposes efficiency of the allocation at each level of the hierarchy, and answers the problem of sharing benefits in a hierarchy. We show that the core we defined has properties very close to the classical case, with respect to marginal vectors, the Weber set, and balancedness. |
| Keywords: | Cooperative game, feasible coalition, core, hierarchy. |
| Date: | 2008–10 |
| URL: | http://d.repec.org/n?u=RePEc:hal:journl:halshs-00344802_v1&r=gth |
| By: | Velu, C.; Iyer, S. |
| Abstract: | Returns-based beliefs provides an explanation for the anomaly between the theory and empirics for the one-shot and finitely-repeated Prisoner’s Dilemma games. Even in a fully specified game, there is strategic uncertainty as players attempt to coordinate their actions. Therefore players form subjective probabilities of the actions of their opponents. We provide a new method termed the ‘returns-based beliefs’ approach of forming subjective probabilities that is based upon the expected returns of a particular strategy, in proportion to the total expected returns of all strategies. This method can be applied even in the absence of knowledge of the players’ respective histories. |
| Keywords: | Prisoner’s Dilemma, Rationality, Subjective Probabilities, Returns-Based Beliefs. |
| JEL: | C72 D43 |
| Date: | 2008–11 |
| URL: | http://d.repec.org/n?u=RePEc:cam:camdae:0854&r=gth |
| By: | Michel Grabisch (CES - Centre d'économie de la Sorbonne - CNRS : UMR8174 - Université Panthéon-Sorbonne - Paris I); Agnieszka Rusinowska (GATE - Groupe d'analyse et de théorie économique - CNRS : UMR5824 - Université Lumière - Lyon II - Ecole Normale Supérieure Lettres et Sciences Humaines) |
| Abstract: | In the paper, we study a relation between command games proposed by Hu and Shapley and an influence model. We show that our framework of influence is more general than the framework of the command games. We define several influence functions which capture the command structure. These functions are compatible with the command games, in the sense that each commandable player for a coalition in the command game is a follower of the coalition under the command influence function. Some of the presented influence functions are equivalent to the command games, that is, they are compatible with the command games, and additionally each follower of a coalition under the command influence function is also a commandable player for that coalition in the command games. For some influence functions, we define the equivalent command games. We show that not for all influence functions the compatible command games exist. Moreover, we propose a more general definition of the influence index and show that under some assumptions, some power indices, which can be used in the command games, coincide with some expressions of the weighted influence indices. Both the Shapley-Shubik index and the Banzhaf index are equal to a difference between the weighted influence indices under some influence functions, and the only difference between thes two power indices lies in the weights for the influence indices. An example of the Confucian model od society is broadly examined. |
| Keywords: | Influence function ; follower ; influence index ; command game ; commandable player ; Shapley-Shubik index ; Banzhaf index ; Coleman indices ; König-Bräuninger index |
| Date: | 2008–11 |
| URL: | http://d.repec.org/n?u=RePEc:hal:cesptp:halshs-00344805_v1&r=gth |
| By: | Michel Grabisch (CES - Centre d'économie de la Sorbonne - CNRS : UMR8174 - Université Panthéon-Sorbonne - Paris I); Yukihiko Funaki (Waseda University - School of Political Science & Economics) |
| Abstract: | The coalition formation problem in an economy with externalities can be adequately modeled by using games in partition function form (PFF games), proposed by Thrall and Lucas. If we suppose that forming the grand coalition generates the largest total surplus, a central question is how to allocate the worth of the grand coalition to each player, i.e., how to find an adequate solution concept, taking into account the whole process of coalition formation. We propose in this paper the original concepts of scenario-value, process-value and value, which represent the average contribution of players in a scenario (a particular sequence of coalitions within a given coalition formation process), in a process (a sequence of partitions of the society), and in the whole (all processes being taken into account), respectively. We give an application to Cournot oligopoly, and two axiomatizations of our solution concept. A comparison with the value proposed by Macho-Stadler et al. for PFF games is done. |
| Keywords: | Coalition formation, games in partition function form, solution concept, Cournot oligopoly. |
| Date: | 2008–11 |
| URL: | http://d.repec.org/n?u=RePEc:hal:cesptp:halshs-00344797_v1&r=gth |
| By: | Michel Grabisch (CES - Centre d'économie de la Sorbonne - CNRS : UMR8174 - Université Panthéon-Sorbonne - Paris I); Agnieszka Rusinowska (GATE - Groupe d'analyse et de théorie économique - CNRS : UMR5824 - Université Lumière - Lyon II - Ecole Normale Supérieure Lettres et Sciences Humaines) |
| Abstract: | We study and compare two frameworks : a model of influence, and command games. In the influence model, in which players are to make a certain acceptance/rejection decision, due to influence of other players, the decision of a player may be different from his inclination. We study a relation between two central concepts of this model : influence function, and follower function. We deliver sufficient and necessary conditions for a function to be a follower function, and we describe the structure of the set of all influence functions that lead to a given follower function. In the command structure introduced by Hu and Shapley, for each player a simple game called the command game is built. One of the central concepts of this model is the concept of command function. We deliver sufficient and necessary conditions for a function to be a command function, and describe the minimal sets generating a normal command game. We also study the relation between command games and influence functions. A sufficient and necessary condition for the equivalence between an influence function and a normal command game is delivered. |
| Keywords: | Influence function, follower function, lower and upper inverses, kernel, command game, command function, minimal sets generating a command game. |
| Date: | 2008–11 |
| URL: | http://d.repec.org/n?u=RePEc:hal:cesptp:halshs-00344823_v1&r=gth |
| By: | McQuillin, Ben |
| Abstract: | The Shapley value assigns, to each game that is adequately represented by its characteristic function, an outcome for each player. An elaboration on the Shapley value that assigns, to characteristic function games, a "partition function" outcome is broadly established and accepted, but elaborations to encompass games with externalities (represented by partition functions) are not. Here, I show that simultaneous consideration of the two elaborations ("generalization" and "extension") obtains a unique Shapley-type value for games in partition function form. The key requirement is that the "Extended, Generalized Shapley Value" (EGSV) should be "recursive": the EGSV of any game should be the EGSV of itself. This requirement forces us to ignore all but the payoffs to bilateral partitions. The EGSV can be conceptualized as the ex ante value of a process of successive bilateral amalgamations. Previous Shapley value extensions, if generalized, are not recursive; indeed, they iterate to the EGSV. |
| Keywords: | Coalition structure; Externalities; Partition function games; Recursion; Shapley value |
| JEL: | D62 C71 |
| Date: | 2008–11–11 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:12049&r=gth |
| By: | Geoffroy de Clippel (Brown University); Roberto Serrano (Brown University) |
| Abstract: | We first observe that two of Maskin´s results do not extend beyond three players: we construct a four-player partition function with nonpositive externalities whose unique solution is inefficient, as well as a four-player characteristic function that has a unique efficient solution for each ordering of the players, but for which the payoff vector obtained by averaging these solutions over the different orderings does not coincide with the Shapley value. On the other hand, we reinforce Maskins insight that externalities may play a crucial role in generating inefficiency. Many existing solutions on how to share profits assume or derive the property of efficiency. Yet we argue that players may have an interest to choose with whom to bargain. We illustrate how this may trigger inefficiency, especially in the presence of externalities, even if bargaining among any group of agents results in an efficient distribution of the surplus they can produce. We also provide some sufficient conditions for efficiency. |
| Keywords: | externalities; coalition formation; Shapley value |
| JEL: | C7 D62 |
| Date: | 2008–11–20 |
| URL: | http://d.repec.org/n?u=RePEc:imd:wpaper:wp2008-11&r=gth |
| By: | Michel Grabisch (CES - Centre d'économie de la Sorbonne - CNRS : UMR8174 - Université Panthéon-Sorbonne - Paris I); Agnieszka Rusinowska (GATE - Groupe d'analyse et de théorie économique - CNRS : UMR5824 - Université Lumière - Lyon II - Ecole Normale Supérieure Lettres et Sciences Humaines) |
| Abstract: | In the paper, we study a model of influence in a social network. It is assumed that each player has an inclination to say YES or NO which, due to influence of other players, may be different from the decision of the player. The point of departure here is the concept of the Hoede-Bakker index - the notion which computes the overall decisional "power" of a player in a social network. The main drawback of the Hoede-Bakker index is that it hides the actual role of the influence function, analyzing only the final decision in terms of success and failure. In this paper, we separate the influence part from the group decision part, and focus on the description and analysis of the influence part. We propose among other descriptive tools a definition of a (weighted) influence index of a coalition upon an individual. Moreover, we consider different influence functions representative of commonly encountered situations. Finally, we propose a suitable definition of a modified decisional power. |
| Keywords: | Influence function, influence index, decisional power, social network. |
| Date: | 2008–11 |
| URL: | http://d.repec.org/n?u=RePEc:hal:cesptp:halshs-00344457_v1&r=gth |
| By: | Kohlscheen, Emanuel (Department of Economics, University of Warwick,); O’Connell, Stephen (Department of Economics, Swarthmore College,) |
| Abstract: | We derive closed-form solutions for the Rubinstein alternating offers game for cases where the two players have (possibly asymmetric) utility functions that belong to the HARA class and discount the future at a constant rate. We show that risk aversion may increase a bargainers payoff. This result - which contradicts Roth’s 1985 theorem tying greater risk neutrality to a smaller payoff - does not rely on imperfect information or departures from expected utility maximization. |
| Date: | 2008 |
| URL: | http://d.repec.org/n?u=RePEc:wrk:warwec:878&r=gth |
| By: | Thierry, BRECHET (UNIVERSITE CATHOLIQUE DE LOUVAIN, Center for Operations Research and Econometrics (CORE)); Francois, GERARD (UNIVERSITE CATHOLIQUE DE LOUVAIN, Center for Operations Research and Econometrics (CORE)); Henry, TULKENS (UNIVERSITE CATHOLIQUE DE LOUVAIN, Center for Operations Research and Econometrics (CORE)); Jean-Pascal, VAN YPERSELE |
| Abstract: | In this paper we analyze the negotiation strategy of the European Union regarding the formation of an international climate agreement for the post-2012 era. We use game theoretical stability concepts to explore incentives for key players in the climate policy game to join future climate agreements. We compare a minus 20 percent unilateral commitment strategy by the EU with a unilateral minus 30 percent emission reduction strategy for all Annex-B countries. Using a numerical integrated assessment climate-economy simulation model, we find that carbon leakage effects are negligible. Ther EU strategy to reduce emissions by 30% (compared to 1990 levels) by 2020 if other Annex-B countries follow does not induce participation of the USA with a similar 30% reduction commitement. However, the model shows that an appropriate initial allocation of emission allowances may stabilize a larger and more ambitious climate coalition than the Kyoto Protocol in its first commitment period. |
| Keywords: | Climate change, Coalition theory, Integrated assessment model, Kyoto protocol |
| JEL: | C6 C7 H4 Q5 |
| Date: | 2008–12–04 |
| URL: | http://d.repec.org/n?u=RePEc:ctl:louvec:2008038&r=gth |
| By: | René van den Brink (VU University Amsterdam); Frank Steffen (The University of Liverpool and University of Hamburg) |
| Abstract: | Power is a core concept in the analysis and design of organizations. One of the problems with the extant literature on positional power in hierarchies is that it is mainly restricted to the analysis of power in terms of the bare positions of the actors. While such an analysis informs us about the authority structure within an organization, it ignores the decision-making mechanisms completely. The few studies which take into account the decision-making mechanisms make all use of adaptations of well-established approaches for the analysis of power in non-hierarchical organizations such as the Banzhaf measure; and thus they are all based on the structure of a simple game, i.e. they are `membership-based'. In van den Brink and Steffen (2008) it is demonstrated that such an approach is in general inappropriate for characterizing power in hierarchies as it cannot be extended to a class of decision-making mechanisms which allow certain actors to terminate a decision before all other members have been involved. As this kind of sequential decision-making mechanism turns out to be particularly relevant for hierarchies, we suggested an action-based approach - represented by an extensive game form - which can take the features of such mechanisms into account. Based on this approach we introduced a power score and power measure that can be applied to ascribe positional power to actors in sequential decision making mechanisms. In this paper we provide axiomatizations of this power score and power measure for one of the most studied decision models, namely that of binary voting. |
| Keywords: | hierarchies; decision-making mechanism; power; positional power; power score; power measure; binary voting; axiomatization |
| JEL: | C79 D02 D71 |
| Date: | 2008–11–24 |
| URL: | http://d.repec.org/n?u=RePEc:dgr:uvatin:20080115&r=gth |