Formation of Stable Strategic Networks with Desired Topologies

• Many real-world networks, such as social networks, consist of strategic agents. The topology of these networks often plays a crucial role in determining the ease and speed with which certain information-driven tasks can be accomplished. Consequently, growing a stable network of a certain desired topology is of interest. Motivated by this, we study the following important problem: Given a certain desired topology, under what conditions would best response link alteration strategies adopted by strategic agents lead to formation of a stable network having the given topology and no other topology. This problem is the inverse of the classical network formation problem where we are concerned with determining stable topologies, given the conditions on the network parameters. We study this interesting inverse problem by proposing (1) a recursive model of network formation and (2) a utility model that captures key determinants of network formation. Building upon these models, we explore relevant topologies such as star graph complete graph, bipartite Turán graph, and multiple stars with interconnected centres. We derive a set of sufficient conditions under which these topologies uniquely emerge, study their social welfare properties and investigate the effects of deviating from the derived conditions.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Bioinformatik (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Bioinformatics (hsv//eng)

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Reglerteknik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Control Engineering (hsv//eng)

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)

Keyword

Strategic networks

pairwise stability

game theory

social welfare

Network formation

graph edit distance

network topology

Publication and Content Type

art (subject category)

ref (subject category)