Search

We present an axiomatic characterization of the Owen-Shapley spatial power index for the case where issues are elements of two-dimensional space. This characterization employs a version of the transfer condition, which enables us to unravel a spatial game into spatial games connected to unanimity games. The other axioms include two conditions concerned particularly with the spatial positions of the players, besides spatial versions of anonymity and dummy. The last condition says that dummy players can be left out in a specific way without changing the power of the other players. We show that this condition can be weakened to requiring dummies to have zero power if we add a condition of positional continuity. We also show that the axioms in our characterization(s) are logically independent.

Beimel, Tassa and Weinreb [SIAM J. Discrete Math. 22 (2008), 360–397] and Farràs and Padró [Lecture Notes in Comput. Sci. 5978, Springer, 2010, 219–236] partially characterised access structures of ideal weighted secret sharing schemes in terms of the operation of composition. They proved that any weighted ideal access structure is a composition of indecomposable ones. Farràs and Padró gave a list of seven classes of access structures – one unipartite, three bipartite and three tripartite – to which all weighted ideal indecomposable access structures may belong. In this paper we determine exactly which access structures from those classes are indecomposable. We also determine which compositions of indecomposable weighted access structures are again weighted and obtain an if-and-only-if characterisation of ideal weighted secret sharing schemes. We use game-theoretic techniques to achieve this.

This paper considers the computational complexity of the design of voting rules, which is formulated by simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.

This paper is a twofold contribution. First, it contributes to the problem of enumerating some classes of simple games and in particular provides the number of weighted games with minimum and the number of weighted games for the dual class as well. Second, we focus on the special case of bipartite complete games with minimum, and we compare and rank these games according to the behavior of some efficient power indices of players of type 1 (or of type 2). The main result of this second part establishes all allowable rankings of these games when the Shapley-Shubik power index is used on players of type 1., 26 pages, 2 figures, to appear in Annals of Operations Research

We survey the results on representations of committees and constitutions by game forms that possess some kind of equilibrium strategies for each profile of preferences of the players. The survey is restricted to discrete models, that is, we deal with finitely many players and alternatives. No prior knowledge of social choice is assumed: As far as definitions are concerned, the paper is self-contained. Section 2 supplies the necessary general tools for the rest of the paper. Each definition is followed by a simple (but nontrivial) example. In Section 3 we give a complete account of representations of committees (proper and monotonic simple games), by exactly and strongly consistent social choice functions. We start with Peleg’s representations of weak games, and then provide a complete and detailed account of Holzman’s solution of the representation problem for simple games without veto players. In Section 4 we deal with representations of constitutions by game forms. Following Gärdenfors we model a constitution by a monotonic and superadditive effectivity function. We fully characterize the representations for three kinds of equilibrium: Nash equilibrium; acceptable equilibrium (Pareto optimal Nash equilibrium); and strong Nash equilibrium. We conclude in Section 5 with a report on two recent works on representations of constitutions under incomplete information.

The final authenticated version is available online at: https://doi.org/10.1007/978-3-319-70647-4_5. Any power index defines a total preorder in a simple game and, thus, induces a hierarchy among its players. The desirability relation, which is also a preorder, induces the same hierarchy as the Banzhaf and the Shapley indices on linear games, i.e., games in which the desirability relation is total. The desirability relation is a sub–preorder of another preorder, the weak desirability relation, and the class of weakly linear games, i.e., games for which the weak desirability relation is total, is larger than the class of linear games. The weak desirability relation induces the same hierarchy as the Banzhaf and the Shapley indices on weakly linear games. In this paper, we define a chain of preorders between the desirability and the weak desirability preorders. From them we obtain new classes of totally preordered games between linear and weakly linear games.

Several relationships between simple games and a particular type of solu- tions for cooperative games are studied in this paper. These solutions belong to the set of semivalues and they are related to a unique parameter that explicitly provides their weighting coefficients. Through the allocations offered by this family of solu- tions, so-called binomial semivalues, and also from their respective potentials, some characteristics of the simple games can be recovered. The paper analyzes the capacity of binomial semivalues to summarize the structure of simple games, and, moreover, a property of separation among simple games is given.

We study the structure of unstable local effectivity functions defined for n players and p alternatives. A stability index based on the notion of cycle is introduced. In the particular case of simple games, the stability index is closely related to the Nakamura Number. In general it may be any integer between 2 and p. We prove that the stability index for maximal effectivity functions and for maximal local effectivity functions is either 2 or 3., On étudie la structure d'instabilité des fonctions d'effectivités locales définies pour n joueurs et p alternatives. Un indice de stabilité basé sur la notion de cycle est définie. En particulier dans le cas des jeux simples cet indice est intimement lié au nombre de Nakamura. En général c'est un entier qui peut prendre une valeur entre 2 et p. On montre que l'indice de stabilité de toute fonction d'effectivité maximale et même de toute fonction d'effectivité locale maximale ne prend que les valeurs 2 ou 3.

Dans un article publié en 1952, peu après la publication du théorème d’impossibilité d’Arrow, le mathématicien français Georges-Théodule Guilbaud a obtenu un résultat dictatorial pour le problème logique de l’agrégation, anticipant ainsi la théorie abstraite de l’agrégation et celle de l’agrégation des jugements. Nous donnons une reconstruction de la preuve du théorème de Guilbaud, qui présente aussi un intérêt technique, puisqu’elle peut être vue comme le premier emploi des ultrafiltres en théorie du choix social. In a paper published in 1952, shortly after the publication of Arrow’s celebrated impossibility result, the French mathematician Georges-Théodule Guilbaud has obtained a dictatorship result for the logical problem of aggregation, thus anticipating the literature on abstract aggregation theory and judgment aggregation. We reconstruct the proof of Guilbaud’s theorem, which is also of technical interest, because it can be seen as the first use of ultrafilters in social choice theory.

Different (proper as well as improper) simple games may share any nonseparating blocking family. An interesting question is whether all such proper games on one hand, and all improper ones on the other, are isomorphic. The answer is given here and the automorphisms of the blocking family help us to understand the structure and links of all such games.

In this paper, we characterize two power indices introduced in [1] using two different modifications of the monotonicity property first stated by [2]. The sets of properties are easily comparable among them and with previous characterizations of other power indices., A. A. Pinto acknowledges the financial support of LIAAD INESC TEC through program PEst,USP-UP project, Faculty of Sciences, University of Porto, Calouste Gulbenkian Foundation,FEDER, POCI 2010 and COMPETE Programmes, PTDC/MAT/121107/2010 and Fundação para a Ciência e a Tecnologia (FCT). J. M. Alonso-Meijide and M. Álvarez-Mozos acknowledge the financial support of the Spanish Ministry of Economy and Competitiveness through Projects ECO2008-03484-C02-02/ECO and MTM2011-27731-C03-03 and of Xunta de Galicia through Project INCITE09-207-064-PR.

Simple games are a powerful tool to analyze decision-making and coalition formation in social and political life. In this paper, we present relation-algebraic models of simple games and develop relational algorithms for solving some basic problems of them. In particular, we test certain fundamental properties of simple games (being monotone, proper, respectively strong) and compute specific players (dummies, dictators, vetoers, null players) and coalitions (minimal winning coalitions and vulnerable winning coalitions). We also apply relation-algebra to determine central and dominant players, swingers and power indices (the Banzhaf, Holler-Packel and Deegan-Packel indices). This leads to relation-algebraic specifications, which can be executed with the help of the BDD-based tool RelView after a simple translation into the tool’s programming language. In order to demonstrate the visualization facilities of RelView we consider an example of the Catalonian Parliament after the 2003 election.

We study the power relation ≥ P. This binary relation on the set of voters was used in [Diffo Lambo, Moulen, 2000] to show that the Taylor’s influence relation ≥ T appraises the voter’s capacity of influencing the voting outcome when individual preference relations are linear orders, if the classical dominance stands for the social outcome and the Kendal’s distance is the means of measuring a voter’s dissatisfaction. In this paper, the definition of ≥P is extended in two directions: on the one hand, dissatisfaction is measured by any distance (apart from the Kendal’s distance), and on the other hand, the domain of individual preference relations has no restriction (it may contain complete weak orders apart from complete linear orders). The above mentioned result on ≥ T now being at times wrong, we come out with a sufficient condition under which ≥ T actually appraises the voter’s capacity of influencing the voting outcome. Moreover we succeed, thanks to this highly unifying condition, in generalizing all the other results of [Diffo Lambo, Moulen, 2000]. Nous étudions ce que nous appelons la relation de puissance. Cette relation binaire, définie sur l’ensemble des électeurs d’un jeu de vote, a permis dans [Diffo Lambo, Moulen, 2000] de montrer que la relation d’influence de Taylor traduit la capacité du votant à influencer le résultat du vote, lorsque les préférences individuelles sont des ordres totaux, le résultat du vote étant représenté par la dominance classique et l’insatisfaction du votant mesurée au moyen de la distance de la différence symétrique. Dans cet article, la définition de la relation de puissance est généralisée dans deux directions : d’une part, l’insatisfaction est mesurée à l’aide d’une distance quelconque (au lieu de la distance de la différence symétrique), et d’autre part, le domaine de préférences individuelles est maintenant quelconque (et peut être constitué de préordres totaux au lieu d’ordres totaux). Le résultat suscité sur la relation d'influence de Taylor étant alors parfois faux, nous obtenons une condition pour que la relation d'influence de Taylor traduise la capacité du votant à influencer le résultat du vote. En outre, nous parvenons, grâce à cette condition suffisamment unificatrice, à généraliser les autres résultats obtenus dans [Diffo Lambo, Moulen, 2000].

The aim of this paper is to present Arrow's theorem and more generally the common framework of many results which can be called "Arrovian theorems". We begin by recalling the Condorcet majority rules and why they fail: the so called "effet Condorcet". These rules are examples of preference aggregation functions defined by a simple game, and then following Guilbaud's approach, we seek if in the class of all these functions we can find some functions avoiding this problem. The rather negative answer is given by the Guilbaud and Nakamura theorems. Taking then an axiomatic approach we show that some independent and Paretian preference aggregation functions avoiding the "effet Condorcet" are defined by a simple game. So the previous results allow to get several Arrovian theorems and finally Arrow's theorem. In the last section we give some historical and bibliographical comments on these results and on several developments showing essentially the robustness of Arrow's theorem. Ce texte a pour but de présenter le théorème d'Arrow et plus généralement la structure commune à de nombreux résultats "arrowien" montrant la difficulté d'agréger des préférences individuelles en une préférence collective. On commence par rappeler "l'effet Condorcet", cause de "l'échec de la règle majoritaire. Cette règle est un exemple de règle définie par un "jeu simple" et, à la suite de Guilbaud, on cherche ensuite si parmi de telles règles on peut en trouver de plus satisfaisantes. La réponse, plutôt négative, est donnée par les théorèmes de Guilbaud et de Nakamura. Adoptant ensuite une démarche axiomatique, on montre que des règles vérifiant les propriétés d'indépendance et de Pareto et évitant "l'effet Condorcet" sont définies par un "jeu simple", ce qui permet d'obtenir des théorèmes arrowiens et finalement le théorème d'Arrow. La dernière section donne des indications sur les nombreux développements montrant la robustesse de ce théorème.