liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Collective decision-making on networked systems in presence of antagonistic interactions
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-6367-6302
2021 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2021. , p. 49
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 2166
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:liu:diva-178301DOI: 10.3384/diss.diva-178301ISBN: 9789179290177 (print)OAI: oai:DiVA.org:liu-178301DiVA, id: diva2:1585664
Public defence
2021-09-24, Online through Zoom (contact ninna.stensgard@liu.se) and Ada Lovelace, B Building, Campus Valla, Linköping, 10:15 (English)
Opponent
Supervisors
Funder
Swedish Research Council, 2015-04390Available from: 2021-08-27 Created: 2021-08-17 Last updated: 2021-10-01Bibliographically approved
List of papers
1. Interval Consensus for Multiagent Networks
Open this publication in new window or tab >>Interval Consensus for Multiagent Networks
2020 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 65, no 5, p. 1855-1869Article in journal (Refereed) Published
Abstract [en]

The constrained consensus problem considered in this paper, denoted interval consensus, is characterized by the fact that each agent can impose a lower and upper bound on the achievable consensus value. Such constraints can be encoded in the consensus dynamics by saturating the values that an agent transmits to its neighboring nodes. We show in the paper that when the intersection of the intervals imposed by the agents is nonempty, the resulting constrained consensus problem must converge to a common value inside that intersection. In our algorithm, convergence happens in a fully distributed manner, and without need of sharing any information on the individual constraining intervals. When the intersection of the intervals is an empty set, the intrinsic nonlinearity of the network dynamics raises new challenges in understanding the node state evolution. Using Brouwer fixed-point theorem we prove that in that case there exists at least one equilibrium, and in fact the possible equilibria are locally stable if the constraints are satisfied or dissatisfied at the same time among all nodes. For graphs with sufficient sparsity it is further proven that there is a unique equilibrium that is globally attractive if the constraint intervals are pairwise disjoint.

Place, publisher, year, edition, pages
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2020
Keywords
Consensus; multiagent systems; nonlinear cooperative systems; saturation constraints
National Category
Communication Systems
Identifiers
urn:nbn:se:liu:diva-165932 (URN)10.1109/TAC.2019.2924131 (DOI)000530344600003 ()
Note

Funding Agencies|Swedish Research CouncilSwedish Research Council [2015-04390]

Available from: 2020-06-04 Created: 2020-06-04 Last updated: 2021-08-17
2. Multiequilibria analysis for a class of collective decision-making networked systems
Open this publication in new window or tab >>Multiequilibria analysis for a class of collective decision-making networked systems
2018 (English)In: IEEE Transactions on Control of Network Systems, E-ISSN 2325-5870, no 4, p. 1931-1940Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Symmetric matrices;Eigenvalues and eigenfunctions;Bifurcation;Neural networks;Decision making;Control systems;Cooperative systems;Collective decision-making;nonlinear cooperative systems;multiple equilibria;Perron-Frobenius theorem;algebraic connectivity
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-151688 (URN)10.1109/TCNS.2017.2774014 (DOI)000454245200038 ()
Note

Funding Agencies|Swedish Research Council [2015-04390]

Available from: 2018-10-02 Created: 2018-10-02 Last updated: 2022-05-11
3. The role of frustration in collective decision-making dynamical processes on multiagent signed networks
Open this publication in new window or tab >>The role of frustration in collective decision-making dynamical processes on multiagent signed networks
2022 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 67, no 10, p. 5191-5206Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2022
Keywords
Bifurcation; Decision making; Social networking (online); Laplace equations; Eigenvalues and eigenfunctions; Symmetric matrices; Labeling; Bifurcation; multiagent systems; nonlinear (non)monotone systems; signed networks
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-179722 (URN)10.1109/TAC.2021.3123222 (DOI)000861438100015 ()
Funder
Swedish Research Council, 2015-04390
Note

Funding Agencies|Swedish Research Council [2015-04390]

Available from: 2021-09-30 Created: 2021-09-30 Last updated: 2023-01-13
4. A signed network perspective on the government formation process in parliamentary democracies
Open this publication in new window or tab >>A signed network perspective on the government formation process in parliamentary democracies
2021 (English)In: Scientific Reports, E-ISSN 2045-2322, Vol. 11, no 1, article id 5134Article in journal (Refereed) Published
Abstract [en]

In parliamentary democracies, government negotiations talks following a general election can sometimes be a long and laborious process. In order to explain this phenomenon, in this paper we use structural balance theory to represent a multiparty parliament as a signed network, with edge signs representing alliances and rivalries among parties. We show that the notion of frustration, which quantifies the amount of "disorder" encoded in the signed graph, correlates very well with the duration of the government negotiation talks. For the 29 European countries considered in this study, the average correlation between frustration and government negotiation talks ranges between 0.42 and 0.69, depending on what information is included in the edges of the signed network. Dynamical models of collective decision-making over signed networks with varying frustration are proposed to explain this correlation.

Place, publisher, year, edition, pages
Nature Research, 2021
National Category
Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-175090 (URN)10.1038/s41598-021-84147-3 (DOI)000626139000024 ()33664333 (PubMedID)
Note

Funding Agencies|Linkoping University; Swedish Research CouncilSwedish Research CouncilEuropean Commission [2015-04390]

Available from: 2021-04-21 Created: 2021-04-21 Last updated: 2022-09-15Bibliographically approved
5. On the properties of Laplacian pseudoinverses
Open this publication in new window or tab >>On the properties of Laplacian pseudoinverses
2021 (English)In: 2021 IEEE 60th Conference on Decision and Control (CDC), IEEE, 2021, p. 5538-5543Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
IEEE, 2021
Series
IEEE Conference on Decision and Control (CDC)
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-178347 (URN)10.1109/CDC45484.2021.9683525 (DOI)000781990304136 ()9781665436595 (ISBN)
Conference
IEEE 60th Conference on Decision and Control (CDC), December 13-15, 2021, Austin, Texas, USA
Funder
Swedish Research Council, 2020-03701ELLIIT - The Linköping‐Lund Initiative on IT and Mobile Communications
Available from: 2021-08-18 Created: 2021-08-18 Last updated: 2024-02-01

Open Access in DiVA

fulltext(4141 kB)436 downloads
File information
File name FULLTEXT01.pdfFile size 4141 kBChecksum SHA-512
b323b6960c7bf94626198be2aac9332b68074d45deb36e4d0e5e797c0d9b22cf0385f4f76b55515464ec6934f627b7dcd7de66642b0c9a6d341b6e0b21bee51c
Type fulltextMimetype application/pdf
Order online >>

Other links

Publisher's full text

Authority records

Fontan, Angela

Search in DiVA

By author/editor
Fontan, Angela
By organisation
Automatic ControlFaculty of Science & Engineering
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 436 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 1084 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf