Skip to main content

ASPECTOS MATEMATICOS, COMPUTACIONALES Y SOCIALES EN CONTEXTOS DE VOTACION Y DE COOPERACION.

MTM2015-66818-P

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
Program Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprogram Subprograma Estatal de Generación de Conocimiento
Call Proyectos de I+D (Excelencia / Generación de Conocimiento)
Call year 2015
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Secretaría de Estado de Educación, Formación Profesional y Universidades
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 60
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publication Capítulo o parte de un libro (BookPart)

On the characterization of weighted simple games

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Freixas Boleda, Marc
  • Kurz, Sascha
The final publication is available at link.springer.com via http://dx.doi.org/10.1007/s11238-017-9606-z, This paper has a twofold scope. The first one is to clarify and put in evidence the isomorphic character of two theories developed in quite different fields: on one side, threshold logic, on the other side, simple games. One of the main purposes in both theories is to determine when a simple game is representable as a weighted game, which allows a very compact and easily comprehensible representation. Deep results were found in threshold logic in the sixties and seventies for this problem. However, game theory has taken the lead and some new results have been obtained for the problem in the past two decades. The second and main goal of this paper is to provide some new results on this problem and propose several open questions and conjectures for future research. The results we obtain depend on two significant parameters of the game: the number of types of equivalent players and the number of types of shift-minimal winning coalitions., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A parameterization for a class of complete games with abstention

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Tchantcho, Bertrand
  • Tsague, Bill Procès
Voting games with abstention are voting systems in which players can cast not only yes and no vote, but are allowed to abstain. This paper centers on the structure of a class of complete games with abstention. We obtain, a parameterization that can be useful for enumerating these games, up to isomorphism. Indeed, any I-complete game is determined by a vector of matrices with non-negative integers entries. It also allows us determining whether a complete game with abstention is a strongly weighted (3, 2) game or not, and for other purposes of interest in game theory., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Bounds for the Nakamura number

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Kurz, Sascha
This is a post-peer-review, pre-copyedit version of an article published in Social choice and welfare. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00355-018-1164-y., The Nakamura number is an appropriate invariant of a simple game to study the existence of social equilibria and the possibility of cycles. For symmetric (quota) games its number can be obtained by an easy formula. For some subclasses of simple games the corresponding Nakamura number has also been characterized. However, in general, not much is known about lower and upper bounds depending on invariants of simple, complete or weighted games. Here, we survey such results and highlight connections with other game theoretic concepts. © 2018, Springer-Verlag GmbH Germany, part of Springer Nature., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The complexity of measuring power in generalized opinion leader decision models

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Serna Iglesias, María José|||0000-0001-9729-8648
We analyze the computational complexity of the power measure in models of collective decision: the generalized opinion leader-follower model and the oblivious and non-oblivious infuence models. We show that computing the power measure is #P-hard in all these models, and provide two subfamilies in which the power measure can be computed in polynomial time., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Influence decision models: from cooperative game theory to social network analysis

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
Cooperative game theory considers simple games and influence games as essential classes of games. A simple game can be viewed as a model of voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. An influence game is a cooperative game in which a team of players (or coalition) succeeds if it is able to convince sufficiently many agents to participate in a task. Furthermore, influence decision models allow to represent discrete system dynamics as graphs whose nodes are activated according to an influence spread model. It let us to depth in the social network analysis. All these concepts are applied to a wide variety of disciplines, such as social sciences, economics, marketing, cognitive sciences, political science, biology, computer science, among others. In this survey we present different advances in these topics, joint work with M. Serna. These advances include representations of simple games, the definition of influence games, and how to characterize different problems on influence games (measures, values, properties and problems for particular cases with respect to both the spread of influence and the structure of the graph). Moreover, we also present equivalent models to the simple games, the computation of satisfaction and power in collective decision-making models, and the definition of new centrality measures used for social network analysis. In addition, several interesting computational complexity results have been found., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The Shapley value analyzed under the Felsenthal and Machover bargaining model

  • Bernardi, Giulia
  • Freixas Bosch, Josep|||0000-0002-9033-9432
This is a post-peer-review, pre-copyedit version of an article published in Public choice. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11127-018-0560-2., In 1996, Felsenthal and Machover proposed a bargaining procedure for a valuable payoff in cooperative and simple games. They proved that the value underlying their bargaining scheme was the Shapley value by showing that it verifies the axioms that Shapley proposed for characterizing his value. They remarked that a direct proof of the result involves rather formidable combinatorial difficulties, but that it has some independent interest. In this paper, we prove such a combinatorial result and obtain a formula for the Shapley value that has a great potential to be extended to more general classes of games., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A note on multinomial probabilistic values

  • Carreras Escobar, Francisco|||0000-0002-7248-9912
  • Puente del Campo, María Albina|||0000-0003-2732-9087
This is a post-peer-review, pre-copyedit version of an article published in "TOP". The final authenticated version is available online at: https://doi.org/10.1007/s11750-017-0464-1, Multinomial values were previously introduced by one of the authors in reliability and extended later to all cooperative games. Here, we present for this subfamily of probabilistic values three new results, previously stated only for binomial semivalues in the literature. They concern the dimension of the subspace spanned by the multinomial values and two characterizations: one, individual, for each multinomial value; another, collective, for the whole subfamily they form. Finally, an application to simple games is provided, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Dimension, egalitarianism and decisiveness of European voting systems

  • Carreras Escobar, Francisco|||0000-0002-7248-9912
  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Magaña Nieto, Antonio|||0000-0003-0879-0759
An analysis of three major aspects has been carried out that may apply to any of the successive voting systems used for the European Union Council of Ministers, from the first one established in the Treaty of Rome in 1958 to the current one established in Lisbon. We mainly consider the voting systems designed for the enlarged European Union adopted in the Athens summit, held in April 2003 but this analysis can be applied to any other system. First, it is shown that the dimension of these voting systems does not, in general, reduce. Next, the egalitarian effects of superposing two or three weighted majority games (often by introducing additional consensus) are considered. Finally, the decisiveness of these voting systems is evaluated and compared., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Satisfaction and power in unanimous majority influence decision models

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
We consider decision models associated with cooperative influence games, the oblivious and the non-oblivious influence models. In those models the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures when the in uence level is set to unanimity and the rule of decision is simple majority. We show that computing the satisfaction and the power measure in those systems are #P-hard., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Using the multilinear extension to study some probabilistic power indices

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
The final publication is available at Springer via http://dx.doi.org/10.1007/s10726-016-9514-6, We consider binary voting systems modeled by a simple game, in which voters vote independently of each other, and the probability distribution over coalitions is known. The Owen’s multilinear extension of the simple game is used to improve the use and the computation of three indices defined in this model: the decisiveness index, which is an extension of the Banzhaf index, the success index, which is an extension of the Rae index, and the luckiness index. This approach leads us to prove new properties and inter-relations between these indices. In particular it is proved that the ordinal equivalence between success and decisiveness indices is achieved in any game if and only if the probability distribution is anonymous. In the anonymous case, the egalitarianism of the three indices is compared, and it is also proved that, for these distributions, decisiveness and success indices respect the strength of the seats, whereas luckiness reverses this order., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Measuring satisfaction in societies with opinion leaders and mediators

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
An opinion leader-follower model (OLF) is a two-action collective decision-making model for societies, in which three kinds of actors are considered:
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Dimension and codimension of simple games

  • Kurz, Sascha
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Olsen, Martin
  • Serna Iglesias, María José|||0000-0001-9729-8648
This paper studies the complexity of computing a representation of a simple game as the intersection (union) of weighted majority games, as well as, the dimension or the codimension. We also present some examples with linear dimension and exponential codimension with respect to the number of players., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A characterization of weighted simple games based on pseudoweightings

  • Freixas Bosch, Josep|||0000-0002-9033-9432
This is a post-peer-review, pre-copyedit version of an article published in Optimization letters. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11590-020-01647-3, The paper provides a new characterization of weighted games within the class of simple games. It is based on a stronger form of the point-set-additive pseudoweighting property of simple games. The characterization obtained is of interest in various research fields such as game theory, coherent structures, logic gates, operations research and Boolean algebra. A (monotonic) simple game corresponds to an inequivalent (monotonic) function in Boolean algebra and a weighted game corresponds to a threshold function. The characterization obtained provides a better understanding of these mathematical structures while opening new prospects for solving numerous open problems in these areas., This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015–66818-P(MINECO/FEDER)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On the construction of high dimensional simple games

  • Olsen, Martin
  • Kurz, Sascha
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
Voting is a commonly applied method for the aggregation of the preferences of multiple agents into a joint decision. If preferences are binary, i.e., “yes” and “no”, every voting system can be described by a (monotone) Boolean function : f0; 1gn ! f0; 1g. However, its naive encoding needs 2n bits. The subclass of threshold functions, which is sufficient for homogeneous agents, allows a more succinct representation using n weights and one threshold. For heterogeneous agents one can represent as an intersection of k threshold functions. Taylor and Zwicker have constructed a sequence of examples requiring k 2 n2 ¿1 and provided a construction guaranteeingk ¿ n bn=2c 2 2n¿o(n). The magnitude of the worst case situation was thought to be determined by Elkind et al. in 2008, but the analysis unfortunately turned out to be wrong. Here we uncover a relation to coding theory that allows the determination of the minimum number k for a subclass of voting systems. As an application, we give a construction for k 2n¿o(n), i.e., there is no gain from a representation complexity point of view., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Combinatorial structures to modeling simple games and applications

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
We connect three different topics: combinatorial structures, game theory and chemistry. In particular, we establish the bases to represent some simple games, defined as influence games, and molecules, defined from atoms, by using combinatorial structures. First, we characterize simple games as influence games using influence graphs. It let us to modeling simple games as combinatorial structures (from the viewpoint of structures or graphs). Second, we formally define molecules as combinations of atoms. It let us to modeling molecules as combinatorial structures (from the viewpoint of combinations). It is open to generate such combinatorial structures using some specific techniques as genetic algorithms, (meta-)heuristics algorithms and parallel programming, among others., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The Banzhaf value for cooperative and simple multichoice games

  • Freixas Bosch, Josep|||0000-0002-9033-9432
This is a post-peer-review, pre-copyedit version of an article published in Group Decision and Negotiation. The final authenticated version is available online at: https://doi.org/10.1007/s10726-019-09651-4., This article proposes a value which can be considered an extension of the Banzhaf value for cooperative games. The proposed value is defined on the class of j-cooperative games, i.e., games in which players choose among a finite set of ordered actions and the result depends only on these elections. If the output is binary, only two options are available, then j-cooperative games become j-simple games. The restriction of the value to j-simple games leads to a power index that can be considered an extension of the Banzhaf power index for simple games. The paper provides an axiomatic characterization for the value and the index which is closely related to the first axiomatization of the Banzhaf value and Banzhaf power index in the respective contexts of cooperative and simple games., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Semivalues: weighting coefficients and allocations on unanimity games

  • Domènech Blázquez, Margarita|||0000-0001-9237-7232
  • Giménez Pradales, José Miguel|||0000-0003-4754-194X
  • Puente del Campo, María Albina|||0000-0003-2732-9087
This is a post-peer-review, pre-copyedit version of an article published in Optimization letters. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11590-017-1224-8., Each semivalue, as a solution concept defined on cooperative games with a finite set of players, is univocally determined by weighting coefficients that apply to players’ marginal contributions. Taking into account that a semivalue induces semivalues on lower cardinalities, we prove that its weighting coefficients can be reconstructed from the last weighting coefficients of its induced semivalues. Moreover, we provide the conditions of a sequence of numbers in order to be the family of the last coefficients of any induced semivalues. As a consequence of this fact, we give two characterizations of each semivalue defined on cooperative games with a finite set of players: one, among all semivalues; another, among all solution concepts on cooperative games., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

An appropriate way to extend the Banzhaf index for multiple levels of approval

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
This is a post-peer-review, pre-copyedit version of an article published in Group decision and negotiation. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10726-020-09718-7., The Banzhaf power index for games admits several extensions if the players have more than two ordered voting options. In this paper we prove that the most intu-itive and recognized extension of the index fails to preserve the desirability rela-tion for games with more than three ordered input levels of approval, a failure that undermines the index to be a good measure of power. This leads us to think of an alternative to the Banzhaf index for several input levels of approval. We propose a candidate for which it is proved that: (1) coincides with the Banzhaf index for sim-ple games, (2) it is proportional to its known extension for three levels of approval, and (3) preserves the desirability relation regardless of the number of input levels of approval. This new index is based on measuring the total capacity the player has to alter the outcome. In addition, it can be expressed through a very appropriate mathematical formulation that greatly facilitates its computation. Defining exten-sions of well-established notions in a wider context requires a careful analysis. Dif-ferent extensions can provide complementary nuances and, when this occurs, none of them can be considered to be ‘the’ extension. As shown in this paper, this situa-tion applies when trying to extend the Banzhaf power index from simple games to the broader context of games with several ordered input levels of approval., This research was partially supported by funds from: the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P (MINECO/FEDER), and the Spanish Ministry of Science and Innovation grant PID2019-I04987GB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Decisiveness indices are semiindices: addendum

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
In the paper Decisiveness indices are semiindices (Freixas and Pons, 2016) it was shown that any decisiveness index obtained from an anonymous probability distribution is a semiindex, and that the converse is not true. In this note we characterize the semiindices which are indices of decisiveness., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Centrality measure in social networks based on linear threshold model

  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Gonzalez Cantergiani, Pablo
  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Serna Iglesias, María José|||0000-0001-9729-8648
Centrality and influence spread are two of the most studied concepts in social network analysis. In recent years, centrality measures have attracted the attention of many researchers, generating a large and varied number of new studies about social network analysis and its applications. However, as far as we know, traditional models of influence spread have not yet been exhaustively used to define centrality measures according to the influence criteria. Most of the considered work in this topic is based on the independent cascade model. In this paper we explore the possibilities of the linear threshold model for the definition of centrality measures to be used on weighted and labeled social networks. We propose a new centrality measure to rank the users of the network, the Linear Threshold Rank (LTR), and a centralization measure to determine to what extent the entire network has a centralized structure, the Linear Threshold Centralization (LTC). We appraise the viability of the approach through several case studies. We consider four different social networks to compare our new measures with two centrality measures based on relevance criteria and another centrality measure based on the independent cascade model. Our results show that our measures are useful for ranking actors and networks in a distinguishable way., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Capítulo o parte de un libro (BookPart)

A value for j-cooperative games: some theoretical aspects and applications

  • Freixas Bosch, Josep|||0000-0002-9033-9432
This is an Accepted Manuscript of a book chapter published by Routledge/CRC Press in Handbook of the Shapley value on December 6, 2019, available online: https://www.crcpress.com/Handbook-of-the-Shapley-Value/Algaba-Fragnelli-Sanchez-Soriano/p/book/9780815374688, A value that has all the ingredients to be a generalization of the Shapley value is proposed for a large class of games called j-cooperative games which are closely related to multi-choice games. When it is restricted to cooperative games, i.e. when j equals 2, it coincides with the Shapley value. An explicit formula in terms of some marginal contributions of the characteristic function is provided for the proposed value. Different arguments support it: (1) The value can be inferred from a natural probabilistic model. (2) An axiomatic characterization uniquely determines it. (3) The value is consistent in its particularization from j-cooperative games to j-simple games. This chapter also proposes various ways of calculating the value by giving an alternative expression that does not depend on the marginal contributions. This chapter shows how the technique of generating functions can be applied to determine such a value when the game is a weighted j-simple game. The chapter concludes by presenting several applications, among them the computation of the value for a proposed reform of the UNSC voting system., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Capítulo o parte de un libro (BookPart)

An equivalent formulation for the Shapley value

  • Freixas Bosch, Josep|||0000-0002-9033-9432
The final authenticated version is available online at: https://doi.org/10.1007/978-3-662-58464-4_1., An equivalent explicit formula for the Shapley value is provided, its equivalence with the classical one is proven by double induction. The importance of this new formula, in contrast to the classical one, is its capability of being extended to more general classes of games, in particular to j-cooperative games or multichoice games, in which players choose among different levels of participation in the game., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Capítulo o parte de un libro (BookPart)

Preorders in simple games

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
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., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Ability to separate situations with a priori coalition structures by means of symmetric solutions

  • Giménez Pradales, José Miguel|||0000-0003-4754-194X
We say that two situations described by cooperative games are inseparable by a family of solutions, when they obtain the same allocation by all solution concept of this family. The situation of separability by a family of linear solutions reduces to separability from the null game. This is the case of the family of solutions based on marginal contributions weighted by coef¿cients only dependent of the coalition size: the semivalues. It is known that for games with four or more players, the spaces of inseparable games from the null game contain games different to zero-game. We will prove that for ¿ve or more players, when a priori coalition blocks are introduced in the situation described by the game, the dimension of the vector spaces of inseparable games from the null game decreases in an important manner., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Decisiveness indices are semiindices

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
In this note we prove that any decisiveness index, defined for any voter as the probability of him/her being decisive, is a semiindex when the probability distribution over coalitions is anonymous, and it is a semiindex with binomial coefficients when the probability over coalitions is anonymous and independent., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Capítulo o parte de un libro (BookPart)

A probabilistic unified approach for power indices in simple games

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
The final publication is available at Springer via https://doi.org/10.1007/978-3-662-60555-4_11, Many power indices on simple games have been defined trying to measure, under different points of view, the “a priori” importance of a voter in a collective binary voting scenario. A unified probabilistic way to define some of these power indices is considered in this paper. We show that six well-known power indices are obtained under such a probabilistic approach. Moreover, some new power indices can naturally be obtained in this way., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

An axiomatization for two power indices for (3,2)-simple games

  • Bernardi, Giulia
  • Freixas Bosch, Josep|||0000-0002-9033-9432
Electronic version of an article published as International Game Theory Review, Vol. 21, Issue 1, 1940001, 2019, p. 1-24. DOI: 10.1142/S0219198919400012] © World Scientific Publishing Company https://www.worldscientific.com/doi/10.1142/S0219198919400012, The aim of this work is to give a characterization of the Shapley–Shubik and the Banzhaf power indices for (3,2)-simple games. We generalize to the set of (3,2)-simple games the classical axioms for power indices on simple games: transfer, anonymity, null player property and efficiency. However, these four axioms are not enough to uniquely characterize the Shapley–Shubik index for (3,2)-simple games. Thus, we introduce a new axiom to prove the uniqueness of the extension of the Shapley–Shubik power index in this context. Moreover, we provide an analogous characterization for the Banzhaf index for (3,2)-simple games, generalizing the four axioms for simple games and adding another property., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Coalition formation and stability

  • Magaña Nieto, Antonio|||0000-0003-0879-0759
  • Carreras Escobar, Francisco|||0000-0002-7248-9912
This paper aims to develop, for any cooperative game, a solution notion that enjoys stability and consists of a coalition structure and an associated payoff vector derived from the Shapley value. To this end, two concepts are combined: those of strong Nash equilibrium and Aumann--Dr\`{e}ze coalitional value. In particular, we are interested in conditions ensuring that the grand coalition is the best preference for all players. Monotonicity, convexity, cohesiveness and other conditions are used to provide several theoretical results that we apply to numerical examples including real--world economic situations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Some properties for bisemivalues on bicooperative games

  • Domènech Blázquez, Margarita|||0000-0001-9237-7232
  • Giménez Pradales, José Miguel|||0000-0003-4754-194X
  • Puente del Campo, María Albina|||0000-0003-2732-9087
This is a post-peer-review, pre-copyedit version of an article published in Journal of Optimization Theory and Applications. The final authenticated version is available online at: http://dx.doi.org/10.1007%2Fs10957-020-01640-x., In this work, we focus on bicooperative games, a variation of the classic cooperative games, and investigate the conditions for the coefficients of the bisemivalues—a generalization of semivalues for cooperative games—necessary and / or sufficient in order to satisfy some properties, including among others, desirability relation, balanced contributions, null player exclusion property and block property. Moreover, a computational procedure to calculate bisemivalues in terms of the multilinear extension of the game is given., This research project was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P (MINECO/FEDER) and Grant SGR 2017–758 of the Catalonia Government (Generalitat de Catalunya)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A critical analysis on the notion of power

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
In this paper we discuss on several ways to extend power indices defined on simple games to the context of (j, 2)-games, i.e., games with 2 possible outputs and j possible input levels. The purpose of this paper is more conceptual than technical, and shows that different power indices can be obtained in (j, 2)-games depending on how the criticality of a player is measured. Some power indices for simple games, regarded as measures of power as payment, can be obtained from the selection of two items: (1) a probabilistic model, and (2) a collection of winning coalitions. The combination of two particular probabilistic models and three collections of winning coalitions lead to six well-known power indices for simple games. The Banzhaf and the Johnston power indices are among them. The main goal of the paper is to discuss the generalizations of these six power indices from (2, 2)-games to (j, 2)-games for j=3. The probabilistic model and the collection of winning coalitions are trivially extendable to (j, 2)-games. However, at least four possible ways of measuring the criticality of a player can be considered in this new context, and lead to different possible extensions of the six power indices to (j, 2)-games. We highlight two of them as being the most interesting under our point of view. The first one would be suitable for assessing sensitivity, because it measures the player’s ability to modify the output by a small change in his input level. The second one would be adequate to evaluate strength, because it measures the voter’s ability to modify the output by any change in his voting. The main conclusion is that different extensions of the considered power indices, as the Banzhaf and the Jonnston indices, are possible for j=3 and that they should be taken into account when working in a multiple input context., This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P(MINECO/FEDER)., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Using the multilinear extension to study some probabilistic power indices

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
The final publication is available at Springer via http://dx.doi.org/10.1007/s10726-016-9514-6, We consider binary voting systems modeled by a simple game, in which voters vote independently of each other, and the probability distribution over coalitions is known. The Owen’s multilinear extension of the simple game is used to improve the use and the computation of three indices defined in this model: the decisiveness index, which is an extension of the Banzhaf index, the success index, which is an extension of the Rae index, and the luckiness index. This approach leads us to prove new properties and inter-relations between these indices. In particular it is proved that the ordinal equivalence between success and decisiveness indices is achieved in any game if and only if the probability distribution is anonymous. In the anonymous case, the egalitarianism of the three indices is compared, and it is also proved that, for these distributions, decisiveness and success indices respect the strength of the seats, whereas luckiness reverses this order., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

An axiomatization for two power indices for (3,2)-simple games

  • Bernardi, Giulia
  • Freixas Bosch, Josep
Electronic version of an article published as International Game Theory Review, Vol. 21, Issue 1, 1940001, 2019, p. 1-24. DOI: 10.1142/S0219198919400012] © World Scientific Publishing Company https://www.worldscientific.com/doi/10.1142/S0219198919400012, The aim of this work is to give a characterization of the Shapley–Shubik and the Banzhaf power indices for (3,2)-simple games. We generalize to the set of (3,2)-simple games the classical axioms for power indices on simple games: transfer, anonymity, null player property and efficiency. However, these four axioms are not enough to uniquely characterize the Shapley–Shubik index for (3,2)-simple games. Thus, we introduce a new axiom to prove the uniqueness of the extension of the Shapley–Shubik power index in this context. Moreover, we provide an analogous characterization for the Banzhaf index for (3,2)-simple games, generalizing the four axioms for simple games and adding another property., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Semivalues: weighting coefficients and allocations on unanimity games

  • Domènech Blázquez, Margarita
  • Giménez Pradales, José Miguel
  • Puente del Campo, María Albina
This is a post-peer-review, pre-copyedit version of an article published in Optimization letters. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11590-017-1224-8., Each semivalue, as a solution concept defined on cooperative games with a finite set of players, is univocally determined by weighting coefficients that apply to players’ marginal contributions. Taking into account that a semivalue induces semivalues on lower cardinalities, we prove that its weighting coefficients can be reconstructed from the last weighting coefficients of its induced semivalues. Moreover, we provide the conditions of a sequence of numbers in order to be the family of the last coefficients of any induced semivalues. As a consequence of this fact, we give two characterizations of each semivalue defined on cooperative games with a finite set of players: one, among all semivalues; another, among all solution concepts on cooperative games., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Bounds for the Nakamura number

  • Freixas Bosch, Josep
  • Kurz, Sascha
This is a post-peer-review, pre-copyedit version of an article published in Social choice and welfare. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00355-018-1164-y., The Nakamura number is an appropriate invariant of a simple game to study the existence of social equilibria and the possibility of cycles. For symmetric (quota) games its number can be obtained by an easy formula. For some subclasses of simple games the corresponding Nakamura number has also been characterized. However, in general, not much is known about lower and upper bounds depending on invariants of simple, complete or weighted games. Here, we survey such results and highlight connections with other game theoretic concepts. © 2018, Springer-Verlag GmbH Germany, part of Springer Nature., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Decisiveness indices are semiindices: addendum

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
In the paper Decisiveness indices are semiindices (Freixas and Pons, 2016) it was shown that any decisiveness index obtained from an anonymous probability distribution is a semiindex, and that the converse is not true. In this note we characterize the semiindices which are indices of decisiveness., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Dimension and codimension of simple games

  • Kurz, Sascha
  • Molinero Albareda, Xavier
  • Olsen, Martin
  • Serna Iglesias, María José
This paper studies the complexity of computing a representation of a simple game as the intersection (union) of weighted majority games, as well as, the dimension or the codimension. We also present some examples with linear dimension and exponential codimension with respect to the number of players., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Centrality measure in social networks based on linear threshold model

  • Riquelme Csori, Fabian Rolando
  • Gonzalez Cantergiani, Pablo
  • Molinero Albareda, Xavier
  • Serna Iglesias, María José
Centrality and influence spread are two of the most studied concepts in social network analysis. In recent years, centrality measures have attracted the attention of many researchers, generating a large and varied number of new studies about social network analysis and its applications. However, as far as we know, traditional models of influence spread have not yet been exhaustively used to define centrality measures according to the influence criteria. Most of the considered work in this topic is based on the independent cascade model. In this paper we explore the possibilities of the linear threshold model for the definition of centrality measures to be used on weighted and labeled social networks. We propose a new centrality measure to rank the users of the network, the Linear Threshold Rank (LTR), and a centralization measure to determine to what extent the entire network has a centralized structure, the Linear Threshold Centralization (LTC). We appraise the viability of the approach through several case studies. We consider four different social networks to compare our new measures with two centrality measures based on relevance criteria and another centrality measure based on the independent cascade model. Our results show that our measures are useful for ranking actors and networks in a distinguishable way., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Dimension, egalitarianism and decisiveness of European voting systems

  • Carreras Escobar, Francisco
  • Freixas Bosch, Josep
  • Magaña Nieto, Antonio
An analysis of three major aspects has been carried out that may apply to any of the successive voting systems used for the European Union Council of Ministers, from the first one established in the Treaty of Rome in 1958 to the current one established in Lisbon. We mainly consider the voting systems designed for the enlarged European Union adopted in the Athens summit, held in April 2003 but this analysis can be applied to any other system. First, it is shown that the dimension of these voting systems does not, in general, reduce. Next, the egalitarian effects of superposing two or three weighted majority games (often by introducing additional consensus) are considered. Finally, the decisiveness of these voting systems is evaluated and compared., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication

A probabilistic unified approach for power indices in simple games

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
The final publication is available at Springer via https://doi.org/10.1007/978-3-662-60555-4_11, Many power indices on simple games have been defined trying to measure, under different points of view, the “a priori” importance of a voter in a collective binary voting scenario. A unified probabilistic way to define some of these power indices is considered in this paper. We show that six well-known power indices are obtained under such a probabilistic approach. Moreover, some new power indices can naturally be obtained in this way., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A critical analysis on the notion of power

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
In this paper we discuss on several ways to extend power indices defined on simple games to the context of (j, 2)-games, i.e., games with 2 possible outputs and j possible input levels. The purpose of this paper is more conceptual than technical, and shows that different power indices can be obtained in (j, 2)-games depending on how the criticality of a player is measured. Some power indices for simple games, regarded as measures of power as payment, can be obtained from the selection of two items: (1) a probabilistic model, and (2) a collection of winning coalitions. The combination of two particular probabilistic models and three collections of winning coalitions lead to six well-known power indices for simple games. The Banzhaf and the Johnston power indices are among them. The main goal of the paper is to discuss the generalizations of these six power indices from (2, 2)-games to (j, 2)-games for j=3. The probabilistic model and the collection of winning coalitions are trivially extendable to (j, 2)-games. However, at least four possible ways of measuring the criticality of a player can be considered in this new context, and lead to different possible extensions of the six power indices to (j, 2)-games. We highlight two of them as being the most interesting under our point of view. The first one would be suitable for assessing sensitivity, because it measures the player’s ability to modify the output by a small change in his input level. The second one would be adequate to evaluate strength, because it measures the voter’s ability to modify the output by any change in his voting. The main conclusion is that different extensions of the considered power indices, as the Banzhaf and the Jonnston indices, are possible for j=3 and that they should be taken into account when working in a multiple input context., This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P(MINECO/FEDER)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On the construction of high dimensional simple games

  • Olsen, Martin
  • Kurz, Sascha
  • Molinero Albareda, Xavier
Voting is a commonly applied method for the aggregation of the preferences of multiple agents into a joint decision. If preferences are binary, i.e., “yes” and “no”, every voting system can be described by a (monotone) Boolean function : f0; 1gn ! f0; 1g. However, its naive encoding needs 2n bits. The subclass of threshold functions, which is sufficient for homogeneous agents, allows a more succinct representation using n weights and one threshold. For heterogeneous agents one can represent as an intersection of k threshold functions. Taylor and Zwicker have constructed a sequence of examples requiring k 2 n2 ¿1 and provided a construction guaranteeingk ¿ n bn=2c 2 2n¿o(n). The magnitude of the worst case situation was thought to be determined by Elkind et al. in 2008, but the analysis unfortunately turned out to be wrong. Here we uncover a relation to coding theory that allows the determination of the minimum number k for a subclass of voting systems. As an application, we give a construction for k 2n¿o(n), i.e., there is no gain from a representation complexity point of view., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The Shapley value analyzed under the Felsenthal and Machover bargaining model

  • Bernardi, Giulia
  • Freixas Bosch, Josep
This is a post-peer-review, pre-copyedit version of an article published in Public choice. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11127-018-0560-2., In 1996, Felsenthal and Machover proposed a bargaining procedure for a valuable payoff in cooperative and simple games. They proved that the value underlying their bargaining scheme was the Shapley value by showing that it verifies the axioms that Shapley proposed for characterizing his value. They remarked that a direct proof of the result involves rather formidable combinatorial difficulties, but that it has some independent interest. In this paper, we prove such a combinatorial result and obtain a formula for the Shapley value that has a great potential to be extended to more general classes of games., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A characterization of weighted simple games based on pseudoweightings

  • Freixas Bosch, Josep
This is a post-peer-review, pre-copyedit version of an article published in Optimization letters. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11590-020-01647-3, The paper provides a new characterization of weighted games within the class of simple games. It is based on a stronger form of the point-set-additive pseudoweighting property of simple games. The characterization obtained is of interest in various research fields such as game theory, coherent structures, logic gates, operations research and Boolean algebra. A (monotonic) simple game corresponds to an inequivalent (monotonic) function in Boolean algebra and a weighted game corresponds to a threshold function. The characterization obtained provides a better understanding of these mathematical structures while opening new prospects for solving numerous open problems in these areas., This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015–66818-P(MINECO/FEDER)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Decisiveness indices are semiindices

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
In this note we prove that any decisiveness index, defined for any voter as the probability of him/her being decisive, is a semiindex when the probability distribution over coalitions is anonymous, and it is a semiindex with binomial coefficients when the probability over coalitions is anonymous and independent., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Influence decision models: from cooperative game theory to social network analysis

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
Cooperative game theory considers simple games and influence games as essential classes of games. A simple game can be viewed as a model of voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. An influence game is a cooperative game in which a team of players (or coalition) succeeds if it is able to convince sufficiently many agents to participate in a task. Furthermore, influence decision models allow to represent discrete system dynamics as graphs whose nodes are activated according to an influence spread model. It let us to depth in the social network analysis. All these concepts are applied to a wide variety of disciplines, such as social sciences, economics, marketing, cognitive sciences, political science, biology, computer science, among others. In this survey we present different advances in these topics, joint work with M. Serna. These advances include representations of simple games, the definition of influence games, and how to characterize different problems on influence games (measures, values, properties and problems for particular cases with respect to both the spread of influence and the structure of the graph). Moreover, we also present equivalent models to the simple games, the computation of satisfaction and power in collective decision-making models, and the definition of new centrality measures used for social network analysis. In addition, several interesting computational complexity results have been found., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A parameterization for a class of complete games with abstention

  • Freixas Bosch, Josep
  • Tchantcho, Bertrand
  • Tsague, Bill Procès
Voting games with abstention are voting systems in which players can cast not only yes and no vote, but are allowed to abstain. This paper centers on the structure of a class of complete games with abstention. We obtain, a parameterization that can be useful for enumerating these games, up to isomorphism. Indeed, any I-complete game is determined by a vector of matrices with non-negative integers entries. It also allows us determining whether a complete game with abstention is a strongly weighted (3, 2) game or not, and for other purposes of interest in game theory., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

An appropriate way to extend the Banzhaf index for multiple levels of approval

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
This is a post-peer-review, pre-copyedit version of an article published in Group decision and negotiation. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10726-020-09718-7., The Banzhaf power index for games admits several extensions if the players have more than two ordered voting options. In this paper we prove that the most intu-itive and recognized extension of the index fails to preserve the desirability rela-tion for games with more than three ordered input levels of approval, a failure that undermines the index to be a good measure of power. This leads us to think of an alternative to the Banzhaf index for several input levels of approval. We propose a candidate for which it is proved that: (1) coincides with the Banzhaf index for sim-ple games, (2) it is proportional to its known extension for three levels of approval, and (3) preserves the desirability relation regardless of the number of input levels of approval. This new index is based on measuring the total capacity the player has to alter the outcome. In addition, it can be expressed through a very appropriate mathematical formulation that greatly facilitates its computation. Defining exten-sions of well-established notions in a wider context requires a careful analysis. Dif-ferent extensions can provide complementary nuances and, when this occurs, none of them can be considered to be ‘the’ extension. As shown in this paper, this situa-tion applies when trying to extend the Banzhaf power index from simple games to the broader context of games with several ordered input levels of approval., This research was partially supported by funds from: the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P (MINECO/FEDER), and the Spanish Ministry of Science and Innovation grant PID2019-I04987GB-I00., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication

Preorders in simple games

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
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., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication

An equivalent formulation for the Shapley value

  • Freixas Bosch, Josep
The final authenticated version is available online at: https://doi.org/10.1007/978-3-662-58464-4_1., An equivalent explicit formula for the Shapley value is provided, its equivalence with the classical one is proven by double induction. The importance of this new formula, in contrast to the classical one, is its capability of being extended to more general classes of games, in particular to j-cooperative games or multichoice games, in which players choose among different levels of participation in the game., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Some properties for bisemivalues on bicooperative games

  • Domènech Blázquez, Margarita
  • Giménez Pradales, José Miguel
  • Puente del Campo, María Albina
This is a post-peer-review, pre-copyedit version of an article published in Journal of Optimization Theory and Applications. The final authenticated version is available online at: http://dx.doi.org/10.1007%2Fs10957-020-01640-x., In this work, we focus on bicooperative games, a variation of the classic cooperative games, and investigate the conditions for the coefficients of the bisemivalues—a generalization of semivalues for cooperative games—necessary and / or sufficient in order to satisfy some properties, including among others, desirability relation, balanced contributions, null player exclusion property and block property. Moreover, a computational procedure to calculate bisemivalues in terms of the multilinear extension of the game is given., This research project was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P (MINECO/FEDER) and Grant SGR 2017–758 of the Catalonia Government (Generalitat de Catalunya)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Combinatorial structures to modeling simple games and applications

  • Molinero Albareda, Xavier
We connect three different topics: combinatorial structures, game theory and chemistry. In particular, we establish the bases to represent some simple games, defined as influence games, and molecules, defined from atoms, by using combinatorial structures. First, we characterize simple games as influence games using influence graphs. It let us to modeling simple games as combinatorial structures (from the viewpoint of structures or graphs). Second, we formally define molecules as combinations of atoms. It let us to modeling molecules as combinatorial structures (from the viewpoint of combinations). It is open to generate such combinatorial structures using some specific techniques as genetic algorithms, (meta-)heuristics algorithms and parallel programming, among others., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Satisfaction and power in unanimous majority influence decision models

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
We consider decision models associated with cooperative influence games, the oblivious and the non-oblivious influence models. In those models the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures when the in uence level is set to unanimity and the rule of decision is simple majority. We show that computing the satisfaction and the power measure in those systems are #P-hard., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The Banzhaf value for cooperative and simple multichoice games

  • Freixas Bosch, Josep
This is a post-peer-review, pre-copyedit version of an article published in Group Decision and Negotiation. The final authenticated version is available online at: https://doi.org/10.1007/s10726-019-09651-4., This article proposes a value which can be considered an extension of the Banzhaf value for cooperative games. The proposed value is defined on the class of j-cooperative games, i.e., games in which players choose among a finite set of ordered actions and the result depends only on these elections. If the output is binary, only two options are available, then j-cooperative games become j-simple games. The restriction of the value to j-simple games leads to a power index that can be considered an extension of the Banzhaf power index for simple games. The paper provides an axiomatic characterization for the value and the index which is closely related to the first axiomatization of the Banzhaf value and Banzhaf power index in the respective contexts of cooperative and simple games., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Ability to separate situations with a priori coalition structures by means of symmetric solutions

  • Giménez Pradales, José Miguel
We say that two situations described by cooperative games are inseparable by a family of solutions, when they obtain the same allocation by all solution concept of this family. The situation of separability by a family of linear solutions reduces to separability from the null game. This is the case of the family of solutions based on marginal contributions weighted by coef¿cients only dependent of the coalition size: the semivalues. It is known that for games with four or more players, the spaces of inseparable games from the null game contain games different to zero-game. We will prove that for ¿ve or more players, when a priori coalition blocks are introduced in the situation described by the game, the dimension of the vector spaces of inseparable games from the null game decreases in an important manner., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Coalition formation and stability

  • Magaña Nieto, Antonio
  • Carreras Escobar, Francisco
This paper aims to develop, for any cooperative game, a solution notion that enjoys stability and consists of a coalition structure and an associated payoff vector derived from the Shapley value. To this end, two concepts are combined: those of strong Nash equilibrium and Aumann--Dr\`{e}ze coalitional value. In particular, we are interested in conditions ensuring that the grand coalition is the best preference for all players. Monotonicity, convexity, cohesiveness and other conditions are used to provide several theoretical results that we apply to numerical examples including real--world economic situations., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A note on multinomial probabilistic values

  • Carreras Escobar, Francisco
  • Puente del Campo, María Albina
This is a post-peer-review, pre-copyedit version of an article published in "TOP". The final authenticated version is available online at: https://doi.org/10.1007/s11750-017-0464-1, Multinomial values were previously introduced by one of the authors in reliability and extended later to all cooperative games. Here, we present for this subfamily of probabilistic values three new results, previously stated only for binomial semivalues in the literature. They concern the dimension of the subspace spanned by the multinomial values and two characterizations: one, individual, for each multinomial value; another, collective, for the whole subfamily they form. Finally, an application to simple games is provided, Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication

On the characterization of weighted simple games

  • Freixas Bosch, Josep
  • Freixas Boleda, Marc
  • Kurz, Sascha
The final publication is available at link.springer.com via http://dx.doi.org/10.1007/s11238-017-9606-z, This paper has a twofold scope. The first one is to clarify and put in evidence the isomorphic character of two theories developed in quite different fields: on one side, threshold logic, on the other side, simple games. One of the main purposes in both theories is to determine when a simple game is representable as a weighted game, which allows a very compact and easily comprehensible representation. Deep results were found in threshold logic in the sixties and seventies for this problem. However, game theory has taken the lead and some new results have been obtained for the problem in the past two decades. The second and main goal of this paper is to provide some new results on this problem and propose several open questions and conjectures for future research. The results we obtain depend on two significant parameters of the game: the number of types of equivalent players and the number of types of shift-minimal winning coalitions., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication

A value for j-cooperative games: some theoretical aspects and applications

  • Freixas Bosch, Josep
This is an Accepted Manuscript of a book chapter published by Routledge/CRC Press in Handbook of the Shapley value on December 6, 2019, available online: https://www.crcpress.com/Handbook-of-the-Shapley-Value/Algaba-Fragnelli-Sanchez-Soriano/p/book/9780815374688, A value that has all the ingredients to be a generalization of the Shapley value is proposed for a large class of games called j-cooperative games which are closely related to multi-choice games. When it is restricted to cooperative games, i.e. when j equals 2, it coincides with the Shapley value. An explicit formula in terms of some marginal contributions of the characteristic function is provided for the proposed value. Different arguments support it: (1) The value can be inferred from a natural probabilistic model. (2) An axiomatic characterization uniquely determines it. (3) The value is consistent in its particularization from j-cooperative games to j-simple games. This chapter also proposes various ways of calculating the value by giving an alternative expression that does not depend on the marginal contributions. This chapter shows how the technique of generating functions can be applied to determine such a value when the game is a weighted j-simple game. The chapter concludes by presenting several applications, among them the computation of the value for a proposed reform of the UNSC voting system., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The complexity of measuring power in generalized opinion leader decision models

  • Molinero Albareda, Xavier
  • Serna Iglesias, María José
We analyze the computational complexity of the power measure in models of collective decision: the generalized opinion leader-follower model and the oblivious and non-oblivious infuence models. We show that computing the power measure is #P-hard in all these models, and provide two subfamilies in which the power measure can be computed in polynomial time., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication

Measuring satisfaction in societies with opinion leaders and mediators

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
An opinion leader-follower model (OLF) is a two-action collective decision-making model for societies, in which three kinds of actors are considered:, Preprint