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): 6
Encontrada(s) 1 página(s)

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 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
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 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 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)