Collective decision-making on networked systems in presence of antagonistic interactions

Sammanfattning: 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.