Design and Analysis of Networks under Strategic Behavior

Networks are enablers, allowing the diffusion of valuable information. But just as a network is a conduit for valuable information, so it is for misinformation. One major challenge in a networked environment is limiting the spread of misinformation. Consider a large online social network, such as Twitter. Unethical users spread antisocial posts, which negatively affect other users and damage community dynamics [6], fraudsters send spam and phishing emails that threaten people's financial security [7], accounts occupied by malicious parties spread toxic information (e.g., hate speech, fake news), stirring up controversy and manipulating political views among social network users [1], fake reviews posted by bots mislead consumers' decision making [15], etc. An intuitive idea to limit the spread of misinformation is removing malicious nodes from networks, for example, terminate accounts on Twitter that spread spam. Importantly, a principled method to decide which nodes to remove from a network has wide applications; in the case of infectious disease, the inoculation of a group of people is essentially "removing" them from the contagion network [2, 5, 8, 12, 16-19]. A critical observation is that the loss associated with a decision whether to remove a node depends both on the node's likelihood of being malicious and its local network structure. Consequently, the typical approach in which we simply classify nodes as malicious or benign using a threshold on the associated maliciousness probability [10] is inadequate, as it fails to account for network consequences of such decisions. Rather, the problem is fundamentally about choosing which subset of nodes to remove, as decisions about removing individual nodes are no longer independent. We developed a model that provides decisions about which nodes to remove [20]. The model considers both the likelihood of nodes being malicious and their local network structures. Several algorithmic insights are derived from studying the model, including hardness results, as well as approximation algorithms. Our ongoing effort focuses on making the model scalable to large-scale networks. Another challenge in a networked environment arises when taking individuals' strategic behavior into account. When facing strategic individuals, game theory is a powerful tool to model their interaction. Many game-theoretic models have been proposed to model strategic behavior on networks, e.g., graphical games [13], networked public goods game [3, 4, 11], etc. Among these models, the research on equilibrium outcomes has attracted much attention. In particular, equilibrium outcomes are not always socially preferable. When the equilibrium outcomes are not socially preferable, a principal may be interested in changing the parameters of the game