Models of Influence and Network Theory – MINT

The research is interdisciplinary, theoretical, applied, empirical and experimental, and concerns items from Social Choice Theory and Political Science (Coalition Formation, Elections), Game Theory (Cooperative Game Theory, Power and Influence Indices, Bargaining, Network Formation, Communication Networks and Hierarchies), and Computer Science (Social Software, Algorithms). The main objective of our research is to design concrete fair procedures for network and coalition formation, and to develop fair measures of agents' strength in networks, that can model different kinds of social, economic and political situations, and can be applied to many organizations. The project essentially consists of three parts, related to each other: Models of Network and Coalition Formation; Measures in Networks; and Cooperation, Networks and Complexity. Coalition formation is important in everyday life, in particular in politics. After elections in systems of proportional allocation (of seats in parliament) one has to form a government by forming a coalition. However, not all coalitions of agents are possible, since some relational structures that agents belong to may prevent the formation of some coalitions. Coalition formation is embedded in networks, in which different agents have different impacts which can and should be measured by appropriate indices or measures. Social software and some techniques of multi-criteria decision-making appear to be a very useful tool to make application of our new procedures for coalition and network formation realistic. We intend to investigate more general non-symmetric models of network formation, and to determine sufficient and necessary conditions for stability and efficiency of these networks. In particular, models with different benefit functions and different costs of forming a link will be studied. We aim to develop a new general procedure for coalition formation, which integrates ideas from different models of coalition formation, in particular, from a model of a stable government, a model of coherent coalitional agreements, and from a consensus model. One of the main issues is to develop a procedure for coalition formation with fuzzy and uncertain preferences of parties. We will compare, theoretically and empirically, the different coalition formation models. We aim to develop different measures, like influence, success, and power measures, that take into account the social network, the mutual influences of the players and the procedural aspects of collective decision-making in a large organization. Measures in a social network with some uncertainty aspects will be developed. Furthermore, we intend to introduce some dynamic aspects to the framework of influence and to analyze the series of influence functions. We want to deliver axiomatic characterizations of these measures, and to apply the new measures to network and coalition formation. We aim to define and study various allocation rules for TU-games with restricted communication. More specifically, we intend to extend the average tree solution introduced in the literature, for cycle-free communication graphs in the following directions: we will generalize the average tree solution for cooperative games with an arbitrary communication graph; we will study tree solutions in which the weights of the rooted spanning trees can be different; we will consider acyclic orientations of the communication graph instead of rooted spanning trees. We aim to study various aspects of the algorithmic complexity of allocation rules. We intend to determine whether restrictions of the communication possibilities can induce significant gains in terms of computational complexity. Within the framework of distributed computing, we plan to study the complexity of creation of the rooted spanning trees from which the average tree solution is defined. We also plan to provide decentralized mechanisms in order to compute the above mentioned allocation rules. Apart from the theoretical study, we will conduct also empirical and experimental research. A number of coalition theories will be tested in the project. Based on the European data, it will be checked empirically whether the coalitions actually formed are coherent, respectively stable, or not. Moreover, we intend to conduct experiments on coalition formation and on measuring influence in networks. Although the project is officially a collaboration between the researchers of three CNRS laboratories, GATE, CES, and CREUSET, one of the main aims of the project is to cooperate with researchers from Dutch Institute on Social Choice Theory, which is an official cooperative body of researchers from several Dutch universities and academies. The research program of this institute focuses on decision-making processes and procedures, applications of Social Choice Theory, and characterization and quantification of influence in strategic networks.