Pasar al contenido principal

TEORIA DE JUEGOS: FUNDAMENTOS MATEMATICOS Y APLICACIONES

MTM2012-34426

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2012
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Secretaría de Estado de Investigación, Desarrollo e Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The cost of getting local monotonicity

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Kurz, Sascha
Committees with yes-no-decisions are commonly modeled as simple games and the ability of a member to influence the group decision is measured by so-called power indices. For a weighted game we say that a power index satisfies local monotonicity if a player who controls a large share of the total weight vote does not have less power than a player with a smaller voting weight. In (Holler, 1982) Manfred Holler introduced the Public Good index. In its unnormalized version, i.e., the raw measure, it counts the number of times that a player belongs to a minimal winning coalition. Unlike the Banzhaf index, it does not count the remaining winning coalitions in which the player is crucial. Holler noticed that his index does not satisfy local monotonicity, a fact that can be seen either as a major drawback (Felsenthal & Machover, 1998, 221 ff.)or as an advantage (Holler & Napel 2004). In this paper we consider a convex combination of the two indices and require the validity of local monotonicity. We prove that the cost of obtaining it is high, i.e., the achievable new indices satisfying local monotonicity are closer to the Banzhaf index than to the Public Good index. All these achievable new indices are more solidary than the Banzhaf index, which makes them as very suitable candidates to divide a public good. As a generalization we consider convex combinations of either: the Shift index, the Public Good index, and the Banzhaf index, or alternatively: the Shift Deegan-Packel, Deegan-Packel, and Johnston indices., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Components with higher and lower risk in a reliability system

  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
A new reliability importance measure for components in a system, that we call Representativeness measure, is introduced. It evaluates to which extent the performance of a component is representative of the erformance of the whole system. Its relationship with Birnbaum’s measure is analyzed, and the ranking of components given by both measures are compared. These rankings happen to be equal when all components have the same reliability but different in general. In contrast with Birnbaum’s, the Representativeness reliability importance measure of a component does depend on its reliability., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Unranking algorithms for combinatorial structures

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Vives Pons, Jordi|||0000-0002-1931-8495
We present an implementation of some unlabeled and labeled unranking algorithms for the open-source algebraic combinatorics package MUPAD-COMBINAT of the computer algebra system MUPAD. We have compared our implementation with the previous versions. All our algorithms improve the previous ones with respect to the required CPU time. Moreover, we have also developed unranking algorithms applied to some unlabeled and labeled admissible operators that are not still implemented in the package MUPAD-COMBINAT. These algorithms are also able to develop some combinatorial structures useful to generate molecules applied to chemistry and influence graphs applied to game theory and social networks, among other topics., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the complexity of exchanging

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Olsen, Martin
  • Serna Iglesias, María José|||0000-0001-9729-8648
We analyze the computational complexity of the problem of deciding whether, for a given simple game, there exists the possibility of rearranging the participants in a set of j given losing coalitions into a set of j winning coalitions. We also look at the problem of turning winning coalitions into losing coalitions. We analyze the problem when the simple game is represented by a list of wining, losing, minimal winning or maximal loosing coalitions., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Forms of representation for simple games: sizes, conversions and equivalences

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Some properties for probabilistic and multinomial (probabilistic) values on cooperative 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 an Accepted Manuscript of an article published by Taylor & Francis in Optimization on 18-02-2016, available online: http://www.tandfonline.com/10.1080/02331934.2016.1147035., We investigate the conditions for the coefficients of probabilistic and multinomial values of cooperative games necessary and/or sufficient in order to satisfy some properties, including marginal contributions, balanced contributions, desirability relation and null player exclusion property. Moreover, a similar analysis is conducted for transfer property of probabilistic power indices on the domain of simple games., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Cooperation through social influence

  • 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 a simple and altruistic multiagent system in which the agents are eager to perform a collective task but where their real engagement depends on the willingness to perform the task of other influential agents. We model this scenario by an influence game, a cooperative simple game in which a team (or coalition) of players succeeds if it is able to convince enough agents to participate in the task (to vote in favor of a decision). We take the linear threshold model as the influence model. We show first the expressiveness of influence games showing that they capture the class of simple games. Then we characterize the computational complexity of various problems on influence games, including measures (length and width), values (Shapley-Shubik and Banzhaf) and properties (of teams and players). Finally, we analyze those problems for some particular extremal cases, with respect to the propagation of influence, showing tighter complexity characterizations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Pure bargaining problems with a coalition structure

  • Carreras Escobar, Francisco|||0000-0002-7248-9912
  • Owen Salazar, Guillermo
The final publication is available at Springer via http://dx.doi.org/10.1007/s41412-016-0007-2, We consider here pure bargaining problems endowed with a coalition structure such that each union is given its own utility. In this context we use the Shapley rule in order to assess the main options available to the agents: individual behavior, cooperative behavior, isolated unions behavior, and bargaining unions behavior. The latter two respectively recall the treatment given by Aumann–Drèze and Owen to cooperative games with a coalition structure. A numerical example illustrates the procedure. We provide criteria to compare any pair of behaviors for each agent, introduce and axiomatically characterize a modified Shapley rule, and determine its natural domain, that is, the set of problems where the bargaining unions behavior is the best option for all agents., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Measuring the relevance of factors in the occurrence of events

  • Fragnelli, Vito
  • Freixas Bosch, Josep|||0000-0002-9033-9432
  • Pons Vallès, Montserrat|||0000-0003-1592-0347
  • Sanmiquel Pera, Lluís|||0000-0001-5612-4713
The final publication is available at Springer via http://dx.doi.org/10.1007/s10100-014-0352-9., A new way to compare the relevance of the different factors intervening in the occurrences of an event is presented and developed in this paper. The idea behind the method comes from cooperative game theory but the focus is slightly different because factors are not necessarily rational decision-makers and because the only data available are obtained by repetition of the event. The concept of relevance measure for a factor in a set of data is introduced, some significant examples are given and the main properties of relevance measures are defined and studied. One of these measures, the fair measure, is proved to have interesting properties which characterize it. Two real world situations, one about traffic accidents and the other one about mining accidents, both of them with real data, are used to show the use of relevance measures to compare factors in each one of these events., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Pure bargaining problems with a coalition structure

  • Carreras Escobar, Francisco
  • Owen Salazar, Guillermo
The final publication is available at Springer via http://dx.doi.org/10.1007/s41412-016-0007-2, We consider here pure bargaining problems endowed with a coalition structure such that each union is given its own utility. In this context we use the Shapley rule in order to assess the main options available to the agents: individual behavior, cooperative behavior, isolated unions behavior, and bargaining unions behavior. The latter two respectively recall the treatment given by Aumann–Drèze and Owen to cooperative games with a coalition structure. A numerical example illustrates the procedure. We provide criteria to compare any pair of behaviors for each agent, introduce and axiomatically characterize a modified Shapley rule, and determine its natural domain, that is, the set of problems where the bargaining unions behavior is the best option for all agents., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The cost of getting local monotonicity

  • Freixas Bosch, Josep
  • Kurz, Sascha
Committees with yes-no-decisions are commonly modeled as simple games and the ability of a member to influence the group decision is measured by so-called power indices. For a weighted game we say that a power index satisfies local monotonicity if a player who controls a large share of the total weight vote does not have less power than a player with a smaller voting weight. In (Holler, 1982) Manfred Holler introduced the Public Good index. In its unnormalized version, i.e., the raw measure, it counts the number of times that a player belongs to a minimal winning coalition. Unlike the Banzhaf index, it does not count the remaining winning coalitions in which the player is crucial. Holler noticed that his index does not satisfy local monotonicity, a fact that can be seen either as a major drawback (Felsenthal & Machover, 1998, 221 ff.)or as an advantage (Holler & Napel 2004). In this paper we consider a convex combination of the two indices and require the validity of local monotonicity. We prove that the cost of obtaining it is high, i.e., the achievable new indices satisfying local monotonicity are closer to the Banzhaf index than to the Public Good index. All these achievable new indices are more solidary than the Banzhaf index, which makes them as very suitable candidates to divide a public good. As a generalization we consider convex combinations of either: the Shift index, the Public Good index, and the Banzhaf index, or alternatively: the Shift Deegan-Packel, Deegan-Packel, and Johnston indices., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Measuring the relevance of factors in the occurrence of events

  • Fragnelli, Vito
  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
  • Sanmiquel Pera, Lluís
The final publication is available at Springer via http://dx.doi.org/10.1007/s10100-014-0352-9., A new way to compare the relevance of the different factors intervening in the occurrences of an event is presented and developed in this paper. The idea behind the method comes from cooperative game theory but the focus is slightly different because factors are not necessarily rational decision-makers and because the only data available are obtained by repetition of the event. The concept of relevance measure for a factor in a set of data is introduced, some significant examples are given and the main properties of relevance measures are defined and studied. One of these measures, the fair measure, is proved to have interesting properties which characterize it. Two real world situations, one about traffic accidents and the other one about mining accidents, both of them with real data, are used to show the use of relevance measures to compare factors in each one of these events., Peer Reviewed, Postprint (author’s final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Forms of representation for simple games: sizes, conversions and equivalences

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems., Peer Reviewed, Postprint (author’s final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Cooperation through social influence

  • Molinero Albareda, Xavier
  • Riquelme Csori, Fabian Rolando
  • Serna Iglesias, María José
We consider a simple and altruistic multiagent system in which the agents are eager to perform a collective task but where their real engagement depends on the willingness to perform the task of other influential agents. We model this scenario by an influence game, a cooperative simple game in which a team (or coalition) of players succeeds if it is able to convince enough agents to participate in the task (to vote in favor of a decision). We take the linear threshold model as the influence model. We show first the expressiveness of influence games showing that they capture the class of simple games. Then we characterize the computational complexity of various problems on influence games, including measures (length and width), values (Shapley-Shubik and Banzhaf) and properties (of teams and players). Finally, we analyze those problems for some particular extremal cases, with respect to the propagation of influence, showing tighter complexity characterizations., Peer Reviewed, Postprint (author’s final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the complexity of exchanging

  • Molinero Albareda, Xavier
  • Olsen, Martin
  • Serna Iglesias, María José
We analyze the computational complexity of the problem of deciding whether, for a given simple game, there exists the possibility of rearranging the participants in a set of j given losing coalitions into a set of j winning coalitions. We also look at the problem of turning winning coalitions into losing coalitions. We analyze the problem when the simple game is represented by a list of wining, losing, minimal winning or maximal loosing coalitions., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Unranking algorithms for combinatorial structures

  • Molinero Albareda, Xavier
  • Vives Pons, Jordi
We present an implementation of some unlabeled and labeled unranking algorithms for the open-source algebraic combinatorics package MUPAD-COMBINAT of the computer algebra system MUPAD. We have compared our implementation with the previous versions. All our algorithms improve the previous ones with respect to the required CPU time. Moreover, we have also developed unranking algorithms applied to some unlabeled and labeled admissible operators that are not still implemented in the package MUPAD-COMBINAT. These algorithms are also able to develop some combinatorial structures useful to generate molecules applied to chemistry and influence graphs applied to game theory and social networks, among other topics., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Components with higher and lower risk in a reliability system

  • Freixas Bosch, Josep
  • Pons Vallès, Montserrat
A new reliability importance measure for components in a system, that we call Representativeness measure, is introduced. It evaluates to which extent the performance of a component is representative of the erformance of the whole system. Its relationship with Birnbaum’s measure is analyzed, and the ranking of components given by both measures are compared. These rankings happen to be equal when all components have the same reliability but different in general. In contrast with Birnbaum’s, the Representativeness reliability importance measure of a component does depend on its reliability., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Some properties for probabilistic and multinomial (probabilistic) values on cooperative games

  • Domènech Blázquez, Margarita
  • Giménez Pradales, José Miguel
  • Puente del Campo, María Albina
This is an Accepted Manuscript of an article published by Taylor & Francis in Optimization on 18-02-2016, available online: http://www.tandfonline.com/10.1080/02331934.2016.1147035., We investigate the conditions for the coefficients of probabilistic and multinomial values of cooperative games necessary and/or sufficient in order to satisfy some properties, including marginal contributions, balanced contributions, desirability relation and null player exclusion property. Moreover, a similar analysis is conducted for transfer property of probabilistic power indices on the domain of simple games., Peer Reviewed, Postprint (author's final draft)