Laplacian dynamics on signed digraphs have a richer behavior than those on nonnegative digraphs. In particular, for the so-called “repelling” signed Laplacians, the marginal stability property (needed to achieve consensus) is not guaranteed a priori and, even when it holds, it does not automatically lead to consensus, as these signed Laplacians may lose rank even in strongly connected digraphs. Furthermore, in the time-varying case, instability can occur even when switching in a family of systems each of which corresponds to a marginally stable signed Laplacian with the correct corank. In this article, we present novel conditions for achieving consensus on signed digraphs based on the property of eventual positivity, a Perron–Frobenius (PF) type of property for signed matrices. The conditions we develop cover both time-invariant and time-varying cases. A particularly simple sufficient condition, valid in both cases, is that the Laplacians are normal matrices. Such condition can be relaxed in several ways. For instance, in the time-invariant case it is enough that the Laplacian has this PF property on the right side, but not on the left side (i.e., on the transpose). For the time-varying case, convergence to consensus can be guaranteed by the existence of a common Lyapunov function for all the signed Laplacians. All conditions can be easily extended to bipartite consensus.

In this article, we consider a collective decision-making process in a network of agents described by a nonlinear interconnected dynamical model with sigmoidal nonlinearities and signed interaction graph. The decisions are encoded in the equilibria of the system. The aim is to investigate this multiagent system when the signed graph representing the community is not structurally balanced and in particular as we vary its frustration, i.e., its distance to structural balance. The model exhibits bifurcations, and a "social effort" parameter, added to the model to represent the strength of the interactions between the agents, plays the role of bifurcation parameter in our analysis. We show that, as the social effort increases, the decision-making dynamics exhibit a pitchfork bifurcation behavior where, from a deadlock situation of "no decision" (i.e., the origin is the only globally stable equilibrium point), two possible (alternative) decision states for the community are achieved (corresponding to two nonzero locally stable equilibria). The value of social effort for which the bifurcation is crossed (and a decision is reached) increases with the frustration of the signed network.

Collective decision-making refers to a process in which the agents of a community exchange opinions with the objective of reaching a common decision. It is often assumed that a collective decision is reached through collaboration among the individuals. However in many contexts, concerning for instance collective human behavior, it is more realistic to assume that the agents can collaborate or compete with each other. In this case, different types of collective behavior can be observed. This thesis investigates collective decision-making problems in multiagent systems, both in the case of collaborative and of antagonistic interactions.

The first problem studied in the thesis is a special instance of the consensus problem, denoted "interval consensus" in this work. It consists in letting the agents impose constraints on the possible common consensus value. It is shown that introducing saturated nonlinearities in the decision-making dynamics to describe how the agents express their opinions effectively allows the agents to influence the achievable consensus value and steer it to the intersection of all the intervals imposed by the agents. 

A second class of collective decision-making models discussed in the thesis is obtained by replacing the saturations with sigmoidal nonlinearities. This nonlinear interconnected model is first investigated in the collaborative case and then in the antagonistic case, represented as a signed graph of interactions. In both cases, it is shown that the behavior of the model can be described by means of bifurcation analysis, with the equilibria of the system encoding the possible decisions for the community. A scalar positive parameter, denoted "social effort", is added to the model to represent the strength of commitment between the agents, and plays the role of bifurcation parameter in the analysis. It is shown that if the social effort is small, then the community is in a deadlock situation (i.e., no decision is taken), while if the agents have the "right" amount of commitment two alternative consensus decision states for the community are achieved. However, by further increasing the social effort, the agents may fall in a situation of "overcommitment" where multiple (more than 2) decisions are possible. When antagonistic interactions between the agents are taken into account, they may lead to conflicts or social tensions during the decision-making process, which can be quantified by the notion of "frustration" of the signed network representing the community. The aim is to understand how the presence of antagonism (represented by the amount of frustration of the signed network) influences the collective decision-making process. It is shown that, while the qualitative behavior of the system does not change, the value of social effort required from the agents to break the deadlock (i.e., the value for which the bifurcation is crossed) increases with the frustration of the signed network: the higher the frustration, the higher the required social commitment.

A natural context to apply these results is that of political decision-making. In particular it is shown in the thesis how the government formation process in parliamentary democracies can be modeled as a collective decision-making system, where the agents are the parliamentary members, the decision is the vote of confidence they cast to a candidate cabinet coalition, and the social effort parameter is a proxy for the duration of the government negotiation talks. A signed network captures the alliances/rivalries between the political parties in the parliament. The idea is that the frustration of the parliamentary networks should correlate well with the duration of the government negotiation, and it is supported by the analysis of the legislative elections in 29 European countries in the last 40 years. 

The final contribution of this thesis is an analysis of the structure of (signed) Laplacian matrices and of their pseudoinverses. It is shown that the pseudoinverse of a Laplacian is in general a signed Laplacian, and in particular that the set of eventually exponentially positive Laplacian matrices (i.e., matrices whose exponential is a matrix with negative entries which becomes and stays positive at a certain power) is closed under stability and matrix pseudoinversion.

The pseudoinverse of a graph Laplacian is used in many applications and fields, such as for instance in the computation of the effective resistance in electrical networks, in the calculation of the hitting/commuting times for a Markov chain and in continuous-time distributed averaging problems. In this paper we show that the Laplacian pseudoinverse is in general not a Laplacian matrix but rather a signed Laplacian with the property of being an eventually exponentially positive matrix, i.e., of obeying a strong Perron-Frobenius property. We show further that the set of signed Laplacians with this structure (i.e., eventual exponential positivity) is closed with respect to matrix pseudoinversion. This is true even for signed digraphs, and provided that we restrict to Laplacians that are weight balanced also stability is guaranteed.

The models of collective decision-making considered in this paper are nonlinear interconnected cooperative systems with saturating interactions. These systems encode the possible outcomes of a decision process into different steady states of the dynamics. In particular, they are characterized by two main attractors in the positive and negative orthant, representing two choices of agreement among the agents, associated to the Perron-Frobenius eigenvector of the system. In this paper we give conditions for the appearance of other equilibria of mixed sign. The conditions are inspired by Perron-Frobenius theory and are related to the algebraic connectivity of the network. We also show how all these equilibria must be contained in a solid disk of radius given by the norm of the equilibrium point which is located in the positive orthant.

In this paper we provide necessary conditions for the existence of multiple equilibrium points for a class of non-linear cooperative networked systems with saturating interactions which describe models of collective decision-making. The multiple steady states of the dynamics represent the possible outcomes of a decision process, and, except for one positive and one negative, have all mixed signs. The conditions we obtain can be formulated in terms of the algebraic connectivity of the network and are inspired by Perron-Frobenius arguments. It is also shown that the mixed-sign equilibria are contained in a ball of radius given by the norm of the positive equilibrium point and centered in the origin. Numerical examples are given to illustrate the results.