The Complexity of Measuring Power in Generalized Opinion Leader Decision Models

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 influence models. We show that computing the power measure is #P-hard in all these models, and provide two subfamilies in w...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2016-10, Vol.54, p.205-210
Main Authors: Molinero, Xavier, Serna, Maria
Format: Article
Language:English
Subjects:
33 Special functions
33F Computational aspects
Classificació AMS
Complexitat computacional
Computational complexity
Decision-making
Decision-making models
Decisió, Presa de
Investigació operativa
Matemàtiques i estadística
Models matemàtics
Power measure
Teoria de jocs
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 influence 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.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2016.09.036