Knowledge-based systems

Vol. 174, p. 144-159

DOI: 10.1016/j.knosys.2019.03.005

Date of publication: 2019-06-15

Abstract:

We introduce collective decision-making models associated with influence spread under the linear threshold model in social networks. We define the oblivious and the non-oblivious influence models. We also introduce the generalized opinion leader–follower model (gOLF) as an extension of the opinion leader–follower model (OLF) proposed by van den Brink et al. (2011). In our model we allow rules for the final decision different from the simple majority used in OLF. We show that gOLF models are non-oblivious influence models on a two-layered bipartite influence digraph. Together with OLF models, the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures for the decision models introduced in the paper. We show that the problem of computing the satisfaction or the power measure is #P-hard in all the introduced models even when the subjacent social network is a bipartite graph. Complementing this result, we provide two subfamilies of decision models in which both measures can be computed in polynomial time. We show that the collective decision functions are monotone and therefore they define an associated simple game. We relate the satisfaction and the power measures with the Rae index and the Banzhaf value of an associated simple game. This will allow the use of known approximation methods for computing the Banzhaf value, or the Rae index to their practical computation.]]>

European Conference on Operational Research

p. 110

Presentation's date: 2018-07-02

Abstract:

An influence game is a cooperative simple game in which a coalition of the players wins if it is able to convince enough agents to participate in the task (to vote in favor of a decision). In this vein, the linear threshold model is taken as the influence model. It is known that influence games capture the class of simple games. Influence games (as simple games) are monotonic. Now, we present some new classes of influence games under some connectivity restrictions over winning coalitions. These classes of influence games are not necessary monotonic. We characterize the computational complexity of problems on influence games over these new classes, including measures (length and width), values (Shapley-Shubik and Banzhaf) and properties (of teams and players). We also analyze those problems for some particular extremal cases, with respect to the propagation of influence.]]>

Electronic notes in discrete mathematics

Vol. 68, p. 197-202

DOI: 10.1016/j.endm.2018.06.034

Date of publication: 2018-07

Abstract:

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.]]>

International Colloquium on Automata, Languages, and Programming

p. 1-14

DOI: 10.4230/LIPIcs.ICALP.2018.116

Presentation's date: 2018-06-09

Abstract:

We show that for no surface except for the plane does monadic second-order logic (MSO) have a zero-one-law - and not even a convergence law - on the class of (connected) graphs embeddable on the surface. In addition we show that every rational in [0,1] is the limiting probability of some MSO formula. This strongly refutes a conjecture by Heinig et al. (2014) who proved a convergence law for planar graphs, and a zero-one law for connected planar graphs, and also identified the so-called gaps of [0,1]: the subintervals that are not limiting probabilities of any MSO formula. The proof relies on a combination of methods from structural graph theory, especially large face-width embeddings of graphs on surfaces, analytic combinatorics, and finite model theory, and several parts of the proof may be of independent interest. In particular, we identify precisely the properties that make the zero-one law work on planar graphs but fail for every other surface.]]>

Balkan Conference on Operational Research

p. B6

Presentation's date: 2018-05-27

Abstract:

Given n players, a simple game is a 0/1 valued TU cooperative game verifying unanimity and monotonicity. In such a game, a coalition, i.e., a subset of players, always wins (winning coalition) or loses (losing coalition). It is known that each simple simple can be expressed as the intersection (or the union) of weighted voting games. A simple game is called weighted voting (majority) game if there is a quote q and an assignment of a non-negative integer weight to each player in such a way that a coalition is winning if and only if the sum of the weights of its players is greater than or equal to the integer quota q. Two important and well studied concepts relating simple games with weighted games are the dimension and the codimension. The dimension is the minimum number of weighted games such that their intersections generate the considered simple game. In the same vein, the codimension is the minimum number of weighted games such that their unions generate the considered simple game. There are some previous studies about the dimension and the codimension of simple games. Nevertheless no complete classification of dimension or codimension of simple games is known even for small number of players. In this work we initiate a systematic such classification with respect to the dimension and the codimension parameters. We introduce the concept of multidimension of a simple game, the minimum number of intersections and unions of weighted games to generate the considered simple game. A similar concept was introduced in another topic (Boolean functions) by Goldberg. We also classify some simple games with respect to their multidimension. Moreover, we present some particular results of the dimension, the codimension and the multidimension for specific simple games depending on properties of the (minimal) winning coalitions. Finally, we study possible relations between k-trade robustness and k-invarinat-trade robustness (concepts that characterize the subclass of simple games called complete simple games) with respect to the dimension, the codimension and the multidimension.]]>

Knowledge-based systems

Vol. 140, p. 92-102

DOI: 10.1016/j.knosys.2017.10.029

Date of publication: 2018-01-15

Abstract:

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.]]>

Electronic notes in discrete mathematics

Vol. 55, p. 147-150

DOI: 10.1016/j.endm.2016.10.037

Date of publication: 2016-11-01

Abstract:

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.]]>

Electronic notes in discrete mathematics

Vol. 54, p. 205-210

DOI: 10.1016/j.endm.2016.09.036

Date of publication: 2016-10

Abstract:

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.]]>

Advances in applied probability

Vol. 48, num. 3, p. 848-864

DOI: 10.1017/apr.2016.31

Date of publication: 2016-09-01

Abstract:

Given any two vertices u, v of a random geometric graph G(n, r), denote by dE(u, v) their Euclidean distance and by dE(u, v) their graph distance. The problem of finding upper bounds on dG(u, v) conditional on dE(u, v) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper we improve the known upper bounds for values of r=¿(vlogn) (that is, for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on dE(u, v) conditional on dE(u, v).]]>

European Conference on Operational Research

p. 160-

Presentation's date: 2016-07

Abstract:

We consider two collective decision-making models associated with influence games [2], the oblivious and non-oblivious influence decision models. The difference is that in oblivious influence models the initial decision of the actors that are neither leaders nor independent is never taken into account, while in the non-oblivious it is taken when the leaders cannot exert enough influence to deviate from it. Following [1] we consider the power measure, for an actor in a decision-making model. Power is ascribed to an actor when, by changing its inclination, the collective decision can be changed. We show that computing the power measure is #P-hard in both oblivious and non-oblivious influence decision models. We present two subfamilies of (oblivious and non-oblivious) influence decision models in which the power measure can be computed in polynomial time.]]>

Discrete Mathematics Days

p. 21-

Presentation's date: 2016-07

Abstract:

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 in uence 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.]]>

Cologne Twente Workshop

p. 153-156

Presentation's date: 2016-06

Abstract:

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.]]>

Date: 2016-05-14

Abstract:

An opinion leader-follower model (OLF) is a two-action collective decision-making model for societies, in which three kinds of actors are considered: "opinion leaders", "followers", and "independent actors". In OLF the initial decision of the followers can be modified by the influence of the leaders. Once the final decision is set, a collective decision is taken applying the simple majority rule. We consider a generalization of \OLF, the gOLF models which allow collective decision taken by rules different from the single majority rule. Inspired in this model we define two new families of collective decision-making models associated with cooperative influence games. We define the "oblivious" and "non-oblivious" influence models. We show that gOLF models are non-oblivious influence models played on a two layered bipartite influence graph. Together with OLF models, the Satisfaction measure was introduced and studied. We analyze the computational complexity of the satisfaction measure for gOLF models and the other collective decision-making models introduced in the paper. We show that computing the satisfaction measure is #P-hard in all the considered models except for the basic OLF inwhich the complexity remains open. On the other hand, we provide two subfamilies of decision models in which the satisfaction measure can be computed in polynomial time. Exploiting the relationship with influence games, we can relate the satisfaction measure with the Rae index of an associated simple game. The Rae index is closely related to the Banzhaf value. Thus, our results also extend the families of simple games for which computing the Rae index and the Banzhaf value is computationally hard.

An opinion leader-follower model (OLF) is a two-action collective decision-making model for societies, in which three kinds of actors are considered:]]>

DOI: arxiv.org/abs/1602.04328

Date: 2016-02-13

Abstract:

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.]]>

Information processing letters

Vol. 116, num. 6, p. 437-441

DOI: 10.1016/j.ipl.2016.01.004

Date of publication: 2016-02-04

Abstract:

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.]]>